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 *ldInst=new
 148       LoadInst(countInst,vector<Value *>
 149                (1,ConstantUInt::get(Type::UIntTy, inc)), "ti1");
 150     Value *val=ConstantSInt::get(Type::IntTy,1);
 151     Instruction *addIn=BinaryOperator::
 152       create(Instruction::Add, ldInst, val,"ti2");
 153
 154     //insert trigger
 155     getTriggerCode(M->getParent(), BB, MethNo,
 156                    ConstantSInt::get(Type::IntTy,inc), addIn);
 157     here=instList.begin();
 158     //end trigger code
 159
 160     assert(inc>=0 && "IT MUST BE POSITIVE NOW");
 161 #ifdef INSERT_STORE
 162     Instruction *stInst=new
 163       StoreInst(addIn, countInst, vector<Value *>
 164                 (1, ConstantUInt::get(Type::UIntTy,inc)));
 165 #endif
 166     here = ++instList.insert(here,ldInst);
 167     here = ++instList.insert(here,addIn);
 168 #ifdef INSERT_STORE
 169     here = ++instList.insert(here,stInst);
 170 #endif
 171     break;
 172   }
 173
 174   //case: count[r+inc]++
 175   case 5:{
 176
 177     //ti1=inc+r
 178     Instruction *ldIndex=new LoadInst(rInst, "ti1");
 179     Value *val=ConstantSInt::get(Type::IntTy,inc);
 180     Instruction *addIndex=BinaryOperator::
 181       create(Instruction::Add, ldIndex, val,"ti2");
 182     //erase following 1 line
 183     //Value *valtemp=ConstantSInt::get(Type::IntTy,999);
 184     //now load count[addIndex]
 185
 186     Instruction *castInst=new CastInst(addIndex,
 187                                        Type::UIntTy,"ctin");
 188     Instruction *ldInst=new
 189       LoadInst(countInst, vector<Value *>(1,castInst), "ti3");
 190     Value *cons=ConstantSInt::get(Type::IntTy,1);
 191     //count[addIndex]++
 192     Instruction *addIn=BinaryOperator::
 193       create(Instruction::Add, ldInst, cons,"ti4");
 194
 195     //insert trigger
 196     getTriggerCode(M->getParent(), BB, MethNo, addIndex, addIn);
 197     here=instList.begin();
 198     //end trigger code
 199
 200 #ifdef INSERT_STORE
 201     ///*
 202     Instruction *stInst=new
 203       StoreInst(addIn, countInst,
 204                 vector<Value *>(1,castInst));
 205     //*/
 206 #endif
 207     here = ++instList.insert(here,ldIndex);
 208     here = ++instList.insert(here,addIndex);
 209     here = ++instList.insert(here,castInst);
 210     here = ++instList.insert(here,ldInst);
 211     here = ++instList.insert(here,addIn);
 212 #ifdef INSERT_STORE
 213     here = ++instList.insert(here,stInst);
 214 #endif
 215     break;
 216   }
 217
 218     //case: count[r]+
 219   case 6:{
 220
 221     //ti1=inc+r
 222     Instruction *ldIndex=new LoadInst(rInst, "ti1");
 223
 224     //now load count[addIndex]
 225     Instruction *castInst2=new
 226       CastInst(ldIndex, Type::UIntTy,"ctin");
 227     Instruction *ldInst=new
 228       LoadInst(countInst, vector<Value *>(1,castInst2), "ti2");
 229     Value *cons=ConstantSInt::get(Type::IntTy,1);
 230
 231     //count[addIndex]++
 232     Instruction *addIn=BinaryOperator::
 233       create(Instruction::Add, ldInst, cons,"ti3");
 234
 235     //insert trigger
 236     getTriggerCode(M->getParent(), BB, MethNo, ldIndex, addIn);
 237     here=instList.begin();
 238     //end trigger code
 239 #ifdef INSERT_STORE
 240     Instruction *stInst=new
 241       StoreInst(addIn, countInst, vector<Value *>(1,castInst2));
 242 #endif
 243     here = ++instList.insert(here,ldIndex);
 244     here = ++instList.insert(here,castInst2);
 245     here = instList.insert(here,ldInst);
 246     here = instList.insert(here,addIn);
 247 #ifdef INSERT_STORE
 248     here = instList.insert(here,stInst);
 249 #endif
 250     break;
 251   }
 252
 253   }
 254   //now check for cdIn and cdOut
 255   //first put cdOut
 256   if(cdIn!=NULL){
 257     cdIn->getCode(rInst, countInst, M, BB, numPaths, MethNo);
 258   }
 259   if(cdOut!=NULL){
 260     cdOut->getCode(rInst, countInst, M, BB, numPaths, MethNo);
 261   }
 262 }
 263
 264
 265
 266 //Insert the initialization code in the top BB
 267 //this includes initializing r, and count
 268 //r is like an accumulator, that
 269 //keeps on adding increments as we traverse along a path
 270 //and at the end of the path, r contains the path
 271 //number of that path
 272 //Count is an array, where Count[k] represents
 273 //the number of executions of path k
 274 void insertInTopBB(BasicBlock *front,
 275                    int k,
 276                    Instruction *rVar,
 277                    Instruction *countVar){
 278   //rVar is variable r,
 279   //countVar is array Count, and these are allocatted outside
 280
 281   //store uint 0, uint *%R, uint 0
 282   vector<Value *> idx;
 283   idx.push_back(ConstantUInt::get(Type::UIntTy, 0));
 284   Instruction *stInstr=new StoreInst(ConstantInt::get(Type::IntTy, 0), rVar,
 285                                      idx);
 286
 287   //now push all instructions in front of the BB
 288   BasicBlock::InstListType& instList=front->getInstList();
 289   BasicBlock::iterator here=instList.begin();
 290   here=++front->getInstList().insert(here, rVar);
 291   here=++front->getInstList().insert(here,countVar);
 292
 293   //Initialize Count[...] with 0
 294
 295   for(int i=0;i<k; i++){
 296     Instruction *stInstrC=new
 297       StoreInst(ConstantInt::get(Type::IntTy, 0),
 298                 countVar, std::vector<Value *>
 299                 (1,ConstantUInt::get(Type::UIntTy, i)));
 300     here=++front->getInstList().insert(here,stInstrC);
 301   }
 302
 303   here = ++front->getInstList().insert(here,stInstr);
 304 }
 305
 306
 307 //insert a basic block with appropriate code
 308 //along a given edge
 309 void insertBB(Edge ed,
 310               getEdgeCode *edgeCode,
 311               Instruction *rInst,
 312               Instruction *countInst,
 313               int numPaths, int Methno){
 314   static int i=-1;
 315   i++;
 316   BasicBlock* BB1=ed.getFirst()->getElement();
 317   BasicBlock* BB2=ed.getSecond()->getElement();
 318
 319 #ifdef DEBUG_PATH_PROFILES
 320   //debugging info
 321   cerr<<"Edges with codes ######################\n";
 322   cerr<<BB1->getName()<<"->"<<BB2->getName()<<"\n";
 323   cerr<<"########################\n";
 324 #endif
 325
 326   char counterstr[100];
 327   sprintf(counterstr,"counter%d",i);
 328   std::string ctr=counterstr;
 329
 330   //We need to insert a BB between BB1 and BB2
 331   TerminatorInst *TI=BB1->getTerminator();
 332   BasicBlock *newBB=new BasicBlock(ctr, BB1->getParent());
 333
 334   //get code for the new BB
 335   edgeCode->getCode(rInst, countInst, BB1->getParent(), newBB, numPaths, Methno);
 336
 337   //Is terminator a branch instruction?
 338   //then we need to change branch destinations to include new BB
 339
 340   //std::cerr<<"before cast!\n";
 341   BranchInst *BI =  cast<BranchInst>(TI);
 342
 343   if(BI->isUnconditional()){
 344     BI->setUnconditionalDest(newBB);
 345     Instruction *newBI2=new BranchInst(BB2);
 346     newBB->getInstList().push_back(newBI2);
 347   }
 348   else{
 349       if(BI->getSuccessor(0)==BB2)
 350       BI->setSuccessor(0, newBB);
 351
 352     if(BI->getSuccessor(1)==BB2)
 353       BI->setSuccessor(1, newBB);
 354
 355     Instruction *newBI2=new BranchInst(BB2);
 356     newBB->getInstList().push_back(newBI2);
 357   }
 358
 359   //std::cerr<<"After casting\n";
 360   //get code for the new BB
 361    //now iterate over BB2, and set its Phi nodes right
 362   for(BasicBlock::iterator BB2Inst = BB2->begin(), BBend = BB2->end();
 363       BB2Inst != BBend; ++BB2Inst){
 364
 365     if(PHINode *phiInst=dyn_cast<PHINode>(&*BB2Inst)){
 366       int bbIndex=phiInst->getBasicBlockIndex(BB1);
 367       assert(bbIndex>=0);
 368       phiInst->setIncomingBlock(bbIndex, newBB);
 369     }
 370   }
 371 }
 372