LoopSplitter - intended to split live intervals over loop boundaries.

Still very much under development. Comments and fixes will be forthcoming.

(This commit includes some small tweaks to LiveIntervals & LoopInfo to support the splitter)



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@108615 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 948 insertions, 3 deletions

diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index 9455fd8..2d93909 100644
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -229,9 +229,12 @@ public:
     return 0;
   }
 
+  /// Edge type.
+  typedef std::pair<BlockT*, BlockT*> Edge;
+
   /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
-  typedef std::pair<const BlockT*,const BlockT*> Edge;
-  void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const {
+  template <typename EdgeT>
+  void getExitEdges(SmallVectorImpl<EdgeT> &ExitEdges) const {
     // Sort the blocks vector so that we can use binary search to do quick
     // lookups.
     SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
@@ -244,7 +247,7 @@ public:
            I != E; ++I)
         if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
           // Not in current loop? It must be an exit block.
-          ExitEdges.push_back(std::make_pair(*BI, *I));
+          ExitEdges.push_back(EdgeT(*BI, *I));
   }
 
   /// getLoopPreheader - If there is a preheader for this loop, return it.  A
diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index c136048..8a59bf1 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -197,6 +197,26 @@ namespace llvm {
       return indexes_->getMBBEndIdx(mbb);
     } 
 
+    bool isLiveInToMBB(const LiveInterval &li,
+                       const MachineBasicBlock *mbb) const {
+      return li.liveAt(getMBBStartIdx(mbb));
+    }
+
+    LiveRange* findEnteringRange(LiveInterval &li,
+                                 const MachineBasicBlock *mbb) {
+      return li.getLiveRangeContaining(getMBBStartIdx(mbb));
+    }
+
+    bool isLiveOutOfMBB(const LiveInterval &li,
+                        const MachineBasicBlock *mbb) const {
+      return li.liveAt(getMBBEndIdx(mbb).getPrevSlot());
+    }
+
+    LiveRange* findExitingRange(LiveInterval &li,
+                                const MachineBasicBlock *mbb) {
+      return li.getLiveRangeContaining(getMBBEndIdx(mbb).getPrevSlot());
+    }
+
     MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
       return indexes_->getMBBFromIndex(index);
     }
@@ -217,6 +237,10 @@ namespace llvm {
       indexes_->replaceMachineInstrInMaps(MI, NewMI);
     }
 
+    void InsertMBBInMaps(MachineBasicBlock *MBB) {
+      indexes_->insertMBBInMaps(MBB);
+    }
+
     bool findLiveInMBBs(SlotIndex Start, SlotIndex End,
                         SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
       return indexes_->findLiveInMBBs(Start, End, MBBs);
diff --git a/lib/CodeGen/Splitter.cpp b/lib/CodeGen/Splitter.cpp
new file mode 100644
index 0000000..c2f2591f
--- /dev/null
+++ b/lib/CodeGen/Splitter.cpp
@@ -0,0 +1,819 @@
+//===-- llvm/CodeGen/Splitter.cpp -  Splitter -----------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "loopsplitter"
+
+#include "Splitter.h"
+
+#include "SimpleRegisterCoalescing.h"
+#include "llvm/Module.h"
+#include "llvm/CodeGen/CalcSpillWeights.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveStackAnalysis.h"
+#include "llvm/CodeGen/MachineDominators.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/SlotIndexes.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetInstrInfo.h"
+
+using namespace llvm;
+
+char LoopSplitter::ID = 0;
+static RegisterPass<LoopSplitter>
+X("loop-splitting", "Split virtual regists across loop boundaries.");
+
+namespace llvm {
+
+  class StartSlotComparator {
+  public:
+    StartSlotComparator(LiveIntervals &lis) : lis(lis) {}
+    bool operator()(const MachineBasicBlock *mbb1,
+                    const MachineBasicBlock *mbb2) const {
+      return lis.getMBBStartIdx(mbb1) < lis.getMBBStartIdx(mbb2);
+    }
+  private:
+    LiveIntervals &lis;
+  };
+
+  class LoopSplit {
+  public:
+    LoopSplit(LoopSplitter &ls, LiveInterval &li, MachineLoop &loop)
+      : ls(ls), li(li), loop(loop), valid(true), inSplit(false), newLI(0) {
+      assert(TargetRegisterInfo::isVirtualRegister(li.reg) &&
+             "Cannot split physical registers.");
+    }
+
+    LiveInterval& getLI() const { return li; }
+
+    MachineLoop& getLoop() const { return loop; }
+
+    bool isValid() const { return valid; }
+
+    bool isWorthwhile() const { return valid && (inSplit || !outSplits.empty()); }
+
+    void invalidate() { valid = false; }
+
+    void splitIncoming() { inSplit = true; }
+
+    void splitOutgoing(MachineLoop::Edge &edge) { outSplits.insert(edge); }
+
+    void addLoopInstr(MachineInstr *i) { loopInstrs.push_back(i); }
+
+    void apply() {
+      assert(valid && "Attempt to apply invalid split.");
+      applyIncoming();
+      applyOutgoing();
+      copyRanges();
+      renameInside();
+    }
+
+  private:
+    LoopSplitter &ls;
+    LiveInterval &li;
+    MachineLoop &loop;
+    bool valid, inSplit;
+    std::set<MachineLoop::Edge> outSplits;
+    std::vector<MachineInstr*> loopInstrs;
+
+    LiveInterval *newLI;
+    std::map<VNInfo*, VNInfo*> vniMap;
+
+    LiveInterval* getNewLI() {
+      if (newLI == 0) {
+        const TargetRegisterClass *trc = ls.mri->getRegClass(li.reg);
+        unsigned vreg = ls.mri->createVirtualRegister(trc);
+        newLI = &ls.lis->getOrCreateInterval(vreg);
+      }
+      return newLI;
+    }
+
+    VNInfo* getNewVNI(VNInfo *oldVNI) {
+      VNInfo *newVNI = vniMap[oldVNI];
+
+      if (newVNI == 0) {
+        newVNI = getNewLI()->createValueCopy(oldVNI,
+                                             ls.lis->getVNInfoAllocator());
+        vniMap[oldVNI] = newVNI;
+      }
+
+      return newVNI;
+    }
+
+    void applyIncoming() {
+      if (!inSplit) {
+        return;
+      }
+
+      MachineBasicBlock *preHeader = loop.getLoopPreheader();
+      if (preHeader == 0) {
+        assert(ls.canInsertPreHeader(loop) &&
+               "Can't insert required preheader.");
+        preHeader = &ls.insertPreHeader(loop);
+      }
+
+      LiveRange *preHeaderRange =
+        ls.lis->findExitingRange(li, preHeader);
+      assert(preHeaderRange != 0 && "Range not live into preheader.");
+
+      // Insert the new copy.
+      MachineInstr *copy = BuildMI(*preHeader,
+                                   preHeader->getFirstTerminator(),
+                                   DebugLoc(),
+                                   ls.tii->get(TargetOpcode::COPY))
+        .addReg(getNewLI()->reg, RegState::Define)
+        .addReg(li.reg, RegState::Kill);
+
+      ls.lis->InsertMachineInstrInMaps(copy);
+
+      SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getDefIndex();
+
+      VNInfo *newVal = getNewVNI(preHeaderRange->valno);
+      newVal->def = copyDefIdx;
+      newVal->setCopy(copy);
+      newVal->setIsDefAccurate(true);
+      li.removeRange(copyDefIdx, ls.lis->getMBBEndIdx(preHeader), true);
+
+      getNewLI()->addRange(LiveRange(copyDefIdx,
+                                     ls.lis->getMBBEndIdx(preHeader),
+                                     newVal));
+    }
+
+    void applyOutgoing() {
+
+      for (std::set<MachineLoop::Edge>::iterator osItr = outSplits.begin(),
+                                                 osEnd = outSplits.end();
+           osItr != osEnd; ++osItr) {
+        MachineLoop::Edge edge = *osItr;
+        MachineBasicBlock *outBlock = edge.second;
+        if (ls.isCriticalEdge(edge)) {
+          assert(ls.canSplitEdge(edge) && "Unsplitable critical edge.");
+          outBlock = &ls.splitEdge(edge, loop);
+        }
+        LiveRange *outRange = ls.lis->findEnteringRange(li, outBlock);
+        assert(outRange != 0 && "No exiting range?");
+
+        MachineInstr *copy = BuildMI(*outBlock, outBlock->begin(),
+                                     DebugLoc(),
+                                     ls.tii->get(TargetOpcode::COPY))
+          .addReg(li.reg, RegState::Define)
+          .addReg(getNewLI()->reg, RegState::Kill);
+
+        ls.lis->InsertMachineInstrInMaps(copy);
+
+        SlotIndex copyDefIdx = ls.lis->getInstructionIndex(copy).getDefIndex();
+        
+        // Blow away output range definition.
+        outRange->valno->def = ls.lis->getInvalidIndex();
+        outRange->valno->setIsDefAccurate(false);
+        li.removeRange(ls.lis->getMBBStartIdx(outBlock), copyDefIdx);
+
+        VNInfo *newVal =
+          getNewLI()->getNextValue(SlotIndex(ls.lis->getMBBStartIdx(outBlock),
+                                             true),
+                                   0, false, ls.lis->getVNInfoAllocator());
+
+        getNewLI()->addRange(LiveRange(ls.lis->getMBBStartIdx(outBlock),
+                                       copyDefIdx, newVal));
+                                       
+      }
+    }
+
+    void copyRange(LiveRange &lr) {
+      std::pair<bool, LoopSplitter::SlotPair> lsr =
+        ls.getLoopSubRange(lr, loop);
+      
+      if (!lsr.first)
+        return;
+
+      LiveRange loopRange(lsr.second.first, lsr.second.second,
+                          getNewVNI(lr.valno));
+
+      li.removeRange(loopRange.start, loopRange.end, true);
+
+      getNewLI()->addRange(loopRange);
+    }
+
+    void copyRanges() {
+      for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(),
+                                                iEnd = loopInstrs.end();
+           iItr != iEnd; ++iItr) {
+        MachineInstr &instr = **iItr;
+        SlotIndex instrIdx = ls.lis->getInstructionIndex(&instr);
+        if (instr.modifiesRegister(li.reg, 0)) {
+          LiveRange *defRange =
+            li.getLiveRangeContaining(instrIdx.getDefIndex());
+          if (defRange != 0) // May have caught this already.
+            copyRange(*defRange);
+        }
+        if (instr.readsRegister(li.reg, 0)) {
+          LiveRange *useRange =
+            li.getLiveRangeContaining(instrIdx.getUseIndex());
+          if (useRange != 0) { // May have caught this already.
+            copyRange(*useRange);
+          }
+        }
+      }
+
+      for (MachineLoop::block_iterator bbItr = loop.block_begin(),
+                                       bbEnd = loop.block_end();
+           bbItr != bbEnd; ++bbItr) {
+        MachineBasicBlock &loopBlock = **bbItr;
+        LiveRange *enteringRange =
+          ls.lis->findEnteringRange(li, &loopBlock);
+        if (enteringRange != 0) {
+          copyRange(*enteringRange);
+        }
+      }
+    } 
+
+    void renameInside() {
+      for (std::vector<MachineInstr*>::iterator iItr = loopInstrs.begin(),
+                                                iEnd = loopInstrs.end();
+           iItr != iEnd; ++iItr) {
+        MachineInstr &instr = **iItr;
+        for (unsigned i = 0; i < instr.getNumOperands(); ++i) {
+          MachineOperand &mop = instr.getOperand(i);
+          if (mop.isReg() && mop.getReg() == li.reg) {
+            mop.setReg(getNewLI()->reg);
+          }
+        }
+      }
+    }
+
+  };
+
+  void LoopSplitter::getAnalysisUsage(AnalysisUsage &au) const {
+    au.addRequired<MachineDominatorTree>();
+    au.addPreserved<MachineDominatorTree>();
+    au.addRequired<MachineLoopInfo>();
+    au.addPreserved<MachineLoopInfo>();
+    au.addPreserved<RegisterCoalescer>();
+    au.addPreserved<CalculateSpillWeights>();
+    au.addPreserved<LiveStacks>();
+    au.addRequired<SlotIndexes>();
+    au.addPreserved<SlotIndexes>();
+    au.addRequired<LiveIntervals>();
+    au.addPreserved<LiveIntervals>();
+    MachineFunctionPass::getAnalysisUsage(au);
+  }
+
+  bool LoopSplitter::runOnMachineFunction(MachineFunction &fn) {
+
+    mf = &fn;
+    mri = &mf->getRegInfo();
+    tii = mf->getTarget().getInstrInfo();
+    tri = mf->getTarget().getRegisterInfo();
+    sis = &getAnalysis<SlotIndexes>();
+    lis = &getAnalysis<LiveIntervals>();
+    mli = &getAnalysis<MachineLoopInfo>();
+    mdt = &getAnalysis<MachineDominatorTree>();
+
+    fqn = mf->getFunction()->getParent()->getModuleIdentifier() + "." +
+      mf->getFunction()->getName().str();
+
+    dbgs() << "Splitting " << mf->getFunction()->getName() << ".";
+
+    dumpOddTerminators();
+
+//      dbgs() << "----------------------------------------\n";
+//      lis->dump();
+//      dbgs() << "----------------------------------------\n";
+       
+//     std::deque<MachineLoop*> loops;
+//     std::copy(mli->begin(), mli->end(), std::back_inserter(loops));
+//     dbgs() << "Loops:\n";
+//     while (!loops.empty()) {
+//       MachineLoop &loop = *loops.front();
+//       loops.pop_front();
+//       std::copy(loop.begin(), loop.end(), std::back_inserter(loops));
+
+//       dumpLoopInfo(loop);
+//     }
+    
+    //lis->dump();
+    //exit(0);
+
+    // Setup initial intervals.
+    for (LiveIntervals::iterator liItr = lis->begin(), liEnd = lis->end();
+         liItr != liEnd; ++liItr) {
+      LiveInterval *li = liItr->second;
+
+      if (TargetRegisterInfo::isVirtualRegister(li->reg) &&
+          !lis->intervalIsInOneMBB(*li)) {
+        intervals.push_back(li);
+      }
+    }
+
+    processIntervals();
+
+    intervals.clear();
+
+//     dbgs() << "----------------------------------------\n";
+//     lis->dump();
+//     dbgs() << "----------------------------------------\n";
+
+    dumpOddTerminators();
+
+    //exit(1);
+
+    return false;
+  }
+
+  void LoopSplitter::releaseMemory() {
+    fqn.clear();
+    intervals.clear();
+    loopRangeMap.clear();
+  }
+
+  void LoopSplitter::dumpOddTerminators() {
+    for (MachineFunction::iterator bbItr = mf->begin(), bbEnd = mf->end();
+         bbItr != bbEnd; ++bbItr) {
+      MachineBasicBlock *mbb = &*bbItr;
+      MachineBasicBlock *a = 0, *b = 0;
+      SmallVector<MachineOperand, 4> c;
+      if (tii->AnalyzeBranch(*mbb, a, b, c)) {
+        dbgs() << "MBB#" << mbb->getNumber() << " has multiway terminator.\n";
+        dbgs() << "  Terminators:\n";
+        for (MachineBasicBlock::iterator iItr = mbb->begin(), iEnd = mbb->end();
+             iItr != iEnd; ++iItr) {
+          MachineInstr *instr= &*iItr;
+          dbgs() << "    " << *instr << "";
+        }
+        dbgs() << "\n  Listed successors: [ ";
+        for (MachineBasicBlock::succ_iterator sItr = mbb->succ_begin(), sEnd = mbb->succ_end();
+             sItr != sEnd; ++sItr) {
+          MachineBasicBlock *succMBB = *sItr;
+          dbgs() << succMBB->getNumber() << " ";
+        }
+        dbgs() << "]\n\n";
+      }
+    }
+  }
+
+  void LoopSplitter::dumpLoopInfo(MachineLoop &loop) {
+    MachineBasicBlock &headerBlock = *loop.getHeader();
+    typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList;
+    ExitEdgesList exitEdges;
+    loop.getExitEdges(exitEdges);
+
+    dbgs() << "  Header: BB#" << headerBlock.getNumber() << ", Contains: [ ";
+    for (std::vector<MachineBasicBlock*>::const_iterator
+           subBlockItr = loop.getBlocks().begin(),
+           subBlockEnd = loop.getBlocks().end();
+         subBlockItr != subBlockEnd; ++subBlockItr) {
+      MachineBasicBlock &subBlock = **subBlockItr;
+      dbgs() << "BB#" << subBlock.getNumber() << " ";
+    }
+    dbgs() << "], Exit edges: [ ";
+    for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(),
+                                 exitEdgeEnd = exitEdges.end();
+         exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) {
+      MachineLoop::Edge &exitEdge = *exitEdgeItr;
+      dbgs() << "(MBB#" << exitEdge.first->getNumber()
+             << ", MBB#" << exitEdge.second->getNumber() << ") ";
+    }
+    dbgs() << "], Sub-Loop Headers: [ ";
+    for (MachineLoop::iterator subLoopItr = loop.begin(),
+                               subLoopEnd = loop.end();
+         subLoopItr != subLoopEnd; ++subLoopItr) {
+      MachineLoop &subLoop = **subLoopItr;
+      MachineBasicBlock &subLoopBlock = *subLoop.getHeader();
+      dbgs() << "BB#" << subLoopBlock.getNumber() << " ";
+    }
+    dbgs() << "]\n";
+  }
+
+  void LoopSplitter::updateTerminators(MachineBasicBlock &mbb) {
+    mbb.updateTerminator();
+
+    for (MachineBasicBlock::iterator miItr = mbb.begin(), miEnd = mbb.end();
+         miItr != miEnd; ++miItr) {
+      if (lis->isNotInMIMap(miItr)) {
+        lis->InsertMachineInstrInMaps(miItr);
+      }
+    }
+  }
+
+  bool LoopSplitter::canInsertPreHeader(MachineLoop &loop) {
+    MachineBasicBlock *header = loop.getHeader();
+    MachineBasicBlock *a = 0, *b = 0;
+    SmallVector<MachineOperand, 4> c;
+
+    for (MachineBasicBlock::pred_iterator pbItr = header->pred_begin(),
+                                          pbEnd = header->pred_end();
+         pbItr != pbEnd; ++pbItr) {
+      MachineBasicBlock *predBlock = *pbItr;
+      if (!!tii->AnalyzeBranch(*predBlock, a, b, c)) {
+        return false;
+      }
+    }
+
+    MachineFunction::iterator headerItr(header);
+    if (headerItr == mf->begin())
+      return true;
+    MachineBasicBlock *headerLayoutPred = llvm::prior(headerItr);
+    assert(headerLayoutPred != 0 && "Header should have layout pred.");
+
+    return (!tii->AnalyzeBranch(*headerLayoutPred, a, b, c));
+  }
+
+  MachineBasicBlock& LoopSplitter::insertPreHeader(MachineLoop &loop) {
+    assert(loop.getLoopPreheader() == 0 && "Loop already has preheader.");
+
+    MachineBasicBlock &header = *loop.getHeader();
+
+    // Save the preds - we'll need to update them once we insert the preheader.
+    typedef std::set<MachineBasicBlock*> HeaderPreds;
+    HeaderPreds headerPreds;
+
+    for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(),
+                                          predEnd = header.pred_end();
+         predItr != predEnd; ++predItr) {
+      if (!loop.contains(*predItr))
+        headerPreds.insert(*predItr);
+    }
+
+    assert(!headerPreds.empty() && "No predecessors for header?");
+
+    //dbgs() << fqn << " MBB#" << header.getNumber() << " inserting preheader...";
+
+    MachineBasicBlock *preHeader =
+      mf->CreateMachineBasicBlock(header.getBasicBlock());
+
+    assert(preHeader != 0 && "Failed to create pre-header.");
+
+    mf->insert(header, preHeader);
+
+    for (HeaderPreds::iterator hpItr = headerPreds.begin(),
+                               hpEnd = headerPreds.end(); 
+         hpItr != hpEnd; ++hpItr) {
+      assert(*hpItr != 0 && "How'd a null predecessor get into this set?");
+      MachineBasicBlock &hp = **hpItr;
+      hp.ReplaceUsesOfBlockWith(&header, preHeader);
+    }
+    preHeader->addSuccessor(&header);
+
+    MachineBasicBlock *oldLayoutPred =
+      llvm::prior(MachineFunction::iterator(preHeader));
+    if (oldLayoutPred != 0) {
+      updateTerminators(*oldLayoutPred);
+    }
+
+    lis->InsertMBBInMaps(preHeader);
+
+    if (MachineLoop *parentLoop = loop.getParentLoop()) {
+      assert(parentLoop->getHeader() != loop.getHeader() &&
+             "Parent loop has same header?");
+      parentLoop->addBasicBlockToLoop(preHeader, mli->getBase());
+
+      // Invalidate all parent loop ranges.
+      while (parentLoop != 0) {
+        loopRangeMap.erase(parentLoop);
+        parentLoop = parentLoop->getParentLoop();
+      }
+    }
+
+    for (LiveIntervals::iterator liItr = lis->begin(),
+                                 liEnd = lis->end();
+         liItr != liEnd; ++liItr) {
+      LiveInterval &li = *liItr->second;
+
+      // Is this safe for physregs?
+      // TargetRegisterInfo::isPhysicalRegister(li.reg) ||
+      if (!lis->isLiveInToMBB(li, &header))
+        continue;
+
+      if (lis->isLiveInToMBB(li, preHeader)) {
+        assert(lis->isLiveOutOfMBB(li, preHeader) &&
+               "Range terminates in newly added preheader?");
+        continue;
+      }
+
+      bool insertRange = false;
+
+      for (MachineBasicBlock::pred_iterator predItr = preHeader->pred_begin(),
+                                            predEnd = preHeader->pred_end();
+           predItr != predEnd; ++predItr) {
+        MachineBasicBlock *predMBB = *predItr;
+        if (lis->isLiveOutOfMBB(li, predMBB)) {
+          insertRange = true;
+          break;
+        }
+      }
+
+      if (!insertRange)
+        continue;
+
+      VNInfo *newVal = li.getNextValue(lis->getMBBStartIdx(preHeader),
+                                       0, false, lis->getVNInfoAllocator());
+      li.addRange(LiveRange(lis->getMBBStartIdx(preHeader),
+                            lis->getMBBEndIdx(preHeader),
+                            newVal));
+    }
+
+
+    //dbgs() << "Dumping SlotIndexes:\n";
+    //sis->dump();
+
+    //dbgs() << "done. (Added MBB#" << preHeader->getNumber() << ")\n";
+
+    return *preHeader;
+  }
+
+  bool LoopSplitter::isCriticalEdge(MachineLoop::Edge &edge) {
+    assert(edge.first->succ_size() > 1 && "Non-sensical edge.");
+    if (edge.second->pred_size() > 1)
+      return true;
+    return false;
+  }
+
+  bool LoopSplitter::canSplitEdge(MachineLoop::Edge &edge) {
+    MachineFunction::iterator outBlockItr(edge.second);
+    if (outBlockItr == mf->begin())
+      return true;
+    MachineBasicBlock *outBlockLayoutPred = llvm::prior(outBlockItr);
+    assert(outBlockLayoutPred != 0 && "Should have a layout pred if out!=begin.");
+    MachineBasicBlock *a = 0, *b = 0;
+    SmallVector<MachineOperand, 4> c;
+    return (!tii->AnalyzeBranch(*outBlockLayoutPred, a, b, c) &&
+            !tii->AnalyzeBranch(*edge.first, a, b, c));
+  }
+
+  MachineBasicBlock& LoopSplitter::splitEdge(MachineLoop::Edge &edge,
+                                             MachineLoop &loop) {
+
+    MachineBasicBlock &inBlock = *edge.first;
+    MachineBasicBlock &outBlock = *edge.second;
+
+    assert((inBlock.succ_size() > 1) && (outBlock.pred_size() > 1) &&
+           "Splitting non-critical edge?");
+
+    //dbgs() << fqn << " Splitting edge (MBB#" << inBlock.getNumber()
+    //       << " -> MBB#" << outBlock.getNumber() << ")...";
+
+    MachineBasicBlock *splitBlock =
+      mf->CreateMachineBasicBlock();
+
+    assert(splitBlock != 0 && "Failed to create split block.");
+
+    mf->insert(&outBlock, splitBlock);
+
+    inBlock.ReplaceUsesOfBlockWith(&outBlock, splitBlock);
+    splitBlock->addSuccessor(&outBlock);
+
+    MachineBasicBlock *oldLayoutPred =
+      llvm::prior(MachineFunction::iterator(splitBlock));
+    if (oldLayoutPred != 0) {
+      updateTerminators(*oldLayoutPred);
+    }
+
+    lis->InsertMBBInMaps(splitBlock);
+
+    loopRangeMap.erase(&loop);
+
+    MachineLoop *splitParentLoop = loop.getParentLoop();
+    while (splitParentLoop != 0 &&
+           !splitParentLoop->contains(&outBlock)) {
+      splitParentLoop = splitParentLoop->getParentLoop();
+    }
+
+    if (splitParentLoop != 0) {
+      assert(splitParentLoop->contains(&loop) &&
+             "Split-block parent doesn't contain original loop?");
+      splitParentLoop->addBasicBlockToLoop(splitBlock, mli->getBase());
+      
+      // Invalidate all parent loop ranges.
+      while (splitParentLoop != 0) {
+        loopRangeMap.erase(splitParentLoop);
+        splitParentLoop = splitParentLoop->getParentLoop();
+      }
+    }
+
+
+    for (LiveIntervals::iterator liItr = lis->begin(),
+                                 liEnd = lis->end();
+         liItr != liEnd; ++liItr) {
+      LiveInterval &li = *liItr->second;
+      bool intersects = lis->isLiveOutOfMBB(li, &inBlock) &&
+                       lis->isLiveInToMBB(li, &outBlock);
+      if (lis->isLiveInToMBB(li, splitBlock)) {
+        if (!intersects) {
+          li.removeRange(lis->getMBBStartIdx(splitBlock),
+                         lis->getMBBEndIdx(splitBlock), true);
+        }
+      } else if (intersects) {
+        VNInfo *newVal = li.getNextValue(lis->getMBBStartIdx(splitBlock),
+                                         0, false, lis->getVNInfoAllocator());
+        li.addRange(LiveRange(lis->getMBBStartIdx(splitBlock),
+                              lis->getMBBEndIdx(splitBlock),
+                              newVal));
+      }
+    }
+
+    //dbgs() << "done. (Added MBB#" << splitBlock->getNumber() << ")\n";
+
+    return *splitBlock;
+  }
+
+  LoopSplitter::LoopRanges& LoopSplitter::getLoopRanges(MachineLoop &loop) {
+    typedef std::set<MachineBasicBlock*, StartSlotComparator> LoopMBBSet;
+    LoopRangeMap::iterator lrItr = loopRangeMap.find(&loop);
+    if (lrItr == loopRangeMap.end()) {
+      LoopMBBSet loopMBBs((StartSlotComparator(*lis))); 
+      std::copy(loop.block_begin(), loop.block_end(),
+                std::inserter(loopMBBs, loopMBBs.begin()));
+
+      assert(!loopMBBs.empty() && "No blocks in loop?");
+
+      LoopRanges &loopRanges = loopRangeMap[&loop];
+      assert(loopRanges.empty() && "Loop encountered but not processed?");
+      SlotIndex oldEnd = lis->getMBBEndIdx(*loopMBBs.begin());
+      loopRanges.push_back(
+        std::make_pair(lis->getMBBStartIdx(*loopMBBs.begin()),
+                       lis->getInvalidIndex()));
+      for (LoopMBBSet::iterator curBlockItr = llvm::next(loopMBBs.begin()),
+                                curBlockEnd = loopMBBs.end();
+           curBlockItr != curBlockEnd; ++curBlockItr) {
+        SlotIndex newStart = lis->getMBBStartIdx(*curBlockItr);
+        if (newStart != oldEnd) {
+          loopRanges.back().second = oldEnd;
+          loopRanges.push_back(std::make_pair(newStart,
+                                              lis->getInvalidIndex()));
+        }
+        oldEnd = lis->getMBBEndIdx(*curBlockItr);
+      }
+
+      loopRanges.back().second =
+        lis->getMBBEndIdx(*llvm::prior(loopMBBs.end()));
+
+      return loopRanges;
+    }
+    return lrItr->second;
+  }
+
+  std::pair<bool, LoopSplitter::SlotPair> LoopSplitter::getLoopSubRange(
+                                                           const LiveRange &lr,
+                                                           MachineLoop &loop) {
+    LoopRanges &loopRanges = getLoopRanges(loop);
+    LoopRanges::iterator lrItr = loopRanges.begin(),
+                         lrEnd = loopRanges.end();
+    while (lrItr != lrEnd && lr.start >= lrItr->second) {
+      ++lrItr;
+    }
+
+    if (lrItr == lrEnd) {
+      SlotIndex invalid = lis->getInvalidIndex();
+      return std::make_pair(false, SlotPair(invalid, invalid));
+    }
+
+    SlotIndex srStart(lr.start < lrItr->first ? lrItr->first : lr.start);
+    SlotIndex srEnd(lr.end > lrItr->second ? lrItr->second : lr.end);
+
+    return std::make_pair(true, SlotPair(srStart, srEnd));      
+  }
+
+  void LoopSplitter::dumpLoopRanges(MachineLoop &loop) {
+    LoopRanges &loopRanges = getLoopRanges(loop);
+    dbgs() << "For loop MBB#" << loop.getHeader()->getNumber() << ", subranges are: [ ";
+    for (LoopRanges::iterator lrItr = loopRanges.begin(), lrEnd = loopRanges.end();
+         lrItr != lrEnd; ++lrItr) {
+      dbgs() << "[" << lrItr->first << ", " << lrItr->second << ") ";
+    }
+    dbgs() << "]\n";
+  }
+
+  void LoopSplitter::processHeader(LoopSplit &split) {
+    MachineBasicBlock &header = *split.getLoop().getHeader();
+    //dbgs() << "  Processing loop header BB#" << header.getNumber() << "\n";
+
+    if (!lis->isLiveInToMBB(split.getLI(), &header))
+      return; // Not live in, but nothing wrong so far.
+
+    MachineBasicBlock *preHeader = split.getLoop().getLoopPreheader();
+    if (!preHeader) {
+
+      if (!canInsertPreHeader(split.getLoop())) {
+        split.invalidate();
+        return; // Couldn't insert a pre-header. Bail on this interval.
+      }
+
+      for (MachineBasicBlock::pred_iterator predItr = header.pred_begin(),
+                                            predEnd = header.pred_end();
+           predItr != predEnd; ++predItr) {
+        if (lis->isLiveOutOfMBB(split.getLI(), *predItr)) {
+          split.splitIncoming();
+          break;
+        }
+      }
+    } else if (lis->isLiveOutOfMBB(split.getLI(), preHeader)) {
+      split.splitIncoming();
+    }
+  }
+
+  void LoopSplitter::processLoopExits(LoopSplit &split) {
+    typedef SmallVector<MachineLoop::Edge, 8> ExitEdgesList;
+    ExitEdgesList exitEdges;
+    split.getLoop().getExitEdges(exitEdges);
+
+    //dbgs() << "  Processing loop exits:\n";
+
+    for (ExitEdgesList::iterator exitEdgeItr = exitEdges.begin(),
+                                 exitEdgeEnd = exitEdges.end();
+         exitEdgeItr != exitEdgeEnd; ++exitEdgeItr) {
+      MachineLoop::Edge exitEdge = *exitEdgeItr;
+
+      LiveRange *inRange =
+        split.getLI().getLiveRangeContaining(lis->getMBBEndIdx(exitEdge.first).getPrevSlot());
+      LiveRange *outRange =
+        split.getLI().getLiveRangeContaining(lis->getMBBStartIdx(exitEdge.second));
+
+      if (outRange != 0) {
+        if (isCriticalEdge(exitEdge) && !canSplitEdge(exitEdge)) {
+          split.invalidate();
+          return;
+        }
+
+        split.splitOutgoing(exitEdge);
+      }
+    }
+  }
+
+  void LoopSplitter::processLoopUses(LoopSplit &split) {
+    std::set<MachineInstr*> processed;
+
+    for (MachineRegisterInfo::reg_iterator
+           rItr = mri->reg_begin(split.getLI().reg),
+           rEnd = mri->reg_end();
+      rItr != rEnd; ++rItr) {
+      MachineInstr &instr = *rItr;
+      if (split.getLoop().contains(&instr) && processed.count(&instr) == 0) {
+        split.addLoopInstr(&instr);
+        processed.insert(&instr);
+      }
+    }
+
+    //dbgs() << "  Rewriting reg" << li.reg << " to reg" << newLI->reg
+    //       << " in blocks [ ";
+    //dbgs() << "]\n";
+  }
+
+  bool LoopSplitter::splitOverLoop(LiveInterval &li, MachineLoop &loop) {
+    assert(TargetRegisterInfo::isVirtualRegister(li.reg) &&
+           "Attempt to split physical register.");
+
+    LoopSplit split(*this, li, loop);
+    processHeader(split);
+    if (split.isValid())
+      processLoopExits(split);
+    if (split.isValid())
+      processLoopUses(split);
+    if (split.isValid() /* && split.isWorthwhile() */) {
+      split.apply();
+      DEBUG(dbgs() << "Success.\n");
+      return true;
+    }
+    DEBUG(dbgs() << "Failed.\n");
+    return false;
+  }
+
+  void LoopSplitter::processInterval(LiveInterval &li) {
+    std::deque<MachineLoop*> loops;
+    std::copy(mli->begin(), mli->end(), std::back_inserter(loops));
+
+    while (!loops.empty()) {
+      MachineLoop &loop = *loops.front();
+      loops.pop_front();
+      DEBUG(
+        dbgs() << fqn << " reg" << li.reg << " " << li.weight << " BB#"
+               << loop.getHeader()->getNumber() << " ";
+      );
+      if (!splitOverLoop(li, loop)) {
+        // Couldn't split over outer loop, schedule sub-loops to be checked.
+	std::copy(loop.begin(), loop.end(), std::back_inserter(loops));
+      }
+    }
+  }
+
+  void LoopSplitter::processIntervals() {
+    while (!intervals.empty()) {
+      LiveInterval &li = *intervals.front();
+      intervals.pop_front();
+
+      assert(!lis->intervalIsInOneMBB(li) &&
+             "Single interval in process worklist.");
+
+      processInterval(li);      
+    }
+  }
+
+}
diff --git a/lib/CodeGen/Splitter.h b/lib/CodeGen/Splitter.h
new file mode 100644
index 0000000..f253ee7
--- /dev/null
+++ b/lib/CodeGen/Splitter.h
@@ -0,0 +1,99 @@
+//===-- llvm/CodeGen/Splitter.h - Splitter -*- C++ -*----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_SPLITTER_H
+#define LLVM_CODEGEN_SPLITTER_H
+
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/SlotIndexes.h"
+
+#include <deque>
+#include <map>
+#include <string>
+#include <vector>
+
+namespace llvm {
+
+  class LiveInterval;
+  class LiveIntervals;
+  class LiveRange;
+  class LoopSplit;
+  class MachineDominatorTree;
+  class MachineRegisterInfo;
+  class SlotIndexes;
+  class TargetInstrInfo;
+  class VNInfo;
+
+  class LoopSplitter : public MachineFunctionPass {
+    friend class LoopSplit;
+  public:
+    static char ID;
+
+    LoopSplitter() : MachineFunctionPass(&ID) {}
+
+    virtual void getAnalysisUsage(AnalysisUsage &au) const;
+
+    virtual bool runOnMachineFunction(MachineFunction &fn);
+
+    virtual void releaseMemory();
+
+
+  private:
+
+    MachineFunction *mf;
+    LiveIntervals *lis;
+    MachineLoopInfo *mli;
+    MachineRegisterInfo *mri;
+    MachineDominatorTree *mdt;
+    SlotIndexes *sis;
+    const TargetInstrInfo *tii;
+    const TargetRegisterInfo *tri;
+
+    std::string fqn;
+    std::deque<LiveInterval*> intervals;
+
+    typedef std::pair<SlotIndex, SlotIndex> SlotPair;
+    typedef std::vector<SlotPair> LoopRanges;
+    typedef std::map<MachineLoop*, LoopRanges> LoopRangeMap;
+    LoopRangeMap loopRangeMap;
+
+    void dumpLoopInfo(MachineLoop &loop);
+
+    void dumpOddTerminators();
+
+    void updateTerminators(MachineBasicBlock &mbb);
+
+    bool canInsertPreHeader(MachineLoop &loop);
+    MachineBasicBlock& insertPreHeader(MachineLoop &loop);
+
+    bool isCriticalEdge(MachineLoop::Edge &edge);
+    bool canSplitEdge(MachineLoop::Edge &edge);
+    MachineBasicBlock& splitEdge(MachineLoop::Edge &edge, MachineLoop &loop);
+
+    LoopRanges& getLoopRanges(MachineLoop &loop);
+    std::pair<bool, SlotPair> getLoopSubRange(const LiveRange &lr,
+                                              MachineLoop &loop);
+
+    void dumpLoopRanges(MachineLoop &loop);
+
+    void processHeader(LoopSplit &split);
+    void processLoopExits(LoopSplit &split);
+    void processLoopUses(LoopSplit &split);
+
+    bool splitOverLoop(LiveInterval &li, MachineLoop &loop);
+
+    void processInterval(LiveInterval &li);
+
+    void processIntervals();
+  };
+
+}
+
+#endif