Major improvement to how nodes are built for a BB.

LLVM instruction is no longer recorded in each node, but BB is.

llvm-svn: 1262

4 files changed, 75 insertions, 37 deletions

diff --git a/llvm/lib/CodeGen/InstrSched/InstrScheduling.cpp b/llvm/lib/CodeGen/InstrSched/InstrScheduling.cpp
index 7a9a801715d..0ba218da1c7 100644
--- a/llvm/lib/CodeGen/InstrSched/InstrScheduling.cpp
+++ b/llvm/lib/CodeGen/InstrSched/InstrScheduling.cpp
@@ -1235,33 +1235,27 @@ ReplaceNopsWithUsefulInstr(SchedulingManager& S,
   // If not enough useful instructions were found, use the NOPs to
   // fill delay slots, otherwise, just discard them.
   //  
-  MachineCodeForVMInstr& termMvec = node->getInstr()->getMachineInstrVec();
-  unsigned int firstDelaySlotIdx;
-  for (unsigned i=0; i < termMvec.size(); ++i)
-    if (termMvec[i] == brInstr)
-      {
-        firstDelaySlotIdx = i+1;
-        break;
-      }
-  assert(firstDelaySlotIdx <= termMvec.size()-1 &&
-         "This sucks! Where's that delay slot instruction?");
+  unsigned int firstDelaySlotIdx = node->getOrigIndexInBB() + 1;
+  MachineCodeForBasicBlock& bbMvec  = node->getBB()->getMachineInstrVec();
+  assert(bbMvec[firstDelaySlotIdx - 1] == brInstr &&
+         "Incorrect instr. index in basic block for brInstr");
   
   // First find all useful instructions already in the delay slots
   // and USE THEM.  We'll throw away the unused alternatives below
   // 
   for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
-    if (! mii.isNop(termMvec[i]->getOpCode()))
+    if (! mii.isNop(bbMvec[i]->getOpCode()))
       sdelayNodeVec.insert(sdelayNodeVec.begin(),
-                           graph->getGraphNodeForInstr(termMvec[i]));
+                           graph->getGraphNodeForInstr(bbMvec[i]));
   
   // Then find the NOPs and keep only as many as are needed.
   // Put the rest in nopNodeVec to be deleted.
   for (unsigned i=firstDelaySlotIdx; i < firstDelaySlotIdx + ndelays; ++i)
-    if (mii.isNop(termMvec[i]->getOpCode()))
+    if (mii.isNop(bbMvec[i]->getOpCode()))
       if (sdelayNodeVec.size() < ndelays)
-        sdelayNodeVec.push_back(graph->getGraphNodeForInstr(termMvec[i]));
+        sdelayNodeVec.push_back(graph->getGraphNodeForInstr(bbMvec[i]));
       else
-        nopNodeVec.push_back(graph->getGraphNodeForInstr(termMvec[i]));
+        nopNodeVec.push_back(graph->getGraphNodeForInstr(bbMvec[i]));
   
   assert(sdelayNodeVec.size() >= ndelays);
   
diff --git a/llvm/lib/CodeGen/InstrSched/SchedGraph.cpp b/llvm/lib/CodeGen/InstrSched/SchedGraph.cpp
index 33436be4aa2..0954ed5efb4 100644
--- a/llvm/lib/CodeGen/InstrSched/SchedGraph.cpp
+++ b/llvm/lib/CodeGen/InstrSched/SchedGraph.cpp
@@ -138,12 +138,12 @@ void SchedGraphEdge::dump(int indent=0) const {
 
 /*ctor*/
 SchedGraphNode::SchedGraphNode(unsigned int _nodeId,
-			       const Instruction* _instr,
+                               const BasicBlock*   _bb,
 			       const MachineInstr* _minstr,
                                int   indexInBB,
 			       const TargetMachine& target)
   : nodeId(_nodeId),
-    instr(_instr),
+    bb(_bb),
     minstr(_minstr),
     origIndexInBB(indexInBB),
     latency(0)
@@ -603,9 +603,6 @@ SchedGraph::addEdgesForInstruction(const MachineInstr& minstr,
   if (node == NULL)
     return;
   
-  assert(node->getInstr() && "Should be no dummy nodes here!");
-  const Instruction* instr = node->getInstr();
-  
   // Add edges for all operands of the machine instruction.
   // 
   for (unsigned i=0, numOps=minstr.getNumOperands(); i < numOps; i++)
@@ -778,26 +775,73 @@ SchedGraph::buildNodesforBB(const TargetMachine& target,
                             ValueToDefVecMap& valueToDefVecMap)
 {
   const MachineInstrInfo& mii = target.getInstrInfo();
-  int origIndexInBB = 0;
   
   // Build graph nodes for each VM instruction and gather def/use info.
   // Do both those together in a single pass over all machine instructions.
-  for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
-    {
-      const Instruction *instr = *II;
-      const MachineCodeForVMInstr& mvec = instr->getMachineInstrVec();
-      for (unsigned i=0; i < mvec.size(); i++)
-        if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
+  const MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec();
+  for (unsigned i=0; i < mvec.size(); i++)
+    if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
+      {
+        SchedGraphNode* node = new SchedGraphNode(getNumNodes(), bb,
+                                                  mvec[i], i, target);
+        this->noteGraphNodeForInstr(mvec[i], node);
+        
+        // Remember all register references and value defs
+        findDefUseInfoAtInstr(target, node,
+                              memNodeVec, regToRefVecMap,valueToDefVecMap);
+      }
+  
+#undef REALLY_NEED_TO_SEARCH_SUCCESSOR_PHIS
+#ifdef REALLY_NEED_TO_SEARCH_SUCCESSOR_PHIS
+  // This is a BIG UGLY HACK.  IT NEEDS TO BE ELIMINATED.
+  // Look for copy instructions inserted in this BB due to Phi instructions
+  // in the successor BBs.
+  // There MUST be exactly one copy per Phi in successor nodes.
+  // 
+  for (BasicBlock::succ_const_iterator SI=bb->succ_begin(), SE=bb->succ_end();
+       SI != SE; ++SI)
+    for (BasicBlock::const_iterator PI=(*SI)->begin(), PE=(*SI)->end();
+         PI != PE; ++PI)
+      {
+        if ((*PI)->getOpcode() != Instruction::PHINode)
+          break;                        // No more Phis in this successor
+        
+        // Find the incoming value from block bb to block (*SI)
+        int bbIndex = cast<PHINode>(*PI)->getBasicBlockIndex(bb);
+        assert(bbIndex >= 0 && "But I know bb is a predecessor of (*SI)?");
+        Value* inVal = cast<PHINode>(*PI)->getIncomingValue(bbIndex);
+        assert(inVal != NULL && "There must be an in-value on every edge");
+        
+        // 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 MachineInstr* theCopy = NULL;
+        for (unsigned i=0; i < mvec.size() && theCopy == NULL; i++)
+          if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
+            // not a Phi: assume this is a copy and examine its operands
+            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;
+                  }
+              }
+        
+        // Found the dang instruction.  Now create a node and do the rest...
+        if (theCopy != NULL)
           {
-            SchedGraphNode* node = new SchedGraphNode(getNumNodes(), instr,
-                                            mvec[i], origIndexInBB++, target);
-            this->noteGraphNodeForInstr(mvec[i], node);
-            
-            // Remember all register references and value defs
+            SchedGraphNode* node = new SchedGraphNode(getNumNodes(), bb,
+                                            theCopy, origIndexInBB++, target);
+            this->noteGraphNodeForInstr(theCopy, node);
             findDefUseInfoAtInstr(target, node,
                                   memNodeVec, regToRefVecMap,valueToDefVecMap);
           }
-    }
+      }
+#endif  REALLY_NEED_TO_SEARCH_SUCCESSOR_PHIS
 }
 
 
diff --git a/llvm/lib/CodeGen/InstrSched/SchedGraph.h b/llvm/lib/CodeGen/InstrSched/SchedGraph.h
index dc5d0059e57..1fec41e4ba8 100644
--- a/llvm/lib/CodeGen/InstrSched/SchedGraph.h
+++ b/llvm/lib/CodeGen/InstrSched/SchedGraph.h
@@ -142,7 +142,7 @@ private:
 class SchedGraphNode: public NonCopyable {
 private:
   unsigned int nodeId;
-  const Instruction* instr;
+  const BasicBlock* bb;
   const MachineInstr* minstr;
   vector<SchedGraphEdge*> inEdges;
   vector<SchedGraphEdge*> outEdges;
@@ -160,13 +160,13 @@ public:
   // Accessor methods
   // 
   unsigned int		getNodeId	() const { return nodeId; }
-  const Instruction*	getInstr	() const { return instr; }
   const MachineInstr*	getMachineInstr	() const { return minstr; }
   const MachineOpCode	getOpCode	() const { return minstr->getOpCode();}
   int			getLatency	() const { return latency; }
   unsigned int		getNumInEdges	() const { return inEdges.size(); }
   unsigned int		getNumOutEdges	() const { return outEdges.size(); }
   bool			isDummyNode	() const { return (minstr == NULL); }
+  const BasicBlock*	getBB           () const { return bb; }
   int                   getOrigIndexInBB() const { return origIndexInBB; }
   
   //
@@ -203,7 +203,7 @@ private:
   // disable default constructor and provide a ctor for single-block graphs
   /*ctor*/		SchedGraphNode();	// DO NOT IMPLEMENT
   /*ctor*/		SchedGraphNode	(unsigned int _nodeId,
-					 const Instruction* _instr,
+					 const BasicBlock*   _bb,
 					 const MachineInstr* _minstr,
                                          int   indexInBB,
 					 const TargetMachine& _target);
diff --git a/llvm/lib/CodeGen/InstrSched/SchedPriorities.cpp b/llvm/lib/CodeGen/InstrSched/SchedPriorities.cpp
index 7840a250984..31d9f6c5926 100644
--- a/llvm/lib/CodeGen/InstrSched/SchedPriorities.cpp
+++ b/llvm/lib/CodeGen/InstrSched/SchedPriorities.cpp
@@ -264,7 +264,7 @@ SchedPriorities::instructionHasLastUse(MethodLiveVarInfo& methodLiveVarInfo,
   
   // else check if instruction is a last use and save it in the hash_map
   bool hasLastUse = false;
-  const BasicBlock* bb = graphNode->getInstr()->getParent();
+  const BasicBlock* bb = graphNode->getBB();
   const LiveVarSet* liveVars =
     methodLiveVarInfo.getLiveVarSetBeforeMInst(minstr, bb);