Initial checkin: helper file to insert instrumentation code along edges
[oota-llvm.git] / lib / Transforms / Instrumentation / ProfilePaths / EdgeCode.cpp
1 //===-- EdgeCode.cpp - generate LLVM instrumentation code --------*- C++ -*--=//
2 //It implements the class EdgeCode: which provides 
3 //support for inserting "appropriate" instrumentation at
4 //designated points in the graph
5 //
6 //It also has methods to insert initialization code in 
7 //top block of cfg
8 //===----------------------------------------------------------------------===//
9
10 #include "Graph.h"
11 #include "llvm/ConstantVals.h"
12 #include "llvm/DerivedTypes.h"
13 #include "llvm/iMemory.h"
14 #include "llvm/iTerminators.h"
15 #include "llvm/iOther.h"
16 #include "llvm/iOperators.h"
17 #include "llvm/iPHINode.h"
18
19 class Method;
20 using std::vector;
21
22 //get the code to be inserted on the edge
23 //This is determined from cond (1-6)
24 void getEdgeCode::getCode(Instruction *rInst, 
25                           Instruction *countInst, 
26                           Method *M, 
27                           BasicBlock *BB){
28   
29   BasicBlock::InstListType& instList=BB->getInstList();
30   BasicBlock::iterator here=instList.begin();
31   
32   //case: r=k code to be inserted
33   switch(cond){
34   case 1:{
35     Value *val=ConstantSInt::get(Type::IntTy,inc);
36     Instruction *stInst=new StoreInst(val, rInst);
37     here=instList.insert(here,stInst)+1;
38     break;
39     }
40
41   //case: r=0 to be inserted
42   case 2:{
43     Value *val=ConstantSInt::get(Type::IntTy,0);
44     Instruction *stInst=new StoreInst(val, rInst);
45     here=instList.insert(here,stInst)+1;
46     break;
47   }
48     
49   //r+=k
50   case 3:{
51     Instruction *ldInst=new LoadInst(rInst, "ti1");
52     Value *val=ConstantSInt::get(Type::IntTy,inc);
53     Instruction *addIn=BinaryOperator::
54       create(Instruction::Add, ldInst, val,"ti2");
55     
56     Instruction *stInst=new StoreInst(addIn, rInst);
57     here=instList.insert(here,ldInst)+1;
58     here=instList.insert(here,addIn)+1;
59     here=instList.insert(here,stInst)+1;
60     break;
61   }
62
63   //count[inc]++
64   case 4:{
65     Instruction *ldInst=new 
66       LoadInst(countInst,vector<Value *>
67                (1,ConstantUInt::get(Type::UIntTy, inc)), "ti1");
68     Value *val=ConstantSInt::get(Type::IntTy,1);
69     Instruction *addIn=BinaryOperator::
70       create(Instruction::Add, ldInst, val,"ti2");
71
72     assert(inc>=0 && "IT MUST BE POSITIVE NOW");
73     Instruction *stInst=new 
74       StoreInst(addIn, countInst, vector<Value *>
75                 (1, ConstantUInt::get(Type::UIntTy,inc)));
76     
77     here=instList.insert(here,ldInst)+1;
78     here=instList.insert(here,addIn)+1;
79     here=instList.insert(here,stInst)+1;
80     break;
81   }
82
83   //case: count[r+inc]++
84   case 5:{
85     //ti1=inc+r
86     Instruction *ldIndex=new LoadInst(rInst, "ti1");
87     Value *val=ConstantSInt::get(Type::IntTy,inc);
88     Instruction *addIndex=BinaryOperator::
89       create(Instruction::Add, ldIndex, val,"ti2");
90     
91     //now load count[addIndex]
92     Instruction *castInst=new CastInst(addIndex, 
93                                        Type::UIntTy,"ctin");
94     Instruction *ldInst=new 
95       LoadInst(countInst, vector<Value *>(1,castInst), "ti3");
96     Value *cons=ConstantSInt::get(Type::IntTy,1);
97     
98     //count[addIndex]++
99     Instruction *addIn=BinaryOperator::
100       create(Instruction::Add, ldInst, cons,"ti4");
101     Instruction *stInst=new 
102       StoreInst(addIn, countInst, 
103                 vector<Value *>(1,castInst));
104     
105     here=instList.insert(here,ldIndex)+1;
106     here=instList.insert(here,addIndex)+1;
107     here=instList.insert(here,castInst)+1;
108     here=instList.insert(here,ldInst)+1;
109     here=instList.insert(here,addIn)+1;
110     here=instList.insert(here,stInst)+1;
111     break;
112   }
113
114     //case: count[r]+
115   case 6:{
116     //ti1=inc+r
117     Instruction *ldIndex=new LoadInst(rInst, "ti1");
118
119     //now load count[addIndex]
120     Instruction *castInst2=new 
121       CastInst(ldIndex, Type::UIntTy,"ctin");
122     Instruction *ldInst=new 
123       LoadInst(countInst, vector<Value *>(1,castInst2), "ti2");
124     Value *cons=ConstantSInt::get(Type::IntTy,1);
125
126     //count[addIndex]++
127     Instruction *addIn=BinaryOperator::
128       create(Instruction::Add, ldInst, cons,"ti3"); 
129     Instruction *stInst=new 
130       StoreInst(addIn, countInst, vector<Value *>(1,castInst2));
131     
132     here=instList.insert(here,ldIndex)+1;
133     here=instList.insert(here,castInst2)+1;
134     here=instList.insert(here,ldInst)+1;
135     here=instList.insert(here,addIn)+1;
136     here=instList.insert(here,stInst)+1;
137     break;
138   }
139     
140   }
141   //now check for cdIn and cdOut
142   //first put cdOut
143   if(cdOut!=NULL){
144     cdOut->getCode(rInst, countInst, M, BB);
145   }
146   if(cdIn!=NULL){
147     cdIn->getCode(rInst, countInst, M, BB);
148   }
149
150 }
151
152
153
154 //Insert the initialization code in the top BB
155 //this includes initializing r, and count
156 //r is like an accumulator, that 
157 //keeps on adding increments as we traverse along a path
158 //and at the end of the path, r contains the path
159 //number of that path
160 //Count is an array, where Count[k] represents
161 //the number of executions of path k
162 void insertInTopBB(BasicBlock *front, 
163                    int k, 
164                    Instruction *rVar, 
165                    Instruction *countVar){
166   //rVar is variable r, 
167   //countVar is array Count, and these are allocatted outside
168   
169   //store uint 0, uint *%R, uint 0
170   vector<Value *> idx;
171   idx.push_back(ConstantUInt::get(Type::UIntTy, 0));
172   Instruction *stInstr=new StoreInst(ConstantInt::get(Type::IntTy, 0), rVar, 
173                                      idx);
174
175   //now push all instructions in front of the BB
176   BasicBlock::InstListType& instList=front->getInstList();
177   BasicBlock::iterator here=instList.begin();
178   here=front->getInstList().insert(here, rVar)+1;
179   here=front->getInstList().insert(here,countVar)+1;
180   
181   //Initialize Count[...] with 0
182   for(int i=0;i<k; i++){
183     Instruction *stInstrC=new 
184       StoreInst(ConstantInt::get(Type::IntTy, 0), 
185                 countVar, std::vector<Value *>
186                 (1,ConstantUInt::get(Type::UIntTy, i))); 
187     here=front->getInstList().insert(here,stInstrC)+1;
188   }
189   
190   here=front->getInstList().insert(here,stInstr)+1;
191 }
192
193
194 //insert a basic block with appropriate code
195 //along a given edge
196 void insertBB(Edge ed,
197               getEdgeCode *edgeCode, 
198               Instruction *rInst, 
199               Instruction *countInst){
200
201   BasicBlock* BB1=ed.getFirst()->getElement();
202   BasicBlock* BB2=ed.getSecond()->getElement();
203   
204 #ifdef DEBUG_PATH_PROFILES
205   //debugging info
206   cerr<<"Edges with codes ######################\n";
207   cerr<<BB1->getName()<<"->"<<BB2->getName()<<"\n";
208   cerr<<"########################\n";
209 #endif
210
211   //We need to insert a BB between BB1 and BB2 
212   TerminatorInst *TI=BB1->getTerminator();
213   BasicBlock *newBB=new BasicBlock("counter", BB1->getParent());
214
215   //get code for the new BB
216   edgeCode->getCode(rInst, countInst, BB1->getParent(), newBB);
217  
218   //Is terminator a branch instruction?
219   //then we need to change branch destinations to include new BB
220
221   BranchInst *BI=cast<BranchInst>(TI);
222  
223   if(BI->isUnconditional()){
224     BI->setUnconditionalDest(newBB);
225     Instruction *newBI2=new BranchInst(BB2);
226     newBB->getInstList().push_back(newBI2);
227   }
228   else{
229     Value *cond=BI->getCondition();
230     BasicBlock *fB, *tB;
231    
232     if(BI->getSuccessor(0)==BB2){
233       tB=newBB;
234       fB=BI->getSuccessor(1);
235     }
236     else{
237       fB=newBB;
238       tB=BI->getSuccessor(0);
239     }
240    
241     delete BB1->getInstList().pop_back();
242     Instruction *newBI=new BranchInst(tB,fB,cond);
243     Instruction *newBI2=new BranchInst(BB2);
244     BB1->getInstList().push_back(newBI);
245     newBB->getInstList().push_back(newBI2);
246   }
247   
248   //now iterate over BB2, and set its Phi nodes right
249   for(BasicBlock::iterator BB2Inst=BB2->begin(), BBend=BB2->end(); 
250       BB2Inst!=BBend; ++BB2Inst){
251    
252     if(PHINode *phiInst=dyn_cast<PHINode>(*BB2Inst)){
253 #ifdef DEBUG_PATH_PROFILES
254       cerr<<"YYYYYYYYYYYYYYYYY\n";
255 #endif
256      
257       int bbIndex=phiInst->getBasicBlockIndex(BB1);
258       if(bbIndex>=0)
259         phiInst->setIncomingBlock(bbIndex, newBB);
260     }
261   }
262 }