Code to maintain kill information during register coalescing.

llvm-svn: 41016

3 files changed, 82 insertions, 29 deletions

diff --git a/llvm/lib/CodeGen/LiveInterval.cpp b/llvm/lib/CodeGen/LiveInterval.cpp
index 32399ef2fc7..2c22976559d 100644
--- a/llvm/lib/CodeGen/LiveInterval.cpp
+++ b/llvm/lib/CodeGen/LiveInterval.cpp
@@ -121,7 +121,10 @@ void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) {
 
   // Erase any dead ranges.
   ranges.erase(next(I), MergeTo);
-  
+
+  // Update kill info.
+  removeKillForValNum(ValId, I->start, I->end-1);
+
   // If the newly formed range now touches the range after it and if they have
   // the same value number, merge the two ranges into one range.
   Ranges::iterator Next = next(I);
@@ -228,9 +231,10 @@ void LiveInterval::removeRange(unsigned Start, unsigned End) {
 
   // If the span we are removing is at the start of the LiveRange, adjust it.
   if (I->start == Start) {
-    if (I->end == End)
+    if (I->end == End) {
+      removeKillForValNum(I->ValId, End);
       ranges.erase(I);  // Removed the whole LiveRange.
-    else
+    } else
       I->start = End;
     return;
   }
@@ -238,6 +242,7 @@ void LiveInterval::removeRange(unsigned Start, unsigned End) {
   // Otherwise if the span we are removing is at the end of the LiveRange,
   // adjust the other way.
   if (I->end == End) {
+    replaceKillForValNum(I->ValId, End, Start);
     I->end = Start;
     return;
   }
@@ -336,7 +341,11 @@ void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments,
     // If we merge some live ranges, chop off the end.
     ranges.erase(OutIt, end());
   }
-  
+
+  // Update val# info first. Increasing live ranges may invalidate some kills.
+  ValueNumberInfo.clear();
+  ValueNumberInfo.append(NewValueNumberInfo.begin(), NewValueNumberInfo.end());
+
   // Okay, now insert the RHS live ranges into the LHS.
   iterator InsertPos = begin();
   for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) {
@@ -345,8 +354,6 @@ void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments,
     InsertPos = addRangeFrom(*I, InsertPos);
   }
 
-  ValueNumberInfo.clear();
-  ValueNumberInfo.append(NewValueNumberInfo.begin(), NewValueNumberInfo.end());
   weight += Other.weight;
   if (Other.preference && !preference)
     preference = Other.preference;
@@ -417,7 +424,7 @@ void LiveInterval::MergeValueNumberInto(unsigned V1, unsigned V2) {
 
   // Make sure V2 is smaller than V1.
   if (V1 < V2) {
-    setValueNumberInfo(V1, getValNumInfo(V2));
+    copyValNumInfo(V1, V2);
     std::swap(V1, V2);
   }
 
@@ -431,6 +438,8 @@ void LiveInterval::MergeValueNumberInto(unsigned V1, unsigned V2) {
     if (LR != begin()) {
       iterator Prev = LR-1;
       if (Prev->ValId == V2 && Prev->end == LR->start) {
+        bool Replaced = replaceKillForValNum(V2, Prev->end, LR->end);
+        assert(Replaced);
         Prev->end = LR->end;
 
         // Erase this live-range.
@@ -449,6 +458,7 @@ void LiveInterval::MergeValueNumberInto(unsigned V1, unsigned V2) {
     // of the loop.
     if (I != end()) {
       if (I->start == LR->end && I->ValId == V2) {
+        removeKillForValNum(V2, LR->end);
         LR->end = I->end;
         ranges.erase(I);
         I = LR+1;
@@ -506,12 +516,23 @@ void LiveInterval::print(std::ostream &OS, const MRegisterInfo *MRI) const {
     for (unsigned i = 0; i != getNumValNums(); ++i) {
       if (i) OS << " ";
       OS << i << "@";
-      if (ValueNumberInfo[i].def == ~0U) {
-        OS << "?";
-      } else if (ValueNumberInfo[i].def == ~1U) {
+      if (ValueNumberInfo[i].def == ~1U) {
         OS << "x";
       } else {
-        OS << ValueNumberInfo[i].def;
+        if (ValueNumberInfo[i].def == ~0U)
+          OS << "?";
+        else
+          OS << ValueNumberInfo[i].def;
+        unsigned e = ValueNumberInfo[i].kills.size();
+        if (e) {
+          OS << "-(";
+          for (unsigned j = 0; j != e; ++j) {
+            OS << ValueNumberInfo[i].kills[j];
+            if (j != e-1)
+              OS << " ";
+          }
+          OS << ")";
+        }
       }
     }
   }
diff --git a/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp b/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
index aac6686a10b..ebf3c57230e 100644
--- a/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/llvm/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -437,6 +437,9 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
       unsigned DefIndex = getDefIndex(getInstructionIndex(vi.DefInst));
       unsigned RedefIndex = getDefIndex(MIIdx);
 
+      const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1);
+      unsigned OldEnd = OldLR->end;
+
       // Delete the initial value, which should be short and continuous,
       // because the 2-addr copy must be in the same MBB as the redef.
       interval.removeRange(DefIndex, RedefIndex);
@@ -448,16 +451,18 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
       // The new value number (#1) is defined by the instruction we claimed
       // defined value #0.
       unsigned ValNo = interval.getNextValue(0, 0);
-      interval.setValueNumberInfo(1, interval.getValNumInfo(0));
+      interval.copyValNumInfo(ValNo, 0);
       
       // Value#0 is now defined by the 2-addr instruction.
-      interval.setValueNumberInfo(0, LiveInterval::VNInfo(DefIndex, 0U));
+      interval.setDefForValNum(0, RedefIndex);
+      interval.setSrcRegForValNum(0, 0);
       
       // Add the new live interval which replaces the range for the input copy.
       LiveRange LR(DefIndex, RedefIndex, ValNo);
       DOUT << " replace range with " << LR;
       interval.addRange(LR);
       interval.addKillForValNum(ValNo, RedefIndex);
+      interval.removeKillForValNum(ValNo, RedefIndex, OldEnd);
 
       // If this redefinition is dead, we need to add a dummy unit live
       // range covering the def slot.
@@ -482,8 +487,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
         DOUT << " Removing [" << Start << "," << End << "] from: ";
         interval.print(DOUT, mri_); DOUT << "\n";
         interval.removeRange(Start, End);
-        bool replaced = interval.replaceKillForValNum(0, End, Start);
-        assert(replaced && "Incorrect kill info?");
+        interval.addKillForValNum(0, Start);
         DOUT << " RESULT: "; interval.print(DOUT, mri_);
 
         // Replace the interval with one of a NEW value number.  Note that this
diff --git a/llvm/lib/CodeGen/SimpleRegisterCoalescing.cpp b/llvm/lib/CodeGen/SimpleRegisterCoalescing.cpp
index 650073b7f76..6870aff8166 100644
--- a/llvm/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/llvm/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -90,7 +90,7 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInte
   // Get the location that B is defined at.  Two options: either this value has
   // an unknown definition point or it is defined at CopyIdx.  If unknown, we 
   // can't process it.
-  unsigned BValNoDefIdx = IntB.getInstForValNum(BValNo);
+  unsigned BValNoDefIdx = IntB.getDefForValNum(BValNo);
   if (!IntB.getSrcRegForValNum(BValNo)) return false;
   assert(BValNoDefIdx == CopyIdx &&
          "Copy doesn't define the value?");
@@ -112,7 +112,7 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInte
   if (rep(SrcReg) != IntB.reg) return false;
   
   // Get the LiveRange in IntB that this value number starts with.
-  unsigned AValNoInstIdx = IntA.getInstForValNum(AValNo);
+  unsigned AValNoInstIdx = IntA.getDefForValNum(AValNo);
   LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNoInstIdx-1);
   
   // Make sure that the end of the live range is inside the same block as
@@ -132,7 +132,8 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInte
   // We are about to delete CopyMI, so need to remove it as the 'instruction
   // that defines this value #'. Update the the valnum with the new defining
   // instruction #.
-  IntB.setValueNumberInfo(BValNo, LiveInterval::VNInfo(FillerStart, 0));
+  IntB.setDefForValNum(BValNo, FillerStart);
+  IntB.setSrcRegForValNum(BValNo, 0);
   
   // Okay, we can merge them.  We need to insert a new liverange:
   // [ValLR.end, BLR.begin) of either value number, then we merge the
@@ -399,7 +400,7 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
 /// contains the value number the copy is from.
 ///
 static unsigned ComputeUltimateVN(unsigned VN,
-                         SmallVector<LiveInterval::VNInfo, 16> &ValueNumberInfo,
+                        SmallVector<LiveInterval::VNInfo, 16> &ValueNumberInfo,
                                   SmallVector<int, 16> &ThisFromOther,
                                   SmallVector<int, 16> &OtherFromThis,
                                   SmallVector<int, 16> &ThisValNoAssignments,
@@ -552,11 +553,14 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS)
   // Okay, now that there is a single LHS value number that we're merging the
   // RHS into, update the value number info for the LHS to indicate that the
   // value number is defined where the RHS value number was.
-  LHS.setValueNumberInfo(LHSValNo, RHS.getValNumInfo(0));
+  const LiveInterval::VNInfo VNI = RHS.getValNumInfo(0);
+  LHS.setDefForValNum(LHSValNo, VNI.def);
+  LHS.setSrcRegForValNum(LHSValNo, VNI.reg);
   
   // Okay, the final step is to loop over the RHS live intervals, adding them to
   // the LHS.
   LHS.MergeRangesInAsValue(RHS, LHSValNo);
+  LHS.addKillsForValNum(LHSValNo, VNI.kills);
   LHS.weight += RHS.weight;
   if (RHS.preference && !LHS.preference)
     LHS.preference = RHS.preference;
@@ -574,6 +578,8 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RH
   // coalesced.
   SmallVector<int, 16> LHSValNoAssignments;
   SmallVector<int, 16> RHSValNoAssignments;
+  SmallVector<int, 16> LHSValsDefinedFromRHS;
+  SmallVector<int, 16> RHSValsDefinedFromLHS;
   SmallVector<LiveInterval::VNInfo, 16> ValueNumberInfo;
                           
   // If a live interval is a physical register, conservatively check if any
@@ -604,6 +610,7 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RH
     // often RHS is small and LHS is large (e.g. a physreg).
     
     // Find out if the RHS is defined as a copy from some value in the LHS.
+    int RHSVal0DefinedFromLHS = -1;
     int RHSValID = -1;
     LiveInterval::VNInfo RHSValNoInfo;
     unsigned RHSSrcReg = RHS.getSrcRegForValNum(0);
@@ -618,9 +625,10 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RH
       }
     } else {
       // It was defined as a copy from the LHS, find out what value # it is.
-      unsigned ValInst = RHS.getInstForValNum(0);
+      unsigned ValInst = RHS.getDefForValNum(0);
       RHSValID = LHS.getLiveRangeContaining(ValInst-1)->ValId;
       RHSValNoInfo = LHS.getValNumInfo(RHSValID);
+      RHSVal0DefinedFromLHS = RHSValID;
     }
     
     LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
@@ -641,13 +649,16 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RH
           // value# for it.  Keep the current value number, but remember it.
           LHSValNoAssignments[VN] = RHSValID = VN;
           ValueNumberInfo[VN] = RHSValNoInfo;
+          RHS.addKills(ValueNumberInfo[VN], LHS.getKillsForValNum(VN));
         } else {
           // Otherwise, use the specified value #.
           LHSValNoAssignments[VN] = RHSValID;
           if (VN != (unsigned)RHSValID)
             ValueNumberInfo[VN].def = ~1U;  // Now this val# is dead.
-          else
+          else {
             ValueNumberInfo[VN] = RHSValNoInfo;
+            RHS.addKills(ValueNumberInfo[VN], LHS.getKillsForValNum(VN));
+          }
         }
       } else {
         ValueNumberInfo[VN] = LHS.getValNumInfo(VN);
@@ -657,11 +668,13 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RH
     
     assert(RHSValID != -1 && "Didn't find value #?");
     RHSValNoAssignments[0] = RHSValID;
-    
+    if (RHSVal0DefinedFromLHS != -1) {
+      int LHSValId = LHSValNoAssignments[RHSVal0DefinedFromLHS];
+      LHS.addKills(ValueNumberInfo[LHSValId], RHS.getKillsForValNum(0));
+    }
   } else {
     // Loop over the value numbers of the LHS, seeing if any are defined from
     // the RHS.
-    SmallVector<int, 16> LHSValsDefinedFromRHS;
     LHSValsDefinedFromRHS.resize(LHS.getNumValNums(), -1);
     for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) {
       unsigned ValSrcReg = LHS.getSrcRegForValNum(VN);
@@ -674,13 +687,12 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RH
         continue;
       
       // Figure out the value # from the RHS.
-      unsigned ValInst = LHS.getInstForValNum(VN);
+      unsigned ValInst = LHS.getDefForValNum(VN);
       LHSValsDefinedFromRHS[VN] = RHS.getLiveRangeContaining(ValInst-1)->ValId;
     }
     
     // Loop over the value numbers of the RHS, seeing if any are defined from
     // the LHS.
-    SmallVector<int, 16> RHSValsDefinedFromLHS;
     RHSValsDefinedFromLHS.resize(RHS.getNumValNums(), -1);
     for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) {
       unsigned ValSrcReg = RHS.getSrcRegForValNum(VN);
@@ -693,7 +705,7 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RH
         continue;
       
       // Figure out the value # from the LHS.
-      unsigned ValInst = RHS.getInstForValNum(VN);
+      unsigned ValInst = RHS.getDefForValNum(VN);
       RHSValsDefinedFromLHS[VN] = LHS.getLiveRangeContaining(ValInst-1)->ValId;
     }
     
@@ -702,14 +714,14 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RH
     ValueNumberInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums());
     
     for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) {
-      if (LHSValNoAssignments[VN] >= 0 || LHS.getInstForValNum(VN) == ~1U) 
+      if (LHSValNoAssignments[VN] >= 0 || LHS.getDefForValNum(VN) == ~1U) 
         continue;
       ComputeUltimateVN(VN, ValueNumberInfo,
                         LHSValsDefinedFromRHS, RHSValsDefinedFromLHS,
                         LHSValNoAssignments, RHSValNoAssignments, LHS, RHS);
     }
     for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) {
-      if (RHSValNoAssignments[VN] >= 0 || RHS.getInstForValNum(VN) == ~1U)
+      if (RHSValNoAssignments[VN] >= 0 || RHS.getDefForValNum(VN) == ~1U)
         continue;
       // If this value number isn't a copy from the LHS, it's a new number.
       if (RHSValsDefinedFromLHS[VN] == -1) {
@@ -766,6 +778,22 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RH
     }
   }
 
+  // Update kill info. Some live ranges are extended due to copy coalescing.
+  for (unsigned i = 0, e = RHSValsDefinedFromLHS.size(); i != e; ++i) {
+    int LHSValId = RHSValsDefinedFromLHS[i];
+    if (LHSValId == -1)
+      continue;
+    unsigned RHSValId = RHSValNoAssignments[i];
+    LHS.addKills(ValueNumberInfo[RHSValId], RHS.getKillsForValNum(i));
+  }
+  for (unsigned i = 0, e = LHSValsDefinedFromRHS.size(); i != e; ++i) {
+    int RHSValId = LHSValsDefinedFromRHS[i];
+    if (RHSValId == -1)
+      continue;
+    unsigned LHSValId = LHSValNoAssignments[i];
+    RHS.addKills(ValueNumberInfo[LHSValId], LHS.getKillsForValNum(i));
+  }
+
   // If we get here, we know that we can coalesce the live ranges.  Ask the
   // intervals to coalesce themselves now.
   LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0],