• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/BasicBlock.h"
30 #include "llvm/Instructions.h"
31 #include "llvm/Pass.h"
32 #include "llvm/Support/CFG.h"
33 #include "llvm/Analysis/ProfileInfoTypes.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
BallLarusNode(BasicBlock * BB)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.
BallLarusEdge(BallLarusNode * source,BallLarusNode * target,unsigned duplicateNumber)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.
BallLarusDag(Function & F)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
305