lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp

   1 //===-- EdgeCode.cpp - generate LLVM instrumentation code -----------------===//
   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/Constants.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 #include "llvm/Module.h"
  19 #include "Config/stdio.h"
  20
  21 #define INSERT_LOAD_COUNT
  22 #define INSERT_STORE
  23
  24 using std::vector;
  25
  26
  27 static void getTriggerCode(Module *M, BasicBlock *BB, int MethNo, Value *pathNo,
  28                            Value *cnt, Instruction *rInst){
  29
  30   vector<Value *> tmpVec;
  31   tmpVec.push_back(Constant::getNullValue(Type::LongTy));
  32   tmpVec.push_back(Constant::getNullValue(Type::LongTy));
  33   Instruction *Idx = new GetElementPtrInst(cnt, tmpVec, "");//,
  34   BB->getInstList().push_back(Idx);
  35
  36   const Type *PIntTy = PointerType::get(Type::IntTy);
  37   Function *trigMeth = M->getOrInsertFunction("trigger", Type::VoidTy,
  38                                               Type::IntTy, Type::IntTy,
  39                                               PIntTy, PIntTy, 0);
  40   assert(trigMeth && "trigger method could not be inserted!");
  41
  42   vector<Value *> trargs;
  43
  44   trargs.push_back(ConstantSInt::get(Type::IntTy,MethNo));
  45   trargs.push_back(pathNo);
  46   trargs.push_back(Idx);
  47   trargs.push_back(rInst);
  48
  49   Instruction *callInst=new CallInst(trigMeth, trargs, "");//, BB->begin());
  50   BB->getInstList().push_back(callInst);
  51   //triggerInst = new CallInst(trigMeth, trargs, "");//, InsertPos);
  52 }
  53
  54
  55 //get the code to be inserted on the edge
  56 //This is determined from cond (1-6)
  57 void getEdgeCode::getCode(Instruction *rInst, Value *countInst,
  58                           Function *M, BasicBlock *BB,
  59                           vector<Value *> &retVec){
  60
  61   //Instruction *InsertPos = BB->getInstList().begin();
  62
  63   //now check for cdIn and cdOut
  64   //first put cdOut
  65   if(cdOut!=NULL){
  66     cdOut->getCode(rInst, countInst, M, BB, retVec);
  67   }
  68
  69   if(cdIn!=NULL){
  70     cdIn->getCode(rInst, countInst, M, BB, retVec);
  71   }
  72
  73   //case: r=k code to be inserted
  74   switch(cond){
  75   case 1:{
  76     Value *val=ConstantSInt::get(Type::IntTy,inc);
  77 #ifdef INSERT_STORE
  78     Instruction *stInst=new StoreInst(val, rInst);//, InsertPos);
  79     BB->getInstList().push_back(stInst);
  80 #endif
  81     break;
  82     }
  83
  84   //case: r=0 to be inserted
  85   case 2:{
  86 #ifdef INSERT_STORE
  87     Instruction *stInst = new StoreInst(ConstantSInt::getNullValue(Type::IntTy), rInst);//, InsertPos);
  88      BB->getInstList().push_back(stInst);
  89 #endif
  90     break;
  91   }
  92
  93   //r+=k
  94   case 3:{
  95     Instruction *ldInst = new LoadInst(rInst, "ti1");//, InsertPos);
  96     BB->getInstList().push_back(ldInst);
  97     Value *val = ConstantSInt::get(Type::IntTy,inc);
  98     Instruction *addIn = BinaryOperator::create(Instruction::Add, ldInst, val,
  99                                           "ti2");//, InsertPos);
 100     BB->getInstList().push_back(addIn);
 101 #ifdef INSERT_STORE
 102     Instruction *stInst = new StoreInst(addIn, rInst);//, InsertPos);
 103     BB->getInstList().push_back(stInst);
 104 #endif
 105     break;
 106   }
 107
 108   //count[inc]++
 109   case 4:{
 110     vector<Value *> tmpVec;
 111     tmpVec.push_back(Constant::getNullValue(Type::LongTy));
 112     tmpVec.push_back(ConstantSInt::get(Type::LongTy, inc));
 113     Instruction *Idx = new GetElementPtrInst(countInst, tmpVec, "");//,
 114
 115     //Instruction *Idx = new GetElementPtrInst(countInst,
 116     //           vector<Value*>(1,ConstantSInt::get(Type::LongTy, inc)),
 117     //                                       "");//, InsertPos);
 118     BB->getInstList().push_back(Idx);
 119
 120     Instruction *ldInst=new LoadInst(Idx, "ti1");//, InsertPos);
 121     BB->getInstList().push_back(ldInst);
 122
 123     Value *val = ConstantSInt::get(Type::IntTy, 1);
 124     //Instruction *addIn =
 125     Instruction *newCount =
 126       BinaryOperator::create(Instruction::Add, ldInst, val,"ti2");
 127     BB->getInstList().push_back(newCount);
 128
 129
 130 #ifdef INSERT_STORE
 131     //Instruction *stInst=new StoreInst(addIn, Idx, InsertPos);
 132     Instruction *stInst=new StoreInst(newCount, Idx);//, InsertPos);
 133     BB->getInstList().push_back(stInst);
 134 #endif
 135
 136     Value *trAddIndex = ConstantSInt::get(Type::IntTy,inc);
 137
 138     retVec.push_back(newCount);
 139     retVec.push_back(trAddIndex);
 140     //insert trigger
 141     //getTriggerCode(M->getParent(), BB, MethNo,
 142     //     ConstantSInt::get(Type::IntTy,inc), newCount, triggerInst);
 143     //end trigger code
 144
 145     assert(inc>=0 && "IT MUST BE POSITIVE NOW");
 146     break;
 147   }
 148
 149   //case: count[r+inc]++
 150   case 5:{
 151
 152     //ti1=inc+r
 153     Instruction *ldIndex=new LoadInst(rInst, "ti1");//, InsertPos);
 154     BB->getInstList().push_back(ldIndex);
 155
 156     Value *val=ConstantSInt::get(Type::IntTy,inc);
 157     Instruction *addIndex=BinaryOperator::
 158       create(Instruction::Add, ldIndex, val,"ti2");//, InsertPos);
 159     BB->getInstList().push_back(addIndex);
 160
 161     //now load count[addIndex]
 162     Instruction *castInst=new CastInst(addIndex,
 163                                        Type::LongTy,"ctin");//, InsertPos);
 164     BB->getInstList().push_back(castInst);
 165
 166     vector<Value *> tmpVec;
 167     tmpVec.push_back(Constant::getNullValue(Type::LongTy));
 168     tmpVec.push_back(castInst);
 169     Instruction *Idx = new GetElementPtrInst(countInst, tmpVec, "");//,
 170     //                                             InsertPos);
 171     BB->getInstList().push_back(Idx);
 172
 173     Instruction *ldInst=new LoadInst(Idx, "ti3");//, InsertPos);
 174     BB->getInstList().push_back(ldInst);
 175
 176     Value *cons=ConstantSInt::get(Type::IntTy,1);
 177     //count[addIndex]++
 178     //std::cerr<<"Type ldInst:"<<ldInst->getType()<<"\t cons:"<<cons->getType()<<"\n";
 179     Instruction *newCount = BinaryOperator::create(Instruction::Add, ldInst,
 180                                                    cons,"");
 181     BB->getInstList().push_back(newCount);
 182
 183 #ifdef INSERT_STORE
 184     Instruction *stInst = new StoreInst(newCount, Idx);//, InsertPos);
 185     BB->getInstList().push_back(stInst);
 186 #endif
 187
 188     retVec.push_back(newCount);
 189     retVec.push_back(addIndex);
 190     //insert trigger
 191     //getTriggerCode(M->getParent(), BB, MethNo, addIndex, newCount, triggerInst);
 192     //end trigger code
 193
 194     break;
 195   }
 196
 197     //case: count[r]+
 198   case 6:{
 199     //ti1=inc+r
 200     Instruction *ldIndex=new LoadInst(rInst, "ti1");//, InsertPos);
 201     BB->getInstList().push_back(ldIndex);
 202
 203     //now load count[addIndex]
 204     Instruction *castInst2=new CastInst(ldIndex, Type::LongTy,"ctin");
 205     BB->getInstList().push_back(castInst2);
 206
 207     vector<Value *> tmpVec;
 208     tmpVec.push_back(Constant::getNullValue(Type::LongTy));
 209     tmpVec.push_back(castInst2);
 210     Instruction *Idx = new GetElementPtrInst(countInst, tmpVec, "");//,
 211
 212     //Instruction *Idx = new GetElementPtrInst(countInst,
 213     //                                       vector<Value*>(1,castInst2), "");
 214
 215     BB->getInstList().push_back(Idx);
 216
 217     Instruction *ldInst=new LoadInst(Idx, "ti2");//, InsertPos);
 218     BB->getInstList().push_back(ldInst);
 219
 220     Value *cons=ConstantSInt::get(Type::IntTy,1);
 221
 222     //count[addIndex]++
 223     Instruction *newCount = BinaryOperator::create(Instruction::Add, ldInst,
 224                                                    cons,"ti3");
 225     BB->getInstList().push_back(newCount);
 226
 227 #ifdef INSERT_STORE
 228     Instruction *stInst = new StoreInst(newCount, Idx);//, InsertPos);
 229     BB->getInstList().push_back(stInst);
 230 #endif
 231
 232     retVec.push_back(newCount);
 233     retVec.push_back(ldIndex);
 234     break;
 235   }
 236
 237   }
 238 }
 239
 240
 241
 242 //Insert the initialization code in the top BB
 243 //this includes initializing r, and count
 244 //r is like an accumulator, that
 245 //keeps on adding increments as we traverse along a path
 246 //and at the end of the path, r contains the path
 247 //number of that path
 248 //Count is an array, where Count[k] represents
 249 //the number of executions of path k
 250 void insertInTopBB(BasicBlock *front,
 251                    int k,
 252                    Instruction *rVar, Value *threshold){
 253   //rVar is variable r,
 254   //countVar is count[]
 255
 256   Value *Int0 = ConstantInt::get(Type::IntTy, 0);
 257
 258   //now push all instructions in front of the BB
 259   BasicBlock::iterator here=front->begin();
 260   front->getInstList().insert(here, rVar);
 261   //front->getInstList().insert(here,countVar);
 262
 263   //Initialize Count[...] with 0
 264
 265   //for (int i=0;i<k; i++){
 266   //Value *GEP2 = new GetElementPtrInst(countVar,
 267   //                      vector<Value *>(1,ConstantSInt::get(Type::LongTy, i)),
 268   //                                    "", here);
 269   //new StoreInst(Int0, GEP2, here);
 270   //}
 271
 272   //store uint 0, uint *%R
 273   new StoreInst(Int0, rVar, here);
 274 }
 275
 276
 277 //insert a basic block with appropriate code
 278 //along a given edge
 279 void insertBB(Edge ed,
 280               getEdgeCode *edgeCode,
 281               Instruction *rInst,
 282               Value *countInst,
 283               int numPaths, int Methno, Value *threshold){
 284
 285   BasicBlock* BB1=ed.getFirst()->getElement();
 286   BasicBlock* BB2=ed.getSecond()->getElement();
 287
 288 #ifdef DEBUG_PATH_PROFILES
 289   //debugging info
 290   cerr<<"Edges with codes ######################\n";
 291   cerr<<BB1->getName()<<"->"<<BB2->getName()<<"\n";
 292   cerr<<"########################\n";
 293 #endif
 294
 295   //We need to insert a BB between BB1 and BB2
 296   TerminatorInst *TI=BB1->getTerminator();
 297   BasicBlock *newBB=new BasicBlock("counter", BB1->getParent());
 298
 299   //get code for the new BB
 300   vector<Value *> retVec;
 301
 302   edgeCode->getCode(rInst, countInst, BB1->getParent(), newBB, retVec);
 303
 304   BranchInst *BI =  cast<BranchInst>(TI);
 305
 306   //Is terminator a branch instruction?
 307   //then we need to change branch destinations to include new BB
 308
 309   if(BI->isUnconditional()){
 310     BI->setUnconditionalDest(newBB);
 311   }
 312   else{
 313       if(BI->getSuccessor(0)==BB2)
 314       BI->setSuccessor(0, newBB);
 315
 316     if(BI->getSuccessor(1)==BB2)
 317       BI->setSuccessor(1, newBB);
 318   }
 319
 320   BasicBlock *triggerBB = NULL;
 321   if(retVec.size()>0){
 322     triggerBB = new BasicBlock("trigger", BB1->getParent());
 323     getTriggerCode(BB1->getParent()->getParent(), triggerBB, Methno,
 324                    retVec[1], countInst, rInst);//retVec[0]);
 325
 326     //Instruction *castInst = new CastInst(retVec[0], Type::IntTy, "");
 327     Instruction *etr = new LoadInst(threshold, "threshold");
 328
 329     //std::cerr<<"type1: "<<etr->getType()<<" type2: "<<retVec[0]->getType()<<"\n";
 330     Instruction *cmpInst = new SetCondInst(Instruction::SetLE, etr,
 331                                            retVec[0], "");
 332     Instruction *newBI2 = new BranchInst(triggerBB, BB2, cmpInst);
 333     //newBB->getInstList().push_back(castInst);
 334     newBB->getInstList().push_back(etr);
 335     newBB->getInstList().push_back(cmpInst);
 336     newBB->getInstList().push_back(newBI2);
 337
 338     //triggerBB->getInstList().push_back(triggerInst);
 339     Instruction *triggerBranch = new BranchInst(BB2);
 340     triggerBB->getInstList().push_back(triggerBranch);
 341   }
 342   else{
 343     Instruction *newBI2=new BranchInst(BB2);
 344     newBB->getInstList().push_back(newBI2);
 345   }
 346
 347   //now iterate over BB2, and set its Phi nodes right
 348   for(BasicBlock::iterator BB2Inst = BB2->begin(), BBend = BB2->end();
 349       BB2Inst != BBend; ++BB2Inst){
 350
 351     if(PHINode *phiInst=dyn_cast<PHINode>(BB2Inst)){
 352       int bbIndex=phiInst->getBasicBlockIndex(BB1);
 353       assert(bbIndex>=0);
 354       phiInst->setIncomingBlock(bbIndex, newBB);
 355
 356       ///check if trigger!=null, then add value corresponding to it too!
 357       if(retVec.size()>0){
 358         assert(triggerBB && "BasicBlock with trigger should not be null!");
 359         Value *vl = phiInst->getIncomingValue((unsigned int)bbIndex);
 360         phiInst->addIncoming(vl, triggerBB);
 361       }
 362     }
 363   }
 364 }
 365