• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- PathProfiling.cpp - Inserts counters for path profiling ------------===//
2 //
3 //                      The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // 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
16 // exit.
17 //
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
22 // tree to chords.
23 //
24 // Terms:
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
30 //                  Ball-Larus DAG.
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.
34 //
35 // [Ball96]
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
39 //
40 // [Ball94]
41 //  Thomas Ball.  "Efficiently Counting Program Events with Support for
42 //  On-line queries."
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"
47 
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"
66 #include <vector>
67 
68 #define HASH_THRESHHOLD 100000
69 
70 using namespace llvm;
71 
72 namespace {
73 class BLInstrumentationNode;
74 class BLInstrumentationEdge;
75 class BLInstrumentationDag;
76 
77 // ---------------------------------------------------------------------------
78 // BLInstrumentationNode extends BallLarusNode with member used by the
79 // instrumentation algortihms.
80 // ---------------------------------------------------------------------------
81 class BLInstrumentationNode : public BallLarusNode {
82 public:
83   // Creates a new BLInstrumentationNode from a BasicBlock.
84   BLInstrumentationNode(BasicBlock* BB);
85 
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);
91 
92   Value* getEndingPathNumber();
93   void setEndingPathNumber(Value* pathNumber);
94 
95   // Get/set the PHINode Instruction for this node.
96   PHINode* getPathPHI();
97   void setPathPHI(PHINode* pathPHI);
98 
99 private:
100 
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.
104 };
105 
106 // --------------------------------------------------------------------------
107 // BLInstrumentationEdge extends BallLarusEdge with data about the
108 // instrumentation that will end up on each edge.
109 // --------------------------------------------------------------------------
110 class BLInstrumentationEdge : public BallLarusEdge {
111 public:
112   BLInstrumentationEdge(BLInstrumentationNode* source,
113                         BLInstrumentationNode* target);
114 
115   // Sets the target node of this edge.  Required to split edges.
116   void setTarget(BallLarusNode* node);
117 
118   // Get/set whether edge is in the spanning tree.
119   bool isInSpanningTree() const;
120   void setIsInSpanningTree(bool isInSpanningTree);
121 
122   // Get/ set whether this edge will be instrumented with a path number
123   // initialization.
124   bool isInitialization() const;
125   void setIsInitialization(bool isInitialization);
126 
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);
133 
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);
141 
142   // Get/set whether the edge has been instrumented.
143   bool hasInstrumentation();
144   void setHasInstrumentation(bool hasInstrumentation);
145 
146   // Returns the successor number of this edge in the source.
147   unsigned getSuccessorNumber();
148 
149 private:
150   // The increment that the code will be instrumented with.
151   long long _increment;
152 
153   // Whether this edge is in the spanning tree.
154   bool _isInSpanningTree;
155 
156   // Whether this edge is an initialiation of the path number.
157   bool _isInitialization;
158 
159   // Whether this edge is a path counter increment.
160   bool _isCounterIncrement;
161 
162   // Whether this edge has been instrumented.
163   bool _hasInstrumentation;
164 };
165 
166 // ---------------------------------------------------------------------------
167 // BLInstrumentationDag extends BallLarusDag with algorithms that
168 // determine where instrumentation should be placed.
169 // ---------------------------------------------------------------------------
170 class BLInstrumentationDag : public BallLarusDag {
171 public:
172   BLInstrumentationDag(Function &F);
173 
174   // Returns the Exit->Root edge. This edge is required for creating
175   // directed cycles in the algorithm for moving instrumentation off of
176   // the spanning tree
177   BallLarusEdge* getExitRootEdge();
178 
179   // Returns an array of phony edges which mark those nodes
180   // with function calls
181   BLEdgeVector getCallPhonyEdges();
182 
183   // Gets/sets the path counter array
184   GlobalVariable* getCounterArray();
185   void setCounterArray(GlobalVariable* c);
186 
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();
191 
192   // Updates the state when an edge has been split
193   void splitUpdate(BLInstrumentationEdge* formerEdge, BasicBlock* newBlock);
194 
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();
200 
201   // Pushes initialization further down in order to group the first
202   // increment and initialization.
203   void pushInitialization();
204 
205   // Pushes the path counter increments up in order to group the last path
206   // number increment.
207   void pushCounters();
208 
209   // Removes phony edges from the successor list of the source, and the
210   // predecessor list of the target.
211   void unlinkPhony();
212 
213   // Generate dot graph for the function
214   void generateDotGraph();
215 
216 protected:
217   // BLInstrumentationDag creates BLInstrumentationNode objects in this
218   // method overriding the creation of BallLarusNode objects.
219   //
220   // Allows subclasses to determine which type of Node is created.
221   // Override this method to produce subclasses of BallLarusNode if
222   // necessary.
223   virtual BallLarusNode* createNode(BasicBlock* BB);
224 
225   // BLInstrumentationDag create BLInstrumentationEdges.
226   //
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);
234 
235 private:
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
239 
240   // Removes the edge from the appropriate predecessor and successor lists.
241   void unlinkEdge(BallLarusEdge* edge);
242 
243   // Makes an edge part of the spanning tree.
244   void makeEdgeSpanning(BLInstrumentationEdge* edge);
245 
246   // Pushes initialization and calls itself recursively.
247   void pushInitializationFromEdge(BLInstrumentationEdge* edge);
248 
249   // Pushes path counter increments up recursively.
250   void pushCountersFromEdge(BLInstrumentationEdge* edge);
251 
252   // Depth first algorithm for determining the chord increments.f
253   void calculateChordIncrementsDfs(
254     long weight, BallLarusNode* v, BallLarusEdge* e);
255 
256   // Determines the relative direction of two edges.
257   int calculateChordIncrementsDir(BallLarusEdge* e, BallLarusEdge* f);
258 };
259 
260 // ---------------------------------------------------------------------------
261 // PathProfiler is a module pass which instruments path profiling instructions
262 // ---------------------------------------------------------------------------
263 class PathProfiler : public ModulePass {
264 private:
265   // Current context for multi threading support.
266   LLVMContext* Context;
267 
268   // Which function are we currently instrumenting
269   unsigned currentFunctionNumber;
270 
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;
275 
276   // Instruments each function with path profiling.  'main' is instrumented
277   // with code to save the profile to disk.
278   bool runOnModule(Module &M);
279 
280   // Analyzes the function for Ball-Larus path profiling, and inserts code.
281   void runOnFunction(std::vector<Constant*> &ftInit, Function &F, Module &M);
282 
283   // Creates an increment constant representing incr.
284   ConstantInt* createIncrementConstant(long incr, int bitsize);
285 
286   // Creates an increment constant representing the value in
287   // edge->getIncrement().
288   ConstantInt* createIncrementConstant(BLInstrumentationEdge* edge);
289 
290   // Finds the insertion point after pathNumber in block.  PathNumber may
291   // be NULL.
292   BasicBlock::iterator getInsertionPoint(
293     BasicBlock* block, Value* pathNumber);
294 
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
297   // initalized.
298   void pushValueIntoNode(
299     BLInstrumentationNode* source, BLInstrumentationNode* target);
300 
301   // Inserts source's pathNumber Value* into the appropriate slot of
302   // target's phiNode.
303   void pushValueIntoPHI(
304     BLInstrumentationNode* target, BLInstrumentationNode* source);
305 
306   // The Value* in node, oldVal,  is updated with a Value* correspodning to
307   // oldVal + addition.
308   void insertNumberIncrement(BLInstrumentationNode* node, Value* addition,
309                              bool atBeginning);
310 
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(
314     Value* incValue,
315     BasicBlock::iterator insertPoint,
316     BLInstrumentationDag* dag,
317     bool increment = true);
318 
319   // A PHINode is created in the node, and its values initialized to -1U.
320   void preparePHI(BLInstrumentationNode* node);
321 
322   // Inserts instrumentation for the given edge
323   //
324   // Pre: The edge's source node has pathNumber set if edge is non zero
325   // path number increment.
326   //
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
329   // execution.
330   void insertInstrumentationStartingAt(
331     BLInstrumentationEdge* edge,
332     BLInstrumentationDag* dag);
333 
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);
337 
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.
342   //
343   // Counter storage is created here.
344   void insertInstrumentation( BLInstrumentationDag& dag, Module &M);
345 
346 public:
347   static char ID; // Pass identification, replacement for typeid
PathProfiler()348   PathProfiler() : ModulePass(ID) {
349     initializePathProfilerPass(*PassRegistry::getPassRegistry());
350   }
351 
getPassName() const352   virtual const char *getPassName() const {
353     return "Path Profiler";
354   }
355 };
356 } // end anonymous namespace
357 
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."));
361 
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",
366                 false, false)
367 
createPathProfilerPass()368 ModulePass *llvm::createPathProfilerPass() { return new PathProfiler(); }
369 
370 namespace llvm {
371   class PathProfilingFunctionTable {};
372 
373   // Type for global array storing references to hashes or arrays
374   template<bool xcompile> class TypeBuilder<PathProfilingFunctionTable,
375                                             xcompile> {
376   public:
get(LLVMContext & C)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
382                 NULL));
383     }
384   };
385 
386   typedef TypeBuilder<PathProfilingFunctionTable, true>
387   ftEntryTypeBuilder;
388 
389   // BallLarusEdge << operator overloading
390   raw_ostream& operator<<(raw_ostream& os,
391                           const BLInstrumentationEdge& edge)
392       LLVM_ATTRIBUTE_USED;
operator <<(raw_ostream & os,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");
400     return(os);
401   }
402 }
403 
404 // Creates a new BLInstrumentationNode from a BasicBlock.
BLInstrumentationNode(BasicBlock * BB)405 BLInstrumentationNode::BLInstrumentationNode(BasicBlock* BB) :
406   BallLarusNode(BB),
407   _startingPathNumber(NULL), _endingPathNumber(NULL), _pathPHI(NULL) {}
408 
409 // Constructor for BLInstrumentationEdge.
BLInstrumentationEdge(BLInstrumentationNode * source,BLInstrumentationNode * target)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) {}
415 
416 // Sets the target node of this edge.  Required to split edges.
setTarget(BallLarusNode * node)417 void BLInstrumentationEdge::setTarget(BallLarusNode* node) {
418   _target = node;
419 }
420 
421 // Returns whether this edge is in the spanning tree.
isInSpanningTree() const422 bool BLInstrumentationEdge::isInSpanningTree() const {
423   return(_isInSpanningTree);
424 }
425 
426 // Sets whether this edge is in the spanning tree.
setIsInSpanningTree(bool isInSpanningTree)427 void BLInstrumentationEdge::setIsInSpanningTree(bool isInSpanningTree) {
428   _isInSpanningTree = isInSpanningTree;
429 }
430 
431 // Returns whether this edge will be instrumented with a path number
432 // initialization.
isInitialization() const433 bool BLInstrumentationEdge::isInitialization() const {
434   return(_isInitialization);
435 }
436 
437 // Sets whether this edge will be instrumented with a path number
438 // initialization.
setIsInitialization(bool isInitialization)439 void BLInstrumentationEdge::setIsInitialization(bool isInitialization) {
440   _isInitialization = isInitialization;
441 }
442 
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().
isCounterIncrement() const447 bool BLInstrumentationEdge::isCounterIncrement() const {
448   return(_isCounterIncrement);
449 }
450 
451 // Sets whether this edge will be instrumented with a path counter
452 // increment.
setIsCounterIncrement(bool isCounterIncrement)453 void BLInstrumentationEdge::setIsCounterIncrement(bool isCounterIncrement) {
454   _isCounterIncrement = isCounterIncrement;
455 }
456 
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.
getIncrement() const462 long BLInstrumentationEdge::getIncrement() const {
463   return(_increment);
464 }
465 
466 // Set whether this edge will be instrumented with a path number
467 // increment.
setIncrement(long increment)468 void BLInstrumentationEdge::setIncrement(long increment) {
469   _increment = increment;
470 }
471 
472 // True iff the edge has already been instrumented.
hasInstrumentation()473 bool BLInstrumentationEdge::hasInstrumentation() {
474   return(_hasInstrumentation);
475 }
476 
477 // Set whether this edge has been instrumented.
setHasInstrumentation(bool hasInstrumentation)478 void BLInstrumentationEdge::setHasInstrumentation(bool hasInstrumentation) {
479   _hasInstrumentation = hasInstrumentation;
480 }
481 
482 // Returns the successor number of this edge in the source.
getSuccessorNumber()483 unsigned BLInstrumentationEdge::getSuccessorNumber() {
484   BallLarusNode* sourceNode = getSource();
485   BallLarusNode* targetNode = getTarget();
486   BasicBlock* source = sourceNode->getBlock();
487   BasicBlock* target = targetNode->getBlock();
488 
489   if(source == NULL || target == NULL)
490     return(0);
491 
492   TerminatorInst* terminator = source->getTerminator();
493 
494         unsigned i;
495   for(i=0; i < terminator->getNumSuccessors(); i++) {
496     if(terminator->getSuccessor(i) == target)
497       break;
498   }
499 
500   return(i);
501 }
502 
503 // BLInstrumentationDag constructor initializes a DAG for the given Function.
BLInstrumentationDag(Function & F)504 BLInstrumentationDag::BLInstrumentationDag(Function &F) : BallLarusDag(F),
505                                                           _counterArray(0) {
506 }
507 
508 // Returns the Exit->Root edge. This edge is required for creating
509 // directed cycles in the algorithm for moving instrumentation off of
510 // the spanning tree
getExitRootEdge()511 BallLarusEdge* BLInstrumentationDag::getExitRootEdge() {
512   BLEdgeIterator erEdge = getExit()->succBegin();
513   return(*erEdge);
514 }
515 
getCallPhonyEdges()516 BLEdgeVector BLInstrumentationDag::getCallPhonyEdges () {
517   BLEdgeVector callEdges;
518 
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);
523   }
524 
525   return callEdges;
526 }
527 
528 // Gets the path counter array
getCounterArray()529 GlobalVariable* BLInstrumentationDag::getCounterArray() {
530   return _counterArray;
531 }
532 
setCounterArray(GlobalVariable * c)533 void BLInstrumentationDag::setCounterArray(GlobalVariable* c) {
534   _counterArray = c;
535 }
536 
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]
calculateChordIncrements()540 void BLInstrumentationDag::calculateChordIncrements() {
541   calculateChordIncrementsDfs(0, getRoot(), NULL);
542 
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());
548   }
549 }
550 
551 // Updates the state when an edge has been split
splitUpdate(BLInstrumentationEdge * formerEdge,BasicBlock * newBlock)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);
558 
559   DEBUG(dbgs() << "  Edge split: " << *formerEdge << "\n");
560 
561   oldTarget->removePredEdge(formerEdge);
562   BallLarusEdge* newEdge = addEdge(newNode, oldTarget,0);
563 
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);
572   }
573 }
574 
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.
calculateSpanningTree()579 void BLInstrumentationDag::calculateSpanningTree() {
580   std::stack<BallLarusNode*> dfsStack;
581 
582   for(BLNodeIterator nodeIt = _nodes.begin(), end = _nodes.end();
583       nodeIt != end; nodeIt++) {
584     (*nodeIt)->setColor(BallLarusNode::WHITE);
585   }
586 
587   dfsStack.push(getRoot());
588   while(dfsStack.size() > 0) {
589     BallLarusNode* node = dfsStack.top();
590     dfsStack.pop();
591 
592     if(node->getColor() == BallLarusNode::WHITE)
593       continue;
594 
595     BallLarusNode* nextNode;
596     bool forward = true;
597     BLEdgeIterator succEnd = node->succEnd();
598 
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();
605         forward = false;
606       }
607 
608       // Ignore split edges
609       if ((*edge)->getType() == BallLarusEdge::SPLITEDGE)
610         continue;
611 
612       nextNode = forward? (*edge)->getTarget(): (*edge)->getSource();
613       if(nextNode->getColor() != BallLarusNode::WHITE) {
614         nextNode->setColor(BallLarusNode::WHITE);
615         makeEdgeSpanning((BLInstrumentationEdge*)(*edge));
616       }
617     }
618   }
619 
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);
627   }
628 }
629 
630 // Pushes initialization further down in order to group the first
631 // increment and initialization.
pushInitialization()632 void BLInstrumentationDag::pushInitialization() {
633   BLInstrumentationEdge* exitRootEdge =
634                 (BLInstrumentationEdge*) getExitRootEdge();
635   exitRootEdge->setIsInitialization(true);
636   pushInitializationFromEdge(exitRootEdge);
637 }
638 
639 // Pushes the path counter increments up in order to group the last path
640 // number increment.
pushCounters()641 void BLInstrumentationDag::pushCounters() {
642   BLInstrumentationEdge* exitRootEdge =
643     (BLInstrumentationEdge*) getExitRootEdge();
644   exitRootEdge->setIsCounterIncrement(true);
645   pushCountersFromEdge(exitRootEdge);
646 }
647 
648 // Removes phony edges from the successor list of the source, and the
649 // predecessor list of the target.
unlinkPhony()650 void BLInstrumentationDag::unlinkPhony() {
651   BallLarusEdge* edge;
652 
653   for(BLEdgeIterator next = _edges.begin(),
654       end = _edges.end(); next != end; next++) {
655     edge = (*next);
656 
657     if( edge->getType() == BallLarusEdge::BACKEDGE_PHONY ||
658         edge->getType() == BallLarusEdge::SPLITEDGE_PHONY ||
659         edge->getType() == BallLarusEdge::CALLEDGE_PHONY ) {
660       unlinkEdge(edge);
661     }
662   }
663 }
664 
665 // Generate a .dot graph to represent the DAG and pathNumbers
generateDotGraph()666 void BLInstrumentationDag::generateDotGraph() {
667   std::string errorInfo;
668   std::string functionName = getFunction().getNameStr();
669   std::string filename = "pathdag." + functionName + ".dot";
670 
671   DEBUG (dbgs() << "Writing '" << filename << "'...\n");
672   raw_fd_ostream dotFile(filename.c_str(), errorInfo);
673 
674   if (!errorInfo.empty()) {
675     errs() << "Error opening '" << filename.c_str() <<"' for writing!";
676     errs() << "\n";
677     return;
678   }
679 
680   dotFile << "digraph " << functionName << " {\n";
681 
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();
686 
687     dotFile << "\t\"" << sourceName.c_str() << "\" -> \""
688             << targetName.c_str() << "\" ";
689 
690     long inc = ((BLInstrumentationEdge*)(*edge))->getIncrement();
691 
692     switch( (*edge)->getType() ) {
693     case BallLarusEdge::NORMAL:
694       dotFile << "[label=" << inc << "] [color=black];\n";
695       break;
696 
697     case BallLarusEdge::BACKEDGE:
698       dotFile << "[color=cyan];\n";
699       break;
700 
701     case BallLarusEdge::BACKEDGE_PHONY:
702       dotFile << "[label=" << inc
703               << "] [color=blue];\n";
704       break;
705 
706     case BallLarusEdge::SPLITEDGE:
707       dotFile << "[color=violet];\n";
708       break;
709 
710     case BallLarusEdge::SPLITEDGE_PHONY:
711       dotFile << "[label=" << inc << "] [color=red];\n";
712       break;
713 
714     case BallLarusEdge::CALLEDGE_PHONY:
715       dotFile << "[label=" << inc     << "] [color=green];\n";
716       break;
717     }
718   }
719 
720   dotFile << "}\n";
721 }
722 
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
726 // created.
createNode(BasicBlock * BB)727 BallLarusNode* BLInstrumentationDag::createNode(BasicBlock* BB) {
728   return( new BLInstrumentationNode(BB) );
729 }
730 
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
734 // created.
createEdge(BallLarusNode * source,BallLarusNode * target,unsigned edgeNumber)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) );
741 }
742 
743 // Sets the Value corresponding to the pathNumber register, constant,
744 // or phinode.  Used by the instrumentation code to remember path
745 // number Values.
getStartingPathNumber()746 Value* BLInstrumentationNode::getStartingPathNumber(){
747   return(_startingPathNumber);
748 }
749 
750 // Sets the Value of the pathNumber.  Used by the instrumentation code.
setStartingPathNumber(Value * pathNumber)751 void BLInstrumentationNode::setStartingPathNumber(Value* pathNumber) {
752   DEBUG(dbgs() << "  SPN-" << getName() << " <-- " << (pathNumber ?
753                                                        pathNumber->getNameStr() : "unused") << "\n");
754   _startingPathNumber = pathNumber;
755 }
756 
getEndingPathNumber()757 Value* BLInstrumentationNode::getEndingPathNumber(){
758   return(_endingPathNumber);
759 }
760 
setEndingPathNumber(Value * pathNumber)761 void BLInstrumentationNode::setEndingPathNumber(Value* pathNumber) {
762   DEBUG(dbgs() << "  EPN-" << getName() << " <-- "
763         << (pathNumber ? pathNumber->getNameStr() : "unused") << "\n");
764   _endingPathNumber = pathNumber;
765 }
766 
767 // Get the PHINode Instruction for this node.  Used by instrumentation
768 // code.
getPathPHI()769 PHINode* BLInstrumentationNode::getPathPHI() {
770   return(_pathPHI);
771 }
772 
773 // Set the PHINode Instruction for this node.  Used by instrumentation
774 // code.
setPathPHI(PHINode * pathPHI)775 void BLInstrumentationNode::setPathPHI(PHINode* pathPHI) {
776   _pathPHI = pathPHI;
777 }
778 
779 // Removes the edge from the appropriate predecessor and successor
780 // lists.
unlinkEdge(BallLarusEdge * edge)781 void BLInstrumentationDag::unlinkEdge(BallLarusEdge* edge) {
782   if(edge == getExitRootEdge())
783     DEBUG(dbgs() << " Removing exit->root edge\n");
784 
785   edge->getSource()->removeSuccEdge(edge);
786   edge->getTarget()->removePredEdge(edge);
787 }
788 
789 // Makes an edge part of the spanning tree.
makeEdgeSpanning(BLInstrumentationEdge * edge)790 void BLInstrumentationDag::makeEdgeSpanning(BLInstrumentationEdge* edge) {
791   edge->setIsInSpanningTree(true);
792   _treeEdges.push_back(edge);
793 }
794 
795 // Pushes initialization and calls itself recursively.
pushInitializationFromEdge(BLInstrumentationEdge * edge)796 void BLInstrumentationDag::pushInitializationFromEdge(
797   BLInstrumentationEdge* edge) {
798   BallLarusNode* target;
799 
800   target = edge->getTarget();
801   if( target->getNumberPredEdges() > 1 || target == getExit() ) {
802     return;
803   } else {
804     for(BLEdgeIterator next = target->succBegin(),
805           end = target->succEnd(); next != end; next++) {
806       BLInstrumentationEdge* intoEdge = (BLInstrumentationEdge*) *next;
807 
808       // Skip split edges
809       if (intoEdge->getType() == BallLarusEdge::SPLITEDGE)
810         continue;
811 
812       intoEdge->setIncrement(intoEdge->getIncrement() +
813                              edge->getIncrement());
814       intoEdge->setIsInitialization(true);
815       pushInitializationFromEdge(intoEdge);
816     }
817 
818     edge->setIncrement(0);
819     edge->setIsInitialization(false);
820   }
821 }
822 
823 // Pushes path counter increments up recursively.
pushCountersFromEdge(BLInstrumentationEdge * edge)824 void BLInstrumentationDag::pushCountersFromEdge(BLInstrumentationEdge* edge) {
825   BallLarusNode* source;
826 
827   source = edge->getSource();
828   if(source->getNumberSuccEdges() > 1 || source == getRoot()
829      || edge->isInitialization()) {
830     return;
831   } else {
832     for(BLEdgeIterator previous = source->predBegin(),
833           end = source->predEnd(); previous != end; previous++) {
834       BLInstrumentationEdge* fromEdge = (BLInstrumentationEdge*) *previous;
835 
836       // Skip split edges
837       if (fromEdge->getType() == BallLarusEdge::SPLITEDGE)
838         continue;
839 
840       fromEdge->setIncrement(fromEdge->getIncrement() +
841                              edge->getIncrement());
842       fromEdge->setIsCounterIncrement(true);
843       pushCountersFromEdge(fromEdge);
844     }
845 
846     edge->setIncrement(0);
847     edge->setIsCounterIncrement(false);
848   }
849 }
850 
851 // Depth first algorithm for determining the chord increments.
calculateChordIncrementsDfs(long weight,BallLarusNode * v,BallLarusEdge * e)852 void BLInstrumentationDag::calculateChordIncrementsDfs(long weight,
853                                                        BallLarusNode* v, BallLarusEdge* e) {
854   BLInstrumentationEdge* f;
855 
856   for(BLEdgeIterator treeEdge = _treeEdges.begin(),
857         end = _treeEdges.end(); treeEdge != end; treeEdge++) {
858     f = (BLInstrumentationEdge*) *treeEdge;
859     if(e != f && v == f->getTarget()) {
860       calculateChordIncrementsDfs(
861         calculateChordIncrementsDir(e,f)*(weight) +
862         f->getWeight(), f->getSource(), f);
863     }
864     if(e != f && v == f->getSource()) {
865       calculateChordIncrementsDfs(
866         calculateChordIncrementsDir(e,f)*(weight) +
867         f->getWeight(), f->getTarget(), f);
868     }
869   }
870 
871   for(BLEdgeIterator chordEdge = _chordEdges.begin(),
872         end = _chordEdges.end(); chordEdge != end; chordEdge++) {
873     f = (BLInstrumentationEdge*) *chordEdge;
874     if(v == f->getSource() || v == f->getTarget()) {
875       f->setIncrement(f->getIncrement() +
876                       calculateChordIncrementsDir(e,f)*weight);
877     }
878   }
879 }
880 
881 // Determines the relative direction of two edges.
calculateChordIncrementsDir(BallLarusEdge * e,BallLarusEdge * f)882 int BLInstrumentationDag::calculateChordIncrementsDir(BallLarusEdge* e,
883                                                       BallLarusEdge* f) {
884   if( e == NULL)
885     return(1);
886   else if(e->getSource() == f->getTarget()
887           || e->getTarget() == f->getSource())
888     return(1);
889 
890   return(-1);
891 }
892 
893 // Creates an increment constant representing incr.
createIncrementConstant(long incr,int bitsize)894 ConstantInt* PathProfiler::createIncrementConstant(long incr,
895                                                    int bitsize) {
896   return(ConstantInt::get(IntegerType::get(*Context, 32), incr));
897 }
898 
899 // Creates an increment constant representing the value in
900 // edge->getIncrement().
createIncrementConstant(BLInstrumentationEdge * edge)901 ConstantInt* PathProfiler::createIncrementConstant(
902   BLInstrumentationEdge* edge) {
903   return(createIncrementConstant(edge->getIncrement(), 32));
904 }
905 
906 // Finds the insertion point after pathNumber in block.  PathNumber may
907 // be NULL.
getInsertionPoint(BasicBlock * block,Value * pathNumber)908 BasicBlock::iterator PathProfiler::getInsertionPoint(BasicBlock* block, Value*
909                                                      pathNumber) {
910   if(pathNumber == NULL || isa<ConstantInt>(pathNumber)
911      || (((Instruction*)(pathNumber))->getParent()) != block) {
912     return(block->getFirstInsertionPt());
913   } else {
914     Instruction* pathNumberInst = (Instruction*) (pathNumber);
915     BasicBlock::iterator insertPoint;
916     BasicBlock::iterator end = block->end();
917 
918     for(insertPoint = block->begin();
919         insertPoint != end; insertPoint++) {
920       Instruction* insertInst = &(*insertPoint);
921 
922       if(insertInst == pathNumberInst)
923         return(++insertPoint);
924     }
925 
926     return(insertPoint);
927   }
928 }
929 
930 // A PHINode is created in the node, and its values initialized to -1U.
preparePHI(BLInstrumentationNode * node)931 void PathProfiler::preparePHI(BLInstrumentationNode* node) {
932   BasicBlock* block = node->getBlock();
933   BasicBlock::iterator insertPoint = block->getFirstInsertionPt();
934   pred_iterator PB = pred_begin(node->getBlock()),
935           PE = pred_end(node->getBlock());
936   PHINode* phi = PHINode::Create(Type::getInt32Ty(*Context),
937                                  std::distance(PB, PE), "pathNumber",
938                                  insertPoint );
939   node->setPathPHI(phi);
940   node->setStartingPathNumber(phi);
941   node->setEndingPathNumber(phi);
942 
943   for(pred_iterator predIt = PB; predIt != PE; predIt++) {
944     BasicBlock* pred = (*predIt);
945 
946     if(pred != NULL)
947       phi->addIncoming(createIncrementConstant((long)-1, 32), pred);
948   }
949 }
950 
951 // Inserts source's pathNumber Value* into target.  Target may or may not
952 // have multiple predecessors, and may or may not have its phiNode
953 // initalized.
pushValueIntoNode(BLInstrumentationNode * source,BLInstrumentationNode * target)954 void PathProfiler::pushValueIntoNode(BLInstrumentationNode* source,
955                                      BLInstrumentationNode* target) {
956   if(target->getBlock() == NULL)
957     return;
958 
959 
960   if(target->getNumberPredEdges() <= 1) {
961     assert(target->getStartingPathNumber() == NULL &&
962            "Target already has path number");
963     target->setStartingPathNumber(source->getEndingPathNumber());
964     target->setEndingPathNumber(source->getEndingPathNumber());
965     DEBUG(dbgs() << "  Passing path number"
966           << (source->getEndingPathNumber() ? "" : " (null)")
967           << " value through.\n");
968   } else {
969     if(target->getPathPHI() == NULL) {
970       DEBUG(dbgs() << "  Initializing PHI node for block '"
971             << target->getName() << "'\n");
972       preparePHI(target);
973     }
974     pushValueIntoPHI(target, source);
975     DEBUG(dbgs() << "  Passing number value into PHI for block '"
976           << target->getName() << "'\n");
977   }
978 }
979 
980 // Inserts source's pathNumber Value* into the appropriate slot of
981 // target's phiNode.
pushValueIntoPHI(BLInstrumentationNode * target,BLInstrumentationNode * source)982 void PathProfiler::pushValueIntoPHI(BLInstrumentationNode* target,
983                                     BLInstrumentationNode* source) {
984   PHINode* phi = target->getPathPHI();
985   assert(phi != NULL && "  Tried to push value into node with PHI, but node"
986          " actually had no PHI.");
987   phi->removeIncomingValue(source->getBlock(), false);
988   phi->addIncoming(source->getEndingPathNumber(), source->getBlock());
989 }
990 
991 // The Value* in node, oldVal,  is updated with a Value* correspodning to
992 // oldVal + addition.
insertNumberIncrement(BLInstrumentationNode * node,Value * addition,bool atBeginning)993 void PathProfiler::insertNumberIncrement(BLInstrumentationNode* node,
994                                          Value* addition, bool atBeginning) {
995   BasicBlock* block = node->getBlock();
996   assert(node->getStartingPathNumber() != NULL);
997   assert(node->getEndingPathNumber() != NULL);
998 
999   BasicBlock::iterator insertPoint;
1000 
1001   if( atBeginning )
1002     insertPoint = block->getFirstInsertionPt();
1003   else
1004     insertPoint = block->getTerminator();
1005 
1006   DEBUG(errs() << "  Creating addition instruction.\n");
1007   Value* newpn = BinaryOperator::Create(Instruction::Add,
1008                                         node->getStartingPathNumber(),
1009                                         addition, "pathNumber", insertPoint);
1010 
1011   node->setEndingPathNumber(newpn);
1012 
1013   if( atBeginning )
1014     node->setStartingPathNumber(newpn);
1015 }
1016 
1017 // Creates a counter increment in the given node.  The Value* in node is
1018 // taken as the index into an array or hash table.  The hash table access
1019 // is a call to the runtime.
insertCounterIncrement(Value * incValue,BasicBlock::iterator insertPoint,BLInstrumentationDag * dag,bool increment)1020 void PathProfiler::insertCounterIncrement(Value* incValue,
1021                                           BasicBlock::iterator insertPoint,
1022                                           BLInstrumentationDag* dag,
1023                                           bool increment) {
1024   // Counter increment for array
1025   if( dag->getNumberOfPaths() <= HASH_THRESHHOLD ) {
1026     // Get pointer to the array location
1027     std::vector<Value*> gepIndices(2);
1028     gepIndices[0] = Constant::getNullValue(Type::getInt32Ty(*Context));
1029     gepIndices[1] = incValue;
1030 
1031     GetElementPtrInst* pcPointer =
1032       GetElementPtrInst::Create(dag->getCounterArray(), gepIndices,
1033                                 "counterInc", insertPoint);
1034 
1035     // Load from the array - call it oldPC
1036     LoadInst* oldPc = new LoadInst(pcPointer, "oldPC", insertPoint);
1037 
1038     // Test to see whether adding 1 will overflow the counter
1039     ICmpInst* isMax = new ICmpInst(insertPoint, CmpInst::ICMP_ULT, oldPc,
1040                                    createIncrementConstant(0xffffffff, 32),
1041                                    "isMax");
1042 
1043     // Select increment for the path counter based on overflow
1044     SelectInst* inc =
1045       SelectInst::Create( isMax, createIncrementConstant(increment?1:-1,32),
1046                           createIncrementConstant(0,32),
1047                           "pathInc", insertPoint);
1048 
1049     // newPc = oldPc + inc
1050     BinaryOperator* newPc = BinaryOperator::Create(Instruction::Add,
1051                                                    oldPc, inc, "newPC",
1052                                                    insertPoint);
1053 
1054     // Store back in to the array
1055     new StoreInst(newPc, pcPointer, insertPoint);
1056   } else { // Counter increment for hash
1057     std::vector<Value*> args(2);
1058     args[0] = ConstantInt::get(Type::getInt32Ty(*Context),
1059                                currentFunctionNumber);
1060     args[1] = incValue;
1061 
1062     CallInst::Create(
1063       increment ? llvmIncrementHashFunction : llvmDecrementHashFunction,
1064       args, "", insertPoint);
1065   }
1066 }
1067 
1068 // Inserts instrumentation for the given edge
1069 //
1070 // Pre: The edge's source node has pathNumber set if edge is non zero
1071 // path number increment.
1072 //
1073 // Post: Edge's target node has a pathNumber set to the path number Value
1074 // corresponding to the value of the path register after edge's
1075 // execution.
1076 //
1077 // FIXME: This should be reworked so it's not recursive.
insertInstrumentationStartingAt(BLInstrumentationEdge * edge,BLInstrumentationDag * dag)1078 void PathProfiler::insertInstrumentationStartingAt(BLInstrumentationEdge* edge,
1079                                                    BLInstrumentationDag* dag) {
1080   // Mark the edge as instrumented
1081   edge->setHasInstrumentation(true);
1082   DEBUG(dbgs() << "\nInstrumenting edge: " << (*edge) << "\n");
1083 
1084   // create a new node for this edge's instrumentation
1085   splitCritical(edge, dag);
1086 
1087   BLInstrumentationNode* sourceNode = (BLInstrumentationNode*)edge->getSource();
1088   BLInstrumentationNode* targetNode = (BLInstrumentationNode*)edge->getTarget();
1089   BLInstrumentationNode* instrumentNode;
1090   BLInstrumentationNode* nextSourceNode;
1091 
1092   bool atBeginning = false;
1093 
1094   // Source node has only 1 successor so any information can be simply
1095   // inserted in to it without splitting
1096   if( sourceNode->getBlock() && sourceNode->getNumberSuccEdges() <= 1) {
1097     DEBUG(dbgs() << "  Potential instructions to be placed in: "
1098           << sourceNode->getName() << " (at end)\n");
1099     instrumentNode = sourceNode;
1100     nextSourceNode = targetNode; // ... since we never made any new nodes
1101   }
1102 
1103   // The target node only has one predecessor, so we can safely insert edge
1104   // instrumentation into it. If there was splitting, it must have been
1105   // successful.
1106   else if( targetNode->getNumberPredEdges() == 1 ) {
1107     DEBUG(dbgs() << "  Potential instructions to be placed in: "
1108           << targetNode->getName() << " (at beginning)\n");
1109     pushValueIntoNode(sourceNode, targetNode);
1110     instrumentNode = targetNode;
1111     nextSourceNode = NULL; // ... otherwise we'll just keep splitting
1112     atBeginning = true;
1113   }
1114 
1115   // Somehow, splitting must have failed.
1116   else {
1117     errs() << "Instrumenting could not split a critical edge.\n";
1118     DEBUG(dbgs() << "  Couldn't split edge " << (*edge) << ".\n");
1119     return;
1120   }
1121 
1122   // Insert instrumentation if this is a back or split edge
1123   if( edge->getType() == BallLarusEdge::BACKEDGE ||
1124       edge->getType() == BallLarusEdge::SPLITEDGE ) {
1125     BLInstrumentationEdge* top =
1126       (BLInstrumentationEdge*) edge->getPhonyRoot();
1127     BLInstrumentationEdge* bottom =
1128       (BLInstrumentationEdge*) edge->getPhonyExit();
1129 
1130     assert( top->isInitialization() && " Top phony edge did not"
1131             " contain a path number initialization.");
1132     assert( bottom->isCounterIncrement() && " Bottom phony edge"
1133             " did not contain a path counter increment.");
1134 
1135     // split edge has yet to be initialized
1136     if( !instrumentNode->getEndingPathNumber() ) {
1137       instrumentNode->setStartingPathNumber(createIncrementConstant(0,32));
1138       instrumentNode->setEndingPathNumber(createIncrementConstant(0,32));
1139     }
1140 
1141     BasicBlock::iterator insertPoint = atBeginning ?
1142       instrumentNode->getBlock()->getFirstInsertionPt() :
1143       instrumentNode->getBlock()->getTerminator();
1144 
1145     // add information from the bottom edge, if it exists
1146     if( bottom->getIncrement() ) {
1147       Value* newpn =
1148         BinaryOperator::Create(Instruction::Add,
1149                                instrumentNode->getStartingPathNumber(),
1150                                createIncrementConstant(bottom),
1151                                "pathNumber", insertPoint);
1152       instrumentNode->setEndingPathNumber(newpn);
1153     }
1154 
1155     insertCounterIncrement(instrumentNode->getEndingPathNumber(),
1156                            insertPoint, dag);
1157 
1158     if( atBeginning )
1159       instrumentNode->setStartingPathNumber(createIncrementConstant(top));
1160 
1161     instrumentNode->setEndingPathNumber(createIncrementConstant(top));
1162 
1163     // Check for path counter increments
1164     if( top->isCounterIncrement() ) {
1165       insertCounterIncrement(instrumentNode->getEndingPathNumber(),
1166                              instrumentNode->getBlock()->getTerminator(),dag);
1167       instrumentNode->setEndingPathNumber(0);
1168     }
1169   }
1170 
1171   // Insert instrumentation if this is a normal edge
1172   else {
1173     BasicBlock::iterator insertPoint = atBeginning ?
1174       instrumentNode->getBlock()->getFirstInsertionPt() :
1175       instrumentNode->getBlock()->getTerminator();
1176 
1177     if( edge->isInitialization() ) { // initialize path number
1178       instrumentNode->setEndingPathNumber(createIncrementConstant(edge));
1179     } else if( edge->getIncrement() )       {// increment path number
1180       Value* newpn =
1181         BinaryOperator::Create(Instruction::Add,
1182                                instrumentNode->getStartingPathNumber(),
1183                                createIncrementConstant(edge),
1184                                "pathNumber", insertPoint);
1185       instrumentNode->setEndingPathNumber(newpn);
1186 
1187       if( atBeginning )
1188         instrumentNode->setStartingPathNumber(newpn);
1189     }
1190 
1191     // Check for path counter increments
1192     if( edge->isCounterIncrement() ) {
1193       insertCounterIncrement(instrumentNode->getEndingPathNumber(),
1194                              insertPoint, dag);
1195       instrumentNode->setEndingPathNumber(0);
1196     }
1197   }
1198 
1199   // Push it along
1200   if (nextSourceNode && instrumentNode->getEndingPathNumber())
1201     pushValueIntoNode(instrumentNode, nextSourceNode);
1202 
1203   // Add all the successors
1204   for( BLEdgeIterator next = targetNode->succBegin(),
1205          end = targetNode->succEnd(); next != end; next++ ) {
1206     // So long as it is un-instrumented, add it to the list
1207     if( !((BLInstrumentationEdge*)(*next))->hasInstrumentation() )
1208       insertInstrumentationStartingAt((BLInstrumentationEdge*)*next,dag);
1209     else
1210       DEBUG(dbgs() << "  Edge " << *(BLInstrumentationEdge*)(*next)
1211             << " already instrumented.\n");
1212   }
1213 }
1214 
1215 // Inserts instrumentation according to the marked edges in dag.  Phony edges
1216 // must be unlinked from the DAG, but accessible from the backedges.  Dag
1217 // must have initializations, path number increments, and counter increments
1218 // present.
1219 //
1220 // Counter storage is created here.
insertInstrumentation(BLInstrumentationDag & dag,Module & M)1221 void PathProfiler::insertInstrumentation(
1222   BLInstrumentationDag& dag, Module &M) {
1223 
1224   BLInstrumentationEdge* exitRootEdge =
1225     (BLInstrumentationEdge*) dag.getExitRootEdge();
1226   insertInstrumentationStartingAt(exitRootEdge, &dag);
1227 
1228   // Iterate through each call edge and apply the appropriate hash increment
1229   // and decrement functions
1230   BLEdgeVector callEdges = dag.getCallPhonyEdges();
1231   for( BLEdgeIterator edge = callEdges.begin(),
1232          end = callEdges.end(); edge != end; edge++ ) {
1233     BLInstrumentationNode* node =
1234       (BLInstrumentationNode*)(*edge)->getSource();
1235     BasicBlock::iterator insertPoint = node->getBlock()->getFirstInsertionPt();
1236 
1237     // Find the first function call
1238     while( ((Instruction&)(*insertPoint)).getOpcode() != Instruction::Call )
1239       insertPoint++;
1240 
1241     DEBUG(dbgs() << "\nInstrumenting method call block '"
1242           << node->getBlock()->getNameStr() << "'\n");
1243     DEBUG(dbgs() << "   Path number initialized: "
1244           << ((node->getStartingPathNumber()) ? "yes" : "no") << "\n");
1245 
1246     Value* newpn;
1247     if( node->getStartingPathNumber() ) {
1248       long inc = ((BLInstrumentationEdge*)(*edge))->getIncrement();
1249       if ( inc )
1250         newpn = BinaryOperator::Create(Instruction::Add,
1251                                        node->getStartingPathNumber(),
1252                                        createIncrementConstant(inc,32),
1253                                        "pathNumber", insertPoint);
1254       else
1255         newpn = node->getStartingPathNumber();
1256     } else {
1257       newpn = (Value*)createIncrementConstant(
1258         ((BLInstrumentationEdge*)(*edge))->getIncrement(), 32);
1259     }
1260 
1261     insertCounterIncrement(newpn, insertPoint, &dag);
1262     insertCounterIncrement(newpn, node->getBlock()->getTerminator(),
1263                            &dag, false);
1264   }
1265 }
1266 
1267 // Entry point of the module
runOnFunction(std::vector<Constant * > & ftInit,Function & F,Module & M)1268 void PathProfiler::runOnFunction(std::vector<Constant*> &ftInit,
1269                                  Function &F, Module &M) {
1270   // Build DAG from CFG
1271   BLInstrumentationDag dag = BLInstrumentationDag(F);
1272   dag.init();
1273 
1274   // give each path a unique integer value
1275   dag.calculatePathNumbers();
1276 
1277   // modify path increments to increase the efficiency
1278   // of instrumentation
1279   dag.calculateSpanningTree();
1280   dag.calculateChordIncrements();
1281   dag.pushInitialization();
1282   dag.pushCounters();
1283   dag.unlinkPhony();
1284 
1285   // potentially generate .dot graph for the dag
1286   if (DotPathDag)
1287     dag.generateDotGraph ();
1288 
1289   // Should we store the information in an array or hash
1290   if( dag.getNumberOfPaths() <= HASH_THRESHHOLD ) {
1291     Type* t = ArrayType::get(Type::getInt32Ty(*Context),
1292                                    dag.getNumberOfPaths());
1293 
1294     dag.setCounterArray(new GlobalVariable(M, t, false,
1295                                            GlobalValue::InternalLinkage,
1296                                            Constant::getNullValue(t), ""));
1297   }
1298 
1299   insertInstrumentation(dag, M);
1300 
1301   // Add to global function reference table
1302   unsigned type;
1303   Type* voidPtr = TypeBuilder<types::i<8>*, true>::get(*Context);
1304 
1305   if( dag.getNumberOfPaths() <= HASH_THRESHHOLD )
1306     type = ProfilingArray;
1307   else
1308     type = ProfilingHash;
1309 
1310   std::vector<Constant*> entryArray(3);
1311   entryArray[0] = createIncrementConstant(type,32);
1312   entryArray[1] = createIncrementConstant(dag.getNumberOfPaths(),32);
1313   entryArray[2] = dag.getCounterArray() ?
1314     ConstantExpr::getBitCast(dag.getCounterArray(), voidPtr) :
1315     Constant::getNullValue(voidPtr);
1316 
1317   StructType* at = ftEntryTypeBuilder::get(*Context);
1318   ConstantStruct* functionEntry =
1319     (ConstantStruct*)ConstantStruct::get(at, entryArray);
1320   ftInit.push_back(functionEntry);
1321 }
1322 
1323 // Output the bitcode if we want to observe instrumentation changess
1324 #define PRINT_MODULE dbgs() <<                               \
1325   "\n\n============= MODULE BEGIN ===============\n" << M << \
1326   "\n============== MODULE END ================\n"
1327 
runOnModule(Module & M)1328 bool PathProfiler::runOnModule(Module &M) {
1329   Context = &M.getContext();
1330 
1331   DEBUG(dbgs()
1332         << "****************************************\n"
1333         << "****************************************\n"
1334         << "**                                    **\n"
1335         << "**   PATH PROFILING INSTRUMENTATION   **\n"
1336         << "**                                    **\n"
1337         << "****************************************\n"
1338         << "****************************************\n");
1339 
1340   // No main, no instrumentation!
1341   Function *Main = M.getFunction("main");
1342 
1343   // Using fortran? ... this kind of works
1344   if (!Main)
1345     Main = M.getFunction("MAIN__");
1346 
1347   if (!Main) {
1348     errs() << "WARNING: cannot insert path profiling into a module"
1349            << " with no main function!\n";
1350     return false;
1351   }
1352 
1353   llvmIncrementHashFunction = M.getOrInsertFunction(
1354     "llvm_increment_path_count",
1355     Type::getVoidTy(*Context), // return type
1356     Type::getInt32Ty(*Context), // function number
1357     Type::getInt32Ty(*Context), // path number
1358     NULL );
1359 
1360   llvmDecrementHashFunction = M.getOrInsertFunction(
1361     "llvm_decrement_path_count",
1362     Type::getVoidTy(*Context), // return type
1363     Type::getInt32Ty(*Context), // function number
1364     Type::getInt32Ty(*Context), // path number
1365     NULL );
1366 
1367   std::vector<Constant*> ftInit;
1368   unsigned functionNumber = 0;
1369   for (Module::iterator F = M.begin(), E = M.end(); F != E; F++) {
1370     if (F->isDeclaration())
1371       continue;
1372 
1373     DEBUG(dbgs() << "Function: " << F->getNameStr() << "\n");
1374     functionNumber++;
1375 
1376     // set function number
1377     currentFunctionNumber = functionNumber;
1378     runOnFunction(ftInit, *F, M);
1379   }
1380 
1381   Type *t = ftEntryTypeBuilder::get(*Context);
1382   ArrayType* ftArrayType = ArrayType::get(t, ftInit.size());
1383   Constant* ftInitConstant = ConstantArray::get(ftArrayType, ftInit);
1384 
1385   DEBUG(dbgs() << " ftArrayType:" << *ftArrayType << "\n");
1386 
1387   GlobalVariable* functionTable =
1388     new GlobalVariable(M, ftArrayType, false, GlobalValue::InternalLinkage,
1389                        ftInitConstant, "functionPathTable");
1390   Type *eltType = ftArrayType->getTypeAtIndex((unsigned)0);
1391   InsertProfilingInitCall(Main, "llvm_start_path_profiling", functionTable,
1392                           PointerType::getUnqual(eltType));
1393 
1394   DEBUG(PRINT_MODULE);
1395 
1396   return true;
1397 }
1398 
1399 // If this edge is a critical edge, then inserts a node at this edge.
1400 // This edge becomes the first edge, and a new BallLarusEdge is created.
1401 // Returns true if the edge was split
splitCritical(BLInstrumentationEdge * edge,BLInstrumentationDag * dag)1402 bool PathProfiler::splitCritical(BLInstrumentationEdge* edge,
1403                                  BLInstrumentationDag* dag) {
1404   unsigned succNum = edge->getSuccessorNumber();
1405   BallLarusNode* sourceNode = edge->getSource();
1406   BallLarusNode* targetNode = edge->getTarget();
1407   BasicBlock* sourceBlock = sourceNode->getBlock();
1408   BasicBlock* targetBlock = targetNode->getBlock();
1409 
1410   if(sourceBlock == NULL || targetBlock == NULL
1411      || sourceNode->getNumberSuccEdges() <= 1
1412      || targetNode->getNumberPredEdges() == 1 ) {
1413     return(false);
1414   }
1415 
1416   TerminatorInst* terminator = sourceBlock->getTerminator();
1417 
1418   if( SplitCriticalEdge(terminator, succNum, this, false)) {
1419     BasicBlock* newBlock = terminator->getSuccessor(succNum);
1420     dag->splitUpdate(edge, newBlock);
1421     return(true);
1422   } else
1423     return(false);
1424 }
1425