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