Home | History | Annotate | Download | only in CodeGen 
      1 //===-- llvm/CodeGen/Splitter.cpp -  Splitter -----------------------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 
     10 #define DEBUG_TYPE "loopsplitter"
     11 
     12 #include "Splitter.h"
     13 
     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"
     28 
     29 using namespace llvm;
     30 
     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)
     40 
     41 namespace llvm {
     42 
     43   class StartSlotComparator {
     44   public:
     45     StartSlotComparator(LiveIntervals &lis) : lis(lis) {}
     46     bool operator()(const MachineBasicBlock *mbb1,
     47                     const MachineBasicBlock *mbb2) const {
     48       return lis.getMBBStartIdx(mbb1) < lis.getMBBStartIdx(mbb2);
     49     }
     50   private:
     51     LiveIntervals &lis;
     52   };
     53 
     54   class LoopSplit {
     55   public:
     56     LoopSplit(LoopSplitter &ls, LiveInterval &li, MachineLoop &loop)
     57       : ls(ls), li(li), loop(loop), valid(true), inSplit(false), newLI(0) {
     58       assert(TargetRegisterInfo::isVirtualRegister(li.reg) &&
     59              "Cannot split physical registers.");
     60     }
     61 
     62     LiveInterval& getLI() const { return li; }
     63 
     64     MachineLoop& getLoop() const { return loop; }
     65 
     66     bool isValid() const { return valid; }
     67 
     68     bool isWorthwhile() const { return valid && (inSplit || !outSplits.empty()); }
     69 
     70     void invalidate() { valid = false; }
     71 
     72     void splitIncoming() { inSplit = true; }
     73 
     74     void splitOutgoing(MachineLoop::Edge &edge) { outSplits.insert(edge); }
     75 
     76     void addLoopInstr(MachineInstr *i) { loopInstrs.push_back(i); }
     77 
     78     void apply() {
     79       assert(valid && "Attempt to apply invalid split.");
     80       applyIncoming();
     81       applyOutgoing();
     82       copyRanges();
     83       renameInside();
     84     }
     85 
     86   private:
     87     LoopSplitter &ls;
     88     LiveInterval &li;
     89     MachineLoop &loop;
     90     bool valid, inSplit;
     91     std::set<MachineLoop::Edge> outSplits;
     92     std::vector<MachineInstr*> loopInstrs;
     93 
     94     LiveInterval *newLI;
     95     std::map<VNInfo*, VNInfo*> vniMap;
     96 
     97     LiveInterval* getNewLI() {
     98       if (newLI == 0) {
     99         const TargetRegisterClass *trc = ls.mri->getRegClass(li.reg);
    100         unsigned vreg = ls.mri->createVirtualRegister(trc);
    101         newLI = &ls.lis->getOrCreateInterval(vreg);
    102       }
    103       return newLI;
    104     }
    105 
    106     VNInfo* getNewVNI(VNInfo *oldVNI) {
    107       VNInfo *newVNI = vniMap[oldVNI];
    108 
    109       if (newVNI == 0) {
    110         newVNI = getNewLI()->createValueCopy(oldVNI,
    111                                              ls.lis->getVNInfoAllocator());
    112         vniMap[oldVNI] = newVNI;
    113       }
    114 
    115       return newVNI;
    116     }
    117 
    118     void applyIncoming() {
    119       if (!inSplit) {
    120         return;
    121       }
    122 
    123       MachineBasicBlock *preHeader = loop.getLoopPreheader();
    124       if (preHeader == 0) {
    125         assert(ls.canInsertPreHeader(loop) &&
    126                "Can't insert required preheader.");
    127         preHeader = &ls.insertPreHeader(loop);
    128       }
    129 
    130       LiveRange *preHeaderRange =
    131         ls.lis->findExitingRange(li, preHeader);
    132       assert(preHeaderRange != 0 && "Range not live into preheader.");
    133 
    134       // Insert the new copy.
    135       MachineInstr *copy = BuildMI(*preHeader,
    136                                    preHeader->getFirstTerminator(),
    137                                    DebugLoc(),
    138                                    ls.tii->get(TargetOpcode::COPY))
    139         .addReg(getNewLI()->reg, RegState::Define)
    140         .addReg(li.reg, RegState::Kill);
    141 
    142       ls.lis->InsertMachineInstrInMaps(copy);
    143 
    144       SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getDefIndex();
    145 
    146       VNInfo *newVal = getNewVNI(preHeaderRange->valno);
    147       newVal->def = copyDefIdx;
    148       newVal->setCopy(copy);
    149       li.removeRange(copyDefIdx, ls.lis->getMBBEndIdx(preHeader), true);
    150 
    151       getNewLI()->addRange(LiveRange(copyDefIdx,
    152                                      ls.lis->getMBBEndIdx(preHeader),
    153                                      newVal));
    154     }
    155 
    156     void applyOutgoing() {
    157 
    158       for (std::set<MachineLoop::Edge>::iterator osItr = outSplits.begin(),
    159                                                  osEnd = outSplits.end();
    160            osItr != osEnd; ++osItr) {
    161         MachineLoop::Edge edge = *osItr;
    162         MachineBasicBlock *outBlock = edge.second;
    163         if (ls.isCriticalEdge(edge)) {
    164           assert(ls.canSplitEdge(edge) && "Unsplitable critical edge.");
    165           outBlock = &ls.splitEdge(edge, loop);
    166         }
    167         LiveRange *outRange = ls.lis->findEnteringRange(li, outBlock);
    168         assert(outRange != 0 && "No exiting range?");
    169 
    170         MachineInstr *copy = BuildMI(*outBlock, outBlock->begin(),
    171                                      DebugLoc(),
    172                                      ls.tii->get(TargetOpcode::COPY))
    173           .addReg(li.reg, RegState::Define)
    174           .addReg(getNewLI()->reg, RegState::Kill);
    175 
    176         ls.lis->InsertMachineInstrInMaps(copy);
    177 
    178         SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getDefIndex();
    179 
    180         // Blow away output range definition.
    181         outRange->valno->def = ls.lis->getInvalidIndex();
    182         li.removeRange(ls.lis->getMBBStartIdx(outBlock), copyDefIdx);
    183 
    184         SlotIndex newDefIdx = ls.lis->getMBBStartIdx(outBlock);
    185         assert(ls.lis->getInstructionFromIndex(newDefIdx) == 0 &&
    186                "PHI def index points at actual instruction.");
    187         VNInfo *newVal =
    188           getNewLI()->getNextValue(newDefIdx, 0, ls.lis->getVNInfoAllocator());
    189 
    190         getNewLI()->addRange(LiveRange(ls.lis->getMBBStartIdx(outBlock),
    191                                        copyDefIdx, newVal));
    192 
    193       }
    194     }
    195 
    196     void copyRange(LiveRange &lr) {
    197       std::pair<bool, LoopSplitter::SlotPair> lsr =
    198         ls.getLoopSubRange(lr, loop);
    199 
    200       if (!lsr.first)
    201         return;
    202 
    203       LiveRange loopRange(lsr.second.first, lsr.second.second,
    204                           getNewVNI(lr.valno));
    205 
    206       li.removeRange(loopRange.start, loopRange.end, true);
    207 
    208       getNewLI()->addRange(loopRange);
    209     }
    210 
    211     void copyRanges() {
    212       for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(),
    213                                                 iEnd = loopInstrs.end();
    214            iItr != iEnd; ++iItr) {
    215         MachineInstr &instr = **iItr;
    216         SlotIndex instrIdx = ls.lis->getInstructionIndex(&instr);
    217         if (instr.modifiesRegister(li.reg, 0)) {
    218           LiveRange *defRange =
    219             li.getLiveRangeContaining(instrIdx.getDefIndex());
    220           if (defRange != 0) // May have caught this already.
    221             copyRange(*defRange);
    222         }
    223         if (instr.readsRegister(li.reg, 0)) {
    224           LiveRange *useRange =
    225             li.getLiveRangeContaining(instrIdx.getUseIndex());
    226           if (useRange != 0) { // May have caught this already.
    227             copyRange(*useRange);
    228           }
    229         }
    230       }
    231 
    232       for (MachineLoop::block_iterator bbItr = loop.block_begin(),
    233                                        bbEnd = loop.block_end();
    234            bbItr != bbEnd; ++bbItr) {
    235         MachineBasicBlock &loopBlock = **bbItr;
    236         LiveRange *enteringRange =
    237           ls.lis->findEnteringRange(li, &loopBlock);
    238         if (enteringRange != 0) {
    239           copyRange(*enteringRange);
    240         }
    241       }
    242     }
    243 
    244     void renameInside() {
    245       for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(),
    246                                                 iEnd = loopInstrs.end();
    247            iItr != iEnd; ++iItr) {
    248         MachineInstr &instr = **iItr;
    249         for (unsigned i = 0; i < instr.getNumOperands(); ++i) {
    250           MachineOperand &mop = instr.getOperand(i);
    251           if (mop.isReg() && mop.getReg() == li.reg) {
    252             mop.setReg(getNewLI()->reg);
    253           }
    254         }
    255       }
    256     }
    257 
    258   };
    259 
    260   void LoopSplitter::getAnalysisUsage(AnalysisUsage &au) const {
    261     au.addRequired<MachineDominatorTree>();
    262     au.addPreserved<MachineDominatorTree>();
    263     au.addRequired<MachineLoopInfo>();
    264     au.addPreserved<MachineLoopInfo>();
    265     au.addPreservedID(RegisterCoalescerPassID);
    266     au.addPreserved<CalculateSpillWeights>();
    267     au.addPreserved<LiveStacks>();
    268     au.addRequired<SlotIndexes>();
    269     au.addPreserved<SlotIndexes>();
    270     au.addRequired<LiveIntervals>();
    271     au.addPreserved<LiveIntervals>();
    272     MachineFunctionPass::getAnalysisUsage(au);
    273   }
    274 
    275   bool LoopSplitter::runOnMachineFunction(MachineFunction &fn) {
    276 
    277     mf = &fn;
    278     mri = &mf->getRegInfo();
    279     tii = mf->getTarget().getInstrInfo();
    280     tri = mf->getTarget().getRegisterInfo();
    281     sis = &getAnalysis<SlotIndexes>();
    282     lis = &getAnalysis<LiveIntervals>();
    283     mli = &getAnalysis<MachineLoopInfo>();
    284     mdt = &getAnalysis<MachineDominatorTree>();
    285 
    286     fqn = mf->getFunction()->getParent()->getModuleIdentifier() + "." +
    287       mf->getFunction()->getName().str();
    288 
    289     dbgs() << "Splitting " << mf->getFunction()->getName() << ".";
    290 
    291     dumpOddTerminators();
    292 
    293 //      dbgs() << "----------------------------------------\n";
    294 //      lis->dump();
    295 //      dbgs() << "----------------------------------------\n";
    296 
    297 //     std::deque<MachineLoop*> loops;
    298 //     std::copy(mli->begin(), mli->end(), std::back_inserter(loops));
    299 //     dbgs() << "Loops:\n";
    300 //     while (!loops.empty()) {
    301 //       MachineLoop &loop = *loops.front();
    302 //       loops.pop_front();
    303 //       std::copy(loop.begin(), loop.end(), std::back_inserter(loops));
    304 
    305 //       dumpLoopInfo(loop);
    306 //     }
    307 
    308     //lis->dump();
    309     //exit(0);
    310 
    311     // Setup initial intervals.
    312     for (LiveIntervals::iterator liItr = lis->begin(), liEnd = lis->end();
    313          liItr != liEnd; ++liItr) {
    314       LiveInterval *li = liItr->second;
    315 
    316       if (TargetRegisterInfo::isVirtualRegister(li->reg) &&
    317           !lis->intervalIsInOneMBB(*li)) {
    318         intervals.push_back(li);
    319       }
    320     }
    321 
    322     processIntervals();
    323 
    324     intervals.clear();
    325 
    326 //     dbgs() << "----------------------------------------\n";
    327 //     lis->dump();
    328 //     dbgs() << "----------------------------------------\n";
    329 
    330     dumpOddTerminators();
    331 
    332     //exit(1);
    333 
    334     return false;
    335   }
    336 
    337   void LoopSplitter::releaseMemory() {
    338     fqn.clear();
    339     intervals.clear();
    340     loopRangeMap.clear();
    341   }
    342 
    343   void LoopSplitter::dumpOddTerminators() {
    344     for (MachineFunction::iterator bbItr = mf->begin(), bbEnd = mf->end();
    345          bbItr != bbEnd; ++bbItr) {
    346       MachineBasicBlock *mbb = &*bbItr;
    347       MachineBasicBlock *a = 0, *b = 0;
    348       SmallVector<MachineOperand, 4> c;
    349       if (tii->AnalyzeBranch(*mbb, a, b, c)) {
    350         dbgs() << "MBB#" << mbb->getNumber() << " has multiway terminator.\n";
    351         dbgs() << "  Terminators:\n";
    352         for (MachineBasicBlock::iterator iItr = mbb->begin(), iEnd = mbb->end();
    353              iItr != iEnd; ++iItr) {
    354           MachineInstr *instr= &*iItr;
    355           dbgs() << "    " << *instr << "";
    356         }
    357         dbgs() << "\n  Listed successors: [ ";
    358         for (MachineBasicBlock::succ_iterator sItr = mbb->succ_begin(), sEnd = mbb->succ_end();
    359              sItr != sEnd; ++sItr) {
    360           MachineBasicBlock *succMBB = *sItr;
    361           dbgs() << succMBB->getNumber() << " ";
    362         }
    363         dbgs() << "]\n\n";
    364       }
    365     }
    366   }
    367 
    368   void LoopSplitter::dumpLoopInfo(MachineLoop &loop) {
    369     MachineBasicBlock &headerBlock = *loop.getHeader();
    370     typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList;
    371     ExitEdgesList exitEdges;
    372     loop.getExitEdges(exitEdges);
    373 
    374     dbgs() << "  Header: BB#" << headerBlock.getNumber() << ", Contains: [ ";
    375     for (std::vector<MachineBasicBlock*>::const_iterator
    376            subBlockItr = loop.getBlocks().begin(),
    377            subBlockEnd = loop.getBlocks().end();
    378          subBlockItr != subBlockEnd; ++subBlockItr) {
    379       MachineBasicBlock &subBlock = **subBlockItr;
    380       dbgs() << "BB#" << subBlock.getNumber() << " ";
    381     }
    382     dbgs() << "], Exit edges: [ ";
    383     for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(),
    384                                  exitEdgeEnd = exitEdges.end();
    385          exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) {
    386       MachineLoop::Edge &exitEdge = *exitEdgeItr;
    387       dbgs() << "(MBB#" << exitEdge.first->getNumber()
    388              << ", MBB#" << exitEdge.second->getNumber() << ") ";
    389     }
    390     dbgs() << "], Sub-Loop Headers: [ ";
    391     for (MachineLoop::iterator subLoopItr = loop.begin(),
    392                                subLoopEnd = loop.end();
    393          subLoopItr != subLoopEnd; ++subLoopItr) {
    394       MachineLoop &subLoop = **subLoopItr;
    395       MachineBasicBlock &subLoopBlock = *subLoop.getHeader();
    396       dbgs() << "BB#" << subLoopBlock.getNumber() << " ";
    397     }
    398     dbgs() << "]\n";
    399   }
    400 
    401   void LoopSplitter::updateTerminators(MachineBasicBlock &mbb) {
    402     mbb.updateTerminator();
    403 
    404     for (MachineBasicBlock::iterator miItr = mbb.begin(), miEnd = mbb.end();
    405          miItr != miEnd; ++miItr) {
    406       if (lis->isNotInMIMap(miItr)) {
    407         lis->InsertMachineInstrInMaps(miItr);
    408       }
    409     }
    410   }
    411 
    412   bool LoopSplitter::canInsertPreHeader(MachineLoop &loop) {
    413     MachineBasicBlock *header = loop.getHeader();
    414     MachineBasicBlock *a = 0, *b = 0;
    415     SmallVector<MachineOperand, 4> c;
    416 
    417     for (MachineBasicBlock::pred_iterator pbItr = header->pred_begin(),
    418                                           pbEnd = header->pred_end();
    419          pbItr != pbEnd; ++pbItr) {
    420       MachineBasicBlock *predBlock = *pbItr;
    421       if (!!tii->AnalyzeBranch(*predBlock, a, b, c)) {
    422         return false;
    423       }
    424     }
    425 
    426     MachineFunction::iterator headerItr(header);
    427     if (headerItr == mf->begin())
    428       return true;
    429     MachineBasicBlock *headerLayoutPred = llvm::prior(headerItr);
    430     assert(headerLayoutPred != 0 && "Header should have layout pred.");
    431 
    432     return (!tii->AnalyzeBranch(*headerLayoutPred, a, b, c));
    433   }
    434 
    435   MachineBasicBlock& LoopSplitter::insertPreHeader(MachineLoop &loop) {
    436     assert(loop.getLoopPreheader() == 0 && "Loop already has preheader.");
    437 
    438     MachineBasicBlock &header = *loop.getHeader();
    439 
    440     // Save the preds - we'll need to update them once we insert the preheader.
    441     typedef std::set<MachineBasicBlock*> HeaderPreds;
    442     HeaderPreds headerPreds;
    443 
    444     for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(),
    445                                           predEnd = header.pred_end();
    446          predItr != predEnd; ++predItr) {
    447       if (!loop.contains(*predItr))
    448         headerPreds.insert(*predItr);
    449     }
    450 
    451     assert(!headerPreds.empty() && "No predecessors for header?");
    452 
    453     //dbgs() << fqn << " MBB#" << header.getNumber() << " inserting preheader...";
    454 
    455     MachineBasicBlock *preHeader =
    456       mf->CreateMachineBasicBlock(header.getBasicBlock());
    457 
    458     assert(preHeader != 0 && "Failed to create pre-header.");
    459 
    460     mf->insert(header, preHeader);
    461 
    462     for (HeaderPreds::iterator hpItr = headerPreds.begin(),
    463                                hpEnd = headerPreds.end();
    464          hpItr != hpEnd; ++hpItr) {
    465       assert(*hpItr != 0 && "How'd a null predecessor get into this set?");
    466       MachineBasicBlock &hp = **hpItr;
    467       hp.ReplaceUsesOfBlockWith(&header, preHeader);
    468     }
    469     preHeader->addSuccessor(&header);
    470 
    471     MachineBasicBlock *oldLayoutPred =
    472       llvm::prior(MachineFunction::iterator(preHeader));
    473     if (oldLayoutPred != 0) {
    474       updateTerminators(*oldLayoutPred);
    475     }
    476 
    477     lis->InsertMBBInMaps(preHeader);
    478 
    479     if (MachineLoop *parentLoop = loop.getParentLoop()) {
    480       assert(parentLoop->getHeader() != loop.getHeader() &&
    481              "Parent loop has same header?");
    482       parentLoop->addBasicBlockToLoop(preHeader, mli->getBase());
    483 
    484       // Invalidate all parent loop ranges.
    485       while (parentLoop != 0) {
    486         loopRangeMap.erase(parentLoop);
    487         parentLoop = parentLoop->getParentLoop();
    488       }
    489     }
    490 
    491     for (LiveIntervals::iterator liItr = lis->begin(),
    492                                  liEnd = lis->end();
    493          liItr != liEnd; ++liItr) {
    494       LiveInterval &li = *liItr->second;
    495 
    496       // Is this safe for physregs?
    497       // TargetRegisterInfo::isPhysicalRegister(li.reg) ||
    498       if (!lis->isLiveInToMBB(li, &header))
    499         continue;
    500 
    501       if (lis->isLiveInToMBB(li, preHeader)) {
    502         assert(lis->isLiveOutOfMBB(li, preHeader) &&
    503                "Range terminates in newly added preheader?");
    504         continue;
    505       }
    506 
    507       bool insertRange = false;
    508 
    509       for (MachineBasicBlock::pred_iterator predItr = preHeader->pred_begin(),
    510                                             predEnd = preHeader->pred_end();
    511            predItr != predEnd; ++predItr) {
    512         MachineBasicBlock *predMBB = *predItr;
    513         if (lis->isLiveOutOfMBB(li, predMBB)) {
    514           insertRange = true;
    515           break;
    516         }
    517       }
    518 
    519       if (!insertRange)
    520         continue;
    521 
    522       SlotIndex newDefIdx = lis->getMBBStartIdx(preHeader);
    523       assert(lis->getInstructionFromIndex(newDefIdx) == 0 &&
    524              "PHI def index points at actual instruction.");
    525       VNInfo *newVal = li.getNextValue(newDefIdx, 0, lis->getVNInfoAllocator());
    526       li.addRange(LiveRange(lis->getMBBStartIdx(preHeader),
    527                             lis->getMBBEndIdx(preHeader),
    528                             newVal));
    529     }
    530 
    531 
    532     //dbgs() << "Dumping SlotIndexes:\n";
    533     //sis->dump();
    534 
    535     //dbgs() << "done. (Added MBB#" << preHeader->getNumber() << ")\n";
    536 
    537     return *preHeader;
    538   }
    539 
    540   bool LoopSplitter::isCriticalEdge(MachineLoop::Edge &edge) {
    541     assert(edge.first->succ_size() > 1 && "Non-sensical edge.");
    542     if (edge.second->pred_size() > 1)
    543       return true;
    544     return false;
    545   }
    546 
    547   bool LoopSplitter::canSplitEdge(MachineLoop::Edge &edge) {
    548     MachineFunction::iterator outBlockItr(edge.second);
    549     if (outBlockItr == mf->begin())
    550       return true;
    551     MachineBasicBlock *outBlockLayoutPred = llvm::prior(outBlockItr);
    552     assert(outBlockLayoutPred != 0 && "Should have a layout pred if out!=begin.");
    553     MachineBasicBlock *a = 0, *b = 0;
    554     SmallVector<MachineOperand, 4> c;
    555     return (!tii->AnalyzeBranch(*outBlockLayoutPred, a, b, c) &&
    556             !tii->AnalyzeBranch(*edge.first, a, b, c));
    557   }
    558 
    559   MachineBasicBlock& LoopSplitter::splitEdge(MachineLoop::Edge &edge,
    560                                              MachineLoop &loop) {
    561 
    562     MachineBasicBlock &inBlock = *edge.first;
    563     MachineBasicBlock &outBlock = *edge.second;
    564 
    565     assert((inBlock.succ_size() > 1) && (outBlock.pred_size() > 1) &&
    566            "Splitting non-critical edge?");
    567 
    568     //dbgs() << fqn << " Splitting edge (MBB#" << inBlock.getNumber()
    569     //       << " -> MBB#" << outBlock.getNumber() << ")...";
    570 
    571     MachineBasicBlock *splitBlock =
    572       mf->CreateMachineBasicBlock();
    573 
    574     assert(splitBlock != 0 && "Failed to create split block.");
    575 
    576     mf->insert(&outBlock, splitBlock);
    577 
    578     inBlock.ReplaceUsesOfBlockWith(&outBlock, splitBlock);
    579     splitBlock->addSuccessor(&outBlock);
    580 
    581     MachineBasicBlock *oldLayoutPred =
    582       llvm::prior(MachineFunction::iterator(splitBlock));
    583     if (oldLayoutPred != 0) {
    584       updateTerminators(*oldLayoutPred);
    585     }
    586 
    587     lis->InsertMBBInMaps(splitBlock);
    588 
    589     loopRangeMap.erase(&loop);
    590 
    591     MachineLoop *splitParentLoop = loop.getParentLoop();
    592     while (splitParentLoop != 0 &&
    593            !splitParentLoop->contains(&outBlock)) {
    594       splitParentLoop = splitParentLoop->getParentLoop();
    595     }
    596 
    597     if (splitParentLoop != 0) {
    598       assert(splitParentLoop->contains(&loop) &&
    599              "Split-block parent doesn't contain original loop?");
    600       splitParentLoop->addBasicBlockToLoop(splitBlock, mli->getBase());
    601 
    602       // Invalidate all parent loop ranges.
    603       while (splitParentLoop != 0) {
    604         loopRangeMap.erase(splitParentLoop);
    605         splitParentLoop = splitParentLoop->getParentLoop();
    606       }
    607     }
    608 
    609 
    610     for (LiveIntervals::iterator liItr = lis->begin(),
    611                                  liEnd = lis->end();
    612          liItr != liEnd; ++liItr) {
    613       LiveInterval &li = *liItr->second;
    614       bool intersects = lis->isLiveOutOfMBB(li, &inBlock) &&
    615                        lis->isLiveInToMBB(li, &outBlock);
    616       if (lis->isLiveInToMBB(li, splitBlock)) {
    617         if (!intersects) {
    618           li.removeRange(lis->getMBBStartIdx(splitBlock),
    619                          lis->getMBBEndIdx(splitBlock), true);
    620         }
    621       } else if (intersects) {
    622         SlotIndex newDefIdx = lis->getMBBStartIdx(splitBlock);
    623         assert(lis->getInstructionFromIndex(newDefIdx) == 0 &&
    624                "PHI def index points at actual instruction.");
    625         VNInfo *newVal = li.getNextValue(newDefIdx, 0,
    626                                          lis->getVNInfoAllocator());
    627         li.addRange(LiveRange(lis->getMBBStartIdx(splitBlock),
    628                               lis->getMBBEndIdx(splitBlock),
    629                               newVal));
    630       }
    631     }
    632 
    633     //dbgs() << "done. (Added MBB#" << splitBlock->getNumber() << ")\n";
    634 
    635     return *splitBlock;
    636   }
    637 
    638   LoopSplitter::LoopRanges& LoopSplitter::getLoopRanges(MachineLoop &loop) {
    639     typedef std::set<MachineBasicBlock*, StartSlotComparator> LoopMBBSet;
    640     LoopRangeMap::iterator lrItr = loopRangeMap.find(&loop);
    641     if (lrItr == loopRangeMap.end()) {
    642       LoopMBBSet loopMBBs((StartSlotComparator(*lis)));
    643       std::copy(loop.block_begin(), loop.block_end(),
    644                 std::inserter(loopMBBs, loopMBBs.begin()));
    645 
    646       assert(!loopMBBs.empty() && "No blocks in loop?");
    647 
    648       LoopRanges &loopRanges = loopRangeMap[&loop];
    649       assert(loopRanges.empty() && "Loop encountered but not processed?");
    650       SlotIndex oldEnd = lis->getMBBEndIdx(*loopMBBs.begin());
    651       loopRanges.push_back(
    652         std::make_pair(lis->getMBBStartIdx(*loopMBBs.begin()),
    653                        lis->getInvalidIndex()));
    654       for (LoopMBBSet::iterator curBlockItr = llvm::next(loopMBBs.begin()),
    655                                 curBlockEnd = loopMBBs.end();
    656            curBlockItr != curBlockEnd; ++curBlockItr) {
    657         SlotIndex newStart = lis->getMBBStartIdx(*curBlockItr);
    658         if (newStart != oldEnd) {
    659           loopRanges.back().second = oldEnd;
    660           loopRanges.push_back(std::make_pair(newStart,
    661                                               lis->getInvalidIndex()));
    662         }
    663         oldEnd = lis->getMBBEndIdx(*curBlockItr);
    664       }
    665 
    666       loopRanges.back().second =
    667         lis->getMBBEndIdx(*llvm::prior(loopMBBs.end()));
    668 
    669       return loopRanges;
    670     }
    671     return lrItr->second;
    672   }
    673 
    674   std::pair<bool, LoopSplitter::SlotPair> LoopSplitter::getLoopSubRange(
    675                                                            const LiveRange &lr,
    676                                                            MachineLoop &loop) {
    677     LoopRanges &loopRanges = getLoopRanges(loop);
    678     LoopRanges::iterator lrItr = loopRanges.begin(),
    679                          lrEnd = loopRanges.end();
    680     while (lrItr != lrEnd && lr.start >= lrItr->second) {
    681       ++lrItr;
    682     }
    683 
    684     if (lrItr == lrEnd) {
    685       SlotIndex invalid = lis->getInvalidIndex();
    686       return std::make_pair(false, SlotPair(invalid, invalid));
    687     }
    688 
    689     SlotIndex srStart(lr.start < lrItr->first ? lrItr->first : lr.start);
    690     SlotIndex srEnd(lr.end > lrItr->second ? lrItr->second : lr.end);
    691 
    692     return std::make_pair(true, SlotPair(srStart, srEnd));
    693   }
    694 
    695   void LoopSplitter::dumpLoopRanges(MachineLoop &loop) {
    696     LoopRanges &loopRanges = getLoopRanges(loop);
    697     dbgs() << "For loop MBB#" << loop.getHeader()->getNumber() << ", subranges are: [ ";
    698     for (LoopRanges::iterator lrItr = loopRanges.begin(), lrEnd = loopRanges.end();
    699          lrItr != lrEnd; ++lrItr) {
    700       dbgs() << "[" << lrItr->first << ", " << lrItr->second << ") ";
    701     }
    702     dbgs() << "]\n";
    703   }
    704 
    705   void LoopSplitter::processHeader(LoopSplit &split) {
    706     MachineBasicBlock &header = *split.getLoop().getHeader();
    707     //dbgs() << "  Processing loop header BB#" << header.getNumber() << "\n";
    708 
    709     if (!lis->isLiveInToMBB(split.getLI(), &header))
    710       return; // Not live in, but nothing wrong so far.
    711 
    712     MachineBasicBlock *preHeader = split.getLoop().getLoopPreheader();
    713     if (!preHeader) {
    714 
    715       if (!canInsertPreHeader(split.getLoop())) {
    716         split.invalidate();
    717         return; // Couldn't insert a pre-header. Bail on this interval.
    718       }
    719 
    720       for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(),
    721                                             predEnd = header.pred_end();
    722            predItr != predEnd; ++predItr) {
    723         if (lis->isLiveOutOfMBB(split.getLI(), *predItr)) {
    724           split.splitIncoming();
    725           break;
    726         }
    727       }
    728     } else if (lis->isLiveOutOfMBB(split.getLI(), preHeader)) {
    729       split.splitIncoming();
    730     }
    731   }
    732 
    733   void LoopSplitter::processLoopExits(LoopSplit &split) {
    734     typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList;
    735     ExitEdgesList exitEdges;
    736     split.getLoop().getExitEdges(exitEdges);
    737 
    738     //dbgs() << "  Processing loop exits:\n";
    739 
    740     for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(),
    741                                  exitEdgeEnd = exitEdges.end();
    742          exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) {
    743       MachineLoop::Edge exitEdge = *exitEdgeItr;
    744 
    745       LiveRange *outRange =
    746         split.getLI().getLiveRangeContaining(lis->getMBBStartIdx(exitEdge.second));
    747 
    748       if (outRange != 0) {
    749         if (isCriticalEdge(exitEdge) && !canSplitEdge(exitEdge)) {
    750           split.invalidate();
    751           return;
    752         }
    753 
    754         split.splitOutgoing(exitEdge);
    755       }
    756     }
    757   }
    758 
    759   void LoopSplitter::processLoopUses(LoopSplit &split) {
    760     std::set<MachineInstr*> processed;
    761 
    762     for (MachineRegisterInfo::reg_iterator
    763            rItr = mri->reg_begin(split.getLI().reg),
    764            rEnd = mri->reg_end();
    765       rItr != rEnd; ++rItr) {
    766       MachineInstr &instr = *rItr;
    767       if (split.getLoop().contains(&instr) && processed.count(&instr) == 0) {
    768         split.addLoopInstr(&instr);
    769         processed.insert(&instr);
    770       }
    771     }
    772 
    773     //dbgs() << "  Rewriting reg" << li.reg << " to reg" << newLI->reg
    774     //       << " in blocks [ ";
    775     //dbgs() << "]\n";
    776   }
    777 
    778   bool LoopSplitter::splitOverLoop(LiveInterval &li, MachineLoop &loop) {
    779     assert(TargetRegisterInfo::isVirtualRegister(li.reg) &&
    780            "Attempt to split physical register.");
    781 
    782     LoopSplit split(*this, li, loop);
    783     processHeader(split);
    784     if (split.isValid())
    785       processLoopExits(split);
    786     if (split.isValid())
    787       processLoopUses(split);
    788     if (split.isValid() /* && split.isWorthwhile() */) {
    789       split.apply();
    790       DEBUG(dbgs() << "Success.\n");
    791       return true;
    792     }
    793     DEBUG(dbgs() << "Failed.\n");
    794     return false;
    795   }
    796 
    797   void LoopSplitter::processInterval(LiveInterval &li) {
    798     std::deque<MachineLoop*> loops;
    799     std::copy(mli->begin(), mli->end(), std::back_inserter(loops));
    800 
    801     while (!loops.empty()) {
    802       MachineLoop &loop = *loops.front();
    803       loops.pop_front();
    804       DEBUG(
    805         dbgs() << fqn << " reg" << li.reg << " " << li.weight << " BB#"
    806                << loop.getHeader()->getNumber() << " ";
    807       );
    808       if (!splitOverLoop(li, loop)) {
    809         // Couldn't split over outer loop, schedule sub-loops to be checked.
    810 	std::copy(loop.begin(), loop.end(), std::back_inserter(loops));
    811       }
    812     }
    813   }
    814 
    815   void LoopSplitter::processIntervals() {
    816     while (!intervals.empty()) {
    817       LiveInterval &li = *intervals.front();
    818       intervals.pop_front();
    819 
    820       assert(!lis->intervalIsInOneMBB(li) &&
    821              "Single interval in process worklist.");
    822 
    823       processInterval(li);
    824     }
    825   }
    826 
    827 }
    828