1218885Sdim//===- PathProfiling.cpp - Inserts counters for path profiling ------------===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// This pass instruments functions for Ball-Larus path profiling. Ball-Larus 11218885Sdim// profiling converts the CFG into a DAG by replacing backedges with edges 12218885Sdim// from entry to the start block and from the end block to exit. The paths 13218885Sdim// along the new DAG are enumrated, i.e. each path is given a path number. 14218885Sdim// Edges are instrumented to increment the path number register, such that the 15218885Sdim// path number register will equal the path number of the path taken at the 16218885Sdim// exit. 17218885Sdim// 18218885Sdim// This file defines classes for building a CFG for use with different stages 19218885Sdim// in the Ball-Larus path profiling instrumentation [Ball96]. The 20218885Sdim// requirements are formatting the llvm CFG into the Ball-Larus DAG, path 21218885Sdim// numbering, finding a spanning tree, moving increments from the spanning 22218885Sdim// tree to chords. 23218885Sdim// 24218885Sdim// Terms: 25218885Sdim// DAG - Directed Acyclic Graph. 26218885Sdim// Ball-Larus DAG - A CFG with an entry node, an exit node, and backedges 27218885Sdim// removed in the following manner. For every backedge 28218885Sdim// v->w, insert edge ENTRY->w and edge v->EXIT. 29218885Sdim// Path Number - The number corresponding to a specific path through a 30218885Sdim// Ball-Larus DAG. 31218885Sdim// Spanning Tree - A subgraph, S, is a spanning tree if S covers all 32218885Sdim// vertices and is a tree. 33218885Sdim// Chord - An edge not in the spanning tree. 34218885Sdim// 35218885Sdim// [Ball96] 36218885Sdim// T. Ball and J. R. Larus. "Efficient Path Profiling." 37218885Sdim// International Symposium on Microarchitecture, pages 46-57, 1996. 38218885Sdim// http://portal.acm.org/citation.cfm?id=243857 39218885Sdim// 40218885Sdim// [Ball94] 41218885Sdim// Thomas Ball. "Efficiently Counting Program Events with Support for 42218885Sdim// On-line queries." 43218885Sdim// ACM Transactions on Programmmg Languages and Systems, Vol 16, No 5, 44218885Sdim// September 1994, Pages 1399-1410. 45218885Sdim//===----------------------------------------------------------------------===// 46218885Sdim#define DEBUG_TYPE "insert-path-profiling" 47218885Sdim 48249423Sdim#include "llvm/Transforms/Instrumentation.h" 49218885Sdim#include "ProfilingUtils.h" 50218885Sdim#include "llvm/Analysis/PathNumbering.h" 51249423Sdim#include "llvm/IR/Constants.h" 52249423Sdim#include "llvm/IR/DerivedTypes.h" 53249423Sdim#include "llvm/IR/InstrTypes.h" 54249423Sdim#include "llvm/IR/Instructions.h" 55249423Sdim#include "llvm/IR/LLVMContext.h" 56249423Sdim#include "llvm/IR/Module.h" 57249423Sdim#include "llvm/IR/TypeBuilder.h" 58218885Sdim#include "llvm/Pass.h" 59218885Sdim#include "llvm/Support/CFG.h" 60218885Sdim#include "llvm/Support/CommandLine.h" 61249423Sdim#include "llvm/Support/Compiler.h" 62218885Sdim#include "llvm/Support/Debug.h" 63218885Sdim#include "llvm/Support/raw_ostream.h" 64218885Sdim#include "llvm/Transforms/Utils/BasicBlockUtils.h" 65218885Sdim#include <vector> 66218885Sdim 67218885Sdim#define HASH_THRESHHOLD 100000 68218885Sdim 69218885Sdimusing namespace llvm; 70218885Sdim 71218885Sdimnamespace { 72218885Sdimclass BLInstrumentationNode; 73218885Sdimclass BLInstrumentationEdge; 74218885Sdimclass BLInstrumentationDag; 75218885Sdim 76218885Sdim// --------------------------------------------------------------------------- 77218885Sdim// BLInstrumentationNode extends BallLarusNode with member used by the 78218885Sdim// instrumentation algortihms. 79218885Sdim// --------------------------------------------------------------------------- 80218885Sdimclass BLInstrumentationNode : public BallLarusNode { 81218885Sdimpublic: 82218885Sdim // Creates a new BLInstrumentationNode from a BasicBlock. 83218885Sdim BLInstrumentationNode(BasicBlock* BB); 84218885Sdim 85218885Sdim // Get/sets the Value corresponding to the pathNumber register, 86218885Sdim // constant or phinode. Used by the instrumentation code to remember 87218885Sdim // path number Values. 88218885Sdim Value* getStartingPathNumber(); 89218885Sdim void setStartingPathNumber(Value* pathNumber); 90218885Sdim 91218885Sdim Value* getEndingPathNumber(); 92218885Sdim void setEndingPathNumber(Value* pathNumber); 93218885Sdim 94218885Sdim // Get/set the PHINode Instruction for this node. 95218885Sdim PHINode* getPathPHI(); 96218885Sdim void setPathPHI(PHINode* pathPHI); 97218885Sdim 98218885Sdimprivate: 99218885Sdim 100218885Sdim Value* _startingPathNumber; // The Value for the current pathNumber. 101218885Sdim Value* _endingPathNumber; // The Value for the current pathNumber. 102218885Sdim PHINode* _pathPHI; // The PHINode for current pathNumber. 103218885Sdim}; 104218885Sdim 105218885Sdim// -------------------------------------------------------------------------- 106218885Sdim// BLInstrumentationEdge extends BallLarusEdge with data about the 107218885Sdim// instrumentation that will end up on each edge. 108218885Sdim// -------------------------------------------------------------------------- 109218885Sdimclass BLInstrumentationEdge : public BallLarusEdge { 110218885Sdimpublic: 111218885Sdim BLInstrumentationEdge(BLInstrumentationNode* source, 112218885Sdim BLInstrumentationNode* target); 113218885Sdim 114218885Sdim // Sets the target node of this edge. Required to split edges. 115218885Sdim void setTarget(BallLarusNode* node); 116218885Sdim 117218885Sdim // Get/set whether edge is in the spanning tree. 118218885Sdim bool isInSpanningTree() const; 119218885Sdim void setIsInSpanningTree(bool isInSpanningTree); 120218885Sdim 121218885Sdim // Get/ set whether this edge will be instrumented with a path number 122218885Sdim // initialization. 123218885Sdim bool isInitialization() const; 124218885Sdim void setIsInitialization(bool isInitialization); 125218885Sdim 126218885Sdim // Get/set whether this edge will be instrumented with a path counter 127218885Sdim // increment. Notice this is incrementing the path counter 128218885Sdim // corresponding to the path number register. The path number 129218885Sdim // increment is determined by getIncrement(). 130218885Sdim bool isCounterIncrement() const; 131218885Sdim void setIsCounterIncrement(bool isCounterIncrement); 132218885Sdim 133218885Sdim // Get/set the path number increment that this edge will be instrumented 134218885Sdim // with. This is distinct from the path counter increment and the 135218885Sdim // weight. The counter increment counts the number of executions of 136218885Sdim // some path, whereas the path number keeps track of which path number 137218885Sdim // the program is on. 138218885Sdim long getIncrement() const; 139218885Sdim void setIncrement(long increment); 140218885Sdim 141218885Sdim // Get/set whether the edge has been instrumented. 142218885Sdim bool hasInstrumentation(); 143218885Sdim void setHasInstrumentation(bool hasInstrumentation); 144218885Sdim 145218885Sdim // Returns the successor number of this edge in the source. 146218885Sdim unsigned getSuccessorNumber(); 147218885Sdim 148218885Sdimprivate: 149218885Sdim // The increment that the code will be instrumented with. 150218885Sdim long long _increment; 151218885Sdim 152218885Sdim // Whether this edge is in the spanning tree. 153218885Sdim bool _isInSpanningTree; 154218885Sdim 155218885Sdim // Whether this edge is an initialiation of the path number. 156218885Sdim bool _isInitialization; 157218885Sdim 158218885Sdim // Whether this edge is a path counter increment. 159218885Sdim bool _isCounterIncrement; 160218885Sdim 161218885Sdim // Whether this edge has been instrumented. 162218885Sdim bool _hasInstrumentation; 163218885Sdim}; 164218885Sdim 165218885Sdim// --------------------------------------------------------------------------- 166218885Sdim// BLInstrumentationDag extends BallLarusDag with algorithms that 167218885Sdim// determine where instrumentation should be placed. 168218885Sdim// --------------------------------------------------------------------------- 169218885Sdimclass BLInstrumentationDag : public BallLarusDag { 170218885Sdimpublic: 171218885Sdim BLInstrumentationDag(Function &F); 172218885Sdim 173218885Sdim // Returns the Exit->Root edge. This edge is required for creating 174218885Sdim // directed cycles in the algorithm for moving instrumentation off of 175218885Sdim // the spanning tree 176218885Sdim BallLarusEdge* getExitRootEdge(); 177218885Sdim 178218885Sdim // Returns an array of phony edges which mark those nodes 179218885Sdim // with function calls 180218885Sdim BLEdgeVector getCallPhonyEdges(); 181218885Sdim 182218885Sdim // Gets/sets the path counter array 183218885Sdim GlobalVariable* getCounterArray(); 184218885Sdim void setCounterArray(GlobalVariable* c); 185218885Sdim 186218885Sdim // Calculates the increments for the chords, thereby removing 187218885Sdim // instrumentation from the spanning tree edges. Implementation is based 188218885Sdim // on the algorithm in Figure 4 of [Ball94] 189218885Sdim void calculateChordIncrements(); 190218885Sdim 191218885Sdim // Updates the state when an edge has been split 192218885Sdim void splitUpdate(BLInstrumentationEdge* formerEdge, BasicBlock* newBlock); 193218885Sdim 194218885Sdim // Calculates a spanning tree of the DAG ignoring cycles. Whichever 195218885Sdim // edges are in the spanning tree will not be instrumented, but this 196218885Sdim // implementation does not try to minimize the instrumentation overhead 197218885Sdim // by trying to find hot edges. 198218885Sdim void calculateSpanningTree(); 199218885Sdim 200218885Sdim // Pushes initialization further down in order to group the first 201218885Sdim // increment and initialization. 202218885Sdim void pushInitialization(); 203218885Sdim 204218885Sdim // Pushes the path counter increments up in order to group the last path 205218885Sdim // number increment. 206218885Sdim void pushCounters(); 207218885Sdim 208218885Sdim // Removes phony edges from the successor list of the source, and the 209218885Sdim // predecessor list of the target. 210218885Sdim void unlinkPhony(); 211218885Sdim 212218885Sdim // Generate dot graph for the function 213218885Sdim void generateDotGraph(); 214218885Sdim 215218885Sdimprotected: 216218885Sdim // BLInstrumentationDag creates BLInstrumentationNode objects in this 217218885Sdim // method overriding the creation of BallLarusNode objects. 218218885Sdim // 219218885Sdim // Allows subclasses to determine which type of Node is created. 220218885Sdim // Override this method to produce subclasses of BallLarusNode if 221218885Sdim // necessary. 222218885Sdim virtual BallLarusNode* createNode(BasicBlock* BB); 223218885Sdim 224218885Sdim // BLInstrumentationDag create BLInstrumentationEdges. 225218885Sdim // 226218885Sdim // Allows subclasses to determine which type of Edge is created. 227218885Sdim // Override this method to produce subclasses of BallLarusEdge if 228218885Sdim // necessary. Parameters source and target will have been created by 229218885Sdim // createNode and can be cast to the subclass of BallLarusNode* 230218885Sdim // returned by createNode. 231218885Sdim virtual BallLarusEdge* createEdge( 232218885Sdim BallLarusNode* source, BallLarusNode* target, unsigned edgeNumber); 233218885Sdim 234218885Sdimprivate: 235218885Sdim BLEdgeVector _treeEdges; // All edges in the spanning tree. 236218885Sdim BLEdgeVector _chordEdges; // All edges not in the spanning tree. 237218885Sdim GlobalVariable* _counterArray; // Array to store path counters 238218885Sdim 239218885Sdim // Removes the edge from the appropriate predecessor and successor lists. 240218885Sdim void unlinkEdge(BallLarusEdge* edge); 241218885Sdim 242218885Sdim // Makes an edge part of the spanning tree. 243218885Sdim void makeEdgeSpanning(BLInstrumentationEdge* edge); 244218885Sdim 245218885Sdim // Pushes initialization and calls itself recursively. 246218885Sdim void pushInitializationFromEdge(BLInstrumentationEdge* edge); 247218885Sdim 248218885Sdim // Pushes path counter increments up recursively. 249218885Sdim void pushCountersFromEdge(BLInstrumentationEdge* edge); 250218885Sdim 251218885Sdim // Depth first algorithm for determining the chord increments.f 252218885Sdim void calculateChordIncrementsDfs( 253218885Sdim long weight, BallLarusNode* v, BallLarusEdge* e); 254218885Sdim 255218885Sdim // Determines the relative direction of two edges. 256218885Sdim int calculateChordIncrementsDir(BallLarusEdge* e, BallLarusEdge* f); 257218885Sdim}; 258218885Sdim 259218885Sdim// --------------------------------------------------------------------------- 260221345Sdim// PathProfiler is a module pass which instruments path profiling instructions 261218885Sdim// --------------------------------------------------------------------------- 262218885Sdimclass PathProfiler : public ModulePass { 263218885Sdimprivate: 264218885Sdim // Current context for multi threading support. 265218885Sdim LLVMContext* Context; 266218885Sdim 267218885Sdim // Which function are we currently instrumenting 268218885Sdim unsigned currentFunctionNumber; 269218885Sdim 270218885Sdim // The function prototype in the profiling runtime for incrementing a 271218885Sdim // single path counter in a hash table. 272218885Sdim Constant* llvmIncrementHashFunction; 273218885Sdim Constant* llvmDecrementHashFunction; 274218885Sdim 275218885Sdim // Instruments each function with path profiling. 'main' is instrumented 276218885Sdim // with code to save the profile to disk. 277218885Sdim bool runOnModule(Module &M); 278218885Sdim 279218885Sdim // Analyzes the function for Ball-Larus path profiling, and inserts code. 280218885Sdim void runOnFunction(std::vector<Constant*> &ftInit, Function &F, Module &M); 281218885Sdim 282218885Sdim // Creates an increment constant representing incr. 283218885Sdim ConstantInt* createIncrementConstant(long incr, int bitsize); 284218885Sdim 285218885Sdim // Creates an increment constant representing the value in 286218885Sdim // edge->getIncrement(). 287218885Sdim ConstantInt* createIncrementConstant(BLInstrumentationEdge* edge); 288218885Sdim 289218885Sdim // Finds the insertion point after pathNumber in block. PathNumber may 290218885Sdim // be NULL. 291218885Sdim BasicBlock::iterator getInsertionPoint( 292218885Sdim BasicBlock* block, Value* pathNumber); 293218885Sdim 294218885Sdim // Inserts source's pathNumber Value* into target. Target may or may not 295218885Sdim // have multiple predecessors, and may or may not have its phiNode 296218885Sdim // initalized. 297218885Sdim void pushValueIntoNode( 298218885Sdim BLInstrumentationNode* source, BLInstrumentationNode* target); 299218885Sdim 300218885Sdim // Inserts source's pathNumber Value* into the appropriate slot of 301218885Sdim // target's phiNode. 302218885Sdim void pushValueIntoPHI( 303218885Sdim BLInstrumentationNode* target, BLInstrumentationNode* source); 304218885Sdim 305218885Sdim // The Value* in node, oldVal, is updated with a Value* correspodning to 306218885Sdim // oldVal + addition. 307218885Sdim void insertNumberIncrement(BLInstrumentationNode* node, Value* addition, 308218885Sdim bool atBeginning); 309218885Sdim 310218885Sdim // Creates a counter increment in the given node. The Value* in node is 311218885Sdim // taken as the index into a hash table. 312218885Sdim void insertCounterIncrement( 313218885Sdim Value* incValue, 314218885Sdim BasicBlock::iterator insertPoint, 315218885Sdim BLInstrumentationDag* dag, 316218885Sdim bool increment = true); 317218885Sdim 318218885Sdim // A PHINode is created in the node, and its values initialized to -1U. 319218885Sdim void preparePHI(BLInstrumentationNode* node); 320218885Sdim 321218885Sdim // Inserts instrumentation for the given edge 322218885Sdim // 323218885Sdim // Pre: The edge's source node has pathNumber set if edge is non zero 324218885Sdim // path number increment. 325218885Sdim // 326218885Sdim // Post: Edge's target node has a pathNumber set to the path number Value 327218885Sdim // corresponding to the value of the path register after edge's 328218885Sdim // execution. 329218885Sdim void insertInstrumentationStartingAt( 330218885Sdim BLInstrumentationEdge* edge, 331218885Sdim BLInstrumentationDag* dag); 332218885Sdim 333218885Sdim // If this edge is a critical edge, then inserts a node at this edge. 334218885Sdim // This edge becomes the first edge, and a new BallLarusEdge is created. 335218885Sdim bool splitCritical(BLInstrumentationEdge* edge, BLInstrumentationDag* dag); 336218885Sdim 337218885Sdim // Inserts instrumentation according to the marked edges in dag. Phony 338218885Sdim // edges must be unlinked from the DAG, but accessible from the 339218885Sdim // backedges. Dag must have initializations, path number increments, and 340218885Sdim // counter increments present. 341218885Sdim // 342218885Sdim // Counter storage is created here. 343218885Sdim void insertInstrumentation( BLInstrumentationDag& dag, Module &M); 344218885Sdim 345218885Sdimpublic: 346218885Sdim static char ID; // Pass identification, replacement for typeid 347218885Sdim PathProfiler() : ModulePass(ID) { 348218885Sdim initializePathProfilerPass(*PassRegistry::getPassRegistry()); 349218885Sdim } 350218885Sdim 351218885Sdim virtual const char *getPassName() const { 352218885Sdim return "Path Profiler"; 353218885Sdim } 354218885Sdim}; 355218885Sdim} // end anonymous namespace 356218885Sdim 357218885Sdim// Should we print the dot-graphs 358218885Sdimstatic cl::opt<bool> DotPathDag("path-profile-pathdag", cl::Hidden, 359218885Sdim cl::desc("Output the path profiling DAG for each function.")); 360218885Sdim 361218885Sdim// Register the path profiler as a pass 362218885Sdimchar PathProfiler::ID = 0; 363218885SdimINITIALIZE_PASS(PathProfiler, "insert-path-profiling", 364218885Sdim "Insert instrumentation for Ball-Larus path profiling", 365218885Sdim false, false) 366218885Sdim 367218885SdimModulePass *llvm::createPathProfilerPass() { return new PathProfiler(); } 368218885Sdim 369218885Sdimnamespace llvm { 370218885Sdim class PathProfilingFunctionTable {}; 371218885Sdim 372218885Sdim // Type for global array storing references to hashes or arrays 373218885Sdim template<bool xcompile> class TypeBuilder<PathProfilingFunctionTable, 374218885Sdim xcompile> { 375218885Sdim public: 376226633Sdim static StructType *get(LLVMContext& C) { 377218885Sdim return( StructType::get( 378224145Sdim TypeBuilder<types::i<32>, xcompile>::get(C), // type 379218885Sdim TypeBuilder<types::i<32>, xcompile>::get(C), // array size 380218885Sdim TypeBuilder<types::i<8>*, xcompile>::get(C), // array/hash ptr 381218885Sdim NULL)); 382218885Sdim } 383218885Sdim }; 384218885Sdim 385218885Sdim typedef TypeBuilder<PathProfilingFunctionTable, true> 386218885Sdim ftEntryTypeBuilder; 387218885Sdim 388218885Sdim // BallLarusEdge << operator overloading 389218885Sdim raw_ostream& operator<<(raw_ostream& os, 390221345Sdim const BLInstrumentationEdge& edge) 391221345Sdim LLVM_ATTRIBUTE_USED; 392221345Sdim raw_ostream& operator<<(raw_ostream& os, 393218885Sdim const BLInstrumentationEdge& edge) { 394218885Sdim os << "[" << edge.getSource()->getName() << " -> " 395218885Sdim << edge.getTarget()->getName() << "] init: " 396218885Sdim << (edge.isInitialization() ? "yes" : "no") 397218885Sdim << " incr:" << edge.getIncrement() << " cinc: " 398218885Sdim << (edge.isCounterIncrement() ? "yes" : "no"); 399218885Sdim return(os); 400218885Sdim } 401218885Sdim} 402218885Sdim 403218885Sdim// Creates a new BLInstrumentationNode from a BasicBlock. 404218885SdimBLInstrumentationNode::BLInstrumentationNode(BasicBlock* BB) : 405218885Sdim BallLarusNode(BB), 406218885Sdim _startingPathNumber(NULL), _endingPathNumber(NULL), _pathPHI(NULL) {} 407218885Sdim 408218885Sdim// Constructor for BLInstrumentationEdge. 409218885SdimBLInstrumentationEdge::BLInstrumentationEdge(BLInstrumentationNode* source, 410218885Sdim BLInstrumentationNode* target) 411218885Sdim : BallLarusEdge(source, target, 0), 412218885Sdim _increment(0), _isInSpanningTree(false), _isInitialization(false), 413218885Sdim _isCounterIncrement(false), _hasInstrumentation(false) {} 414218885Sdim 415218885Sdim// Sets the target node of this edge. Required to split edges. 416218885Sdimvoid BLInstrumentationEdge::setTarget(BallLarusNode* node) { 417218885Sdim _target = node; 418218885Sdim} 419218885Sdim 420218885Sdim// Returns whether this edge is in the spanning tree. 421218885Sdimbool BLInstrumentationEdge::isInSpanningTree() const { 422218885Sdim return(_isInSpanningTree); 423218885Sdim} 424218885Sdim 425218885Sdim// Sets whether this edge is in the spanning tree. 426218885Sdimvoid BLInstrumentationEdge::setIsInSpanningTree(bool isInSpanningTree) { 427218885Sdim _isInSpanningTree = isInSpanningTree; 428218885Sdim} 429218885Sdim 430218885Sdim// Returns whether this edge will be instrumented with a path number 431218885Sdim// initialization. 432218885Sdimbool BLInstrumentationEdge::isInitialization() const { 433218885Sdim return(_isInitialization); 434218885Sdim} 435218885Sdim 436218885Sdim// Sets whether this edge will be instrumented with a path number 437218885Sdim// initialization. 438218885Sdimvoid BLInstrumentationEdge::setIsInitialization(bool isInitialization) { 439218885Sdim _isInitialization = isInitialization; 440218885Sdim} 441218885Sdim 442218885Sdim// Returns whether this edge will be instrumented with a path counter 443218885Sdim// increment. Notice this is incrementing the path counter 444218885Sdim// corresponding to the path number register. The path number 445218885Sdim// increment is determined by getIncrement(). 446218885Sdimbool BLInstrumentationEdge::isCounterIncrement() const { 447218885Sdim return(_isCounterIncrement); 448218885Sdim} 449218885Sdim 450218885Sdim// Sets whether this edge will be instrumented with a path counter 451218885Sdim// increment. 452218885Sdimvoid BLInstrumentationEdge::setIsCounterIncrement(bool isCounterIncrement) { 453218885Sdim _isCounterIncrement = isCounterIncrement; 454218885Sdim} 455218885Sdim 456218885Sdim// Gets the path number increment that this edge will be instrumented 457218885Sdim// with. This is distinct from the path counter increment and the 458218885Sdim// weight. The counter increment is counts the number of executions of 459218885Sdim// some path, whereas the path number keeps track of which path number 460218885Sdim// the program is on. 461218885Sdimlong BLInstrumentationEdge::getIncrement() const { 462218885Sdim return(_increment); 463218885Sdim} 464218885Sdim 465218885Sdim// Set whether this edge will be instrumented with a path number 466218885Sdim// increment. 467218885Sdimvoid BLInstrumentationEdge::setIncrement(long increment) { 468218885Sdim _increment = increment; 469218885Sdim} 470218885Sdim 471218885Sdim// True iff the edge has already been instrumented. 472218885Sdimbool BLInstrumentationEdge::hasInstrumentation() { 473218885Sdim return(_hasInstrumentation); 474218885Sdim} 475218885Sdim 476218885Sdim// Set whether this edge has been instrumented. 477218885Sdimvoid BLInstrumentationEdge::setHasInstrumentation(bool hasInstrumentation) { 478218885Sdim _hasInstrumentation = hasInstrumentation; 479218885Sdim} 480218885Sdim 481218885Sdim// Returns the successor number of this edge in the source. 482218885Sdimunsigned BLInstrumentationEdge::getSuccessorNumber() { 483218885Sdim BallLarusNode* sourceNode = getSource(); 484218885Sdim BallLarusNode* targetNode = getTarget(); 485218885Sdim BasicBlock* source = sourceNode->getBlock(); 486218885Sdim BasicBlock* target = targetNode->getBlock(); 487218885Sdim 488218885Sdim if(source == NULL || target == NULL) 489218885Sdim return(0); 490218885Sdim 491218885Sdim TerminatorInst* terminator = source->getTerminator(); 492218885Sdim 493218885Sdim unsigned i; 494218885Sdim for(i=0; i < terminator->getNumSuccessors(); i++) { 495218885Sdim if(terminator->getSuccessor(i) == target) 496218885Sdim break; 497218885Sdim } 498218885Sdim 499218885Sdim return(i); 500218885Sdim} 501218885Sdim 502218885Sdim// BLInstrumentationDag constructor initializes a DAG for the given Function. 503218885SdimBLInstrumentationDag::BLInstrumentationDag(Function &F) : BallLarusDag(F), 504218885Sdim _counterArray(0) { 505218885Sdim} 506218885Sdim 507218885Sdim// Returns the Exit->Root edge. This edge is required for creating 508218885Sdim// directed cycles in the algorithm for moving instrumentation off of 509218885Sdim// the spanning tree 510218885SdimBallLarusEdge* BLInstrumentationDag::getExitRootEdge() { 511218885Sdim BLEdgeIterator erEdge = getExit()->succBegin(); 512218885Sdim return(*erEdge); 513218885Sdim} 514218885Sdim 515218885SdimBLEdgeVector BLInstrumentationDag::getCallPhonyEdges () { 516218885Sdim BLEdgeVector callEdges; 517218885Sdim 518218885Sdim for( BLEdgeIterator edge = _edges.begin(), end = _edges.end(); 519218885Sdim edge != end; edge++ ) { 520218885Sdim if( (*edge)->getType() == BallLarusEdge::CALLEDGE_PHONY ) 521218885Sdim callEdges.push_back(*edge); 522218885Sdim } 523218885Sdim 524218885Sdim return callEdges; 525218885Sdim} 526218885Sdim 527218885Sdim// Gets the path counter array 528218885SdimGlobalVariable* BLInstrumentationDag::getCounterArray() { 529218885Sdim return _counterArray; 530218885Sdim} 531218885Sdim 532218885Sdimvoid BLInstrumentationDag::setCounterArray(GlobalVariable* c) { 533218885Sdim _counterArray = c; 534218885Sdim} 535218885Sdim 536218885Sdim// Calculates the increment for the chords, thereby removing 537218885Sdim// instrumentation from the spanning tree edges. Implementation is based on 538218885Sdim// the algorithm in Figure 4 of [Ball94] 539218885Sdimvoid BLInstrumentationDag::calculateChordIncrements() { 540218885Sdim calculateChordIncrementsDfs(0, getRoot(), NULL); 541218885Sdim 542218885Sdim BLInstrumentationEdge* chord; 543218885Sdim for(BLEdgeIterator chordEdge = _chordEdges.begin(), 544218885Sdim end = _chordEdges.end(); chordEdge != end; chordEdge++) { 545218885Sdim chord = (BLInstrumentationEdge*) *chordEdge; 546218885Sdim chord->setIncrement(chord->getIncrement() + chord->getWeight()); 547218885Sdim } 548218885Sdim} 549218885Sdim 550218885Sdim// Updates the state when an edge has been split 551218885Sdimvoid BLInstrumentationDag::splitUpdate(BLInstrumentationEdge* formerEdge, 552218885Sdim BasicBlock* newBlock) { 553218885Sdim BallLarusNode* oldTarget = formerEdge->getTarget(); 554218885Sdim BallLarusNode* newNode = addNode(newBlock); 555218885Sdim formerEdge->setTarget(newNode); 556218885Sdim newNode->addPredEdge(formerEdge); 557218885Sdim 558218885Sdim DEBUG(dbgs() << " Edge split: " << *formerEdge << "\n"); 559218885Sdim 560218885Sdim oldTarget->removePredEdge(formerEdge); 561218885Sdim BallLarusEdge* newEdge = addEdge(newNode, oldTarget,0); 562218885Sdim 563218885Sdim if( formerEdge->getType() == BallLarusEdge::BACKEDGE || 564218885Sdim formerEdge->getType() == BallLarusEdge::SPLITEDGE) { 565218885Sdim newEdge->setType(formerEdge->getType()); 566218885Sdim newEdge->setPhonyRoot(formerEdge->getPhonyRoot()); 567218885Sdim newEdge->setPhonyExit(formerEdge->getPhonyExit()); 568218885Sdim formerEdge->setType(BallLarusEdge::NORMAL); 569218885Sdim formerEdge->setPhonyRoot(NULL); 570218885Sdim formerEdge->setPhonyExit(NULL); 571218885Sdim } 572218885Sdim} 573218885Sdim 574218885Sdim// Calculates a spanning tree of the DAG ignoring cycles. Whichever 575218885Sdim// edges are in the spanning tree will not be instrumented, but this 576218885Sdim// implementation does not try to minimize the instrumentation overhead 577218885Sdim// by trying to find hot edges. 578218885Sdimvoid BLInstrumentationDag::calculateSpanningTree() { 579218885Sdim std::stack<BallLarusNode*> dfsStack; 580218885Sdim 581218885Sdim for(BLNodeIterator nodeIt = _nodes.begin(), end = _nodes.end(); 582218885Sdim nodeIt != end; nodeIt++) { 583218885Sdim (*nodeIt)->setColor(BallLarusNode::WHITE); 584218885Sdim } 585218885Sdim 586218885Sdim dfsStack.push(getRoot()); 587218885Sdim while(dfsStack.size() > 0) { 588218885Sdim BallLarusNode* node = dfsStack.top(); 589218885Sdim dfsStack.pop(); 590218885Sdim 591218885Sdim if(node->getColor() == BallLarusNode::WHITE) 592218885Sdim continue; 593218885Sdim 594218885Sdim BallLarusNode* nextNode; 595218885Sdim bool forward = true; 596218885Sdim BLEdgeIterator succEnd = node->succEnd(); 597218885Sdim 598218885Sdim node->setColor(BallLarusNode::WHITE); 599218885Sdim // first iterate over successors then predecessors 600218885Sdim for(BLEdgeIterator edge = node->succBegin(), predEnd = node->predEnd(); 601218885Sdim edge != predEnd; edge++) { 602218885Sdim if(edge == succEnd) { 603218885Sdim edge = node->predBegin(); 604218885Sdim forward = false; 605218885Sdim } 606218885Sdim 607218885Sdim // Ignore split edges 608218885Sdim if ((*edge)->getType() == BallLarusEdge::SPLITEDGE) 609218885Sdim continue; 610218885Sdim 611218885Sdim nextNode = forward? (*edge)->getTarget(): (*edge)->getSource(); 612218885Sdim if(nextNode->getColor() != BallLarusNode::WHITE) { 613218885Sdim nextNode->setColor(BallLarusNode::WHITE); 614218885Sdim makeEdgeSpanning((BLInstrumentationEdge*)(*edge)); 615218885Sdim } 616218885Sdim } 617218885Sdim } 618218885Sdim 619218885Sdim for(BLEdgeIterator edge = _edges.begin(), end = _edges.end(); 620218885Sdim edge != end; edge++) { 621218885Sdim BLInstrumentationEdge* instEdge = (BLInstrumentationEdge*) (*edge); 622218885Sdim // safe since createEdge is overriden 623218885Sdim if(!instEdge->isInSpanningTree() && (*edge)->getType() 624218885Sdim != BallLarusEdge::SPLITEDGE) 625218885Sdim _chordEdges.push_back(instEdge); 626218885Sdim } 627218885Sdim} 628218885Sdim 629218885Sdim// Pushes initialization further down in order to group the first 630218885Sdim// increment and initialization. 631218885Sdimvoid BLInstrumentationDag::pushInitialization() { 632218885Sdim BLInstrumentationEdge* exitRootEdge = 633218885Sdim (BLInstrumentationEdge*) getExitRootEdge(); 634218885Sdim exitRootEdge->setIsInitialization(true); 635218885Sdim pushInitializationFromEdge(exitRootEdge); 636218885Sdim} 637218885Sdim 638218885Sdim// Pushes the path counter increments up in order to group the last path 639218885Sdim// number increment. 640218885Sdimvoid BLInstrumentationDag::pushCounters() { 641218885Sdim BLInstrumentationEdge* exitRootEdge = 642218885Sdim (BLInstrumentationEdge*) getExitRootEdge(); 643218885Sdim exitRootEdge->setIsCounterIncrement(true); 644218885Sdim pushCountersFromEdge(exitRootEdge); 645218885Sdim} 646218885Sdim 647218885Sdim// Removes phony edges from the successor list of the source, and the 648218885Sdim// predecessor list of the target. 649218885Sdimvoid BLInstrumentationDag::unlinkPhony() { 650218885Sdim BallLarusEdge* edge; 651218885Sdim 652218885Sdim for(BLEdgeIterator next = _edges.begin(), 653218885Sdim end = _edges.end(); next != end; next++) { 654218885Sdim edge = (*next); 655218885Sdim 656218885Sdim if( edge->getType() == BallLarusEdge::BACKEDGE_PHONY || 657218885Sdim edge->getType() == BallLarusEdge::SPLITEDGE_PHONY || 658218885Sdim edge->getType() == BallLarusEdge::CALLEDGE_PHONY ) { 659218885Sdim unlinkEdge(edge); 660218885Sdim } 661218885Sdim } 662218885Sdim} 663218885Sdim 664218885Sdim// Generate a .dot graph to represent the DAG and pathNumbers 665218885Sdimvoid BLInstrumentationDag::generateDotGraph() { 666218885Sdim std::string errorInfo; 667234353Sdim std::string functionName = getFunction().getName().str(); 668218885Sdim std::string filename = "pathdag." + functionName + ".dot"; 669218885Sdim 670218885Sdim DEBUG (dbgs() << "Writing '" << filename << "'...\n"); 671218885Sdim raw_fd_ostream dotFile(filename.c_str(), errorInfo); 672218885Sdim 673218885Sdim if (!errorInfo.empty()) { 674218885Sdim errs() << "Error opening '" << filename.c_str() <<"' for writing!"; 675218885Sdim errs() << "\n"; 676218885Sdim return; 677218885Sdim } 678218885Sdim 679218885Sdim dotFile << "digraph " << functionName << " {\n"; 680218885Sdim 681218885Sdim for( BLEdgeIterator edge = _edges.begin(), end = _edges.end(); 682218885Sdim edge != end; edge++) { 683218885Sdim std::string sourceName = (*edge)->getSource()->getName(); 684218885Sdim std::string targetName = (*edge)->getTarget()->getName(); 685218885Sdim 686218885Sdim dotFile << "\t\"" << sourceName.c_str() << "\" -> \"" 687218885Sdim << targetName.c_str() << "\" "; 688218885Sdim 689218885Sdim long inc = ((BLInstrumentationEdge*)(*edge))->getIncrement(); 690218885Sdim 691218885Sdim switch( (*edge)->getType() ) { 692218885Sdim case BallLarusEdge::NORMAL: 693218885Sdim dotFile << "[label=" << inc << "] [color=black];\n"; 694218885Sdim break; 695218885Sdim 696218885Sdim case BallLarusEdge::BACKEDGE: 697218885Sdim dotFile << "[color=cyan];\n"; 698218885Sdim break; 699218885Sdim 700218885Sdim case BallLarusEdge::BACKEDGE_PHONY: 701218885Sdim dotFile << "[label=" << inc 702218885Sdim << "] [color=blue];\n"; 703218885Sdim break; 704218885Sdim 705218885Sdim case BallLarusEdge::SPLITEDGE: 706218885Sdim dotFile << "[color=violet];\n"; 707218885Sdim break; 708218885Sdim 709218885Sdim case BallLarusEdge::SPLITEDGE_PHONY: 710218885Sdim dotFile << "[label=" << inc << "] [color=red];\n"; 711218885Sdim break; 712218885Sdim 713218885Sdim case BallLarusEdge::CALLEDGE_PHONY: 714218885Sdim dotFile << "[label=" << inc << "] [color=green];\n"; 715218885Sdim break; 716218885Sdim } 717218885Sdim } 718218885Sdim 719218885Sdim dotFile << "}\n"; 720218885Sdim} 721218885Sdim 722218885Sdim// Allows subclasses to determine which type of Node is created. 723218885Sdim// Override this method to produce subclasses of BallLarusNode if 724218885Sdim// necessary. The destructor of BallLarusDag will call free on each pointer 725218885Sdim// created. 726218885SdimBallLarusNode* BLInstrumentationDag::createNode(BasicBlock* BB) { 727218885Sdim return( new BLInstrumentationNode(BB) ); 728218885Sdim} 729218885Sdim 730218885Sdim// Allows subclasses to determine which type of Edge is created. 731218885Sdim// Override this method to produce subclasses of BallLarusEdge if 732218885Sdim// necessary. The destructor of BallLarusDag will call free on each pointer 733218885Sdim// created. 734218885SdimBallLarusEdge* BLInstrumentationDag::createEdge(BallLarusNode* source, 735218885Sdim BallLarusNode* target, unsigned edgeNumber) { 736218885Sdim // One can cast from BallLarusNode to BLInstrumentationNode since createNode 737218885Sdim // is overriden to produce BLInstrumentationNode. 738218885Sdim return( new BLInstrumentationEdge((BLInstrumentationNode*)source, 739218885Sdim (BLInstrumentationNode*)target) ); 740218885Sdim} 741218885Sdim 742218885Sdim// Sets the Value corresponding to the pathNumber register, constant, 743218885Sdim// or phinode. Used by the instrumentation code to remember path 744218885Sdim// number Values. 745218885SdimValue* BLInstrumentationNode::getStartingPathNumber(){ 746218885Sdim return(_startingPathNumber); 747218885Sdim} 748218885Sdim 749218885Sdim// Sets the Value of the pathNumber. Used by the instrumentation code. 750218885Sdimvoid BLInstrumentationNode::setStartingPathNumber(Value* pathNumber) { 751218885Sdim DEBUG(dbgs() << " SPN-" << getName() << " <-- " << (pathNumber ? 752234353Sdim pathNumber->getName() : 753234353Sdim "unused") << "\n"); 754218885Sdim _startingPathNumber = pathNumber; 755218885Sdim} 756218885Sdim 757218885SdimValue* BLInstrumentationNode::getEndingPathNumber(){ 758218885Sdim return(_endingPathNumber); 759218885Sdim} 760218885Sdim 761218885Sdimvoid BLInstrumentationNode::setEndingPathNumber(Value* pathNumber) { 762218885Sdim DEBUG(dbgs() << " EPN-" << getName() << " <-- " 763234353Sdim << (pathNumber ? pathNumber->getName() : "unused") << "\n"); 764218885Sdim _endingPathNumber = pathNumber; 765218885Sdim} 766218885Sdim 767218885Sdim// Get the PHINode Instruction for this node. Used by instrumentation 768218885Sdim// code. 769218885SdimPHINode* BLInstrumentationNode::getPathPHI() { 770218885Sdim return(_pathPHI); 771218885Sdim} 772218885Sdim 773218885Sdim// Set the PHINode Instruction for this node. Used by instrumentation 774218885Sdim// code. 775218885Sdimvoid BLInstrumentationNode::setPathPHI(PHINode* pathPHI) { 776218885Sdim _pathPHI = pathPHI; 777218885Sdim} 778218885Sdim 779218885Sdim// Removes the edge from the appropriate predecessor and successor 780218885Sdim// lists. 781218885Sdimvoid BLInstrumentationDag::unlinkEdge(BallLarusEdge* edge) { 782218885Sdim if(edge == getExitRootEdge()) 783218885Sdim DEBUG(dbgs() << " Removing exit->root edge\n"); 784218885Sdim 785218885Sdim edge->getSource()->removeSuccEdge(edge); 786218885Sdim edge->getTarget()->removePredEdge(edge); 787218885Sdim} 788218885Sdim 789218885Sdim// Makes an edge part of the spanning tree. 790218885Sdimvoid BLInstrumentationDag::makeEdgeSpanning(BLInstrumentationEdge* edge) { 791218885Sdim edge->setIsInSpanningTree(true); 792218885Sdim _treeEdges.push_back(edge); 793218885Sdim} 794218885Sdim 795218885Sdim// Pushes initialization and calls itself recursively. 796218885Sdimvoid BLInstrumentationDag::pushInitializationFromEdge( 797218885Sdim BLInstrumentationEdge* edge) { 798218885Sdim BallLarusNode* target; 799218885Sdim 800218885Sdim target = edge->getTarget(); 801218885Sdim if( target->getNumberPredEdges() > 1 || target == getExit() ) { 802218885Sdim return; 803218885Sdim } else { 804218885Sdim for(BLEdgeIterator next = target->succBegin(), 805218885Sdim end = target->succEnd(); next != end; next++) { 806218885Sdim BLInstrumentationEdge* intoEdge = (BLInstrumentationEdge*) *next; 807218885Sdim 808218885Sdim // Skip split edges 809218885Sdim if (intoEdge->getType() == BallLarusEdge::SPLITEDGE) 810218885Sdim continue; 811218885Sdim 812218885Sdim intoEdge->setIncrement(intoEdge->getIncrement() + 813218885Sdim edge->getIncrement()); 814218885Sdim intoEdge->setIsInitialization(true); 815218885Sdim pushInitializationFromEdge(intoEdge); 816218885Sdim } 817218885Sdim 818218885Sdim edge->setIncrement(0); 819218885Sdim edge->setIsInitialization(false); 820218885Sdim } 821218885Sdim} 822218885Sdim 823218885Sdim// Pushes path counter increments up recursively. 824218885Sdimvoid BLInstrumentationDag::pushCountersFromEdge(BLInstrumentationEdge* edge) { 825218885Sdim BallLarusNode* source; 826218885Sdim 827218885Sdim source = edge->getSource(); 828218885Sdim if(source->getNumberSuccEdges() > 1 || source == getRoot() 829218885Sdim || edge->isInitialization()) { 830218885Sdim return; 831218885Sdim } else { 832218885Sdim for(BLEdgeIterator previous = source->predBegin(), 833218885Sdim end = source->predEnd(); previous != end; previous++) { 834218885Sdim BLInstrumentationEdge* fromEdge = (BLInstrumentationEdge*) *previous; 835218885Sdim 836218885Sdim // Skip split edges 837218885Sdim if (fromEdge->getType() == BallLarusEdge::SPLITEDGE) 838218885Sdim continue; 839218885Sdim 840218885Sdim fromEdge->setIncrement(fromEdge->getIncrement() + 841218885Sdim edge->getIncrement()); 842218885Sdim fromEdge->setIsCounterIncrement(true); 843218885Sdim pushCountersFromEdge(fromEdge); 844218885Sdim } 845218885Sdim 846218885Sdim edge->setIncrement(0); 847218885Sdim edge->setIsCounterIncrement(false); 848218885Sdim } 849218885Sdim} 850218885Sdim 851218885Sdim// Depth first algorithm for determining the chord increments. 852218885Sdimvoid BLInstrumentationDag::calculateChordIncrementsDfs(long weight, 853218885Sdim BallLarusNode* v, BallLarusEdge* e) { 854218885Sdim BLInstrumentationEdge* f; 855218885Sdim 856218885Sdim for(BLEdgeIterator treeEdge = _treeEdges.begin(), 857218885Sdim end = _treeEdges.end(); treeEdge != end; treeEdge++) { 858218885Sdim f = (BLInstrumentationEdge*) *treeEdge; 859218885Sdim if(e != f && v == f->getTarget()) { 860218885Sdim calculateChordIncrementsDfs( 861218885Sdim calculateChordIncrementsDir(e,f)*(weight) + 862218885Sdim f->getWeight(), f->getSource(), f); 863218885Sdim } 864218885Sdim if(e != f && v == f->getSource()) { 865218885Sdim calculateChordIncrementsDfs( 866218885Sdim calculateChordIncrementsDir(e,f)*(weight) + 867218885Sdim f->getWeight(), f->getTarget(), f); 868218885Sdim } 869218885Sdim } 870218885Sdim 871218885Sdim for(BLEdgeIterator chordEdge = _chordEdges.begin(), 872218885Sdim end = _chordEdges.end(); chordEdge != end; chordEdge++) { 873218885Sdim f = (BLInstrumentationEdge*) *chordEdge; 874218885Sdim if(v == f->getSource() || v == f->getTarget()) { 875218885Sdim f->setIncrement(f->getIncrement() + 876218885Sdim calculateChordIncrementsDir(e,f)*weight); 877218885Sdim } 878218885Sdim } 879218885Sdim} 880218885Sdim 881218885Sdim// Determines the relative direction of two edges. 882218885Sdimint BLInstrumentationDag::calculateChordIncrementsDir(BallLarusEdge* e, 883218885Sdim BallLarusEdge* f) { 884218885Sdim if( e == NULL) 885218885Sdim return(1); 886218885Sdim else if(e->getSource() == f->getTarget() 887218885Sdim || e->getTarget() == f->getSource()) 888218885Sdim return(1); 889218885Sdim 890218885Sdim return(-1); 891218885Sdim} 892218885Sdim 893218885Sdim// Creates an increment constant representing incr. 894218885SdimConstantInt* PathProfiler::createIncrementConstant(long incr, 895218885Sdim int bitsize) { 896218885Sdim return(ConstantInt::get(IntegerType::get(*Context, 32), incr)); 897218885Sdim} 898218885Sdim 899218885Sdim// Creates an increment constant representing the value in 900218885Sdim// edge->getIncrement(). 901218885SdimConstantInt* PathProfiler::createIncrementConstant( 902218885Sdim BLInstrumentationEdge* edge) { 903218885Sdim return(createIncrementConstant(edge->getIncrement(), 32)); 904218885Sdim} 905218885Sdim 906218885Sdim// Finds the insertion point after pathNumber in block. PathNumber may 907218885Sdim// be NULL. 908218885SdimBasicBlock::iterator PathProfiler::getInsertionPoint(BasicBlock* block, Value* 909218885Sdim pathNumber) { 910218885Sdim if(pathNumber == NULL || isa<ConstantInt>(pathNumber) 911218885Sdim || (((Instruction*)(pathNumber))->getParent()) != block) { 912226633Sdim return(block->getFirstInsertionPt()); 913218885Sdim } else { 914218885Sdim Instruction* pathNumberInst = (Instruction*) (pathNumber); 915218885Sdim BasicBlock::iterator insertPoint; 916218885Sdim BasicBlock::iterator end = block->end(); 917218885Sdim 918218885Sdim for(insertPoint = block->begin(); 919218885Sdim insertPoint != end; insertPoint++) { 920218885Sdim Instruction* insertInst = &(*insertPoint); 921218885Sdim 922218885Sdim if(insertInst == pathNumberInst) 923218885Sdim return(++insertPoint); 924218885Sdim } 925218885Sdim 926218885Sdim return(insertPoint); 927218885Sdim } 928218885Sdim} 929218885Sdim 930218885Sdim// A PHINode is created in the node, and its values initialized to -1U. 931218885Sdimvoid PathProfiler::preparePHI(BLInstrumentationNode* node) { 932218885Sdim BasicBlock* block = node->getBlock(); 933226633Sdim BasicBlock::iterator insertPoint = block->getFirstInsertionPt(); 934221345Sdim pred_iterator PB = pred_begin(node->getBlock()), 935221345Sdim PE = pred_end(node->getBlock()); 936221345Sdim PHINode* phi = PHINode::Create(Type::getInt32Ty(*Context), 937221345Sdim std::distance(PB, PE), "pathNumber", 938218885Sdim insertPoint ); 939218885Sdim node->setPathPHI(phi); 940218885Sdim node->setStartingPathNumber(phi); 941218885Sdim node->setEndingPathNumber(phi); 942218885Sdim 943221345Sdim for(pred_iterator predIt = PB; predIt != PE; predIt++) { 944218885Sdim BasicBlock* pred = (*predIt); 945218885Sdim 946218885Sdim if(pred != NULL) 947218885Sdim phi->addIncoming(createIncrementConstant((long)-1, 32), pred); 948218885Sdim } 949218885Sdim} 950218885Sdim 951218885Sdim// Inserts source's pathNumber Value* into target. Target may or may not 952218885Sdim// have multiple predecessors, and may or may not have its phiNode 953218885Sdim// initalized. 954218885Sdimvoid PathProfiler::pushValueIntoNode(BLInstrumentationNode* source, 955218885Sdim BLInstrumentationNode* target) { 956218885Sdim if(target->getBlock() == NULL) 957218885Sdim return; 958218885Sdim 959218885Sdim 960218885Sdim if(target->getNumberPredEdges() <= 1) { 961218885Sdim assert(target->getStartingPathNumber() == NULL && 962218885Sdim "Target already has path number"); 963218885Sdim target->setStartingPathNumber(source->getEndingPathNumber()); 964218885Sdim target->setEndingPathNumber(source->getEndingPathNumber()); 965218885Sdim DEBUG(dbgs() << " Passing path number" 966218885Sdim << (source->getEndingPathNumber() ? "" : " (null)") 967218885Sdim << " value through.\n"); 968218885Sdim } else { 969218885Sdim if(target->getPathPHI() == NULL) { 970218885Sdim DEBUG(dbgs() << " Initializing PHI node for block '" 971218885Sdim << target->getName() << "'\n"); 972218885Sdim preparePHI(target); 973218885Sdim } 974218885Sdim pushValueIntoPHI(target, source); 975218885Sdim DEBUG(dbgs() << " Passing number value into PHI for block '" 976218885Sdim << target->getName() << "'\n"); 977218885Sdim } 978218885Sdim} 979218885Sdim 980218885Sdim// Inserts source's pathNumber Value* into the appropriate slot of 981218885Sdim// target's phiNode. 982218885Sdimvoid PathProfiler::pushValueIntoPHI(BLInstrumentationNode* target, 983218885Sdim BLInstrumentationNode* source) { 984218885Sdim PHINode* phi = target->getPathPHI(); 985218885Sdim assert(phi != NULL && " Tried to push value into node with PHI, but node" 986218885Sdim " actually had no PHI."); 987218885Sdim phi->removeIncomingValue(source->getBlock(), false); 988218885Sdim phi->addIncoming(source->getEndingPathNumber(), source->getBlock()); 989218885Sdim} 990218885Sdim 991218885Sdim// The Value* in node, oldVal, is updated with a Value* correspodning to 992218885Sdim// oldVal + addition. 993218885Sdimvoid PathProfiler::insertNumberIncrement(BLInstrumentationNode* node, 994218885Sdim Value* addition, bool atBeginning) { 995218885Sdim BasicBlock* block = node->getBlock(); 996218885Sdim assert(node->getStartingPathNumber() != NULL); 997218885Sdim assert(node->getEndingPathNumber() != NULL); 998218885Sdim 999218885Sdim BasicBlock::iterator insertPoint; 1000218885Sdim 1001218885Sdim if( atBeginning ) 1002226633Sdim insertPoint = block->getFirstInsertionPt(); 1003218885Sdim else 1004218885Sdim insertPoint = block->getTerminator(); 1005218885Sdim 1006218885Sdim DEBUG(errs() << " Creating addition instruction.\n"); 1007218885Sdim Value* newpn = BinaryOperator::Create(Instruction::Add, 1008218885Sdim node->getStartingPathNumber(), 1009218885Sdim addition, "pathNumber", insertPoint); 1010218885Sdim 1011218885Sdim node->setEndingPathNumber(newpn); 1012218885Sdim 1013218885Sdim if( atBeginning ) 1014218885Sdim node->setStartingPathNumber(newpn); 1015218885Sdim} 1016218885Sdim 1017218885Sdim// Creates a counter increment in the given node. The Value* in node is 1018218885Sdim// taken as the index into an array or hash table. The hash table access 1019218885Sdim// is a call to the runtime. 1020218885Sdimvoid PathProfiler::insertCounterIncrement(Value* incValue, 1021218885Sdim BasicBlock::iterator insertPoint, 1022218885Sdim BLInstrumentationDag* dag, 1023218885Sdim bool increment) { 1024218885Sdim // Counter increment for array 1025218885Sdim if( dag->getNumberOfPaths() <= HASH_THRESHHOLD ) { 1026218885Sdim // Get pointer to the array location 1027218885Sdim std::vector<Value*> gepIndices(2); 1028218885Sdim gepIndices[0] = Constant::getNullValue(Type::getInt32Ty(*Context)); 1029218885Sdim gepIndices[1] = incValue; 1030218885Sdim 1031218885Sdim GetElementPtrInst* pcPointer = 1032226633Sdim GetElementPtrInst::Create(dag->getCounterArray(), gepIndices, 1033218885Sdim "counterInc", insertPoint); 1034218885Sdim 1035218885Sdim // Load from the array - call it oldPC 1036218885Sdim LoadInst* oldPc = new LoadInst(pcPointer, "oldPC", insertPoint); 1037218885Sdim 1038218885Sdim // Test to see whether adding 1 will overflow the counter 1039218885Sdim ICmpInst* isMax = new ICmpInst(insertPoint, CmpInst::ICMP_ULT, oldPc, 1040218885Sdim createIncrementConstant(0xffffffff, 32), 1041218885Sdim "isMax"); 1042218885Sdim 1043218885Sdim // Select increment for the path counter based on overflow 1044218885Sdim SelectInst* inc = 1045218885Sdim SelectInst::Create( isMax, createIncrementConstant(increment?1:-1,32), 1046218885Sdim createIncrementConstant(0,32), 1047218885Sdim "pathInc", insertPoint); 1048218885Sdim 1049218885Sdim // newPc = oldPc + inc 1050218885Sdim BinaryOperator* newPc = BinaryOperator::Create(Instruction::Add, 1051218885Sdim oldPc, inc, "newPC", 1052218885Sdim insertPoint); 1053218885Sdim 1054218885Sdim // Store back in to the array 1055218885Sdim new StoreInst(newPc, pcPointer, insertPoint); 1056218885Sdim } else { // Counter increment for hash 1057218885Sdim std::vector<Value*> args(2); 1058218885Sdim args[0] = ConstantInt::get(Type::getInt32Ty(*Context), 1059218885Sdim currentFunctionNumber); 1060218885Sdim args[1] = incValue; 1061218885Sdim 1062218885Sdim CallInst::Create( 1063218885Sdim increment ? llvmIncrementHashFunction : llvmDecrementHashFunction, 1064224145Sdim args, "", insertPoint); 1065218885Sdim } 1066218885Sdim} 1067218885Sdim 1068218885Sdim// Inserts instrumentation for the given edge 1069218885Sdim// 1070218885Sdim// Pre: The edge's source node has pathNumber set if edge is non zero 1071218885Sdim// path number increment. 1072218885Sdim// 1073218885Sdim// Post: Edge's target node has a pathNumber set to the path number Value 1074218885Sdim// corresponding to the value of the path register after edge's 1075218885Sdim// execution. 1076218885Sdim// 1077218885Sdim// FIXME: This should be reworked so it's not recursive. 1078218885Sdimvoid PathProfiler::insertInstrumentationStartingAt(BLInstrumentationEdge* edge, 1079218885Sdim BLInstrumentationDag* dag) { 1080218885Sdim // Mark the edge as instrumented 1081218885Sdim edge->setHasInstrumentation(true); 1082218885Sdim DEBUG(dbgs() << "\nInstrumenting edge: " << (*edge) << "\n"); 1083218885Sdim 1084218885Sdim // create a new node for this edge's instrumentation 1085218885Sdim splitCritical(edge, dag); 1086218885Sdim 1087218885Sdim BLInstrumentationNode* sourceNode = (BLInstrumentationNode*)edge->getSource(); 1088218885Sdim BLInstrumentationNode* targetNode = (BLInstrumentationNode*)edge->getTarget(); 1089218885Sdim BLInstrumentationNode* instrumentNode; 1090218885Sdim BLInstrumentationNode* nextSourceNode; 1091218885Sdim 1092218885Sdim bool atBeginning = false; 1093218885Sdim 1094218885Sdim // Source node has only 1 successor so any information can be simply 1095218885Sdim // inserted in to it without splitting 1096218885Sdim if( sourceNode->getBlock() && sourceNode->getNumberSuccEdges() <= 1) { 1097218885Sdim DEBUG(dbgs() << " Potential instructions to be placed in: " 1098218885Sdim << sourceNode->getName() << " (at end)\n"); 1099218885Sdim instrumentNode = sourceNode; 1100218885Sdim nextSourceNode = targetNode; // ... since we never made any new nodes 1101218885Sdim } 1102218885Sdim 1103218885Sdim // The target node only has one predecessor, so we can safely insert edge 1104218885Sdim // instrumentation into it. If there was splitting, it must have been 1105218885Sdim // successful. 1106218885Sdim else if( targetNode->getNumberPredEdges() == 1 ) { 1107218885Sdim DEBUG(dbgs() << " Potential instructions to be placed in: " 1108218885Sdim << targetNode->getName() << " (at beginning)\n"); 1109218885Sdim pushValueIntoNode(sourceNode, targetNode); 1110218885Sdim instrumentNode = targetNode; 1111218885Sdim nextSourceNode = NULL; // ... otherwise we'll just keep splitting 1112218885Sdim atBeginning = true; 1113218885Sdim } 1114218885Sdim 1115218885Sdim // Somehow, splitting must have failed. 1116218885Sdim else { 1117218885Sdim errs() << "Instrumenting could not split a critical edge.\n"; 1118218885Sdim DEBUG(dbgs() << " Couldn't split edge " << (*edge) << ".\n"); 1119218885Sdim return; 1120218885Sdim } 1121218885Sdim 1122218885Sdim // Insert instrumentation if this is a back or split edge 1123218885Sdim if( edge->getType() == BallLarusEdge::BACKEDGE || 1124218885Sdim edge->getType() == BallLarusEdge::SPLITEDGE ) { 1125218885Sdim BLInstrumentationEdge* top = 1126218885Sdim (BLInstrumentationEdge*) edge->getPhonyRoot(); 1127218885Sdim BLInstrumentationEdge* bottom = 1128218885Sdim (BLInstrumentationEdge*) edge->getPhonyExit(); 1129218885Sdim 1130218885Sdim assert( top->isInitialization() && " Top phony edge did not" 1131218885Sdim " contain a path number initialization."); 1132218885Sdim assert( bottom->isCounterIncrement() && " Bottom phony edge" 1133218885Sdim " did not contain a path counter increment."); 1134218885Sdim 1135218885Sdim // split edge has yet to be initialized 1136218885Sdim if( !instrumentNode->getEndingPathNumber() ) { 1137218885Sdim instrumentNode->setStartingPathNumber(createIncrementConstant(0,32)); 1138218885Sdim instrumentNode->setEndingPathNumber(createIncrementConstant(0,32)); 1139218885Sdim } 1140218885Sdim 1141218885Sdim BasicBlock::iterator insertPoint = atBeginning ? 1142226633Sdim instrumentNode->getBlock()->getFirstInsertionPt() : 1143218885Sdim instrumentNode->getBlock()->getTerminator(); 1144218885Sdim 1145218885Sdim // add information from the bottom edge, if it exists 1146218885Sdim if( bottom->getIncrement() ) { 1147218885Sdim Value* newpn = 1148218885Sdim BinaryOperator::Create(Instruction::Add, 1149218885Sdim instrumentNode->getStartingPathNumber(), 1150218885Sdim createIncrementConstant(bottom), 1151218885Sdim "pathNumber", insertPoint); 1152218885Sdim instrumentNode->setEndingPathNumber(newpn); 1153218885Sdim } 1154218885Sdim 1155218885Sdim insertCounterIncrement(instrumentNode->getEndingPathNumber(), 1156218885Sdim insertPoint, dag); 1157218885Sdim 1158218885Sdim if( atBeginning ) 1159218885Sdim instrumentNode->setStartingPathNumber(createIncrementConstant(top)); 1160218885Sdim 1161218885Sdim instrumentNode->setEndingPathNumber(createIncrementConstant(top)); 1162218885Sdim 1163218885Sdim // Check for path counter increments 1164218885Sdim if( top->isCounterIncrement() ) { 1165218885Sdim insertCounterIncrement(instrumentNode->getEndingPathNumber(), 1166218885Sdim instrumentNode->getBlock()->getTerminator(),dag); 1167218885Sdim instrumentNode->setEndingPathNumber(0); 1168218885Sdim } 1169218885Sdim } 1170218885Sdim 1171218885Sdim // Insert instrumentation if this is a normal edge 1172218885Sdim else { 1173218885Sdim BasicBlock::iterator insertPoint = atBeginning ? 1174226633Sdim instrumentNode->getBlock()->getFirstInsertionPt() : 1175218885Sdim instrumentNode->getBlock()->getTerminator(); 1176218885Sdim 1177218885Sdim if( edge->isInitialization() ) { // initialize path number 1178218885Sdim instrumentNode->setEndingPathNumber(createIncrementConstant(edge)); 1179218885Sdim } else if( edge->getIncrement() ) {// increment path number 1180218885Sdim Value* newpn = 1181218885Sdim BinaryOperator::Create(Instruction::Add, 1182218885Sdim instrumentNode->getStartingPathNumber(), 1183218885Sdim createIncrementConstant(edge), 1184218885Sdim "pathNumber", insertPoint); 1185218885Sdim instrumentNode->setEndingPathNumber(newpn); 1186218885Sdim 1187218885Sdim if( atBeginning ) 1188218885Sdim instrumentNode->setStartingPathNumber(newpn); 1189218885Sdim } 1190218885Sdim 1191218885Sdim // Check for path counter increments 1192218885Sdim if( edge->isCounterIncrement() ) { 1193218885Sdim insertCounterIncrement(instrumentNode->getEndingPathNumber(), 1194218885Sdim insertPoint, dag); 1195218885Sdim instrumentNode->setEndingPathNumber(0); 1196218885Sdim } 1197218885Sdim } 1198218885Sdim 1199218885Sdim // Push it along 1200218885Sdim if (nextSourceNode && instrumentNode->getEndingPathNumber()) 1201218885Sdim pushValueIntoNode(instrumentNode, nextSourceNode); 1202218885Sdim 1203218885Sdim // Add all the successors 1204218885Sdim for( BLEdgeIterator next = targetNode->succBegin(), 1205218885Sdim end = targetNode->succEnd(); next != end; next++ ) { 1206218885Sdim // So long as it is un-instrumented, add it to the list 1207218885Sdim if( !((BLInstrumentationEdge*)(*next))->hasInstrumentation() ) 1208218885Sdim insertInstrumentationStartingAt((BLInstrumentationEdge*)*next,dag); 1209218885Sdim else 1210218885Sdim DEBUG(dbgs() << " Edge " << *(BLInstrumentationEdge*)(*next) 1211218885Sdim << " already instrumented.\n"); 1212218885Sdim } 1213218885Sdim} 1214218885Sdim 1215218885Sdim// Inserts instrumentation according to the marked edges in dag. Phony edges 1216218885Sdim// must be unlinked from the DAG, but accessible from the backedges. Dag 1217218885Sdim// must have initializations, path number increments, and counter increments 1218218885Sdim// present. 1219218885Sdim// 1220218885Sdim// Counter storage is created here. 1221218885Sdimvoid PathProfiler::insertInstrumentation( 1222218885Sdim BLInstrumentationDag& dag, Module &M) { 1223218885Sdim 1224218885Sdim BLInstrumentationEdge* exitRootEdge = 1225218885Sdim (BLInstrumentationEdge*) dag.getExitRootEdge(); 1226218885Sdim insertInstrumentationStartingAt(exitRootEdge, &dag); 1227218885Sdim 1228218885Sdim // Iterate through each call edge and apply the appropriate hash increment 1229218885Sdim // and decrement functions 1230218885Sdim BLEdgeVector callEdges = dag.getCallPhonyEdges(); 1231218885Sdim for( BLEdgeIterator edge = callEdges.begin(), 1232218885Sdim end = callEdges.end(); edge != end; edge++ ) { 1233218885Sdim BLInstrumentationNode* node = 1234218885Sdim (BLInstrumentationNode*)(*edge)->getSource(); 1235226633Sdim BasicBlock::iterator insertPoint = node->getBlock()->getFirstInsertionPt(); 1236218885Sdim 1237218885Sdim // Find the first function call 1238218885Sdim while( ((Instruction&)(*insertPoint)).getOpcode() != Instruction::Call ) 1239218885Sdim insertPoint++; 1240218885Sdim 1241218885Sdim DEBUG(dbgs() << "\nInstrumenting method call block '" 1242234353Sdim << node->getBlock()->getName() << "'\n"); 1243218885Sdim DEBUG(dbgs() << " Path number initialized: " 1244234353Sdim << ((node->getStartingPathNumber()) ? "yes" : "no") << "\n"); 1245218885Sdim 1246218885Sdim Value* newpn; 1247218885Sdim if( node->getStartingPathNumber() ) { 1248218885Sdim long inc = ((BLInstrumentationEdge*)(*edge))->getIncrement(); 1249218885Sdim if ( inc ) 1250218885Sdim newpn = BinaryOperator::Create(Instruction::Add, 1251218885Sdim node->getStartingPathNumber(), 1252218885Sdim createIncrementConstant(inc,32), 1253218885Sdim "pathNumber", insertPoint); 1254218885Sdim else 1255218885Sdim newpn = node->getStartingPathNumber(); 1256218885Sdim } else { 1257218885Sdim newpn = (Value*)createIncrementConstant( 1258218885Sdim ((BLInstrumentationEdge*)(*edge))->getIncrement(), 32); 1259218885Sdim } 1260218885Sdim 1261218885Sdim insertCounterIncrement(newpn, insertPoint, &dag); 1262218885Sdim insertCounterIncrement(newpn, node->getBlock()->getTerminator(), 1263218885Sdim &dag, false); 1264218885Sdim } 1265218885Sdim} 1266218885Sdim 1267218885Sdim// Entry point of the module 1268218885Sdimvoid PathProfiler::runOnFunction(std::vector<Constant*> &ftInit, 1269218885Sdim Function &F, Module &M) { 1270218885Sdim // Build DAG from CFG 1271218885Sdim BLInstrumentationDag dag = BLInstrumentationDag(F); 1272218885Sdim dag.init(); 1273218885Sdim 1274218885Sdim // give each path a unique integer value 1275218885Sdim dag.calculatePathNumbers(); 1276218885Sdim 1277218885Sdim // modify path increments to increase the efficiency 1278218885Sdim // of instrumentation 1279218885Sdim dag.calculateSpanningTree(); 1280218885Sdim dag.calculateChordIncrements(); 1281218885Sdim dag.pushInitialization(); 1282218885Sdim dag.pushCounters(); 1283218885Sdim dag.unlinkPhony(); 1284218885Sdim 1285218885Sdim // potentially generate .dot graph for the dag 1286218885Sdim if (DotPathDag) 1287218885Sdim dag.generateDotGraph (); 1288218885Sdim 1289218885Sdim // Should we store the information in an array or hash 1290218885Sdim if( dag.getNumberOfPaths() <= HASH_THRESHHOLD ) { 1291226633Sdim Type* t = ArrayType::get(Type::getInt32Ty(*Context), 1292218885Sdim dag.getNumberOfPaths()); 1293218885Sdim 1294218885Sdim dag.setCounterArray(new GlobalVariable(M, t, false, 1295218885Sdim GlobalValue::InternalLinkage, 1296218885Sdim Constant::getNullValue(t), "")); 1297218885Sdim } 1298218885Sdim 1299218885Sdim insertInstrumentation(dag, M); 1300218885Sdim 1301218885Sdim // Add to global function reference table 1302218885Sdim unsigned type; 1303226633Sdim Type* voidPtr = TypeBuilder<types::i<8>*, true>::get(*Context); 1304218885Sdim 1305218885Sdim if( dag.getNumberOfPaths() <= HASH_THRESHHOLD ) 1306218885Sdim type = ProfilingArray; 1307218885Sdim else 1308218885Sdim type = ProfilingHash; 1309218885Sdim 1310218885Sdim std::vector<Constant*> entryArray(3); 1311218885Sdim entryArray[0] = createIncrementConstant(type,32); 1312218885Sdim entryArray[1] = createIncrementConstant(dag.getNumberOfPaths(),32); 1313218885Sdim entryArray[2] = dag.getCounterArray() ? 1314218885Sdim ConstantExpr::getBitCast(dag.getCounterArray(), voidPtr) : 1315218885Sdim Constant::getNullValue(voidPtr); 1316218885Sdim 1317226633Sdim StructType* at = ftEntryTypeBuilder::get(*Context); 1318218885Sdim ConstantStruct* functionEntry = 1319218885Sdim (ConstantStruct*)ConstantStruct::get(at, entryArray); 1320218885Sdim ftInit.push_back(functionEntry); 1321218885Sdim} 1322218885Sdim 1323218885Sdim// Output the bitcode if we want to observe instrumentation changess 1324218885Sdim#define PRINT_MODULE dbgs() << \ 1325218885Sdim "\n\n============= MODULE BEGIN ===============\n" << M << \ 1326218885Sdim "\n============== MODULE END ================\n" 1327218885Sdim 1328218885Sdimbool PathProfiler::runOnModule(Module &M) { 1329218885Sdim Context = &M.getContext(); 1330218885Sdim 1331218885Sdim DEBUG(dbgs() 1332218885Sdim << "****************************************\n" 1333218885Sdim << "****************************************\n" 1334218885Sdim << "** **\n" 1335218885Sdim << "** PATH PROFILING INSTRUMENTATION **\n" 1336218885Sdim << "** **\n" 1337218885Sdim << "****************************************\n" 1338218885Sdim << "****************************************\n"); 1339218885Sdim 1340218885Sdim // No main, no instrumentation! 1341218885Sdim Function *Main = M.getFunction("main"); 1342218885Sdim 1343218885Sdim // Using fortran? ... this kind of works 1344218885Sdim if (!Main) 1345218885Sdim Main = M.getFunction("MAIN__"); 1346218885Sdim 1347218885Sdim if (!Main) { 1348218885Sdim errs() << "WARNING: cannot insert path profiling into a module" 1349218885Sdim << " with no main function!\n"; 1350218885Sdim return false; 1351218885Sdim } 1352218885Sdim 1353218885Sdim llvmIncrementHashFunction = M.getOrInsertFunction( 1354218885Sdim "llvm_increment_path_count", 1355218885Sdim Type::getVoidTy(*Context), // return type 1356218885Sdim Type::getInt32Ty(*Context), // function number 1357218885Sdim Type::getInt32Ty(*Context), // path number 1358218885Sdim NULL ); 1359218885Sdim 1360218885Sdim llvmDecrementHashFunction = M.getOrInsertFunction( 1361218885Sdim "llvm_decrement_path_count", 1362218885Sdim Type::getVoidTy(*Context), // return type 1363218885Sdim Type::getInt32Ty(*Context), // function number 1364218885Sdim Type::getInt32Ty(*Context), // path number 1365218885Sdim NULL ); 1366218885Sdim 1367218885Sdim std::vector<Constant*> ftInit; 1368218885Sdim unsigned functionNumber = 0; 1369218885Sdim for (Module::iterator F = M.begin(), E = M.end(); F != E; F++) { 1370218885Sdim if (F->isDeclaration()) 1371218885Sdim continue; 1372218885Sdim 1373234353Sdim DEBUG(dbgs() << "Function: " << F->getName() << "\n"); 1374218885Sdim functionNumber++; 1375218885Sdim 1376218885Sdim // set function number 1377218885Sdim currentFunctionNumber = functionNumber; 1378218885Sdim runOnFunction(ftInit, *F, M); 1379218885Sdim } 1380218885Sdim 1381226633Sdim Type *t = ftEntryTypeBuilder::get(*Context); 1382226633Sdim ArrayType* ftArrayType = ArrayType::get(t, ftInit.size()); 1383218885Sdim Constant* ftInitConstant = ConstantArray::get(ftArrayType, ftInit); 1384218885Sdim 1385218885Sdim DEBUG(dbgs() << " ftArrayType:" << *ftArrayType << "\n"); 1386218885Sdim 1387218885Sdim GlobalVariable* functionTable = 1388218885Sdim new GlobalVariable(M, ftArrayType, false, GlobalValue::InternalLinkage, 1389218885Sdim ftInitConstant, "functionPathTable"); 1390226633Sdim Type *eltType = ftArrayType->getTypeAtIndex((unsigned)0); 1391218885Sdim InsertProfilingInitCall(Main, "llvm_start_path_profiling", functionTable, 1392218885Sdim PointerType::getUnqual(eltType)); 1393218885Sdim 1394218885Sdim DEBUG(PRINT_MODULE); 1395218885Sdim 1396218885Sdim return true; 1397218885Sdim} 1398218885Sdim 1399218885Sdim// If this edge is a critical edge, then inserts a node at this edge. 1400218885Sdim// This edge becomes the first edge, and a new BallLarusEdge is created. 1401218885Sdim// Returns true if the edge was split 1402218885Sdimbool PathProfiler::splitCritical(BLInstrumentationEdge* edge, 1403218885Sdim BLInstrumentationDag* dag) { 1404218885Sdim unsigned succNum = edge->getSuccessorNumber(); 1405218885Sdim BallLarusNode* sourceNode = edge->getSource(); 1406218885Sdim BallLarusNode* targetNode = edge->getTarget(); 1407218885Sdim BasicBlock* sourceBlock = sourceNode->getBlock(); 1408218885Sdim BasicBlock* targetBlock = targetNode->getBlock(); 1409218885Sdim 1410218885Sdim if(sourceBlock == NULL || targetBlock == NULL 1411218885Sdim || sourceNode->getNumberSuccEdges() <= 1 1412218885Sdim || targetNode->getNumberPredEdges() == 1 ) { 1413218885Sdim return(false); 1414218885Sdim } 1415218885Sdim 1416218885Sdim TerminatorInst* terminator = sourceBlock->getTerminator(); 1417218885Sdim 1418218885Sdim if( SplitCriticalEdge(terminator, succNum, this, false)) { 1419218885Sdim BasicBlock* newBlock = terminator->getSuccessor(succNum); 1420218885Sdim dag->splitUpdate(edge, newBlock); 1421218885Sdim return(true); 1422218885Sdim } else 1423218885Sdim return(false); 1424218885Sdim} 1425