-//===-- SchedGraph.h - Scheduling Graph --------------------------*- C++ -*--=//
+//===-- SchedGraph.h - Scheduling Graph -------------------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
//
-// Purpose:
-// Scheduling graph based on SSA graph plus extra dependence edges
-// capturing dependences due to machine resources (machine registers,
-// CC registers, and any others).
+// This is a scheduling graph based on SSA graph plus extra dependence edges
+// capturing dependences due to machine resources (machine registers, CC
+// registers, and any others).
//
-// Strategy:
-// This graph tries to leverage the SSA graph as much as possible,
-// but captures the extra dependences through a common interface.
+// This graph tries to leverage the SSA graph as much as possible, but captures
+// the extra dependences through a common interface.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_SCHEDGRAPH_H
#define LLVM_CODEGEN_SCHEDGRAPH_H
+#include "llvm/CodeGen/SchedGraphCommon.h"
#include "llvm/CodeGen/MachineInstr.h"
-#include "Support/GraphTraits.h"
-#include "Support/hash_map"
#include "llvm/Transforms/Scalar.h"
-#include "llvm/CodeGen/SchedGraphCommon.h"
+#include "llvm/ADT/hash_map"
+#include "llvm/ADT/GraphTraits.h"
+
+namespace llvm {
class RegToRefVecMap;
class ValueToDefVecMap;
class SchedGraphNode : public SchedGraphNodeCommon {
- 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 ();
+ SchedGraphNode(unsigned nodeId, MachineBasicBlock *mbb, int indexInBB,
+ const TargetMachine& Target);
+ ~SchedGraphNode();
friend class SchedGraph; // give access for ctor and dtor
friend class SchedGraphEdge; // give access for adding edges
public:
+
// Accessor methods
- const MachineInstr* getMachineInstr () const { return MI; }
- const MachineOpCode getOpCode () const { return MI->getOpCode(); }
- bool isDummyNode () const { return (MI == NULL); }
- MachineBasicBlock &getMachineBasicBlock() const { return *MBB; }
+ 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; }
+ void print(std::ostream &os) const;
};
class SchedGraph : public SchedGraphCommon {
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; }
+ 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;
}
// Debugging support
- void dump () const;
+ void dump() const;
protected:
SchedGraph(MachineBasicBlock& mbb, const TargetMachine& TM);
private:
friend class SchedGraphSet; // give access to ctor
-
-
-
+
inline void noteGraphNodeForInstr (const MachineInstr* minstr,
- SchedGraphNode* node)
- {
+ SchedGraphNode* node) {
assert((*this)[minstr] == NULL);
(*this)[minstr] = node;
}
//
// Graph builder
//
- void buildGraph (const TargetMachine& target);
+ void buildGraph(const TargetMachine& target);
- void buildNodesForBB (const TargetMachine& target,
- MachineBasicBlock &MBB,
- std::vector<SchedGraphNode*>& memNV,
- std::vector<SchedGraphNode*>& callNV,
- RegToRefVecMap& regToRefVecMap,
- ValueToDefVecMap& valueToDefVecMap);
+ 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*>& memNV,
- std::vector<SchedGraphNode*>& callNV,
- RegToRefVecMap& regToRefVecMap,
- ValueToDefVecMap& valueToDefVecMap);
-
+ void findDefUseInfoAtInstr(const TargetMachine& target, SchedGraphNode* node,
+ std::vector<SchedGraphNode*>& memNV,
+ std::vector<SchedGraphNode*>& callNV,
+ RegToRefVecMap& regToRefVecMap,
+ ValueToDefVecMap& valueToDefVecMap);
- void addEdgesForInstruction(const MachineInstr& minstr,
- const ValueToDefVecMap& valueToDefVecMap,
- const TargetMachine& target);
+ void addEdgesForInstruction(const MachineInstr& minstr,
+ const ValueToDefVecMap& valueToDefVecMap,
+ const TargetMachine& target);
- void addCDEdges (const TerminatorInst* term,
- const TargetMachine& target);
+ void addCDEdges(const TerminatorInst* term, const TargetMachine& target);
- void addMemEdges (const std::vector<SchedGraphNode*>& memNod,
- const TargetMachine& target);
+ 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 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);
+ void addMachineRegEdges(RegToRefVecMap& regToRefVecMap,
+ const TargetMachine& target);
- void addEdgesForValue (SchedGraphNode* refNode,
- const RefVec& defVec,
- const Value* defValue,
- bool refNodeIsDef,
- bool refNodeIsDefAndUse,
- const TargetMachine& target);
- void addDummyEdges();
+ void addEdgesForValue(SchedGraphNode* refNode, const RefVec& defVec,
+ const Value* defValue, bool refNodeIsDef,
+ bool refNodeIsDefAndUse,
+ const TargetMachine& target);
+
+ void addDummyEdges();
};
std::vector<SchedGraph*> Graphs;
// Graph builder
- void buildGraphsForMethod (const Function *F, const TargetMachine& target);
+ void buildGraphsForMethod(const Function *F, const TargetMachine& target);
inline void addGraph(SchedGraph* graph) {
assert(graph != NULL);
}
public:
- SchedGraphSet(const Function * function, const TargetMachine& target);
+ SchedGraphSet(const Function *function, const TargetMachine& target);
~SchedGraphSet();
//iterators
-//********************** Sched Graph Iterators *****************************/
-
-// Ok to make it a template because it shd get instantiated at most twice:
-// for <SchedGraphNode, SchedGraphNode::iterator> and
-// for <const SchedGraphNode, SchedGraphNode::const_iterator>.
-//
-template <class _NodeType, class _EdgeType, class _EdgeIter>
-class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
-protected:
- _EdgeIter oi;
-public:
- typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
-
- inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
-
- inline bool operator==(const _Self& x) const { return oi == x.oi; }
- inline bool operator!=(const _Self& x) const { return !operator==(x); }
-
- // operator*() differs for pred or succ iterator
- inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
- inline _NodeType* operator->() const { return operator*(); }
-
- inline _EdgeType* getEdge() const { return *(oi); }
-
- inline _Self &operator++() { ++oi; return *this; } // Preincrement
- inline _Self operator++(int) { // Postincrement
- _Self tmp(*this); ++*this; return tmp;
- }
-
- inline _Self &operator--() { --oi; return *this; } // Predecrement
- inline _Self operator--(int) { // Postdecrement
- _Self tmp = *this; --*this; return tmp;
- }
-};
-
-template <class _NodeType, class _EdgeType, class _EdgeIter>
-class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
-protected:
- _EdgeIter oi;
-public:
- typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
-
- inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
-
- 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 (_NodeType*)(*oi)->getSink(); }
- inline _NodeType* operator->() const { return operator*(); }
-
- inline _EdgeType* getEdge() const { return *(oi); }
-
- inline _Self &operator++() { ++oi; return *this; } // Preincrement
- inline _Self operator++(int) { // Postincrement
- _Self tmp(*this); ++*this; return tmp;
- }
-
- inline _Self &operator--() { --oi; return *this; } // Predecrement
- inline _Self operator--(int) { // Postdecrement
- _Self tmp = *this; --*this; return tmp;
- }
-};
//
// sg_pred_iterator
typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
sg_pred_const_iterator;
-inline sg_pred_iterator pred_begin( SchedGraphNode *N) {
+inline sg_pred_iterator pred_begin(SchedGraphNode *N) {
return sg_pred_iterator(N->beginInEdges());
}
-inline sg_pred_iterator pred_end( SchedGraphNode *N) {
+inline sg_pred_iterator pred_end(SchedGraphNode *N) {
return sg_pred_iterator(N->endInEdges());
}
inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
return sg_pred_const_iterator(N->beginInEdges());
}
-inline sg_pred_const_iterator pred_end( const SchedGraphNode *N) {
+inline sg_pred_const_iterator pred_end(const SchedGraphNode *N) {
return sg_pred_const_iterator(N->endInEdges());
}
typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
sg_succ_const_iterator;
-inline sg_succ_iterator succ_begin( SchedGraphNode *N) {
+inline sg_succ_iterator succ_begin(SchedGraphNode *N) {
return sg_succ_iterator(N->beginOutEdges());
}
-inline sg_succ_iterator succ_end( SchedGraphNode *N) {
+inline sg_succ_iterator succ_end(SchedGraphNode *N) {
return sg_succ_iterator(N->endOutEdges());
}
inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
return sg_succ_const_iterator(N->beginOutEdges());
}
-inline sg_succ_const_iterator succ_end( const SchedGraphNode *N) {
+inline sg_succ_const_iterator succ_end(const SchedGraphNode *N) {
return sg_succ_const_iterator(N->endOutEdges());
}
}
};
-
-std::ostream &operator<<(std::ostream& os, const SchedGraphEdge& edge);
-std::ostream &operator<<(std::ostream &os, const SchedGraphNode& node);
+} // End llvm namespace
#endif