lib/CodeGen/Splitter.cpp

   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 {
  42   class StartSlotComparator {
  43   public:
  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);
  48     }
  49   private:
  50     LiveIntervals &lis;
  51   };
  52 }
  53
  54 namespace llvm {
  55
  56   class LoopSplit {
  57   public:
  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.");
  62     }
  63
  64     LiveInterval& getLI() const { return li; }
  65
  66     MachineLoop& getLoop() const { return loop; }
  67
  68     bool isValid() const { return valid; }
  69
  70     bool isWorthwhile() const { return valid && (inSplit || !outSplits.empty()); }
  71
  72     void invalidate() { valid = false; }
  73
  74     void splitIncoming() { inSplit = true; }
  75
  76     void splitOutgoing(MachineLoop::Edge &edge) { outSplits.insert(edge); }
  77
  78     void addLoopInstr(MachineInstr *i) { loopInstrs.push_back(i); }
  79
  80     void apply() {
  81       assert(valid && "Attempt to apply invalid split.");
  82       applyIncoming();
  83       applyOutgoing();
  84       copyRanges();
  85       renameInside();
  86     }
  87
  88   private:
  89     LoopSplitter &ls;
  90     LiveInterval &li;
  91     MachineLoop &loop;
  92     bool valid, inSplit;
  93     std::set<MachineLoop::Edge> outSplits;
  94     std::vector<MachineInstr*> loopInstrs;
  95
  96     LiveInterval *newLI;
  97     std::map<VNInfo*, VNInfo*> vniMap;
  98
  99     LiveInterval* getNewLI() {
 100       if (newLI == 0) {
 101         const TargetRegisterClass *trc = ls.mri->getRegClass(li.reg);
 102         unsigned vreg = ls.mri->createVirtualRegister(trc);
 103         newLI = &ls.lis->getOrCreateInterval(vreg);
 104       }
 105       return newLI;
 106     }
 107
 108     VNInfo* getNewVNI(VNInfo *oldVNI) {
 109       VNInfo *newVNI = vniMap[oldVNI];
 110
 111       if (newVNI == 0) {
 112         newVNI = getNewLI()->createValueCopy(oldVNI,
 113                                              ls.lis->getVNInfoAllocator());
 114         vniMap[oldVNI] = newVNI;
 115       }
 116
 117       return newVNI;
 118     }
 119
 120     void applyIncoming() {
 121       if (!inSplit) {
 122         return;
 123       }
 124
 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);
 130       }
 131
 132       LiveRange *preHeaderRange =
 133         ls.lis->findExitingRange(li, preHeader);
 134       assert(preHeaderRange != 0 && "Range not live into preheader.");
 135
 136       // Insert the new copy.
 137       MachineInstr *copy = BuildMI(*preHeader,
 138                                    preHeader->getFirstTerminator(),
 139                                    DebugLoc(),
 140                                    ls.tii->get(TargetOpcode::COPY))
 141         .addReg(getNewLI()->reg, RegState::Define)
 142         .addReg(li.reg, RegState::Kill);
 143
 144       ls.lis->InsertMachineInstrInMaps(copy);
 145
 146       SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getRegSlot();
 147
 148       VNInfo *newVal = getNewVNI(preHeaderRange->valno);
 149       newVal->def = copyDefIdx;
 150       newVal->setCopy(copy);
 151       li.removeRange(copyDefIdx, ls.lis->getMBBEndIdx(preHeader), true);
 152
 153       getNewLI()->addRange(LiveRange(copyDefIdx,
 154                                      ls.lis->getMBBEndIdx(preHeader),
 155                                      newVal));
 156     }
 157
 158     void applyOutgoing() {
 159
 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);
 168         }
 169         LiveRange *outRange = ls.lis->findEnteringRange(li, outBlock);
 170         assert(outRange != 0 && "No exiting range?");
 171
 172         MachineInstr *copy = BuildMI(*outBlock, outBlock->begin(),
 173                                      DebugLoc(),
 174                                      ls.tii->get(TargetOpcode::COPY))
 175           .addReg(li.reg, RegState::Define)
 176           .addReg(getNewLI()->reg, RegState::Kill);
 177
 178         ls.lis->InsertMachineInstrInMaps(copy);
 179
 180         SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getRegSlot();
 181
 182         // Blow away output range definition.
 183         outRange->valno->def = ls.lis->getInvalidIndex();
 184         li.removeRange(ls.lis->getMBBStartIdx(outBlock), copyDefIdx);
 185
 186         SlotIndex newDefIdx = ls.lis->getMBBStartIdx(outBlock);
 187         assert(ls.lis->getInstructionFromIndex(newDefIdx) == 0 &&
 188                "PHI def index points at actual instruction.");
 189         VNInfo *newVal =
 190           getNewLI()->getNextValue(newDefIdx, 0, ls.lis->getVNInfoAllocator());
 191
 192         getNewLI()->addRange(LiveRange(ls.lis->getMBBStartIdx(outBlock),
 193                                        copyDefIdx, newVal));
 194
 195       }
 196     }
 197
 198     void copyRange(LiveRange &lr) {
 199       std::pair<bool, LoopSplitter::SlotPair> lsr =
 200         ls.getLoopSubRange(lr, loop);
 201
 202       if (!lsr.first)
 203         return;
 204
 205       LiveRange loopRange(lsr.second.first, lsr.second.second,
 206                           getNewVNI(lr.valno));
 207
 208       li.removeRange(loopRange.start, loopRange.end, true);
 209
 210       getNewLI()->addRange(loopRange);
 211     }
 212
 213     void copyRanges() {
 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);
 224         }
 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);
 230           }
 231         }
 232       }
 233
 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);
 242         }
 243       }
 244     }
 245
 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);
 255           }
 256         }
 257       }
 258     }
 259
 260   };
 261
 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);
 275   }
 276
 277   bool LoopSplitter::runOnMachineFunction(MachineFunction &fn) {
 278
 279     mf = &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>();
 287
 288     fqn = mf->getFunction()->getParent()->getModuleIdentifier() + "." +
 289       mf->getFunction()->getName().str();
 290
 291     dbgs() << "Splitting " << mf->getFunction()->getName() << ".";
 292
 293     dumpOddTerminators();
 294
 295 //      dbgs() << "----------------------------------------\n";
 296 //      lis->dump();
 297 //      dbgs() << "----------------------------------------\n";
 298
 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));
 306
 307 //       dumpLoopInfo(loop);
 308 //     }
 309
 310     //lis->dump();
 311     //exit(0);
 312
 313     // Setup initial intervals.
 314     for (LiveIntervals::iterator liItr = lis->begin(), liEnd = lis->end();
 315          liItr != liEnd; ++liItr) {
 316       LiveInterval *li = liItr->second;
 317
 318       if (TargetRegisterInfo::isVirtualRegister(li->reg) &&
 319           !lis->intervalIsInOneMBB(*li)) {
 320         intervals.push_back(li);
 321       }
 322     }
 323
 324     processIntervals();
 325
 326     intervals.clear();
 327
 328 //     dbgs() << "----------------------------------------\n";
 329 //     lis->dump();
 330 //     dbgs() << "----------------------------------------\n";
 331
 332     dumpOddTerminators();
 333
 334     //exit(1);
 335
 336     return false;
 337   }
 338
 339   void LoopSplitter::releaseMemory() {
 340     fqn.clear();
 341     intervals.clear();
 342     loopRangeMap.clear();
 343   }
 344
 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 << "";
 358         }
 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() << " ";
 364         }
 365         dbgs() << "]\n\n";
 366       }
 367     }
 368   }
 369
 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);
 375
 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() << " ";
 383     }
 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() << ") ";
 391     }
 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() << " ";
 399     }
 400     dbgs() << "]\n";
 401   }
 402
 403   void LoopSplitter::updateTerminators(MachineBasicBlock &mbb) {
 404     mbb.updateTerminator();
 405
 406     for (MachineBasicBlock::iterator miItr = mbb.begin(), miEnd = mbb.end();
 407          miItr != miEnd; ++miItr) {
 408       if (lis->isNotInMIMap(miItr)) {
 409         lis->InsertMachineInstrInMaps(miItr);
 410       }
 411     }
 412   }
 413
 414   bool LoopSplitter::canInsertPreHeader(MachineLoop &loop) {
 415     MachineBasicBlock *header = loop.getHeader();
 416     MachineBasicBlock *a = 0, *b = 0;
 417     SmallVector<MachineOperand, 4> c;
 418
 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)) {
 424         return false;
 425       }
 426     }
 427
 428     MachineFunction::iterator headerItr(header);
 429     if (headerItr == mf->begin())
 430       return true;
 431     MachineBasicBlock *headerLayoutPred = llvm::prior(headerItr);
 432     assert(headerLayoutPred != 0 && "Header should have layout pred.");
 433
 434     return (!tii->AnalyzeBranch(*headerLayoutPred, a, b, c));
 435   }
 436
 437   MachineBasicBlock& LoopSplitter::insertPreHeader(MachineLoop &loop) {
 438     assert(loop.getLoopPreheader() == 0 && "Loop already has preheader.");
 439
 440     MachineBasicBlock &header = *loop.getHeader();
 441
 442     // Save the preds - we'll need to update them once we insert the preheader.
 443     typedef std::set<MachineBasicBlock*> HeaderPreds;
 444     HeaderPreds headerPreds;
 445
 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);
 451     }
 452
 453     assert(!headerPreds.empty() && "No predecessors for header?");
 454
 455     //dbgs() << fqn << " MBB#" << header.getNumber() << " inserting preheader...";
 456
 457     MachineBasicBlock *preHeader =
 458       mf->CreateMachineBasicBlock(header.getBasicBlock());
 459
 460     assert(preHeader != 0 && "Failed to create pre-header.");
 461
 462     mf->insert(header, preHeader);
 463
 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);
 470     }
 471     preHeader->addSuccessor(&header);
 472
 473     MachineBasicBlock *oldLayoutPred =
 474       llvm::prior(MachineFunction::iterator(preHeader));
 475     if (oldLayoutPred != 0) {
 476       updateTerminators(*oldLayoutPred);
 477     }
 478
 479     lis->InsertMBBInMaps(preHeader);
 480
 481     if (MachineLoop *parentLoop = loop.getParentLoop()) {
 482       assert(parentLoop->getHeader() != loop.getHeader() &&
 483              "Parent loop has same header?");
 484       parentLoop->addBasicBlockToLoop(preHeader, mli->getBase());
 485
 486       // Invalidate all parent loop ranges.
 487       while (parentLoop != 0) {
 488         loopRangeMap.erase(parentLoop);
 489         parentLoop = parentLoop->getParentLoop();
 490       }
 491     }
 492
 493     for (LiveIntervals::iterator liItr = lis->begin(),
 494                                  liEnd = lis->end();
 495          liItr != liEnd; ++liItr) {
 496       LiveInterval &li = *liItr->second;
 497
 498       // Is this safe for physregs?
 499       // TargetRegisterInfo::isPhysicalRegister(li.reg) ||
 500       if (!lis->isLiveInToMBB(li, &header))
 501         continue;
 502
 503       if (lis->isLiveInToMBB(li, preHeader)) {
 504         assert(lis->isLiveOutOfMBB(li, preHeader) &&
 505                "Range terminates in newly added preheader?");
 506         continue;
 507       }
 508
 509       bool insertRange = false;
 510
 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)) {
 516           insertRange = true;
 517           break;
 518         }
 519       }
 520
 521       if (!insertRange)
 522         continue;
 523
 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),
 530                             newVal));
 531     }
 532
 533
 534     //dbgs() << "Dumping SlotIndexes:\n";
 535     //sis->dump();
 536
 537     //dbgs() << "done. (Added MBB#" << preHeader->getNumber() << ")\n";
 538
 539     return *preHeader;
 540   }
 541
 542   bool LoopSplitter::isCriticalEdge(MachineLoop::Edge &edge) {
 543     assert(edge.first->succ_size() > 1 && "Non-sensical edge.");
 544     if (edge.second->pred_size() > 1)
 545       return true;
 546     return false;
 547   }
 548
 549   bool LoopSplitter::canSplitEdge(MachineLoop::Edge &edge) {
 550     MachineFunction::iterator outBlockItr(edge.second);
 551     if (outBlockItr == mf->begin())
 552       return true;
 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));
 559   }
 560
 561   MachineBasicBlock& LoopSplitter::splitEdge(MachineLoop::Edge &edge,
 562                                              MachineLoop &loop) {
 563
 564     MachineBasicBlock &inBlock = *edge.first;
 565     MachineBasicBlock &outBlock = *edge.second;
 566
 567     assert((inBlock.succ_size() > 1) && (outBlock.pred_size() > 1) &&
 568            "Splitting non-critical edge?");
 569
 570     //dbgs() << fqn << " Splitting edge (MBB#" << inBlock.getNumber()
 571     //       << " -> MBB#" << outBlock.getNumber() << ")...";
 572
 573     MachineBasicBlock *splitBlock =
 574       mf->CreateMachineBasicBlock();
 575
 576     assert(splitBlock != 0 && "Failed to create split block.");
 577
 578     mf->insert(&outBlock, splitBlock);
 579
 580     inBlock.ReplaceUsesOfBlockWith(&outBlock, splitBlock);
 581     splitBlock->addSuccessor(&outBlock);
 582
 583     MachineBasicBlock *oldLayoutPred =
 584       llvm::prior(MachineFunction::iterator(splitBlock));
 585     if (oldLayoutPred != 0) {
 586       updateTerminators(*oldLayoutPred);
 587     }
 588
 589     lis->InsertMBBInMaps(splitBlock);
 590
 591     loopRangeMap.erase(&loop);
 592
 593     MachineLoop *splitParentLoop = loop.getParentLoop();
 594     while (splitParentLoop != 0 &&
 595            !splitParentLoop->contains(&outBlock)) {
 596       splitParentLoop = splitParentLoop->getParentLoop();
 597     }
 598
 599     if (splitParentLoop != 0) {
 600       assert(splitParentLoop->contains(&loop) &&
 601              "Split-block parent doesn't contain original loop?");
 602       splitParentLoop->addBasicBlockToLoop(splitBlock, mli->getBase());
 603
 604       // Invalidate all parent loop ranges.
 605       while (splitParentLoop != 0) {
 606         loopRangeMap.erase(splitParentLoop);
 607         splitParentLoop = splitParentLoop->getParentLoop();
 608       }
 609     }
 610
 611
 612     for (LiveIntervals::iterator liItr = lis->begin(),
 613                                  liEnd = lis->end();
 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)) {
 619         if (!intersects) {
 620           li.removeRange(lis->getMBBStartIdx(splitBlock),
 621                          lis->getMBBEndIdx(splitBlock), true);
 622         }
 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),
 631                               newVal));
 632       }
 633     }
 634
 635     //dbgs() << "done. (Added MBB#" << splitBlock->getNumber() << ")\n";
 636
 637     return *splitBlock;
 638   }
 639
 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()));
 647
 648       assert(!loopMBBs.empty() && "No blocks in loop?");
 649
 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()));
 664         }
 665         oldEnd = lis->getMBBEndIdx(*curBlockItr);
 666       }
 667
 668       loopRanges.back().second =
 669         lis->getMBBEndIdx(*llvm::prior(loopMBBs.end()));
 670
 671       return loopRanges;
 672     }
 673     return lrItr->second;
 674   }
 675
 676   std::pair<bool, LoopSplitter::SlotPair> LoopSplitter::getLoopSubRange(
 677                                                            const LiveRange &lr,
 678                                                            MachineLoop &loop) {
 679     LoopRanges &loopRanges = getLoopRanges(loop);
 680     LoopRanges::iterator lrItr = loopRanges.begin(),
 681                          lrEnd = loopRanges.end();
 682     while (lrItr != lrEnd && lr.start >= lrItr->second) {
 683       ++lrItr;
 684     }
 685
 686     if (lrItr == lrEnd) {
 687       SlotIndex invalid = lis->getInvalidIndex();
 688       return std::make_pair(false, SlotPair(invalid, invalid));
 689     }
 690
 691     SlotIndex srStart(lr.start < lrItr->first ? lrItr->first : lr.start);
 692     SlotIndex srEnd(lr.end > lrItr->second ? lrItr->second : lr.end);
 693
 694     return std::make_pair(true, SlotPair(srStart, srEnd));
 695   }
 696
 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 << ") ";
 703     }
 704     dbgs() << "]\n";
 705   }
 706
 707   void LoopSplitter::processHeader(LoopSplit &split) {
 708     MachineBasicBlock &header = *split.getLoop().getHeader();
 709     //dbgs() << "  Processing loop header BB#" << header.getNumber() << "\n";
 710
 711     if (!lis->isLiveInToMBB(split.getLI(), &header))
 712       return; // Not live in, but nothing wrong so far.
 713
 714     MachineBasicBlock *preHeader = split.getLoop().getLoopPreheader();
 715     if (!preHeader) {
 716
 717       if (!canInsertPreHeader(split.getLoop())) {
 718         split.invalidate();
 719         return; // Couldn't insert a pre-header. Bail on this interval.
 720       }
 721
 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();
 727           break;
 728         }
 729       }
 730     } else if (lis->isLiveOutOfMBB(split.getLI(), preHeader)) {
 731       split.splitIncoming();
 732     }
 733   }
 734
 735   void LoopSplitter::processLoopExits(LoopSplit &split) {
 736     typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList;
 737     ExitEdgesList exitEdges;
 738     split.getLoop().getExitEdges(exitEdges);
 739
 740     //dbgs() << "  Processing loop exits:\n";
 741
 742     for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(),
 743                                  exitEdgeEnd = exitEdges.end();
 744          exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) {
 745       MachineLoop::Edge exitEdge = *exitEdgeItr;
 746
 747       LiveRange *outRange =
 748         split.getLI().getLiveRangeContaining(lis->getMBBStartIdx(exitEdge.second));
 749
 750       if (outRange != 0) {
 751         if (isCriticalEdge(exitEdge) && !canSplitEdge(exitEdge)) {
 752           split.invalidate();
 753           return;
 754         }
 755
 756         split.splitOutgoing(exitEdge);
 757       }
 758     }
 759   }
 760
 761   void LoopSplitter::processLoopUses(LoopSplit &split) {
 762     std::set<MachineInstr*> processed;
 763
 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);
 772       }
 773     }
 774
 775     //dbgs() << "  Rewriting reg" << li.reg << " to reg" << newLI->reg
 776     //       << " in blocks [ ";
 777     //dbgs() << "]\n";
 778   }
 779
 780   bool LoopSplitter::splitOverLoop(LiveInterval &li, MachineLoop &loop) {
 781     assert(TargetRegisterInfo::isVirtualRegister(li.reg) &&
 782            "Attempt to split physical register.");
 783
 784     LoopSplit split(*this, li, loop);
 785     processHeader(split);
 786     if (split.isValid())
 787       processLoopExits(split);
 788     if (split.isValid())
 789       processLoopUses(split);
 790     if (split.isValid() /* && split.isWorthwhile() */) {
 791       split.apply();
 792       DEBUG(dbgs() << "Success.\n");
 793       return true;
 794     }
 795     DEBUG(dbgs() << "Failed.\n");
 796     return false;
 797   }
 798
 799   void LoopSplitter::processInterval(LiveInterval &li) {
 800     std::deque<MachineLoop*> loops;
 801     std::copy(mli->begin(), mli->end(), std::back_inserter(loops));
 802
 803     while (!loops.empty()) {
 804       MachineLoop &loop = *loops.front();
 805       loops.pop_front();
 806       DEBUG(
 807         dbgs() << fqn << " reg" << li.reg << " " << li.weight << " BB#"
 808                << loop.getHeader()->getNumber() << " ";
 809       );
 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));
 813       }
 814     }
 815   }
 816
 817   void LoopSplitter::processIntervals() {
 818     while (!intervals.empty()) {
 819       LiveInterval &li = *intervals.front();
 820       intervals.pop_front();
 821
 822       assert(!lis->intervalIsInOneMBB(li) &&
 823              "Single interval in process worklist.");
 824
 825       processInterval(li);
 826     }
 827   }
 828
 829 }