Added support for register allocators to record which intervals are spill intervals, and where the uses and defs of the original intervals were in the original code.

Spill intervals can be hidden using the "-rmf-intervals=virt-nospills*" option.



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

3 files changed, 193 insertions, 83 deletions

diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp
index c6fdf04c7a..61f337bab4 100644
--- a/lib/CodeGen/RegAllocPBQP.cpp
+++ b/lib/CodeGen/RegAllocPBQP.cpp
@@ -140,6 +140,7 @@ namespace {
     const TargetInstrInfo *tii;
     const MachineLoopInfo *loopInfo;
     MachineRegisterInfo *mri;
+    RenderMachineFunction *rmf;
 
     LiveIntervals *lis;
     LiveStacks *lss;
@@ -761,9 +762,11 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) {
       const LiveInterval *spillInterval = node2LI[node];
       double oldSpillWeight = spillInterval->weight;
       SmallVector<LiveInterval*, 8> spillIs;
+      rmf->rememberUseDefs(spillInterval);
       std::vector<LiveInterval*> newSpills =
         lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm);
       addStackInterval(spillInterval, mri);
+      rmf->rememberSpills(spillInterval, newSpills);
 
       (void) oldSpillWeight;
       DEBUG(dbgs() << "VREG " << virtReg << " -> SPILLED (Cost: "
@@ -871,7 +874,7 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
   lis = &getAnalysis<LiveIntervals>();
   lss = &getAnalysis<LiveStacks>();
   loopInfo = &getAnalysis<MachineLoopInfo>();
-  RenderMachineFunction *rmf = &getAnalysis<RenderMachineFunction>();
+  rmf = &getAnalysis<RenderMachineFunction>();
 
   vrm = &getAnalysis<VirtRegMap>();
 
diff --git a/lib/CodeGen/RenderMachineFunction.cpp b/lib/CodeGen/RenderMachineFunction.cpp
index 184b06ed6b..93426eecbb 100644
--- a/lib/CodeGen/RenderMachineFunction.cpp
+++ b/lib/CodeGen/RenderMachineFunction.cpp
@@ -57,6 +57,11 @@ showIntervals("rmf-intervals",
               cl::init(""), cl::Hidden);
 
 static cl::opt<bool>
+filterEmpty("rmf-filter-empty-intervals",
+            cl::desc("Don't display empty intervals."),
+            cl::init(true), cl::Hidden);
+
+static cl::opt<bool>
 showEmptyIndexes("rmf-empty-indexes",
                  cl::desc("Render indexes not associated with instructions or "
                           "MBB starts."),
@@ -150,10 +155,14 @@ namespace llvm {
                                           const std::string &intervalRangeStr) {
     if (intervalRangeStr == "*") {
       intervalTypesToRender |= All;
+    } else if (intervalRangeStr == "virt-nospills*") {
+      intervalTypesToRender |= VirtNoSpills;
+    } else if (intervalRangeStr == "spills*") {
+      intervalTypesToRender |= VirtSpills;
     } else if (intervalRangeStr == "virt*") {
-      intervalTypesToRender |= VirtPlusExplicit;
+      intervalTypesToRender |= AllVirt;
     } else if (intervalRangeStr == "phys*") {
-      intervalTypesToRender |= PhysPlusExplicit;
+      intervalTypesToRender |= AllPhys;
     } else {
       std::istringstream iss(intervalRangeStr);
       unsigned reg1, reg2;
@@ -179,10 +188,12 @@ namespace llvm {
 
   void MFRenderingOptions::setup(MachineFunction *mf,
                                  const TargetRegisterInfo *tri,
-                                 LiveIntervals *lis) {
+                                 LiveIntervals *lis,
+                                 const RenderMachineFunction *rmf) {
     this->mf = mf;
     this->tri = tri;
     this->lis = lis;
+    this->rmf = rmf;
 
     clear();
   }
@@ -252,12 +263,19 @@ namespace llvm {
       if (intervalTypesToRender != ExplicitOnly) {
         for (LiveIntervals::iterator liItr = lis->begin(), liEnd = lis->end();
              liItr != liEnd; ++liItr) {
-
-          if ((TargetRegisterInfo::isPhysicalRegister(liItr->first) &&
-               (intervalTypesToRender & PhysPlusExplicit)) ||
-              (TargetRegisterInfo::isVirtualRegister(liItr->first) &&
-               (intervalTypesToRender & VirtPlusExplicit))) {
-            intervalSet.insert(liItr->second);
+          LiveInterval *li = liItr->second;
+
+          if (filterEmpty && li->empty())
+            continue;
+
+          if ((TargetRegisterInfo::isPhysicalRegister(li->reg) &&
+               (intervalTypesToRender & AllPhys))) {
+            intervalSet.insert(li);
+          } else if (TargetRegisterInfo::isVirtualRegister(li->reg)) {
+            if (((intervalTypesToRender & VirtNoSpills) && !rmf->isSpill(li)) || 
+                ((intervalTypesToRender & VirtSpills) && rmf->isSpill(li))) {
+              intervalSet.insert(li);
+            }
           }
         }
       }
@@ -542,7 +560,26 @@ namespace llvm {
                                         SlotIndex i) const {
     const MachineInstr *mi = sis->getInstructionFromIndex(i);
 
+    // For uses/defs recorded use/def indexes override current liveness and
+    // instruction operands (Only for the interval which records the indexes).
+    if (i.isUse() || i.isDef()) {
+      UseDefs::const_iterator udItr = useDefs.find(li);
+      if (udItr != useDefs.end()) {
+        const SlotSet &slotSet = udItr->second;
+        if (slotSet.count(i)) {
+          if (i.isUse()) {
+            return Used;
+          }
+          // else
+          return Defined;
+        }
+      }
+    }
+
+    // If the slot is a load/store, or there's no info in the use/def set then
+    // use liveness and instruction operand info.
     if (li->liveAt(i)) {
+
       if (mi == 0) {
         if (vrm == 0 || 
             (vrm->getStackSlot(li->reg) == VirtRegMap::NO_STACK_SLOT)) {
@@ -880,6 +917,7 @@ namespace llvm {
   }
 
   bool RenderMachineFunction::runOnMachineFunction(MachineFunction &fn) {
+
     mf = &fn;
     mri = &mf->getRegInfo();
     tri = mf->getTarget().getRegisterInfo();
@@ -887,7 +925,10 @@ namespace llvm {
     sis = &getAnalysis<SlotIndexes>();
 
     trei.setup(mf, mri, tri, lis);
-    ro.setup(mf, tri, lis);
+    ro.setup(mf, tri, lis, this);
+    spillIntervals.clear();
+    spillFor.clear();
+    useDefs.clear();
 
     fqn = mf->getFunction()->getParent()->getModuleIdentifier() + "." +
           mf->getFunction()->getName().str();
@@ -898,6 +939,50 @@ namespace llvm {
   void RenderMachineFunction::releaseMemory() {
     trei.clear();
     ro.clear();
+    spillIntervals.clear();
+    spillFor.clear();
+    useDefs.clear();
+  }
+
+  void RenderMachineFunction::rememberUseDefs(const LiveInterval *li) {
+
+    if (!ro.shouldRenderCurrentMachineFunction())
+      return; 
+
+    for (MachineRegisterInfo::reg_iterator rItr = mri->reg_begin(li->reg),
+                                           rEnd = mri->reg_end();
+         rItr != rEnd; ++rItr) {
+      const MachineInstr *mi = &*rItr;
+      if (mi->readsRegister(li->reg)) {
+        useDefs[li].insert(lis->getInstructionIndex(mi).getUseIndex());
+      }
+      if (mi->definesRegister(li->reg)) {
+        useDefs[li].insert(lis->getInstructionIndex(mi).getDefIndex());
+      }
+    }
+  }
+
+  void RenderMachineFunction::rememberSpills(
+                                     const LiveInterval *li,
+                                     const std::vector<LiveInterval*> &spills) {
+
+    if (!ro.shouldRenderCurrentMachineFunction())
+      return; 
+
+    for (std::vector<LiveInterval*>::const_iterator siItr = spills.begin(),
+                                                    siEnd = spills.end();
+         siItr != siEnd; ++siItr) {
+      const LiveInterval *spill = *siItr;
+      spillIntervals[li].insert(spill);
+      spillFor[spill] = li;
+    }
+  }
+
+  bool RenderMachineFunction::isSpill(const LiveInterval *li) const {
+    SpillForMap::const_iterator sfItr = spillFor.find(li);
+    if (sfItr == spillFor.end())
+      return false;
+    return true;
   }
 
   void RenderMachineFunction::renderMachineFunction(
diff --git a/lib/CodeGen/RenderMachineFunction.h b/lib/CodeGen/RenderMachineFunction.h
index 71a613beda..8d56a8292a 100644
--- a/lib/CodeGen/RenderMachineFunction.h
+++ b/lib/CodeGen/RenderMachineFunction.h
@@ -28,77 +28,12 @@ namespace llvm {
   class LiveIntervals;
   class MachineInstr;
   class MachineRegisterInfo;
+  class RenderMachineFunction;
   class TargetRegisterClass;
   class TargetRegisterInfo;
   class VirtRegMap;
   class raw_ostream;
 
-  /// \brief Provide extra information about the physical and virtual registers
-  ///        in the function being compiled.
-  class TargetRegisterExtraInfo {
-  public:
-    TargetRegisterExtraInfo();
-
-    /// \brief Set up TargetRegisterExtraInfo with pointers to necessary
-    ///        sources of information.
-    void setup(MachineFunction *mf, MachineRegisterInfo *mri,
-               const TargetRegisterInfo *tri, LiveIntervals *lis);
-
-    /// \brief Recompute tables for changed function.
-    void reset(); 
-
-    /// \brief Free all tables in TargetRegisterExtraInfo.
-    void clear();
-
-    /// \brief Maximum number of registers from trc which alias reg.
-    unsigned getWorst(unsigned reg, const TargetRegisterClass *trc) const;
-
-    /// \brief Returns the number of allocable registers in trc.
-    unsigned getCapacity(const TargetRegisterClass *trc) const;
-
-    /// \brief Return the number of registers of class trc that may be
-    ///        needed at slot i.
-    unsigned getPressureAtSlot(const TargetRegisterClass *trc,
-                               SlotIndex i) const;
-
-    /// \brief Return true if the number of registers of type trc that may be
-    ///        needed at slot i is greater than the capacity of trc.
-    bool classOverCapacityAtSlot(const TargetRegisterClass *trc,
-                                 SlotIndex i) const;
-
-  private:
-
-    MachineFunction *mf;
-    MachineRegisterInfo *mri;
-    const TargetRegisterInfo *tri;
-    LiveIntervals *lis;
-
-    typedef std::map<const TargetRegisterClass*, unsigned> WorstMapLine;
-    typedef std::map<const TargetRegisterClass*, WorstMapLine> VRWorstMap;
-    VRWorstMap vrWorst;
-
-    typedef std::map<unsigned, WorstMapLine> PRWorstMap;
-    PRWorstMap prWorst;
-
-    typedef std::map<const TargetRegisterClass*, unsigned> CapacityMap;
-    CapacityMap capacityMap;
-
-    typedef std::map<const TargetRegisterClass*, unsigned> PressureMapLine;
-    typedef std::map<SlotIndex, PressureMapLine> PressureMap;
-    PressureMap pressureMap;
-
-    bool mapsPopulated;
-
-    /// \brief Initialise the 'worst' table.
-    void initWorst();
- 
-    /// \brief Initialise the 'capacity' table.
-    void initCapacity();
-
-    /// \brief Initialise/Reset the 'pressure' and live states tables.
-    void resetPressureAndLiveStates();
-  };
-
   /// \brief Helper class to process rendering options. Tries to be as lazy as
   ///        possible.
   class MFRenderingOptions {
@@ -125,7 +60,7 @@ namespace llvm {
 
     /// Initialise the rendering options.
     void setup(MachineFunction *mf, const TargetRegisterInfo *tri,
-               LiveIntervals *lis);
+               LiveIntervals *lis, const RenderMachineFunction *rmf);
 
     /// Clear translations of options to the current function.
     void clear();
@@ -160,9 +95,11 @@ namespace llvm {
 
     static std::set<std::pair<unsigned, unsigned> > intervalNumsToRender;
     typedef enum { ExplicitOnly     = 0,
-                   VirtPlusExplicit = 1,
-                   PhysPlusExplicit = 2,
-                   All              = 3 }
+                   AllPhys          = 1,
+                   VirtNoSpills     = 2,
+                   VirtSpills       = 4,
+                   AllVirt          = 6,
+                   All              = 7 }
       IntervalTypesToRender;
     static unsigned intervalTypesToRender;
 
@@ -180,6 +117,7 @@ namespace llvm {
     MachineFunction *mf;
     const TargetRegisterInfo *tri;
     LiveIntervals *lis;
+    const RenderMachineFunction *rmf;
 
     mutable bool regClassesTranslatedToCurrentFunction;
     mutable RegClassSet regClassSet;
@@ -192,6 +130,72 @@ namespace llvm {
     void translateIntervalNumbersToCurrentFunction() const;
   };
 
+  /// \brief Provide extra information about the physical and virtual registers
+  ///        in the function being compiled.
+  class TargetRegisterExtraInfo {
+  public:
+    TargetRegisterExtraInfo();
+
+    /// \brief Set up TargetRegisterExtraInfo with pointers to necessary
+    ///        sources of information.
+    void setup(MachineFunction *mf, MachineRegisterInfo *mri,
+               const TargetRegisterInfo *tri, LiveIntervals *lis);
+
+    /// \brief Recompute tables for changed function.
+    void reset(); 
+
+    /// \brief Free all tables in TargetRegisterExtraInfo.
+    void clear();
+
+    /// \brief Maximum number of registers from trc which alias reg.
+    unsigned getWorst(unsigned reg, const TargetRegisterClass *trc) const;
+
+    /// \brief Returns the number of allocable registers in trc.
+    unsigned getCapacity(const TargetRegisterClass *trc) const;
+
+    /// \brief Return the number of registers of class trc that may be
+    ///        needed at slot i.
+    unsigned getPressureAtSlot(const TargetRegisterClass *trc,
+                               SlotIndex i) const;
+
+    /// \brief Return true if the number of registers of type trc that may be
+    ///        needed at slot i is greater than the capacity of trc.
+    bool classOverCapacityAtSlot(const TargetRegisterClass *trc,
+                                 SlotIndex i) const;
+
+  private:
+
+    MachineFunction *mf;
+    MachineRegisterInfo *mri;
+    const TargetRegisterInfo *tri;
+    LiveIntervals *lis;
+
+    typedef std::map<const TargetRegisterClass*, unsigned> WorstMapLine;
+    typedef std::map<const TargetRegisterClass*, WorstMapLine> VRWorstMap;
+    VRWorstMap vrWorst;
+
+    typedef std::map<unsigned, WorstMapLine> PRWorstMap;
+    PRWorstMap prWorst;
+
+    typedef std::map<const TargetRegisterClass*, unsigned> CapacityMap;
+    CapacityMap capacityMap;
+
+    typedef std::map<const TargetRegisterClass*, unsigned> PressureMapLine;
+    typedef std::map<SlotIndex, PressureMapLine> PressureMap;
+    PressureMap pressureMap;
+
+    bool mapsPopulated;
+
+    /// \brief Initialise the 'worst' table.
+    void initWorst();
+ 
+    /// \brief Initialise the 'capacity' table.
+    void initCapacity();
+
+    /// \brief Initialise/Reset the 'pressure' and live states tables.
+    void resetPressureAndLiveStates();
+  };
+
   /// \brief Render MachineFunction objects and related information to a HTML
   ///        page.
   class RenderMachineFunction : public MachineFunctionPass {
@@ -206,6 +210,13 @@ namespace llvm {
 
     virtual void releaseMemory();
 
+    void rememberUseDefs(const LiveInterval *li);
+
+    void rememberSpills(const LiveInterval *li,
+                        const std::vector<LiveInterval*> &spills);
+
+    bool isSpill(const LiveInterval *li) const;
+
     /// \brief Render this machine function to HTML.
     /// 
     /// @param renderContextStr This parameter will be included in the top of
@@ -225,10 +236,8 @@ namespace llvm {
 
   private:
     class Spacer;
-
     friend raw_ostream& operator<<(raw_ostream &os, const Spacer &s);
 
-
     std::string fqn;
 
     MachineFunction *mf;
@@ -241,6 +250,8 @@ namespace llvm {
     TargetRegisterExtraInfo trei;
     MFRenderingOptions ro;
 
+    
+
     // Utilities.
     typedef enum { Dead, Defined, Used, AliveReg, AliveStack } LiveState;
     LiveState getLiveStateAt(const LiveInterval *li, SlotIndex i) const;
@@ -249,6 +260,17 @@ namespace llvm {
     PressureState getPressureStateAt(const TargetRegisterClass *trc,
                                      SlotIndex i) const;
 
+    typedef std::map<const LiveInterval*, std::set<const LiveInterval*> >
+      SpillIntervals;
+    SpillIntervals spillIntervals;
+
+    typedef std::map<const LiveInterval*, const LiveInterval*> SpillForMap;
+    SpillForMap spillFor;
+
+    typedef std::set<SlotIndex> SlotSet;
+    typedef std::map<const LiveInterval*, SlotSet> UseDefs;
+    UseDefs useDefs;
+
     // ---------- Rendering methods ----------
 
     /// For inserting spaces when pretty printing.