Only add true dep. edges from an earlier to a later instruction.
This wasn't a problem until we started putting copies for Phi values
that produced cycles in the SchedGraph!
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@1254 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/InstrSched/SchedGraph.cpp b/lib/CodeGen/InstrSched/SchedGraph.cpp
index 6091312..33436be 100644
--- a/lib/CodeGen/InstrSched/SchedGraph.cpp
+++ b/lib/CodeGen/InstrSched/SchedGraph.cpp
@@ -140,10 +140,12 @@
SchedGraphNode::SchedGraphNode(unsigned int _nodeId,
const Instruction* _instr,
const MachineInstr* _minstr,
+ int indexInBB,
const TargetMachine& target)
: nodeId(_nodeId),
instr(_instr),
minstr(_minstr),
+ origIndexInBB(indexInBB),
latency(0)
{
if (minstr)
@@ -583,8 +585,12 @@
const Value* defValue,
const TargetMachine& target)
{
+ // Add edges from all def nodes that are before destNode in the BB.
+ // BIGTIME FIXME:
+ // We could probably add non-SSA edges here too! But I'll do that later.
for (RefVec::const_iterator I=defVec.begin(), E=defVec.end(); I != E; ++I)
- (void) new SchedGraphEdge((*I).first, destNode, defValue);
+ if ((*I).first->getOrigIndexInBB() < destNode->getOrigIndexInBB())
+ (void) new SchedGraphEdge((*I).first, destNode, defValue);
}
@@ -765,25 +771,33 @@
void
-SchedGraph::buildNodesforVMInstr(const TargetMachine& target,
- const Instruction* instr,
- vector<SchedGraphNode*>& memNodeVec,
- RegToRefVecMap& regToRefVecMap,
- ValueToDefVecMap& valueToDefVecMap)
+SchedGraph::buildNodesforBB(const TargetMachine& target,
+ const BasicBlock* bb,
+ vector<SchedGraphNode*>& memNodeVec,
+ RegToRefVecMap& regToRefVecMap,
+ ValueToDefVecMap& valueToDefVecMap)
{
const MachineInstrInfo& mii = target.getInstrInfo();
- const MachineCodeForVMInstr& mvec = instr->getMachineInstrVec();
- for (unsigned i=0; i < mvec.size(); i++)
- if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
- {
- SchedGraphNode* node = new SchedGraphNode(getNumNodes(),
- instr, mvec[i], target);
- this->noteGraphNodeForInstr(mvec[i], node);
-
- // Remember all register references and value defs
- findDefUseInfoAtInstr(target, node,
- memNodeVec, regToRefVecMap, valueToDefVecMap);
- }
+ 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()))
+ {
+ SchedGraphNode* node = new SchedGraphNode(getNumNodes(), instr,
+ mvec[i], origIndexInBB++, target);
+ this->noteGraphNodeForInstr(mvec[i], node);
+
+ // Remember all register references and value defs
+ findDefUseInfoAtInstr(target, node,
+ memNodeVec, regToRefVecMap,valueToDefVecMap);
+ }
+ }
}
@@ -818,8 +832,8 @@
RegToRefVecMap regToRefVecMap;
// Make a dummy root node. We'll add edges to the real roots later.
- graphRoot = new SchedGraphNode(0, NULL, NULL, target);
- graphLeaf = new SchedGraphNode(1, NULL, NULL, target);
+ graphRoot = new SchedGraphNode(0, NULL, NULL, -1, target);
+ graphLeaf = new SchedGraphNode(1, NULL, NULL, -1, target);
//----------------------------------------------------------------
// First add nodes for all the machine instructions in the basic block
@@ -828,15 +842,7 @@
// Also, remember the load/store instructions to add memory deps later.
//----------------------------------------------------------------
- for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
- {
- const Instruction *instr = *II;
-
- // Build graph nodes for this VM instruction and gather def/use info.
- // Do these together in a single pass over all machine instructions.
- buildNodesforVMInstr(target, instr,
- memNodeVec, regToRefVecMap, valueToDefVecMap);
- }
+ buildNodesforBB(target, bb, memNodeVec, regToRefVecMap, valueToDefVecMap);
//----------------------------------------------------------------
// Now add edges for the following (all are incoming edges except (4)):
diff --git a/lib/CodeGen/InstrSched/SchedGraph.h b/lib/CodeGen/InstrSched/SchedGraph.h
index 6f6739b..dc5d0059 100644
--- a/lib/CodeGen/InstrSched/SchedGraph.h
+++ b/lib/CodeGen/InstrSched/SchedGraph.h
@@ -146,6 +146,7 @@
const MachineInstr* minstr;
vector<SchedGraphEdge*> inEdges;
vector<SchedGraphEdge*> outEdges;
+ int origIndexInBB; // original position of machine instr in BB
int latency;
public:
@@ -166,6 +167,7 @@
unsigned int getNumInEdges () const { return inEdges.size(); }
unsigned int getNumOutEdges () const { return outEdges.size(); }
bool isDummyNode () const { return (minstr == NULL); }
+ int getOrigIndexInBB() const { return origIndexInBB; }
//
// Iterators
@@ -203,6 +205,7 @@
/*ctor*/ SchedGraphNode (unsigned int _nodeId,
const Instruction* _instr,
const MachineInstr* _minstr,
+ int indexInBB,
const TargetMachine& _target);
/*dtor*/ ~SchedGraphNode ();
};
@@ -303,8 +306,8 @@
//
void buildGraph (const TargetMachine& target);
- void buildNodesforVMInstr (const TargetMachine& target,
- const Instruction* instr,
+ void buildNodesforBB (const TargetMachine& target,
+ const BasicBlock* bb,
vector<SchedGraphNode*>& memNodeVec,
RegToRefVecMap& regToRefVecMap,
ValueToDefVecMap& valueToDefVecMap);
diff --git a/lib/Target/SparcV9/InstrSched/SchedGraph.cpp b/lib/Target/SparcV9/InstrSched/SchedGraph.cpp
index 6091312..33436be 100644
--- a/lib/Target/SparcV9/InstrSched/SchedGraph.cpp
+++ b/lib/Target/SparcV9/InstrSched/SchedGraph.cpp
@@ -140,10 +140,12 @@
SchedGraphNode::SchedGraphNode(unsigned int _nodeId,
const Instruction* _instr,
const MachineInstr* _minstr,
+ int indexInBB,
const TargetMachine& target)
: nodeId(_nodeId),
instr(_instr),
minstr(_minstr),
+ origIndexInBB(indexInBB),
latency(0)
{
if (minstr)
@@ -583,8 +585,12 @@
const Value* defValue,
const TargetMachine& target)
{
+ // Add edges from all def nodes that are before destNode in the BB.
+ // BIGTIME FIXME:
+ // We could probably add non-SSA edges here too! But I'll do that later.
for (RefVec::const_iterator I=defVec.begin(), E=defVec.end(); I != E; ++I)
- (void) new SchedGraphEdge((*I).first, destNode, defValue);
+ if ((*I).first->getOrigIndexInBB() < destNode->getOrigIndexInBB())
+ (void) new SchedGraphEdge((*I).first, destNode, defValue);
}
@@ -765,25 +771,33 @@
void
-SchedGraph::buildNodesforVMInstr(const TargetMachine& target,
- const Instruction* instr,
- vector<SchedGraphNode*>& memNodeVec,
- RegToRefVecMap& regToRefVecMap,
- ValueToDefVecMap& valueToDefVecMap)
+SchedGraph::buildNodesforBB(const TargetMachine& target,
+ const BasicBlock* bb,
+ vector<SchedGraphNode*>& memNodeVec,
+ RegToRefVecMap& regToRefVecMap,
+ ValueToDefVecMap& valueToDefVecMap)
{
const MachineInstrInfo& mii = target.getInstrInfo();
- const MachineCodeForVMInstr& mvec = instr->getMachineInstrVec();
- for (unsigned i=0; i < mvec.size(); i++)
- if (! mii.isDummyPhiInstr(mvec[i]->getOpCode()))
- {
- SchedGraphNode* node = new SchedGraphNode(getNumNodes(),
- instr, mvec[i], target);
- this->noteGraphNodeForInstr(mvec[i], node);
-
- // Remember all register references and value defs
- findDefUseInfoAtInstr(target, node,
- memNodeVec, regToRefVecMap, valueToDefVecMap);
- }
+ 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()))
+ {
+ SchedGraphNode* node = new SchedGraphNode(getNumNodes(), instr,
+ mvec[i], origIndexInBB++, target);
+ this->noteGraphNodeForInstr(mvec[i], node);
+
+ // Remember all register references and value defs
+ findDefUseInfoAtInstr(target, node,
+ memNodeVec, regToRefVecMap,valueToDefVecMap);
+ }
+ }
}
@@ -818,8 +832,8 @@
RegToRefVecMap regToRefVecMap;
// Make a dummy root node. We'll add edges to the real roots later.
- graphRoot = new SchedGraphNode(0, NULL, NULL, target);
- graphLeaf = new SchedGraphNode(1, NULL, NULL, target);
+ graphRoot = new SchedGraphNode(0, NULL, NULL, -1, target);
+ graphLeaf = new SchedGraphNode(1, NULL, NULL, -1, target);
//----------------------------------------------------------------
// First add nodes for all the machine instructions in the basic block
@@ -828,15 +842,7 @@
// Also, remember the load/store instructions to add memory deps later.
//----------------------------------------------------------------
- for (BasicBlock::const_iterator II = bb->begin(); II != bb->end(); ++II)
- {
- const Instruction *instr = *II;
-
- // Build graph nodes for this VM instruction and gather def/use info.
- // Do these together in a single pass over all machine instructions.
- buildNodesforVMInstr(target, instr,
- memNodeVec, regToRefVecMap, valueToDefVecMap);
- }
+ buildNodesforBB(target, bb, memNodeVec, regToRefVecMap, valueToDefVecMap);
//----------------------------------------------------------------
// Now add edges for the following (all are incoming edges except (4)):
diff --git a/lib/Target/SparcV9/InstrSched/SchedGraph.h b/lib/Target/SparcV9/InstrSched/SchedGraph.h
index 6f6739b..dc5d0059 100644
--- a/lib/Target/SparcV9/InstrSched/SchedGraph.h
+++ b/lib/Target/SparcV9/InstrSched/SchedGraph.h
@@ -146,6 +146,7 @@
const MachineInstr* minstr;
vector<SchedGraphEdge*> inEdges;
vector<SchedGraphEdge*> outEdges;
+ int origIndexInBB; // original position of machine instr in BB
int latency;
public:
@@ -166,6 +167,7 @@
unsigned int getNumInEdges () const { return inEdges.size(); }
unsigned int getNumOutEdges () const { return outEdges.size(); }
bool isDummyNode () const { return (minstr == NULL); }
+ int getOrigIndexInBB() const { return origIndexInBB; }
//
// Iterators
@@ -203,6 +205,7 @@
/*ctor*/ SchedGraphNode (unsigned int _nodeId,
const Instruction* _instr,
const MachineInstr* _minstr,
+ int indexInBB,
const TargetMachine& _target);
/*dtor*/ ~SchedGraphNode ();
};
@@ -303,8 +306,8 @@
//
void buildGraph (const TargetMachine& target);
- void buildNodesforVMInstr (const TargetMachine& target,
- const Instruction* instr,
+ void buildNodesforBB (const TargetMachine& target,
+ const BasicBlock* bb,
vector<SchedGraphNode*>& memNodeVec,
RegToRefVecMap& regToRefVecMap,
ValueToDefVecMap& valueToDefVecMap);