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