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 "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
  20 using std::vector;
  21
  22 //get the code to be inserted on the edge
  23 //This is determined from cond (1-6)
  24 void getEdgeCode::getCode(Instruction *rInst,
  25                           Instruction *countInst,
  26                           Function *M,
  27                           BasicBlock *BB){
  28
  29   BasicBlock::InstListType& instList=BB->getInstList();
  30   BasicBlock::iterator here=instList.begin();
  31
  32   //case: r=k code to be inserted
  33   switch(cond){
  34   case 1:{
  35     Value *val=ConstantSInt::get(Type::IntTy,inc);
  36     Instruction *stInst=new StoreInst(val, rInst);
  37     here=instList.insert(here,stInst)+1;
  38     break;
  39     }
  40
  41   //case: r=0 to be inserted
  42   case 2:{
  43     Value *val=ConstantSInt::get(Type::IntTy,0);
  44     Instruction *stInst=new StoreInst(val, rInst);
  45     here=instList.insert(here,stInst)+1;
  46     break;
  47   }
  48
  49   //r+=k
  50   case 3:{
  51     Instruction *ldInst=new LoadInst(rInst, "ti1");
  52     Value *val=ConstantSInt::get(Type::IntTy,inc);
  53     Instruction *addIn=BinaryOperator::
  54       create(Instruction::Add, ldInst, val,"ti2");
  55
  56     Instruction *stInst=new StoreInst(addIn, rInst);
  57     here=instList.insert(here,ldInst)+1;
  58     here=instList.insert(here,addIn)+1;
  59     here=instList.insert(here,stInst)+1;
  60     break;
  61   }
  62
  63   //count[inc]++
  64   case 4:{
  65     Instruction *ldInst=new
  66       LoadInst(countInst,vector<Value *>
  67                (1,ConstantUInt::get(Type::UIntTy, inc)), "ti1");
  68     Value *val=ConstantSInt::get(Type::IntTy,1);
  69     Instruction *addIn=BinaryOperator::
  70       create(Instruction::Add, ldInst, val,"ti2");
  71
  72     assert(inc>=0 && "IT MUST BE POSITIVE NOW");
  73     Instruction *stInst=new
  74       StoreInst(addIn, countInst, vector<Value *>
  75                 (1, ConstantUInt::get(Type::UIntTy,inc)));
  76
  77     here=instList.insert(here,ldInst)+1;
  78     here=instList.insert(here,addIn)+1;
  79     here=instList.insert(here,stInst)+1;
  80     break;
  81   }
  82
  83   //case: count[r+inc]++
  84   case 5:{
  85     //ti1=inc+r
  86     Instruction *ldIndex=new LoadInst(rInst, "ti1");
  87     Value *val=ConstantSInt::get(Type::IntTy,inc);
  88     Instruction *addIndex=BinaryOperator::
  89       create(Instruction::Add, ldIndex, val,"ti2");
  90
  91     //now load count[addIndex]
  92     Instruction *castInst=new CastInst(addIndex,
  93                                        Type::UIntTy,"ctin");
  94     Instruction *ldInst=new
  95       LoadInst(countInst, vector<Value *>(1,castInst), "ti3");
  96     Value *cons=ConstantSInt::get(Type::IntTy,1);
  97
  98     //count[addIndex]++
  99     Instruction *addIn=BinaryOperator::
 100       create(Instruction::Add, ldInst, cons,"ti4");
 101     Instruction *stInst=new
 102       StoreInst(addIn, countInst,
 103                 vector<Value *>(1,castInst));
 104
 105     here=instList.insert(here,ldIndex)+1;
 106     here=instList.insert(here,addIndex)+1;
 107     here=instList.insert(here,castInst)+1;
 108     here=instList.insert(here,ldInst)+1;
 109     here=instList.insert(here,addIn)+1;
 110     here=instList.insert(here,stInst)+1;
 111     break;
 112   }
 113
 114     //case: count[r]+
 115   case 6:{
 116     //ti1=inc+r
 117     Instruction *ldIndex=new LoadInst(rInst, "ti1");
 118
 119     //now load count[addIndex]
 120     Instruction *castInst2=new
 121       CastInst(ldIndex, Type::UIntTy,"ctin");
 122     Instruction *ldInst=new
 123       LoadInst(countInst, vector<Value *>(1,castInst2), "ti2");
 124     Value *cons=ConstantSInt::get(Type::IntTy,1);
 125
 126     //count[addIndex]++
 127     Instruction *addIn=BinaryOperator::
 128       create(Instruction::Add, ldInst, cons,"ti3");
 129     Instruction *stInst=new
 130       StoreInst(addIn, countInst, vector<Value *>(1,castInst2));
 131
 132     here=instList.insert(here,ldIndex)+1;
 133     here=instList.insert(here,castInst2)+1;
 134     here=instList.insert(here,ldInst)+1;
 135     here=instList.insert(here,addIn)+1;
 136     here=instList.insert(here,stInst)+1;
 137     break;
 138   }
 139
 140   }
 141   //now check for cdIn and cdOut
 142   //first put cdOut
 143   if(cdOut!=NULL){
 144     cdOut->getCode(rInst, countInst, M, BB);
 145   }
 146   if(cdIn!=NULL){
 147     cdIn->getCode(rInst, countInst, M, BB);
 148   }
 149
 150 }
 151
 152
 153
 154 //Insert the initialization code in the top BB
 155 //this includes initializing r, and count
 156 //r is like an accumulator, that
 157 //keeps on adding increments as we traverse along a path
 158 //and at the end of the path, r contains the path
 159 //number of that path
 160 //Count is an array, where Count[k] represents
 161 //the number of executions of path k
 162 void insertInTopBB(BasicBlock *front,
 163                    int k,
 164                    Instruction *rVar,
 165                    Instruction *countVar){
 166   //rVar is variable r,
 167   //countVar is array Count, and these are allocatted outside
 168
 169   //store uint 0, uint *%R, uint 0
 170   vector<Value *> idx;
 171   idx.push_back(ConstantUInt::get(Type::UIntTy, 0));
 172   Instruction *stInstr=new StoreInst(ConstantInt::get(Type::IntTy, 0), rVar,
 173                                      idx);
 174
 175   //now push all instructions in front of the BB
 176   BasicBlock::InstListType& instList=front->getInstList();
 177   BasicBlock::iterator here=instList.begin();
 178   here=front->getInstList().insert(here, rVar)+1;
 179   here=front->getInstList().insert(here,countVar)+1;
 180
 181   //Initialize Count[...] with 0
 182   for(int i=0;i<k; i++){
 183     Instruction *stInstrC=new
 184       StoreInst(ConstantInt::get(Type::IntTy, 0),
 185                 countVar, std::vector<Value *>
 186                 (1,ConstantUInt::get(Type::UIntTy, i)));
 187     here=front->getInstList().insert(here,stInstrC)+1;
 188   }
 189
 190   here=front->getInstList().insert(here,stInstr)+1;
 191 }
 192
 193
 194 //insert a basic block with appropriate code
 195 //along a given edge
 196 void insertBB(Edge ed,
 197               getEdgeCode *edgeCode,
 198               Instruction *rInst,
 199               Instruction *countInst){
 200
 201   BasicBlock* BB1=ed.getFirst()->getElement();
 202   BasicBlock* BB2=ed.getSecond()->getElement();
 203
 204 #ifdef DEBUG_PATH_PROFILES
 205   //debugging info
 206   cerr<<"Edges with codes ######################\n";
 207   cerr<<BB1->getName()<<"->"<<BB2->getName()<<"\n";
 208   cerr<<"########################\n";
 209 #endif
 210
 211   //We need to insert a BB between BB1 and BB2
 212   TerminatorInst *TI=BB1->getTerminator();
 213   BasicBlock *newBB=new BasicBlock("counter", BB1->getParent());
 214
 215   //get code for the new BB
 216   edgeCode->getCode(rInst, countInst, BB1->getParent(), newBB);
 217
 218   //Is terminator a branch instruction?
 219   //then we need to change branch destinations to include new BB
 220
 221   BranchInst *BI=cast<BranchInst>(TI);
 222
 223   if(BI->isUnconditional()){
 224     BI->setUnconditionalDest(newBB);
 225     Instruction *newBI2=new BranchInst(BB2);
 226     newBB->getInstList().push_back(newBI2);
 227   }
 228   else{
 229     Value *cond=BI->getCondition();
 230     BasicBlock *fB, *tB;
 231
 232     if(BI->getSuccessor(0)==BB2){
 233       tB=newBB;
 234       fB=BI->getSuccessor(1);
 235     }
 236     else{
 237       fB=newBB;
 238       tB=BI->getSuccessor(0);
 239     }
 240
 241     delete BB1->getInstList().pop_back();
 242     Instruction *newBI=new BranchInst(tB,fB,cond);
 243     Instruction *newBI2=new BranchInst(BB2);
 244     BB1->getInstList().push_back(newBI);
 245     newBB->getInstList().push_back(newBI2);
 246   }
 247
 248   //now iterate over BB2, and set its Phi nodes right
 249   for(BasicBlock::iterator BB2Inst=BB2->begin(), BBend=BB2->end();
 250       BB2Inst!=BBend; ++BB2Inst){
 251
 252     if(PHINode *phiInst=dyn_cast<PHINode>(*BB2Inst)){
 253 #ifdef DEBUG_PATH_PROFILES
 254       cerr<<"YYYYYYYYYYYYYYYYY\n";
 255 #endif
 256
 257       int bbIndex=phiInst->getBasicBlockIndex(BB1);
 258       if(bbIndex>=0)
 259         phiInst->setIncomingBlock(bbIndex, newBB);
 260     }
 261   }
 262 }