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/TypeBuilder.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"
40
41#include <queue>
42#include <stack>
43#include <string>
44#include <utility>
45#include <sstream>
46
47using namespace llvm;
48
49// Are we enabling early termination
50static 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
56BasicBlock* BallLarusNode::getBlock() {
57  return(_basicBlock);
58}
59
60// Returns the number of paths to the exit starting at the node.
61unsigned BallLarusNode::getNumberPaths() {
62  return(_numberPaths);
63}
64
65// Sets the number of paths to the exit starting at the node.
66void BallLarusNode::setNumberPaths(unsigned numberPaths) {
67  _numberPaths = numberPaths;
68}
69
70// Gets the NodeColor used in graph algorithms.
71BallLarusNode::NodeColor BallLarusNode::getColor() {
72  return(_color);
73}
74
75// Sets the NodeColor used in graph algorithms.
76void BallLarusNode::setColor(BallLarusNode::NodeColor color) {
77  _color = color;
78}
79
80// Returns an iterator over predecessor edges. Includes phony and
81// backedges.
82BLEdgeIterator BallLarusNode::predBegin() {
83  return(_predEdges.begin());
84}
85
86// Returns the end sentinel for the predecessor iterator.
87BLEdgeIterator BallLarusNode::predEnd() {
88  return(_predEdges.end());
89}
90
91// Returns the number of predecessor edges.  Includes phony and
92// backedges.
93unsigned BallLarusNode::getNumberPredEdges() {
94  return(_predEdges.size());
95}
96
97// Returns an iterator over successor edges. Includes phony and
98// backedges.
99BLEdgeIterator BallLarusNode::succBegin() {
100  return(_succEdges.begin());
101}
102
103// Returns the end sentinel for the successor iterator.
104BLEdgeIterator BallLarusNode::succEnd() {
105  return(_succEdges.end());
106}
107
108// Returns the number of successor edges.  Includes phony and
109// backedges.
110unsigned BallLarusNode::getNumberSuccEdges() {
111  return(_succEdges.size());
112}
113
114// Add an edge to the predecessor list.
115void BallLarusNode::addPredEdge(BallLarusEdge* edge) {
116  _predEdges.push_back(edge);
117}
118
119// Remove an edge from the predecessor list.
120void BallLarusNode::removePredEdge(BallLarusEdge* edge) {
121  removeEdge(_predEdges, edge);
122}
123
124// Add an edge to the successor list.
125void BallLarusNode::addSuccEdge(BallLarusEdge* edge) {
126  _succEdges.push_back(edge);
127}
128
129// Remove an edge from the successor list.
130void 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.
137std::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.
154void 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.
168BallLarusNode* BallLarusEdge::getSource() const {
169  return(_source);
170}
171
172// Returns the target node of this edge.
173BallLarusNode* BallLarusEdge::getTarget() const {
174  return(_target);
175}
176
177// Sets the type of the edge.
178BallLarusEdge::EdgeType BallLarusEdge::getType() const {
179  return _edgeType;
180}
181
182// Gets the type of the edge.
183void 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.
189unsigned BallLarusEdge::getWeight() {
190  return(_weight);
191}
192
193// Sets the weight of the edge.  Used during path numbering.
194void BallLarusEdge::setWeight(unsigned weight) {
195  _weight = weight;
196}
197
198// Gets the phony edge originating at the root.
199BallLarusEdge* BallLarusEdge::getPhonyRoot() {
200  return _phonyRoot;
201}
202
203// Sets the phony edge originating at the root.
204void BallLarusEdge::setPhonyRoot(BallLarusEdge* phonyRoot) {
205  _phonyRoot = phonyRoot;
206}
207
208// Gets the phony edge terminating at the exit.
209BallLarusEdge* BallLarusEdge::getPhonyExit() {
210  return _phonyExit;
211}
212
213// Sets the phony edge terminating at the exit.
214void BallLarusEdge::setPhonyExit(BallLarusEdge* phonyExit) {
215  _phonyExit = phonyExit;
216}
217
218// Gets the associated real edge if this is a phony edge.
219BallLarusEdge* BallLarusEdge::getRealEdge() {
220  return _realEdge;
221}
222
223// Sets the associated real edge if this is a phony edge.
224void BallLarusEdge::setRealEdge(BallLarusEdge* realEdge) {
225  _realEdge = realEdge;
226}
227
228// Returns the duplicate number of the edge.
229unsigned BallLarusEdge::getDuplicateNumber() {
230  return(_duplicateNumber);
231}
232
233// Initialization that requires virtual functions which are not fully
234// functional in the constructor.
235void 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.
254BallLarusDag::~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.
266void 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.
339unsigned BallLarusDag::getNumberOfPaths() {
340  return(getRoot()->getNumberPaths());
341}
342
343// Returns the root (i.e. entry) node for the DAG.
344BallLarusNode* BallLarusDag::getRoot() {
345  return _root;
346}
347
348// Returns the exit node for the DAG.
349BallLarusNode* BallLarusDag::getExit() {
350  return _exit;
351}
352
353// Returns the function for the DAG.
354Function& BallLarusDag::getFunction() {
355  return(_function);
356}
357
358// Clears the node colors.
359void 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.
365void 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))
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.
417void 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.
445void 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.
475BallLarusNode* 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.
483BallLarusEdge* 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.
490BallLarusNode* 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.
497BallLarusEdge* 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.
508void 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