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 static RegisterPass<LoopSplitter>
33 X("loop-splitting", "Split virtual regists across loop boundaries.");
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 newVal->setIsDefAccurate(true);
144 li.removeRange(copyDefIdx, ls.lis->getMBBEndIdx(preHeader), true);
146 getNewLI()->addRange(LiveRange(copyDefIdx,
147 ls.lis->getMBBEndIdx(preHeader),
151 void applyOutgoing() {
153 for (std::set<MachineLoop::Edge>::iterator osItr = outSplits.begin(),
154 osEnd = outSplits.end();
155 osItr != osEnd; ++osItr) {
156 MachineLoop::Edge edge = *osItr;
157 MachineBasicBlock *outBlock = edge.second;
158 if (ls.isCriticalEdge(edge)) {
159 assert(ls.canSplitEdge(edge) && "Unsplitable critical edge.");
160 outBlock = &ls.splitEdge(edge, loop);
162 LiveRange *outRange = ls.lis->findEnteringRange(li, outBlock);
163 assert(outRange != 0 && "No exiting range?");
165 MachineInstr *copy = BuildMI(*outBlock, outBlock->begin(),
167 ls.tii->get(TargetOpcode::COPY))
168 .addReg(li.reg, RegState::Define)
169 .addReg(getNewLI()->reg, RegState::Kill);
171 ls.lis->InsertMachineInstrInMaps(copy);
173 SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getDefIndex();
175 // Blow away output range definition.
176 outRange->valno->def = ls.lis->getInvalidIndex();
177 outRange->valno->setIsDefAccurate(false);
178 li.removeRange(ls.lis->getMBBStartIdx(outBlock), copyDefIdx);
181 getNewLI()->getNextValue(SlotIndex(ls.lis->getMBBStartIdx(outBlock),
183 0, false, ls.lis->getVNInfoAllocator());
185 getNewLI()->addRange(LiveRange(ls.lis->getMBBStartIdx(outBlock),
186 copyDefIdx, newVal));
191 void copyRange(LiveRange &lr) {
192 std::pair<bool, LoopSplitter::SlotPair> lsr =
193 ls.getLoopSubRange(lr, loop);
198 LiveRange loopRange(lsr.second.first, lsr.second.second,
199 getNewVNI(lr.valno));
201 li.removeRange(loopRange.start, loopRange.end, true);
203 getNewLI()->addRange(loopRange);
207 for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(),
208 iEnd = loopInstrs.end();
209 iItr != iEnd; ++iItr) {
210 MachineInstr &instr = **iItr;
211 SlotIndex instrIdx = ls.lis->getInstructionIndex(&instr);
212 if (instr.modifiesRegister(li.reg, 0)) {
213 LiveRange *defRange =
214 li.getLiveRangeContaining(instrIdx.getDefIndex());
215 if (defRange != 0) // May have caught this already.
216 copyRange(*defRange);
218 if (instr.readsRegister(li.reg, 0)) {
219 LiveRange *useRange =
220 li.getLiveRangeContaining(instrIdx.getUseIndex());
221 if (useRange != 0) { // May have caught this already.
222 copyRange(*useRange);
227 for (MachineLoop::block_iterator bbItr = loop.block_begin(),
228 bbEnd = loop.block_end();
229 bbItr != bbEnd; ++bbItr) {
230 MachineBasicBlock &loopBlock = **bbItr;
231 LiveRange *enteringRange =
232 ls.lis->findEnteringRange(li, &loopBlock);
233 if (enteringRange != 0) {
234 copyRange(*enteringRange);
239 void renameInside() {
240 for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(),
241 iEnd = loopInstrs.end();
242 iItr != iEnd; ++iItr) {
243 MachineInstr &instr = **iItr;
244 for (unsigned i = 0; i < instr.getNumOperands(); ++i) {
245 MachineOperand &mop = instr.getOperand(i);
246 if (mop.isReg() && mop.getReg() == li.reg) {
247 mop.setReg(getNewLI()->reg);
255 void LoopSplitter::getAnalysisUsage(AnalysisUsage &au) const {
256 au.addRequired<MachineDominatorTree>();
257 au.addPreserved<MachineDominatorTree>();
258 au.addRequired<MachineLoopInfo>();
259 au.addPreserved<MachineLoopInfo>();
260 au.addPreserved<RegisterCoalescer>();
261 au.addPreserved<CalculateSpillWeights>();
262 au.addPreserved<LiveStacks>();
263 au.addRequired<SlotIndexes>();
264 au.addPreserved<SlotIndexes>();
265 au.addRequired<LiveIntervals>();
266 au.addPreserved<LiveIntervals>();
267 MachineFunctionPass::getAnalysisUsage(au);
270 bool LoopSplitter::runOnMachineFunction(MachineFunction &fn) {
273 mri = &mf->getRegInfo();
274 tii = mf->getTarget().getInstrInfo();
275 tri = mf->getTarget().getRegisterInfo();
276 sis = &getAnalysis<SlotIndexes>();
277 lis = &getAnalysis<LiveIntervals>();
278 mli = &getAnalysis<MachineLoopInfo>();
279 mdt = &getAnalysis<MachineDominatorTree>();
281 fqn = mf->getFunction()->getParent()->getModuleIdentifier() + "." +
282 mf->getFunction()->getName().str();
284 dbgs() << "Splitting " << mf->getFunction()->getName() << ".";
286 dumpOddTerminators();
288 // dbgs() << "----------------------------------------\n";
290 // dbgs() << "----------------------------------------\n";
292 // std::deque<MachineLoop*> loops;
293 // std::copy(mli->begin(), mli->end(), std::back_inserter(loops));
294 // dbgs() << "Loops:\n";
295 // while (!loops.empty()) {
296 // MachineLoop &loop = *loops.front();
297 // loops.pop_front();
298 // std::copy(loop.begin(), loop.end(), std::back_inserter(loops));
300 // dumpLoopInfo(loop);
306 // Setup initial intervals.
307 for (LiveIntervals::iterator liItr = lis->begin(), liEnd = lis->end();
308 liItr != liEnd; ++liItr) {
309 LiveInterval *li = liItr->second;
311 if (TargetRegisterInfo::isVirtualRegister(li->reg) &&
312 !lis->intervalIsInOneMBB(*li)) {
313 intervals.push_back(li);
321 // dbgs() << "----------------------------------------\n";
323 // dbgs() << "----------------------------------------\n";
325 dumpOddTerminators();
332 void LoopSplitter::releaseMemory() {
335 loopRangeMap.clear();
338 void LoopSplitter::dumpOddTerminators() {
339 for (MachineFunction::iterator bbItr = mf->begin(), bbEnd = mf->end();
340 bbItr != bbEnd; ++bbItr) {
341 MachineBasicBlock *mbb = &*bbItr;
342 MachineBasicBlock *a = 0, *b = 0;
343 SmallVector<MachineOperand, 4> c;
344 if (tii->AnalyzeBranch(*mbb, a, b, c)) {
345 dbgs() << "MBB#" << mbb->getNumber() << " has multiway terminator.\n";
346 dbgs() << " Terminators:\n";
347 for (MachineBasicBlock::iterator iItr = mbb->begin(), iEnd = mbb->end();
348 iItr != iEnd; ++iItr) {
349 MachineInstr *instr= &*iItr;
350 dbgs() << " " << *instr << "";
352 dbgs() << "\n Listed successors: [ ";
353 for (MachineBasicBlock::succ_iterator sItr = mbb->succ_begin(), sEnd = mbb->succ_end();
354 sItr != sEnd; ++sItr) {
355 MachineBasicBlock *succMBB = *sItr;
356 dbgs() << succMBB->getNumber() << " ";
363 void LoopSplitter::dumpLoopInfo(MachineLoop &loop) {
364 MachineBasicBlock &headerBlock = *loop.getHeader();
365 typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList;
366 ExitEdgesList exitEdges;
367 loop.getExitEdges(exitEdges);
369 dbgs() << " Header: BB#" << headerBlock.getNumber() << ", Contains: [ ";
370 for (std::vector<MachineBasicBlock*>::const_iterator
371 subBlockItr = loop.getBlocks().begin(),
372 subBlockEnd = loop.getBlocks().end();
373 subBlockItr != subBlockEnd; ++subBlockItr) {
374 MachineBasicBlock &subBlock = **subBlockItr;
375 dbgs() << "BB#" << subBlock.getNumber() << " ";
377 dbgs() << "], Exit edges: [ ";
378 for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(),
379 exitEdgeEnd = exitEdges.end();
380 exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) {
381 MachineLoop::Edge &exitEdge = *exitEdgeItr;
382 dbgs() << "(MBB#" << exitEdge.first->getNumber()
383 << ", MBB#" << exitEdge.second->getNumber() << ") ";
385 dbgs() << "], Sub-Loop Headers: [ ";
386 for (MachineLoop::iterator subLoopItr = loop.begin(),
387 subLoopEnd = loop.end();
388 subLoopItr != subLoopEnd; ++subLoopItr) {
389 MachineLoop &subLoop = **subLoopItr;
390 MachineBasicBlock &subLoopBlock = *subLoop.getHeader();
391 dbgs() << "BB#" << subLoopBlock.getNumber() << " ";
396 void LoopSplitter::updateTerminators(MachineBasicBlock &mbb) {
397 mbb.updateTerminator();
399 for (MachineBasicBlock::iterator miItr = mbb.begin(), miEnd = mbb.end();
400 miItr != miEnd; ++miItr) {
401 if (lis->isNotInMIMap(miItr)) {
402 lis->InsertMachineInstrInMaps(miItr);
407 bool LoopSplitter::canInsertPreHeader(MachineLoop &loop) {
408 MachineBasicBlock *header = loop.getHeader();
409 MachineBasicBlock *a = 0, *b = 0;
410 SmallVector<MachineOperand, 4> c;
412 for (MachineBasicBlock::pred_iterator pbItr = header->pred_begin(),
413 pbEnd = header->pred_end();
414 pbItr != pbEnd; ++pbItr) {
415 MachineBasicBlock *predBlock = *pbItr;
416 if (!!tii->AnalyzeBranch(*predBlock, a, b, c)) {
421 MachineFunction::iterator headerItr(header);
422 if (headerItr == mf->begin())
424 MachineBasicBlock *headerLayoutPred = llvm::prior(headerItr);
425 assert(headerLayoutPred != 0 && "Header should have layout pred.");
427 return (!tii->AnalyzeBranch(*headerLayoutPred, a, b, c));
430 MachineBasicBlock& LoopSplitter::insertPreHeader(MachineLoop &loop) {
431 assert(loop.getLoopPreheader() == 0 && "Loop already has preheader.");
433 MachineBasicBlock &header = *loop.getHeader();
435 // Save the preds - we'll need to update them once we insert the preheader.
436 typedef std::set<MachineBasicBlock*> HeaderPreds;
437 HeaderPreds headerPreds;
439 for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(),
440 predEnd = header.pred_end();
441 predItr != predEnd; ++predItr) {
442 if (!loop.contains(*predItr))
443 headerPreds.insert(*predItr);
446 assert(!headerPreds.empty() && "No predecessors for header?");
448 //dbgs() << fqn << " MBB#" << header.getNumber() << " inserting preheader...";
450 MachineBasicBlock *preHeader =
451 mf->CreateMachineBasicBlock(header.getBasicBlock());
453 assert(preHeader != 0 && "Failed to create pre-header.");
455 mf->insert(header, preHeader);
457 for (HeaderPreds::iterator hpItr = headerPreds.begin(),
458 hpEnd = headerPreds.end();
459 hpItr != hpEnd; ++hpItr) {
460 assert(*hpItr != 0 && "How'd a null predecessor get into this set?");
461 MachineBasicBlock &hp = **hpItr;
462 hp.ReplaceUsesOfBlockWith(&header, preHeader);
464 preHeader->addSuccessor(&header);
466 MachineBasicBlock *oldLayoutPred =
467 llvm::prior(MachineFunction::iterator(preHeader));
468 if (oldLayoutPred != 0) {
469 updateTerminators(*oldLayoutPred);
472 lis->InsertMBBInMaps(preHeader);
474 if (MachineLoop *parentLoop = loop.getParentLoop()) {
475 assert(parentLoop->getHeader() != loop.getHeader() &&
476 "Parent loop has same header?");
477 parentLoop->addBasicBlockToLoop(preHeader, mli->getBase());
479 // Invalidate all parent loop ranges.
480 while (parentLoop != 0) {
481 loopRangeMap.erase(parentLoop);
482 parentLoop = parentLoop->getParentLoop();
486 for (LiveIntervals::iterator liItr = lis->begin(),
488 liItr != liEnd; ++liItr) {
489 LiveInterval &li = *liItr->second;
491 // Is this safe for physregs?
492 // TargetRegisterInfo::isPhysicalRegister(li.reg) ||
493 if (!lis->isLiveInToMBB(li, &header))
496 if (lis->isLiveInToMBB(li, preHeader)) {
497 assert(lis->isLiveOutOfMBB(li, preHeader) &&
498 "Range terminates in newly added preheader?");
502 bool insertRange = false;
504 for (MachineBasicBlock::pred_iterator predItr = preHeader->pred_begin(),
505 predEnd = preHeader->pred_end();
506 predItr != predEnd; ++predItr) {
507 MachineBasicBlock *predMBB = *predItr;
508 if (lis->isLiveOutOfMBB(li, predMBB)) {
517 VNInfo *newVal = li.getNextValue(lis->getMBBStartIdx(preHeader),
518 0, false, lis->getVNInfoAllocator());
519 li.addRange(LiveRange(lis->getMBBStartIdx(preHeader),
520 lis->getMBBEndIdx(preHeader),
525 //dbgs() << "Dumping SlotIndexes:\n";
528 //dbgs() << "done. (Added MBB#" << preHeader->getNumber() << ")\n";
533 bool LoopSplitter::isCriticalEdge(MachineLoop::Edge &edge) {
534 assert(edge.first->succ_size() > 1 && "Non-sensical edge.");
535 if (edge.second->pred_size() > 1)
540 bool LoopSplitter::canSplitEdge(MachineLoop::Edge &edge) {
541 MachineFunction::iterator outBlockItr(edge.second);
542 if (outBlockItr == mf->begin())
544 MachineBasicBlock *outBlockLayoutPred = llvm::prior(outBlockItr);
545 assert(outBlockLayoutPred != 0 && "Should have a layout pred if out!=begin.");
546 MachineBasicBlock *a = 0, *b = 0;
547 SmallVector<MachineOperand, 4> c;
548 return (!tii->AnalyzeBranch(*outBlockLayoutPred, a, b, c) &&
549 !tii->AnalyzeBranch(*edge.first, a, b, c));
552 MachineBasicBlock& LoopSplitter::splitEdge(MachineLoop::Edge &edge,
555 MachineBasicBlock &inBlock = *edge.first;
556 MachineBasicBlock &outBlock = *edge.second;
558 assert((inBlock.succ_size() > 1) && (outBlock.pred_size() > 1) &&
559 "Splitting non-critical edge?");
561 //dbgs() << fqn << " Splitting edge (MBB#" << inBlock.getNumber()
562 // << " -> MBB#" << outBlock.getNumber() << ")...";
564 MachineBasicBlock *splitBlock =
565 mf->CreateMachineBasicBlock();
567 assert(splitBlock != 0 && "Failed to create split block.");
569 mf->insert(&outBlock, splitBlock);
571 inBlock.ReplaceUsesOfBlockWith(&outBlock, splitBlock);
572 splitBlock->addSuccessor(&outBlock);
574 MachineBasicBlock *oldLayoutPred =
575 llvm::prior(MachineFunction::iterator(splitBlock));
576 if (oldLayoutPred != 0) {
577 updateTerminators(*oldLayoutPred);
580 lis->InsertMBBInMaps(splitBlock);
582 loopRangeMap.erase(&loop);
584 MachineLoop *splitParentLoop = loop.getParentLoop();
585 while (splitParentLoop != 0 &&
586 !splitParentLoop->contains(&outBlock)) {
587 splitParentLoop = splitParentLoop->getParentLoop();
590 if (splitParentLoop != 0) {
591 assert(splitParentLoop->contains(&loop) &&
592 "Split-block parent doesn't contain original loop?");
593 splitParentLoop->addBasicBlockToLoop(splitBlock, mli->getBase());
595 // Invalidate all parent loop ranges.
596 while (splitParentLoop != 0) {
597 loopRangeMap.erase(splitParentLoop);
598 splitParentLoop = splitParentLoop->getParentLoop();
603 for (LiveIntervals::iterator liItr = lis->begin(),
605 liItr != liEnd; ++liItr) {
606 LiveInterval &li = *liItr->second;
607 bool intersects = lis->isLiveOutOfMBB(li, &inBlock) &&
608 lis->isLiveInToMBB(li, &outBlock);
609 if (lis->isLiveInToMBB(li, splitBlock)) {
611 li.removeRange(lis->getMBBStartIdx(splitBlock),
612 lis->getMBBEndIdx(splitBlock), true);
614 } else if (intersects) {
615 VNInfo *newVal = li.getNextValue(lis->getMBBStartIdx(splitBlock),
616 0, false, lis->getVNInfoAllocator());
617 li.addRange(LiveRange(lis->getMBBStartIdx(splitBlock),
618 lis->getMBBEndIdx(splitBlock),
623 //dbgs() << "done. (Added MBB#" << splitBlock->getNumber() << ")\n";
628 LoopSplitter::LoopRanges& LoopSplitter::getLoopRanges(MachineLoop &loop) {
629 typedef std::set<MachineBasicBlock*, StartSlotComparator> LoopMBBSet;
630 LoopRangeMap::iterator lrItr = loopRangeMap.find(&loop);
631 if (lrItr == loopRangeMap.end()) {
632 LoopMBBSet loopMBBs((StartSlotComparator(*lis)));
633 std::copy(loop.block_begin(), loop.block_end(),
634 std::inserter(loopMBBs, loopMBBs.begin()));
636 assert(!loopMBBs.empty() && "No blocks in loop?");
638 LoopRanges &loopRanges = loopRangeMap[&loop];
639 assert(loopRanges.empty() && "Loop encountered but not processed?");
640 SlotIndex oldEnd = lis->getMBBEndIdx(*loopMBBs.begin());
641 loopRanges.push_back(
642 std::make_pair(lis->getMBBStartIdx(*loopMBBs.begin()),
643 lis->getInvalidIndex()));
644 for (LoopMBBSet::iterator curBlockItr = llvm::next(loopMBBs.begin()),
645 curBlockEnd = loopMBBs.end();
646 curBlockItr != curBlockEnd; ++curBlockItr) {
647 SlotIndex newStart = lis->getMBBStartIdx(*curBlockItr);
648 if (newStart != oldEnd) {
649 loopRanges.back().second = oldEnd;
650 loopRanges.push_back(std::make_pair(newStart,
651 lis->getInvalidIndex()));
653 oldEnd = lis->getMBBEndIdx(*curBlockItr);
656 loopRanges.back().second =
657 lis->getMBBEndIdx(*llvm::prior(loopMBBs.end()));
661 return lrItr->second;
664 std::pair<bool, LoopSplitter::SlotPair> LoopSplitter::getLoopSubRange(
667 LoopRanges &loopRanges = getLoopRanges(loop);
668 LoopRanges::iterator lrItr = loopRanges.begin(),
669 lrEnd = loopRanges.end();
670 while (lrItr != lrEnd && lr.start >= lrItr->second) {
674 if (lrItr == lrEnd) {
675 SlotIndex invalid = lis->getInvalidIndex();
676 return std::make_pair(false, SlotPair(invalid, invalid));
679 SlotIndex srStart(lr.start < lrItr->first ? lrItr->first : lr.start);
680 SlotIndex srEnd(lr.end > lrItr->second ? lrItr->second : lr.end);
682 return std::make_pair(true, SlotPair(srStart, srEnd));
685 void LoopSplitter::dumpLoopRanges(MachineLoop &loop) {
686 LoopRanges &loopRanges = getLoopRanges(loop);
687 dbgs() << "For loop MBB#" << loop.getHeader()->getNumber() << ", subranges are: [ ";
688 for (LoopRanges::iterator lrItr = loopRanges.begin(), lrEnd = loopRanges.end();
689 lrItr != lrEnd; ++lrItr) {
690 dbgs() << "[" << lrItr->first << ", " << lrItr->second << ") ";
695 void LoopSplitter::processHeader(LoopSplit &split) {
696 MachineBasicBlock &header = *split.getLoop().getHeader();
697 //dbgs() << " Processing loop header BB#" << header.getNumber() << "\n";
699 if (!lis->isLiveInToMBB(split.getLI(), &header))
700 return; // Not live in, but nothing wrong so far.
702 MachineBasicBlock *preHeader = split.getLoop().getLoopPreheader();
705 if (!canInsertPreHeader(split.getLoop())) {
707 return; // Couldn't insert a pre-header. Bail on this interval.
710 for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(),
711 predEnd = header.pred_end();
712 predItr != predEnd; ++predItr) {
713 if (lis->isLiveOutOfMBB(split.getLI(), *predItr)) {
714 split.splitIncoming();
718 } else if (lis->isLiveOutOfMBB(split.getLI(), preHeader)) {
719 split.splitIncoming();
723 void LoopSplitter::processLoopExits(LoopSplit &split) {
724 typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList;
725 ExitEdgesList exitEdges;
726 split.getLoop().getExitEdges(exitEdges);
728 //dbgs() << " Processing loop exits:\n";
730 for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(),
731 exitEdgeEnd = exitEdges.end();
732 exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) {
733 MachineLoop::Edge exitEdge = *exitEdgeItr;
735 LiveRange *outRange =
736 split.getLI().getLiveRangeContaining(lis->getMBBStartIdx(exitEdge.second));
739 if (isCriticalEdge(exitEdge) && !canSplitEdge(exitEdge)) {
744 split.splitOutgoing(exitEdge);
749 void LoopSplitter::processLoopUses(LoopSplit &split) {
750 std::set<MachineInstr*> processed;
752 for (MachineRegisterInfo::reg_iterator
753 rItr = mri->reg_begin(split.getLI().reg),
754 rEnd = mri->reg_end();
755 rItr != rEnd; ++rItr) {
756 MachineInstr &instr = *rItr;
757 if (split.getLoop().contains(&instr) && processed.count(&instr) == 0) {
758 split.addLoopInstr(&instr);
759 processed.insert(&instr);
763 //dbgs() << " Rewriting reg" << li.reg << " to reg" << newLI->reg
764 // << " in blocks [ ";
768 bool LoopSplitter::splitOverLoop(LiveInterval &li, MachineLoop &loop) {
769 assert(TargetRegisterInfo::isVirtualRegister(li.reg) &&
770 "Attempt to split physical register.");
772 LoopSplit split(*this, li, loop);
773 processHeader(split);
775 processLoopExits(split);
777 processLoopUses(split);
778 if (split.isValid() /* && split.isWorthwhile() */) {
780 DEBUG(dbgs() << "Success.\n");
783 DEBUG(dbgs() << "Failed.\n");
787 void LoopSplitter::processInterval(LiveInterval &li) {
788 std::deque<MachineLoop*> loops;
789 std::copy(mli->begin(), mli->end(), std::back_inserter(loops));
791 while (!loops.empty()) {
792 MachineLoop &loop = *loops.front();
795 dbgs() << fqn << " reg" << li.reg << " " << li.weight << " BB#"
796 << loop.getHeader()->getNumber() << " ";
798 if (!splitOverLoop(li, loop)) {
799 // Couldn't split over outer loop, schedule sub-loops to be checked.
800 std::copy(loop.begin(), loop.end(), std::back_inserter(loops));
805 void LoopSplitter::processIntervals() {
806 while (!intervals.empty()) {
807 LiveInterval &li = *intervals.front();
808 intervals.pop_front();
810 assert(!lis->intervalIsInOneMBB(li) &&
811 "Single interval in process worklist.");