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/Support/Compiler.h"
59 #include "llvm/Support/CFG.h"
60 #include "llvm/Support/CommandLine.h"
61 #include "llvm/Support/Debug.h"
62 #include "llvm/Support/TypeBuilder.h"
63 #include "llvm/Support/raw_ostream.h"
64 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
65 #include "llvm/Transforms/Instrumentation.h"
69 #define HASH_THRESHHOLD 100000
74 class BLInstrumentationNode;
75 class BLInstrumentationEdge;
76 class BLInstrumentationDag;
78 // ---------------------------------------------------------------------------
79 // BLInstrumentationNode extends BallLarusNode with member used by the
80 // instrumentation algortihms.
81 // ---------------------------------------------------------------------------
82 class BLInstrumentationNode : public BallLarusNode {
84 // Creates a new BLInstrumentationNode from a BasicBlock.
85 BLInstrumentationNode(BasicBlock* BB);
87 // Get/sets the Value corresponding to the pathNumber register,
88 // constant or phinode. Used by the instrumentation code to remember
89 // path number Values.
90 Value* getStartingPathNumber();
91 void setStartingPathNumber(Value* pathNumber);
93 Value* getEndingPathNumber();
94 void setEndingPathNumber(Value* pathNumber);
96 // Get/set the PHINode Instruction for this node.
97 PHINode* getPathPHI();
98 void setPathPHI(PHINode* pathPHI);
102 Value* _startingPathNumber; // The Value for the current pathNumber.
103 Value* _endingPathNumber; // The Value for the current pathNumber.
104 PHINode* _pathPHI; // The PHINode for current pathNumber.
107 // --------------------------------------------------------------------------
108 // BLInstrumentationEdge extends BallLarusEdge with data about the
109 // instrumentation that will end up on each edge.
110 // --------------------------------------------------------------------------
111 class BLInstrumentationEdge : public BallLarusEdge {
113 BLInstrumentationEdge(BLInstrumentationNode* source,
114 BLInstrumentationNode* target);
116 // Sets the target node of this edge. Required to split edges.
117 void setTarget(BallLarusNode* node);
119 // Get/set whether edge is in the spanning tree.
120 bool isInSpanningTree() const;
121 void setIsInSpanningTree(bool isInSpanningTree);
123 // Get/ set whether this edge will be instrumented with a path number
125 bool isInitialization() const;
126 void setIsInitialization(bool isInitialization);
128 // Get/set whether this edge will be instrumented with a path counter
129 // increment. Notice this is incrementing the path counter
130 // corresponding to the path number register. The path number
131 // increment is determined by getIncrement().
132 bool isCounterIncrement() const;
133 void setIsCounterIncrement(bool isCounterIncrement);
135 // Get/set the path number increment that this edge will be instrumented
136 // with. This is distinct from the path counter increment and the
137 // weight. The counter increment counts the number of executions of
138 // some path, whereas the path number keeps track of which path number
139 // the program is on.
140 long getIncrement() const;
141 void setIncrement(long increment);
143 // Get/set whether the edge has been instrumented.
144 bool hasInstrumentation();
145 void setHasInstrumentation(bool hasInstrumentation);
147 // Returns the successor number of this edge in the source.
148 unsigned getSuccessorNumber();
151 // The increment that the code will be instrumented with.
152 long long _increment;
154 // Whether this edge is in the spanning tree.
155 bool _isInSpanningTree;
157 // Whether this edge is an initialiation of the path number.
158 bool _isInitialization;
160 // Whether this edge is a path counter increment.
161 bool _isCounterIncrement;
163 // Whether this edge has been instrumented.
164 bool _hasInstrumentation;
167 // ---------------------------------------------------------------------------
168 // BLInstrumentationDag extends BallLarusDag with algorithms that
169 // determine where instrumentation should be placed.
170 // ---------------------------------------------------------------------------
171 class BLInstrumentationDag : public BallLarusDag {
173 BLInstrumentationDag(Function &F);
175 // Returns the Exit->Root edge. This edge is required for creating
176 // directed cycles in the algorithm for moving instrumentation off of
178 BallLarusEdge* getExitRootEdge();
180 // Returns an array of phony edges which mark those nodes
181 // with function calls
182 BLEdgeVector getCallPhonyEdges();
184 // Gets/sets the path counter array
185 GlobalVariable* getCounterArray();
186 void setCounterArray(GlobalVariable* c);
188 // Calculates the increments for the chords, thereby removing
189 // instrumentation from the spanning tree edges. Implementation is based
190 // on the algorithm in Figure 4 of [Ball94]
191 void calculateChordIncrements();
193 // Updates the state when an edge has been split
194 void splitUpdate(BLInstrumentationEdge* formerEdge, BasicBlock* newBlock);
196 // Calculates a spanning tree of the DAG ignoring cycles. Whichever
197 // edges are in the spanning tree will not be instrumented, but this
198 // implementation does not try to minimize the instrumentation overhead
199 // by trying to find hot edges.
200 void calculateSpanningTree();
202 // Pushes initialization further down in order to group the first
203 // increment and initialization.
204 void pushInitialization();
206 // Pushes the path counter increments up in order to group the last path
210 // Removes phony edges from the successor list of the source, and the
211 // predecessor list of the target.
214 // Generate dot graph for the function
215 void generateDotGraph();
218 // BLInstrumentationDag creates BLInstrumentationNode objects in this
219 // method overriding the creation of BallLarusNode objects.
221 // Allows subclasses to determine which type of Node is created.
222 // Override this method to produce subclasses of BallLarusNode if
224 virtual BallLarusNode* createNode(BasicBlock* BB);
226 // BLInstrumentationDag create BLInstrumentationEdges.
228 // Allows subclasses to determine which type of Edge is created.
229 // Override this method to produce subclasses of BallLarusEdge if
230 // necessary. Parameters source and target will have been created by
231 // createNode and can be cast to the subclass of BallLarusNode*
232 // returned by createNode.
233 virtual BallLarusEdge* createEdge(
234 BallLarusNode* source, BallLarusNode* target, unsigned edgeNumber);
237 BLEdgeVector _treeEdges; // All edges in the spanning tree.
238 BLEdgeVector _chordEdges; // All edges not in the spanning tree.
239 GlobalVariable* _counterArray; // Array to store path counters
241 // Removes the edge from the appropriate predecessor and successor lists.
242 void unlinkEdge(BallLarusEdge* edge);
244 // Makes an edge part of the spanning tree.
245 void makeEdgeSpanning(BLInstrumentationEdge* edge);
247 // Pushes initialization and calls itself recursively.
248 void pushInitializationFromEdge(BLInstrumentationEdge* edge);
250 // Pushes path counter increments up recursively.
251 void pushCountersFromEdge(BLInstrumentationEdge* edge);
253 // Depth first algorithm for determining the chord increments.f
254 void calculateChordIncrementsDfs(
255 long weight, BallLarusNode* v, BallLarusEdge* e);
257 // Determines the relative direction of two edges.
258 int calculateChordIncrementsDir(BallLarusEdge* e, BallLarusEdge* f);
261 // ---------------------------------------------------------------------------
262 // PathProfiler is a module pass which instruments path profiling instructions
263 // ---------------------------------------------------------------------------
264 class PathProfiler : public ModulePass {
266 // Current context for multi threading support.
267 LLVMContext* Context;
269 // Which function are we currently instrumenting
270 unsigned currentFunctionNumber;
272 // The function prototype in the profiling runtime for incrementing a
273 // single path counter in a hash table.
274 Constant* llvmIncrementHashFunction;
275 Constant* llvmDecrementHashFunction;
277 // Instruments each function with path profiling. 'main' is instrumented
278 // with code to save the profile to disk.
279 bool runOnModule(Module &M);
281 // Analyzes the function for Ball-Larus path profiling, and inserts code.
282 void runOnFunction(std::vector<Constant*> &ftInit, Function &F, Module &M);
284 // Creates an increment constant representing incr.
285 ConstantInt* createIncrementConstant(long incr, int bitsize);
287 // Creates an increment constant representing the value in
288 // edge->getIncrement().
289 ConstantInt* createIncrementConstant(BLInstrumentationEdge* edge);
291 // Finds the insertion point after pathNumber in block. PathNumber may
293 BasicBlock::iterator getInsertionPoint(
294 BasicBlock* block, Value* pathNumber);
296 // Inserts source's pathNumber Value* into target. Target may or may not
297 // have multiple predecessors, and may or may not have its phiNode
299 void pushValueIntoNode(
300 BLInstrumentationNode* source, BLInstrumentationNode* target);
302 // Inserts source's pathNumber Value* into the appropriate slot of
304 void pushValueIntoPHI(
305 BLInstrumentationNode* target, BLInstrumentationNode* source);
307 // The Value* in node, oldVal, is updated with a Value* correspodning to
308 // oldVal + addition.
309 void insertNumberIncrement(BLInstrumentationNode* node, Value* addition,
312 // Creates a counter increment in the given node. The Value* in node is
313 // taken as the index into a hash table.
314 void insertCounterIncrement(
316 BasicBlock::iterator insertPoint,
317 BLInstrumentationDag* dag,
318 bool increment = true);
320 // A PHINode is created in the node, and its values initialized to -1U.
321 void preparePHI(BLInstrumentationNode* node);
323 // Inserts instrumentation for the given edge
325 // Pre: The edge's source node has pathNumber set if edge is non zero
326 // path number increment.
328 // Post: Edge's target node has a pathNumber set to the path number Value
329 // corresponding to the value of the path register after edge's
331 void insertInstrumentationStartingAt(
332 BLInstrumentationEdge* edge,
333 BLInstrumentationDag* dag);
335 // If this edge is a critical edge, then inserts a node at this edge.
336 // This edge becomes the first edge, and a new BallLarusEdge is created.
337 bool splitCritical(BLInstrumentationEdge* edge, BLInstrumentationDag* dag);
339 // Inserts instrumentation according to the marked edges in dag. Phony
340 // edges must be unlinked from the DAG, but accessible from the
341 // backedges. Dag must have initializations, path number increments, and
342 // counter increments present.
344 // Counter storage is created here.
345 void insertInstrumentation( BLInstrumentationDag& dag, Module &M);
348 static char ID; // Pass identification, replacement for typeid
349 PathProfiler() : ModulePass(ID) {
350 initializePathProfilerPass(*PassRegistry::getPassRegistry());
353 virtual const char *getPassName() const {
354 return "Path Profiler";
357 } // end anonymous namespace
359 // Should we print the dot-graphs
360 static cl::opt<bool> DotPathDag("path-profile-pathdag", cl::Hidden,
361 cl::desc("Output the path profiling DAG for each function."));
363 // Register the path profiler as a pass
364 char PathProfiler::ID = 0;
365 INITIALIZE_PASS(PathProfiler, "insert-path-profiling",
366 "Insert instrumentation for Ball-Larus path profiling",
369 ModulePass *llvm::createPathProfilerPass() { return new PathProfiler(); }
372 class PathProfilingFunctionTable {};
374 // Type for global array storing references to hashes or arrays
375 template<bool xcompile> class TypeBuilder<PathProfilingFunctionTable,
378 static const StructType *get(LLVMContext& C) {
379 return( StructType::get(
380 C, TypeBuilder<types::i<32>, xcompile>::get(C), // type
381 TypeBuilder<types::i<32>, xcompile>::get(C), // array size
382 TypeBuilder<types::i<8>*, xcompile>::get(C), // array/hash ptr
387 typedef TypeBuilder<PathProfilingFunctionTable, true>
390 // BallLarusEdge << operator overloading
391 raw_ostream& operator<<(raw_ostream& os,
392 const BLInstrumentationEdge& edge)
394 raw_ostream& operator<<(raw_ostream& os,
395 const BLInstrumentationEdge& edge) {
396 os << "[" << edge.getSource()->getName() << " -> "
397 << edge.getTarget()->getName() << "] init: "
398 << (edge.isInitialization() ? "yes" : "no")
399 << " incr:" << edge.getIncrement() << " cinc: "
400 << (edge.isCounterIncrement() ? "yes" : "no");
405 // Creates a new BLInstrumentationNode from a BasicBlock.
406 BLInstrumentationNode::BLInstrumentationNode(BasicBlock* BB) :
408 _startingPathNumber(NULL), _endingPathNumber(NULL), _pathPHI(NULL) {}
410 // Constructor for BLInstrumentationEdge.
411 BLInstrumentationEdge::BLInstrumentationEdge(BLInstrumentationNode* source,
412 BLInstrumentationNode* target)
413 : BallLarusEdge(source, target, 0),
414 _increment(0), _isInSpanningTree(false), _isInitialization(false),
415 _isCounterIncrement(false), _hasInstrumentation(false) {}
417 // Sets the target node of this edge. Required to split edges.
418 void BLInstrumentationEdge::setTarget(BallLarusNode* node) {
422 // Returns whether this edge is in the spanning tree.
423 bool BLInstrumentationEdge::isInSpanningTree() const {
424 return(_isInSpanningTree);
427 // Sets whether this edge is in the spanning tree.
428 void BLInstrumentationEdge::setIsInSpanningTree(bool isInSpanningTree) {
429 _isInSpanningTree = isInSpanningTree;
432 // Returns whether this edge will be instrumented with a path number
434 bool BLInstrumentationEdge::isInitialization() const {
435 return(_isInitialization);
438 // Sets whether this edge will be instrumented with a path number
440 void BLInstrumentationEdge::setIsInitialization(bool isInitialization) {
441 _isInitialization = isInitialization;
444 // Returns whether this edge will be instrumented with a path counter
445 // increment. Notice this is incrementing the path counter
446 // corresponding to the path number register. The path number
447 // increment is determined by getIncrement().
448 bool BLInstrumentationEdge::isCounterIncrement() const {
449 return(_isCounterIncrement);
452 // Sets whether this edge will be instrumented with a path counter
454 void BLInstrumentationEdge::setIsCounterIncrement(bool isCounterIncrement) {
455 _isCounterIncrement = isCounterIncrement;
458 // Gets the path number increment that this edge will be instrumented
459 // with. This is distinct from the path counter increment and the
460 // weight. The counter increment is counts the number of executions of
461 // some path, whereas the path number keeps track of which path number
462 // the program is on.
463 long BLInstrumentationEdge::getIncrement() const {
467 // Set whether this edge will be instrumented with a path number
469 void BLInstrumentationEdge::setIncrement(long increment) {
470 _increment = increment;
473 // True iff the edge has already been instrumented.
474 bool BLInstrumentationEdge::hasInstrumentation() {
475 return(_hasInstrumentation);
478 // Set whether this edge has been instrumented.
479 void BLInstrumentationEdge::setHasInstrumentation(bool hasInstrumentation) {
480 _hasInstrumentation = hasInstrumentation;
483 // Returns the successor number of this edge in the source.
484 unsigned BLInstrumentationEdge::getSuccessorNumber() {
485 BallLarusNode* sourceNode = getSource();
486 BallLarusNode* targetNode = getTarget();
487 BasicBlock* source = sourceNode->getBlock();
488 BasicBlock* target = targetNode->getBlock();
490 if(source == NULL || target == NULL)
493 TerminatorInst* terminator = source->getTerminator();
496 for(i=0; i < terminator->getNumSuccessors(); i++) {
497 if(terminator->getSuccessor(i) == target)
504 // BLInstrumentationDag constructor initializes a DAG for the given Function.
505 BLInstrumentationDag::BLInstrumentationDag(Function &F) : BallLarusDag(F),
509 // Returns the Exit->Root edge. This edge is required for creating
510 // directed cycles in the algorithm for moving instrumentation off of
512 BallLarusEdge* BLInstrumentationDag::getExitRootEdge() {
513 BLEdgeIterator erEdge = getExit()->succBegin();
517 BLEdgeVector BLInstrumentationDag::getCallPhonyEdges () {
518 BLEdgeVector callEdges;
520 for( BLEdgeIterator edge = _edges.begin(), end = _edges.end();
521 edge != end; edge++ ) {
522 if( (*edge)->getType() == BallLarusEdge::CALLEDGE_PHONY )
523 callEdges.push_back(*edge);
529 // Gets the path counter array
530 GlobalVariable* BLInstrumentationDag::getCounterArray() {
531 return _counterArray;
534 void BLInstrumentationDag::setCounterArray(GlobalVariable* c) {
538 // Calculates the increment for the chords, thereby removing
539 // instrumentation from the spanning tree edges. Implementation is based on
540 // the algorithm in Figure 4 of [Ball94]
541 void BLInstrumentationDag::calculateChordIncrements() {
542 calculateChordIncrementsDfs(0, getRoot(), NULL);
544 BLInstrumentationEdge* chord;
545 for(BLEdgeIterator chordEdge = _chordEdges.begin(),
546 end = _chordEdges.end(); chordEdge != end; chordEdge++) {
547 chord = (BLInstrumentationEdge*) *chordEdge;
548 chord->setIncrement(chord->getIncrement() + chord->getWeight());
552 // Updates the state when an edge has been split
553 void BLInstrumentationDag::splitUpdate(BLInstrumentationEdge* formerEdge,
554 BasicBlock* newBlock) {
555 BallLarusNode* oldTarget = formerEdge->getTarget();
556 BallLarusNode* newNode = addNode(newBlock);
557 formerEdge->setTarget(newNode);
558 newNode->addPredEdge(formerEdge);
560 DEBUG(dbgs() << " Edge split: " << *formerEdge << "\n");
562 oldTarget->removePredEdge(formerEdge);
563 BallLarusEdge* newEdge = addEdge(newNode, oldTarget,0);
565 if( formerEdge->getType() == BallLarusEdge::BACKEDGE ||
566 formerEdge->getType() == BallLarusEdge::SPLITEDGE) {
567 newEdge->setType(formerEdge->getType());
568 newEdge->setPhonyRoot(formerEdge->getPhonyRoot());
569 newEdge->setPhonyExit(formerEdge->getPhonyExit());
570 formerEdge->setType(BallLarusEdge::NORMAL);
571 formerEdge->setPhonyRoot(NULL);
572 formerEdge->setPhonyExit(NULL);
576 // Calculates a spanning tree of the DAG ignoring cycles. Whichever
577 // edges are in the spanning tree will not be instrumented, but this
578 // implementation does not try to minimize the instrumentation overhead
579 // by trying to find hot edges.
580 void BLInstrumentationDag::calculateSpanningTree() {
581 std::stack<BallLarusNode*> dfsStack;
583 for(BLNodeIterator nodeIt = _nodes.begin(), end = _nodes.end();
584 nodeIt != end; nodeIt++) {
585 (*nodeIt)->setColor(BallLarusNode::WHITE);
588 dfsStack.push(getRoot());
589 while(dfsStack.size() > 0) {
590 BallLarusNode* node = dfsStack.top();
593 if(node->getColor() == BallLarusNode::WHITE)
596 BallLarusNode* nextNode;
598 BLEdgeIterator succEnd = node->succEnd();
600 node->setColor(BallLarusNode::WHITE);
601 // first iterate over successors then predecessors
602 for(BLEdgeIterator edge = node->succBegin(), predEnd = node->predEnd();
603 edge != predEnd; edge++) {
604 if(edge == succEnd) {
605 edge = node->predBegin();
609 // Ignore split edges
610 if ((*edge)->getType() == BallLarusEdge::SPLITEDGE)
613 nextNode = forward? (*edge)->getTarget(): (*edge)->getSource();
614 if(nextNode->getColor() != BallLarusNode::WHITE) {
615 nextNode->setColor(BallLarusNode::WHITE);
616 makeEdgeSpanning((BLInstrumentationEdge*)(*edge));
621 for(BLEdgeIterator edge = _edges.begin(), end = _edges.end();
622 edge != end; edge++) {
623 BLInstrumentationEdge* instEdge = (BLInstrumentationEdge*) (*edge);
624 // safe since createEdge is overriden
625 if(!instEdge->isInSpanningTree() && (*edge)->getType()
626 != BallLarusEdge::SPLITEDGE)
627 _chordEdges.push_back(instEdge);
631 // Pushes initialization further down in order to group the first
632 // increment and initialization.
633 void BLInstrumentationDag::pushInitialization() {
634 BLInstrumentationEdge* exitRootEdge =
635 (BLInstrumentationEdge*) getExitRootEdge();
636 exitRootEdge->setIsInitialization(true);
637 pushInitializationFromEdge(exitRootEdge);
640 // Pushes the path counter increments up in order to group the last path
642 void BLInstrumentationDag::pushCounters() {
643 BLInstrumentationEdge* exitRootEdge =
644 (BLInstrumentationEdge*) getExitRootEdge();
645 exitRootEdge->setIsCounterIncrement(true);
646 pushCountersFromEdge(exitRootEdge);
649 // Removes phony edges from the successor list of the source, and the
650 // predecessor list of the target.
651 void BLInstrumentationDag::unlinkPhony() {
654 for(BLEdgeIterator next = _edges.begin(),
655 end = _edges.end(); next != end; next++) {
658 if( edge->getType() == BallLarusEdge::BACKEDGE_PHONY ||
659 edge->getType() == BallLarusEdge::SPLITEDGE_PHONY ||
660 edge->getType() == BallLarusEdge::CALLEDGE_PHONY ) {
666 // Generate a .dot graph to represent the DAG and pathNumbers
667 void BLInstrumentationDag::generateDotGraph() {
668 std::string errorInfo;
669 std::string functionName = getFunction().getNameStr();
670 std::string filename = "pathdag." + functionName + ".dot";
672 DEBUG (dbgs() << "Writing '" << filename << "'...\n");
673 raw_fd_ostream dotFile(filename.c_str(), errorInfo);
675 if (!errorInfo.empty()) {
676 errs() << "Error opening '" << filename.c_str() <<"' for writing!";
681 dotFile << "digraph " << functionName << " {\n";
683 for( BLEdgeIterator edge = _edges.begin(), end = _edges.end();
684 edge != end; edge++) {
685 std::string sourceName = (*edge)->getSource()->getName();
686 std::string targetName = (*edge)->getTarget()->getName();
688 dotFile << "\t\"" << sourceName.c_str() << "\" -> \""
689 << targetName.c_str() << "\" ";
691 long inc = ((BLInstrumentationEdge*)(*edge))->getIncrement();
693 switch( (*edge)->getType() ) {
694 case BallLarusEdge::NORMAL:
695 dotFile << "[label=" << inc << "] [color=black];\n";
698 case BallLarusEdge::BACKEDGE:
699 dotFile << "[color=cyan];\n";
702 case BallLarusEdge::BACKEDGE_PHONY:
703 dotFile << "[label=" << inc
704 << "] [color=blue];\n";
707 case BallLarusEdge::SPLITEDGE:
708 dotFile << "[color=violet];\n";
711 case BallLarusEdge::SPLITEDGE_PHONY:
712 dotFile << "[label=" << inc << "] [color=red];\n";
715 case BallLarusEdge::CALLEDGE_PHONY:
716 dotFile << "[label=" << inc << "] [color=green];\n";
724 // Allows subclasses to determine which type of Node is created.
725 // Override this method to produce subclasses of BallLarusNode if
726 // necessary. The destructor of BallLarusDag will call free on each pointer
728 BallLarusNode* BLInstrumentationDag::createNode(BasicBlock* BB) {
729 return( new BLInstrumentationNode(BB) );
732 // Allows subclasses to determine which type of Edge is created.
733 // Override this method to produce subclasses of BallLarusEdge if
734 // necessary. The destructor of BallLarusDag will call free on each pointer
736 BallLarusEdge* BLInstrumentationDag::createEdge(BallLarusNode* source,
737 BallLarusNode* target, unsigned edgeNumber) {
738 // One can cast from BallLarusNode to BLInstrumentationNode since createNode
739 // is overriden to produce BLInstrumentationNode.
740 return( new BLInstrumentationEdge((BLInstrumentationNode*)source,
741 (BLInstrumentationNode*)target) );
744 // Sets the Value corresponding to the pathNumber register, constant,
745 // or phinode. Used by the instrumentation code to remember path
747 Value* BLInstrumentationNode::getStartingPathNumber(){
748 return(_startingPathNumber);
751 // Sets the Value of the pathNumber. Used by the instrumentation code.
752 void BLInstrumentationNode::setStartingPathNumber(Value* pathNumber) {
753 DEBUG(dbgs() << " SPN-" << getName() << " <-- " << (pathNumber ?
754 pathNumber->getNameStr() : "unused") << "\n");
755 _startingPathNumber = pathNumber;
758 Value* BLInstrumentationNode::getEndingPathNumber(){
759 return(_endingPathNumber);
762 void BLInstrumentationNode::setEndingPathNumber(Value* pathNumber) {
763 DEBUG(dbgs() << " EPN-" << getName() << " <-- "
764 << (pathNumber ? pathNumber->getNameStr() : "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->getFirstNonPHI());
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->getFirstNonPHI();
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->getFirstNonPHI();
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(),
1034 gepIndices.begin(), gepIndices.end(),
1035 "counterInc", insertPoint);
1037 // Load from the array - call it oldPC
1038 LoadInst* oldPc = new LoadInst(pcPointer, "oldPC", insertPoint);
1040 // Test to see whether adding 1 will overflow the counter
1041 ICmpInst* isMax = new ICmpInst(insertPoint, CmpInst::ICMP_ULT, oldPc,
1042 createIncrementConstant(0xffffffff, 32),
1045 // Select increment for the path counter based on overflow
1047 SelectInst::Create( isMax, createIncrementConstant(increment?1:-1,32),
1048 createIncrementConstant(0,32),
1049 "pathInc", insertPoint);
1051 // newPc = oldPc + inc
1052 BinaryOperator* newPc = BinaryOperator::Create(Instruction::Add,
1053 oldPc, inc, "newPC",
1056 // Store back in to the array
1057 new StoreInst(newPc, pcPointer, insertPoint);
1058 } else { // Counter increment for hash
1059 std::vector<Value*> args(2);
1060 args[0] = ConstantInt::get(Type::getInt32Ty(*Context),
1061 currentFunctionNumber);
1065 increment ? llvmIncrementHashFunction : llvmDecrementHashFunction,
1066 args.begin(), args.end(), "", insertPoint);
1070 // Inserts instrumentation for the given edge
1072 // Pre: The edge's source node has pathNumber set if edge is non zero
1073 // path number increment.
1075 // Post: Edge's target node has a pathNumber set to the path number Value
1076 // corresponding to the value of the path register after edge's
1079 // FIXME: This should be reworked so it's not recursive.
1080 void PathProfiler::insertInstrumentationStartingAt(BLInstrumentationEdge* edge,
1081 BLInstrumentationDag* dag) {
1082 // Mark the edge as instrumented
1083 edge->setHasInstrumentation(true);
1084 DEBUG(dbgs() << "\nInstrumenting edge: " << (*edge) << "\n");
1086 // create a new node for this edge's instrumentation
1087 splitCritical(edge, dag);
1089 BLInstrumentationNode* sourceNode = (BLInstrumentationNode*)edge->getSource();
1090 BLInstrumentationNode* targetNode = (BLInstrumentationNode*)edge->getTarget();
1091 BLInstrumentationNode* instrumentNode;
1092 BLInstrumentationNode* nextSourceNode;
1094 bool atBeginning = false;
1096 // Source node has only 1 successor so any information can be simply
1097 // inserted in to it without splitting
1098 if( sourceNode->getBlock() && sourceNode->getNumberSuccEdges() <= 1) {
1099 DEBUG(dbgs() << " Potential instructions to be placed in: "
1100 << sourceNode->getName() << " (at end)\n");
1101 instrumentNode = sourceNode;
1102 nextSourceNode = targetNode; // ... since we never made any new nodes
1105 // The target node only has one predecessor, so we can safely insert edge
1106 // instrumentation into it. If there was splitting, it must have been
1108 else if( targetNode->getNumberPredEdges() == 1 ) {
1109 DEBUG(dbgs() << " Potential instructions to be placed in: "
1110 << targetNode->getName() << " (at beginning)\n");
1111 pushValueIntoNode(sourceNode, targetNode);
1112 instrumentNode = targetNode;
1113 nextSourceNode = NULL; // ... otherwise we'll just keep splitting
1117 // Somehow, splitting must have failed.
1119 errs() << "Instrumenting could not split a critical edge.\n";
1120 DEBUG(dbgs() << " Couldn't split edge " << (*edge) << ".\n");
1124 // Insert instrumentation if this is a back or split edge
1125 if( edge->getType() == BallLarusEdge::BACKEDGE ||
1126 edge->getType() == BallLarusEdge::SPLITEDGE ) {
1127 BLInstrumentationEdge* top =
1128 (BLInstrumentationEdge*) edge->getPhonyRoot();
1129 BLInstrumentationEdge* bottom =
1130 (BLInstrumentationEdge*) edge->getPhonyExit();
1132 assert( top->isInitialization() && " Top phony edge did not"
1133 " contain a path number initialization.");
1134 assert( bottom->isCounterIncrement() && " Bottom phony edge"
1135 " did not contain a path counter increment.");
1137 // split edge has yet to be initialized
1138 if( !instrumentNode->getEndingPathNumber() ) {
1139 instrumentNode->setStartingPathNumber(createIncrementConstant(0,32));
1140 instrumentNode->setEndingPathNumber(createIncrementConstant(0,32));
1143 BasicBlock::iterator insertPoint = atBeginning ?
1144 instrumentNode->getBlock()->getFirstNonPHI() :
1145 instrumentNode->getBlock()->getTerminator();
1147 // add information from the bottom edge, if it exists
1148 if( bottom->getIncrement() ) {
1150 BinaryOperator::Create(Instruction::Add,
1151 instrumentNode->getStartingPathNumber(),
1152 createIncrementConstant(bottom),
1153 "pathNumber", insertPoint);
1154 instrumentNode->setEndingPathNumber(newpn);
1157 insertCounterIncrement(instrumentNode->getEndingPathNumber(),
1161 instrumentNode->setStartingPathNumber(createIncrementConstant(top));
1163 instrumentNode->setEndingPathNumber(createIncrementConstant(top));
1165 // Check for path counter increments
1166 if( top->isCounterIncrement() ) {
1167 insertCounterIncrement(instrumentNode->getEndingPathNumber(),
1168 instrumentNode->getBlock()->getTerminator(),dag);
1169 instrumentNode->setEndingPathNumber(0);
1173 // Insert instrumentation if this is a normal edge
1175 BasicBlock::iterator insertPoint = atBeginning ?
1176 instrumentNode->getBlock()->getFirstNonPHI() :
1177 instrumentNode->getBlock()->getTerminator();
1179 if( edge->isInitialization() ) { // initialize path number
1180 instrumentNode->setEndingPathNumber(createIncrementConstant(edge));
1181 } else if( edge->getIncrement() ) {// increment path number
1183 BinaryOperator::Create(Instruction::Add,
1184 instrumentNode->getStartingPathNumber(),
1185 createIncrementConstant(edge),
1186 "pathNumber", insertPoint);
1187 instrumentNode->setEndingPathNumber(newpn);
1190 instrumentNode->setStartingPathNumber(newpn);
1193 // Check for path counter increments
1194 if( edge->isCounterIncrement() ) {
1195 insertCounterIncrement(instrumentNode->getEndingPathNumber(),
1197 instrumentNode->setEndingPathNumber(0);
1202 if (nextSourceNode && instrumentNode->getEndingPathNumber())
1203 pushValueIntoNode(instrumentNode, nextSourceNode);
1205 // Add all the successors
1206 for( BLEdgeIterator next = targetNode->succBegin(),
1207 end = targetNode->succEnd(); next != end; next++ ) {
1208 // So long as it is un-instrumented, add it to the list
1209 if( !((BLInstrumentationEdge*)(*next))->hasInstrumentation() )
1210 insertInstrumentationStartingAt((BLInstrumentationEdge*)*next,dag);
1212 DEBUG(dbgs() << " Edge " << *(BLInstrumentationEdge*)(*next)
1213 << " already instrumented.\n");
1217 // Inserts instrumentation according to the marked edges in dag. Phony edges
1218 // must be unlinked from the DAG, but accessible from the backedges. Dag
1219 // must have initializations, path number increments, and counter increments
1222 // Counter storage is created here.
1223 void PathProfiler::insertInstrumentation(
1224 BLInstrumentationDag& dag, Module &M) {
1226 BLInstrumentationEdge* exitRootEdge =
1227 (BLInstrumentationEdge*) dag.getExitRootEdge();
1228 insertInstrumentationStartingAt(exitRootEdge, &dag);
1230 // Iterate through each call edge and apply the appropriate hash increment
1231 // and decrement functions
1232 BLEdgeVector callEdges = dag.getCallPhonyEdges();
1233 for( BLEdgeIterator edge = callEdges.begin(),
1234 end = callEdges.end(); edge != end; edge++ ) {
1235 BLInstrumentationNode* node =
1236 (BLInstrumentationNode*)(*edge)->getSource();
1237 BasicBlock::iterator insertPoint = node->getBlock()->getFirstNonPHI();
1239 // Find the first function call
1240 while( ((Instruction&)(*insertPoint)).getOpcode() != Instruction::Call )
1243 DEBUG(dbgs() << "\nInstrumenting method call block '"
1244 << node->getBlock()->getNameStr() << "'\n");
1245 DEBUG(dbgs() << " Path number initialized: "
1246 << ((node->getStartingPathNumber()) ? "yes" : "no") << "\n");
1249 if( node->getStartingPathNumber() ) {
1250 long inc = ((BLInstrumentationEdge*)(*edge))->getIncrement();
1252 newpn = BinaryOperator::Create(Instruction::Add,
1253 node->getStartingPathNumber(),
1254 createIncrementConstant(inc,32),
1255 "pathNumber", insertPoint);
1257 newpn = node->getStartingPathNumber();
1259 newpn = (Value*)createIncrementConstant(
1260 ((BLInstrumentationEdge*)(*edge))->getIncrement(), 32);
1263 insertCounterIncrement(newpn, insertPoint, &dag);
1264 insertCounterIncrement(newpn, node->getBlock()->getTerminator(),
1269 // Entry point of the module
1270 void PathProfiler::runOnFunction(std::vector<Constant*> &ftInit,
1271 Function &F, Module &M) {
1272 // Build DAG from CFG
1273 BLInstrumentationDag dag = BLInstrumentationDag(F);
1276 // give each path a unique integer value
1277 dag.calculatePathNumbers();
1279 // modify path increments to increase the efficiency
1280 // of instrumentation
1281 dag.calculateSpanningTree();
1282 dag.calculateChordIncrements();
1283 dag.pushInitialization();
1287 // potentially generate .dot graph for the dag
1289 dag.generateDotGraph ();
1291 // Should we store the information in an array or hash
1292 if( dag.getNumberOfPaths() <= HASH_THRESHHOLD ) {
1293 const Type* t = ArrayType::get(Type::getInt32Ty(*Context),
1294 dag.getNumberOfPaths());
1296 dag.setCounterArray(new GlobalVariable(M, t, false,
1297 GlobalValue::InternalLinkage,
1298 Constant::getNullValue(t), ""));
1301 insertInstrumentation(dag, M);
1303 // Add to global function reference table
1305 const Type* voidPtr = TypeBuilder<types::i<8>*, true>::get(*Context);
1307 if( dag.getNumberOfPaths() <= HASH_THRESHHOLD )
1308 type = ProfilingArray;
1310 type = ProfilingHash;
1312 std::vector<Constant*> entryArray(3);
1313 entryArray[0] = createIncrementConstant(type,32);
1314 entryArray[1] = createIncrementConstant(dag.getNumberOfPaths(),32);
1315 entryArray[2] = dag.getCounterArray() ?
1316 ConstantExpr::getBitCast(dag.getCounterArray(), voidPtr) :
1317 Constant::getNullValue(voidPtr);
1319 const StructType* at = ftEntryTypeBuilder::get(*Context);
1320 ConstantStruct* functionEntry =
1321 (ConstantStruct*)ConstantStruct::get(at, entryArray);
1322 ftInit.push_back(functionEntry);
1325 // Output the bitcode if we want to observe instrumentation changess
1326 #define PRINT_MODULE dbgs() << \
1327 "\n\n============= MODULE BEGIN ===============\n" << M << \
1328 "\n============== MODULE END ================\n"
1330 bool PathProfiler::runOnModule(Module &M) {
1331 Context = &M.getContext();
1334 << "****************************************\n"
1335 << "****************************************\n"
1337 << "** PATH PROFILING INSTRUMENTATION **\n"
1339 << "****************************************\n"
1340 << "****************************************\n");
1342 // No main, no instrumentation!
1343 Function *Main = M.getFunction("main");
1345 // Using fortran? ... this kind of works
1347 Main = M.getFunction("MAIN__");
1350 errs() << "WARNING: cannot insert path profiling into a module"
1351 << " with no main function!\n";
1355 BasicBlock::iterator insertPoint = Main->getEntryBlock().getFirstNonPHI();
1357 llvmIncrementHashFunction = M.getOrInsertFunction(
1358 "llvm_increment_path_count",
1359 Type::getVoidTy(*Context), // return type
1360 Type::getInt32Ty(*Context), // function number
1361 Type::getInt32Ty(*Context), // path number
1364 llvmDecrementHashFunction = M.getOrInsertFunction(
1365 "llvm_decrement_path_count",
1366 Type::getVoidTy(*Context), // return type
1367 Type::getInt32Ty(*Context), // function number
1368 Type::getInt32Ty(*Context), // path number
1371 std::vector<Constant*> ftInit;
1372 unsigned functionNumber = 0;
1373 for (Module::iterator F = M.begin(), E = M.end(); F != E; F++) {
1374 if (F->isDeclaration())
1377 DEBUG(dbgs() << "Function: " << F->getNameStr() << "\n");
1380 // set function number
1381 currentFunctionNumber = functionNumber;
1382 runOnFunction(ftInit, *F, M);
1385 const Type *t = ftEntryTypeBuilder::get(*Context);
1386 const ArrayType* ftArrayType = ArrayType::get(t, ftInit.size());
1387 Constant* ftInitConstant = ConstantArray::get(ftArrayType, ftInit);
1389 DEBUG(dbgs() << " ftArrayType:" << *ftArrayType << "\n");
1391 GlobalVariable* functionTable =
1392 new GlobalVariable(M, ftArrayType, false, GlobalValue::InternalLinkage,
1393 ftInitConstant, "functionPathTable");
1394 const Type *eltType = ftArrayType->getTypeAtIndex((unsigned)0);
1395 InsertProfilingInitCall(Main, "llvm_start_path_profiling", functionTable,
1396 PointerType::getUnqual(eltType));
1398 DEBUG(PRINT_MODULE);
1403 // If this edge is a critical edge, then inserts a node at this edge.
1404 // This edge becomes the first edge, and a new BallLarusEdge is created.
1405 // Returns true if the edge was split
1406 bool PathProfiler::splitCritical(BLInstrumentationEdge* edge,
1407 BLInstrumentationDag* dag) {
1408 unsigned succNum = edge->getSuccessorNumber();
1409 BallLarusNode* sourceNode = edge->getSource();
1410 BallLarusNode* targetNode = edge->getTarget();
1411 BasicBlock* sourceBlock = sourceNode->getBlock();
1412 BasicBlock* targetBlock = targetNode->getBlock();
1414 if(sourceBlock == NULL || targetBlock == NULL
1415 || sourceNode->getNumberSuccEdges() <= 1
1416 || targetNode->getNumberPredEdges() == 1 ) {
1420 TerminatorInst* terminator = sourceBlock->getTerminator();
1422 if( SplitCriticalEdge(terminator, succNum, this, false)) {
1423 BasicBlock* newBlock = terminator->getSuccessor(succNum);
1424 dag->splitUpdate(edge, newBlock);