mi-sched: Precompute a PressureDiff for each instruction, adjust for liveness later.

Created SUPressureDiffs array to hold the per node PDiff computed during DAG building.

Added a getUpwardPressureDelta API that will soon replace the old
one. Compute PressureDelta here from the precomputed PressureDiffs.

Updating for liveness will come next.

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

3 files changed, 115 insertions, 25 deletions

diff --git a/include/llvm/CodeGen/MachineScheduler.h b/include/llvm/CodeGen/MachineScheduler.h
index 3182440548..8f307f91a5 100644
--- a/include/llvm/CodeGen/MachineScheduler.h
+++ b/include/llvm/CodeGen/MachineScheduler.h
@@ -221,14 +221,17 @@ protected:
 
   MachineBasicBlock::iterator LiveRegionEnd;
 
-  /// Register pressure in this region computed by buildSchedGraph.
+  // Map each SU to its summary of pressure changes.
+  PressureDiffs SUPressureDiffs;
+
+  /// Register pressure in this region computed by initRegPressure.
   IntervalPressure RegPressure;
   RegPressureTracker RPTracker;
 
   /// List of pressure sets that exceed the target's pressure limit before
   /// scheduling, listed in increasing set ID order. Each pressure set is paired
   /// with its max pressure in the currently scheduled regions.
-  std::vector<PressureElement> RegionCriticalPSets;
+  std::vector<PressureChange> RegionCriticalPSets;
 
   /// The top of the unscheduled zone.
   MachineBasicBlock::iterator CurrentTop;
@@ -314,10 +317,14 @@ public:
   /// Get register pressure for the entire scheduling region before scheduling.
   const IntervalPressure &getRegPressure() const { return RegPressure; }
 
-  const std::vector<PressureElement> &getRegionCriticalPSets() const {
+  const std::vector<PressureChange> &getRegionCriticalPSets() const {
     return RegionCriticalPSets;
   }
 
+  PressureDiff &getPressureDiff(const SUnit *SU) {
+    return SUPressureDiffs[SU->NodeNum];
+  }
+
   const SUnit *getNextClusterPred() const { return NextClusterPred; }
 
   const SUnit *getNextClusterSucc() const { return NextClusterSucc; }
diff --git a/include/llvm/CodeGen/RegisterPressure.h b/include/llvm/CodeGen/RegisterPressure.h
index 8a0a8f3d93..b271f7f3d5 100644
--- a/include/llvm/CodeGen/RegisterPressure.h
+++ b/include/llvm/CodeGen/RegisterPressure.h
@@ -89,20 +89,85 @@ struct RegionPressure : RegisterPressure {
   void openBottom(MachineBasicBlock::const_iterator PrevBottom);
 };
 
-/// An element of pressure difference that identifies the pressure set and
-/// amount of increase or decrease in units of pressure.
-struct PressureElement {
-  unsigned PSetID;
-  int UnitIncrease;
+/// Capture a change in pressure for a single pressure set. UnitInc may be
+/// expressed in terms of upward or downward pressure depending on the client
+/// and will be dynamically adjusted for current liveness.
+///
+/// Pressure increments are tiny, typically 1-2 units, and this is only for
+/// heuristics, so we don't check UnitInc overflow. Instead, we may have a
+/// higher level assert that pressure is consistent within a region. We also
+/// effectively ignore dead defs which don't affect heuristics much.
+class PressureChange {
+  uint16_t PSetID; // ID+1. 0=Invalid.
+  int16_t  UnitInc;
+public:
+  PressureChange(): PSetID(0), UnitInc(0) {}
+  PressureChange(unsigned id): PSetID(id+1), UnitInc(0) {
+    assert(id < UINT16_MAX && "PSetID overflow.");
+  }
+
+  bool isValid() const { return PSetID > 0; }
+
+  unsigned getPSet() const {
+    assert(isValid() && "invalid PressureChange");
+    return PSetID - 1;
+  }
+
+  int getUnitInc() const { return UnitInc; }
+
+  void setUnitInc(int Inc) { UnitInc = Inc; }
+
+  // If PSetID is invalid, convert to INT_MAX to give it lowest priority.
+  int getRank() const { return (PSetID - 1) & INT_MAX; }
+
+  bool operator==(const PressureChange &RHS) const {
+    return PSetID == RHS.PSetID && UnitInc == RHS.UnitInc;
+  }
+};
+
+template <> struct isPodLike<PressureChange> {
+   static const bool value = true;
+};
+
+/// List of PressureChanges in order of increasing, unique PSetID.
+///
+/// Use a small fixed number, because we can fit more PressureChanges in an
+/// empty SmallVector than ever need to be tracked per register class. If more
+/// PSets are affected, then we only track the most constrained.
+class PressureDiff {
+  // The initial design was for MaxPSets=4, but that requires PSet partitions,
+  // which are not yet implemented. (PSet partitions are equivalent PSets given
+  // the register classes actually in use within the scheduling region.)
+  enum { MaxPSets = 16 };
+
+  PressureChange PressureChanges[MaxPSets];
+public:
+  typedef PressureChange* iterator;
+  typedef const PressureChange* const_iterator;
+  iterator begin() { return &PressureChanges[0]; }
+  iterator end() { return &PressureChanges[MaxPSets]; }
 
-  PressureElement(): PSetID(~0U), UnitIncrease(0) {}
-  PressureElement(unsigned id, int inc): PSetID(id), UnitIncrease(inc) {}
+  void addPressureChange(unsigned RegUnit, bool IsDec,
+                         const MachineRegisterInfo *MRI);
+};
+
+/// Array of PressureDiffs.
+class PressureDiffs {
+  PressureDiff *PDiffArray;
+  unsigned Size;
+  unsigned Max;
+public:
+  PressureDiffs(): PDiffArray(0), Size(0), Max(0) {}
 
-  bool isValid() const { return PSetID != ~0U; }
+  void init(unsigned N);
 
-  // If signed PSetID is negative, it is invalid; convert it to INT_MAX to give
-  // it lowest priority.
-  int PSetRank() const { return PSetID & INT_MAX; }
+  PressureDiff &operator[](unsigned Idx) {
+    assert(Idx < Size && "PressureDiff index out of bounds");
+    return PDiffArray[Idx];
+  }
+  const PressureDiff &operator[](unsigned Idx) const {
+    return const_cast<PressureDiffs*>(this)->operator[](Idx);
+  }
 };
 
 /// Store the effects of a change in pressure on things that MI scheduler cares
@@ -120,11 +185,19 @@ struct PressureElement {
 /// CurrentMax records the largest increase in the tracker's max pressure that
 /// exceeds the current limit for some pressure set determined by the client.
 struct RegPressureDelta {
-  PressureElement Excess;
-  PressureElement CriticalMax;
-  PressureElement CurrentMax;
+  PressureChange Excess;
+  PressureChange CriticalMax;
+  PressureChange CurrentMax;
 
   RegPressureDelta() {}
+
+  bool operator==(const RegPressureDelta &RHS) const {
+    return Excess == RHS.Excess && CriticalMax == RHS.CriticalMax
+      && CurrentMax == RHS.CurrentMax;
+  }
+  bool operator!=(const RegPressureDelta &RHS) const {
+    return !operator==(RHS);
+  }
 };
 
 /// \brief A set of live virtual registers and physical register units.
@@ -135,7 +208,7 @@ struct LiveRegSet {
   SparseSet<unsigned> PhysRegs;
   SparseSet<unsigned, VirtReg2IndexFunctor> VirtRegs;
 
-  bool contains(unsigned Reg) {
+  bool contains(unsigned Reg) const {
     if (TargetRegisterInfo::isVirtualRegister(Reg))
       return VirtRegs.count(Reg);
     return PhysRegs.count(Reg);
@@ -239,7 +312,7 @@ public:
   SlotIndex getCurrSlot() const;
 
   /// Recede across the previous instruction.
-  bool recede();
+  bool recede(PressureDiff *PDiff = 0);
 
   /// Advance across the current instruction.
   bool advance();
@@ -282,31 +355,39 @@ public:
   /// limit based on the tracker's current pressure, and record the number of
   /// excess register units of that pressure set introduced by this instruction.
   void getMaxUpwardPressureDelta(const MachineInstr *MI,
+                                 PressureDiff *PDiff,
                                  RegPressureDelta &Delta,
-                                 ArrayRef<PressureElement> CriticalPSets,
+                                 ArrayRef<PressureChange> CriticalPSets,
                                  ArrayRef<unsigned> MaxPressureLimit);
 
+  void getUpwardPressureDelta(const MachineInstr *MI,
+                              /*const*/ PressureDiff &PDiff,
+                              RegPressureDelta &Delta,
+                              ArrayRef<PressureChange> CriticalPSets,
+                              ArrayRef<unsigned> MaxPressureLimit) const;
+
   /// Consider the pressure increase caused by traversing this instruction
   /// top-down. Find the pressure set with the most change beyond its pressure
   /// limit based on the tracker's current pressure, and record the number of
   /// excess register units of that pressure set introduced by this instruction.
   void getMaxDownwardPressureDelta(const MachineInstr *MI,
                                    RegPressureDelta &Delta,
-                                   ArrayRef<PressureElement> CriticalPSets,
+                                   ArrayRef<PressureChange> CriticalPSets,
                                    ArrayRef<unsigned> MaxPressureLimit);
 
   /// Find the pressure set with the most change beyond its pressure limit after
   /// traversing this instruction either upward or downward depending on the
   /// closed end of the current region.
-  void getMaxPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta,
-                           ArrayRef<PressureElement> CriticalPSets,
+  void getMaxPressureDelta(const MachineInstr *MI,
+                           RegPressureDelta &Delta,
+                           ArrayRef<PressureChange> CriticalPSets,
                            ArrayRef<unsigned> MaxPressureLimit) {
     if (isTopClosed())
       return getMaxDownwardPressureDelta(MI, Delta, CriticalPSets,
                                          MaxPressureLimit);
 
     assert(isBottomClosed() && "Uninitialized pressure tracker");
-    return getMaxUpwardPressureDelta(MI, Delta, CriticalPSets,
+    return getMaxUpwardPressureDelta(MI, 0, Delta, CriticalPSets,
                                      MaxPressureLimit);
   }
 
diff --git a/include/llvm/CodeGen/ScheduleDAGInstrs.h b/include/llvm/CodeGen/ScheduleDAGInstrs.h
index 4a447e2f4a..999f2d3377 100644
--- a/include/llvm/CodeGen/ScheduleDAGInstrs.h
+++ b/include/llvm/CodeGen/ScheduleDAGInstrs.h
@@ -28,6 +28,7 @@ namespace llvm {
   class MachineDominatorTree;
   class LiveIntervals;
   class RegPressureTracker;
+  class PressureDiffs;
 
   /// An individual mapping from virtual register number to SUnit.
   struct VReg2SUnit {
@@ -195,7 +196,8 @@ namespace llvm {
 
     /// buildSchedGraph - Build SUnits from the MachineBasicBlock that we are
     /// input.
-    void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker = 0);
+    void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker = 0,
+                         PressureDiffs *PDiffs = 0);
 
     /// addSchedBarrierDeps - Add dependencies from instructions in the current
     /// list of instructions being scheduled to scheduling barrier. We want to