Improved tracking of value number kills. VN kills are now represented

as an (index,bool) pair. The bool flag records whether the kill is a
PHI kill or not. This code will be used to enable splitting of live
intervals containing PHI-kills.

A slight change to live interval weights introduced an extra spill
into lsr-code-insertion (outside the critical sections). The test 
condition has been updated to reflect this.



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

9 files changed, 164 insertions, 66 deletions

diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
index 0cb7e90043..6977baedb9 100644
--- a/include/llvm/CodeGen/LiveInterval.h
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -62,13 +62,28 @@ namespace llvm {
     unsigned char flags;
 
   public:
+    /// Holds information about individual kills.
+    struct KillInfo {
+      bool isPHIKill : 1;
+      unsigned killIdx : 31;
+
+      KillInfo(bool isPHIKill, unsigned killIdx)
+        : isPHIKill(isPHIKill), killIdx(killIdx) {
+
+        assert(killIdx != 0 && "Zero kill indices are no longer permitted.");
+      }
+
+    };
+
+    typedef SmallVector<KillInfo, 4> KillSet;
+
     /// The ID number of this value.
     unsigned id;
     
     /// The index of the defining instruction (if isDefAccurate() returns true).
     unsigned def;
     MachineInstr *copy;
-    SmallVector<unsigned, 4> kills;
+    KillSet kills;
 
     VNInfo()
       : flags(IS_UNUSED), id(~1U), def(0), copy(0) {}
@@ -137,6 +152,18 @@ namespace llvm {
 
   };
 
+  inline bool operator<(const VNInfo::KillInfo &k1, const VNInfo::KillInfo &k2) {
+    return k1.killIdx < k2.killIdx;
+  }
+  
+  inline bool operator<(const VNInfo::KillInfo &k, unsigned idx) {
+    return k.killIdx < idx;
+  }
+
+  inline bool operator<(unsigned idx, const VNInfo::KillInfo &k) {
+    return idx < k.killIdx;
+  }
+
   /// LiveRange structure - This represents a simple register range in the
   /// program, with an inclusive start point and an exclusive end point.
   /// These ranges are rendered as [start,end).
@@ -339,27 +366,28 @@ namespace llvm {
 
     /// addKill - Add a kill instruction index to the specified value
     /// number.
-    static void addKill(VNInfo *VNI, unsigned KillIdx) {
-      SmallVector<unsigned, 4> &kills = VNI->kills;
+    static void addKill(VNInfo *VNI, unsigned KillIdx, bool phiKill) {
+      VNInfo::KillSet &kills = VNI->kills;
+      VNInfo::KillInfo newKill(phiKill, KillIdx);
       if (kills.empty()) {
-        kills.push_back(KillIdx);
+        kills.push_back(newKill);
       } else {
-        SmallVector<unsigned, 4>::iterator
-          I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
-        kills.insert(I, KillIdx);
+        VNInfo::KillSet::iterator
+          I = std::lower_bound(kills.begin(), kills.end(), newKill);
+        kills.insert(I, newKill);
       }
     }
 
     /// addKills - Add a number of kills into the VNInfo kill vector. If this
     /// interval is live at a kill point, then the kill is not added.
-    void addKills(VNInfo *VNI, const SmallVector<unsigned, 4> &kills) {
+    void addKills(VNInfo *VNI, const VNInfo::KillSet &kills) {
       for (unsigned i = 0, e = static_cast<unsigned>(kills.size());
            i != e; ++i) {
-        unsigned KillIdx = kills[i];
-        if (!liveBeforeAndAt(KillIdx)) {
-          SmallVector<unsigned, 4>::iterator
-            I = std::lower_bound(VNI->kills.begin(), VNI->kills.end(), KillIdx);
-          VNI->kills.insert(I, KillIdx);
+        const VNInfo::KillInfo &Kill = kills[i];
+        if (!liveBeforeAndAt(Kill.killIdx)) {
+          VNInfo::KillSet::iterator
+            I = std::lower_bound(VNI->kills.begin(), VNI->kills.end(), Kill);
+          VNI->kills.insert(I, Kill);
         }
       }
     }
@@ -367,10 +395,10 @@ namespace llvm {
     /// removeKill - Remove the specified kill from the list of kills of
     /// the specified val#.
     static bool removeKill(VNInfo *VNI, unsigned KillIdx) {
-      SmallVector<unsigned, 4> &kills = VNI->kills;
-      SmallVector<unsigned, 4>::iterator
+      VNInfo::KillSet &kills = VNI->kills;
+      VNInfo::KillSet::iterator
         I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
-      if (I != kills.end() && *I == KillIdx) {
+      if (I != kills.end() && I->killIdx == KillIdx) {
         kills.erase(I);
         return true;
       }
@@ -380,10 +408,11 @@ namespace llvm {
     /// removeKills - Remove all the kills in specified range
     /// [Start, End] of the specified val#.
     static void removeKills(VNInfo *VNI, unsigned Start, unsigned End) {
-      SmallVector<unsigned, 4> &kills = VNI->kills;
-      SmallVector<unsigned, 4>::iterator
+      VNInfo::KillSet &kills = VNI->kills;
+
+      VNInfo::KillSet::iterator
         I = std::lower_bound(kills.begin(), kills.end(), Start);
-      SmallVector<unsigned, 4>::iterator
+      VNInfo::KillSet::iterator
         E = std::upper_bound(kills.begin(), kills.end(), End);
       kills.erase(I, E);
     }
@@ -391,15 +420,15 @@ namespace llvm {
     /// isKill - Return true if the specified index is a kill of the
     /// specified val#.
     static bool isKill(const VNInfo *VNI, unsigned KillIdx) {
-      const SmallVector<unsigned, 4> &kills = VNI->kills;
-      SmallVector<unsigned, 4>::const_iterator
+      const VNInfo::KillSet &kills = VNI->kills;
+      VNInfo::KillSet::const_iterator
         I = std::lower_bound(kills.begin(), kills.end(), KillIdx);
-      return I != kills.end() && *I == KillIdx;
+      return I != kills.end() && I->killIdx == KillIdx;
     }
 
     /// isOnlyLROfValNo - Return true if the specified live range is the only
     /// one defined by the its val#.
-    bool isOnlyLROfValNo( const LiveRange *LR) {
+    bool isOnlyLROfValNo(const LiveRange *LR) {
       for (const_iterator I = begin(), E = end(); I != E; ++I) {
         const LiveRange *Tmp = I;
         if (Tmp != LR && Tmp->valno == LR->valno)
@@ -481,6 +510,13 @@ namespace llvm {
       return I == end() ? 0 : &*I;
     }
 
+    /// getLiveRangeContaining - Return the live range that contains the
+    /// specified index, or null if there is none.
+    LiveRange *getLiveRangeContaining(unsigned Idx) {
+      iterator I = FindLiveRangeContaining(Idx);
+      return I == end() ? 0 : &*I;
+    }
+
     /// FindLiveRangeContaining - Return an iterator to the live range that
     /// contains the specified index, or end() if there is none.
     const_iterator FindLiveRangeContaining(unsigned Idx) const;
diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index 7ae98bb093..40991e74e3 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -88,6 +88,8 @@ namespace llvm {
     typedef DenseMap<unsigned, LiveInterval*> Reg2IntervalMap;
     Reg2IntervalMap r2iMap_;
 
+    DenseMap<MachineBasicBlock*, unsigned> terminatorGaps;
+
     BitVector allocatableRegs_;
 
     std::vector<MachineInstr*> ClonedMIs;
diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 26722a3ca1..b786b1d85b 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -377,8 +377,9 @@ void LiveInterval::scaleNumbering(unsigned factor) {
       vni->def = InstrSlots::scale(vni->def, factor);
 
     for (unsigned i = 0; i < vni->kills.size(); ++i) {
-      if (vni->kills[i] != 0)
-        vni->kills[i] = InstrSlots::scale(vni->kills[i], factor);
+      if (!vni->kills[i].isPHIKill)
+        vni->kills[i].killIdx =
+          InstrSlots::scale(vni->kills[i].killIdx, factor);
     }
   }
 }
@@ -840,7 +841,9 @@ void LiveInterval::print(std::ostream &OS,
         if (ee || vni->hasPHIKill()) {
           OS << "-(";
           for (unsigned j = 0; j != ee; ++j) {
-            OS << vni->kills[j];
+            OS << vni->kills[j].killIdx;
+            if (vni->kills[j].isPHIKill)
+              OS << "*";
             if (j != ee-1)
               OS << " ";
           }
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 52a30bc067..27ab5d5357 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -92,6 +92,8 @@ void LiveIntervals::releaseMemory() {
   mi2iMap_.clear();
   i2miMap_.clear();
   r2iMap_.clear();
+  terminatorGaps.clear();
+
   // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
   VNInfoAllocator.Reset();
   while (!ClonedMIs.empty()) {
@@ -223,6 +225,7 @@ void LiveIntervals::computeNumbering() {
   MBB2IdxMap.clear();
   mi2iMap_.clear();
   i2miMap_.clear();
+  terminatorGaps.clear();
   
   FunctionSize = 0;
   
@@ -241,6 +244,19 @@ void LiveIntervals::computeNumbering() {
 
     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
          I != E; ++I) {
+      
+      if (I == MBB->getFirstTerminator()) {
+        // Leave a gap for before terminators, this is where we will point
+        // PHI kills.
+        bool inserted =
+          terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second;
+        assert(inserted && 
+               "Multiple 'first' terminators encountered during numbering.");
+        i2miMap_.push_back(0);
+
+        MIIndex += InstrSlots::NUM;
+      }
+
       bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
       assert(inserted && "multiple MachineInstr -> index mappings");
       inserted = true;
@@ -256,11 +272,24 @@ void LiveIntervals::computeNumbering() {
       while (Slots--)
         i2miMap_.push_back(0);
     }
+  
+    if (MBB->getFirstTerminator() == MBB->end()) {
+      // Leave a gap for before terminators, this is where we will point
+      // PHI kills.
+      bool inserted =
+        terminatorGaps.insert(std::make_pair(&*MBB, MIIndex)).second;
+      assert(inserted && 
+             "Multiple 'first' terminators encountered during numbering.");
+      i2miMap_.push_back(0);
+ 
+      MIIndex += InstrSlots::NUM;
+    }
     
     // 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());
   
   if (!OldI2MI.empty())
@@ -335,18 +364,31 @@ void LiveIntervals::computeNumbering() {
         // Remap the VNInfo kill indices, which works the same as
         // the end indices above.
         for (size_t i = 0; i < vni->kills.size(); ++i) {
-          // PHI kills don't need to be remapped.
-          if (!vni->kills[i]) continue;
-          
-          unsigned index = (vni->kills[i]-1) / InstrSlots::NUM;
-          unsigned offset = vni->kills[i] % InstrSlots::NUM;
+          unsigned killIdx = vni->kills[i].killIdx;
+
+          unsigned index = (killIdx - 1) / InstrSlots::NUM;
+          unsigned offset = killIdx % InstrSlots::NUM;
+
           if (offset == InstrSlots::LOAD) {
-            std::vector<IdxMBBPair>::const_iterator I =
+            assert("Value killed at a load slot.");
+            /*std::vector<IdxMBBPair>::const_iterator I =
              std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]);
             --I;
 
-            vni->kills[i] = getMBBEndIdx(I->second);
+            vni->kills[i] = getMBBEndIdx(I->second);*/
           } else {
+            if (vni->kills[i].isPHIKill) {
+              std::vector<IdxMBBPair>::const_iterator I =
+                std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), index);
+              --I;
+              vni->kills[i].killIdx = terminatorGaps[I->second];  
+            } else {
+              assert(OldI2MI[index] != 0 &&
+                     "Kill refers to instruction not present in index maps.");
+              vni->kills[i].killIdx = mi2iMap_[OldI2MI[index]] + offset;
+            }
+           
+            /*
             unsigned idx = index;
             while (index < OldI2MI.size() && !OldI2MI[index]) ++index;
             
@@ -355,6 +397,7 @@ void LiveIntervals::computeNumbering() {
                               (idx == index ? offset : 0);
             else
               vni->kills[i] = InstrSlots::NUM * i2miMap_.size();
+            */
           }
         }
       }
@@ -379,6 +422,13 @@ void LiveIntervals::scaleNumbering(int factor) {
   }
   std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
 
+  // Scale terminator gaps.
+  for (DenseMap<MachineBasicBlock*, unsigned>::iterator
+       TGI = terminatorGaps.begin(), TGE = terminatorGaps.end();
+       TGI != TGE; ++TGI) {
+    terminatorGaps[TGI->first] = InstrSlots::scale(TGI->second, factor);
+  }
+
   // Scale the intervals.
   for (iterator LI = begin(), LE = end(); LI != LE; ++LI) {
     LI->second->scaleNumbering(factor);
@@ -589,7 +639,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
         LiveRange LR(defIndex, killIdx, ValNo);
         interval.addRange(LR);
         DOUT << " +" << LR << "\n";
-        interval.addKill(ValNo, killIdx);
+        interval.addKill(ValNo, killIdx, false);
         return;
       }
     }
@@ -622,7 +672,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
       LiveRange LR(getMBBStartIdx(Kill->getParent()),
                    killIdx, ValNo);
       interval.addRange(LR);
-      interval.addKill(ValNo, killIdx);
+      interval.addKill(ValNo, killIdx, false);
       DOUT << " +" << LR;
     }
 
@@ -671,7 +721,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
       LiveRange LR(DefIndex, RedefIndex, ValNo);
       DOUT << " replace range with " << LR;
       interval.addRange(LR);
-      interval.addKill(ValNo, RedefIndex);
+      interval.addKill(ValNo, RedefIndex, false);
 
       // If this redefinition is dead, we need to add a dummy unit live
       // range covering the def slot.
@@ -696,7 +746,11 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
         unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
         DOUT << " Removing [" << Start << "," << End << "] from: ";
         interval.print(DOUT, tri_); DOUT << "\n";
-        interval.removeRange(Start, End);
+        interval.removeRange(Start, End);        
+        assert(interval.ranges.size() == 1 &&
+               "newly discovered PHI interval has >1 ranges.");
+        MachineBasicBlock *killMBB = getMBBFromIndex(interval.endNumber());
+        interval.addKill(VNI, terminatorGaps[killMBB], true);        
         VNI->setHasPHIKill(true);
         DOUT << " RESULT: "; interval.print(DOUT, tri_);
 
@@ -707,7 +761,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
         LR.valno->setIsPHIDef(true);
         DOUT << " replace range with " << LR;
         interval.addRange(LR);
-        interval.addKill(LR.valno, End);
+        interval.addKill(LR.valno, End, false);
         DOUT << " RESULT: "; interval.print(DOUT, tri_);
       }
 
@@ -731,7 +785,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
       unsigned killIndex = getMBBEndIdx(mbb) + 1;
       LiveRange LR(defIndex, killIndex, ValNo);
       interval.addRange(LR);
-      interval.addKill(ValNo, killIndex);
+      interval.addKill(ValNo, terminatorGaps[mbb], true);
       ValNo->setHasPHIKill(true);
       DOUT << " +" << LR;
     }
@@ -819,7 +873,7 @@ exit:
     ValNo->setHasRedefByEC(true);
   LiveRange LR(start, end, ValNo);
   interval.addRange(LR);
-  interval.addKill(LR.valno, end);
+  interval.addKill(LR.valno, end, false);
   DOUT << " +" << LR << '\n';
 }
 
@@ -910,7 +964,7 @@ void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
   LiveRange LR(start, end, vni);
   
   interval.addRange(LR);
-  interval.addKill(LR.valno, end);
+  interval.addKill(LR.valno, end, false);
   DOUT << " +" << LR << '\n';
 }
 
@@ -1608,7 +1662,10 @@ bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
                                    MachineBasicBlock *MBB, unsigned Idx) const {
   unsigned End = getMBBEndIdx(MBB);
   for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
-    unsigned KillIdx = VNI->kills[j];
+    if (VNI->kills[j].isPHIKill)
+      continue;
+
+    unsigned KillIdx = VNI->kills[j].killIdx;
     if (KillIdx > Idx && KillIdx < End)
       return true;
   }
@@ -2412,13 +2469,14 @@ bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
 }
 
 LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
-                                                   MachineInstr* startInst) {
+                                                  MachineInstr* startInst) {
   LiveInterval& Interval = getOrCreateInterval(reg);
   VNInfo* VN = Interval.getNextValue(
             getInstructionIndex(startInst) + InstrSlots::DEF,
             startInst, true, getVNInfoAllocator());
   VN->setHasPHIKill(true);
-  VN->kills.push_back(getMBBEndIdx(startInst->getParent()));
+  VN->kills.push_back(
+    VNInfo::KillInfo(terminatorGaps[startInst->getParent()], true));
   LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF,
                getMBBEndIdx(startInst->getParent()) + 1, VN);
   Interval.addRange(LR);
diff --git a/lib/CodeGen/PreAllocSplitting.cpp b/lib/CodeGen/PreAllocSplitting.cpp
index ae60c86c3d..076f4896cf 100644
--- a/lib/CodeGen/PreAllocSplitting.cpp
+++ b/lib/CodeGen/PreAllocSplitting.cpp
@@ -543,7 +543,7 @@ PreAllocSplitting::PerformPHIConstruction(MachineBasicBlock::iterator UseI,
     // FIXME: Need to set kills properly for inter-block stuff.
     if (LI->isKill(RetVNI, UseIndex)) LI->removeKill(RetVNI, UseIndex);
     if (IsIntraBlock)
-      LI->addKill(RetVNI, EndIndex);
+      LI->addKill(RetVNI, EndIndex, false);
   } else if (ContainsDefs && ContainsUses) {
     SmallPtrSet<MachineInstr*, 2>& BlockDefs = Defs[MBB];
     SmallPtrSet<MachineInstr*, 2>& BlockUses = Uses[MBB];
@@ -605,7 +605,7 @@ PreAllocSplitting::PerformPHIConstruction(MachineBasicBlock::iterator UseI,
     if (foundUse && LI->isKill(RetVNI, StartIndex))
       LI->removeKill(RetVNI, StartIndex);
     if (IsIntraBlock) {
-      LI->addKill(RetVNI, EndIndex);
+      LI->addKill(RetVNI, EndIndex, false);
     }
   }
   
@@ -682,7 +682,7 @@ PreAllocSplitting::PerformPHIConstructionFallBack(MachineBasicBlock::iterator Us
       I->second->setHasPHIKill(true);
       unsigned KillIndex = LIs->getMBBEndIdx(I->first);
       if (!LiveInterval::isKill(I->second, KillIndex))
-        LI->addKill(I->second, KillIndex);
+        LI->addKill(I->second, KillIndex, false);
     }
   }
       
@@ -694,7 +694,7 @@ PreAllocSplitting::PerformPHIConstructionFallBack(MachineBasicBlock::iterator Us
     EndIndex = LIs->getMBBEndIdx(MBB);
   LI->addRange(LiveRange(StartIndex, EndIndex+1, RetVNI));
   if (IsIntraBlock)
-    LI->addKill(RetVNI, EndIndex);
+    LI->addKill(RetVNI, EndIndex, false);
 
   // Memoize results so we don't have to recompute them.
   if (!IsIntraBlock)
@@ -771,7 +771,7 @@ void PreAllocSplitting::ReconstructLiveInterval(LiveInterval* LI) {
     
     VNInfo* DeadVN = NewVNs[&*DI];
     LI->addRange(LiveRange(DefIdx, DefIdx+1, DeadVN));
-    LI->addKill(DeadVN, DefIdx);
+    LI->addKill(DeadVN, DefIdx, false);
   }
 }
 
@@ -801,14 +801,15 @@ void PreAllocSplitting::RenumberValno(VNInfo* VN) {
     VNsToCopy.push_back(OldVN);
     
     // Locate two-address redefinitions
-    for (SmallVector<unsigned, 4>::iterator KI = OldVN->kills.begin(),
+    for (VNInfo::KillSet::iterator KI = OldVN->kills.begin(),
          KE = OldVN->kills.end(); KI != KE; ++KI) {
-      MachineInstr* MI = LIs->getInstructionFromIndex(*KI);
+      assert(!KI->isPHIKill && "VN previously reported having no PHI kills.");
+      MachineInstr* MI = LIs->getInstructionFromIndex(KI->killIdx);
       unsigned DefIdx = MI->findRegisterDefOperandIdx(CurrLI->reg);
       if (DefIdx == ~0U) continue;
       if (MI->isRegTiedToUseOperand(DefIdx)) {
         VNInfo* NextVN =
-                     CurrLI->findDefinedVNInfo(LiveIntervals::getDefIndex(*KI));
+          CurrLI->findDefinedVNInfo(LiveIntervals::getDefIndex(KI->killIdx));
         if (NextVN == OldVN) continue;
         Stack.push_back(NextVN);
       }
diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp
index 7e7d6b8f68..48e6d45713 100644
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -356,7 +356,7 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
 
   bool BHasPHIKill = BValNo->hasPHIKill();
   SmallVector<VNInfo*, 4> BDeadValNos;
-  SmallVector<unsigned, 4> BKills;
+  VNInfo::KillSet BKills;
   std::map<unsigned, unsigned> BExtend;
 
   // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.
@@ -395,7 +395,7 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
       if (Extended)
         UseMO.setIsKill(false);
       else
-        BKills.push_back(li_->getUseIndex(UseIdx)+1);
+        BKills.push_back(VNInfo::KillInfo(false, li_->getUseIndex(UseIdx)+1));
     }
     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
     if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
@@ -441,9 +441,9 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
   ValNo->def = AValNo->def;
   ValNo->copy = NULL;
   for (unsigned j = 0, ee = ValNo->kills.size(); j != ee; ++j) {
-    unsigned Kill = ValNo->kills[j];
+    unsigned Kill = ValNo->kills[j].killIdx;
     if (Kill != BLR->end)
-      BKills.push_back(Kill);
+      BKills.push_back(VNInfo::KillInfo(ValNo->kills[j].isPHIKill, Kill));
   }
   ValNo->kills.clear();
   for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
@@ -547,7 +547,7 @@ SimpleRegisterCoalescing::TrimLiveIntervalToLastUse(unsigned CopyIdx,
     // of last use.
     LastUse->setIsKill();
     removeRange(li, li_->getDefIndex(LastUseIdx), LR->end, li_, tri_);
-    li.addKill(LR->valno, LastUseIdx+1);
+    li.addKill(LR->valno, LastUseIdx+1, false);
     unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
     if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
         DstReg == li.reg) {
@@ -674,9 +674,7 @@ bool SimpleRegisterCoalescing::isBackEdgeCopy(MachineInstr *CopyMI,
     LI.FindLiveRangeContaining(li_->getDefIndex(DefIdx));
   if (DstLR == LI.end())
     return false;
-  unsigned KillIdx = li_->getMBBEndIdx(MBB) + 1;
-  if (DstLR->valno->kills.size() == 1 &&
-      DstLR->valno->kills[0] == KillIdx && DstLR->valno->hasPHIKill())
+  if (DstLR->valno->kills.size() == 1 && DstLR->valno->kills[0].isPHIKill)
     return true;
   return false;
 }
@@ -1019,7 +1017,7 @@ void SimpleRegisterCoalescing::TurnCopiesFromValNoToImpDefs(LiveInterval &li,
   }
   if (LastUse) {
     LastUse->setIsKill();
-    li.addKill(VNI, LastUseIdx+1);
+    li.addKill(VNI, LastUseIdx+1, false);
   } else {
     // Remove dead implicit_def's.
     while (!ImpDefs.empty()) {
diff --git a/lib/CodeGen/Spiller.cpp b/lib/CodeGen/Spiller.cpp
index 405cd8087a..faaee0a8d6 100644
--- a/lib/CodeGen/Spiller.cpp
+++ b/lib/CodeGen/Spiller.cpp
@@ -136,7 +136,7 @@ protected:
 
     VNInfo *vni =
       li->getNextValue(storeInstIdx, 0, true, lis->getVNInfoAllocator());
-    vni->kills.push_back(storeInstIdx);
+    li->addKill(vni, storeInstIdx, false);
     DOUT << "    Inserting store range: [" << start << ", " << end << ")\n";
     LiveRange lr(start, end, vni);
       
@@ -201,7 +201,7 @@ protected:
 
     VNInfo *vni =
       li->getNextValue(loadInstIdx, 0, true, lis->getVNInfoAllocator());
-    vni->kills.push_back(lis->getInstructionIndex(mi));
+    li->addKill(vni, lis->getInstructionIndex(mi), false);
     DOUT << "    Intserting load range: [" << start << ", " << end << ")\n";
     LiveRange lr(start, end, vni);
 
diff --git a/lib/CodeGen/StrongPHIElimination.cpp b/lib/CodeGen/StrongPHIElimination.cpp
index ca9952863b..efd19fa999 100644
--- a/lib/CodeGen/StrongPHIElimination.cpp
+++ b/lib/CodeGen/StrongPHIElimination.cpp
@@ -829,8 +829,8 @@ void StrongPHIElimination::InsertCopies(MachineDomTreeNode* MDTN,
         VNInfo* FirstVN = *Int.vni_begin();
         FirstVN->setHasPHIKill(false);
         if (I->getOperand(i).isKill())
-          FirstVN->kills.push_back(
-                         LiveIntervals::getUseIndex(LI.getInstructionIndex(I)));
+          Int.addKill(FirstVN,
+                 LiveIntervals::getUseIndex(LI.getInstructionIndex(I)), false);
         
         LiveRange LR (LI.getMBBStartIdx(I->getParent()),
                       LiveIntervals::getUseIndex(LI.getInstructionIndex(I))+1,
diff --git a/test/CodeGen/ARM/lsr-code-insertion.ll b/test/CodeGen/ARM/lsr-code-insertion.ll
index 3881e91453..0a9227982d 100644
--- a/test/CodeGen/ARM/lsr-code-insertion.ll
+++ b/test/CodeGen/ARM/lsr-code-insertion.ll
@@ -1,4 +1,4 @@
-; RUN: llvm-as < %s | llc -stats |& grep {39.*Number of machine instrs printed}
+; RUN: llvm-as < %s | llc -stats |& grep {40.*Number of machine instrs printed}
 ; RUN: llvm-as < %s | llc -stats |& grep {.*Number of re-materialization}
 ; This test really wants to check that the resultant "cond_true" block only 
 ; has a single store in it, and that cond_true55 only has code to materialize