diff options
Diffstat (limited to 'contrib/llvm/lib/Transforms/Instrumentation')
13 files changed, 4654 insertions, 0 deletions
diff --git a/contrib/llvm/lib/Transforms/Instrumentation/AddressSanitizer.cpp b/contrib/llvm/lib/Transforms/Instrumentation/AddressSanitizer.cpp new file mode 100644 index 0000000..17b83ce --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/AddressSanitizer.cpp @@ -0,0 +1,1054 @@ +//===-- AddressSanitizer.cpp - memory error detector ------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file is a part of AddressSanitizer, an address sanity checker. +// Details of the algorithm: +// http://code.google.com/p/address-sanitizer/wiki/AddressSanitizerAlgorithm +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "asan" + +#include "FunctionBlackList.h" +#include "llvm/Function.h" +#include "llvm/IRBuilder.h" +#include "llvm/InlineAsm.h" +#include "llvm/IntrinsicInst.h" +#include "llvm/LLVMContext.h" +#include "llvm/Module.h" +#include "llvm/Type.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/OwningPtr.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/ADT/Triple.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/DataTypes.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/system_error.h" +#include "llvm/Target/TargetData.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Transforms/Instrumentation.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/ModuleUtils.h" + +#include <string> +#include <algorithm> + +using namespace llvm; + +static const uint64_t kDefaultShadowScale = 3; +static const uint64_t kDefaultShadowOffset32 = 1ULL << 29; +static const uint64_t kDefaultShadowOffset64 = 1ULL << 44; +static const uint64_t kDefaultShadowOffsetAndroid = 0; + +static const size_t kMaxStackMallocSize = 1 << 16; // 64K +static const uintptr_t kCurrentStackFrameMagic = 0x41B58AB3; +static const uintptr_t kRetiredStackFrameMagic = 0x45E0360E; + +static const char *kAsanModuleCtorName = "asan.module_ctor"; +static const char *kAsanModuleDtorName = "asan.module_dtor"; +static const int kAsanCtorAndCtorPriority = 1; +static const char *kAsanReportErrorTemplate = "__asan_report_"; +static const char *kAsanRegisterGlobalsName = "__asan_register_globals"; +static const char *kAsanUnregisterGlobalsName = "__asan_unregister_globals"; +static const char *kAsanInitName = "__asan_init"; +static const char *kAsanHandleNoReturnName = "__asan_handle_no_return"; +static const char *kAsanMappingOffsetName = "__asan_mapping_offset"; +static const char *kAsanMappingScaleName = "__asan_mapping_scale"; +static const char *kAsanStackMallocName = "__asan_stack_malloc"; +static const char *kAsanStackFreeName = "__asan_stack_free"; + +static const int kAsanStackLeftRedzoneMagic = 0xf1; +static const int kAsanStackMidRedzoneMagic = 0xf2; +static const int kAsanStackRightRedzoneMagic = 0xf3; +static const int kAsanStackPartialRedzoneMagic = 0xf4; + +// Accesses sizes are powers of two: 1, 2, 4, 8, 16. +static const size_t kNumberOfAccessSizes = 5; + +// Command-line flags. + +// This flag may need to be replaced with -f[no-]asan-reads. +static cl::opt<bool> ClInstrumentReads("asan-instrument-reads", + cl::desc("instrument read instructions"), cl::Hidden, cl::init(true)); +static cl::opt<bool> ClInstrumentWrites("asan-instrument-writes", + cl::desc("instrument write instructions"), cl::Hidden, cl::init(true)); +static cl::opt<bool> ClInstrumentAtomics("asan-instrument-atomics", + cl::desc("instrument atomic instructions (rmw, cmpxchg)"), + cl::Hidden, cl::init(true)); +static cl::opt<bool> ClAlwaysSlowPath("asan-always-slow-path", + cl::desc("use instrumentation with slow path for all accesses"), + cl::Hidden, cl::init(false)); +// This flag limits the number of instructions to be instrumented +// in any given BB. Normally, this should be set to unlimited (INT_MAX), +// but due to http://llvm.org/bugs/show_bug.cgi?id=12652 we temporary +// set it to 10000. +static cl::opt<int> ClMaxInsnsToInstrumentPerBB("asan-max-ins-per-bb", + cl::init(10000), + cl::desc("maximal number of instructions to instrument in any given BB"), + cl::Hidden); +// This flag may need to be replaced with -f[no]asan-stack. +static cl::opt<bool> ClStack("asan-stack", + cl::desc("Handle stack memory"), cl::Hidden, cl::init(true)); +// This flag may need to be replaced with -f[no]asan-use-after-return. +static cl::opt<bool> ClUseAfterReturn("asan-use-after-return", + cl::desc("Check return-after-free"), cl::Hidden, cl::init(false)); +// This flag may need to be replaced with -f[no]asan-globals. +static cl::opt<bool> ClGlobals("asan-globals", + cl::desc("Handle global objects"), cl::Hidden, cl::init(true)); +static cl::opt<bool> ClMemIntrin("asan-memintrin", + cl::desc("Handle memset/memcpy/memmove"), cl::Hidden, cl::init(true)); +// This flag may need to be replaced with -fasan-blacklist. +static cl::opt<std::string> ClBlackListFile("asan-blacklist", + cl::desc("File containing the list of functions to ignore " + "during instrumentation"), cl::Hidden); + +// These flags allow to change the shadow mapping. +// The shadow mapping looks like +// Shadow = (Mem >> scale) + (1 << offset_log) +static cl::opt<int> ClMappingScale("asan-mapping-scale", + cl::desc("scale of asan shadow mapping"), cl::Hidden, cl::init(0)); +static cl::opt<int> ClMappingOffsetLog("asan-mapping-offset-log", + cl::desc("offset of asan shadow mapping"), cl::Hidden, cl::init(-1)); + +// Optimization flags. Not user visible, used mostly for testing +// and benchmarking the tool. +static cl::opt<bool> ClOpt("asan-opt", + cl::desc("Optimize instrumentation"), cl::Hidden, cl::init(true)); +static cl::opt<bool> ClOptSameTemp("asan-opt-same-temp", + cl::desc("Instrument the same temp just once"), cl::Hidden, + cl::init(true)); +static cl::opt<bool> ClOptGlobals("asan-opt-globals", + cl::desc("Don't instrument scalar globals"), cl::Hidden, cl::init(true)); + +// Debug flags. +static cl::opt<int> ClDebug("asan-debug", cl::desc("debug"), cl::Hidden, + cl::init(0)); +static cl::opt<int> ClDebugStack("asan-debug-stack", cl::desc("debug stack"), + cl::Hidden, cl::init(0)); +static cl::opt<std::string> ClDebugFunc("asan-debug-func", + cl::Hidden, cl::desc("Debug func")); +static cl::opt<int> ClDebugMin("asan-debug-min", cl::desc("Debug min inst"), + cl::Hidden, cl::init(-1)); +static cl::opt<int> ClDebugMax("asan-debug-max", cl::desc("Debug man inst"), + cl::Hidden, cl::init(-1)); + +namespace { + +/// An object of this type is created while instrumenting every function. +struct AsanFunctionContext { + AsanFunctionContext(Function &Function) : F(Function) { } + + Function &F; +}; + +/// AddressSanitizer: instrument the code in module to find memory bugs. +struct AddressSanitizer : public ModulePass { + AddressSanitizer(); + virtual const char *getPassName() const; + void instrumentMop(AsanFunctionContext &AFC, Instruction *I); + void instrumentAddress(AsanFunctionContext &AFC, + Instruction *OrigIns, IRBuilder<> &IRB, + Value *Addr, uint32_t TypeSize, bool IsWrite); + Value *createSlowPathCmp(IRBuilder<> &IRB, Value *AddrLong, + Value *ShadowValue, uint32_t TypeSize); + Instruction *generateCrashCode(Instruction *InsertBefore, Value *Addr, + bool IsWrite, size_t AccessSizeIndex); + bool instrumentMemIntrinsic(AsanFunctionContext &AFC, MemIntrinsic *MI); + void instrumentMemIntrinsicParam(AsanFunctionContext &AFC, + Instruction *OrigIns, Value *Addr, + Value *Size, + Instruction *InsertBefore, bool IsWrite); + Value *memToShadow(Value *Shadow, IRBuilder<> &IRB); + bool handleFunction(Module &M, Function &F); + bool maybeInsertAsanInitAtFunctionEntry(Function &F); + bool poisonStackInFunction(Module &M, Function &F); + virtual bool runOnModule(Module &M); + bool insertGlobalRedzones(Module &M); + static char ID; // Pass identification, replacement for typeid + + private: + + uint64_t getAllocaSizeInBytes(AllocaInst *AI) { + Type *Ty = AI->getAllocatedType(); + uint64_t SizeInBytes = TD->getTypeAllocSize(Ty); + return SizeInBytes; + } + uint64_t getAlignedSize(uint64_t SizeInBytes) { + return ((SizeInBytes + RedzoneSize - 1) + / RedzoneSize) * RedzoneSize; + } + uint64_t getAlignedAllocaSize(AllocaInst *AI) { + uint64_t SizeInBytes = getAllocaSizeInBytes(AI); + return getAlignedSize(SizeInBytes); + } + + Function *checkInterfaceFunction(Constant *FuncOrBitcast); + void PoisonStack(const ArrayRef<AllocaInst*> &AllocaVec, IRBuilder<> IRB, + Value *ShadowBase, bool DoPoison); + bool LooksLikeCodeInBug11395(Instruction *I); + + LLVMContext *C; + TargetData *TD; + uint64_t MappingOffset; + int MappingScale; + size_t RedzoneSize; + int LongSize; + Type *IntptrTy; + Type *IntptrPtrTy; + Function *AsanCtorFunction; + Function *AsanInitFunction; + Instruction *CtorInsertBefore; + OwningPtr<FunctionBlackList> BL; + // This array is indexed by AccessIsWrite and log2(AccessSize). + Function *AsanErrorCallback[2][kNumberOfAccessSizes]; + InlineAsm *EmptyAsm; +}; + +} // namespace + +char AddressSanitizer::ID = 0; +INITIALIZE_PASS(AddressSanitizer, "asan", + "AddressSanitizer: detects use-after-free and out-of-bounds bugs.", + false, false) +AddressSanitizer::AddressSanitizer() : ModulePass(ID) { } +ModulePass *llvm::createAddressSanitizerPass() { + return new AddressSanitizer(); +} + +const char *AddressSanitizer::getPassName() const { + return "AddressSanitizer"; +} + +static size_t TypeSizeToSizeIndex(uint32_t TypeSize) { + size_t Res = CountTrailingZeros_32(TypeSize / 8); + assert(Res < kNumberOfAccessSizes); + return Res; +} + +// Create a constant for Str so that we can pass it to the run-time lib. +static GlobalVariable *createPrivateGlobalForString(Module &M, StringRef Str) { + Constant *StrConst = ConstantDataArray::getString(M.getContext(), Str); + return new GlobalVariable(M, StrConst->getType(), true, + GlobalValue::PrivateLinkage, StrConst, ""); +} + +// Split the basic block and insert an if-then code. +// Before: +// Head +// Cmp +// Tail +// After: +// Head +// if (Cmp) +// ThenBlock +// Tail +// +// ThenBlock block is created and its terminator is returned. +// If Unreachable, ThenBlock is terminated with UnreachableInst, otherwise +// it is terminated with BranchInst to Tail. +static TerminatorInst *splitBlockAndInsertIfThen(Value *Cmp, bool Unreachable) { + Instruction *SplitBefore = cast<Instruction>(Cmp)->getNextNode(); + BasicBlock *Head = SplitBefore->getParent(); + BasicBlock *Tail = Head->splitBasicBlock(SplitBefore); + TerminatorInst *HeadOldTerm = Head->getTerminator(); + LLVMContext &C = Head->getParent()->getParent()->getContext(); + BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail); + TerminatorInst *CheckTerm; + if (Unreachable) + CheckTerm = new UnreachableInst(C, ThenBlock); + else + CheckTerm = BranchInst::Create(Tail, ThenBlock); + BranchInst *HeadNewTerm = + BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cmp); + ReplaceInstWithInst(HeadOldTerm, HeadNewTerm); + return CheckTerm; +} + +Value *AddressSanitizer::memToShadow(Value *Shadow, IRBuilder<> &IRB) { + // Shadow >> scale + Shadow = IRB.CreateLShr(Shadow, MappingScale); + if (MappingOffset == 0) + return Shadow; + // (Shadow >> scale) | offset + return IRB.CreateOr(Shadow, ConstantInt::get(IntptrTy, + MappingOffset)); +} + +void AddressSanitizer::instrumentMemIntrinsicParam( + AsanFunctionContext &AFC, Instruction *OrigIns, + Value *Addr, Value *Size, Instruction *InsertBefore, bool IsWrite) { + // Check the first byte. + { + IRBuilder<> IRB(InsertBefore); + instrumentAddress(AFC, OrigIns, IRB, Addr, 8, IsWrite); + } + // Check the last byte. + { + IRBuilder<> IRB(InsertBefore); + Value *SizeMinusOne = IRB.CreateSub( + Size, ConstantInt::get(Size->getType(), 1)); + SizeMinusOne = IRB.CreateIntCast(SizeMinusOne, IntptrTy, false); + Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy); + Value *AddrPlusSizeMinisOne = IRB.CreateAdd(AddrLong, SizeMinusOne); + instrumentAddress(AFC, OrigIns, IRB, AddrPlusSizeMinisOne, 8, IsWrite); + } +} + +// Instrument memset/memmove/memcpy +bool AddressSanitizer::instrumentMemIntrinsic(AsanFunctionContext &AFC, + MemIntrinsic *MI) { + Value *Dst = MI->getDest(); + MemTransferInst *MemTran = dyn_cast<MemTransferInst>(MI); + Value *Src = MemTran ? MemTran->getSource() : 0; + Value *Length = MI->getLength(); + + Constant *ConstLength = dyn_cast<Constant>(Length); + Instruction *InsertBefore = MI; + if (ConstLength) { + if (ConstLength->isNullValue()) return false; + } else { + // The size is not a constant so it could be zero -- check at run-time. + IRBuilder<> IRB(InsertBefore); + + Value *Cmp = IRB.CreateICmpNE(Length, + Constant::getNullValue(Length->getType())); + InsertBefore = splitBlockAndInsertIfThen(Cmp, false); + } + + instrumentMemIntrinsicParam(AFC, MI, Dst, Length, InsertBefore, true); + if (Src) + instrumentMemIntrinsicParam(AFC, MI, Src, Length, InsertBefore, false); + return true; +} + +// If I is an interesting memory access, return the PointerOperand +// and set IsWrite. Otherwise return NULL. +static Value *isInterestingMemoryAccess(Instruction *I, bool *IsWrite) { + if (LoadInst *LI = dyn_cast<LoadInst>(I)) { + if (!ClInstrumentReads) return NULL; + *IsWrite = false; + return LI->getPointerOperand(); + } + if (StoreInst *SI = dyn_cast<StoreInst>(I)) { + if (!ClInstrumentWrites) return NULL; + *IsWrite = true; + return SI->getPointerOperand(); + } + if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(I)) { + if (!ClInstrumentAtomics) return NULL; + *IsWrite = true; + return RMW->getPointerOperand(); + } + if (AtomicCmpXchgInst *XCHG = dyn_cast<AtomicCmpXchgInst>(I)) { + if (!ClInstrumentAtomics) return NULL; + *IsWrite = true; + return XCHG->getPointerOperand(); + } + return NULL; +} + +void AddressSanitizer::instrumentMop(AsanFunctionContext &AFC, Instruction *I) { + bool IsWrite; + Value *Addr = isInterestingMemoryAccess(I, &IsWrite); + assert(Addr); + if (ClOpt && ClOptGlobals && isa<GlobalVariable>(Addr)) { + // We are accessing a global scalar variable. Nothing to catch here. + return; + } + Type *OrigPtrTy = Addr->getType(); + Type *OrigTy = cast<PointerType>(OrigPtrTy)->getElementType(); + + assert(OrigTy->isSized()); + uint32_t TypeSize = TD->getTypeStoreSizeInBits(OrigTy); + + if (TypeSize != 8 && TypeSize != 16 && + TypeSize != 32 && TypeSize != 64 && TypeSize != 128) { + // Ignore all unusual sizes. + return; + } + + IRBuilder<> IRB(I); + instrumentAddress(AFC, I, IRB, Addr, TypeSize, IsWrite); +} + +// Validate the result of Module::getOrInsertFunction called for an interface +// function of AddressSanitizer. If the instrumented module defines a function +// with the same name, their prototypes must match, otherwise +// getOrInsertFunction returns a bitcast. +Function *AddressSanitizer::checkInterfaceFunction(Constant *FuncOrBitcast) { + if (isa<Function>(FuncOrBitcast)) return cast<Function>(FuncOrBitcast); + FuncOrBitcast->dump(); + report_fatal_error("trying to redefine an AddressSanitizer " + "interface function"); +} + +Instruction *AddressSanitizer::generateCrashCode( + Instruction *InsertBefore, Value *Addr, + bool IsWrite, size_t AccessSizeIndex) { + IRBuilder<> IRB(InsertBefore); + CallInst *Call = IRB.CreateCall(AsanErrorCallback[IsWrite][AccessSizeIndex], + Addr); + // We don't do Call->setDoesNotReturn() because the BB already has + // UnreachableInst at the end. + // This EmptyAsm is required to avoid callback merge. + IRB.CreateCall(EmptyAsm); + return Call; +} + +Value *AddressSanitizer::createSlowPathCmp(IRBuilder<> &IRB, Value *AddrLong, + Value *ShadowValue, + uint32_t TypeSize) { + size_t Granularity = 1 << MappingScale; + // Addr & (Granularity - 1) + Value *LastAccessedByte = IRB.CreateAnd( + AddrLong, ConstantInt::get(IntptrTy, Granularity - 1)); + // (Addr & (Granularity - 1)) + size - 1 + if (TypeSize / 8 > 1) + LastAccessedByte = IRB.CreateAdd( + LastAccessedByte, ConstantInt::get(IntptrTy, TypeSize / 8 - 1)); + // (uint8_t) ((Addr & (Granularity-1)) + size - 1) + LastAccessedByte = IRB.CreateIntCast( + LastAccessedByte, ShadowValue->getType(), false); + // ((uint8_t) ((Addr & (Granularity-1)) + size - 1)) >= ShadowValue + return IRB.CreateICmpSGE(LastAccessedByte, ShadowValue); +} + +void AddressSanitizer::instrumentAddress(AsanFunctionContext &AFC, + Instruction *OrigIns, + IRBuilder<> &IRB, Value *Addr, + uint32_t TypeSize, bool IsWrite) { + Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy); + + Type *ShadowTy = IntegerType::get( + *C, std::max(8U, TypeSize >> MappingScale)); + Type *ShadowPtrTy = PointerType::get(ShadowTy, 0); + Value *ShadowPtr = memToShadow(AddrLong, IRB); + Value *CmpVal = Constant::getNullValue(ShadowTy); + Value *ShadowValue = IRB.CreateLoad( + IRB.CreateIntToPtr(ShadowPtr, ShadowPtrTy)); + + Value *Cmp = IRB.CreateICmpNE(ShadowValue, CmpVal); + size_t AccessSizeIndex = TypeSizeToSizeIndex(TypeSize); + size_t Granularity = 1 << MappingScale; + TerminatorInst *CrashTerm = 0; + + if (ClAlwaysSlowPath || (TypeSize < 8 * Granularity)) { + TerminatorInst *CheckTerm = splitBlockAndInsertIfThen(Cmp, false); + assert(dyn_cast<BranchInst>(CheckTerm)->isUnconditional()); + BasicBlock *NextBB = CheckTerm->getSuccessor(0); + IRB.SetInsertPoint(CheckTerm); + Value *Cmp2 = createSlowPathCmp(IRB, AddrLong, ShadowValue, TypeSize); + BasicBlock *CrashBlock = BasicBlock::Create(*C, "", &AFC.F, NextBB); + CrashTerm = new UnreachableInst(*C, CrashBlock); + BranchInst *NewTerm = BranchInst::Create(CrashBlock, NextBB, Cmp2); + ReplaceInstWithInst(CheckTerm, NewTerm); + } else { + CrashTerm = splitBlockAndInsertIfThen(Cmp, true); + } + + Instruction *Crash = + generateCrashCode(CrashTerm, AddrLong, IsWrite, AccessSizeIndex); + Crash->setDebugLoc(OrigIns->getDebugLoc()); +} + +// This function replaces all global variables with new variables that have +// trailing redzones. It also creates a function that poisons +// redzones and inserts this function into llvm.global_ctors. +bool AddressSanitizer::insertGlobalRedzones(Module &M) { + SmallVector<GlobalVariable *, 16> GlobalsToChange; + + for (Module::GlobalListType::iterator G = M.getGlobalList().begin(), + E = M.getGlobalList().end(); G != E; ++G) { + Type *Ty = cast<PointerType>(G->getType())->getElementType(); + DEBUG(dbgs() << "GLOBAL: " << *G); + + if (!Ty->isSized()) continue; + if (!G->hasInitializer()) continue; + // Touch only those globals that will not be defined in other modules. + // Don't handle ODR type linkages since other modules may be built w/o asan. + if (G->getLinkage() != GlobalVariable::ExternalLinkage && + G->getLinkage() != GlobalVariable::PrivateLinkage && + G->getLinkage() != GlobalVariable::InternalLinkage) + continue; + // Two problems with thread-locals: + // - The address of the main thread's copy can't be computed at link-time. + // - Need to poison all copies, not just the main thread's one. + if (G->isThreadLocal()) + continue; + // For now, just ignore this Alloca if the alignment is large. + if (G->getAlignment() > RedzoneSize) continue; + + // Ignore all the globals with the names starting with "\01L_OBJC_". + // Many of those are put into the .cstring section. The linker compresses + // that section by removing the spare \0s after the string terminator, so + // our redzones get broken. + if ((G->getName().find("\01L_OBJC_") == 0) || + (G->getName().find("\01l_OBJC_") == 0)) { + DEBUG(dbgs() << "Ignoring \\01L_OBJC_* global: " << *G); + continue; + } + + if (G->hasSection()) { + StringRef Section(G->getSection()); + // Ignore the globals from the __OBJC section. The ObjC runtime assumes + // those conform to /usr/lib/objc/runtime.h, so we can't add redzones to + // them. + if ((Section.find("__OBJC,") == 0) || + (Section.find("__DATA, __objc_") == 0)) { + DEBUG(dbgs() << "Ignoring ObjC runtime global: " << *G); + continue; + } + // See http://code.google.com/p/address-sanitizer/issues/detail?id=32 + // Constant CFString instances are compiled in the following way: + // -- the string buffer is emitted into + // __TEXT,__cstring,cstring_literals + // -- the constant NSConstantString structure referencing that buffer + // is placed into __DATA,__cfstring + // Therefore there's no point in placing redzones into __DATA,__cfstring. + // Moreover, it causes the linker to crash on OS X 10.7 + if (Section.find("__DATA,__cfstring") == 0) { + DEBUG(dbgs() << "Ignoring CFString: " << *G); + continue; + } + } + + GlobalsToChange.push_back(G); + } + + size_t n = GlobalsToChange.size(); + if (n == 0) return false; + + // A global is described by a structure + // size_t beg; + // size_t size; + // size_t size_with_redzone; + // const char *name; + // We initialize an array of such structures and pass it to a run-time call. + StructType *GlobalStructTy = StructType::get(IntptrTy, IntptrTy, + IntptrTy, IntptrTy, NULL); + SmallVector<Constant *, 16> Initializers(n); + + IRBuilder<> IRB(CtorInsertBefore); + + for (size_t i = 0; i < n; i++) { + GlobalVariable *G = GlobalsToChange[i]; + PointerType *PtrTy = cast<PointerType>(G->getType()); + Type *Ty = PtrTy->getElementType(); + uint64_t SizeInBytes = TD->getTypeAllocSize(Ty); + uint64_t RightRedzoneSize = RedzoneSize + + (RedzoneSize - (SizeInBytes % RedzoneSize)); + Type *RightRedZoneTy = ArrayType::get(IRB.getInt8Ty(), RightRedzoneSize); + + StructType *NewTy = StructType::get(Ty, RightRedZoneTy, NULL); + Constant *NewInitializer = ConstantStruct::get( + NewTy, G->getInitializer(), + Constant::getNullValue(RightRedZoneTy), NULL); + + SmallString<2048> DescriptionOfGlobal = G->getName(); + DescriptionOfGlobal += " ("; + DescriptionOfGlobal += M.getModuleIdentifier(); + DescriptionOfGlobal += ")"; + GlobalVariable *Name = createPrivateGlobalForString(M, DescriptionOfGlobal); + + // Create a new global variable with enough space for a redzone. + GlobalVariable *NewGlobal = new GlobalVariable( + M, NewTy, G->isConstant(), G->getLinkage(), + NewInitializer, "", G, G->getThreadLocalMode()); + NewGlobal->copyAttributesFrom(G); + NewGlobal->setAlignment(RedzoneSize); + + Value *Indices2[2]; + Indices2[0] = IRB.getInt32(0); + Indices2[1] = IRB.getInt32(0); + + G->replaceAllUsesWith( + ConstantExpr::getGetElementPtr(NewGlobal, Indices2, true)); + NewGlobal->takeName(G); + G->eraseFromParent(); + + Initializers[i] = ConstantStruct::get( + GlobalStructTy, + ConstantExpr::getPointerCast(NewGlobal, IntptrTy), + ConstantInt::get(IntptrTy, SizeInBytes), + ConstantInt::get(IntptrTy, SizeInBytes + RightRedzoneSize), + ConstantExpr::getPointerCast(Name, IntptrTy), + NULL); + DEBUG(dbgs() << "NEW GLOBAL:\n" << *NewGlobal); + } + + ArrayType *ArrayOfGlobalStructTy = ArrayType::get(GlobalStructTy, n); + GlobalVariable *AllGlobals = new GlobalVariable( + M, ArrayOfGlobalStructTy, false, GlobalVariable::PrivateLinkage, + ConstantArray::get(ArrayOfGlobalStructTy, Initializers), ""); + + Function *AsanRegisterGlobals = checkInterfaceFunction(M.getOrInsertFunction( + kAsanRegisterGlobalsName, IRB.getVoidTy(), IntptrTy, IntptrTy, NULL)); + AsanRegisterGlobals->setLinkage(Function::ExternalLinkage); + + IRB.CreateCall2(AsanRegisterGlobals, + IRB.CreatePointerCast(AllGlobals, IntptrTy), + ConstantInt::get(IntptrTy, n)); + + // We also need to unregister globals at the end, e.g. when a shared library + // gets closed. + Function *AsanDtorFunction = Function::Create( + FunctionType::get(Type::getVoidTy(*C), false), + GlobalValue::InternalLinkage, kAsanModuleDtorName, &M); + BasicBlock *AsanDtorBB = BasicBlock::Create(*C, "", AsanDtorFunction); + IRBuilder<> IRB_Dtor(ReturnInst::Create(*C, AsanDtorBB)); + Function *AsanUnregisterGlobals = + checkInterfaceFunction(M.getOrInsertFunction( + kAsanUnregisterGlobalsName, + IRB.getVoidTy(), IntptrTy, IntptrTy, NULL)); + AsanUnregisterGlobals->setLinkage(Function::ExternalLinkage); + + IRB_Dtor.CreateCall2(AsanUnregisterGlobals, + IRB.CreatePointerCast(AllGlobals, IntptrTy), + ConstantInt::get(IntptrTy, n)); + appendToGlobalDtors(M, AsanDtorFunction, kAsanCtorAndCtorPriority); + + DEBUG(dbgs() << M); + return true; +} + +// virtual +bool AddressSanitizer::runOnModule(Module &M) { + // Initialize the private fields. No one has accessed them before. + TD = getAnalysisIfAvailable<TargetData>(); + if (!TD) + return false; + BL.reset(new FunctionBlackList(ClBlackListFile)); + + C = &(M.getContext()); + LongSize = TD->getPointerSizeInBits(); + IntptrTy = Type::getIntNTy(*C, LongSize); + IntptrPtrTy = PointerType::get(IntptrTy, 0); + + AsanCtorFunction = Function::Create( + FunctionType::get(Type::getVoidTy(*C), false), + GlobalValue::InternalLinkage, kAsanModuleCtorName, &M); + BasicBlock *AsanCtorBB = BasicBlock::Create(*C, "", AsanCtorFunction); + CtorInsertBefore = ReturnInst::Create(*C, AsanCtorBB); + + // call __asan_init in the module ctor. + IRBuilder<> IRB(CtorInsertBefore); + AsanInitFunction = checkInterfaceFunction( + M.getOrInsertFunction(kAsanInitName, IRB.getVoidTy(), NULL)); + AsanInitFunction->setLinkage(Function::ExternalLinkage); + IRB.CreateCall(AsanInitFunction); + + // Create __asan_report* callbacks. + for (size_t AccessIsWrite = 0; AccessIsWrite <= 1; AccessIsWrite++) { + for (size_t AccessSizeIndex = 0; AccessSizeIndex < kNumberOfAccessSizes; + AccessSizeIndex++) { + // IsWrite and TypeSize are encoded in the function name. + std::string FunctionName = std::string(kAsanReportErrorTemplate) + + (AccessIsWrite ? "store" : "load") + itostr(1 << AccessSizeIndex); + // If we are merging crash callbacks, they have two parameters. + AsanErrorCallback[AccessIsWrite][AccessSizeIndex] = cast<Function>( + M.getOrInsertFunction(FunctionName, IRB.getVoidTy(), IntptrTy, NULL)); + } + } + // We insert an empty inline asm after __asan_report* to avoid callback merge. + EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false), + StringRef(""), StringRef(""), + /*hasSideEffects=*/true); + + llvm::Triple targetTriple(M.getTargetTriple()); + bool isAndroid = targetTriple.getEnvironment() == llvm::Triple::ANDROIDEABI; + + MappingOffset = isAndroid ? kDefaultShadowOffsetAndroid : + (LongSize == 32 ? kDefaultShadowOffset32 : kDefaultShadowOffset64); + if (ClMappingOffsetLog >= 0) { + if (ClMappingOffsetLog == 0) { + // special case + MappingOffset = 0; + } else { + MappingOffset = 1ULL << ClMappingOffsetLog; + } + } + MappingScale = kDefaultShadowScale; + if (ClMappingScale) { + MappingScale = ClMappingScale; + } + // Redzone used for stack and globals is at least 32 bytes. + // For scales 6 and 7, the redzone has to be 64 and 128 bytes respectively. + RedzoneSize = std::max(32, (int)(1 << MappingScale)); + + bool Res = false; + + if (ClGlobals) + Res |= insertGlobalRedzones(M); + + if (ClMappingOffsetLog >= 0) { + // Tell the run-time the current values of mapping offset and scale. + GlobalValue *asan_mapping_offset = + new GlobalVariable(M, IntptrTy, true, GlobalValue::LinkOnceODRLinkage, + ConstantInt::get(IntptrTy, MappingOffset), + kAsanMappingOffsetName); + // Read the global, otherwise it may be optimized away. + IRB.CreateLoad(asan_mapping_offset, true); + } + if (ClMappingScale) { + GlobalValue *asan_mapping_scale = + new GlobalVariable(M, IntptrTy, true, GlobalValue::LinkOnceODRLinkage, + ConstantInt::get(IntptrTy, MappingScale), + kAsanMappingScaleName); + // Read the global, otherwise it may be optimized away. + IRB.CreateLoad(asan_mapping_scale, true); + } + + + for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { + if (F->isDeclaration()) continue; + Res |= handleFunction(M, *F); + } + + appendToGlobalCtors(M, AsanCtorFunction, kAsanCtorAndCtorPriority); + + return Res; +} + +bool AddressSanitizer::maybeInsertAsanInitAtFunctionEntry(Function &F) { + // For each NSObject descendant having a +load method, this method is invoked + // by the ObjC runtime before any of the static constructors is called. + // Therefore we need to instrument such methods with a call to __asan_init + // at the beginning in order to initialize our runtime before any access to + // the shadow memory. + // We cannot just ignore these methods, because they may call other + // instrumented functions. + if (F.getName().find(" load]") != std::string::npos) { + IRBuilder<> IRB(F.begin()->begin()); + IRB.CreateCall(AsanInitFunction); + return true; + } + return false; +} + +bool AddressSanitizer::handleFunction(Module &M, Function &F) { + if (BL->isIn(F)) return false; + if (&F == AsanCtorFunction) return false; + + // If needed, insert __asan_init before checking for AddressSafety attr. + maybeInsertAsanInitAtFunctionEntry(F); + + if (!F.hasFnAttr(Attribute::AddressSafety)) return false; + + if (!ClDebugFunc.empty() && ClDebugFunc != F.getName()) + return false; + // We want to instrument every address only once per basic block + // (unless there are calls between uses). + SmallSet<Value*, 16> TempsToInstrument; + SmallVector<Instruction*, 16> ToInstrument; + SmallVector<Instruction*, 8> NoReturnCalls; + bool IsWrite; + + // Fill the set of memory operations to instrument. + for (Function::iterator FI = F.begin(), FE = F.end(); + FI != FE; ++FI) { + TempsToInstrument.clear(); + int NumInsnsPerBB = 0; + for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); + BI != BE; ++BI) { + if (LooksLikeCodeInBug11395(BI)) return false; + if (Value *Addr = isInterestingMemoryAccess(BI, &IsWrite)) { + if (ClOpt && ClOptSameTemp) { + if (!TempsToInstrument.insert(Addr)) + continue; // We've seen this temp in the current BB. + } + } else if (isa<MemIntrinsic>(BI) && ClMemIntrin) { + // ok, take it. + } else { + if (CallInst *CI = dyn_cast<CallInst>(BI)) { + // A call inside BB. + TempsToInstrument.clear(); + if (CI->doesNotReturn()) { + NoReturnCalls.push_back(CI); + } + } + continue; + } + ToInstrument.push_back(BI); + NumInsnsPerBB++; + if (NumInsnsPerBB >= ClMaxInsnsToInstrumentPerBB) + break; + } + } + + AsanFunctionContext AFC(F); + + // Instrument. + int NumInstrumented = 0; + for (size_t i = 0, n = ToInstrument.size(); i != n; i++) { + Instruction *Inst = ToInstrument[i]; + if (ClDebugMin < 0 || ClDebugMax < 0 || + (NumInstrumented >= ClDebugMin && NumInstrumented <= ClDebugMax)) { + if (isInterestingMemoryAccess(Inst, &IsWrite)) + instrumentMop(AFC, Inst); + else + instrumentMemIntrinsic(AFC, cast<MemIntrinsic>(Inst)); + } + NumInstrumented++; + } + + DEBUG(dbgs() << F); + + bool ChangedStack = poisonStackInFunction(M, F); + + // We must unpoison the stack before every NoReturn call (throw, _exit, etc). + // See e.g. http://code.google.com/p/address-sanitizer/issues/detail?id=37 + for (size_t i = 0, n = NoReturnCalls.size(); i != n; i++) { + Instruction *CI = NoReturnCalls[i]; + IRBuilder<> IRB(CI); + IRB.CreateCall(M.getOrInsertFunction(kAsanHandleNoReturnName, + IRB.getVoidTy(), NULL)); + } + + return NumInstrumented > 0 || ChangedStack || !NoReturnCalls.empty(); +} + +static uint64_t ValueForPoison(uint64_t PoisonByte, size_t ShadowRedzoneSize) { + if (ShadowRedzoneSize == 1) return PoisonByte; + if (ShadowRedzoneSize == 2) return (PoisonByte << 8) + PoisonByte; + if (ShadowRedzoneSize == 4) + return (PoisonByte << 24) + (PoisonByte << 16) + + (PoisonByte << 8) + (PoisonByte); + llvm_unreachable("ShadowRedzoneSize is either 1, 2 or 4"); +} + +static void PoisonShadowPartialRightRedzone(uint8_t *Shadow, + size_t Size, + size_t RedzoneSize, + size_t ShadowGranularity, + uint8_t Magic) { + for (size_t i = 0; i < RedzoneSize; + i+= ShadowGranularity, Shadow++) { + if (i + ShadowGranularity <= Size) { + *Shadow = 0; // fully addressable + } else if (i >= Size) { + *Shadow = Magic; // unaddressable + } else { + *Shadow = Size - i; // first Size-i bytes are addressable + } + } +} + +void AddressSanitizer::PoisonStack(const ArrayRef<AllocaInst*> &AllocaVec, + IRBuilder<> IRB, + Value *ShadowBase, bool DoPoison) { + size_t ShadowRZSize = RedzoneSize >> MappingScale; + assert(ShadowRZSize >= 1 && ShadowRZSize <= 4); + Type *RZTy = Type::getIntNTy(*C, ShadowRZSize * 8); + Type *RZPtrTy = PointerType::get(RZTy, 0); + + Value *PoisonLeft = ConstantInt::get(RZTy, + ValueForPoison(DoPoison ? kAsanStackLeftRedzoneMagic : 0LL, ShadowRZSize)); + Value *PoisonMid = ConstantInt::get(RZTy, + ValueForPoison(DoPoison ? kAsanStackMidRedzoneMagic : 0LL, ShadowRZSize)); + Value *PoisonRight = ConstantInt::get(RZTy, + ValueForPoison(DoPoison ? kAsanStackRightRedzoneMagic : 0LL, ShadowRZSize)); + + // poison the first red zone. + IRB.CreateStore(PoisonLeft, IRB.CreateIntToPtr(ShadowBase, RZPtrTy)); + + // poison all other red zones. + uint64_t Pos = RedzoneSize; + for (size_t i = 0, n = AllocaVec.size(); i < n; i++) { + AllocaInst *AI = AllocaVec[i]; + uint64_t SizeInBytes = getAllocaSizeInBytes(AI); + uint64_t AlignedSize = getAlignedAllocaSize(AI); + assert(AlignedSize - SizeInBytes < RedzoneSize); + Value *Ptr = NULL; + + Pos += AlignedSize; + + assert(ShadowBase->getType() == IntptrTy); + if (SizeInBytes < AlignedSize) { + // Poison the partial redzone at right + Ptr = IRB.CreateAdd( + ShadowBase, ConstantInt::get(IntptrTy, + (Pos >> MappingScale) - ShadowRZSize)); + size_t AddressableBytes = RedzoneSize - (AlignedSize - SizeInBytes); + uint32_t Poison = 0; + if (DoPoison) { + PoisonShadowPartialRightRedzone((uint8_t*)&Poison, AddressableBytes, + RedzoneSize, + 1ULL << MappingScale, + kAsanStackPartialRedzoneMagic); + } + Value *PartialPoison = ConstantInt::get(RZTy, Poison); + IRB.CreateStore(PartialPoison, IRB.CreateIntToPtr(Ptr, RZPtrTy)); + } + + // Poison the full redzone at right. + Ptr = IRB.CreateAdd(ShadowBase, + ConstantInt::get(IntptrTy, Pos >> MappingScale)); + Value *Poison = i == AllocaVec.size() - 1 ? PoisonRight : PoisonMid; + IRB.CreateStore(Poison, IRB.CreateIntToPtr(Ptr, RZPtrTy)); + + Pos += RedzoneSize; + } +} + +// Workaround for bug 11395: we don't want to instrument stack in functions +// with large assembly blobs (32-bit only), otherwise reg alloc may crash. +// FIXME: remove once the bug 11395 is fixed. +bool AddressSanitizer::LooksLikeCodeInBug11395(Instruction *I) { + if (LongSize != 32) return false; + CallInst *CI = dyn_cast<CallInst>(I); + if (!CI || !CI->isInlineAsm()) return false; + if (CI->getNumArgOperands() <= 5) return false; + // We have inline assembly with quite a few arguments. + return true; +} + +// Find all static Alloca instructions and put +// poisoned red zones around all of them. +// Then unpoison everything back before the function returns. +// +// Stack poisoning does not play well with exception handling. +// When an exception is thrown, we essentially bypass the code +// that unpoisones the stack. This is why the run-time library has +// to intercept __cxa_throw (as well as longjmp, etc) and unpoison the entire +// stack in the interceptor. This however does not work inside the +// actual function which catches the exception. Most likely because the +// compiler hoists the load of the shadow value somewhere too high. +// This causes asan to report a non-existing bug on 453.povray. +// It sounds like an LLVM bug. +bool AddressSanitizer::poisonStackInFunction(Module &M, Function &F) { + if (!ClStack) return false; + SmallVector<AllocaInst*, 16> AllocaVec; + SmallVector<Instruction*, 8> RetVec; + uint64_t TotalSize = 0; + + // Filter out Alloca instructions we want (and can) handle. + // Collect Ret instructions. + for (Function::iterator FI = F.begin(), FE = F.end(); + FI != FE; ++FI) { + BasicBlock &BB = *FI; + for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); + BI != BE; ++BI) { + if (isa<ReturnInst>(BI)) { + RetVec.push_back(BI); + continue; + } + + AllocaInst *AI = dyn_cast<AllocaInst>(BI); + if (!AI) continue; + if (AI->isArrayAllocation()) continue; + if (!AI->isStaticAlloca()) continue; + if (!AI->getAllocatedType()->isSized()) continue; + if (AI->getAlignment() > RedzoneSize) continue; + AllocaVec.push_back(AI); + uint64_t AlignedSize = getAlignedAllocaSize(AI); + TotalSize += AlignedSize; + } + } + + if (AllocaVec.empty()) return false; + + uint64_t LocalStackSize = TotalSize + (AllocaVec.size() + 1) * RedzoneSize; + + bool DoStackMalloc = ClUseAfterReturn + && LocalStackSize <= kMaxStackMallocSize; + + Instruction *InsBefore = AllocaVec[0]; + IRBuilder<> IRB(InsBefore); + + + Type *ByteArrayTy = ArrayType::get(IRB.getInt8Ty(), LocalStackSize); + AllocaInst *MyAlloca = + new AllocaInst(ByteArrayTy, "MyAlloca", InsBefore); + MyAlloca->setAlignment(RedzoneSize); + assert(MyAlloca->isStaticAlloca()); + Value *OrigStackBase = IRB.CreatePointerCast(MyAlloca, IntptrTy); + Value *LocalStackBase = OrigStackBase; + + if (DoStackMalloc) { + Value *AsanStackMallocFunc = M.getOrInsertFunction( + kAsanStackMallocName, IntptrTy, IntptrTy, IntptrTy, NULL); + LocalStackBase = IRB.CreateCall2(AsanStackMallocFunc, + ConstantInt::get(IntptrTy, LocalStackSize), OrigStackBase); + } + + // This string will be parsed by the run-time (DescribeStackAddress). + SmallString<2048> StackDescriptionStorage; + raw_svector_ostream StackDescription(StackDescriptionStorage); + StackDescription << F.getName() << " " << AllocaVec.size() << " "; + + uint64_t Pos = RedzoneSize; + // Replace Alloca instructions with base+offset. + for (size_t i = 0, n = AllocaVec.size(); i < n; i++) { + AllocaInst *AI = AllocaVec[i]; + uint64_t SizeInBytes = getAllocaSizeInBytes(AI); + StringRef Name = AI->getName(); + StackDescription << Pos << " " << SizeInBytes << " " + << Name.size() << " " << Name << " "; + uint64_t AlignedSize = getAlignedAllocaSize(AI); + assert((AlignedSize % RedzoneSize) == 0); + AI->replaceAllUsesWith( + IRB.CreateIntToPtr( + IRB.CreateAdd(LocalStackBase, ConstantInt::get(IntptrTy, Pos)), + AI->getType())); + Pos += AlignedSize + RedzoneSize; + } + assert(Pos == LocalStackSize); + + // Write the Magic value and the frame description constant to the redzone. + Value *BasePlus0 = IRB.CreateIntToPtr(LocalStackBase, IntptrPtrTy); + IRB.CreateStore(ConstantInt::get(IntptrTy, kCurrentStackFrameMagic), + BasePlus0); + Value *BasePlus1 = IRB.CreateAdd(LocalStackBase, + ConstantInt::get(IntptrTy, LongSize/8)); + BasePlus1 = IRB.CreateIntToPtr(BasePlus1, IntptrPtrTy); + Value *Description = IRB.CreatePointerCast( + createPrivateGlobalForString(M, StackDescription.str()), + IntptrTy); + IRB.CreateStore(Description, BasePlus1); + + // Poison the stack redzones at the entry. + Value *ShadowBase = memToShadow(LocalStackBase, IRB); + PoisonStack(ArrayRef<AllocaInst*>(AllocaVec), IRB, ShadowBase, true); + + Value *AsanStackFreeFunc = NULL; + if (DoStackMalloc) { + AsanStackFreeFunc = M.getOrInsertFunction( + kAsanStackFreeName, IRB.getVoidTy(), + IntptrTy, IntptrTy, IntptrTy, NULL); + } + + // Unpoison the stack before all ret instructions. + for (size_t i = 0, n = RetVec.size(); i < n; i++) { + Instruction *Ret = RetVec[i]; + IRBuilder<> IRBRet(Ret); + + // Mark the current frame as retired. + IRBRet.CreateStore(ConstantInt::get(IntptrTy, kRetiredStackFrameMagic), + BasePlus0); + // Unpoison the stack. + PoisonStack(ArrayRef<AllocaInst*>(AllocaVec), IRBRet, ShadowBase, false); + + if (DoStackMalloc) { + IRBRet.CreateCall3(AsanStackFreeFunc, LocalStackBase, + ConstantInt::get(IntptrTy, LocalStackSize), + OrigStackBase); + } + } + + if (ClDebugStack) { + DEBUG(dbgs() << F); + } + + return true; +} diff --git a/contrib/llvm/lib/Transforms/Instrumentation/BoundsChecking.cpp b/contrib/llvm/lib/Transforms/Instrumentation/BoundsChecking.cpp new file mode 100644 index 0000000..09e0f14 --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/BoundsChecking.cpp @@ -0,0 +1,209 @@ +//===- BoundsChecking.cpp - Instrumentation for run-time bounds checking --===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements a pass that instruments the code to perform run-time +// bounds checking on loads, stores, and other memory intrinsics. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "bounds-checking" +#include "llvm/IRBuilder.h" +#include "llvm/Intrinsics.h" +#include "llvm/Pass.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/MemoryBuiltins.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/InstIterator.h" +#include "llvm/Support/TargetFolder.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetData.h" +#include "llvm/Transforms/Instrumentation.h" +using namespace llvm; + +static cl::opt<bool> SingleTrapBB("bounds-checking-single-trap", + cl::desc("Use one trap block per function")); + +STATISTIC(ChecksAdded, "Bounds checks added"); +STATISTIC(ChecksSkipped, "Bounds checks skipped"); +STATISTIC(ChecksUnable, "Bounds checks unable to add"); + +typedef IRBuilder<true, TargetFolder> BuilderTy; + +namespace { + struct BoundsChecking : public FunctionPass { + static char ID; + + BoundsChecking(unsigned _Penalty = 5) : FunctionPass(ID), Penalty(_Penalty){ + initializeBoundsCheckingPass(*PassRegistry::getPassRegistry()); + } + + virtual bool runOnFunction(Function &F); + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired<TargetData>(); + } + + private: + const TargetData *TD; + ObjectSizeOffsetEvaluator *ObjSizeEval; + BuilderTy *Builder; + Instruction *Inst; + BasicBlock *TrapBB; + unsigned Penalty; + + BasicBlock *getTrapBB(); + void emitBranchToTrap(Value *Cmp = 0); + bool computeAllocSize(Value *Ptr, APInt &Offset, Value* &OffsetValue, + APInt &Size, Value* &SizeValue); + bool instrument(Value *Ptr, Value *Val); + }; +} + +char BoundsChecking::ID = 0; +INITIALIZE_PASS(BoundsChecking, "bounds-checking", "Run-time bounds checking", + false, false) + + +/// getTrapBB - create a basic block that traps. All overflowing conditions +/// branch to this block. There's only one trap block per function. +BasicBlock *BoundsChecking::getTrapBB() { + if (TrapBB && SingleTrapBB) + return TrapBB; + + Function *Fn = Inst->getParent()->getParent(); + BasicBlock::iterator PrevInsertPoint = Builder->GetInsertPoint(); + TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn); + Builder->SetInsertPoint(TrapBB); + + llvm::Value *F = Intrinsic::getDeclaration(Fn->getParent(), Intrinsic::trap); + CallInst *TrapCall = Builder->CreateCall(F); + TrapCall->setDoesNotReturn(); + TrapCall->setDoesNotThrow(); + TrapCall->setDebugLoc(Inst->getDebugLoc()); + Builder->CreateUnreachable(); + + Builder->SetInsertPoint(PrevInsertPoint); + return TrapBB; +} + + +/// emitBranchToTrap - emit a branch instruction to a trap block. +/// If Cmp is non-null, perform a jump only if its value evaluates to true. +void BoundsChecking::emitBranchToTrap(Value *Cmp) { + // check if the comparison is always false + ConstantInt *C = dyn_cast_or_null<ConstantInt>(Cmp); + if (C) { + ++ChecksSkipped; + if (!C->getZExtValue()) + return; + else + Cmp = 0; // unconditional branch + } + + Instruction *Inst = Builder->GetInsertPoint(); + BasicBlock *OldBB = Inst->getParent(); + BasicBlock *Cont = OldBB->splitBasicBlock(Inst); + OldBB->getTerminator()->eraseFromParent(); + + if (Cmp) + BranchInst::Create(getTrapBB(), Cont, Cmp, OldBB); + else + BranchInst::Create(getTrapBB(), OldBB); +} + + +/// instrument - adds run-time bounds checks to memory accessing instructions. +/// Ptr is the pointer that will be read/written, and InstVal is either the +/// result from the load or the value being stored. It is used to determine the +/// size of memory block that is touched. +/// Returns true if any change was made to the IR, false otherwise. +bool BoundsChecking::instrument(Value *Ptr, Value *InstVal) { + uint64_t NeededSize = TD->getTypeStoreSize(InstVal->getType()); + DEBUG(dbgs() << "Instrument " << *Ptr << " for " << Twine(NeededSize) + << " bytes\n"); + + SizeOffsetEvalType SizeOffset = ObjSizeEval->compute(Ptr); + + if (!ObjSizeEval->bothKnown(SizeOffset)) { + ++ChecksUnable; + return false; + } + + Value *Size = SizeOffset.first; + Value *Offset = SizeOffset.second; + ConstantInt *SizeCI = dyn_cast<ConstantInt>(Size); + + IntegerType *IntTy = TD->getIntPtrType(Inst->getContext()); + Value *NeededSizeVal = ConstantInt::get(IntTy, NeededSize); + + // three checks are required to ensure safety: + // . Offset >= 0 (since the offset is given from the base ptr) + // . Size >= Offset (unsigned) + // . Size - Offset >= NeededSize (unsigned) + // + // optimization: if Size >= 0 (signed), skip 1st check + // FIXME: add NSW/NUW here? -- we dont care if the subtraction overflows + Value *ObjSize = Builder->CreateSub(Size, Offset); + Value *Cmp2 = Builder->CreateICmpULT(Size, Offset); + Value *Cmp3 = Builder->CreateICmpULT(ObjSize, NeededSizeVal); + Value *Or = Builder->CreateOr(Cmp2, Cmp3); + if (!SizeCI || SizeCI->getValue().slt(0)) { + Value *Cmp1 = Builder->CreateICmpSLT(Offset, ConstantInt::get(IntTy, 0)); + Or = Builder->CreateOr(Cmp1, Or); + } + emitBranchToTrap(Or); + + ++ChecksAdded; + return true; +} + +bool BoundsChecking::runOnFunction(Function &F) { + TD = &getAnalysis<TargetData>(); + + TrapBB = 0; + BuilderTy TheBuilder(F.getContext(), TargetFolder(TD)); + Builder = &TheBuilder; + ObjectSizeOffsetEvaluator TheObjSizeEval(TD, F.getContext()); + ObjSizeEval = &TheObjSizeEval; + + // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory + // touching instructions + std::vector<Instruction*> WorkList; + for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) { + Instruction *I = &*i; + if (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<AtomicCmpXchgInst>(I) || + isa<AtomicRMWInst>(I)) + WorkList.push_back(I); + } + + bool MadeChange = false; + for (std::vector<Instruction*>::iterator i = WorkList.begin(), + e = WorkList.end(); i != e; ++i) { + Inst = *i; + + Builder->SetInsertPoint(Inst); + if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { + MadeChange |= instrument(LI->getPointerOperand(), LI); + } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { + MadeChange |= instrument(SI->getPointerOperand(), SI->getValueOperand()); + } else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(Inst)) { + MadeChange |= instrument(AI->getPointerOperand(),AI->getCompareOperand()); + } else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(Inst)) { + MadeChange |= instrument(AI->getPointerOperand(), AI->getValOperand()); + } else { + llvm_unreachable("unknown Instruction type"); + } + } + return MadeChange; +} + +FunctionPass *llvm::createBoundsCheckingPass(unsigned Penalty) { + return new BoundsChecking(Penalty); +} diff --git a/contrib/llvm/lib/Transforms/Instrumentation/EdgeProfiling.cpp b/contrib/llvm/lib/Transforms/Instrumentation/EdgeProfiling.cpp new file mode 100644 index 0000000..e8ef265 --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/EdgeProfiling.cpp @@ -0,0 +1,117 @@ +//===- EdgeProfiling.cpp - Insert counters for edge profiling -------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass instruments the specified program with counters for edge profiling. +// Edge profiling can give a reasonable approximation of the hot paths through a +// program, and is used for a wide variety of program transformations. +// +// Note that this implementation is very naive. We insert a counter for *every* +// edge in the program, instead of using control flow information to prune the +// number of counters inserted. +// +//===----------------------------------------------------------------------===// +#define DEBUG_TYPE "insert-edge-profiling" + +#include "ProfilingUtils.h" +#include "llvm/Module.h" +#include "llvm/Pass.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Instrumentation.h" +#include "llvm/ADT/Statistic.h" +#include <set> +using namespace llvm; + +STATISTIC(NumEdgesInserted, "The # of edges inserted."); + +namespace { + class EdgeProfiler : public ModulePass { + bool runOnModule(Module &M); + public: + static char ID; // Pass identification, replacement for typeid + EdgeProfiler() : ModulePass(ID) { + initializeEdgeProfilerPass(*PassRegistry::getPassRegistry()); + } + + virtual const char *getPassName() const { + return "Edge Profiler"; + } + }; +} + +char EdgeProfiler::ID = 0; +INITIALIZE_PASS(EdgeProfiler, "insert-edge-profiling", + "Insert instrumentation for edge profiling", false, false) + +ModulePass *llvm::createEdgeProfilerPass() { return new EdgeProfiler(); } + +bool EdgeProfiler::runOnModule(Module &M) { + Function *Main = M.getFunction("main"); + if (Main == 0) { + errs() << "WARNING: cannot insert edge profiling into a module" + << " with no main function!\n"; + return false; // No main, no instrumentation! + } + + std::set<BasicBlock*> BlocksToInstrument; + unsigned NumEdges = 0; + for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { + if (F->isDeclaration()) continue; + // Reserve space for (0,entry) edge. + ++NumEdges; + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { + // Keep track of which blocks need to be instrumented. We don't want to + // instrument blocks that are added as the result of breaking critical + // edges! + BlocksToInstrument.insert(BB); + NumEdges += BB->getTerminator()->getNumSuccessors(); + } + } + + Type *ATy = ArrayType::get(Type::getInt32Ty(M.getContext()), NumEdges); + GlobalVariable *Counters = + new GlobalVariable(M, ATy, false, GlobalValue::InternalLinkage, + Constant::getNullValue(ATy), "EdgeProfCounters"); + NumEdgesInserted = NumEdges; + + // Instrument all of the edges... + unsigned i = 0; + for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { + if (F->isDeclaration()) continue; + // Create counter for (0,entry) edge. + IncrementCounterInBlock(&F->getEntryBlock(), i++, Counters); + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) + if (BlocksToInstrument.count(BB)) { // Don't instrument inserted blocks + // Okay, we have to add a counter of each outgoing edge. If the + // outgoing edge is not critical don't split it, just insert the counter + // in the source or destination of the edge. + TerminatorInst *TI = BB->getTerminator(); + for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) { + // If the edge is critical, split it. + SplitCriticalEdge(TI, s, this); + + // Okay, we are guaranteed that the edge is no longer critical. If we + // only have a single successor, insert the counter in this block, + // otherwise insert it in the successor block. + if (TI->getNumSuccessors() == 1) { + // Insert counter at the start of the block + IncrementCounterInBlock(BB, i++, Counters, false); + } else { + // Insert counter at the start of the block + IncrementCounterInBlock(TI->getSuccessor(s), i++, Counters); + } + } + } + } + + // Add the initialization call to main. + InsertProfilingInitCall(Main, "llvm_start_edge_profiling", Counters); + return true; +} + diff --git a/contrib/llvm/lib/Transforms/Instrumentation/FunctionBlackList.cpp b/contrib/llvm/lib/Transforms/Instrumentation/FunctionBlackList.cpp new file mode 100644 index 0000000..188ea4d --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/FunctionBlackList.cpp @@ -0,0 +1,79 @@ +//===-- FunctionBlackList.cpp - blacklist of functions --------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This is a utility class for instrumentation passes (like AddressSanitizer +// or ThreadSanitizer) to avoid instrumenting some functions based on +// user-supplied blacklist. +// +//===----------------------------------------------------------------------===// + +#include "FunctionBlackList.h" +#include "llvm/ADT/OwningPtr.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/Function.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/Regex.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/system_error.h" + +namespace llvm { + +FunctionBlackList::FunctionBlackList(const std::string &Path) { + Functions = NULL; + const char *kFunPrefix = "fun:"; + if (!Path.size()) return; + std::string Fun; + + OwningPtr<MemoryBuffer> File; + if (error_code EC = MemoryBuffer::getFile(Path.c_str(), File)) { + report_fatal_error("Can't open blacklist file " + Path + ": " + + EC.message()); + } + MemoryBuffer *Buff = File.take(); + const char *Data = Buff->getBufferStart(); + size_t DataLen = Buff->getBufferSize(); + SmallVector<StringRef, 16> Lines; + SplitString(StringRef(Data, DataLen), Lines, "\n\r"); + for (size_t i = 0, numLines = Lines.size(); i < numLines; i++) { + if (Lines[i].startswith(kFunPrefix)) { + std::string ThisFunc = Lines[i].substr(strlen(kFunPrefix)); + std::string ThisFuncRE; + // add ThisFunc replacing * with .* + for (size_t j = 0, n = ThisFunc.size(); j < n; j++) { + if (ThisFunc[j] == '*') + ThisFuncRE += '.'; + ThisFuncRE += ThisFunc[j]; + } + // Check that the regexp is valid. + Regex CheckRE(ThisFuncRE); + std::string Error; + if (!CheckRE.isValid(Error)) + report_fatal_error("malformed blacklist regex: " + ThisFunc + + ": " + Error); + // Append to the final regexp. + if (Fun.size()) + Fun += "|"; + Fun += ThisFuncRE; + } + } + if (Fun.size()) { + Functions = new Regex(Fun); + } +} + +bool FunctionBlackList::isIn(const Function &F) { + if (Functions) { + bool Res = Functions->match(F.getName()); + return Res; + } + return false; +} + +} // namespace llvm diff --git a/contrib/llvm/lib/Transforms/Instrumentation/FunctionBlackList.h b/contrib/llvm/lib/Transforms/Instrumentation/FunctionBlackList.h new file mode 100644 index 0000000..c1239b9 --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/FunctionBlackList.h @@ -0,0 +1,37 @@ +//===-- FunctionBlackList.cpp - blacklist of functions ----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +//===----------------------------------------------------------------------===// +// +// This is a utility class for instrumentation passes (like AddressSanitizer +// or ThreadSanitizer) to avoid instrumenting some functions based on +// user-supplied blacklist. +// +//===----------------------------------------------------------------------===// +// + +#include <string> + +namespace llvm { +class Function; +class Regex; + +// Blacklisted functions are not instrumented. +// The blacklist file contains one or more lines like this: +// --- +// fun:FunctionWildCard +// --- +// This is similar to the "ignore" feature of ThreadSanitizer. +// http://code.google.com/p/data-race-test/wiki/ThreadSanitizerIgnores +class FunctionBlackList { + public: + FunctionBlackList(const std::string &Path); + bool isIn(const Function &F); + private: + Regex *Functions; +}; + +} // namespace llvm diff --git a/contrib/llvm/lib/Transforms/Instrumentation/GCOVProfiling.cpp b/contrib/llvm/lib/Transforms/Instrumentation/GCOVProfiling.cpp new file mode 100644 index 0000000..264a6a6 --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/GCOVProfiling.cpp @@ -0,0 +1,747 @@ +//===- GCOVProfiling.cpp - Insert edge counters for gcov profiling --------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass implements GCOV-style profiling. When this pass is run it emits +// "gcno" files next to the existing source, and instruments the code that runs +// to records the edges between blocks that run and emit a complementary "gcda" +// file on exit. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "insert-gcov-profiling" + +#include "ProfilingUtils.h" +#include "llvm/Transforms/Instrumentation.h" +#include "llvm/DebugInfo.h" +#include "llvm/IRBuilder.h" +#include "llvm/Instructions.h" +#include "llvm/Module.h" +#include "llvm/Pass.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/ADT/UniqueVector.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/DebugLoc.h" +#include "llvm/Support/InstIterator.h" +#include "llvm/Support/PathV2.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/ModuleUtils.h" +#include <string> +#include <utility> +using namespace llvm; + +namespace { + class GCOVProfiler : public ModulePass { + public: + static char ID; + GCOVProfiler() + : ModulePass(ID), EmitNotes(true), EmitData(true), Use402Format(false), + UseExtraChecksum(false) { + initializeGCOVProfilerPass(*PassRegistry::getPassRegistry()); + } + GCOVProfiler(bool EmitNotes, bool EmitData, bool use402Format = false, + bool useExtraChecksum = false) + : ModulePass(ID), EmitNotes(EmitNotes), EmitData(EmitData), + Use402Format(use402Format), UseExtraChecksum(useExtraChecksum) { + assert((EmitNotes || EmitData) && "GCOVProfiler asked to do nothing?"); + initializeGCOVProfilerPass(*PassRegistry::getPassRegistry()); + } + virtual const char *getPassName() const { + return "GCOV Profiler"; + } + private: + bool runOnModule(Module &M); + + // Create the GCNO files for the Module based on DebugInfo. + void emitGCNO(); + + // Modify the program to track transitions along edges and call into the + // profiling runtime to emit .gcda files when run. + bool emitProfileArcs(); + + // Get pointers to the functions in the runtime library. + Constant *getStartFileFunc(); + Constant *getIncrementIndirectCounterFunc(); + Constant *getEmitFunctionFunc(); + Constant *getEmitArcsFunc(); + Constant *getEndFileFunc(); + + // Create or retrieve an i32 state value that is used to represent the + // pred block number for certain non-trivial edges. + GlobalVariable *getEdgeStateValue(); + + // Produce a table of pointers to counters, by predecessor and successor + // block number. + GlobalVariable *buildEdgeLookupTable(Function *F, + GlobalVariable *Counter, + const UniqueVector<BasicBlock *> &Preds, + const UniqueVector<BasicBlock *> &Succs); + + // Add the function to write out all our counters to the global destructor + // list. + void insertCounterWriteout(SmallVector<std::pair<GlobalVariable *, + MDNode *>, 8> &); + void insertIndirectCounterIncrement(); + + std::string mangleName(DICompileUnit CU, std::string NewStem); + + bool EmitNotes; + bool EmitData; + bool Use402Format; + bool UseExtraChecksum; + + Module *M; + LLVMContext *Ctx; + }; +} + +char GCOVProfiler::ID = 0; +INITIALIZE_PASS(GCOVProfiler, "insert-gcov-profiling", + "Insert instrumentation for GCOV profiling", false, false) + +ModulePass *llvm::createGCOVProfilerPass(bool EmitNotes, bool EmitData, + bool Use402Format, + bool UseExtraChecksum) { + return new GCOVProfiler(EmitNotes, EmitData, Use402Format, UseExtraChecksum); +} + +namespace { + class GCOVRecord { + protected: + static const char *LinesTag; + static const char *FunctionTag; + static const char *BlockTag; + static const char *EdgeTag; + + GCOVRecord() {} + + void writeBytes(const char *Bytes, int Size) { + os->write(Bytes, Size); + } + + void write(uint32_t i) { + writeBytes(reinterpret_cast<char*>(&i), 4); + } + + // Returns the length measured in 4-byte blocks that will be used to + // represent this string in a GCOV file + unsigned lengthOfGCOVString(StringRef s) { + // A GCOV string is a length, followed by a NUL, then between 0 and 3 NULs + // padding out to the next 4-byte word. The length is measured in 4-byte + // words including padding, not bytes of actual string. + return (s.size() / 4) + 1; + } + + void writeGCOVString(StringRef s) { + uint32_t Len = lengthOfGCOVString(s); + write(Len); + writeBytes(s.data(), s.size()); + + // Write 1 to 4 bytes of NUL padding. + assert((unsigned)(4 - (s.size() % 4)) > 0); + assert((unsigned)(4 - (s.size() % 4)) <= 4); + writeBytes("\0\0\0\0", 4 - (s.size() % 4)); + } + + raw_ostream *os; + }; + const char *GCOVRecord::LinesTag = "\0\0\x45\x01"; + const char *GCOVRecord::FunctionTag = "\0\0\0\1"; + const char *GCOVRecord::BlockTag = "\0\0\x41\x01"; + const char *GCOVRecord::EdgeTag = "\0\0\x43\x01"; + + class GCOVFunction; + class GCOVBlock; + + // Constructed only by requesting it from a GCOVBlock, this object stores a + // list of line numbers and a single filename, representing lines that belong + // to the block. + class GCOVLines : public GCOVRecord { + public: + void addLine(uint32_t Line) { + Lines.push_back(Line); + } + + uint32_t length() { + // Here 2 = 1 for string length + 1 for '0' id#. + return lengthOfGCOVString(Filename) + 2 + Lines.size(); + } + + void writeOut() { + write(0); + writeGCOVString(Filename); + for (int i = 0, e = Lines.size(); i != e; ++i) + write(Lines[i]); + } + + GCOVLines(StringRef F, raw_ostream *os) + : Filename(F) { + this->os = os; + } + + private: + StringRef Filename; + SmallVector<uint32_t, 32> Lines; + }; + + // Represent a basic block in GCOV. Each block has a unique number in the + // function, number of lines belonging to each block, and a set of edges to + // other blocks. + class GCOVBlock : public GCOVRecord { + public: + GCOVLines &getFile(StringRef Filename) { + GCOVLines *&Lines = LinesByFile[Filename]; + if (!Lines) { + Lines = new GCOVLines(Filename, os); + } + return *Lines; + } + + void addEdge(GCOVBlock &Successor) { + OutEdges.push_back(&Successor); + } + + void writeOut() { + uint32_t Len = 3; + for (StringMap<GCOVLines *>::iterator I = LinesByFile.begin(), + E = LinesByFile.end(); I != E; ++I) { + Len += I->second->length(); + } + + writeBytes(LinesTag, 4); + write(Len); + write(Number); + for (StringMap<GCOVLines *>::iterator I = LinesByFile.begin(), + E = LinesByFile.end(); I != E; ++I) + I->second->writeOut(); + write(0); + write(0); + } + + ~GCOVBlock() { + DeleteContainerSeconds(LinesByFile); + } + + private: + friend class GCOVFunction; + + GCOVBlock(uint32_t Number, raw_ostream *os) + : Number(Number) { + this->os = os; + } + + uint32_t Number; + StringMap<GCOVLines *> LinesByFile; + SmallVector<GCOVBlock *, 4> OutEdges; + }; + + // A function has a unique identifier, a checksum (we leave as zero) and a + // set of blocks and a map of edges between blocks. This is the only GCOV + // object users can construct, the blocks and lines will be rooted here. + class GCOVFunction : public GCOVRecord { + public: + GCOVFunction(DISubprogram SP, raw_ostream *os, + bool Use402Format, bool UseExtraChecksum) { + this->os = os; + + Function *F = SP.getFunction(); + DEBUG(dbgs() << "Function: " << F->getName() << "\n"); + uint32_t i = 0; + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { + Blocks[BB] = new GCOVBlock(i++, os); + } + ReturnBlock = new GCOVBlock(i++, os); + + writeBytes(FunctionTag, 4); + uint32_t BlockLen = 1 + 1 + 1 + lengthOfGCOVString(SP.getName()) + + 1 + lengthOfGCOVString(SP.getFilename()) + 1; + if (UseExtraChecksum) + ++BlockLen; + write(BlockLen); + uint32_t Ident = reinterpret_cast<intptr_t>((MDNode*)SP); + write(Ident); + write(0); // lineno checksum + if (UseExtraChecksum) + write(0); // cfg checksum + writeGCOVString(SP.getName()); + writeGCOVString(SP.getFilename()); + write(SP.getLineNumber()); + } + + ~GCOVFunction() { + DeleteContainerSeconds(Blocks); + delete ReturnBlock; + } + + GCOVBlock &getBlock(BasicBlock *BB) { + return *Blocks[BB]; + } + + GCOVBlock &getReturnBlock() { + return *ReturnBlock; + } + + void writeOut() { + // Emit count of blocks. + writeBytes(BlockTag, 4); + write(Blocks.size() + 1); + for (int i = 0, e = Blocks.size() + 1; i != e; ++i) { + write(0); // No flags on our blocks. + } + DEBUG(dbgs() << Blocks.size() << " blocks.\n"); + + // Emit edges between blocks. + for (DenseMap<BasicBlock *, GCOVBlock *>::iterator I = Blocks.begin(), + E = Blocks.end(); I != E; ++I) { + GCOVBlock &Block = *I->second; + if (Block.OutEdges.empty()) continue; + + writeBytes(EdgeTag, 4); + write(Block.OutEdges.size() * 2 + 1); + write(Block.Number); + for (int i = 0, e = Block.OutEdges.size(); i != e; ++i) { + DEBUG(dbgs() << Block.Number << " -> " << Block.OutEdges[i]->Number + << "\n"); + write(Block.OutEdges[i]->Number); + write(0); // no flags + } + } + + // Emit lines for each block. + for (DenseMap<BasicBlock *, GCOVBlock *>::iterator I = Blocks.begin(), + E = Blocks.end(); I != E; ++I) { + I->second->writeOut(); + } + } + + private: + DenseMap<BasicBlock *, GCOVBlock *> Blocks; + GCOVBlock *ReturnBlock; + }; +} + +std::string GCOVProfiler::mangleName(DICompileUnit CU, std::string NewStem) { + if (NamedMDNode *GCov = M->getNamedMetadata("llvm.gcov")) { + for (int i = 0, e = GCov->getNumOperands(); i != e; ++i) { + MDNode *N = GCov->getOperand(i); + if (N->getNumOperands() != 2) continue; + MDString *GCovFile = dyn_cast<MDString>(N->getOperand(0)); + MDNode *CompileUnit = dyn_cast<MDNode>(N->getOperand(1)); + if (!GCovFile || !CompileUnit) continue; + if (CompileUnit == CU) { + SmallString<128> Filename = GCovFile->getString(); + sys::path::replace_extension(Filename, NewStem); + return Filename.str(); + } + } + } + + SmallString<128> Filename = CU.getFilename(); + sys::path::replace_extension(Filename, NewStem); + return sys::path::filename(Filename.str()); +} + +bool GCOVProfiler::runOnModule(Module &M) { + this->M = &M; + Ctx = &M.getContext(); + + if (EmitNotes) emitGCNO(); + if (EmitData) return emitProfileArcs(); + return false; +} + +void GCOVProfiler::emitGCNO() { + NamedMDNode *CU_Nodes = M->getNamedMetadata("llvm.dbg.cu"); + if (!CU_Nodes) return; + + for (unsigned i = 0, e = CU_Nodes->getNumOperands(); i != e; ++i) { + // Each compile unit gets its own .gcno file. This means that whether we run + // this pass over the original .o's as they're produced, or run it after + // LTO, we'll generate the same .gcno files. + + DICompileUnit CU(CU_Nodes->getOperand(i)); + std::string ErrorInfo; + raw_fd_ostream out(mangleName(CU, "gcno").c_str(), ErrorInfo, + raw_fd_ostream::F_Binary); + if (!Use402Format) + out.write("oncg*404MVLL", 12); + else + out.write("oncg*204MVLL", 12); + + DIArray SPs = CU.getSubprograms(); + for (unsigned i = 0, e = SPs.getNumElements(); i != e; ++i) { + DISubprogram SP(SPs.getElement(i)); + if (!SP.Verify()) continue; + + Function *F = SP.getFunction(); + if (!F) continue; + GCOVFunction Func(SP, &out, Use402Format, UseExtraChecksum); + + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { + GCOVBlock &Block = Func.getBlock(BB); + TerminatorInst *TI = BB->getTerminator(); + if (int successors = TI->getNumSuccessors()) { + for (int i = 0; i != successors; ++i) { + Block.addEdge(Func.getBlock(TI->getSuccessor(i))); + } + } else if (isa<ReturnInst>(TI)) { + Block.addEdge(Func.getReturnBlock()); + } + + uint32_t Line = 0; + for (BasicBlock::iterator I = BB->begin(), IE = BB->end(); + I != IE; ++I) { + const DebugLoc &Loc = I->getDebugLoc(); + if (Loc.isUnknown()) continue; + if (Line == Loc.getLine()) continue; + Line = Loc.getLine(); + if (SP != getDISubprogram(Loc.getScope(*Ctx))) continue; + + GCOVLines &Lines = Block.getFile(SP.getFilename()); + Lines.addLine(Loc.getLine()); + } + } + Func.writeOut(); + } + out.write("\0\0\0\0\0\0\0\0", 8); // EOF + out.close(); + } +} + +bool GCOVProfiler::emitProfileArcs() { + NamedMDNode *CU_Nodes = M->getNamedMetadata("llvm.dbg.cu"); + if (!CU_Nodes) return false; + + bool Result = false; + bool InsertIndCounterIncrCode = false; + for (unsigned i = 0, e = CU_Nodes->getNumOperands(); i != e; ++i) { + DICompileUnit CU(CU_Nodes->getOperand(i)); + DIArray SPs = CU.getSubprograms(); + SmallVector<std::pair<GlobalVariable *, MDNode *>, 8> CountersBySP; + for (unsigned i = 0, e = SPs.getNumElements(); i != e; ++i) { + DISubprogram SP(SPs.getElement(i)); + if (!SP.Verify()) continue; + Function *F = SP.getFunction(); + if (!F) continue; + if (!Result) Result = true; + unsigned Edges = 0; + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { + TerminatorInst *TI = BB->getTerminator(); + if (isa<ReturnInst>(TI)) + ++Edges; + else + Edges += TI->getNumSuccessors(); + } + + ArrayType *CounterTy = + ArrayType::get(Type::getInt64Ty(*Ctx), Edges); + GlobalVariable *Counters = + new GlobalVariable(*M, CounterTy, false, + GlobalValue::InternalLinkage, + Constant::getNullValue(CounterTy), + "__llvm_gcov_ctr"); + CountersBySP.push_back(std::make_pair(Counters, (MDNode*)SP)); + + UniqueVector<BasicBlock *> ComplexEdgePreds; + UniqueVector<BasicBlock *> ComplexEdgeSuccs; + + unsigned Edge = 0; + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { + TerminatorInst *TI = BB->getTerminator(); + int Successors = isa<ReturnInst>(TI) ? 1 : TI->getNumSuccessors(); + if (Successors) { + IRBuilder<> Builder(TI); + + if (Successors == 1) { + Value *Counter = Builder.CreateConstInBoundsGEP2_64(Counters, 0, + Edge); + Value *Count = Builder.CreateLoad(Counter); + Count = Builder.CreateAdd(Count, + ConstantInt::get(Type::getInt64Ty(*Ctx),1)); + Builder.CreateStore(Count, Counter); + } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { + Value *Sel = Builder.CreateSelect( + BI->getCondition(), + ConstantInt::get(Type::getInt64Ty(*Ctx), Edge), + ConstantInt::get(Type::getInt64Ty(*Ctx), Edge + 1)); + SmallVector<Value *, 2> Idx; + Idx.push_back(Constant::getNullValue(Type::getInt64Ty(*Ctx))); + Idx.push_back(Sel); + Value *Counter = Builder.CreateInBoundsGEP(Counters, Idx); + Value *Count = Builder.CreateLoad(Counter); + Count = Builder.CreateAdd(Count, + ConstantInt::get(Type::getInt64Ty(*Ctx),1)); + Builder.CreateStore(Count, Counter); + } else { + ComplexEdgePreds.insert(BB); + for (int i = 0; i != Successors; ++i) + ComplexEdgeSuccs.insert(TI->getSuccessor(i)); + } + Edge += Successors; + } + } + + if (!ComplexEdgePreds.empty()) { + GlobalVariable *EdgeTable = + buildEdgeLookupTable(F, Counters, + ComplexEdgePreds, ComplexEdgeSuccs); + GlobalVariable *EdgeState = getEdgeStateValue(); + + Type *Int32Ty = Type::getInt32Ty(*Ctx); + for (int i = 0, e = ComplexEdgePreds.size(); i != e; ++i) { + IRBuilder<> Builder(ComplexEdgePreds[i+1]->getTerminator()); + Builder.CreateStore(ConstantInt::get(Int32Ty, i), EdgeState); + } + for (int i = 0, e = ComplexEdgeSuccs.size(); i != e; ++i) { + // call runtime to perform increment + BasicBlock::iterator InsertPt = + ComplexEdgeSuccs[i+1]->getFirstInsertionPt(); + IRBuilder<> Builder(InsertPt); + Value *CounterPtrArray = + Builder.CreateConstInBoundsGEP2_64(EdgeTable, 0, + i * ComplexEdgePreds.size()); + + // Build code to increment the counter. + InsertIndCounterIncrCode = true; + Builder.CreateCall2(getIncrementIndirectCounterFunc(), + EdgeState, CounterPtrArray); + } + } + } + + insertCounterWriteout(CountersBySP); + } + + if (InsertIndCounterIncrCode) + insertIndirectCounterIncrement(); + + return Result; +} + +// All edges with successors that aren't branches are "complex", because it +// requires complex logic to pick which counter to update. +GlobalVariable *GCOVProfiler::buildEdgeLookupTable( + Function *F, + GlobalVariable *Counters, + const UniqueVector<BasicBlock *> &Preds, + const UniqueVector<BasicBlock *> &Succs) { + // TODO: support invoke, threads. We rely on the fact that nothing can modify + // the whole-Module pred edge# between the time we set it and the time we next + // read it. Threads and invoke make this untrue. + + // emit [(succs * preds) x i64*], logically [succ x [pred x i64*]]. + Type *Int64PtrTy = Type::getInt64PtrTy(*Ctx); + ArrayType *EdgeTableTy = ArrayType::get( + Int64PtrTy, Succs.size() * Preds.size()); + + Constant **EdgeTable = new Constant*[Succs.size() * Preds.size()]; + Constant *NullValue = Constant::getNullValue(Int64PtrTy); + for (int i = 0, ie = Succs.size() * Preds.size(); i != ie; ++i) + EdgeTable[i] = NullValue; + + unsigned Edge = 0; + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { + TerminatorInst *TI = BB->getTerminator(); + int Successors = isa<ReturnInst>(TI) ? 1 : TI->getNumSuccessors(); + if (Successors > 1 && !isa<BranchInst>(TI) && !isa<ReturnInst>(TI)) { + for (int i = 0; i != Successors; ++i) { + BasicBlock *Succ = TI->getSuccessor(i); + IRBuilder<> builder(Succ); + Value *Counter = builder.CreateConstInBoundsGEP2_64(Counters, 0, + Edge + i); + EdgeTable[((Succs.idFor(Succ)-1) * Preds.size()) + + (Preds.idFor(BB)-1)] = cast<Constant>(Counter); + } + } + Edge += Successors; + } + + ArrayRef<Constant*> V(&EdgeTable[0], Succs.size() * Preds.size()); + GlobalVariable *EdgeTableGV = + new GlobalVariable( + *M, EdgeTableTy, true, GlobalValue::InternalLinkage, + ConstantArray::get(EdgeTableTy, V), + "__llvm_gcda_edge_table"); + EdgeTableGV->setUnnamedAddr(true); + return EdgeTableGV; +} + +Constant *GCOVProfiler::getStartFileFunc() { + FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), + Type::getInt8PtrTy(*Ctx), false); + return M->getOrInsertFunction("llvm_gcda_start_file", FTy); +} + +Constant *GCOVProfiler::getIncrementIndirectCounterFunc() { + Type *Int32Ty = Type::getInt32Ty(*Ctx); + Type *Int64Ty = Type::getInt64Ty(*Ctx); + Type *Args[] = { + Int32Ty->getPointerTo(), // uint32_t *predecessor + Int64Ty->getPointerTo()->getPointerTo() // uint64_t **counters + }; + FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), Args, false); + return M->getOrInsertFunction("__llvm_gcov_indirect_counter_increment", FTy); +} + +Constant *GCOVProfiler::getEmitFunctionFunc() { + Type *Args[2] = { + Type::getInt32Ty(*Ctx), // uint32_t ident + Type::getInt8PtrTy(*Ctx), // const char *function_name + }; + FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), Args, false); + return M->getOrInsertFunction("llvm_gcda_emit_function", FTy); +} + +Constant *GCOVProfiler::getEmitArcsFunc() { + Type *Args[] = { + Type::getInt32Ty(*Ctx), // uint32_t num_counters + Type::getInt64PtrTy(*Ctx), // uint64_t *counters + }; + FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), + Args, false); + return M->getOrInsertFunction("llvm_gcda_emit_arcs", FTy); +} + +Constant *GCOVProfiler::getEndFileFunc() { + FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), false); + return M->getOrInsertFunction("llvm_gcda_end_file", FTy); +} + +GlobalVariable *GCOVProfiler::getEdgeStateValue() { + GlobalVariable *GV = M->getGlobalVariable("__llvm_gcov_global_state_pred"); + if (!GV) { + GV = new GlobalVariable(*M, Type::getInt32Ty(*Ctx), false, + GlobalValue::InternalLinkage, + ConstantInt::get(Type::getInt32Ty(*Ctx), + 0xffffffff), + "__llvm_gcov_global_state_pred"); + GV->setUnnamedAddr(true); + } + return GV; +} + +void GCOVProfiler::insertCounterWriteout( + SmallVector<std::pair<GlobalVariable *, MDNode *>, 8> &CountersBySP) { + FunctionType *WriteoutFTy = + FunctionType::get(Type::getVoidTy(*Ctx), false); + Function *WriteoutF = Function::Create(WriteoutFTy, + GlobalValue::InternalLinkage, + "__llvm_gcov_writeout", M); + WriteoutF->setUnnamedAddr(true); + BasicBlock *BB = BasicBlock::Create(*Ctx, "", WriteoutF); + IRBuilder<> Builder(BB); + + Constant *StartFile = getStartFileFunc(); + Constant *EmitFunction = getEmitFunctionFunc(); + Constant *EmitArcs = getEmitArcsFunc(); + Constant *EndFile = getEndFileFunc(); + + NamedMDNode *CU_Nodes = M->getNamedMetadata("llvm.dbg.cu"); + if (CU_Nodes) { + for (unsigned i = 0, e = CU_Nodes->getNumOperands(); i != e; ++i) { + DICompileUnit compile_unit(CU_Nodes->getOperand(i)); + std::string FilenameGcda = mangleName(compile_unit, "gcda"); + Builder.CreateCall(StartFile, + Builder.CreateGlobalStringPtr(FilenameGcda)); + for (SmallVector<std::pair<GlobalVariable *, MDNode *>, 8>::iterator + I = CountersBySP.begin(), E = CountersBySP.end(); + I != E; ++I) { + DISubprogram SP(I->second); + intptr_t ident = reinterpret_cast<intptr_t>(I->second); + Builder.CreateCall2(EmitFunction, + ConstantInt::get(Type::getInt32Ty(*Ctx), ident), + Builder.CreateGlobalStringPtr(SP.getName())); + + GlobalVariable *GV = I->first; + unsigned Arcs = + cast<ArrayType>(GV->getType()->getElementType())->getNumElements(); + Builder.CreateCall2(EmitArcs, + ConstantInt::get(Type::getInt32Ty(*Ctx), Arcs), + Builder.CreateConstGEP2_64(GV, 0, 0)); + } + Builder.CreateCall(EndFile); + } + } + Builder.CreateRetVoid(); + + // Create a small bit of code that registers the "__llvm_gcov_writeout" + // function to be executed at exit. + FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), false); + Function *F = Function::Create(FTy, GlobalValue::InternalLinkage, + "__llvm_gcov_init", M); + F->setUnnamedAddr(true); + F->setLinkage(GlobalValue::InternalLinkage); + F->addFnAttr(Attribute::NoInline); + + BB = BasicBlock::Create(*Ctx, "entry", F); + Builder.SetInsertPoint(BB); + + FTy = FunctionType::get(Type::getInt32Ty(*Ctx), + PointerType::get(FTy, 0), false); + Constant *AtExitFn = M->getOrInsertFunction("atexit", FTy); + Builder.CreateCall(AtExitFn, WriteoutF); + Builder.CreateRetVoid(); + + appendToGlobalCtors(*M, F, 0); +} + +void GCOVProfiler::insertIndirectCounterIncrement() { + Function *Fn = + cast<Function>(GCOVProfiler::getIncrementIndirectCounterFunc()); + Fn->setUnnamedAddr(true); + Fn->setLinkage(GlobalValue::InternalLinkage); + Fn->addFnAttr(Attribute::NoInline); + + Type *Int32Ty = Type::getInt32Ty(*Ctx); + Type *Int64Ty = Type::getInt64Ty(*Ctx); + Constant *NegOne = ConstantInt::get(Int32Ty, 0xffffffff); + + // Create basic blocks for function. + BasicBlock *BB = BasicBlock::Create(*Ctx, "entry", Fn); + IRBuilder<> Builder(BB); + + BasicBlock *PredNotNegOne = BasicBlock::Create(*Ctx, "", Fn); + BasicBlock *CounterEnd = BasicBlock::Create(*Ctx, "", Fn); + BasicBlock *Exit = BasicBlock::Create(*Ctx, "exit", Fn); + + // uint32_t pred = *predecessor; + // if (pred == 0xffffffff) return; + Argument *Arg = Fn->arg_begin(); + Arg->setName("predecessor"); + Value *Pred = Builder.CreateLoad(Arg, "pred"); + Value *Cond = Builder.CreateICmpEQ(Pred, NegOne); + BranchInst::Create(Exit, PredNotNegOne, Cond, BB); + + Builder.SetInsertPoint(PredNotNegOne); + + // uint64_t *counter = counters[pred]; + // if (!counter) return; + Value *ZExtPred = Builder.CreateZExt(Pred, Int64Ty); + Arg = llvm::next(Fn->arg_begin()); + Arg->setName("counters"); + Value *GEP = Builder.CreateGEP(Arg, ZExtPred); + Value *Counter = Builder.CreateLoad(GEP, "counter"); + Cond = Builder.CreateICmpEQ(Counter, + Constant::getNullValue(Int64Ty->getPointerTo())); + Builder.CreateCondBr(Cond, Exit, CounterEnd); + + // ++*counter; + Builder.SetInsertPoint(CounterEnd); + Value *Add = Builder.CreateAdd(Builder.CreateLoad(Counter), + ConstantInt::get(Int64Ty, 1)); + Builder.CreateStore(Add, Counter); + Builder.CreateBr(Exit); + + // Fill in the exit block. + Builder.SetInsertPoint(Exit); + Builder.CreateRetVoid(); +} diff --git a/contrib/llvm/lib/Transforms/Instrumentation/Instrumentation.cpp b/contrib/llvm/lib/Transforms/Instrumentation/Instrumentation.cpp new file mode 100644 index 0000000..1e0b4a3 --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/Instrumentation.cpp @@ -0,0 +1,36 @@ +//===-- Instrumentation.cpp - TransformUtils Infrastructure ---------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the common initialization infrastructure for the +// Instrumentation library. +// +//===----------------------------------------------------------------------===// + +#include "llvm/InitializePasses.h" +#include "llvm-c/Initialization.h" + +using namespace llvm; + +/// initializeInstrumentation - Initialize all passes in the TransformUtils +/// library. +void llvm::initializeInstrumentation(PassRegistry &Registry) { + initializeAddressSanitizerPass(Registry); + initializeBoundsCheckingPass(Registry); + initializeEdgeProfilerPass(Registry); + initializeGCOVProfilerPass(Registry); + initializeOptimalEdgeProfilerPass(Registry); + initializePathProfilerPass(Registry); + initializeThreadSanitizerPass(Registry); +} + +/// LLVMInitializeInstrumentation - C binding for +/// initializeInstrumentation. +void LLVMInitializeInstrumentation(LLVMPassRegistryRef R) { + initializeInstrumentation(*unwrap(R)); +} diff --git a/contrib/llvm/lib/Transforms/Instrumentation/MaximumSpanningTree.h b/contrib/llvm/lib/Transforms/Instrumentation/MaximumSpanningTree.h new file mode 100644 index 0000000..f76c77e --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/MaximumSpanningTree.h @@ -0,0 +1,108 @@ +//===- llvm/Analysis/MaximumSpanningTree.h - Interface ----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This module provides means for calculating a maximum spanning tree for a +// given set of weighted edges. The type parameter T is the type of a node. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H +#define LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H + +#include "llvm/BasicBlock.h" +#include "llvm/ADT/EquivalenceClasses.h" +#include <vector> +#include <algorithm> + +namespace llvm { + + /// MaximumSpanningTree - A MST implementation. + /// The type parameter T determines the type of the nodes of the graph. + template <typename T> + class MaximumSpanningTree { + + // A comparing class for comparing weighted edges. + template <typename CT> + struct EdgeWeightCompare { + bool operator()(typename MaximumSpanningTree<CT>::EdgeWeight X, + typename MaximumSpanningTree<CT>::EdgeWeight Y) const { + if (X.second > Y.second) return true; + if (X.second < Y.second) return false; + if (const BasicBlock *BBX = dyn_cast<BasicBlock>(X.first.first)) { + if (const BasicBlock *BBY = dyn_cast<BasicBlock>(Y.first.first)) { + if (BBX->size() > BBY->size()) return true; + if (BBX->size() < BBY->size()) return false; + } + } + if (const BasicBlock *BBX = dyn_cast<BasicBlock>(X.first.second)) { + if (const BasicBlock *BBY = dyn_cast<BasicBlock>(Y.first.second)) { + if (BBX->size() > BBY->size()) return true; + if (BBX->size() < BBY->size()) return false; + } + } + return false; + } + }; + + public: + typedef std::pair<const T*, const T*> Edge; + typedef std::pair<Edge, double> EdgeWeight; + typedef std::vector<EdgeWeight> EdgeWeights; + protected: + typedef std::vector<Edge> MaxSpanTree; + + MaxSpanTree MST; + + public: + static char ID; // Class identification, replacement for typeinfo + + /// MaximumSpanningTree() - Takes a vector of weighted edges and returns a + /// spanning tree. + MaximumSpanningTree(EdgeWeights &EdgeVector) { + + std::stable_sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare<T>()); + + // Create spanning tree, Forest contains a special data structure + // that makes checking if two nodes are already in a common (sub-)tree + // fast and cheap. + EquivalenceClasses<const T*> Forest; + for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), + EWe = EdgeVector.end(); EWi != EWe; ++EWi) { + Edge e = (*EWi).first; + + Forest.insert(e.first); + Forest.insert(e.second); + } + + // Iterate over the sorted edges, biggest first. + for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), + EWe = EdgeVector.end(); EWi != EWe; ++EWi) { + Edge e = (*EWi).first; + + if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) { + Forest.unionSets(e.first, e.second); + // So we know now that the edge is not already in a subtree, so we push + // the edge to the MST. + MST.push_back(e); + } + } + } + + typename MaxSpanTree::iterator begin() { + return MST.begin(); + } + + typename MaxSpanTree::iterator end() { + return MST.end(); + } + }; + +} // End llvm namespace + +#endif diff --git a/contrib/llvm/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp b/contrib/llvm/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp new file mode 100644 index 0000000..1fe1254 --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp @@ -0,0 +1,225 @@ +//===- OptimalEdgeProfiling.cpp - Insert counters for opt. edge profiling -===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass instruments the specified program with counters for edge profiling. +// Edge profiling can give a reasonable approximation of the hot paths through a +// program, and is used for a wide variety of program transformations. +// +//===----------------------------------------------------------------------===// +#define DEBUG_TYPE "insert-optimal-edge-profiling" +#include "ProfilingUtils.h" +#include "llvm/Constants.h" +#include "llvm/Module.h" +#include "llvm/Pass.h" +#include "llvm/Analysis/Passes.h" +#include "llvm/Analysis/ProfileInfo.h" +#include "llvm/Analysis/ProfileInfoLoader.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Support/Debug.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Instrumentation.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/Statistic.h" +#include "MaximumSpanningTree.h" +using namespace llvm; + +STATISTIC(NumEdgesInserted, "The # of edges inserted."); + +namespace { + class OptimalEdgeProfiler : public ModulePass { + bool runOnModule(Module &M); + public: + static char ID; // Pass identification, replacement for typeid + OptimalEdgeProfiler() : ModulePass(ID) { + initializeOptimalEdgeProfilerPass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequiredID(ProfileEstimatorPassID); + AU.addRequired<ProfileInfo>(); + } + + virtual const char *getPassName() const { + return "Optimal Edge Profiler"; + } + }; +} + +char OptimalEdgeProfiler::ID = 0; +INITIALIZE_PASS_BEGIN(OptimalEdgeProfiler, "insert-optimal-edge-profiling", + "Insert optimal instrumentation for edge profiling", + false, false) +INITIALIZE_PASS_DEPENDENCY(ProfileEstimatorPass) +INITIALIZE_AG_DEPENDENCY(ProfileInfo) +INITIALIZE_PASS_END(OptimalEdgeProfiler, "insert-optimal-edge-profiling", + "Insert optimal instrumentation for edge profiling", + false, false) + +ModulePass *llvm::createOptimalEdgeProfilerPass() { + return new OptimalEdgeProfiler(); +} + +inline static void printEdgeCounter(ProfileInfo::Edge e, + BasicBlock* b, + unsigned i) { + DEBUG(dbgs() << "--Edge Counter for " << (e) << " in " \ + << ((b)?(b)->getName():"0") << " (# " << (i) << ")\n"); +} + +bool OptimalEdgeProfiler::runOnModule(Module &M) { + Function *Main = M.getFunction("main"); + if (Main == 0) { + errs() << "WARNING: cannot insert edge profiling into a module" + << " with no main function!\n"; + return false; // No main, no instrumentation! + } + + // NumEdges counts all the edges that may be instrumented. Later on its + // decided which edges to actually instrument, to achieve optimal profiling. + // For the entry block a virtual edge (0,entry) is reserved, for each block + // with no successors an edge (BB,0) is reserved. These edges are necessary + // to calculate a truly optimal maximum spanning tree and thus an optimal + // instrumentation. + unsigned NumEdges = 0; + + for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { + if (F->isDeclaration()) continue; + // Reserve space for (0,entry) edge. + ++NumEdges; + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { + // Keep track of which blocks need to be instrumented. We don't want to + // instrument blocks that are added as the result of breaking critical + // edges! + if (BB->getTerminator()->getNumSuccessors() == 0) { + // Reserve space for (BB,0) edge. + ++NumEdges; + } else { + NumEdges += BB->getTerminator()->getNumSuccessors(); + } + } + } + + // In the profiling output a counter for each edge is reserved, but only few + // are used. This is done to be able to read back in the profile without + // calulating the maximum spanning tree again, instead each edge counter that + // is not used is initialised with -1 to signal that this edge counter has to + // be calculated from other edge counters on reading the profile info back + // in. + + Type *Int32 = Type::getInt32Ty(M.getContext()); + ArrayType *ATy = ArrayType::get(Int32, NumEdges); + GlobalVariable *Counters = + new GlobalVariable(M, ATy, false, GlobalValue::InternalLinkage, + Constant::getNullValue(ATy), "OptEdgeProfCounters"); + NumEdgesInserted = 0; + + std::vector<Constant*> Initializer(NumEdges); + Constant *Zero = ConstantInt::get(Int32, 0); + Constant *Uncounted = ConstantInt::get(Int32, ProfileInfoLoader::Uncounted); + + // Instrument all of the edges not in MST... + unsigned i = 0; + for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) { + if (F->isDeclaration()) continue; + DEBUG(dbgs() << "Working on " << F->getName() << "\n"); + + // Calculate a Maximum Spanning Tree with the edge weights determined by + // ProfileEstimator. ProfileEstimator also assign weights to the virtual + // edges (0,entry) and (BB,0) (for blocks with no successors) and this + // edges also participate in the maximum spanning tree calculation. + // The third parameter of MaximumSpanningTree() has the effect that not the + // actual MST is returned but the edges _not_ in the MST. + + ProfileInfo::EdgeWeights ECs = + getAnalysis<ProfileInfo>(*F).getEdgeWeights(F); + std::vector<ProfileInfo::EdgeWeight> EdgeVector(ECs.begin(), ECs.end()); + MaximumSpanningTree<BasicBlock> MST(EdgeVector); + std::stable_sort(MST.begin(), MST.end()); + + // Check if (0,entry) not in the MST. If not, instrument edge + // (IncrementCounterInBlock()) and set the counter initially to zero, if + // the edge is in the MST the counter is initialised to -1. + + BasicBlock *entry = &(F->getEntryBlock()); + ProfileInfo::Edge edge = ProfileInfo::getEdge(0, entry); + if (!std::binary_search(MST.begin(), MST.end(), edge)) { + printEdgeCounter(edge, entry, i); + IncrementCounterInBlock(entry, i, Counters); ++NumEdgesInserted; + Initializer[i++] = (Zero); + } else{ + Initializer[i++] = (Uncounted); + } + + // InsertedBlocks contains all blocks that were inserted for splitting an + // edge, this blocks do not have to be instrumented. + DenseSet<BasicBlock*> InsertedBlocks; + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { + // Check if block was not inserted and thus does not have to be + // instrumented. + if (InsertedBlocks.count(BB)) continue; + + // Okay, we have to add a counter of each outgoing edge not in MST. If + // the outgoing edge is not critical don't split it, just insert the + // counter in the source or destination of the edge. Also, if the block + // has no successors, the virtual edge (BB,0) is processed. + TerminatorInst *TI = BB->getTerminator(); + if (TI->getNumSuccessors() == 0) { + ProfileInfo::Edge edge = ProfileInfo::getEdge(BB, 0); + if (!std::binary_search(MST.begin(), MST.end(), edge)) { + printEdgeCounter(edge, BB, i); + IncrementCounterInBlock(BB, i, Counters); ++NumEdgesInserted; + Initializer[i++] = (Zero); + } else{ + Initializer[i++] = (Uncounted); + } + } + for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) { + BasicBlock *Succ = TI->getSuccessor(s); + ProfileInfo::Edge edge = ProfileInfo::getEdge(BB,Succ); + if (!std::binary_search(MST.begin(), MST.end(), edge)) { + + // If the edge is critical, split it. + bool wasInserted = SplitCriticalEdge(TI, s, this); + Succ = TI->getSuccessor(s); + if (wasInserted) + InsertedBlocks.insert(Succ); + + // Okay, we are guaranteed that the edge is no longer critical. If + // we only have a single successor, insert the counter in this block, + // otherwise insert it in the successor block. + if (TI->getNumSuccessors() == 1) { + // Insert counter at the start of the block + printEdgeCounter(edge, BB, i); + IncrementCounterInBlock(BB, i, Counters); ++NumEdgesInserted; + } else { + // Insert counter at the start of the block + printEdgeCounter(edge, Succ, i); + IncrementCounterInBlock(Succ, i, Counters); ++NumEdgesInserted; + } + Initializer[i++] = (Zero); + } else { + Initializer[i++] = (Uncounted); + } + } + } + } + + // Check if the number of edges counted at first was the number of edges we + // considered for instrumentation. + assert(i == NumEdges && "the number of edges in counting array is wrong"); + + // Assign the now completely defined initialiser to the array. + Constant *init = ConstantArray::get(ATy, Initializer); + Counters->setInitializer(init); + + // Add the initialization call to main. + InsertProfilingInitCall(Main, "llvm_start_opt_edge_profiling", Counters); + return true; +} + diff --git a/contrib/llvm/lib/Transforms/Instrumentation/PathProfiling.cpp b/contrib/llvm/lib/Transforms/Instrumentation/PathProfiling.cpp new file mode 100644 index 0000000..cc27146 --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/PathProfiling.cpp @@ -0,0 +1,1425 @@ +//===- PathProfiling.cpp - Inserts counters for path profiling ------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass instruments functions for Ball-Larus path profiling. Ball-Larus +// profiling converts the CFG into a DAG by replacing backedges with edges +// from entry to the start block and from the end block to exit. The paths +// along the new DAG are enumrated, i.e. each path is given a path number. +// Edges are instrumented to increment the path number register, such that the +// path number register will equal the path number of the path taken at the +// exit. +// +// This file defines classes for building a CFG for use with different stages +// in the Ball-Larus path profiling instrumentation [Ball96]. The +// requirements are formatting the llvm CFG into the Ball-Larus DAG, path +// numbering, finding a spanning tree, moving increments from the spanning +// tree to chords. +// +// Terms: +// DAG - Directed Acyclic Graph. +// Ball-Larus DAG - A CFG with an entry node, an exit node, and backedges +// removed in the following manner. For every backedge +// v->w, insert edge ENTRY->w and edge v->EXIT. +// Path Number - The number corresponding to a specific path through a +// Ball-Larus DAG. +// Spanning Tree - A subgraph, S, is a spanning tree if S covers all +// vertices and is a tree. +// Chord - An edge not in the spanning tree. +// +// [Ball96] +// T. Ball and J. R. Larus. "Efficient Path Profiling." +// International Symposium on Microarchitecture, pages 46-57, 1996. +// http://portal.acm.org/citation.cfm?id=243857 +// +// [Ball94] +// Thomas Ball. "Efficiently Counting Program Events with Support for +// On-line queries." +// ACM Transactions on Programmmg Languages and Systems, Vol 16, No 5, +// September 1994, Pages 1399-1410. +//===----------------------------------------------------------------------===// +#define DEBUG_TYPE "insert-path-profiling" + +#include "llvm/DerivedTypes.h" +#include "ProfilingUtils.h" +#include "llvm/Analysis/PathNumbering.h" +#include "llvm/Constants.h" +#include "llvm/DerivedTypes.h" +#include "llvm/InstrTypes.h" +#include "llvm/Instructions.h" +#include "llvm/LLVMContext.h" +#include "llvm/Module.h" +#include "llvm/Pass.h" +#include "llvm/TypeBuilder.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/CFG.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Instrumentation.h" +#include <vector> + +#define HASH_THRESHHOLD 100000 + +using namespace llvm; + +namespace { +class BLInstrumentationNode; +class BLInstrumentationEdge; +class BLInstrumentationDag; + +// --------------------------------------------------------------------------- +// BLInstrumentationNode extends BallLarusNode with member used by the +// instrumentation algortihms. +// --------------------------------------------------------------------------- +class BLInstrumentationNode : public BallLarusNode { +public: + // Creates a new BLInstrumentationNode from a BasicBlock. + BLInstrumentationNode(BasicBlock* BB); + + // Get/sets the Value corresponding to the pathNumber register, + // constant or phinode. Used by the instrumentation code to remember + // path number Values. + Value* getStartingPathNumber(); + void setStartingPathNumber(Value* pathNumber); + + Value* getEndingPathNumber(); + void setEndingPathNumber(Value* pathNumber); + + // Get/set the PHINode Instruction for this node. + PHINode* getPathPHI(); + void setPathPHI(PHINode* pathPHI); + +private: + + Value* _startingPathNumber; // The Value for the current pathNumber. + Value* _endingPathNumber; // The Value for the current pathNumber. + PHINode* _pathPHI; // The PHINode for current pathNumber. +}; + +// -------------------------------------------------------------------------- +// BLInstrumentationEdge extends BallLarusEdge with data about the +// instrumentation that will end up on each edge. +// -------------------------------------------------------------------------- +class BLInstrumentationEdge : public BallLarusEdge { +public: + BLInstrumentationEdge(BLInstrumentationNode* source, + BLInstrumentationNode* target); + + // Sets the target node of this edge. Required to split edges. + void setTarget(BallLarusNode* node); + + // Get/set whether edge is in the spanning tree. + bool isInSpanningTree() const; + void setIsInSpanningTree(bool isInSpanningTree); + + // Get/ set whether this edge will be instrumented with a path number + // initialization. + bool isInitialization() const; + void setIsInitialization(bool isInitialization); + + // Get/set whether this edge will be instrumented with a path counter + // increment. Notice this is incrementing the path counter + // corresponding to the path number register. The path number + // increment is determined by getIncrement(). + bool isCounterIncrement() const; + void setIsCounterIncrement(bool isCounterIncrement); + + // Get/set the path number increment that this edge will be instrumented + // with. This is distinct from the path counter increment and the + // weight. The counter increment counts the number of executions of + // some path, whereas the path number keeps track of which path number + // the program is on. + long getIncrement() const; + void setIncrement(long increment); + + // Get/set whether the edge has been instrumented. + bool hasInstrumentation(); + void setHasInstrumentation(bool hasInstrumentation); + + // Returns the successor number of this edge in the source. + unsigned getSuccessorNumber(); + +private: + // The increment that the code will be instrumented with. + long long _increment; + + // Whether this edge is in the spanning tree. + bool _isInSpanningTree; + + // Whether this edge is an initialiation of the path number. + bool _isInitialization; + + // Whether this edge is a path counter increment. + bool _isCounterIncrement; + + // Whether this edge has been instrumented. + bool _hasInstrumentation; +}; + +// --------------------------------------------------------------------------- +// BLInstrumentationDag extends BallLarusDag with algorithms that +// determine where instrumentation should be placed. +// --------------------------------------------------------------------------- +class BLInstrumentationDag : public BallLarusDag { +public: + BLInstrumentationDag(Function &F); + + // Returns the Exit->Root edge. This edge is required for creating + // directed cycles in the algorithm for moving instrumentation off of + // the spanning tree + BallLarusEdge* getExitRootEdge(); + + // Returns an array of phony edges which mark those nodes + // with function calls + BLEdgeVector getCallPhonyEdges(); + + // Gets/sets the path counter array + GlobalVariable* getCounterArray(); + void setCounterArray(GlobalVariable* c); + + // Calculates the increments for the chords, thereby removing + // instrumentation from the spanning tree edges. Implementation is based + // on the algorithm in Figure 4 of [Ball94] + void calculateChordIncrements(); + + // Updates the state when an edge has been split + void splitUpdate(BLInstrumentationEdge* formerEdge, BasicBlock* newBlock); + + // Calculates a spanning tree of the DAG ignoring cycles. Whichever + // edges are in the spanning tree will not be instrumented, but this + // implementation does not try to minimize the instrumentation overhead + // by trying to find hot edges. + void calculateSpanningTree(); + + // Pushes initialization further down in order to group the first + // increment and initialization. + void pushInitialization(); + + // Pushes the path counter increments up in order to group the last path + // number increment. + void pushCounters(); + + // Removes phony edges from the successor list of the source, and the + // predecessor list of the target. + void unlinkPhony(); + + // Generate dot graph for the function + void generateDotGraph(); + +protected: + // BLInstrumentationDag creates BLInstrumentationNode objects in this + // method overriding the creation of BallLarusNode objects. + // + // Allows subclasses to determine which type of Node is created. + // Override this method to produce subclasses of BallLarusNode if + // necessary. + virtual BallLarusNode* createNode(BasicBlock* BB); + + // BLInstrumentationDag create BLInstrumentationEdges. + // + // Allows subclasses to determine which type of Edge is created. + // Override this method to produce subclasses of BallLarusEdge if + // necessary. Parameters source and target will have been created by + // createNode and can be cast to the subclass of BallLarusNode* + // returned by createNode. + virtual BallLarusEdge* createEdge( + BallLarusNode* source, BallLarusNode* target, unsigned edgeNumber); + +private: + BLEdgeVector _treeEdges; // All edges in the spanning tree. + BLEdgeVector _chordEdges; // All edges not in the spanning tree. + GlobalVariable* _counterArray; // Array to store path counters + + // Removes the edge from the appropriate predecessor and successor lists. + void unlinkEdge(BallLarusEdge* edge); + + // Makes an edge part of the spanning tree. + void makeEdgeSpanning(BLInstrumentationEdge* edge); + + // Pushes initialization and calls itself recursively. + void pushInitializationFromEdge(BLInstrumentationEdge* edge); + + // Pushes path counter increments up recursively. + void pushCountersFromEdge(BLInstrumentationEdge* edge); + + // Depth first algorithm for determining the chord increments.f + void calculateChordIncrementsDfs( + long weight, BallLarusNode* v, BallLarusEdge* e); + + // Determines the relative direction of two edges. + int calculateChordIncrementsDir(BallLarusEdge* e, BallLarusEdge* f); +}; + +// --------------------------------------------------------------------------- +// PathProfiler is a module pass which instruments path profiling instructions +// --------------------------------------------------------------------------- +class PathProfiler : public ModulePass { +private: + // Current context for multi threading support. + LLVMContext* Context; + + // Which function are we currently instrumenting + unsigned currentFunctionNumber; + + // The function prototype in the profiling runtime for incrementing a + // single path counter in a hash table. + Constant* llvmIncrementHashFunction; + Constant* llvmDecrementHashFunction; + + // Instruments each function with path profiling. 'main' is instrumented + // with code to save the profile to disk. + bool runOnModule(Module &M); + + // Analyzes the function for Ball-Larus path profiling, and inserts code. + void runOnFunction(std::vector<Constant*> &ftInit, Function &F, Module &M); + + // Creates an increment constant representing incr. + ConstantInt* createIncrementConstant(long incr, int bitsize); + + // Creates an increment constant representing the value in + // edge->getIncrement(). + ConstantInt* createIncrementConstant(BLInstrumentationEdge* edge); + + // Finds the insertion point after pathNumber in block. PathNumber may + // be NULL. + BasicBlock::iterator getInsertionPoint( + BasicBlock* block, Value* pathNumber); + + // Inserts source's pathNumber Value* into target. Target may or may not + // have multiple predecessors, and may or may not have its phiNode + // initalized. + void pushValueIntoNode( + BLInstrumentationNode* source, BLInstrumentationNode* target); + + // Inserts source's pathNumber Value* into the appropriate slot of + // target's phiNode. + void pushValueIntoPHI( + BLInstrumentationNode* target, BLInstrumentationNode* source); + + // The Value* in node, oldVal, is updated with a Value* correspodning to + // oldVal + addition. + void insertNumberIncrement(BLInstrumentationNode* node, Value* addition, + bool atBeginning); + + // Creates a counter increment in the given node. The Value* in node is + // taken as the index into a hash table. + void insertCounterIncrement( + Value* incValue, + BasicBlock::iterator insertPoint, + BLInstrumentationDag* dag, + bool increment = true); + + // A PHINode is created in the node, and its values initialized to -1U. + void preparePHI(BLInstrumentationNode* node); + + // Inserts instrumentation for the given edge + // + // Pre: The edge's source node has pathNumber set if edge is non zero + // path number increment. + // + // Post: Edge's target node has a pathNumber set to the path number Value + // corresponding to the value of the path register after edge's + // execution. + void insertInstrumentationStartingAt( + BLInstrumentationEdge* edge, + BLInstrumentationDag* dag); + + // If this edge is a critical edge, then inserts a node at this edge. + // This edge becomes the first edge, and a new BallLarusEdge is created. + bool splitCritical(BLInstrumentationEdge* edge, BLInstrumentationDag* dag); + + // Inserts instrumentation according to the marked edges in dag. Phony + // edges must be unlinked from the DAG, but accessible from the + // backedges. Dag must have initializations, path number increments, and + // counter increments present. + // + // Counter storage is created here. + void insertInstrumentation( BLInstrumentationDag& dag, Module &M); + +public: + static char ID; // Pass identification, replacement for typeid + PathProfiler() : ModulePass(ID) { + initializePathProfilerPass(*PassRegistry::getPassRegistry()); + } + + virtual const char *getPassName() const { + return "Path Profiler"; + } +}; +} // end anonymous namespace + +// Should we print the dot-graphs +static cl::opt<bool> DotPathDag("path-profile-pathdag", cl::Hidden, + cl::desc("Output the path profiling DAG for each function.")); + +// Register the path profiler as a pass +char PathProfiler::ID = 0; +INITIALIZE_PASS(PathProfiler, "insert-path-profiling", + "Insert instrumentation for Ball-Larus path profiling", + false, false) + +ModulePass *llvm::createPathProfilerPass() { return new PathProfiler(); } + +namespace llvm { + class PathProfilingFunctionTable {}; + + // Type for global array storing references to hashes or arrays + template<bool xcompile> class TypeBuilder<PathProfilingFunctionTable, + xcompile> { + public: + static StructType *get(LLVMContext& C) { + return( StructType::get( + TypeBuilder<types::i<32>, xcompile>::get(C), // type + TypeBuilder<types::i<32>, xcompile>::get(C), // array size + TypeBuilder<types::i<8>*, xcompile>::get(C), // array/hash ptr + NULL)); + } + }; + + typedef TypeBuilder<PathProfilingFunctionTable, true> + ftEntryTypeBuilder; + + // BallLarusEdge << operator overloading + raw_ostream& operator<<(raw_ostream& os, + const BLInstrumentationEdge& edge) + LLVM_ATTRIBUTE_USED; + raw_ostream& operator<<(raw_ostream& os, + const BLInstrumentationEdge& edge) { + os << "[" << edge.getSource()->getName() << " -> " + << edge.getTarget()->getName() << "] init: " + << (edge.isInitialization() ? "yes" : "no") + << " incr:" << edge.getIncrement() << " cinc: " + << (edge.isCounterIncrement() ? "yes" : "no"); + return(os); + } +} + +// Creates a new BLInstrumentationNode from a BasicBlock. +BLInstrumentationNode::BLInstrumentationNode(BasicBlock* BB) : + BallLarusNode(BB), + _startingPathNumber(NULL), _endingPathNumber(NULL), _pathPHI(NULL) {} + +// Constructor for BLInstrumentationEdge. +BLInstrumentationEdge::BLInstrumentationEdge(BLInstrumentationNode* source, + BLInstrumentationNode* target) + : BallLarusEdge(source, target, 0), + _increment(0), _isInSpanningTree(false), _isInitialization(false), + _isCounterIncrement(false), _hasInstrumentation(false) {} + +// Sets the target node of this edge. Required to split edges. +void BLInstrumentationEdge::setTarget(BallLarusNode* node) { + _target = node; +} + +// Returns whether this edge is in the spanning tree. +bool BLInstrumentationEdge::isInSpanningTree() const { + return(_isInSpanningTree); +} + +// Sets whether this edge is in the spanning tree. +void BLInstrumentationEdge::setIsInSpanningTree(bool isInSpanningTree) { + _isInSpanningTree = isInSpanningTree; +} + +// Returns whether this edge will be instrumented with a path number +// initialization. +bool BLInstrumentationEdge::isInitialization() const { + return(_isInitialization); +} + +// Sets whether this edge will be instrumented with a path number +// initialization. +void BLInstrumentationEdge::setIsInitialization(bool isInitialization) { + _isInitialization = isInitialization; +} + +// Returns whether this edge will be instrumented with a path counter +// increment. Notice this is incrementing the path counter +// corresponding to the path number register. The path number +// increment is determined by getIncrement(). +bool BLInstrumentationEdge::isCounterIncrement() const { + return(_isCounterIncrement); +} + +// Sets whether this edge will be instrumented with a path counter +// increment. +void BLInstrumentationEdge::setIsCounterIncrement(bool isCounterIncrement) { + _isCounterIncrement = isCounterIncrement; +} + +// Gets the path number increment that this edge will be instrumented +// with. This is distinct from the path counter increment and the +// weight. The counter increment is counts the number of executions of +// some path, whereas the path number keeps track of which path number +// the program is on. +long BLInstrumentationEdge::getIncrement() const { + return(_increment); +} + +// Set whether this edge will be instrumented with a path number +// increment. +void BLInstrumentationEdge::setIncrement(long increment) { + _increment = increment; +} + +// True iff the edge has already been instrumented. +bool BLInstrumentationEdge::hasInstrumentation() { + return(_hasInstrumentation); +} + +// Set whether this edge has been instrumented. +void BLInstrumentationEdge::setHasInstrumentation(bool hasInstrumentation) { + _hasInstrumentation = hasInstrumentation; +} + +// Returns the successor number of this edge in the source. +unsigned BLInstrumentationEdge::getSuccessorNumber() { + BallLarusNode* sourceNode = getSource(); + BallLarusNode* targetNode = getTarget(); + BasicBlock* source = sourceNode->getBlock(); + BasicBlock* target = targetNode->getBlock(); + + if(source == NULL || target == NULL) + return(0); + + TerminatorInst* terminator = source->getTerminator(); + + unsigned i; + for(i=0; i < terminator->getNumSuccessors(); i++) { + if(terminator->getSuccessor(i) == target) + break; + } + + return(i); +} + +// BLInstrumentationDag constructor initializes a DAG for the given Function. +BLInstrumentationDag::BLInstrumentationDag(Function &F) : BallLarusDag(F), + _counterArray(0) { +} + +// Returns the Exit->Root edge. This edge is required for creating +// directed cycles in the algorithm for moving instrumentation off of +// the spanning tree +BallLarusEdge* BLInstrumentationDag::getExitRootEdge() { + BLEdgeIterator erEdge = getExit()->succBegin(); + return(*erEdge); +} + +BLEdgeVector BLInstrumentationDag::getCallPhonyEdges () { + BLEdgeVector callEdges; + + for( BLEdgeIterator edge = _edges.begin(), end = _edges.end(); + edge != end; edge++ ) { + if( (*edge)->getType() == BallLarusEdge::CALLEDGE_PHONY ) + callEdges.push_back(*edge); + } + + return callEdges; +} + +// Gets the path counter array +GlobalVariable* BLInstrumentationDag::getCounterArray() { + return _counterArray; +} + +void BLInstrumentationDag::setCounterArray(GlobalVariable* c) { + _counterArray = c; +} + +// Calculates the increment for the chords, thereby removing +// instrumentation from the spanning tree edges. Implementation is based on +// the algorithm in Figure 4 of [Ball94] +void BLInstrumentationDag::calculateChordIncrements() { + calculateChordIncrementsDfs(0, getRoot(), NULL); + + BLInstrumentationEdge* chord; + for(BLEdgeIterator chordEdge = _chordEdges.begin(), + end = _chordEdges.end(); chordEdge != end; chordEdge++) { + chord = (BLInstrumentationEdge*) *chordEdge; + chord->setIncrement(chord->getIncrement() + chord->getWeight()); + } +} + +// Updates the state when an edge has been split +void BLInstrumentationDag::splitUpdate(BLInstrumentationEdge* formerEdge, + BasicBlock* newBlock) { + BallLarusNode* oldTarget = formerEdge->getTarget(); + BallLarusNode* newNode = addNode(newBlock); + formerEdge->setTarget(newNode); + newNode->addPredEdge(formerEdge); + + DEBUG(dbgs() << " Edge split: " << *formerEdge << "\n"); + + oldTarget->removePredEdge(formerEdge); + BallLarusEdge* newEdge = addEdge(newNode, oldTarget,0); + + if( formerEdge->getType() == BallLarusEdge::BACKEDGE || + formerEdge->getType() == BallLarusEdge::SPLITEDGE) { + newEdge->setType(formerEdge->getType()); + newEdge->setPhonyRoot(formerEdge->getPhonyRoot()); + newEdge->setPhonyExit(formerEdge->getPhonyExit()); + formerEdge->setType(BallLarusEdge::NORMAL); + formerEdge->setPhonyRoot(NULL); + formerEdge->setPhonyExit(NULL); + } +} + +// Calculates a spanning tree of the DAG ignoring cycles. Whichever +// edges are in the spanning tree will not be instrumented, but this +// implementation does not try to minimize the instrumentation overhead +// by trying to find hot edges. +void BLInstrumentationDag::calculateSpanningTree() { + std::stack<BallLarusNode*> dfsStack; + + for(BLNodeIterator nodeIt = _nodes.begin(), end = _nodes.end(); + nodeIt != end; nodeIt++) { + (*nodeIt)->setColor(BallLarusNode::WHITE); + } + + dfsStack.push(getRoot()); + while(dfsStack.size() > 0) { + BallLarusNode* node = dfsStack.top(); + dfsStack.pop(); + + if(node->getColor() == BallLarusNode::WHITE) + continue; + + BallLarusNode* nextNode; + bool forward = true; + BLEdgeIterator succEnd = node->succEnd(); + + node->setColor(BallLarusNode::WHITE); + // first iterate over successors then predecessors + for(BLEdgeIterator edge = node->succBegin(), predEnd = node->predEnd(); + edge != predEnd; edge++) { + if(edge == succEnd) { + edge = node->predBegin(); + forward = false; + } + + // Ignore split edges + if ((*edge)->getType() == BallLarusEdge::SPLITEDGE) + continue; + + nextNode = forward? (*edge)->getTarget(): (*edge)->getSource(); + if(nextNode->getColor() != BallLarusNode::WHITE) { + nextNode->setColor(BallLarusNode::WHITE); + makeEdgeSpanning((BLInstrumentationEdge*)(*edge)); + } + } + } + + for(BLEdgeIterator edge = _edges.begin(), end = _edges.end(); + edge != end; edge++) { + BLInstrumentationEdge* instEdge = (BLInstrumentationEdge*) (*edge); + // safe since createEdge is overriden + if(!instEdge->isInSpanningTree() && (*edge)->getType() + != BallLarusEdge::SPLITEDGE) + _chordEdges.push_back(instEdge); + } +} + +// Pushes initialization further down in order to group the first +// increment and initialization. +void BLInstrumentationDag::pushInitialization() { + BLInstrumentationEdge* exitRootEdge = + (BLInstrumentationEdge*) getExitRootEdge(); + exitRootEdge->setIsInitialization(true); + pushInitializationFromEdge(exitRootEdge); +} + +// Pushes the path counter increments up in order to group the last path +// number increment. +void BLInstrumentationDag::pushCounters() { + BLInstrumentationEdge* exitRootEdge = + (BLInstrumentationEdge*) getExitRootEdge(); + exitRootEdge->setIsCounterIncrement(true); + pushCountersFromEdge(exitRootEdge); +} + +// Removes phony edges from the successor list of the source, and the +// predecessor list of the target. +void BLInstrumentationDag::unlinkPhony() { + BallLarusEdge* edge; + + for(BLEdgeIterator next = _edges.begin(), + end = _edges.end(); next != end; next++) { + edge = (*next); + + if( edge->getType() == BallLarusEdge::BACKEDGE_PHONY || + edge->getType() == BallLarusEdge::SPLITEDGE_PHONY || + edge->getType() == BallLarusEdge::CALLEDGE_PHONY ) { + unlinkEdge(edge); + } + } +} + +// Generate a .dot graph to represent the DAG and pathNumbers +void BLInstrumentationDag::generateDotGraph() { + std::string errorInfo; + std::string functionName = getFunction().getName().str(); + std::string filename = "pathdag." + functionName + ".dot"; + + DEBUG (dbgs() << "Writing '" << filename << "'...\n"); + raw_fd_ostream dotFile(filename.c_str(), errorInfo); + + if (!errorInfo.empty()) { + errs() << "Error opening '" << filename.c_str() <<"' for writing!"; + errs() << "\n"; + return; + } + + dotFile << "digraph " << functionName << " {\n"; + + for( BLEdgeIterator edge = _edges.begin(), end = _edges.end(); + edge != end; edge++) { + std::string sourceName = (*edge)->getSource()->getName(); + std::string targetName = (*edge)->getTarget()->getName(); + + dotFile << "\t\"" << sourceName.c_str() << "\" -> \"" + << targetName.c_str() << "\" "; + + long inc = ((BLInstrumentationEdge*)(*edge))->getIncrement(); + + switch( (*edge)->getType() ) { + case BallLarusEdge::NORMAL: + dotFile << "[label=" << inc << "] [color=black];\n"; + break; + + case BallLarusEdge::BACKEDGE: + dotFile << "[color=cyan];\n"; + break; + + case BallLarusEdge::BACKEDGE_PHONY: + dotFile << "[label=" << inc + << "] [color=blue];\n"; + break; + + case BallLarusEdge::SPLITEDGE: + dotFile << "[color=violet];\n"; + break; + + case BallLarusEdge::SPLITEDGE_PHONY: + dotFile << "[label=" << inc << "] [color=red];\n"; + break; + + case BallLarusEdge::CALLEDGE_PHONY: + dotFile << "[label=" << inc << "] [color=green];\n"; + break; + } + } + + dotFile << "}\n"; +} + +// Allows subclasses to determine which type of Node is created. +// Override this method to produce subclasses of BallLarusNode if +// necessary. The destructor of BallLarusDag will call free on each pointer +// created. +BallLarusNode* BLInstrumentationDag::createNode(BasicBlock* BB) { + return( new BLInstrumentationNode(BB) ); +} + +// Allows subclasses to determine which type of Edge is created. +// Override this method to produce subclasses of BallLarusEdge if +// necessary. The destructor of BallLarusDag will call free on each pointer +// created. +BallLarusEdge* BLInstrumentationDag::createEdge(BallLarusNode* source, + BallLarusNode* target, unsigned edgeNumber) { + // One can cast from BallLarusNode to BLInstrumentationNode since createNode + // is overriden to produce BLInstrumentationNode. + return( new BLInstrumentationEdge((BLInstrumentationNode*)source, + (BLInstrumentationNode*)target) ); +} + +// Sets the Value corresponding to the pathNumber register, constant, +// or phinode. Used by the instrumentation code to remember path +// number Values. +Value* BLInstrumentationNode::getStartingPathNumber(){ + return(_startingPathNumber); +} + +// Sets the Value of the pathNumber. Used by the instrumentation code. +void BLInstrumentationNode::setStartingPathNumber(Value* pathNumber) { + DEBUG(dbgs() << " SPN-" << getName() << " <-- " << (pathNumber ? + pathNumber->getName() : + "unused") << "\n"); + _startingPathNumber = pathNumber; +} + +Value* BLInstrumentationNode::getEndingPathNumber(){ + return(_endingPathNumber); +} + +void BLInstrumentationNode::setEndingPathNumber(Value* pathNumber) { + DEBUG(dbgs() << " EPN-" << getName() << " <-- " + << (pathNumber ? pathNumber->getName() : "unused") << "\n"); + _endingPathNumber = pathNumber; +} + +// Get the PHINode Instruction for this node. Used by instrumentation +// code. +PHINode* BLInstrumentationNode::getPathPHI() { + return(_pathPHI); +} + +// Set the PHINode Instruction for this node. Used by instrumentation +// code. +void BLInstrumentationNode::setPathPHI(PHINode* pathPHI) { + _pathPHI = pathPHI; +} + +// Removes the edge from the appropriate predecessor and successor +// lists. +void BLInstrumentationDag::unlinkEdge(BallLarusEdge* edge) { + if(edge == getExitRootEdge()) + DEBUG(dbgs() << " Removing exit->root edge\n"); + + edge->getSource()->removeSuccEdge(edge); + edge->getTarget()->removePredEdge(edge); +} + +// Makes an edge part of the spanning tree. +void BLInstrumentationDag::makeEdgeSpanning(BLInstrumentationEdge* edge) { + edge->setIsInSpanningTree(true); + _treeEdges.push_back(edge); +} + +// Pushes initialization and calls itself recursively. +void BLInstrumentationDag::pushInitializationFromEdge( + BLInstrumentationEdge* edge) { + BallLarusNode* target; + + target = edge->getTarget(); + if( target->getNumberPredEdges() > 1 || target == getExit() ) { + return; + } else { + for(BLEdgeIterator next = target->succBegin(), + end = target->succEnd(); next != end; next++) { + BLInstrumentationEdge* intoEdge = (BLInstrumentationEdge*) *next; + + // Skip split edges + if (intoEdge->getType() == BallLarusEdge::SPLITEDGE) + continue; + + intoEdge->setIncrement(intoEdge->getIncrement() + + edge->getIncrement()); + intoEdge->setIsInitialization(true); + pushInitializationFromEdge(intoEdge); + } + + edge->setIncrement(0); + edge->setIsInitialization(false); + } +} + +// Pushes path counter increments up recursively. +void BLInstrumentationDag::pushCountersFromEdge(BLInstrumentationEdge* edge) { + BallLarusNode* source; + + source = edge->getSource(); + if(source->getNumberSuccEdges() > 1 || source == getRoot() + || edge->isInitialization()) { + return; + } else { + for(BLEdgeIterator previous = source->predBegin(), + end = source->predEnd(); previous != end; previous++) { + BLInstrumentationEdge* fromEdge = (BLInstrumentationEdge*) *previous; + + // Skip split edges + if (fromEdge->getType() == BallLarusEdge::SPLITEDGE) + continue; + + fromEdge->setIncrement(fromEdge->getIncrement() + + edge->getIncrement()); + fromEdge->setIsCounterIncrement(true); + pushCountersFromEdge(fromEdge); + } + + edge->setIncrement(0); + edge->setIsCounterIncrement(false); + } +} + +// Depth first algorithm for determining the chord increments. +void BLInstrumentationDag::calculateChordIncrementsDfs(long weight, + BallLarusNode* v, BallLarusEdge* e) { + BLInstrumentationEdge* f; + + for(BLEdgeIterator treeEdge = _treeEdges.begin(), + end = _treeEdges.end(); treeEdge != end; treeEdge++) { + f = (BLInstrumentationEdge*) *treeEdge; + if(e != f && v == f->getTarget()) { + calculateChordIncrementsDfs( + calculateChordIncrementsDir(e,f)*(weight) + + f->getWeight(), f->getSource(), f); + } + if(e != f && v == f->getSource()) { + calculateChordIncrementsDfs( + calculateChordIncrementsDir(e,f)*(weight) + + f->getWeight(), f->getTarget(), f); + } + } + + for(BLEdgeIterator chordEdge = _chordEdges.begin(), + end = _chordEdges.end(); chordEdge != end; chordEdge++) { + f = (BLInstrumentationEdge*) *chordEdge; + if(v == f->getSource() || v == f->getTarget()) { + f->setIncrement(f->getIncrement() + + calculateChordIncrementsDir(e,f)*weight); + } + } +} + +// Determines the relative direction of two edges. +int BLInstrumentationDag::calculateChordIncrementsDir(BallLarusEdge* e, + BallLarusEdge* f) { + if( e == NULL) + return(1); + else if(e->getSource() == f->getTarget() + || e->getTarget() == f->getSource()) + return(1); + + return(-1); +} + +// Creates an increment constant representing incr. +ConstantInt* PathProfiler::createIncrementConstant(long incr, + int bitsize) { + return(ConstantInt::get(IntegerType::get(*Context, 32), incr)); +} + +// Creates an increment constant representing the value in +// edge->getIncrement(). +ConstantInt* PathProfiler::createIncrementConstant( + BLInstrumentationEdge* edge) { + return(createIncrementConstant(edge->getIncrement(), 32)); +} + +// Finds the insertion point after pathNumber in block. PathNumber may +// be NULL. +BasicBlock::iterator PathProfiler::getInsertionPoint(BasicBlock* block, Value* + pathNumber) { + if(pathNumber == NULL || isa<ConstantInt>(pathNumber) + || (((Instruction*)(pathNumber))->getParent()) != block) { + return(block->getFirstInsertionPt()); + } else { + Instruction* pathNumberInst = (Instruction*) (pathNumber); + BasicBlock::iterator insertPoint; + BasicBlock::iterator end = block->end(); + + for(insertPoint = block->begin(); + insertPoint != end; insertPoint++) { + Instruction* insertInst = &(*insertPoint); + + if(insertInst == pathNumberInst) + return(++insertPoint); + } + + return(insertPoint); + } +} + +// A PHINode is created in the node, and its values initialized to -1U. +void PathProfiler::preparePHI(BLInstrumentationNode* node) { + BasicBlock* block = node->getBlock(); + BasicBlock::iterator insertPoint = block->getFirstInsertionPt(); + pred_iterator PB = pred_begin(node->getBlock()), + PE = pred_end(node->getBlock()); + PHINode* phi = PHINode::Create(Type::getInt32Ty(*Context), + std::distance(PB, PE), "pathNumber", + insertPoint ); + node->setPathPHI(phi); + node->setStartingPathNumber(phi); + node->setEndingPathNumber(phi); + + for(pred_iterator predIt = PB; predIt != PE; predIt++) { + BasicBlock* pred = (*predIt); + + if(pred != NULL) + phi->addIncoming(createIncrementConstant((long)-1, 32), pred); + } +} + +// Inserts source's pathNumber Value* into target. Target may or may not +// have multiple predecessors, and may or may not have its phiNode +// initalized. +void PathProfiler::pushValueIntoNode(BLInstrumentationNode* source, + BLInstrumentationNode* target) { + if(target->getBlock() == NULL) + return; + + + if(target->getNumberPredEdges() <= 1) { + assert(target->getStartingPathNumber() == NULL && + "Target already has path number"); + target->setStartingPathNumber(source->getEndingPathNumber()); + target->setEndingPathNumber(source->getEndingPathNumber()); + DEBUG(dbgs() << " Passing path number" + << (source->getEndingPathNumber() ? "" : " (null)") + << " value through.\n"); + } else { + if(target->getPathPHI() == NULL) { + DEBUG(dbgs() << " Initializing PHI node for block '" + << target->getName() << "'\n"); + preparePHI(target); + } + pushValueIntoPHI(target, source); + DEBUG(dbgs() << " Passing number value into PHI for block '" + << target->getName() << "'\n"); + } +} + +// Inserts source's pathNumber Value* into the appropriate slot of +// target's phiNode. +void PathProfiler::pushValueIntoPHI(BLInstrumentationNode* target, + BLInstrumentationNode* source) { + PHINode* phi = target->getPathPHI(); + assert(phi != NULL && " Tried to push value into node with PHI, but node" + " actually had no PHI."); + phi->removeIncomingValue(source->getBlock(), false); + phi->addIncoming(source->getEndingPathNumber(), source->getBlock()); +} + +// The Value* in node, oldVal, is updated with a Value* correspodning to +// oldVal + addition. +void PathProfiler::insertNumberIncrement(BLInstrumentationNode* node, + Value* addition, bool atBeginning) { + BasicBlock* block = node->getBlock(); + assert(node->getStartingPathNumber() != NULL); + assert(node->getEndingPathNumber() != NULL); + + BasicBlock::iterator insertPoint; + + if( atBeginning ) + insertPoint = block->getFirstInsertionPt(); + else + insertPoint = block->getTerminator(); + + DEBUG(errs() << " Creating addition instruction.\n"); + Value* newpn = BinaryOperator::Create(Instruction::Add, + node->getStartingPathNumber(), + addition, "pathNumber", insertPoint); + + node->setEndingPathNumber(newpn); + + if( atBeginning ) + node->setStartingPathNumber(newpn); +} + +// Creates a counter increment in the given node. The Value* in node is +// taken as the index into an array or hash table. The hash table access +// is a call to the runtime. +void PathProfiler::insertCounterIncrement(Value* incValue, + BasicBlock::iterator insertPoint, + BLInstrumentationDag* dag, + bool increment) { + // Counter increment for array + if( dag->getNumberOfPaths() <= HASH_THRESHHOLD ) { + // Get pointer to the array location + std::vector<Value*> gepIndices(2); + gepIndices[0] = Constant::getNullValue(Type::getInt32Ty(*Context)); + gepIndices[1] = incValue; + + GetElementPtrInst* pcPointer = + GetElementPtrInst::Create(dag->getCounterArray(), gepIndices, + "counterInc", insertPoint); + + // Load from the array - call it oldPC + LoadInst* oldPc = new LoadInst(pcPointer, "oldPC", insertPoint); + + // Test to see whether adding 1 will overflow the counter + ICmpInst* isMax = new ICmpInst(insertPoint, CmpInst::ICMP_ULT, oldPc, + createIncrementConstant(0xffffffff, 32), + "isMax"); + + // Select increment for the path counter based on overflow + SelectInst* inc = + SelectInst::Create( isMax, createIncrementConstant(increment?1:-1,32), + createIncrementConstant(0,32), + "pathInc", insertPoint); + + // newPc = oldPc + inc + BinaryOperator* newPc = BinaryOperator::Create(Instruction::Add, + oldPc, inc, "newPC", + insertPoint); + + // Store back in to the array + new StoreInst(newPc, pcPointer, insertPoint); + } else { // Counter increment for hash + std::vector<Value*> args(2); + args[0] = ConstantInt::get(Type::getInt32Ty(*Context), + currentFunctionNumber); + args[1] = incValue; + + CallInst::Create( + increment ? llvmIncrementHashFunction : llvmDecrementHashFunction, + args, "", insertPoint); + } +} + +// Inserts instrumentation for the given edge +// +// Pre: The edge's source node has pathNumber set if edge is non zero +// path number increment. +// +// Post: Edge's target node has a pathNumber set to the path number Value +// corresponding to the value of the path register after edge's +// execution. +// +// FIXME: This should be reworked so it's not recursive. +void PathProfiler::insertInstrumentationStartingAt(BLInstrumentationEdge* edge, + BLInstrumentationDag* dag) { + // Mark the edge as instrumented + edge->setHasInstrumentation(true); + DEBUG(dbgs() << "\nInstrumenting edge: " << (*edge) << "\n"); + + // create a new node for this edge's instrumentation + splitCritical(edge, dag); + + BLInstrumentationNode* sourceNode = (BLInstrumentationNode*)edge->getSource(); + BLInstrumentationNode* targetNode = (BLInstrumentationNode*)edge->getTarget(); + BLInstrumentationNode* instrumentNode; + BLInstrumentationNode* nextSourceNode; + + bool atBeginning = false; + + // Source node has only 1 successor so any information can be simply + // inserted in to it without splitting + if( sourceNode->getBlock() && sourceNode->getNumberSuccEdges() <= 1) { + DEBUG(dbgs() << " Potential instructions to be placed in: " + << sourceNode->getName() << " (at end)\n"); + instrumentNode = sourceNode; + nextSourceNode = targetNode; // ... since we never made any new nodes + } + + // The target node only has one predecessor, so we can safely insert edge + // instrumentation into it. If there was splitting, it must have been + // successful. + else if( targetNode->getNumberPredEdges() == 1 ) { + DEBUG(dbgs() << " Potential instructions to be placed in: " + << targetNode->getName() << " (at beginning)\n"); + pushValueIntoNode(sourceNode, targetNode); + instrumentNode = targetNode; + nextSourceNode = NULL; // ... otherwise we'll just keep splitting + atBeginning = true; + } + + // Somehow, splitting must have failed. + else { + errs() << "Instrumenting could not split a critical edge.\n"; + DEBUG(dbgs() << " Couldn't split edge " << (*edge) << ".\n"); + return; + } + + // Insert instrumentation if this is a back or split edge + if( edge->getType() == BallLarusEdge::BACKEDGE || + edge->getType() == BallLarusEdge::SPLITEDGE ) { + BLInstrumentationEdge* top = + (BLInstrumentationEdge*) edge->getPhonyRoot(); + BLInstrumentationEdge* bottom = + (BLInstrumentationEdge*) edge->getPhonyExit(); + + assert( top->isInitialization() && " Top phony edge did not" + " contain a path number initialization."); + assert( bottom->isCounterIncrement() && " Bottom phony edge" + " did not contain a path counter increment."); + + // split edge has yet to be initialized + if( !instrumentNode->getEndingPathNumber() ) { + instrumentNode->setStartingPathNumber(createIncrementConstant(0,32)); + instrumentNode->setEndingPathNumber(createIncrementConstant(0,32)); + } + + BasicBlock::iterator insertPoint = atBeginning ? + instrumentNode->getBlock()->getFirstInsertionPt() : + instrumentNode->getBlock()->getTerminator(); + + // add information from the bottom edge, if it exists + if( bottom->getIncrement() ) { + Value* newpn = + BinaryOperator::Create(Instruction::Add, + instrumentNode->getStartingPathNumber(), + createIncrementConstant(bottom), + "pathNumber", insertPoint); + instrumentNode->setEndingPathNumber(newpn); + } + + insertCounterIncrement(instrumentNode->getEndingPathNumber(), + insertPoint, dag); + + if( atBeginning ) + instrumentNode->setStartingPathNumber(createIncrementConstant(top)); + + instrumentNode->setEndingPathNumber(createIncrementConstant(top)); + + // Check for path counter increments + if( top->isCounterIncrement() ) { + insertCounterIncrement(instrumentNode->getEndingPathNumber(), + instrumentNode->getBlock()->getTerminator(),dag); + instrumentNode->setEndingPathNumber(0); + } + } + + // Insert instrumentation if this is a normal edge + else { + BasicBlock::iterator insertPoint = atBeginning ? + instrumentNode->getBlock()->getFirstInsertionPt() : + instrumentNode->getBlock()->getTerminator(); + + if( edge->isInitialization() ) { // initialize path number + instrumentNode->setEndingPathNumber(createIncrementConstant(edge)); + } else if( edge->getIncrement() ) {// increment path number + Value* newpn = + BinaryOperator::Create(Instruction::Add, + instrumentNode->getStartingPathNumber(), + createIncrementConstant(edge), + "pathNumber", insertPoint); + instrumentNode->setEndingPathNumber(newpn); + + if( atBeginning ) + instrumentNode->setStartingPathNumber(newpn); + } + + // Check for path counter increments + if( edge->isCounterIncrement() ) { + insertCounterIncrement(instrumentNode->getEndingPathNumber(), + insertPoint, dag); + instrumentNode->setEndingPathNumber(0); + } + } + + // Push it along + if (nextSourceNode && instrumentNode->getEndingPathNumber()) + pushValueIntoNode(instrumentNode, nextSourceNode); + + // Add all the successors + for( BLEdgeIterator next = targetNode->succBegin(), + end = targetNode->succEnd(); next != end; next++ ) { + // So long as it is un-instrumented, add it to the list + if( !((BLInstrumentationEdge*)(*next))->hasInstrumentation() ) + insertInstrumentationStartingAt((BLInstrumentationEdge*)*next,dag); + else + DEBUG(dbgs() << " Edge " << *(BLInstrumentationEdge*)(*next) + << " already instrumented.\n"); + } +} + +// Inserts instrumentation according to the marked edges in dag. Phony edges +// must be unlinked from the DAG, but accessible from the backedges. Dag +// must have initializations, path number increments, and counter increments +// present. +// +// Counter storage is created here. +void PathProfiler::insertInstrumentation( + BLInstrumentationDag& dag, Module &M) { + + BLInstrumentationEdge* exitRootEdge = + (BLInstrumentationEdge*) dag.getExitRootEdge(); + insertInstrumentationStartingAt(exitRootEdge, &dag); + + // Iterate through each call edge and apply the appropriate hash increment + // and decrement functions + BLEdgeVector callEdges = dag.getCallPhonyEdges(); + for( BLEdgeIterator edge = callEdges.begin(), + end = callEdges.end(); edge != end; edge++ ) { + BLInstrumentationNode* node = + (BLInstrumentationNode*)(*edge)->getSource(); + BasicBlock::iterator insertPoint = node->getBlock()->getFirstInsertionPt(); + + // Find the first function call + while( ((Instruction&)(*insertPoint)).getOpcode() != Instruction::Call ) + insertPoint++; + + DEBUG(dbgs() << "\nInstrumenting method call block '" + << node->getBlock()->getName() << "'\n"); + DEBUG(dbgs() << " Path number initialized: " + << ((node->getStartingPathNumber()) ? "yes" : "no") << "\n"); + + Value* newpn; + if( node->getStartingPathNumber() ) { + long inc = ((BLInstrumentationEdge*)(*edge))->getIncrement(); + if ( inc ) + newpn = BinaryOperator::Create(Instruction::Add, + node->getStartingPathNumber(), + createIncrementConstant(inc,32), + "pathNumber", insertPoint); + else + newpn = node->getStartingPathNumber(); + } else { + newpn = (Value*)createIncrementConstant( + ((BLInstrumentationEdge*)(*edge))->getIncrement(), 32); + } + + insertCounterIncrement(newpn, insertPoint, &dag); + insertCounterIncrement(newpn, node->getBlock()->getTerminator(), + &dag, false); + } +} + +// Entry point of the module +void PathProfiler::runOnFunction(std::vector<Constant*> &ftInit, + Function &F, Module &M) { + // Build DAG from CFG + BLInstrumentationDag dag = BLInstrumentationDag(F); + dag.init(); + + // give each path a unique integer value + dag.calculatePathNumbers(); + + // modify path increments to increase the efficiency + // of instrumentation + dag.calculateSpanningTree(); + dag.calculateChordIncrements(); + dag.pushInitialization(); + dag.pushCounters(); + dag.unlinkPhony(); + + // potentially generate .dot graph for the dag + if (DotPathDag) + dag.generateDotGraph (); + + // Should we store the information in an array or hash + if( dag.getNumberOfPaths() <= HASH_THRESHHOLD ) { + Type* t = ArrayType::get(Type::getInt32Ty(*Context), + dag.getNumberOfPaths()); + + dag.setCounterArray(new GlobalVariable(M, t, false, + GlobalValue::InternalLinkage, + Constant::getNullValue(t), "")); + } + + insertInstrumentation(dag, M); + + // Add to global function reference table + unsigned type; + Type* voidPtr = TypeBuilder<types::i<8>*, true>::get(*Context); + + if( dag.getNumberOfPaths() <= HASH_THRESHHOLD ) + type = ProfilingArray; + else + type = ProfilingHash; + + std::vector<Constant*> entryArray(3); + entryArray[0] = createIncrementConstant(type,32); + entryArray[1] = createIncrementConstant(dag.getNumberOfPaths(),32); + entryArray[2] = dag.getCounterArray() ? + ConstantExpr::getBitCast(dag.getCounterArray(), voidPtr) : + Constant::getNullValue(voidPtr); + + StructType* at = ftEntryTypeBuilder::get(*Context); + ConstantStruct* functionEntry = + (ConstantStruct*)ConstantStruct::get(at, entryArray); + ftInit.push_back(functionEntry); +} + +// Output the bitcode if we want to observe instrumentation changess +#define PRINT_MODULE dbgs() << \ + "\n\n============= MODULE BEGIN ===============\n" << M << \ + "\n============== MODULE END ================\n" + +bool PathProfiler::runOnModule(Module &M) { + Context = &M.getContext(); + + DEBUG(dbgs() + << "****************************************\n" + << "****************************************\n" + << "** **\n" + << "** PATH PROFILING INSTRUMENTATION **\n" + << "** **\n" + << "****************************************\n" + << "****************************************\n"); + + // No main, no instrumentation! + Function *Main = M.getFunction("main"); + + // Using fortran? ... this kind of works + if (!Main) + Main = M.getFunction("MAIN__"); + + if (!Main) { + errs() << "WARNING: cannot insert path profiling into a module" + << " with no main function!\n"; + return false; + } + + llvmIncrementHashFunction = M.getOrInsertFunction( + "llvm_increment_path_count", + Type::getVoidTy(*Context), // return type + Type::getInt32Ty(*Context), // function number + Type::getInt32Ty(*Context), // path number + NULL ); + + llvmDecrementHashFunction = M.getOrInsertFunction( + "llvm_decrement_path_count", + Type::getVoidTy(*Context), // return type + Type::getInt32Ty(*Context), // function number + Type::getInt32Ty(*Context), // path number + NULL ); + + std::vector<Constant*> ftInit; + unsigned functionNumber = 0; + for (Module::iterator F = M.begin(), E = M.end(); F != E; F++) { + if (F->isDeclaration()) + continue; + + DEBUG(dbgs() << "Function: " << F->getName() << "\n"); + functionNumber++; + + // set function number + currentFunctionNumber = functionNumber; + runOnFunction(ftInit, *F, M); + } + + Type *t = ftEntryTypeBuilder::get(*Context); + ArrayType* ftArrayType = ArrayType::get(t, ftInit.size()); + Constant* ftInitConstant = ConstantArray::get(ftArrayType, ftInit); + + DEBUG(dbgs() << " ftArrayType:" << *ftArrayType << "\n"); + + GlobalVariable* functionTable = + new GlobalVariable(M, ftArrayType, false, GlobalValue::InternalLinkage, + ftInitConstant, "functionPathTable"); + Type *eltType = ftArrayType->getTypeAtIndex((unsigned)0); + InsertProfilingInitCall(Main, "llvm_start_path_profiling", functionTable, + PointerType::getUnqual(eltType)); + + DEBUG(PRINT_MODULE); + + return true; +} + +// If this edge is a critical edge, then inserts a node at this edge. +// This edge becomes the first edge, and a new BallLarusEdge is created. +// Returns true if the edge was split +bool PathProfiler::splitCritical(BLInstrumentationEdge* edge, + BLInstrumentationDag* dag) { + unsigned succNum = edge->getSuccessorNumber(); + BallLarusNode* sourceNode = edge->getSource(); + BallLarusNode* targetNode = edge->getTarget(); + BasicBlock* sourceBlock = sourceNode->getBlock(); + BasicBlock* targetBlock = targetNode->getBlock(); + + if(sourceBlock == NULL || targetBlock == NULL + || sourceNode->getNumberSuccEdges() <= 1 + || targetNode->getNumberPredEdges() == 1 ) { + return(false); + } + + TerminatorInst* terminator = sourceBlock->getTerminator(); + + if( SplitCriticalEdge(terminator, succNum, this, false)) { + BasicBlock* newBlock = terminator->getSuccessor(succNum); + dag->splitUpdate(edge, newBlock); + return(true); + } else + return(false); +} diff --git a/contrib/llvm/lib/Transforms/Instrumentation/ProfilingUtils.cpp b/contrib/llvm/lib/Transforms/Instrumentation/ProfilingUtils.cpp new file mode 100644 index 0000000..de57cd1 --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/ProfilingUtils.cpp @@ -0,0 +1,169 @@ +//===- ProfilingUtils.cpp - Helper functions shared by profilers ----------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements a few helper functions which are used by profile +// instrumentation code to instrument the code. This allows the profiler pass +// to worry about *what* to insert, and these functions take care of *how* to do +// it. +// +//===----------------------------------------------------------------------===// + +#include "ProfilingUtils.h" +#include "llvm/Constants.h" +#include "llvm/DerivedTypes.h" +#include "llvm/Instructions.h" +#include "llvm/LLVMContext.h" +#include "llvm/Module.h" + +void llvm::InsertProfilingInitCall(Function *MainFn, const char *FnName, + GlobalValue *Array, + PointerType *arrayType) { + LLVMContext &Context = MainFn->getContext(); + Type *ArgVTy = + PointerType::getUnqual(Type::getInt8PtrTy(Context)); + PointerType *UIntPtr = arrayType ? arrayType : + Type::getInt32PtrTy(Context); + Module &M = *MainFn->getParent(); + Constant *InitFn = M.getOrInsertFunction(FnName, Type::getInt32Ty(Context), + Type::getInt32Ty(Context), + ArgVTy, UIntPtr, + Type::getInt32Ty(Context), + (Type *)0); + + // This could force argc and argv into programs that wouldn't otherwise have + // them, but instead we just pass null values in. + std::vector<Value*> Args(4); + Args[0] = Constant::getNullValue(Type::getInt32Ty(Context)); + Args[1] = Constant::getNullValue(ArgVTy); + + // Skip over any allocas in the entry block. + BasicBlock *Entry = MainFn->begin(); + BasicBlock::iterator InsertPos = Entry->begin(); + while (isa<AllocaInst>(InsertPos)) ++InsertPos; + + std::vector<Constant*> GEPIndices(2, + Constant::getNullValue(Type::getInt32Ty(Context))); + unsigned NumElements = 0; + if (Array) { + Args[2] = ConstantExpr::getGetElementPtr(Array, GEPIndices); + NumElements = + cast<ArrayType>(Array->getType()->getElementType())->getNumElements(); + } else { + // If this profiling instrumentation doesn't have a constant array, just + // pass null. + Args[2] = ConstantPointerNull::get(UIntPtr); + } + Args[3] = ConstantInt::get(Type::getInt32Ty(Context), NumElements); + + CallInst *InitCall = CallInst::Create(InitFn, Args, "newargc", InsertPos); + + // If argc or argv are not available in main, just pass null values in. + Function::arg_iterator AI; + switch (MainFn->arg_size()) { + default: + case 2: + AI = MainFn->arg_begin(); ++AI; + if (AI->getType() != ArgVTy) { + Instruction::CastOps opcode = CastInst::getCastOpcode(AI, false, ArgVTy, + false); + InitCall->setArgOperand(1, + CastInst::Create(opcode, AI, ArgVTy, "argv.cast", InitCall)); + } else { + InitCall->setArgOperand(1, AI); + } + /* FALL THROUGH */ + + case 1: + AI = MainFn->arg_begin(); + // If the program looked at argc, have it look at the return value of the + // init call instead. + if (!AI->getType()->isIntegerTy(32)) { + Instruction::CastOps opcode; + if (!AI->use_empty()) { + opcode = CastInst::getCastOpcode(InitCall, true, AI->getType(), true); + AI->replaceAllUsesWith( + CastInst::Create(opcode, InitCall, AI->getType(), "", InsertPos)); + } + opcode = CastInst::getCastOpcode(AI, true, + Type::getInt32Ty(Context), true); + InitCall->setArgOperand(0, + CastInst::Create(opcode, AI, Type::getInt32Ty(Context), + "argc.cast", InitCall)); + } else { + AI->replaceAllUsesWith(InitCall); + InitCall->setArgOperand(0, AI); + } + + case 0: break; + } +} + +void llvm::IncrementCounterInBlock(BasicBlock *BB, unsigned CounterNum, + GlobalValue *CounterArray, bool beginning) { + // Insert the increment after any alloca or PHI instructions... + BasicBlock::iterator InsertPos = beginning ? BB->getFirstInsertionPt() : + BB->getTerminator(); + while (isa<AllocaInst>(InsertPos)) + ++InsertPos; + + LLVMContext &Context = BB->getContext(); + + // Create the getelementptr constant expression + std::vector<Constant*> Indices(2); + Indices[0] = Constant::getNullValue(Type::getInt32Ty(Context)); + Indices[1] = ConstantInt::get(Type::getInt32Ty(Context), CounterNum); + Constant *ElementPtr = + ConstantExpr::getGetElementPtr(CounterArray, Indices); + + // Load, increment and store the value back. + Value *OldVal = new LoadInst(ElementPtr, "OldFuncCounter", InsertPos); + Value *NewVal = BinaryOperator::Create(Instruction::Add, OldVal, + ConstantInt::get(Type::getInt32Ty(Context), 1), + "NewFuncCounter", InsertPos); + new StoreInst(NewVal, ElementPtr, InsertPos); +} + +void llvm::InsertProfilingShutdownCall(Function *Callee, Module *Mod) { + // llvm.global_dtors is an array of type { i32, void ()* }. Prepare those + // types. + Type *GlobalDtorElems[2] = { + Type::getInt32Ty(Mod->getContext()), + FunctionType::get(Type::getVoidTy(Mod->getContext()), false)->getPointerTo() + }; + StructType *GlobalDtorElemTy = + StructType::get(Mod->getContext(), GlobalDtorElems, false); + + // Construct the new element we'll be adding. + Constant *Elem[2] = { + ConstantInt::get(Type::getInt32Ty(Mod->getContext()), 65535), + ConstantExpr::getBitCast(Callee, GlobalDtorElems[1]) + }; + + // If llvm.global_dtors exists, make a copy of the things in its list and + // delete it, to replace it with one that has a larger array type. + std::vector<Constant *> dtors; + if (GlobalVariable *GlobalDtors = Mod->getNamedGlobal("llvm.global_dtors")) { + if (ConstantArray *InitList = + dyn_cast<ConstantArray>(GlobalDtors->getInitializer())) { + for (unsigned i = 0, e = InitList->getType()->getNumElements(); + i != e; ++i) + dtors.push_back(cast<Constant>(InitList->getOperand(i))); + } + GlobalDtors->eraseFromParent(); + } + + // Build up llvm.global_dtors with our new item in it. + GlobalVariable *GlobalDtors = new GlobalVariable( + *Mod, ArrayType::get(GlobalDtorElemTy, 1), false, + GlobalValue::AppendingLinkage, NULL, "llvm.global_dtors"); + + dtors.push_back(ConstantStruct::get(GlobalDtorElemTy, Elem)); + GlobalDtors->setInitializer(ConstantArray::get( + cast<ArrayType>(GlobalDtors->getType()->getElementType()), dtors)); +} diff --git a/contrib/llvm/lib/Transforms/Instrumentation/ProfilingUtils.h b/contrib/llvm/lib/Transforms/Instrumentation/ProfilingUtils.h new file mode 100644 index 0000000..09b2217 --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/ProfilingUtils.h @@ -0,0 +1,36 @@ +//===- ProfilingUtils.h - Helper functions shared by profilers --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines a few helper functions which are used by profile +// instrumentation code to instrument the code. This allows the profiler pass +// to worry about *what* to insert, and these functions take care of *how* to do +// it. +// +//===----------------------------------------------------------------------===// + +#ifndef PROFILINGUTILS_H +#define PROFILINGUTILS_H + +namespace llvm { + class BasicBlock; + class Function; + class GlobalValue; + class Module; + class PointerType; + + void InsertProfilingInitCall(Function *MainFn, const char *FnName, + GlobalValue *Arr = 0, + PointerType *arrayType = 0); + void IncrementCounterInBlock(BasicBlock *BB, unsigned CounterNum, + GlobalValue *CounterArray, + bool beginning = true); + void InsertProfilingShutdownCall(Function *Callee, Module *Mod); +} + +#endif diff --git a/contrib/llvm/lib/Transforms/Instrumentation/ThreadSanitizer.cpp b/contrib/llvm/lib/Transforms/Instrumentation/ThreadSanitizer.cpp new file mode 100644 index 0000000..dc0fa71 --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/ThreadSanitizer.cpp @@ -0,0 +1,412 @@ +//===-- ThreadSanitizer.cpp - race detector -------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file is a part of ThreadSanitizer, a race detector. +// +// The tool is under development, for the details about previous versions see +// http://code.google.com/p/data-race-test +// +// The instrumentation phase is quite simple: +// - Insert calls to run-time library before every memory access. +// - Optimizations may apply to avoid instrumenting some of the accesses. +// - Insert calls at function entry/exit. +// The rest is handled by the run-time library. +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "tsan" + +#include "FunctionBlackList.h" +#include "llvm/Function.h" +#include "llvm/IRBuilder.h" +#include "llvm/Intrinsics.h" +#include "llvm/LLVMContext.h" +#include "llvm/Metadata.h" +#include "llvm/Module.h" +#include "llvm/Type.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetData.h" +#include "llvm/Transforms/Instrumentation.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/ModuleUtils.h" + +using namespace llvm; + +static cl::opt<std::string> ClBlackListFile("tsan-blacklist", + cl::desc("Blacklist file"), cl::Hidden); + +STATISTIC(NumInstrumentedReads, "Number of instrumented reads"); +STATISTIC(NumInstrumentedWrites, "Number of instrumented writes"); +STATISTIC(NumOmittedReadsBeforeWrite, + "Number of reads ignored due to following writes"); +STATISTIC(NumAccessesWithBadSize, "Number of accesses with bad size"); +STATISTIC(NumInstrumentedVtableWrites, "Number of vtable ptr writes"); +STATISTIC(NumOmittedReadsFromConstantGlobals, + "Number of reads from constant globals"); +STATISTIC(NumOmittedReadsFromVtable, "Number of vtable reads"); + +namespace { + +/// ThreadSanitizer: instrument the code in module to find races. +struct ThreadSanitizer : public FunctionPass { + ThreadSanitizer(); + const char *getPassName() const; + bool runOnFunction(Function &F); + bool doInitialization(Module &M); + static char ID; // Pass identification, replacement for typeid. + + private: + bool instrumentLoadOrStore(Instruction *I); + bool instrumentAtomic(Instruction *I); + void chooseInstructionsToInstrument(SmallVectorImpl<Instruction*> &Local, + SmallVectorImpl<Instruction*> &All); + bool addrPointsToConstantData(Value *Addr); + int getMemoryAccessFuncIndex(Value *Addr); + + TargetData *TD; + OwningPtr<FunctionBlackList> BL; + IntegerType *OrdTy; + // Callbacks to run-time library are computed in doInitialization. + Function *TsanFuncEntry; + Function *TsanFuncExit; + // Accesses sizes are powers of two: 1, 2, 4, 8, 16. + static const size_t kNumberOfAccessSizes = 5; + Function *TsanRead[kNumberOfAccessSizes]; + Function *TsanWrite[kNumberOfAccessSizes]; + Function *TsanAtomicLoad[kNumberOfAccessSizes]; + Function *TsanAtomicStore[kNumberOfAccessSizes]; + Function *TsanVptrUpdate; +}; +} // namespace + +char ThreadSanitizer::ID = 0; +INITIALIZE_PASS(ThreadSanitizer, "tsan", + "ThreadSanitizer: detects data races.", + false, false) + +const char *ThreadSanitizer::getPassName() const { + return "ThreadSanitizer"; +} + +ThreadSanitizer::ThreadSanitizer() + : FunctionPass(ID), + TD(NULL) { +} + +FunctionPass *llvm::createThreadSanitizerPass() { + return new ThreadSanitizer(); +} + +static Function *checkInterfaceFunction(Constant *FuncOrBitcast) { + if (Function *F = dyn_cast<Function>(FuncOrBitcast)) + return F; + FuncOrBitcast->dump(); + report_fatal_error("ThreadSanitizer interface function redefined"); +} + +bool ThreadSanitizer::doInitialization(Module &M) { + TD = getAnalysisIfAvailable<TargetData>(); + if (!TD) + return false; + BL.reset(new FunctionBlackList(ClBlackListFile)); + + // Always insert a call to __tsan_init into the module's CTORs. + IRBuilder<> IRB(M.getContext()); + Value *TsanInit = M.getOrInsertFunction("__tsan_init", + IRB.getVoidTy(), NULL); + appendToGlobalCtors(M, cast<Function>(TsanInit), 0); + + // Initialize the callbacks. + TsanFuncEntry = checkInterfaceFunction(M.getOrInsertFunction( + "__tsan_func_entry", IRB.getVoidTy(), IRB.getInt8PtrTy(), NULL)); + TsanFuncExit = checkInterfaceFunction(M.getOrInsertFunction( + "__tsan_func_exit", IRB.getVoidTy(), NULL)); + OrdTy = IRB.getInt32Ty(); + for (size_t i = 0; i < kNumberOfAccessSizes; ++i) { + const size_t ByteSize = 1 << i; + const size_t BitSize = ByteSize * 8; + SmallString<32> ReadName("__tsan_read" + itostr(ByteSize)); + TsanRead[i] = checkInterfaceFunction(M.getOrInsertFunction( + ReadName, IRB.getVoidTy(), IRB.getInt8PtrTy(), NULL)); + + SmallString<32> WriteName("__tsan_write" + itostr(ByteSize)); + TsanWrite[i] = checkInterfaceFunction(M.getOrInsertFunction( + WriteName, IRB.getVoidTy(), IRB.getInt8PtrTy(), NULL)); + + Type *Ty = Type::getIntNTy(M.getContext(), BitSize); + Type *PtrTy = Ty->getPointerTo(); + SmallString<32> AtomicLoadName("__tsan_atomic" + itostr(BitSize) + + "_load"); + TsanAtomicLoad[i] = checkInterfaceFunction(M.getOrInsertFunction( + AtomicLoadName, Ty, PtrTy, OrdTy, NULL)); + + SmallString<32> AtomicStoreName("__tsan_atomic" + itostr(BitSize) + + "_store"); + TsanAtomicStore[i] = checkInterfaceFunction(M.getOrInsertFunction( + AtomicStoreName, IRB.getVoidTy(), PtrTy, Ty, OrdTy, + NULL)); + } + TsanVptrUpdate = checkInterfaceFunction(M.getOrInsertFunction( + "__tsan_vptr_update", IRB.getVoidTy(), IRB.getInt8PtrTy(), + IRB.getInt8PtrTy(), NULL)); + return true; +} + +static bool isVtableAccess(Instruction *I) { + if (MDNode *Tag = I->getMetadata(LLVMContext::MD_tbaa)) { + if (Tag->getNumOperands() < 1) return false; + if (MDString *Tag1 = dyn_cast<MDString>(Tag->getOperand(0))) { + if (Tag1->getString() == "vtable pointer") return true; + } + } + return false; +} + +bool ThreadSanitizer::addrPointsToConstantData(Value *Addr) { + // If this is a GEP, just analyze its pointer operand. + if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Addr)) + Addr = GEP->getPointerOperand(); + + if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) { + if (GV->isConstant()) { + // Reads from constant globals can not race with any writes. + NumOmittedReadsFromConstantGlobals++; + return true; + } + } else if(LoadInst *L = dyn_cast<LoadInst>(Addr)) { + if (isVtableAccess(L)) { + // Reads from a vtable pointer can not race with any writes. + NumOmittedReadsFromVtable++; + return true; + } + } + return false; +} + +// Instrumenting some of the accesses may be proven redundant. +// Currently handled: +// - read-before-write (within same BB, no calls between) +// +// We do not handle some of the patterns that should not survive +// after the classic compiler optimizations. +// E.g. two reads from the same temp should be eliminated by CSE, +// two writes should be eliminated by DSE, etc. +// +// 'Local' is a vector of insns within the same BB (no calls between). +// 'All' is a vector of insns that will be instrumented. +void ThreadSanitizer::chooseInstructionsToInstrument( + SmallVectorImpl<Instruction*> &Local, + SmallVectorImpl<Instruction*> &All) { + SmallSet<Value*, 8> WriteTargets; + // Iterate from the end. + for (SmallVectorImpl<Instruction*>::reverse_iterator It = Local.rbegin(), + E = Local.rend(); It != E; ++It) { + Instruction *I = *It; + if (StoreInst *Store = dyn_cast<StoreInst>(I)) { + WriteTargets.insert(Store->getPointerOperand()); + } else { + LoadInst *Load = cast<LoadInst>(I); + Value *Addr = Load->getPointerOperand(); + if (WriteTargets.count(Addr)) { + // We will write to this temp, so no reason to analyze the read. + NumOmittedReadsBeforeWrite++; + continue; + } + if (addrPointsToConstantData(Addr)) { + // Addr points to some constant data -- it can not race with any writes. + continue; + } + } + All.push_back(I); + } + Local.clear(); +} + +static bool isAtomic(Instruction *I) { + if (LoadInst *LI = dyn_cast<LoadInst>(I)) + return LI->isAtomic() && LI->getSynchScope() == CrossThread; + if (StoreInst *SI = dyn_cast<StoreInst>(I)) + return SI->isAtomic() && SI->getSynchScope() == CrossThread; + if (isa<AtomicRMWInst>(I)) + return true; + if (isa<AtomicCmpXchgInst>(I)) + return true; + if (FenceInst *FI = dyn_cast<FenceInst>(I)) + return FI->getSynchScope() == CrossThread; + return false; +} + +bool ThreadSanitizer::runOnFunction(Function &F) { + if (!TD) return false; + if (BL->isIn(F)) return false; + SmallVector<Instruction*, 8> RetVec; + SmallVector<Instruction*, 8> AllLoadsAndStores; + SmallVector<Instruction*, 8> LocalLoadsAndStores; + SmallVector<Instruction*, 8> AtomicAccesses; + bool Res = false; + bool HasCalls = false; + + // Traverse all instructions, collect loads/stores/returns, check for calls. + for (Function::iterator FI = F.begin(), FE = F.end(); + FI != FE; ++FI) { + BasicBlock &BB = *FI; + for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); + BI != BE; ++BI) { + if (isAtomic(BI)) + AtomicAccesses.push_back(BI); + else if (isa<LoadInst>(BI) || isa<StoreInst>(BI)) + LocalLoadsAndStores.push_back(BI); + else if (isa<ReturnInst>(BI)) + RetVec.push_back(BI); + else if (isa<CallInst>(BI) || isa<InvokeInst>(BI)) { + HasCalls = true; + chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores); + } + } + chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores); + } + + // We have collected all loads and stores. + // FIXME: many of these accesses do not need to be checked for races + // (e.g. variables that do not escape, etc). + + // Instrument memory accesses. + for (size_t i = 0, n = AllLoadsAndStores.size(); i < n; ++i) { + Res |= instrumentLoadOrStore(AllLoadsAndStores[i]); + } + + // Instrument atomic memory accesses. + for (size_t i = 0, n = AtomicAccesses.size(); i < n; ++i) { + Res |= instrumentAtomic(AtomicAccesses[i]); + } + + // Instrument function entry/exit points if there were instrumented accesses. + if (Res || HasCalls) { + IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI()); + Value *ReturnAddress = IRB.CreateCall( + Intrinsic::getDeclaration(F.getParent(), Intrinsic::returnaddress), + IRB.getInt32(0)); + IRB.CreateCall(TsanFuncEntry, ReturnAddress); + for (size_t i = 0, n = RetVec.size(); i < n; ++i) { + IRBuilder<> IRBRet(RetVec[i]); + IRBRet.CreateCall(TsanFuncExit); + } + Res = true; + } + return Res; +} + +bool ThreadSanitizer::instrumentLoadOrStore(Instruction *I) { + IRBuilder<> IRB(I); + bool IsWrite = isa<StoreInst>(*I); + Value *Addr = IsWrite + ? cast<StoreInst>(I)->getPointerOperand() + : cast<LoadInst>(I)->getPointerOperand(); + int Idx = getMemoryAccessFuncIndex(Addr); + if (Idx < 0) + return false; + if (IsWrite && isVtableAccess(I)) { + DEBUG(dbgs() << " VPTR : " << *I << "\n"); + Value *StoredValue = cast<StoreInst>(I)->getValueOperand(); + // StoredValue does not necessary have a pointer type. + if (isa<IntegerType>(StoredValue->getType())) + StoredValue = IRB.CreateIntToPtr(StoredValue, IRB.getInt8PtrTy()); + // Call TsanVptrUpdate. + IRB.CreateCall2(TsanVptrUpdate, + IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()), + IRB.CreatePointerCast(StoredValue, IRB.getInt8PtrTy())); + NumInstrumentedVtableWrites++; + return true; + } + Value *OnAccessFunc = IsWrite ? TsanWrite[Idx] : TsanRead[Idx]; + IRB.CreateCall(OnAccessFunc, IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy())); + if (IsWrite) NumInstrumentedWrites++; + else NumInstrumentedReads++; + return true; +} + +static ConstantInt *createOrdering(IRBuilder<> *IRB, AtomicOrdering ord) { + uint32_t v = 0; + switch (ord) { + case NotAtomic: assert(false); + case Unordered: // Fall-through. + case Monotonic: v = 1 << 0; break; + // case Consume: v = 1 << 1; break; // Not specified yet. + case Acquire: v = 1 << 2; break; + case Release: v = 1 << 3; break; + case AcquireRelease: v = 1 << 4; break; + case SequentiallyConsistent: v = 1 << 5; break; + } + return IRB->getInt32(v); +} + +bool ThreadSanitizer::instrumentAtomic(Instruction *I) { + IRBuilder<> IRB(I); + if (LoadInst *LI = dyn_cast<LoadInst>(I)) { + Value *Addr = LI->getPointerOperand(); + int Idx = getMemoryAccessFuncIndex(Addr); + if (Idx < 0) + return false; + const size_t ByteSize = 1 << Idx; + const size_t BitSize = ByteSize * 8; + Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize); + Type *PtrTy = Ty->getPointerTo(); + Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy), + createOrdering(&IRB, LI->getOrdering())}; + CallInst *C = CallInst::Create(TsanAtomicLoad[Idx], + ArrayRef<Value*>(Args)); + ReplaceInstWithInst(I, C); + + } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { + Value *Addr = SI->getPointerOperand(); + int Idx = getMemoryAccessFuncIndex(Addr); + if (Idx < 0) + return false; + const size_t ByteSize = 1 << Idx; + const size_t BitSize = ByteSize * 8; + Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize); + Type *PtrTy = Ty->getPointerTo(); + Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy), + IRB.CreateIntCast(SI->getValueOperand(), Ty, false), + createOrdering(&IRB, SI->getOrdering())}; + CallInst *C = CallInst::Create(TsanAtomicStore[Idx], + ArrayRef<Value*>(Args)); + ReplaceInstWithInst(I, C); + } else if (isa<AtomicRMWInst>(I)) { + // FIXME: Not yet supported. + } else if (isa<AtomicCmpXchgInst>(I)) { + // FIXME: Not yet supported. + } else if (isa<FenceInst>(I)) { + // FIXME: Not yet supported. + } + return true; +} + +int ThreadSanitizer::getMemoryAccessFuncIndex(Value *Addr) { + Type *OrigPtrTy = Addr->getType(); + Type *OrigTy = cast<PointerType>(OrigPtrTy)->getElementType(); + assert(OrigTy->isSized()); + uint32_t TypeSize = TD->getTypeStoreSizeInBits(OrigTy); + if (TypeSize != 8 && TypeSize != 16 && + TypeSize != 32 && TypeSize != 64 && TypeSize != 128) { + NumAccessesWithBadSize++; + // Ignore all unusual sizes. + return -1; + } + size_t Idx = CountTrailingZeros_32(TypeSize / 8); + assert(Idx < kNumberOfAccessSizes); + return Idx; +} |
