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