1 //===-- ProfilePaths.cpp - interface to insert instrumentation ---*- C++ -*--=//
3 // This inserts instrumentation for counting
4 // execution of paths though a given function
5 // Its implemented as a "Function" 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 constructed graph (implementation in Graph.cpp and GraphAuxiliary.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 function 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 minimum number of edges.
25 //===----------------------------------------------------------------------===//
27 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
28 #include "llvm/Support/CFG.h"
29 #include "llvm/Constants.h"
30 #include "llvm/DerivedTypes.h"
31 #include "llvm/iMemory.h"
32 #include "llvm/iOperators.h"
33 #include "llvm/iOther.h"
34 #include "llvm/Module.h"
37 #include "Config/stdio.h"
39 struct ProfilePaths : public FunctionPass {
40 bool runOnFunction(Function &F);
42 // Before this pass, make sure that there is only one
43 // entry and only one exit node for the function in the CFG of the function
45 void ProfilePaths::getAnalysisUsage(AnalysisUsage &AU) const {
46 AU.addRequired<UnifyFunctionExitNodes>();
50 static RegisterOpt<ProfilePaths> X("paths", "Profile Paths");
52 static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
53 for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
54 if(((*si)->getElement())==BB){
61 //Per function pass for inserting counters and trigger code
62 bool ProfilePaths::runOnFunction(Function &F){
65 static int CountCounter = 1;
70 //increment counter for instrumented functions. mn is now function#
73 // Transform the cfg s.t. we have just one exit node
74 BasicBlock *ExitNode =
75 getAnalysis<UnifyFunctionExitNodes>().getReturnBlock();
77 //iterating over BBs and making graph
78 std::vector<Node *> nodes;
79 std::vector<Edge> edges;
82 Node *exitNode = 0, *startNode = 0;
84 // The nodes must be uniquely identified:
85 // That is, no two nodes must hav same BB*
87 for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB) {
88 Node *nd=new Node(BB);
96 // now do it again to insert edges
97 for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB){
98 Node *nd=findBB(nodes, BB);
99 assert(nd && "No node for this edge!");
101 for(succ_iterator s=succ_begin(BB), se=succ_end(BB); s!=se; ++s){
102 Node *nd2=findBB(nodes,*s);
103 assert(nd2 && "No node for this edge!");
109 Graph g(nodes,edges, startNode, exitNode);
111 #ifdef DEBUG_PATH_PROFILES
112 std::cerr<<"Original graph\n";
116 BasicBlock *fr = &F.front();
118 // The graph is made acyclic: this is done
119 // by removing back edges for now, and adding them later on
120 std::vector<Edge> be;
121 std::map<Node *, int> nodePriority; //it ranks nodes in depth first order traversal
122 g.getBackEdges(be, nodePriority);
124 #ifdef DEBUG_PATH_PROFILES
125 std::cerr<<"BackEdges-------------\n";
126 for (std::vector<Edge>::iterator VI=be.begin(); VI!=be.end(); ++VI){
130 std::cerr<<"------\n";
133 #ifdef DEBUG_PATH_PROFILES
134 cerr<<"Backedges:"<<be.size()<<endl;
136 //Now we need to reflect the effect of back edges
137 //This is done by adding dummy edges
138 //If a->b is a back edge
139 //Then we add 2 back edges for it:
140 //1. from root->b (in vector stDummy)
141 //and 2. from a->exit (in vector exDummy)
142 std::vector<Edge> stDummy;
143 std::vector<Edge> exDummy;
144 addDummyEdges(stDummy, exDummy, g, be);
146 #ifdef DEBUG_PATH_PROFILES
147 std::cerr<<"After adding dummy edges\n";
151 // Now, every edge in the graph is assigned a weight
152 // This weight later adds on to assign path
153 // numbers to different paths in the graph
154 // All paths for now are acyclic,
155 // since no back edges in the graph now
156 // numPaths is the number of acyclic paths in the graph
157 int numPaths=valueAssignmentToEdges(g, nodePriority, be);
159 //if(numPaths<=1) return false;
161 static GlobalVariable *threshold = NULL;
162 static bool insertedThreshold = false;
164 if(!insertedThreshold){
165 threshold = new GlobalVariable(Type::IntTy, false,
166 GlobalValue::ExternalLinkage, 0,
169 F.getParent()->getGlobalList().push_back(threshold);
170 insertedThreshold = true;
173 assert(threshold && "GlobalVariable threshold not defined!");
176 if(fr->getParent()->getName() == "main"){
177 //initialize threshold
179 // FIXME: THIS IS HORRIBLY BROKEN. FUNCTION PASSES CANNOT DO THIS, EXCEPT
180 // IN THEIR INITIALIZE METHOD!!
181 Function *initialize =
182 F.getParent()->getOrInsertFunction("reoptimizerInitialize", Type::VoidTy,
183 PointerType::get(Type::IntTy), 0);
185 std::vector<Value *> trargs;
186 trargs.push_back(threshold);
187 new CallInst(initialize, trargs, "", fr->begin());
191 if(numPaths<=1 || numPaths >5000) return false;
193 #ifdef DEBUG_PATH_PROFILES
197 //create instruction allocation r and count
198 //r is the variable that'll act like an accumulator
199 //all along the path, we just add edge values to r
200 //and at the end, r reflects the path number
201 //count is an array: count[x] would store
202 //the number of executions of path numbered x
204 Instruction *rVar=new
205 AllocaInst(Type::IntTy,
206 ConstantUInt::get(Type::UIntTy,1),"R");
208 //Instruction *countVar=new
209 //AllocaInst(Type::IntTy,
210 // ConstantUInt::get(Type::UIntTy, numPaths), "Count");
212 //initialize counter array!
213 std::vector<Constant*> arrayInitialize;
214 for(int xi=0; xi<numPaths; xi++)
215 arrayInitialize.push_back(ConstantSInt::get(Type::IntTy, 0));
217 const ArrayType *ATy = ArrayType::get(Type::IntTy, numPaths);
218 Constant *initializer = ConstantArray::get(ATy, arrayInitialize);
220 sprintf(tempChar, "Count%d", CountCounter);
222 std::string countStr = tempChar;
223 GlobalVariable *countVar = new GlobalVariable(ATy, false,
224 GlobalValue::InternalLinkage,
225 initializer, countStr,
228 // insert initialization code in first (entry) BB
229 // this includes initializing r and count
230 insertInTopBB(&F.getEntryBlock(), numPaths, rVar, threshold);
232 //now process the graph: get path numbers,
233 //get increments along different paths,
234 //and assign "increments" and "updates" (to r and count)
235 //"optimally". Finally, insert llvm code along various edges
236 processGraph(g, rVar, countVar, be, stDummy, exDummy, numPaths, mn,
239 return true; // Always modifies function