1 //===-- ProfilePaths.cpp - interface to insert instrumentation --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This inserts instrumentation for counting execution of paths though a given
11 // function Its implemented as a "Function" Pass, and called using opt
13 // This pass is implemented by using algorithms similar to
14 // 1."Efficient Path Profiling": Ball, T. and Larus, J. R.,
15 // Proceedings of Micro-29, Dec 1996, Paris, France.
16 // 2."Efficiently Counting Program events with support for on-line
17 // "queries": Ball T., ACM Transactions on Programming Languages
18 // and systems, Sep 1994.
20 // The algorithms work on a Graph constructed over the nodes made from Basic
21 // Blocks: The transformations then take place on the constructed graph
22 // (implementation in Graph.cpp and GraphAuxiliary.cpp) and finally, appropriate
23 // instrumentation is placed over suitable edges. (code inserted through
26 // The algorithm inserts code such that every acyclic path in the CFG of a
27 // function is identified through a unique number. the code insertion is optimal
28 // in the sense that its inserted over a minimal set of edges. Also, the
29 // algorithm makes sure than initialization, path increment and counter update
30 // can be collapsed into minimum number of edges.
32 //===----------------------------------------------------------------------===//
34 #include "llvm/Transforms/Instrumentation.h"
35 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
36 #include "llvm/Support/CFG.h"
37 #include "llvm/Constants.h"
38 #include "llvm/DerivedTypes.h"
39 #include "llvm/Instructions.h"
40 #include "llvm/Module.h"
47 struct ProfilePaths : public FunctionPass {
48 bool runOnFunction(Function &F);
50 // Before this pass, make sure that there is only one
51 // entry and only one exit node for the function in the CFG of the function
53 void getAnalysisUsage(AnalysisUsage &AU) const {
54 AU.addRequired<UnifyFunctionExitNodes>();
58 static RegisterOpt<ProfilePaths> X("paths", "Profile Paths");
60 FunctionPass *createProfilePathsPass() { return new ProfilePaths(); }
62 static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
63 for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
64 if(((*si)->getElement())==BB){
71 //Per function pass for inserting counters and trigger code
72 bool ProfilePaths::runOnFunction(Function &F){
75 static int CountCounter = 1;
80 //increment counter for instrumented functions. mn is now function#
83 // Transform the cfg s.t. we have just one exit node
84 BasicBlock *ExitNode =
85 getAnalysis<UnifyFunctionExitNodes>().getReturnBlock();
87 //iterating over BBs and making graph
88 std::vector<Node *> nodes;
89 std::vector<Edge> edges;
91 Node *exitNode = 0, *startNode = 0;
93 // The nodes must be uniquely identified:
94 // That is, no two nodes must hav same BB*
96 for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB) {
97 Node *nd=new Node(BB);
105 // now do it again to insert edges
106 for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB){
107 Node *nd=findBB(nodes, BB);
108 assert(nd && "No node for this edge!");
110 for(succ_iterator s=succ_begin(BB), se=succ_end(BB); s!=se; ++s){
111 Node *nd2=findBB(nodes,*s);
112 assert(nd2 && "No node for this edge!");
118 Graph g(nodes,edges, startNode, exitNode);
120 #ifdef DEBUG_PATH_PROFILES
121 std::cerr<<"Original graph\n";
125 BasicBlock *fr = &F.front();
127 // The graph is made acyclic: this is done
128 // by removing back edges for now, and adding them later on
129 std::vector<Edge> be;
130 std::map<Node *, int> nodePriority; //it ranks nodes in depth first order traversal
131 g.getBackEdges(be, nodePriority);
133 #ifdef DEBUG_PATH_PROFILES
134 std::cerr<<"BackEdges-------------\n";
135 for (std::vector<Edge>::iterator VI=be.begin(); VI!=be.end(); ++VI){
139 std::cerr<<"------\n";
142 #ifdef DEBUG_PATH_PROFILES
143 cerr<<"Backedges:"<<be.size()<<endl;
145 //Now we need to reflect the effect of back edges
146 //This is done by adding dummy edges
147 //If a->b is a back edge
148 //Then we add 2 back edges for it:
149 //1. from root->b (in vector stDummy)
150 //and 2. from a->exit (in vector exDummy)
151 std::vector<Edge> stDummy;
152 std::vector<Edge> exDummy;
153 addDummyEdges(stDummy, exDummy, g, be);
155 #ifdef DEBUG_PATH_PROFILES
156 std::cerr<<"After adding dummy edges\n";
160 // Now, every edge in the graph is assigned a weight
161 // This weight later adds on to assign path
162 // numbers to different paths in the graph
163 // All paths for now are acyclic,
164 // since no back edges in the graph now
165 // numPaths is the number of acyclic paths in the graph
166 int numPaths=valueAssignmentToEdges(g, nodePriority, be);
168 //if(numPaths<=1) return false;
170 static GlobalVariable *threshold = NULL;
171 static bool insertedThreshold = false;
173 if(!insertedThreshold){
174 threshold = new GlobalVariable(Type::IntTy, false,
175 GlobalValue::ExternalLinkage, 0,
178 F.getParent()->getGlobalList().push_back(threshold);
179 insertedThreshold = true;
182 assert(threshold && "GlobalVariable threshold not defined!");
185 if(fr->getParent()->getName() == "main"){
186 //initialize threshold
188 // FIXME: THIS IS HORRIBLY BROKEN. FUNCTION PASSES CANNOT DO THIS, EXCEPT
189 // IN THEIR INITIALIZE METHOD!!
190 Function *initialize =
191 F.getParent()->getOrInsertFunction("reoptimizerInitialize", Type::VoidTy,
192 PointerType::get(Type::IntTy), 0);
194 std::vector<Value *> trargs;
195 trargs.push_back(threshold);
196 new CallInst(initialize, trargs, "", fr->begin());
200 if(numPaths<=1 || numPaths >5000) return false;
202 #ifdef DEBUG_PATH_PROFILES
206 //create instruction allocation r and count
207 //r is the variable that'll act like an accumulator
208 //all along the path, we just add edge values to r
209 //and at the end, r reflects the path number
210 //count is an array: count[x] would store
211 //the number of executions of path numbered x
213 Instruction *rVar=new
214 AllocaInst(Type::IntTy,
215 ConstantUInt::get(Type::UIntTy,1),"R");
217 //Instruction *countVar=new
218 //AllocaInst(Type::IntTy,
219 // ConstantUInt::get(Type::UIntTy, numPaths), "Count");
221 //initialize counter array!
222 std::vector<Constant*> arrayInitialize;
223 for(int xi=0; xi<numPaths; xi++)
224 arrayInitialize.push_back(ConstantSInt::get(Type::IntTy, 0));
226 const ArrayType *ATy = ArrayType::get(Type::IntTy, numPaths);
227 Constant *initializer = ConstantArray::get(ATy, arrayInitialize);
229 sprintf(tempChar, "Count%d", CountCounter);
231 std::string countStr = tempChar;
232 GlobalVariable *countVar = new GlobalVariable(ATy, false,
233 GlobalValue::InternalLinkage,
234 initializer, countStr,
237 // insert initialization code in first (entry) BB
238 // this includes initializing r and count
239 insertInTopBB(&F.getEntryBlock(), numPaths, rVar, threshold);
241 //now process the graph: get path numbers,
242 //get increments along different paths,
243 //and assign "increments" and "updates" (to r and count)
244 //"optimally". Finally, insert llvm code along various edges
245 processGraph(g, rVar, countVar, be, stDummy, exDummy, numPaths, mn,
248 return true; // Always modifies function
251 } // End llvm namespace