1 //===-- llvm/CodeGen/Splitter.cpp - Splitter -----------------------------===//
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 #define DEBUG_TYPE "loopsplitter"
14 #include "llvm/Module.h"
15 #include "llvm/CodeGen/CalcSpillWeights.h"
16 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
17 #include "llvm/CodeGen/LiveStackAnalysis.h"
18 #include "llvm/CodeGen/MachineDominators.h"
19 #include "llvm/CodeGen/MachineInstrBuilder.h"
20 #include "llvm/CodeGen/MachineFunction.h"
21 #include "llvm/CodeGen/MachineRegisterInfo.h"
22 #include "llvm/CodeGen/Passes.h"
23 #include "llvm/CodeGen/SlotIndexes.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/raw_ostream.h"
26 #include "llvm/Target/TargetMachine.h"
27 #include "llvm/Target/TargetInstrInfo.h"
31 char LoopSplitter::ID = 0;
32 INITIALIZE_PASS_BEGIN(LoopSplitter, "loop-splitting",
33 "Split virtual regists across loop boundaries.", false, false)
34 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
35 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
36 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
37 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
38 INITIALIZE_PASS_END(LoopSplitter, "loop-splitting",
39 "Split virtual regists across loop boundaries.", false, false)
42 class StartSlotComparator {
44 StartSlotComparator(LiveIntervals &lis) : lis(lis) {}
45 bool operator()(const MachineBasicBlock *mbb1,
46 const MachineBasicBlock *mbb2) const {
47 return lis.getMBBStartIdx(mbb1) < lis.getMBBStartIdx(mbb2);
58 LoopSplit(LoopSplitter &ls, LiveInterval &li, MachineLoop &loop)
59 : ls(ls), li(li), loop(loop), valid(true), inSplit(false), newLI(0) {
60 assert(TargetRegisterInfo::isVirtualRegister(li.reg) &&
61 "Cannot split physical registers.");
64 LiveInterval& getLI() const { return li; }
66 MachineLoop& getLoop() const { return loop; }
68 bool isValid() const { return valid; }
70 bool isWorthwhile() const { return valid && (inSplit || !outSplits.empty()); }
72 void invalidate() { valid = false; }
74 void splitIncoming() { inSplit = true; }
76 void splitOutgoing(MachineLoop::Edge &edge) { outSplits.insert(edge); }
78 void addLoopInstr(MachineInstr *i) { loopInstrs.push_back(i); }
81 assert(valid && "Attempt to apply invalid split.");
93 std::set<MachineLoop::Edge> outSplits;
94 std::vector<MachineInstr*> loopInstrs;
97 std::map<VNInfo*, VNInfo*> vniMap;
99 LiveInterval* getNewLI() {
101 const TargetRegisterClass *trc = ls.mri->getRegClass(li.reg);
102 unsigned vreg = ls.mri->createVirtualRegister(trc);
103 newLI = &ls.lis->getOrCreateInterval(vreg);
108 VNInfo* getNewVNI(VNInfo *oldVNI) {
109 VNInfo *newVNI = vniMap[oldVNI];
112 newVNI = getNewLI()->createValueCopy(oldVNI,
113 ls.lis->getVNInfoAllocator());
114 vniMap[oldVNI] = newVNI;
120 void applyIncoming() {
125 MachineBasicBlock *preHeader = loop.getLoopPreheader();
126 if (preHeader == 0) {
127 assert(ls.canInsertPreHeader(loop) &&
128 "Can't insert required preheader.");
129 preHeader = &ls.insertPreHeader(loop);
132 LiveRange *preHeaderRange =
133 ls.lis->findExitingRange(li, preHeader);
134 assert(preHeaderRange != 0 && "Range not live into preheader.");
136 // Insert the new copy.
137 MachineInstr *copy = BuildMI(*preHeader,
138 preHeader->getFirstTerminator(),
140 ls.tii->get(TargetOpcode::COPY))
141 .addReg(getNewLI()->reg, RegState::Define)
142 .addReg(li.reg, RegState::Kill);
144 ls.lis->InsertMachineInstrInMaps(copy);
146 SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getRegSlot();
148 VNInfo *newVal = getNewVNI(preHeaderRange->valno);
149 newVal->def = copyDefIdx;
150 newVal->setCopy(copy);
151 li.removeRange(copyDefIdx, ls.lis->getMBBEndIdx(preHeader), true);
153 getNewLI()->addRange(LiveRange(copyDefIdx,
154 ls.lis->getMBBEndIdx(preHeader),
158 void applyOutgoing() {
160 for (std::set<MachineLoop::Edge>::iterator osItr = outSplits.begin(),
161 osEnd = outSplits.end();
162 osItr != osEnd; ++osItr) {
163 MachineLoop::Edge edge = *osItr;
164 MachineBasicBlock *outBlock = edge.second;
165 if (ls.isCriticalEdge(edge)) {
166 assert(ls.canSplitEdge(edge) && "Unsplitable critical edge.");
167 outBlock = &ls.splitEdge(edge, loop);
169 LiveRange *outRange = ls.lis->findEnteringRange(li, outBlock);
170 assert(outRange != 0 && "No exiting range?");
172 MachineInstr *copy = BuildMI(*outBlock, outBlock->begin(),
174 ls.tii->get(TargetOpcode::COPY))
175 .addReg(li.reg, RegState::Define)
176 .addReg(getNewLI()->reg, RegState::Kill);
178 ls.lis->InsertMachineInstrInMaps(copy);
180 SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getRegSlot();
182 // Blow away output range definition.
183 outRange->valno->def = ls.lis->getInvalidIndex();
184 li.removeRange(ls.lis->getMBBStartIdx(outBlock), copyDefIdx);
186 SlotIndex newDefIdx = ls.lis->getMBBStartIdx(outBlock);
187 assert(ls.lis->getInstructionFromIndex(newDefIdx) == 0 &&
188 "PHI def index points at actual instruction.");
190 getNewLI()->getNextValue(newDefIdx, 0, ls.lis->getVNInfoAllocator());
192 getNewLI()->addRange(LiveRange(ls.lis->getMBBStartIdx(outBlock),
193 copyDefIdx, newVal));
198 void copyRange(LiveRange &lr) {
199 std::pair<bool, LoopSplitter::SlotPair> lsr =
200 ls.getLoopSubRange(lr, loop);
205 LiveRange loopRange(lsr.second.first, lsr.second.second,
206 getNewVNI(lr.valno));
208 li.removeRange(loopRange.start, loopRange.end, true);
210 getNewLI()->addRange(loopRange);
214 for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(),
215 iEnd = loopInstrs.end();
216 iItr != iEnd; ++iItr) {
217 MachineInstr &instr = **iItr;
218 SlotIndex instrIdx = ls.lis->getInstructionIndex(&instr);
219 if (instr.modifiesRegister(li.reg, 0)) {
220 LiveRange *defRange =
221 li.getLiveRangeContaining(instrIdx.getRegSlot());
222 if (defRange != 0) // May have caught this already.
223 copyRange(*defRange);
225 if (instr.readsRegister(li.reg, 0)) {
226 LiveRange *useRange =
227 li.getLiveRangeContaining(instrIdx.getRegSlot(true));
228 if (useRange != 0) { // May have caught this already.
229 copyRange(*useRange);
234 for (MachineLoop::block_iterator bbItr = loop.block_begin(),
235 bbEnd = loop.block_end();
236 bbItr != bbEnd; ++bbItr) {
237 MachineBasicBlock &loopBlock = **bbItr;
238 LiveRange *enteringRange =
239 ls.lis->findEnteringRange(li, &loopBlock);
240 if (enteringRange != 0) {
241 copyRange(*enteringRange);
246 void renameInside() {
247 for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(),
248 iEnd = loopInstrs.end();
249 iItr != iEnd; ++iItr) {
250 MachineInstr &instr = **iItr;
251 for (unsigned i = 0; i < instr.getNumOperands(); ++i) {
252 MachineOperand &mop = instr.getOperand(i);
253 if (mop.isReg() && mop.getReg() == li.reg) {
254 mop.setReg(getNewLI()->reg);
262 void LoopSplitter::getAnalysisUsage(AnalysisUsage &au) const {
263 au.addRequired<MachineDominatorTree>();
264 au.addPreserved<MachineDominatorTree>();
265 au.addRequired<MachineLoopInfo>();
266 au.addPreserved<MachineLoopInfo>();
267 au.addPreservedID(RegisterCoalescerPassID);
268 au.addPreserved<CalculateSpillWeights>();
269 au.addPreserved<LiveStacks>();
270 au.addRequired<SlotIndexes>();
271 au.addPreserved<SlotIndexes>();
272 au.addRequired<LiveIntervals>();
273 au.addPreserved<LiveIntervals>();
274 MachineFunctionPass::getAnalysisUsage(au);
277 bool LoopSplitter::runOnMachineFunction(MachineFunction &fn) {
280 mri = &mf->getRegInfo();
281 tii = mf->getTarget().getInstrInfo();
282 tri = mf->getTarget().getRegisterInfo();
283 sis = &getAnalysis<SlotIndexes>();
284 lis = &getAnalysis<LiveIntervals>();
285 mli = &getAnalysis<MachineLoopInfo>();
286 mdt = &getAnalysis<MachineDominatorTree>();
288 fqn = mf->getFunction()->getParent()->getModuleIdentifier() + "." +
289 mf->getFunction()->getName().str();
291 dbgs() << "Splitting " << mf->getFunction()->getName() << ".";
293 dumpOddTerminators();
295 // dbgs() << "----------------------------------------\n";
297 // dbgs() << "----------------------------------------\n";
299 // std::deque<MachineLoop*> loops;
300 // std::copy(mli->begin(), mli->end(), std::back_inserter(loops));
301 // dbgs() << "Loops:\n";
302 // while (!loops.empty()) {
303 // MachineLoop &loop = *loops.front();
304 // loops.pop_front();
305 // std::copy(loop.begin(), loop.end(), std::back_inserter(loops));
307 // dumpLoopInfo(loop);
313 // Setup initial intervals.
314 for (LiveIntervals::iterator liItr = lis->begin(), liEnd = lis->end();
315 liItr != liEnd; ++liItr) {
316 LiveInterval *li = liItr->second;
318 if (TargetRegisterInfo::isVirtualRegister(li->reg) &&
319 !lis->intervalIsInOneMBB(*li)) {
320 intervals.push_back(li);
328 // dbgs() << "----------------------------------------\n";
330 // dbgs() << "----------------------------------------\n";
332 dumpOddTerminators();
339 void LoopSplitter::releaseMemory() {
342 loopRangeMap.clear();
345 void LoopSplitter::dumpOddTerminators() {
346 for (MachineFunction::iterator bbItr = mf->begin(), bbEnd = mf->end();
347 bbItr != bbEnd; ++bbItr) {
348 MachineBasicBlock *mbb = &*bbItr;
349 MachineBasicBlock *a = 0, *b = 0;
350 SmallVector<MachineOperand, 4> c;
351 if (tii->AnalyzeBranch(*mbb, a, b, c)) {
352 dbgs() << "MBB#" << mbb->getNumber() << " has multiway terminator.\n";
353 dbgs() << " Terminators:\n";
354 for (MachineBasicBlock::iterator iItr = mbb->begin(), iEnd = mbb->end();
355 iItr != iEnd; ++iItr) {
356 MachineInstr *instr= &*iItr;
357 dbgs() << " " << *instr << "";
359 dbgs() << "\n Listed successors: [ ";
360 for (MachineBasicBlock::succ_iterator sItr = mbb->succ_begin(), sEnd = mbb->succ_end();
361 sItr != sEnd; ++sItr) {
362 MachineBasicBlock *succMBB = *sItr;
363 dbgs() << succMBB->getNumber() << " ";
370 void LoopSplitter::dumpLoopInfo(MachineLoop &loop) {
371 MachineBasicBlock &headerBlock = *loop.getHeader();
372 typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList;
373 ExitEdgesList exitEdges;
374 loop.getExitEdges(exitEdges);
376 dbgs() << " Header: BB#" << headerBlock.getNumber() << ", Contains: [ ";
377 for (std::vector<MachineBasicBlock*>::const_iterator
378 subBlockItr = loop.getBlocks().begin(),
379 subBlockEnd = loop.getBlocks().end();
380 subBlockItr != subBlockEnd; ++subBlockItr) {
381 MachineBasicBlock &subBlock = **subBlockItr;
382 dbgs() << "BB#" << subBlock.getNumber() << " ";
384 dbgs() << "], Exit edges: [ ";
385 for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(),
386 exitEdgeEnd = exitEdges.end();
387 exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) {
388 MachineLoop::Edge &exitEdge = *exitEdgeItr;
389 dbgs() << "(MBB#" << exitEdge.first->getNumber()
390 << ", MBB#" << exitEdge.second->getNumber() << ") ";
392 dbgs() << "], Sub-Loop Headers: [ ";
393 for (MachineLoop::iterator subLoopItr = loop.begin(),
394 subLoopEnd = loop.end();
395 subLoopItr != subLoopEnd; ++subLoopItr) {
396 MachineLoop &subLoop = **subLoopItr;
397 MachineBasicBlock &subLoopBlock = *subLoop.getHeader();
398 dbgs() << "BB#" << subLoopBlock.getNumber() << " ";
403 void LoopSplitter::updateTerminators(MachineBasicBlock &mbb) {
404 mbb.updateTerminator();
406 for (MachineBasicBlock::iterator miItr = mbb.begin(), miEnd = mbb.end();
407 miItr != miEnd; ++miItr) {
408 if (lis->isNotInMIMap(miItr)) {
409 lis->InsertMachineInstrInMaps(miItr);
414 bool LoopSplitter::canInsertPreHeader(MachineLoop &loop) {
415 MachineBasicBlock *header = loop.getHeader();
416 MachineBasicBlock *a = 0, *b = 0;
417 SmallVector<MachineOperand, 4> c;
419 for (MachineBasicBlock::pred_iterator pbItr = header->pred_begin(),
420 pbEnd = header->pred_end();
421 pbItr != pbEnd; ++pbItr) {
422 MachineBasicBlock *predBlock = *pbItr;
423 if (!!tii->AnalyzeBranch(*predBlock, a, b, c)) {
428 MachineFunction::iterator headerItr(header);
429 if (headerItr == mf->begin())
431 MachineBasicBlock *headerLayoutPred = llvm::prior(headerItr);
432 assert(headerLayoutPred != 0 && "Header should have layout pred.");
434 return (!tii->AnalyzeBranch(*headerLayoutPred, a, b, c));
437 MachineBasicBlock& LoopSplitter::insertPreHeader(MachineLoop &loop) {
438 assert(loop.getLoopPreheader() == 0 && "Loop already has preheader.");
440 MachineBasicBlock &header = *loop.getHeader();
442 // Save the preds - we'll need to update them once we insert the preheader.
443 typedef std::set<MachineBasicBlock*> HeaderPreds;
444 HeaderPreds headerPreds;
446 for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(),
447 predEnd = header.pred_end();
448 predItr != predEnd; ++predItr) {
449 if (!loop.contains(*predItr))
450 headerPreds.insert(*predItr);
453 assert(!headerPreds.empty() && "No predecessors for header?");
455 //dbgs() << fqn << " MBB#" << header.getNumber() << " inserting preheader...";
457 MachineBasicBlock *preHeader =
458 mf->CreateMachineBasicBlock(header.getBasicBlock());
460 assert(preHeader != 0 && "Failed to create pre-header.");
462 mf->insert(header, preHeader);
464 for (HeaderPreds::iterator hpItr = headerPreds.begin(),
465 hpEnd = headerPreds.end();
466 hpItr != hpEnd; ++hpItr) {
467 assert(*hpItr != 0 && "How'd a null predecessor get into this set?");
468 MachineBasicBlock &hp = **hpItr;
469 hp.ReplaceUsesOfBlockWith(&header, preHeader);
471 preHeader->addSuccessor(&header);
473 MachineBasicBlock *oldLayoutPred =
474 llvm::prior(MachineFunction::iterator(preHeader));
475 if (oldLayoutPred != 0) {
476 updateTerminators(*oldLayoutPred);
479 lis->InsertMBBInMaps(preHeader);
481 if (MachineLoop *parentLoop = loop.getParentLoop()) {
482 assert(parentLoop->getHeader() != loop.getHeader() &&
483 "Parent loop has same header?");
484 parentLoop->addBasicBlockToLoop(preHeader, mli->getBase());
486 // Invalidate all parent loop ranges.
487 while (parentLoop != 0) {
488 loopRangeMap.erase(parentLoop);
489 parentLoop = parentLoop->getParentLoop();
493 for (LiveIntervals::iterator liItr = lis->begin(),
495 liItr != liEnd; ++liItr) {
496 LiveInterval &li = *liItr->second;
498 // Is this safe for physregs?
499 // TargetRegisterInfo::isPhysicalRegister(li.reg) ||
500 if (!lis->isLiveInToMBB(li, &header))
503 if (lis->isLiveInToMBB(li, preHeader)) {
504 assert(lis->isLiveOutOfMBB(li, preHeader) &&
505 "Range terminates in newly added preheader?");
509 bool insertRange = false;
511 for (MachineBasicBlock::pred_iterator predItr = preHeader->pred_begin(),
512 predEnd = preHeader->pred_end();
513 predItr != predEnd; ++predItr) {
514 MachineBasicBlock *predMBB = *predItr;
515 if (lis->isLiveOutOfMBB(li, predMBB)) {
524 SlotIndex newDefIdx = lis->getMBBStartIdx(preHeader);
525 assert(lis->getInstructionFromIndex(newDefIdx) == 0 &&
526 "PHI def index points at actual instruction.");
527 VNInfo *newVal = li.getNextValue(newDefIdx, 0, lis->getVNInfoAllocator());
528 li.addRange(LiveRange(lis->getMBBStartIdx(preHeader),
529 lis->getMBBEndIdx(preHeader),
534 //dbgs() << "Dumping SlotIndexes:\n";
537 //dbgs() << "done. (Added MBB#" << preHeader->getNumber() << ")\n";
542 bool LoopSplitter::isCriticalEdge(MachineLoop::Edge &edge) {
543 assert(edge.first->succ_size() > 1 && "Non-sensical edge.");
544 if (edge.second->pred_size() > 1)
549 bool LoopSplitter::canSplitEdge(MachineLoop::Edge &edge) {
550 MachineFunction::iterator outBlockItr(edge.second);
551 if (outBlockItr == mf->begin())
553 MachineBasicBlock *outBlockLayoutPred = llvm::prior(outBlockItr);
554 assert(outBlockLayoutPred != 0 && "Should have a layout pred if out!=begin.");
555 MachineBasicBlock *a = 0, *b = 0;
556 SmallVector<MachineOperand, 4> c;
557 return (!tii->AnalyzeBranch(*outBlockLayoutPred, a, b, c) &&
558 !tii->AnalyzeBranch(*edge.first, a, b, c));
561 MachineBasicBlock& LoopSplitter::splitEdge(MachineLoop::Edge &edge,
564 MachineBasicBlock &inBlock = *edge.first;
565 MachineBasicBlock &outBlock = *edge.second;
567 assert((inBlock.succ_size() > 1) && (outBlock.pred_size() > 1) &&
568 "Splitting non-critical edge?");
570 //dbgs() << fqn << " Splitting edge (MBB#" << inBlock.getNumber()
571 // << " -> MBB#" << outBlock.getNumber() << ")...";
573 MachineBasicBlock *splitBlock =
574 mf->CreateMachineBasicBlock();
576 assert(splitBlock != 0 && "Failed to create split block.");
578 mf->insert(&outBlock, splitBlock);
580 inBlock.ReplaceUsesOfBlockWith(&outBlock, splitBlock);
581 splitBlock->addSuccessor(&outBlock);
583 MachineBasicBlock *oldLayoutPred =
584 llvm::prior(MachineFunction::iterator(splitBlock));
585 if (oldLayoutPred != 0) {
586 updateTerminators(*oldLayoutPred);
589 lis->InsertMBBInMaps(splitBlock);
591 loopRangeMap.erase(&loop);
593 MachineLoop *splitParentLoop = loop.getParentLoop();
594 while (splitParentLoop != 0 &&
595 !splitParentLoop->contains(&outBlock)) {
596 splitParentLoop = splitParentLoop->getParentLoop();
599 if (splitParentLoop != 0) {
600 assert(splitParentLoop->contains(&loop) &&
601 "Split-block parent doesn't contain original loop?");
602 splitParentLoop->addBasicBlockToLoop(splitBlock, mli->getBase());
604 // Invalidate all parent loop ranges.
605 while (splitParentLoop != 0) {
606 loopRangeMap.erase(splitParentLoop);
607 splitParentLoop = splitParentLoop->getParentLoop();
612 for (LiveIntervals::iterator liItr = lis->begin(),
614 liItr != liEnd; ++liItr) {
615 LiveInterval &li = *liItr->second;
616 bool intersects = lis->isLiveOutOfMBB(li, &inBlock) &&
617 lis->isLiveInToMBB(li, &outBlock);
618 if (lis->isLiveInToMBB(li, splitBlock)) {
620 li.removeRange(lis->getMBBStartIdx(splitBlock),
621 lis->getMBBEndIdx(splitBlock), true);
623 } else if (intersects) {
624 SlotIndex newDefIdx = lis->getMBBStartIdx(splitBlock);
625 assert(lis->getInstructionFromIndex(newDefIdx) == 0 &&
626 "PHI def index points at actual instruction.");
627 VNInfo *newVal = li.getNextValue(newDefIdx, 0,
628 lis->getVNInfoAllocator());
629 li.addRange(LiveRange(lis->getMBBStartIdx(splitBlock),
630 lis->getMBBEndIdx(splitBlock),
635 //dbgs() << "done. (Added MBB#" << splitBlock->getNumber() << ")\n";
640 LoopSplitter::LoopRanges& LoopSplitter::getLoopRanges(MachineLoop &loop) {
641 typedef std::set<MachineBasicBlock*, StartSlotComparator> LoopMBBSet;
642 LoopRangeMap::iterator lrItr = loopRangeMap.find(&loop);
643 if (lrItr == loopRangeMap.end()) {
644 LoopMBBSet loopMBBs((StartSlotComparator(*lis)));
645 std::copy(loop.block_begin(), loop.block_end(),
646 std::inserter(loopMBBs, loopMBBs.begin()));
648 assert(!loopMBBs.empty() && "No blocks in loop?");
650 LoopRanges &loopRanges = loopRangeMap[&loop];
651 assert(loopRanges.empty() && "Loop encountered but not processed?");
652 SlotIndex oldEnd = lis->getMBBEndIdx(*loopMBBs.begin());
653 loopRanges.push_back(
654 std::make_pair(lis->getMBBStartIdx(*loopMBBs.begin()),
655 lis->getInvalidIndex()));
656 for (LoopMBBSet::iterator curBlockItr = llvm::next(loopMBBs.begin()),
657 curBlockEnd = loopMBBs.end();
658 curBlockItr != curBlockEnd; ++curBlockItr) {
659 SlotIndex newStart = lis->getMBBStartIdx(*curBlockItr);
660 if (newStart != oldEnd) {
661 loopRanges.back().second = oldEnd;
662 loopRanges.push_back(std::make_pair(newStart,
663 lis->getInvalidIndex()));
665 oldEnd = lis->getMBBEndIdx(*curBlockItr);
668 loopRanges.back().second =
669 lis->getMBBEndIdx(*llvm::prior(loopMBBs.end()));
673 return lrItr->second;
676 std::pair<bool, LoopSplitter::SlotPair> LoopSplitter::getLoopSubRange(
679 LoopRanges &loopRanges = getLoopRanges(loop);
680 LoopRanges::iterator lrItr = loopRanges.begin(),
681 lrEnd = loopRanges.end();
682 while (lrItr != lrEnd && lr.start >= lrItr->second) {
686 if (lrItr == lrEnd) {
687 SlotIndex invalid = lis->getInvalidIndex();
688 return std::make_pair(false, SlotPair(invalid, invalid));
691 SlotIndex srStart(lr.start < lrItr->first ? lrItr->first : lr.start);
692 SlotIndex srEnd(lr.end > lrItr->second ? lrItr->second : lr.end);
694 return std::make_pair(true, SlotPair(srStart, srEnd));
697 void LoopSplitter::dumpLoopRanges(MachineLoop &loop) {
698 LoopRanges &loopRanges = getLoopRanges(loop);
699 dbgs() << "For loop MBB#" << loop.getHeader()->getNumber() << ", subranges are: [ ";
700 for (LoopRanges::iterator lrItr = loopRanges.begin(), lrEnd = loopRanges.end();
701 lrItr != lrEnd; ++lrItr) {
702 dbgs() << "[" << lrItr->first << ", " << lrItr->second << ") ";
707 void LoopSplitter::processHeader(LoopSplit &split) {
708 MachineBasicBlock &header = *split.getLoop().getHeader();
709 //dbgs() << " Processing loop header BB#" << header.getNumber() << "\n";
711 if (!lis->isLiveInToMBB(split.getLI(), &header))
712 return; // Not live in, but nothing wrong so far.
714 MachineBasicBlock *preHeader = split.getLoop().getLoopPreheader();
717 if (!canInsertPreHeader(split.getLoop())) {
719 return; // Couldn't insert a pre-header. Bail on this interval.
722 for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(),
723 predEnd = header.pred_end();
724 predItr != predEnd; ++predItr) {
725 if (lis->isLiveOutOfMBB(split.getLI(), *predItr)) {
726 split.splitIncoming();
730 } else if (lis->isLiveOutOfMBB(split.getLI(), preHeader)) {
731 split.splitIncoming();
735 void LoopSplitter::processLoopExits(LoopSplit &split) {
736 typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList;
737 ExitEdgesList exitEdges;
738 split.getLoop().getExitEdges(exitEdges);
740 //dbgs() << " Processing loop exits:\n";
742 for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(),
743 exitEdgeEnd = exitEdges.end();
744 exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) {
745 MachineLoop::Edge exitEdge = *exitEdgeItr;
747 LiveRange *outRange =
748 split.getLI().getLiveRangeContaining(lis->getMBBStartIdx(exitEdge.second));
751 if (isCriticalEdge(exitEdge) && !canSplitEdge(exitEdge)) {
756 split.splitOutgoing(exitEdge);
761 void LoopSplitter::processLoopUses(LoopSplit &split) {
762 std::set<MachineInstr*> processed;
764 for (MachineRegisterInfo::reg_iterator
765 rItr = mri->reg_begin(split.getLI().reg),
766 rEnd = mri->reg_end();
767 rItr != rEnd; ++rItr) {
768 MachineInstr &instr = *rItr;
769 if (split.getLoop().contains(&instr) && processed.count(&instr) == 0) {
770 split.addLoopInstr(&instr);
771 processed.insert(&instr);
775 //dbgs() << " Rewriting reg" << li.reg << " to reg" << newLI->reg
776 // << " in blocks [ ";
780 bool LoopSplitter::splitOverLoop(LiveInterval &li, MachineLoop &loop) {
781 assert(TargetRegisterInfo::isVirtualRegister(li.reg) &&
782 "Attempt to split physical register.");
784 LoopSplit split(*this, li, loop);
785 processHeader(split);
787 processLoopExits(split);
789 processLoopUses(split);
790 if (split.isValid() /* && split.isWorthwhile() */) {
792 DEBUG(dbgs() << "Success.\n");
795 DEBUG(dbgs() << "Failed.\n");
799 void LoopSplitter::processInterval(LiveInterval &li) {
800 std::deque<MachineLoop*> loops;
801 std::copy(mli->begin(), mli->end(), std::back_inserter(loops));
803 while (!loops.empty()) {
804 MachineLoop &loop = *loops.front();
807 dbgs() << fqn << " reg" << li.reg << " " << li.weight << " BB#"
808 << loop.getHeader()->getNumber() << " ";
810 if (!splitOverLoop(li, loop)) {
811 // Couldn't split over outer loop, schedule sub-loops to be checked.
812 std::copy(loop.begin(), loop.end(), std::back_inserter(loops));
817 void LoopSplitter::processIntervals() {
818 while (!intervals.empty()) {
819 LiveInterval &li = *intervals.front();
820 intervals.pop_front();
822 assert(!lis->intervalIsInOneMBB(li) &&
823 "Single interval in process worklist.");