1 //===- PathNumbering.h ----------------------------------------*- C++ -*---===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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].
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.
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
24 //===----------------------------------------------------------------------===//
26 #ifndef LLVM_PATH_NUMBERING_H
27 #define LLVM_PATH_NUMBERING_H
29 #include "llvm/BasicBlock.h"
30 #include "llvm/Instructions.h"
31 #include "llvm/Pass.h"
32 #include "llvm/Support/CFG.h"
33 #include "llvm/Analysis/ProfileInfoTypes.h"
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;
51 // Represents a basic block with information necessary for the BallLarus
55 enum NodeColor { WHITE, GRAY, BLACK };
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;
64 // Returns the basic block for the BallLarusNode
65 BasicBlock* getBlock();
67 // Get/set the number of paths to the exit starting at the node.
68 unsigned getNumberPaths();
69 void setNumberPaths(unsigned numberPaths);
71 // Get/set the NodeColor used in graph algorithms.
73 void setColor(NodeColor color);
75 // Iterator information for predecessor edges. Includes phony and
77 BLEdgeIterator predBegin();
78 BLEdgeIterator predEnd();
79 unsigned getNumberPredEdges();
81 // Iterator information for successor edges. Includes phony and
83 BLEdgeIterator succBegin();
84 BLEdgeIterator succEnd();
85 unsigned getNumberSuccEdges();
87 // Add an edge to the predecessor list.
88 void addPredEdge(BallLarusEdge* edge);
90 // Remove an edge from the predecessor list.
91 void removePredEdge(BallLarusEdge* edge);
93 // Add an edge to the successor list.
94 void addSuccEdge(BallLarusEdge* edge);
96 // Remove an edge from the successor list.
97 void removeSuccEdge(BallLarusEdge* edge);
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();
105 // The corresponding underlying BB.
106 BasicBlock* _basicBlock;
108 // Holds the predecessor edges of this node.
109 BLEdgeVector _predEdges;
111 // Holds the successor edges of this node.
112 BLEdgeVector _succEdges;
114 // The number of paths from the node to the exit.
115 unsigned _numberPaths;
117 // 'Color' used by graph algorithms to mark the node.
120 // Unique ID to ensure naming difference with dotgraphs
123 // Removes an edge from an edgeVector. Used by removePredEdge and
125 void removeEdge(BLEdgeVector& v, BallLarusEdge* e);
128 // Represents an edge in the Dag. For an edge, v -> w, v is the source, and
130 class BallLarusEdge {
132 enum EdgeType { NORMAL, BACKEDGE, SPLITEDGE,
133 BACKEDGE_PHONY, SPLITEDGE_PHONY, CALLEDGE_PHONY };
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) {}
141 // Returns the source/ target node of this edge.
142 BallLarusNode* getSource() const;
143 BallLarusNode* getTarget() const;
145 // Sets the type of the edge.
146 EdgeType getType() const;
148 // Gets the type of the edge.
149 void setType(EdgeType type);
151 // Returns the weight of this edge. Used to decode path numbers to
152 // sequences of basic blocks.
153 unsigned getWeight();
155 // Sets the weight of the edge. Used during path numbering.
156 void setWeight(unsigned weight);
158 // Gets/sets the phony edge originating at the root.
159 BallLarusEdge* getPhonyRoot();
160 void setPhonyRoot(BallLarusEdge* phonyRoot);
162 // Gets/sets the phony edge terminating at the exit.
163 BallLarusEdge* getPhonyExit();
164 void setPhonyExit(BallLarusEdge* phonyExit);
166 // Gets/sets the associated real edge if this is a phony edge.
167 BallLarusEdge* getRealEdge();
168 void setRealEdge(BallLarusEdge* realEdge);
170 // Returns the duplicate number of the edge.
171 unsigned getDuplicateNumber();
174 // Source node for this edge.
175 BallLarusNode* _source;
177 // Target node for this edge.
178 BallLarusNode* _target;
181 // Edge weight cooresponding to path number increments before removing
182 // increments along a spanning tree. The sum over the edge weights gives
186 // Type to represent for what this edge is intended
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;
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;
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;
202 // An ID to differentiate between those edges which have the same source
203 // and destination blocks.
204 unsigned _duplicateNumber;
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.
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) {}
218 // Initialization that requires virtual functions which are not fully
219 // functional in the constructor.
222 // Frees all memory associated with the DAG.
223 virtual ~BallLarusDag();
225 // Calculate the path numbers by assigning edge increments as prescribed
226 // in Ball-Larus path profiling.
227 void calculatePathNumbers();
229 // Returns the number of paths for the DAG.
230 unsigned getNumberOfPaths();
232 // Returns the root (i.e. entry) node for the DAG.
233 BallLarusNode* getRoot();
235 // Returns the exit node for the DAG.
236 BallLarusNode* getExit();
238 // Returns the function for the DAG.
239 Function& getFunction();
241 // Clears the node colors.
242 void clearColors(BallLarusNode::NodeColor color);
245 // All nodes in the DAG.
248 // All edges in the DAG.
251 // All backedges in the DAG.
252 BLEdgeVector _backEdges;
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
258 virtual BallLarusNode* createNode(BasicBlock* BB);
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);
269 // Proxy to node's constructor. Updates the DAG state.
270 BallLarusNode* addNode(BasicBlock* BB);
272 // Proxy to edge's constructor. Updates the DAG state.
273 BallLarusEdge* addEdge(BallLarusNode* source, BallLarusNode* target,
274 unsigned duplicateNumber);
277 // The root (i.e. entry) node for this DAG.
278 BallLarusNode* _root;
280 // The exit node for this DAG.
281 BallLarusNode* _exit;
283 // The function represented by this DAG.
286 // Processes one node and its imediate edges for building the DAG.
287 void buildNode(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& dfsStack);
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);
294 // The weight on each edge is the increment required along any path that
295 // contains that edge.
296 void calculatePathNumbersFrom(BallLarusNode* node);
298 // Adds a backedge with its phony edges. Updates the DAG state.
299 void addBackedge(BallLarusNode* source, BallLarusNode* target,
300 unsigned duplicateCount);
302 } // end namespace llvm