Added major new capabilities to scheduler (only BURR for now) to support physical register dependency. The BURR scheduler can now backtrace and duplicate instructions in order to avoid "expensive / impossible to copy" values (e.g. status flag EFLAGS for x86) from being clobbered.

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

1 files changed, 125 insertions, 57 deletions

diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
index 13465957b9..b77512228c 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp
@@ -27,6 +27,65 @@
 #include "llvm/Support/MathExtras.h"
 using namespace llvm;
 
+
+/// getPhysicalRegisterRegClass - Returns the Register Class of a physical
+/// register.
+static const TargetRegisterClass *getPhysicalRegisterRegClass(
+        const MRegisterInfo *MRI,
+        MVT::ValueType VT,
+        unsigned reg) {
+  assert(MRegisterInfo::isPhysicalRegister(reg) &&
+         "reg must be a physical register");
+  // Pick the register class of the right type that contains this physreg.
+  for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(),
+         E = MRI->regclass_end(); I != E; ++I)
+    if ((*I)->hasType(VT) && (*I)->contains(reg))
+      return *I;
+  assert(false && "Couldn't find the register class");
+  return 0;
+}
+
+
+/// CheckForPhysRegDependency - Check if the dependency between def and use of
+/// a specified operand is a physical register dependency. If so, returns the
+/// register and the cost of copying the register.
+static void CheckForPhysRegDependency(SDNode *Def, SDNode *Use, unsigned Op,
+                                      const MRegisterInfo *MRI, 
+                                      const TargetInstrInfo *TII,
+                                      unsigned &PhysReg, int &Cost) {
+  if (Op != 2 || Use->getOpcode() != ISD::CopyToReg)
+    return;
+
+  unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
+  if (MRegisterInfo::isVirtualRegister(Reg))
+    return;
+
+  unsigned ResNo = Use->getOperand(2).ResNo;
+  if (Def->isTargetOpcode()) {
+    const TargetInstrDescriptor &II = TII->get(Def->getTargetOpcode());
+    if (ResNo >= II.numDefs &&
+        II.ImplicitDefs[ResNo - II.numDefs] == Reg) {
+      PhysReg = Reg;
+      const TargetRegisterClass *RC =
+        getPhysicalRegisterRegClass(MRI, Def->getValueType(ResNo), Reg);
+      Cost = RC->getCopyCost();
+    }
+  }
+}
+
+SUnit *ScheduleDAG::Clone(SUnit *Old) {
+  SUnit *SU = NewSUnit(Old->Node);
+  for (unsigned i = 0, e = SU->FlaggedNodes.size(); i != e; ++i)
+    SU->FlaggedNodes.push_back(SU->FlaggedNodes[i]);
+  SU->InstanceNo = SUnitMap[Old->Node].size();
+  SU->Latency = Old->Latency;
+  SU->isTwoAddress = Old->isTwoAddress;
+  SU->isCommutable = Old->isCommutable;
+  SU->hasImplicitDefs = Old->hasImplicitDefs;
+  SUnitMap[Old->Node].push_back(SU);
+  return SU;
+}
+
 /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
 /// This SUnit graph is similar to the SelectionDAG, but represents flagged
 /// together nodes with a single SUnit.
@@ -44,7 +103,7 @@ void ScheduleDAG::BuildSchedUnits() {
       continue;
     
     // If this node has already been processed, stop now.
-    if (SUnitMap[NI]) continue;
+    if (SUnitMap[NI].size()) continue;
     
     SUnit *NodeSUnit = NewSUnit(NI);
     
@@ -59,7 +118,7 @@ void ScheduleDAG::BuildSchedUnits() {
       do {
         N = N->getOperand(N->getNumOperands()-1).Val;
         NodeSUnit->FlaggedNodes.push_back(N);
-        SUnitMap[N] = NodeSUnit;
+        SUnitMap[N].push_back(NodeSUnit);
       } while (N->getNumOperands() &&
                N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag);
       std::reverse(NodeSUnit->FlaggedNodes.begin(),
@@ -79,7 +138,7 @@ void ScheduleDAG::BuildSchedUnits() {
         if (FlagVal.isOperand(*UI)) {
           HasFlagUse = true;
           NodeSUnit->FlaggedNodes.push_back(N);
-          SUnitMap[N] = NodeSUnit;
+          SUnitMap[N].push_back(NodeSUnit);
           N = *UI;
           break;
         }
@@ -89,7 +148,7 @@ void ScheduleDAG::BuildSchedUnits() {
     // Now all flagged nodes are in FlaggedNodes and N is the bottom-most node.
     // Update the SUnit
     NodeSUnit->Node = N;
-    SUnitMap[N] = NodeSUnit;
+    SUnitMap[N].push_back(NodeSUnit);
     
     // Compute the latency for the node.  We use the sum of the latencies for
     // all nodes flagged together into this SUnit.
@@ -125,13 +184,16 @@ void ScheduleDAG::BuildSchedUnits() {
     
     if (MainNode->isTargetOpcode()) {
       unsigned Opc = MainNode->getTargetOpcode();
-      for (unsigned i = 0, ee = TII->getNumOperands(Opc); i != ee; ++i) {
-        if (TII->getOperandConstraint(Opc, i, TOI::TIED_TO) != -1) {
+      const TargetInstrDescriptor &TID = TII->get(Opc);
+      if (TID.ImplicitDefs)
+        SU->hasImplicitDefs = true;
+      for (unsigned i = 0; i != TID.numOperands; ++i) {
+        if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
           SU->isTwoAddress = true;
           break;
         }
       }
-      if (TII->isCommutableInstr(Opc))
+      if (TID.Flags & M_COMMUTABLE)
         SU->isCommutable = true;
     }
     
@@ -141,34 +203,25 @@ void ScheduleDAG::BuildSchedUnits() {
     
     for (unsigned n = 0, e = SU->FlaggedNodes.size(); n != e; ++n) {
       SDNode *N = SU->FlaggedNodes[n];
+      if (N->isTargetOpcode() && TII->getImplicitDefs(N->getTargetOpcode()))
+        SU->hasImplicitDefs = true;
       
       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
         SDNode *OpN = N->getOperand(i).Val;
         if (isPassiveNode(OpN)) continue;   // Not scheduled.
-        SUnit *OpSU = SUnitMap[OpN];
+        SUnit *OpSU = SUnitMap[OpN].front();
         assert(OpSU && "Node has no SUnit!");
         if (OpSU == SU) continue;           // In the same group.
 
         MVT::ValueType OpVT = N->getOperand(i).getValueType();
         assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!");
         bool isChain = OpVT == MVT::Other;
-        
-        if (SU->addPred(OpSU, isChain)) {
-          if (!isChain) {
-            SU->NumPreds++;
-            SU->NumPredsLeft++;
-          } else {
-            SU->NumChainPredsLeft++;
-          }
-        }
-        if (OpSU->addSucc(SU, isChain)) {
-          if (!isChain) {
-            OpSU->NumSuccs++;
-            OpSU->NumSuccsLeft++;
-          } else {
-            OpSU->NumChainSuccsLeft++;
-          }
-        }
+
+        unsigned PhysReg = 0;
+        int Cost = 1;
+        // Determine if this is a physical register dependency.
+        CheckForPhysRegDependency(OpN, N, i, MRI, TII, PhysReg, Cost);
+        SU->addPred(OpSU, isChain, false, PhysReg, Cost);
       }
     }
     
@@ -200,7 +253,7 @@ void ScheduleDAG::CalculateDepths() {
 
 void ScheduleDAG::CalculateHeights() {
   std::vector<std::pair<SUnit*, unsigned> > WorkList;
-  SUnit *Root = SUnitMap[DAG.getRoot().Val];
+  SUnit *Root = SUnitMap[DAG.getRoot().Val].front();
   WorkList.push_back(std::make_pair(Root, 0U));
 
   while (!WorkList.empty()) {
@@ -254,27 +307,14 @@ static const TargetRegisterClass *getInstrOperandRegClass(
          ? TII->getPointerRegClass() : MRI->getRegClass(toi.RegClass);
 }
 
-// Returns the Register Class of a physical register
-static const TargetRegisterClass *getPhysicalRegisterRegClass(
-        const MRegisterInfo *MRI,
-        MVT::ValueType VT,
-        unsigned reg) {
-  assert(MRegisterInfo::isPhysicalRegister(reg) &&
-         "reg must be a physical register");
-  // Pick the register class of the right type that contains this physreg.
-  for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(),
-         E = MRI->regclass_end(); I != E; ++I)
-    if ((*I)->hasType(VT) && (*I)->contains(reg))
-      return *I;
-  assert(false && "Couldn't find the register class");
-  return 0;
-}
-
-void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo, unsigned SrcReg,
+void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo,
+                                  unsigned InstanceNo, unsigned SrcReg,
                                   DenseMap<SDOperand, unsigned> &VRBaseMap) {
   unsigned VRBase = 0;
   if (MRegisterInfo::isVirtualRegister(SrcReg)) {
     // Just use the input register directly!
+    if (InstanceNo > 0)
+      VRBaseMap.erase(SDOperand(Node, ResNo));
     bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,ResNo),SrcReg));
     assert(isNew && "Node emitted out of order - early");
     return;
@@ -282,32 +322,54 @@ void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo, unsigned SrcReg,
 
   // If the node is only used by a CopyToReg and the dest reg is a vreg, use
   // the CopyToReg'd destination register instead of creating a new vreg.
+  bool MatchReg = true;
   for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
        UI != E; ++UI) {
     SDNode *Use = *UI;
+    bool Match = true;
     if (Use->getOpcode() == ISD::CopyToReg && 
         Use->getOperand(2).Val == Node &&
         Use->getOperand(2).ResNo == ResNo) {
       unsigned DestReg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
       if (MRegisterInfo::isVirtualRegister(DestReg)) {
         VRBase = DestReg;
-        break;
+        Match = false;
+      } else if (DestReg != SrcReg)
+        Match = false;
+    } else {
+      for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) {
+        SDOperand Op = Use->getOperand(i);
+        if (Op.Val != Node)
+          continue;
+        MVT::ValueType VT = Node->getValueType(Op.ResNo);
+        if (VT != MVT::Other && VT != MVT::Flag)
+          Match = false;
       }
     }
+    MatchReg &= Match;
+    if (VRBase)
+      break;
   }
 
-  // Figure out the register class to create for the destreg.
   const TargetRegisterClass *TRC = 0;
-  if (VRBase) {
+  // Figure out the register class to create for the destreg.
+  if (VRBase)
     TRC = RegMap->getRegClass(VRBase);
-  } else {
+  else
     TRC = getPhysicalRegisterRegClass(MRI, Node->getValueType(ResNo), SrcReg);
-
+    
+  // If all uses are reading from the src physical register and copying the
+  // register is either impossible or very expensive, then don't create a copy.
+  if (MatchReg && TRC->getCopyCost() < 0) {
+    VRBase = SrcReg;
+  } else {
     // Create the reg, emit the copy.
     VRBase = RegMap->createVirtualRegister(TRC);
+    MRI->copyRegToReg(*BB, BB->end(), VRBase, SrcReg, TRC);
   }
-  MRI->copyRegToReg(*BB, BB->end(), VRBase, SrcReg, TRC);
 
+  if (InstanceNo > 0)
+    VRBaseMap.erase(SDOperand(Node, ResNo));
   bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,ResNo), VRBase));
   assert(isNew && "Node emitted out of order - early");
 }
@@ -611,7 +673,7 @@ void ScheduleDAG::EmitSubregNode(SDNode *Node,
 
 /// EmitNode - Generate machine code for an node and needed dependencies.
 ///
-void ScheduleDAG::EmitNode(SDNode *Node, 
+void ScheduleDAG::EmitNode(SDNode *Node, unsigned InstanceNo,
                            DenseMap<SDOperand, unsigned> &VRBaseMap) {
   // If machine instruction
   if (Node->isTargetOpcode()) {
@@ -677,7 +739,7 @@ void ScheduleDAG::EmitNode(SDNode *Node,
       for (unsigned i = II.numDefs; i < NumResults; ++i) {
         unsigned Reg = II.ImplicitDefs[i - II.numDefs];
         if (Node->hasAnyUseOfValue(i))
-          EmitCopyFromReg(Node, i, Reg, VRBaseMap);
+          EmitCopyFromReg(Node, i, InstanceNo, Reg, VRBaseMap);
       }
     }
   } else {
@@ -713,7 +775,7 @@ void ScheduleDAG::EmitNode(SDNode *Node,
     }
     case ISD::CopyFromReg: {
       unsigned SrcReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
-      EmitCopyFromReg(Node, 0, SrcReg, VRBaseMap);
+      EmitCopyFromReg(Node, 0, InstanceNo, SrcReg, VRBaseMap);
       break;
     }
     case ISD::INLINEASM: {
@@ -802,9 +864,9 @@ void ScheduleDAG::EmitSchedule() {
   DenseMap<SDOperand, unsigned> VRBaseMap;
   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
     if (SUnit *SU = Sequence[i]) {
-      for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; j++)
-        EmitNode(SU->FlaggedNodes[j], VRBaseMap);
-      EmitNode(SU->Node, VRBaseMap);
+      for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; ++j)
+        EmitNode(SU->FlaggedNodes[j], SU->InstanceNo, VRBaseMap);
+      EmitNode(SU->Node, SU->InstanceNo, VRBaseMap);
     } else {
       // Null SUnit* is a noop.
       EmitNoop();
@@ -869,7 +931,10 @@ void SUnit::dumpAll(const SelectionDAG *G) const {
         cerr << "   ch  #";
       else
         cerr << "   val #";
-      cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")\n";
+      cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
+      if (I->isSpecial)
+        cerr << " *";
+      cerr << "\n";
     }
   }
   if (Succs.size() != 0) {
@@ -880,7 +945,10 @@ void SUnit::dumpAll(const SelectionDAG *G) const {
         cerr << "   ch  #";
       else
         cerr << "   val #";
-      cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")\n";
+      cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
+      if (I->isSpecial)
+        cerr << " *";
+      cerr << "\n";
     }
   }
   cerr << "\n";