A single MachineInstr operand may now be both a def and a use,

so additional dep. edges have to be added.
This was needed to correctly handle conditional move instructions!
MachineCodeForBasicBlock is now an annotation on BasicBlock.
Renamed "earliestForNode" to "earliestReadyTimeForNode".


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

5 files changed, 91 insertions, 102 deletions

diff --git a/lib/CodeGen/InstrSched/InstrScheduling.cpp b/lib/CodeGen/InstrSched/InstrScheduling.cpp
index 46c1c15998..6ea37247d0 100644
--- a/lib/CodeGen/InstrSched/InstrScheduling.cpp
+++ b/lib/CodeGen/InstrSched/InstrScheduling.cpp
@@ -8,6 +8,7 @@
 #include "SchedPriorities.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineCodeForInstruction.h"
+#include "llvm/CodeGen/MachineCodeForBasicBlock.h"
 #include "llvm/CodeGen/MachineCodeForMethod.h"
 #include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.h" // FIXME: Remove when modularized better
 #include "llvm/Target/TargetMachine.h"
@@ -631,7 +632,7 @@ AssignInstructionsToSlots(class SchedulingManager& S, unsigned maxIssue)
 static void
 RecordSchedule(const BasicBlock* bb, const SchedulingManager& S)
 {
-  MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec();
+  MachineCodeForBasicBlock& mvec = MachineCodeForBasicBlock::get(bb);
   const MachineInstrInfo& mii = S.schedInfo.getInstrInfo();
   
 #ifndef NDEBUG
@@ -1220,7 +1221,7 @@ ReplaceNopsWithUsefulInstr(SchedulingManager& S,
   // fill delay slots, otherwise, just discard them.
   //  
   unsigned int firstDelaySlotIdx = node->getOrigIndexInBB() + 1;
-  MachineCodeForBasicBlock& bbMvec  = node->getBB()->getMachineInstrVec();
+  MachineCodeForBasicBlock& bbMvec = MachineCodeForBasicBlock::get(node->getBB());
   assert(bbMvec[firstDelaySlotIdx - 1] == brInstr &&
          "Incorrect instr. index in basic block for brInstr");
   
@@ -1313,7 +1314,7 @@ ChooseInstructionsForDelaySlots(SchedulingManager& S,
   // Simply passing in an empty delayNodeVec will have this effect.
   // 
   delayNodeVec.clear();
-  const MachineCodeForBasicBlock& bbMvec = bb->getMachineInstrVec();
+  const MachineCodeForBasicBlock& bbMvec = MachineCodeForBasicBlock::get(bb);
   for (unsigned i=0; i < bbMvec.size(); i++)
     if (bbMvec[i] != brInstr &&
         mii.getNumDelaySlots(bbMvec[i]->getOpCode()) > 0)
diff --git a/lib/CodeGen/InstrSched/SchedGraph.cpp b/lib/CodeGen/InstrSched/SchedGraph.cpp
index 3cd6cfafaf..96962ced14 100644
--- a/lib/CodeGen/InstrSched/SchedGraph.cpp
+++ b/lib/CodeGen/InstrSched/SchedGraph.cpp
@@ -15,6 +15,7 @@
 #include "SchedGraph.h"
 #include "llvm/CodeGen/InstrSelection.h"
 #include "llvm/CodeGen/MachineCodeForInstruction.h"
+#include "llvm/CodeGen/MachineCodeForBasicBlock.h"
 #include "llvm/Target/MachineRegInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/BasicBlock.h"
@@ -393,7 +394,7 @@ SchedGraph::addCDEdges(const TerminatorInst* term,
   // all preceding instructions in the basic block.  Use 0 latency again.
   // 
   const BasicBlock* bb = firstBrNode->getBB();
-  const MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec();
+  const MachineCodeForBasicBlock& mvec = MachineCodeForBasicBlock::get(bb);
   for (unsigned i=0, N=mvec.size(); i < N; i++) 
     {
       if (mvec[i] == termMvec[first]) // reached the first branch
@@ -550,7 +551,9 @@ SchedGraph::addMachineRegEdges(RegToRefVecMap& regToRefVecMap,
 	  SchedGraphNode* node = regRefVec[i].first;
 	  unsigned int opNum   = regRefVec[i].second;
 	  bool isDef = node->getMachineInstr()->operandIsDefined(opNum);
-	        
+	  bool isDefAndUse =
+            node->getMachineInstr()->operandIsDefinedAndUsed(opNum);
+          
           for (unsigned p=0; p < i; ++p)
             {
               SchedGraphNode* prevNode = regRefVec[p].first;
@@ -559,14 +562,22 @@ SchedGraph::addMachineRegEdges(RegToRefVecMap& regToRefVecMap,
                   unsigned int prevOpNum = regRefVec[p].second;
                   bool prevIsDef =
                     prevNode->getMachineInstr()->operandIsDefined(prevOpNum);
-                  
+                  bool prevIsDefAndUse =
+                    prevNode->getMachineInstr()->operandIsDefinedAndUsed(prevOpNum);
                   if (isDef)
-                    new SchedGraphEdge(prevNode, node, regNum,
-                                       (prevIsDef)? SchedGraphEdge::OutputDep
-                                                  : SchedGraphEdge::AntiDep);
-                  else if (prevIsDef)
-                    new SchedGraphEdge(prevNode, node, regNum,
-                                       SchedGraphEdge::TrueDep);
+                    {
+                      if (prevIsDef)
+                        new SchedGraphEdge(prevNode, node, regNum,
+                                           SchedGraphEdge::OutputDep);
+                      if (!prevIsDef || prevIsDefAndUse)
+                        new SchedGraphEdge(prevNode, node, regNum,
+                                           SchedGraphEdge::AntiDep);
+                    }
+                  
+                  if (prevIsDef)
+                    if (!isDef || isDefAndUse)
+                      new SchedGraphEdge(prevNode, node, regNum,
+                                         SchedGraphEdge::TrueDep);
                 }
             }
         }
@@ -574,13 +585,20 @@ SchedGraph::addMachineRegEdges(RegToRefVecMap& regToRefVecMap,
 }
 
 
+// Adds dependences to/from refNode from/to all other defs
+// in the basic block.  refNode may be a use, a def, or both.
+// We do not consider other uses because we are not building use-use deps.
+// 
 void
 SchedGraph::addEdgesForValue(SchedGraphNode* refNode,
                              const RefVec& defVec,
                              const Value* defValue,
                              bool  refNodeIsDef,
+                             bool  refNodeIsDefAndUse,
                              const TargetMachine& target)
 {
+  bool refNodeIsUse = !refNodeIsDef || refNodeIsDefAndUse;
+  
   // Add true or output dep edges from all def nodes before refNode in BB.
   // Add anti or output dep edges to all def nodes after refNode.
   for (RefVec::const_iterator I=defVec.begin(), E=defVec.end(); I != E; ++I)
@@ -589,15 +607,23 @@ SchedGraph::addEdgesForValue(SchedGraphNode* refNode,
         continue;                       // Dont add any self-loops
       
       if ((*I).first->getOrigIndexInBB() < refNode->getOrigIndexInBB())
-        // (*).first is before refNode
-        (void) new SchedGraphEdge((*I).first, refNode, defValue,
-                                  (refNodeIsDef)? SchedGraphEdge::OutputDep
-                                                : SchedGraphEdge::TrueDep);
+        { // (*).first is before refNode
+          if (refNodeIsDef)
+            (void) new SchedGraphEdge((*I).first, refNode, defValue,
+                                      SchedGraphEdge::OutputDep);
+          if (refNodeIsUse)
+            (void) new SchedGraphEdge((*I).first, refNode, defValue,
+                                      SchedGraphEdge::TrueDep);
+        }
       else
-        // (*).first is after refNode
-        (void) new SchedGraphEdge(refNode, (*I).first, defValue,
-                                  (refNodeIsDef)? SchedGraphEdge::OutputDep
-                                                : SchedGraphEdge::AntiDep);
+        { // (*).first is after refNode
+          if (refNodeIsDef)
+            (void) new SchedGraphEdge(refNode, (*I).first, defValue,
+                                      SchedGraphEdge::OutputDep);
+          if (refNodeIsUse)
+            (void) new SchedGraphEdge(refNode, (*I).first, defValue,
+                                      SchedGraphEdge::AntiDep);
+        }
     }
 }
 
@@ -626,7 +652,8 @@ SchedGraph::addEdgesForInstruction(const MachineInstr& minstr,
               ValueToDefVecMap::const_iterator I = valueToDefVecMap.find(srcI);
               if (I != valueToDefVecMap.end())
                 addEdgesForValue(node, (*I).second, mop.getVRegValue(),
-                                 minstr.operandIsDefined(i), target);
+                                 minstr.operandIsDefined(i),
+                                 minstr.operandIsDefinedAndUsed(i), target);
             }
 	  break;
 	  
@@ -649,73 +676,20 @@ SchedGraph::addEdgesForInstruction(const MachineInstr& minstr,
   // value of a Ret instruction.
   // 
   for (unsigned i=0, N=minstr.getNumImplicitRefs(); i < N; ++i)
-    if (! minstr.implicitRefIsDefined(i))
+    if (! minstr.implicitRefIsDefined(i) ||
+        minstr.implicitRefIsDefinedAndUsed(i))
       if (const Instruction* srcI =
           dyn_cast_or_null<Instruction>(minstr.getImplicitRef(i)))
         {
           ValueToDefVecMap::const_iterator I = valueToDefVecMap.find(srcI);
           if (I != valueToDefVecMap.end())
             addEdgesForValue(node, (*I).second, minstr.getImplicitRef(i),
-                             minstr.implicitRefIsDefined(i), target);
+                             minstr.implicitRefIsDefined(i),
+                             minstr.implicitRefIsDefinedAndUsed(i), target);
         }
 }
 
 
-#undef NEED_SEPARATE_NONSSA_EDGES_CODE
-#ifdef NEED_SEPARATE_NONSSA_EDGES_CODE
-void
-SchedGraph::addNonSSAEdgesForValue(const Instruction* instr,
-                                   const TargetMachine& target)
-{
-  if (isa<PHINode>(instr))
-    return;
-  
-  MachineCodeForVMInstr& mvec = instr->getMachineInstrVec();
-  const MachineInstrInfo& mii = target.getInstrInfo();
-  RefVec refVec;
-  
-  for (unsigned i=0, N=mvec.size(); i < N; i++)
-    for (int o=0, N = mii.getNumOperands(mvec[i]->getOpCode()); o < N; o++)
-      {
-	const MachineOperand& mop = mvec[i]->getOperand(o); 
-	
-	if ((mop.getOperandType() == MachineOperand::MO_VirtualRegister ||
-             mop.getOperandType() == MachineOperand::MO_CCRegister)
-	    && mop.getVRegValue() == (Value*) instr)
-          {
-	    // this operand is a definition or use of value `instr'
-	    SchedGraphNode* node = this->getGraphNodeForInstr(mvec[i]);
-            assert(node && "No node for machine instruction in this BB?");
-            refVec.push_back(std::make_pair(node, o));
-          }
-      }
-  
-  // refVec is ordered by control flow order of the machine instructions
-  for (unsigned i=0; i < refVec.size(); ++i)
-    {
-      SchedGraphNode* node = refVec[i].first;
-      unsigned int   opNum = refVec[i].second;
-      bool isDef = node->getMachineInstr()->operandIsDefined(opNum);
-      
-      if (isDef)
-        // add output and/or anti deps to this definition
-        for (unsigned p=0; p < i; ++p)
-          {
-            SchedGraphNode* prevNode = refVec[p].first;
-            if (prevNode != node)
-              {
-                bool prevIsDef = prevNode->getMachineInstr()->
-                  operandIsDefined(refVec[p].second);
-                new SchedGraphEdge(prevNode, node, SchedGraphEdge::ValueDep,
-                                   (prevIsDef)? SchedGraphEdge::OutputDep
-                                              : SchedGraphEdge::AntiDep);
-              }
-          }
-    }
-}
-#endif //NEED_SEPARATE_NONSSA_EDGES_CODE
-
-
 void
 SchedGraph::findDefUseInfoAtInstr(const TargetMachine& target,
                                   SchedGraphNode* node,
@@ -786,7 +760,7 @@ SchedGraph::buildNodesforBB(const TargetMachine& target,
   
   // Build graph nodes for each VM instruction and gather def/use info.
   // Do both those together in a single pass over all machine instructions.
-  const MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec();
+  const MachineCodeForBasicBlock& mvec = MachineCodeForBasicBlock::get(bb);
   for (unsigned i=0; i < mvec.size(); i++)
     if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
       {
@@ -822,7 +796,7 @@ SchedGraph::buildNodesforBB(const TargetMachine& target,
         
         // Find the machine instruction that makes a copy of inval to (*PI).
         // This must be in the current basic block (bb).
-        const MachineCodeForVMInstr& mvec = (*PI)->getMachineInstrVec();
+        const MachineCodeForVMInstr& mvec = MachineCodeForBasicBlock::get(*PI);
         const MachineInstr* theCopy = NULL;
         for (unsigned i=0; i < mvec.size() && theCopy == NULL; i++)
           if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
@@ -830,13 +804,17 @@ SchedGraph::buildNodesforBB(const TargetMachine& target,
             for (int o=0, N=(int) mvec[i]->getNumOperands(); o < N; o++)
               {
                 const MachineOperand& mop = mvec[i]->getOperand(o);
+                
                 if (mvec[i]->operandIsDefined(o))
                   assert(mop.getVRegValue() == (*PI) && "dest shd be my Phi");
-                else if (mop.getVRegValue() == inVal)
-                  { // found the copy!
-                    theCopy = mvec[i];
-                    break;
-                  }
+                
+                if (! mvec[i]->operandIsDefined(o) ||
+                    NOT NEEDED? mvec[i]->operandIsDefinedAndUsed(o))
+                  if (mop.getVRegValue() == inVal)
+                    { // found the copy!
+                      theCopy = mvec[i];
+                      break;
+                    }
               }
         
         // Found the dang instruction.  Now create a node and do the rest...
@@ -911,7 +889,7 @@ SchedGraph::buildGraph(const TargetMachine& target)
   // 
   //----------------------------------------------------------------
       
-  MachineCodeForBasicBlock& bbMvec = bb->getMachineInstrVec();
+  MachineCodeForBasicBlock& bbMvec = MachineCodeForBasicBlock::get(bb);
   
   // First, add edges to the terminator instruction of the basic block.
   this->addCDEdges(bb->getTerminator(), target);
diff --git a/lib/CodeGen/InstrSched/SchedGraph.h b/lib/CodeGen/InstrSched/SchedGraph.h
index 441a46c0e5..aa258813c3 100644
--- a/lib/CodeGen/InstrSched/SchedGraph.h
+++ b/lib/CodeGen/InstrSched/SchedGraph.h
@@ -327,6 +327,7 @@ private:
                                          const RefVec& defVec,
                                          const Value* defValue,
                                          bool  refNodeIsDef,
+                                         bool  refNodeIsDefAndUse,
 					 const TargetMachine& target);
   
   void		addDummyEdges		();
diff --git a/lib/CodeGen/InstrSched/SchedPriorities.cpp b/lib/CodeGen/InstrSched/SchedPriorities.cpp
index aba49bd54c..8a1c9a5348 100644
--- a/lib/CodeGen/InstrSched/SchedPriorities.cpp
+++ b/lib/CodeGen/InstrSched/SchedPriorities.cpp
@@ -28,9 +28,10 @@ SchedPriorities::SchedPriorities(const Function *, const SchedGraph *G,
                                  FunctionLiveVarInfo &LVI)
   : curTime(0), graph(G), methodLiveVarInfo(LVI),
     nodeDelayVec(G->getNumNodes(), INVALID_LATENCY), // make errors obvious
-    earliestForNode(G->getNumNodes(), 0),
+    earliestReadyTimeForNode(G->getNumNodes(), 0),
     earliestReadyTime(0),
-    nextToTry(candsAsHeap.begin()) {
+    nextToTry(candsAsHeap.begin())
+{
   computeDelays(graph);
 }
 
@@ -51,7 +52,7 @@ SchedPriorities::computeDelays(const SchedGraph* graph)
       const SchedGraphNode* node = *poIter;
       cycles_t nodeDelay;
       if (node->beginOutEdges() == node->endOutEdges())
-	nodeDelay = node->getLatency();
+        nodeDelay = node->getLatency();
       else
 	{
 	  // Iterate over the out-edges of the node to compute delay
@@ -59,7 +60,7 @@ SchedPriorities::computeDelays(const SchedGraph* graph)
 	  for (SchedGraphNode::const_iterator E=node->beginOutEdges();
 	       E != node->endOutEdges(); ++E)
 	    {
-	      cycles_t sinkDelay = getNodeDelayRef((*E)->getSink());
+	      cycles_t sinkDelay = getNodeDelay((*E)->getSink());
 	      nodeDelay = std::max(nodeDelay, sinkDelay + (*E)->getMinDelay());
 	    }
 	}
@@ -104,13 +105,13 @@ SchedPriorities::insertReady(const SchedGraphNode* node)
   candsAsSet.insert(node);
   mcands.clear(); // ensure reset choices is called before any more choices
   earliestReadyTime = std::min(earliestReadyTime,
-                               earliestForNode[node->getNodeId()]);
+                       getEarliestReadyTimeForNode(node));
   
   if (SchedDebugLevel >= Sched_PrintSchedTrace)
     {
       cerr << " Node " << node->getNodeId() << " will be ready in Cycle "
-           << earliestForNode[node->getNodeId()] << "; "
-	   << " Delay = " <<(long)getNodeDelayRef(node) << "; Instruction: \n";
+           << getEarliestReadyTimeForNode(node) << "; "
+	   << " Delay = " <<(long)getNodeDelay(node) << "; Instruction: \n";
       cerr << "        " << *node->getMachineInstr() << "\n";
     }
 }
@@ -123,21 +124,21 @@ SchedPriorities::issuedReadyNodeAt(cycles_t curTime,
   candsAsSet.erase(node);
   mcands.clear(); // ensure reset choices is called before any more choices
   
-  if (earliestReadyTime == getEarliestForNodeRef(node))
+  if (earliestReadyTime == getEarliestReadyTimeForNode(node))
     {// earliestReadyTime may have been due to this node, so recompute it
       earliestReadyTime = HUGE_LATENCY;
       for (NodeHeap::const_iterator I=candsAsHeap.begin();
 	   I != candsAsHeap.end(); ++I)
 	if (candsAsHeap.getNode(I))
 	  earliestReadyTime = std::min(earliestReadyTime, 
-				getEarliestForNodeRef(candsAsHeap.getNode(I)));
+				getEarliestReadyTimeForNode(candsAsHeap.getNode(I)));
     }
   
   // Now update ready times for successors
   for (SchedGraphNode::const_iterator E=node->beginOutEdges();
        E != node->endOutEdges(); ++E)
     {
-      cycles_t& etime = getEarliestForNodeRef((*E)->getSink());
+      cycles_t& etime = getEarliestReadyTimeForNodeRef((*E)->getSink());
       etime = std::max(etime, curTime + (*E)->getMinDelay());
     }    
 }
@@ -216,7 +217,7 @@ SchedPriorities::getNextHighest(const SchedulingManager& S,
       // If not, remove it from mcands and continue.  Refill mcands if
       // it becomes empty.
       nextChoice = candsAsHeap.getNode(mcands[nextIdx]);
-      if (getEarliestForNodeRef(nextChoice) > curTime
+      if (getEarliestReadyTimeForNode(nextChoice) > curTime
 	  || ! instrIsFeasible(S, nextChoice->getMachineInstr()->getOpCode()))
 	{
 	  mcands.erase(mcands.begin() + nextIdx);
diff --git a/lib/CodeGen/InstrSched/SchedPriorities.h b/lib/CodeGen/InstrSched/SchedPriorities.h
index a34557ca15..f5c29b27e3 100644
--- a/lib/CodeGen/InstrSched/SchedPriorities.h
+++ b/lib/CodeGen/InstrSched/SchedPriorities.h
@@ -159,7 +159,8 @@ private:
   FunctionLiveVarInfo &methodLiveVarInfo;
   std::hash_map<const MachineInstr*, bool> lastUseMap;
   std::vector<cycles_t> nodeDelayVec;
-  std::vector<cycles_t> earliestForNode;
+  std::vector<cycles_t> nodeEarliestUseVec;
+  std::vector<cycles_t> earliestReadyTimeForNode;
   cycles_t earliestReadyTime;
   NodeHeap candsAsHeap;				// candidate nodes, ready to go
   std::hash_set<const SchedGraphNode*> candsAsSet;//same entries as candsAsHeap,
@@ -183,14 +184,21 @@ private:
 					 const SchedGraphNode* graphNode);
   
   // NOTE: The next two return references to the actual vector entries.
-  //       Use with care.
+  //       Use the following two if you don't need to modify the value.
   cycles_t&	getNodeDelayRef		(const SchedGraphNode* node) {
     assert(node->getNodeId() < nodeDelayVec.size());
     return nodeDelayVec[node->getNodeId()];
   }
-  cycles_t&	getEarliestForNodeRef	(const SchedGraphNode* node) {
-    assert(node->getNodeId() < earliestForNode.size());
-    return earliestForNode[node->getNodeId()];
+  cycles_t&     getEarliestReadyTimeForNodeRef   (const SchedGraphNode* node) {
+    assert(node->getNodeId() < earliestReadyTimeForNode.size());
+    return earliestReadyTimeForNode[node->getNodeId()];
+  }
+  
+  cycles_t      getNodeDelay            (const SchedGraphNode* node) const {
+    return ((SchedPriorities*) this)->getNodeDelayRef(node); 
+  }
+  cycles_t      getEarliestReadyTimeForNode(const SchedGraphNode* node) const {
+    return ((SchedPriorities*) this)->getEarliestReadyTimeForNodeRef(node);
   }
 };