lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp

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