1 //===- PathNumbering.cpp --------------------------------------*- 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 //===----------------------------------------------------------------------===//
25 #define DEBUG_TYPE "ball-larus-numbering"
27 #include "llvm/Analysis/PathNumbering.h"
28 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/DerivedTypes.h"
30 #include "llvm/IR/InstrTypes.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/Module.h"
33 #include "llvm/IR/TypeBuilder.h"
34 #include "llvm/Pass.h"
35 #include "llvm/Support/CFG.h"
36 #include "llvm/Support/CommandLine.h"
37 #include "llvm/Support/Compiler.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/raw_ostream.h"
48 // Are we enabling early termination
49 static cl::opt<bool> ProcessEarlyTermination(
50 "path-profile-early-termination", cl::Hidden,
51 cl::desc("In path profiling, insert extra instrumentation to account for "
52 "unexpected function termination."));
54 // Returns the basic block for the BallLarusNode
55 BasicBlock* BallLarusNode::getBlock() {
59 // Returns the number of paths to the exit starting at the node.
60 unsigned BallLarusNode::getNumberPaths() {
64 // Sets the number of paths to the exit starting at the node.
65 void BallLarusNode::setNumberPaths(unsigned numberPaths) {
66 _numberPaths = numberPaths;
69 // Gets the NodeColor used in graph algorithms.
70 BallLarusNode::NodeColor BallLarusNode::getColor() {
74 // Sets the NodeColor used in graph algorithms.
75 void BallLarusNode::setColor(BallLarusNode::NodeColor color) {
79 // Returns an iterator over predecessor edges. Includes phony and
81 BLEdgeIterator BallLarusNode::predBegin() {
82 return(_predEdges.begin());
85 // Returns the end sentinel for the predecessor iterator.
86 BLEdgeIterator BallLarusNode::predEnd() {
87 return(_predEdges.end());
90 // Returns the number of predecessor edges. Includes phony and
92 unsigned BallLarusNode::getNumberPredEdges() {
93 return(_predEdges.size());
96 // Returns an iterator over successor edges. Includes phony and
98 BLEdgeIterator BallLarusNode::succBegin() {
99 return(_succEdges.begin());
102 // Returns the end sentinel for the successor iterator.
103 BLEdgeIterator BallLarusNode::succEnd() {
104 return(_succEdges.end());
107 // Returns the number of successor edges. Includes phony and
109 unsigned BallLarusNode::getNumberSuccEdges() {
110 return(_succEdges.size());
113 // Add an edge to the predecessor list.
114 void BallLarusNode::addPredEdge(BallLarusEdge* edge) {
115 _predEdges.push_back(edge);
118 // Remove an edge from the predecessor list.
119 void BallLarusNode::removePredEdge(BallLarusEdge* edge) {
120 removeEdge(_predEdges, edge);
123 // Add an edge to the successor list.
124 void BallLarusNode::addSuccEdge(BallLarusEdge* edge) {
125 _succEdges.push_back(edge);
128 // Remove an edge from the successor list.
129 void BallLarusNode::removeSuccEdge(BallLarusEdge* edge) {
130 removeEdge(_succEdges, edge);
133 // Returns the name of the BasicBlock being represented. If BasicBlock
134 // is null then returns "<null>". If BasicBlock has no name, then
135 // "<unnamed>" is returned. Intended for use with debug output.
136 std::string BallLarusNode::getName() {
137 std::stringstream name;
139 if(getBlock() != NULL) {
140 if(getBlock()->hasName()) {
141 std::string tempName(getBlock()->getName());
142 name << tempName.c_str() << " (" << _uid << ")";
144 name << "<unnamed> (" << _uid << ")";
146 name << "<null> (" << _uid << ")";
151 // Removes an edge from an edgeVector. Used by removePredEdge and
153 void BallLarusNode::removeEdge(BLEdgeVector& v, BallLarusEdge* e) {
154 // TODO: Avoid linear scan by using a set instead
155 for(BLEdgeIterator i = v.begin(),
166 // Returns the source node of this edge.
167 BallLarusNode* BallLarusEdge::getSource() const {
171 // Returns the target node of this edge.
172 BallLarusNode* BallLarusEdge::getTarget() const {
176 // Sets the type of the edge.
177 BallLarusEdge::EdgeType BallLarusEdge::getType() const {
181 // Gets the type of the edge.
182 void BallLarusEdge::setType(EdgeType type) {
186 // Returns the weight of this edge. Used to decode path numbers to sequences
188 unsigned BallLarusEdge::getWeight() {
192 // Sets the weight of the edge. Used during path numbering.
193 void BallLarusEdge::setWeight(unsigned weight) {
197 // Gets the phony edge originating at the root.
198 BallLarusEdge* BallLarusEdge::getPhonyRoot() {
202 // Sets the phony edge originating at the root.
203 void BallLarusEdge::setPhonyRoot(BallLarusEdge* phonyRoot) {
204 _phonyRoot = phonyRoot;
207 // Gets the phony edge terminating at the exit.
208 BallLarusEdge* BallLarusEdge::getPhonyExit() {
212 // Sets the phony edge terminating at the exit.
213 void BallLarusEdge::setPhonyExit(BallLarusEdge* phonyExit) {
214 _phonyExit = phonyExit;
217 // Gets the associated real edge if this is a phony edge.
218 BallLarusEdge* BallLarusEdge::getRealEdge() {
222 // Sets the associated real edge if this is a phony edge.
223 void BallLarusEdge::setRealEdge(BallLarusEdge* realEdge) {
224 _realEdge = realEdge;
227 // Returns the duplicate number of the edge.
228 unsigned BallLarusEdge::getDuplicateNumber() {
229 return(_duplicateNumber);
232 // Initialization that requires virtual functions which are not fully
233 // functional in the constructor.
234 void BallLarusDag::init() {
235 BLBlockNodeMap inDag;
236 std::stack<BallLarusNode*> dfsStack;
238 _root = addNode(&(_function.getEntryBlock()));
239 _exit = addNode(NULL);
241 // start search from root
242 dfsStack.push(getRoot());
244 // dfs to add each bb into the dag
245 while(dfsStack.size())
246 buildNode(inDag, dfsStack);
248 // put in the final edge
249 addEdge(getExit(),getRoot(),0);
252 // Frees all memory associated with the DAG.
253 BallLarusDag::~BallLarusDag() {
254 for(BLEdgeIterator edge = _edges.begin(), end = _edges.end(); edge != end;
258 for(BLNodeIterator node = _nodes.begin(), end = _nodes.end(); node != end;
263 // Calculate the path numbers by assigning edge increments as prescribed
264 // in Ball-Larus path profiling.
265 void BallLarusDag::calculatePathNumbers() {
267 std::queue<BallLarusNode*> bfsQueue;
268 bfsQueue.push(getExit());
270 while(bfsQueue.size() > 0) {
271 node = bfsQueue.front();
273 DEBUG(dbgs() << "calculatePathNumbers on " << node->getName() << "\n");
276 unsigned prevPathNumber = node->getNumberPaths();
277 calculatePathNumbersFrom(node);
279 // Check for DAG splitting
280 if( node->getNumberPaths() > 100000000 && node != getRoot() ) {
281 // Add new phony edge from the split-node to the DAG's exit
282 BallLarusEdge* exitEdge = addEdge(node, getExit(), 0);
283 exitEdge->setType(BallLarusEdge::SPLITEDGE_PHONY);
285 // Counters to handle the possibility of a multi-graph
286 BasicBlock* oldTarget = 0;
287 unsigned duplicateNumber = 0;
289 // Iterate through each successor edge, adding phony edges
290 for( BLEdgeIterator succ = node->succBegin(), end = node->succEnd();
291 succ != end; oldTarget = (*succ)->getTarget()->getBlock(), succ++ ) {
293 if( (*succ)->getType() == BallLarusEdge::NORMAL ) {
294 // is this edge a duplicate?
295 if( oldTarget != (*succ)->getTarget()->getBlock() )
298 // create the new phony edge: root -> succ
299 BallLarusEdge* rootEdge =
300 addEdge(getRoot(), (*succ)->getTarget(), duplicateNumber++);
301 rootEdge->setType(BallLarusEdge::SPLITEDGE_PHONY);
302 rootEdge->setRealEdge(*succ);
304 // split on this edge and reference it's exit/root phony edges
305 (*succ)->setType(BallLarusEdge::SPLITEDGE);
306 (*succ)->setPhonyRoot(rootEdge);
307 (*succ)->setPhonyExit(exitEdge);
308 (*succ)->setWeight(0);
312 calculatePathNumbersFrom(node);
315 DEBUG(dbgs() << "prev, new number paths " << prevPathNumber << ", "
316 << node->getNumberPaths() << ".\n");
318 if(prevPathNumber == 0 && node->getNumberPaths() != 0) {
319 DEBUG(dbgs() << "node ready : " << node->getName() << "\n");
320 for(BLEdgeIterator pred = node->predBegin(), end = node->predEnd();
321 pred != end; pred++) {
322 if( (*pred)->getType() == BallLarusEdge::BACKEDGE ||
323 (*pred)->getType() == BallLarusEdge::SPLITEDGE )
326 BallLarusNode* nextNode = (*pred)->getSource();
328 if(nextNode->getNumberPaths() == 0)
329 bfsQueue.push(nextNode);
334 DEBUG(dbgs() << "\tNumber of paths: " << getRoot()->getNumberPaths() << "\n");
337 // Returns the number of paths for the Dag.
338 unsigned BallLarusDag::getNumberOfPaths() {
339 return(getRoot()->getNumberPaths());
342 // Returns the root (i.e. entry) node for the DAG.
343 BallLarusNode* BallLarusDag::getRoot() {
347 // Returns the exit node for the DAG.
348 BallLarusNode* BallLarusDag::getExit() {
352 // Returns the function for the DAG.
353 Function& BallLarusDag::getFunction() {
357 // Clears the node colors.
358 void BallLarusDag::clearColors(BallLarusNode::NodeColor color) {
359 for (BLNodeIterator nodeIt = _nodes.begin(); nodeIt != _nodes.end(); nodeIt++)
360 (*nodeIt)->setColor(color);
363 // Processes one node and its imediate edges for building the DAG.
364 void BallLarusDag::buildNode(BLBlockNodeMap& inDag, BLNodeStack& dfsStack) {
365 BallLarusNode* currentNode = dfsStack.top();
366 BasicBlock* currentBlock = currentNode->getBlock();
368 if(currentNode->getColor() != BallLarusNode::WHITE) {
369 // we have already visited this node
371 currentNode->setColor(BallLarusNode::BLACK);
373 // are there any external procedure calls?
374 if( ProcessEarlyTermination ) {
375 for( BasicBlock::iterator bbCurrent = currentNode->getBlock()->begin(),
376 bbEnd = currentNode->getBlock()->end(); bbCurrent != bbEnd;
378 Instruction& instr = *bbCurrent;
379 if( instr.getOpcode() == Instruction::Call ) {
380 BallLarusEdge* callEdge = addEdge(currentNode, getExit(), 0);
381 callEdge->setType(BallLarusEdge::CALLEDGE_PHONY);
387 TerminatorInst* terminator = currentNode->getBlock()->getTerminator();
388 if(isa<ReturnInst>(terminator) || isa<UnreachableInst>(terminator) ||
389 isa<ResumeInst>(terminator))
390 addEdge(currentNode, getExit(),0);
392 currentNode->setColor(BallLarusNode::GRAY);
393 inDag[currentBlock] = currentNode;
395 BasicBlock* oldSuccessor = 0;
396 unsigned duplicateNumber = 0;
398 // iterate through this node's successors
399 for(succ_iterator successor = succ_begin(currentBlock),
400 succEnd = succ_end(currentBlock); successor != succEnd;
401 oldSuccessor = *successor, ++successor ) {
402 BasicBlock* succBB = *successor;
404 // is this edge a duplicate?
405 if (oldSuccessor == succBB)
410 buildEdge(inDag, dfsStack, currentNode, succBB, duplicateNumber);
415 // Process an edge in the CFG for DAG building.
416 void BallLarusDag::buildEdge(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>&
417 dfsStack, BallLarusNode* currentNode,
418 BasicBlock* succBB, unsigned duplicateCount) {
419 BallLarusNode* succNode = inDag[succBB];
421 if(succNode && succNode->getColor() == BallLarusNode::BLACK) {
422 // visited node and forward edge
423 addEdge(currentNode, succNode, duplicateCount);
424 } else if(succNode && succNode->getColor() == BallLarusNode::GRAY) {
425 // visited node and back edge
426 DEBUG(dbgs() << "Backedge detected.\n");
427 addBackedge(currentNode, succNode, duplicateCount);
429 BallLarusNode* childNode;
430 // not visited node and forward edge
431 if(succNode) // an unvisited node that is child of a gray node
432 childNode = succNode;
433 else { // an unvisited node that is a child of a an unvisted node
434 childNode = addNode(succBB);
435 inDag[succBB] = childNode;
437 addEdge(currentNode, childNode, duplicateCount);
438 dfsStack.push(childNode);
442 // The weight on each edge is the increment required along any path that
443 // contains that edge.
444 void BallLarusDag::calculatePathNumbersFrom(BallLarusNode* node) {
445 if(node == getExit())
446 // The Exit node must be base case
447 node->setNumberPaths(1);
449 unsigned sumPaths = 0;
450 BallLarusNode* succNode;
452 for(BLEdgeIterator succ = node->succBegin(), end = node->succEnd();
453 succ != end; succ++) {
454 if( (*succ)->getType() == BallLarusEdge::BACKEDGE ||
455 (*succ)->getType() == BallLarusEdge::SPLITEDGE )
458 (*succ)->setWeight(sumPaths);
459 succNode = (*succ)->getTarget();
461 if( !succNode->getNumberPaths() )
463 sumPaths += succNode->getNumberPaths();
466 node->setNumberPaths(sumPaths);
470 // Allows subclasses to determine which type of Node is created.
471 // Override this method to produce subclasses of BallLarusNode if
472 // necessary. The destructor of BallLarusDag will call free on each
474 BallLarusNode* BallLarusDag::createNode(BasicBlock* BB) {
475 return( new BallLarusNode(BB) );
478 // Allows subclasses to determine which type of Edge is created.
479 // Override this method to produce subclasses of BallLarusEdge if
480 // necessary. The destructor of BallLarusDag will call free on each
482 BallLarusEdge* BallLarusDag::createEdge(BallLarusNode* source,
483 BallLarusNode* target,
484 unsigned duplicateCount) {
485 return( new BallLarusEdge(source, target, duplicateCount) );
488 // Proxy to node's constructor. Updates the DAG state.
489 BallLarusNode* BallLarusDag::addNode(BasicBlock* BB) {
490 BallLarusNode* newNode = createNode(BB);
491 _nodes.push_back(newNode);
495 // Proxy to edge's constructor. Updates the DAG state.
496 BallLarusEdge* BallLarusDag::addEdge(BallLarusNode* source,
497 BallLarusNode* target,
498 unsigned duplicateCount) {
499 BallLarusEdge* newEdge = createEdge(source, target, duplicateCount);
500 _edges.push_back(newEdge);
501 source->addSuccEdge(newEdge);
502 target->addPredEdge(newEdge);
506 // Adds a backedge with its phony edges. Updates the DAG state.
507 void BallLarusDag::addBackedge(BallLarusNode* source, BallLarusNode* target,
508 unsigned duplicateCount) {
509 BallLarusEdge* childEdge = addEdge(source, target, duplicateCount);
510 childEdge->setType(BallLarusEdge::BACKEDGE);
512 childEdge->setPhonyRoot(addEdge(getRoot(), target,0));
513 childEdge->setPhonyExit(addEdge(source, getExit(),0));
515 childEdge->getPhonyRoot()->setRealEdge(childEdge);
516 childEdge->getPhonyRoot()->setType(BallLarusEdge::BACKEDGE_PHONY);
518 childEdge->getPhonyExit()->setRealEdge(childEdge);
519 childEdge->getPhonyExit()->setType(BallLarusEdge::BACKEDGE_PHONY);
520 _backEdges.push_back(childEdge);