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 "SimpleRegisterCoalescing.h"
15 #include "llvm/Module.h"
16 #include "llvm/CodeGen/CalcSpillWeights.h"
17 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
18 #include "llvm/CodeGen/LiveStackAnalysis.h"
19 #include "llvm/CodeGen/MachineDominators.h"
20 #include "llvm/CodeGen/MachineInstrBuilder.h"
21 #include "llvm/CodeGen/MachineFunction.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.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(LoopSplitter, "loop-splitting",
33 "Split virtual regists across loop boundaries.", false, false);
37 class StartSlotComparator {
39 StartSlotComparator(LiveIntervals &lis) : lis(lis) {}
40 bool operator()(const MachineBasicBlock *mbb1,
41 const MachineBasicBlock *mbb2) const {
42 return lis.getMBBStartIdx(mbb1) < lis.getMBBStartIdx(mbb2);
50 LoopSplit(LoopSplitter &ls, LiveInterval &li, MachineLoop &loop)
51 : ls(ls), li(li), loop(loop), valid(true), inSplit(false), newLI(0) {
52 assert(TargetRegisterInfo::isVirtualRegister(li.reg) &&
53 "Cannot split physical registers.");
56 LiveInterval& getLI() const { return li; }
58 MachineLoop& getLoop() const { return loop; }
60 bool isValid() const { return valid; }
62 bool isWorthwhile() const { return valid && (inSplit || !outSplits.empty()); }
64 void invalidate() { valid = false; }
66 void splitIncoming() { inSplit = true; }
68 void splitOutgoing(MachineLoop::Edge &edge) { outSplits.insert(edge); }
70 void addLoopInstr(MachineInstr *i) { loopInstrs.push_back(i); }
73 assert(valid && "Attempt to apply invalid split.");
85 std::set<MachineLoop::Edge> outSplits;
86 std::vector<MachineInstr*> loopInstrs;
89 std::map<VNInfo*, VNInfo*> vniMap;
91 LiveInterval* getNewLI() {
93 const TargetRegisterClass *trc = ls.mri->getRegClass(li.reg);
94 unsigned vreg = ls.mri->createVirtualRegister(trc);
95 newLI = &ls.lis->getOrCreateInterval(vreg);
100 VNInfo* getNewVNI(VNInfo *oldVNI) {
101 VNInfo *newVNI = vniMap[oldVNI];
104 newVNI = getNewLI()->createValueCopy(oldVNI,
105 ls.lis->getVNInfoAllocator());
106 vniMap[oldVNI] = newVNI;
112 void applyIncoming() {
117 MachineBasicBlock *preHeader = loop.getLoopPreheader();
118 if (preHeader == 0) {
119 assert(ls.canInsertPreHeader(loop) &&
120 "Can't insert required preheader.");
121 preHeader = &ls.insertPreHeader(loop);
124 LiveRange *preHeaderRange =
125 ls.lis->findExitingRange(li, preHeader);
126 assert(preHeaderRange != 0 && "Range not live into preheader.");
128 // Insert the new copy.
129 MachineInstr *copy = BuildMI(*preHeader,
130 preHeader->getFirstTerminator(),
132 ls.tii->get(TargetOpcode::COPY))
133 .addReg(getNewLI()->reg, RegState::Define)
134 .addReg(li.reg, RegState::Kill);
136 ls.lis->InsertMachineInstrInMaps(copy);
138 SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getDefIndex();
140 VNInfo *newVal = getNewVNI(preHeaderRange->valno);
141 newVal->def = copyDefIdx;
142 newVal->setCopy(copy);
143 li.removeRange(copyDefIdx, ls.lis->getMBBEndIdx(preHeader), true);
145 getNewLI()->addRange(LiveRange(copyDefIdx,
146 ls.lis->getMBBEndIdx(preHeader),
150 void applyOutgoing() {
152 for (std::set<MachineLoop::Edge>::iterator osItr = outSplits.begin(),
153 osEnd = outSplits.end();
154 osItr != osEnd; ++osItr) {
155 MachineLoop::Edge edge = *osItr;
156 MachineBasicBlock *outBlock = edge.second;
157 if (ls.isCriticalEdge(edge)) {
158 assert(ls.canSplitEdge(edge) && "Unsplitable critical edge.");
159 outBlock = &ls.splitEdge(edge, loop);
161 LiveRange *outRange = ls.lis->findEnteringRange(li, outBlock);
162 assert(outRange != 0 && "No exiting range?");
164 MachineInstr *copy = BuildMI(*outBlock, outBlock->begin(),
166 ls.tii->get(TargetOpcode::COPY))
167 .addReg(li.reg, RegState::Define)
168 .addReg(getNewLI()->reg, RegState::Kill);
170 ls.lis->InsertMachineInstrInMaps(copy);
172 SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getDefIndex();
174 // Blow away output range definition.
175 outRange->valno->def = ls.lis->getInvalidIndex();
176 li.removeRange(ls.lis->getMBBStartIdx(outBlock), copyDefIdx);
178 SlotIndex newDefIdx = ls.lis->getMBBStartIdx(outBlock);
179 assert(ls.lis->getInstructionFromIndex(newDefIdx) == 0 &&
180 "PHI def index points at actual instruction.");
182 getNewLI()->getNextValue(newDefIdx, 0, ls.lis->getVNInfoAllocator());
184 getNewLI()->addRange(LiveRange(ls.lis->getMBBStartIdx(outBlock),
185 copyDefIdx, newVal));
190 void copyRange(LiveRange &lr) {
191 std::pair<bool, LoopSplitter::SlotPair> lsr =
192 ls.getLoopSubRange(lr, loop);
197 LiveRange loopRange(lsr.second.first, lsr.second.second,
198 getNewVNI(lr.valno));
200 li.removeRange(loopRange.start, loopRange.end, true);
202 getNewLI()->addRange(loopRange);
206 for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(),
207 iEnd = loopInstrs.end();
208 iItr != iEnd; ++iItr) {
209 MachineInstr &instr = **iItr;
210 SlotIndex instrIdx = ls.lis->getInstructionIndex(&instr);
211 if (instr.modifiesRegister(li.reg, 0)) {
212 LiveRange *defRange =
213 li.getLiveRangeContaining(instrIdx.getDefIndex());
214 if (defRange != 0) // May have caught this already.
215 copyRange(*defRange);
217 if (instr.readsRegister(li.reg, 0)) {
218 LiveRange *useRange =
219 li.getLiveRangeContaining(instrIdx.getUseIndex());
220 if (useRange != 0) { // May have caught this already.
221 copyRange(*useRange);
226 for (MachineLoop::block_iterator bbItr = loop.block_begin(),
227 bbEnd = loop.block_end();
228 bbItr != bbEnd; ++bbItr) {
229 MachineBasicBlock &loopBlock = **bbItr;
230 LiveRange *enteringRange =
231 ls.lis->findEnteringRange(li, &loopBlock);
232 if (enteringRange != 0) {
233 copyRange(*enteringRange);
238 void renameInside() {
239 for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(),
240 iEnd = loopInstrs.end();
241 iItr != iEnd; ++iItr) {
242 MachineInstr &instr = **iItr;
243 for (unsigned i = 0; i < instr.getNumOperands(); ++i) {
244 MachineOperand &mop = instr.getOperand(i);
245 if (mop.isReg() && mop.getReg() == li.reg) {
246 mop.setReg(getNewLI()->reg);
254 void LoopSplitter::getAnalysisUsage(AnalysisUsage &au) const {
255 au.addRequired<MachineDominatorTree>();
256 au.addPreserved<MachineDominatorTree>();
257 au.addRequired<MachineLoopInfo>();
258 au.addPreserved<MachineLoopInfo>();
259 au.addPreserved<RegisterCoalescer>();
260 au.addPreserved<CalculateSpillWeights>();
261 au.addPreserved<LiveStacks>();
262 au.addRequired<SlotIndexes>();
263 au.addPreserved<SlotIndexes>();
264 au.addRequired<LiveIntervals>();
265 au.addPreserved<LiveIntervals>();
266 MachineFunctionPass::getAnalysisUsage(au);
269 bool LoopSplitter::runOnMachineFunction(MachineFunction &fn) {
272 mri = &mf->getRegInfo();
273 tii = mf->getTarget().getInstrInfo();
274 tri = mf->getTarget().getRegisterInfo();
275 sis = &getAnalysis<SlotIndexes>();
276 lis = &getAnalysis<LiveIntervals>();
277 mli = &getAnalysis<MachineLoopInfo>();
278 mdt = &getAnalysis<MachineDominatorTree>();
280 fqn = mf->getFunction()->getParent()->getModuleIdentifier() + "." +
281 mf->getFunction()->getName().str();
283 dbgs() << "Splitting " << mf->getFunction()->getName() << ".";
285 dumpOddTerminators();
287 // dbgs() << "----------------------------------------\n";
289 // dbgs() << "----------------------------------------\n";
291 // std::deque<MachineLoop*> loops;
292 // std::copy(mli->begin(), mli->end(), std::back_inserter(loops));
293 // dbgs() << "Loops:\n";
294 // while (!loops.empty()) {
295 // MachineLoop &loop = *loops.front();
296 // loops.pop_front();
297 // std::copy(loop.begin(), loop.end(), std::back_inserter(loops));
299 // dumpLoopInfo(loop);
305 // Setup initial intervals.
306 for (LiveIntervals::iterator liItr = lis->begin(), liEnd = lis->end();
307 liItr != liEnd; ++liItr) {
308 LiveInterval *li = liItr->second;
310 if (TargetRegisterInfo::isVirtualRegister(li->reg) &&
311 !lis->intervalIsInOneMBB(*li)) {
312 intervals.push_back(li);
320 // dbgs() << "----------------------------------------\n";
322 // dbgs() << "----------------------------------------\n";
324 dumpOddTerminators();
331 void LoopSplitter::releaseMemory() {
334 loopRangeMap.clear();
337 void LoopSplitter::dumpOddTerminators() {
338 for (MachineFunction::iterator bbItr = mf->begin(), bbEnd = mf->end();
339 bbItr != bbEnd; ++bbItr) {
340 MachineBasicBlock *mbb = &*bbItr;
341 MachineBasicBlock *a = 0, *b = 0;
342 SmallVector<MachineOperand, 4> c;
343 if (tii->AnalyzeBranch(*mbb, a, b, c)) {
344 dbgs() << "MBB#" << mbb->getNumber() << " has multiway terminator.\n";
345 dbgs() << " Terminators:\n";
346 for (MachineBasicBlock::iterator iItr = mbb->begin(), iEnd = mbb->end();
347 iItr != iEnd; ++iItr) {
348 MachineInstr *instr= &*iItr;
349 dbgs() << " " << *instr << "";
351 dbgs() << "\n Listed successors: [ ";
352 for (MachineBasicBlock::succ_iterator sItr = mbb->succ_begin(), sEnd = mbb->succ_end();
353 sItr != sEnd; ++sItr) {
354 MachineBasicBlock *succMBB = *sItr;
355 dbgs() << succMBB->getNumber() << " ";
362 void LoopSplitter::dumpLoopInfo(MachineLoop &loop) {
363 MachineBasicBlock &headerBlock = *loop.getHeader();
364 typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList;
365 ExitEdgesList exitEdges;
366 loop.getExitEdges(exitEdges);
368 dbgs() << " Header: BB#" << headerBlock.getNumber() << ", Contains: [ ";
369 for (std::vector<MachineBasicBlock*>::const_iterator
370 subBlockItr = loop.getBlocks().begin(),
371 subBlockEnd = loop.getBlocks().end();
372 subBlockItr != subBlockEnd; ++subBlockItr) {
373 MachineBasicBlock &subBlock = **subBlockItr;
374 dbgs() << "BB#" << subBlock.getNumber() << " ";
376 dbgs() << "], Exit edges: [ ";
377 for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(),
378 exitEdgeEnd = exitEdges.end();
379 exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) {
380 MachineLoop::Edge &exitEdge = *exitEdgeItr;
381 dbgs() << "(MBB#" << exitEdge.first->getNumber()
382 << ", MBB#" << exitEdge.second->getNumber() << ") ";
384 dbgs() << "], Sub-Loop Headers: [ ";
385 for (MachineLoop::iterator subLoopItr = loop.begin(),
386 subLoopEnd = loop.end();
387 subLoopItr != subLoopEnd; ++subLoopItr) {
388 MachineLoop &subLoop = **subLoopItr;
389 MachineBasicBlock &subLoopBlock = *subLoop.getHeader();
390 dbgs() << "BB#" << subLoopBlock.getNumber() << " ";
395 void LoopSplitter::updateTerminators(MachineBasicBlock &mbb) {
396 mbb.updateTerminator();
398 for (MachineBasicBlock::iterator miItr = mbb.begin(), miEnd = mbb.end();
399 miItr != miEnd; ++miItr) {
400 if (lis->isNotInMIMap(miItr)) {
401 lis->InsertMachineInstrInMaps(miItr);
406 bool LoopSplitter::canInsertPreHeader(MachineLoop &loop) {
407 MachineBasicBlock *header = loop.getHeader();
408 MachineBasicBlock *a = 0, *b = 0;
409 SmallVector<MachineOperand, 4> c;
411 for (MachineBasicBlock::pred_iterator pbItr = header->pred_begin(),
412 pbEnd = header->pred_end();
413 pbItr != pbEnd; ++pbItr) {
414 MachineBasicBlock *predBlock = *pbItr;
415 if (!!tii->AnalyzeBranch(*predBlock, a, b, c)) {
420 MachineFunction::iterator headerItr(header);
421 if (headerItr == mf->begin())
423 MachineBasicBlock *headerLayoutPred = llvm::prior(headerItr);
424 assert(headerLayoutPred != 0 && "Header should have layout pred.");
426 return (!tii->AnalyzeBranch(*headerLayoutPred, a, b, c));
429 MachineBasicBlock& LoopSplitter::insertPreHeader(MachineLoop &loop) {
430 assert(loop.getLoopPreheader() == 0 && "Loop already has preheader.");
432 MachineBasicBlock &header = *loop.getHeader();
434 // Save the preds - we'll need to update them once we insert the preheader.
435 typedef std::set<MachineBasicBlock*> HeaderPreds;
436 HeaderPreds headerPreds;
438 for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(),
439 predEnd = header.pred_end();
440 predItr != predEnd; ++predItr) {
441 if (!loop.contains(*predItr))
442 headerPreds.insert(*predItr);
445 assert(!headerPreds.empty() && "No predecessors for header?");
447 //dbgs() << fqn << " MBB#" << header.getNumber() << " inserting preheader...";
449 MachineBasicBlock *preHeader =
450 mf->CreateMachineBasicBlock(header.getBasicBlock());
452 assert(preHeader != 0 && "Failed to create pre-header.");
454 mf->insert(header, preHeader);
456 for (HeaderPreds::iterator hpItr = headerPreds.begin(),
457 hpEnd = headerPreds.end();
458 hpItr != hpEnd; ++hpItr) {
459 assert(*hpItr != 0 && "How'd a null predecessor get into this set?");
460 MachineBasicBlock &hp = **hpItr;
461 hp.ReplaceUsesOfBlockWith(&header, preHeader);
463 preHeader->addSuccessor(&header);
465 MachineBasicBlock *oldLayoutPred =
466 llvm::prior(MachineFunction::iterator(preHeader));
467 if (oldLayoutPred != 0) {
468 updateTerminators(*oldLayoutPred);
471 lis->InsertMBBInMaps(preHeader);
473 if (MachineLoop *parentLoop = loop.getParentLoop()) {
474 assert(parentLoop->getHeader() != loop.getHeader() &&
475 "Parent loop has same header?");
476 parentLoop->addBasicBlockToLoop(preHeader, mli->getBase());
478 // Invalidate all parent loop ranges.
479 while (parentLoop != 0) {
480 loopRangeMap.erase(parentLoop);
481 parentLoop = parentLoop->getParentLoop();
485 for (LiveIntervals::iterator liItr = lis->begin(),
487 liItr != liEnd; ++liItr) {
488 LiveInterval &li = *liItr->second;
490 // Is this safe for physregs?
491 // TargetRegisterInfo::isPhysicalRegister(li.reg) ||
492 if (!lis->isLiveInToMBB(li, &header))
495 if (lis->isLiveInToMBB(li, preHeader)) {
496 assert(lis->isLiveOutOfMBB(li, preHeader) &&
497 "Range terminates in newly added preheader?");
501 bool insertRange = false;
503 for (MachineBasicBlock::pred_iterator predItr = preHeader->pred_begin(),
504 predEnd = preHeader->pred_end();
505 predItr != predEnd; ++predItr) {
506 MachineBasicBlock *predMBB = *predItr;
507 if (lis->isLiveOutOfMBB(li, predMBB)) {
516 SlotIndex newDefIdx = lis->getMBBStartIdx(preHeader);
517 assert(lis->getInstructionFromIndex(newDefIdx) == 0 &&
518 "PHI def index points at actual instruction.");
519 VNInfo *newVal = li.getNextValue(newDefIdx, 0, lis->getVNInfoAllocator());
520 li.addRange(LiveRange(lis->getMBBStartIdx(preHeader),
521 lis->getMBBEndIdx(preHeader),
526 //dbgs() << "Dumping SlotIndexes:\n";
529 //dbgs() << "done. (Added MBB#" << preHeader->getNumber() << ")\n";
534 bool LoopSplitter::isCriticalEdge(MachineLoop::Edge &edge) {
535 assert(edge.first->succ_size() > 1 && "Non-sensical edge.");
536 if (edge.second->pred_size() > 1)
541 bool LoopSplitter::canSplitEdge(MachineLoop::Edge &edge) {
542 MachineFunction::iterator outBlockItr(edge.second);
543 if (outBlockItr == mf->begin())
545 MachineBasicBlock *outBlockLayoutPred = llvm::prior(outBlockItr);
546 assert(outBlockLayoutPred != 0 && "Should have a layout pred if out!=begin.");
547 MachineBasicBlock *a = 0, *b = 0;
548 SmallVector<MachineOperand, 4> c;
549 return (!tii->AnalyzeBranch(*outBlockLayoutPred, a, b, c) &&
550 !tii->AnalyzeBranch(*edge.first, a, b, c));
553 MachineBasicBlock& LoopSplitter::splitEdge(MachineLoop::Edge &edge,
556 MachineBasicBlock &inBlock = *edge.first;
557 MachineBasicBlock &outBlock = *edge.second;
559 assert((inBlock.succ_size() > 1) && (outBlock.pred_size() > 1) &&
560 "Splitting non-critical edge?");
562 //dbgs() << fqn << " Splitting edge (MBB#" << inBlock.getNumber()
563 // << " -> MBB#" << outBlock.getNumber() << ")...";
565 MachineBasicBlock *splitBlock =
566 mf->CreateMachineBasicBlock();
568 assert(splitBlock != 0 && "Failed to create split block.");
570 mf->insert(&outBlock, splitBlock);
572 inBlock.ReplaceUsesOfBlockWith(&outBlock, splitBlock);
573 splitBlock->addSuccessor(&outBlock);
575 MachineBasicBlock *oldLayoutPred =
576 llvm::prior(MachineFunction::iterator(splitBlock));
577 if (oldLayoutPred != 0) {
578 updateTerminators(*oldLayoutPred);
581 lis->InsertMBBInMaps(splitBlock);
583 loopRangeMap.erase(&loop);
585 MachineLoop *splitParentLoop = loop.getParentLoop();
586 while (splitParentLoop != 0 &&
587 !splitParentLoop->contains(&outBlock)) {
588 splitParentLoop = splitParentLoop->getParentLoop();
591 if (splitParentLoop != 0) {
592 assert(splitParentLoop->contains(&loop) &&
593 "Split-block parent doesn't contain original loop?");
594 splitParentLoop->addBasicBlockToLoop(splitBlock, mli->getBase());
596 // Invalidate all parent loop ranges.
597 while (splitParentLoop != 0) {
598 loopRangeMap.erase(splitParentLoop);
599 splitParentLoop = splitParentLoop->getParentLoop();
604 for (LiveIntervals::iterator liItr = lis->begin(),
606 liItr != liEnd; ++liItr) {
607 LiveInterval &li = *liItr->second;
608 bool intersects = lis->isLiveOutOfMBB(li, &inBlock) &&
609 lis->isLiveInToMBB(li, &outBlock);
610 if (lis->isLiveInToMBB(li, splitBlock)) {
612 li.removeRange(lis->getMBBStartIdx(splitBlock),
613 lis->getMBBEndIdx(splitBlock), true);
615 } else if (intersects) {
616 SlotIndex newDefIdx = lis->getMBBStartIdx(splitBlock);
617 assert(lis->getInstructionFromIndex(newDefIdx) == 0 &&
618 "PHI def index points at actual instruction.");
619 VNInfo *newVal = li.getNextValue(newDefIdx, 0,
620 lis->getVNInfoAllocator());
621 li.addRange(LiveRange(lis->getMBBStartIdx(splitBlock),
622 lis->getMBBEndIdx(splitBlock),
627 //dbgs() << "done. (Added MBB#" << splitBlock->getNumber() << ")\n";
632 LoopSplitter::LoopRanges& LoopSplitter::getLoopRanges(MachineLoop &loop) {
633 typedef std::set<MachineBasicBlock*, StartSlotComparator> LoopMBBSet;
634 LoopRangeMap::iterator lrItr = loopRangeMap.find(&loop);
635 if (lrItr == loopRangeMap.end()) {
636 LoopMBBSet loopMBBs((StartSlotComparator(*lis)));
637 std::copy(loop.block_begin(), loop.block_end(),
638 std::inserter(loopMBBs, loopMBBs.begin()));
640 assert(!loopMBBs.empty() && "No blocks in loop?");
642 LoopRanges &loopRanges = loopRangeMap[&loop];
643 assert(loopRanges.empty() && "Loop encountered but not processed?");
644 SlotIndex oldEnd = lis->getMBBEndIdx(*loopMBBs.begin());
645 loopRanges.push_back(
646 std::make_pair(lis->getMBBStartIdx(*loopMBBs.begin()),
647 lis->getInvalidIndex()));
648 for (LoopMBBSet::iterator curBlockItr = llvm::next(loopMBBs.begin()),
649 curBlockEnd = loopMBBs.end();
650 curBlockItr != curBlockEnd; ++curBlockItr) {
651 SlotIndex newStart = lis->getMBBStartIdx(*curBlockItr);
652 if (newStart != oldEnd) {
653 loopRanges.back().second = oldEnd;
654 loopRanges.push_back(std::make_pair(newStart,
655 lis->getInvalidIndex()));
657 oldEnd = lis->getMBBEndIdx(*curBlockItr);
660 loopRanges.back().second =
661 lis->getMBBEndIdx(*llvm::prior(loopMBBs.end()));
665 return lrItr->second;
668 std::pair<bool, LoopSplitter::SlotPair> LoopSplitter::getLoopSubRange(
671 LoopRanges &loopRanges = getLoopRanges(loop);
672 LoopRanges::iterator lrItr = loopRanges.begin(),
673 lrEnd = loopRanges.end();
674 while (lrItr != lrEnd && lr.start >= lrItr->second) {
678 if (lrItr == lrEnd) {
679 SlotIndex invalid = lis->getInvalidIndex();
680 return std::make_pair(false, SlotPair(invalid, invalid));
683 SlotIndex srStart(lr.start < lrItr->first ? lrItr->first : lr.start);
684 SlotIndex srEnd(lr.end > lrItr->second ? lrItr->second : lr.end);
686 return std::make_pair(true, SlotPair(srStart, srEnd));
689 void LoopSplitter::dumpLoopRanges(MachineLoop &loop) {
690 LoopRanges &loopRanges = getLoopRanges(loop);
691 dbgs() << "For loop MBB#" << loop.getHeader()->getNumber() << ", subranges are: [ ";
692 for (LoopRanges::iterator lrItr = loopRanges.begin(), lrEnd = loopRanges.end();
693 lrItr != lrEnd; ++lrItr) {
694 dbgs() << "[" << lrItr->first << ", " << lrItr->second << ") ";
699 void LoopSplitter::processHeader(LoopSplit &split) {
700 MachineBasicBlock &header = *split.getLoop().getHeader();
701 //dbgs() << " Processing loop header BB#" << header.getNumber() << "\n";
703 if (!lis->isLiveInToMBB(split.getLI(), &header))
704 return; // Not live in, but nothing wrong so far.
706 MachineBasicBlock *preHeader = split.getLoop().getLoopPreheader();
709 if (!canInsertPreHeader(split.getLoop())) {
711 return; // Couldn't insert a pre-header. Bail on this interval.
714 for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(),
715 predEnd = header.pred_end();
716 predItr != predEnd; ++predItr) {
717 if (lis->isLiveOutOfMBB(split.getLI(), *predItr)) {
718 split.splitIncoming();
722 } else if (lis->isLiveOutOfMBB(split.getLI(), preHeader)) {
723 split.splitIncoming();
727 void LoopSplitter::processLoopExits(LoopSplit &split) {
728 typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList;
729 ExitEdgesList exitEdges;
730 split.getLoop().getExitEdges(exitEdges);
732 //dbgs() << " Processing loop exits:\n";
734 for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(),
735 exitEdgeEnd = exitEdges.end();
736 exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) {
737 MachineLoop::Edge exitEdge = *exitEdgeItr;
739 LiveRange *outRange =
740 split.getLI().getLiveRangeContaining(lis->getMBBStartIdx(exitEdge.second));
743 if (isCriticalEdge(exitEdge) && !canSplitEdge(exitEdge)) {
748 split.splitOutgoing(exitEdge);
753 void LoopSplitter::processLoopUses(LoopSplit &split) {
754 std::set<MachineInstr*> processed;
756 for (MachineRegisterInfo::reg_iterator
757 rItr = mri->reg_begin(split.getLI().reg),
758 rEnd = mri->reg_end();
759 rItr != rEnd; ++rItr) {
760 MachineInstr &instr = *rItr;
761 if (split.getLoop().contains(&instr) && processed.count(&instr) == 0) {
762 split.addLoopInstr(&instr);
763 processed.insert(&instr);
767 //dbgs() << " Rewriting reg" << li.reg << " to reg" << newLI->reg
768 // << " in blocks [ ";
772 bool LoopSplitter::splitOverLoop(LiveInterval &li, MachineLoop &loop) {
773 assert(TargetRegisterInfo::isVirtualRegister(li.reg) &&
774 "Attempt to split physical register.");
776 LoopSplit split(*this, li, loop);
777 processHeader(split);
779 processLoopExits(split);
781 processLoopUses(split);
782 if (split.isValid() /* && split.isWorthwhile() */) {
784 DEBUG(dbgs() << "Success.\n");
787 DEBUG(dbgs() << "Failed.\n");
791 void LoopSplitter::processInterval(LiveInterval &li) {
792 std::deque<MachineLoop*> loops;
793 std::copy(mli->begin(), mli->end(), std::back_inserter(loops));
795 while (!loops.empty()) {
796 MachineLoop &loop = *loops.front();
799 dbgs() << fqn << " reg" << li.reg << " " << li.weight << " BB#"
800 << loop.getHeader()->getNumber() << " ";
802 if (!splitOverLoop(li, loop)) {
803 // Couldn't split over outer loop, schedule sub-loops to be checked.
804 std::copy(loop.begin(), loop.end(), std::back_inserter(loops));
809 void LoopSplitter::processIntervals() {
810 while (!intervals.empty()) {
811 LiveInterval &li = *intervals.front();
812 intervals.pop_front();
814 assert(!lis->intervalIsInOneMBB(li) &&
815 "Single interval in process worklist.");