include/llvm/Analysis/PathNumbering.h

   1 //===- PathNumbering.h ----------------------------------------*- C++ -*---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Ball-Larus path numbers uniquely identify paths through a directed acyclic
  11 // graph (DAG) [Ball96].  For a CFG backedges are removed and replaced by phony
  12 // edges to obtain a DAG, and thus the unique path numbers [Ball96].
  13 //
  14 // The purpose of this analysis is to enumerate the edges in a CFG in order
  15 // to obtain paths from path numbers in a convenient manner.  As described in
  16 // [Ball96] edges can be enumerated such that given a path number by following
  17 // the CFG and updating the path number, the path is obtained.
  18 //
  19 // [Ball96]
  20 //  T. Ball and J. R. Larus. "Efficient Path Profiling."
  21 //  International Symposium on Microarchitecture, pages 46-57, 1996.
  22 //  http://portal.acm.org/citation.cfm?id=243857
  23 //
  24 //===----------------------------------------------------------------------===//
  25
  26 #ifndef LLVM_PATH_NUMBERING_H
  27 #define LLVM_PATH_NUMBERING_H
  28
  29 #include "llvm/Analysis/ProfileInfoTypes.h"
  30 #include "llvm/BasicBlock.h"
  31 #include "llvm/Instructions.h"
  32 #include "llvm/Pass.h"
  33 #include "llvm/Support/CFG.h"
  34 #include <map>
  35 #include <stack>
  36 #include <vector>
  37
  38 namespace llvm {
  39 class BallLarusNode;
  40 class BallLarusEdge;
  41 class BallLarusDag;
  42
  43 // typedefs for storage/ interators of various DAG components
  44 typedef std::vector<BallLarusNode*> BLNodeVector;
  45 typedef std::vector<BallLarusNode*>::iterator BLNodeIterator;
  46 typedef std::vector<BallLarusEdge*> BLEdgeVector;
  47 typedef std::vector<BallLarusEdge*>::iterator BLEdgeIterator;
  48 typedef std::map<BasicBlock*, BallLarusNode*> BLBlockNodeMap;
  49 typedef std::stack<BallLarusNode*> BLNodeStack;
  50
  51 // Represents a basic block with information necessary for the BallLarus
  52 // algorithms.
  53 class BallLarusNode {
  54 public:
  55   enum NodeColor { WHITE, GRAY, BLACK };
  56
  57   // Constructor: Initializes a new Node for the given BasicBlock
  58   BallLarusNode(BasicBlock* BB) :
  59     _basicBlock(BB), _numberPaths(0), _color(WHITE) {
  60     static unsigned nextUID = 0;
  61     _uid = nextUID++;
  62   }
  63
  64   // Returns the basic block for the BallLarusNode
  65   BasicBlock* getBlock();
  66
  67   // Get/set the number of paths to the exit starting at the node.
  68   unsigned getNumberPaths();
  69   void setNumberPaths(unsigned numberPaths);
  70
  71   // Get/set the NodeColor used in graph algorithms.
  72   NodeColor getColor();
  73   void setColor(NodeColor color);
  74
  75   // Iterator information for predecessor edges. Includes phony and
  76   // backedges.
  77   BLEdgeIterator predBegin();
  78   BLEdgeIterator predEnd();
  79   unsigned getNumberPredEdges();
  80
  81   // Iterator information for successor edges. Includes phony and
  82   // backedges.
  83   BLEdgeIterator succBegin();
  84   BLEdgeIterator succEnd();
  85   unsigned getNumberSuccEdges();
  86
  87   // Add an edge to the predecessor list.
  88   void addPredEdge(BallLarusEdge* edge);
  89
  90   // Remove an edge from the predecessor list.
  91   void removePredEdge(BallLarusEdge* edge);
  92
  93   // Add an edge to the successor list.
  94   void addSuccEdge(BallLarusEdge* edge);
  95
  96   // Remove an edge from the successor list.
  97   void removeSuccEdge(BallLarusEdge* edge);
  98
  99   // Returns the name of the BasicBlock being represented.  If BasicBlock
 100   // is null then returns "<null>".  If BasicBlock has no name, then
 101   // "<unnamed>" is returned.  Intended for use with debug output.
 102   std::string getName();
 103
 104 private:
 105   // The corresponding underlying BB.
 106   BasicBlock* _basicBlock;
 107
 108   // Holds the predecessor edges of this node.
 109   BLEdgeVector _predEdges;
 110
 111   // Holds the successor edges of this node.
 112   BLEdgeVector _succEdges;
 113
 114   // The number of paths from the node to the exit.
 115   unsigned _numberPaths;
 116
 117   // 'Color' used by graph algorithms to mark the node.
 118   NodeColor _color;
 119
 120   // Unique ID to ensure naming difference with dotgraphs
 121   unsigned _uid;
 122
 123   // Removes an edge from an edgeVector.  Used by removePredEdge and
 124   // removeSuccEdge.
 125   void removeEdge(BLEdgeVector& v, BallLarusEdge* e);
 126 };
 127
 128 // Represents an edge in the Dag.  For an edge, v -> w, v is the source, and
 129 // w is the target.
 130 class BallLarusEdge {
 131 public:
 132   enum EdgeType { NORMAL, BACKEDGE, SPLITEDGE,
 133     BACKEDGE_PHONY, SPLITEDGE_PHONY, CALLEDGE_PHONY };
 134
 135   // Constructor: Initializes an BallLarusEdge with a source and target.
 136   BallLarusEdge(BallLarusNode* source, BallLarusNode* target,
 137                                 unsigned duplicateNumber)
 138     : _source(source), _target(target), _weight(0), _edgeType(NORMAL),
 139       _realEdge(NULL), _duplicateNumber(duplicateNumber) {}
 140
 141   // Returns the source/ target node of this edge.
 142   BallLarusNode* getSource() const;
 143   BallLarusNode* getTarget() const;
 144
 145   // Sets the type of the edge.
 146   EdgeType getType() const;
 147
 148   // Gets the type of the edge.
 149   void setType(EdgeType type);
 150
 151   // Returns the weight of this edge.  Used to decode path numbers to
 152   // sequences of basic blocks.
 153   unsigned getWeight();
 154
 155   // Sets the weight of the edge.  Used during path numbering.
 156   void setWeight(unsigned weight);
 157
 158   // Gets/sets the phony edge originating at the root.
 159   BallLarusEdge* getPhonyRoot();
 160   void setPhonyRoot(BallLarusEdge* phonyRoot);
 161
 162   // Gets/sets the phony edge terminating at the exit.
 163   BallLarusEdge* getPhonyExit();
 164   void setPhonyExit(BallLarusEdge* phonyExit);
 165
 166   // Gets/sets the associated real edge if this is a phony edge.
 167   BallLarusEdge* getRealEdge();
 168   void setRealEdge(BallLarusEdge* realEdge);
 169
 170   // Returns the duplicate number of the edge.
 171   unsigned getDuplicateNumber();
 172
 173 protected:
 174   // Source node for this edge.
 175   BallLarusNode* _source;
 176
 177   // Target node for this edge.
 178   BallLarusNode* _target;
 179
 180 private:
 181   // Edge weight cooresponding to path number increments before removing
 182   // increments along a spanning tree. The sum over the edge weights gives
 183   // the path number.
 184   unsigned _weight;
 185
 186   // Type to represent for what this edge is intended
 187   EdgeType _edgeType;
 188
 189   // For backedges and split-edges, the phony edge which is linked to the
 190   // root node of the DAG. This contains a path number initialization.
 191   BallLarusEdge* _phonyRoot;
 192
 193   // For backedges and split-edges, the phony edge which is linked to the
 194   // exit node of the DAG. This contains a path counter increment, and
 195   // potentially a path number increment.
 196   BallLarusEdge* _phonyExit;
 197
 198   // If this is a phony edge, _realEdge is a link to the back or split
 199   // edge. Otherwise, this is null.
 200   BallLarusEdge* _realEdge;
 201
 202   // An ID to differentiate between those edges which have the same source
 203   // and destination blocks.
 204   unsigned _duplicateNumber;
 205 };
 206
 207 // Represents the Ball Larus DAG for a given Function.  Can calculate
 208 // various properties required for instrumentation or analysis.  E.g. the
 209 // edge weights that determine the path number.
 210 class BallLarusDag {
 211 public:
 212   // Initializes a BallLarusDag from the CFG of a given function.  Must
 213   // call init() after creation, since some initialization requires
 214   // virtual functions.
 215   BallLarusDag(Function &F)
 216     : _root(NULL), _exit(NULL), _function(F) {}
 217
 218   // Initialization that requires virtual functions which are not fully
 219   // functional in the constructor.
 220   void init();
 221
 222   // Frees all memory associated with the DAG.
 223   virtual ~BallLarusDag();
 224
 225   // Calculate the path numbers by assigning edge increments as prescribed
 226   // in Ball-Larus path profiling.
 227   void calculatePathNumbers();
 228
 229   // Returns the number of paths for the DAG.
 230   unsigned getNumberOfPaths();
 231
 232   // Returns the root (i.e. entry) node for the DAG.
 233   BallLarusNode* getRoot();
 234
 235   // Returns the exit node for the DAG.
 236   BallLarusNode* getExit();
 237
 238   // Returns the function for the DAG.
 239   Function& getFunction();
 240
 241   // Clears the node colors.
 242   void clearColors(BallLarusNode::NodeColor color);
 243
 244 protected:
 245   // All nodes in the DAG.
 246   BLNodeVector _nodes;
 247
 248   // All edges in the DAG.
 249   BLEdgeVector _edges;
 250
 251   // All backedges in the DAG.
 252   BLEdgeVector _backEdges;
 253
 254   // Allows subclasses to determine which type of Node is created.
 255   // Override this method to produce subclasses of BallLarusNode if
 256   // necessary. The destructor of BallLarusDag will call free on each pointer
 257   // created.
 258   virtual BallLarusNode* createNode(BasicBlock* BB);
 259
 260   // Allows subclasses to determine which type of Edge is created.
 261   // Override this method to produce subclasses of BallLarusEdge if
 262   // necessary.  Parameters source and target will have been created by
 263   // createNode and can be cast to the subclass of BallLarusNode*
 264   // returned by createNode. The destructor of BallLarusDag will call free
 265   // on each pointer created.
 266   virtual BallLarusEdge* createEdge(BallLarusNode* source, BallLarusNode*
 267                                     target, unsigned duplicateNumber);
 268
 269   // Proxy to node's constructor.  Updates the DAG state.
 270   BallLarusNode* addNode(BasicBlock* BB);
 271
 272   // Proxy to edge's constructor.  Updates the DAG state.
 273   BallLarusEdge* addEdge(BallLarusNode* source, BallLarusNode* target,
 274                          unsigned duplicateNumber);
 275
 276 private:
 277   // The root (i.e. entry) node for this DAG.
 278   BallLarusNode* _root;
 279
 280   // The exit node for this DAG.
 281   BallLarusNode* _exit;
 282
 283   // The function represented by this DAG.
 284   Function& _function;
 285
 286   // Processes one node and its imediate edges for building the DAG.
 287   void buildNode(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& dfsStack);
 288
 289   // Process an edge in the CFG for DAG building.
 290   void buildEdge(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& dfsStack,
 291                  BallLarusNode* currentNode, BasicBlock* succBB,
 292                  unsigned duplicateNumber);
 293
 294   // The weight on each edge is the increment required along any path that
 295   // contains that edge.
 296   void calculatePathNumbersFrom(BallLarusNode* node);
 297
 298   // Adds a backedge with its phony edges.  Updates the DAG state.
 299   void addBackedge(BallLarusNode* source, BallLarusNode* target,
 300                    unsigned duplicateCount);
 301 };
 302 } // end namespace llvm
 303
 304 #endif