1 files changed, 145 insertions, 23 deletions

diff --git a/include/llvm/CodeGen/RegisterPressure.h b/include/llvm/CodeGen/RegisterPressure.h
index 267018074677..a801d1d1eee9 100644
--- a/include/llvm/CodeGen/RegisterPressure.h
+++ b/include/llvm/CodeGen/RegisterPressure.h
@@ -22,7 +22,7 @@
 namespace llvm {
 
 class LiveIntervals;
-class LiveInterval;
+class LiveRange;
 class RegisterClassInfo;
 class MachineInstr;
 
@@ -89,16 +89,89 @@ 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;
+  }
+  // If PSetID is invalid, return UINT16_MAX to give it lowest priority.
+  unsigned getPSetOrMax() const { return (PSetID - 1) & UINT16_MAX; }
+
+  int getUnitInc() const { return UnitInc; }
+
+  void setUnitInc(int Inc) { UnitInc = Inc; }
+
+  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]; }
+  const_iterator begin() const { return &PressureChanges[0]; }
+  const_iterator end() const { return &PressureChanges[MaxPSets]; }
+
+  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) {}
+  ~PressureDiffs() { free(PDiffArray); }
+
+  void clear() { Size = 0; }
 
-  PressureElement(): PSetID(~0U), UnitIncrease(0) {}
-  PressureElement(unsigned id, int inc): PSetID(id), UnitIncrease(inc) {}
+  void init(unsigned N);
 
-  bool isValid() const { return PSetID != ~0U; }
+  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
@@ -116,11 +189,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.
@@ -131,7 +212,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);
@@ -183,6 +264,9 @@ class RegPressureTracker {
   /// or RegisterPressure. If requireIntervals is false, LIS are ignored.
   bool RequireIntervals;
 
+  /// True if UntiedDefs will be populated.
+  bool TrackUntiedDefs;
+
   /// Register pressure corresponds to liveness before this instruction
   /// iterator. It may point to the end of the block or a DebugValue rather than
   /// an instruction.
@@ -194,16 +278,26 @@ class RegPressureTracker {
   /// Set of live registers.
   LiveRegSet LiveRegs;
 
+  /// Set of vreg defs that start a live range.
+  SparseSet<unsigned, VirtReg2IndexFunctor> UntiedDefs;
+  /// Live-through pressure.
+  std::vector<unsigned> LiveThruPressure;
+
 public:
   RegPressureTracker(IntervalPressure &rp) :
-    MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(true) {}
+    MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(true),
+    TrackUntiedDefs(false) {}
 
   RegPressureTracker(RegionPressure &rp) :
-    MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(false) {}
+    MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(false),
+    TrackUntiedDefs(false) {}
+
+  void reset();
 
   void init(const MachineFunction *mf, const RegisterClassInfo *rci,
             const LiveIntervals *lis, const MachineBasicBlock *mbb,
-            MachineBasicBlock::const_iterator pos);
+            MachineBasicBlock::const_iterator pos,
+            bool ShouldTrackUntiedDefs = false);
 
   /// Force liveness of virtual registers or physical register
   /// units. Particularly useful to initialize the livein/out state of the
@@ -224,7 +318,7 @@ public:
   SlotIndex getCurrSlot() const;
 
   /// Recede across the previous instruction.
-  bool recede();
+  bool recede(SmallVectorImpl<unsigned> *LiveUses = 0, PressureDiff *PDiff = 0);
 
   /// Advance across the current instruction.
   bool advance();
@@ -232,6 +326,17 @@ public:
   /// Finalize the region boundaries and recored live ins and live outs.
   void closeRegion();
 
+  /// Initialize the LiveThru pressure set based on the untied defs found in
+  /// RPTracker.
+  void initLiveThru(const RegPressureTracker &RPTracker);
+
+  /// Copy an existing live thru pressure result.
+  void initLiveThru(ArrayRef<unsigned> PressureSet) {
+    LiveThruPressure.assign(PressureSet.begin(), PressureSet.end());
+  }
+
+  ArrayRef<unsigned> getLiveThru() const { return LiveThruPressure; }
+
   /// Get the resulting register pressure over the traversed region.
   /// This result is complete if either advance() or recede() has returned true,
   /// or if closeRegion() was explicitly invoked.
@@ -256,31 +361,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);
   }
 
@@ -304,10 +417,14 @@ public:
     return getDownwardPressure(MI, PressureResult, MaxPressureResult);
   }
 
+  bool hasUntiedDef(unsigned VirtReg) const {
+    return UntiedDefs.count(VirtReg);
+  }
+
   void dump() const;
 
 protected:
-  const LiveInterval *getInterval(unsigned Reg) const;
+  const LiveRange *getLiveRange(unsigned Reg) const;
 
   void increaseRegPressure(ArrayRef<unsigned> Regs);
   void decreaseRegPressure(ArrayRef<unsigned> Regs);
@@ -315,6 +432,11 @@ protected:
   void bumpUpwardPressure(const MachineInstr *MI);
   void bumpDownwardPressure(const MachineInstr *MI);
 };
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+void dumpRegSetPressure(ArrayRef<unsigned> SetPressure,
+                        const TargetRegisterInfo *TRI);
+#endif
 } // end namespace llvm
 
 #endif