Revert r139247 "Cache intermediate results during traceSiblingValue."

It broke the self host and clang-x86_64-darwin10-RA.

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

1 files changed, 82 insertions, 221 deletions

diff --git a/lib/CodeGen/InlineSpiller.cpp b/lib/CodeGen/InlineSpiller.cpp
index d5c1da9d4b..f0f69872b0 100644
--- a/lib/CodeGen/InlineSpiller.cpp
+++ b/lib/CodeGen/InlineSpiller.cpp
@@ -17,7 +17,6 @@
 #include "LiveRangeEdit.h"
 #include "VirtRegMap.h"
 #include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveStackAnalysis.h"
@@ -76,55 +75,30 @@ class InlineSpiller : public Spiller {
   // Values that failed to remat at some point.
   SmallPtrSet<VNInfo*, 8> UsedValues;
 
-public:
   // Information about a value that was defined by a copy from a sibling
   // register.
   struct SibValueInfo {
     // True when all reaching defs were reloads: No spill is necessary.
     bool AllDefsAreReloads;
 
-    // True when value is defined by an original PHI not from splitting.
-    bool DefByOrigPHI;
-
     // The preferred register to spill.
     unsigned SpillReg;
 
     // The value of SpillReg that should be spilled.
     VNInfo *SpillVNI;
 
-    // The block where SpillVNI should be spilled. Currently, this must be the
-    // block containing SpillVNI->def.
-    MachineBasicBlock *SpillMBB;
-
     // A defining instruction that is not a sibling copy or a reload, or NULL.
     // This can be used as a template for rematerialization.
     MachineInstr *DefMI;
 
-    // List of values that depend on this one.  These values are actually the
-    // same, but live range splitting has placed them in different registers,
-    // or SSA update needed to insert PHI-defs to preserve SSA form.  This is
-    // copies of the current value and phi-kills.  Usually only phi-kills cause
-    // more than one dependent value.
-    TinyPtrVector<VNInfo*> Deps;
-
     SibValueInfo(unsigned Reg, VNInfo *VNI)
-      : AllDefsAreReloads(true), DefByOrigPHI(false),
-        SpillReg(Reg), SpillVNI(VNI), SpillMBB(0), DefMI(0) {}
-
-    // Returns true when a def has been found.
-    bool hasDef() const { return DefByOrigPHI || DefMI; }
+      : AllDefsAreReloads(false), SpillReg(Reg), SpillVNI(VNI), DefMI(0) {}
   };
 
-private:
   // Values in RegsToSpill defined by sibling copies.
   typedef DenseMap<VNInfo*, SibValueInfo> SibValueMap;
   SibValueMap SibValues;
 
-  // Values live-out from basic blocks.  This is the same as
-  // LI.getVNInfoAt(LIS.getMBBEndIdx(MBB).getPrevSlot())
-  typedef DenseMap<MachineBasicBlock*, VNInfo*> LiveOutMap;
-  LiveOutMap LiveOutValues;
-
   // Dead defs generated during spilling.
   SmallVector<MachineInstr*, 8> DeadDefs;
 
@@ -160,7 +134,6 @@ private:
 
   bool isSibling(unsigned Reg);
   MachineInstr *traceSiblingValue(unsigned, VNInfo*, VNInfo*);
-  void propagateSiblingValue(SibValueMap::iterator, VNInfo *VNI = 0);
   void analyzeSiblingValues();
 
   bool hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI);
@@ -309,135 +282,6 @@ bool InlineSpiller::isSibling(unsigned Reg) {
            VRM.getOriginal(Reg) == Original;
 }
 
-#ifndef NDEBUG
-static raw_ostream &operator<<(raw_ostream &OS,
-                               const InlineSpiller::SibValueInfo &SVI) {
-  OS << "spill " << PrintReg(SVI.SpillReg) << ':'
-     << SVI.SpillVNI->id << '@' << SVI.SpillVNI->def;
-  if (SVI.AllDefsAreReloads)
-    OS << " all-reloads";
-  if (SVI.DefByOrigPHI)
-    OS << " orig-phi";
-  if (SVI.DefMI)
-    OS << " def: " << *SVI.DefMI;
-  else
-    OS << '\n';
-  return OS;
-}
-#endif
-
-/// propagateSiblingValue - Propagate the value in SVI to dependents if it is
-/// known.  Otherwise remember the dependency for later.
-///
-/// @param SVI SibValues entry to propagate.
-/// @param VNI Dependent value, or NULL to propagate to all saved dependents.
-void InlineSpiller::propagateSiblingValue(SibValueMap::iterator SVI,
-                                          VNInfo *VNI) {
-  SibValueInfo &SV = SVI->second;
-
-  if (!SV.SpillMBB)
-    SV.SpillMBB = LIS.getMBBFromIndex(SV.SpillVNI->def);
-
-  // Should this value be propagated as a preferred spill candidate?  We don't
-  // propagate values of registers that are about to spill.
-  bool PropSpill = !isRegToSpill(SV.SpillReg);
-  unsigned SpillDepth = ~0u;
-
-  // Further values that need to be updated.
-  SmallVector<VNInfo*, 8> WorkList;
-
-  // Defer propagation if the value is not known yet.
-  if (VNI) {
-    SV.Deps.push_back(VNI);
-    // Don't propagate to other dependents than VNI. SVI hasn't changed.
-    WorkList.push_back(VNI);
-  } else {
-    // No VNI given, update all Deps.
-    WorkList.append(SV.Deps.begin(), SV.Deps.end());
-  }
-
-  // Has the value been completely determined yet?  If not, defer propagation.
-  if (!SV.hasDef())
-    return;
-
-  while (!WorkList.empty()) {
-    SibValueMap::iterator DepSVI = SibValues.find(WorkList.pop_back_val());
-    assert(DepSVI != SibValues.end() && "Dependent value not in SibValues");
-    SibValueInfo &DepSV = DepSVI->second;
-    bool Changed = false;
-
-    if (!DepSV.SpillMBB)
-      DepSV.SpillMBB = LIS.getMBBFromIndex(DepSV.SpillVNI->def);
-
-    // Propagate defining instruction.
-    if (!DepSV.hasDef()) {
-      Changed = true;
-      DepSV.DefMI = SV.DefMI;
-      DepSV.DefByOrigPHI = SV.DefByOrigPHI;
-    }
-
-    // Propagate AllDefsAreReloads.  For PHI values, this computes an AND of
-    // all predecessors.
-    if (!SV.AllDefsAreReloads && DepSV.AllDefsAreReloads) {
-      Changed = true;
-      DepSV.AllDefsAreReloads = false;
-    }
-
-    // Propagate best spill value.
-    if (PropSpill && SV.SpillVNI != DepSV.SpillVNI) {
-      if (SV.SpillMBB == DepSV.SpillMBB) {
-        // DepSV is in the same block.  Hoist when dominated.
-        if (SV.SpillVNI->def < DepSV.SpillVNI->def) {
-          // This is an alternative def earlier in the same MBB.
-          // Hoist the spill as far as possible in SpillMBB. This can ease
-          // register pressure:
-          //
-          //   x = def
-          //   y = use x
-          //   s = copy x
-          //
-          // Hoisting the spill of s to immediately after the def removes the
-          // interference between x and y:
-          //
-          //   x = def
-          //   spill x
-          //   y = use x<kill>
-          //
-          Changed = true;
-          DepSV.SpillReg = SV.SpillReg;
-          DepSV.SpillVNI = SV.SpillVNI;
-          DepSV.SpillMBB = SV.SpillMBB;
-        }
-      } else {
-        // DepSV is in a different block.
-        if (SpillDepth == ~0u)
-          SpillDepth = Loops.getLoopDepth(SV.SpillMBB);
-
-        // Also hoist spills to blocks with smaller loop depth, but make sure
-        // that the new value dominates.  Non-phi dependents are always
-        // dominated, phis need checking.
-        if ((Loops.getLoopDepth(DepSV.SpillMBB) > SpillDepth) &&
-            (!DepSVI->first->isPHIDef() ||
-             MDT.dominates(SV.SpillMBB, DepSV.SpillMBB))) {
-          Changed = true;
-          DepSV.SpillReg = SV.SpillReg;
-          DepSV.SpillVNI = SV.SpillVNI;
-          DepSV.SpillMBB = SV.SpillMBB;
-        }
-      }
-    }
-
-    if (!Changed)
-      continue;
-
-    // Something changed in DepSVI. Propagate to dependents.
-    WorkList.append(DepSV.Deps.begin(), DepSV.Deps.end());
-
-    DEBUG(dbgs() << "  update " << DepSVI->first->id << '@'
-                 << DepSVI->first->def << " to:\t" << DepSV);
-  }
-}
-
 /// traceSiblingValue - Trace a value that is about to be spilled back to the
 /// real defining instructions by looking through sibling copies. Always stay
 /// within the range of OrigVNI so the registers are known to carry the same
@@ -450,68 +294,84 @@ void InlineSpiller::propagateSiblingValue(SibValueMap::iterator SVI,
 ///
 MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI,
                                                VNInfo *OrigVNI) {
-  // Check if a cached value already exists.
-  SibValueMap::iterator SVI;
-  bool Inserted;
-  tie(SVI, Inserted) =
-    SibValues.insert(std::make_pair(UseVNI, SibValueInfo(UseReg, UseVNI)));
-  if (!Inserted) {
-    DEBUG(dbgs() << "Cached value " << PrintReg(UseReg) << ':'
-                 << UseVNI->id << '@' << UseVNI->def << ' ' << SVI->second);
-    return SVI->second.DefMI;
-  }
-
   DEBUG(dbgs() << "Tracing value " << PrintReg(UseReg) << ':'
                << UseVNI->id << '@' << UseVNI->def << '\n');
-
-  // List of (Reg, VNI) that have been inserted into SibValues, but need to be
-  // processed.
+  SmallPtrSet<VNInfo*, 8> Visited;
   SmallVector<std::pair<unsigned, VNInfo*>, 8> WorkList;
   WorkList.push_back(std::make_pair(UseReg, UseVNI));
 
+  // Best spill candidate seen so far. This must dominate UseVNI.
+  SibValueInfo SVI(UseReg, UseVNI);
+  MachineBasicBlock *UseMBB = LIS.getMBBFromIndex(UseVNI->def);
+  MachineBasicBlock *SpillMBB = UseMBB;
+  unsigned SpillDepth = Loops.getLoopDepth(SpillMBB);
+  bool SeenOrigPHI = false; // Original PHI met.
+
   do {
     unsigned Reg;
     VNInfo *VNI;
     tie(Reg, VNI) = WorkList.pop_back_val();
-    DEBUG(dbgs() << "  " << PrintReg(Reg) << ':' << VNI->id << '@' << VNI->def
-                 << ":\t");
+    if (!Visited.insert(VNI))
+      continue;
 
-    // First check if this value has already been computed.
-    SVI = SibValues.find(VNI);
-    assert(SVI != SibValues.end() && "Missing SibValues entry");
+    // Is this value a better spill candidate?
+    if (!isRegToSpill(Reg)) {
+      MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
+      if (MBB == SpillMBB) {
+        // This is an alternative def earlier in the same MBB.
+        // Hoist the spill as far as possible in SpillMBB. This can ease
+        // register pressure:
+        //
+        //   x = def
+        //   y = use x
+        //   s = copy x
+        //
+        // Hoisting the spill of s to immediately after the def removes the
+        // interference between x and y:
+        //
+        //   x = def
+        //   spill x
+        //   y = use x<kill>
+        //
+        if (VNI->def < SVI.SpillVNI->def) {
+          DEBUG(dbgs() << "  hoist in BB#" << MBB->getNumber() << ": "
+                       << PrintReg(Reg) << ':' << VNI->id << '@' << VNI->def
+                       << '\n');
+          SVI.SpillReg = Reg;
+          SVI.SpillVNI = VNI;
+        }
+      } else if (MBB != UseMBB && MDT.dominates(MBB, UseMBB)) {
+        // This is a valid spill location dominating UseVNI.
+        // Prefer to spill at a smaller loop depth.
+        unsigned Depth = Loops.getLoopDepth(MBB);
+        if (Depth < SpillDepth) {
+          DEBUG(dbgs() << "  spill depth " << Depth << ": " << PrintReg(Reg)
+                       << ':' << VNI->id << '@' << VNI->def << '\n');
+          SVI.SpillReg = Reg;
+          SVI.SpillVNI = VNI;
+          SpillMBB = MBB;
+          SpillDepth = Depth;
+        }
+      }
+    }
 
     // Trace through PHI-defs created by live range splitting.
     if (VNI->isPHIDef()) {
       if (VNI->def == OrigVNI->def) {
-        DEBUG(dbgs() << "orig phi value\n");
-        SVI->second.DefByOrigPHI = true;
-        SVI->second.AllDefsAreReloads = false;
-        propagateSiblingValue(SVI);
+        DEBUG(dbgs() << "  orig phi value " << PrintReg(Reg) << ':'
+                     << VNI->id << '@' << VNI->def << '\n');
+        SeenOrigPHI = true;
         continue;
       }
       // Get values live-out of predecessors.
       LiveInterval &LI = LIS.getInterval(Reg);
       MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
-      DEBUG(dbgs() << "split phi value, check " << MBB->pred_size()
-                   << " preds\n");
       for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
              PE = MBB->pred_end(); PI != PE; ++PI) {
-        // Use a cache of block live-out values.  This is faster than using
-        // getVNInfoAt on complex intervals.
-        VNInfo *&PVNI = LiveOutValues[*PI];
-        if (!PVNI)
-          PVNI = LI.getVNInfoAt(LIS.getMBBEndIdx(*PI).getPrevSlot());
-        if (!PVNI)
-          continue;
-        // Known predecessor value? Try an insertion.
-        tie(SVI, Inserted) =
-          SibValues.insert(std::make_pair(PVNI, SibValueInfo(Reg, PVNI)));
-        // This is the first time we see PVNI, add it to the worklist.
-        if (Inserted)
+        VNInfo *PVNI = LI.getVNInfoAt(LIS.getMBBEndIdx(*PI).getPrevSlot());
+        if (PVNI)
           WorkList.push_back(std::make_pair(Reg, PVNI));
-        propagateSiblingValue(SVI, VNI);
       }
-      // Next work list item.
       continue;
     }
 
@@ -524,43 +384,46 @@ MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI,
         LiveInterval &SrcLI = LIS.getInterval(SrcReg);
         VNInfo *SrcVNI = SrcLI.getVNInfoAt(VNI->def.getUseIndex());
         assert(SrcVNI && "Copy from non-existing value");
-        DEBUG(dbgs() << "copy of " << PrintReg(SrcReg) << ':'
+        DEBUG(dbgs() << "  copy of " << PrintReg(SrcReg) << ':'
                      << SrcVNI->id << '@' << SrcVNI->def << '\n');
-        // Known sibling source value? Try an insertion.
-        tie(SVI, Inserted) = SibValues.insert(std::make_pair(SrcVNI,
-                                                 SibValueInfo(SrcReg, SrcVNI)));
-        // This is the first time we see Src, add it to the worklist.
-        if (Inserted)
-          WorkList.push_back(std::make_pair(SrcReg, SrcVNI));
-        propagateSiblingValue(SVI, VNI);
-        // Next work list item.
+        WorkList.push_back(std::make_pair(SrcReg, SrcVNI));
         continue;
       }
     }
 
     // Track reachable reloads.
-    SVI->second.DefMI = MI;
-    SVI->second.SpillMBB = MI->getParent();
     int FI;
     if (Reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot) {
-      DEBUG(dbgs() << "reload\n");
-      propagateSiblingValue(SVI);
-      // Next work list item.
+      DEBUG(dbgs() << "  reload " << PrintReg(Reg) << ':'
+                   << VNI->id << "@" << VNI->def << '\n');
+      SVI.AllDefsAreReloads = true;
       continue;
     }
 
+    // We have an 'original' def. Don't record trivial cases.
+    if (VNI == UseVNI) {
+      DEBUG(dbgs() << "Not a sibling copy.\n");
+      return MI;
+    }
+
     // Potential remat candidate.
-    DEBUG(dbgs() << "def " << *MI);
-    SVI->second.AllDefsAreReloads = false;
-    propagateSiblingValue(SVI);
+    DEBUG(dbgs() << "  def " << PrintReg(Reg) << ':'
+                 << VNI->id << '@' << VNI->def << '\t' << *MI);
+    SVI.DefMI = MI;
   } while (!WorkList.empty());
 
-  // Look up the value we were looking for.  We already did this lokup at the
-  // top of the function, but SibValues may have been invalidated.
-  SVI = SibValues.find(UseVNI);
-  assert(SVI != SibValues.end() && "Didn't compute requested info");
-  DEBUG(dbgs() << "  traced to:\t" << SVI->second);
-  return SVI->second.DefMI;
+  if (SeenOrigPHI || SVI.DefMI)
+    SVI.AllDefsAreReloads = false;
+
+  DEBUG({
+    if (SVI.AllDefsAreReloads)
+      dbgs() << "All defs are reloads.\n";
+    else
+      dbgs() << "Prefer to spill " << PrintReg(SVI.SpillReg) << ':'
+             << SVI.SpillVNI->id << '@' << SVI.SpillVNI->def << '\n';
+  });
+  SibValues.insert(std::make_pair(UseVNI, SVI));
+  return SVI.DefMI;
 }
 
 /// analyzeSiblingValues - Trace values defined by sibling copies back to
@@ -569,7 +432,6 @@ MachineInstr *InlineSpiller::traceSiblingValue(unsigned UseReg, VNInfo *UseVNI,
 /// Keep track of values that may be rematerializable.
 void InlineSpiller::analyzeSiblingValues() {
   SibValues.clear();
-  LiveOutValues.clear();
 
   // No siblings at all?
   if (Edit->getReg() == Original)
@@ -644,7 +506,6 @@ bool InlineSpiller::hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI) {
 
   // Already spilled everywhere.
   if (SVI.AllDefsAreReloads) {
-    DEBUG(dbgs() << "\tno spill needed: " << SVI);
     ++NumOmitReloadSpill;
     return true;
   }