LLVM API Documentation

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

DependenceGraph.h

Go to the documentation of this file.
00001 //===- DependenceGraph.h - Dependence graph for a function ------*- 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 // This file provides an explicit representation for the dependence graph
00011 // of a function, with one node per instruction and one edge per dependence.
00012 // Dependences include both data and control dependences.
00013 // 
00014 // Each dep. graph node (class DepGraphNode) keeps lists of incoming and
00015 // outgoing dependence edges.
00016 // 
00017 // Each dep. graph edge (class Dependence) keeps a pointer to one end-point
00018 // of the dependence.  This saves space and is important because dep. graphs
00019 // can grow quickly.  It works just fine because the standard idiom is to
00020 // start with a known node and enumerate the dependences to or from that node.
00021 //
00022 //===----------------------------------------------------------------------===//
00023 
00024 #ifndef LLVM_ANALYSIS_DEPENDENCEGRAPH_H
00025 #define LLVM_ANALYSIS_DEPENDENCEGRAPH_H
00026 
00027 #include "llvm/ADT/hash_map"
00028 #include <cassert>
00029 #include <iosfwd>
00030 #include <utility>
00031 #include <vector>
00032 
00033 namespace llvm {
00034 
00035 class Instruction;
00036 class Function;
00037 class Dependence;
00038 class DepGraphNode;
00039 class DependenceGraph;
00040 
00041 //----------------------------------------------------------------------------
00042 /// enum DependenceType - The standard data dependence types
00043 ///
00044 enum DependenceType {
00045   NoDependence       = 0x0,
00046   TrueDependence     = 0x1,
00047   AntiDependence     = 0x2,
00048   OutputDependence   = 0x4,
00049   ControlDependence  = 0x8,         // from a terminator to some other instr.
00050   IncomingFlag       = 0x10         // is this an incoming or outgoing dep?
00051 };
00052 
00053 //----------------------------------------------------------------------------
00054 /// Dependence Class - A representation of a simple (non-loop-related)
00055 /// dependence.
00056 ///
00057 class Dependence {
00058   DepGraphNode*   toOrFromNode;
00059   unsigned char  depType;
00060 
00061 public:
00062   Dependence(DepGraphNode* toOrFromN, DependenceType type, bool isIncoming)
00063     : toOrFromNode(toOrFromN),
00064       depType(type | (isIncoming? IncomingFlag : 0x0)) { }
00065 
00066   Dependence(const Dependence& D) : toOrFromNode(D.toOrFromNode),
00067       depType(D.depType) { }
00068 
00069   bool operator==(const Dependence& D) const {
00070     return toOrFromNode == D.toOrFromNode && depType == D.depType;
00071   }
00072 
00073   /// Get information about the type of dependence.
00074   /// 
00075   unsigned getDepType() const {
00076     return depType;
00077   }
00078 
00079   /// Get source or sink depending on what type of node this is!
00080   /// 
00081   DepGraphNode* getSrc() {
00082     assert(depType & IncomingFlag); return toOrFromNode;
00083   }
00084   const DepGraphNode* getSrc() const {
00085     assert(depType & IncomingFlag); return toOrFromNode;
00086   }
00087 
00088   DepGraphNode* getSink() {
00089     assert(! (depType & IncomingFlag)); return toOrFromNode;
00090   }
00091   const DepGraphNode* getSink() const {
00092     assert(! (depType & IncomingFlag)); return toOrFromNode;
00093   }
00094 
00095   /// Debugging support methods
00096   /// 
00097   void print(std::ostream &O) const;
00098 
00099   // Default constructor: Do not use directly except for graph builder code
00100   // 
00101   Dependence() : toOrFromNode(NULL), depType(NoDependence) { }
00102 };
00103 
00104 #ifdef SUPPORTING_LOOP_DEPENDENCES
00105 struct LoopDependence: public Dependence {
00106   DependenceDirection dir;
00107   int                 distance;
00108   short               level;
00109   LoopInfo*           enclosingLoop;
00110 };
00111 #endif
00112 
00113 
00114 //----------------------------------------------------------------------------
00115 /// DepGraphNode Class - A representation of a single node in a dependence
00116 /// graph, corresponding to a single instruction.
00117 ///
00118 class DepGraphNode {
00119   Instruction*  instr;
00120   std::vector<Dependence>  inDeps;
00121   std::vector<Dependence>  outDeps;
00122   friend class DependenceGraph;
00123   
00124   typedef std::vector<Dependence>::      iterator       iterator;
00125   typedef std::vector<Dependence>::const_iterator const_iterator;
00126 
00127         iterator inDepBegin()        { return inDeps.begin(); }
00128   const_iterator inDepBegin()  const { return inDeps.begin(); }
00129         iterator inDepEnd()          { return inDeps.end();   }
00130   const_iterator inDepEnd()    const { return inDeps.end();   }
00131   
00132         iterator outDepBegin()       { return outDeps.begin(); }
00133   const_iterator outDepBegin() const { return outDeps.begin(); }
00134         iterator outDepEnd()         { return outDeps.end();   }
00135   const_iterator outDepEnd()   const { return outDeps.end();   }
00136 
00137 public:
00138   DepGraphNode(Instruction& I) : instr(&I) { }
00139 
00140         Instruction& getInstr()       { return *instr; }
00141   const Instruction& getInstr() const { return *instr; }
00142 
00143   /// Debugging support methods
00144   /// 
00145   void print(std::ostream &O) const;
00146 };
00147 
00148 
00149 //----------------------------------------------------------------------------
00150 /// DependenceGraph Class - A representation of a dependence graph for a
00151 /// procedure. The primary query operation here is to look up a DepGraphNode for
00152 /// a particular instruction, and then use the in/out dependence iterators
00153 /// for the node.
00154 ///
00155 class DependenceGraph {
00156   DependenceGraph(const DependenceGraph&); // DO NOT IMPLEMENT
00157   void operator=(const DependenceGraph&);  // DO NOT IMPLEMENT
00158 
00159   typedef hash_map<Instruction*, DepGraphNode*> DepNodeMapType;
00160   typedef DepNodeMapType::      iterator       map_iterator;
00161   typedef DepNodeMapType::const_iterator const_map_iterator;
00162 
00163   DepNodeMapType depNodeMap;
00164 
00165   inline DepGraphNode* getNodeInternal(Instruction& inst,
00166                                        bool createIfMissing = false) {
00167     map_iterator I = depNodeMap.find(&inst);
00168     if (I == depNodeMap.end())
00169       return (!createIfMissing)? NULL :
00170         depNodeMap.insert(
00171             std::make_pair(&inst, new DepGraphNode(inst))).first->second;
00172     else
00173       return I->second;
00174   }
00175 
00176 public:
00177   typedef std::vector<Dependence>::      iterator       iterator;
00178   typedef std::vector<Dependence>::const_iterator const_iterator;
00179 
00180 public:
00181   DependenceGraph() { }
00182   ~DependenceGraph();
00183 
00184   /// Get the graph node for an instruction.  There will be one if and
00185   /// only if there are any dependences incident on this instruction.
00186   /// If there is none, these methods will return NULL.
00187   /// 
00188   DepGraphNode* getNode(Instruction& inst, bool createIfMissing = false) {
00189     return getNodeInternal(inst, createIfMissing);
00190   }
00191   const DepGraphNode* getNode(const Instruction& inst) const {
00192     return const_cast<DependenceGraph*>(this)
00193       ->getNodeInternal(const_cast<Instruction&>(inst));
00194   }
00195 
00196   iterator inDepBegin(DepGraphNode& T) {
00197     return T.inDeps.begin();
00198   }
00199   const_iterator inDepBegin (const DepGraphNode& T) const {
00200     return T.inDeps.begin();
00201   }
00202 
00203   iterator inDepEnd(DepGraphNode& T) {
00204     return T.inDeps.end();
00205   }
00206   const_iterator inDepEnd(const DepGraphNode& T) const {
00207     return T.inDeps.end();
00208   }
00209 
00210   iterator outDepBegin(DepGraphNode& F) {
00211     return F.outDeps.begin();
00212   }
00213   const_iterator outDepBegin(const DepGraphNode& F) const {
00214     return F.outDeps.begin();
00215   }
00216 
00217   iterator outDepEnd(DepGraphNode& F) {
00218     return F.outDeps.end();
00219   }
00220   const_iterator outDepEnd(const DepGraphNode& F) const {
00221     return F.outDeps.end();
00222   }
00223 
00224   /// Debugging support methods
00225   /// 
00226   void print(const Function& func, std::ostream &O) const;
00227 
00228 public:
00229   /// AddSimpleDependence - adding and modifying the dependence graph.
00230   /// These should to be used only by dependence analysis implementations.
00231   ///
00232   void AddSimpleDependence(Instruction& fromI, Instruction& toI,
00233                            DependenceType depType) {
00234     DepGraphNode* fromNode = getNodeInternal(fromI, /*create*/ true);
00235     DepGraphNode* toNode   = getNodeInternal(toI,   /*create*/ true);
00236     fromNode->outDeps.push_back(Dependence(toNode, depType, false));
00237     toNode->  inDeps. push_back(Dependence(fromNode, depType, true));
00238   }
00239 
00240 #ifdef SUPPORTING_LOOP_DEPENDENCES
00241   // This interface is a placeholder to show what information is needed.
00242   // It will probably change when it starts being used.
00243   void AddLoopDependence(Instruction&  fromI,
00244                          Instruction&  toI,
00245                          DependenceType      depType,
00246                          DependenceDirection dir,
00247                          int                 distance,
00248                          short               level,
00249                          LoopInfo*           enclosingLoop);
00250 #endif // SUPPORTING_LOOP_DEPENDENCES
00251 };
00252 
00253 } // End llvm namespace
00254 
00255 #endif