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