lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp

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