diff options
Diffstat (limited to 'contrib/llvm/lib/Transforms/Instrumentation')
15 files changed, 2933 insertions, 2302 deletions
diff --git a/contrib/llvm/lib/Transforms/Instrumentation/AddressSanitizer.cpp b/contrib/llvm/lib/Transforms/Instrumentation/AddressSanitizer.cpp index 623c470..d731ec5 100644 --- a/contrib/llvm/lib/Transforms/Instrumentation/AddressSanitizer.cpp +++ b/contrib/llvm/lib/Transforms/Instrumentation/AddressSanitizer.cpp @@ -23,6 +23,7 @@ #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/ADT/Triple.h" #include "llvm/DIBuilder.h" @@ -39,13 +40,14 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/DataTypes.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/Endian.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Support/system_error.h" -#include "llvm/Target/TargetMachine.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" -#include "llvm/Transforms/Utils/BlackList.h" +#include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/ModuleUtils.h" +#include "llvm/Transforms/Utils/SpecialCaseList.h" #include <algorithm> #include <string> @@ -56,36 +58,49 @@ static const uint64_t kDefaultShadowOffset32 = 1ULL << 29; static const uint64_t kDefaultShadowOffset64 = 1ULL << 44; static const uint64_t kDefaultShort64bitShadowOffset = 0x7FFF8000; // < 2G. static const uint64_t kPPC64_ShadowOffset64 = 1ULL << 41; +static const uint64_t kMIPS32_ShadowOffset32 = 0x0aaa8000; +static const size_t kMinStackMallocSize = 1 << 6; // 64B 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 *kAsanReportLoadN = "__asan_report_load_n"; -static const char *kAsanReportStoreN = "__asan_report_store_n"; -static const char *kAsanRegisterGlobalsName = "__asan_register_globals"; -static const char *kAsanUnregisterGlobalsName = "__asan_unregister_globals"; -static const char *kAsanPoisonGlobalsName = "__asan_before_dynamic_init"; -static const char *kAsanUnpoisonGlobalsName = "__asan_after_dynamic_init"; -static const char *kAsanInitName = "__asan_init_v3"; -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 char *kAsanGenPrefix = "__asan_gen_"; -static const char *kAsanPoisonStackMemoryName = "__asan_poison_stack_memory"; -static const char *kAsanUnpoisonStackMemoryName = +static const char *const kAsanModuleCtorName = "asan.module_ctor"; +static const char *const kAsanModuleDtorName = "asan.module_dtor"; +static const int kAsanCtorAndCtorPriority = 1; +static const char *const kAsanReportErrorTemplate = "__asan_report_"; +static const char *const kAsanReportLoadN = "__asan_report_load_n"; +static const char *const kAsanReportStoreN = "__asan_report_store_n"; +static const char *const kAsanRegisterGlobalsName = "__asan_register_globals"; +static const char *const kAsanUnregisterGlobalsName = + "__asan_unregister_globals"; +static const char *const kAsanPoisonGlobalsName = "__asan_before_dynamic_init"; +static const char *const kAsanUnpoisonGlobalsName = "__asan_after_dynamic_init"; +static const char *const kAsanInitName = "__asan_init_v3"; +static const char *const kAsanCovName = "__sanitizer_cov"; +static const char *const kAsanHandleNoReturnName = "__asan_handle_no_return"; +static const char *const kAsanMappingOffsetName = "__asan_mapping_offset"; +static const char *const kAsanMappingScaleName = "__asan_mapping_scale"; +static const int kMaxAsanStackMallocSizeClass = 10; +static const char *const kAsanStackMallocNameTemplate = "__asan_stack_malloc_"; +static const char *const kAsanStackFreeNameTemplate = "__asan_stack_free_"; +static const char *const kAsanGenPrefix = "__asan_gen_"; +static const char *const kAsanPoisonStackMemoryName = + "__asan_poison_stack_memory"; +static const char *const kAsanUnpoisonStackMemoryName = "__asan_unpoison_stack_memory"; +static const char *const kAsanOptionDetectUAR = + "__asan_option_detect_stack_use_after_return"; + +// These constants must match the definitions in the run-time library. static const int kAsanStackLeftRedzoneMagic = 0xf1; static const int kAsanStackMidRedzoneMagic = 0xf2; static const int kAsanStackRightRedzoneMagic = 0xf3; static const int kAsanStackPartialRedzoneMagic = 0xf4; +#ifndef NDEBUG +static const int kAsanStackAfterReturnMagic = 0xf5; +#endif // Accesses sizes are powers of two: 1, 2, 4, 8, 16. static const size_t kNumberOfAccessSizes = 5; @@ -120,6 +135,8 @@ static cl::opt<bool> ClUseAfterReturn("asan-use-after-return", // 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> ClCoverage("asan-coverage", + cl::desc("ASan coverage"), cl::Hidden, cl::init(false)); static cl::opt<bool> ClInitializers("asan-initialization-order", cl::desc("Handle C++ initializer order"), cl::Hidden, cl::init(false)); static cl::opt<bool> ClMemIntrin("asan-memintrin", @@ -130,6 +147,19 @@ static cl::opt<std::string> ClBlacklistFile("asan-blacklist", cl::desc("File containing the list of objects to ignore " "during instrumentation"), cl::Hidden); +// This is an experimental feature that will allow to choose between +// instrumented and non-instrumented code at link-time. +// If this option is on, just before instrumenting a function we create its +// clone; if the function is not changed by asan the clone is deleted. +// If we end up with a clone, we put the instrumented function into a section +// called "ASAN" and the uninstrumented function into a section called "NOASAN". +// +// This is still a prototype, we need to figure out a way to keep two copies of +// a function so that the linker can easily choose one of them. +static cl::opt<bool> ClKeepUninstrumented("asan-keep-uninstrumented-functions", + cl::desc("Keep uninstrumented copies of functions"), + cl::Hidden, cl::init(false)); + // These flags allow to change the shadow mapping. // The shadow mapping looks like // Shadow = (Mem >> scale) + (1 << offset_log) @@ -167,6 +197,13 @@ static cl::opt<int> ClDebugMin("asan-debug-min", cl::desc("Debug min inst"), static cl::opt<int> ClDebugMax("asan-debug-max", cl::desc("Debug man inst"), cl::Hidden, cl::init(-1)); +STATISTIC(NumInstrumentedReads, "Number of instrumented reads"); +STATISTIC(NumInstrumentedWrites, "Number of instrumented writes"); +STATISTIC(NumOptimizedAccessesToGlobalArray, + "Number of optimized accesses to global arrays"); +STATISTIC(NumOptimizedAccessesToGlobalVar, + "Number of optimized accesses to global vars"); + namespace { /// A set of dynamically initialized globals extracted from metadata. class SetOfDynamicallyInitializedGlobals { @@ -206,8 +243,11 @@ static ShadowMapping getShadowMapping(const Module &M, int LongSize, llvm::Triple TargetTriple(M.getTargetTriple()); bool IsAndroid = TargetTriple.getEnvironment() == llvm::Triple::Android; bool IsMacOSX = TargetTriple.getOS() == llvm::Triple::MacOSX; - bool IsPPC64 = TargetTriple.getArch() == llvm::Triple::ppc64; + bool IsPPC64 = TargetTriple.getArch() == llvm::Triple::ppc64 || + TargetTriple.getArch() == llvm::Triple::ppc64le; bool IsX86_64 = TargetTriple.getArch() == llvm::Triple::x86_64; + bool IsMIPS32 = TargetTriple.getArch() == llvm::Triple::mips || + TargetTriple.getArch() == llvm::Triple::mipsel; ShadowMapping Mapping; @@ -217,7 +257,8 @@ static ShadowMapping getShadowMapping(const Module &M, int LongSize, Mapping.OrShadowOffset = !IsPPC64 && !ClShort64BitOffset; Mapping.Offset = (IsAndroid || ZeroBaseShadow) ? 0 : - (LongSize == 32 ? kDefaultShadowOffset32 : + (LongSize == 32 ? + (IsMIPS32 ? kMIPS32_ShadowOffset32 : kDefaultShadowOffset32) : IsPPC64 ? kPPC64_ShadowOffset64 : kDefaultShadowOffset64); if (!ZeroBaseShadow && ClShort64BitOffset && IsX86_64 && !IsMacOSX) { assert(LongSize == 64); @@ -285,6 +326,8 @@ struct AddressSanitizer : public FunctionPass { bool ShouldInstrumentGlobal(GlobalVariable *G); bool LooksLikeCodeInBug11395(Instruction *I); void FindDynamicInitializers(Module &M); + bool GlobalIsLinkerInitialized(GlobalVariable *G); + bool InjectCoverage(Function &F); bool CheckInitOrder; bool CheckUseAfterReturn; @@ -300,7 +343,8 @@ struct AddressSanitizer : public FunctionPass { Function *AsanCtorFunction; Function *AsanInitFunction; Function *AsanHandleNoReturnFunc; - OwningPtr<BlackList> BL; + Function *AsanCovFunction; + OwningPtr<SpecialCaseList> BL; // This array is indexed by AccessIsWrite and log2(AccessSize). Function *AsanErrorCallback[2][kNumberOfAccessSizes]; // This array is indexed by AccessIsWrite. @@ -340,7 +384,7 @@ class AddressSanitizerModule : public ModulePass { SmallString<64> BlacklistFile; bool ZeroBaseShadow; - OwningPtr<BlackList> BL; + OwningPtr<SpecialCaseList> BL; SetOfDynamicallyInitializedGlobals DynamicallyInitializedGlobals; Type *IntptrTy; LLVMContext *C; @@ -375,12 +419,14 @@ struct FunctionStackPoisoner : public InstVisitor<FunctionStackPoisoner> { uint64_t TotalStackSize; unsigned StackAlignment; - Function *AsanStackMallocFunc, *AsanStackFreeFunc; + Function *AsanStackMallocFunc[kMaxAsanStackMallocSizeClass + 1], + *AsanStackFreeFunc[kMaxAsanStackMallocSizeClass + 1]; Function *AsanPoisonStackMemoryFunc, *AsanUnpoisonStackMemoryFunc; // Stores a place and arguments of poisoning/unpoisoning call for alloca. struct AllocaPoisonCall { IntrinsicInst *InsBefore; + AllocaInst *AI; uint64_t Size; bool DoPoison; }; @@ -433,7 +479,7 @@ struct FunctionStackPoisoner : public InstVisitor<FunctionStackPoisoner> { StackAlignment = std::max(StackAlignment, AI.getAlignment()); AllocaVec.push_back(&AI); - uint64_t AlignedSize = getAlignedAllocaSize(&AI); + uint64_t AlignedSize = getAlignedAllocaSize(&AI); TotalStackSize += AlignedSize; } @@ -459,7 +505,7 @@ struct FunctionStackPoisoner : public InstVisitor<FunctionStackPoisoner> { AllocaInst *AI = findAllocaForValue(II.getArgOperand(1)); if (!AI) return; bool DoPoison = (ID == Intrinsic::lifetime_end); - AllocaPoisonCall APC = {&II, SizeValue, DoPoison}; + AllocaPoisonCall APC = {&II, AI, SizeValue, DoPoison}; AllocaPoisonCallVec.push_back(APC); } @@ -467,33 +513,37 @@ struct FunctionStackPoisoner : public InstVisitor<FunctionStackPoisoner> { void initializeCallbacks(Module &M); // Check if we want (and can) handle this alloca. - bool isInterestingAlloca(AllocaInst &AI) { + bool isInterestingAlloca(AllocaInst &AI) const { return (!AI.isArrayAllocation() && AI.isStaticAlloca() && + AI.getAlignment() <= RedzoneSize() && AI.getAllocatedType()->isSized()); } size_t RedzoneSize() const { return RedzoneSizeForScale(Mapping.Scale); } - uint64_t getAllocaSizeInBytes(AllocaInst *AI) { + uint64_t getAllocaSizeInBytes(AllocaInst *AI) const { Type *Ty = AI->getAllocatedType(); uint64_t SizeInBytes = ASan.TD->getTypeAllocSize(Ty); return SizeInBytes; } - uint64_t getAlignedSize(uint64_t SizeInBytes) { + uint64_t getAlignedSize(uint64_t SizeInBytes) const { size_t RZ = RedzoneSize(); return ((SizeInBytes + RZ - 1) / RZ) * RZ; } - uint64_t getAlignedAllocaSize(AllocaInst *AI) { + uint64_t getAlignedAllocaSize(AllocaInst *AI) const { uint64_t SizeInBytes = getAllocaSizeInBytes(AI); return getAlignedSize(SizeInBytes); } /// Finds alloca where the value comes from. AllocaInst *findAllocaForValue(Value *V); - void poisonRedZones(const ArrayRef<AllocaInst*> &AllocaVec, IRBuilder<> IRB, + void poisonRedZones(const ArrayRef<AllocaInst*> &AllocaVec, IRBuilder<> &IRB, Value *ShadowBase, bool DoPoison); - void poisonAlloca(Value *V, uint64_t Size, IRBuilder<> IRB, bool DoPoison); + void poisonAlloca(Value *V, uint64_t Size, IRBuilder<> &IRB, bool DoPoison); + + void SetShadowToStackAfterReturnInlined(IRBuilder<> &IRB, Value *ShadowBase, + int Size); }; } // namespace @@ -520,16 +570,16 @@ ModulePass *llvm::createAddressSanitizerModulePass( } static size_t TypeSizeToSizeIndex(uint32_t TypeSize) { - size_t Res = CountTrailingZeros_32(TypeSize / 8); + size_t Res = countTrailingZeros(TypeSize / 8); assert(Res < kNumberOfAccessSizes); return Res; } -// Create a constant for Str so that we can pass it to the run-time lib. +// \brief 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); GlobalVariable *GV = new GlobalVariable(M, StrConst->getType(), true, - GlobalValue::PrivateLinkage, StrConst, + GlobalValue::InternalLinkage, StrConst, kAsanGenPrefix); GV->setUnnamedAddr(true); // Ok to merge these. GV->setAlignment(1); // Strings may not be merged w/o setting align 1. @@ -620,6 +670,13 @@ static Value *isInterestingMemoryAccess(Instruction *I, bool *IsWrite) { return NULL; } +bool AddressSanitizer::GlobalIsLinkerInitialized(GlobalVariable *G) { + // If a global variable does not have dynamic initialization we don't + // have to instrument it. However, if a global does not have initializer + // at all, we assume it has dynamic initializer (in other TU). + return G->hasInitializer() && !DynamicallyInitializedGlobals.Contains(G); +} + void AddressSanitizer::instrumentMop(Instruction *I) { bool IsWrite = false; Value *Addr = isInterestingMemoryAccess(I, &IsWrite); @@ -628,13 +685,19 @@ void AddressSanitizer::instrumentMop(Instruction *I) { if (GlobalVariable *G = dyn_cast<GlobalVariable>(Addr)) { // If initialization order checking is disabled, a simple access to a // dynamically initialized global is always valid. - if (!CheckInitOrder) - return; - // If a global variable does not have dynamic initialization we don't - // have to instrument it. However, if a global does not have initailizer - // at all, we assume it has dynamic initializer (in other TU). - if (G->hasInitializer() && !DynamicallyInitializedGlobals.Contains(G)) + if (!CheckInitOrder || GlobalIsLinkerInitialized(G)) { + NumOptimizedAccessesToGlobalVar++; return; + } + } + ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr); + if (CE && CE->isGEPWithNoNotionalOverIndexing()) { + if (GlobalVariable *G = dyn_cast<GlobalVariable>(CE->getOperand(0))) { + if (CE->getOperand(1)->isNullValue() && GlobalIsLinkerInitialized(G)) { + NumOptimizedAccessesToGlobalArray++; + return; + } + } } } @@ -646,6 +709,11 @@ void AddressSanitizer::instrumentMop(Instruction *I) { assert((TypeSize % 8) == 0); + if (IsWrite) + NumInstrumentedWrites++; + else + NumInstrumentedReads++; + // Instrument a 1-, 2-, 4-, 8-, or 16- byte access with one check. if (TypeSize == 8 || TypeSize == 16 || TypeSize == 32 || TypeSize == 64 || TypeSize == 128) @@ -861,7 +929,7 @@ bool AddressSanitizerModule::runOnModule(Module &M) { TD = getAnalysisIfAvailable<DataLayout>(); if (!TD) return false; - BL.reset(new BlackList(BlacklistFile)); + BL.reset(SpecialCaseList::createOrDie(BlacklistFile)); if (BL->isIn(M)) return false; C = &(M.getContext()); int LongSize = TD->getPointerSizeInBits(); @@ -892,8 +960,7 @@ bool AddressSanitizerModule::runOnModule(Module &M) { StructType *GlobalStructTy = StructType::get(IntptrTy, IntptrTy, IntptrTy, IntptrTy, IntptrTy, IntptrTy, NULL); - SmallVector<Constant *, 16> Initializers(n), DynamicInit; - + SmallVector<Constant *, 16> Initializers(n); Function *CtorFunc = M.getFunction(kAsanModuleCtorName); assert(CtorFunc); @@ -929,7 +996,7 @@ bool AddressSanitizerModule::runOnModule(Module &M) { bool GlobalHasDynamicInitializer = DynamicallyInitializedGlobals.Contains(G); // Don't check initialization order if this global is blacklisted. - GlobalHasDynamicInitializer &= !BL->isInInit(*G); + GlobalHasDynamicInitializer &= !BL->isIn(*G, "init"); StructType *NewTy = StructType::get(Ty, RightRedZoneTy, NULL); Constant *NewInitializer = ConstantStruct::get( @@ -939,8 +1006,11 @@ bool AddressSanitizerModule::runOnModule(Module &M) { GlobalVariable *Name = createPrivateGlobalForString(M, G->getName()); // Create a new global variable with enough space for a redzone. + GlobalValue::LinkageTypes Linkage = G->getLinkage(); + if (G->isConstant() && Linkage == GlobalValue::PrivateLinkage) + Linkage = GlobalValue::InternalLinkage; GlobalVariable *NewGlobal = new GlobalVariable( - M, NewTy, G->isConstant(), G->getLinkage(), + M, NewTy, G->isConstant(), Linkage, NewInitializer, "", G, G->getThreadLocalMode()); NewGlobal->copyAttributesFrom(G); NewGlobal->setAlignment(MinRZ); @@ -973,7 +1043,7 @@ bool AddressSanitizerModule::runOnModule(Module &M) { ArrayType *ArrayOfGlobalStructTy = ArrayType::get(GlobalStructTy, n); GlobalVariable *AllGlobals = new GlobalVariable( - M, ArrayOfGlobalStructTy, false, GlobalVariable::PrivateLinkage, + M, ArrayOfGlobalStructTy, false, GlobalVariable::InternalLinkage, ConstantArray::get(ArrayOfGlobalStructTy, Initializers), ""); // Create calls for poisoning before initializers run and unpoisoning after. @@ -1021,6 +1091,8 @@ void AddressSanitizer::initializeCallbacks(Module &M) { AsanHandleNoReturnFunc = checkInterfaceFunction(M.getOrInsertFunction( kAsanHandleNoReturnName, IRB.getVoidTy(), NULL)); + AsanCovFunction = checkInterfaceFunction(M.getOrInsertFunction( + kAsanCovName, 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(""), @@ -1051,7 +1123,7 @@ bool AddressSanitizer::doInitialization(Module &M) { if (!TD) return false; - BL.reset(new BlackList(BlacklistFile)); + BL.reset(SpecialCaseList::createOrDie(BlacklistFile)); DynamicallyInitializedGlobals.Init(M); C = &(M.getContext()); @@ -1092,6 +1164,47 @@ bool AddressSanitizer::maybeInsertAsanInitAtFunctionEntry(Function &F) { return false; } +// Poor man's coverage that works with ASan. +// We create a Guard boolean variable with the same linkage +// as the function and inject this code into the entry block: +// if (*Guard) { +// __sanitizer_cov(&F); +// *Guard = 1; +// } +// The accesses to Guard are atomic. The rest of the logic is +// in __sanitizer_cov (it's fine to call it more than once). +// +// This coverage implementation provides very limited data: +// it only tells if a given function was ever executed. +// No counters, no per-basic-block or per-edge data. +// But for many use cases this is what we need and the added slowdown +// is negligible. This simple implementation will probably be obsoleted +// by the upcoming Clang-based coverage implementation. +// By having it here and now we hope to +// a) get the functionality to users earlier and +// b) collect usage statistics to help improve Clang coverage design. +bool AddressSanitizer::InjectCoverage(Function &F) { + if (!ClCoverage) return false; + IRBuilder<> IRB(F.getEntryBlock().getFirstInsertionPt()); + Type *Int8Ty = IRB.getInt8Ty(); + GlobalVariable *Guard = new GlobalVariable( + *F.getParent(), Int8Ty, false, GlobalValue::PrivateLinkage, + Constant::getNullValue(Int8Ty), "__asan_gen_cov_" + F.getName()); + LoadInst *Load = IRB.CreateLoad(Guard); + Load->setAtomic(Monotonic); + Load->setAlignment(1); + Value *Cmp = IRB.CreateICmpEQ(Constant::getNullValue(Int8Ty), Load); + Instruction *Ins = SplitBlockAndInsertIfThen(cast<Instruction>(Cmp), false); + IRB.SetInsertPoint(Ins); + // We pass &F to __sanitizer_cov. We could avoid this and rely on + // GET_CALLER_PC, but having the PC of the first instruction is just nice. + IRB.CreateCall(AsanCovFunction, IRB.CreatePointerCast(&F, IntptrTy)); + StoreInst *Store = IRB.CreateStore(ConstantInt::get(Int8Ty, 1), Guard); + Store->setAtomic(Monotonic); + Store->setAlignment(1); + return true; +} + bool AddressSanitizer::runOnFunction(Function &F) { if (BL->isIn(F)) return false; if (&F == AsanCtorFunction) return false; @@ -1102,8 +1215,7 @@ bool AddressSanitizer::runOnFunction(Function &F) { // If needed, insert __asan_init before checking for SanitizeAddress attr. maybeInsertAsanInitAtFunctionEntry(F); - if (!F.getAttributes().hasAttribute(AttributeSet::FunctionIndex, - Attribute::SanitizeAddress)) + if (!F.hasFnAttribute(Attribute::SanitizeAddress)) return false; if (!ClDebugFunc.empty() && ClDebugFunc != F.getName()) @@ -1114,6 +1226,7 @@ bool AddressSanitizer::runOnFunction(Function &F) { SmallSet<Value*, 16> TempsToInstrument; SmallVector<Instruction*, 16> ToInstrument; SmallVector<Instruction*, 8> NoReturnCalls; + int NumAllocas = 0; bool IsWrite; // Fill the set of memory operations to instrument. @@ -1132,6 +1245,8 @@ bool AddressSanitizer::runOnFunction(Function &F) { } else if (isa<MemIntrinsic>(BI) && ClMemIntrin) { // ok, take it. } else { + if (isa<AllocaInst>(BI)) + NumAllocas++; CallSite CS(BI); if (CS) { // A call inside BB. @@ -1148,6 +1263,17 @@ bool AddressSanitizer::runOnFunction(Function &F) { } } + Function *UninstrumentedDuplicate = 0; + bool LikelyToInstrument = + !NoReturnCalls.empty() || !ToInstrument.empty() || (NumAllocas > 0); + if (ClKeepUninstrumented && LikelyToInstrument) { + ValueToValueMapTy VMap; + UninstrumentedDuplicate = CloneFunction(&F, VMap, false); + UninstrumentedDuplicate->removeFnAttr(Attribute::SanitizeAddress); + UninstrumentedDuplicate->setName("NOASAN_" + F.getName()); + F.getParent()->getFunctionList().push_back(UninstrumentedDuplicate); + } + // Instrument. int NumInstrumented = 0; for (size_t i = 0, n = ToInstrument.size(); i != n; i++) { @@ -1172,9 +1298,29 @@ bool AddressSanitizer::runOnFunction(Function &F) { IRBuilder<> IRB(CI); IRB.CreateCall(AsanHandleNoReturnFunc); } - DEBUG(dbgs() << "ASAN done instrumenting:\n" << F << "\n"); - return NumInstrumented > 0 || ChangedStack || !NoReturnCalls.empty(); + bool res = NumInstrumented > 0 || ChangedStack || !NoReturnCalls.empty(); + + if (InjectCoverage(F)) + res = true; + + DEBUG(dbgs() << "ASAN done instrumenting: " << res << " " << F << "\n"); + + if (ClKeepUninstrumented) { + if (!res) { + // No instrumentation is done, no need for the duplicate. + if (UninstrumentedDuplicate) + UninstrumentedDuplicate->eraseFromParent(); + } else { + // The function was instrumented. We must have the duplicate. + assert(UninstrumentedDuplicate); + UninstrumentedDuplicate->setSection("NOASAN"); + assert(!F.hasSection()); + F.setSection("ASAN"); + } + } + + return res; } static uint64_t ValueForPoison(uint64_t PoisonByte, size_t ShadowRedzoneSize) { @@ -1217,11 +1363,15 @@ bool AddressSanitizer::LooksLikeCodeInBug11395(Instruction *I) { void FunctionStackPoisoner::initializeCallbacks(Module &M) { IRBuilder<> IRB(*C); - AsanStackMallocFunc = checkInterfaceFunction(M.getOrInsertFunction( - kAsanStackMallocName, IntptrTy, IntptrTy, IntptrTy, NULL)); - AsanStackFreeFunc = checkInterfaceFunction(M.getOrInsertFunction( - kAsanStackFreeName, IRB.getVoidTy(), - IntptrTy, IntptrTy, IntptrTy, NULL)); + for (int i = 0; i <= kMaxAsanStackMallocSizeClass; i++) { + std::string Suffix = itostr(i); + AsanStackMallocFunc[i] = checkInterfaceFunction( + M.getOrInsertFunction(kAsanStackMallocNameTemplate + Suffix, IntptrTy, + IntptrTy, IntptrTy, NULL)); + AsanStackFreeFunc[i] = checkInterfaceFunction(M.getOrInsertFunction( + kAsanStackFreeNameTemplate + Suffix, IRB.getVoidTy(), IntptrTy, + IntptrTy, IntptrTy, NULL)); + } AsanPoisonStackMemoryFunc = checkInterfaceFunction(M.getOrInsertFunction( kAsanPoisonStackMemoryName, IRB.getVoidTy(), IntptrTy, IntptrTy, NULL)); AsanUnpoisonStackMemoryFunc = checkInterfaceFunction(M.getOrInsertFunction( @@ -1229,7 +1379,7 @@ void FunctionStackPoisoner::initializeCallbacks(Module &M) { } void FunctionStackPoisoner::poisonRedZones( - const ArrayRef<AllocaInst*> &AllocaVec, IRBuilder<> IRB, Value *ShadowBase, + const ArrayRef<AllocaInst*> &AllocaVec, IRBuilder<> &IRB, Value *ShadowBase, bool DoPoison) { size_t ShadowRZSize = RedzoneSize() >> Mapping.Scale; assert(ShadowRZSize >= 1 && ShadowRZSize <= 4); @@ -1270,6 +1420,10 @@ void FunctionStackPoisoner::poisonRedZones( RedzoneSize(), 1ULL << Mapping.Scale, kAsanStackPartialRedzoneMagic); + Poison = + ASan.TD->isLittleEndian() + ? support::endian::byte_swap<uint32_t, support::little>(Poison) + : support::endian::byte_swap<uint32_t, support::big>(Poison); } Value *PartialPoison = ConstantInt::get(RZTy, Poison); IRB.CreateStore(PartialPoison, IRB.CreateIntToPtr(Ptr, RZPtrTy)); @@ -1286,12 +1440,40 @@ void FunctionStackPoisoner::poisonRedZones( } } +// Fake stack allocator (asan_fake_stack.h) has 11 size classes +// for every power of 2 from kMinStackMallocSize to kMaxAsanStackMallocSizeClass +static int StackMallocSizeClass(uint64_t LocalStackSize) { + assert(LocalStackSize <= kMaxStackMallocSize); + uint64_t MaxSize = kMinStackMallocSize; + for (int i = 0; ; i++, MaxSize *= 2) + if (LocalStackSize <= MaxSize) + return i; + llvm_unreachable("impossible LocalStackSize"); +} + +// Set Size bytes starting from ShadowBase to kAsanStackAfterReturnMagic. +// We can not use MemSet intrinsic because it may end up calling the actual +// memset. Size is a multiple of 8. +// Currently this generates 8-byte stores on x86_64; it may be better to +// generate wider stores. +void FunctionStackPoisoner::SetShadowToStackAfterReturnInlined( + IRBuilder<> &IRB, Value *ShadowBase, int Size) { + assert(!(Size % 8)); + assert(kAsanStackAfterReturnMagic == 0xf5); + for (int i = 0; i < Size; i += 8) { + Value *p = IRB.CreateAdd(ShadowBase, ConstantInt::get(IntptrTy, i)); + IRB.CreateStore(ConstantInt::get(IRB.getInt64Ty(), 0xf5f5f5f5f5f5f5f5ULL), + IRB.CreateIntToPtr(p, IRB.getInt64Ty()->getPointerTo())); + } +} + void FunctionStackPoisoner::poisonStack() { uint64_t LocalStackSize = TotalStackSize + (AllocaVec.size() + 1) * RedzoneSize(); bool DoStackMalloc = ASan.CheckUseAfterReturn && LocalStackSize <= kMaxStackMallocSize; + int StackMallocIdx = -1; assert(AllocaVec.size() > 0); Instruction *InsBefore = AllocaVec[0]; @@ -1309,8 +1491,28 @@ void FunctionStackPoisoner::poisonStack() { Value *LocalStackBase = OrigStackBase; if (DoStackMalloc) { - LocalStackBase = IRB.CreateCall2(AsanStackMallocFunc, + // LocalStackBase = OrigStackBase + // if (__asan_option_detect_stack_use_after_return) + // LocalStackBase = __asan_stack_malloc_N(LocalStackBase, OrigStackBase); + StackMallocIdx = StackMallocSizeClass(LocalStackSize); + assert(StackMallocIdx <= kMaxAsanStackMallocSizeClass); + Constant *OptionDetectUAR = F.getParent()->getOrInsertGlobal( + kAsanOptionDetectUAR, IRB.getInt32Ty()); + Value *Cmp = IRB.CreateICmpNE(IRB.CreateLoad(OptionDetectUAR), + Constant::getNullValue(IRB.getInt32Ty())); + Instruction *Term = + SplitBlockAndInsertIfThen(cast<Instruction>(Cmp), false); + BasicBlock *CmpBlock = cast<Instruction>(Cmp)->getParent(); + IRBuilder<> IRBIf(Term); + LocalStackBase = IRBIf.CreateCall2( + AsanStackMallocFunc[StackMallocIdx], ConstantInt::get(IntptrTy, LocalStackSize), OrigStackBase); + BasicBlock *SetBlock = cast<Instruction>(LocalStackBase)->getParent(); + IRB.SetInsertPoint(InsBefore); + PHINode *Phi = IRB.CreatePHI(IntptrTy, 2); + Phi->addIncoming(OrigStackBase, CmpBlock); + Phi->addIncoming(LocalStackBase, SetBlock); + LocalStackBase = Phi; } // This string will be parsed by the run-time (DescribeAddressIfStack). @@ -1322,11 +1524,10 @@ void FunctionStackPoisoner::poisonStack() { bool HavePoisonedAllocas = false; for (size_t i = 0, n = AllocaPoisonCallVec.size(); i < n; i++) { const AllocaPoisonCall &APC = AllocaPoisonCallVec[i]; - IntrinsicInst *II = APC.InsBefore; - AllocaInst *AI = findAllocaForValue(II->getArgOperand(1)); - assert(AI); - IRBuilder<> IRB(II); - poisonAlloca(AI, APC.Size, IRB, APC.DoPoison); + assert(APC.InsBefore); + assert(APC.AI); + IRBuilder<> IRB(APC.InsBefore); + poisonAlloca(APC.AI, APC.Size, IRB, APC.DoPoison); HavePoisonedAllocas |= APC.DoPoison; } @@ -1384,10 +1585,35 @@ void FunctionStackPoisoner::poisonStack() { // Unpoison the stack. poisonRedZones(AllocaVec, IRBRet, ShadowBase, false); if (DoStackMalloc) { + assert(StackMallocIdx >= 0); // In use-after-return mode, mark the whole stack frame unaddressable. - IRBRet.CreateCall3(AsanStackFreeFunc, LocalStackBase, - ConstantInt::get(IntptrTy, LocalStackSize), - OrigStackBase); + if (StackMallocIdx <= 4) { + // For small sizes inline the whole thing: + // if LocalStackBase != OrigStackBase: + // memset(ShadowBase, kAsanStackAfterReturnMagic, ShadowSize); + // **SavedFlagPtr(LocalStackBase) = 0 + // FIXME: if LocalStackBase != OrigStackBase don't call poisonRedZones. + Value *Cmp = IRBRet.CreateICmpNE(LocalStackBase, OrigStackBase); + TerminatorInst *PoisonTerm = + SplitBlockAndInsertIfThen(cast<Instruction>(Cmp), false); + IRBuilder<> IRBPoison(PoisonTerm); + int ClassSize = kMinStackMallocSize << StackMallocIdx; + SetShadowToStackAfterReturnInlined(IRBPoison, ShadowBase, + ClassSize >> Mapping.Scale); + Value *SavedFlagPtrPtr = IRBPoison.CreateAdd( + LocalStackBase, + ConstantInt::get(IntptrTy, ClassSize - ASan.LongSize / 8)); + Value *SavedFlagPtr = IRBPoison.CreateLoad( + IRBPoison.CreateIntToPtr(SavedFlagPtrPtr, IntptrPtrTy)); + IRBPoison.CreateStore( + Constant::getNullValue(IRBPoison.getInt8Ty()), + IRBPoison.CreateIntToPtr(SavedFlagPtr, IRBPoison.getInt8PtrTy())); + } else { + // For larger frames call __asan_stack_free_*. + IRBRet.CreateCall3(AsanStackFreeFunc[StackMallocIdx], LocalStackBase, + ConstantInt::get(IntptrTy, LocalStackSize), + OrigStackBase); + } } else if (HavePoisonedAllocas) { // If we poisoned some allocas in llvm.lifetime analysis, // unpoison whole stack frame now. @@ -1402,7 +1628,7 @@ void FunctionStackPoisoner::poisonStack() { } void FunctionStackPoisoner::poisonAlloca(Value *V, uint64_t Size, - IRBuilder<> IRB, bool DoPoison) { + IRBuilder<> &IRB, bool DoPoison) { // For now just insert the call to ASan runtime. Value *AddrArg = IRB.CreatePointerCast(V, IntptrTy); Value *SizeArg = ConstantInt::get(IntptrTy, Size); diff --git a/contrib/llvm/lib/Transforms/Instrumentation/BlackList.cpp b/contrib/llvm/lib/Transforms/Instrumentation/BlackList.cpp deleted file mode 100644 index 39de4b0..0000000 --- a/contrib/llvm/lib/Transforms/Instrumentation/BlackList.cpp +++ /dev/null @@ -1,126 +0,0 @@ -//===-- BlackList.cpp - blacklist for sanitizers --------------------------===// -// -// 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 or global -// variables based on a user-supplied blacklist. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Transforms/Utils/BlackList.h" -#include "llvm/ADT/OwningPtr.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/StringExtras.h" -#include "llvm/IR/DerivedTypes.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/GlobalVariable.h" -#include "llvm/IR/Module.h" -#include "llvm/Support/MemoryBuffer.h" -#include "llvm/Support/Regex.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Support/system_error.h" -#include <string> -#include <utility> - -namespace llvm { - -BlackList::BlackList(const StringRef Path) { - // Validate and open blacklist file. - if (Path.empty()) return; - OwningPtr<MemoryBuffer> File; - if (error_code EC = MemoryBuffer::getFile(Path, File)) { - report_fatal_error("Can't open blacklist file: " + Path + ": " + - EC.message()); - } - - // Iterate through each line in the blacklist file. - SmallVector<StringRef, 16> Lines; - SplitString(File.take()->getBuffer(), Lines, "\n\r"); - StringMap<std::string> Regexps; - for (SmallVector<StringRef, 16>::iterator I = Lines.begin(), E = Lines.end(); - I != E; ++I) { - // Ignore empty lines and lines starting with "#" - if (I->empty() || I->startswith("#")) - continue; - // Get our prefix and unparsed regexp. - std::pair<StringRef, StringRef> SplitLine = I->split(":"); - StringRef Prefix = SplitLine.first; - std::string Regexp = SplitLine.second; - if (Regexp.empty()) { - // Missing ':' in the line. - report_fatal_error("malformed blacklist line: " + SplitLine.first); - } - - // Replace * with .* - for (size_t pos = 0; (pos = Regexp.find("*", pos)) != std::string::npos; - pos += strlen(".*")) { - Regexp.replace(pos, strlen("*"), ".*"); - } - - // Check that the regexp is valid. - Regex CheckRE(Regexp); - std::string Error; - if (!CheckRE.isValid(Error)) { - report_fatal_error("malformed blacklist regex: " + SplitLine.second + - ": " + Error); - } - - // Add this regexp into the proper group by its prefix. - if (!Regexps[Prefix].empty()) - Regexps[Prefix] += "|"; - Regexps[Prefix] += Regexp; - } - - // Iterate through each of the prefixes, and create Regexs for them. - for (StringMap<std::string>::const_iterator I = Regexps.begin(), - E = Regexps.end(); I != E; ++I) { - Entries[I->getKey()] = new Regex(I->getValue()); - } -} - -bool BlackList::isIn(const Function &F) const { - return isIn(*F.getParent()) || inSection("fun", F.getName()); -} - -bool BlackList::isIn(const GlobalVariable &G) const { - return isIn(*G.getParent()) || inSection("global", G.getName()); -} - -bool BlackList::isIn(const Module &M) const { - return inSection("src", M.getModuleIdentifier()); -} - -static StringRef GetGVTypeString(const GlobalVariable &G) { - // Types of GlobalVariables are always pointer types. - Type *GType = G.getType()->getElementType(); - // For now we support blacklisting struct types only. - if (StructType *SGType = dyn_cast<StructType>(GType)) { - if (!SGType->isLiteral()) - return SGType->getName(); - } - return "<unknown type>"; -} - -bool BlackList::isInInit(const GlobalVariable &G) const { - return (isIn(*G.getParent()) || - inSection("global-init", G.getName()) || - inSection("global-init-type", GetGVTypeString(G)) || - inSection("global-init-src", G.getParent()->getModuleIdentifier())); -} - -bool BlackList::inSection(const StringRef Section, - const StringRef Query) const { - StringMap<Regex*>::const_iterator I = Entries.find(Section); - if (I == Entries.end()) return false; - - Regex *FunctionRegex = I->getValue(); - return FunctionRegex->match(Query); -} - -} // namespace llvm diff --git a/contrib/llvm/lib/Transforms/Instrumentation/BoundsChecking.cpp b/contrib/llvm/lib/Transforms/Instrumentation/BoundsChecking.cpp index b094d42..7a9f0f6 100644 --- a/contrib/llvm/lib/Transforms/Instrumentation/BoundsChecking.cpp +++ b/contrib/llvm/lib/Transforms/Instrumentation/BoundsChecking.cpp @@ -80,7 +80,7 @@ BasicBlock *BoundsChecking::getTrapBB() { return TrapBB; Function *Fn = Inst->getParent()->getParent(); - BasicBlock::iterator PrevInsertPoint = Builder->GetInsertPoint(); + IRBuilder<>::InsertPointGuard Guard(*Builder); TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn); Builder->SetInsertPoint(TrapBB); @@ -91,7 +91,6 @@ BasicBlock *BoundsChecking::getTrapBB() { TrapCall->setDebugLoc(Inst->getDebugLoc()); Builder->CreateUnreachable(); - Builder->SetInsertPoint(PrevInsertPoint); return TrapBB; } @@ -173,7 +172,8 @@ bool BoundsChecking::runOnFunction(Function &F) { TrapBB = 0; BuilderTy TheBuilder(F.getContext(), TargetFolder(TD)); Builder = &TheBuilder; - ObjectSizeOffsetEvaluator TheObjSizeEval(TD, TLI, F.getContext()); + ObjectSizeOffsetEvaluator TheObjSizeEval(TD, TLI, F.getContext(), + /*RoundToAlign=*/true); ObjSizeEval = &TheObjSizeEval; // check HANDLE_MEMORY_INST in include/llvm/Instruction.def for memory diff --git a/contrib/llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp b/contrib/llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp new file mode 100644 index 0000000..9b9e725 --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp @@ -0,0 +1,1397 @@ +//===-- DataFlowSanitizer.cpp - dynamic data flow analysis ----------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This file is a part of DataFlowSanitizer, a generalised dynamic data flow +/// analysis. +/// +/// Unlike other Sanitizer tools, this tool is not designed to detect a specific +/// class of bugs on its own. Instead, it provides a generic dynamic data flow +/// analysis framework to be used by clients to help detect application-specific +/// issues within their own code. +/// +/// The analysis is based on automatic propagation of data flow labels (also +/// known as taint labels) through a program as it performs computation. Each +/// byte of application memory is backed by two bytes of shadow memory which +/// hold the label. On Linux/x86_64, memory is laid out as follows: +/// +/// +--------------------+ 0x800000000000 (top of memory) +/// | application memory | +/// +--------------------+ 0x700000008000 (kAppAddr) +/// | | +/// | unused | +/// | | +/// +--------------------+ 0x200200000000 (kUnusedAddr) +/// | union table | +/// +--------------------+ 0x200000000000 (kUnionTableAddr) +/// | shadow memory | +/// +--------------------+ 0x000000010000 (kShadowAddr) +/// | reserved by kernel | +/// +--------------------+ 0x000000000000 +/// +/// To derive a shadow memory address from an application memory address, +/// bits 44-46 are cleared to bring the address into the range +/// [0x000000008000,0x100000000000). Then the address is shifted left by 1 to +/// account for the double byte representation of shadow labels and move the +/// address into the shadow memory range. See the function +/// DataFlowSanitizer::getShadowAddress below. +/// +/// For more information, please refer to the design document: +/// http://clang.llvm.org/docs/DataFlowSanitizerDesign.html + +#include "llvm/Transforms/Instrumentation.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/InlineAsm.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/MDBuilder.h" +#include "llvm/IR/Type.h" +#include "llvm/IR/Value.h" +#include "llvm/InstVisitor.h" +#include "llvm/Pass.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Utils/SpecialCaseList.h" +#include <iterator> + +using namespace llvm; + +// The -dfsan-preserve-alignment flag controls whether this pass assumes that +// alignment requirements provided by the input IR are correct. For example, +// if the input IR contains a load with alignment 8, this flag will cause +// the shadow load to have alignment 16. This flag is disabled by default as +// we have unfortunately encountered too much code (including Clang itself; +// see PR14291) which performs misaligned access. +static cl::opt<bool> ClPreserveAlignment( + "dfsan-preserve-alignment", + cl::desc("respect alignment requirements provided by input IR"), cl::Hidden, + cl::init(false)); + +// The ABI list file controls how shadow parameters are passed. The pass treats +// every function labelled "uninstrumented" in the ABI list file as conforming +// to the "native" (i.e. unsanitized) ABI. Unless the ABI list contains +// additional annotations for those functions, a call to one of those functions +// will produce a warning message, as the labelling behaviour of the function is +// unknown. The other supported annotations are "functional" and "discard", +// which are described below under DataFlowSanitizer::WrapperKind. +static cl::opt<std::string> ClABIListFile( + "dfsan-abilist", + cl::desc("File listing native ABI functions and how the pass treats them"), + cl::Hidden); + +// Controls whether the pass uses IA_Args or IA_TLS as the ABI for instrumented +// functions (see DataFlowSanitizer::InstrumentedABI below). +static cl::opt<bool> ClArgsABI( + "dfsan-args-abi", + cl::desc("Use the argument ABI rather than the TLS ABI"), + cl::Hidden); + +static cl::opt<bool> ClDebugNonzeroLabels( + "dfsan-debug-nonzero-labels", + cl::desc("Insert calls to __dfsan_nonzero_label on observing a parameter, " + "load or return with a nonzero label"), + cl::Hidden); + +namespace { + +class DataFlowSanitizer : public ModulePass { + friend struct DFSanFunction; + friend class DFSanVisitor; + + enum { + ShadowWidth = 16 + }; + + /// Which ABI should be used for instrumented functions? + enum InstrumentedABI { + /// Argument and return value labels are passed through additional + /// arguments and by modifying the return type. + IA_Args, + + /// Argument and return value labels are passed through TLS variables + /// __dfsan_arg_tls and __dfsan_retval_tls. + IA_TLS + }; + + /// How should calls to uninstrumented functions be handled? + enum WrapperKind { + /// This function is present in an uninstrumented form but we don't know + /// how it should be handled. Print a warning and call the function anyway. + /// Don't label the return value. + WK_Warning, + + /// This function does not write to (user-accessible) memory, and its return + /// value is unlabelled. + WK_Discard, + + /// This function does not write to (user-accessible) memory, and the label + /// of its return value is the union of the label of its arguments. + WK_Functional, + + /// Instead of calling the function, a custom wrapper __dfsw_F is called, + /// where F is the name of the function. This function may wrap the + /// original function or provide its own implementation. This is similar to + /// the IA_Args ABI, except that IA_Args uses a struct return type to + /// pass the return value shadow in a register, while WK_Custom uses an + /// extra pointer argument to return the shadow. This allows the wrapped + /// form of the function type to be expressed in C. + WK_Custom + }; + + DataLayout *DL; + Module *Mod; + LLVMContext *Ctx; + IntegerType *ShadowTy; + PointerType *ShadowPtrTy; + IntegerType *IntptrTy; + ConstantInt *ZeroShadow; + ConstantInt *ShadowPtrMask; + ConstantInt *ShadowPtrMul; + Constant *ArgTLS; + Constant *RetvalTLS; + void *(*GetArgTLSPtr)(); + void *(*GetRetvalTLSPtr)(); + Constant *GetArgTLS; + Constant *GetRetvalTLS; + FunctionType *DFSanUnionFnTy; + FunctionType *DFSanUnionLoadFnTy; + FunctionType *DFSanUnimplementedFnTy; + FunctionType *DFSanSetLabelFnTy; + FunctionType *DFSanNonzeroLabelFnTy; + Constant *DFSanUnionFn; + Constant *DFSanUnionLoadFn; + Constant *DFSanUnimplementedFn; + Constant *DFSanSetLabelFn; + Constant *DFSanNonzeroLabelFn; + MDNode *ColdCallWeights; + OwningPtr<SpecialCaseList> ABIList; + DenseMap<Value *, Function *> UnwrappedFnMap; + AttributeSet ReadOnlyNoneAttrs; + + Value *getShadowAddress(Value *Addr, Instruction *Pos); + Value *combineShadows(Value *V1, Value *V2, Instruction *Pos); + bool isInstrumented(const Function *F); + bool isInstrumented(const GlobalAlias *GA); + FunctionType *getArgsFunctionType(FunctionType *T); + FunctionType *getTrampolineFunctionType(FunctionType *T); + FunctionType *getCustomFunctionType(FunctionType *T); + InstrumentedABI getInstrumentedABI(); + WrapperKind getWrapperKind(Function *F); + void addGlobalNamePrefix(GlobalValue *GV); + Function *buildWrapperFunction(Function *F, StringRef NewFName, + GlobalValue::LinkageTypes NewFLink, + FunctionType *NewFT); + Constant *getOrBuildTrampolineFunction(FunctionType *FT, StringRef FName); + + public: + DataFlowSanitizer(StringRef ABIListFile = StringRef(), + void *(*getArgTLS)() = 0, void *(*getRetValTLS)() = 0); + static char ID; + bool doInitialization(Module &M); + bool runOnModule(Module &M); +}; + +struct DFSanFunction { + DataFlowSanitizer &DFS; + Function *F; + DataFlowSanitizer::InstrumentedABI IA; + bool IsNativeABI; + Value *ArgTLSPtr; + Value *RetvalTLSPtr; + AllocaInst *LabelReturnAlloca; + DenseMap<Value *, Value *> ValShadowMap; + DenseMap<AllocaInst *, AllocaInst *> AllocaShadowMap; + std::vector<std::pair<PHINode *, PHINode *> > PHIFixups; + DenseSet<Instruction *> SkipInsts; + DenseSet<Value *> NonZeroChecks; + + DFSanFunction(DataFlowSanitizer &DFS, Function *F, bool IsNativeABI) + : DFS(DFS), F(F), IA(DFS.getInstrumentedABI()), + IsNativeABI(IsNativeABI), ArgTLSPtr(0), RetvalTLSPtr(0), + LabelReturnAlloca(0) {} + Value *getArgTLSPtr(); + Value *getArgTLS(unsigned Index, Instruction *Pos); + Value *getRetvalTLS(); + Value *getShadow(Value *V); + void setShadow(Instruction *I, Value *Shadow); + Value *combineOperandShadows(Instruction *Inst); + Value *loadShadow(Value *ShadowAddr, uint64_t Size, uint64_t Align, + Instruction *Pos); + void storeShadow(Value *Addr, uint64_t Size, uint64_t Align, Value *Shadow, + Instruction *Pos); +}; + +class DFSanVisitor : public InstVisitor<DFSanVisitor> { + public: + DFSanFunction &DFSF; + DFSanVisitor(DFSanFunction &DFSF) : DFSF(DFSF) {} + + void visitOperandShadowInst(Instruction &I); + + void visitBinaryOperator(BinaryOperator &BO); + void visitCastInst(CastInst &CI); + void visitCmpInst(CmpInst &CI); + void visitGetElementPtrInst(GetElementPtrInst &GEPI); + void visitLoadInst(LoadInst &LI); + void visitStoreInst(StoreInst &SI); + void visitReturnInst(ReturnInst &RI); + void visitCallSite(CallSite CS); + void visitPHINode(PHINode &PN); + void visitExtractElementInst(ExtractElementInst &I); + void visitInsertElementInst(InsertElementInst &I); + void visitShuffleVectorInst(ShuffleVectorInst &I); + void visitExtractValueInst(ExtractValueInst &I); + void visitInsertValueInst(InsertValueInst &I); + void visitAllocaInst(AllocaInst &I); + void visitSelectInst(SelectInst &I); + void visitMemSetInst(MemSetInst &I); + void visitMemTransferInst(MemTransferInst &I); +}; + +} + +char DataFlowSanitizer::ID; +INITIALIZE_PASS(DataFlowSanitizer, "dfsan", + "DataFlowSanitizer: dynamic data flow analysis.", false, false) + +ModulePass *llvm::createDataFlowSanitizerPass(StringRef ABIListFile, + void *(*getArgTLS)(), + void *(*getRetValTLS)()) { + return new DataFlowSanitizer(ABIListFile, getArgTLS, getRetValTLS); +} + +DataFlowSanitizer::DataFlowSanitizer(StringRef ABIListFile, + void *(*getArgTLS)(), + void *(*getRetValTLS)()) + : ModulePass(ID), GetArgTLSPtr(getArgTLS), GetRetvalTLSPtr(getRetValTLS), + ABIList(SpecialCaseList::createOrDie(ABIListFile.empty() ? ClABIListFile + : ABIListFile)) { +} + +FunctionType *DataFlowSanitizer::getArgsFunctionType(FunctionType *T) { + llvm::SmallVector<Type *, 4> ArgTypes; + std::copy(T->param_begin(), T->param_end(), std::back_inserter(ArgTypes)); + for (unsigned i = 0, e = T->getNumParams(); i != e; ++i) + ArgTypes.push_back(ShadowTy); + if (T->isVarArg()) + ArgTypes.push_back(ShadowPtrTy); + Type *RetType = T->getReturnType(); + if (!RetType->isVoidTy()) + RetType = StructType::get(RetType, ShadowTy, (Type *)0); + return FunctionType::get(RetType, ArgTypes, T->isVarArg()); +} + +FunctionType *DataFlowSanitizer::getTrampolineFunctionType(FunctionType *T) { + assert(!T->isVarArg()); + llvm::SmallVector<Type *, 4> ArgTypes; + ArgTypes.push_back(T->getPointerTo()); + std::copy(T->param_begin(), T->param_end(), std::back_inserter(ArgTypes)); + for (unsigned i = 0, e = T->getNumParams(); i != e; ++i) + ArgTypes.push_back(ShadowTy); + Type *RetType = T->getReturnType(); + if (!RetType->isVoidTy()) + ArgTypes.push_back(ShadowPtrTy); + return FunctionType::get(T->getReturnType(), ArgTypes, false); +} + +FunctionType *DataFlowSanitizer::getCustomFunctionType(FunctionType *T) { + assert(!T->isVarArg()); + llvm::SmallVector<Type *, 4> ArgTypes; + for (FunctionType::param_iterator i = T->param_begin(), e = T->param_end(); + i != e; ++i) { + FunctionType *FT; + if (isa<PointerType>(*i) && (FT = dyn_cast<FunctionType>(cast<PointerType>( + *i)->getElementType()))) { + ArgTypes.push_back(getTrampolineFunctionType(FT)->getPointerTo()); + ArgTypes.push_back(Type::getInt8PtrTy(*Ctx)); + } else { + ArgTypes.push_back(*i); + } + } + for (unsigned i = 0, e = T->getNumParams(); i != e; ++i) + ArgTypes.push_back(ShadowTy); + Type *RetType = T->getReturnType(); + if (!RetType->isVoidTy()) + ArgTypes.push_back(ShadowPtrTy); + return FunctionType::get(T->getReturnType(), ArgTypes, false); +} + +bool DataFlowSanitizer::doInitialization(Module &M) { + DL = getAnalysisIfAvailable<DataLayout>(); + if (!DL) + return false; + + Mod = &M; + Ctx = &M.getContext(); + ShadowTy = IntegerType::get(*Ctx, ShadowWidth); + ShadowPtrTy = PointerType::getUnqual(ShadowTy); + IntptrTy = DL->getIntPtrType(*Ctx); + ZeroShadow = ConstantInt::getSigned(ShadowTy, 0); + ShadowPtrMask = ConstantInt::getSigned(IntptrTy, ~0x700000000000LL); + ShadowPtrMul = ConstantInt::getSigned(IntptrTy, ShadowWidth / 8); + + Type *DFSanUnionArgs[2] = { ShadowTy, ShadowTy }; + DFSanUnionFnTy = + FunctionType::get(ShadowTy, DFSanUnionArgs, /*isVarArg=*/ false); + Type *DFSanUnionLoadArgs[2] = { ShadowPtrTy, IntptrTy }; + DFSanUnionLoadFnTy = + FunctionType::get(ShadowTy, DFSanUnionLoadArgs, /*isVarArg=*/ false); + DFSanUnimplementedFnTy = FunctionType::get( + Type::getVoidTy(*Ctx), Type::getInt8PtrTy(*Ctx), /*isVarArg=*/false); + Type *DFSanSetLabelArgs[3] = { ShadowTy, Type::getInt8PtrTy(*Ctx), IntptrTy }; + DFSanSetLabelFnTy = FunctionType::get(Type::getVoidTy(*Ctx), + DFSanSetLabelArgs, /*isVarArg=*/false); + DFSanNonzeroLabelFnTy = FunctionType::get( + Type::getVoidTy(*Ctx), ArrayRef<Type *>(), /*isVarArg=*/false); + + if (GetArgTLSPtr) { + Type *ArgTLSTy = ArrayType::get(ShadowTy, 64); + ArgTLS = 0; + GetArgTLS = ConstantExpr::getIntToPtr( + ConstantInt::get(IntptrTy, uintptr_t(GetArgTLSPtr)), + PointerType::getUnqual( + FunctionType::get(PointerType::getUnqual(ArgTLSTy), (Type *)0))); + } + if (GetRetvalTLSPtr) { + RetvalTLS = 0; + GetRetvalTLS = ConstantExpr::getIntToPtr( + ConstantInt::get(IntptrTy, uintptr_t(GetRetvalTLSPtr)), + PointerType::getUnqual( + FunctionType::get(PointerType::getUnqual(ShadowTy), (Type *)0))); + } + + ColdCallWeights = MDBuilder(*Ctx).createBranchWeights(1, 1000); + return true; +} + +bool DataFlowSanitizer::isInstrumented(const Function *F) { + return !ABIList->isIn(*F, "uninstrumented"); +} + +bool DataFlowSanitizer::isInstrumented(const GlobalAlias *GA) { + return !ABIList->isIn(*GA, "uninstrumented"); +} + +DataFlowSanitizer::InstrumentedABI DataFlowSanitizer::getInstrumentedABI() { + return ClArgsABI ? IA_Args : IA_TLS; +} + +DataFlowSanitizer::WrapperKind DataFlowSanitizer::getWrapperKind(Function *F) { + if (ABIList->isIn(*F, "functional")) + return WK_Functional; + if (ABIList->isIn(*F, "discard")) + return WK_Discard; + if (ABIList->isIn(*F, "custom")) + return WK_Custom; + + return WK_Warning; +} + +void DataFlowSanitizer::addGlobalNamePrefix(GlobalValue *GV) { + std::string GVName = GV->getName(), Prefix = "dfs$"; + GV->setName(Prefix + GVName); + + // Try to change the name of the function in module inline asm. We only do + // this for specific asm directives, currently only ".symver", to try to avoid + // corrupting asm which happens to contain the symbol name as a substring. + // Note that the substitution for .symver assumes that the versioned symbol + // also has an instrumented name. + std::string Asm = GV->getParent()->getModuleInlineAsm(); + std::string SearchStr = ".symver " + GVName + ","; + size_t Pos = Asm.find(SearchStr); + if (Pos != std::string::npos) { + Asm.replace(Pos, SearchStr.size(), + ".symver " + Prefix + GVName + "," + Prefix); + GV->getParent()->setModuleInlineAsm(Asm); + } +} + +Function * +DataFlowSanitizer::buildWrapperFunction(Function *F, StringRef NewFName, + GlobalValue::LinkageTypes NewFLink, + FunctionType *NewFT) { + FunctionType *FT = F->getFunctionType(); + Function *NewF = Function::Create(NewFT, NewFLink, NewFName, + F->getParent()); + NewF->copyAttributesFrom(F); + NewF->removeAttributes( + AttributeSet::ReturnIndex, + AttributeFuncs::typeIncompatible(NewFT->getReturnType(), + AttributeSet::ReturnIndex)); + + BasicBlock *BB = BasicBlock::Create(*Ctx, "entry", NewF); + std::vector<Value *> Args; + unsigned n = FT->getNumParams(); + for (Function::arg_iterator ai = NewF->arg_begin(); n != 0; ++ai, --n) + Args.push_back(&*ai); + CallInst *CI = CallInst::Create(F, Args, "", BB); + if (FT->getReturnType()->isVoidTy()) + ReturnInst::Create(*Ctx, BB); + else + ReturnInst::Create(*Ctx, CI, BB); + + return NewF; +} + +Constant *DataFlowSanitizer::getOrBuildTrampolineFunction(FunctionType *FT, + StringRef FName) { + FunctionType *FTT = getTrampolineFunctionType(FT); + Constant *C = Mod->getOrInsertFunction(FName, FTT); + Function *F = dyn_cast<Function>(C); + if (F && F->isDeclaration()) { + F->setLinkage(GlobalValue::LinkOnceODRLinkage); + BasicBlock *BB = BasicBlock::Create(*Ctx, "entry", F); + std::vector<Value *> Args; + Function::arg_iterator AI = F->arg_begin(); ++AI; + for (unsigned N = FT->getNumParams(); N != 0; ++AI, --N) + Args.push_back(&*AI); + CallInst *CI = + CallInst::Create(&F->getArgumentList().front(), Args, "", BB); + ReturnInst *RI; + if (FT->getReturnType()->isVoidTy()) + RI = ReturnInst::Create(*Ctx, BB); + else + RI = ReturnInst::Create(*Ctx, CI, BB); + + DFSanFunction DFSF(*this, F, /*IsNativeABI=*/true); + Function::arg_iterator ValAI = F->arg_begin(), ShadowAI = AI; ++ValAI; + for (unsigned N = FT->getNumParams(); N != 0; ++ValAI, ++ShadowAI, --N) + DFSF.ValShadowMap[ValAI] = ShadowAI; + DFSanVisitor(DFSF).visitCallInst(*CI); + if (!FT->getReturnType()->isVoidTy()) + new StoreInst(DFSF.getShadow(RI->getReturnValue()), + &F->getArgumentList().back(), RI); + } + + return C; +} + +bool DataFlowSanitizer::runOnModule(Module &M) { + if (!DL) + return false; + + if (ABIList->isIn(M, "skip")) + return false; + + if (!GetArgTLSPtr) { + Type *ArgTLSTy = ArrayType::get(ShadowTy, 64); + ArgTLS = Mod->getOrInsertGlobal("__dfsan_arg_tls", ArgTLSTy); + if (GlobalVariable *G = dyn_cast<GlobalVariable>(ArgTLS)) + G->setThreadLocalMode(GlobalVariable::InitialExecTLSModel); + } + if (!GetRetvalTLSPtr) { + RetvalTLS = Mod->getOrInsertGlobal("__dfsan_retval_tls", ShadowTy); + if (GlobalVariable *G = dyn_cast<GlobalVariable>(RetvalTLS)) + G->setThreadLocalMode(GlobalVariable::InitialExecTLSModel); + } + + DFSanUnionFn = Mod->getOrInsertFunction("__dfsan_union", DFSanUnionFnTy); + if (Function *F = dyn_cast<Function>(DFSanUnionFn)) { + F->addAttribute(AttributeSet::FunctionIndex, Attribute::ReadNone); + F->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt); + F->addAttribute(1, Attribute::ZExt); + F->addAttribute(2, Attribute::ZExt); + } + DFSanUnionLoadFn = + Mod->getOrInsertFunction("__dfsan_union_load", DFSanUnionLoadFnTy); + if (Function *F = dyn_cast<Function>(DFSanUnionLoadFn)) { + F->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt); + } + DFSanUnimplementedFn = + Mod->getOrInsertFunction("__dfsan_unimplemented", DFSanUnimplementedFnTy); + DFSanSetLabelFn = + Mod->getOrInsertFunction("__dfsan_set_label", DFSanSetLabelFnTy); + if (Function *F = dyn_cast<Function>(DFSanSetLabelFn)) { + F->addAttribute(1, Attribute::ZExt); + } + DFSanNonzeroLabelFn = + Mod->getOrInsertFunction("__dfsan_nonzero_label", DFSanNonzeroLabelFnTy); + + std::vector<Function *> FnsToInstrument; + llvm::SmallPtrSet<Function *, 2> FnsWithNativeABI; + for (Module::iterator i = M.begin(), e = M.end(); i != e; ++i) { + if (!i->isIntrinsic() && + i != DFSanUnionFn && + i != DFSanUnionLoadFn && + i != DFSanUnimplementedFn && + i != DFSanSetLabelFn && + i != DFSanNonzeroLabelFn) + FnsToInstrument.push_back(&*i); + } + + // Give function aliases prefixes when necessary, and build wrappers where the + // instrumentedness is inconsistent. + for (Module::alias_iterator i = M.alias_begin(), e = M.alias_end(); i != e;) { + GlobalAlias *GA = &*i; + ++i; + // Don't stop on weak. We assume people aren't playing games with the + // instrumentedness of overridden weak aliases. + if (Function *F = dyn_cast<Function>( + GA->resolveAliasedGlobal(/*stopOnWeak=*/false))) { + bool GAInst = isInstrumented(GA), FInst = isInstrumented(F); + if (GAInst && FInst) { + addGlobalNamePrefix(GA); + } else if (GAInst != FInst) { + // Non-instrumented alias of an instrumented function, or vice versa. + // Replace the alias with a native-ABI wrapper of the aliasee. The pass + // below will take care of instrumenting it. + Function *NewF = + buildWrapperFunction(F, "", GA->getLinkage(), F->getFunctionType()); + GA->replaceAllUsesWith(NewF); + NewF->takeName(GA); + GA->eraseFromParent(); + FnsToInstrument.push_back(NewF); + } + } + } + + AttrBuilder B; + B.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone); + ReadOnlyNoneAttrs = AttributeSet::get(*Ctx, AttributeSet::FunctionIndex, B); + + // First, change the ABI of every function in the module. ABI-listed + // functions keep their original ABI and get a wrapper function. + for (std::vector<Function *>::iterator i = FnsToInstrument.begin(), + e = FnsToInstrument.end(); + i != e; ++i) { + Function &F = **i; + FunctionType *FT = F.getFunctionType(); + + bool IsZeroArgsVoidRet = (FT->getNumParams() == 0 && !FT->isVarArg() && + FT->getReturnType()->isVoidTy()); + + if (isInstrumented(&F)) { + // Instrumented functions get a 'dfs$' prefix. This allows us to more + // easily identify cases of mismatching ABIs. + if (getInstrumentedABI() == IA_Args && !IsZeroArgsVoidRet) { + FunctionType *NewFT = getArgsFunctionType(FT); + Function *NewF = Function::Create(NewFT, F.getLinkage(), "", &M); + NewF->copyAttributesFrom(&F); + NewF->removeAttributes( + AttributeSet::ReturnIndex, + AttributeFuncs::typeIncompatible(NewFT->getReturnType(), + AttributeSet::ReturnIndex)); + for (Function::arg_iterator FArg = F.arg_begin(), + NewFArg = NewF->arg_begin(), + FArgEnd = F.arg_end(); + FArg != FArgEnd; ++FArg, ++NewFArg) { + FArg->replaceAllUsesWith(NewFArg); + } + NewF->getBasicBlockList().splice(NewF->begin(), F.getBasicBlockList()); + + for (Function::use_iterator ui = F.use_begin(), ue = F.use_end(); + ui != ue;) { + BlockAddress *BA = dyn_cast<BlockAddress>(ui.getUse().getUser()); + ++ui; + if (BA) { + BA->replaceAllUsesWith( + BlockAddress::get(NewF, BA->getBasicBlock())); + delete BA; + } + } + F.replaceAllUsesWith( + ConstantExpr::getBitCast(NewF, PointerType::getUnqual(FT))); + NewF->takeName(&F); + F.eraseFromParent(); + *i = NewF; + addGlobalNamePrefix(NewF); + } else { + addGlobalNamePrefix(&F); + } + // Hopefully, nobody will try to indirectly call a vararg + // function... yet. + } else if (FT->isVarArg()) { + UnwrappedFnMap[&F] = &F; + *i = 0; + } else if (!IsZeroArgsVoidRet || getWrapperKind(&F) == WK_Custom) { + // Build a wrapper function for F. The wrapper simply calls F, and is + // added to FnsToInstrument so that any instrumentation according to its + // WrapperKind is done in the second pass below. + FunctionType *NewFT = getInstrumentedABI() == IA_Args + ? getArgsFunctionType(FT) + : FT; + Function *NewF = buildWrapperFunction( + &F, std::string("dfsw$") + std::string(F.getName()), + GlobalValue::LinkOnceODRLinkage, NewFT); + if (getInstrumentedABI() == IA_TLS) + NewF->removeAttributes(AttributeSet::FunctionIndex, ReadOnlyNoneAttrs); + + Value *WrappedFnCst = + ConstantExpr::getBitCast(NewF, PointerType::getUnqual(FT)); + F.replaceAllUsesWith(WrappedFnCst); + UnwrappedFnMap[WrappedFnCst] = &F; + *i = NewF; + + if (!F.isDeclaration()) { + // This function is probably defining an interposition of an + // uninstrumented function and hence needs to keep the original ABI. + // But any functions it may call need to use the instrumented ABI, so + // we instrument it in a mode which preserves the original ABI. + FnsWithNativeABI.insert(&F); + + // This code needs to rebuild the iterators, as they may be invalidated + // by the push_back, taking care that the new range does not include + // any functions added by this code. + size_t N = i - FnsToInstrument.begin(), + Count = e - FnsToInstrument.begin(); + FnsToInstrument.push_back(&F); + i = FnsToInstrument.begin() + N; + e = FnsToInstrument.begin() + Count; + } + } + } + + for (std::vector<Function *>::iterator i = FnsToInstrument.begin(), + e = FnsToInstrument.end(); + i != e; ++i) { + if (!*i || (*i)->isDeclaration()) + continue; + + removeUnreachableBlocks(**i); + + DFSanFunction DFSF(*this, *i, FnsWithNativeABI.count(*i)); + + // DFSanVisitor may create new basic blocks, which confuses df_iterator. + // Build a copy of the list before iterating over it. + llvm::SmallVector<BasicBlock *, 4> BBList; + std::copy(df_begin(&(*i)->getEntryBlock()), df_end(&(*i)->getEntryBlock()), + std::back_inserter(BBList)); + + for (llvm::SmallVector<BasicBlock *, 4>::iterator i = BBList.begin(), + e = BBList.end(); + i != e; ++i) { + Instruction *Inst = &(*i)->front(); + while (1) { + // DFSanVisitor may split the current basic block, changing the current + // instruction's next pointer and moving the next instruction to the + // tail block from which we should continue. + Instruction *Next = Inst->getNextNode(); + // DFSanVisitor may delete Inst, so keep track of whether it was a + // terminator. + bool IsTerminator = isa<TerminatorInst>(Inst); + if (!DFSF.SkipInsts.count(Inst)) + DFSanVisitor(DFSF).visit(Inst); + if (IsTerminator) + break; + Inst = Next; + } + } + + // We will not necessarily be able to compute the shadow for every phi node + // until we have visited every block. Therefore, the code that handles phi + // nodes adds them to the PHIFixups list so that they can be properly + // handled here. + for (std::vector<std::pair<PHINode *, PHINode *> >::iterator + i = DFSF.PHIFixups.begin(), + e = DFSF.PHIFixups.end(); + i != e; ++i) { + for (unsigned val = 0, n = i->first->getNumIncomingValues(); val != n; + ++val) { + i->second->setIncomingValue( + val, DFSF.getShadow(i->first->getIncomingValue(val))); + } + } + + // -dfsan-debug-nonzero-labels will split the CFG in all kinds of crazy + // places (i.e. instructions in basic blocks we haven't even begun visiting + // yet). To make our life easier, do this work in a pass after the main + // instrumentation. + if (ClDebugNonzeroLabels) { + for (DenseSet<Value *>::iterator i = DFSF.NonZeroChecks.begin(), + e = DFSF.NonZeroChecks.end(); + i != e; ++i) { + Instruction *Pos; + if (Instruction *I = dyn_cast<Instruction>(*i)) + Pos = I->getNextNode(); + else + Pos = DFSF.F->getEntryBlock().begin(); + while (isa<PHINode>(Pos) || isa<AllocaInst>(Pos)) + Pos = Pos->getNextNode(); + IRBuilder<> IRB(Pos); + Instruction *NeInst = cast<Instruction>( + IRB.CreateICmpNE(*i, DFSF.DFS.ZeroShadow)); + BranchInst *BI = cast<BranchInst>(SplitBlockAndInsertIfThen( + NeInst, /*Unreachable=*/ false, ColdCallWeights)); + IRBuilder<> ThenIRB(BI); + ThenIRB.CreateCall(DFSF.DFS.DFSanNonzeroLabelFn); + } + } + } + + return false; +} + +Value *DFSanFunction::getArgTLSPtr() { + if (ArgTLSPtr) + return ArgTLSPtr; + if (DFS.ArgTLS) + return ArgTLSPtr = DFS.ArgTLS; + + IRBuilder<> IRB(F->getEntryBlock().begin()); + return ArgTLSPtr = IRB.CreateCall(DFS.GetArgTLS); +} + +Value *DFSanFunction::getRetvalTLS() { + if (RetvalTLSPtr) + return RetvalTLSPtr; + if (DFS.RetvalTLS) + return RetvalTLSPtr = DFS.RetvalTLS; + + IRBuilder<> IRB(F->getEntryBlock().begin()); + return RetvalTLSPtr = IRB.CreateCall(DFS.GetRetvalTLS); +} + +Value *DFSanFunction::getArgTLS(unsigned Idx, Instruction *Pos) { + IRBuilder<> IRB(Pos); + return IRB.CreateConstGEP2_64(getArgTLSPtr(), 0, Idx); +} + +Value *DFSanFunction::getShadow(Value *V) { + if (!isa<Argument>(V) && !isa<Instruction>(V)) + return DFS.ZeroShadow; + Value *&Shadow = ValShadowMap[V]; + if (!Shadow) { + if (Argument *A = dyn_cast<Argument>(V)) { + if (IsNativeABI) + return DFS.ZeroShadow; + switch (IA) { + case DataFlowSanitizer::IA_TLS: { + Value *ArgTLSPtr = getArgTLSPtr(); + Instruction *ArgTLSPos = + DFS.ArgTLS ? &*F->getEntryBlock().begin() + : cast<Instruction>(ArgTLSPtr)->getNextNode(); + IRBuilder<> IRB(ArgTLSPos); + Shadow = IRB.CreateLoad(getArgTLS(A->getArgNo(), ArgTLSPos)); + break; + } + case DataFlowSanitizer::IA_Args: { + unsigned ArgIdx = A->getArgNo() + F->getArgumentList().size() / 2; + Function::arg_iterator i = F->arg_begin(); + while (ArgIdx--) + ++i; + Shadow = i; + assert(Shadow->getType() == DFS.ShadowTy); + break; + } + } + NonZeroChecks.insert(Shadow); + } else { + Shadow = DFS.ZeroShadow; + } + } + return Shadow; +} + +void DFSanFunction::setShadow(Instruction *I, Value *Shadow) { + assert(!ValShadowMap.count(I)); + assert(Shadow->getType() == DFS.ShadowTy); + ValShadowMap[I] = Shadow; +} + +Value *DataFlowSanitizer::getShadowAddress(Value *Addr, Instruction *Pos) { + assert(Addr != RetvalTLS && "Reinstrumenting?"); + IRBuilder<> IRB(Pos); + return IRB.CreateIntToPtr( + IRB.CreateMul( + IRB.CreateAnd(IRB.CreatePtrToInt(Addr, IntptrTy), ShadowPtrMask), + ShadowPtrMul), + ShadowPtrTy); +} + +// Generates IR to compute the union of the two given shadows, inserting it +// before Pos. Returns the computed union Value. +Value *DataFlowSanitizer::combineShadows(Value *V1, Value *V2, + Instruction *Pos) { + if (V1 == ZeroShadow) + return V2; + if (V2 == ZeroShadow) + return V1; + if (V1 == V2) + return V1; + IRBuilder<> IRB(Pos); + BasicBlock *Head = Pos->getParent(); + Value *Ne = IRB.CreateICmpNE(V1, V2); + Instruction *NeInst = dyn_cast<Instruction>(Ne); + if (NeInst) { + BranchInst *BI = cast<BranchInst>(SplitBlockAndInsertIfThen( + NeInst, /*Unreachable=*/ false, ColdCallWeights)); + IRBuilder<> ThenIRB(BI); + CallInst *Call = ThenIRB.CreateCall2(DFSanUnionFn, V1, V2); + Call->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt); + Call->addAttribute(1, Attribute::ZExt); + Call->addAttribute(2, Attribute::ZExt); + + BasicBlock *Tail = BI->getSuccessor(0); + PHINode *Phi = PHINode::Create(ShadowTy, 2, "", Tail->begin()); + Phi->addIncoming(Call, Call->getParent()); + Phi->addIncoming(V1, Head); + Pos = Phi; + return Phi; + } else { + assert(0 && "todo"); + return 0; + } +} + +// A convenience function which folds the shadows of each of the operands +// of the provided instruction Inst, inserting the IR before Inst. Returns +// the computed union Value. +Value *DFSanFunction::combineOperandShadows(Instruction *Inst) { + if (Inst->getNumOperands() == 0) + return DFS.ZeroShadow; + + Value *Shadow = getShadow(Inst->getOperand(0)); + for (unsigned i = 1, n = Inst->getNumOperands(); i != n; ++i) { + Shadow = DFS.combineShadows(Shadow, getShadow(Inst->getOperand(i)), Inst); + } + return Shadow; +} + +void DFSanVisitor::visitOperandShadowInst(Instruction &I) { + Value *CombinedShadow = DFSF.combineOperandShadows(&I); + DFSF.setShadow(&I, CombinedShadow); +} + +// Generates IR to load shadow corresponding to bytes [Addr, Addr+Size), where +// Addr has alignment Align, and take the union of each of those shadows. +Value *DFSanFunction::loadShadow(Value *Addr, uint64_t Size, uint64_t Align, + Instruction *Pos) { + if (AllocaInst *AI = dyn_cast<AllocaInst>(Addr)) { + llvm::DenseMap<AllocaInst *, AllocaInst *>::iterator i = + AllocaShadowMap.find(AI); + if (i != AllocaShadowMap.end()) { + IRBuilder<> IRB(Pos); + return IRB.CreateLoad(i->second); + } + } + + uint64_t ShadowAlign = Align * DFS.ShadowWidth / 8; + SmallVector<Value *, 2> Objs; + GetUnderlyingObjects(Addr, Objs, DFS.DL); + bool AllConstants = true; + for (SmallVector<Value *, 2>::iterator i = Objs.begin(), e = Objs.end(); + i != e; ++i) { + if (isa<Function>(*i) || isa<BlockAddress>(*i)) + continue; + if (isa<GlobalVariable>(*i) && cast<GlobalVariable>(*i)->isConstant()) + continue; + + AllConstants = false; + break; + } + if (AllConstants) + return DFS.ZeroShadow; + + Value *ShadowAddr = DFS.getShadowAddress(Addr, Pos); + switch (Size) { + case 0: + return DFS.ZeroShadow; + case 1: { + LoadInst *LI = new LoadInst(ShadowAddr, "", Pos); + LI->setAlignment(ShadowAlign); + return LI; + } + case 2: { + IRBuilder<> IRB(Pos); + Value *ShadowAddr1 = + IRB.CreateGEP(ShadowAddr, ConstantInt::get(DFS.IntptrTy, 1)); + return DFS.combineShadows(IRB.CreateAlignedLoad(ShadowAddr, ShadowAlign), + IRB.CreateAlignedLoad(ShadowAddr1, ShadowAlign), + Pos); + } + } + if (Size % (64 / DFS.ShadowWidth) == 0) { + // Fast path for the common case where each byte has identical shadow: load + // shadow 64 bits at a time, fall out to a __dfsan_union_load call if any + // shadow is non-equal. + BasicBlock *FallbackBB = BasicBlock::Create(*DFS.Ctx, "", F); + IRBuilder<> FallbackIRB(FallbackBB); + CallInst *FallbackCall = FallbackIRB.CreateCall2( + DFS.DFSanUnionLoadFn, ShadowAddr, ConstantInt::get(DFS.IntptrTy, Size)); + FallbackCall->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt); + + // Compare each of the shadows stored in the loaded 64 bits to each other, + // by computing (WideShadow rotl ShadowWidth) == WideShadow. + IRBuilder<> IRB(Pos); + Value *WideAddr = + IRB.CreateBitCast(ShadowAddr, Type::getInt64PtrTy(*DFS.Ctx)); + Value *WideShadow = IRB.CreateAlignedLoad(WideAddr, ShadowAlign); + Value *TruncShadow = IRB.CreateTrunc(WideShadow, DFS.ShadowTy); + Value *ShlShadow = IRB.CreateShl(WideShadow, DFS.ShadowWidth); + Value *ShrShadow = IRB.CreateLShr(WideShadow, 64 - DFS.ShadowWidth); + Value *RotShadow = IRB.CreateOr(ShlShadow, ShrShadow); + Value *ShadowsEq = IRB.CreateICmpEQ(WideShadow, RotShadow); + + BasicBlock *Head = Pos->getParent(); + BasicBlock *Tail = Head->splitBasicBlock(Pos); + // In the following code LastBr will refer to the previous basic block's + // conditional branch instruction, whose true successor is fixed up to point + // to the next block during the loop below or to the tail after the final + // iteration. + BranchInst *LastBr = BranchInst::Create(FallbackBB, FallbackBB, ShadowsEq); + ReplaceInstWithInst(Head->getTerminator(), LastBr); + + for (uint64_t Ofs = 64 / DFS.ShadowWidth; Ofs != Size; + Ofs += 64 / DFS.ShadowWidth) { + BasicBlock *NextBB = BasicBlock::Create(*DFS.Ctx, "", F); + IRBuilder<> NextIRB(NextBB); + WideAddr = NextIRB.CreateGEP(WideAddr, ConstantInt::get(DFS.IntptrTy, 1)); + Value *NextWideShadow = NextIRB.CreateAlignedLoad(WideAddr, ShadowAlign); + ShadowsEq = NextIRB.CreateICmpEQ(WideShadow, NextWideShadow); + LastBr->setSuccessor(0, NextBB); + LastBr = NextIRB.CreateCondBr(ShadowsEq, FallbackBB, FallbackBB); + } + + LastBr->setSuccessor(0, Tail); + FallbackIRB.CreateBr(Tail); + PHINode *Shadow = PHINode::Create(DFS.ShadowTy, 2, "", &Tail->front()); + Shadow->addIncoming(FallbackCall, FallbackBB); + Shadow->addIncoming(TruncShadow, LastBr->getParent()); + return Shadow; + } + + IRBuilder<> IRB(Pos); + CallInst *FallbackCall = IRB.CreateCall2( + DFS.DFSanUnionLoadFn, ShadowAddr, ConstantInt::get(DFS.IntptrTy, Size)); + FallbackCall->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt); + return FallbackCall; +} + +void DFSanVisitor::visitLoadInst(LoadInst &LI) { + uint64_t Size = DFSF.DFS.DL->getTypeStoreSize(LI.getType()); + uint64_t Align; + if (ClPreserveAlignment) { + Align = LI.getAlignment(); + if (Align == 0) + Align = DFSF.DFS.DL->getABITypeAlignment(LI.getType()); + } else { + Align = 1; + } + IRBuilder<> IRB(&LI); + Value *LoadedShadow = + DFSF.loadShadow(LI.getPointerOperand(), Size, Align, &LI); + Value *PtrShadow = DFSF.getShadow(LI.getPointerOperand()); + Value *CombinedShadow = DFSF.DFS.combineShadows(LoadedShadow, PtrShadow, &LI); + if (CombinedShadow != DFSF.DFS.ZeroShadow) + DFSF.NonZeroChecks.insert(CombinedShadow); + + DFSF.setShadow(&LI, CombinedShadow); +} + +void DFSanFunction::storeShadow(Value *Addr, uint64_t Size, uint64_t Align, + Value *Shadow, Instruction *Pos) { + if (AllocaInst *AI = dyn_cast<AllocaInst>(Addr)) { + llvm::DenseMap<AllocaInst *, AllocaInst *>::iterator i = + AllocaShadowMap.find(AI); + if (i != AllocaShadowMap.end()) { + IRBuilder<> IRB(Pos); + IRB.CreateStore(Shadow, i->second); + return; + } + } + + uint64_t ShadowAlign = Align * DFS.ShadowWidth / 8; + IRBuilder<> IRB(Pos); + Value *ShadowAddr = DFS.getShadowAddress(Addr, Pos); + if (Shadow == DFS.ZeroShadow) { + IntegerType *ShadowTy = IntegerType::get(*DFS.Ctx, Size * DFS.ShadowWidth); + Value *ExtZeroShadow = ConstantInt::get(ShadowTy, 0); + Value *ExtShadowAddr = + IRB.CreateBitCast(ShadowAddr, PointerType::getUnqual(ShadowTy)); + IRB.CreateAlignedStore(ExtZeroShadow, ExtShadowAddr, ShadowAlign); + return; + } + + const unsigned ShadowVecSize = 128 / DFS.ShadowWidth; + uint64_t Offset = 0; + if (Size >= ShadowVecSize) { + VectorType *ShadowVecTy = VectorType::get(DFS.ShadowTy, ShadowVecSize); + Value *ShadowVec = UndefValue::get(ShadowVecTy); + for (unsigned i = 0; i != ShadowVecSize; ++i) { + ShadowVec = IRB.CreateInsertElement( + ShadowVec, Shadow, ConstantInt::get(Type::getInt32Ty(*DFS.Ctx), i)); + } + Value *ShadowVecAddr = + IRB.CreateBitCast(ShadowAddr, PointerType::getUnqual(ShadowVecTy)); + do { + Value *CurShadowVecAddr = IRB.CreateConstGEP1_32(ShadowVecAddr, Offset); + IRB.CreateAlignedStore(ShadowVec, CurShadowVecAddr, ShadowAlign); + Size -= ShadowVecSize; + ++Offset; + } while (Size >= ShadowVecSize); + Offset *= ShadowVecSize; + } + while (Size > 0) { + Value *CurShadowAddr = IRB.CreateConstGEP1_32(ShadowAddr, Offset); + IRB.CreateAlignedStore(Shadow, CurShadowAddr, ShadowAlign); + --Size; + ++Offset; + } +} + +void DFSanVisitor::visitStoreInst(StoreInst &SI) { + uint64_t Size = + DFSF.DFS.DL->getTypeStoreSize(SI.getValueOperand()->getType()); + uint64_t Align; + if (ClPreserveAlignment) { + Align = SI.getAlignment(); + if (Align == 0) + Align = DFSF.DFS.DL->getABITypeAlignment(SI.getValueOperand()->getType()); + } else { + Align = 1; + } + DFSF.storeShadow(SI.getPointerOperand(), Size, Align, + DFSF.getShadow(SI.getValueOperand()), &SI); +} + +void DFSanVisitor::visitBinaryOperator(BinaryOperator &BO) { + visitOperandShadowInst(BO); +} + +void DFSanVisitor::visitCastInst(CastInst &CI) { visitOperandShadowInst(CI); } + +void DFSanVisitor::visitCmpInst(CmpInst &CI) { visitOperandShadowInst(CI); } + +void DFSanVisitor::visitGetElementPtrInst(GetElementPtrInst &GEPI) { + visitOperandShadowInst(GEPI); +} + +void DFSanVisitor::visitExtractElementInst(ExtractElementInst &I) { + visitOperandShadowInst(I); +} + +void DFSanVisitor::visitInsertElementInst(InsertElementInst &I) { + visitOperandShadowInst(I); +} + +void DFSanVisitor::visitShuffleVectorInst(ShuffleVectorInst &I) { + visitOperandShadowInst(I); +} + +void DFSanVisitor::visitExtractValueInst(ExtractValueInst &I) { + visitOperandShadowInst(I); +} + +void DFSanVisitor::visitInsertValueInst(InsertValueInst &I) { + visitOperandShadowInst(I); +} + +void DFSanVisitor::visitAllocaInst(AllocaInst &I) { + bool AllLoadsStores = true; + for (Instruction::use_iterator i = I.use_begin(), e = I.use_end(); i != e; + ++i) { + if (isa<LoadInst>(*i)) + continue; + + if (StoreInst *SI = dyn_cast<StoreInst>(*i)) { + if (SI->getPointerOperand() == &I) + continue; + } + + AllLoadsStores = false; + break; + } + if (AllLoadsStores) { + IRBuilder<> IRB(&I); + DFSF.AllocaShadowMap[&I] = IRB.CreateAlloca(DFSF.DFS.ShadowTy); + } + DFSF.setShadow(&I, DFSF.DFS.ZeroShadow); +} + +void DFSanVisitor::visitSelectInst(SelectInst &I) { + Value *CondShadow = DFSF.getShadow(I.getCondition()); + Value *TrueShadow = DFSF.getShadow(I.getTrueValue()); + Value *FalseShadow = DFSF.getShadow(I.getFalseValue()); + + if (isa<VectorType>(I.getCondition()->getType())) { + DFSF.setShadow( + &I, DFSF.DFS.combineShadows( + CondShadow, + DFSF.DFS.combineShadows(TrueShadow, FalseShadow, &I), &I)); + } else { + Value *ShadowSel; + if (TrueShadow == FalseShadow) { + ShadowSel = TrueShadow; + } else { + ShadowSel = + SelectInst::Create(I.getCondition(), TrueShadow, FalseShadow, "", &I); + } + DFSF.setShadow(&I, DFSF.DFS.combineShadows(CondShadow, ShadowSel, &I)); + } +} + +void DFSanVisitor::visitMemSetInst(MemSetInst &I) { + IRBuilder<> IRB(&I); + Value *ValShadow = DFSF.getShadow(I.getValue()); + IRB.CreateCall3( + DFSF.DFS.DFSanSetLabelFn, ValShadow, + IRB.CreateBitCast(I.getDest(), Type::getInt8PtrTy(*DFSF.DFS.Ctx)), + IRB.CreateZExtOrTrunc(I.getLength(), DFSF.DFS.IntptrTy)); +} + +void DFSanVisitor::visitMemTransferInst(MemTransferInst &I) { + IRBuilder<> IRB(&I); + Value *DestShadow = DFSF.DFS.getShadowAddress(I.getDest(), &I); + Value *SrcShadow = DFSF.DFS.getShadowAddress(I.getSource(), &I); + Value *LenShadow = IRB.CreateMul( + I.getLength(), + ConstantInt::get(I.getLength()->getType(), DFSF.DFS.ShadowWidth / 8)); + Value *AlignShadow; + if (ClPreserveAlignment) { + AlignShadow = IRB.CreateMul(I.getAlignmentCst(), + ConstantInt::get(I.getAlignmentCst()->getType(), + DFSF.DFS.ShadowWidth / 8)); + } else { + AlignShadow = ConstantInt::get(I.getAlignmentCst()->getType(), + DFSF.DFS.ShadowWidth / 8); + } + Type *Int8Ptr = Type::getInt8PtrTy(*DFSF.DFS.Ctx); + DestShadow = IRB.CreateBitCast(DestShadow, Int8Ptr); + SrcShadow = IRB.CreateBitCast(SrcShadow, Int8Ptr); + IRB.CreateCall5(I.getCalledValue(), DestShadow, SrcShadow, LenShadow, + AlignShadow, I.getVolatileCst()); +} + +void DFSanVisitor::visitReturnInst(ReturnInst &RI) { + if (!DFSF.IsNativeABI && RI.getReturnValue()) { + switch (DFSF.IA) { + case DataFlowSanitizer::IA_TLS: { + Value *S = DFSF.getShadow(RI.getReturnValue()); + IRBuilder<> IRB(&RI); + IRB.CreateStore(S, DFSF.getRetvalTLS()); + break; + } + case DataFlowSanitizer::IA_Args: { + IRBuilder<> IRB(&RI); + Type *RT = DFSF.F->getFunctionType()->getReturnType(); + Value *InsVal = + IRB.CreateInsertValue(UndefValue::get(RT), RI.getReturnValue(), 0); + Value *InsShadow = + IRB.CreateInsertValue(InsVal, DFSF.getShadow(RI.getReturnValue()), 1); + RI.setOperand(0, InsShadow); + break; + } + } + } +} + +void DFSanVisitor::visitCallSite(CallSite CS) { + Function *F = CS.getCalledFunction(); + if ((F && F->isIntrinsic()) || isa<InlineAsm>(CS.getCalledValue())) { + visitOperandShadowInst(*CS.getInstruction()); + return; + } + + IRBuilder<> IRB(CS.getInstruction()); + + DenseMap<Value *, Function *>::iterator i = + DFSF.DFS.UnwrappedFnMap.find(CS.getCalledValue()); + if (i != DFSF.DFS.UnwrappedFnMap.end()) { + Function *F = i->second; + switch (DFSF.DFS.getWrapperKind(F)) { + case DataFlowSanitizer::WK_Warning: { + CS.setCalledFunction(F); + IRB.CreateCall(DFSF.DFS.DFSanUnimplementedFn, + IRB.CreateGlobalStringPtr(F->getName())); + DFSF.setShadow(CS.getInstruction(), DFSF.DFS.ZeroShadow); + return; + } + case DataFlowSanitizer::WK_Discard: { + CS.setCalledFunction(F); + DFSF.setShadow(CS.getInstruction(), DFSF.DFS.ZeroShadow); + return; + } + case DataFlowSanitizer::WK_Functional: { + CS.setCalledFunction(F); + visitOperandShadowInst(*CS.getInstruction()); + return; + } + case DataFlowSanitizer::WK_Custom: { + // Don't try to handle invokes of custom functions, it's too complicated. + // Instead, invoke the dfsw$ wrapper, which will in turn call the __dfsw_ + // wrapper. + if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) { + FunctionType *FT = F->getFunctionType(); + FunctionType *CustomFT = DFSF.DFS.getCustomFunctionType(FT); + std::string CustomFName = "__dfsw_"; + CustomFName += F->getName(); + Constant *CustomF = + DFSF.DFS.Mod->getOrInsertFunction(CustomFName, CustomFT); + if (Function *CustomFn = dyn_cast<Function>(CustomF)) { + CustomFn->copyAttributesFrom(F); + + // Custom functions returning non-void will write to the return label. + if (!FT->getReturnType()->isVoidTy()) { + CustomFn->removeAttributes(AttributeSet::FunctionIndex, + DFSF.DFS.ReadOnlyNoneAttrs); + } + } + + std::vector<Value *> Args; + + CallSite::arg_iterator i = CS.arg_begin(); + for (unsigned n = FT->getNumParams(); n != 0; ++i, --n) { + Type *T = (*i)->getType(); + FunctionType *ParamFT; + if (isa<PointerType>(T) && + (ParamFT = dyn_cast<FunctionType>( + cast<PointerType>(T)->getElementType()))) { + std::string TName = "dfst"; + TName += utostr(FT->getNumParams() - n); + TName += "$"; + TName += F->getName(); + Constant *T = DFSF.DFS.getOrBuildTrampolineFunction(ParamFT, TName); + Args.push_back(T); + Args.push_back( + IRB.CreateBitCast(*i, Type::getInt8PtrTy(*DFSF.DFS.Ctx))); + } else { + Args.push_back(*i); + } + } + + i = CS.arg_begin(); + for (unsigned n = FT->getNumParams(); n != 0; ++i, --n) + Args.push_back(DFSF.getShadow(*i)); + + if (!FT->getReturnType()->isVoidTy()) { + if (!DFSF.LabelReturnAlloca) { + DFSF.LabelReturnAlloca = + new AllocaInst(DFSF.DFS.ShadowTy, "labelreturn", + DFSF.F->getEntryBlock().begin()); + } + Args.push_back(DFSF.LabelReturnAlloca); + } + + CallInst *CustomCI = IRB.CreateCall(CustomF, Args); + CustomCI->setCallingConv(CI->getCallingConv()); + CustomCI->setAttributes(CI->getAttributes()); + + if (!FT->getReturnType()->isVoidTy()) { + LoadInst *LabelLoad = IRB.CreateLoad(DFSF.LabelReturnAlloca); + DFSF.setShadow(CustomCI, LabelLoad); + } + + CI->replaceAllUsesWith(CustomCI); + CI->eraseFromParent(); + return; + } + break; + } + } + } + + FunctionType *FT = cast<FunctionType>( + CS.getCalledValue()->getType()->getPointerElementType()); + if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_TLS) { + for (unsigned i = 0, n = FT->getNumParams(); i != n; ++i) { + IRB.CreateStore(DFSF.getShadow(CS.getArgument(i)), + DFSF.getArgTLS(i, CS.getInstruction())); + } + } + + Instruction *Next = 0; + if (!CS.getType()->isVoidTy()) { + if (InvokeInst *II = dyn_cast<InvokeInst>(CS.getInstruction())) { + if (II->getNormalDest()->getSinglePredecessor()) { + Next = II->getNormalDest()->begin(); + } else { + BasicBlock *NewBB = + SplitEdge(II->getParent(), II->getNormalDest(), &DFSF.DFS); + Next = NewBB->begin(); + } + } else { + Next = CS->getNextNode(); + } + + if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_TLS) { + IRBuilder<> NextIRB(Next); + LoadInst *LI = NextIRB.CreateLoad(DFSF.getRetvalTLS()); + DFSF.SkipInsts.insert(LI); + DFSF.setShadow(CS.getInstruction(), LI); + DFSF.NonZeroChecks.insert(LI); + } + } + + // Do all instrumentation for IA_Args down here to defer tampering with the + // CFG in a way that SplitEdge may be able to detect. + if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_Args) { + FunctionType *NewFT = DFSF.DFS.getArgsFunctionType(FT); + Value *Func = + IRB.CreateBitCast(CS.getCalledValue(), PointerType::getUnqual(NewFT)); + std::vector<Value *> Args; + + CallSite::arg_iterator i = CS.arg_begin(), e = CS.arg_end(); + for (unsigned n = FT->getNumParams(); n != 0; ++i, --n) + Args.push_back(*i); + + i = CS.arg_begin(); + for (unsigned n = FT->getNumParams(); n != 0; ++i, --n) + Args.push_back(DFSF.getShadow(*i)); + + if (FT->isVarArg()) { + unsigned VarArgSize = CS.arg_size() - FT->getNumParams(); + ArrayType *VarArgArrayTy = ArrayType::get(DFSF.DFS.ShadowTy, VarArgSize); + AllocaInst *VarArgShadow = + new AllocaInst(VarArgArrayTy, "", DFSF.F->getEntryBlock().begin()); + Args.push_back(IRB.CreateConstGEP2_32(VarArgShadow, 0, 0)); + for (unsigned n = 0; i != e; ++i, ++n) { + IRB.CreateStore(DFSF.getShadow(*i), + IRB.CreateConstGEP2_32(VarArgShadow, 0, n)); + Args.push_back(*i); + } + } + + CallSite NewCS; + if (InvokeInst *II = dyn_cast<InvokeInst>(CS.getInstruction())) { + NewCS = IRB.CreateInvoke(Func, II->getNormalDest(), II->getUnwindDest(), + Args); + } else { + NewCS = IRB.CreateCall(Func, Args); + } + NewCS.setCallingConv(CS.getCallingConv()); + NewCS.setAttributes(CS.getAttributes().removeAttributes( + *DFSF.DFS.Ctx, AttributeSet::ReturnIndex, + AttributeFuncs::typeIncompatible(NewCS.getInstruction()->getType(), + AttributeSet::ReturnIndex))); + + if (Next) { + ExtractValueInst *ExVal = + ExtractValueInst::Create(NewCS.getInstruction(), 0, "", Next); + DFSF.SkipInsts.insert(ExVal); + ExtractValueInst *ExShadow = + ExtractValueInst::Create(NewCS.getInstruction(), 1, "", Next); + DFSF.SkipInsts.insert(ExShadow); + DFSF.setShadow(ExVal, ExShadow); + DFSF.NonZeroChecks.insert(ExShadow); + + CS.getInstruction()->replaceAllUsesWith(ExVal); + } + + CS.getInstruction()->eraseFromParent(); + } +} + +void DFSanVisitor::visitPHINode(PHINode &PN) { + PHINode *ShadowPN = + PHINode::Create(DFSF.DFS.ShadowTy, PN.getNumIncomingValues(), "", &PN); + + // Give the shadow phi node valid predecessors to fool SplitEdge into working. + Value *UndefShadow = UndefValue::get(DFSF.DFS.ShadowTy); + for (PHINode::block_iterator i = PN.block_begin(), e = PN.block_end(); i != e; + ++i) { + ShadowPN->addIncoming(UndefShadow, *i); + } + + DFSF.PHIFixups.push_back(std::make_pair(&PN, ShadowPN)); + DFSF.setShadow(&PN, ShadowPN); +} diff --git a/contrib/llvm/lib/Transforms/Instrumentation/DebugIR.cpp b/contrib/llvm/lib/Transforms/Instrumentation/DebugIR.cpp new file mode 100644 index 0000000..f50a044 --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/DebugIR.cpp @@ -0,0 +1,618 @@ +//===--- DebugIR.cpp - Transform debug metadata to allow debugging IR -----===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// A Module transform pass that emits a succinct version of the IR and replaces +// the source file metadata to allow debuggers to step through the IR. +// +// FIXME: instead of replacing debug metadata, this pass should allow for +// additional metadata to be used to point capable debuggers to the IR file +// without destroying the mapping to the original source file. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "debug-ir" + +#include "llvm/ADT/ValueMap.h" +#include "llvm/Assembly/AssemblyAnnotationWriter.h" +#include "llvm/DebugInfo.h" +#include "llvm/DIBuilder.h" +#include "llvm/InstVisitor.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Module.h" +#include "llvm/Transforms/Instrumentation.h" +#include "llvm/Transforms/Utils/Cloning.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ToolOutputFile.h" +#include "llvm/Support/FormattedStream.h" +#include "llvm/Support/FileSystem.h" +#include "llvm/Support/Path.h" + +#include "DebugIR.h" + +#include <string> + +#define STR_HELPER(x) #x +#define STR(x) STR_HELPER(x) + +using namespace llvm; + +namespace { + +/// Builds a map of Value* to line numbers on which the Value appears in a +/// textual representation of the IR by plugging into the AssemblyWriter by +/// masquerading as an AssemblyAnnotationWriter. +class ValueToLineMap : public AssemblyAnnotationWriter { + ValueMap<const Value *, unsigned int> Lines; + typedef ValueMap<const Value *, unsigned int>::const_iterator LineIter; + + void addEntry(const Value *V, formatted_raw_ostream &Out) { + Out.flush(); + Lines.insert(std::make_pair(V, Out.getLine() + 1)); + } + +public: + + /// Prints Module to a null buffer in order to build the map of Value pointers + /// to line numbers. + ValueToLineMap(const Module *M) { + raw_null_ostream ThrowAway; + M->print(ThrowAway, this); + } + + // This function is called after an Instruction, GlobalValue, or GlobalAlias + // is printed. + void printInfoComment(const Value &V, formatted_raw_ostream &Out) { + addEntry(&V, Out); + } + + void emitFunctionAnnot(const Function *F, formatted_raw_ostream &Out) { + addEntry(F, Out); + } + + /// If V appears on a line in the textual IR representation, sets Line to the + /// line number and returns true, otherwise returns false. + bool getLine(const Value *V, unsigned int &Line) const { + LineIter i = Lines.find(V); + if (i != Lines.end()) { + Line = i->second; + return true; + } + return false; + } +}; + +/// Removes debug intrisncs like llvm.dbg.declare and llvm.dbg.value. +class DebugIntrinsicsRemover : public InstVisitor<DebugIntrinsicsRemover> { + void remove(Instruction &I) { I.eraseFromParent(); } + +public: + static void process(Module &M) { + DebugIntrinsicsRemover Remover; + Remover.visit(&M); + } + void visitDbgDeclareInst(DbgDeclareInst &I) { remove(I); } + void visitDbgValueInst(DbgValueInst &I) { remove(I); } + void visitDbgInfoIntrinsic(DbgInfoIntrinsic &I) { remove(I); } +}; + +/// Removes debug metadata (!dbg) nodes from all instructions, and optionally +/// metadata named "llvm.dbg.cu" if RemoveNamedInfo is true. +class DebugMetadataRemover : public InstVisitor<DebugMetadataRemover> { + bool RemoveNamedInfo; + +public: + static void process(Module &M, bool RemoveNamedInfo = true) { + DebugMetadataRemover Remover(RemoveNamedInfo); + Remover.run(&M); + } + + DebugMetadataRemover(bool RemoveNamedInfo) + : RemoveNamedInfo(RemoveNamedInfo) {} + + void visitInstruction(Instruction &I) { + if (I.getMetadata(LLVMContext::MD_dbg)) + I.setMetadata(LLVMContext::MD_dbg, 0); + } + + void run(Module *M) { + // Remove debug metadata attached to instructions + visit(M); + + if (RemoveNamedInfo) { + // Remove CU named metadata (and all children nodes) + NamedMDNode *Node = M->getNamedMetadata("llvm.dbg.cu"); + if (Node) + M->eraseNamedMetadata(Node); + } + } +}; + +/// Updates debug metadata in a Module: +/// - changes Filename/Directory to values provided on construction +/// - adds/updates line number (DebugLoc) entries associated with each +/// instruction to reflect the instruction's location in an LLVM IR file +class DIUpdater : public InstVisitor<DIUpdater> { + /// Builder of debug information + DIBuilder Builder; + + /// Helper for type attributes/sizes/etc + DataLayout Layout; + + /// Map of Value* to line numbers + const ValueToLineMap LineTable; + + /// Map of Value* (in original Module) to Value* (in optional cloned Module) + const ValueToValueMapTy *VMap; + + /// Directory of debug metadata + DebugInfoFinder Finder; + + /// Source filename and directory + StringRef Filename; + StringRef Directory; + + // CU nodes needed when creating DI subprograms + MDNode *FileNode; + MDNode *LexicalBlockFileNode; + const MDNode *CUNode; + + ValueMap<const Function *, MDNode *> SubprogramDescriptors; + DenseMap<const Type *, MDNode *> TypeDescriptors; + +public: + DIUpdater(Module &M, StringRef Filename = StringRef(), + StringRef Directory = StringRef(), const Module *DisplayM = 0, + const ValueToValueMapTy *VMap = 0) + : Builder(M), Layout(&M), LineTable(DisplayM ? DisplayM : &M), VMap(VMap), + Finder(), Filename(Filename), Directory(Directory), FileNode(0), + LexicalBlockFileNode(0), CUNode(0) { + Finder.processModule(M); + visit(&M); + } + + ~DIUpdater() { Builder.finalize(); } + + void visitModule(Module &M) { + if (Finder.compile_unit_count() > 1) + report_fatal_error("DebugIR pass supports only a signle compile unit per " + "Module."); + createCompileUnit( + Finder.compile_unit_count() == 1 ? *Finder.compile_unit_begin() : 0); + } + + void visitFunction(Function &F) { + if (F.isDeclaration() || findDISubprogram(&F)) + return; + + StringRef MangledName = F.getName(); + DICompositeType Sig = createFunctionSignature(&F); + + // find line of function declaration + unsigned Line = 0; + if (!findLine(&F, Line)) { + DEBUG(dbgs() << "WARNING: No line for Function " << F.getName().str() + << "\n"); + return; + } + + Instruction *FirstInst = F.begin()->begin(); + unsigned ScopeLine = 0; + if (!findLine(FirstInst, ScopeLine)) { + DEBUG(dbgs() << "WARNING: No line for 1st Instruction in Function " + << F.getName().str() << "\n"); + return; + } + + bool Local = F.hasInternalLinkage(); + bool IsDefinition = !F.isDeclaration(); + bool IsOptimized = false; + + int FuncFlags = llvm::DIDescriptor::FlagPrototyped; + assert(CUNode && FileNode); + DISubprogram Sub = Builder.createFunction( + DICompileUnit(CUNode), F.getName(), MangledName, DIFile(FileNode), Line, + Sig, Local, IsDefinition, ScopeLine, FuncFlags, IsOptimized, &F); + assert(Sub.isSubprogram()); + DEBUG(dbgs() << "create subprogram mdnode " << *Sub << ": " + << "\n"); + + SubprogramDescriptors.insert(std::make_pair(&F, Sub)); + } + + void visitInstruction(Instruction &I) { + DebugLoc Loc(I.getDebugLoc()); + + /// If a ValueToValueMap is provided, use it to get the real instruction as + /// the line table was generated on a clone of the module on which we are + /// operating. + Value *RealInst = 0; + if (VMap) + RealInst = VMap->lookup(&I); + + if (!RealInst) + RealInst = &I; + + unsigned Col = 0; // FIXME: support columns + unsigned Line; + if (!LineTable.getLine(RealInst, Line)) { + // Instruction has no line, it may have been removed (in the module that + // will be passed to the debugger) so there is nothing to do here. + DEBUG(dbgs() << "WARNING: no LineTable entry for instruction " << RealInst + << "\n"); + DEBUG(RealInst->dump()); + return; + } + + DebugLoc NewLoc; + if (!Loc.isUnknown()) + // I had a previous debug location: re-use the DebugLoc + NewLoc = DebugLoc::get(Line, Col, Loc.getScope(RealInst->getContext()), + Loc.getInlinedAt(RealInst->getContext())); + else if (MDNode *scope = findScope(&I)) + NewLoc = DebugLoc::get(Line, Col, scope, 0); + else { + DEBUG(dbgs() << "WARNING: no valid scope for instruction " << &I + << ". no DebugLoc will be present." + << "\n"); + return; + } + + addDebugLocation(I, NewLoc); + } + +private: + + void createCompileUnit(MDNode *CUToReplace) { + std::string Flags; + bool IsOptimized = false; + StringRef Producer; + unsigned RuntimeVersion(0); + StringRef SplitName; + + if (CUToReplace) { + // save fields from existing CU to re-use in the new CU + DICompileUnit ExistingCU(CUToReplace); + Producer = ExistingCU.getProducer(); + IsOptimized = ExistingCU.isOptimized(); + Flags = ExistingCU.getFlags(); + RuntimeVersion = ExistingCU.getRunTimeVersion(); + SplitName = ExistingCU.getSplitDebugFilename(); + } else { + Producer = + "LLVM Version " STR(LLVM_VERSION_MAJOR) "." STR(LLVM_VERSION_MINOR); + } + + CUNode = + Builder.createCompileUnit(dwarf::DW_LANG_C99, Filename, Directory, + Producer, IsOptimized, Flags, RuntimeVersion); + + if (CUToReplace) + CUToReplace->replaceAllUsesWith(const_cast<MDNode *>(CUNode)); + + DICompileUnit CU(CUNode); + FileNode = Builder.createFile(Filename, Directory); + LexicalBlockFileNode = Builder.createLexicalBlockFile(CU, DIFile(FileNode)); + } + + /// Returns the MDNode* that represents the DI scope to associate with I + MDNode *findScope(const Instruction *I) { + const Function *F = I->getParent()->getParent(); + if (MDNode *ret = findDISubprogram(F)) + return ret; + + DEBUG(dbgs() << "WARNING: Using fallback lexical block file scope " + << LexicalBlockFileNode << " as scope for instruction " << I + << "\n"); + return LexicalBlockFileNode; + } + + /// Returns the MDNode* that is the descriptor for F + MDNode *findDISubprogram(const Function *F) { + typedef ValueMap<const Function *, MDNode *>::const_iterator FuncNodeIter; + FuncNodeIter i = SubprogramDescriptors.find(F); + if (i != SubprogramDescriptors.end()) + return i->second; + + DEBUG(dbgs() << "searching for DI scope node for Function " << F + << " in a list of " << Finder.subprogram_count() + << " subprogram nodes" + << "\n"); + + for (DebugInfoFinder::iterator i = Finder.subprogram_begin(), + e = Finder.subprogram_end(); + i != e; ++i) { + DISubprogram S(*i); + if (S.getFunction() == F) { + DEBUG(dbgs() << "Found DISubprogram " << *i << " for function " + << S.getFunction() << "\n"); + return *i; + } + } + DEBUG(dbgs() << "unable to find DISubprogram node for function " + << F->getName().str() << "\n"); + return 0; + } + + /// Sets Line to the line number on which V appears and returns true. If a + /// line location for V is not found, returns false. + bool findLine(const Value *V, unsigned &Line) { + if (LineTable.getLine(V, Line)) + return true; + + if (VMap) { + Value *mapped = VMap->lookup(V); + if (mapped && LineTable.getLine(mapped, Line)) + return true; + } + return false; + } + + std::string getTypeName(Type *T) { + std::string TypeName; + raw_string_ostream TypeStream(TypeName); + T->print(TypeStream); + TypeStream.flush(); + return TypeName; + } + + /// Returns the MDNode that represents type T if it is already created, or 0 + /// if it is not. + MDNode *getType(const Type *T) { + typedef DenseMap<const Type *, MDNode *>::const_iterator TypeNodeIter; + TypeNodeIter i = TypeDescriptors.find(T); + if (i != TypeDescriptors.end()) + return i->second; + return 0; + } + + /// Returns a DebugInfo type from an LLVM type T. + DIDerivedType getOrCreateType(Type *T) { + MDNode *N = getType(T); + if (N) + return DIDerivedType(N); + else if (T->isVoidTy()) + return DIDerivedType(0); + else if (T->isStructTy()) { + N = Builder.createStructType( + DIScope(LexicalBlockFileNode), T->getStructName(), DIFile(FileNode), + 0, Layout.getTypeSizeInBits(T), Layout.getABITypeAlignment(T), 0, + DIType(0), DIArray(0)); // filled in later + + // N is added to the map (early) so that element search below can find it, + // so as to avoid infinite recursion for structs that contain pointers to + // their own type. + TypeDescriptors[T] = N; + DICompositeType StructDescriptor(N); + + SmallVector<Value *, 4> Elements; + for (unsigned i = 0; i < T->getStructNumElements(); ++i) + Elements.push_back(getOrCreateType(T->getStructElementType(i))); + + // set struct elements + StructDescriptor.setTypeArray(Builder.getOrCreateArray(Elements)); + } else if (T->isPointerTy()) { + Type *PointeeTy = T->getPointerElementType(); + if (!(N = getType(PointeeTy))) + N = Builder.createPointerType( + getOrCreateType(PointeeTy), Layout.getPointerTypeSizeInBits(T), + Layout.getPrefTypeAlignment(T), getTypeName(T)); + } else if (T->isArrayTy()) { + SmallVector<Value *, 1> Subrange; + Subrange.push_back( + Builder.getOrCreateSubrange(0, T->getArrayNumElements() - 1)); + + N = Builder.createArrayType(Layout.getTypeSizeInBits(T), + Layout.getPrefTypeAlignment(T), + getOrCreateType(T->getArrayElementType()), + Builder.getOrCreateArray(Subrange)); + } else { + int encoding = llvm::dwarf::DW_ATE_signed; + if (T->isIntegerTy()) + encoding = llvm::dwarf::DW_ATE_unsigned; + else if (T->isFloatingPointTy()) + encoding = llvm::dwarf::DW_ATE_float; + + N = Builder.createBasicType(getTypeName(T), T->getPrimitiveSizeInBits(), + 0, encoding); + } + TypeDescriptors[T] = N; + return DIDerivedType(N); + } + + /// Returns a DebugInfo type that represents a function signature for Func. + DICompositeType createFunctionSignature(const Function *Func) { + SmallVector<Value *, 4> Params; + DIDerivedType ReturnType(getOrCreateType(Func->getReturnType())); + Params.push_back(ReturnType); + + const Function::ArgumentListType &Args(Func->getArgumentList()); + for (Function::ArgumentListType::const_iterator i = Args.begin(), + e = Args.end(); + i != e; ++i) { + Type *T(i->getType()); + Params.push_back(getOrCreateType(T)); + } + + DIArray ParamArray = Builder.getOrCreateArray(Params); + return Builder.createSubroutineType(DIFile(FileNode), ParamArray); + } + + /// Associates Instruction I with debug location Loc. + void addDebugLocation(Instruction &I, DebugLoc Loc) { + MDNode *MD = Loc.getAsMDNode(I.getContext()); + I.setMetadata(LLVMContext::MD_dbg, MD); + } +}; + +/// Sets Filename/Directory from the Module identifier and returns true, or +/// false if source information is not present. +bool getSourceInfoFromModule(const Module &M, std::string &Directory, + std::string &Filename) { + std::string PathStr(M.getModuleIdentifier()); + if (PathStr.length() == 0 || PathStr == "<stdin>") + return false; + + Filename = sys::path::filename(PathStr); + SmallVector<char, 16> Path(PathStr.begin(), PathStr.end()); + sys::path::remove_filename(Path); + Directory = StringRef(Path.data(), Path.size()); + return true; +} + +// Sets Filename/Directory from debug information in M and returns true, or +// false if no debug information available, or cannot be parsed. +bool getSourceInfoFromDI(const Module &M, std::string &Directory, + std::string &Filename) { + NamedMDNode *CUNode = M.getNamedMetadata("llvm.dbg.cu"); + if (!CUNode || CUNode->getNumOperands() == 0) + return false; + + DICompileUnit CU(CUNode->getOperand(0)); + if (!CU.Verify()) + return false; + + Filename = CU.getFilename(); + Directory = CU.getDirectory(); + return true; +} + +} // anonymous namespace + +namespace llvm { + +bool DebugIR::getSourceInfo(const Module &M) { + ParsedPath = getSourceInfoFromDI(M, Directory, Filename) || + getSourceInfoFromModule(M, Directory, Filename); + return ParsedPath; +} + +bool DebugIR::updateExtension(StringRef NewExtension) { + size_t dot = Filename.find_last_of("."); + if (dot == std::string::npos) + return false; + + Filename.erase(dot); + Filename += NewExtension.str(); + return true; +} + +void DebugIR::generateFilename(OwningPtr<int> &fd) { + SmallVector<char, 16> PathVec; + fd.reset(new int); + sys::fs::createTemporaryFile("debug-ir", "ll", *fd, PathVec); + StringRef Path(PathVec.data(), PathVec.size()); + Filename = sys::path::filename(Path); + sys::path::remove_filename(PathVec); + Directory = StringRef(PathVec.data(), PathVec.size()); + + GeneratedPath = true; +} + +std::string DebugIR::getPath() { + SmallVector<char, 16> Path; + sys::path::append(Path, Directory, Filename); + Path.resize(Filename.size() + Directory.size() + 2); + Path[Filename.size() + Directory.size() + 1] = '\0'; + return std::string(Path.data()); +} + +void DebugIR::writeDebugBitcode(const Module *M, int *fd) { + OwningPtr<raw_fd_ostream> Out; + std::string error; + + if (!fd) { + std::string Path = getPath(); + Out.reset(new raw_fd_ostream(Path.c_str(), error)); + DEBUG(dbgs() << "WRITING debug bitcode from Module " << M << " to file " + << Path << "\n"); + } else { + DEBUG(dbgs() << "WRITING debug bitcode from Module " << M << " to fd " + << *fd << "\n"); + Out.reset(new raw_fd_ostream(*fd, true)); + } + + M->print(*Out, 0); + Out->close(); +} + +void DebugIR::createDebugInfo(Module &M, OwningPtr<Module> &DisplayM) { + if (M.getFunctionList().size() == 0) + // no functions -- no debug info needed + return; + + OwningPtr<ValueToValueMapTy> VMap; + + if (WriteSourceToDisk && (HideDebugIntrinsics || HideDebugMetadata)) { + VMap.reset(new ValueToValueMapTy); + DisplayM.reset(CloneModule(&M, *VMap)); + + if (HideDebugIntrinsics) + DebugIntrinsicsRemover::process(*DisplayM); + + if (HideDebugMetadata) + DebugMetadataRemover::process(*DisplayM); + } + + DIUpdater R(M, Filename, Directory, DisplayM.get(), VMap.get()); +} + +bool DebugIR::isMissingPath() { return Filename.empty() || Directory.empty(); } + +bool DebugIR::runOnModule(Module &M) { + OwningPtr<int> fd; + + if (isMissingPath() && !getSourceInfo(M)) { + if (!WriteSourceToDisk) + report_fatal_error("DebugIR unable to determine file name in input. " + "Ensure Module contains an identifier, a valid " + "DICompileUnit, or construct DebugIR with " + "non-empty Filename/Directory parameters."); + else + generateFilename(fd); + } + + if (!GeneratedPath && WriteSourceToDisk) + updateExtension(".debug-ll"); + + // Clear line numbers. Keep debug info (if any) if we were able to read the + // file name from the DICompileUnit descriptor. + DebugMetadataRemover::process(M, !ParsedPath); + + OwningPtr<Module> DisplayM; + createDebugInfo(M, DisplayM); + if (WriteSourceToDisk) { + Module *OutputM = DisplayM.get() ? DisplayM.get() : &M; + writeDebugBitcode(OutputM, fd.get()); + } + + DEBUG(M.dump()); + return true; +} + +bool DebugIR::runOnModule(Module &M, std::string &Path) { + bool result = runOnModule(M); + Path = getPath(); + return result; +} + +} // llvm namespace + +char DebugIR::ID = 0; +INITIALIZE_PASS(DebugIR, "debug-ir", "Enable debugging IR", false, false) + +ModulePass *llvm::createDebugIRPass(bool HideDebugIntrinsics, + bool HideDebugMetadata, StringRef Directory, + StringRef Filename) { + return new DebugIR(HideDebugIntrinsics, HideDebugMetadata, Directory, + Filename); +} + +ModulePass *llvm::createDebugIRPass() { return new DebugIR(); } diff --git a/contrib/llvm/lib/Transforms/Instrumentation/DebugIR.h b/contrib/llvm/lib/Transforms/Instrumentation/DebugIR.h new file mode 100644 index 0000000..13774cf --- /dev/null +++ b/contrib/llvm/lib/Transforms/Instrumentation/DebugIR.h @@ -0,0 +1,99 @@ +//===- llvm/Transforms/Instrumentation/DebugIR.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 file defines the interface of the DebugIR pass. For most users, +// including Instrumentation.h and calling createDebugIRPass() is sufficient and +// there is no need to include this file. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_INSTRUMENTATION_DEBUGIR_H +#define LLVM_TRANSFORMS_INSTRUMENTATION_DEBUGIR_H + +#include "llvm/ADT/OwningPtr.h" +#include "llvm/Pass.h" + +namespace llvm { + +class DebugIR : public llvm::ModulePass { + /// If true, write a source file to disk. + bool WriteSourceToDisk; + + /// Hide certain (non-essential) debug information (only relevant if + /// createSource is true. + bool HideDebugIntrinsics; + bool HideDebugMetadata; + + /// The location of the source file. + std::string Directory; + std::string Filename; + + /// True if a temporary file name was generated. + bool GeneratedPath; + + /// True if the file name was read from the Module. + bool ParsedPath; + +public: + static char ID; + + const char *getPassName() const { return "DebugIR"; } + + /// Generate a file on disk to be displayed in a debugger. If Filename and + /// Directory are empty, a temporary path will be generated. + DebugIR(bool HideDebugIntrinsics, bool HideDebugMetadata, + llvm::StringRef Directory, llvm::StringRef Filename) + : ModulePass(ID), WriteSourceToDisk(true), + HideDebugIntrinsics(HideDebugIntrinsics), + HideDebugMetadata(HideDebugMetadata), Directory(Directory), + Filename(Filename), GeneratedPath(false), ParsedPath(false) {} + + /// Modify input in-place; do not generate additional files, and do not hide + /// any debug intrinsics/metadata that might be present. + DebugIR() + : ModulePass(ID), WriteSourceToDisk(false), HideDebugIntrinsics(false), + HideDebugMetadata(false), GeneratedPath(false), ParsedPath(false) {} + + /// Run pass on M and set Path to the source file path in the output module. + bool runOnModule(llvm::Module &M, std::string &Path); + bool runOnModule(llvm::Module &M); + +private: + + /// Returns the concatenated Directory + Filename, without error checking + std::string getPath(); + + /// Attempts to read source information from debug information in M, and if + /// that fails, from M's identifier. Returns true on success, false otherwise. + bool getSourceInfo(const llvm::Module &M); + + /// Replace the extension of Filename with NewExtension, and return true if + /// successful. Return false if extension could not be found or Filename is + /// empty. + bool updateExtension(llvm::StringRef NewExtension); + + /// Generate a temporary filename and open an fd + void generateFilename(llvm::OwningPtr<int> &fd); + + /// Creates DWARF CU/Subroutine metadata + void createDebugInfo(llvm::Module &M, + llvm::OwningPtr<llvm::Module> &DisplayM); + + /// Returns true if either Directory or Filename is missing, false otherwise. + bool isMissingPath(); + + /// Write M to disk, optionally passing in an fd to an open file which is + /// closed by this function after writing. If no fd is specified, a new file + /// is opened, written, and closed. + void writeDebugBitcode(const llvm::Module *M, int *fd = 0); +}; + +} // llvm namespace + +#endif // LLVM_TRANSFORMS_INSTRUMENTATION_DEBUGIR_H diff --git a/contrib/llvm/lib/Transforms/Instrumentation/EdgeProfiling.cpp b/contrib/llvm/lib/Transforms/Instrumentation/EdgeProfiling.cpp deleted file mode 100644 index a2459fb..0000000 --- a/contrib/llvm/lib/Transforms/Instrumentation/EdgeProfiling.cpp +++ /dev/null @@ -1,117 +0,0 @@ -//===- 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 "llvm/Transforms/Instrumentation.h" -#include "ProfilingUtils.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/IR/Module.h" -#include "llvm/Pass.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.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/GCOVProfiling.cpp b/contrib/llvm/lib/Transforms/Instrumentation/GCOVProfiling.cpp index 2edd151..206bffb 100644 --- a/contrib/llvm/lib/Transforms/Instrumentation/GCOVProfiling.cpp +++ b/contrib/llvm/lib/Transforms/Instrumentation/GCOVProfiling.cpp @@ -17,7 +17,6 @@ #define DEBUG_TYPE "insert-gcov-profiling" #include "llvm/Transforms/Instrumentation.h" -#include "ProfilingUtils.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Statistic.h" @@ -34,9 +33,10 @@ #include "llvm/Support/DebugLoc.h" #include "llvm/Support/FileSystem.h" #include "llvm/Support/InstIterator.h" -#include "llvm/Support/PathV2.h" +#include "llvm/Support/Path.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/ModuleUtils.h" +#include <algorithm> #include <string> #include <utility> using namespace llvm; @@ -102,6 +102,7 @@ namespace { Constant *getIncrementIndirectCounterFunc(); Constant *getEmitFunctionFunc(); Constant *getEmitArcsFunc(); + Constant *getSummaryInfoFunc(); Constant *getDeleteWriteoutFunctionListFunc(); Constant *getDeleteFlushFunctionListFunc(); Constant *getEndFileFunc(); @@ -153,10 +154,10 @@ static std::string getFunctionName(DISubprogram SP) { namespace { class GCOVRecord { protected: - static const char *LinesTag; - static const char *FunctionTag; - static const char *BlockTag; - static const char *EdgeTag; + static const char *const LinesTag; + static const char *const FunctionTag; + static const char *const BlockTag; + static const char *const EdgeTag; GCOVRecord() {} @@ -170,7 +171,7 @@ namespace { // Returns the length measured in 4-byte blocks that will be used to // represent this string in a GCOV file - unsigned lengthOfGCOVString(StringRef s) { + static 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. @@ -190,10 +191,10 @@ namespace { 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"; + const char *const GCOVRecord::LinesTag = "\0\0\x45\x01"; + const char *const GCOVRecord::FunctionTag = "\0\0\0\1"; + const char *const GCOVRecord::BlockTag = "\0\0\x41\x01"; + const char *const GCOVRecord::EdgeTag = "\0\0\x43\x01"; class GCOVFunction; class GCOVBlock; @@ -207,7 +208,7 @@ namespace { Lines.push_back(Line); } - uint32_t length() { + uint32_t length() const { // Here 2 = 1 for string length + 1 for '0' id#. return lengthOfGCOVString(Filename) + 2 + Lines.size(); } @@ -229,6 +230,15 @@ namespace { SmallVector<uint32_t, 32> Lines; }; + + // Sorting function for deterministic behaviour in GCOVBlock::writeOut. + struct StringKeySort { + bool operator()(StringMapEntry<GCOVLines *> *LHS, + StringMapEntry<GCOVLines *> *RHS) const { + return LHS->getKey() < RHS->getKey(); + } + }; + // 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. @@ -248,17 +258,23 @@ namespace { void writeOut() { uint32_t Len = 3; + SmallVector<StringMapEntry<GCOVLines *> *, 32> SortedLinesByFile; for (StringMap<GCOVLines *>::iterator I = LinesByFile.begin(), E = LinesByFile.end(); I != E; ++I) { Len += I->second->length(); + SortedLinesByFile.push_back(&*I); } writeBytes(LinesTag, 4); write(Len); write(Number); - for (StringMap<GCOVLines *>::iterator I = LinesByFile.begin(), - E = LinesByFile.end(); I != E; ++I) - I->second->writeOut(); + + StringKeySort Sorter; + std::sort(SortedLinesByFile.begin(), SortedLinesByFile.end(), Sorter); + for (SmallVectorImpl<StringMapEntry<GCOVLines *> *>::iterator + I = SortedLinesByFile.begin(), E = SortedLinesByFile.end(); + I != E; ++I) + (*I)->getValue()->writeOut(); write(0); write(0); } @@ -335,9 +351,10 @@ namespace { 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 (Blocks.empty()) return; + Function *F = Blocks.begin()->first->getParent(); + for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { + GCOVBlock &Block = *Blocks[I]; if (Block.OutEdges.empty()) continue; writeBytes(EdgeTag, 4); @@ -352,9 +369,8 @@ namespace { } // Emit lines for each block. - for (DenseMap<BasicBlock *, GCOVBlock *>::iterator I = Blocks.begin(), - E = Blocks.end(); I != E; ++I) { - I->second->writeOut(); + for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { + Blocks[I]->writeOut(); } } @@ -410,7 +426,7 @@ void GCOVProfiler::emitProfileNotes() { DICompileUnit CU(CU_Nodes->getOperand(i)); std::string ErrorInfo; raw_fd_ostream out(mangleName(CU, "gcno").c_str(), ErrorInfo, - raw_fd_ostream::F_Binary); + sys::fs::F_Binary); out.write("oncg", 4); out.write(ReversedVersion, 4); out.write("MVLL", 4); @@ -418,7 +434,10 @@ void GCOVProfiler::emitProfileNotes() { DIArray SPs = CU.getSubprograms(); for (unsigned i = 0, e = SPs.getNumElements(); i != e; ++i) { DISubprogram SP(SPs.getElement(i)); - if (!SP.Verify()) continue; + assert((!SP || SP.isSubprogram()) && + "A MDNode in subprograms of a CU should be null or a DISubprogram."); + if (!SP) + continue; Function *F = SP.getFunction(); if (!F) continue; @@ -467,7 +486,10 @@ bool GCOVProfiler::emitProfileArcs() { 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; + assert((!SP || SP.isSubprogram()) && + "A MDNode in subprograms of a CU should be null or a DISubprogram."); + if (!SP) + continue; Function *F = SP.getFunction(); if (!F) continue; if (!Result) Result = true; @@ -497,15 +519,15 @@ bool GCOVProfiler::emitProfileArcs() { TerminatorInst *TI = BB->getTerminator(); int Successors = isa<ReturnInst>(TI) ? 1 : TI->getNumSuccessors(); if (Successors) { - IRBuilder<> Builder(TI); - if (Successors == 1) { + IRBuilder<> Builder(BB->getFirstInsertionPt()); Value *Counter = Builder.CreateConstInBoundsGEP2_64(Counters, 0, Edge); Value *Count = Builder.CreateLoad(Counter); Count = Builder.CreateAdd(Count, Builder.getInt64(1)); Builder.CreateStore(Count, Counter); } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { + IRBuilder<> Builder(BI); Value *Sel = Builder.CreateSelect(BI->getCondition(), Builder.getInt64(Edge), Builder.getInt64(Edge + 1)); @@ -521,6 +543,7 @@ bool GCOVProfiler::emitProfileArcs() { for (int i = 0; i != Successors; ++i) ComplexEdgeSuccs.insert(TI->getSuccessor(i)); } + Edge += Successors; } } @@ -532,14 +555,13 @@ bool GCOVProfiler::emitProfileArcs() { GlobalVariable *EdgeState = getEdgeStateValue(); for (int i = 0, e = ComplexEdgePreds.size(); i != e; ++i) { - IRBuilder<> Builder(ComplexEdgePreds[i+1]->getTerminator()); + IRBuilder<> Builder(ComplexEdgePreds[i + 1]->getFirstInsertionPt()); Builder.CreateStore(Builder.getInt32(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); + // Call runtime to perform increment. + IRBuilder<> Builder(ComplexEdgeSuccs[i+1]->getFirstInsertionPt()); Value *CounterPtrArray = Builder.CreateConstInBoundsGEP2_64(EdgeTable, 0, i * ComplexEdgePreds.size()); @@ -577,7 +599,7 @@ bool GCOVProfiler::emitProfileArcs() { }; FTy = FunctionType::get(Builder.getVoidTy(), Params, false); - // Inialize the environment and register the local writeout and flush + // Initialize the environment and register the local writeout and flush // functions. Constant *GCOVInit = M->getOrInsertFunction("llvm_gcov_init", FTy); Builder.CreateCall2(GCOVInit, WriteoutF, FlushF); @@ -679,6 +701,11 @@ Constant *GCOVProfiler::getEmitArcsFunc() { return M->getOrInsertFunction("llvm_gcda_emit_arcs", FTy); } +Constant *GCOVProfiler::getSummaryInfoFunc() { + FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), false); + return M->getOrInsertFunction("llvm_gcda_summary_info", FTy); +} + Constant *GCOVProfiler::getDeleteWriteoutFunctionListFunc() { FunctionType *FTy = FunctionType::get(Type::getVoidTy(*Ctx), false); return M->getOrInsertFunction("llvm_delete_writeout_function_list", FTy); @@ -725,6 +752,7 @@ Function *GCOVProfiler::insertCounterWriteout( Constant *StartFile = getStartFileFunc(); Constant *EmitFunction = getEmitFunctionFunc(); Constant *EmitArcs = getEmitArcsFunc(); + Constant *SummaryInfo = getSummaryInfoFunc(); Constant *EndFile = getEndFileFunc(); NamedMDNode *CU_Nodes = M->getNamedMetadata("llvm.dbg.cu"); @@ -751,6 +779,7 @@ Function *GCOVProfiler::insertCounterWriteout( Builder.getInt32(Arcs), Builder.CreateConstGEP2_64(GV, 0, 0)); } + Builder.CreateCall(SummaryInfo); Builder.CreateCall(EndFile); } } diff --git a/contrib/llvm/lib/Transforms/Instrumentation/Instrumentation.cpp b/contrib/llvm/lib/Transforms/Instrumentation/Instrumentation.cpp index 9f35396..b1bea38 100644 --- a/contrib/llvm/lib/Transforms/Instrumentation/Instrumentation.cpp +++ b/contrib/llvm/lib/Transforms/Instrumentation/Instrumentation.cpp @@ -24,12 +24,10 @@ void llvm::initializeInstrumentation(PassRegistry &Registry) { initializeAddressSanitizerPass(Registry); initializeAddressSanitizerModulePass(Registry); initializeBoundsCheckingPass(Registry); - initializeEdgeProfilerPass(Registry); initializeGCOVProfilerPass(Registry); - initializeOptimalEdgeProfilerPass(Registry); - initializePathProfilerPass(Registry); initializeMemorySanitizerPass(Registry); initializeThreadSanitizerPass(Registry); + initializeDataFlowSanitizerPass(Registry); } /// LLVMInitializeInstrumentation - C binding for diff --git a/contrib/llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp b/contrib/llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp index 4e75904..d547adc 100644 --- a/contrib/llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp +++ b/contrib/llvm/lib/Transforms/Instrumentation/MemorySanitizer.cpp @@ -66,6 +66,31 @@ /// avoids storing origin to memory when a fully initialized value is stored. /// This way it avoids needless overwritting origin of the 4-byte region on /// a short (i.e. 1 byte) clean store, and it is also good for performance. +/// +/// Atomic handling. +/// +/// Ideally, every atomic store of application value should update the +/// corresponding shadow location in an atomic way. Unfortunately, atomic store +/// of two disjoint locations can not be done without severe slowdown. +/// +/// Therefore, we implement an approximation that may err on the safe side. +/// In this implementation, every atomically accessed location in the program +/// may only change from (partially) uninitialized to fully initialized, but +/// not the other way around. We load the shadow _after_ the application load, +/// and we store the shadow _before_ the app store. Also, we always store clean +/// shadow (if the application store is atomic). This way, if the store-load +/// pair constitutes a happens-before arc, shadow store and load are correctly +/// ordered such that the load will get either the value that was stored, or +/// some later value (which is always clean). +/// +/// This does not work very well with Compare-And-Swap (CAS) and +/// Read-Modify-Write (RMW) operations. To follow the above logic, CAS and RMW +/// must store the new shadow before the app operation, and load the shadow +/// after the app operation. Computers don't work this way. Current +/// implementation ignores the load aspect of CAS/RMW, always returning a clean +/// value. It implements the store part as a simple atomic store by storing a +/// clean shadow. + //===----------------------------------------------------------------------===// #define DEBUG_TYPE "msan" @@ -74,6 +99,7 @@ #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SmallString.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Triple.h" #include "llvm/ADT/ValueMap.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Function.h" @@ -90,9 +116,9 @@ #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" -#include "llvm/Transforms/Utils/BlackList.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/ModuleUtils.h" +#include "llvm/Transforms/Utils/SpecialCaseList.h" using namespace llvm; @@ -156,6 +182,18 @@ static cl::opt<std::string> ClBlacklistFile("msan-blacklist", cl::desc("File containing the list of functions where MemorySanitizer " "should not report bugs"), cl::Hidden); +// Experimental. Wraps all indirect calls in the instrumented code with +// a call to the given function. This is needed to assist the dynamic +// helper tool (MSanDR) to regain control on transition between instrumented and +// non-instrumented code. +static cl::opt<std::string> ClWrapIndirectCalls("msan-wrap-indirect-calls", + cl::desc("Wrap indirect calls with a given function"), + cl::Hidden); + +static cl::opt<bool> ClWrapIndirectCallsFast("msan-wrap-indirect-calls-fast", + cl::desc("Do not wrap indirect calls with target in the same module"), + cl::Hidden, cl::init(true)); + namespace { /// \brief An instrumentation pass implementing detection of uninitialized @@ -167,12 +205,12 @@ class MemorySanitizer : public FunctionPass { public: MemorySanitizer(bool TrackOrigins = false, StringRef BlacklistFile = StringRef()) - : FunctionPass(ID), - TrackOrigins(TrackOrigins || ClTrackOrigins), - TD(0), - WarningFn(0), - BlacklistFile(BlacklistFile.empty() ? ClBlacklistFile - : BlacklistFile) { } + : FunctionPass(ID), + TrackOrigins(TrackOrigins || ClTrackOrigins), + TD(0), + WarningFn(0), + BlacklistFile(BlacklistFile.empty() ? ClBlacklistFile : BlacklistFile), + WrapIndirectCalls(!ClWrapIndirectCalls.empty()) {} const char *getPassName() const { return "MemorySanitizer"; } bool runOnFunction(Function &F); bool doInitialization(Module &M); @@ -206,13 +244,16 @@ class MemorySanitizer : public FunctionPass { /// function. GlobalVariable *OriginTLS; + GlobalVariable *MsandrModuleStart; + GlobalVariable *MsandrModuleEnd; + /// \brief The run-time callback to print a warning. Value *WarningFn; /// \brief Run-time helper that copies origin info for a memory range. Value *MsanCopyOriginFn; /// \brief Run-time helper that generates a new origin value for a stack /// allocation. - Value *MsanSetAllocaOriginFn; + Value *MsanSetAllocaOrigin4Fn; /// \brief Run-time helper that poisons stack on function entry. Value *MsanPoisonStackFn; /// \brief MSan runtime replacements for memmove, memcpy and memset. @@ -228,13 +269,19 @@ class MemorySanitizer : public FunctionPass { MDNode *ColdCallWeights; /// \brief Branch weights for origin store. MDNode *OriginStoreWeights; - /// \bried Path to blacklist file. + /// \brief Path to blacklist file. SmallString<64> BlacklistFile; /// \brief The blacklist. - OwningPtr<BlackList> BL; + OwningPtr<SpecialCaseList> BL; /// \brief An empty volatile inline asm that prevents callback merge. InlineAsm *EmptyAsm; + bool WrapIndirectCalls; + /// \brief Run-time wrapper for indirect calls. + Value *IndirectCallWrapperFn; + // Argument and return type of IndirectCallWrapperFn: void (*f)(void). + Type *AnyFunctionPtrTy; + friend struct MemorySanitizerVisitor; friend struct VarArgAMD64Helper; }; @@ -280,9 +327,9 @@ void MemorySanitizer::initializeCallbacks(Module &M) { MsanCopyOriginFn = M.getOrInsertFunction( "__msan_copy_origin", IRB.getVoidTy(), IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IntptrTy, NULL); - MsanSetAllocaOriginFn = M.getOrInsertFunction( - "__msan_set_alloca_origin", IRB.getVoidTy(), IRB.getInt8PtrTy(), IntptrTy, - IRB.getInt8PtrTy(), NULL); + MsanSetAllocaOrigin4Fn = M.getOrInsertFunction( + "__msan_set_alloca_origin4", IRB.getVoidTy(), IRB.getInt8PtrTy(), IntptrTy, + IRB.getInt8PtrTy(), IntptrTy, NULL); MsanPoisonStackFn = M.getOrInsertFunction( "__msan_poison_stack", IRB.getVoidTy(), IRB.getInt8PtrTy(), IntptrTy, NULL); MemmoveFn = M.getOrInsertFunction( @@ -299,35 +346,53 @@ void MemorySanitizer::initializeCallbacks(Module &M) { RetvalTLS = new GlobalVariable( M, ArrayType::get(IRB.getInt64Ty(), 8), false, GlobalVariable::ExternalLinkage, 0, "__msan_retval_tls", 0, - GlobalVariable::GeneralDynamicTLSModel); + GlobalVariable::InitialExecTLSModel); RetvalOriginTLS = new GlobalVariable( M, OriginTy, false, GlobalVariable::ExternalLinkage, 0, - "__msan_retval_origin_tls", 0, GlobalVariable::GeneralDynamicTLSModel); + "__msan_retval_origin_tls", 0, GlobalVariable::InitialExecTLSModel); ParamTLS = new GlobalVariable( M, ArrayType::get(IRB.getInt64Ty(), 1000), false, GlobalVariable::ExternalLinkage, 0, "__msan_param_tls", 0, - GlobalVariable::GeneralDynamicTLSModel); + GlobalVariable::InitialExecTLSModel); ParamOriginTLS = new GlobalVariable( M, ArrayType::get(OriginTy, 1000), false, GlobalVariable::ExternalLinkage, - 0, "__msan_param_origin_tls", 0, GlobalVariable::GeneralDynamicTLSModel); + 0, "__msan_param_origin_tls", 0, GlobalVariable::InitialExecTLSModel); VAArgTLS = new GlobalVariable( M, ArrayType::get(IRB.getInt64Ty(), 1000), false, GlobalVariable::ExternalLinkage, 0, "__msan_va_arg_tls", 0, - GlobalVariable::GeneralDynamicTLSModel); + GlobalVariable::InitialExecTLSModel); VAArgOverflowSizeTLS = new GlobalVariable( M, IRB.getInt64Ty(), false, GlobalVariable::ExternalLinkage, 0, "__msan_va_arg_overflow_size_tls", 0, - GlobalVariable::GeneralDynamicTLSModel); + GlobalVariable::InitialExecTLSModel); OriginTLS = new GlobalVariable( M, IRB.getInt32Ty(), false, GlobalVariable::ExternalLinkage, 0, - "__msan_origin_tls", 0, GlobalVariable::GeneralDynamicTLSModel); + "__msan_origin_tls", 0, GlobalVariable::InitialExecTLSModel); // We insert an empty inline asm after __msan_report* to avoid callback merge. EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false), StringRef(""), StringRef(""), /*hasSideEffects=*/true); + + if (WrapIndirectCalls) { + AnyFunctionPtrTy = + PointerType::getUnqual(FunctionType::get(IRB.getVoidTy(), false)); + IndirectCallWrapperFn = M.getOrInsertFunction( + ClWrapIndirectCalls, AnyFunctionPtrTy, AnyFunctionPtrTy, NULL); + } + + if (ClWrapIndirectCallsFast) { + MsandrModuleStart = new GlobalVariable( + M, IRB.getInt32Ty(), false, GlobalValue::ExternalLinkage, + 0, "__executable_start"); + MsandrModuleStart->setVisibility(GlobalVariable::HiddenVisibility); + MsandrModuleEnd = new GlobalVariable( + M, IRB.getInt32Ty(), false, GlobalValue::ExternalLinkage, + 0, "_end"); + MsandrModuleEnd->setVisibility(GlobalVariable::HiddenVisibility); + } } /// \brief Module-level initialization. @@ -337,7 +402,7 @@ bool MemorySanitizer::doInitialization(Module &M) { TD = getAnalysisIfAvailable<DataLayout>(); if (!TD) return false; - BL.reset(new BlackList(BlacklistFile)); + BL.reset(SpecialCaseList::createOrDie(BlacklistFile)); C = &(M.getContext()); unsigned PtrSize = TD->getPointerSizeInBits(/* AddressSpace */0); switch (PtrSize) { @@ -365,11 +430,13 @@ bool MemorySanitizer::doInitialization(Module &M) { appendToGlobalCtors(M, cast<Function>(M.getOrInsertFunction( "__msan_init", IRB.getVoidTy(), NULL)), 0); - new GlobalVariable(M, IRB.getInt32Ty(), true, GlobalValue::WeakODRLinkage, - IRB.getInt32(TrackOrigins), "__msan_track_origins"); + if (TrackOrigins) + new GlobalVariable(M, IRB.getInt32Ty(), true, GlobalValue::WeakODRLinkage, + IRB.getInt32(TrackOrigins), "__msan_track_origins"); - new GlobalVariable(M, IRB.getInt32Ty(), true, GlobalValue::WeakODRLinkage, - IRB.getInt32(ClKeepGoing), "__msan_keep_going"); + if (ClKeepGoing) + new GlobalVariable(M, IRB.getInt32Ty(), true, GlobalValue::WeakODRLinkage, + IRB.getInt32(ClKeepGoing), "__msan_keep_going"); return true; } @@ -420,27 +487,40 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { MemorySanitizer &MS; SmallVector<PHINode *, 16> ShadowPHINodes, OriginPHINodes; ValueMap<Value*, Value*> ShadowMap, OriginMap; + OwningPtr<VarArgHelper> VAHelper; + + // The following flags disable parts of MSan instrumentation based on + // blacklist contents and command-line options. bool InsertChecks; bool LoadShadow; - OwningPtr<VarArgHelper> VAHelper; + bool PoisonStack; + bool PoisonUndef; + bool CheckReturnValue; struct ShadowOriginAndInsertPoint { - Instruction *Shadow; - Instruction *Origin; + Value *Shadow; + Value *Origin; Instruction *OrigIns; - ShadowOriginAndInsertPoint(Instruction *S, Instruction *O, Instruction *I) + ShadowOriginAndInsertPoint(Value *S, Value *O, Instruction *I) : Shadow(S), Origin(O), OrigIns(I) { } ShadowOriginAndInsertPoint() : Shadow(0), Origin(0), OrigIns(0) { } }; SmallVector<ShadowOriginAndInsertPoint, 16> InstrumentationList; SmallVector<Instruction*, 16> StoreList; + SmallVector<CallSite, 16> IndirectCallList; MemorySanitizerVisitor(Function &F, MemorySanitizer &MS) : F(F), MS(MS), VAHelper(CreateVarArgHelper(F, MS, *this)) { - LoadShadow = InsertChecks = - !MS.BL->isIn(F) && - F.getAttributes().hasAttribute(AttributeSet::FunctionIndex, - Attribute::SanitizeMemory); + bool SanitizeFunction = !MS.BL->isIn(F) && F.getAttributes().hasAttribute( + AttributeSet::FunctionIndex, + Attribute::SanitizeMemory); + InsertChecks = SanitizeFunction; + LoadShadow = SanitizeFunction; + PoisonStack = SanitizeFunction && ClPoisonStack; + PoisonUndef = SanitizeFunction && ClPoisonUndef; + // FIXME: Consider using SpecialCaseList to specify a list of functions that + // must always return fully initialized values. For now, we hardcode "main". + CheckReturnValue = SanitizeFunction && (F.getName() == "main"); DEBUG(if (!InsertChecks) dbgs() << "MemorySanitizer is not inserting checks into '" @@ -454,7 +534,7 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { IRBuilder<> IRB(&I); Value *Val = I.getValueOperand(); Value *Addr = I.getPointerOperand(); - Value *Shadow = getShadow(Val); + Value *Shadow = I.isAtomic() ? getCleanShadow(Val) : getShadow(Val); Value *ShadowPtr = getShadowPtr(Addr, Shadow->getType(), IRB); StoreInst *NewSI = @@ -463,7 +543,10 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { (void)NewSI; if (ClCheckAccessAddress) - insertCheck(Addr, &I); + insertShadowCheck(Addr, &I); + + if (I.isAtomic()) + I.setOrdering(addReleaseOrdering(I.getOrdering())); if (MS.TrackOrigins) { unsigned Alignment = std::max(kMinOriginAlignment, I.getAlignment()); @@ -473,11 +556,10 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { } else { Value *ConvertedShadow = convertToShadowTyNoVec(Shadow, IRB); - Constant *Cst = dyn_cast_or_null<Constant>(ConvertedShadow); // TODO(eugenis): handle non-zero constant shadow by inserting an // unconditional check (can not simply fail compilation as this could // be in the dead code). - if (Cst) + if (isa<Constant>(ConvertedShadow)) continue; Value *Cmp = IRB.CreateICmpNE(ConvertedShadow, @@ -495,12 +577,15 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { void materializeChecks() { for (size_t i = 0, n = InstrumentationList.size(); i < n; i++) { - Instruction *Shadow = InstrumentationList[i].Shadow; + Value *Shadow = InstrumentationList[i].Shadow; Instruction *OrigIns = InstrumentationList[i].OrigIns; IRBuilder<> IRB(OrigIns); DEBUG(dbgs() << " SHAD0 : " << *Shadow << "\n"); Value *ConvertedShadow = convertToShadowTyNoVec(Shadow, IRB); DEBUG(dbgs() << " SHAD1 : " << *ConvertedShadow << "\n"); + // See the comment in materializeStores(). + if (isa<Constant>(ConvertedShadow)) + continue; Value *Cmp = IRB.CreateICmpNE(ConvertedShadow, getCleanShadow(ConvertedShadow), "_mscmp"); Instruction *CheckTerm = @@ -510,7 +595,7 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { IRB.SetInsertPoint(CheckTerm); if (MS.TrackOrigins) { - Instruction *Origin = InstrumentationList[i].Origin; + Value *Origin = InstrumentationList[i].Origin; IRB.CreateStore(Origin ? (Value*)Origin : (Value*)IRB.getInt32(0), MS.OriginTLS); } @@ -522,6 +607,48 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { DEBUG(dbgs() << "DONE:\n" << F); } + void materializeIndirectCalls() { + for (size_t i = 0, n = IndirectCallList.size(); i < n; i++) { + CallSite CS = IndirectCallList[i]; + Instruction *I = CS.getInstruction(); + BasicBlock *B = I->getParent(); + IRBuilder<> IRB(I); + Value *Fn0 = CS.getCalledValue(); + Value *Fn = IRB.CreateBitCast(Fn0, MS.AnyFunctionPtrTy); + + if (ClWrapIndirectCallsFast) { + // Check that call target is inside this module limits. + Value *Start = + IRB.CreateBitCast(MS.MsandrModuleStart, MS.AnyFunctionPtrTy); + Value *End = IRB.CreateBitCast(MS.MsandrModuleEnd, MS.AnyFunctionPtrTy); + + Value *NotInThisModule = IRB.CreateOr(IRB.CreateICmpULT(Fn, Start), + IRB.CreateICmpUGE(Fn, End)); + + PHINode *NewFnPhi = + IRB.CreatePHI(Fn0->getType(), 2, "msandr.indirect_target"); + + Instruction *CheckTerm = SplitBlockAndInsertIfThen( + cast<Instruction>(NotInThisModule), + /* Unreachable */ false, MS.ColdCallWeights); + + IRB.SetInsertPoint(CheckTerm); + // Slow path: call wrapper function to possibly transform the call + // target. + Value *NewFn = IRB.CreateBitCast( + IRB.CreateCall(MS.IndirectCallWrapperFn, Fn), Fn0->getType()); + + NewFnPhi->addIncoming(Fn0, B); + NewFnPhi->addIncoming(NewFn, dyn_cast<Instruction>(NewFn)->getParent()); + CS.setCalledFunction(NewFnPhi); + } else { + Value *NewFn = IRB.CreateBitCast( + IRB.CreateCall(MS.IndirectCallWrapperFn, Fn), Fn0->getType()); + CS.setCalledFunction(NewFn); + } + } + } + /// \brief Add MemorySanitizer instrumentation to a function. bool runOnFunction() { MS.initializeCallbacks(*F.getParent()); @@ -564,6 +691,9 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { // Insert shadow value checks. materializeChecks(); + // Wrap indirect calls. + materializeIndirectCalls(); + return true; } @@ -741,7 +871,7 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { return Shadow; } if (UndefValue *U = dyn_cast<UndefValue>(V)) { - Value *AllOnes = ClPoisonUndef ? getPoisonedShadow(V) : getCleanShadow(V); + Value *AllOnes = PoisonUndef ? getPoisonedShadow(V) : getCleanShadow(V); DEBUG(dbgs() << "Undef: " << *U << " ==> " << *AllOnes << "\n"); (void)U; return AllOnes; @@ -768,14 +898,21 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { if (AI->hasByValAttr()) { // ByVal pointer itself has clean shadow. We copy the actual // argument shadow to the underlying memory. + // Figure out maximal valid memcpy alignment. + unsigned ArgAlign = AI->getParamAlignment(); + if (ArgAlign == 0) { + Type *EltType = A->getType()->getPointerElementType(); + ArgAlign = MS.TD->getABITypeAlignment(EltType); + } + unsigned CopyAlign = std::min(ArgAlign, kShadowTLSAlignment); Value *Cpy = EntryIRB.CreateMemCpy( - getShadowPtr(V, EntryIRB.getInt8Ty(), EntryIRB), - Base, Size, AI->getParamAlignment()); + getShadowPtr(V, EntryIRB.getInt8Ty(), EntryIRB), Base, Size, + CopyAlign); DEBUG(dbgs() << " ByValCpy: " << *Cpy << "\n"); (void)Cpy; *ShadowPtr = getCleanShadow(V); } else { - *ShadowPtr = EntryIRB.CreateLoad(Base); + *ShadowPtr = EntryIRB.CreateAlignedLoad(Base, kShadowTLSAlignment); } DEBUG(dbgs() << " ARG: " << *AI << " ==> " << **ShadowPtr << "\n"); @@ -784,7 +921,7 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { setOrigin(A, EntryIRB.CreateLoad(OriginPtr)); } } - ArgOffset += DataLayout::RoundUpAlignment(Size, 8); + ArgOffset += DataLayout::RoundUpAlignment(Size, kShadowTLSAlignment); } assert(*ShadowPtr && "Could not find shadow for an argument"); return *ShadowPtr; @@ -820,20 +957,63 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { /// \brief Remember the place where a shadow check should be inserted. /// /// This location will be later instrumented with a check that will print a - /// UMR warning in runtime if the value is not fully defined. - void insertCheck(Value *Val, Instruction *OrigIns) { - assert(Val); + /// UMR warning in runtime if the shadow value is not 0. + void insertShadowCheck(Value *Shadow, Value *Origin, Instruction *OrigIns) { + assert(Shadow); if (!InsertChecks) return; - Instruction *Shadow = dyn_cast_or_null<Instruction>(getShadow(Val)); - if (!Shadow) return; #ifndef NDEBUG Type *ShadowTy = Shadow->getType(); assert((isa<IntegerType>(ShadowTy) || isa<VectorType>(ShadowTy)) && "Can only insert checks for integer and vector shadow types"); #endif - Instruction *Origin = dyn_cast_or_null<Instruction>(getOrigin(Val)); InstrumentationList.push_back( - ShadowOriginAndInsertPoint(Shadow, Origin, OrigIns)); + ShadowOriginAndInsertPoint(Shadow, Origin, OrigIns)); + } + + /// \brief Remember the place where a shadow check should be inserted. + /// + /// This location will be later instrumented with a check that will print a + /// UMR warning in runtime if the value is not fully defined. + void insertShadowCheck(Value *Val, Instruction *OrigIns) { + assert(Val); + Instruction *Shadow = dyn_cast_or_null<Instruction>(getShadow(Val)); + if (!Shadow) return; + Instruction *Origin = dyn_cast_or_null<Instruction>(getOrigin(Val)); + insertShadowCheck(Shadow, Origin, OrigIns); + } + + AtomicOrdering addReleaseOrdering(AtomicOrdering a) { + switch (a) { + case NotAtomic: + return NotAtomic; + case Unordered: + case Monotonic: + case Release: + return Release; + case Acquire: + case AcquireRelease: + return AcquireRelease; + case SequentiallyConsistent: + return SequentiallyConsistent; + } + llvm_unreachable("Unknown ordering"); + } + + AtomicOrdering addAcquireOrdering(AtomicOrdering a) { + switch (a) { + case NotAtomic: + return NotAtomic; + case Unordered: + case Monotonic: + case Acquire: + return Acquire; + case Release: + case AcquireRelease: + return AcquireRelease; + case SequentiallyConsistent: + return SequentiallyConsistent; + } + llvm_unreachable("Unknown ordering"); } // ------------------- Visitors. @@ -844,7 +1024,7 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { /// Optionally, checks that the load address is fully defined. void visitLoadInst(LoadInst &I) { assert(I.getType()->isSized() && "Load type must have size"); - IRBuilder<> IRB(&I); + IRBuilder<> IRB(I.getNextNode()); Type *ShadowTy = getShadowTy(&I); Value *Addr = I.getPointerOperand(); if (LoadShadow) { @@ -856,7 +1036,10 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { } if (ClCheckAccessAddress) - insertCheck(I.getPointerOperand(), &I); + insertShadowCheck(I.getPointerOperand(), &I); + + if (I.isAtomic()) + I.setOrdering(addAcquireOrdering(I.getOrdering())); if (MS.TrackOrigins) { if (LoadShadow) { @@ -877,9 +1060,40 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { StoreList.push_back(&I); } + void handleCASOrRMW(Instruction &I) { + assert(isa<AtomicRMWInst>(I) || isa<AtomicCmpXchgInst>(I)); + + IRBuilder<> IRB(&I); + Value *Addr = I.getOperand(0); + Value *ShadowPtr = getShadowPtr(Addr, I.getType(), IRB); + + if (ClCheckAccessAddress) + insertShadowCheck(Addr, &I); + + // Only test the conditional argument of cmpxchg instruction. + // The other argument can potentially be uninitialized, but we can not + // detect this situation reliably without possible false positives. + if (isa<AtomicCmpXchgInst>(I)) + insertShadowCheck(I.getOperand(1), &I); + + IRB.CreateStore(getCleanShadow(&I), ShadowPtr); + + setShadow(&I, getCleanShadow(&I)); + } + + void visitAtomicRMWInst(AtomicRMWInst &I) { + handleCASOrRMW(I); + I.setOrdering(addReleaseOrdering(I.getOrdering())); + } + + void visitAtomicCmpXchgInst(AtomicCmpXchgInst &I) { + handleCASOrRMW(I); + I.setOrdering(addReleaseOrdering(I.getOrdering())); + } + // Vector manipulation. void visitExtractElementInst(ExtractElementInst &I) { - insertCheck(I.getOperand(1), &I); + insertShadowCheck(I.getOperand(1), &I); IRBuilder<> IRB(&I); setShadow(&I, IRB.CreateExtractElement(getShadow(&I, 0), I.getOperand(1), "_msprop")); @@ -887,7 +1101,7 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { } void visitInsertElementInst(InsertElementInst &I) { - insertCheck(I.getOperand(2), &I); + insertShadowCheck(I.getOperand(2), &I); IRBuilder<> IRB(&I); setShadow(&I, IRB.CreateInsertElement(getShadow(&I, 0), getShadow(&I, 1), I.getOperand(2), "_msprop")); @@ -895,7 +1109,7 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { } void visitShuffleVectorInst(ShuffleVectorInst &I) { - insertCheck(I.getOperand(2), &I); + insertShadowCheck(I.getOperand(2), &I); IRBuilder<> IRB(&I); setShadow(&I, IRB.CreateShuffleVector(getShadow(&I, 0), getShadow(&I, 1), I.getOperand(2), "_msprop")); @@ -1094,18 +1308,19 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { /// \brief Cast between two shadow types, extending or truncating as /// necessary. - Value *CreateShadowCast(IRBuilder<> &IRB, Value *V, Type *dstTy) { + Value *CreateShadowCast(IRBuilder<> &IRB, Value *V, Type *dstTy, + bool Signed = false) { Type *srcTy = V->getType(); if (dstTy->isIntegerTy() && srcTy->isIntegerTy()) - return IRB.CreateIntCast(V, dstTy, false); + return IRB.CreateIntCast(V, dstTy, Signed); if (dstTy->isVectorTy() && srcTy->isVectorTy() && dstTy->getVectorNumElements() == srcTy->getVectorNumElements()) - return IRB.CreateIntCast(V, dstTy, false); + return IRB.CreateIntCast(V, dstTy, Signed); size_t srcSizeInBits = VectorOrPrimitiveTypeSizeInBits(srcTy); size_t dstSizeInBits = VectorOrPrimitiveTypeSizeInBits(dstTy); Value *V1 = IRB.CreateBitCast(V, Type::getIntNTy(*MS.C, srcSizeInBits)); Value *V2 = - IRB.CreateIntCast(V1, Type::getIntNTy(*MS.C, dstSizeInBits), false); + IRB.CreateIntCast(V1, Type::getIntNTy(*MS.C, dstSizeInBits), Signed); return IRB.CreateBitCast(V2, dstTy); // TODO: handle struct types. } @@ -1130,7 +1345,7 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { void handleDiv(Instruction &I) { IRBuilder<> IRB(&I); // Strict on the second argument. - insertCheck(I.getOperand(1), &I); + insertShadowCheck(I.getOperand(1), &I); setShadow(&I, getShadow(&I, 0)); setOrigin(&I, getOrigin(&I, 0)); } @@ -1413,7 +1628,7 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { IRB.CreateAlignedStore(Shadow, ShadowPtr, 1); if (ClCheckAccessAddress) - insertCheck(Addr, &I); + insertShadowCheck(Addr, &I); // FIXME: use ClStoreCleanOrigin // FIXME: factor out common code from materializeStores @@ -1440,9 +1655,8 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { setShadow(&I, getCleanShadow(&I)); } - if (ClCheckAccessAddress) - insertCheck(Addr, &I); + insertShadowCheck(Addr, &I); if (MS.TrackOrigins) { if (LoadShadow) @@ -1539,11 +1753,119 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { setOrigin(&I, getOrigin(Op)); } + // \brief Instrument vector convert instrinsic. + // + // This function instruments intrinsics like cvtsi2ss: + // %Out = int_xxx_cvtyyy(%ConvertOp) + // or + // %Out = int_xxx_cvtyyy(%CopyOp, %ConvertOp) + // Intrinsic converts \p NumUsedElements elements of \p ConvertOp to the same + // number \p Out elements, and (if has 2 arguments) copies the rest of the + // elements from \p CopyOp. + // In most cases conversion involves floating-point value which may trigger a + // hardware exception when not fully initialized. For this reason we require + // \p ConvertOp[0:NumUsedElements] to be fully initialized and trap otherwise. + // We copy the shadow of \p CopyOp[NumUsedElements:] to \p + // Out[NumUsedElements:]. This means that intrinsics without \p CopyOp always + // return a fully initialized value. + void handleVectorConvertIntrinsic(IntrinsicInst &I, int NumUsedElements) { + IRBuilder<> IRB(&I); + Value *CopyOp, *ConvertOp; + + switch (I.getNumArgOperands()) { + case 2: + CopyOp = I.getArgOperand(0); + ConvertOp = I.getArgOperand(1); + break; + case 1: + ConvertOp = I.getArgOperand(0); + CopyOp = NULL; + break; + default: + llvm_unreachable("Cvt intrinsic with unsupported number of arguments."); + } + + // The first *NumUsedElements* elements of ConvertOp are converted to the + // same number of output elements. The rest of the output is copied from + // CopyOp, or (if not available) filled with zeroes. + // Combine shadow for elements of ConvertOp that are used in this operation, + // and insert a check. + // FIXME: consider propagating shadow of ConvertOp, at least in the case of + // int->any conversion. + Value *ConvertShadow = getShadow(ConvertOp); + Value *AggShadow = 0; + if (ConvertOp->getType()->isVectorTy()) { + AggShadow = IRB.CreateExtractElement( + ConvertShadow, ConstantInt::get(IRB.getInt32Ty(), 0)); + for (int i = 1; i < NumUsedElements; ++i) { + Value *MoreShadow = IRB.CreateExtractElement( + ConvertShadow, ConstantInt::get(IRB.getInt32Ty(), i)); + AggShadow = IRB.CreateOr(AggShadow, MoreShadow); + } + } else { + AggShadow = ConvertShadow; + } + assert(AggShadow->getType()->isIntegerTy()); + insertShadowCheck(AggShadow, getOrigin(ConvertOp), &I); + + // Build result shadow by zero-filling parts of CopyOp shadow that come from + // ConvertOp. + if (CopyOp) { + assert(CopyOp->getType() == I.getType()); + assert(CopyOp->getType()->isVectorTy()); + Value *ResultShadow = getShadow(CopyOp); + Type *EltTy = ResultShadow->getType()->getVectorElementType(); + for (int i = 0; i < NumUsedElements; ++i) { + ResultShadow = IRB.CreateInsertElement( + ResultShadow, ConstantInt::getNullValue(EltTy), + ConstantInt::get(IRB.getInt32Ty(), i)); + } + setShadow(&I, ResultShadow); + setOrigin(&I, getOrigin(CopyOp)); + } else { + setShadow(&I, getCleanShadow(&I)); + } + } + void visitIntrinsicInst(IntrinsicInst &I) { switch (I.getIntrinsicID()) { case llvm::Intrinsic::bswap: handleBswap(I); break; + case llvm::Intrinsic::x86_avx512_cvtsd2usi64: + case llvm::Intrinsic::x86_avx512_cvtsd2usi: + case llvm::Intrinsic::x86_avx512_cvtss2usi64: + case llvm::Intrinsic::x86_avx512_cvtss2usi: + case llvm::Intrinsic::x86_avx512_cvttss2usi64: + case llvm::Intrinsic::x86_avx512_cvttss2usi: + case llvm::Intrinsic::x86_avx512_cvttsd2usi64: + case llvm::Intrinsic::x86_avx512_cvttsd2usi: + case llvm::Intrinsic::x86_avx512_cvtusi2sd: + case llvm::Intrinsic::x86_avx512_cvtusi2ss: + case llvm::Intrinsic::x86_avx512_cvtusi642sd: + case llvm::Intrinsic::x86_avx512_cvtusi642ss: + case llvm::Intrinsic::x86_sse2_cvtsd2si64: + case llvm::Intrinsic::x86_sse2_cvtsd2si: + case llvm::Intrinsic::x86_sse2_cvtsd2ss: + case llvm::Intrinsic::x86_sse2_cvtsi2sd: + case llvm::Intrinsic::x86_sse2_cvtsi642sd: + case llvm::Intrinsic::x86_sse2_cvtss2sd: + case llvm::Intrinsic::x86_sse2_cvttsd2si64: + case llvm::Intrinsic::x86_sse2_cvttsd2si: + case llvm::Intrinsic::x86_sse_cvtsi2ss: + case llvm::Intrinsic::x86_sse_cvtsi642ss: + case llvm::Intrinsic::x86_sse_cvtss2si64: + case llvm::Intrinsic::x86_sse_cvtss2si: + case llvm::Intrinsic::x86_sse_cvttss2si64: + case llvm::Intrinsic::x86_sse_cvttss2si: + handleVectorConvertIntrinsic(I, 1); + break; + case llvm::Intrinsic::x86_sse2_cvtdq2pd: + case llvm::Intrinsic::x86_sse2_cvtps2pd: + case llvm::Intrinsic::x86_sse_cvtps2pi: + case llvm::Intrinsic::x86_sse_cvttps2pi: + handleVectorConvertIntrinsic(I, 2); + break; default: if (!handleUnknownIntrinsic(I)) visitInstruction(I); @@ -1589,6 +1911,10 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { } } IRBuilder<> IRB(&I); + + if (MS.WrapIndirectCalls && !CS.getCalledFunction()) + IndirectCallList.push_back(CS); + unsigned ArgOffset = 0; DEBUG(dbgs() << " CallSite: " << I << "\n"); for (CallSite::arg_iterator ArgIt = CS.arg_begin(), End = CS.arg_end(); @@ -1632,7 +1958,7 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { DEBUG(dbgs() << " done with call args\n"); FunctionType *FT = - cast<FunctionType>(CS.getCalledValue()->getType()-> getContainedType(0)); + cast<FunctionType>(CS.getCalledValue()->getType()->getContainedType(0)); if (FT->isVarArg()) { VAHelper->visitCallSite(CS, IRB); } @@ -1671,12 +1997,17 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { void visitReturnInst(ReturnInst &I) { IRBuilder<> IRB(&I); - if (Value *RetVal = I.getReturnValue()) { - // Set the shadow for the RetVal. + Value *RetVal = I.getReturnValue(); + if (!RetVal) return; + Value *ShadowPtr = getShadowPtrForRetval(RetVal, IRB); + if (CheckReturnValue) { + insertShadowCheck(RetVal, &I); + Value *Shadow = getCleanShadow(RetVal); + IRB.CreateAlignedStore(Shadow, ShadowPtr, kShadowTLSAlignment); + } else { Value *Shadow = getShadow(RetVal); - Value *ShadowPtr = getShadowPtrForRetval(RetVal, IRB); - DEBUG(dbgs() << "Return: " << *Shadow << "\n" << *ShadowPtr << "\n"); IRB.CreateAlignedStore(Shadow, ShadowPtr, kShadowTLSAlignment); + // FIXME: make it conditional if ClStoreCleanOrigin==0 if (MS.TrackOrigins) IRB.CreateStore(getOrigin(RetVal), getOriginPtrForRetval(IRB)); } @@ -1694,20 +2025,19 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { void visitAllocaInst(AllocaInst &I) { setShadow(&I, getCleanShadow(&I)); - if (!ClPoisonStack) return; IRBuilder<> IRB(I.getNextNode()); uint64_t Size = MS.TD->getTypeAllocSize(I.getAllocatedType()); - if (ClPoisonStackWithCall) { + if (PoisonStack && ClPoisonStackWithCall) { IRB.CreateCall2(MS.MsanPoisonStackFn, IRB.CreatePointerCast(&I, IRB.getInt8PtrTy()), ConstantInt::get(MS.IntptrTy, Size)); } else { Value *ShadowBase = getShadowPtr(&I, Type::getInt8PtrTy(*MS.C), IRB); - IRB.CreateMemSet(ShadowBase, IRB.getInt8(ClPoisonStackPattern), - Size, I.getAlignment()); + Value *PoisonValue = IRB.getInt8(PoisonStack ? ClPoisonStackPattern : 0); + IRB.CreateMemSet(ShadowBase, PoisonValue, Size, I.getAlignment()); } - if (MS.TrackOrigins) { + if (PoisonStack && MS.TrackOrigins) { setOrigin(&I, getCleanOrigin()); SmallString<2048> StackDescriptionStorage; raw_svector_ostream StackDescription(StackDescriptionStorage); @@ -1720,18 +2050,34 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { Value *Descr = createPrivateNonConstGlobalForString(*F.getParent(), StackDescription.str()); - IRB.CreateCall3(MS.MsanSetAllocaOriginFn, + + IRB.CreateCall4(MS.MsanSetAllocaOrigin4Fn, IRB.CreatePointerCast(&I, IRB.getInt8PtrTy()), ConstantInt::get(MS.IntptrTy, Size), - IRB.CreatePointerCast(Descr, IRB.getInt8PtrTy())); + IRB.CreatePointerCast(Descr, IRB.getInt8PtrTy()), + IRB.CreatePointerCast(&F, MS.IntptrTy)); } } void visitSelectInst(SelectInst& I) { IRBuilder<> IRB(&I); - setShadow(&I, IRB.CreateSelect(I.getCondition(), - getShadow(I.getTrueValue()), getShadow(I.getFalseValue()), - "_msprop")); + // a = select b, c, d + Value *S = IRB.CreateSelect(I.getCondition(), getShadow(I.getTrueValue()), + getShadow(I.getFalseValue())); + if (I.getType()->isAggregateType()) { + // To avoid "sign extending" i1 to an arbitrary aggregate type, we just do + // an extra "select". This results in much more compact IR. + // Sa = select Sb, poisoned, (select b, Sc, Sd) + S = IRB.CreateSelect(getShadow(I.getCondition()), + getPoisonedShadow(getShadowTy(I.getType())), S, + "_msprop_select_agg"); + } else { + // Sa = (sext Sb) | (select b, Sc, Sd) + S = IRB.CreateOr(S, CreateShadowCast(IRB, getShadow(I.getCondition()), + S->getType(), true), + "_msprop_select"); + } + setShadow(&I, S); if (MS.TrackOrigins) { // Origins are always i32, so any vector conditions must be flattened. // FIXME: consider tracking vector origins for app vectors? @@ -1766,7 +2112,7 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { Value *ResShadow = IRB.CreateExtractValue(AggShadow, I.getIndices()); DEBUG(dbgs() << " ResShadow: " << *ResShadow << "\n"); setShadow(&I, ResShadow); - setOrigin(&I, getCleanOrigin()); + setOriginForNaryOp(I); } void visitInsertValueInst(InsertValueInst &I) { @@ -1779,7 +2125,7 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { Value *Res = IRB.CreateInsertValue(AggShadow, InsShadow, I.getIndices()); DEBUG(dbgs() << " Res: " << *Res << "\n"); setShadow(&I, Res); - setOrigin(&I, getCleanOrigin()); + setOriginForNaryOp(I); } void dumpInst(Instruction &I) { @@ -1802,7 +2148,7 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> { dumpInst(I); DEBUG(dbgs() << "DEFAULT: " << I << "\n"); for (size_t i = 0, n = I.getNumOperands(); i < n; i++) - insertCheck(I.getOperand(i), &I); + insertShadowCheck(I.getOperand(i), &I); setShadow(&I, getCleanShadow(&I)); setOrigin(&I, getCleanOrigin()); } @@ -1956,16 +2302,35 @@ struct VarArgAMD64Helper : public VarArgHelper { Value *OverflowArgAreaPtr = IRB.CreateLoad(OverflowArgAreaPtrPtr); Value *OverflowArgAreaShadowPtr = MSV.getShadowPtr(OverflowArgAreaPtr, IRB.getInt8Ty(), IRB); - Value *SrcPtr = - getShadowPtrForVAArgument(VAArgTLSCopy, IRB, AMD64FpEndOffset); + Value *SrcPtr = IRB.CreateConstGEP1_32(VAArgTLSCopy, AMD64FpEndOffset); IRB.CreateMemCpy(OverflowArgAreaShadowPtr, SrcPtr, VAArgOverflowSize, 16); } } }; -VarArgHelper* CreateVarArgHelper(Function &Func, MemorySanitizer &Msan, +/// \brief A no-op implementation of VarArgHelper. +struct VarArgNoOpHelper : public VarArgHelper { + VarArgNoOpHelper(Function &F, MemorySanitizer &MS, + MemorySanitizerVisitor &MSV) {} + + void visitCallSite(CallSite &CS, IRBuilder<> &IRB) {} + + void visitVAStartInst(VAStartInst &I) {} + + void visitVACopyInst(VACopyInst &I) {} + + void finalizeInstrumentation() {} +}; + +VarArgHelper *CreateVarArgHelper(Function &Func, MemorySanitizer &Msan, MemorySanitizerVisitor &Visitor) { - return new VarArgAMD64Helper(Func, Msan, Visitor); + // VarArg handling is only implemented on AMD64. False positives are possible + // on other platforms. + llvm::Triple TargetTriple(Func.getParent()->getTargetTriple()); + if (TargetTriple.getArch() == llvm::Triple::x86_64) + return new VarArgAMD64Helper(Func, Msan, Visitor); + else + return new VarArgNoOpHelper(Func, Msan, Visitor); } } // namespace diff --git a/contrib/llvm/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp b/contrib/llvm/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp deleted file mode 100644 index b45aef65..0000000 --- a/contrib/llvm/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp +++ /dev/null @@ -1,225 +0,0 @@ -//===- 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 "llvm/Transforms/Instrumentation.h" -#include "MaximumSpanningTree.h" -#include "ProfilingUtils.h" -#include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/Analysis/Passes.h" -#include "llvm/Analysis/ProfileInfo.h" -#include "llvm/Analysis/ProfileInfoLoader.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/Module.h" -#include "llvm/Pass.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.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 deleted file mode 100644 index 7de7326..0000000 --- a/contrib/llvm/lib/Transforms/Instrumentation/PathProfiling.cpp +++ /dev/null @@ -1,1424 +0,0 @@ -//===- 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/Transforms/Instrumentation.h" -#include "ProfilingUtils.h" -#include "llvm/Analysis/PathNumbering.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/DerivedTypes.h" -#include "llvm/IR/InstrTypes.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Module.h" -#include "llvm/IR/TypeBuilder.h" -#include "llvm/Pass.h" -#include "llvm/Support/CFG.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Compiler.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.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 deleted file mode 100644 index 4b3de6d..0000000 --- a/contrib/llvm/lib/Transforms/Instrumentation/ProfilingUtils.cpp +++ /dev/null @@ -1,169 +0,0 @@ -//===- 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/IR/Constants.h" -#include "llvm/IR/DerivedTypes.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/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 deleted file mode 100644 index 09b2217..0000000 --- a/contrib/llvm/lib/Transforms/Instrumentation/ProfilingUtils.h +++ /dev/null @@ -1,36 +0,0 @@ -//===- 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 index 299060a..89fb746 100644 --- a/contrib/llvm/lib/Transforms/Instrumentation/ThreadSanitizer.cpp +++ b/contrib/llvm/lib/Transforms/Instrumentation/ThreadSanitizer.cpp @@ -41,8 +41,8 @@ #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" -#include "llvm/Transforms/Utils/BlackList.h" #include "llvm/Transforms/Utils/ModuleUtils.h" +#include "llvm/Transforms/Utils/SpecialCaseList.h" using namespace llvm; @@ -99,7 +99,7 @@ struct ThreadSanitizer : public FunctionPass { DataLayout *TD; Type *IntptrTy; SmallString<64> BlacklistFile; - OwningPtr<BlackList> BL; + OwningPtr<SpecialCaseList> BL; IntegerType *OrdTy; // Callbacks to run-time library are computed in doInitialization. Function *TsanFuncEntry; @@ -227,7 +227,7 @@ bool ThreadSanitizer::doInitialization(Module &M) { TD = getAnalysisIfAvailable<DataLayout>(); if (!TD) return false; - BL.reset(new BlackList(BlacklistFile)); + BL.reset(SpecialCaseList::createOrDie(BlacklistFile)); // Always insert a call to __tsan_init into the module's CTORs. IRBuilder<> IRB(M.getContext()); @@ -240,12 +240,8 @@ bool ThreadSanitizer::doInitialization(Module &M) { } 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; - } - } + if (MDNode *Tag = I->getMetadata(LLVMContext::MD_tbaa)) + return Tag->isTBAAVtableAccess(); return false; } @@ -362,7 +358,7 @@ bool ThreadSanitizer::runOnFunction(Function &F) { // (e.g. variables that do not escape, etc). // Instrument memory accesses. - if (ClInstrumentMemoryAccesses) + if (ClInstrumentMemoryAccesses && F.hasFnAttribute(Attribute::SanitizeThread)) for (size_t i = 0, n = AllLoadsAndStores.size(); i < n; ++i) { Res |= instrumentLoadOrStore(AllLoadsAndStores[i]); } @@ -579,7 +575,7 @@ int ThreadSanitizer::getMemoryAccessFuncIndex(Value *Addr) { // Ignore all unusual sizes. return -1; } - size_t Idx = CountTrailingZeros_32(TypeSize / 8); + size_t Idx = countTrailingZeros(TypeSize / 8); assert(Idx < kNumberOfAccessSizes); return Idx; } |
