1 //===- PathProfiling.cpp - Inserts counters for path profiling ------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass instruments functions for Ball-Larus path profiling. Ball-Larus
11 // profiling converts the CFG into a DAG by replacing backedges with edges
12 // from entry to the start block and from the end block to exit. The paths
13 // along the new DAG are enumrated, i.e. each path is given a path number.
14 // Edges are instrumented to increment the path number register, such that the
15 // path number register will equal the path number of the path taken at the
18 // This file defines classes for building a CFG for use with different stages
19 // in the Ball-Larus path profiling instrumentation [Ball96]. The
20 // requirements are formatting the llvm CFG into the Ball-Larus DAG, path
21 // numbering, finding a spanning tree, moving increments from the spanning
25 // DAG - Directed Acyclic Graph.
26 // Ball-Larus DAG - A CFG with an entry node, an exit node, and backedges
27 // removed in the following manner. For every backedge
28 // v->w, insert edge ENTRY->w and edge v->EXIT.
29 // Path Number - The number corresponding to a specific path through a
31 // Spanning Tree - A subgraph, S, is a spanning tree if S covers all
32 // vertices and is a tree.
33 // Chord - An edge not in the spanning tree.
36 // T. Ball and J. R. Larus. "Efficient Path Profiling."
37 // International Symposium on Microarchitecture, pages 46-57, 1996.
38 // http://portal.acm.org/citation.cfm?id=243857
41 // Thomas Ball. "Efficiently Counting Program Events with Support for
43 // ACM Transactions on Programmmg Languages and Systems, Vol 16, No 5,
44 // September 1994, Pages 1399-1410.
45 //===----------------------------------------------------------------------===//
46 #define DEBUG_TYPE "insert-path-profiling"
48 #include "llvm/DerivedTypes.h"
49 #include "ProfilingUtils.h"
50 #include "llvm/Analysis/PathNumbering.h"
51 #include "llvm/Constants.h"
52 #include "llvm/DerivedTypes.h"
53 #include "llvm/InstrTypes.h"
54 #include "llvm/Instructions.h"
55 #include "llvm/LLVMContext.h"
56 #include "llvm/Module.h"
57 #include "llvm/Pass.h"
58 #include "llvm/TypeBuilder.h"
59 #include "llvm/Support/Compiler.h"
60 #include "llvm/Support/CFG.h"
61 #include "llvm/Support/CommandLine.h"
62 #include "llvm/Support/Debug.h"
63 #include "llvm/Support/raw_ostream.h"
64 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
65 #include "llvm/Transforms/Instrumentation.h"
68 #define HASH_THRESHHOLD 100000
73 class BLInstrumentationNode;
74 class BLInstrumentationEdge;
75 class BLInstrumentationDag;
77 // ---------------------------------------------------------------------------
78 // BLInstrumentationNode extends BallLarusNode with member used by the
79 // instrumentation algortihms.
80 // ---------------------------------------------------------------------------
81 class BLInstrumentationNode : public BallLarusNode {
83 // Creates a new BLInstrumentationNode from a BasicBlock.
84 BLInstrumentationNode(BasicBlock* BB);
86 // Get/sets the Value corresponding to the pathNumber register,
87 // constant or phinode. Used by the instrumentation code to remember
88 // path number Values.
89 Value* getStartingPathNumber();
90 void setStartingPathNumber(Value* pathNumber);
92 Value* getEndingPathNumber();
93 void setEndingPathNumber(Value* pathNumber);
95 // Get/set the PHINode Instruction for this node.
96 PHINode* getPathPHI();
97 void setPathPHI(PHINode* pathPHI);
101 Value* _startingPathNumber; // The Value for the current pathNumber.
102 Value* _endingPathNumber; // The Value for the current pathNumber.
103 PHINode* _pathPHI; // The PHINode for current pathNumber.
106 // --------------------------------------------------------------------------
107 // BLInstrumentationEdge extends BallLarusEdge with data about the
108 // instrumentation that will end up on each edge.
109 // --------------------------------------------------------------------------
110 class BLInstrumentationEdge : public BallLarusEdge {
112 BLInstrumentationEdge(BLInstrumentationNode* source,
113 BLInstrumentationNode* target);
115 // Sets the target node of this edge. Required to split edges.
116 void setTarget(BallLarusNode* node);
118 // Get/set whether edge is in the spanning tree.
119 bool isInSpanningTree() const;
120 void setIsInSpanningTree(bool isInSpanningTree);
122 // Get/ set whether this edge will be instrumented with a path number
124 bool isInitialization() const;
125 void setIsInitialization(bool isInitialization);
127 // Get/set whether this edge will be instrumented with a path counter
128 // increment. Notice this is incrementing the path counter
129 // corresponding to the path number register. The path number
130 // increment is determined by getIncrement().
131 bool isCounterIncrement() const;
132 void setIsCounterIncrement(bool isCounterIncrement);
134 // Get/set the path number increment that this edge will be instrumented
135 // with. This is distinct from the path counter increment and the
136 // weight. The counter increment counts the number of executions of
137 // some path, whereas the path number keeps track of which path number
138 // the program is on.
139 long getIncrement() const;
140 void setIncrement(long increment);
142 // Get/set whether the edge has been instrumented.
143 bool hasInstrumentation();
144 void setHasInstrumentation(bool hasInstrumentation);
146 // Returns the successor number of this edge in the source.
147 unsigned getSuccessorNumber();
150 // The increment that the code will be instrumented with.
151 long long _increment;
153 // Whether this edge is in the spanning tree.
154 bool _isInSpanningTree;
156 // Whether this edge is an initialiation of the path number.
157 bool _isInitialization;
159 // Whether this edge is a path counter increment.
160 bool _isCounterIncrement;
162 // Whether this edge has been instrumented.
163 bool _hasInstrumentation;
166 // ---------------------------------------------------------------------------
167 // BLInstrumentationDag extends BallLarusDag with algorithms that
168 // determine where instrumentation should be placed.
169 // ---------------------------------------------------------------------------
170 class BLInstrumentationDag : public BallLarusDag {
172 BLInstrumentationDag(Function &F);
174 // Returns the Exit->Root edge. This edge is required for creating
175 // directed cycles in the algorithm for moving instrumentation off of
177 BallLarusEdge* getExitRootEdge();
179 // Returns an array of phony edges which mark those nodes
180 // with function calls
181 BLEdgeVector getCallPhonyEdges();
183 // Gets/sets the path counter array
184 GlobalVariable* getCounterArray();
185 void setCounterArray(GlobalVariable* c);
187 // Calculates the increments for the chords, thereby removing
188 // instrumentation from the spanning tree edges. Implementation is based
189 // on the algorithm in Figure 4 of [Ball94]
190 void calculateChordIncrements();
192 // Updates the state when an edge has been split
193 void splitUpdate(BLInstrumentationEdge* formerEdge, BasicBlock* newBlock);
195 // Calculates a spanning tree of the DAG ignoring cycles. Whichever
196 // edges are in the spanning tree will not be instrumented, but this
197 // implementation does not try to minimize the instrumentation overhead
198 // by trying to find hot edges.
199 void calculateSpanningTree();
201 // Pushes initialization further down in order to group the first
202 // increment and initialization.
203 void pushInitialization();
205 // Pushes the path counter increments up in order to group the last path
209 // Removes phony edges from the successor list of the source, and the
210 // predecessor list of the target.
213 // Generate dot graph for the function
214 void generateDotGraph();
217 // BLInstrumentationDag creates BLInstrumentationNode objects in this
218 // method overriding the creation of BallLarusNode objects.
220 // Allows subclasses to determine which type of Node is created.
221 // Override this method to produce subclasses of BallLarusNode if
223 virtual BallLarusNode* createNode(BasicBlock* BB);
225 // BLInstrumentationDag create BLInstrumentationEdges.
227 // Allows subclasses to determine which type of Edge is created.
228 // Override this method to produce subclasses of BallLarusEdge if
229 // necessary. Parameters source and target will have been created by
230 // createNode and can be cast to the subclass of BallLarusNode*
231 // returned by createNode.
232 virtual BallLarusEdge* createEdge(
233 BallLarusNode* source, BallLarusNode* target, unsigned edgeNumber);
236 BLEdgeVector _treeEdges; // All edges in the spanning tree.
237 BLEdgeVector _chordEdges; // All edges not in the spanning tree.
238 GlobalVariable* _counterArray; // Array to store path counters
240 // Removes the edge from the appropriate predecessor and successor lists.
241 void unlinkEdge(BallLarusEdge* edge);
243 // Makes an edge part of the spanning tree.
244 void makeEdgeSpanning(BLInstrumentationEdge* edge);
246 // Pushes initialization and calls itself recursively.
247 void pushInitializationFromEdge(BLInstrumentationEdge* edge);
249 // Pushes path counter increments up recursively.
250 void pushCountersFromEdge(BLInstrumentationEdge* edge);
252 // Depth first algorithm for determining the chord increments.f
253 void calculateChordIncrementsDfs(
254 long weight, BallLarusNode* v, BallLarusEdge* e);
256 // Determines the relative direction of two edges.
257 int calculateChordIncrementsDir(BallLarusEdge* e, BallLarusEdge* f);
260 // ---------------------------------------------------------------------------
261 // PathProfiler is a module pass which instruments path profiling instructions
262 // ---------------------------------------------------------------------------
263 class PathProfiler : public ModulePass {
265 // Current context for multi threading support.
266 LLVMContext* Context;
268 // Which function are we currently instrumenting
269 unsigned currentFunctionNumber;
271 // The function prototype in the profiling runtime for incrementing a
272 // single path counter in a hash table.
273 Constant* llvmIncrementHashFunction;
274 Constant* llvmDecrementHashFunction;
276 // Instruments each function with path profiling. 'main' is instrumented
277 // with code to save the profile to disk.
278 bool runOnModule(Module &M);
280 // Analyzes the function for Ball-Larus path profiling, and inserts code.
281 void runOnFunction(std::vector<Constant*> &ftInit, Function &F, Module &M);
283 // Creates an increment constant representing incr.
284 ConstantInt* createIncrementConstant(long incr, int bitsize);
286 // Creates an increment constant representing the value in
287 // edge->getIncrement().
288 ConstantInt* createIncrementConstant(BLInstrumentationEdge* edge);
290 // Finds the insertion point after pathNumber in block. PathNumber may
292 BasicBlock::iterator getInsertionPoint(
293 BasicBlock* block, Value* pathNumber);
295 // Inserts source's pathNumber Value* into target. Target may or may not
296 // have multiple predecessors, and may or may not have its phiNode
298 void pushValueIntoNode(
299 BLInstrumentationNode* source, BLInstrumentationNode* target);
301 // Inserts source's pathNumber Value* into the appropriate slot of
303 void pushValueIntoPHI(
304 BLInstrumentationNode* target, BLInstrumentationNode* source);
306 // The Value* in node, oldVal, is updated with a Value* correspodning to
307 // oldVal + addition.
308 void insertNumberIncrement(BLInstrumentationNode* node, Value* addition,
311 // Creates a counter increment in the given node. The Value* in node is
312 // taken as the index into a hash table.
313 void insertCounterIncrement(
315 BasicBlock::iterator insertPoint,
316 BLInstrumentationDag* dag,
317 bool increment = true);
319 // A PHINode is created in the node, and its values initialized to -1U.
320 void preparePHI(BLInstrumentationNode* node);
322 // Inserts instrumentation for the given edge
324 // Pre: The edge's source node has pathNumber set if edge is non zero
325 // path number increment.
327 // Post: Edge's target node has a pathNumber set to the path number Value
328 // corresponding to the value of the path register after edge's
330 void insertInstrumentationStartingAt(
331 BLInstrumentationEdge* edge,
332 BLInstrumentationDag* dag);
334 // If this edge is a critical edge, then inserts a node at this edge.
335 // This edge becomes the first edge, and a new BallLarusEdge is created.
336 bool splitCritical(BLInstrumentationEdge* edge, BLInstrumentationDag* dag);
338 // Inserts instrumentation according to the marked edges in dag. Phony
339 // edges must be unlinked from the DAG, but accessible from the
340 // backedges. Dag must have initializations, path number increments, and
341 // counter increments present.
343 // Counter storage is created here.
344 void insertInstrumentation( BLInstrumentationDag& dag, Module &M);
347 static char ID; // Pass identification, replacement for typeid
348 PathProfiler() : ModulePass(ID) {
349 initializePathProfilerPass(*PassRegistry::getPassRegistry());
352 virtual const char *getPassName() const {
353 return "Path Profiler";
356 } // end anonymous namespace
358 // Should we print the dot-graphs
359 static cl::opt<bool> DotPathDag("path-profile-pathdag", cl::Hidden,
360 cl::desc("Output the path profiling DAG for each function."));
362 // Register the path profiler as a pass
363 char PathProfiler::ID = 0;
364 INITIALIZE_PASS(PathProfiler, "insert-path-profiling",
365 "Insert instrumentation for Ball-Larus path profiling",
368 ModulePass *llvm::createPathProfilerPass() { return new PathProfiler(); }
371 class PathProfilingFunctionTable {};
373 // Type for global array storing references to hashes or arrays
374 template<bool xcompile> class TypeBuilder<PathProfilingFunctionTable,
377 static StructType *get(LLVMContext& C) {
378 return( StructType::get(
379 TypeBuilder<types::i<32>, xcompile>::get(C), // type
380 TypeBuilder<types::i<32>, xcompile>::get(C), // array size
381 TypeBuilder<types::i<8>*, xcompile>::get(C), // array/hash ptr
386 typedef TypeBuilder<PathProfilingFunctionTable, true>
389 // BallLarusEdge << operator overloading
390 raw_ostream& operator<<(raw_ostream& os,
391 const BLInstrumentationEdge& edge)
393 raw_ostream& operator<<(raw_ostream& os,
394 const BLInstrumentationEdge& edge) {
395 os << "[" << edge.getSource()->getName() << " -> "
396 << edge.getTarget()->getName() << "] init: "
397 << (edge.isInitialization() ? "yes" : "no")
398 << " incr:" << edge.getIncrement() << " cinc: "
399 << (edge.isCounterIncrement() ? "yes" : "no");
404 // Creates a new BLInstrumentationNode from a BasicBlock.
405 BLInstrumentationNode::BLInstrumentationNode(BasicBlock* BB) :
407 _startingPathNumber(NULL), _endingPathNumber(NULL), _pathPHI(NULL) {}
409 // Constructor for BLInstrumentationEdge.
410 BLInstrumentationEdge::BLInstrumentationEdge(BLInstrumentationNode* source,
411 BLInstrumentationNode* target)
412 : BallLarusEdge(source, target, 0),
413 _increment(0), _isInSpanningTree(false), _isInitialization(false),
414 _isCounterIncrement(false), _hasInstrumentation(false) {}
416 // Sets the target node of this edge. Required to split edges.
417 void BLInstrumentationEdge::setTarget(BallLarusNode* node) {
421 // Returns whether this edge is in the spanning tree.
422 bool BLInstrumentationEdge::isInSpanningTree() const {
423 return(_isInSpanningTree);
426 // Sets whether this edge is in the spanning tree.
427 void BLInstrumentationEdge::setIsInSpanningTree(bool isInSpanningTree) {
428 _isInSpanningTree = isInSpanningTree;
431 // Returns whether this edge will be instrumented with a path number
433 bool BLInstrumentationEdge::isInitialization() const {
434 return(_isInitialization);
437 // Sets whether this edge will be instrumented with a path number
439 void BLInstrumentationEdge::setIsInitialization(bool isInitialization) {
440 _isInitialization = isInitialization;
443 // Returns whether this edge will be instrumented with a path counter
444 // increment. Notice this is incrementing the path counter
445 // corresponding to the path number register. The path number
446 // increment is determined by getIncrement().
447 bool BLInstrumentationEdge::isCounterIncrement() const {
448 return(_isCounterIncrement);
451 // Sets whether this edge will be instrumented with a path counter
453 void BLInstrumentationEdge::setIsCounterIncrement(bool isCounterIncrement) {
454 _isCounterIncrement = isCounterIncrement;
457 // Gets the path number increment that this edge will be instrumented
458 // with. This is distinct from the path counter increment and the
459 // weight. The counter increment is counts the number of executions of
460 // some path, whereas the path number keeps track of which path number
461 // the program is on.
462 long BLInstrumentationEdge::getIncrement() const {
466 // Set whether this edge will be instrumented with a path number
468 void BLInstrumentationEdge::setIncrement(long increment) {
469 _increment = increment;
472 // True iff the edge has already been instrumented.
473 bool BLInstrumentationEdge::hasInstrumentation() {
474 return(_hasInstrumentation);
477 // Set whether this edge has been instrumented.
478 void BLInstrumentationEdge::setHasInstrumentation(bool hasInstrumentation) {
479 _hasInstrumentation = hasInstrumentation;
482 // Returns the successor number of this edge in the source.
483 unsigned BLInstrumentationEdge::getSuccessorNumber() {
484 BallLarusNode* sourceNode = getSource();
485 BallLarusNode* targetNode = getTarget();
486 BasicBlock* source = sourceNode->getBlock();
487 BasicBlock* target = targetNode->getBlock();
489 if(source == NULL || target == NULL)
492 TerminatorInst* terminator = source->getTerminator();
495 for(i=0; i < terminator->getNumSuccessors(); i++) {
496 if(terminator->getSuccessor(i) == target)
503 // BLInstrumentationDag constructor initializes a DAG for the given Function.
504 BLInstrumentationDag::BLInstrumentationDag(Function &F) : BallLarusDag(F),
508 // Returns the Exit->Root edge. This edge is required for creating
509 // directed cycles in the algorithm for moving instrumentation off of
511 BallLarusEdge* BLInstrumentationDag::getExitRootEdge() {
512 BLEdgeIterator erEdge = getExit()->succBegin();
516 BLEdgeVector BLInstrumentationDag::getCallPhonyEdges () {
517 BLEdgeVector callEdges;
519 for( BLEdgeIterator edge = _edges.begin(), end = _edges.end();
520 edge != end; edge++ ) {
521 if( (*edge)->getType() == BallLarusEdge::CALLEDGE_PHONY )
522 callEdges.push_back(*edge);
528 // Gets the path counter array
529 GlobalVariable* BLInstrumentationDag::getCounterArray() {
530 return _counterArray;
533 void BLInstrumentationDag::setCounterArray(GlobalVariable* c) {
537 // Calculates the increment for the chords, thereby removing
538 // instrumentation from the spanning tree edges. Implementation is based on
539 // the algorithm in Figure 4 of [Ball94]
540 void BLInstrumentationDag::calculateChordIncrements() {
541 calculateChordIncrementsDfs(0, getRoot(), NULL);
543 BLInstrumentationEdge* chord;
544 for(BLEdgeIterator chordEdge = _chordEdges.begin(),
545 end = _chordEdges.end(); chordEdge != end; chordEdge++) {
546 chord = (BLInstrumentationEdge*) *chordEdge;
547 chord->setIncrement(chord->getIncrement() + chord->getWeight());
551 // Updates the state when an edge has been split
552 void BLInstrumentationDag::splitUpdate(BLInstrumentationEdge* formerEdge,
553 BasicBlock* newBlock) {
554 BallLarusNode* oldTarget = formerEdge->getTarget();
555 BallLarusNode* newNode = addNode(newBlock);
556 formerEdge->setTarget(newNode);
557 newNode->addPredEdge(formerEdge);
559 DEBUG(dbgs() << " Edge split: " << *formerEdge << "\n");
561 oldTarget->removePredEdge(formerEdge);
562 BallLarusEdge* newEdge = addEdge(newNode, oldTarget,0);
564 if( formerEdge->getType() == BallLarusEdge::BACKEDGE ||
565 formerEdge->getType() == BallLarusEdge::SPLITEDGE) {
566 newEdge->setType(formerEdge->getType());
567 newEdge->setPhonyRoot(formerEdge->getPhonyRoot());
568 newEdge->setPhonyExit(formerEdge->getPhonyExit());
569 formerEdge->setType(BallLarusEdge::NORMAL);
570 formerEdge->setPhonyRoot(NULL);
571 formerEdge->setPhonyExit(NULL);
575 // Calculates a spanning tree of the DAG ignoring cycles. Whichever
576 // edges are in the spanning tree will not be instrumented, but this
577 // implementation does not try to minimize the instrumentation overhead
578 // by trying to find hot edges.
579 void BLInstrumentationDag::calculateSpanningTree() {
580 std::stack<BallLarusNode*> dfsStack;
582 for(BLNodeIterator nodeIt = _nodes.begin(), end = _nodes.end();
583 nodeIt != end; nodeIt++) {
584 (*nodeIt)->setColor(BallLarusNode::WHITE);
587 dfsStack.push(getRoot());
588 while(dfsStack.size() > 0) {
589 BallLarusNode* node = dfsStack.top();
592 if(node->getColor() == BallLarusNode::WHITE)
595 BallLarusNode* nextNode;
597 BLEdgeIterator succEnd = node->succEnd();
599 node->setColor(BallLarusNode::WHITE);
600 // first iterate over successors then predecessors
601 for(BLEdgeIterator edge = node->succBegin(), predEnd = node->predEnd();
602 edge != predEnd; edge++) {
603 if(edge == succEnd) {
604 edge = node->predBegin();
608 // Ignore split edges
609 if ((*edge)->getType() == BallLarusEdge::SPLITEDGE)
612 nextNode = forward? (*edge)->getTarget(): (*edge)->getSource();
613 if(nextNode->getColor() != BallLarusNode::WHITE) {
614 nextNode->setColor(BallLarusNode::WHITE);
615 makeEdgeSpanning((BLInstrumentationEdge*)(*edge));
620 for(BLEdgeIterator edge = _edges.begin(), end = _edges.end();
621 edge != end; edge++) {
622 BLInstrumentationEdge* instEdge = (BLInstrumentationEdge*) (*edge);
623 // safe since createEdge is overriden
624 if(!instEdge->isInSpanningTree() && (*edge)->getType()
625 != BallLarusEdge::SPLITEDGE)
626 _chordEdges.push_back(instEdge);
630 // Pushes initialization further down in order to group the first
631 // increment and initialization.
632 void BLInstrumentationDag::pushInitialization() {
633 BLInstrumentationEdge* exitRootEdge =
634 (BLInstrumentationEdge*) getExitRootEdge();
635 exitRootEdge->setIsInitialization(true);
636 pushInitializationFromEdge(exitRootEdge);
639 // Pushes the path counter increments up in order to group the last path
641 void BLInstrumentationDag::pushCounters() {
642 BLInstrumentationEdge* exitRootEdge =
643 (BLInstrumentationEdge*) getExitRootEdge();
644 exitRootEdge->setIsCounterIncrement(true);
645 pushCountersFromEdge(exitRootEdge);
648 // Removes phony edges from the successor list of the source, and the
649 // predecessor list of the target.
650 void BLInstrumentationDag::unlinkPhony() {
653 for(BLEdgeIterator next = _edges.begin(),
654 end = _edges.end(); next != end; next++) {
657 if( edge->getType() == BallLarusEdge::BACKEDGE_PHONY ||
658 edge->getType() == BallLarusEdge::SPLITEDGE_PHONY ||
659 edge->getType() == BallLarusEdge::CALLEDGE_PHONY ) {
665 // Generate a .dot graph to represent the DAG and pathNumbers
666 void BLInstrumentationDag::generateDotGraph() {
667 std::string errorInfo;
668 std::string functionName = getFunction().getName().str();
669 std::string filename = "pathdag." + functionName + ".dot";
671 DEBUG (dbgs() << "Writing '" << filename << "'...\n");
672 raw_fd_ostream dotFile(filename.c_str(), errorInfo);
674 if (!errorInfo.empty()) {
675 errs() << "Error opening '" << filename.c_str() <<"' for writing!";
680 dotFile << "digraph " << functionName << " {\n";
682 for( BLEdgeIterator edge = _edges.begin(), end = _edges.end();
683 edge != end; edge++) {
684 std::string sourceName = (*edge)->getSource()->getName();
685 std::string targetName = (*edge)->getTarget()->getName();
687 dotFile << "\t\"" << sourceName.c_str() << "\" -> \""
688 << targetName.c_str() << "\" ";
690 long inc = ((BLInstrumentationEdge*)(*edge))->getIncrement();
692 switch( (*edge)->getType() ) {
693 case BallLarusEdge::NORMAL:
694 dotFile << "[label=" << inc << "] [color=black];\n";
697 case BallLarusEdge::BACKEDGE:
698 dotFile << "[color=cyan];\n";
701 case BallLarusEdge::BACKEDGE_PHONY:
702 dotFile << "[label=" << inc
703 << "] [color=blue];\n";
706 case BallLarusEdge::SPLITEDGE:
707 dotFile << "[color=violet];\n";
710 case BallLarusEdge::SPLITEDGE_PHONY:
711 dotFile << "[label=" << inc << "] [color=red];\n";
714 case BallLarusEdge::CALLEDGE_PHONY:
715 dotFile << "[label=" << inc << "] [color=green];\n";
723 // Allows subclasses to determine which type of Node is created.
724 // Override this method to produce subclasses of BallLarusNode if
725 // necessary. The destructor of BallLarusDag will call free on each pointer
727 BallLarusNode* BLInstrumentationDag::createNode(BasicBlock* BB) {
728 return( new BLInstrumentationNode(BB) );
731 // Allows subclasses to determine which type of Edge is created.
732 // Override this method to produce subclasses of BallLarusEdge if
733 // necessary. The destructor of BallLarusDag will call free on each pointer
735 BallLarusEdge* BLInstrumentationDag::createEdge(BallLarusNode* source,
736 BallLarusNode* target, unsigned edgeNumber) {
737 // One can cast from BallLarusNode to BLInstrumentationNode since createNode
738 // is overriden to produce BLInstrumentationNode.
739 return( new BLInstrumentationEdge((BLInstrumentationNode*)source,
740 (BLInstrumentationNode*)target) );
743 // Sets the Value corresponding to the pathNumber register, constant,
744 // or phinode. Used by the instrumentation code to remember path
746 Value* BLInstrumentationNode::getStartingPathNumber(){
747 return(_startingPathNumber);
750 // Sets the Value of the pathNumber. Used by the instrumentation code.
751 void BLInstrumentationNode::setStartingPathNumber(Value* pathNumber) {
752 DEBUG(dbgs() << " SPN-" << getName() << " <-- " << (pathNumber ?
753 pathNumber->getName() :
755 _startingPathNumber = pathNumber;
758 Value* BLInstrumentationNode::getEndingPathNumber(){
759 return(_endingPathNumber);
762 void BLInstrumentationNode::setEndingPathNumber(Value* pathNumber) {
763 DEBUG(dbgs() << " EPN-" << getName() << " <-- "
764 << (pathNumber ? pathNumber->getName() : "unused") << "\n");
765 _endingPathNumber = pathNumber;
768 // Get the PHINode Instruction for this node. Used by instrumentation
770 PHINode* BLInstrumentationNode::getPathPHI() {
774 // Set the PHINode Instruction for this node. Used by instrumentation
776 void BLInstrumentationNode::setPathPHI(PHINode* pathPHI) {
780 // Removes the edge from the appropriate predecessor and successor
782 void BLInstrumentationDag::unlinkEdge(BallLarusEdge* edge) {
783 if(edge == getExitRootEdge())
784 DEBUG(dbgs() << " Removing exit->root edge\n");
786 edge->getSource()->removeSuccEdge(edge);
787 edge->getTarget()->removePredEdge(edge);
790 // Makes an edge part of the spanning tree.
791 void BLInstrumentationDag::makeEdgeSpanning(BLInstrumentationEdge* edge) {
792 edge->setIsInSpanningTree(true);
793 _treeEdges.push_back(edge);
796 // Pushes initialization and calls itself recursively.
797 void BLInstrumentationDag::pushInitializationFromEdge(
798 BLInstrumentationEdge* edge) {
799 BallLarusNode* target;
801 target = edge->getTarget();
802 if( target->getNumberPredEdges() > 1 || target == getExit() ) {
805 for(BLEdgeIterator next = target->succBegin(),
806 end = target->succEnd(); next != end; next++) {
807 BLInstrumentationEdge* intoEdge = (BLInstrumentationEdge*) *next;
810 if (intoEdge->getType() == BallLarusEdge::SPLITEDGE)
813 intoEdge->setIncrement(intoEdge->getIncrement() +
814 edge->getIncrement());
815 intoEdge->setIsInitialization(true);
816 pushInitializationFromEdge(intoEdge);
819 edge->setIncrement(0);
820 edge->setIsInitialization(false);
824 // Pushes path counter increments up recursively.
825 void BLInstrumentationDag::pushCountersFromEdge(BLInstrumentationEdge* edge) {
826 BallLarusNode* source;
828 source = edge->getSource();
829 if(source->getNumberSuccEdges() > 1 || source == getRoot()
830 || edge->isInitialization()) {
833 for(BLEdgeIterator previous = source->predBegin(),
834 end = source->predEnd(); previous != end; previous++) {
835 BLInstrumentationEdge* fromEdge = (BLInstrumentationEdge*) *previous;
838 if (fromEdge->getType() == BallLarusEdge::SPLITEDGE)
841 fromEdge->setIncrement(fromEdge->getIncrement() +
842 edge->getIncrement());
843 fromEdge->setIsCounterIncrement(true);
844 pushCountersFromEdge(fromEdge);
847 edge->setIncrement(0);
848 edge->setIsCounterIncrement(false);
852 // Depth first algorithm for determining the chord increments.
853 void BLInstrumentationDag::calculateChordIncrementsDfs(long weight,
854 BallLarusNode* v, BallLarusEdge* e) {
855 BLInstrumentationEdge* f;
857 for(BLEdgeIterator treeEdge = _treeEdges.begin(),
858 end = _treeEdges.end(); treeEdge != end; treeEdge++) {
859 f = (BLInstrumentationEdge*) *treeEdge;
860 if(e != f && v == f->getTarget()) {
861 calculateChordIncrementsDfs(
862 calculateChordIncrementsDir(e,f)*(weight) +
863 f->getWeight(), f->getSource(), f);
865 if(e != f && v == f->getSource()) {
866 calculateChordIncrementsDfs(
867 calculateChordIncrementsDir(e,f)*(weight) +
868 f->getWeight(), f->getTarget(), f);
872 for(BLEdgeIterator chordEdge = _chordEdges.begin(),
873 end = _chordEdges.end(); chordEdge != end; chordEdge++) {
874 f = (BLInstrumentationEdge*) *chordEdge;
875 if(v == f->getSource() || v == f->getTarget()) {
876 f->setIncrement(f->getIncrement() +
877 calculateChordIncrementsDir(e,f)*weight);
882 // Determines the relative direction of two edges.
883 int BLInstrumentationDag::calculateChordIncrementsDir(BallLarusEdge* e,
887 else if(e->getSource() == f->getTarget()
888 || e->getTarget() == f->getSource())
894 // Creates an increment constant representing incr.
895 ConstantInt* PathProfiler::createIncrementConstant(long incr,
897 return(ConstantInt::get(IntegerType::get(*Context, 32), incr));
900 // Creates an increment constant representing the value in
901 // edge->getIncrement().
902 ConstantInt* PathProfiler::createIncrementConstant(
903 BLInstrumentationEdge* edge) {
904 return(createIncrementConstant(edge->getIncrement(), 32));
907 // Finds the insertion point after pathNumber in block. PathNumber may
909 BasicBlock::iterator PathProfiler::getInsertionPoint(BasicBlock* block, Value*
911 if(pathNumber == NULL || isa<ConstantInt>(pathNumber)
912 || (((Instruction*)(pathNumber))->getParent()) != block) {
913 return(block->getFirstInsertionPt());
915 Instruction* pathNumberInst = (Instruction*) (pathNumber);
916 BasicBlock::iterator insertPoint;
917 BasicBlock::iterator end = block->end();
919 for(insertPoint = block->begin();
920 insertPoint != end; insertPoint++) {
921 Instruction* insertInst = &(*insertPoint);
923 if(insertInst == pathNumberInst)
924 return(++insertPoint);
931 // A PHINode is created in the node, and its values initialized to -1U.
932 void PathProfiler::preparePHI(BLInstrumentationNode* node) {
933 BasicBlock* block = node->getBlock();
934 BasicBlock::iterator insertPoint = block->getFirstInsertionPt();
935 pred_iterator PB = pred_begin(node->getBlock()),
936 PE = pred_end(node->getBlock());
937 PHINode* phi = PHINode::Create(Type::getInt32Ty(*Context),
938 std::distance(PB, PE), "pathNumber",
940 node->setPathPHI(phi);
941 node->setStartingPathNumber(phi);
942 node->setEndingPathNumber(phi);
944 for(pred_iterator predIt = PB; predIt != PE; predIt++) {
945 BasicBlock* pred = (*predIt);
948 phi->addIncoming(createIncrementConstant((long)-1, 32), pred);
952 // Inserts source's pathNumber Value* into target. Target may or may not
953 // have multiple predecessors, and may or may not have its phiNode
955 void PathProfiler::pushValueIntoNode(BLInstrumentationNode* source,
956 BLInstrumentationNode* target) {
957 if(target->getBlock() == NULL)
961 if(target->getNumberPredEdges() <= 1) {
962 assert(target->getStartingPathNumber() == NULL &&
963 "Target already has path number");
964 target->setStartingPathNumber(source->getEndingPathNumber());
965 target->setEndingPathNumber(source->getEndingPathNumber());
966 DEBUG(dbgs() << " Passing path number"
967 << (source->getEndingPathNumber() ? "" : " (null)")
968 << " value through.\n");
970 if(target->getPathPHI() == NULL) {
971 DEBUG(dbgs() << " Initializing PHI node for block '"
972 << target->getName() << "'\n");
975 pushValueIntoPHI(target, source);
976 DEBUG(dbgs() << " Passing number value into PHI for block '"
977 << target->getName() << "'\n");
981 // Inserts source's pathNumber Value* into the appropriate slot of
983 void PathProfiler::pushValueIntoPHI(BLInstrumentationNode* target,
984 BLInstrumentationNode* source) {
985 PHINode* phi = target->getPathPHI();
986 assert(phi != NULL && " Tried to push value into node with PHI, but node"
987 " actually had no PHI.");
988 phi->removeIncomingValue(source->getBlock(), false);
989 phi->addIncoming(source->getEndingPathNumber(), source->getBlock());
992 // The Value* in node, oldVal, is updated with a Value* correspodning to
993 // oldVal + addition.
994 void PathProfiler::insertNumberIncrement(BLInstrumentationNode* node,
995 Value* addition, bool atBeginning) {
996 BasicBlock* block = node->getBlock();
997 assert(node->getStartingPathNumber() != NULL);
998 assert(node->getEndingPathNumber() != NULL);
1000 BasicBlock::iterator insertPoint;
1003 insertPoint = block->getFirstInsertionPt();
1005 insertPoint = block->getTerminator();
1007 DEBUG(errs() << " Creating addition instruction.\n");
1008 Value* newpn = BinaryOperator::Create(Instruction::Add,
1009 node->getStartingPathNumber(),
1010 addition, "pathNumber", insertPoint);
1012 node->setEndingPathNumber(newpn);
1015 node->setStartingPathNumber(newpn);
1018 // Creates a counter increment in the given node. The Value* in node is
1019 // taken as the index into an array or hash table. The hash table access
1020 // is a call to the runtime.
1021 void PathProfiler::insertCounterIncrement(Value* incValue,
1022 BasicBlock::iterator insertPoint,
1023 BLInstrumentationDag* dag,
1025 // Counter increment for array
1026 if( dag->getNumberOfPaths() <= HASH_THRESHHOLD ) {
1027 // Get pointer to the array location
1028 std::vector<Value*> gepIndices(2);
1029 gepIndices[0] = Constant::getNullValue(Type::getInt32Ty(*Context));
1030 gepIndices[1] = incValue;
1032 GetElementPtrInst* pcPointer =
1033 GetElementPtrInst::Create(dag->getCounterArray(), gepIndices,
1034 "counterInc", insertPoint);
1036 // Load from the array - call it oldPC
1037 LoadInst* oldPc = new LoadInst(pcPointer, "oldPC", insertPoint);
1039 // Test to see whether adding 1 will overflow the counter
1040 ICmpInst* isMax = new ICmpInst(insertPoint, CmpInst::ICMP_ULT, oldPc,
1041 createIncrementConstant(0xffffffff, 32),
1044 // Select increment for the path counter based on overflow
1046 SelectInst::Create( isMax, createIncrementConstant(increment?1:-1,32),
1047 createIncrementConstant(0,32),
1048 "pathInc", insertPoint);
1050 // newPc = oldPc + inc
1051 BinaryOperator* newPc = BinaryOperator::Create(Instruction::Add,
1052 oldPc, inc, "newPC",
1055 // Store back in to the array
1056 new StoreInst(newPc, pcPointer, insertPoint);
1057 } else { // Counter increment for hash
1058 std::vector<Value*> args(2);
1059 args[0] = ConstantInt::get(Type::getInt32Ty(*Context),
1060 currentFunctionNumber);
1064 increment ? llvmIncrementHashFunction : llvmDecrementHashFunction,
1065 args, "", insertPoint);
1069 // Inserts instrumentation for the given edge
1071 // Pre: The edge's source node has pathNumber set if edge is non zero
1072 // path number increment.
1074 // Post: Edge's target node has a pathNumber set to the path number Value
1075 // corresponding to the value of the path register after edge's
1078 // FIXME: This should be reworked so it's not recursive.
1079 void PathProfiler::insertInstrumentationStartingAt(BLInstrumentationEdge* edge,
1080 BLInstrumentationDag* dag) {
1081 // Mark the edge as instrumented
1082 edge->setHasInstrumentation(true);
1083 DEBUG(dbgs() << "\nInstrumenting edge: " << (*edge) << "\n");
1085 // create a new node for this edge's instrumentation
1086 splitCritical(edge, dag);
1088 BLInstrumentationNode* sourceNode = (BLInstrumentationNode*)edge->getSource();
1089 BLInstrumentationNode* targetNode = (BLInstrumentationNode*)edge->getTarget();
1090 BLInstrumentationNode* instrumentNode;
1091 BLInstrumentationNode* nextSourceNode;
1093 bool atBeginning = false;
1095 // Source node has only 1 successor so any information can be simply
1096 // inserted in to it without splitting
1097 if( sourceNode->getBlock() && sourceNode->getNumberSuccEdges() <= 1) {
1098 DEBUG(dbgs() << " Potential instructions to be placed in: "
1099 << sourceNode->getName() << " (at end)\n");
1100 instrumentNode = sourceNode;
1101 nextSourceNode = targetNode; // ... since we never made any new nodes
1104 // The target node only has one predecessor, so we can safely insert edge
1105 // instrumentation into it. If there was splitting, it must have been
1107 else if( targetNode->getNumberPredEdges() == 1 ) {
1108 DEBUG(dbgs() << " Potential instructions to be placed in: "
1109 << targetNode->getName() << " (at beginning)\n");
1110 pushValueIntoNode(sourceNode, targetNode);
1111 instrumentNode = targetNode;
1112 nextSourceNode = NULL; // ... otherwise we'll just keep splitting
1116 // Somehow, splitting must have failed.
1118 errs() << "Instrumenting could not split a critical edge.\n";
1119 DEBUG(dbgs() << " Couldn't split edge " << (*edge) << ".\n");
1123 // Insert instrumentation if this is a back or split edge
1124 if( edge->getType() == BallLarusEdge::BACKEDGE ||
1125 edge->getType() == BallLarusEdge::SPLITEDGE ) {
1126 BLInstrumentationEdge* top =
1127 (BLInstrumentationEdge*) edge->getPhonyRoot();
1128 BLInstrumentationEdge* bottom =
1129 (BLInstrumentationEdge*) edge->getPhonyExit();
1131 assert( top->isInitialization() && " Top phony edge did not"
1132 " contain a path number initialization.");
1133 assert( bottom->isCounterIncrement() && " Bottom phony edge"
1134 " did not contain a path counter increment.");
1136 // split edge has yet to be initialized
1137 if( !instrumentNode->getEndingPathNumber() ) {
1138 instrumentNode->setStartingPathNumber(createIncrementConstant(0,32));
1139 instrumentNode->setEndingPathNumber(createIncrementConstant(0,32));
1142 BasicBlock::iterator insertPoint = atBeginning ?
1143 instrumentNode->getBlock()->getFirstInsertionPt() :
1144 instrumentNode->getBlock()->getTerminator();
1146 // add information from the bottom edge, if it exists
1147 if( bottom->getIncrement() ) {
1149 BinaryOperator::Create(Instruction::Add,
1150 instrumentNode->getStartingPathNumber(),
1151 createIncrementConstant(bottom),
1152 "pathNumber", insertPoint);
1153 instrumentNode->setEndingPathNumber(newpn);
1156 insertCounterIncrement(instrumentNode->getEndingPathNumber(),
1160 instrumentNode->setStartingPathNumber(createIncrementConstant(top));
1162 instrumentNode->setEndingPathNumber(createIncrementConstant(top));
1164 // Check for path counter increments
1165 if( top->isCounterIncrement() ) {
1166 insertCounterIncrement(instrumentNode->getEndingPathNumber(),
1167 instrumentNode->getBlock()->getTerminator(),dag);
1168 instrumentNode->setEndingPathNumber(0);
1172 // Insert instrumentation if this is a normal edge
1174 BasicBlock::iterator insertPoint = atBeginning ?
1175 instrumentNode->getBlock()->getFirstInsertionPt() :
1176 instrumentNode->getBlock()->getTerminator();
1178 if( edge->isInitialization() ) { // initialize path number
1179 instrumentNode->setEndingPathNumber(createIncrementConstant(edge));
1180 } else if( edge->getIncrement() ) {// increment path number
1182 BinaryOperator::Create(Instruction::Add,
1183 instrumentNode->getStartingPathNumber(),
1184 createIncrementConstant(edge),
1185 "pathNumber", insertPoint);
1186 instrumentNode->setEndingPathNumber(newpn);
1189 instrumentNode->setStartingPathNumber(newpn);
1192 // Check for path counter increments
1193 if( edge->isCounterIncrement() ) {
1194 insertCounterIncrement(instrumentNode->getEndingPathNumber(),
1196 instrumentNode->setEndingPathNumber(0);
1201 if (nextSourceNode && instrumentNode->getEndingPathNumber())
1202 pushValueIntoNode(instrumentNode, nextSourceNode);
1204 // Add all the successors
1205 for( BLEdgeIterator next = targetNode->succBegin(),
1206 end = targetNode->succEnd(); next != end; next++ ) {
1207 // So long as it is un-instrumented, add it to the list
1208 if( !((BLInstrumentationEdge*)(*next))->hasInstrumentation() )
1209 insertInstrumentationStartingAt((BLInstrumentationEdge*)*next,dag);
1211 DEBUG(dbgs() << " Edge " << *(BLInstrumentationEdge*)(*next)
1212 << " already instrumented.\n");
1216 // Inserts instrumentation according to the marked edges in dag. Phony edges
1217 // must be unlinked from the DAG, but accessible from the backedges. Dag
1218 // must have initializations, path number increments, and counter increments
1221 // Counter storage is created here.
1222 void PathProfiler::insertInstrumentation(
1223 BLInstrumentationDag& dag, Module &M) {
1225 BLInstrumentationEdge* exitRootEdge =
1226 (BLInstrumentationEdge*) dag.getExitRootEdge();
1227 insertInstrumentationStartingAt(exitRootEdge, &dag);
1229 // Iterate through each call edge and apply the appropriate hash increment
1230 // and decrement functions
1231 BLEdgeVector callEdges = dag.getCallPhonyEdges();
1232 for( BLEdgeIterator edge = callEdges.begin(),
1233 end = callEdges.end(); edge != end; edge++ ) {
1234 BLInstrumentationNode* node =
1235 (BLInstrumentationNode*)(*edge)->getSource();
1236 BasicBlock::iterator insertPoint = node->getBlock()->getFirstInsertionPt();
1238 // Find the first function call
1239 while( ((Instruction&)(*insertPoint)).getOpcode() != Instruction::Call )
1242 DEBUG(dbgs() << "\nInstrumenting method call block '"
1243 << node->getBlock()->getName() << "'\n");
1244 DEBUG(dbgs() << " Path number initialized: "
1245 << ((node->getStartingPathNumber()) ? "yes" : "no") << "\n");
1248 if( node->getStartingPathNumber() ) {
1249 long inc = ((BLInstrumentationEdge*)(*edge))->getIncrement();
1251 newpn = BinaryOperator::Create(Instruction::Add,
1252 node->getStartingPathNumber(),
1253 createIncrementConstant(inc,32),
1254 "pathNumber", insertPoint);
1256 newpn = node->getStartingPathNumber();
1258 newpn = (Value*)createIncrementConstant(
1259 ((BLInstrumentationEdge*)(*edge))->getIncrement(), 32);
1262 insertCounterIncrement(newpn, insertPoint, &dag);
1263 insertCounterIncrement(newpn, node->getBlock()->getTerminator(),
1268 // Entry point of the module
1269 void PathProfiler::runOnFunction(std::vector<Constant*> &ftInit,
1270 Function &F, Module &M) {
1271 // Build DAG from CFG
1272 BLInstrumentationDag dag = BLInstrumentationDag(F);
1275 // give each path a unique integer value
1276 dag.calculatePathNumbers();
1278 // modify path increments to increase the efficiency
1279 // of instrumentation
1280 dag.calculateSpanningTree();
1281 dag.calculateChordIncrements();
1282 dag.pushInitialization();
1286 // potentially generate .dot graph for the dag
1288 dag.generateDotGraph ();
1290 // Should we store the information in an array or hash
1291 if( dag.getNumberOfPaths() <= HASH_THRESHHOLD ) {
1292 Type* t = ArrayType::get(Type::getInt32Ty(*Context),
1293 dag.getNumberOfPaths());
1295 dag.setCounterArray(new GlobalVariable(M, t, false,
1296 GlobalValue::InternalLinkage,
1297 Constant::getNullValue(t), ""));
1300 insertInstrumentation(dag, M);
1302 // Add to global function reference table
1304 Type* voidPtr = TypeBuilder<types::i<8>*, true>::get(*Context);
1306 if( dag.getNumberOfPaths() <= HASH_THRESHHOLD )
1307 type = ProfilingArray;
1309 type = ProfilingHash;
1311 std::vector<Constant*> entryArray(3);
1312 entryArray[0] = createIncrementConstant(type,32);
1313 entryArray[1] = createIncrementConstant(dag.getNumberOfPaths(),32);
1314 entryArray[2] = dag.getCounterArray() ?
1315 ConstantExpr::getBitCast(dag.getCounterArray(), voidPtr) :
1316 Constant::getNullValue(voidPtr);
1318 StructType* at = ftEntryTypeBuilder::get(*Context);
1319 ConstantStruct* functionEntry =
1320 (ConstantStruct*)ConstantStruct::get(at, entryArray);
1321 ftInit.push_back(functionEntry);
1324 // Output the bitcode if we want to observe instrumentation changess
1325 #define PRINT_MODULE dbgs() << \
1326 "\n\n============= MODULE BEGIN ===============\n" << M << \
1327 "\n============== MODULE END ================\n"
1329 bool PathProfiler::runOnModule(Module &M) {
1330 Context = &M.getContext();
1333 << "****************************************\n"
1334 << "****************************************\n"
1336 << "** PATH PROFILING INSTRUMENTATION **\n"
1338 << "****************************************\n"
1339 << "****************************************\n");
1341 // No main, no instrumentation!
1342 Function *Main = M.getFunction("main");
1344 // Using fortran? ... this kind of works
1346 Main = M.getFunction("MAIN__");
1349 errs() << "WARNING: cannot insert path profiling into a module"
1350 << " with no main function!\n";
1354 llvmIncrementHashFunction = M.getOrInsertFunction(
1355 "llvm_increment_path_count",
1356 Type::getVoidTy(*Context), // return type
1357 Type::getInt32Ty(*Context), // function number
1358 Type::getInt32Ty(*Context), // path number
1361 llvmDecrementHashFunction = M.getOrInsertFunction(
1362 "llvm_decrement_path_count",
1363 Type::getVoidTy(*Context), // return type
1364 Type::getInt32Ty(*Context), // function number
1365 Type::getInt32Ty(*Context), // path number
1368 std::vector<Constant*> ftInit;
1369 unsigned functionNumber = 0;
1370 for (Module::iterator F = M.begin(), E = M.end(); F != E; F++) {
1371 if (F->isDeclaration())
1374 DEBUG(dbgs() << "Function: " << F->getName() << "\n");
1377 // set function number
1378 currentFunctionNumber = functionNumber;
1379 runOnFunction(ftInit, *F, M);
1382 Type *t = ftEntryTypeBuilder::get(*Context);
1383 ArrayType* ftArrayType = ArrayType::get(t, ftInit.size());
1384 Constant* ftInitConstant = ConstantArray::get(ftArrayType, ftInit);
1386 DEBUG(dbgs() << " ftArrayType:" << *ftArrayType << "\n");
1388 GlobalVariable* functionTable =
1389 new GlobalVariable(M, ftArrayType, false, GlobalValue::InternalLinkage,
1390 ftInitConstant, "functionPathTable");
1391 Type *eltType = ftArrayType->getTypeAtIndex((unsigned)0);
1392 InsertProfilingInitCall(Main, "llvm_start_path_profiling", functionTable,
1393 PointerType::getUnqual(eltType));
1395 DEBUG(PRINT_MODULE);
1400 // If this edge is a critical edge, then inserts a node at this edge.
1401 // This edge becomes the first edge, and a new BallLarusEdge is created.
1402 // Returns true if the edge was split
1403 bool PathProfiler::splitCritical(BLInstrumentationEdge* edge,
1404 BLInstrumentationDag* dag) {
1405 unsigned succNum = edge->getSuccessorNumber();
1406 BallLarusNode* sourceNode = edge->getSource();
1407 BallLarusNode* targetNode = edge->getTarget();
1408 BasicBlock* sourceBlock = sourceNode->getBlock();
1409 BasicBlock* targetBlock = targetNode->getBlock();
1411 if(sourceBlock == NULL || targetBlock == NULL
1412 || sourceNode->getNumberSuccEdges() <= 1
1413 || targetNode->getNumberPredEdges() == 1 ) {
1417 TerminatorInst* terminator = sourceBlock->getTerminator();
1419 if( SplitCriticalEdge(terminator, succNum, this, false)) {
1420 BasicBlock* newBlock = terminator->getSuccessor(succNum);
1421 dag->splitUpdate(edge, newBlock);