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/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"
  40 #include <queue>
  41 #include <sstream>
  42 #include <stack>
  43 #include <string>
  44 #include <utility>
  45
  46 using namespace llvm;
  47
  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."));
  53
  54 // Returns the basic block for the BallLarusNode
  55 BasicBlock* BallLarusNode::getBlock() {
  56   return(_basicBlock);
  57 }
  58
  59 // Returns the number of paths to the exit starting at the node.
  60 unsigned BallLarusNode::getNumberPaths() {
  61   return(_numberPaths);
  62 }
  63
  64 // Sets the number of paths to the exit starting at the node.
  65 void BallLarusNode::setNumberPaths(unsigned numberPaths) {
  66   _numberPaths = numberPaths;
  67 }
  68
  69 // Gets the NodeColor used in graph algorithms.
  70 BallLarusNode::NodeColor BallLarusNode::getColor() {
  71   return(_color);
  72 }
  73
  74 // Sets the NodeColor used in graph algorithms.
  75 void BallLarusNode::setColor(BallLarusNode::NodeColor color) {
  76   _color = color;
  77 }
  78
  79 // Returns an iterator over predecessor edges. Includes phony and
  80 // backedges.
  81 BLEdgeIterator BallLarusNode::predBegin() {
  82   return(_predEdges.begin());
  83 }
  84
  85 // Returns the end sentinel for the predecessor iterator.
  86 BLEdgeIterator BallLarusNode::predEnd() {
  87   return(_predEdges.end());
  88 }
  89
  90 // Returns the number of predecessor edges.  Includes phony and
  91 // backedges.
  92 unsigned BallLarusNode::getNumberPredEdges() {
  93   return(_predEdges.size());
  94 }
  95
  96 // Returns an iterator over successor edges. Includes phony and
  97 // backedges.
  98 BLEdgeIterator BallLarusNode::succBegin() {
  99   return(_succEdges.begin());
 100 }
 101
 102 // Returns the end sentinel for the successor iterator.
 103 BLEdgeIterator BallLarusNode::succEnd() {
 104   return(_succEdges.end());
 105 }
 106
 107 // Returns the number of successor edges.  Includes phony and
 108 // backedges.
 109 unsigned BallLarusNode::getNumberSuccEdges() {
 110   return(_succEdges.size());
 111 }
 112
 113 // Add an edge to the predecessor list.
 114 void BallLarusNode::addPredEdge(BallLarusEdge* edge) {
 115   _predEdges.push_back(edge);
 116 }
 117
 118 // Remove an edge from the predecessor list.
 119 void BallLarusNode::removePredEdge(BallLarusEdge* edge) {
 120   removeEdge(_predEdges, edge);
 121 }
 122
 123 // Add an edge to the successor list.
 124 void BallLarusNode::addSuccEdge(BallLarusEdge* edge) {
 125   _succEdges.push_back(edge);
 126 }
 127
 128 // Remove an edge from the successor list.
 129 void BallLarusNode::removeSuccEdge(BallLarusEdge* edge) {
 130   removeEdge(_succEdges, edge);
 131 }
 132
 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;
 138
 139   if(getBlock() != NULL) {
 140     if(getBlock()->hasName()) {
 141       std::string tempName(getBlock()->getName());
 142       name << tempName.c_str() << " (" << _uid << ")";
 143     } else
 144       name << "<unnamed> (" << _uid << ")";
 145   } else
 146     name << "<null> (" << _uid << ")";
 147
 148   return name.str();
 149 }
 150
 151 // Removes an edge from an edgeVector.  Used by removePredEdge and
 152 // removeSuccEdge.
 153 void BallLarusNode::removeEdge(BLEdgeVector& v, BallLarusEdge* e) {
 154   // TODO: Avoid linear scan by using a set instead
 155   for(BLEdgeIterator i = v.begin(),
 156         end = v.end();
 157       i != end;
 158       ++i) {
 159     if((*i) == e) {
 160       v.erase(i);
 161       break;
 162     }
 163   }
 164 }
 165
 166 // Returns the source node of this edge.
 167 BallLarusNode* BallLarusEdge::getSource() const {
 168   return(_source);
 169 }
 170
 171 // Returns the target node of this edge.
 172 BallLarusNode* BallLarusEdge::getTarget() const {
 173   return(_target);
 174 }
 175
 176 // Sets the type of the edge.
 177 BallLarusEdge::EdgeType BallLarusEdge::getType() const {
 178   return _edgeType;
 179 }
 180
 181 // Gets the type of the edge.
 182 void BallLarusEdge::setType(EdgeType type) {
 183   _edgeType = type;
 184 }
 185
 186 // Returns the weight of this edge.  Used to decode path numbers to sequences
 187 // of basic blocks.
 188 unsigned BallLarusEdge::getWeight() {
 189   return(_weight);
 190 }
 191
 192 // Sets the weight of the edge.  Used during path numbering.
 193 void BallLarusEdge::setWeight(unsigned weight) {
 194   _weight = weight;
 195 }
 196
 197 // Gets the phony edge originating at the root.
 198 BallLarusEdge* BallLarusEdge::getPhonyRoot() {
 199   return _phonyRoot;
 200 }
 201
 202 // Sets the phony edge originating at the root.
 203 void BallLarusEdge::setPhonyRoot(BallLarusEdge* phonyRoot) {
 204   _phonyRoot = phonyRoot;
 205 }
 206
 207 // Gets the phony edge terminating at the exit.
 208 BallLarusEdge* BallLarusEdge::getPhonyExit() {
 209   return _phonyExit;
 210 }
 211
 212 // Sets the phony edge terminating at the exit.
 213 void BallLarusEdge::setPhonyExit(BallLarusEdge* phonyExit) {
 214   _phonyExit = phonyExit;
 215 }
 216
 217 // Gets the associated real edge if this is a phony edge.
 218 BallLarusEdge* BallLarusEdge::getRealEdge() {
 219   return _realEdge;
 220 }
 221
 222 // Sets the associated real edge if this is a phony edge.
 223 void BallLarusEdge::setRealEdge(BallLarusEdge* realEdge) {
 224   _realEdge = realEdge;
 225 }
 226
 227 // Returns the duplicate number of the edge.
 228 unsigned BallLarusEdge::getDuplicateNumber() {
 229   return(_duplicateNumber);
 230 }
 231
 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;
 237
 238   _root = addNode(&(_function.getEntryBlock()));
 239   _exit = addNode(NULL);
 240
 241   // start search from root
 242   dfsStack.push(getRoot());
 243
 244   // dfs to add each bb into the dag
 245   while(dfsStack.size())
 246     buildNode(inDag, dfsStack);
 247
 248   // put in the final edge
 249   addEdge(getExit(),getRoot(),0);
 250 }
 251
 252 // Frees all memory associated with the DAG.
 253 BallLarusDag::~BallLarusDag() {
 254   for(BLEdgeIterator edge = _edges.begin(), end = _edges.end(); edge != end;
 255       ++edge)
 256     delete (*edge);
 257
 258   for(BLNodeIterator node = _nodes.begin(), end = _nodes.end(); node != end;
 259       ++node)
 260     delete (*node);
 261 }
 262
 263 // Calculate the path numbers by assigning edge increments as prescribed
 264 // in Ball-Larus path profiling.
 265 void BallLarusDag::calculatePathNumbers() {
 266   BallLarusNode* node;
 267   std::queue<BallLarusNode*> bfsQueue;
 268   bfsQueue.push(getExit());
 269
 270   while(bfsQueue.size() > 0) {
 271     node = bfsQueue.front();
 272
 273     DEBUG(dbgs() << "calculatePathNumbers on " << node->getName() << "\n");
 274
 275     bfsQueue.pop();
 276     unsigned prevPathNumber = node->getNumberPaths();
 277     calculatePathNumbersFrom(node);
 278
 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);
 284
 285       // Counters to handle the possibility of a multi-graph
 286       BasicBlock* oldTarget = 0;
 287       unsigned duplicateNumber = 0;
 288
 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++ ) {
 292
 293         if( (*succ)->getType() == BallLarusEdge::NORMAL ) {
 294           // is this edge a duplicate?
 295           if( oldTarget != (*succ)->getTarget()->getBlock() )
 296             duplicateNumber = 0;
 297
 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);
 303
 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);
 309         }
 310       }
 311
 312       calculatePathNumbersFrom(node);
 313     }
 314
 315     DEBUG(dbgs() << "prev, new number paths " << prevPathNumber << ", "
 316           << node->getNumberPaths() << ".\n");
 317
 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 )
 324           continue;
 325
 326         BallLarusNode* nextNode = (*pred)->getSource();
 327         // not yet visited?
 328         if(nextNode->getNumberPaths() == 0)
 329           bfsQueue.push(nextNode);
 330       }
 331     }
 332   }
 333
 334   DEBUG(dbgs() << "\tNumber of paths: " << getRoot()->getNumberPaths() << "\n");
 335 }
 336
 337 // Returns the number of paths for the Dag.
 338 unsigned BallLarusDag::getNumberOfPaths() {
 339   return(getRoot()->getNumberPaths());
 340 }
 341
 342 // Returns the root (i.e. entry) node for the DAG.
 343 BallLarusNode* BallLarusDag::getRoot() {
 344   return _root;
 345 }
 346
 347 // Returns the exit node for the DAG.
 348 BallLarusNode* BallLarusDag::getExit() {
 349   return _exit;
 350 }
 351
 352 // Returns the function for the DAG.
 353 Function& BallLarusDag::getFunction() {
 354   return(_function);
 355 }
 356
 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);
 361 }
 362
 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();
 367
 368   if(currentNode->getColor() != BallLarusNode::WHITE) {
 369     // we have already visited this node
 370     dfsStack.pop();
 371     currentNode->setColor(BallLarusNode::BLACK);
 372   } else {
 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;
 377            bbCurrent++ ) {
 378         Instruction& instr = *bbCurrent;
 379         if( instr.getOpcode() == Instruction::Call ) {
 380           BallLarusEdge* callEdge = addEdge(currentNode, getExit(), 0);
 381           callEdge->setType(BallLarusEdge::CALLEDGE_PHONY);
 382           break;
 383         }
 384       }
 385     }
 386
 387     TerminatorInst* terminator = currentNode->getBlock()->getTerminator();
 388     if(isa<ReturnInst>(terminator) || isa<UnreachableInst>(terminator) ||
 389        isa<ResumeInst>(terminator))
 390       addEdge(currentNode, getExit(),0);
 391
 392     currentNode->setColor(BallLarusNode::GRAY);
 393     inDag[currentBlock] = currentNode;
 394
 395     BasicBlock* oldSuccessor = 0;
 396     unsigned duplicateNumber = 0;
 397
 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;
 403
 404       // is this edge a duplicate?
 405       if (oldSuccessor == succBB)
 406         duplicateNumber++;
 407       else
 408         duplicateNumber = 0;
 409
 410       buildEdge(inDag, dfsStack, currentNode, succBB, duplicateNumber);
 411     }
 412   }
 413 }
 414
 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];
 420
 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);
 428   } else {
 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;
 436     }
 437     addEdge(currentNode, childNode, duplicateCount);
 438     dfsStack.push(childNode);
 439   }
 440 }
 441
 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);
 448   else {
 449     unsigned sumPaths = 0;
 450     BallLarusNode* succNode;
 451
 452     for(BLEdgeIterator succ = node->succBegin(), end = node->succEnd();
 453         succ != end; succ++) {
 454       if( (*succ)->getType() == BallLarusEdge::BACKEDGE ||
 455           (*succ)->getType() == BallLarusEdge::SPLITEDGE )
 456         continue;
 457
 458       (*succ)->setWeight(sumPaths);
 459       succNode = (*succ)->getTarget();
 460
 461       if( !succNode->getNumberPaths() )
 462         return;
 463       sumPaths += succNode->getNumberPaths();
 464     }
 465
 466     node->setNumberPaths(sumPaths);
 467   }
 468 }
 469
 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
 473 // pointer created.
 474 BallLarusNode* BallLarusDag::createNode(BasicBlock* BB) {
 475   return( new BallLarusNode(BB) );
 476 }
 477
 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
 481 // pointer created.
 482 BallLarusEdge* BallLarusDag::createEdge(BallLarusNode* source,
 483                                         BallLarusNode* target,
 484                                         unsigned duplicateCount) {
 485   return( new BallLarusEdge(source, target, duplicateCount) );
 486 }
 487
 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);
 492   return( newNode );
 493 }
 494
 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);
 503   return(newEdge);
 504 }
 505
 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);
 511
 512   childEdge->setPhonyRoot(addEdge(getRoot(), target,0));
 513   childEdge->setPhonyExit(addEdge(source, getExit(),0));
 514
 515   childEdge->getPhonyRoot()->setRealEdge(childEdge);
 516   childEdge->getPhonyRoot()->setType(BallLarusEdge::BACKEDGE_PHONY);
 517
 518   childEdge->getPhonyExit()->setRealEdge(childEdge);
 519   childEdge->getPhonyExit()->setType(BallLarusEdge::BACKEDGE_PHONY);
 520   _backEdges.push_back(childEdge);
 521 }