LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

SchedGraphCommon.h

Go to the documentation of this file.
00001 //===-- SchedGraphCommon.h - Scheduling Base Graph --------------*- C++ -*-===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // A common graph class that is based on the SSA graph. It includes
00011 // extra dependencies that are caused by machine resources.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #ifndef LLVM_CODEGEN_SCHEDGRAPHCOMMON_H
00016 #define LLVM_CODEGEN_SCHEDGRAPHCOMMON_H
00017 
00018 #include "llvm/Value.h"
00019 #include "llvm/ADT/iterator"
00020 #include <vector>
00021 
00022 namespace llvm {
00023 
00024 class SchedGraphEdge;
00025 class SchedGraphNode;
00026 
00027 /******************** Exported Data Types and Constants ********************/
00028 
00029 typedef int ResourceId;
00030 const ResourceId InvalidRID        = -1;
00031 const ResourceId MachineCCRegsRID  = -2; // use +ve numbers for actual regs
00032 const ResourceId MachineIntRegsRID = -3; // use +ve numbers for actual regs
00033 const ResourceId MachineFPRegsRID  = -4; // use +ve numbers for actual regs
00034 
00035 
00036 //*********************** Public Class Declarations ************************/
00037 class SchedGraphNodeCommon {
00038 protected:
00039   unsigned ID;
00040   std::vector<SchedGraphEdge*> inEdges;
00041   std::vector<SchedGraphEdge*> outEdges;
00042   int latency;
00043   int origIndexInBB;            // original position of instr in BB
00044 
00045 public:
00046   typedef std::vector<SchedGraphEdge*>::iterator iterator;
00047   typedef std::vector<SchedGraphEdge*>::const_iterator const_iterator;
00048   typedef std::vector<SchedGraphEdge*>::reverse_iterator reverse_iterator;
00049   typedef std::vector<SchedGraphEdge*>::const_reverse_iterator const_reverse_iterator;
00050   
00051   // Accessor methods
00052   unsigned getNodeId() const { return ID; }
00053   int getLatency() const { return latency; }
00054   unsigned getNumInEdges() const { return inEdges.size(); }
00055   unsigned getNumOutEdges() const { return outEdges.size(); }
00056   int getOrigIndexInBB() const { return origIndexInBB; }
00057 
00058   // Iterators
00059   iterator beginInEdges() { return inEdges.begin(); }
00060   iterator endInEdges()  { return inEdges.end(); }
00061   iterator beginOutEdges() { return outEdges.begin(); }
00062   iterator endOutEdges() { return outEdges.end(); }
00063   
00064   const_iterator beginInEdges() const { return inEdges.begin(); }
00065   const_iterator endInEdges() const { return inEdges.end(); }
00066   const_iterator beginOutEdges() const { return outEdges.begin(); }
00067   const_iterator endOutEdges() const { return outEdges.end(); }
00068 
00069   void dump(int indent=0) const;
00070 
00071   // Debugging support
00072   virtual void print(std::ostream &os) const = 0;
00073   
00074 protected:
00075   friend class SchedGraphCommon;
00076   friend class SchedGraphEdge;    // give access for adding edges
00077   
00078   
00079   // disable default constructor and provide a ctor for single-block graphs
00080   SchedGraphNodeCommon(); // DO NOT IMPLEMENT
00081   
00082   inline SchedGraphNodeCommon(unsigned Id, int index, int late=0) : ID(Id), latency(late), origIndexInBB(index) {}
00083   
00084   virtual ~SchedGraphNodeCommon();
00085   
00086   //Functions to add and remove edges
00087   inline void addInEdge(SchedGraphEdge* edge) { inEdges.push_back(edge); }
00088   inline void addOutEdge(SchedGraphEdge* edge) { outEdges.push_back(edge); }
00089   void removeInEdge(const SchedGraphEdge* edge);
00090   void removeOutEdge(const SchedGraphEdge* edge);
00091   
00092 };
00093 
00094 // ostream << operator for SchedGraphNode class
00095 inline std::ostream &operator<<(std::ostream &os, 
00096         const SchedGraphNodeCommon &node) {
00097   node.print(os);
00098   return os;
00099 }
00100 
00101 
00102 
00103 
00104 //
00105 // SchedGraphEdge - Edge class to represent dependencies
00106 //
00107 class SchedGraphEdge {
00108 public:
00109   enum SchedGraphEdgeDepType {
00110     CtrlDep, MemoryDep, ValueDep, MachineRegister, MachineResource
00111   };
00112   enum DataDepOrderType {
00113     TrueDep = 0x1, AntiDep=0x2, OutputDep=0x4, NonDataDep=0x8
00114   };
00115   
00116 protected:
00117   SchedGraphNodeCommon* src;
00118   SchedGraphNodeCommon* sink;
00119   SchedGraphEdgeDepType depType;
00120   unsigned int depOrderType;
00121   int minDelay; // cached latency (assumes fixed target arch)
00122   int iteDiff;
00123   
00124   union {
00125     const Value* val;
00126     int          machineRegNum;
00127     ResourceId   resourceId;
00128   };
00129 
00130 public: 
00131   // For all constructors, if minDelay is unspecified, minDelay is
00132   // set to _src->getLatency().
00133   
00134   // constructor for CtrlDep or MemoryDep edges, selected by 3rd argument
00135   SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
00136      SchedGraphEdgeDepType _depType, unsigned int _depOrderType,
00137      int _minDelay = -1);
00138   
00139   // constructor for explicit value dependence (may be true/anti/output)
00140   SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
00141      const Value* _val, unsigned int _depOrderType,
00142      int _minDelay = -1);
00143   
00144   // constructor for machine register dependence
00145   SchedGraphEdge(SchedGraphNodeCommon* _src,SchedGraphNodeCommon* _sink,
00146      unsigned int _regNum, unsigned int _depOrderType,
00147      int _minDelay = -1);
00148   
00149   // constructor for any other machine resource dependences.
00150   // DataDepOrderType is always NonDataDep.  It it not an argument to
00151   // avoid overloading ambiguity with previous constructor.
00152   SchedGraphEdge(SchedGraphNodeCommon* _src, SchedGraphNodeCommon* _sink,
00153      ResourceId _resourceId, int _minDelay = -1);
00154   
00155   ~SchedGraphEdge() {}
00156   
00157   SchedGraphNodeCommon* getSrc() const { return src; }
00158   SchedGraphNodeCommon* getSink() const { return sink; }
00159   int getMinDelay() const { return minDelay; }
00160   SchedGraphEdgeDepType getDepType() const { return depType; }
00161   unsigned int getDepOrderType() const { return depOrderType; }
00162 
00163   const Value* getValue() const {
00164     assert(depType == ValueDep); return val;
00165   }
00166 
00167   int getMachineReg() const {
00168     assert(depType == MachineRegister); return machineRegNum;
00169   }
00170 
00171   int getResourceId() const {
00172     assert(depType == MachineResource); return resourceId;
00173   }
00174 
00175   void setIteDiff(int _iteDiff) {
00176     iteDiff = _iteDiff;
00177   }
00178 
00179   int getIteDiff() {
00180     return iteDiff;
00181   }
00182   
00183 public:
00184   // Debugging support
00185   void print(std::ostream &os) const;
00186   void dump(int indent=0) const;
00187     
00188 private:
00189   // disable default ctor
00190   SchedGraphEdge(); // DO NOT IMPLEMENT
00191 };
00192 
00193 // ostream << operator for SchedGraphNode class
00194 inline std::ostream &operator<<(std::ostream &os, const SchedGraphEdge &edge) {
00195   edge.print(os);
00196   return os;
00197 }
00198 
00199 class SchedGraphCommon {
00200   
00201 protected:
00202   SchedGraphNodeCommon* graphRoot;     // the root and leaf are not inserted
00203   SchedGraphNodeCommon* graphLeaf;     //  in the hash_map (see getNumNodes())
00204 
00205 public:
00206   //
00207   // Accessor methods
00208   //
00209   SchedGraphNodeCommon* getRoot() const { return graphRoot; }
00210   SchedGraphNodeCommon* getLeaf() const { return graphLeaf; } 
00211  
00212   //
00213   // Delete nodes or edges from the graph.
00214   // 
00215   void eraseNode(SchedGraphNodeCommon* node);
00216   void eraseIncomingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
00217   void eraseOutgoingEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
00218   void eraseIncidentEdges(SchedGraphNodeCommon* node, bool addDummyEdges = true);
00219   
00220   SchedGraphCommon() {}
00221   ~SchedGraphCommon();
00222 };
00223 
00224 
00225 //********************** Sched Graph Iterators *****************************/
00226 
00227 // Ok to make it a template because it shd get instantiated at most twice:
00228 // for <SchedGraphNode, SchedGraphNode::iterator> and
00229 // for <const SchedGraphNode, SchedGraphNode::const_iterator>.
00230 // 
00231 template <class _NodeType, class _EdgeType, class _EdgeIter>
00232 class SGPredIterator: public bidirectional_iterator<_NodeType, ptrdiff_t> {
00233 protected:
00234   _EdgeIter oi;
00235 public:
00236   typedef SGPredIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
00237   
00238   inline SGPredIterator(_EdgeIter startEdge) : oi(startEdge) {}
00239   
00240   inline bool operator==(const _Self& x) const { return oi == x.oi; }
00241   inline bool operator!=(const _Self& x) const { return !operator==(x); }
00242   
00243   // operator*() differs for pred or succ iterator
00244   inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSrc(); }
00245   inline _NodeType* operator->() const { return operator*(); }
00246   
00247   inline _EdgeType* getEdge() const { return *(oi); }
00248   
00249   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
00250   inline _Self operator++(int) {                        // Postincrement
00251     _Self tmp(*this); ++*this; return tmp; 
00252   }
00253   
00254   inline _Self &operator--() { --oi; return *this; }    // Predecrement
00255   inline _Self operator--(int) {                        // Postdecrement
00256     _Self tmp = *this; --*this; return tmp;
00257   }
00258 };
00259 
00260 template <class _NodeType, class _EdgeType, class _EdgeIter>
00261 class SGSuccIterator : public bidirectional_iterator<_NodeType, ptrdiff_t> {
00262 protected:
00263   _EdgeIter oi;
00264 public:
00265   typedef SGSuccIterator<_NodeType, _EdgeType, _EdgeIter> _Self;
00266   
00267   inline SGSuccIterator(_EdgeIter startEdge) : oi(startEdge) {}
00268   
00269   inline bool operator==(const _Self& x) const { return oi == x.oi; }
00270   inline bool operator!=(const _Self& x) const { return !operator==(x); }
00271   
00272   inline _NodeType* operator*() const { return (_NodeType*)(*oi)->getSink(); }
00273   inline _NodeType* operator->() const { return operator*(); }
00274   
00275   inline _EdgeType* getEdge() const { return *(oi); }
00276   
00277   inline _Self &operator++() { ++oi; return *this; }    // Preincrement
00278   inline _Self operator++(int) {                        // Postincrement
00279     _Self tmp(*this); ++*this; return tmp; 
00280   }
00281   
00282   inline _Self &operator--() { --oi; return *this; }    // Predecrement
00283   inline _Self operator--(int) {                        // Postdecrement
00284     _Self tmp = *this; --*this; return tmp;
00285   }
00286 };
00287 } // End llvm namespace
00288 
00289 #endif