-//===-- SchedGraphCommon.h - Scheduling Base Graph ---------------*- C++ -*---=//
+//===-- SchedGraphCommon.h - Scheduling Base Graph --------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
//
// A common graph class that is based on the SSA graph. It includes
// extra dependencies that are caused by machine resources.
//
-//===-------------------------------------------------------------------------=//
+//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_SCHEDGRAPHCOMMON_H
#define LLVM_CODEGEN_SCHEDGRAPHCOMMON_H
#include "llvm/Value.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/Support/Streams.h"
+#include <vector>
+
+namespace llvm {
class SchedGraphEdge;
class SchedGraphNode;
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;
-
+
// Accessor methods
unsigned getNodeId() const { return ID; }
int getLatency() const { return latency; }
// Iterators
iterator beginInEdges() { return inEdges.begin(); }
- iterator endInEdges() { return inEdges.end(); }
+ 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(); }
// Debugging support
virtual void print(std::ostream &os) const = 0;
-
+ void print(std::ostream *os) const { if (os) print(*os); }
+
protected:
- friend class SchedGraph;
friend class SchedGraphCommon;
- friend class SchedGraphEdge; // give access for adding edges
-
-
+ friend class SchedGraphEdge; // give access for adding edges
+
+
// disable default constructor and provide a ctor for single-block graphs
- SchedGraphNodeCommon(); // DO NOT IMPLEMENT
-
- inline SchedGraphNodeCommon(unsigned Id, int index) : ID(Id), latency(0),
- origIndexInBB(index) {}
+ SchedGraphNodeCommon(); // DO NOT IMPLEMENT
+
+ inline SchedGraphNodeCommon(unsigned Id, int index, int late=0) : ID(Id), latency(late), origIndexInBB(index) {}
+
virtual ~SchedGraphNodeCommon();
-
+
//Functions to add and remove edges
inline void addInEdge(SchedGraphEdge* edge) { inEdges.push_back(edge); }
inline void addOutEdge(SchedGraphEdge* edge) { outEdges.push_back(edge); }
void removeInEdge(const SchedGraphEdge* edge);
void removeOutEdge(const SchedGraphEdge* edge);
+
};
// ostream << operator for SchedGraphNode class
-inline std::ostream &operator<<(std::ostream &os,
- const SchedGraphNodeCommon &node) {
+inline std::ostream &operator<<(std::ostream &os,
+ const SchedGraphNodeCommon &node) {
node.print(os);
return os;
}
-
-
-
//
// SchedGraphEdge - Edge class to represent dependencies
//
enum DataDepOrderType {
TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
};
-
+
protected:
- SchedGraphNodeCommon* src;
- SchedGraphNodeCommon* sink;
+ SchedGraphNodeCommon* src;
+ SchedGraphNodeCommon* sink;
SchedGraphEdgeDepType depType;
unsigned int depOrderType;
int minDelay; // cached latency (assumes fixed target arch)
int iteDiff;
-
+
union {
const Value* val;
int machineRegNum;
ResourceId resourceId;
};
-public:
+public:
// For all constructors, if minDelay is unspecified, minDelay is
// set to _src->getLatency().
-
+
// constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
- SchedGraphEdgeDepType _depType, unsigned int _depOrderType,
- int _minDelay = -1);
-
+ SchedGraphEdgeDepType _depType, unsigned int _depOrderType,
+ int _minDelay = -1);
+
// constructor for explicit value dependence (may be true/anti/output)
SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
- const Value* _val, unsigned int _depOrderType,
- int _minDelay = -1);
-
+ const Value* _val, unsigned int _depOrderType,
+ int _minDelay = -1);
+
// constructor for machine register dependence
SchedGraphEdge(SchedGraphNodeCommon* _src,SchedGraphNodeCommon* _sink,
- unsigned int _regNum, unsigned int _depOrderType,
- int _minDelay = -1);
-
+ 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.
SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
- ResourceId _resourceId, int _minDelay = -1);
-
+ ResourceId _resourceId, int _minDelay = -1);
+
~SchedGraphEdge() {}
-
- SchedGraphNodeCommon* getSrc() const { return src; }
- SchedGraphNodeCommon* getSink() const { return sink; }
+
+ SchedGraphNodeCommon* getSrc() const { return src; }
+ SchedGraphNodeCommon* getSink() const { return sink; }
int getMinDelay() const { return minDelay; }
SchedGraphEdgeDepType getDepType() const { return depType; }
-
+ unsigned int getDepOrderType() const { return depOrderType; }
+
const Value* getValue() const {
assert(depType == ValueDep); return val;
}
int getIteDiff() {
return iteDiff;
}
-
+
public:
// Debugging support
void print(std::ostream &os) const;
+ void print(std::ostream *os) const { if (os) print(*os); }
void dump(int indent=0) const;
-
+
private:
// disable default ctor
- SchedGraphEdge(); // DO NOT IMPLEMENT
+ SchedGraphEdge(); // DO NOT IMPLEMENT
};
// ostream << operator for SchedGraphNode class
}
class SchedGraphCommon {
-
+
protected:
SchedGraphNodeCommon* graphRoot; // the root and leaf are not inserted
SchedGraphNodeCommon* graphLeaf; // in the hash_map (see getNumNodes())
// Accessor methods
//
SchedGraphNodeCommon* getRoot() const { return graphRoot; }
- SchedGraphNodeCommon* getLeaf() const { return graphLeaf; }
-
+ SchedGraphNodeCommon* getLeaf() const { return graphLeaf; }
+
//
// Delete nodes or edges from the graph.
- //
+ //
void eraseNode(SchedGraphNodeCommon* node);
void eraseIncomingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
void eraseOutgoingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
void eraseIncidentEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
-
+
SchedGraphCommon() {}
~SchedGraphCommon();
};
+
+//********************** 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;
+ }
+};
+} // End llvm namespace
+
#endif
projects / oota-llvm.git / blobdiff