aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Transforms/Instrumentation
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Instrumentation')
-rw-r--r--lib/Transforms/Instrumentation/AddressSanitizer.cpp240
-rw-r--r--lib/Transforms/Instrumentation/BoundsChecking.cpp6
-rw-r--r--lib/Transforms/Instrumentation/CMakeLists.txt5
-rw-r--r--lib/Transforms/Instrumentation/DataFlowSanitizer.cpp1397
-rw-r--r--lib/Transforms/Instrumentation/DebugIR.cpp3
-rw-r--r--lib/Transforms/Instrumentation/EdgeProfiling.cpp117
-rw-r--r--lib/Transforms/Instrumentation/GCOVProfiling.cpp25
-rw-r--r--lib/Transforms/Instrumentation/Instrumentation.cpp4
-rw-r--r--lib/Transforms/Instrumentation/MemorySanitizer.cpp443
-rw-r--r--lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp225
-rw-r--r--lib/Transforms/Instrumentation/PathProfiling.cpp1424
-rw-r--r--lib/Transforms/Instrumentation/ProfilingUtils.cpp169
-rw-r--r--lib/Transforms/Instrumentation/ProfilingUtils.h36
-rw-r--r--lib/Transforms/Instrumentation/ThreadSanitizer.cpp12
14 files changed, 2015 insertions, 2091 deletions
diff --git a/lib/Transforms/Instrumentation/AddressSanitizer.cpp b/lib/Transforms/Instrumentation/AddressSanitizer.cpp
index d77e20b..d731ec5 100644
--- a/lib/Transforms/Instrumentation/AddressSanitizer.cpp
+++ b/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"
@@ -59,6 +60,7 @@ 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;
@@ -75,21 +77,30 @@ static const char *const kAsanUnregisterGlobalsName =
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 char *const kAsanStackMallocName = "__asan_stack_malloc";
-static const char *const kAsanStackFreeName = "__asan_stack_free";
+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;
@@ -124,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",
@@ -184,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 {
@@ -306,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;
@@ -321,6 +343,7 @@ struct AddressSanitizer : public FunctionPass {
Function *AsanCtorFunction;
Function *AsanInitFunction;
Function *AsanHandleNoReturnFunc;
+ Function *AsanCovFunction;
OwningPtr<SpecialCaseList> BL;
// This array is indexed by AccessIsWrite and log2(AccessSize).
Function *AsanErrorCallback[2][kNumberOfAccessSizes];
@@ -396,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;
};
@@ -480,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);
}
@@ -488,7 +513,7 @@ 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() &&
@@ -498,24 +523,27 @@ struct FunctionStackPoisoner : public InstVisitor<FunctionStackPoisoner> {
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
@@ -642,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);
@@ -650,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;
+ }
+ }
}
}
@@ -668,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)
@@ -883,7 +929,7 @@ bool AddressSanitizerModule::runOnModule(Module &M) {
TD = getAnalysisIfAvailable<DataLayout>();
if (!TD)
return false;
- BL.reset(new SpecialCaseList(BlacklistFile));
+ BL.reset(SpecialCaseList::createOrDie(BlacklistFile));
if (BL->isIn(M)) return false;
C = &(M.getContext());
int LongSize = TD->getPointerSizeInBits();
@@ -914,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);
@@ -1046,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(""),
@@ -1076,7 +1123,7 @@ bool AddressSanitizer::doInitialization(Module &M) {
if (!TD)
return false;
- BL.reset(new SpecialCaseList(BlacklistFile));
+ BL.reset(SpecialCaseList::createOrDie(BlacklistFile));
DynamicallyInitializedGlobals.Init(M);
C = &(M.getContext());
@@ -1117,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;
@@ -1212,6 +1300,10 @@ bool AddressSanitizer::runOnFunction(Function &F) {
}
bool res = NumInstrumented > 0 || ChangedStack || !NoReturnCalls.empty();
+
+ if (InjectCoverage(F))
+ res = true;
+
DEBUG(dbgs() << "ASAN done instrumenting: " << res << " " << F << "\n");
if (ClKeepUninstrumented) {
@@ -1271,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(
@@ -1283,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);
@@ -1344,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];
@@ -1367,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).
@@ -1380,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;
}
@@ -1442,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.
@@ -1460,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/lib/Transforms/Instrumentation/BoundsChecking.cpp b/lib/Transforms/Instrumentation/BoundsChecking.cpp
index b094d42..7a9f0f6 100644
--- a/lib/Transforms/Instrumentation/BoundsChecking.cpp
+++ b/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/lib/Transforms/Instrumentation/CMakeLists.txt b/lib/Transforms/Instrumentation/CMakeLists.txt
index 5e34863..3563593 100644
--- a/lib/Transforms/Instrumentation/CMakeLists.txt
+++ b/lib/Transforms/Instrumentation/CMakeLists.txt
@@ -1,14 +1,11 @@
add_llvm_library(LLVMInstrumentation
AddressSanitizer.cpp
BoundsChecking.cpp
+ DataFlowSanitizer.cpp
DebugIR.cpp
- EdgeProfiling.cpp
GCOVProfiling.cpp
MemorySanitizer.cpp
Instrumentation.cpp
- OptimalEdgeProfiling.cpp
- PathProfiling.cpp
- ProfilingUtils.cpp
ThreadSanitizer.cpp
)
diff --git a/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp b/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp
new file mode 100644
index 0000000..9b9e725
--- /dev/null
+++ b/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/lib/Transforms/Instrumentation/DebugIR.cpp b/lib/Transforms/Instrumentation/DebugIR.cpp
index 651381d..f50a044 100644
--- a/lib/Transforms/Instrumentation/DebugIR.cpp
+++ b/lib/Transforms/Instrumentation/DebugIR.cpp
@@ -25,6 +25,7 @@
#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"
@@ -401,7 +402,7 @@ private:
Type *PointeeTy = T->getPointerElementType();
if (!(N = getType(PointeeTy)))
N = Builder.createPointerType(
- getOrCreateType(PointeeTy), Layout.getPointerSizeInBits(),
+ getOrCreateType(PointeeTy), Layout.getPointerTypeSizeInBits(T),
Layout.getPrefTypeAlignment(T), getTypeName(T));
} else if (T->isArrayTy()) {
SmallVector<Value *, 1> Subrange;
diff --git a/lib/Transforms/Instrumentation/EdgeProfiling.cpp b/lib/Transforms/Instrumentation/EdgeProfiling.cpp
deleted file mode 100644
index a2459fb..0000000
--- a/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/lib/Transforms/Instrumentation/GCOVProfiling.cpp b/lib/Transforms/Instrumentation/GCOVProfiling.cpp
index 4c2681f..206bffb 100644
--- a/lib/Transforms/Instrumentation/GCOVProfiling.cpp
+++ b/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"
@@ -103,6 +102,7 @@ namespace {
Constant *getIncrementIndirectCounterFunc();
Constant *getEmitFunctionFunc();
Constant *getEmitArcsFunc();
+ Constant *getSummaryInfoFunc();
Constant *getDeleteWriteoutFunctionListFunc();
Constant *getDeleteFlushFunctionListFunc();
Constant *getEndFileFunc();
@@ -519,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));
@@ -543,6 +543,7 @@ bool GCOVProfiler::emitProfileArcs() {
for (int i = 0; i != Successors; ++i)
ComplexEdgeSuccs.insert(TI->getSuccessor(i));
}
+
Edge += Successors;
}
}
@@ -554,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());
@@ -599,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);
@@ -701,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);
@@ -747,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");
@@ -773,6 +779,7 @@ Function *GCOVProfiler::insertCounterWriteout(
Builder.getInt32(Arcs),
Builder.CreateConstGEP2_64(GV, 0, 0));
}
+ Builder.CreateCall(SummaryInfo);
Builder.CreateCall(EndFile);
}
}
diff --git a/lib/Transforms/Instrumentation/Instrumentation.cpp b/lib/Transforms/Instrumentation/Instrumentation.cpp
index 9f35396..b1bea38 100644
--- a/lib/Transforms/Instrumentation/Instrumentation.cpp
+++ b/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/lib/Transforms/Instrumentation/MemorySanitizer.cpp b/lib/Transforms/Instrumentation/MemorySanitizer.cpp
index 0251f16..d547adc 100644
--- a/lib/Transforms/Instrumentation/MemorySanitizer.cpp
+++ b/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"
@@ -157,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
@@ -168,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);
@@ -207,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.
@@ -236,6 +276,12 @@ class MemorySanitizer : public FunctionPass {
/// \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;
};
@@ -281,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(
@@ -329,6 +375,24 @@ void MemorySanitizer::initializeCallbacks(Module &M) {
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.
@@ -338,7 +402,7 @@ bool MemorySanitizer::doInitialization(Module &M) {
TD = getAnalysisIfAvailable<DataLayout>();
if (!TD)
return false;
- BL.reset(new SpecialCaseList(BlacklistFile));
+ BL.reset(SpecialCaseList::createOrDie(BlacklistFile));
C = &(M.getContext());
unsigned PtrSize = TD->getPointerSizeInBits(/* AddressSpace */0);
switch (PtrSize) {
@@ -423,22 +487,27 @@ 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;
bool PoisonStack;
bool PoisonUndef;
- OwningPtr<VarArgHelper> VAHelper;
+ 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)) {
@@ -449,6 +518,9 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> {
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 '"
@@ -462,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 =
@@ -471,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());
@@ -481,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,
@@ -503,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 =
@@ -518,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);
}
@@ -530,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());
@@ -572,6 +691,9 @@ struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> {
// Insert shadow value checks.
materializeChecks();
+ // Wrap indirect calls.
+ materializeIndirectCalls();
+
return true;
}
@@ -835,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.
@@ -859,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) {
@@ -871,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) {
@@ -892,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"));
@@ -902,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"));
@@ -910,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"));
@@ -1109,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.
}
@@ -1145,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));
}
@@ -1428,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
@@ -1455,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)
@@ -1554,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);
@@ -1604,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();
@@ -1647,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);
}
@@ -1686,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));
}
@@ -1734,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?
@@ -1780,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) {
@@ -1793,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) {
@@ -1816,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());
}
@@ -1970,8 +2302,7 @@ 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);
}
}
diff --git a/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp b/lib/Transforms/Instrumentation/OptimalEdgeProfiling.cpp
deleted file mode 100644
index b45aef6..0000000
--- a/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/lib/Transforms/Instrumentation/PathProfiling.cpp b/lib/Transforms/Instrumentation/PathProfiling.cpp
deleted file mode 100644
index 7de7326..0000000
--- a/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/lib/Transforms/Instrumentation/ProfilingUtils.cpp b/lib/Transforms/Instrumentation/ProfilingUtils.cpp
deleted file mode 100644
index 4b3de6d..0000000
--- a/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/lib/Transforms/Instrumentation/ProfilingUtils.h b/lib/Transforms/Instrumentation/ProfilingUtils.h
deleted file mode 100644
index 09b2217..0000000
--- a/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/lib/Transforms/Instrumentation/ThreadSanitizer.cpp b/lib/Transforms/Instrumentation/ThreadSanitizer.cpp
index cc971a3..89fb746 100644
--- a/lib/Transforms/Instrumentation/ThreadSanitizer.cpp
+++ b/lib/Transforms/Instrumentation/ThreadSanitizer.cpp
@@ -227,7 +227,7 @@ bool ThreadSanitizer::doInitialization(Module &M) {
TD = getAnalysisIfAvailable<DataLayout>();
if (!TD)
return false;
- BL.reset(new SpecialCaseList(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]);
}
generated by cgit v1.1 at 2024-06-07 15:22:01 +0000