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, 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                  bool isMethodEntry = false)
 271 {
 272   const Type* ValTy = Val->getType();
 273
 274   assert((ValTy->isPrimitiveType() || isa<PointerType>(ValTy)) &&
 275          ValTy != Type::VoidTy && ValTy != Type::TypeTy &&
 276          ValTy != Type::LabelTy && "Unsupported type for printing");
 277
 278   const Value* scopeToUse =
 279     (isMethodExit || isMethodEntry)? (const Value*)BB->getParent() : (const Value*)BB;
 280
 281   // Create the marker string...
 282   ostringstream scopeNameString;
 283   if (isMethodExit || isMethodEntry)
 284     scopeNameString << " METHOD ";
 285   else
 286     scopeNameString << " BASIC BLOCK ";
 287
 288   scopeNameString << ((scopeToUse->hasName())
 289                       ? scopeToUse->getName().c_str()
 290                       : itostr((int) scopeToUse).c_str())
 291                   << " : ";
 292
 293   WriteAsOperand(scopeNameString, Val) << " = ";
 294
 295   string fmtString(indent, ' ');
 296   if (isMethodEntry)
 297     fmtString += string(" AT ENTRY OF") + scopeNameString.str();
 298   else
 299     fmtString += string(" AT EXIT OF") + scopeNameString.str();
 300
 301   // Turn the marker string into a global variable...
 302   GlobalVariable *fmtVal = GetStringRef(Mod, fmtString);
 303
 304   // Insert the first print instruction to print the string flag:
 305   Instruction *I = new CallInst(GetPrintMethodForType(Mod, fmtVal->getType()),
 306                                 vector<Value*>(1, fmtVal));
 307   BBI = BB->getInstList().insert(BBI, I)+1;
 308
 309   // Insert the next print instruction to print the value:
 310   I = new CallInst(GetPrintMethodForType(Mod, ValTy),
 311                    vector<Value*>(1, Val));
 312   BBI = BB->getInstList().insert(BBI, I)+1;
 313
 314   // Print out a newline
 315   fmtVal = GetStringRef(Mod, "\n");
 316   I = new CallInst(GetPrintMethodForType(Mod, fmtVal->getType()),
 317                    vector<Value*>(1, fmtVal));
 318   BBI = BB->getInstList().insert(BBI, I)+1;
 319 }
 320
 321
 322 static LoadInst*
 323 InsertLoadInst(StoreInst* storeInst,
 324                BasicBlock *bb,
 325                BasicBlock::iterator &BBI)
 326 {
 327   LoadInst* loadInst = new LoadInst(storeInst->getPointerOperand(),
 328                                     storeInst->getIndices());
 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 }