1 //===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains the SplitAnalysis class as well as mutator functions for
11 // live range splitting.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "regalloc"
17 #include "LiveRangeEdit.h"
18 #include "VirtRegMap.h"
19 #include "llvm/CodeGen/CalcSpillWeights.h"
20 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
21 #include "llvm/CodeGen/MachineDominators.h"
22 #include "llvm/CodeGen/MachineInstrBuilder.h"
23 #include "llvm/CodeGen/MachineRegisterInfo.h"
24 #include "llvm/Support/CommandLine.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include "llvm/Target/TargetInstrInfo.h"
28 #include "llvm/Target/TargetMachine.h"
33 AllowSplit("spiller-splits-edges",
34 cl::desc("Allow critical edge splitting during spilling"));
36 //===----------------------------------------------------------------------===//
38 //===----------------------------------------------------------------------===//
40 SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm,
41 const LiveIntervals &lis,
42 const MachineLoopInfo &mli)
43 : MF(vrm.getMachineFunction()),
47 TII(*MF.getTarget().getInstrInfo()),
50 void SplitAnalysis::clear() {
58 bool SplitAnalysis::canAnalyzeBranch(const MachineBasicBlock *MBB) {
59 MachineBasicBlock *T, *F;
60 SmallVector<MachineOperand, 4> Cond;
61 return !TII.AnalyzeBranch(const_cast<MachineBasicBlock&>(*MBB), T, F, Cond);
64 /// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
65 void SplitAnalysis::analyzeUses() {
66 const MachineRegisterInfo &MRI = MF.getRegInfo();
67 for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(CurLI->reg),
68 E = MRI.reg_end(); I != E; ++I) {
69 MachineOperand &MO = I.getOperand();
70 if (MO.isUse() && MO.isUndef())
72 MachineInstr *MI = MO.getParent();
73 if (MI->isDebugValue() || !UsingInstrs.insert(MI))
75 UseSlots.push_back(LIS.getInstructionIndex(MI).getDefIndex());
76 MachineBasicBlock *MBB = MI->getParent();
79 array_pod_sort(UseSlots.begin(), UseSlots.end());
81 DEBUG(dbgs() << " counted "
82 << UsingInstrs.size() << " instrs, "
83 << UsingBlocks.size() << " blocks.\n");
86 /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
87 /// where CurLI is live.
88 void SplitAnalysis::calcLiveBlockInfo() {
92 LiveInterval::const_iterator LVI = CurLI->begin();
93 LiveInterval::const_iterator LVE = CurLI->end();
95 SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
96 UseI = UseSlots.begin();
97 UseE = UseSlots.end();
99 // Loop over basic blocks where CurLI is live.
100 MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start);
104 SlotIndex Start, Stop;
105 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
107 // The last split point is the latest possible insertion point that dominates
108 // all successor blocks. If interference reaches LastSplitPoint, it is not
109 // possible to insert a split or reload that makes CurLI live in the
111 MachineBasicBlock::iterator LSP = LIS.getLastSplitPoint(*CurLI, BI.MBB);
112 if (LSP == BI.MBB->end())
113 BI.LastSplitPoint = Stop;
115 BI.LastSplitPoint = LIS.getInstructionIndex(LSP);
117 // LVI is the first live segment overlapping MBB.
118 BI.LiveIn = LVI->start <= Start;
122 // Find the first and last uses in the block.
123 BI.Uses = hasUses(MFI);
124 if (BI.Uses && UseI != UseE) {
126 assert(BI.FirstUse >= Start);
128 while (UseI != UseE && *UseI < Stop);
129 BI.LastUse = UseI[-1];
130 assert(BI.LastUse < Stop);
133 // Look for gaps in the live range.
136 while (LVI->end < Stop) {
137 SlotIndex LastStop = LVI->end;
138 if (++LVI == LVE || LVI->start >= Stop) {
143 if (LastStop < LVI->start) {
150 // Don't set LiveThrough when the block has a gap.
151 BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut;
152 LiveBlocks.push_back(BI);
154 // LVI is now at LVE or LVI->end >= Stop.
158 // Live segment ends exactly at Stop. Move to the next segment.
159 if (LVI->end == Stop && ++LVI == LVE)
162 // Pick the next basic block.
163 if (LVI->start < Stop)
166 MFI = LIS.getMBBFromIndex(LVI->start);
170 bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {
171 unsigned OrigReg = VRM.getOriginal(CurLI->reg);
172 const LiveInterval &Orig = LIS.getInterval(OrigReg);
173 assert(!Orig.empty() && "Splitting empty interval?");
174 LiveInterval::const_iterator I = Orig.find(Idx);
176 // Range containing Idx should begin at Idx.
177 if (I != Orig.end() && I->start <= Idx)
178 return I->start == Idx;
180 // Range does not contain Idx, previous must end at Idx.
181 return I != Orig.begin() && (--I)->end == Idx;
184 void SplitAnalysis::print(const BlockPtrSet &B, raw_ostream &OS) const {
185 for (BlockPtrSet::const_iterator I = B.begin(), E = B.end(); I != E; ++I) {
186 unsigned count = UsingBlocks.lookup(*I);
187 OS << " BB#" << (*I)->getNumber();
189 OS << '(' << count << ')';
193 void SplitAnalysis::analyze(const LiveInterval *li) {
200 //===----------------------------------------------------------------------===//
202 //===----------------------------------------------------------------------===//
204 // Work around the fact that the std::pair constructors are broken for pointer
205 // pairs in some implementations. makeVV(x, 0) works.
206 static inline std::pair<const VNInfo*, VNInfo*>
207 makeVV(const VNInfo *a, VNInfo *b) {
208 return std::make_pair(a, b);
211 void LiveIntervalMap::reset(LiveInterval *li) {
213 LiveOutCache.clear();
217 // mapValue - Find the mapped value for ParentVNI at Idx.
218 // Potentially create phi-def values.
219 VNInfo *LiveIntervalMap::mapValue(const VNInfo *ParentVNI, SlotIndex Idx,
221 assert(LI && "call reset first");
222 assert(ParentVNI && "Mapping NULL value");
223 assert(Idx.isValid() && "Invalid SlotIndex");
224 assert(ParentLI.getVNInfoAt(Idx) == ParentVNI && "Bad ParentVNI");
226 // This is a complex mapped value. There may be multiple defs, and we may need
227 // to create phi-defs.
228 if (simple) *simple = false;
229 MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx);
230 assert(IdxMBB && "No MBB at Idx");
232 // Is there a def in the same MBB we can extend?
233 if (VNInfo *VNI = extendTo(IdxMBB, Idx))
236 // Now for the fun part. We know that ParentVNI potentially has multiple defs,
237 // and we may need to create even more phi-defs to preserve VNInfo SSA form.
238 // Perform a search for all predecessor blocks where we know the dominating
239 // VNInfo. Insert phi-def VNInfos along the path back to IdxMBB.
240 DEBUG(dbgs() << "\n Reaching defs for BB#" << IdxMBB->getNumber()
241 << " at " << Idx << " in " << *LI << '\n');
243 // Blocks where LI should be live-in.
244 SmallVector<MachineDomTreeNode*, 16> LiveIn;
245 LiveIn.push_back(MDT[IdxMBB]);
247 // Using LiveOutCache as a visited set, perform a BFS for all reaching defs.
248 for (unsigned i = 0; i != LiveIn.size(); ++i) {
249 MachineBasicBlock *MBB = LiveIn[i]->getBlock();
250 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
251 PE = MBB->pred_end(); PI != PE; ++PI) {
252 MachineBasicBlock *Pred = *PI;
253 // Is this a known live-out block?
254 std::pair<LiveOutMap::iterator,bool> LOIP =
255 LiveOutCache.insert(std::make_pair(Pred, LiveOutPair()));
256 // Yes, we have been here before.
258 DEBUG(if (VNInfo *VNI = LOIP.first->second.first)
259 dbgs() << " known valno #" << VNI->id
260 << " at BB#" << Pred->getNumber() << '\n');
264 // Does Pred provide a live-out value?
265 SlotIndex Last = LIS.getMBBEndIdx(Pred).getPrevSlot();
266 if (VNInfo *VNI = extendTo(Pred, Last)) {
267 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(VNI->def);
268 DEBUG(dbgs() << " found valno #" << VNI->id
269 << " from BB#" << DefMBB->getNumber()
270 << " at BB#" << Pred->getNumber() << '\n');
271 LiveOutPair &LOP = LOIP.first->second;
273 LOP.second = MDT[DefMBB];
276 // No, we need a live-in value for Pred as well
278 LiveIn.push_back(MDT[Pred]);
282 // We may need to add phi-def values to preserve the SSA form.
283 // This is essentially the same iterative algorithm that SSAUpdater uses,
284 // except we already have a dominator tree, so we don't have to recompute it.
289 DEBUG(dbgs() << " Iterating over " << LiveIn.size() << " blocks.\n");
290 // Propagate live-out values down the dominator tree, inserting phi-defs when
291 // necessary. Since LiveIn was created by a BFS, going backwards makes it more
292 // likely for us to visit immediate dominators before their children.
293 for (unsigned i = LiveIn.size(); i; --i) {
294 MachineDomTreeNode *Node = LiveIn[i-1];
295 MachineBasicBlock *MBB = Node->getBlock();
296 MachineDomTreeNode *IDom = Node->getIDom();
297 LiveOutPair IDomValue;
298 // We need a live-in value to a block with no immediate dominator?
299 // This is probably an unreachable block that has survived somehow.
300 bool needPHI = !IDom;
302 // Get the IDom live-out value.
304 LiveOutMap::iterator I = LiveOutCache.find(IDom->getBlock());
305 if (I != LiveOutCache.end())
306 IDomValue = I->second;
308 // If IDom is outside our set of live-out blocks, there must be new
309 // defs, and we need a phi-def here.
313 // IDom dominates all of our predecessors, but it may not be the immediate
314 // dominator. Check if any of them have live-out values that are properly
315 // dominated by IDom. If so, we need a phi-def here.
317 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
318 PE = MBB->pred_end(); PI != PE; ++PI) {
319 LiveOutPair Value = LiveOutCache[*PI];
320 if (!Value.first || Value.first == IDomValue.first)
322 // This predecessor is carrying something other than IDomValue.
323 // It could be because IDomValue hasn't propagated yet, or it could be
324 // because MBB is in the dominance frontier of that value.
325 if (MDT.dominates(IDom, Value.second)) {
332 // Create a phi-def if required.
335 SlotIndex Start = LIS.getMBBStartIdx(MBB);
336 VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator());
337 VNI->setIsPHIDef(true);
338 DEBUG(dbgs() << " - BB#" << MBB->getNumber()
339 << " phi-def #" << VNI->id << " at " << Start << '\n');
340 // We no longer need LI to be live-in.
341 LiveIn.erase(LiveIn.begin()+(i-1));
342 // Blocks in LiveIn are either IdxMBB, or have a value live-through.
345 // Check if we need to update live-out info.
346 LiveOutMap::iterator I = LiveOutCache.find(MBB);
347 if (I == LiveOutCache.end() || I->second.second == Node) {
348 // We already have a live-out defined in MBB, so this must be IdxMBB.
349 assert(MBB == IdxMBB && "Adding phi-def to known live-out");
350 LI->addRange(LiveRange(Start, Idx.getNextSlot(), VNI));
352 // This phi-def is also live-out, so color the whole block.
353 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
354 I->second = LiveOutPair(VNI, Node);
356 } else if (IDomValue.first) {
357 // No phi-def here. Remember incoming value for IdxMBB.
359 IdxVNI = IDomValue.first;
360 // Propagate IDomValue if needed:
361 // MBB is live-out and doesn't define its own value.
362 LiveOutMap::iterator I = LiveOutCache.find(MBB);
363 if (I != LiveOutCache.end() && I->second.second != Node &&
364 I->second.first != IDomValue.first) {
366 I->second = IDomValue;
367 DEBUG(dbgs() << " - BB#" << MBB->getNumber()
368 << " idom valno #" << IDomValue.first->id
369 << " from BB#" << IDom->getBlock()->getNumber() << '\n');
373 DEBUG(dbgs() << " - made " << Changes << " changes.\n");
376 assert(IdxVNI && "Didn't find value for Idx");
379 // Check the LiveOutCache invariants.
380 for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end();
382 assert(I->first && "Null MBB entry in cache");
383 assert(I->second.first && "Null VNInfo in cache");
384 assert(I->second.second && "Null DomTreeNode in cache");
385 if (I->second.second->getBlock() == I->first)
387 for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(),
388 PE = I->first->pred_end(); PI != PE; ++PI)
389 assert(LiveOutCache.lookup(*PI) == I->second && "Bad invariant");
393 // Since we went through the trouble of a full BFS visiting all reaching defs,
394 // the values in LiveIn are now accurate. No more phi-defs are needed
395 // for these blocks, so we can color the live ranges.
396 // This makes the next mapValue call much faster.
397 for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) {
398 MachineBasicBlock *MBB = LiveIn[i]->getBlock();
399 SlotIndex Start = LIS.getMBBStartIdx(MBB);
400 VNInfo *VNI = LiveOutCache.lookup(MBB).first;
402 // Anything in LiveIn other than IdxMBB is live-through.
403 // In IdxMBB, we should stop at Idx unless the same value is live-out.
404 if (MBB == IdxMBB && IdxVNI != VNI)
405 LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI));
407 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
414 void LiveIntervalMap::dumpCache() {
415 for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end();
417 assert(I->first && "Null MBB entry in cache");
418 assert(I->second.first && "Null VNInfo in cache");
419 assert(I->second.second && "Null DomTreeNode in cache");
420 dbgs() << " cache: BB#" << I->first->getNumber()
421 << " has valno #" << I->second.first->id << " from BB#"
422 << I->second.second->getBlock()->getNumber() << ", preds";
423 for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(),
424 PE = I->first->pred_end(); PI != PE; ++PI)
425 dbgs() << " BB#" << (*PI)->getNumber();
428 dbgs() << " cache: " << LiveOutCache.size() << " entries.\n";
432 // extendTo - Find the last LI value defined in MBB at or before Idx. The
433 // ParentLI is assumed to be live at Idx. Extend the live range to Idx.
434 // Return the found VNInfo, or NULL.
435 VNInfo *LiveIntervalMap::extendTo(const MachineBasicBlock *MBB, SlotIndex Idx) {
436 assert(LI && "call reset first");
437 LiveInterval::iterator I = std::upper_bound(LI->begin(), LI->end(), Idx);
438 if (I == LI->begin())
441 if (I->end <= LIS.getMBBStartIdx(MBB))
444 I->end = Idx.getNextSlot();
449 //===----------------------------------------------------------------------===//
451 //===----------------------------------------------------------------------===//
453 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
454 SplitEditor::SplitEditor(SplitAnalysis &sa,
457 MachineDominatorTree &mdt,
459 : SA(sa), LIS(lis), VRM(vrm),
460 MRI(vrm.getMachineFunction().getRegInfo()),
462 TII(*vrm.getMachineFunction().getTarget().getInstrInfo()),
463 TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()),
468 // We don't need an AliasAnalysis since we will only be performing
469 // cheap-as-a-copy remats anyway.
470 Edit.anyRematerializable(LIS, TII, 0);
473 void SplitEditor::dump() const {
474 if (RegAssign.empty()) {
475 dbgs() << " empty\n";
479 for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
480 dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
484 VNInfo *SplitEditor::defValue(unsigned RegIdx,
485 const VNInfo *ParentVNI,
487 assert(ParentVNI && "Mapping NULL value");
488 assert(Idx.isValid() && "Invalid SlotIndex");
489 assert(Edit.getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
490 LiveInterval *LI = Edit.get(RegIdx);
492 // Create a new value.
493 VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator());
495 // Preserve the PHIDef bit.
496 if (ParentVNI->isPHIDef() && Idx == ParentVNI->def)
497 VNI->setIsPHIDef(true);
499 // Use insert for lookup, so we can add missing values with a second lookup.
500 std::pair<ValueMap::iterator, bool> InsP =
501 Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI));
503 // This was the first time (RegIdx, ParentVNI) was mapped.
504 // Keep it as a simple def without any liveness.
508 // If the previous value was a simple mapping, add liveness for it now.
509 if (VNInfo *OldVNI = InsP.first->second) {
510 SlotIndex Def = OldVNI->def;
511 LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI));
512 // No longer a simple mapping.
513 InsP.first->second = 0;
516 // This is a complex mapping, add liveness for VNI
517 SlotIndex Def = VNI->def;
518 LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
523 void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) {
524 assert(ParentVNI && "Mapping NULL value");
525 VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)];
527 // ParentVNI was either unmapped or already complex mapped. Either way.
531 // This was previously a single mapping. Make sure the old def is represented
532 // by a trivial live range.
533 SlotIndex Def = VNI->def;
534 Edit.get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
538 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
541 MachineBasicBlock &MBB,
542 MachineBasicBlock::iterator I) {
543 MachineInstr *CopyMI = 0;
545 LiveInterval *LI = Edit.get(RegIdx);
547 // Attempt cheap-as-a-copy rematerialization.
548 LiveRangeEdit::Remat RM(ParentVNI);
549 if (Edit.canRematerializeAt(RM, UseIdx, true, LIS)) {
550 Def = Edit.rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI);
552 // Can't remat, just insert a copy from parent.
553 CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
554 .addReg(Edit.getReg());
555 Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex();
558 // Temporarily mark all values as complex mapped.
559 markComplexMapped(RegIdx, ParentVNI);
561 // Define the value in Reg.
562 VNInfo *VNI = defValue(RegIdx, ParentVNI, Def);
563 VNI->setCopy(CopyMI);
567 /// Create a new virtual register and live interval.
568 void SplitEditor::openIntv() {
569 assert(!OpenIdx && "Previous LI not closed before openIntv");
571 // Create the complement as index 0.
573 Edit.create(MRI, LIS, VRM);
574 LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent()));
575 LIMappers.back().reset(Edit.get(0));
578 // Create the open interval.
579 OpenIdx = Edit.size();
580 Edit.create(MRI, LIS, VRM);
581 LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent()));
582 LIMappers[OpenIdx].reset(Edit.get(OpenIdx));
585 SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
586 assert(OpenIdx && "openIntv not called before enterIntvBefore");
587 DEBUG(dbgs() << " enterIntvBefore " << Idx);
588 Idx = Idx.getBaseIndex();
589 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
591 DEBUG(dbgs() << ": not live\n");
594 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
595 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
596 assert(MI && "enterIntvBefore called with invalid index");
598 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
602 SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
603 assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
604 SlotIndex End = LIS.getMBBEndIdx(&MBB);
605 SlotIndex Last = End.getPrevSlot();
606 DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last);
607 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Last);
609 DEBUG(dbgs() << ": not live\n");
612 DEBUG(dbgs() << ": valno " << ParentVNI->id);
613 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
614 LIS.getLastSplitPoint(Edit.getParent(), &MBB));
615 RegAssign.insert(VNI->def, End, OpenIdx);
620 /// useIntv - indicate that all instructions in MBB should use OpenLI.
621 void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
622 useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));
625 void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
626 assert(OpenIdx && "openIntv not called before useIntv");
627 DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):");
628 RegAssign.insert(Start, End, OpenIdx);
632 SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {
633 assert(OpenIdx && "openIntv not called before leaveIntvAfter");
634 DEBUG(dbgs() << " leaveIntvAfter " << Idx);
636 // The interval must be live beyond the instruction at Idx.
637 Idx = Idx.getBoundaryIndex();
638 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
640 DEBUG(dbgs() << ": not live\n");
641 return Idx.getNextSlot();
643 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
645 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
646 assert(MI && "No instruction at index");
647 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(),
648 llvm::next(MachineBasicBlock::iterator(MI)));
652 SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {
653 assert(OpenIdx && "openIntv not called before leaveIntvBefore");
654 DEBUG(dbgs() << " leaveIntvBefore " << Idx);
656 // The interval must be live into the instruction at Idx.
657 Idx = Idx.getBoundaryIndex();
658 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
660 DEBUG(dbgs() << ": not live\n");
661 return Idx.getNextSlot();
663 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
665 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
666 assert(MI && "No instruction at index");
667 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
671 SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
672 assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
673 SlotIndex Start = LIS.getMBBStartIdx(&MBB);
674 DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start);
676 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Start);
678 DEBUG(dbgs() << ": not live\n");
682 VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
683 MBB.SkipPHIsAndLabels(MBB.begin()));
684 RegAssign.insert(Start, VNI->def, OpenIdx);
689 void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
690 assert(OpenIdx && "openIntv not called before overlapIntv");
691 assert(Edit.getParent().getVNInfoAt(Start) ==
692 Edit.getParent().getVNInfoAt(End.getPrevSlot()) &&
693 "Parent changes value in extended range");
694 assert(Edit.get(0)->getVNInfoAt(Start) && "Start must come from leaveIntv*");
695 assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
696 "Range cannot span basic blocks");
698 // Treat this as useIntv() for now. The complement interval will be extended
699 // as needed by mapValue().
700 DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):");
701 RegAssign.insert(Start, End, OpenIdx);
705 /// closeIntv - Indicate that we are done editing the currently open
706 /// LiveInterval, and ranges can be trimmed.
707 void SplitEditor::closeIntv() {
708 assert(OpenIdx && "openIntv not called before closeIntv");
712 /// rewriteAssigned - Rewrite all uses of Edit.getReg().
713 void SplitEditor::rewriteAssigned() {
714 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit.getReg()),
715 RE = MRI.reg_end(); RI != RE;) {
716 MachineOperand &MO = RI.getOperand();
717 MachineInstr *MI = MO.getParent();
719 // LiveDebugVariables should have handled all DBG_VALUE instructions.
720 if (MI->isDebugValue()) {
721 DEBUG(dbgs() << "Zapping " << *MI);
726 // <undef> operands don't really read the register, so just assign them to
728 if (MO.isUse() && MO.isUndef()) {
729 MO.setReg(Edit.get(0)->reg);
733 SlotIndex Idx = LIS.getInstructionIndex(MI);
734 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
736 // Rewrite to the mapped register at Idx.
737 unsigned RegIdx = RegAssign.lookup(Idx);
738 MO.setReg(Edit.get(RegIdx)->reg);
739 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t'
740 << Idx << ':' << RegIdx << '\t' << *MI);
742 // Extend liveness to Idx.
743 const VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
744 LIMappers[RegIdx].mapValue(ParentVNI, Idx);
748 /// rewriteSplit - Rewrite uses of Intvs[0] according to the ConEQ mapping.
749 void SplitEditor::rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs,
750 const ConnectedVNInfoEqClasses &ConEq) {
751 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Intvs[0]->reg),
752 RE = MRI.reg_end(); RI != RE;) {
753 MachineOperand &MO = RI.getOperand();
754 MachineInstr *MI = MO.getParent();
756 if (MO.isUse() && MO.isUndef())
758 // DBG_VALUE instructions should have been eliminated earlier.
759 SlotIndex Idx = LIS.getInstructionIndex(MI);
760 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
761 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t'
763 const VNInfo *VNI = Intvs[0]->getVNInfoAt(Idx);
764 assert(VNI && "Interval not live at use.");
765 MO.setReg(Intvs[ConEq.getEqClass(VNI)]->reg);
766 DEBUG(dbgs() << VNI->id << '\t' << *MI);
770 void SplitEditor::finish() {
771 assert(OpenIdx == 0 && "Previous LI not closed before rewrite");
773 // At this point, the live intervals in Edit contain VNInfos corresponding to
774 // the inserted copies.
776 // Add the original defs from the parent interval.
777 for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(),
778 E = Edit.getParent().vni_end(); I != E; ++I) {
779 const VNInfo *ParentVNI = *I;
780 if (ParentVNI->isUnused())
782 unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
783 // Mark all values as complex to force liveness computation.
784 // This should really only be necessary for remat victims, but we are lazy.
785 markComplexMapped(RegIdx, ParentVNI);
786 defValue(RegIdx, ParentVNI, ParentVNI->def);
790 // Every new interval must have a def by now, otherwise the split is bogus.
791 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I)
792 assert((*I)->hasAtLeastOneValue() && "Split interval has no value");
795 // FIXME: Don't recompute the liveness of all values, infer it from the
796 // overlaps between the parent live interval and RegAssign.
797 // The mapValue algorithm is only necessary when:
798 // - The parent value maps to multiple defs, and new phis are needed, or
799 // - The value has been rematerialized before some uses, and we want to
800 // minimize the live range so it only reaches the remaining uses.
801 // All other values have simple liveness that can be computed from RegAssign
802 // and the parent live interval.
804 // Extend live ranges to be live-out for successor PHI values.
805 for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(),
806 E = Edit.getParent().vni_end(); I != E; ++I) {
807 const VNInfo *PHIVNI = *I;
808 if (PHIVNI->isUnused() || !PHIVNI->isPHIDef())
810 unsigned RegIdx = RegAssign.lookup(PHIVNI->def);
811 LiveIntervalMap &LIM = LIMappers[RegIdx];
812 MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def);
813 DEBUG(dbgs() << " map phi in BB#" << MBB->getNumber() << '@' << PHIVNI->def
814 << " -> " << RegIdx << '\n');
815 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
816 PE = MBB->pred_end(); PI != PE; ++PI) {
817 SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot();
818 DEBUG(dbgs() << " pred BB#" << (*PI)->getNumber() << '@' << End);
819 // The predecessor may not have a live-out value. That is OK, like an
820 // undef PHI operand.
821 if (VNInfo *VNI = Edit.getParent().getVNInfoAt(End)) {
822 DEBUG(dbgs() << " has parent valno #" << VNI->id << " live out\n");
823 assert(RegAssign.lookup(End) == RegIdx &&
824 "Different register assignment in phi predecessor");
825 LIM.mapValue(VNI, End);
828 DEBUG(dbgs() << " is not live-out\n");
830 DEBUG(dbgs() << " " << *LIM.getLI() << '\n');
833 // Rewrite instructions.
836 // FIXME: Delete defs that were rematted everywhere.
838 // Get rid of unused values and set phi-kill flags.
839 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I)
840 (*I)->RenumberValues(LIS);
842 // Now check if any registers were separated into multiple components.
843 ConnectedVNInfoEqClasses ConEQ(LIS);
844 for (unsigned i = 0, e = Edit.size(); i != e; ++i) {
845 // Don't use iterators, they are invalidated by create() below.
846 LiveInterval *li = Edit.get(i);
847 unsigned NumComp = ConEQ.Classify(li);
850 DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n');
851 SmallVector<LiveInterval*, 8> dups;
853 for (unsigned i = 1; i != NumComp; ++i)
854 dups.push_back(&Edit.create(MRI, LIS, VRM));
855 rewriteComponents(dups, ConEQ);
856 ConEQ.Distribute(&dups[0]);
859 // Calculate spill weight and allocation hints for new intervals.
860 VirtRegAuxInfo vrai(VRM.getMachineFunction(), LIS, SA.Loops);
861 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I){
862 LiveInterval &li = **I;
863 vrai.CalculateRegClass(li.reg);
864 vrai.CalculateWeightAndHint(li);
865 DEBUG(dbgs() << " new interval " << MRI.getRegClass(li.reg)->getName()
866 << ":" << li << '\n');
871 //===----------------------------------------------------------------------===//
872 // Single Block Splitting
873 //===----------------------------------------------------------------------===//
875 /// getMultiUseBlocks - if CurLI has more than one use in a basic block, it
876 /// may be an advantage to split CurLI for the duration of the block.
877 bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) {
878 // If CurLI is local to one block, there is no point to splitting it.
879 if (LiveBlocks.size() <= 1)
881 // Add blocks with multiple uses.
882 for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
883 const BlockInfo &BI = LiveBlocks[i];
886 unsigned Instrs = UsingBlocks.lookup(BI.MBB);
889 if (Instrs == 2 && BI.LiveIn && BI.LiveOut && !BI.LiveThrough)
891 Blocks.insert(BI.MBB);
893 return !Blocks.empty();
896 /// splitSingleBlocks - Split CurLI into a separate live interval inside each
897 /// basic block in Blocks.
898 void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) {
899 DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n");
901 for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) {
902 const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i];
903 if (!BI.Uses || !Blocks.count(BI.MBB))
907 SlotIndex SegStart = enterIntvBefore(BI.FirstUse);
908 if (!BI.LiveOut || BI.LastUse < BI.LastSplitPoint) {
909 useIntv(SegStart, leaveIntvAfter(BI.LastUse));
911 // The last use is after the last valid split point.
912 SlotIndex SegStop = leaveIntvBefore(BI.LastSplitPoint);
913 useIntv(SegStart, SegStop);
914 overlapIntv(SegStop, BI.LastUse);