1 //===-- ProfilePaths.cpp - interface to insert instrumentation ---*- C++ -*--=//
3 // This inserts intrumentation for counting
4 // execution of paths though a given method
5 // Its implemented as a "Method" Pass, and called using opt
7 // This pass is implemented by using algorithms similar to
8 // 1."Efficient Path Profiling": Ball, T. and Larus, J. R.,
9 // Proceedings of Micro-29, Dec 1996, Paris, France.
10 // 2."Efficiently Counting Program events with support for on-line
11 // "queries": Ball T., ACM Transactions on Programming Languages
12 // and systems, Sep 1994.
14 // The algorithms work on a Graph constructed over the nodes
15 // made from Basic Blocks: The transformations then take place on
16 // the constucted graph (implementation in Graph.cpp and GraphAuxillary.cpp)
17 // and finally, appropriate instrumentation is placed over suitable edges.
18 // (code inserted through EdgeCode.cpp).
20 // The algorithm inserts code such that every acyclic path in the CFG
21 // of a method is identified through a unique number. the code insertion
22 // is optimal in the sense that its inserted over a minimal set of edges. Also,
23 // the algorithm makes sure than initialization, path increment and counter
24 // update can be collapsed into minmimum number of edges.
25 //===----------------------------------------------------------------------===//
27 #include "llvm/Transforms/Instrumentation/ProfilePaths.h"
28 #include "llvm/Transforms/UnifyMethodExitNodes.h"
29 #include "llvm/Support/CFG.h"
30 #include "llvm/Method.h"
31 #include "llvm/BasicBlock.h"
32 #include "llvm/ConstantVals.h"
33 #include "llvm/DerivedTypes.h"
34 #include "llvm/iMemory.h"
35 #include "llvm/Pass.h"
40 class ProfilePaths: public MethodPass {
42 bool runOnMethod(Method *M);
44 // Before this pass, make sure that there is only one
45 // entry and only one exit node for the method in the CFG of the method
47 void ProfilePaths::getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
48 Pass::AnalysisSet &Destroyed,
49 Pass::AnalysisSet &Provided) {
50 Requires.push_back(UnifyMethodExitNodes::ID);
54 // createProfilePathsPass - Create a new pass to add path profiling
56 Pass *createProfilePathsPass() {
57 return new ProfilePaths();
61 static Node *findBB(std::set<Node *> &st, BasicBlock *BB){
62 for(std::set<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
63 if(((*si)->getElement())==BB){
70 //Per method pass for inserting counters and trigger code
71 bool ProfilePaths::runOnMethod(Method *M){
72 //Transform the cfg s.t. we have just one exit node
73 BasicBlock *ExitNode =
74 getAnalysis<UnifyMethodExitNodes>().getExitNode();
76 //iterating over BBs and making graph
77 std::set<Node *> nodes;
80 Node *exitNode, *startNode;
82 //The nodes must be uniquesly identified:
83 //That is, no two nodes must hav same BB*
85 //First enter just nodes: later enter edges
86 for (Method::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
87 Node *nd=new Node(*BB);
95 //now do it againto insert edges
96 for (Method::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
97 Node *nd=findBB(nodes, *BB);
98 assert(nd && "No node for this edge!");
99 for(BasicBlock::succ_iterator s=succ_begin(*BB), se=succ_end(*BB);
101 Node *nd2=findBB(nodes,*s);
102 assert(nd2 && "No node for this edge!");
108 Graph g(nodes,edges, startNode, exitNode);
110 #ifdef DEBUG_PATH_PROFILES
114 BasicBlock *fr=M->front();
116 //If only one BB, don't instrument
117 if (M->getBasicBlocks().size() == 1) {
118 //The graph is made acyclic: this is done
119 //by removing back edges for now, and adding them later on
122 #ifdef DEBUG_PATH_PROFILES
123 cerr<<"Backedges:"<<be.size()<<endl;
125 //Now we need to reflect the effect of back edges
126 //This is done by adding dummy edges
127 //If a->b is a back edge
128 //Then we add 2 back edges for it:
129 //1. from root->b (in vector stDummy)
130 //and 2. from a->exit (in vector exDummy)
131 vector<Edge> stDummy;
132 vector<Edge> exDummy;
133 addDummyEdges(stDummy, exDummy, g, be);
135 //Now, every edge in the graph is assigned a weight
136 //This weight later adds on to assign path
137 //numbers to different paths in the graph
138 // All paths for now are acyclic,
139 //since no back edges in the graph now
140 //numPaths is the number of acyclic paths in the graph
141 int numPaths=valueAssignmentToEdges(g);
143 //create instruction allocation r and count
144 //r is the variable that'll act like an accumulator
145 //all along the path, we just add edge values to r
146 //and at the end, r reflects the path number
147 //count is an array: count[x] would store
148 //the number of executions of path numbered x
149 Instruction *rVar=new
150 AllocaInst(PointerType::get(Type::IntTy),
151 ConstantUInt::get(Type::UIntTy,1),"R");
153 Instruction *countVar=new
154 AllocaInst(PointerType::get(Type::IntTy),
155 ConstantUInt::get(Type::UIntTy, numPaths), "Count");
157 //insert initialization code in first (entry) BB
158 //this includes initializing r and count
159 insertInTopBB(M->getEntryNode(),numPaths, rVar, countVar);
161 //now process the graph: get path numbers,
162 //get increments along different paths,
163 //and assign "increments" and "updates" (to r and count)
164 //"optimally". Finally, insert llvm code along various edges
165 processGraph(g, rVar, countVar, be, stDummy, exDummy);
168 return true; // Always modifies method