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 "RegisterCoalescer.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"
  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.addPreserved<RegisterCoalescer>();
 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 }