• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- PathNumbering.cpp --------------------------------------*- 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 #define DEBUG_TYPE "ball-larus-numbering"
26 
27 #include "llvm/Analysis/PathNumbering.h"
28 #include "llvm/Constants.h"
29 #include "llvm/DerivedTypes.h"
30 #include "llvm/InstrTypes.h"
31 #include "llvm/Instructions.h"
32 #include "llvm/Module.h"
33 #include "llvm/Pass.h"
34 #include "llvm/Support/CFG.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Compiler.h"
37 #include "llvm/Support/Debug.h"
38 #include "llvm/Support/TypeBuilder.h"
39 #include "llvm/Support/raw_ostream.h"
40 
41 #include <queue>
42 #include <stack>
43 #include <string>
44 #include <utility>
45 #include <sstream>
46 
47 using namespace llvm;
48 
49 // Are we enabling early termination
50 static cl::opt<bool> ProcessEarlyTermination(
51   "path-profile-early-termination", cl::Hidden,
52   cl::desc("In path profiling, insert extra instrumentation to account for "
53            "unexpected function termination."));
54 
55 // Returns the basic block for the BallLarusNode
getBlock()56 BasicBlock* BallLarusNode::getBlock() {
57   return(_basicBlock);
58 }
59 
60 // Returns the number of paths to the exit starting at the node.
getNumberPaths()61 unsigned BallLarusNode::getNumberPaths() {
62   return(_numberPaths);
63 }
64 
65 // Sets the number of paths to the exit starting at the node.
setNumberPaths(unsigned numberPaths)66 void BallLarusNode::setNumberPaths(unsigned numberPaths) {
67   _numberPaths = numberPaths;
68 }
69 
70 // Gets the NodeColor used in graph algorithms.
getColor()71 BallLarusNode::NodeColor BallLarusNode::getColor() {
72   return(_color);
73 }
74 
75 // Sets the NodeColor used in graph algorithms.
setColor(BallLarusNode::NodeColor color)76 void BallLarusNode::setColor(BallLarusNode::NodeColor color) {
77   _color = color;
78 }
79 
80 // Returns an iterator over predecessor edges. Includes phony and
81 // backedges.
predBegin()82 BLEdgeIterator BallLarusNode::predBegin() {
83   return(_predEdges.begin());
84 }
85 
86 // Returns the end sentinel for the predecessor iterator.
predEnd()87 BLEdgeIterator BallLarusNode::predEnd() {
88   return(_predEdges.end());
89 }
90 
91 // Returns the number of predecessor edges.  Includes phony and
92 // backedges.
getNumberPredEdges()93 unsigned BallLarusNode::getNumberPredEdges() {
94   return(_predEdges.size());
95 }
96 
97 // Returns an iterator over successor edges. Includes phony and
98 // backedges.
succBegin()99 BLEdgeIterator BallLarusNode::succBegin() {
100   return(_succEdges.begin());
101 }
102 
103 // Returns the end sentinel for the successor iterator.
succEnd()104 BLEdgeIterator BallLarusNode::succEnd() {
105   return(_succEdges.end());
106 }
107 
108 // Returns the number of successor edges.  Includes phony and
109 // backedges.
getNumberSuccEdges()110 unsigned BallLarusNode::getNumberSuccEdges() {
111   return(_succEdges.size());
112 }
113 
114 // Add an edge to the predecessor list.
addPredEdge(BallLarusEdge * edge)115 void BallLarusNode::addPredEdge(BallLarusEdge* edge) {
116   _predEdges.push_back(edge);
117 }
118 
119 // Remove an edge from the predecessor list.
removePredEdge(BallLarusEdge * edge)120 void BallLarusNode::removePredEdge(BallLarusEdge* edge) {
121   removeEdge(_predEdges, edge);
122 }
123 
124 // Add an edge to the successor list.
addSuccEdge(BallLarusEdge * edge)125 void BallLarusNode::addSuccEdge(BallLarusEdge* edge) {
126   _succEdges.push_back(edge);
127 }
128 
129 // Remove an edge from the successor list.
removeSuccEdge(BallLarusEdge * edge)130 void BallLarusNode::removeSuccEdge(BallLarusEdge* edge) {
131   removeEdge(_succEdges, edge);
132 }
133 
134 // Returns the name of the BasicBlock being represented.  If BasicBlock
135 // is null then returns "<null>".  If BasicBlock has no name, then
136 // "<unnamed>" is returned.  Intended for use with debug output.
getName()137 std::string BallLarusNode::getName() {
138   std::stringstream name;
139 
140   if(getBlock() != NULL) {
141     if(getBlock()->hasName()) {
142       std::string tempName(getBlock()->getName());
143       name << tempName.c_str() << " (" << _uid << ")";
144     } else
145       name << "<unnamed> (" << _uid << ")";
146   } else
147     name << "<null> (" << _uid << ")";
148 
149   return name.str();
150 }
151 
152 // Removes an edge from an edgeVector.  Used by removePredEdge and
153 // removeSuccEdge.
removeEdge(BLEdgeVector & v,BallLarusEdge * e)154 void BallLarusNode::removeEdge(BLEdgeVector& v, BallLarusEdge* e) {
155   // TODO: Avoid linear scan by using a set instead
156   for(BLEdgeIterator i = v.begin(),
157         end = v.end();
158       i != end;
159       ++i) {
160     if((*i) == e) {
161       v.erase(i);
162       break;
163     }
164   }
165 }
166 
167 // Returns the source node of this edge.
getSource() const168 BallLarusNode* BallLarusEdge::getSource() const {
169   return(_source);
170 }
171 
172 // Returns the target node of this edge.
getTarget() const173 BallLarusNode* BallLarusEdge::getTarget() const {
174   return(_target);
175 }
176 
177 // Sets the type of the edge.
getType() const178 BallLarusEdge::EdgeType BallLarusEdge::getType() const {
179   return _edgeType;
180 }
181 
182 // Gets the type of the edge.
setType(EdgeType type)183 void BallLarusEdge::setType(EdgeType type) {
184   _edgeType = type;
185 }
186 
187 // Returns the weight of this edge.  Used to decode path numbers to sequences
188 // of basic blocks.
getWeight()189 unsigned BallLarusEdge::getWeight() {
190   return(_weight);
191 }
192 
193 // Sets the weight of the edge.  Used during path numbering.
setWeight(unsigned weight)194 void BallLarusEdge::setWeight(unsigned weight) {
195   _weight = weight;
196 }
197 
198 // Gets the phony edge originating at the root.
getPhonyRoot()199 BallLarusEdge* BallLarusEdge::getPhonyRoot() {
200   return _phonyRoot;
201 }
202 
203 // Sets the phony edge originating at the root.
setPhonyRoot(BallLarusEdge * phonyRoot)204 void BallLarusEdge::setPhonyRoot(BallLarusEdge* phonyRoot) {
205   _phonyRoot = phonyRoot;
206 }
207 
208 // Gets the phony edge terminating at the exit.
getPhonyExit()209 BallLarusEdge* BallLarusEdge::getPhonyExit() {
210   return _phonyExit;
211 }
212 
213 // Sets the phony edge terminating at the exit.
setPhonyExit(BallLarusEdge * phonyExit)214 void BallLarusEdge::setPhonyExit(BallLarusEdge* phonyExit) {
215   _phonyExit = phonyExit;
216 }
217 
218 // Gets the associated real edge if this is a phony edge.
getRealEdge()219 BallLarusEdge* BallLarusEdge::getRealEdge() {
220   return _realEdge;
221 }
222 
223 // Sets the associated real edge if this is a phony edge.
setRealEdge(BallLarusEdge * realEdge)224 void BallLarusEdge::setRealEdge(BallLarusEdge* realEdge) {
225   _realEdge = realEdge;
226 }
227 
228 // Returns the duplicate number of the edge.
getDuplicateNumber()229 unsigned BallLarusEdge::getDuplicateNumber() {
230   return(_duplicateNumber);
231 }
232 
233 // Initialization that requires virtual functions which are not fully
234 // functional in the constructor.
init()235 void BallLarusDag::init() {
236   BLBlockNodeMap inDag;
237   std::stack<BallLarusNode*> dfsStack;
238 
239   _root = addNode(&(_function.getEntryBlock()));
240   _exit = addNode(NULL);
241 
242   // start search from root
243   dfsStack.push(getRoot());
244 
245   // dfs to add each bb into the dag
246   while(dfsStack.size())
247     buildNode(inDag, dfsStack);
248 
249   // put in the final edge
250   addEdge(getExit(),getRoot(),0);
251 }
252 
253 // Frees all memory associated with the DAG.
~BallLarusDag()254 BallLarusDag::~BallLarusDag() {
255   for(BLEdgeIterator edge = _edges.begin(), end = _edges.end(); edge != end;
256       ++edge)
257     delete (*edge);
258 
259   for(BLNodeIterator node = _nodes.begin(), end = _nodes.end(); node != end;
260       ++node)
261     delete (*node);
262 }
263 
264 // Calculate the path numbers by assigning edge increments as prescribed
265 // in Ball-Larus path profiling.
calculatePathNumbers()266 void BallLarusDag::calculatePathNumbers() {
267   BallLarusNode* node;
268   std::queue<BallLarusNode*> bfsQueue;
269   bfsQueue.push(getExit());
270 
271   while(bfsQueue.size() > 0) {
272     node = bfsQueue.front();
273 
274     DEBUG(dbgs() << "calculatePathNumbers on " << node->getName() << "\n");
275 
276     bfsQueue.pop();
277     unsigned prevPathNumber = node->getNumberPaths();
278     calculatePathNumbersFrom(node);
279 
280     // Check for DAG splitting
281     if( node->getNumberPaths() > 100000000 && node != getRoot() ) {
282       // Add new phony edge from the split-node to the DAG's exit
283       BallLarusEdge* exitEdge = addEdge(node, getExit(), 0);
284       exitEdge->setType(BallLarusEdge::SPLITEDGE_PHONY);
285 
286       // Counters to handle the possibility of a multi-graph
287       BasicBlock* oldTarget = 0;
288       unsigned duplicateNumber = 0;
289 
290       // Iterate through each successor edge, adding phony edges
291       for( BLEdgeIterator succ = node->succBegin(), end = node->succEnd();
292            succ != end; oldTarget = (*succ)->getTarget()->getBlock(), succ++ ) {
293 
294         if( (*succ)->getType() == BallLarusEdge::NORMAL ) {
295           // is this edge a duplicate?
296           if( oldTarget != (*succ)->getTarget()->getBlock() )
297             duplicateNumber = 0;
298 
299           // create the new phony edge: root -> succ
300           BallLarusEdge* rootEdge =
301             addEdge(getRoot(), (*succ)->getTarget(), duplicateNumber++);
302           rootEdge->setType(BallLarusEdge::SPLITEDGE_PHONY);
303           rootEdge->setRealEdge(*succ);
304 
305           // split on this edge and reference it's exit/root phony edges
306           (*succ)->setType(BallLarusEdge::SPLITEDGE);
307           (*succ)->setPhonyRoot(rootEdge);
308           (*succ)->setPhonyExit(exitEdge);
309           (*succ)->setWeight(0);
310         }
311       }
312 
313       calculatePathNumbersFrom(node);
314     }
315 
316     DEBUG(dbgs() << "prev, new number paths " << prevPathNumber << ", "
317           << node->getNumberPaths() << ".\n");
318 
319     if(prevPathNumber == 0 && node->getNumberPaths() != 0) {
320       DEBUG(dbgs() << "node ready : " << node->getName() << "\n");
321       for(BLEdgeIterator pred = node->predBegin(), end = node->predEnd();
322           pred != end; pred++) {
323         if( (*pred)->getType() == BallLarusEdge::BACKEDGE ||
324             (*pred)->getType() == BallLarusEdge::SPLITEDGE )
325           continue;
326 
327         BallLarusNode* nextNode = (*pred)->getSource();
328         // not yet visited?
329         if(nextNode->getNumberPaths() == 0)
330           bfsQueue.push(nextNode);
331       }
332     }
333   }
334 
335   DEBUG(dbgs() << "\tNumber of paths: " << getRoot()->getNumberPaths() << "\n");
336 }
337 
338 // Returns the number of paths for the Dag.
getNumberOfPaths()339 unsigned BallLarusDag::getNumberOfPaths() {
340   return(getRoot()->getNumberPaths());
341 }
342 
343 // Returns the root (i.e. entry) node for the DAG.
getRoot()344 BallLarusNode* BallLarusDag::getRoot() {
345   return _root;
346 }
347 
348 // Returns the exit node for the DAG.
getExit()349 BallLarusNode* BallLarusDag::getExit() {
350   return _exit;
351 }
352 
353 // Returns the function for the DAG.
getFunction()354 Function& BallLarusDag::getFunction() {
355   return(_function);
356 }
357 
358 // Clears the node colors.
clearColors(BallLarusNode::NodeColor color)359 void BallLarusDag::clearColors(BallLarusNode::NodeColor color) {
360   for (BLNodeIterator nodeIt = _nodes.begin(); nodeIt != _nodes.end(); nodeIt++)
361     (*nodeIt)->setColor(color);
362 }
363 
364 // Processes one node and its imediate edges for building the DAG.
buildNode(BLBlockNodeMap & inDag,BLNodeStack & dfsStack)365 void BallLarusDag::buildNode(BLBlockNodeMap& inDag, BLNodeStack& dfsStack) {
366   BallLarusNode* currentNode = dfsStack.top();
367   BasicBlock* currentBlock = currentNode->getBlock();
368 
369   if(currentNode->getColor() != BallLarusNode::WHITE) {
370     // we have already visited this node
371     dfsStack.pop();
372     currentNode->setColor(BallLarusNode::BLACK);
373   } else {
374     // are there any external procedure calls?
375     if( ProcessEarlyTermination ) {
376       for( BasicBlock::iterator bbCurrent = currentNode->getBlock()->begin(),
377              bbEnd = currentNode->getBlock()->end(); bbCurrent != bbEnd;
378            bbCurrent++ ) {
379         Instruction& instr = *bbCurrent;
380         if( instr.getOpcode() == Instruction::Call ) {
381           BallLarusEdge* callEdge = addEdge(currentNode, getExit(), 0);
382           callEdge->setType(BallLarusEdge::CALLEDGE_PHONY);
383           break;
384         }
385       }
386     }
387 
388     TerminatorInst* terminator = currentNode->getBlock()->getTerminator();
389     if(isa<ReturnInst>(terminator) || isa<UnreachableInst>(terminator)
390        || isa<ResumeInst>(terminator) || isa<UnwindInst>(terminator))
391       addEdge(currentNode, getExit(),0);
392 
393     currentNode->setColor(BallLarusNode::GRAY);
394     inDag[currentBlock] = currentNode;
395 
396     BasicBlock* oldSuccessor = 0;
397     unsigned duplicateNumber = 0;
398 
399     // iterate through this node's successors
400     for(succ_iterator successor = succ_begin(currentBlock),
401           succEnd = succ_end(currentBlock); successor != succEnd;
402         oldSuccessor = *successor, ++successor ) {
403       BasicBlock* succBB = *successor;
404 
405       // is this edge a duplicate?
406       if (oldSuccessor == succBB)
407         duplicateNumber++;
408       else
409         duplicateNumber = 0;
410 
411       buildEdge(inDag, dfsStack, currentNode, succBB, duplicateNumber);
412     }
413   }
414 }
415 
416 // Process an edge in the CFG for DAG building.
buildEdge(BLBlockNodeMap & inDag,std::stack<BallLarusNode * > & dfsStack,BallLarusNode * currentNode,BasicBlock * succBB,unsigned duplicateCount)417 void BallLarusDag::buildEdge(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>&
418                              dfsStack, BallLarusNode* currentNode,
419                              BasicBlock* succBB, unsigned duplicateCount) {
420   BallLarusNode* succNode = inDag[succBB];
421 
422   if(succNode && succNode->getColor() == BallLarusNode::BLACK) {
423     // visited node and forward edge
424     addEdge(currentNode, succNode, duplicateCount);
425   } else if(succNode && succNode->getColor() == BallLarusNode::GRAY) {
426     // visited node and back edge
427     DEBUG(dbgs() << "Backedge detected.\n");
428     addBackedge(currentNode, succNode, duplicateCount);
429   } else {
430     BallLarusNode* childNode;
431     // not visited node and forward edge
432     if(succNode) // an unvisited node that is child of a gray node
433       childNode = succNode;
434     else { // an unvisited node that is a child of a an unvisted node
435       childNode = addNode(succBB);
436       inDag[succBB] = childNode;
437     }
438     addEdge(currentNode, childNode, duplicateCount);
439     dfsStack.push(childNode);
440   }
441 }
442 
443 // The weight on each edge is the increment required along any path that
444 // contains that edge.
calculatePathNumbersFrom(BallLarusNode * node)445 void BallLarusDag::calculatePathNumbersFrom(BallLarusNode* node) {
446   if(node == getExit())
447     // The Exit node must be base case
448     node->setNumberPaths(1);
449   else {
450     unsigned sumPaths = 0;
451     BallLarusNode* succNode;
452 
453     for(BLEdgeIterator succ = node->succBegin(), end = node->succEnd();
454         succ != end; succ++) {
455       if( (*succ)->getType() == BallLarusEdge::BACKEDGE ||
456           (*succ)->getType() == BallLarusEdge::SPLITEDGE )
457         continue;
458 
459       (*succ)->setWeight(sumPaths);
460       succNode = (*succ)->getTarget();
461 
462       if( !succNode->getNumberPaths() )
463         return;
464       sumPaths += succNode->getNumberPaths();
465     }
466 
467     node->setNumberPaths(sumPaths);
468   }
469 }
470 
471 // Allows subclasses to determine which type of Node is created.
472 // Override this method to produce subclasses of BallLarusNode if
473 // necessary. The destructor of BallLarusDag will call free on each
474 // pointer created.
createNode(BasicBlock * BB)475 BallLarusNode* BallLarusDag::createNode(BasicBlock* BB) {
476   return( new BallLarusNode(BB) );
477 }
478 
479 // Allows subclasses to determine which type of Edge is created.
480 // Override this method to produce subclasses of BallLarusEdge if
481 // necessary. The destructor of BallLarusDag will call free on each
482 // pointer created.
createEdge(BallLarusNode * source,BallLarusNode * target,unsigned duplicateCount)483 BallLarusEdge* BallLarusDag::createEdge(BallLarusNode* source,
484                                         BallLarusNode* target,
485                                         unsigned duplicateCount) {
486   return( new BallLarusEdge(source, target, duplicateCount) );
487 }
488 
489 // Proxy to node's constructor.  Updates the DAG state.
addNode(BasicBlock * BB)490 BallLarusNode* BallLarusDag::addNode(BasicBlock* BB) {
491   BallLarusNode* newNode = createNode(BB);
492   _nodes.push_back(newNode);
493   return( newNode );
494 }
495 
496 // Proxy to edge's constructor. Updates the DAG state.
addEdge(BallLarusNode * source,BallLarusNode * target,unsigned duplicateCount)497 BallLarusEdge* BallLarusDag::addEdge(BallLarusNode* source,
498                                      BallLarusNode* target,
499                                      unsigned duplicateCount) {
500   BallLarusEdge* newEdge = createEdge(source, target, duplicateCount);
501   _edges.push_back(newEdge);
502   source->addSuccEdge(newEdge);
503   target->addPredEdge(newEdge);
504   return(newEdge);
505 }
506 
507 // Adds a backedge with its phony edges. Updates the DAG state.
addBackedge(BallLarusNode * source,BallLarusNode * target,unsigned duplicateCount)508 void BallLarusDag::addBackedge(BallLarusNode* source, BallLarusNode* target,
509                                unsigned duplicateCount) {
510   BallLarusEdge* childEdge = addEdge(source, target, duplicateCount);
511   childEdge->setType(BallLarusEdge::BACKEDGE);
512 
513   childEdge->setPhonyRoot(addEdge(getRoot(), target,0));
514   childEdge->setPhonyExit(addEdge(source, getExit(),0));
515 
516   childEdge->getPhonyRoot()->setRealEdge(childEdge);
517   childEdge->getPhonyRoot()->setType(BallLarusEdge::BACKEDGE_PHONY);
518 
519   childEdge->getPhonyExit()->setRealEdge(childEdge);
520   childEdge->getPhonyExit()->setType(BallLarusEdge::BACKEDGE_PHONY);
521   _backEdges.push_back(childEdge);
522 }
523