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