[analyzer] Overhaul how the static analyzer expects CFGs by forcing CFGs to be linearized only when used by the static analyzer. This required a rewrite of LiveVariables, and exposed a ton of subtle bugs.
The motivation of this large change is to drastically simplify the logic in ExprEngine going forward.
Some fallout is that the output of some BugReporterVisitors is not as accurate as before; those will
need to be fixed over time. There is also some possible performance regression as RemoveDeadBindings
will be called frequently; this can also be improved over time.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@136419 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp b/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp
index 2c5a1a2..f86bf55 100644
--- a/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp
+++ b/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp
@@ -68,12 +68,12 @@
}
namespace {
-class DeadStoreObs : public LiveVariables::ObserverTy {
+class DeadStoreObs : public LiveVariables::Observer {
const CFG &cfg;
ASTContext &Ctx;
BugReporter& BR;
ParentMap& Parents;
- llvm::SmallPtrSet<VarDecl*, 20> Escaped;
+ llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
llvm::OwningPtr<ReachableCode> reachableCode;
const CFGBlock *currentBlock;
@@ -82,13 +82,14 @@
public:
DeadStoreObs(const CFG &cfg, ASTContext &ctx,
BugReporter& br, ParentMap& parents,
- llvm::SmallPtrSet<VarDecl*, 20> &escaped)
+ llvm::SmallPtrSet<const VarDecl*, 20> &escaped)
: cfg(cfg), Ctx(ctx), BR(br), Parents(parents),
Escaped(escaped), currentBlock(0) {}
virtual ~DeadStoreObs() {}
- void Report(VarDecl* V, DeadStoreKind dsk, SourceLocation L, SourceRange R) {
+ void Report(const VarDecl* V, DeadStoreKind dsk,
+ SourceLocation L, SourceRange R) {
if (Escaped.count(V))
return;
@@ -134,10 +135,9 @@
BR.EmitBasicReport(BugType, "Dead store", msg, L, R);
}
- void CheckVarDecl(VarDecl* VD, Expr* Ex, Expr* Val,
+ void CheckVarDecl(const VarDecl* VD, const Expr* Ex, const Expr* Val,
DeadStoreKind dsk,
- const LiveVariables::AnalysisDataTy& AD,
- const LiveVariables::ValTy& Live) {
+ const LiveVariables::LivenessValues &Live) {
if (!VD->hasLocalStorage())
return;
@@ -146,30 +146,29 @@
if (VD->getType()->getAs<ReferenceType>())
return;
- if (!Live(VD, AD) &&
+ if (!Live.isLive(VD) &&
!(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>()))
Report(VD, dsk, Ex->getSourceRange().getBegin(),
Val->getSourceRange());
}
- void CheckDeclRef(DeclRefExpr* DR, Expr* Val, DeadStoreKind dsk,
- const LiveVariables::AnalysisDataTy& AD,
- const LiveVariables::ValTy& Live) {
- if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
- CheckVarDecl(VD, DR, Val, dsk, AD, Live);
+ void CheckDeclRef(const DeclRefExpr* DR, const Expr* Val, DeadStoreKind dsk,
+ const LiveVariables::LivenessValues& Live) {
+ if (const VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
+ CheckVarDecl(VD, DR, Val, dsk, Live);
}
- bool isIncrement(VarDecl* VD, BinaryOperator* B) {
+ bool isIncrement(VarDecl* VD, const BinaryOperator* B) {
if (B->isCompoundAssignmentOp())
return true;
- Expr* RHS = B->getRHS()->IgnoreParenCasts();
- BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
+ const Expr* RHS = B->getRHS()->IgnoreParenCasts();
+ const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
if (!BRHS)
return false;
- DeclRefExpr *DR;
+ const DeclRefExpr *DR;
if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
if (DR->getDecl() == VD)
@@ -182,9 +181,8 @@
return false;
}
- virtual void ObserveStmt(Stmt* S, const CFGBlock *block,
- const LiveVariables::AnalysisDataTy& AD,
- const LiveVariables::ValTy& Live) {
+ virtual void observeStmt(const Stmt* S, const CFGBlock *block,
+ const LiveVariables::LivenessValues &Live) {
currentBlock = block;
@@ -194,7 +192,7 @@
// Only cover dead stores from regular assignments. ++/-- dead stores
// have never flagged a real bug.
- if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
+ if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
if (!B->isAssignmentOp()) return; // Skip non-assignments.
if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()))
@@ -220,26 +218,26 @@
? Enclosing
: (isIncrement(VD,B) ? DeadIncrement : Standard);
- CheckVarDecl(VD, DR, B->getRHS(), dsk, AD, Live);
+ CheckVarDecl(VD, DR, B->getRHS(), dsk, Live);
}
}
- else if (UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
+ else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
if (!U->isIncrementOp() || U->isPrefix())
return;
- Stmt *parent = Parents.getParentIgnoreParenCasts(U);
+ const Stmt *parent = Parents.getParentIgnoreParenCasts(U);
if (!parent || !isa<ReturnStmt>(parent))
return;
- Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
+ const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
- if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(Ex))
- CheckDeclRef(DR, U, DeadIncrement, AD, Live);
+ if (const DeclRefExpr* DR = dyn_cast<DeclRefExpr>(Ex))
+ CheckDeclRef(DR, U, DeadIncrement, Live);
}
- else if (DeclStmt* DS = dyn_cast<DeclStmt>(S))
+ else if (const DeclStmt* DS = dyn_cast<DeclStmt>(S))
// Iterate through the decls. Warn if any initializers are complex
// expressions that are not live (never used).
- for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE=DS->decl_end();
+ for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end();
DI != DE; ++DI) {
VarDecl* V = dyn_cast<VarDecl>(*DI);
@@ -265,7 +263,7 @@
// A dead initialization is a variable that is dead after it
// is initialized. We don't flag warnings for those variables
// marked 'unused'.
- if (!Live(V, AD) && V->getAttr<UnusedAttr>() == 0) {
+ if (!Live.isLive(V) && V->getAttr<UnusedAttr>() == 0) {
// Special case: check for initializations with constants.
//
// e.g. : int x = 0;
@@ -318,7 +316,7 @@
CFG& getCFG() { return *cfg; }
- llvm::SmallPtrSet<VarDecl*, 20> Escaped;
+ llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
void VisitUnaryOperator(UnaryOperator* U) {
// Check for '&'. Any VarDecl whose value has its address-taken we
@@ -351,7 +349,7 @@
FindEscaped FS(&cfg);
FS.getCFG().VisitBlockStmts(FS);
DeadStoreObs A(cfg, BR.getContext(), BR, pmap, FS.Escaped);
- L->runOnAllBlocks(cfg, &A);
+ L->runOnAllBlocks(A);
}
}
};
diff --git a/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp b/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp
index b540bce..69081a9 100644
--- a/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp
+++ b/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp
@@ -111,13 +111,19 @@
// FIXME: This should be extended to include other unreachable markers,
// such as llvm_unreachable.
if (!CB->empty()) {
- CFGElement First = CB->front();
- if (const CFGStmt *S = First.getAs<CFGStmt>()) {
- if (const CallExpr *CE = dyn_cast<CallExpr>(S->getStmt())) {
- if (CE->isBuiltinCall(Ctx) == Builtin::BI__builtin_unreachable)
- continue;
- }
+ bool foundUnreachable = false;
+ for (CFGBlock::const_iterator ci = CB->begin(), ce = CB->end();
+ ci != ce; ++ci) {
+ if (const CFGStmt *S = (*ci).getAs<CFGStmt>())
+ if (const CallExpr *CE = dyn_cast<CallExpr>(S->getStmt())) {
+ if (CE->isBuiltinCall(Ctx) == Builtin::BI__builtin_unreachable) {
+ foundUnreachable = true;
+ break;
+ }
+ }
}
+ if (foundUnreachable)
+ continue;
}
// We found a block that wasn't covered - find the statement to report
diff --git a/lib/StaticAnalyzer/Core/AnalysisManager.cpp b/lib/StaticAnalyzer/Core/AnalysisManager.cpp
index 274d7a6..543388e 100644
--- a/lib/StaticAnalyzer/Core/AnalysisManager.cpp
+++ b/lib/StaticAnalyzer/Core/AnalysisManager.cpp
@@ -35,6 +35,7 @@
EagerlyAssume(eager), TrimGraph(trim), InlineCall(inlinecall),
EagerlyTrimEGraph(eagerlyTrimEGraph)
{
+ AnaCtxMgr.getCFGBuildOptions().setAllAlwaysAdd();
}
AnalysisContext *
diff --git a/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp b/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp
index 8e31ade..75e232f 100644
--- a/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp
+++ b/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp
@@ -39,8 +39,6 @@
return ME->getBase()->IgnoreParenCasts();
}
else if (const ArraySubscriptExpr *AE = dyn_cast<ArraySubscriptExpr>(S)) {
- // Retrieve the base for arrays since BasicStoreManager doesn't know how
- // to reason about them.
return AE->getBase();
}
@@ -314,6 +312,21 @@
return;
GRStateManager &StateMgr = BRC.getStateManager();
+
+ // Walk through nodes until we get one that matches the statement
+ // exactly.
+ while (N) {
+ const ProgramPoint &pp = N->getLocation();
+ if (const PostStmt *ps = dyn_cast<PostStmt>(&pp)) {
+ if (ps->getStmt() == S)
+ break;
+ }
+ N = *N->pred_begin();
+ }
+
+ if (!N)
+ return;
+
const GRState *state = N->getState();
// Walk through lvalue-to-rvalue conversions.
diff --git a/lib/StaticAnalyzer/Core/Environment.cpp b/lib/StaticAnalyzer/Core/Environment.cpp
index 4a2d33d..92c4a4c 100644
--- a/lib/StaticAnalyzer/Core/Environment.cpp
+++ b/lib/StaticAnalyzer/Core/Environment.cpp
@@ -158,8 +158,6 @@
const GRState *ST,
SmallVectorImpl<const MemRegion*> &DRoots) {
- CFG &C = *SymReaper.getLocationContext()->getCFG();
-
// We construct a new Environment object entirely, as this is cheaper than
// individually removing all the subexpression bindings (which will greatly
// outnumber block-level expression bindings).
@@ -172,7 +170,6 @@
I != E; ++I) {
const Stmt *BlkExpr = I.getKey();
-
// For recorded locations (used when evaluating loads and stores), we
// consider them live only when their associated normal expression is
// also live.
@@ -182,28 +179,8 @@
deferredLocations.push_back(std::make_pair(BlkExpr, I.getData()));
continue;
}
-
const SVal &X = I.getData();
- // Block-level expressions in callers are assumed always live.
- if (isBlockExprInCallers(BlkExpr, SymReaper.getLocationContext())) {
- NewEnv.ExprBindings = F.add(NewEnv.ExprBindings, BlkExpr, X);
-
- if (isa<loc::MemRegionVal>(X)) {
- const MemRegion* R = cast<loc::MemRegionVal>(X).getRegion();
- DRoots.push_back(R);
- }
-
- // Mark all symbols in the block expr's value live.
- MarkLiveCallback cb(SymReaper);
- ST->scanReachableSymbols(X, cb);
- continue;
- }
-
- // Not a block-level expression?
- if (!C.isBlkExpr(BlkExpr))
- continue;
-
if (SymReaper.isLive(BlkExpr)) {
// Copy the binding to the new map.
NewEnv.ExprBindings = F.add(NewEnv.ExprBindings, BlkExpr, X);
diff --git a/lib/StaticAnalyzer/Core/ExprEngine.cpp b/lib/StaticAnalyzer/Core/ExprEngine.cpp
index 003c0f3..2c7ad63 100644
--- a/lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ b/lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -244,7 +244,7 @@
// Create the cleaned state.
const LocationContext *LC = EntryNode->getLocationContext();
- SymbolReaper SymReaper(LC, currentStmt, SymMgr);
+ SymbolReaper SymReaper(LC, currentStmt, SymMgr, getStoreManager());
if (AMgr.shouldPurgeDead()) {
const GRState *St = EntryNode->getState();
diff --git a/lib/StaticAnalyzer/Core/GRState.cpp b/lib/StaticAnalyzer/Core/GRState.cpp
index cbc4909..370f98a 100644
--- a/lib/StaticAnalyzer/Core/GRState.cpp
+++ b/lib/StaticAnalyzer/Core/GRState.cpp
@@ -78,8 +78,11 @@
state, RegionRoots);
// Clean up the store.
- NewState.setStore(StoreMgr->removeDeadBindings(NewState.getStore(), LCtx,
- SymReaper, RegionRoots));
+ StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx,
+ SymReaper, RegionRoots);
+ NewState.setStore(newStore);
+ SymReaper.setReapedStore(newStore);
+
state = getPersistentState(NewState);
return ConstraintMgr->removeDeadBindings(state, SymReaper);
}
@@ -519,9 +522,9 @@
namespace {
class ScanReachableSymbols : public SubRegionMap::Visitor {
- typedef llvm::DenseSet<const MemRegion*> VisitedRegionsTy;
+ typedef llvm::DenseMap<const void*, unsigned> VisitedItems;
- VisitedRegionsTy visited;
+ VisitedItems visited;
const GRState *state;
SymbolVisitor &visitor;
llvm::OwningPtr<SubRegionMap> SRM;
@@ -533,6 +536,7 @@
bool scan(nonloc::CompoundVal val);
bool scan(SVal val);
bool scan(const MemRegion *R);
+ bool scan(const SymExpr *sym);
// From SubRegionMap::Visitor.
bool Visit(const MemRegion* Parent, const MemRegion* SubRegion) {
@@ -549,6 +553,33 @@
return true;
}
+bool ScanReachableSymbols::scan(const SymExpr *sym) {
+ unsigned &isVisited = visited[sym];
+ if (isVisited)
+ return true;
+ isVisited = 1;
+
+ if (const SymbolData *sData = dyn_cast<SymbolData>(sym))
+ if (!visitor.VisitSymbol(sData))
+ return false;
+
+ switch (sym->getKind()) {
+ case SymExpr::RegionValueKind:
+ case SymExpr::ConjuredKind:
+ case SymExpr::DerivedKind:
+ case SymExpr::ExtentKind:
+ case SymExpr::MetadataKind:
+ break;
+ case SymExpr::SymIntKind:
+ return scan(cast<SymIntExpr>(sym)->getLHS());
+ case SymExpr::SymSymKind: {
+ const SymSymExpr *x = cast<SymSymExpr>(sym);
+ return scan(x->getLHS()) && scan(x->getRHS());
+ }
+ }
+ return true;
+}
+
bool ScanReachableSymbols::scan(SVal val) {
if (loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(&val))
return scan(X->getRegion());
@@ -557,7 +588,10 @@
return scan(X->getLoc());
if (SymbolRef Sym = val.getAsSymbol())
- return visitor.VisitSymbol(Sym);
+ return scan(Sym);
+
+ if (const SymExpr *Sym = val.getAsSymbolicExpression())
+ return scan(Sym);
if (nonloc::CompoundVal *X = dyn_cast<nonloc::CompoundVal>(&val))
return scan(*X);
@@ -566,10 +600,13 @@
}
bool ScanReachableSymbols::scan(const MemRegion *R) {
- if (isa<MemSpaceRegion>(R) || visited.count(R))
+ if (isa<MemSpaceRegion>(R))
return true;
-
- visited.insert(R);
+
+ unsigned &isVisited = visited[R];
+ if (isVisited)
+ return true;
+ isVisited = 1;
// If this is a symbolic region, visit the symbol for the region.
if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
diff --git a/lib/StaticAnalyzer/Core/SymbolManager.cpp b/lib/StaticAnalyzer/Core/SymbolManager.cpp
index b55c969..7ae338e 100644
--- a/lib/StaticAnalyzer/Core/SymbolManager.cpp
+++ b/lib/StaticAnalyzer/Core/SymbolManager.cpp
@@ -15,6 +15,7 @@
#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
#include "clang/Analysis/Analyses/LiveVariables.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
#include "llvm/Support/raw_ostream.h"
using namespace clang;
@@ -272,7 +273,7 @@
return Reaper.isLive(SR->getSymbol());
if (const VarRegion *VR = dyn_cast<VarRegion>(MR))
- return Reaper.isLive(VR);
+ return Reaper.isLive(VR, true);
// FIXME: This is a gross over-approximation. What we really need is a way to
// tell if anything still refers to this region. Unlike SymbolicRegions,
@@ -331,13 +332,35 @@
isLive(Loc, ExprVal);
}
-bool SymbolReaper::isLive(const VarRegion *VR) const {
+bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{
const StackFrameContext *VarContext = VR->getStackFrame();
const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame();
- if (VarContext == CurrentContext)
- return LCtx->getAnalysisContext()->getRelaxedLiveVariables()->
- isLive(Loc, VR->getDecl());
+ if (VarContext == CurrentContext) {
+ if (LCtx->getAnalysisContext()->getRelaxedLiveVariables()->
+ isLive(Loc, VR->getDecl()))
+ return true;
+
+ if (!includeStoreBindings)
+ return false;
+
+ unsigned &cachedQuery =
+ const_cast<SymbolReaper*>(this)->includedRegionCache[VR];
+
+ if (cachedQuery) {
+ return cachedQuery == 1;
+ }
+
+ // Query the store to see if the region occurs in any live bindings.
+ if (Store store = reapedStore.getStore()) {
+ bool hasRegion =
+ reapedStore.getStoreManager().includedInBindings(store, VR);
+ cachedQuery = hasRegion ? 1 : 2;
+ return hasRegion;
+ }
+
+ return false;
+ }
return VarContext->isParentOf(CurrentContext);
}