Recover most of the compile time regression due to recent live interval changes.

1. Eliminate the costly live interval "swapping".
2. Change ValueNumberInfo container from SmallVector to std::vector. The former
   performs slowly when the vector size is very large.


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

2 files changed, 46 insertions, 44 deletions

diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 9697d43bb4..0be4e9bed4 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -288,25 +288,12 @@ LiveInterval::FindLiveRangeContaining(unsigned Idx) {
 void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments,
                         int *RHSValNoAssignments, 
                         SmallVector<VNInfo, 16> &NewValueNumberInfo) {
-  
-  // Try to do the least amount of work possible.  In particular, if there are
-  // more liverange chunks in the other set than there are in the 'this' set,
-  // swap sets to merge the fewest chunks in possible.
-  //
-  // Also, if one range is a physreg and one is a vreg, we always merge from the
-  // vreg into the physreg, which leaves the vreg intervals pristine.
-  if ((Other.ranges.size() > ranges.size() &&
-      MRegisterInfo::isVirtualRegister(reg)) ||
-      MRegisterInfo::isPhysicalRegister(Other.reg)) {
-    swap(Other);
-    std::swap(LHSValNoAssignments, RHSValNoAssignments);
-  }
 
   // Determine if any of our live range values are mapped.  This is uncommon, so
   // we want to avoid the interval scan if not.
   bool MustMapCurValNos = false;
   for (unsigned i = 0, e = getNumValNums(); i != e; ++i) {
-    if (ValueNumberInfo[i].def == ~1U) continue;  // tombstone value #
+    if (getDefForValNum(i) == ~1U) continue;  // tombstone value #
     if (i != (unsigned)LHSValNoAssignments[i]) {
       MustMapCurValNos = true;
       break;
@@ -345,7 +332,9 @@ void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments,
 
   // Update val# info first. Increasing live ranges may invalidate some kills.
   ValueNumberInfo.clear();
-  ValueNumberInfo.append(NewValueNumberInfo.begin(), NewValueNumberInfo.end());
+  for (SmallVector<VNInfo, 16>::iterator I = NewValueNumberInfo.begin(),
+         E = NewValueNumberInfo.end(); I != E; ++I)
+    ValueNumberInfo.push_back(*I);
 
   // Okay, now insert the RHS live ranges into the LHS.
   iterator InsertPos = begin();
@@ -472,7 +461,7 @@ void LiveInterval::MergeValueNumberInto(unsigned V1, unsigned V2) {
       ValueNumberInfo.pop_back();
     } while (ValueNumberInfo.back().def == ~1U);
   } else {
-    ValueNumberInfo[V1].def = ~1U;
+    setDefForValNum(V1, ~1U);
   }
 }
 
@@ -511,22 +500,25 @@ void LiveInterval::print(std::ostream &OS, const MRegisterInfo *MRI) const {
   // Print value number info.
   if (getNumValNums()) {
     OS << "  ";
-    for (unsigned i = 0; i != getNumValNums(); ++i) {
-      if (i) OS << " ";
-      OS << i << "@";
-      if (ValueNumberInfo[i].def == ~1U) {
+    unsigned vnum = 0;
+    for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e;
+         ++i, ++vnum) {
+      const VNInfo &vni = *i;
+      if (vnum) OS << " ";
+      OS << vnum << "@";
+      if (vni.def == ~1U) {
         OS << "x";
       } else {
-        if (ValueNumberInfo[i].def == ~0U)
+        if (vni.def == ~0U)
           OS << "?";
         else
-          OS << ValueNumberInfo[i].def;
-        unsigned e = ValueNumberInfo[i].kills.size();
-        if (e) {
+          OS << vni.def;
+        unsigned ee = vni.kills.size();
+        if (ee) {
           OS << "-(";
-          for (unsigned j = 0; j != e; ++j) {
-            OS << ValueNumberInfo[i].kills[j];
-            if (j != e-1)
+          for (unsigned j = 0; j != ee; ++j) {
+            OS << vni.kills[j];
+            if (j != ee-1)
               OS << " ";
           }
           OS << ")";
diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp
index 276a5092f6..d8d0ce2ce4 100644
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -309,7 +309,8 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
   // Otherwise, if one of the intervals being joined is a physreg, this method
   // always canonicalizes DstInt to be it.  The output "SrcInt" will not have
   // been modified, so we can use this information below to update aliases.
-  if (JoinIntervals(DstInt, SrcInt)) {
+  bool Swapped = false;
+  if (JoinIntervals(DstInt, SrcInt, Swapped)) {
     if (isDead) {
       // Result of the copy is dead. Propagate this property.
       if (SrcStart == 0) {
@@ -330,8 +331,8 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
 
     if (isShorten || isDead) {
       // Shorten the destination live interval.
-      if (repSrcReg == DstInt.reg)
-        DstInt.removeRange(RemoveStart, RemoveEnd);
+      if (Swapped)
+        SrcInt.removeRange(RemoveStart, RemoveEnd);
     }
   } else {
     // Coalescing failed.
@@ -345,9 +346,12 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
     return false;
   }
 
-  bool Swapped = repSrcReg == DstInt.reg;
-  if (Swapped)
+  LiveInterval *ResSrcInt = &SrcInt;
+  LiveInterval *ResDstInt = &DstInt;
+  if (Swapped) {
     std::swap(repSrcReg, repDstReg);
+    std::swap(ResSrcInt, ResDstInt);
+  }
   assert(MRegisterInfo::isVirtualRegister(repSrcReg) &&
          "LiveInterval::join didn't work right!");
                                
@@ -356,15 +360,15 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
   // have clobbered values for this range.
   if (MRegisterInfo::isPhysicalRegister(repDstReg)) {
     // Unset unnecessary kills.
-    if (!DstInt.containsOneValue()) {
-      for (LiveInterval::Ranges::const_iterator I = SrcInt.begin(),
-             E = SrcInt.end(); I != E; ++I)
+    if (!ResDstInt->containsOneValue()) {
+      for (LiveInterval::Ranges::const_iterator I = ResSrcInt->begin(),
+             E = ResSrcInt->end(); I != E; ++I)
         unsetRegisterKills(I->start, I->end, repDstReg);
     }
 
     // Update the liveintervals of sub-registers.
     for (const unsigned *AS = mri_->getSubRegisters(repDstReg); *AS; ++AS)
-      li_->getInterval(*AS).MergeInClobberRanges(SrcInt);
+      li_->getInterval(*AS).MergeInClobberRanges(*ResSrcInt);
   } else {
     // Merge use info if the destination is a virtual register.
     LiveVariables::VarInfo& dVI = lv_->getVarInfo(repDstReg);
@@ -372,7 +376,7 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
     dVI.NumUses += sVI.NumUses;
   }
 
-  DOUT << "\n\t\tJoined.  Result = "; DstInt.print(DOUT, mri_);
+  DOUT << "\n\t\tJoined.  Result = "; ResDstInt->print(DOUT, mri_);
   DOUT << "\n";
 
   // Remember these liveintervals have been joined.
@@ -380,10 +384,6 @@ bool SimpleRegisterCoalescing::JoinCopy(MachineInstr *CopyMI,
   if (MRegisterInfo::isVirtualRegister(repDstReg))
     JoinedLIs.set(repDstReg - MRegisterInfo::FirstVirtualRegister);
 
-  // If the intervals were swapped by Join, swap them back so that the register
-  // mapping (in the r2i map) is correct.
-  if (Swapped) SrcInt.swap(DstInt);
-
   // repSrcReg is guarateed to be the register whose live interval that is
   // being merged.
   li_->removeInterval(repSrcReg);
@@ -586,7 +586,8 @@ bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS)
 /// physreg, this method always canonicalizes LHS to be it.  The output
 /// "RHS" will not have been modified, so we can use this information
 /// below to update aliases.
-bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) {
+bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS,
+                                             LiveInterval &RHS, bool &Swapped) {
   // Compute the final value assignment, assuming that the live ranges can be
   // coalesced.
   SmallVector<int, 16> LHSValNoAssignments;
@@ -815,8 +816,17 @@ bool SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RH
 
   // 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],
-           ValueNumberInfo);
+  if ((RHS.ranges.size() > LHS.ranges.size() &&
+      MRegisterInfo::isVirtualRegister(LHS.reg)) ||
+      MRegisterInfo::isPhysicalRegister(RHS.reg)) {
+    RHS.join(LHS, &RHSValNoAssignments[0], &LHSValNoAssignments[0],
+             ValueNumberInfo);
+    Swapped = true;
+  } else {
+    LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0],
+             ValueNumberInfo);
+    Swapped = false;
+  }
   return true;
 }