lib/Analysis/PathNumbering.cpp

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