NoQ created this revision.
NoQ added reviewers: dcoughlin, xazax.hun, a_sidorin, george.karpenkov, szepet,
rnkovacs, Szelethus.
Herald added subscribers: cfe-commits, dkrupp, donat.nagy, mikhail.ramalho,
a.sidorin, baloghadamsoftware.
For the first time in years, there seems to be a bug in our "live variables"
analysis, which is an auxiliary data flow analysis that decides which variables
and expressions are live, so that we could collect dead symbols, clean up the
program state, and, ultimately, find memory leaks.
The bug shows up on the move-checker, as demonstrated on attached tests (except
the do-while test, which worked fine, but i added it to make sure it stays that
way). It was originally hidden by D54372 <https://reviews.llvm.org/D54372> and
seems to have been another reason why the hack that was removed in D54372
<https://reviews.llvm.org/D54372> was introduced in the first place.
Consider `checkMoreLoopZombies1()` (other tests are similar). `LiveVariables`
analysis reports that //expression// `e` that constitutes the true-branch of
`if` is live throughout almost the whole body of the loop (!), namely, until
the beginning of `if (true)` "on the next iteration" (quotes because it doesn't
really make sense for live variables analysis, but kinda makes sense for us to
think of it this way). There's a brief period when it doesn't live, but it
quickly becomes live again. The expression, being an lvalue, evaluates to the
`VarRegion` for variable `e`. This means that at least one of the two - the
variable `e` itself and the expression that evaluates to the region `e` - is
always live, and region `e` never becomes dead, and the moved-from state never
gets cleaned up, which leads to an invalid use-after-move report on the second
iteration of the loop.
Expressions don't need to be live after the first statement that contains them
is evaluated. So the liveness analysis was overly conservative in this case,
and it caused problems for a checker that relies on values being cleaned up
perfectly.
It was essential that the expression `e` appears directly as a sub-statement of
`if`, i.e. written without `{`...`}`. Otherwise the compound statement would
have been marked as live instead, which is kinda fine, even if it doesn't make
sense.
Because of that, when the `if`-statement is being evaluated as a terminator,
the generic code that works for pretty much all statements was marking the
expression as live:
for (Stmt *Child : S->children()) {
if (Child)
AddLiveStmt(val.liveStmts, LV.SSetFact, Child);
This caused `e` to be incorrectly marked as live at the end of block that
terminates at `if (true)`, which is propagated to the beginning of that block
(similarly to how in `x ? y : z` expressions `y` and `z` need to live at
operator `x ?`, so that the operator could have been evaluated), which is then
propagated to the while-loop terminator.
This is fixed by specializing the generic case for these control flow operators
to avoid the unnecessary propagation of non-compound-statement branch liveness.
-----
Because i wanted to add more direct tests for this stuff (as we had none), i
had to introduce a new debug checker to dump statement liveness:
`debug.DumpLiveStmts`. Dumps should be human-readable and testable.
These direct tests indicate that the same incorrect behavior does indeed occur
in the do-while loop case, even if it doesn't have much consequences for the
move-checker.
-----
I'll add more tests if i notice that this change increases the number of leaks
Static Analyzer finds.
Repository:
rC Clang
https://reviews.llvm.org/D55566
Files:
include/clang/Analysis/Analyses/LiveVariables.h
include/clang/StaticAnalyzer/Checkers/Checkers.td
lib/Analysis/LiveVariables.cpp
lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
test/Analysis/live-stmts.cpp
test/Analysis/use-after-move.cpp
Index: test/Analysis/use-after-move.cpp
===================================================================
--- test/Analysis/use-after-move.cpp
+++ test/Analysis/use-after-move.cpp
@@ -784,6 +784,45 @@
}
}
+void checkMoreLoopZombies1(bool flag) {
+ while (flag) {
+ Empty e{};
+ if (true)
+ e; // expected-warning {{expression result unused}}
+ Empty f = std::move(e); // no-warning
+ }
+}
+
+bool coin();
+
+void checkMoreLoopZombies2(bool flag) {
+ while (flag) {
+ Empty e{};
+ while (coin())
+ e; // expected-warning {{expression result unused}}
+ Empty f = std::move(e); // no-warning
+ }
+}
+
+void checkMoreLoopZombies3(bool flag) {
+ while (flag) {
+ Empty e{};
+ do
+ e; // expected-warning {{expression result unused}}
+ while (coin());
+ Empty f = std::move(e); // no-warning
+ }
+}
+
+void checkMoreLoopZombies4(bool flag) {
+ while (flag) {
+ Empty e{};
+ for (; coin();)
+ e; // expected-warning {{expression result unused}}
+ Empty f = std::move(e); // no-warning
+ }
+}
+
struct MoveOnlyWithDestructor {
MoveOnlyWithDestructor();
~MoveOnlyWithDestructor();
Index: test/Analysis/live-stmts.cpp
===================================================================
--- /dev/null
+++ test/Analysis/live-stmts.cpp
@@ -0,0 +1,167 @@
+// RUN: %clang_analyze_cc1 -w -analyzer-checker=debug.DumpLiveStmts %s 2>&1\
+// RUN: | FileCheck %s
+
+int coin();
+
+
+int testThatDumperWorks(int x, int y, int z) {
+ return x ? y : z;
+}
+// CHECK: [ B0 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B1 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B2 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'y' 'int'
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'z' 'int'
+// CHECK-EMPTY:
+// CHECK-NEXT: ImplicitCastExpr {{.*}} <IntegralToBoolean>
+// CHECK-NEXT: `-ImplicitCastExpr {{.*}} <LValueToRValue>
+// CHECK-NEXT: `-DeclRefExpr {{.*}} 'x' 'int'
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B3 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'y' 'int'
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'z' 'int'
+// CHECK-EMPTY:
+// CHECK-NEXT: ImplicitCastExpr {{.*}} <IntegralToBoolean>
+// CHECK-NEXT: `-ImplicitCastExpr {{.*}} <LValueToRValue>
+// CHECK-NEXT: `-DeclRefExpr {{.*}} 'x' 'int'
+// CHECK: [ B4 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'y' 'int'
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'z' 'int'
+// CHECK-EMPTY:
+// CHECK-NEXT: ImplicitCastExpr {{.*}} <IntegralToBoolean>
+// CHECK-NEXT: `-ImplicitCastExpr {{.*}} <LValueToRValue>
+// CHECK-NEXT: `-DeclRefExpr {{.*}} 'x' 'int'
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B5 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'y' 'int'
+// CHECK-EMPTY:
+// CHECK-NEXT: DeclRefExpr {{.*}} 'z' 'int'
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+
+
+void testIfBranchExpression(bool flag) {
+ // No expressions should be carried over from one block to another here.
+ while (flag) {
+ int e = 1;
+ if (true)
+ e;
+ }
+}
+// CHECK: [ B0 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B1 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B2 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B3 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B4 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B5 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+
+
+void testWhileBodyExpression(bool flag) {
+ // No expressions should be carried over from one block to another here.
+ while (flag) {
+ int e = 1;
+ while (coin())
+ e;
+ }
+}
+// CHECK: [ B0 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B1 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B2 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B3 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B4 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B5 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+
+
+void testDoWhileBodyExpression(bool flag) {
+ // No expressions should be carried over from one block to another here.
+ while (flag) {
+ int e = 1;
+ do
+ e;
+ while (coin());
+ }
+}
+// CHECK: [ B0 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B1 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B2 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B3 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B4 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B5 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+
+
+void testForBodyExpression(bool flag) {
+ // No expressions should be carried over from one block to another here.
+ while (flag) {
+ int e = 1;
+ for (; coin();)
+ e;
+ }
+}
+// CHECK: [ B0 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B1 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B2 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B3 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B4 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+// CHECK: [ B5 (live statements at block exit) ]
+// CHECK-EMPTY:
+// CHECK-EMPTY:
+
Index: lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
===================================================================
--- lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
+++ lib/StaticAnalyzer/Checkers/DebugCheckers.cpp
@@ -68,6 +68,25 @@
mgr.registerChecker<LiveVariablesDumper>();
}
+//===----------------------------------------------------------------------===//
+// LiveStatementsDumper
+//===----------------------------------------------------------------------===//
+
+namespace {
+class LiveStatementsDumper : public Checker<check::ASTCodeBody> {
+public:
+ void checkASTCodeBody(const Decl *D, AnalysisManager& Mgr,
+ BugReporter &BR) const {
+ if (LiveVariables *L = Mgr.getAnalysis<RelaxedLiveVariables>(D))
+ L->dumpStmtLiveness(Mgr.getSourceManager());
+ }
+};
+}
+
+void ento::registerLiveStatementsDumper(CheckerManager &mgr) {
+ mgr.registerChecker<LiveStatementsDumper>();
+}
+
//===----------------------------------------------------------------------===//
// CFGViewer
//===----------------------------------------------------------------------===//
Index: lib/Analysis/LiveVariables.cpp
===================================================================
--- lib/Analysis/LiveVariables.cpp
+++ lib/Analysis/LiveVariables.cpp
@@ -93,6 +93,7 @@
LiveVariables::Observer *obs = nullptr);
void dumpBlockLiveness(const SourceManager& M);
+ void dumpStmtLiveness(const SourceManager& M);
LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign)
: analysisContext(ac),
@@ -327,6 +328,35 @@
// No need to unconditionally visit subexpressions.
return;
}
+ case Stmt::IfStmtClass: {
+ // If one of the branches is an expression rather than a compound
+ // statement, it will be bad if we mark it as live at the terminator
+ // of the if-statement (i.e., immediately after the condition expression).
+ AddLiveStmt(val.liveStmts, LV.SSetFact, cast<IfStmt>(S)->getCond());
+ return;
+ }
+ case Stmt::WhileStmtClass: {
+ // If the loop body is an expression rather than a compound statement,
+ // it will be bad if we mark it as live at the terminator of the loop
+ // (i.e., immediately after the condition expression).
+ AddLiveStmt(val.liveStmts, LV.SSetFact, cast<WhileStmt>(S)->getCond());
+ return;
+ }
+ case Stmt::DoStmtClass: {
+ // If the loop body is an expression rather than a compound statement,
+ // it will be bad if we mark it as live at the terminator of the loop
+ // (i.e., immediately after the condition expression).
+ AddLiveStmt(val.liveStmts, LV.SSetFact, cast<DoStmt>(S)->getCond());
+ return;
+ }
+ case Stmt::ForStmtClass: {
+ // If the loop body is an expression rather than a compound statement,
+ // it will be bad if we mark it as live at the terminator of the loop
+ // (i.e., immediately after the condition expression).
+ AddLiveStmt(val.liveStmts, LV.SSetFact, cast<ForStmt>(S)->getCond());
+ return;
+ }
+
}
for (Stmt *Child : S->children()) {
@@ -632,5 +662,23 @@
llvm::errs() << "\n";
}
+void LiveVariables::dumpStmtLiveness(const SourceManager &M) {
+ getImpl(impl).dumpStmtLiveness(M);
+}
+
+void LiveVariablesImpl::dumpStmtLiveness(const SourceManager &M) {
+ // Don't iterate over blockEndsToLiveness directly because it's not sorted.
+ for (auto I : *analysisContext.getCFG()) {
+
+ llvm::errs() << "\n[ B" << I->getBlockID()
+ << " (live statements at block exit) ]\n";
+ for (auto S : blocksEndToLiveness[I].liveStmts) {
+ llvm::errs() << "\n";
+ S->dump();
+ }
+ llvm::errs() << "\n";
+ }
+}
+
const void *LiveVariables::getTag() { static int x; return &x; }
const void *RelaxedLiveVariables::getTag() { static int x; return &x; }
Index: include/clang/StaticAnalyzer/Checkers/Checkers.td
===================================================================
--- include/clang/StaticAnalyzer/Checkers/Checkers.td
+++ include/clang/StaticAnalyzer/Checkers/Checkers.td
@@ -704,6 +704,9 @@
def LiveVariablesDumper : Checker<"DumpLiveVars">,
HelpText<"Print results of live variable analysis">;
+def LiveStatementsDumper : Checker<"DumpLiveStmts">,
+ HelpText<"Print results of live variable analysis">;
+
def CFGViewer : Checker<"ViewCFG">,
HelpText<"View Control-Flow Graphs using GraphViz">;
Index: include/clang/Analysis/Analyses/LiveVariables.h
===================================================================
--- include/clang/Analysis/Analyses/LiveVariables.h
+++ include/clang/Analysis/Analyses/LiveVariables.h
@@ -88,9 +88,13 @@
/// before the given block-level expression (see runOnAllBlocks).
bool isLive(const Stmt *Loc, const Stmt *StmtVal);
- /// Print to stderr the liveness information associated with
+ /// Print to stderr the variable liveness information associated with
/// each basic block.
- void dumpBlockLiveness(const SourceManager& M);
+ void dumpBlockLiveness(const SourceManager &M);
+
+ /// Print to stderr the statement liveness information associated with
+ /// each basic block.
+ void dumpStmtLiveness(const SourceManager &M);
void runOnAllBlocks(Observer &obs);
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
