Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(368)

Unified Diff: lib/Transforms/Instrumentation/AddressSanitizer.cpp

Issue 8222043: Reduced number of ASAN checks. Base URL: http://llvm.org/git/llvm.git@master
Patch Set: Fix. Created 10 years, 12 months ago
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | no next file » | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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(
« no previous file with comments | « no previous file | no next file » | no next file with comments »

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b