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