Fix some register-alias-related bugs in the post-RA scheduler liveness

computation code. Also, avoid adding output-depenency edges when both
defs are dead, which frequently happens with EFLAGS defs.

Compute Depth and Height lazily, and always in terms of edge latency
values. For the schedulers that don't care about latency, edge latencies
are set to 1.

Eliminate Cycle and CycleBound, and LatencyPriorityQueue's Latencies array.
These are all subsumed by the Depth and Height fields.


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

3 files changed, 68 insertions, 28 deletions

diff --git a/include/llvm/CodeGen/LatencyPriorityQueue.h b/include/llvm/CodeGen/LatencyPriorityQueue.h
index f7eb3a62a2a9..71fae2aeabb5 100644
--- a/include/llvm/CodeGen/LatencyPriorityQueue.h
+++ b/include/llvm/CodeGen/LatencyPriorityQueue.h
@@ -34,10 +34,6 @@ namespace llvm {
     // SUnits - The SUnits for the current graph.
     std::vector<SUnit> *SUnits;
     
-    // Latencies - The latency (max of latency from this node to the bb exit)
-    // for each node.
-    std::vector<int> Latencies;
-
     /// NumNodesSolelyBlocking - This vector contains, for every node in the
     /// Queue, the number of nodes that the node is the sole unscheduled
     /// predecessor for.  This is used as a tie-breaker heuristic for better
@@ -51,29 +47,23 @@ public:
     
     void initNodes(std::vector<SUnit> &sunits) {
       SUnits = &sunits;
-      // Calculate node priorities.
-      CalculatePriorities();
+      NumNodesSolelyBlocking.resize(SUnits->size(), 0);
     }
 
     void addNode(const SUnit *SU) {
-      Latencies.resize(SUnits->size(), -1);
       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
-      CalcLatency(*SU);
     }
 
     void updateNode(const SUnit *SU) {
-      Latencies[SU->NodeNum] = -1;
-      CalcLatency(*SU);
     }
 
     void releaseState() {
       SUnits = 0;
-      Latencies.clear();
     }
     
     unsigned getLatency(unsigned NodeNum) const {
-      assert(NodeNum < Latencies.size());
-      return Latencies[NodeNum];
+      assert(NodeNum < (*SUnits).size());
+      return (*SUnits)[NodeNum].getHeight();
     }
     
     unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
@@ -114,8 +104,6 @@ public:
     void ScheduledNode(SUnit *Node);
 
 private:
-    void CalculatePriorities();
-    void CalcLatency(const SUnit &SU);
     void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
     SUnit *getSingleUnscheduledPred(SUnit *SU);
   };
diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h
index 2f6fd009284b..ee640e24a1e8 100644
--- a/include/llvm/CodeGen/ScheduleDAG.h
+++ b/include/llvm/CodeGen/ScheduleDAG.h
@@ -242,10 +242,12 @@ namespace llvm {
     bool isPending        : 1;          // True once pending.
     bool isAvailable      : 1;          // True once available.
     bool isScheduled      : 1;          // True once scheduled.
-    unsigned CycleBound;                // Upper/lower cycle to be scheduled at.
-    unsigned Cycle;                     // Once scheduled, the cycle of the op.
-    unsigned Depth;                     // Node depth;
-    unsigned Height;                    // Node height;
+  private:
+    bool isDepthCurrent   : 1;          // True if Depth is current.
+    bool isHeightCurrent  : 1;          // True if Height is current.
+    unsigned Depth;                     // Node depth.
+    unsigned Height;                    // Node height.
+  public:
     const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null.
     const TargetRegisterClass *CopySrcRC;
     
@@ -256,7 +258,8 @@ namespace llvm {
         Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
         isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
         isPending(false), isAvailable(false), isScheduled(false),
-        CycleBound(0), Cycle(~0u), Depth(0), Height(0),
+        isDepthCurrent(false), isHeightCurrent(false),
+        Depth(0), Height(0),
         CopyDstRC(NULL), CopySrcRC(NULL) {}
 
     /// SUnit - Construct an SUnit for post-regalloc scheduling to represent
@@ -266,7 +269,8 @@ namespace llvm {
         Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
         isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
         isPending(false), isAvailable(false), isScheduled(false),
-        CycleBound(0), Cycle(~0u), Depth(0), Height(0),
+        isDepthCurrent(false), isHeightCurrent(false),
+        Depth(0), Height(0),
         CopyDstRC(NULL), CopySrcRC(NULL) {}
 
     /// setNode - Assign the representative SDNode for this SUnit.
@@ -307,6 +311,41 @@ namespace llvm {
     /// the specified node.
     void removePred(const SDep &D);
 
+    /// getHeight - Return the height of this node, which is the length of the
+    /// maximum path down to any node with has no successors.
+    unsigned getDepth() const {
+      if (!isDepthCurrent) const_cast<SUnit *>(this)->ComputeDepth();
+      return Depth;
+    }
+
+    /// getHeight - Return the height of this node, which is the length of the
+    /// maximum path up to any node with has no predecessors.
+    unsigned getHeight() const {
+      if (!isHeightCurrent) const_cast<SUnit *>(this)->ComputeHeight();
+      return Height;
+    }
+
+    /// setDepthToAtLeast - If NewDepth is greater than this node's depth
+    /// value, set it to be the new depth value. This also recursively
+    /// marks successor nodes dirty.
+    void setDepthToAtLeast(unsigned NewDepth);
+
+    /// setDepthToAtLeast - If NewDepth is greater than this node's depth
+    /// value, set it to be the new height value. This also recursively
+    /// marks predecessor nodes dirty.
+    void setHeightToAtLeast(unsigned NewHeight);
+
+    /// setDepthDirty - Set a flag in this node to indicate that its
+    /// stored Depth value will require recomputation the next time
+    /// getDepth() is called.
+    void setDepthDirty();
+
+    /// setHeightDirty - Set a flag in this node to indicate that its
+    /// stored Height value will require recomputation the next time
+    /// getHeight() is called.
+    void setHeightDirty();
+
+    /// isPred - Test if node N is a predecessor of this node.
     bool isPred(SUnit *N) {
       for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
         if (Preds[i].getSUnit() == N)
@@ -314,6 +353,7 @@ namespace llvm {
       return false;
     }
     
+    /// isSucc - Test if node N is a successor of this node.
     bool isSucc(SUnit *N) {
       for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i)
         if (Succs[i].getSUnit() == N)
@@ -324,6 +364,10 @@ namespace llvm {
     void dump(const ScheduleDAG *G) const;
     void dumpAll(const ScheduleDAG *G) const;
     void print(raw_ostream &O, const ScheduleDAG *G) const;
+
+  private:
+    void ComputeDepth();
+    void ComputeHeight();
   };
 
   //===--------------------------------------------------------------------===//
@@ -397,12 +441,7 @@ namespace llvm {
 
     /// ComputeLatency - Compute node latency.
     ///
-    virtual void ComputeLatency(SUnit *SU) { SU->Latency = 1; }
-
-    /// CalculateDepths, CalculateHeights - Calculate node depth / height.
-    ///
-    void CalculateDepths();
-    void CalculateHeights();
+    virtual void ComputeLatency(SUnit *SU) = 0;
 
   protected:
     /// EmitNoop - Emit a noop instruction.
@@ -440,6 +479,11 @@ namespace llvm {
 
     void EmitCrossRCCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap);
 
+    /// ForceUnitLatencies - Return true if all scheduling edges should be given a
+    /// latency value of one.  The default is to return false; schedulers may
+    /// override this as needed.
+    virtual bool ForceUnitLatencies() const { return false; }
+
   private:
     /// EmitLiveInCopy - Emit a copy for a live in physical register. If the
     /// physical register has only a single copy use, then coalesced the copy
diff --git a/include/llvm/CodeGen/ScheduleDAGInstrs.h b/include/llvm/CodeGen/ScheduleDAGInstrs.h
index 2b6c1d3a559e..c74ef57674ff 100644
--- a/include/llvm/CodeGen/ScheduleDAGInstrs.h
+++ b/include/llvm/CodeGen/ScheduleDAGInstrs.h
@@ -18,10 +18,18 @@
 #include "llvm/CodeGen/ScheduleDAG.h"
 
 namespace llvm {
+  class MachineLoopInfo;
+  class MachineDominatorTree;
+
   class ScheduleDAGInstrs : public ScheduleDAG {
+    const MachineLoopInfo &MLI;
+    const MachineDominatorTree &MDT;
+
   public:
     ScheduleDAGInstrs(MachineBasicBlock *bb,
-                      const TargetMachine &tm);
+                      const TargetMachine &tm,
+                      const MachineLoopInfo &mli,
+                      const MachineDominatorTree &mdt);
 
     virtual ~ScheduleDAGInstrs() {}