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