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 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
205 SplitEditor::SplitEditor(SplitAnalysis &sa,
208 MachineDominatorTree &mdt,
210 : SA(sa), LIS(lis), VRM(vrm),
211 MRI(vrm.getMachineFunction().getRegInfo()),
213 TII(*vrm.getMachineFunction().getTarget().getInstrInfo()),
214 TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()),
219 // We don't need an AliasAnalysis since we will only be performing
220 // cheap-as-a-copy remats anyway.
221 Edit.anyRematerializable(LIS, TII, 0);
224 void SplitEditor::dump() const {
225 if (RegAssign.empty()) {
226 dbgs() << " empty\n";
230 for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
231 dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
235 VNInfo *SplitEditor::defValue(unsigned RegIdx,
236 const VNInfo *ParentVNI,
238 assert(ParentVNI && "Mapping NULL value");
239 assert(Idx.isValid() && "Invalid SlotIndex");
240 assert(Edit.getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
241 LiveInterval *LI = Edit.get(RegIdx);
243 // Create a new value.
244 VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator());
246 // Preserve the PHIDef bit.
247 if (ParentVNI->isPHIDef() && Idx == ParentVNI->def)
248 VNI->setIsPHIDef(true);
250 // Use insert for lookup, so we can add missing values with a second lookup.
251 std::pair<ValueMap::iterator, bool> InsP =
252 Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI));
254 // This was the first time (RegIdx, ParentVNI) was mapped.
255 // Keep it as a simple def without any liveness.
259 // If the previous value was a simple mapping, add liveness for it now.
260 if (VNInfo *OldVNI = InsP.first->second) {
261 SlotIndex Def = OldVNI->def;
262 LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI));
263 // No longer a simple mapping.
264 InsP.first->second = 0;
267 // This is a complex mapping, add liveness for VNI
268 SlotIndex Def = VNI->def;
269 LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
274 void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) {
275 assert(ParentVNI && "Mapping NULL value");
276 VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)];
278 // ParentVNI was either unmapped or already complex mapped. Either way.
282 // This was previously a single mapping. Make sure the old def is represented
283 // by a trivial live range.
284 SlotIndex Def = VNI->def;
285 Edit.get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
289 // extendRange - Extend the live range to reach Idx.
290 // Potentially create phi-def values.
291 void SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) {
292 assert(Idx.isValid() && "Invalid SlotIndex");
293 MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx);
294 assert(IdxMBB && "No MBB at Idx");
295 LiveInterval *LI = Edit.get(RegIdx);
297 // Is there a def in the same MBB we can extend?
298 if (LI->extendInBlock(LIS.getMBBStartIdx(IdxMBB), Idx))
301 // Now for the fun part. We know that ParentVNI potentially has multiple defs,
302 // and we may need to create even more phi-defs to preserve VNInfo SSA form.
303 // Perform a search for all predecessor blocks where we know the dominating
304 // VNInfo. Insert phi-def VNInfos along the path back to IdxMBB.
305 DEBUG(dbgs() << "\n Reaching defs for BB#" << IdxMBB->getNumber()
306 << " at " << Idx << " in " << *LI << '\n');
308 // Blocks where LI should be live-in.
309 SmallVector<MachineDomTreeNode*, 16> LiveIn;
310 LiveIn.push_back(MDT[IdxMBB]);
312 // Using LiveOutCache as a visited set, perform a BFS for all reaching defs.
313 for (unsigned i = 0; i != LiveIn.size(); ++i) {
314 MachineBasicBlock *MBB = LiveIn[i]->getBlock();
315 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
316 PE = MBB->pred_end(); PI != PE; ++PI) {
317 MachineBasicBlock *Pred = *PI;
318 // Is this a known live-out block?
319 std::pair<LiveOutMap::iterator,bool> LOIP =
320 LiveOutCache.insert(std::make_pair(Pred, LiveOutPair()));
321 // Yes, we have been here before.
325 // Does Pred provide a live-out value?
326 SlotIndex Start, Last;
327 tie(Start, Last) = LIS.getSlotIndexes()->getMBBRange(Pred);
328 Last = Last.getPrevSlot();
329 if (VNInfo *VNI = LI->extendInBlock(Start, Last)) {
330 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(VNI->def);
331 LiveOutPair &LOP = LOIP.first->second;
333 LOP.second = MDT[DefMBB];
336 // No, we need a live-in value for Pred as well
338 LiveIn.push_back(MDT[Pred]);
342 // We may need to add phi-def values to preserve the SSA form.
343 VNInfo *IdxVNI = updateSSA(RegIdx, LiveIn, Idx, IdxMBB);
346 // Check the LiveOutCache invariants.
347 for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end();
349 assert(I->first && "Null MBB entry in cache");
350 assert(I->second.first && "Null VNInfo in cache");
351 assert(I->second.second && "Null DomTreeNode in cache");
352 if (I->second.second->getBlock() == I->first)
354 for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(),
355 PE = I->first->pred_end(); PI != PE; ++PI)
356 assert(LiveOutCache.lookup(*PI) == I->second && "Bad invariant");
360 // Since we went through the trouble of a full BFS visiting all reaching defs,
361 // the values in LiveIn are now accurate. No more phi-defs are needed
362 // for these blocks, so we can color the live ranges.
363 for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) {
364 MachineBasicBlock *MBB = LiveIn[i]->getBlock();
365 SlotIndex Start = LIS.getMBBStartIdx(MBB);
366 VNInfo *VNI = LiveOutCache.lookup(MBB).first;
368 // Anything in LiveIn other than IdxMBB is live-through.
369 // In IdxMBB, we should stop at Idx unless the same value is live-out.
370 if (MBB == IdxMBB && IdxVNI != VNI)
371 LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI));
373 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
377 VNInfo *SplitEditor::updateSSA(unsigned RegIdx,
378 SmallVectorImpl<MachineDomTreeNode*> &LiveIn,
380 const MachineBasicBlock *IdxMBB) {
381 // This is essentially the same iterative algorithm that SSAUpdater uses,
382 // except we already have a dominator tree, so we don't have to recompute it.
383 LiveInterval *LI = Edit.get(RegIdx);
388 DEBUG(dbgs() << " Iterating over " << LiveIn.size() << " blocks.\n");
389 // Propagate live-out values down the dominator tree, inserting phi-defs
390 // when necessary. Since LiveIn was created by a BFS, going backwards makes
391 // it more likely for us to visit immediate dominators before their
393 for (unsigned i = LiveIn.size(); i; --i) {
394 MachineDomTreeNode *Node = LiveIn[i-1];
395 MachineBasicBlock *MBB = Node->getBlock();
396 MachineDomTreeNode *IDom = Node->getIDom();
397 LiveOutPair IDomValue;
398 // We need a live-in value to a block with no immediate dominator?
399 // This is probably an unreachable block that has survived somehow.
400 bool needPHI = !IDom;
402 // Get the IDom live-out value.
404 LiveOutMap::iterator I = LiveOutCache.find(IDom->getBlock());
405 if (I != LiveOutCache.end())
406 IDomValue = I->second;
408 // If IDom is outside our set of live-out blocks, there must be new
409 // defs, and we need a phi-def here.
413 // IDom dominates all of our predecessors, but it may not be the immediate
414 // dominator. Check if any of them have live-out values that are properly
415 // dominated by IDom. If so, we need a phi-def here.
417 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
418 PE = MBB->pred_end(); PI != PE; ++PI) {
419 LiveOutPair Value = LiveOutCache[*PI];
420 if (!Value.first || Value.first == IDomValue.first)
422 // This predecessor is carrying something other than IDomValue.
423 // It could be because IDomValue hasn't propagated yet, or it could be
424 // because MBB is in the dominance frontier of that value.
425 if (MDT.dominates(IDom, Value.second)) {
432 // Create a phi-def if required.
435 SlotIndex Start = LIS.getMBBStartIdx(MBB);
436 VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator());
437 VNI->setIsPHIDef(true);
438 DEBUG(dbgs() << " - BB#" << MBB->getNumber()
439 << " phi-def #" << VNI->id << " at " << Start << '\n');
440 // We no longer need LI to be live-in.
441 LiveIn.erase(LiveIn.begin()+(i-1));
442 // Blocks in LiveIn are either IdxMBB, or have a value live-through.
445 // Check if we need to update live-out info.
446 LiveOutMap::iterator I = LiveOutCache.find(MBB);
447 if (I == LiveOutCache.end() || I->second.second == Node) {
448 // We already have a live-out defined in MBB, so this must be IdxMBB.
449 assert(MBB == IdxMBB && "Adding phi-def to known live-out");
450 LI->addRange(LiveRange(Start, Idx.getNextSlot(), VNI));
452 // This phi-def is also live-out, so color the whole block.
453 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
454 I->second = LiveOutPair(VNI, Node);
456 } else if (IDomValue.first) {
457 // No phi-def here. Remember incoming value for IdxMBB.
459 IdxVNI = IDomValue.first;
460 // Propagate IDomValue if needed:
461 // MBB is live-out and doesn't define its own value.
462 LiveOutMap::iterator I = LiveOutCache.find(MBB);
463 if (I != LiveOutCache.end() && I->second.second != Node &&
464 I->second.first != IDomValue.first) {
466 I->second = IDomValue;
467 DEBUG(dbgs() << " - BB#" << MBB->getNumber()
468 << " idom valno #" << IDomValue.first->id
469 << " from BB#" << IDom->getBlock()->getNumber() << '\n');
473 DEBUG(dbgs() << " - made " << Changes << " changes.\n");
476 assert(IdxVNI && "Didn't find value for Idx");
480 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
483 MachineBasicBlock &MBB,
484 MachineBasicBlock::iterator I) {
485 MachineInstr *CopyMI = 0;
487 LiveInterval *LI = Edit.get(RegIdx);
489 // Attempt cheap-as-a-copy rematerialization.
490 LiveRangeEdit::Remat RM(ParentVNI);
491 if (Edit.canRematerializeAt(RM, UseIdx, true, LIS)) {
492 Def = Edit.rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI);
494 // Can't remat, just insert a copy from parent.
495 CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
496 .addReg(Edit.getReg());
497 Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex();
500 // Temporarily mark all values as complex mapped.
501 markComplexMapped(RegIdx, ParentVNI);
503 // Define the value in Reg.
504 VNInfo *VNI = defValue(RegIdx, ParentVNI, Def);
505 VNI->setCopy(CopyMI);
509 /// Create a new virtual register and live interval.
510 void SplitEditor::openIntv() {
511 assert(!OpenIdx && "Previous LI not closed before openIntv");
513 // Create the complement as index 0.
515 Edit.create(MRI, LIS, VRM);
517 // Create the open interval.
518 OpenIdx = Edit.size();
519 Edit.create(MRI, LIS, VRM);
522 SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
523 assert(OpenIdx && "openIntv not called before enterIntvBefore");
524 DEBUG(dbgs() << " enterIntvBefore " << Idx);
525 Idx = Idx.getBaseIndex();
526 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
528 DEBUG(dbgs() << ": not live\n");
531 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
532 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
533 assert(MI && "enterIntvBefore called with invalid index");
535 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
539 SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
540 assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
541 SlotIndex End = LIS.getMBBEndIdx(&MBB);
542 SlotIndex Last = End.getPrevSlot();
543 DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last);
544 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Last);
546 DEBUG(dbgs() << ": not live\n");
549 DEBUG(dbgs() << ": valno " << ParentVNI->id);
550 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
551 LIS.getLastSplitPoint(Edit.getParent(), &MBB));
552 RegAssign.insert(VNI->def, End, OpenIdx);
557 /// useIntv - indicate that all instructions in MBB should use OpenLI.
558 void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
559 useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));
562 void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
563 assert(OpenIdx && "openIntv not called before useIntv");
564 DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):");
565 RegAssign.insert(Start, End, OpenIdx);
569 SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {
570 assert(OpenIdx && "openIntv not called before leaveIntvAfter");
571 DEBUG(dbgs() << " leaveIntvAfter " << Idx);
573 // The interval must be live beyond the instruction at Idx.
574 Idx = Idx.getBoundaryIndex();
575 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
577 DEBUG(dbgs() << ": not live\n");
578 return Idx.getNextSlot();
580 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
582 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
583 assert(MI && "No instruction at index");
584 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(),
585 llvm::next(MachineBasicBlock::iterator(MI)));
589 SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {
590 assert(OpenIdx && "openIntv not called before leaveIntvBefore");
591 DEBUG(dbgs() << " leaveIntvBefore " << Idx);
593 // The interval must be live into the instruction at Idx.
594 Idx = Idx.getBoundaryIndex();
595 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
597 DEBUG(dbgs() << ": not live\n");
598 return Idx.getNextSlot();
600 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
602 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
603 assert(MI && "No instruction at index");
604 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
608 SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
609 assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
610 SlotIndex Start = LIS.getMBBStartIdx(&MBB);
611 DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start);
613 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Start);
615 DEBUG(dbgs() << ": not live\n");
619 VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
620 MBB.SkipPHIsAndLabels(MBB.begin()));
621 RegAssign.insert(Start, VNI->def, OpenIdx);
626 void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
627 assert(OpenIdx && "openIntv not called before overlapIntv");
628 assert(Edit.getParent().getVNInfoAt(Start) ==
629 Edit.getParent().getVNInfoAt(End.getPrevSlot()) &&
630 "Parent changes value in extended range");
631 assert(Edit.get(0)->getVNInfoAt(Start) && "Start must come from leaveIntv*");
632 assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
633 "Range cannot span basic blocks");
635 // Treat this as useIntv() for now.
636 // The complement interval will be extended as needed by extendRange().
637 DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):");
638 RegAssign.insert(Start, End, OpenIdx);
642 /// closeIntv - Indicate that we are done editing the currently open
643 /// LiveInterval, and ranges can be trimmed.
644 void SplitEditor::closeIntv() {
645 assert(OpenIdx && "openIntv not called before closeIntv");
649 /// rewriteAssigned - Rewrite all uses of Edit.getReg().
650 void SplitEditor::rewriteAssigned() {
651 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit.getReg()),
652 RE = MRI.reg_end(); RI != RE;) {
653 MachineOperand &MO = RI.getOperand();
654 MachineInstr *MI = MO.getParent();
656 // LiveDebugVariables should have handled all DBG_VALUE instructions.
657 if (MI->isDebugValue()) {
658 DEBUG(dbgs() << "Zapping " << *MI);
663 // <undef> operands don't really read the register, so just assign them to
665 if (MO.isUse() && MO.isUndef()) {
666 MO.setReg(Edit.get(0)->reg);
670 SlotIndex Idx = LIS.getInstructionIndex(MI);
671 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
673 // Rewrite to the mapped register at Idx.
674 unsigned RegIdx = RegAssign.lookup(Idx);
675 MO.setReg(Edit.get(RegIdx)->reg);
676 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t'
677 << Idx << ':' << RegIdx << '\t' << *MI);
679 // Extend liveness to Idx.
680 extendRange(RegIdx, Idx);
684 /// rewriteSplit - Rewrite uses of Intvs[0] according to the ConEQ mapping.
685 void SplitEditor::rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs,
686 const ConnectedVNInfoEqClasses &ConEq) {
687 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Intvs[0]->reg),
688 RE = MRI.reg_end(); RI != RE;) {
689 MachineOperand &MO = RI.getOperand();
690 MachineInstr *MI = MO.getParent();
692 if (MO.isUse() && MO.isUndef())
694 // DBG_VALUE instructions should have been eliminated earlier.
695 SlotIndex Idx = LIS.getInstructionIndex(MI);
696 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
697 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t'
699 const VNInfo *VNI = Intvs[0]->getVNInfoAt(Idx);
700 assert(VNI && "Interval not live at use.");
701 MO.setReg(Intvs[ConEq.getEqClass(VNI)]->reg);
702 DEBUG(dbgs() << VNI->id << '\t' << *MI);
706 void SplitEditor::finish() {
707 assert(OpenIdx == 0 && "Previous LI not closed before rewrite");
709 // At this point, the live intervals in Edit contain VNInfos corresponding to
710 // the inserted copies.
712 // Add the original defs from the parent interval.
713 for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(),
714 E = Edit.getParent().vni_end(); I != E; ++I) {
715 const VNInfo *ParentVNI = *I;
716 if (ParentVNI->isUnused())
718 unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
719 // Mark all values as complex to force liveness computation.
720 // This should really only be necessary for remat victims, but we are lazy.
721 markComplexMapped(RegIdx, ParentVNI);
722 defValue(RegIdx, ParentVNI, ParentVNI->def);
726 // Every new interval must have a def by now, otherwise the split is bogus.
727 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I)
728 assert((*I)->hasAtLeastOneValue() && "Split interval has no value");
731 // FIXME: Don't recompute the liveness of all values, infer it from the
732 // overlaps between the parent live interval and RegAssign.
733 // The extendRange algorithm is only necessary when:
734 // - The parent value maps to multiple defs, and new phis are needed, or
735 // - The value has been rematerialized before some uses, and we want to
736 // minimize the live range so it only reaches the remaining uses.
737 // All other values have simple liveness that can be computed from RegAssign
738 // and the parent live interval.
740 // Extend live ranges to be live-out for successor PHI values.
741 for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(),
742 E = Edit.getParent().vni_end(); I != E; ++I) {
743 const VNInfo *PHIVNI = *I;
744 if (PHIVNI->isUnused() || !PHIVNI->isPHIDef())
746 unsigned RegIdx = RegAssign.lookup(PHIVNI->def);
747 MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def);
748 DEBUG(dbgs() << " map phi in BB#" << MBB->getNumber() << '@' << PHIVNI->def
749 << " -> " << RegIdx << '\n');
750 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
751 PE = MBB->pred_end(); PI != PE; ++PI) {
752 SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot();
753 DEBUG(dbgs() << " pred BB#" << (*PI)->getNumber() << '@' << End);
754 // The predecessor may not have a live-out value. That is OK, like an
755 // undef PHI operand.
756 if (Edit.getParent().liveAt(End)) {
757 DEBUG(dbgs() << " has parent live out\n");
758 assert(RegAssign.lookup(End) == RegIdx &&
759 "Different register assignment in phi predecessor");
760 extendRange(RegIdx, End);
762 DEBUG(dbgs() << " is not live-out\n");
764 DEBUG(dbgs() << " " << *Edit.get(RegIdx) << '\n');
767 // Rewrite instructions.
770 // FIXME: Delete defs that were rematted everywhere.
772 // Get rid of unused values and set phi-kill flags.
773 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I)
774 (*I)->RenumberValues(LIS);
776 // Now check if any registers were separated into multiple components.
777 ConnectedVNInfoEqClasses ConEQ(LIS);
778 for (unsigned i = 0, e = Edit.size(); i != e; ++i) {
779 // Don't use iterators, they are invalidated by create() below.
780 LiveInterval *li = Edit.get(i);
781 unsigned NumComp = ConEQ.Classify(li);
784 DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n');
785 SmallVector<LiveInterval*, 8> dups;
787 for (unsigned i = 1; i != NumComp; ++i)
788 dups.push_back(&Edit.create(MRI, LIS, VRM));
789 rewriteComponents(dups, ConEQ);
790 ConEQ.Distribute(&dups[0]);
793 // Calculate spill weight and allocation hints for new intervals.
794 VirtRegAuxInfo vrai(VRM.getMachineFunction(), LIS, SA.Loops);
795 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I){
796 LiveInterval &li = **I;
797 vrai.CalculateRegClass(li.reg);
798 vrai.CalculateWeightAndHint(li);
799 DEBUG(dbgs() << " new interval " << MRI.getRegClass(li.reg)->getName()
800 << ":" << li << '\n');
805 //===----------------------------------------------------------------------===//
806 // Single Block Splitting
807 //===----------------------------------------------------------------------===//
809 /// getMultiUseBlocks - if CurLI has more than one use in a basic block, it
810 /// may be an advantage to split CurLI for the duration of the block.
811 bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) {
812 // If CurLI is local to one block, there is no point to splitting it.
813 if (LiveBlocks.size() <= 1)
815 // Add blocks with multiple uses.
816 for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
817 const BlockInfo &BI = LiveBlocks[i];
820 unsigned Instrs = UsingBlocks.lookup(BI.MBB);
823 if (Instrs == 2 && BI.LiveIn && BI.LiveOut && !BI.LiveThrough)
825 Blocks.insert(BI.MBB);
827 return !Blocks.empty();
830 /// splitSingleBlocks - Split CurLI into a separate live interval inside each
831 /// basic block in Blocks.
832 void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) {
833 DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n");
835 for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) {
836 const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i];
837 if (!BI.Uses || !Blocks.count(BI.MBB))
841 SlotIndex SegStart = enterIntvBefore(BI.FirstUse);
842 if (!BI.LiveOut || BI.LastUse < BI.LastSplitPoint) {
843 useIntv(SegStart, leaveIntvAfter(BI.LastUse));
845 // The last use is after the last valid split point.
846 SlotIndex SegStop = leaveIntvBefore(BI.LastSplitPoint);
847 useIntv(SegStart, SegStop);
848 overlapIntv(SegStop, BI.LastUse);