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