Index: lib/Transforms/Instrumentation/AddressSanitizer.cpp |
diff --git a/lib/Transforms/Instrumentation/AddressSanitizer.cpp b/lib/Transforms/Instrumentation/AddressSanitizer.cpp |
index 623c4705061ef9cd316cf3edcdfb826a7433675a..5b531d2bec679d723172981f1137f3a9fc23e78c 100644 |
--- a/lib/Transforms/Instrumentation/AddressSanitizer.cpp |
+++ b/lib/Transforms/Instrumentation/AddressSanitizer.cpp |
@@ -17,12 +17,16 @@ |
#include "llvm/Transforms/Instrumentation.h" |
#include "llvm/ADT/ArrayRef.h" |
+#include "llvm/ADT/BitVector.h" |
#include "llvm/ADT/DenseMap.h" |
#include "llvm/ADT/DepthFirstIterator.h" |
+#include "llvm/ADT/MapVector.h" |
#include "llvm/ADT/OwningPtr.h" |
+#include "llvm/ADT/SCCIterator.h" |
#include "llvm/ADT/SmallSet.h" |
#include "llvm/ADT/SmallString.h" |
#include "llvm/ADT/SmallVector.h" |
+#include "llvm/ADT/Statistic.h" |
#include "llvm/ADT/StringExtras.h" |
#include "llvm/ADT/Triple.h" |
#include "llvm/DIBuilder.h" |
@@ -35,6 +39,7 @@ |
#include "llvm/IR/Module.h" |
#include "llvm/IR/Type.h" |
#include "llvm/InstVisitor.h" |
+#include "llvm/Support/CFG.h" |
#include "llvm/Support/CallSite.h" |
#include "llvm/Support/CommandLine.h" |
#include "llvm/Support/DataTypes.h" |
@@ -47,7 +52,9 @@ |
#include "llvm/Transforms/Utils/Local.h" |
#include "llvm/Transforms/Utils/ModuleUtils.h" |
#include <algorithm> |
+#include <map> |
#include <string> |
+#include <vector> |
using namespace llvm; |
@@ -150,6 +157,9 @@ static cl::opt<bool> ClOptSameTemp("asan-opt-same-temp", |
cl::init(true)); |
static cl::opt<bool> ClOptGlobals("asan-opt-globals", |
cl::desc("Don't instrument scalar globals"), cl::Hidden, cl::init(true)); |
+static cl::opt<bool> ClOptSCC("asan-opt-scc", |
+ cl::desc("Don't instrument temps already instrumented in " |
+ "predessors in the SCC"), cl::Hidden, cl::init(true)); |
static cl::opt<bool> ClCheckLifetime("asan-check-lifetime", |
cl::desc("Use llvm.lifetime intrinsics to insert extra checks"), |
@@ -167,6 +177,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(NumInstrumentedInstructions, |
+ "Total number of instrumented instructions"); |
+STATISTIC(NumInstrumentedSCC, |
+ "Number of instrumented instructions by SCC approach"); |
+STATISTIC(NumInstrumentedBase, |
+ "Number of instrumented instructions by basic approach"); |
+ |
namespace { |
/// A set of dynamically initialized globals extracted from metadata. |
class SetOfDynamicallyInitializedGlobals { |
@@ -280,12 +297,66 @@ struct AddressSanitizer : public FunctionPass { |
static char ID; // Pass identification, replacement for typeid |
private: |
+ struct SCCBlock { |
+ // Indices of predessors in the graph of SCCs. |
+ std::vector<unsigned> Preds; |
+ |
+ // Vector of entry blocks in the current component. |
+ std::vector<BasicBlock*> EntryBlocks; |
+ |
+ // Vector of inner blocks in the current component. |
+ std::vector<BasicBlock*> InnerBlocks; |
+ |
+ // i-th element if |IsInstrumented| is true iff it's guaranteed |
+ // that i-th interesting memory access in the whole function is |
+ // instrumented at exit from this component. |
+ BitVector IsInstrumented; |
+ |
+ // True if any of basic blocks from this component has call |
+ // instruction. |
+ bool HasCallInstruction; |
+ }; |
+ |
void initializeCallbacks(Module &M); |
bool ShouldInstrumentGlobal(GlobalVariable *G); |
bool LooksLikeCodeInBug11395(Instruction *I); |
+ bool CanInstrumentFunction(Function &F); |
void FindDynamicInitializers(Module &M); |
+ // Basic analysis. |
+ // |
+ // Store all instructions that need to be instrumented into |
+ // |ToInstrument|, store calls which do not return in |
+ // |NoReturnCalls|. |
+ bool baseAnalyzeFunction(Function &F, |
+ SmallVector<Instruction*, 16> &ToInstrument, |
+ SmallVector<Instruction*, 8> &NoReturnCalls); |
+ |
+ // SCC analysis. |
+ // |
+ // Analyzes single SCC constructed from basic blocks. Stores all |
+ // instructions that need to be instrumented in |ToInstrument|, |
+ // calls which do not return in |NoReturnCalls| and adjusts the |
+ // component's post-invariant bit vector. |
+ void sccAnalyzeComponent( |
+ unsigned ComponentIndex, |
+ std::vector<SCCBlock> &SCC, |
+ const MapVector<Value*, unsigned> &InterestingAccess, |
+ SmallVector<Instruction*, 16> &ToInstrument, |
+ SmallVector<Instruction*, 8> &NoReturnCalls); |
+ void sccAddComponent(std::vector<BasicBlock*> &BasicBlocks, |
+ std::map<BasicBlock*, unsigned> &SCCMapping, |
+ std::vector<SCCBlock> &SCC); |
+ // Analyzes graph constructed from SCCs of |F|'s basic blocks. If |
+ // fuction can be instrumented, stores all instructions that need to |
+ // be instrumented in |ToInstrument|, stores all calls which do not |
+ // return in |NoReturnCalls| and returns true. Otherwise, returns |
+ // false. |
+ bool sccAnalyzeFunction(Function &F, |
+ SmallVector<Instruction*, 16> &ToInstrument, |
+ SmallVector<Instruction*, 8> &NoReturnCalls); |
+ |
bool CheckInitOrder; |
bool CheckUseAfterReturn; |
bool CheckLifetime; |
@@ -620,6 +691,75 @@ static Value *isInterestingMemoryAccess(Instruction *I, bool *IsWrite) { |
return NULL; |
} |
+static bool hasCallInstruction(BasicBlock &BB) { |
+ for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); |
+ BI != BE; ++BI) { |
+ CallSite CS(BI); |
+ if (CS) |
+ return true; |
+ } |
+ return false; |
+} |
+ |
+// Returns map of all interesting to memory accesses (loads and |
+// stores). Memory accesses are stored with their order numbers, |
+// starting with zero. |
+static void getInterestingAccesses(BasicBlock &BB, |
+ MapVector<Value*, unsigned> &M) { |
+ bool IsWrite; |
+ for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE; ++BI) { |
+ if (Value *Addr = isInterestingMemoryAccess(BI, &IsWrite)) { |
+ if (M.find(Addr) != M.end()) |
+ continue; |
+ unsigned Index = M.size(); |
+ M.insert(std::make_pair(Addr, Index)); |
+ } |
+ } |
+} |
+ |
+// Returns all instructions that must be instrumented (currently, |
+// memory intrinsics, loads and stores). In addition, returns all call |
+// instructions which do not return. Modifies |IsInstrumented| |
+// according to memory accesses and calls inside |BB|. |
+static void getInsnsToInstrument( |
+ BasicBlock &BB, |
+ const MapVector<Value*, unsigned> &InterestingAccess, |
+ BitVector &IsInstrumented, |
+ SmallVector<Instruction*, 16> &ToInstrument, |
+ SmallVector<Instruction*, 8> &NoReturnCalls) { |
+ int NumInsnsPerBB = 0; |
+ bool IsWrite; |
+ for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE; ++BI) { |
+ if (Value *Addr = isInterestingMemoryAccess(BI, &IsWrite)) { |
+ if (ClOpt && (ClOptSameTemp || ClOptSCC)) { |
+ MapVector<Value*, unsigned>::const_iterator MI = |
+ InterestingAccess.find(Addr); |
+ assert(MI != InterestingAccess.end()); |
+ unsigned Index = MI->second; |
+ if (IsInstrumented.test(Index)) |
+ continue; // We've seen this temp in the current BB. |
+ IsInstrumented.set(Index); |
+ } |
+ // OK, take it. |
+ } else if (isa<MemIntrinsic>(BI) && ClMemIntrin) { |
+ // OK, take it. |
+ } else { |
+ CallSite CS(BI); |
+ if (CS) { |
+ // A call inside BB. |
+ IsInstrumented.reset(); |
+ if (CS.doesNotReturn()) |
+ NoReturnCalls.push_back(CS.getInstruction()); |
+ } |
+ continue; |
+ } |
+ ToInstrument.push_back(BI); |
+ NumInsnsPerBB++; |
+ if (NumInsnsPerBB >= ClMaxInsnsToInstrumentPerBB) |
+ break; |
+ } |
+} |
+ |
void AddressSanitizer::instrumentMop(Instruction *I) { |
bool IsWrite = false; |
Value *Addr = isInterestingMemoryAccess(I, &IsWrite); |
@@ -1109,47 +1249,20 @@ bool AddressSanitizer::runOnFunction(Function &F) { |
if (!ClDebugFunc.empty() && ClDebugFunc != F.getName()) |
return false; |
- // We want to instrument every address only once per basic block (unless there |
- // are calls between uses). |
- SmallSet<Value*, 16> TempsToInstrument; |
SmallVector<Instruction*, 16> ToInstrument; |
SmallVector<Instruction*, 8> NoReturnCalls; |
- bool IsWrite; |
- // Fill the set of memory operations to instrument. |
- for (Function::iterator FI = F.begin(), FE = F.end(); |
- FI != FE; ++FI) { |
- TempsToInstrument.clear(); |
- int NumInsnsPerBB = 0; |
- for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); |
- BI != BE; ++BI) { |
- if (LooksLikeCodeInBug11395(BI)) return false; |
- if (Value *Addr = isInterestingMemoryAccess(BI, &IsWrite)) { |
- if (ClOpt && ClOptSameTemp) { |
- if (!TempsToInstrument.insert(Addr)) |
- continue; // We've seen this temp in the current BB. |
- } |
- } else if (isa<MemIntrinsic>(BI) && ClMemIntrin) { |
- // ok, take it. |
- } else { |
- CallSite CS(BI); |
- if (CS) { |
- // A call inside BB. |
- TempsToInstrument.clear(); |
- if (CS.doesNotReturn()) |
- NoReturnCalls.push_back(CS.getInstruction()); |
- } |
- continue; |
- } |
- ToInstrument.push_back(BI); |
- NumInsnsPerBB++; |
- if (NumInsnsPerBB >= ClMaxInsnsToInstrumentPerBB) |
- break; |
- } |
- } |
+ bool SCCAnalysis = false; |
+ if (ClOptSCC && sccAnalyzeFunction(F, ToInstrument, NoReturnCalls)) |
+ SCCAnalysis = true; |
+ else if (baseAnalyzeFunction(F, ToInstrument, NoReturnCalls)) |
+ SCCAnalysis = false; |
+ else |
+ return false; |
// Instrument. |
int NumInstrumented = 0; |
+ bool IsWrite; |
for (size_t i = 0, n = ToInstrument.size(); i != n; i++) { |
Instruction *Inst = ToInstrument[i]; |
if (ClDebugMin < 0 || ClDebugMax < 0 || |
@@ -1162,6 +1275,12 @@ bool AddressSanitizer::runOnFunction(Function &F) { |
NumInstrumented++; |
} |
+ NumInstrumentedInstructions += NumInstrumented; |
+ if (SCCAnalysis) |
+ NumInstrumentedSCC += NumInstrumented; |
+ else |
+ NumInstrumentedBase += NumInstrumented; |
+ |
FunctionStackPoisoner FSP(F, *this); |
bool ChangedStack = FSP.runOnFunction(); |
@@ -1177,6 +1296,159 @@ bool AddressSanitizer::runOnFunction(Function &F) { |
return NumInstrumented > 0 || ChangedStack || !NoReturnCalls.empty(); |
} |
+bool AddressSanitizer::baseAnalyzeFunction( |
+ Function& F, |
+ SmallVector<Instruction*, 16> &ToInstrument, |
+ SmallVector<Instruction*, 8> &NoReturnCalls) { |
+ if (!CanInstrumentFunction(F)) |
+ return false; |
+ for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { |
+ BasicBlock &BB = *FI; |
+ MapVector<Value*, unsigned> InterestingAccess; |
+ getInterestingAccesses(BB, InterestingAccess); |
+ BitVector IsInstrumented(InterestingAccess.size()); |
+ getInsnsToInstrument(BB, InterestingAccess, IsInstrumented, ToInstrument, |
+ NoReturnCalls); |
+ } |
+ return true; |
+} |
+ |
+void AddressSanitizer::sccAnalyzeComponent( |
+ unsigned ComponentIndex, |
+ std::vector<SCCBlock> &SCC, |
+ const MapVector<Value*, unsigned> &InterestingAccess, |
+ SmallVector<Instruction*, 16> &ToInstrument, |
+ SmallVector<Instruction*, 8> &NoReturnCalls) { |
+ SCCBlock &Component = SCC[ComponentIndex]; |
+ BitVector IsInstrumented(InterestingAccess.size()); |
+ Component.IsInstrumented.resize(InterestingAccess.size()); |
+ if (!Component.HasCallInstruction) { |
+ // Constructs pre-invariant BitVector. i-th element of |
+ // IsInstrumented is true iff it's guaranteed that i-th memory |
+ // access from InterestingAccess do not require instrumentation. |
+ if (!Component.Preds.empty()) { |
+ IsInstrumented.set(0, InterestingAccess.size()); |
+ for (std::vector<unsigned>::iterator SI = Component.Preds.begin(), |
+ SE = Component.Preds.end(); SI != SE; ++SI) { |
+ IsInstrumented &= SCC[*SI].IsInstrumented; |
+ } |
+ } |
+ Component.IsInstrumented.set(); |
+ } |
+ |
+ // Iterate over all entry blocks and update pre-invariant vector for |
+ // inner blocks. |
+ for (std::vector<BasicBlock*>::iterator I = Component.EntryBlocks.begin(), |
+ E = Component.EntryBlocks.end(); I != E; ++I) { |
+ BitVector PostEntryInstrumented(IsInstrumented); |
+ BasicBlock *BB = *I; |
+ assert(BB); |
+ getInsnsToInstrument(*BB, InterestingAccess, PostEntryInstrumented, |
+ ToInstrument, NoReturnCalls); |
+ Component.IsInstrumented &= PostEntryInstrumented; |
+ } |
+ |
+ // Iterate over all inner blocks. |
+ for (std::vector<BasicBlock*>::iterator I = Component.InnerBlocks.begin(), |
+ E = Component.InnerBlocks.end(); I != E; ++I) { |
+ BitVector PreInnerInstrumented(Component.IsInstrumented); |
+ BasicBlock *BB = *I; |
+ assert(BB); |
+ getInsnsToInstrument(*BB, InterestingAccess, PreInnerInstrumented, |
+ ToInstrument, NoReturnCalls); |
+ } |
+} |
+ |
+void AddressSanitizer::sccAddComponent( |
+ std::vector<BasicBlock*> &BasicBlocks, |
+ std::map<BasicBlock*, unsigned> &SCCMapping, |
+ std::vector<SCCBlock> &SCC) { |
+ unsigned NewComponentIndex = SCC.size(); |
+ SCC.push_back(SCCBlock()); |
+ SCCBlock &Component = SCC.back(); |
+ Component.HasCallInstruction = false; |
+ for (std::vector<BasicBlock*>::iterator I = BasicBlocks.begin(), |
+ E = BasicBlocks.end(); I != E; ++I) { |
+ BasicBlock *BB = *I; |
+ SCCMapping[BB] = NewComponentIndex; |
+ if (hasCallInstruction(*BB)) |
+ Component.HasCallInstruction = true; |
+ } |
+ for (std::vector<BasicBlock*>::iterator I = BasicBlocks.begin(), |
+ E = BasicBlocks.end(); I != E; ++I) { |
+ BasicBlock *BB = *I; |
+ assert(BB); |
+ bool IsEntryBlock = (pred_begin(BB) == pred_end(BB)); |
+ for (pred_iterator BI = pred_begin(BB), BE = pred_end(BB); BI != BE; ++BI) { |
+ BasicBlock *PredBB = *BI; |
+ assert(SCCMapping.find(PredBB) != SCCMapping.end()); |
+ if (SCCMapping[PredBB] != NewComponentIndex) { |
+ Component.Preds.push_back(SCCMapping[PredBB]); |
+ IsEntryBlock = true; |
+ } |
+ } |
+ if (IsEntryBlock) |
+ Component.EntryBlocks.push_back(BB); |
+ else |
+ Component.InnerBlocks.push_back(BB); |
+ } |
+ |
+ // Remove duplicates from the list of predessors. |
+ std::sort(Component.Preds.begin(), Component.Preds.end()); |
+ Component.Preds.resize(std::unique(Component.Preds.begin(), |
+ Component.Preds.end()) - |
+ Component.Preds.begin()); |
+} |
+ |
+bool AddressSanitizer::sccAnalyzeFunction( |
+ Function &F, |
+ SmallVector<Instruction*, 16> &ToInstrument, |
+ SmallVector<Instruction*, 8> &NoReturnCalls) { |
+ if (!CanInstrumentFunction(F)) |
+ return false; |
+ |
+ // Can't use SCC analysis when function has more than one entry |
+ // basic blocks. |
+ int NumEntryNodes = 0; |
+ for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { |
+ if (pred_begin(FI) == pred_end(FI)) |
+ ++NumEntryNodes; |
+ } |
+ if (NumEntryNodes != 1) |
+ return false; |
+ |
+ // List of all interesting memory accesses. |
+ MapVector<Value*, unsigned> InterestingAccess; |
+ for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) |
+ getInterestingAccesses(*FI, InterestingAccess); |
+ |
+ std::vector<std::vector<BasicBlock*> > SCCBlocks; |
+ |
+ // Add SCCs in the topological order (the entry node goes last). |
+ for (scc_iterator<Function*> SCCI = scc_begin(&F), SCCE = scc_end(&F); |
+ SCCI != SCCE; ++SCCI) { |
+ SCCBlocks.push_back(*SCCI); |
+ } |
+ |
+ // Reverse order, so the entry node goes first. |
+ std::reverse(SCCBlocks.begin(), SCCBlocks.end()); |
+ |
+ // Vector of SCCs. |
+ std::vector<SCCBlock> SCC; |
+ |
+ // Maps each BasicBlock to the index of the corresponding SCC. |
+ std::map<BasicBlock*, unsigned> SCCMapping; |
+ |
+ for (size_t i = 0; i < SCCBlocks.size(); ++i) |
+ sccAddComponent(SCCBlocks[i], SCCMapping, SCC); |
+ |
+ // Analyze SCCs in the topological order. |
+ for (unsigned I = 0; I < SCC.size(); ++I) |
+ sccAnalyzeComponent(I, SCC, InterestingAccess, ToInstrument, NoReturnCalls); |
+ |
+ return true; |
+} |
+ |
static uint64_t ValueForPoison(uint64_t PoisonByte, size_t ShadowRedzoneSize) { |
if (ShadowRedzoneSize == 1) return PoisonByte; |
if (ShadowRedzoneSize == 2) return (PoisonByte << 8) + PoisonByte; |
@@ -1215,6 +1487,17 @@ bool AddressSanitizer::LooksLikeCodeInBug11395(Instruction *I) { |
return true; |
} |
+bool AddressSanitizer::CanInstrumentFunction(Function &F) { |
+ for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { |
+ for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); |
+ BI != BE; ++BI) { |
+ if (LooksLikeCodeInBug11395(BI)) |
+ return false; |
+ } |
+ } |
+ return true; |
+} |
+ |
void FunctionStackPoisoner::initializeCallbacks(Module &M) { |
IRBuilder<> IRB(*C); |
AsanStackMallocFunc = checkInterfaceFunction(M.getOrInsertFunction( |