2 files changed, 47 insertions, 0 deletions

diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index bf0a8295d5..c9f9d2dcc2 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -36,6 +36,7 @@ namespace llvm {
   class TargetInstrInfo;
   class TargetRegisterClass;
   class VirtRegMap;
+  typedef std::pair<unsigned, MachineBasicBlock*> IdxMBBPair;
 
   class LiveIntervals : public MachineFunctionPass {
     MachineFunction* mf_;
@@ -52,6 +53,10 @@ namespace llvm {
     /// specified basic block.
     std::vector<std::pair<unsigned, unsigned> > MBB2IdxMap;
 
+    /// Idx2MBBMap - Sorted list of pairs of index of first instruction
+    /// and MBB id.
+    std::vector<IdxMBBPair> Idx2MBBMap;
+
     typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
     Mi2IndexMap mi2iMap_;
 
@@ -158,6 +163,12 @@ namespace llvm {
       return i2miMap_[index];
     }
 
+    /// findLiveInMBBs - Given a live range, if the value of the range
+    /// is live in any MBB returns true as well as the list of basic blocks
+    /// where the value is live in.
+    bool findLiveInMBBs(const LiveRange &LR,
+                        SmallVector<MachineBasicBlock*, 4> &MBBs) const;
+
     // Interval creation
 
     LiveInterval &getOrCreateInterval(unsigned reg) {
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index c574bef4a6..3aec772f1a 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -62,6 +62,7 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
 }
 
 void LiveIntervals::releaseMemory() {
+  Idx2MBBMap.clear();
   mi2iMap_.clear();
   i2miMap_.clear();
   r2iMap_.clear();
@@ -71,6 +72,22 @@ void LiveIntervals::releaseMemory() {
     delete ClonedMIs[i];
 }
 
+namespace llvm {
+  inline bool operator<(unsigned V, const IdxMBBPair &IM) {
+    return V < IM.first;
+  }
+
+  inline bool operator<(const IdxMBBPair &IM, unsigned V) {
+    return IM.first < V;
+  }
+
+  struct Idx2MBBCompare {
+    bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
+      return LHS.first < RHS.first;
+    }
+  };
+}
+
 /// runOnMachineFunction - Register allocate the whole function
 ///
 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
@@ -100,7 +117,9 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
 
     // Set the MBB2IdxMap entry for this MBB.
     MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
+    Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
   }
+  std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
 
   computeIntervals();
 
@@ -797,6 +816,23 @@ void LiveIntervals::computeIntervals() {
   }
 }
 
+bool LiveIntervals::findLiveInMBBs(const LiveRange &LR,
+                               SmallVector<MachineBasicBlock*, 4> &MBBs) const {
+  std::vector<IdxMBBPair>::const_iterator I =
+    std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start);
+
+  bool ResVal = false;
+  while (I != Idx2MBBMap.end()) {
+    if (LR.end <= I->first)
+      break;
+    MBBs.push_back(I->second);
+    ResVal = true;
+    ++I;
+  }
+  return ResVal;
+}
+
+
 LiveInterval LiveIntervals::createInterval(unsigned reg) {
   float Weight = MRegisterInfo::isPhysicalRegister(reg) ?
                        HUGE_VALF : 0.0F;