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