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