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 // extendRange - Extend the live range to reach Idx.
218 // Potentially create phi-def values.
219 void LiveIntervalMap::extendRange(SlotIndex Idx) {
220 assert(LI && "call reset first");
221 assert(Idx.isValid() && "Invalid SlotIndex");
222 MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx);
223 assert(IdxMBB && "No MBB at Idx");
225 // Is there a def in the same MBB we can extend?
226 if (LI->extendInBlock(LIS.getMBBStartIdx(IdxMBB), Idx))
229 // Now for the fun part. We know that ParentVNI potentially has multiple defs,
230 // and we may need to create even more phi-defs to preserve VNInfo SSA form.
231 // Perform a search for all predecessor blocks where we know the dominating
232 // VNInfo. Insert phi-def VNInfos along the path back to IdxMBB.
233 DEBUG(dbgs() << "\n Reaching defs for BB#" << IdxMBB->getNumber()
234 << " at " << Idx << " in " << *LI << '\n');
236 // Blocks where LI should be live-in.
237 SmallVector<MachineDomTreeNode*, 16> LiveIn;
238 LiveIn.push_back(MDT[IdxMBB]);
240 // Using LiveOutCache as a visited set, perform a BFS for all reaching defs.
241 for (unsigned i = 0; i != LiveIn.size(); ++i) {
242 MachineBasicBlock *MBB = LiveIn[i]->getBlock();
243 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
244 PE = MBB->pred_end(); PI != PE; ++PI) {
245 MachineBasicBlock *Pred = *PI;
246 // Is this a known live-out block?
247 std::pair<LiveOutMap::iterator,bool> LOIP =
248 LiveOutCache.insert(std::make_pair(Pred, LiveOutPair()));
249 // Yes, we have been here before.
251 DEBUG(if (VNInfo *VNI = LOIP.first->second.first)
252 dbgs() << " known valno #" << VNI->id
253 << " at BB#" << Pred->getNumber() << '\n');
257 // Does Pred provide a live-out value?
258 SlotIndex Start, Last;
259 tie(Start, Last) = LIS.getSlotIndexes()->getMBBRange(Pred);
260 Last = Last.getPrevSlot();
261 if (VNInfo *VNI = LI->extendInBlock(Start, Last)) {
262 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(VNI->def);
263 DEBUG(dbgs() << " found valno #" << VNI->id
264 << " from BB#" << DefMBB->getNumber()
265 << " at BB#" << Pred->getNumber() << '\n');
266 LiveOutPair &LOP = LOIP.first->second;
268 LOP.second = MDT[DefMBB];
271 // No, we need a live-in value for Pred as well
273 LiveIn.push_back(MDT[Pred]);
277 // We may need to add phi-def values to preserve the SSA form.
278 // This is essentially the same iterative algorithm that SSAUpdater uses,
279 // except we already have a dominator tree, so we don't have to recompute it.
284 DEBUG(dbgs() << " Iterating over " << LiveIn.size() << " blocks.\n");
285 // Propagate live-out values down the dominator tree, inserting phi-defs when
286 // necessary. Since LiveIn was created by a BFS, going backwards makes it more
287 // likely for us to visit immediate dominators before their children.
288 for (unsigned i = LiveIn.size(); i; --i) {
289 MachineDomTreeNode *Node = LiveIn[i-1];
290 MachineBasicBlock *MBB = Node->getBlock();
291 MachineDomTreeNode *IDom = Node->getIDom();
292 LiveOutPair IDomValue;
293 // We need a live-in value to a block with no immediate dominator?
294 // This is probably an unreachable block that has survived somehow.
295 bool needPHI = !IDom;
297 // Get the IDom live-out value.
299 LiveOutMap::iterator I = LiveOutCache.find(IDom->getBlock());
300 if (I != LiveOutCache.end())
301 IDomValue = I->second;
303 // If IDom is outside our set of live-out blocks, there must be new
304 // defs, and we need a phi-def here.
308 // IDom dominates all of our predecessors, but it may not be the immediate
309 // dominator. Check if any of them have live-out values that are properly
310 // dominated by IDom. If so, we need a phi-def here.
312 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
313 PE = MBB->pred_end(); PI != PE; ++PI) {
314 LiveOutPair Value = LiveOutCache[*PI];
315 if (!Value.first || Value.first == IDomValue.first)
317 // This predecessor is carrying something other than IDomValue.
318 // It could be because IDomValue hasn't propagated yet, or it could be
319 // because MBB is in the dominance frontier of that value.
320 if (MDT.dominates(IDom, Value.second)) {
327 // Create a phi-def if required.
330 SlotIndex Start = LIS.getMBBStartIdx(MBB);
331 VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator());
332 VNI->setIsPHIDef(true);
333 DEBUG(dbgs() << " - BB#" << MBB->getNumber()
334 << " phi-def #" << VNI->id << " at " << Start << '\n');
335 // We no longer need LI to be live-in.
336 LiveIn.erase(LiveIn.begin()+(i-1));
337 // Blocks in LiveIn are either IdxMBB, or have a value live-through.
340 // Check if we need to update live-out info.
341 LiveOutMap::iterator I = LiveOutCache.find(MBB);
342 if (I == LiveOutCache.end() || I->second.second == Node) {
343 // We already have a live-out defined in MBB, so this must be IdxMBB.
344 assert(MBB == IdxMBB && "Adding phi-def to known live-out");
345 LI->addRange(LiveRange(Start, Idx.getNextSlot(), VNI));
347 // This phi-def is also live-out, so color the whole block.
348 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
349 I->second = LiveOutPair(VNI, Node);
351 } else if (IDomValue.first) {
352 // No phi-def here. Remember incoming value for IdxMBB.
354 IdxVNI = IDomValue.first;
355 // Propagate IDomValue if needed:
356 // MBB is live-out and doesn't define its own value.
357 LiveOutMap::iterator I = LiveOutCache.find(MBB);
358 if (I != LiveOutCache.end() && I->second.second != Node &&
359 I->second.first != IDomValue.first) {
361 I->second = IDomValue;
362 DEBUG(dbgs() << " - BB#" << MBB->getNumber()
363 << " idom valno #" << IDomValue.first->id
364 << " from BB#" << IDom->getBlock()->getNumber() << '\n');
368 DEBUG(dbgs() << " - made " << Changes << " changes.\n");
371 assert(IdxVNI && "Didn't find value for Idx");
374 // Check the LiveOutCache invariants.
375 for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end();
377 assert(I->first && "Null MBB entry in cache");
378 assert(I->second.first && "Null VNInfo in cache");
379 assert(I->second.second && "Null DomTreeNode in cache");
380 if (I->second.second->getBlock() == I->first)
382 for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(),
383 PE = I->first->pred_end(); PI != PE; ++PI)
384 assert(LiveOutCache.lookup(*PI) == I->second && "Bad invariant");
388 // Since we went through the trouble of a full BFS visiting all reaching defs,
389 // the values in LiveIn are now accurate. No more phi-defs are needed
390 // for these blocks, so we can color the live ranges.
391 for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) {
392 MachineBasicBlock *MBB = LiveIn[i]->getBlock();
393 SlotIndex Start = LIS.getMBBStartIdx(MBB);
394 VNInfo *VNI = LiveOutCache.lookup(MBB).first;
396 // Anything in LiveIn other than IdxMBB is live-through.
397 // In IdxMBB, we should stop at Idx unless the same value is live-out.
398 if (MBB == IdxMBB && IdxVNI != VNI)
399 LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI));
401 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
406 void LiveIntervalMap::dumpCache() {
407 for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end();
409 assert(I->first && "Null MBB entry in cache");
410 assert(I->second.first && "Null VNInfo in cache");
411 assert(I->second.second && "Null DomTreeNode in cache");
412 dbgs() << " cache: BB#" << I->first->getNumber()
413 << " has valno #" << I->second.first->id << " from BB#"
414 << I->second.second->getBlock()->getNumber() << ", preds";
415 for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(),
416 PE = I->first->pred_end(); PI != PE; ++PI)
417 dbgs() << " BB#" << (*PI)->getNumber();
420 dbgs() << " cache: " << LiveOutCache.size() << " entries.\n";
425 //===----------------------------------------------------------------------===//
427 //===----------------------------------------------------------------------===//
429 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
430 SplitEditor::SplitEditor(SplitAnalysis &sa,
433 MachineDominatorTree &mdt,
435 : SA(sa), LIS(lis), VRM(vrm),
436 MRI(vrm.getMachineFunction().getRegInfo()),
438 TII(*vrm.getMachineFunction().getTarget().getInstrInfo()),
439 TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()),
444 // We don't need an AliasAnalysis since we will only be performing
445 // cheap-as-a-copy remats anyway.
446 Edit.anyRematerializable(LIS, TII, 0);
449 void SplitEditor::dump() const {
450 if (RegAssign.empty()) {
451 dbgs() << " empty\n";
455 for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
456 dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
460 VNInfo *SplitEditor::defValue(unsigned RegIdx,
461 const VNInfo *ParentVNI,
463 assert(ParentVNI && "Mapping NULL value");
464 assert(Idx.isValid() && "Invalid SlotIndex");
465 assert(Edit.getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
466 LiveInterval *LI = Edit.get(RegIdx);
468 // Create a new value.
469 VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator());
471 // Preserve the PHIDef bit.
472 if (ParentVNI->isPHIDef() && Idx == ParentVNI->def)
473 VNI->setIsPHIDef(true);
475 // Use insert for lookup, so we can add missing values with a second lookup.
476 std::pair<ValueMap::iterator, bool> InsP =
477 Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI));
479 // This was the first time (RegIdx, ParentVNI) was mapped.
480 // Keep it as a simple def without any liveness.
484 // If the previous value was a simple mapping, add liveness for it now.
485 if (VNInfo *OldVNI = InsP.first->second) {
486 SlotIndex Def = OldVNI->def;
487 LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI));
488 // No longer a simple mapping.
489 InsP.first->second = 0;
492 // This is a complex mapping, add liveness for VNI
493 SlotIndex Def = VNI->def;
494 LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
499 void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) {
500 assert(ParentVNI && "Mapping NULL value");
501 VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)];
503 // ParentVNI was either unmapped or already complex mapped. Either way.
507 // This was previously a single mapping. Make sure the old def is represented
508 // by a trivial live range.
509 SlotIndex Def = VNI->def;
510 Edit.get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
514 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
517 MachineBasicBlock &MBB,
518 MachineBasicBlock::iterator I) {
519 MachineInstr *CopyMI = 0;
521 LiveInterval *LI = Edit.get(RegIdx);
523 // Attempt cheap-as-a-copy rematerialization.
524 LiveRangeEdit::Remat RM(ParentVNI);
525 if (Edit.canRematerializeAt(RM, UseIdx, true, LIS)) {
526 Def = Edit.rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI);
528 // Can't remat, just insert a copy from parent.
529 CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
530 .addReg(Edit.getReg());
531 Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex();
534 // Temporarily mark all values as complex mapped.
535 markComplexMapped(RegIdx, ParentVNI);
537 // Define the value in Reg.
538 VNInfo *VNI = defValue(RegIdx, ParentVNI, Def);
539 VNI->setCopy(CopyMI);
543 /// Create a new virtual register and live interval.
544 void SplitEditor::openIntv() {
545 assert(!OpenIdx && "Previous LI not closed before openIntv");
547 // Create the complement as index 0.
549 Edit.create(MRI, LIS, VRM);
550 LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent()));
551 LIMappers.back().reset(Edit.get(0));
554 // Create the open interval.
555 OpenIdx = Edit.size();
556 Edit.create(MRI, LIS, VRM);
557 LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent()));
558 LIMappers[OpenIdx].reset(Edit.get(OpenIdx));
561 SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
562 assert(OpenIdx && "openIntv not called before enterIntvBefore");
563 DEBUG(dbgs() << " enterIntvBefore " << Idx);
564 Idx = Idx.getBaseIndex();
565 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
567 DEBUG(dbgs() << ": not live\n");
570 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
571 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
572 assert(MI && "enterIntvBefore called with invalid index");
574 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
578 SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
579 assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
580 SlotIndex End = LIS.getMBBEndIdx(&MBB);
581 SlotIndex Last = End.getPrevSlot();
582 DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last);
583 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Last);
585 DEBUG(dbgs() << ": not live\n");
588 DEBUG(dbgs() << ": valno " << ParentVNI->id);
589 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
590 LIS.getLastSplitPoint(Edit.getParent(), &MBB));
591 RegAssign.insert(VNI->def, End, OpenIdx);
596 /// useIntv - indicate that all instructions in MBB should use OpenLI.
597 void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
598 useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));
601 void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
602 assert(OpenIdx && "openIntv not called before useIntv");
603 DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):");
604 RegAssign.insert(Start, End, OpenIdx);
608 SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {
609 assert(OpenIdx && "openIntv not called before leaveIntvAfter");
610 DEBUG(dbgs() << " leaveIntvAfter " << Idx);
612 // The interval must be live beyond the instruction at Idx.
613 Idx = Idx.getBoundaryIndex();
614 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
616 DEBUG(dbgs() << ": not live\n");
617 return Idx.getNextSlot();
619 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
621 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
622 assert(MI && "No instruction at index");
623 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(),
624 llvm::next(MachineBasicBlock::iterator(MI)));
628 SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {
629 assert(OpenIdx && "openIntv not called before leaveIntvBefore");
630 DEBUG(dbgs() << " leaveIntvBefore " << Idx);
632 // The interval must be live into the instruction at Idx.
633 Idx = Idx.getBoundaryIndex();
634 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
636 DEBUG(dbgs() << ": not live\n");
637 return Idx.getNextSlot();
639 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
641 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
642 assert(MI && "No instruction at index");
643 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
647 SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
648 assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
649 SlotIndex Start = LIS.getMBBStartIdx(&MBB);
650 DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start);
652 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Start);
654 DEBUG(dbgs() << ": not live\n");
658 VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
659 MBB.SkipPHIsAndLabels(MBB.begin()));
660 RegAssign.insert(Start, VNI->def, OpenIdx);
665 void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
666 assert(OpenIdx && "openIntv not called before overlapIntv");
667 assert(Edit.getParent().getVNInfoAt(Start) ==
668 Edit.getParent().getVNInfoAt(End.getPrevSlot()) &&
669 "Parent changes value in extended range");
670 assert(Edit.get(0)->getVNInfoAt(Start) && "Start must come from leaveIntv*");
671 assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
672 "Range cannot span basic blocks");
674 // Treat this as useIntv() for now.
675 // The complement interval will be extended as needed by extendRange().
676 DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):");
677 RegAssign.insert(Start, End, OpenIdx);
681 /// closeIntv - Indicate that we are done editing the currently open
682 /// LiveInterval, and ranges can be trimmed.
683 void SplitEditor::closeIntv() {
684 assert(OpenIdx && "openIntv not called before closeIntv");
688 /// rewriteAssigned - Rewrite all uses of Edit.getReg().
689 void SplitEditor::rewriteAssigned() {
690 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit.getReg()),
691 RE = MRI.reg_end(); RI != RE;) {
692 MachineOperand &MO = RI.getOperand();
693 MachineInstr *MI = MO.getParent();
695 // LiveDebugVariables should have handled all DBG_VALUE instructions.
696 if (MI->isDebugValue()) {
697 DEBUG(dbgs() << "Zapping " << *MI);
702 // <undef> operands don't really read the register, so just assign them to
704 if (MO.isUse() && MO.isUndef()) {
705 MO.setReg(Edit.get(0)->reg);
709 SlotIndex Idx = LIS.getInstructionIndex(MI);
710 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
712 // Rewrite to the mapped register at Idx.
713 unsigned RegIdx = RegAssign.lookup(Idx);
714 MO.setReg(Edit.get(RegIdx)->reg);
715 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t'
716 << Idx << ':' << RegIdx << '\t' << *MI);
718 // Extend liveness to Idx.
719 LIMappers[RegIdx].extendRange(Idx);
723 /// rewriteSplit - Rewrite uses of Intvs[0] according to the ConEQ mapping.
724 void SplitEditor::rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs,
725 const ConnectedVNInfoEqClasses &ConEq) {
726 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Intvs[0]->reg),
727 RE = MRI.reg_end(); RI != RE;) {
728 MachineOperand &MO = RI.getOperand();
729 MachineInstr *MI = MO.getParent();
731 if (MO.isUse() && MO.isUndef())
733 // DBG_VALUE instructions should have been eliminated earlier.
734 SlotIndex Idx = LIS.getInstructionIndex(MI);
735 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
736 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t'
738 const VNInfo *VNI = Intvs[0]->getVNInfoAt(Idx);
739 assert(VNI && "Interval not live at use.");
740 MO.setReg(Intvs[ConEq.getEqClass(VNI)]->reg);
741 DEBUG(dbgs() << VNI->id << '\t' << *MI);
745 void SplitEditor::finish() {
746 assert(OpenIdx == 0 && "Previous LI not closed before rewrite");
748 // At this point, the live intervals in Edit contain VNInfos corresponding to
749 // the inserted copies.
751 // Add the original defs from the parent interval.
752 for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(),
753 E = Edit.getParent().vni_end(); I != E; ++I) {
754 const VNInfo *ParentVNI = *I;
755 if (ParentVNI->isUnused())
757 unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
758 // Mark all values as complex to force liveness computation.
759 // This should really only be necessary for remat victims, but we are lazy.
760 markComplexMapped(RegIdx, ParentVNI);
761 defValue(RegIdx, ParentVNI, ParentVNI->def);
765 // Every new interval must have a def by now, otherwise the split is bogus.
766 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I)
767 assert((*I)->hasAtLeastOneValue() && "Split interval has no value");
770 // FIXME: Don't recompute the liveness of all values, infer it from the
771 // overlaps between the parent live interval and RegAssign.
772 // The extendRange algorithm is only necessary when:
773 // - The parent value maps to multiple defs, and new phis are needed, or
774 // - The value has been rematerialized before some uses, and we want to
775 // minimize the live range so it only reaches the remaining uses.
776 // All other values have simple liveness that can be computed from RegAssign
777 // and the parent live interval.
779 // Extend live ranges to be live-out for successor PHI values.
780 for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(),
781 E = Edit.getParent().vni_end(); I != E; ++I) {
782 const VNInfo *PHIVNI = *I;
783 if (PHIVNI->isUnused() || !PHIVNI->isPHIDef())
785 unsigned RegIdx = RegAssign.lookup(PHIVNI->def);
786 LiveIntervalMap &LIM = LIMappers[RegIdx];
787 MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def);
788 DEBUG(dbgs() << " map phi in BB#" << MBB->getNumber() << '@' << PHIVNI->def
789 << " -> " << RegIdx << '\n');
790 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
791 PE = MBB->pred_end(); PI != PE; ++PI) {
792 SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot();
793 DEBUG(dbgs() << " pred BB#" << (*PI)->getNumber() << '@' << End);
794 // The predecessor may not have a live-out value. That is OK, like an
795 // undef PHI operand.
796 if (VNInfo *VNI = Edit.getParent().getVNInfoAt(End)) {
797 DEBUG(dbgs() << " has parent valno #" << VNI->id << " live out\n");
798 assert(RegAssign.lookup(End) == RegIdx &&
799 "Different register assignment in phi predecessor");
800 LIM.extendRange(End);
803 DEBUG(dbgs() << " is not live-out\n");
805 DEBUG(dbgs() << " " << *LIM.getLI() << '\n');
808 // Rewrite instructions.
811 // FIXME: Delete defs that were rematted everywhere.
813 // Get rid of unused values and set phi-kill flags.
814 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I)
815 (*I)->RenumberValues(LIS);
817 // Now check if any registers were separated into multiple components.
818 ConnectedVNInfoEqClasses ConEQ(LIS);
819 for (unsigned i = 0, e = Edit.size(); i != e; ++i) {
820 // Don't use iterators, they are invalidated by create() below.
821 LiveInterval *li = Edit.get(i);
822 unsigned NumComp = ConEQ.Classify(li);
825 DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n');
826 SmallVector<LiveInterval*, 8> dups;
828 for (unsigned i = 1; i != NumComp; ++i)
829 dups.push_back(&Edit.create(MRI, LIS, VRM));
830 rewriteComponents(dups, ConEQ);
831 ConEQ.Distribute(&dups[0]);
834 // Calculate spill weight and allocation hints for new intervals.
835 VirtRegAuxInfo vrai(VRM.getMachineFunction(), LIS, SA.Loops);
836 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I){
837 LiveInterval &li = **I;
838 vrai.CalculateRegClass(li.reg);
839 vrai.CalculateWeightAndHint(li);
840 DEBUG(dbgs() << " new interval " << MRI.getRegClass(li.reg)->getName()
841 << ":" << li << '\n');
846 //===----------------------------------------------------------------------===//
847 // Single Block Splitting
848 //===----------------------------------------------------------------------===//
850 /// getMultiUseBlocks - if CurLI has more than one use in a basic block, it
851 /// may be an advantage to split CurLI for the duration of the block.
852 bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) {
853 // If CurLI is local to one block, there is no point to splitting it.
854 if (LiveBlocks.size() <= 1)
856 // Add blocks with multiple uses.
857 for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
858 const BlockInfo &BI = LiveBlocks[i];
861 unsigned Instrs = UsingBlocks.lookup(BI.MBB);
864 if (Instrs == 2 && BI.LiveIn && BI.LiveOut && !BI.LiveThrough)
866 Blocks.insert(BI.MBB);
868 return !Blocks.empty();
871 /// splitSingleBlocks - Split CurLI into a separate live interval inside each
872 /// basic block in Blocks.
873 void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) {
874 DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n");
876 for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) {
877 const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i];
878 if (!BI.Uses || !Blocks.count(BI.MBB))
882 SlotIndex SegStart = enterIntvBefore(BI.FirstUse);
883 if (!BI.LiveOut || BI.LastUse < BI.LastSplitPoint) {
884 useIntv(SegStart, leaveIntvAfter(BI.LastUse));
886 // The last use is after the last valid split point.
887 SlotIndex SegStop = leaveIntvBefore(BI.LastSplitPoint);
888 useIntv(SegStart, SegStop);
889 overlapIntv(SegStop, BI.LastUse);