Added a check in the preRA scheduler for potential interference on a

induction variable. The preRA scheduler is unaware of induction vars,
so we look for potential "virtual register cycles" instead.

Fixes <rdar://problem/8946719> Bad scheduling prevents coalescing


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

3 files changed, 107 insertions, 4 deletions

diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
index f5a5db8..b2e9c15 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
@@ -77,6 +77,9 @@ static cl::opt<bool> DisableSchedRegPressure(
 static cl::opt<bool> DisableSchedLiveUses(
   "disable-sched-live-uses", cl::Hidden, cl::init(true),
   cl::desc("Disable live use priority in sched=list-ilp"));
+static cl::opt<bool> DisableSchedVRegCycle(
+  "disable-sched-vrcycle", cl::Hidden, cl::init(false),
+  cl::desc("Disable virtual register cycle interference checks"));
 static cl::opt<bool> DisableSchedStalls(
   "disable-sched-stalls", cl::Hidden, cl::init(true),
   cl::desc("Disable no-stall priority in sched=list-ilp"));
@@ -2045,6 +2048,44 @@ static bool UnitsSharePred(const SUnit *left, const SUnit *right) {
   return false;
 }
 
+// Return true if the virtual register defined by VRCycleSU may interfere with
+// VRUseSU.
+//
+// Note: We may consider two SU's that use the same value live into a loop as
+// interferng even though the value is not an induction variable. This is an
+// unfortunate consequence of scheduling on the selection DAG.
+static bool checkVRegCycleInterference(const SUnit *VRCycleSU,
+                                       const SUnit *VRUseSU) {
+  for (SUnit::const_pred_iterator I = VRCycleSU->Preds.begin(),
+         E = VRCycleSU->Preds.end(); I != E; ++I) {
+    if (I->isCtrl()) continue;  // ignore chain preds
+    SDNode *InNode = I->getSUnit()->getNode();
+    if (!InNode || InNode->getOpcode() != ISD::CopyFromReg)
+      continue;
+    for (SUnit::const_pred_iterator II = VRUseSU->Preds.begin(),
+           EE = VRUseSU->Preds.end(); II != EE; ++II) {
+      if (II->getSUnit() == I->getSUnit())
+        return true;
+    }
+  }
+  return false;
+}
+
+// Compare the VRegCycle properties of the nodes.
+// Return -1 if left has higher priority, 1 if right has higher priority.
+// Return 0 if priority is equivalent.
+static int BUCompareVRegCycle(const SUnit *left, const SUnit *right) {
+  if (left->isVRegCycle && !right->isVRegCycle) {
+    if (checkVRegCycleInterference(left, right))
+      return -1;
+  }
+  else if (!left->isVRegCycle && right->isVRegCycle) {
+    if (checkVRegCycleInterference(right, left))
+      return 1;
+  }
+  return 0;
+}
+
 // Check for either a dependence (latency) or resource (hazard) stall.
 //
 // Note: The ScheduleHazardRecognizer interface requires a non-const SU.
@@ -2232,11 +2273,15 @@ bool hybrid_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
           << left->NodeNum << ")\n");
     return false;
   }
-  else if (!LHigh && !RHigh) {
-    int result = BUCompareLatency(left, right, true /*checkPref*/, SPQ);
-    if (result != 0)
-      return result > 0;
+  int result = 0;
+  if (!DisableSchedVRegCycle) {
+    result = BUCompareVRegCycle(left, right);
   }
+  if (result == 0 && !LHigh && !RHigh) {
+    result = BUCompareLatency(left, right, true /*checkPref*/, SPQ);
+  }
+  if (result != 0)
+    return result > 0;
   return BURRSort(left, right, SPQ);
 }
 
@@ -2302,6 +2347,12 @@ bool ilp_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
     if (RReduce && !LReduce) return true;
   }
 
+  if (!DisableSchedVRegCycle) {
+    int result = BUCompareVRegCycle(left, right);
+    if (result != 0)
+      return result > 0;
+  }
+
   if (!DisableSchedLiveUses && (LLiveUses != RLiveUses)) {
     DEBUG(dbgs() << "Live uses SU(" << left->NodeNum << "): " << LLiveUses
           << " != SU(" << right->NodeNum << "): " << RLiveUses << "\n");
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp
index 202f7ab..24a1937 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp
@@ -81,6 +81,7 @@ SUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) {
   SUnit *SU = NewSUnit(Old->getNode());
   SU->OrigNode = Old->OrigNode;
   SU->Latency = Old->Latency;
+  SU->isVRegCycle = Old->isVRegCycle;
   SU->isCall = Old->isCall;
   SU->isTwoAddress = Old->isTwoAddress;
   SU->isCommutable = Old->isCommutable;
@@ -341,6 +342,10 @@ void ScheduleDAGSDNodes::BuildSchedUnits() {
     assert(N->getNodeId() == -1 && "Node already inserted!");
     N->setNodeId(NodeSUnit->NodeNum);
 
+    // Set isVRegCycle if the node operands are live into and value is live out
+    // of a single block loop.
+    InitVRegCycleFlag(NodeSUnit);
+
     // Compute NumRegDefsLeft. This must be done before AddSchedEdges.
     InitNumRegDefsLeft(NodeSUnit);
 
@@ -507,6 +512,47 @@ void ScheduleDAGSDNodes::RegDefIter::Advance() {
   }
 }
 
+// Set isVRegCycle if this node's single use is CopyToReg and its only active
+// data operands are CopyFromReg.
+//
+// This is only relevant for single-block loops, in which case the VRegCycle
+// node is likely an induction variable in which the operand and target virtual
+// registers should be coalesced (e.g. pre/post increment values). Setting the
+// isVRegCycle flag helps the scheduler prioritize other uses of the same
+// CopyFromReg so that this node becomes the virtual register "kill". This
+// avoids interference between the values live in and out of the block and
+// eliminates a copy inside the loop.
+void ScheduleDAGSDNodes::InitVRegCycleFlag(SUnit *SU) {
+  if (!BB->isSuccessor(BB))
+    return;
+
+  SDNode *N = SU->getNode();
+  if (N->getGluedNode())
+    return;
+
+  if (!N->hasOneUse() || N->use_begin()->getOpcode() != ISD::CopyToReg)
+    return;
+
+  bool FoundLiveIn = false;
+  for (SDNode::op_iterator OI = N->op_begin(), E = N->op_end(); OI != E; ++OI) {
+    EVT OpVT = OI->getValueType();
+    assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!");
+
+    if (OpVT == MVT::Other)
+      continue; // ignore chain operands
+
+    if (isPassiveNode(OI->getNode()))
+      continue; // ignore constants and such
+
+    if (OI->getNode()->getOpcode() != ISD::CopyFromReg)
+      return;
+
+    FoundLiveIn = true;
+  }
+  if (FoundLiveIn)
+    SU->isVRegCycle = true;
+}
+
 void ScheduleDAGSDNodes::InitNumRegDefsLeft(SUnit *SU) {
   assert(SU->NumRegDefsLeft == 0 && "expect a new node");
   for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) {
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h
index cc7310e..b5f68f3 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h
@@ -80,6 +80,12 @@ namespace llvm {
     /// flagged together nodes with a single SUnit.
     virtual void BuildSchedGraph(AliasAnalysis *AA);
 
+    /// InitVRegCycleFlag - Set isVRegCycle if this node's single use is
+    /// CopyToReg and its only active data operands are CopyFromReg within a
+    /// single block loop.
+    ///
+    void InitVRegCycleFlag(SUnit *SU);
+
     /// InitNumRegDefsLeft - Determine the # of regs defined by this node.
     ///
     void InitNumRegDefsLeft(SUnit *SU);