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