for (SchedGraphNode::const_iterator EI = node->beginInEdges();
EI != node->endInEdges(); ++EI)
- if (! (*EI)->getSrc()->isDummyNode()
- && mii.isLoad((*EI)->getSrc()->getOpCode())
+ if (! ((SchedGraphNode*)(*EI)->getSrc())->isDummyNode()
+ && mii.isLoad(((SchedGraphNode*)(*EI)->getSrc())->getOpCode())
&& (*EI)->getDepType() == SchedGraphEdge::CtrlDep)
return false;
bool onlyCDEdgeToBranch = true;
for (SchedGraphNode::const_iterator OEI = node->beginOutEdges();
OEI != node->endOutEdges(); ++OEI)
- if (! (*OEI)->getSink()->isDummyNode()
+ if (! ((SchedGraphNode*)(*OEI)->getSink())->isDummyNode()
&& ((*OEI)->getSink() != brNode
|| (*OEI)->getDepType() != SchedGraphEdge::CtrlDep))
{
//===----------------------------------------------------------------------===//
#include "SchedGraph.h"
-#include "llvm/CodeGen/InstrSelection.h"
-#include "llvm/CodeGen/MachineCodeForInstruction.h"
-#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/Target/TargetRegInfo.h"
+#include "llvm/CodeGen/SchedGraphCommon.h"
+#include <iostream>
+
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
+#include "Support/STLExtras.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/CodeGen/MachineCodeForInstruction.h"
+#include "llvm/Target/TargetRegInfo.h"
#include "llvm/Function.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/InstrSelection.h"
#include "llvm/iOther.h"
#include "Support/StringExtras.h"
-#include "Support/STLExtras.h"
+
//*********************** Internal Data Structures *************************/
typedef hash_map<const Value*, RefVec>::const_iterator const_iterator;
};
-//
-// class SchedGraphEdge
-//
-
-/*ctor*/
-SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- SchedGraphEdgeDepType _depType,
- unsigned int _depOrderType,
- int _minDelay)
- : src(_src),
- sink(_sink),
- depType(_depType),
- depOrderType(_depOrderType),
- minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
- val(NULL)
-{
- assert(src != sink && "Self-loop in scheduling graph!");
- src->addOutEdge(this);
- sink->addInEdge(this);
-}
-
-
-/*ctor*/
-SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- const Value* _val,
- unsigned int _depOrderType,
- int _minDelay)
- : src(_src),
- sink(_sink),
- depType(ValueDep),
- depOrderType(_depOrderType),
- minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
- val(_val)
-{
- assert(src != sink && "Self-loop in scheduling graph!");
- src->addOutEdge(this);
- sink->addInEdge(this);
-}
-
-
-/*ctor*/
-SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- unsigned int _regNum,
- unsigned int _depOrderType,
- int _minDelay)
- : src(_src),
- sink(_sink),
- depType(MachineRegister),
- depOrderType(_depOrderType),
- minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
- machineRegNum(_regNum)
-{
- assert(src != sink && "Self-loop in scheduling graph!");
- src->addOutEdge(this);
- sink->addInEdge(this);
-}
-
-
-/*ctor*/
-SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- ResourceId _resourceId,
- int _minDelay)
- : src(_src),
- sink(_sink),
- depType(MachineResource),
- depOrderType(NonDataDep),
- minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
- resourceId(_resourceId)
-{
- assert(src != sink && "Self-loop in scheduling graph!");
- src->addOutEdge(this);
- sink->addInEdge(this);
-}
-
-/*dtor*/
-SchedGraphEdge::~SchedGraphEdge()
-{
-}
-
-void SchedGraphEdge::dump(int indent) const {
- std::cerr << std::string(indent*2, ' ') << *this;
-}
-
//
// class SchedGraphNode
MachineBasicBlock *mbb,
int indexInBB,
const TargetMachine& Target)
- : nodeId(NID), MBB(mbb), minstr(mbb ? (*mbb)[indexInBB] : 0),
- origIndexInBB(indexInBB), latency(0) {
- if (minstr)
+ : SchedGraphNodeCommon(NID), origIndexInBB(indexInBB), MBB(mbb), MI(mbb ? (*mbb)[indexInBB] : 0)
+ {
+ if (MI)
{
- MachineOpCode mopCode = minstr->getOpCode();
+ MachineOpCode mopCode = MI->getOpCode();
latency = Target.getInstrInfo().hasResultInterlock(mopCode)
? Target.getInstrInfo().minLatency(mopCode)
: Target.getInstrInfo().maxLatency(mopCode);
deleter<SchedGraphEdge>);
}
-void SchedGraphNode::dump(int indent) const {
- std::cerr << std::string(indent*2, ' ') << *this;
-}
-
-
-inline void
-SchedGraphNode::addInEdge(SchedGraphEdge* edge)
-{
- inEdges.push_back(edge);
-}
-
-
-inline void
-SchedGraphNode::addOutEdge(SchedGraphEdge* edge)
-{
- outEdges.push_back(edge);
-}
-
-inline void
-SchedGraphNode::removeInEdge(const SchedGraphEdge* edge)
-{
- assert(edge->getSink() == this);
-
- for (iterator I = beginInEdges(); I != endInEdges(); ++I)
- if ((*I) == edge)
- {
- inEdges.erase(I);
- break;
- }
-}
-
-inline void
-SchedGraphNode::removeOutEdge(const SchedGraphEdge* edge)
-{
- assert(edge->getSrc() == this);
-
- for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
- if ((*I) == edge)
- {
- outEdges.erase(I);
- break;
- }
-}
-
-
//
// class SchedGraph
//
}
-void
-SchedGraph::eraseIncomingEdges(SchedGraphNode* node, bool addDummyEdges)
-{
- // Delete and disconnect all in-edges for the node
- for (SchedGraphNode::iterator I = node->beginInEdges();
- I != node->endInEdges(); ++I)
- {
- SchedGraphNode* srcNode = (*I)->getSrc();
- srcNode->removeOutEdge(*I);
- delete *I;
-
- if (addDummyEdges &&
- srcNode != getRoot() &&
- srcNode->beginOutEdges() == srcNode->endOutEdges())
- {
- // srcNode has no more out edges, so add an edge to dummy EXIT node
- assert(node != getLeaf() && "Adding edge that was just removed?");
- (void) new SchedGraphEdge(srcNode, getLeaf(),
- SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
- }
- }
-
- node->inEdges.clear();
-}
-
-void
-SchedGraph::eraseOutgoingEdges(SchedGraphNode* node, bool addDummyEdges)
-{
- // Delete and disconnect all out-edges for the node
- for (SchedGraphNode::iterator I = node->beginOutEdges();
- I != node->endOutEdges(); ++I)
- {
- SchedGraphNode* sinkNode = (*I)->getSink();
- sinkNode->removeInEdge(*I);
- delete *I;
-
- if (addDummyEdges &&
- sinkNode != getLeaf() &&
- sinkNode->beginInEdges() == sinkNode->endInEdges())
- { //sinkNode has no more in edges, so add an edge from dummy ENTRY node
- assert(node != getRoot() && "Adding edge that was just removed?");
- (void) new SchedGraphEdge(getRoot(), sinkNode,
- SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
- }
- }
-
- node->outEdges.clear();
-}
-
-void
-SchedGraph::eraseIncidentEdges(SchedGraphNode* node, bool addDummyEdges)
-{
- this->eraseIncomingEdges(node, addDummyEdges);
- this->eraseOutgoingEdges(node, addDummyEdges);
-}
-
void
SchedGraph::addDummyEdges()
// Collect the register references and value defs. for explicit operands
//
- const MachineInstr& minstr = *node->getMachineInstr();
- for (int i=0, numOps = (int) minstr.getNumOperands(); i < numOps; i++)
+ const MachineInstr& MI = *node->getMachineInstr();
+ for (int i=0, numOps = (int) MI.getNumOperands(); i < numOps; i++)
{
- const MachineOperand& mop = minstr.getOperand(i);
+ const MachineOperand& mop = MI.getOperand(i);
// if this references a register other than the hardwired
// "zero" register, record the reference.
}
// ignore all other non-def operands
- if (!minstr.getOperand(i).opIsDefOnly() &&
- !minstr.getOperand(i).opIsDefAndUse())
+ if (!MI.getOperand(i).opIsDefOnly() &&
+ !MI.getOperand(i).opIsDefAndUse())
continue;
// We must be defining a value.
// Collect value defs. for implicit operands. They may have allocated
// physical registers also.
//
- for (unsigned i=0, N = minstr.getNumImplicitRefs(); i != N; ++i)
+ for (unsigned i=0, N = MI.getNumImplicitRefs(); i != N; ++i)
{
- const MachineOperand& mop = minstr.getImplicitOp(i);
+ const MachineOperand& mop = MI.getImplicitOp(i);
if (mop.hasAllocatedReg())
{
int regNum = mop.getAllocatedRegNum();
if (regNum != target.getRegInfo().getZeroRegNum())
regToRefVecMap[mop.getAllocatedRegNum()]
- .push_back(std::make_pair(node, i + minstr.getNumOperands()));
+ .push_back(std::make_pair(node, i + MI.getNumOperands()));
continue; // nothing more to do
}
if (mop.opIsDefOnly() || mop.opIsDefAndUse()) {
- assert(minstr.getImplicitRef(i) != NULL && "Null value being defined?");
- valueToDefVecMap[minstr.getImplicitRef(i)].push_back(std::make_pair(node,
+ assert(MI.getImplicitRef(i) != NULL && "Null value being defined?");
+ valueToDefVecMap[MI.getImplicitRef(i)].push_back(std::make_pair(node,
-i));
}
}
/*ctor*/
SchedGraphSet::SchedGraphSet(const Function* _function,
const TargetMachine& target) :
- method(_function)
+ function(_function)
{
- buildGraphsForMethod(method, target);
+ buildGraphsForMethod(function, target);
}
void
SchedGraphSet::dump() const
{
- std::cerr << "======== Sched graphs for function `" << method->getName()
+ std::cerr << "======== Sched graphs for function `" << function->getName()
<< "' ========\n\n";
for (const_iterator I=begin(); I != end(); ++I)
(*I)->dump();
- std::cerr << "\n====== End graphs for function `" << method->getName()
+ std::cerr << "\n====== End graphs for function `" << function->getName()
<< "' ========\n\n";
}
std::ostream &operator<<(std::ostream &os, const SchedGraphNode& node)
{
os << std::string(8, ' ')
- << "Node " << node.nodeId << " : "
+ << "Node " << node.ID << " : "
<< "latency = " << node.latency << "\n" << std::string(12, ' ');
if (node.getMachineInstr() == NULL)
#include "llvm/CodeGen/MachineInstr.h"
#include "Support/GraphTraits.h"
#include "Support/hash_map"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/CodeGen/SchedGraphCommon.h"
-class Value;
-class Instruction;
-class TerminatorInst;
-class BasicBlock;
-class Function;
-class TargetMachine;
-class SchedGraphEdge;
-class SchedGraphNode;
-class SchedGraph;
class RegToRefVecMap;
class ValueToDefVecMap;
class RefVec;
-class MachineInstr;
-class MachineBasicBlock;
+class SchedGraphNode : public SchedGraphNodeCommon {
-/******************** Exported Data Types and Constants ********************/
-
-typedef int ResourceId;
-const ResourceId InvalidRID = -1;
-const ResourceId MachineCCRegsRID = -2; // use +ve numbers for actual regs
-const ResourceId MachineIntRegsRID = -3; // use +ve numbers for actual regs
-const ResourceId MachineFPRegsRID = -4; // use +ve numbers for actual regs
-
-
-//*********************** Public Class Declarations ************************/
-
-class SchedGraphEdge {
- SchedGraphEdge(const SchedGraphEdge &); // DO NOT IMPLEMENT
- void operator=(const SchedGraphEdge &); // DO NOT IMPLEMENT
-public:
- enum SchedGraphEdgeDepType {
- CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
- };
- enum DataDepOrderType {
- TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
- };
-
-private:
- SchedGraphNode* src;
- SchedGraphNode* sink;
- SchedGraphEdgeDepType depType;
- unsigned int depOrderType;
- int minDelay; // cached latency (assumes fixed target arch)
-
- union {
- const Value* val;
- int machineRegNum;
- ResourceId resourceId;
- };
-
-public:
- // For all constructors, if minDelay is unspecified, minDelay is
- // set to _src->getLatency().
- // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
- /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- SchedGraphEdgeDepType _depType,
- unsigned int _depOrderType,
- int _minDelay = -1);
-
- // constructor for explicit value dependence (may be true/anti/output)
- /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- const Value* _val,
- unsigned int _depOrderType,
- int _minDelay = -1);
-
- // constructor for machine register dependence
- /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- unsigned int _regNum,
- unsigned int _depOrderType,
- int _minDelay = -1);
-
- // constructor for any other machine resource dependences.
- // DataDepOrderType is always NonDataDep. It it not an argument to
- // avoid overloading ambiguity with previous constructor.
- /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- ResourceId _resourceId,
- int _minDelay = -1);
-
- /*dtor*/ ~SchedGraphEdge();
-
- SchedGraphNode* getSrc () const { return src; }
- SchedGraphNode* getSink () const { return sink; }
- int getMinDelay () const { return minDelay; }
- SchedGraphEdgeDepType getDepType () const { return depType; }
-
- const Value* getValue () const {
- assert(depType == ValueDep); return val;
- }
- int getMachineReg () const {
- assert(depType == MachineRegister); return machineRegNum;
- }
- int getResourceId () const {
- assert(depType == MachineResource); return resourceId;
- }
-
-public:
- //
- // Debugging support
- //
- friend std::ostream& operator<<(std::ostream& os, const SchedGraphEdge& edge);
-
- void dump (int indent=0) const;
-
-private:
- // disable default ctor
- /*ctor*/ SchedGraphEdge(); // DO NOT IMPLEMENT
-};
+ int origIndexInBB; // original position of machine instr in BB
+ MachineBasicBlock *MBB;
+ const MachineInstr *MI;
+ SchedGraphNode (unsigned nodeId, MachineBasicBlock *mbb,
+ int indexInBB, const TargetMachine& Target);
+ ~SchedGraphNode ();
-class SchedGraphNode {
- unsigned nodeId;
- MachineBasicBlock *MBB;
- const MachineInstr* minstr;
- std::vector<SchedGraphEdge*> inEdges;
- std::vector<SchedGraphEdge*> outEdges;
- int origIndexInBB; // original position of machine instr in BB
- int latency;
+ friend class SchedGraph; // give access for ctor and dtor
+ friend class SchedGraphEdge; // give access for adding edges
- SchedGraphNode(const SchedGraphNode &); // DO NOT IMPLEMENT
- void operator=(const SchedGraphNode &); // DO NOT IMPLEMENT
-public:
- typedef std::vector<SchedGraphEdge*>:: iterator iterator;
- typedef std::vector<SchedGraphEdge*>::const_iterator const_iterator;
- typedef std::vector<SchedGraphEdge*>:: reverse_iterator reverse_iterator;
- typedef std::vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;
-
public:
- //
// Accessor methods
- //
- unsigned getNodeId () const { return nodeId; }
- const MachineInstr* getMachineInstr () const { return minstr; }
- const MachineOpCode getOpCode () const { return minstr->getOpCode(); }
- int getLatency () const { return latency; }
- unsigned getNumInEdges () const { return inEdges.size(); }
- unsigned getNumOutEdges () const { return outEdges.size(); }
- bool isDummyNode () const { return (minstr == NULL); }
+ const MachineInstr* getMachineInstr () const { return MI; }
+ const MachineOpCode getOpCode () const { return MI->getOpCode(); }
+ bool isDummyNode () const { return (MI == NULL); }
MachineBasicBlock &getMachineBasicBlock() const { return *MBB; }
- int getOrigIndexInBB() const { return origIndexInBB; }
-
- //
- // Iterators
- //
- iterator beginInEdges () { return inEdges.begin(); }
- iterator endInEdges () { return inEdges.end(); }
- iterator beginOutEdges () { return outEdges.begin(); }
- iterator endOutEdges () { return outEdges.end(); }
-
- const_iterator beginInEdges () const { return inEdges.begin(); }
- const_iterator endInEdges () const { return inEdges.end(); }
- const_iterator beginOutEdges () const { return outEdges.begin(); }
- const_iterator endOutEdges () const { return outEdges.end(); }
-
-public:
- //
- // Debugging support
- //
- friend std::ostream& operator<<(std::ostream& os, const SchedGraphNode& node);
-
- void dump (int indent=0) const;
-
-private:
- friend class SchedGraph; // give access for ctor and dtor
- friend class SchedGraphEdge; // give access for adding edges
-
- void addInEdge (SchedGraphEdge* edge);
- void addOutEdge (SchedGraphEdge* edge);
-
- void removeInEdge (const SchedGraphEdge* edge);
- void removeOutEdge (const SchedGraphEdge* edge);
-
- // disable default constructor and provide a ctor for single-block graphs
- /*ctor*/ SchedGraphNode(); // DO NOT IMPLEMENT
- /*ctor*/ SchedGraphNode (unsigned nodeId,
- MachineBasicBlock *mbb,
- int indexInBB,
- const TargetMachine& Target);
- /*dtor*/ ~SchedGraphNode ();
-};
-
+ int getOrigIndexInBB() const { return origIndexInBB; }
+};
-class SchedGraph : private hash_map<const MachineInstr*, SchedGraphNode*> {
- MachineBasicBlock &MBB; // basic blocks for this graph
- SchedGraphNode* graphRoot; // the root and leaf are not inserted
- SchedGraphNode* graphLeaf; // in the hash_map (see getNumNodes())
+class SchedGraph : public SchedGraphCommon {
+ MachineBasicBlock &MBB;
+ hash_map<const MachineInstr*, SchedGraphNode*> GraphMap;
- typedef hash_map<const MachineInstr*, SchedGraphNode*> map_base;
- SchedGraph(const SchedGraph &); // DO NOT IMPLEMENT
- void operator=(const SchedGraph &); // DO NOT IMPLEMENT
public:
- using map_base::iterator;
- using map_base::const_iterator;
-
-public:
- //
- // Accessor methods
- //
- MachineBasicBlock &getBasicBlock() const { return MBB; }
- unsigned getNumNodes() const { return size()+2; }
- SchedGraphNode* getRoot() const { return graphRoot; }
- SchedGraphNode* getLeaf() const { return graphLeaf; }
-
- SchedGraphNode* getGraphNodeForInstr(const MachineInstr* minstr) const {
- const_iterator onePair = this->find(minstr);
- return (onePair != this->end())? (*onePair).second : NULL;
+ typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator iterator;
+ typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
+
+ MachineBasicBlock& getBasicBlock() const{return MBB;}
+ const unsigned int getNumNodes() const { return GraphMap.size()+2; }
+ SchedGraphNode* getGraphNodeForInstr(const MachineInstr* MI) const {
+ const_iterator onePair = find(MI);
+ return (onePair != end())? onePair->second : NULL;
}
- //
- // Delete nodes or edges from the graph.
- //
- void eraseNode (SchedGraphNode* node);
-
- void eraseIncomingEdges (SchedGraphNode* node,
- bool addDummyEdges = true);
-
- void eraseOutgoingEdges (SchedGraphNode* node,
- bool addDummyEdges = true);
-
- void eraseIncidentEdges (SchedGraphNode* node,
- bool addDummyEdges = true);
+ // Debugging support
+ void dump () const;
- //
- // Unordered iterators.
- // Return values is pair<const MachineIntr*,SchedGraphNode*>.
- //
- using map_base::begin;
- using map_base::end;
+protected:
+ SchedGraph(MachineBasicBlock& mbb, const TargetMachine& TM);
+ ~SchedGraph();
- //
- // Ordered iterators.
+ // Unordered iterators.
// Return values is pair<const MachineIntr*,SchedGraphNode*>.
//
- // void postord_init();
- // postorder_iterator postord_begin();
- // postorder_iterator postord_end();
- // const_postorder_iterator postord_begin() const;
- // const_postorder_iterator postord_end() const;
+ hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator begin() const {
+ return GraphMap.begin();
+ }
+ hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator end() const {
+ return GraphMap.end();
+ }
+
+ unsigned size() { return GraphMap.size(); }
+ iterator find(const MachineInstr *MI) const { return GraphMap.find(MI); }
- //
- // Debugging support
- //
- void dump () const;
+ SchedGraphNode *&operator[](const MachineInstr *MI) {
+ return GraphMap[MI];
+ }
private:
friend class SchedGraphSet; // give access to ctor
- // disable default constructor and provide a ctor for single-block graphs
- /*ctor*/ SchedGraph (MachineBasicBlock &bb,
- const TargetMachine& target);
- /*dtor*/ ~SchedGraph ();
+
inline void noteGraphNodeForInstr (const MachineInstr* minstr,
SchedGraphNode* node)
//
void buildGraph (const TargetMachine& target);
- void buildNodesForBB (const TargetMachine& target,
+ void buildNodesForBB (const TargetMachine& target,
MachineBasicBlock &MBB,
std::vector<SchedGraphNode*>& memNV,
std::vector<SchedGraphNode*>& callNV,
RegToRefVecMap& regToRefVecMap,
ValueToDefVecMap& valueToDefVecMap);
+
void findDefUseInfoAtInstr (const TargetMachine& target,
SchedGraphNode* node,
std::vector<SchedGraphNode*>& callNV,
RegToRefVecMap& regToRefVecMap,
ValueToDefVecMap& valueToDefVecMap);
+
void addEdgesForInstruction(const MachineInstr& minstr,
const ValueToDefVecMap& valueToDefVecMap,
void addCDEdges (const TerminatorInst* term,
const TargetMachine& target);
- void addMemEdges (const std::vector<SchedGraphNode*>& memNV,
+ void addMemEdges (const std::vector<SchedGraphNode*>& memNod,
const TargetMachine& target);
+ void addCallCCEdges (const std::vector<SchedGraphNode*>& memNod,
+ MachineBasicBlock& bbMvec,
+ const TargetMachine& target);
void addCallDepEdges (const std::vector<SchedGraphNode*>& callNV,
const TargetMachine& target);
-
+
void addMachineRegEdges (RegToRefVecMap& regToRefVecMap,
const TargetMachine& target);
bool refNodeIsDef,
bool refNodeIsDefAndUse,
const TargetMachine& target);
-
- void addDummyEdges ();
+ void addDummyEdges();
+
};
-class SchedGraphSet : private std::vector<SchedGraph*> {
-private:
- const Function* method;
- SchedGraphSet(const SchedGraphSet&); // DO NOT IMPLEMENT
- void operator=(const SchedGraphSet&); // DO NOT IMPLEMENT
-public:
- typedef std::vector<SchedGraph*> baseVector;
- using baseVector::iterator;
- using baseVector::const_iterator;
-
+class SchedGraphSet {
+ const Function* function;
+ std::vector<SchedGraph*> Graphs;
+
+ // Graph builder
+ void buildGraphsForMethod (const Function *F, const TargetMachine& target);
+
+ inline void addGraph(SchedGraph* graph) {
+ assert(graph != NULL);
+ Graphs.push_back(graph);
+ }
+
public:
- SchedGraphSet(const Function *F, const TargetMachine &TM);
+ SchedGraphSet(const Function * function, const TargetMachine& target);
~SchedGraphSet();
- // Iterators
- using baseVector::begin;
- using baseVector::end;
-
+ //iterators
+ typedef std::vector<SchedGraph*>::const_iterator iterator;
+ typedef std::vector<SchedGraph*>::const_iterator const_iterator;
+
+ std::vector<SchedGraph*>::const_iterator begin() const { return Graphs.begin(); }
+ std::vector<SchedGraph*>::const_iterator end() const { return Graphs.end(); }
+
// Debugging support
void dump() const;
-
-private:
- inline void addGraph(SchedGraph* graph) {
- assert(graph != NULL);
- this->push_back(graph);
- }
-
- // Graph builder
- void buildGraphsForMethod(const Function *F, const TargetMachine &TM);
};
+
//********************** Sched Graph Iterators *****************************/
// Ok to make it a template because it shd get instantiated at most twice:
inline bool operator!=(const _Self& x) const { return !operator==(x); }
// operator*() differs for pred or succ iterator
- inline _NodeType* operator*() const { return (*oi)->getSrc(); }
+ inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
inline _NodeType* operator->() const { return operator*(); }
inline _EdgeType* getEdge() const { return *(oi); }
inline bool operator==(const _Self& x) const { return oi == x.oi; }
inline bool operator!=(const _Self& x) const { return !operator==(x); }
- inline _NodeType* operator*() const { return (*oi)->getSink(); }
+ inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
inline _NodeType* operator->() const { return operator*(); }
inline _EdgeType* getEdge() const { return *(oi); }
typedef SchedGraphNode NodeType;
typedef sg_succ_iterator ChildIteratorType;
- static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); }
+ static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); }
static inline ChildIteratorType child_begin(NodeType *N) {
return succ_begin(N);
}
typedef sg_succ_const_iterator ChildIteratorType;
static inline NodeType *getEntryNode(const SchedGraph *SG) {
- return SG->getRoot();
+ return (NodeType*)SG->getRoot();
}
static inline ChildIteratorType child_begin(NodeType *N) {
return succ_begin(N);
--- /dev/null
+#include "llvm/CodeGen/SchedGraphCommon.h"
+#include "Support/STLExtras.h"
+
+class SchedGraphCommon;
+
+//
+// class SchedGraphEdge
+//
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
+ SchedGraphNodeCommon* _sink,
+ SchedGraphEdgeDepType _depType,
+ unsigned int _depOrderType,
+ int _minDelay)
+ : src(_src),
+ sink(_sink),
+ depType(_depType),
+ depOrderType(_depOrderType),
+ minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
+ val(NULL)
+{
+ iteDiff=0;
+ assert(src != sink && "Self-loop in scheduling graph!");
+ src->addOutEdge(this);
+ sink->addInEdge(this);
+}
+
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
+ SchedGraphNodeCommon* _sink,
+ const Value* _val,
+ unsigned int _depOrderType,
+ int _minDelay)
+ : src(_src),
+ sink(_sink),
+ depType(ValueDep),
+ depOrderType(_depOrderType),
+ minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
+ val(_val)
+{
+ iteDiff=0;
+ assert(src != sink && "Self-loop in scheduling graph!");
+ src->addOutEdge(this);
+ sink->addInEdge(this);
+}
+
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
+ SchedGraphNodeCommon* _sink,
+ unsigned int _regNum,
+ unsigned int _depOrderType,
+ int _minDelay)
+ : src(_src),
+ sink(_sink),
+ depType(MachineRegister),
+ depOrderType(_depOrderType),
+ minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
+ machineRegNum(_regNum)
+{
+ iteDiff=0;
+ assert(src != sink && "Self-loop in scheduling graph!");
+ src->addOutEdge(this);
+ sink->addInEdge(this);
+}
+
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
+ SchedGraphNodeCommon* _sink,
+ ResourceId _resourceId,
+ int _minDelay)
+ : src(_src),
+ sink(_sink),
+ depType(MachineResource),
+ depOrderType(NonDataDep),
+ minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
+ resourceId(_resourceId)
+{
+ iteDiff=0;
+ assert(src != sink && "Self-loop in scheduling graph!");
+ src->addOutEdge(this);
+ sink->addInEdge(this);
+}
+
+/*dtor*/
+SchedGraphEdge::~SchedGraphEdge()
+{
+}
+
+void SchedGraphEdge::dump(int indent) const {
+ std::cerr << std::string(indent*2, ' ') << *this;
+}
+
+
+
+/*ctor*/
+
+SchedGraphNodeCommon::SchedGraphNodeCommon(unsigned _nodeId)
+ :ID(_nodeId),
+ latency(0){
+
+}
+
+/*dtor*/
+SchedGraphNodeCommon::~SchedGraphNodeCommon()
+{
+ // for each node, delete its out-edges
+ std::for_each(beginOutEdges(), endOutEdges(),
+ deleter<SchedGraphEdge>);
+}
+
+
+void SchedGraphNodeCommon::dump(int indent) const {
+ std::cerr << std::string(indent*2, ' ') << *this;
+}
+
+
+inline void
+SchedGraphNodeCommon::addInEdge(SchedGraphEdge* edge)
+{
+ inEdges.push_back(edge);
+}
+
+
+inline void
+SchedGraphNodeCommon::addOutEdge(SchedGraphEdge* edge)
+{
+ outEdges.push_back(edge);
+}
+
+inline void
+SchedGraphNodeCommon::removeInEdge(const SchedGraphEdge* edge)
+{
+ assert(edge->getSink() == this);
+
+ for (iterator I = beginInEdges(); I != endInEdges(); ++I)
+ if ((*I) == edge)
+ {
+ inEdges.erase(I);
+ break;
+ }
+}
+
+inline void
+SchedGraphNodeCommon::removeOutEdge(const SchedGraphEdge* edge)
+{
+ assert(edge->getSrc() == this);
+
+ for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
+ if ((*I) == edge)
+ {
+ outEdges.erase(I);
+ break;
+ }
+}
+
+
+//class SchedGraphCommon
+
+/*ctor*/
+SchedGraphCommon::SchedGraphCommon()
+{
+}
+
+
+/*dtor*/
+SchedGraphCommon::~SchedGraphCommon()
+{
+
+ delete graphRoot;
+ delete graphLeaf;
+}
+
+
+void
+SchedGraphCommon::eraseIncomingEdges(SchedGraphNodeCommon* node, bool addDummyEdges)
+{
+ // Delete and disconnect all in-edges for the node
+ for (SchedGraphNodeCommon::iterator I = node->beginInEdges();
+ I != node->endInEdges(); ++I)
+ {
+ SchedGraphNodeCommon* srcNode = (*I)->getSrc();
+ srcNode->removeOutEdge(*I);
+ delete *I;
+
+ if (addDummyEdges &&
+ srcNode != getRoot() &&
+ srcNode->beginOutEdges() == srcNode->endOutEdges())
+ { // srcNode has no more out edges, so add an edge to dummy EXIT node
+ assert(node != getLeaf() && "Adding edge that was just removed?");
+ (void) new SchedGraphEdge(srcNode, getLeaf(),
+ SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
+ }
+ }
+
+ node->inEdges.clear();
+}
+
+void
+SchedGraphCommon::eraseOutgoingEdges(SchedGraphNodeCommon* node, bool addDummyEdges)
+{
+ // Delete and disconnect all out-edges for the node
+ for (SchedGraphNodeCommon::iterator I = node->beginOutEdges();
+ I != node->endOutEdges(); ++I)
+ {
+ SchedGraphNodeCommon* sinkNode = (*I)->getSink();
+ sinkNode->removeInEdge(*I);
+ delete *I;
+
+ if (addDummyEdges &&
+ sinkNode != getLeaf() &&
+ sinkNode->beginInEdges() == sinkNode->endInEdges())
+ { //sinkNode has no more in edges, so add an edge from dummy ENTRY node
+ assert(node != getRoot() && "Adding edge that was just removed?");
+ (void) new SchedGraphEdge(getRoot(), sinkNode,
+ SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
+ }
+ }
+
+ node->outEdges.clear();
+}
+
+void
+SchedGraphCommon::eraseIncidentEdges(SchedGraphNodeCommon* node, bool addDummyEdges)
+{
+ this->eraseIncomingEdges(node, addDummyEdges);
+ this->eraseOutgoingEdges(node, addDummyEdges);
+}
+
+std::ostream &operator<<(std::ostream &os, const SchedGraphNodeCommon& node)
+{
+
+ return os;
+}
for (SchedGraphNode::const_iterator E=node->beginOutEdges();
E != node->endOutEdges(); ++E)
{
- cycles_t sinkDelay = getNodeDelay((*E)->getSink());
+ cycles_t sinkDelay = getNodeDelay((SchedGraphNode*)(*E)->getSink());
nodeDelay = std::max(nodeDelay, sinkDelay + (*E)->getMinDelay());
}
}
void
SchedPriorities::initializeReadyHeap(const SchedGraph* graph)
{
- const SchedGraphNode* graphRoot = graph->getRoot();
+ const SchedGraphNode* graphRoot = (const SchedGraphNode*)graph->getRoot();
assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root");
// Insert immediate successors of dummy root, which are the actual roots
for (SchedGraphNode::const_iterator E=node->beginOutEdges();
E != node->endOutEdges(); ++E)
{
- cycles_t& etime = getEarliestReadyTimeForNodeRef((*E)->getSink());
+ cycles_t& etime = getEarliestReadyTimeForNodeRef((SchedGraphNode*)(*E)->getSink());
etime = std::max(etime, curTime + (*E)->getMinDelay());
}
}
for (SchedGraphNode::const_iterator EI = node->beginInEdges();
EI != node->endInEdges(); ++EI)
- if (! (*EI)->getSrc()->isDummyNode()
- && mii.isLoad((*EI)->getSrc()->getOpCode())
+ if (! ((SchedGraphNode*)(*EI)->getSrc())->isDummyNode()
+ && mii.isLoad(((SchedGraphNode*)(*EI)->getSrc())->getOpCode())
&& (*EI)->getDepType() == SchedGraphEdge::CtrlDep)
return false;
bool onlyCDEdgeToBranch = true;
for (SchedGraphNode::const_iterator OEI = node->beginOutEdges();
OEI != node->endOutEdges(); ++OEI)
- if (! (*OEI)->getSink()->isDummyNode()
+ if (! ((SchedGraphNode*)(*OEI)->getSink())->isDummyNode()
&& ((*OEI)->getSink() != brNode
|| (*OEI)->getDepType() != SchedGraphEdge::CtrlDep))
{
//===----------------------------------------------------------------------===//
#include "SchedGraph.h"
-#include "llvm/CodeGen/InstrSelection.h"
-#include "llvm/CodeGen/MachineCodeForInstruction.h"
-#include "llvm/CodeGen/MachineFunction.h"
-#include "llvm/Target/TargetRegInfo.h"
+#include "llvm/CodeGen/SchedGraphCommon.h"
+#include <iostream>
+
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
+#include "Support/STLExtras.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/CodeGen/MachineCodeForInstruction.h"
+#include "llvm/Target/TargetRegInfo.h"
#include "llvm/Function.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/InstrSelection.h"
#include "llvm/iOther.h"
#include "Support/StringExtras.h"
-#include "Support/STLExtras.h"
+
//*********************** Internal Data Structures *************************/
typedef hash_map<const Value*, RefVec>::const_iterator const_iterator;
};
-//
-// class SchedGraphEdge
-//
-
-/*ctor*/
-SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- SchedGraphEdgeDepType _depType,
- unsigned int _depOrderType,
- int _minDelay)
- : src(_src),
- sink(_sink),
- depType(_depType),
- depOrderType(_depOrderType),
- minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
- val(NULL)
-{
- assert(src != sink && "Self-loop in scheduling graph!");
- src->addOutEdge(this);
- sink->addInEdge(this);
-}
-
-
-/*ctor*/
-SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- const Value* _val,
- unsigned int _depOrderType,
- int _minDelay)
- : src(_src),
- sink(_sink),
- depType(ValueDep),
- depOrderType(_depOrderType),
- minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
- val(_val)
-{
- assert(src != sink && "Self-loop in scheduling graph!");
- src->addOutEdge(this);
- sink->addInEdge(this);
-}
-
-
-/*ctor*/
-SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- unsigned int _regNum,
- unsigned int _depOrderType,
- int _minDelay)
- : src(_src),
- sink(_sink),
- depType(MachineRegister),
- depOrderType(_depOrderType),
- minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
- machineRegNum(_regNum)
-{
- assert(src != sink && "Self-loop in scheduling graph!");
- src->addOutEdge(this);
- sink->addInEdge(this);
-}
-
-
-/*ctor*/
-SchedGraphEdge::SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- ResourceId _resourceId,
- int _minDelay)
- : src(_src),
- sink(_sink),
- depType(MachineResource),
- depOrderType(NonDataDep),
- minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
- resourceId(_resourceId)
-{
- assert(src != sink && "Self-loop in scheduling graph!");
- src->addOutEdge(this);
- sink->addInEdge(this);
-}
-
-/*dtor*/
-SchedGraphEdge::~SchedGraphEdge()
-{
-}
-
-void SchedGraphEdge::dump(int indent) const {
- std::cerr << std::string(indent*2, ' ') << *this;
-}
-
//
// class SchedGraphNode
MachineBasicBlock *mbb,
int indexInBB,
const TargetMachine& Target)
- : nodeId(NID), MBB(mbb), minstr(mbb ? (*mbb)[indexInBB] : 0),
- origIndexInBB(indexInBB), latency(0) {
- if (minstr)
+ : SchedGraphNodeCommon(NID), origIndexInBB(indexInBB), MBB(mbb), MI(mbb ? (*mbb)[indexInBB] : 0)
+ {
+ if (MI)
{
- MachineOpCode mopCode = minstr->getOpCode();
+ MachineOpCode mopCode = MI->getOpCode();
latency = Target.getInstrInfo().hasResultInterlock(mopCode)
? Target.getInstrInfo().minLatency(mopCode)
: Target.getInstrInfo().maxLatency(mopCode);
deleter<SchedGraphEdge>);
}
-void SchedGraphNode::dump(int indent) const {
- std::cerr << std::string(indent*2, ' ') << *this;
-}
-
-
-inline void
-SchedGraphNode::addInEdge(SchedGraphEdge* edge)
-{
- inEdges.push_back(edge);
-}
-
-
-inline void
-SchedGraphNode::addOutEdge(SchedGraphEdge* edge)
-{
- outEdges.push_back(edge);
-}
-
-inline void
-SchedGraphNode::removeInEdge(const SchedGraphEdge* edge)
-{
- assert(edge->getSink() == this);
-
- for (iterator I = beginInEdges(); I != endInEdges(); ++I)
- if ((*I) == edge)
- {
- inEdges.erase(I);
- break;
- }
-}
-
-inline void
-SchedGraphNode::removeOutEdge(const SchedGraphEdge* edge)
-{
- assert(edge->getSrc() == this);
-
- for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
- if ((*I) == edge)
- {
- outEdges.erase(I);
- break;
- }
-}
-
-
//
// class SchedGraph
//
}
-void
-SchedGraph::eraseIncomingEdges(SchedGraphNode* node, bool addDummyEdges)
-{
- // Delete and disconnect all in-edges for the node
- for (SchedGraphNode::iterator I = node->beginInEdges();
- I != node->endInEdges(); ++I)
- {
- SchedGraphNode* srcNode = (*I)->getSrc();
- srcNode->removeOutEdge(*I);
- delete *I;
-
- if (addDummyEdges &&
- srcNode != getRoot() &&
- srcNode->beginOutEdges() == srcNode->endOutEdges())
- {
- // srcNode has no more out edges, so add an edge to dummy EXIT node
- assert(node != getLeaf() && "Adding edge that was just removed?");
- (void) new SchedGraphEdge(srcNode, getLeaf(),
- SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
- }
- }
-
- node->inEdges.clear();
-}
-
-void
-SchedGraph::eraseOutgoingEdges(SchedGraphNode* node, bool addDummyEdges)
-{
- // Delete and disconnect all out-edges for the node
- for (SchedGraphNode::iterator I = node->beginOutEdges();
- I != node->endOutEdges(); ++I)
- {
- SchedGraphNode* sinkNode = (*I)->getSink();
- sinkNode->removeInEdge(*I);
- delete *I;
-
- if (addDummyEdges &&
- sinkNode != getLeaf() &&
- sinkNode->beginInEdges() == sinkNode->endInEdges())
- { //sinkNode has no more in edges, so add an edge from dummy ENTRY node
- assert(node != getRoot() && "Adding edge that was just removed?");
- (void) new SchedGraphEdge(getRoot(), sinkNode,
- SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
- }
- }
-
- node->outEdges.clear();
-}
-
-void
-SchedGraph::eraseIncidentEdges(SchedGraphNode* node, bool addDummyEdges)
-{
- this->eraseIncomingEdges(node, addDummyEdges);
- this->eraseOutgoingEdges(node, addDummyEdges);
-}
-
void
SchedGraph::addDummyEdges()
// Collect the register references and value defs. for explicit operands
//
- const MachineInstr& minstr = *node->getMachineInstr();
- for (int i=0, numOps = (int) minstr.getNumOperands(); i < numOps; i++)
+ const MachineInstr& MI = *node->getMachineInstr();
+ for (int i=0, numOps = (int) MI.getNumOperands(); i < numOps; i++)
{
- const MachineOperand& mop = minstr.getOperand(i);
+ const MachineOperand& mop = MI.getOperand(i);
// if this references a register other than the hardwired
// "zero" register, record the reference.
}
// ignore all other non-def operands
- if (!minstr.getOperand(i).opIsDefOnly() &&
- !minstr.getOperand(i).opIsDefAndUse())
+ if (!MI.getOperand(i).opIsDefOnly() &&
+ !MI.getOperand(i).opIsDefAndUse())
continue;
// We must be defining a value.
// Collect value defs. for implicit operands. They may have allocated
// physical registers also.
//
- for (unsigned i=0, N = minstr.getNumImplicitRefs(); i != N; ++i)
+ for (unsigned i=0, N = MI.getNumImplicitRefs(); i != N; ++i)
{
- const MachineOperand& mop = minstr.getImplicitOp(i);
+ const MachineOperand& mop = MI.getImplicitOp(i);
if (mop.hasAllocatedReg())
{
int regNum = mop.getAllocatedRegNum();
if (regNum != target.getRegInfo().getZeroRegNum())
regToRefVecMap[mop.getAllocatedRegNum()]
- .push_back(std::make_pair(node, i + minstr.getNumOperands()));
+ .push_back(std::make_pair(node, i + MI.getNumOperands()));
continue; // nothing more to do
}
if (mop.opIsDefOnly() || mop.opIsDefAndUse()) {
- assert(minstr.getImplicitRef(i) != NULL && "Null value being defined?");
- valueToDefVecMap[minstr.getImplicitRef(i)].push_back(std::make_pair(node,
+ assert(MI.getImplicitRef(i) != NULL && "Null value being defined?");
+ valueToDefVecMap[MI.getImplicitRef(i)].push_back(std::make_pair(node,
-i));
}
}
/*ctor*/
SchedGraphSet::SchedGraphSet(const Function* _function,
const TargetMachine& target) :
- method(_function)
+ function(_function)
{
- buildGraphsForMethod(method, target);
+ buildGraphsForMethod(function, target);
}
void
SchedGraphSet::dump() const
{
- std::cerr << "======== Sched graphs for function `" << method->getName()
+ std::cerr << "======== Sched graphs for function `" << function->getName()
<< "' ========\n\n";
for (const_iterator I=begin(); I != end(); ++I)
(*I)->dump();
- std::cerr << "\n====== End graphs for function `" << method->getName()
+ std::cerr << "\n====== End graphs for function `" << function->getName()
<< "' ========\n\n";
}
std::ostream &operator<<(std::ostream &os, const SchedGraphNode& node)
{
os << std::string(8, ' ')
- << "Node " << node.nodeId << " : "
+ << "Node " << node.ID << " : "
<< "latency = " << node.latency << "\n" << std::string(12, ' ');
if (node.getMachineInstr() == NULL)
#include "llvm/CodeGen/MachineInstr.h"
#include "Support/GraphTraits.h"
#include "Support/hash_map"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/CodeGen/SchedGraphCommon.h"
-class Value;
-class Instruction;
-class TerminatorInst;
-class BasicBlock;
-class Function;
-class TargetMachine;
-class SchedGraphEdge;
-class SchedGraphNode;
-class SchedGraph;
class RegToRefVecMap;
class ValueToDefVecMap;
class RefVec;
-class MachineInstr;
-class MachineBasicBlock;
+class SchedGraphNode : public SchedGraphNodeCommon {
-/******************** Exported Data Types and Constants ********************/
-
-typedef int ResourceId;
-const ResourceId InvalidRID = -1;
-const ResourceId MachineCCRegsRID = -2; // use +ve numbers for actual regs
-const ResourceId MachineIntRegsRID = -3; // use +ve numbers for actual regs
-const ResourceId MachineFPRegsRID = -4; // use +ve numbers for actual regs
-
-
-//*********************** Public Class Declarations ************************/
-
-class SchedGraphEdge {
- SchedGraphEdge(const SchedGraphEdge &); // DO NOT IMPLEMENT
- void operator=(const SchedGraphEdge &); // DO NOT IMPLEMENT
-public:
- enum SchedGraphEdgeDepType {
- CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
- };
- enum DataDepOrderType {
- TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
- };
-
-private:
- SchedGraphNode* src;
- SchedGraphNode* sink;
- SchedGraphEdgeDepType depType;
- unsigned int depOrderType;
- int minDelay; // cached latency (assumes fixed target arch)
-
- union {
- const Value* val;
- int machineRegNum;
- ResourceId resourceId;
- };
-
-public:
- // For all constructors, if minDelay is unspecified, minDelay is
- // set to _src->getLatency().
- // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
- /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- SchedGraphEdgeDepType _depType,
- unsigned int _depOrderType,
- int _minDelay = -1);
-
- // constructor for explicit value dependence (may be true/anti/output)
- /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- const Value* _val,
- unsigned int _depOrderType,
- int _minDelay = -1);
-
- // constructor for machine register dependence
- /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- unsigned int _regNum,
- unsigned int _depOrderType,
- int _minDelay = -1);
-
- // constructor for any other machine resource dependences.
- // DataDepOrderType is always NonDataDep. It it not an argument to
- // avoid overloading ambiguity with previous constructor.
- /*ctor*/ SchedGraphEdge(SchedGraphNode* _src,
- SchedGraphNode* _sink,
- ResourceId _resourceId,
- int _minDelay = -1);
-
- /*dtor*/ ~SchedGraphEdge();
-
- SchedGraphNode* getSrc () const { return src; }
- SchedGraphNode* getSink () const { return sink; }
- int getMinDelay () const { return minDelay; }
- SchedGraphEdgeDepType getDepType () const { return depType; }
-
- const Value* getValue () const {
- assert(depType == ValueDep); return val;
- }
- int getMachineReg () const {
- assert(depType == MachineRegister); return machineRegNum;
- }
- int getResourceId () const {
- assert(depType == MachineResource); return resourceId;
- }
-
-public:
- //
- // Debugging support
- //
- friend std::ostream& operator<<(std::ostream& os, const SchedGraphEdge& edge);
-
- void dump (int indent=0) const;
-
-private:
- // disable default ctor
- /*ctor*/ SchedGraphEdge(); // DO NOT IMPLEMENT
-};
+ int origIndexInBB; // original position of machine instr in BB
+ MachineBasicBlock *MBB;
+ const MachineInstr *MI;
+ SchedGraphNode (unsigned nodeId, MachineBasicBlock *mbb,
+ int indexInBB, const TargetMachine& Target);
+ ~SchedGraphNode ();
-class SchedGraphNode {
- unsigned nodeId;
- MachineBasicBlock *MBB;
- const MachineInstr* minstr;
- std::vector<SchedGraphEdge*> inEdges;
- std::vector<SchedGraphEdge*> outEdges;
- int origIndexInBB; // original position of machine instr in BB
- int latency;
+ friend class SchedGraph; // give access for ctor and dtor
+ friend class SchedGraphEdge; // give access for adding edges
- SchedGraphNode(const SchedGraphNode &); // DO NOT IMPLEMENT
- void operator=(const SchedGraphNode &); // DO NOT IMPLEMENT
-public:
- typedef std::vector<SchedGraphEdge*>:: iterator iterator;
- typedef std::vector<SchedGraphEdge*>::const_iterator const_iterator;
- typedef std::vector<SchedGraphEdge*>:: reverse_iterator reverse_iterator;
- typedef std::vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;
-
public:
- //
// Accessor methods
- //
- unsigned getNodeId () const { return nodeId; }
- const MachineInstr* getMachineInstr () const { return minstr; }
- const MachineOpCode getOpCode () const { return minstr->getOpCode(); }
- int getLatency () const { return latency; }
- unsigned getNumInEdges () const { return inEdges.size(); }
- unsigned getNumOutEdges () const { return outEdges.size(); }
- bool isDummyNode () const { return (minstr == NULL); }
+ const MachineInstr* getMachineInstr () const { return MI; }
+ const MachineOpCode getOpCode () const { return MI->getOpCode(); }
+ bool isDummyNode () const { return (MI == NULL); }
MachineBasicBlock &getMachineBasicBlock() const { return *MBB; }
- int getOrigIndexInBB() const { return origIndexInBB; }
-
- //
- // Iterators
- //
- iterator beginInEdges () { return inEdges.begin(); }
- iterator endInEdges () { return inEdges.end(); }
- iterator beginOutEdges () { return outEdges.begin(); }
- iterator endOutEdges () { return outEdges.end(); }
-
- const_iterator beginInEdges () const { return inEdges.begin(); }
- const_iterator endInEdges () const { return inEdges.end(); }
- const_iterator beginOutEdges () const { return outEdges.begin(); }
- const_iterator endOutEdges () const { return outEdges.end(); }
-
-public:
- //
- // Debugging support
- //
- friend std::ostream& operator<<(std::ostream& os, const SchedGraphNode& node);
-
- void dump (int indent=0) const;
-
-private:
- friend class SchedGraph; // give access for ctor and dtor
- friend class SchedGraphEdge; // give access for adding edges
-
- void addInEdge (SchedGraphEdge* edge);
- void addOutEdge (SchedGraphEdge* edge);
-
- void removeInEdge (const SchedGraphEdge* edge);
- void removeOutEdge (const SchedGraphEdge* edge);
-
- // disable default constructor and provide a ctor for single-block graphs
- /*ctor*/ SchedGraphNode(); // DO NOT IMPLEMENT
- /*ctor*/ SchedGraphNode (unsigned nodeId,
- MachineBasicBlock *mbb,
- int indexInBB,
- const TargetMachine& Target);
- /*dtor*/ ~SchedGraphNode ();
-};
-
+ int getOrigIndexInBB() const { return origIndexInBB; }
+};
-class SchedGraph : private hash_map<const MachineInstr*, SchedGraphNode*> {
- MachineBasicBlock &MBB; // basic blocks for this graph
- SchedGraphNode* graphRoot; // the root and leaf are not inserted
- SchedGraphNode* graphLeaf; // in the hash_map (see getNumNodes())
+class SchedGraph : public SchedGraphCommon {
+ MachineBasicBlock &MBB;
+ hash_map<const MachineInstr*, SchedGraphNode*> GraphMap;
- typedef hash_map<const MachineInstr*, SchedGraphNode*> map_base;
- SchedGraph(const SchedGraph &); // DO NOT IMPLEMENT
- void operator=(const SchedGraph &); // DO NOT IMPLEMENT
public:
- using map_base::iterator;
- using map_base::const_iterator;
-
-public:
- //
- // Accessor methods
- //
- MachineBasicBlock &getBasicBlock() const { return MBB; }
- unsigned getNumNodes() const { return size()+2; }
- SchedGraphNode* getRoot() const { return graphRoot; }
- SchedGraphNode* getLeaf() const { return graphLeaf; }
-
- SchedGraphNode* getGraphNodeForInstr(const MachineInstr* minstr) const {
- const_iterator onePair = this->find(minstr);
- return (onePair != this->end())? (*onePair).second : NULL;
+ typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator iterator;
+ typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
+
+ MachineBasicBlock& getBasicBlock() const{return MBB;}
+ const unsigned int getNumNodes() const { return GraphMap.size()+2; }
+ SchedGraphNode* getGraphNodeForInstr(const MachineInstr* MI) const {
+ const_iterator onePair = find(MI);
+ return (onePair != end())? onePair->second : NULL;
}
- //
- // Delete nodes or edges from the graph.
- //
- void eraseNode (SchedGraphNode* node);
-
- void eraseIncomingEdges (SchedGraphNode* node,
- bool addDummyEdges = true);
-
- void eraseOutgoingEdges (SchedGraphNode* node,
- bool addDummyEdges = true);
-
- void eraseIncidentEdges (SchedGraphNode* node,
- bool addDummyEdges = true);
+ // Debugging support
+ void dump () const;
- //
- // Unordered iterators.
- // Return values is pair<const MachineIntr*,SchedGraphNode*>.
- //
- using map_base::begin;
- using map_base::end;
+protected:
+ SchedGraph(MachineBasicBlock& mbb, const TargetMachine& TM);
+ ~SchedGraph();
- //
- // Ordered iterators.
+ // Unordered iterators.
// Return values is pair<const MachineIntr*,SchedGraphNode*>.
//
- // void postord_init();
- // postorder_iterator postord_begin();
- // postorder_iterator postord_end();
- // const_postorder_iterator postord_begin() const;
- // const_postorder_iterator postord_end() const;
+ hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator begin() const {
+ return GraphMap.begin();
+ }
+ hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator end() const {
+ return GraphMap.end();
+ }
+
+ unsigned size() { return GraphMap.size(); }
+ iterator find(const MachineInstr *MI) const { return GraphMap.find(MI); }
- //
- // Debugging support
- //
- void dump () const;
+ SchedGraphNode *&operator[](const MachineInstr *MI) {
+ return GraphMap[MI];
+ }
private:
friend class SchedGraphSet; // give access to ctor
- // disable default constructor and provide a ctor for single-block graphs
- /*ctor*/ SchedGraph (MachineBasicBlock &bb,
- const TargetMachine& target);
- /*dtor*/ ~SchedGraph ();
+
inline void noteGraphNodeForInstr (const MachineInstr* minstr,
SchedGraphNode* node)
//
void buildGraph (const TargetMachine& target);
- void buildNodesForBB (const TargetMachine& target,
+ void buildNodesForBB (const TargetMachine& target,
MachineBasicBlock &MBB,
std::vector<SchedGraphNode*>& memNV,
std::vector<SchedGraphNode*>& callNV,
RegToRefVecMap& regToRefVecMap,
ValueToDefVecMap& valueToDefVecMap);
+
void findDefUseInfoAtInstr (const TargetMachine& target,
SchedGraphNode* node,
std::vector<SchedGraphNode*>& callNV,
RegToRefVecMap& regToRefVecMap,
ValueToDefVecMap& valueToDefVecMap);
+
void addEdgesForInstruction(const MachineInstr& minstr,
const ValueToDefVecMap& valueToDefVecMap,
void addCDEdges (const TerminatorInst* term,
const TargetMachine& target);
- void addMemEdges (const std::vector<SchedGraphNode*>& memNV,
+ void addMemEdges (const std::vector<SchedGraphNode*>& memNod,
const TargetMachine& target);
+ void addCallCCEdges (const std::vector<SchedGraphNode*>& memNod,
+ MachineBasicBlock& bbMvec,
+ const TargetMachine& target);
void addCallDepEdges (const std::vector<SchedGraphNode*>& callNV,
const TargetMachine& target);
-
+
void addMachineRegEdges (RegToRefVecMap& regToRefVecMap,
const TargetMachine& target);
bool refNodeIsDef,
bool refNodeIsDefAndUse,
const TargetMachine& target);
-
- void addDummyEdges ();
+ void addDummyEdges();
+
};
-class SchedGraphSet : private std::vector<SchedGraph*> {
-private:
- const Function* method;
- SchedGraphSet(const SchedGraphSet&); // DO NOT IMPLEMENT
- void operator=(const SchedGraphSet&); // DO NOT IMPLEMENT
-public:
- typedef std::vector<SchedGraph*> baseVector;
- using baseVector::iterator;
- using baseVector::const_iterator;
-
+class SchedGraphSet {
+ const Function* function;
+ std::vector<SchedGraph*> Graphs;
+
+ // Graph builder
+ void buildGraphsForMethod (const Function *F, const TargetMachine& target);
+
+ inline void addGraph(SchedGraph* graph) {
+ assert(graph != NULL);
+ Graphs.push_back(graph);
+ }
+
public:
- SchedGraphSet(const Function *F, const TargetMachine &TM);
+ SchedGraphSet(const Function * function, const TargetMachine& target);
~SchedGraphSet();
- // Iterators
- using baseVector::begin;
- using baseVector::end;
-
+ //iterators
+ typedef std::vector<SchedGraph*>::const_iterator iterator;
+ typedef std::vector<SchedGraph*>::const_iterator const_iterator;
+
+ std::vector<SchedGraph*>::const_iterator begin() const { return Graphs.begin(); }
+ std::vector<SchedGraph*>::const_iterator end() const { return Graphs.end(); }
+
// Debugging support
void dump() const;
-
-private:
- inline void addGraph(SchedGraph* graph) {
- assert(graph != NULL);
- this->push_back(graph);
- }
-
- // Graph builder
- void buildGraphsForMethod(const Function *F, const TargetMachine &TM);
};
+
//********************** Sched Graph Iterators *****************************/
// Ok to make it a template because it shd get instantiated at most twice:
inline bool operator!=(const _Self& x) const { return !operator==(x); }
// operator*() differs for pred or succ iterator
- inline _NodeType* operator*() const { return (*oi)->getSrc(); }
+ inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
inline _NodeType* operator->() const { return operator*(); }
inline _EdgeType* getEdge() const { return *(oi); }
inline bool operator==(const _Self& x) const { return oi == x.oi; }
inline bool operator!=(const _Self& x) const { return !operator==(x); }
- inline _NodeType* operator*() const { return (*oi)->getSink(); }
+ inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
inline _NodeType* operator->() const { return operator*(); }
inline _EdgeType* getEdge() const { return *(oi); }
typedef SchedGraphNode NodeType;
typedef sg_succ_iterator ChildIteratorType;
- static inline NodeType *getEntryNode(SchedGraph *SG) { return SG->getRoot(); }
+ static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); }
static inline ChildIteratorType child_begin(NodeType *N) {
return succ_begin(N);
}
typedef sg_succ_const_iterator ChildIteratorType;
static inline NodeType *getEntryNode(const SchedGraph *SG) {
- return SG->getRoot();
+ return (NodeType*)SG->getRoot();
}
static inline ChildIteratorType child_begin(NodeType *N) {
return succ_begin(N);
--- /dev/null
+#include "llvm/CodeGen/SchedGraphCommon.h"
+#include "Support/STLExtras.h"
+
+class SchedGraphCommon;
+
+//
+// class SchedGraphEdge
+//
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
+ SchedGraphNodeCommon* _sink,
+ SchedGraphEdgeDepType _depType,
+ unsigned int _depOrderType,
+ int _minDelay)
+ : src(_src),
+ sink(_sink),
+ depType(_depType),
+ depOrderType(_depOrderType),
+ minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
+ val(NULL)
+{
+ iteDiff=0;
+ assert(src != sink && "Self-loop in scheduling graph!");
+ src->addOutEdge(this);
+ sink->addInEdge(this);
+}
+
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
+ SchedGraphNodeCommon* _sink,
+ const Value* _val,
+ unsigned int _depOrderType,
+ int _minDelay)
+ : src(_src),
+ sink(_sink),
+ depType(ValueDep),
+ depOrderType(_depOrderType),
+ minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
+ val(_val)
+{
+ iteDiff=0;
+ assert(src != sink && "Self-loop in scheduling graph!");
+ src->addOutEdge(this);
+ sink->addInEdge(this);
+}
+
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
+ SchedGraphNodeCommon* _sink,
+ unsigned int _regNum,
+ unsigned int _depOrderType,
+ int _minDelay)
+ : src(_src),
+ sink(_sink),
+ depType(MachineRegister),
+ depOrderType(_depOrderType),
+ minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
+ machineRegNum(_regNum)
+{
+ iteDiff=0;
+ assert(src != sink && "Self-loop in scheduling graph!");
+ src->addOutEdge(this);
+ sink->addInEdge(this);
+}
+
+
+/*ctor*/
+SchedGraphEdge::SchedGraphEdge(SchedGraphNodeCommon* _src,
+ SchedGraphNodeCommon* _sink,
+ ResourceId _resourceId,
+ int _minDelay)
+ : src(_src),
+ sink(_sink),
+ depType(MachineResource),
+ depOrderType(NonDataDep),
+ minDelay((_minDelay >= 0)? _minDelay : _src->getLatency()),
+ resourceId(_resourceId)
+{
+ iteDiff=0;
+ assert(src != sink && "Self-loop in scheduling graph!");
+ src->addOutEdge(this);
+ sink->addInEdge(this);
+}
+
+/*dtor*/
+SchedGraphEdge::~SchedGraphEdge()
+{
+}
+
+void SchedGraphEdge::dump(int indent) const {
+ std::cerr << std::string(indent*2, ' ') << *this;
+}
+
+
+
+/*ctor*/
+
+SchedGraphNodeCommon::SchedGraphNodeCommon(unsigned _nodeId)
+ :ID(_nodeId),
+ latency(0){
+
+}
+
+/*dtor*/
+SchedGraphNodeCommon::~SchedGraphNodeCommon()
+{
+ // for each node, delete its out-edges
+ std::for_each(beginOutEdges(), endOutEdges(),
+ deleter<SchedGraphEdge>);
+}
+
+
+void SchedGraphNodeCommon::dump(int indent) const {
+ std::cerr << std::string(indent*2, ' ') << *this;
+}
+
+
+inline void
+SchedGraphNodeCommon::addInEdge(SchedGraphEdge* edge)
+{
+ inEdges.push_back(edge);
+}
+
+
+inline void
+SchedGraphNodeCommon::addOutEdge(SchedGraphEdge* edge)
+{
+ outEdges.push_back(edge);
+}
+
+inline void
+SchedGraphNodeCommon::removeInEdge(const SchedGraphEdge* edge)
+{
+ assert(edge->getSink() == this);
+
+ for (iterator I = beginInEdges(); I != endInEdges(); ++I)
+ if ((*I) == edge)
+ {
+ inEdges.erase(I);
+ break;
+ }
+}
+
+inline void
+SchedGraphNodeCommon::removeOutEdge(const SchedGraphEdge* edge)
+{
+ assert(edge->getSrc() == this);
+
+ for (iterator I = beginOutEdges(); I != endOutEdges(); ++I)
+ if ((*I) == edge)
+ {
+ outEdges.erase(I);
+ break;
+ }
+}
+
+
+//class SchedGraphCommon
+
+/*ctor*/
+SchedGraphCommon::SchedGraphCommon()
+{
+}
+
+
+/*dtor*/
+SchedGraphCommon::~SchedGraphCommon()
+{
+
+ delete graphRoot;
+ delete graphLeaf;
+}
+
+
+void
+SchedGraphCommon::eraseIncomingEdges(SchedGraphNodeCommon* node, bool addDummyEdges)
+{
+ // Delete and disconnect all in-edges for the node
+ for (SchedGraphNodeCommon::iterator I = node->beginInEdges();
+ I != node->endInEdges(); ++I)
+ {
+ SchedGraphNodeCommon* srcNode = (*I)->getSrc();
+ srcNode->removeOutEdge(*I);
+ delete *I;
+
+ if (addDummyEdges &&
+ srcNode != getRoot() &&
+ srcNode->beginOutEdges() == srcNode->endOutEdges())
+ { // srcNode has no more out edges, so add an edge to dummy EXIT node
+ assert(node != getLeaf() && "Adding edge that was just removed?");
+ (void) new SchedGraphEdge(srcNode, getLeaf(),
+ SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
+ }
+ }
+
+ node->inEdges.clear();
+}
+
+void
+SchedGraphCommon::eraseOutgoingEdges(SchedGraphNodeCommon* node, bool addDummyEdges)
+{
+ // Delete and disconnect all out-edges for the node
+ for (SchedGraphNodeCommon::iterator I = node->beginOutEdges();
+ I != node->endOutEdges(); ++I)
+ {
+ SchedGraphNodeCommon* sinkNode = (*I)->getSink();
+ sinkNode->removeInEdge(*I);
+ delete *I;
+
+ if (addDummyEdges &&
+ sinkNode != getLeaf() &&
+ sinkNode->beginInEdges() == sinkNode->endInEdges())
+ { //sinkNode has no more in edges, so add an edge from dummy ENTRY node
+ assert(node != getRoot() && "Adding edge that was just removed?");
+ (void) new SchedGraphEdge(getRoot(), sinkNode,
+ SchedGraphEdge::CtrlDep, SchedGraphEdge::NonDataDep, 0);
+ }
+ }
+
+ node->outEdges.clear();
+}
+
+void
+SchedGraphCommon::eraseIncidentEdges(SchedGraphNodeCommon* node, bool addDummyEdges)
+{
+ this->eraseIncomingEdges(node, addDummyEdges);
+ this->eraseOutgoingEdges(node, addDummyEdges);
+}
+
+std::ostream &operator<<(std::ostream &os, const SchedGraphNodeCommon& node)
+{
+
+ return os;
+}
for (SchedGraphNode::const_iterator E=node->beginOutEdges();
E != node->endOutEdges(); ++E)
{
- cycles_t sinkDelay = getNodeDelay((*E)->getSink());
+ cycles_t sinkDelay = getNodeDelay((SchedGraphNode*)(*E)->getSink());
nodeDelay = std::max(nodeDelay, sinkDelay + (*E)->getMinDelay());
}
}
void
SchedPriorities::initializeReadyHeap(const SchedGraph* graph)
{
- const SchedGraphNode* graphRoot = graph->getRoot();
+ const SchedGraphNode* graphRoot = (const SchedGraphNode*)graph->getRoot();
assert(graphRoot->getMachineInstr() == NULL && "Expect dummy root");
// Insert immediate successors of dummy root, which are the actual roots
for (SchedGraphNode::const_iterator E=node->beginOutEdges();
E != node->endOutEdges(); ++E)
{
- cycles_t& etime = getEarliestReadyTimeForNodeRef((*E)->getSink());
+ cycles_t& etime = getEarliestReadyTimeForNodeRef((SchedGraphNode*)(*E)->getSink());
etime = std::max(etime, curTime + (*E)->getMinDelay());
}
}
projects / oota-llvm.git / commitdiff