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