lib/Transforms/Instrumentation/TraceValues.cpp

   1 // $Id$
   2 //***************************************************************************
   3 // File:
   4 //      TraceValues.cpp
   5 //
   6 // Purpose:
   7 //      Support for inserting LLVM code to print values at basic block
   8 //      and method exits.  Also exports functions to create a call
   9 //      "printf" instruction with one of the signatures listed below.
  10 //
  11 // History:
  12 //      10/11/01         -  Vikram Adve  -  Created
  13 //**************************************************************************/
  14
  15
  16 #include "llvm/Transforms/Instrumentation/TraceValues.h"
  17 #include "llvm/GlobalVariable.h"
  18 #include "llvm/ConstPoolVals.h"
  19 #include "llvm/Type.h"
  20 #include "llvm/DerivedTypes.h"
  21 #include "llvm/Instruction.h"
  22 #include "llvm/iMemory.h"
  23 #include "llvm/iTerminators.h"
  24 #include "llvm/iOther.h"
  25 #include "llvm/BasicBlock.h"
  26 #include "llvm/Method.h"
  27 #include "llvm/Module.h"
  28 #include "llvm/SymbolTable.h"
  29 #include "llvm/Assembly/Writer.h"
  30 #include "llvm/Support/HashExtras.h"
  31 #include <hash_set>
  32 #include <sstream>
  33
  34
  35 static const char*
  36 PrintMethodNameForType(const Type* type)
  37 {
  38   if (PointerType* pty = dyn_cast<PointerType>(type))
  39     {
  40       const Type* elemTy;
  41       if (ArrayType* aty = dyn_cast<ArrayType>(pty->getValueType()))
  42         elemTy = aty->getElementType();
  43       else
  44         elemTy = pty->getValueType();
  45       if (elemTy == Type::SByteTy || elemTy == Type::UByteTy)
  46         return "printString";
  47     }
  48
  49   switch (type->getPrimitiveID())
  50     {
  51     case Type::BoolTyID:    return "printBool";
  52     case Type::UByteTyID:   return "printUByte";
  53     case Type::SByteTyID:   return "printSByte";
  54     case Type::UShortTyID:  return "printUShort";
  55     case Type::ShortTyID:   return "printShort";
  56     case Type::UIntTyID:    return "printUInt";
  57     case Type::IntTyID:     return "printInt";
  58     case Type::ULongTyID:   return "printULong";
  59     case Type::LongTyID:    return "printLong";
  60     case Type::FloatTyID:   return "printFloat";
  61     case Type::DoubleTyID:  return "printDouble";
  62     case Type::PointerTyID: return "printPointer";
  63     default:
  64       assert(0 && "Unsupported type for printing");
  65       return NULL;
  66     }
  67 }
  68
  69 static inline GlobalVariable *GetStringRef(Module *M, const string &str) {
  70   ConstPoolArray *Init = ConstPoolArray::get(str);
  71   GlobalVariable *GV = new GlobalVariable(Init->getType(), /*Const*/true, Init);
  72   M->getGlobalList().push_back(GV);
  73   return GV;
  74 }
  75
  76
  77 static inline bool
  78 TraceThisOpCode(unsigned opCode)
  79 {
  80   // Explicitly test for opCodes *not* to trace so that any new opcodes will
  81   // be traced by default (VoidTy's are already excluded)
  82   //
  83   return (opCode  < Instruction::FirstOtherOp &&
  84           opCode != Instruction::Alloca &&
  85           opCode != Instruction::PHINode &&
  86           opCode != Instruction::Cast);
  87 }
  88
  89 //
  90 // Check if this instruction has any uses outside its basic block,
  91 // or if it used by either a Call or Return instruction.
  92 //
  93 static inline bool
  94 LiveAtBBExit(Instruction* I)
  95 {
  96   BasicBlock* bb = I->getParent();
  97   bool isLive = false;
  98   for (Value::use_const_iterator U = I->use_begin(); U != I->use_end(); ++U)
  99     {
 100       const Instruction* userI = dyn_cast<Instruction>(*U);
 101       if (userI == NULL
 102           || userI->getParent() != bb
 103           || userI->getOpcode() == Instruction::Call
 104           || userI->getOpcode() == Instruction::Ret)
 105         isLive = true;
 106     }
 107   return isLive;
 108 }
 109
 110
 111 static void
 112 FindValuesToTraceInBB(BasicBlock* bb, vector<Instruction*>& valuesToTraceInBB)
 113 {
 114   for (BasicBlock::iterator II = bb->begin(); II != bb->end(); ++II)
 115     if ((*II)->getOpcode() == Instruction::Store
 116         || (LiveAtBBExit(*II) &&
 117             (*II)->getType()->isPrimitiveType() &&
 118             (*II)->getType() != Type::VoidTy &&
 119             TraceThisOpCode((*II)->getOpcode())))
 120       {
 121         valuesToTraceInBB.push_back(*II);
 122       }
 123 }
 124
 125 //
 126 // Let's save this code for future use; it has been tested and works:
 127 //
 128 // The signatures of the printf methods supported are:
 129 //   int printf(ubyte*,  ubyte*,  ubyte*,  ubyte*,  int      intValue)
 130 //   int printf(ubyte*,  ubyte*,  ubyte*,  ubyte*,  unsigned uintValue)
 131 //   int printf(ubyte*,  ubyte*,  ubyte*,  ubyte*,  float    floatValue)
 132 //   int printf(ubyte*,  ubyte*,  ubyte*,  ubyte*,  double   doubleValue)
 133 //   int printf(ubyte*,  ubyte*,  ubyte*,  ubyte*,  char*    stringValue)
 134 //   int printf(ubyte*,  ubyte*,  ubyte*,  ubyte*,  void*    ptrValue)
 135 //
 136 // The invocation should be:
 137 //       call "printf"(fmt, bbName, valueName, valueTypeName, value).
 138 //
 139 Value *GetPrintfMethodForType(Module* module, const Type* valueType)
 140 {
 141   PointerType *ubytePtrTy = PointerType::get(ArrayType::get(Type::UByteTy));
 142   vector<const Type*> argTypesVec(4, ubytePtrTy);
 143   argTypesVec.push_back(valueType);
 144
 145   MethodType *printMethodTy = MethodType::get(Type::IntTy, argTypesVec,
 146                                               /*isVarArg*/ false);
 147
 148   SymbolTable *ST = module->getSymbolTable();
 149   if (Value *Meth = ST->lookup(PointerType::get(printMethodTy), "printf"))
 150     return Meth;
 151
 152   // Create a new method and add it to the module
 153   Method *printMethod = new Method(printMethodTy, "printf");
 154   module->getMethodList().push_back(printMethod);
 155
 156   return printMethod;
 157 }
 158
 159
 160 Instruction*
 161 CreatePrintfInstr(Value* val,
 162                   const BasicBlock* bb,
 163                   Module* module,
 164                   unsigned int indent,
 165                   bool isMethodExit)
 166 {
 167   ostringstream fmtString, scopeNameString, valNameString;
 168   vector<Value*> paramList;
 169   const Type* valueType = val->getType();
 170   Method* printMethod = cast<Method>(GetPrintfMethodForType(module,valueType));
 171
 172   if (! valueType->isPrimitiveType() ||
 173       valueType->getPrimitiveID() == Type::VoidTyID ||
 174       valueType->getPrimitiveID() == Type::TypeTyID ||
 175       valueType->getPrimitiveID() == Type::LabelTyID)
 176     {
 177       assert(0 && "Unsupported type for printing");
 178       return NULL;
 179     }
 180
 181   const Value* scopeToUse = (isMethodExit)? (const Value*) bb->getParent()
 182                                           : (const Value*) bb;
 183   if (scopeToUse->hasName())
 184     scopeNameString << scopeToUse->getName() << ends;
 185   else
 186     scopeNameString << scopeToUse << ends;
 187
 188   if (val->hasName())
 189     valNameString << val->getName() << ends;
 190   else
 191     valNameString << val << ends;
 192
 193   for (unsigned i=0; i < indent; i++)
 194     fmtString << " ";
 195
 196   fmtString << " At exit of "
 197             << ((isMethodExit)? "Method " : "BB ")
 198             << "%s : val %s = %s ";
 199
 200   GlobalVariable* scopeNameVal = GetStringRef(module, scopeNameString.str());
 201   GlobalVariable* valNameVal   = GetStringRef(module,valNameString.str());
 202   GlobalVariable* typeNameVal  = GetStringRef(module,
 203                                      val->getType()->getDescription().c_str());
 204
 205   switch(valueType->getPrimitiveID())
 206     {
 207     case Type::BoolTyID:
 208     case Type::UByteTyID: case Type::UShortTyID:
 209     case Type::UIntTyID:  case Type::ULongTyID:
 210     case Type::SByteTyID: case Type::ShortTyID:
 211     case Type::IntTyID:   case Type::LongTyID:
 212       fmtString << " %d\n";
 213       break;
 214
 215     case Type::FloatTyID:     case Type::DoubleTyID:
 216       fmtString << " %g\n";
 217       break;
 218
 219     case Type::PointerTyID:
 220       fmtString << " %p\n";
 221       break;
 222
 223     default:
 224       assert(0 && "Should not get here.  Check the IF expression above");
 225       return NULL;
 226     }
 227
 228   fmtString << ends;
 229   GlobalVariable* fmtVal = GetStringRef(module, fmtString.str());
 230
 231   paramList.push_back(fmtVal);
 232   paramList.push_back(scopeNameVal);
 233   paramList.push_back(valNameVal);
 234   paramList.push_back(typeNameVal);
 235   paramList.push_back(val);
 236
 237   return new CallInst(printMethod, paramList);
 238 }
 239
 240
 241 // The invocation should be:
 242 //       call "printString"([ubyte*] or [sbyte*] or ubyte* or sbyte*).
 243 //       call "printLong"(long)
 244 //       call "printInt"(int) ...
 245 //
 246 static Value *GetPrintMethodForType(Module *Mod, const Type *VTy) {
 247   MethodType *MTy = MethodType::get(Type::VoidTy, vector<const Type*>(1, VTy),
 248                                     /*isVarArg*/ false);
 249
 250   const char* printMethodName = PrintMethodNameForType(VTy);
 251   SymbolTable *ST = Mod->getSymbolTableSure();
 252   if (Value *V = ST->lookup(PointerType::get(MTy), printMethodName))
 253     return V;
 254
 255   // Create a new method and add it to the module
 256   Method *M = new Method(MTy, printMethodName);
 257   Mod->getMethodList().push_back(M);
 258   return M;
 259 }
 260
 261
 262 static void
 263 InsertPrintInsts(Value *Val,
 264                  BasicBlock* BB,
 265                  BasicBlock::iterator &BBI,
 266                  Module *Mod,
 267                  unsigned int indent,
 268                  bool isMethodExit)
 269 {
 270   const Type* ValTy = Val->getType();
 271
 272   assert((ValTy->isPrimitiveType() || isa<PointerType>(ValTy)) &&
 273          ValTy != Type::VoidTy && ValTy != Type::TypeTy &&
 274          ValTy != Type::LabelTy && "Unsupported type for printing");
 275
 276   const Value* scopeToUse =
 277     isMethodExit ? (const Value*)BB->getParent() : (const Value*)BB;
 278
 279   // Create the marker string...
 280   ostringstream scopeNameString;
 281   WriteAsOperand(scopeNameString, scopeToUse) << " : ";
 282   WriteAsOperand(scopeNameString, Val) << " = ";
 283
 284   string fmtString(indent, ' ');
 285   fmtString += string(" At exit of") + scopeNameString.str();
 286
 287   // Turn the marker string into a global variable...
 288   GlobalVariable *fmtVal = GetStringRef(Mod, fmtString);
 289
 290   // Insert the first print instruction to print the string flag:
 291   Instruction *I = new CallInst(GetPrintMethodForType(Mod, fmtVal->getType()),
 292                                 vector<Value*>(1, fmtVal));
 293   BBI = BB->getInstList().insert(BBI, I)+1;
 294
 295   // Insert the next print instruction to print the value:
 296   I = new CallInst(GetPrintMethodForType(Mod, ValTy),
 297                    vector<Value*>(1, Val));
 298   BBI = BB->getInstList().insert(BBI, I)+1;
 299
 300   // Print out a newline
 301   fmtVal = GetStringRef(Mod, "\n");
 302   I = new CallInst(GetPrintMethodForType(Mod, fmtVal->getType()),
 303                    vector<Value*>(1, fmtVal));
 304   BBI = BB->getInstList().insert(BBI, I)+1;
 305 }
 306
 307
 308 static LoadInst*
 309 InsertLoadInst(StoreInst* storeInst,
 310                BasicBlock *bb,
 311                BasicBlock::iterator &BBI)
 312 {
 313   LoadInst* loadInst = new LoadInst(storeInst->getPtrOperand(),
 314                                     storeInst->getIndexVec());
 315   BBI = bb->getInstList().insert(BBI, loadInst) + 1;
 316   return loadInst;
 317 }
 318
 319
 320 //
 321 // Insert print instructions at the end of the basic block *bb
 322 // for each value in valueVec[] that is live at the end of that basic block,
 323 // or that is stored to memory in this basic block.
 324 // If the value is stored to memory, we load it back before printing
 325 // We also return all such loaded values in the vector valuesStoredInMethod
 326 // for printing at the exit from the method.  (Note that in each invocation
 327 // of the method, this will only get the last value stored for each static
 328 // store instruction).
 329 // *bb must be the block in which the value is computed;
 330 // this is not checked here.
 331 //
 332 static void
 333 TraceValuesAtBBExit(const vector<Instruction*>& valueVec,
 334                     BasicBlock* bb,
 335                     Module* module,
 336                     unsigned int indent,
 337                     bool isMethodExit,
 338                     vector<Instruction*>* valuesStoredInMethod)
 339 {
 340   // Get an iterator to point to the insertion location, which is
 341   // just before the terminator instruction.
 342   //
 343   BasicBlock::InstListType& instList = bb->getInstList();
 344   BasicBlock::iterator here = instList.end()-1;
 345   assert((*here)->isTerminator());
 346
 347   // If the terminator is a conditional branch, insert the trace code just
 348   // before the instruction that computes the branch condition (just to
 349   // avoid putting a call between the CC-setting instruction and the branch).
 350   // Use laterInstrSet to mark instructions that come after the setCC instr
 351   // because those cannot be traced at the location we choose.
 352   //
 353   hash_set<Instruction*> laterInstrSet;
 354   if (BranchInst* brInst = dyn_cast<BranchInst>(*here))
 355     if (! brInst->isUnconditional())
 356       if (Instruction* setCC = dyn_cast<Instruction>(brInst->getCondition()))
 357         if (setCC->getParent() == bb)
 358           {
 359             while ((*here) != setCC && here != instList.begin())
 360               {
 361                 --here;
 362                 laterInstrSet.insert(*here);
 363               }
 364             assert((*here) == setCC && "Missed the setCC instruction?");
 365             laterInstrSet.insert(*here);
 366           }
 367
 368   // Insert a print instruction for each value.
 369   //
 370   for (unsigned i=0, N=valueVec.size(); i < N; i++)
 371     {
 372       Instruction* I = valueVec[i];
 373       if (I->getOpcode() == Instruction::Store)
 374         {
 375           assert(valuesStoredInMethod != NULL &&
 376                  "Should not be printing a store instruction at method exit");
 377           I = InsertLoadInst((StoreInst*) I, bb, here);
 378           valuesStoredInMethod->push_back(I);
 379         }
 380       if (laterInstrSet.find(I) == laterInstrSet.end())
 381         InsertPrintInsts(I, bb, here, module, indent, isMethodExit);
 382     }
 383 }
 384
 385
 386
 387 static Instruction*
 388 CreateMethodTraceInst(Method* method,
 389                       unsigned int indent,
 390                       const string& msg)
 391 {
 392   string fmtString(indent, ' ');
 393   ostringstream methodNameString;
 394   WriteAsOperand(methodNameString, method);
 395   fmtString += msg + methodNameString.str() + '\n';
 396
 397   GlobalVariable *fmtVal = GetStringRef(method->getParent(), fmtString);
 398   Instruction *printInst =
 399     new CallInst(GetPrintMethodForType(method->getParent(), fmtVal->getType()),
 400                  vector<Value*>(1, fmtVal));
 401
 402   return printInst;
 403 }
 404
 405
 406 static inline void
 407 InsertCodeToShowMethodEntry(Method* method,
 408                             BasicBlock* entryBB,
 409                             unsigned int indent)
 410 {
 411   // Get an iterator to point to the insertion location
 412   BasicBlock::InstListType& instList = entryBB->getInstList();
 413   BasicBlock::iterator here = instList.begin();
 414
 415   Instruction *printInst = CreateMethodTraceInst(method, indent,
 416                                                  "Entering Method");
 417
 418   here = entryBB->getInstList().insert(here, printInst) + 1;
 419 }
 420
 421
 422 static inline void
 423 InsertCodeToShowMethodExit(Method* method,
 424                            BasicBlock* exitBB,
 425                            unsigned int indent)
 426 {
 427   // Get an iterator to point to the insertion location
 428   BasicBlock::InstListType& instList = exitBB->getInstList();
 429   BasicBlock::iterator here = instList.end()-1;
 430   assert((*here)->isTerminator());
 431
 432   Instruction *printInst = CreateMethodTraceInst(method, indent,
 433                                                  "Leaving Method");
 434
 435   exitBB->getInstList().insert(here, printInst) + 1;
 436 }
 437
 438
 439 //************************** External Functions ****************************/
 440
 441
 442 bool
 443 InsertTraceCode::doInsertTraceCode(Method *M,
 444                                    bool traceBasicBlockExits,
 445                                    bool traceMethodExits)
 446 {
 447   vector<Instruction*> valuesStoredInMethod;
 448   Module* module = M->getParent();
 449   vector<BasicBlock*> exitBlocks;
 450
 451   if (M->isExternal() ||
 452       (! traceBasicBlockExits && ! traceMethodExits))
 453     return false;
 454
 455   if (traceMethodExits)
 456     InsertCodeToShowMethodEntry(M, M->getEntryNode(), /*indent*/ 0);
 457
 458   for (Method::iterator BI = M->begin(); BI != M->end(); ++BI)
 459     {
 460       BasicBlock* bb = *BI;
 461       bool isExitBlock = false;
 462       vector<Instruction*> valuesToTraceInBB;
 463
 464       FindValuesToTraceInBB(bb, valuesToTraceInBB);
 465
 466       if (bb->succ_begin() == bb->succ_end())
 467         { // record this as an exit block
 468           exitBlocks.push_back(bb);
 469           isExitBlock = true;
 470         }
 471
 472       if (traceBasicBlockExits)
 473         TraceValuesAtBBExit(valuesToTraceInBB, bb, module,
 474                             /*indent*/ 4, /*isMethodExit*/ false,
 475                             &valuesStoredInMethod);
 476     }
 477
 478   if (traceMethodExits)
 479     for (unsigned i=0; i < exitBlocks.size(); ++i)
 480       {
 481         TraceValuesAtBBExit(valuesStoredInMethod, exitBlocks[i], module,
 482                             /*indent*/ 0, /*isMethodExit*/ true,
 483                             /*valuesStoredInMethod*/ NULL);
 484         InsertCodeToShowMethodExit(M, exitBlocks[i], /*indent*/ 0);
 485       }
 486
 487   return true;
 488 }