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/MachineLoopInfo.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/Support/CommandLine.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/raw_ostream.h"
28 #include "llvm/Target/TargetInstrInfo.h"
29 #include "llvm/Target/TargetMachine.h"
34 AllowSplit("spiller-splits-edges",
35 cl::desc("Allow critical edge splitting during spilling"));
37 //===----------------------------------------------------------------------===//
39 //===----------------------------------------------------------------------===//
41 SplitAnalysis::SplitAnalysis(const MachineFunction &mf,
42 const LiveIntervals &lis,
43 const MachineLoopInfo &mli)
47 TII(*mf.getTarget().getInstrInfo()),
50 void SplitAnalysis::clear() {
59 bool SplitAnalysis::canAnalyzeBranch(const MachineBasicBlock *MBB) {
60 MachineBasicBlock *T, *F;
61 SmallVector<MachineOperand, 4> Cond;
62 return !TII.AnalyzeBranch(const_cast<MachineBasicBlock&>(*MBB), T, F, Cond);
65 /// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
66 void SplitAnalysis::analyzeUses() {
67 const MachineRegisterInfo &MRI = MF.getRegInfo();
68 for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(CurLI->reg),
69 E = MRI.reg_end(); I != E; ++I) {
70 MachineOperand &MO = I.getOperand();
71 if (MO.isUse() && MO.isUndef())
73 MachineInstr *MI = MO.getParent();
74 if (MI->isDebugValue() || !UsingInstrs.insert(MI))
76 UseSlots.push_back(LIS.getInstructionIndex(MI).getDefIndex());
77 MachineBasicBlock *MBB = MI->getParent();
78 if (UsingBlocks[MBB]++)
80 for (MachineLoop *Loop = Loops.getLoopFor(MBB); Loop;
81 Loop = Loop->getParentLoop())
84 array_pod_sort(UseSlots.begin(), UseSlots.end());
86 DEBUG(dbgs() << " counted "
87 << UsingInstrs.size() << " instrs, "
88 << UsingBlocks.size() << " blocks, "
89 << UsingLoops.size() << " loops.\n");
92 /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
93 /// where CurLI is live.
94 void SplitAnalysis::calcLiveBlockInfo() {
98 LiveInterval::const_iterator LVI = CurLI->begin();
99 LiveInterval::const_iterator LVE = CurLI->end();
101 SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
102 UseI = UseSlots.begin();
103 UseE = UseSlots.end();
105 // Loop over basic blocks where CurLI is live.
106 MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start);
110 SlotIndex Start, Stop;
111 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
113 // The last split point is the latest possible insertion point that dominates
114 // all successor blocks. If interference reaches LastSplitPoint, it is not
115 // possible to insert a split or reload that makes CurLI live in the
117 MachineBasicBlock::iterator LSP = LIS.getLastSplitPoint(*CurLI, BI.MBB);
118 if (LSP == BI.MBB->end())
119 BI.LastSplitPoint = Stop;
121 BI.LastSplitPoint = LIS.getInstructionIndex(LSP);
123 // LVI is the first live segment overlapping MBB.
124 BI.LiveIn = LVI->start <= Start;
128 // Find the first and last uses in the block.
129 BI.Uses = hasUses(MFI);
130 if (BI.Uses && UseI != UseE) {
132 assert(BI.FirstUse >= Start);
134 while (UseI != UseE && *UseI < Stop);
135 BI.LastUse = UseI[-1];
136 assert(BI.LastUse < Stop);
139 // Look for gaps in the live range.
142 while (LVI->end < Stop) {
143 SlotIndex LastStop = LVI->end;
144 if (++LVI == LVE || LVI->start >= Stop) {
149 if (LastStop < LVI->start) {
156 // Don't set LiveThrough when the block has a gap.
157 BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut;
158 LiveBlocks.push_back(BI);
160 // LVI is now at LVE or LVI->end >= Stop.
164 // Live segment ends exactly at Stop. Move to the next segment.
165 if (LVI->end == Stop && ++LVI == LVE)
168 // Pick the next basic block.
169 if (LVI->start < Stop)
172 MFI = LIS.getMBBFromIndex(LVI->start);
176 void SplitAnalysis::print(const BlockPtrSet &B, raw_ostream &OS) const {
177 for (BlockPtrSet::const_iterator I = B.begin(), E = B.end(); I != E; ++I) {
178 unsigned count = UsingBlocks.lookup(*I);
179 OS << " BB#" << (*I)->getNumber();
181 OS << '(' << count << ')';
185 // Get three sets of basic blocks surrounding a loop: Blocks inside the loop,
186 // predecessor blocks, and exit blocks.
187 void SplitAnalysis::getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks) {
190 // Blocks in the loop.
191 Blocks.Loop.insert(Loop->block_begin(), Loop->block_end());
193 // Predecessor blocks.
194 const MachineBasicBlock *Header = Loop->getHeader();
195 for (MachineBasicBlock::const_pred_iterator I = Header->pred_begin(),
196 E = Header->pred_end(); I != E; ++I)
197 if (!Blocks.Loop.count(*I))
198 Blocks.Preds.insert(*I);
201 for (MachineLoop::block_iterator I = Loop->block_begin(),
202 E = Loop->block_end(); I != E; ++I) {
203 const MachineBasicBlock *MBB = *I;
204 for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(),
205 SE = MBB->succ_end(); SI != SE; ++SI)
206 if (!Blocks.Loop.count(*SI))
207 Blocks.Exits.insert(*SI);
211 void SplitAnalysis::print(const LoopBlocks &B, raw_ostream &OS) const {
220 /// analyzeLoopPeripheralUse - Return an enum describing how CurLI is used in
221 /// and around the Loop.
222 SplitAnalysis::LoopPeripheralUse SplitAnalysis::
223 analyzeLoopPeripheralUse(const SplitAnalysis::LoopBlocks &Blocks) {
224 LoopPeripheralUse use = ContainedInLoop;
225 for (BlockCountMap::iterator I = UsingBlocks.begin(), E = UsingBlocks.end();
227 const MachineBasicBlock *MBB = I->first;
228 // Is this a peripheral block?
229 if (use < MultiPeripheral &&
230 (Blocks.Preds.count(MBB) || Blocks.Exits.count(MBB))) {
231 if (I->second > 1) use = MultiPeripheral;
232 else use = SinglePeripheral;
235 // Is it a loop block?
236 if (Blocks.Loop.count(MBB))
238 // It must be an unrelated block.
239 DEBUG(dbgs() << ", outside: BB#" << MBB->getNumber());
245 /// getCriticalExits - It may be necessary to partially break critical edges
246 /// leaving the loop if an exit block has predecessors from outside the loop
248 void SplitAnalysis::getCriticalExits(const SplitAnalysis::LoopBlocks &Blocks,
249 BlockPtrSet &CriticalExits) {
250 CriticalExits.clear();
252 // A critical exit block has CurLI live-in, and has a predecessor that is not
253 // in the loop nor a loop predecessor. For such an exit block, the edges
254 // carrying the new variable must be moved to a new pre-exit block.
255 for (BlockPtrSet::iterator I = Blocks.Exits.begin(), E = Blocks.Exits.end();
257 const MachineBasicBlock *Exit = *I;
258 // A single-predecessor exit block is definitely not a critical edge.
259 if (Exit->pred_size() == 1)
261 // This exit may not have CurLI live in at all. No need to split.
262 if (!LIS.isLiveInToMBB(*CurLI, Exit))
264 // Does this exit block have a predecessor that is not a loop block or loop
266 for (MachineBasicBlock::const_pred_iterator PI = Exit->pred_begin(),
267 PE = Exit->pred_end(); PI != PE; ++PI) {
268 const MachineBasicBlock *Pred = *PI;
269 if (Blocks.Loop.count(Pred) || Blocks.Preds.count(Pred))
271 // This is a critical exit block, and we need to split the exit edge.
272 CriticalExits.insert(Exit);
278 void SplitAnalysis::getCriticalPreds(const SplitAnalysis::LoopBlocks &Blocks,
279 BlockPtrSet &CriticalPreds) {
280 CriticalPreds.clear();
282 // A critical predecessor block has CurLI live-out, and has a successor that
283 // has CurLI live-in and is not in the loop nor a loop exit block. For such a
284 // predecessor block, we must carry the value in both the 'inside' and
285 // 'outside' registers.
286 for (BlockPtrSet::iterator I = Blocks.Preds.begin(), E = Blocks.Preds.end();
288 const MachineBasicBlock *Pred = *I;
289 // Definitely not a critical edge.
290 if (Pred->succ_size() == 1)
292 // This block may not have CurLI live out at all if there is a PHI.
293 if (!LIS.isLiveOutOfMBB(*CurLI, Pred))
295 // Does this block have a successor outside the loop?
296 for (MachineBasicBlock::const_pred_iterator SI = Pred->succ_begin(),
297 SE = Pred->succ_end(); SI != SE; ++SI) {
298 const MachineBasicBlock *Succ = *SI;
299 if (Blocks.Loop.count(Succ) || Blocks.Exits.count(Succ))
301 if (!LIS.isLiveInToMBB(*CurLI, Succ))
303 // This is a critical predecessor block.
304 CriticalPreds.insert(Pred);
310 /// canSplitCriticalExits - Return true if it is possible to insert new exit
311 /// blocks before the blocks in CriticalExits.
313 SplitAnalysis::canSplitCriticalExits(const SplitAnalysis::LoopBlocks &Blocks,
314 BlockPtrSet &CriticalExits) {
315 // If we don't allow critical edge splitting, require no critical exits.
317 return CriticalExits.empty();
319 for (BlockPtrSet::iterator I = CriticalExits.begin(), E = CriticalExits.end();
321 const MachineBasicBlock *Succ = *I;
322 // We want to insert a new pre-exit MBB before Succ, and change all the
323 // in-loop blocks to branch to the pre-exit instead of Succ.
324 // Check that all the in-loop predecessors can be changed.
325 for (MachineBasicBlock::const_pred_iterator PI = Succ->pred_begin(),
326 PE = Succ->pred_end(); PI != PE; ++PI) {
327 const MachineBasicBlock *Pred = *PI;
328 // The external predecessors won't be altered.
329 if (!Blocks.Loop.count(Pred) && !Blocks.Preds.count(Pred))
331 if (!canAnalyzeBranch(Pred))
335 // If Succ's layout predecessor falls through, that too must be analyzable.
336 // We need to insert the pre-exit block in the gap.
337 MachineFunction::const_iterator MFI = Succ;
338 if (MFI == MF.begin())
340 if (!canAnalyzeBranch(--MFI))
343 // No problems found.
347 void SplitAnalysis::analyze(const LiveInterval *li) {
353 void SplitAnalysis::getSplitLoops(LoopPtrSet &Loops) {
354 assert(CurLI && "Call analyze() before getSplitLoops");
355 if (UsingLoops.empty())
359 BlockPtrSet CriticalExits;
361 // We split around loops where CurLI is used outside the periphery.
362 for (LoopCountMap::const_iterator I = UsingLoops.begin(),
363 E = UsingLoops.end(); I != E; ++I) {
364 const MachineLoop *Loop = I->first;
365 getLoopBlocks(Loop, Blocks);
366 DEBUG({ dbgs() << " "; print(Blocks, dbgs()); });
368 switch(analyzeLoopPeripheralUse(Blocks)) {
371 case MultiPeripheral:
372 // FIXME: We could split a live range with multiple uses in a peripheral
373 // block and still make progress. However, it is possible that splitting
374 // another live range will insert copies into a peripheral block, and
375 // there is a small chance we can enter an infinite loop, inserting copies
377 // For safety, stick to splitting live ranges with uses outside the
379 DEBUG(dbgs() << ": multiple peripheral uses");
381 case ContainedInLoop:
382 DEBUG(dbgs() << ": fully contained\n");
384 case SinglePeripheral:
385 DEBUG(dbgs() << ": single peripheral use\n");
388 // Will it be possible to split around this loop?
389 getCriticalExits(Blocks, CriticalExits);
390 DEBUG(dbgs() << ": " << CriticalExits.size() << " critical exits\n");
391 if (!canSplitCriticalExits(Blocks, CriticalExits))
393 // This is a possible split.
397 DEBUG(dbgs() << " getSplitLoops found " << Loops.size()
398 << " candidate loops.\n");
401 const MachineLoop *SplitAnalysis::getBestSplitLoop() {
403 getSplitLoops(Loops);
407 // Pick the earliest loop.
408 // FIXME: Are there other heuristics to consider?
409 const MachineLoop *Best = 0;
411 for (LoopPtrSet::const_iterator I = Loops.begin(), E = Loops.end(); I != E;
413 SlotIndex Idx = LIS.getMBBStartIdx((*I)->getHeader());
414 if (!Best || Idx < BestIdx)
415 Best = *I, BestIdx = Idx;
417 DEBUG(dbgs() << " getBestSplitLoop found " << *Best);
421 /// isBypassLoop - Return true if CurLI is live through Loop and has no uses
422 /// inside the loop. Bypass loops are candidates for splitting because it can
423 /// prevent interference inside the loop.
424 bool SplitAnalysis::isBypassLoop(const MachineLoop *Loop) {
425 // If CurLI is live into the loop header and there are no uses in the loop, it
426 // must be live in the entire loop and live on at least one exiting edge.
427 return !UsingLoops.count(Loop) &&
428 LIS.isLiveInToMBB(*CurLI, Loop->getHeader());
431 /// getBypassLoops - Get all the maximal bypass loops. These are the bypass
432 /// loops whose parent is not a bypass loop.
433 void SplitAnalysis::getBypassLoops(LoopPtrSet &BypassLoops) {
434 SmallVector<MachineLoop*, 8> Todo(Loops.begin(), Loops.end());
435 while (!Todo.empty()) {
436 MachineLoop *Loop = Todo.pop_back_val();
437 if (!UsingLoops.count(Loop)) {
438 // This is either a bypass loop or completely irrelevant.
439 if (LIS.isLiveInToMBB(*CurLI, Loop->getHeader()))
440 BypassLoops.insert(Loop);
441 // Either way, skip the child loops.
445 // The child loops may be bypass loops.
446 Todo.append(Loop->begin(), Loop->end());
451 //===----------------------------------------------------------------------===//
453 //===----------------------------------------------------------------------===//
455 // Work around the fact that the std::pair constructors are broken for pointer
456 // pairs in some implementations. makeVV(x, 0) works.
457 static inline std::pair<const VNInfo*, VNInfo*>
458 makeVV(const VNInfo *a, VNInfo *b) {
459 return std::make_pair(a, b);
462 void LiveIntervalMap::reset(LiveInterval *li) {
465 LiveOutCache.clear();
468 bool LiveIntervalMap::isComplexMapped(const VNInfo *ParentVNI) const {
469 ValueMap::const_iterator i = Values.find(ParentVNI);
470 return i != Values.end() && i->second == 0;
473 // defValue - Introduce a LI def for ParentVNI that could be later than
475 VNInfo *LiveIntervalMap::defValue(const VNInfo *ParentVNI, SlotIndex Idx) {
476 assert(LI && "call reset first");
477 assert(ParentVNI && "Mapping NULL value");
478 assert(Idx.isValid() && "Invalid SlotIndex");
479 assert(ParentLI.getVNInfoAt(Idx) == ParentVNI && "Bad ParentVNI");
481 // Create a new value.
482 VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator());
484 // Preserve the PHIDef bit.
485 if (ParentVNI->isPHIDef() && Idx == ParentVNI->def)
486 VNI->setIsPHIDef(true);
488 // Use insert for lookup, so we can add missing values with a second lookup.
489 std::pair<ValueMap::iterator,bool> InsP =
490 Values.insert(makeVV(ParentVNI, Idx == ParentVNI->def ? VNI : 0));
492 // This is now a complex def. Mark with a NULL in valueMap.
494 InsP.first->second = 0;
500 // mapValue - Find the mapped value for ParentVNI at Idx.
501 // Potentially create phi-def values.
502 VNInfo *LiveIntervalMap::mapValue(const VNInfo *ParentVNI, SlotIndex Idx,
504 assert(LI && "call reset first");
505 assert(ParentVNI && "Mapping NULL value");
506 assert(Idx.isValid() && "Invalid SlotIndex");
507 assert(ParentLI.getVNInfoAt(Idx) == ParentVNI && "Bad ParentVNI");
509 // Use insert for lookup, so we can add missing values with a second lookup.
510 std::pair<ValueMap::iterator,bool> InsP =
511 Values.insert(makeVV(ParentVNI, 0));
513 // This was an unknown value. Create a simple mapping.
515 if (simple) *simple = true;
516 return InsP.first->second = LI->createValueCopy(ParentVNI,
517 LIS.getVNInfoAllocator());
520 // This was a simple mapped value.
521 if (InsP.first->second) {
522 if (simple) *simple = true;
523 return InsP.first->second;
526 // This is a complex mapped value. There may be multiple defs, and we may need
527 // to create phi-defs.
528 if (simple) *simple = false;
529 MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx);
530 assert(IdxMBB && "No MBB at Idx");
532 // Is there a def in the same MBB we can extend?
533 if (VNInfo *VNI = extendTo(IdxMBB, Idx))
536 // Now for the fun part. We know that ParentVNI potentially has multiple defs,
537 // and we may need to create even more phi-defs to preserve VNInfo SSA form.
538 // Perform a search for all predecessor blocks where we know the dominating
539 // VNInfo. Insert phi-def VNInfos along the path back to IdxMBB.
540 DEBUG(dbgs() << "\n Reaching defs for BB#" << IdxMBB->getNumber()
541 << " at " << Idx << " in " << *LI << '\n');
543 // Blocks where LI should be live-in.
544 SmallVector<MachineDomTreeNode*, 16> LiveIn;
545 LiveIn.push_back(MDT[IdxMBB]);
547 // Using LiveOutCache as a visited set, perform a BFS for all reaching defs.
548 for (unsigned i = 0; i != LiveIn.size(); ++i) {
549 MachineBasicBlock *MBB = LiveIn[i]->getBlock();
550 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
551 PE = MBB->pred_end(); PI != PE; ++PI) {
552 MachineBasicBlock *Pred = *PI;
553 // Is this a known live-out block?
554 std::pair<LiveOutMap::iterator,bool> LOIP =
555 LiveOutCache.insert(std::make_pair(Pred, LiveOutPair()));
556 // Yes, we have been here before.
558 DEBUG(if (VNInfo *VNI = LOIP.first->second.first)
559 dbgs() << " known valno #" << VNI->id
560 << " at BB#" << Pred->getNumber() << '\n');
564 // Does Pred provide a live-out value?
565 SlotIndex Last = LIS.getMBBEndIdx(Pred).getPrevSlot();
566 if (VNInfo *VNI = extendTo(Pred, Last)) {
567 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(VNI->def);
568 DEBUG(dbgs() << " found valno #" << VNI->id
569 << " from BB#" << DefMBB->getNumber()
570 << " at BB#" << Pred->getNumber() << '\n');
571 LiveOutPair &LOP = LOIP.first->second;
573 LOP.second = MDT[DefMBB];
576 // No, we need a live-in value for Pred as well
578 LiveIn.push_back(MDT[Pred]);
582 // We may need to add phi-def values to preserve the SSA form.
583 // This is essentially the same iterative algorithm that SSAUpdater uses,
584 // except we already have a dominator tree, so we don't have to recompute it.
589 DEBUG(dbgs() << " Iterating over " << LiveIn.size() << " blocks.\n");
590 // Propagate live-out values down the dominator tree, inserting phi-defs when
591 // necessary. Since LiveIn was created by a BFS, going backwards makes it more
592 // likely for us to visit immediate dominators before their children.
593 for (unsigned i = LiveIn.size(); i; --i) {
594 MachineDomTreeNode *Node = LiveIn[i-1];
595 MachineBasicBlock *MBB = Node->getBlock();
596 MachineDomTreeNode *IDom = Node->getIDom();
597 LiveOutPair IDomValue;
598 // We need a live-in value to a block with no immediate dominator?
599 // This is probably an unreachable block that has survived somehow.
600 bool needPHI = !IDom;
602 // Get the IDom live-out value.
604 LiveOutMap::iterator I = LiveOutCache.find(IDom->getBlock());
605 if (I != LiveOutCache.end())
606 IDomValue = I->second;
608 // If IDom is outside our set of live-out blocks, there must be new
609 // defs, and we need a phi-def here.
613 // IDom dominates all of our predecessors, but it may not be the immediate
614 // dominator. Check if any of them have live-out values that are properly
615 // dominated by IDom. If so, we need a phi-def here.
617 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
618 PE = MBB->pred_end(); PI != PE; ++PI) {
619 LiveOutPair Value = LiveOutCache[*PI];
620 if (!Value.first || Value.first == IDomValue.first)
622 // This predecessor is carrying something other than IDomValue.
623 // It could be because IDomValue hasn't propagated yet, or it could be
624 // because MBB is in the dominance frontier of that value.
625 if (MDT.dominates(IDom, Value.second)) {
632 // Create a phi-def if required.
635 SlotIndex Start = LIS.getMBBStartIdx(MBB);
636 VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator());
637 VNI->setIsPHIDef(true);
638 DEBUG(dbgs() << " - BB#" << MBB->getNumber()
639 << " phi-def #" << VNI->id << " at " << Start << '\n');
640 // We no longer need LI to be live-in.
641 LiveIn.erase(LiveIn.begin()+(i-1));
642 // Blocks in LiveIn are either IdxMBB, or have a value live-through.
645 // Check if we need to update live-out info.
646 LiveOutMap::iterator I = LiveOutCache.find(MBB);
647 if (I == LiveOutCache.end() || I->second.second == Node) {
648 // We already have a live-out defined in MBB, so this must be IdxMBB.
649 assert(MBB == IdxMBB && "Adding phi-def to known live-out");
650 LI->addRange(LiveRange(Start, Idx.getNextSlot(), VNI));
652 // This phi-def is also live-out, so color the whole block.
653 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
654 I->second = LiveOutPair(VNI, Node);
656 } else if (IDomValue.first) {
657 // No phi-def here. Remember incoming value for IdxMBB.
659 IdxVNI = IDomValue.first;
660 // Propagate IDomValue if needed:
661 // MBB is live-out and doesn't define its own value.
662 LiveOutMap::iterator I = LiveOutCache.find(MBB);
663 if (I != LiveOutCache.end() && I->second.second != Node &&
664 I->second.first != IDomValue.first) {
666 I->second = IDomValue;
667 DEBUG(dbgs() << " - BB#" << MBB->getNumber()
668 << " idom valno #" << IDomValue.first->id
669 << " from BB#" << IDom->getBlock()->getNumber() << '\n');
673 DEBUG(dbgs() << " - made " << Changes << " changes.\n");
676 assert(IdxVNI && "Didn't find value for Idx");
679 // Check the LiveOutCache invariants.
680 for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end();
682 assert(I->first && "Null MBB entry in cache");
683 assert(I->second.first && "Null VNInfo in cache");
684 assert(I->second.second && "Null DomTreeNode in cache");
685 if (I->second.second->getBlock() == I->first)
687 for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(),
688 PE = I->first->pred_end(); PI != PE; ++PI)
689 assert(LiveOutCache.lookup(*PI) == I->second && "Bad invariant");
693 // Since we went through the trouble of a full BFS visiting all reaching defs,
694 // the values in LiveIn are now accurate. No more phi-defs are needed
695 // for these blocks, so we can color the live ranges.
696 // This makes the next mapValue call much faster.
697 for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) {
698 MachineBasicBlock *MBB = LiveIn[i]->getBlock();
699 SlotIndex Start = LIS.getMBBStartIdx(MBB);
700 VNInfo *VNI = LiveOutCache.lookup(MBB).first;
702 // Anything in LiveIn other than IdxMBB is live-through.
703 // In IdxMBB, we should stop at Idx unless the same value is live-out.
704 if (MBB == IdxMBB && IdxVNI != VNI)
705 LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI));
707 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
714 void LiveIntervalMap::dumpCache() {
715 for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end();
717 assert(I->first && "Null MBB entry in cache");
718 assert(I->second.first && "Null VNInfo in cache");
719 assert(I->second.second && "Null DomTreeNode in cache");
720 dbgs() << " cache: BB#" << I->first->getNumber()
721 << " has valno #" << I->second.first->id << " from BB#"
722 << I->second.second->getBlock()->getNumber() << ", preds";
723 for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(),
724 PE = I->first->pred_end(); PI != PE; ++PI)
725 dbgs() << " BB#" << (*PI)->getNumber();
728 dbgs() << " cache: " << LiveOutCache.size() << " entries.\n";
732 // extendTo - Find the last LI value defined in MBB at or before Idx. The
733 // ParentLI is assumed to be live at Idx. Extend the live range to Idx.
734 // Return the found VNInfo, or NULL.
735 VNInfo *LiveIntervalMap::extendTo(const MachineBasicBlock *MBB, SlotIndex Idx) {
736 assert(LI && "call reset first");
737 LiveInterval::iterator I = std::upper_bound(LI->begin(), LI->end(), Idx);
738 if (I == LI->begin())
741 if (I->end <= LIS.getMBBStartIdx(MBB))
744 I->end = Idx.getNextSlot();
748 // addSimpleRange - Add a simple range from ParentLI to LI.
749 // ParentVNI must be live in the [Start;End) interval.
750 void LiveIntervalMap::addSimpleRange(SlotIndex Start, SlotIndex End,
751 const VNInfo *ParentVNI) {
752 assert(LI && "call reset first");
754 VNInfo *VNI = mapValue(ParentVNI, Start, &simple);
755 // A simple mapping is easy.
757 LI->addRange(LiveRange(Start, End, VNI));
761 // ParentVNI is a complex value. We must map per MBB.
762 MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start);
763 MachineFunction::iterator MBBE = LIS.getMBBFromIndex(End.getPrevSlot());
766 LI->addRange(LiveRange(Start, End, VNI));
771 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
773 // Run sequence of full blocks.
774 for (++MBB; MBB != MBBE; ++MBB) {
775 Start = LIS.getMBBStartIdx(MBB);
776 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB),
777 mapValue(ParentVNI, Start)));
781 Start = LIS.getMBBStartIdx(MBB);
783 LI->addRange(LiveRange(Start, End, mapValue(ParentVNI, Start)));
786 /// addRange - Add live ranges to LI where [Start;End) intersects ParentLI.
787 /// All needed values whose def is not inside [Start;End) must be defined
788 /// beforehand so mapValue will work.
789 void LiveIntervalMap::addRange(SlotIndex Start, SlotIndex End) {
790 assert(LI && "call reset first");
791 LiveInterval::const_iterator B = ParentLI.begin(), E = ParentLI.end();
792 LiveInterval::const_iterator I = std::lower_bound(B, E, Start);
794 // Check if --I begins before Start and overlaps.
798 addSimpleRange(Start, std::min(End, I->end), I->valno);
802 // The remaining ranges begin after Start.
803 for (;I != E && I->start < End; ++I)
804 addSimpleRange(I->start, std::min(End, I->end), I->valno);
808 //===----------------------------------------------------------------------===//
810 //===----------------------------------------------------------------------===//
812 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
813 SplitEditor::SplitEditor(SplitAnalysis &sa,
816 MachineDominatorTree &mdt,
818 : sa_(sa), LIS(lis), VRM(vrm),
819 MRI(vrm.getMachineFunction().getRegInfo()),
821 TII(*vrm.getMachineFunction().getTarget().getInstrInfo()),
822 TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()),
827 // We don't need an AliasAnalysis since we will only be performing
828 // cheap-as-a-copy remats anyway.
829 Edit.anyRematerializable(LIS, TII, 0);
832 void SplitEditor::dump() const {
833 if (RegAssign.empty()) {
834 dbgs() << " empty\n";
838 for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
839 dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
843 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
846 MachineBasicBlock &MBB,
847 MachineBasicBlock::iterator I) {
848 MachineInstr *CopyMI = 0;
850 LiveInterval *LI = Edit.get(RegIdx);
852 // Attempt cheap-as-a-copy rematerialization.
853 LiveRangeEdit::Remat RM(ParentVNI);
854 if (Edit.canRematerializeAt(RM, UseIdx, true, LIS)) {
855 Def = Edit.rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI);
857 // Can't remat, just insert a copy from parent.
858 CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
859 .addReg(Edit.getReg());
860 Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex();
863 // Define the value in Reg.
864 VNInfo *VNI = LIMappers[RegIdx].defValue(ParentVNI, Def);
865 VNI->setCopy(CopyMI);
867 // Add minimal liveness for the new value.
868 Edit.get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
872 /// Create a new virtual register and live interval.
873 void SplitEditor::openIntv() {
874 assert(!OpenIdx && "Previous LI not closed before openIntv");
876 // Create the complement as index 0.
878 Edit.create(MRI, LIS, VRM);
879 LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent()));
880 LIMappers.back().reset(Edit.get(0));
883 // Create the open interval.
884 OpenIdx = Edit.size();
885 Edit.create(MRI, LIS, VRM);
886 LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent()));
887 LIMappers[OpenIdx].reset(Edit.get(OpenIdx));
890 SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
891 assert(OpenIdx && "openIntv not called before enterIntvBefore");
892 DEBUG(dbgs() << " enterIntvBefore " << Idx);
893 Idx = Idx.getBaseIndex();
894 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
896 DEBUG(dbgs() << ": not live\n");
899 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
900 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
901 assert(MI && "enterIntvBefore called with invalid index");
903 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
907 SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
908 assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
909 SlotIndex End = LIS.getMBBEndIdx(&MBB);
910 SlotIndex Last = End.getPrevSlot();
911 DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last);
912 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Last);
914 DEBUG(dbgs() << ": not live\n");
917 DEBUG(dbgs() << ": valno " << ParentVNI->id);
918 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
919 LIS.getLastSplitPoint(Edit.getParent(), &MBB));
920 RegAssign.insert(VNI->def, End, OpenIdx);
925 /// useIntv - indicate that all instructions in MBB should use OpenLI.
926 void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
927 useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));
930 void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
931 assert(OpenIdx && "openIntv not called before useIntv");
932 DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):");
933 RegAssign.insert(Start, End, OpenIdx);
937 SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {
938 assert(OpenIdx && "openIntv not called before leaveIntvAfter");
939 DEBUG(dbgs() << " leaveIntvAfter " << Idx);
941 // The interval must be live beyond the instruction at Idx.
942 Idx = Idx.getBoundaryIndex();
943 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
945 DEBUG(dbgs() << ": not live\n");
946 return Idx.getNextSlot();
948 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
950 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
951 assert(MI && "No instruction at index");
952 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(),
953 llvm::next(MachineBasicBlock::iterator(MI)));
957 SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {
958 assert(OpenIdx && "openIntv not called before leaveIntvBefore");
959 DEBUG(dbgs() << " leaveIntvBefore " << Idx);
961 // The interval must be live into the instruction at Idx.
962 Idx = Idx.getBoundaryIndex();
963 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
965 DEBUG(dbgs() << ": not live\n");
966 return Idx.getNextSlot();
968 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
970 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
971 assert(MI && "No instruction at index");
972 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
976 SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
977 assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
978 SlotIndex Start = LIS.getMBBStartIdx(&MBB);
979 DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start);
981 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Start);
983 DEBUG(dbgs() << ": not live\n");
987 VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
988 MBB.SkipPHIsAndLabels(MBB.begin()));
989 RegAssign.insert(Start, VNI->def, OpenIdx);
994 void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
995 assert(OpenIdx && "openIntv not called before overlapIntv");
996 assert(Edit.getParent().getVNInfoAt(Start) ==
997 Edit.getParent().getVNInfoAt(End.getPrevSlot()) &&
998 "Parent changes value in extended range");
999 assert(Edit.get(0)->getVNInfoAt(Start) && "Start must come from leaveIntv*");
1000 assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
1001 "Range cannot span basic blocks");
1003 // Treat this as useIntv() for now. The complement interval will be extended
1004 // as needed by mapValue().
1005 DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):");
1006 RegAssign.insert(Start, End, OpenIdx);
1010 /// closeIntv - Indicate that we are done editing the currently open
1011 /// LiveInterval, and ranges can be trimmed.
1012 void SplitEditor::closeIntv() {
1013 assert(OpenIdx && "openIntv not called before closeIntv");
1017 /// rewriteAssigned - Rewrite all uses of Edit.getReg().
1018 void SplitEditor::rewriteAssigned() {
1019 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit.getReg()),
1020 RE = MRI.reg_end(); RI != RE;) {
1021 MachineOperand &MO = RI.getOperand();
1022 MachineInstr *MI = MO.getParent();
1024 // LiveDebugVariables should have handled all DBG_VALUE instructions.
1025 if (MI->isDebugValue()) {
1026 DEBUG(dbgs() << "Zapping " << *MI);
1031 // <undef> operands don't really read the register, so just assign them to
1033 if (MO.isUse() && MO.isUndef()) {
1034 MO.setReg(Edit.get(0)->reg);
1038 SlotIndex Idx = LIS.getInstructionIndex(MI);
1039 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
1041 // Rewrite to the mapped register at Idx.
1042 unsigned RegIdx = RegAssign.lookup(Idx);
1043 MO.setReg(Edit.get(RegIdx)->reg);
1044 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t'
1045 << Idx << ':' << RegIdx << '\t' << *MI);
1047 // Extend liveness to Idx.
1048 const VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
1049 LIMappers[RegIdx].mapValue(ParentVNI, Idx);
1053 /// rewriteSplit - Rewrite uses of Intvs[0] according to the ConEQ mapping.
1054 void SplitEditor::rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs,
1055 const ConnectedVNInfoEqClasses &ConEq) {
1056 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Intvs[0]->reg),
1057 RE = MRI.reg_end(); RI != RE;) {
1058 MachineOperand &MO = RI.getOperand();
1059 MachineInstr *MI = MO.getParent();
1061 if (MO.isUse() && MO.isUndef())
1063 // DBG_VALUE instructions should have been eliminated earlier.
1064 SlotIndex Idx = LIS.getInstructionIndex(MI);
1065 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
1066 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t'
1068 const VNInfo *VNI = Intvs[0]->getVNInfoAt(Idx);
1069 assert(VNI && "Interval not live at use.");
1070 MO.setReg(Intvs[ConEq.getEqClass(VNI)]->reg);
1071 DEBUG(dbgs() << VNI->id << '\t' << *MI);
1075 void SplitEditor::finish() {
1076 assert(OpenIdx == 0 && "Previous LI not closed before rewrite");
1078 // At this point, the live intervals in Edit contain VNInfos corresponding to
1079 // the inserted copies.
1081 // Add the original defs from the parent interval.
1082 for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(),
1083 E = Edit.getParent().vni_end(); I != E; ++I) {
1084 const VNInfo *ParentVNI = *I;
1085 if (ParentVNI->isUnused())
1087 LiveIntervalMap &LIM = LIMappers[RegAssign.lookup(ParentVNI->def)];
1088 VNInfo *VNI = LIM.defValue(ParentVNI, ParentVNI->def);
1089 LIM.getLI()->addRange(LiveRange(ParentVNI->def,
1090 ParentVNI->def.getNextSlot(), VNI));
1091 // Mark all values as complex to force liveness computation.
1092 // This should really only be necessary for remat victims, but we are lazy.
1093 LIM.markComplexMapped(ParentVNI);
1097 // Every new interval must have a def by now, otherwise the split is bogus.
1098 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I)
1099 assert((*I)->hasAtLeastOneValue() && "Split interval has no value");
1102 // FIXME: Don't recompute the liveness of all values, infer it from the
1103 // overlaps between the parent live interval and RegAssign.
1104 // The mapValue algorithm is only necessary when:
1105 // - The parent value maps to multiple defs, and new phis are needed, or
1106 // - The value has been rematerialized before some uses, and we want to
1107 // minimize the live range so it only reaches the remaining uses.
1108 // All other values have simple liveness that can be computed from RegAssign
1109 // and the parent live interval.
1111 // Extend live ranges to be live-out for successor PHI values.
1112 for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(),
1113 E = Edit.getParent().vni_end(); I != E; ++I) {
1114 const VNInfo *PHIVNI = *I;
1115 if (PHIVNI->isUnused() || !PHIVNI->isPHIDef())
1117 unsigned RegIdx = RegAssign.lookup(PHIVNI->def);
1118 LiveIntervalMap &LIM = LIMappers[RegIdx];
1119 MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def);
1120 DEBUG(dbgs() << " map phi in BB#" << MBB->getNumber() << '@' << PHIVNI->def
1121 << " -> " << RegIdx << '\n');
1122 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
1123 PE = MBB->pred_end(); PI != PE; ++PI) {
1124 SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot();
1125 DEBUG(dbgs() << " pred BB#" << (*PI)->getNumber() << '@' << End);
1126 // The predecessor may not have a live-out value. That is OK, like an
1127 // undef PHI operand.
1128 if (VNInfo *VNI = Edit.getParent().getVNInfoAt(End)) {
1129 DEBUG(dbgs() << " has parent valno #" << VNI->id << " live out\n");
1130 assert(RegAssign.lookup(End) == RegIdx &&
1131 "Different register assignment in phi predecessor");
1132 LIM.mapValue(VNI, End);
1135 DEBUG(dbgs() << " is not live-out\n");
1137 DEBUG(dbgs() << " " << *LIM.getLI() << '\n');
1140 // Rewrite instructions.
1143 // FIXME: Delete defs that were rematted everywhere.
1145 // Get rid of unused values and set phi-kill flags.
1146 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I)
1147 (*I)->RenumberValues(LIS);
1149 // Now check if any registers were separated into multiple components.
1150 ConnectedVNInfoEqClasses ConEQ(LIS);
1151 for (unsigned i = 0, e = Edit.size(); i != e; ++i) {
1152 // Don't use iterators, they are invalidated by create() below.
1153 LiveInterval *li = Edit.get(i);
1154 unsigned NumComp = ConEQ.Classify(li);
1157 DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n');
1158 SmallVector<LiveInterval*, 8> dups;
1160 for (unsigned i = 1; i != NumComp; ++i)
1161 dups.push_back(&Edit.create(MRI, LIS, VRM));
1162 rewriteComponents(dups, ConEQ);
1163 ConEQ.Distribute(&dups[0]);
1166 // Calculate spill weight and allocation hints for new intervals.
1167 VirtRegAuxInfo vrai(VRM.getMachineFunction(), LIS, sa_.Loops);
1168 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I){
1169 LiveInterval &li = **I;
1170 vrai.CalculateRegClass(li.reg);
1171 vrai.CalculateWeightAndHint(li);
1172 DEBUG(dbgs() << " new interval " << MRI.getRegClass(li.reg)->getName()
1173 << ":" << li << '\n');
1178 //===----------------------------------------------------------------------===//
1180 //===----------------------------------------------------------------------===//
1182 void SplitEditor::splitAroundLoop(const MachineLoop *Loop) {
1183 SplitAnalysis::LoopBlocks Blocks;
1184 sa_.getLoopBlocks(Loop, Blocks);
1187 dbgs() << " splitAround"; sa_.print(Blocks, dbgs()); dbgs() << '\n';
1190 // Break critical edges as needed.
1191 SplitAnalysis::BlockPtrSet CriticalExits;
1192 sa_.getCriticalExits(Blocks, CriticalExits);
1193 assert(CriticalExits.empty() && "Cannot break critical exits yet");
1195 // Create new live interval for the loop.
1198 // Insert copies in the predecessors if live-in to the header.
1199 if (LIS.isLiveInToMBB(Edit.getParent(), Loop->getHeader())) {
1200 for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Preds.begin(),
1201 E = Blocks.Preds.end(); I != E; ++I) {
1202 MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I);
1203 enterIntvAtEnd(MBB);
1207 // Switch all loop blocks.
1208 for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Loop.begin(),
1209 E = Blocks.Loop.end(); I != E; ++I)
1212 // Insert back copies in the exit blocks.
1213 for (SplitAnalysis::BlockPtrSet::iterator I = Blocks.Exits.begin(),
1214 E = Blocks.Exits.end(); I != E; ++I) {
1215 MachineBasicBlock &MBB = const_cast<MachineBasicBlock&>(**I);
1216 leaveIntvAtTop(MBB);
1225 //===----------------------------------------------------------------------===//
1226 // Single Block Splitting
1227 //===----------------------------------------------------------------------===//
1229 /// getMultiUseBlocks - if CurLI has more than one use in a basic block, it
1230 /// may be an advantage to split CurLI for the duration of the block.
1231 bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) {
1232 // If CurLI is local to one block, there is no point to splitting it.
1233 if (LiveBlocks.size() <= 1)
1235 // Add blocks with multiple uses.
1236 for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
1237 const BlockInfo &BI = LiveBlocks[i];
1240 unsigned Instrs = UsingBlocks.lookup(BI.MBB);
1243 if (Instrs == 2 && BI.LiveIn && BI.LiveOut && !BI.LiveThrough)
1245 Blocks.insert(BI.MBB);
1247 return !Blocks.empty();
1250 /// splitSingleBlocks - Split CurLI into a separate live interval inside each
1251 /// basic block in Blocks.
1252 void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) {
1253 DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n");
1255 for (unsigned i = 0, e = sa_.LiveBlocks.size(); i != e; ++i) {
1256 const SplitAnalysis::BlockInfo &BI = sa_.LiveBlocks[i];
1257 if (!BI.Uses || !Blocks.count(BI.MBB))
1261 SlotIndex SegStart = enterIntvBefore(BI.FirstUse);
1262 if (BI.LastUse < BI.LastSplitPoint) {
1263 useIntv(SegStart, leaveIntvAfter(BI.LastUse));
1265 // THe last use os after tha last valid split point.
1266 SlotIndex SegStop = leaveIntvBefore(BI.LastSplitPoint);
1267 useIntv(SegStart, SegStop);
1268 overlapIntv(SegStop, BI.LastUse);
1276 //===----------------------------------------------------------------------===//
1277 // Sub Block Splitting
1278 //===----------------------------------------------------------------------===//
1280 /// getBlockForInsideSplit - If CurLI is contained inside a single basic block,
1281 /// and it wou pay to subdivide the interval inside that block, return it.
1282 /// Otherwise return NULL. The returned block can be passed to
1283 /// SplitEditor::splitInsideBlock.
1284 const MachineBasicBlock *SplitAnalysis::getBlockForInsideSplit() {
1285 // The interval must be exclusive to one block.
1286 if (UsingBlocks.size() != 1)
1288 // Don't to this for less than 4 instructions. We want to be sure that
1289 // splitting actually reduces the instruction count per interval.
1290 if (UsingInstrs.size() < 4)
1292 return UsingBlocks.begin()->first;
1295 /// splitInsideBlock - Split CurLI into multiple intervals inside MBB.
1296 void SplitEditor::splitInsideBlock(const MachineBasicBlock *MBB) {
1297 SmallVector<SlotIndex, 32> Uses;
1298 Uses.reserve(sa_.UsingInstrs.size());
1299 for (SplitAnalysis::InstrPtrSet::const_iterator I = sa_.UsingInstrs.begin(),
1300 E = sa_.UsingInstrs.end(); I != E; ++I)
1301 if ((*I)->getParent() == MBB)
1302 Uses.push_back(LIS.getInstructionIndex(*I));
1303 DEBUG(dbgs() << " splitInsideBlock BB#" << MBB->getNumber() << " for "
1304 << Uses.size() << " instructions.\n");
1305 assert(Uses.size() >= 3 && "Need at least 3 instructions");
1306 array_pod_sort(Uses.begin(), Uses.end());
1308 // Simple algorithm: Find the largest gap between uses as determined by slot
1309 // indices. Create new intervals for instructions before the gap and after the
1311 unsigned bestPos = 0;
1313 DEBUG(dbgs() << " dist (" << Uses[0]);
1314 for (unsigned i = 1, e = Uses.size(); i != e; ++i) {
1315 int g = Uses[i-1].distance(Uses[i]);
1316 DEBUG(dbgs() << ") -" << g << "- (" << Uses[i]);
1318 bestPos = i, bestGap = g;
1320 DEBUG(dbgs() << "), best: -" << bestGap << "-\n");
1322 // bestPos points to the first use after the best gap.
1323 assert(bestPos > 0 && "Invalid gap");
1325 // FIXME: Don't create intervals for low densities.
1327 // First interval before the gap. Don't create single-instr intervals.
1330 useIntv(enterIntvBefore(Uses.front()), leaveIntvAfter(Uses[bestPos-1]));
1334 // Second interval after the gap.
1335 if (bestPos < Uses.size()-1) {
1337 useIntv(enterIntvBefore(Uses[bestPos]), leaveIntvAfter(Uses.back()));