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 <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<const Type*> args;
  31   //args.push_back(PointerType::get(Type::SByteTy));
  32   args.push_back(Type::IntTy);
  33   args.push_back(Type::IntTy);
  34   //args.push_back(Type::IntTy);
  35   args.push_back(PointerType::get(Type::IntTy));
  36   args.push_back(PointerType::get(Type::IntTy));
  37   const FunctionType *MTy = FunctionType::get(Type::VoidTy, args, false);
  38
  39   vector<Value *> tmpVec;
  40   tmpVec.push_back(Constant::getNullValue(Type::LongTy));
  41   tmpVec.push_back(Constant::getNullValue(Type::LongTy));
  42   Instruction *Idx = new GetElementPtrInst(cnt, tmpVec, "");//,
  43   BB->getInstList().push_back(Idx);
  44
  45   Function *trigMeth = M->getOrInsertFunction("trigger", MTy);
  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   //insert initialize function for initializing
 282   //vector<const Type*> inCountArgs;
 283   //inCountArgs.push_back(PointerType::get(Type::IntTy));
 284   //inCountArgs.push_back(Type::IntTy);
 285
 286   //const FunctionType *cFty = FunctionType::get(Type::VoidTy, inCountArgs,
 287   //                                               false);
 288 //Function *inCountMth = front->getParent()->getParent()->getOrInsertFunction("llvmInitializeCounter", cFty);
 289 //assert(inCountMth && "Initialize method could not be inserted!");
 290
 291 //vector<Value *> iniArgs;
 292 //iniArgs.push_back(countVar);
 293 //iniArgs.push_back(ConstantSInt::get(Type::IntTy, k));
 294 //new CallInst(inCountMth, iniArgs, "", here);
 295
 296
 297   if(front->getParent()->getName() == "main"){
 298     //intialize threshold
 299     vector<const Type*> initialize_args;
 300     initialize_args.push_back(PointerType::get(Type::IntTy));
 301
 302     const FunctionType *Fty = FunctionType::get(Type::VoidTy, initialize_args,
 303                                                 false);
 304     Function *initialMeth = front->getParent()->getParent()->getOrInsertFunction("reoptimizerInitialize", Fty);
 305     assert(initialMeth && "Initialize method could not be inserted!");
 306
 307     vector<Value *> trargs;
 308     trargs.push_back(threshold);
 309
 310     new CallInst(initialMeth, trargs, "", here);
 311   }
 312 }
 313
 314
 315 //insert a basic block with appropriate code
 316 //along a given edge
 317 void insertBB(Edge ed,
 318               getEdgeCode *edgeCode,
 319               Instruction *rInst,
 320               Value *countInst,
 321               int numPaths, int Methno, Value *threshold){
 322
 323   BasicBlock* BB1=ed.getFirst()->getElement();
 324   BasicBlock* BB2=ed.getSecond()->getElement();
 325
 326 #ifdef DEBUG_PATH_PROFILES
 327   //debugging info
 328   cerr<<"Edges with codes ######################\n";
 329   cerr<<BB1->getName()<<"->"<<BB2->getName()<<"\n";
 330   cerr<<"########################\n";
 331 #endif
 332
 333   //We need to insert a BB between BB1 and BB2
 334   TerminatorInst *TI=BB1->getTerminator();
 335   BasicBlock *newBB=new BasicBlock("counter", BB1->getParent());
 336
 337   //get code for the new BB
 338   vector<Value *> retVec;
 339
 340   edgeCode->getCode(rInst, countInst, BB1->getParent(), newBB, retVec);
 341
 342   BranchInst *BI =  cast<BranchInst>(TI);
 343
 344   //Is terminator a branch instruction?
 345   //then we need to change branch destinations to include new BB
 346
 347   if(BI->isUnconditional()){
 348     BI->setUnconditionalDest(newBB);
 349   }
 350   else{
 351       if(BI->getSuccessor(0)==BB2)
 352       BI->setSuccessor(0, newBB);
 353
 354     if(BI->getSuccessor(1)==BB2)
 355       BI->setSuccessor(1, newBB);
 356   }
 357
 358   BasicBlock *triggerBB = NULL;
 359   if(retVec.size()>0){
 360     triggerBB = new BasicBlock("trigger", BB1->getParent());
 361     getTriggerCode(BB1->getParent()->getParent(), triggerBB, Methno,
 362                    retVec[1], countInst, rInst);//retVec[0]);
 363
 364     //Instruction *castInst = new CastInst(retVec[0], Type::IntTy, "");
 365     Instruction *etr = new LoadInst(threshold, "threshold");
 366
 367     //std::cerr<<"type1: "<<etr->getType()<<" type2: "<<retVec[0]->getType()<<"\n";
 368     Instruction *cmpInst = new SetCondInst(Instruction::SetLE, etr,
 369                                            retVec[0], "");
 370     Instruction *newBI2 = new BranchInst(triggerBB, BB2, cmpInst);
 371     //newBB->getInstList().push_back(castInst);
 372     newBB->getInstList().push_back(etr);
 373     newBB->getInstList().push_back(cmpInst);
 374     newBB->getInstList().push_back(newBI2);
 375
 376     //triggerBB->getInstList().push_back(triggerInst);
 377     Instruction *triggerBranch = new BranchInst(BB2);
 378     triggerBB->getInstList().push_back(triggerBranch);
 379   }
 380   else{
 381     Instruction *newBI2=new BranchInst(BB2);
 382     newBB->getInstList().push_back(newBI2);
 383   }
 384
 385   //now iterate over BB2, and set its Phi nodes right
 386   for(BasicBlock::iterator BB2Inst = BB2->begin(), BBend = BB2->end();
 387       BB2Inst != BBend; ++BB2Inst){
 388
 389     if(PHINode *phiInst=dyn_cast<PHINode>(BB2Inst)){
 390       int bbIndex=phiInst->getBasicBlockIndex(BB1);
 391       assert(bbIndex>=0);
 392       phiInst->setIncomingBlock(bbIndex, newBB);
 393
 394       ///check if trigger!=null, then add value corresponding to it too!
 395       if(retVec.size()>0){
 396         assert(triggerBB && "BasicBlock with trigger should not be null!");
 397         Value *vl = phiInst->getIncomingValue((unsigned int)bbIndex);
 398         phiInst->addIncoming(vl, triggerBB);
 399       }
 400     }
 401   }
 402 }
 403