szepet updated this revision to Diff 130503.
szepet marked 2 inline comments as done.
szepet added a comment.
Added comments and removed indirect goto support from this patch.
> This seems a bit scary because if there's no obvious one-to-once
> correspondence between entrances and exits along every path, how would we
> know when to pop loop contexts from the stack of location contexts? Like, if
> we attach variable lifetime checks to the loop exit, would we need to write
> additional code in the analyzer to see if the variable indeed goes out of
> scope on the current path.
Yepp, we should check if the current loop (one quick method on the
LocationContext) belongs to the LoopExit. This was already necessary in the
previous patch since cases like:
if(Cond)
for(;;){...}
stmt1
stmt2
...
In the above example even if `Cond` is false the analyzer will encounter the
LoopExit since it is the first element of the `breakBlock` of the loop. (So it
is within the same block as stmt1 and stmt2)
I have removed IndirectGoto support since it was not precise enough and rather
handle this in the analyzer. (`isPrecisableModelableLoop` function in the
https://reviews.llvm.org/D41151)
https://reviews.llvm.org/D39398
Files:
include/clang/Analysis/CFG.h
lib/Analysis/CFG.cpp
test/Analysis/loopexit-cfg-output.cpp
Index: test/Analysis/loopexit-cfg-output.cpp
===================================================================
--- test/Analysis/loopexit-cfg-output.cpp
+++ test/Analysis/loopexit-cfg-output.cpp
@@ -458,19 +458,428 @@
// CHECK: [B0 (EXIT)]
// CHECK-NEXT: Preds (1): B1
-void check_break()
-{
- for(int i = 2; i < 6; i++) {
- if(i == 4)
+void check_break() {
+ for (int i = 2; i < 6; i++) {
+ if (i == 4)
break;
}
int i = 1;
- while(i<5){
+ while (i < 5) {
i++;
- if(i%2)
+ if (i % 2)
break;
}
-
+
+ return;
+}
+
+// CHECK: [B11 (ENTRY)]
+// CHECK-NEXT: Succs (1): B10
+
+// CHECK: [B1]
+// CHECK-NEXT: 1: ForStmt (LoopExit)
+// CHECK-NEXT: 2: return;
+// CHECK-NEXT: Preds (1): B9
+// CHECK-NEXT: Succs (1): B0
+
+// CHECK: [B2]
+// CHECK-NEXT: 1: i
+// CHECK-NEXT: 2: [B2.1]++
+// CHECK-NEXT: Preds (1): B3
+// CHECK-NEXT: Succs (1): B9
+
+// CHECK: [B3]
+// CHECK-NEXT: 1: WhileStmt (LoopExit)
+// CHECK-NEXT: Preds (1): B7
+// CHECK-NEXT: Succs (1): B2
+
+// CHECK: [B4]
+// CHECK-NEXT: Preds (1): B6
+// CHECK-NEXT: Succs (1): B7
+
+// CHECK: [B5]
+// CHECK-NEXT: 1: WhileStmt (LoopExit)
+// CHECK-NEXT: 2: ForStmt (LoopExit)
+// CHECK-NEXT: T: goto lab;
+// CHECK-NEXT: Preds (1): B6
+// CHECK-NEXT: Succs (1): B10
+
+// CHECK: [B6]
+// CHECK-NEXT: 1: j
+// CHECK-NEXT: 2: [B6.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 2
+// CHECK-NEXT: 4: [B6.2] % [B6.3]
+// CHECK-NEXT: 5: [B6.4] (ImplicitCastExpr, IntegralToBoolean, _Bool)
+// CHECK-NEXT: T: if [B6.5]
+// CHECK-NEXT: Preds (1): B7
+// CHECK-NEXT: Succs (2): B5 B4
+
+// CHECK: [B7]
+// CHECK-NEXT: 1: j
+// CHECK-NEXT: 2: [B7.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 12
+// CHECK-NEXT: 4: [B7.2] < [B7.3]
+// CHECK-NEXT: T: while [B7.4]
+// CHECK-NEXT: Preds (2): B4 B8
+// CHECK-NEXT: Succs (2): B6 B3
+
+// CHECK: [B8]
+// CHECK-NEXT: 1: 1
+// CHECK-NEXT: 2: int j = 1;
+// CHECK-NEXT: Preds (1): B9
+// CHECK-NEXT: Succs (1): B7
+
+// CHECK: [B9]
+// CHECK-NEXT: 1: i
+// CHECK-NEXT: 2: [B9.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 10
+// CHECK-NEXT: 4: [B9.2] < [B9.3]
+// CHECK-NEXT: T: for (...; [B9.4]; ...)
+// CHECK-NEXT: Preds (2): B2 B10
+// CHECK-NEXT: Succs (2): B8 B1
+
+// CHECK: [B10]
+// CHECK-NEXT: lab:
+// CHECK-NEXT: 1: 0
+// CHECK-NEXT: 2: int i = 0;
+// CHECK-NEXT: Preds (2): B5 B11
+// CHECK-NEXT: Succs (1): B9
+
+// CHECK: [B0 (EXIT)]
+// CHECK-NEXT: Preds (1): B1
+void check_goto() {
+lab:
+ for (int i = 0; i < 10; i++) {
+ int j = 1;
+ while (j < 12) {
+ if (j % 2)
+ goto lab;
+ }
+ }
+ return;
+}
+
+// CHECK: [B11 (ENTRY)]
+// CHECK-NEXT: Succs (1): B10
+
+// CHECK: [B1]
+// CHECK-NEXT: 1: ForStmt (LoopExit)
+// CHECK-NEXT: 2: return;
+// CHECK-NEXT: Preds (1): B9
+// CHECK-NEXT: Succs (1): B0
+
+// CHECK: [B2]
+// CHECK-NEXT: 1: i
+// CHECK-NEXT: 2: [B2.1]++
+// CHECK-NEXT: Preds (1): B3
+// CHECK-NEXT: Succs (1): B9
+
+// CHECK: [B3]
+// CHECK-NEXT: 1: WhileStmt (LoopExit)
+// CHECK-NEXT: Preds (1): B7
+// CHECK-NEXT: Succs (1): B2
+
+// CHECK: [B4]
+// CHECK-NEXT: Preds (1): B6
+// CHECK-NEXT: Succs (1): B7
+
+// CHECK: [B5]
+// CHECK-NEXT: 1: WhileStmt (LoopExit)
+// CHECK-NEXT: T: goto lab;
+// CHECK-NEXT: Preds (1): B6
+// CHECK-NEXT: Succs (1): B8
+
+// CHECK: [B6]
+// CHECK-NEXT: 1: j
+// CHECK-NEXT: 2: [B6.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 2
+// CHECK-NEXT: 4: [B6.2] % [B6.3]
+// CHECK-NEXT: 5: [B6.4] (ImplicitCastExpr, IntegralToBoolean, _Bool)
+// CHECK-NEXT: T: if [B6.5]
+// CHECK-NEXT: Preds (1): B7
+// CHECK-NEXT: Succs (2): B5 B4
+
+// CHECK: [B7]
+// CHECK-NEXT: 1: j
+// CHECK-NEXT: 2: [B7.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 12
+// CHECK-NEXT: 4: [B7.2] < [B7.3]
+// CHECK-NEXT: T: while [B7.4]
+// CHECK-NEXT: Preds (2): B4 B8
+// CHECK-NEXT: Succs (2): B6 B3
+
+// CHECK: [B8]
+// CHECK-NEXT: lab:
+// CHECK-NEXT: 1: 1
+// CHECK-NEXT: 2: int j = 1;
+// CHECK-NEXT: Preds (2): B9 B5
+// CHECK-NEXT: Succs (1): B7
+
+// CHECK: [B9]
+// CHECK-NEXT: 1: i
+// CHECK-NEXT: 2: [B9.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 10
+// CHECK-NEXT: 4: [B9.2] < [B9.3]
+// CHECK-NEXT: T: for (...; [B9.4]; ...)
+// CHECK-NEXT: Preds (2): B2 B10
+// CHECK-NEXT: Succs (2): B8 B1
+
+// CHECK: [B10]
+// CHECK-NEXT: 1: 0
+// CHECK-NEXT: 2: int i = 0;
+// CHECK-NEXT: Preds (1): B11
+// CHECK-NEXT: Succs (1): B9
+
+// CHECK: [B0 (EXIT)]
+// CHECK-NEXT: Preds (1): B1
+
+void check_goto2() {
+ for (int i = 0; i < 10; i++) {
+ lab:
+ int j = 1;
+ while (j < 12) {
+ if (j % 2)
+ goto lab;
+ }
+ }
return;
}
+
+// CHECK: [B10 (ENTRY)]
+// CHECK-NEXT: Succs (1): B9
+
+// CHECK: [B1]
+// CHECK-NEXT: 1: ForStmt (LoopExit)
+// CHECK-NEXT: 2: return;
+// CHECK-NEXT: Preds (1): B8
+// CHECK-NEXT: Succs (1): B0
+
+// CHECK: [B2]
+// CHECK-NEXT: 1: i
+// CHECK-NEXT: 2: [B2.1]++
+// CHECK-NEXT: Preds (1): B3
+// CHECK-NEXT: Succs (1): B8
+
+// CHECK: [B3]
+// CHECK-NEXT: 1: WhileStmt (LoopExit)
+// CHECK-NEXT: Preds (1): B6
+// CHECK-NEXT: Succs (1): B2
+
+// CHECK: [B4]
+// CHECK-NEXT: Preds (1): B5
+// CHECK-NEXT: Succs (1): B6
+
+// CHECK: [B5]
+// CHECK-NEXT: lab:
+// CHECK-NEXT: 1: 2
+// CHECK-NEXT: 2: j
+// CHECK-NEXT: 3: [B5.2] = [B5.1]
+// CHECK-NEXT: Preds (2): B6 B7
+// CHECK-NEXT: Succs (1): B4
+
+// CHECK: [B6]
+// CHECK-NEXT: 1: j
+// CHECK-NEXT: 2: [B6.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 12
+// CHECK-NEXT: 4: [B6.2] < [B6.3]
+// CHECK-NEXT: T: while [B6.4]
+// CHECK-NEXT: Preds (1): B4
+// CHECK-NEXT: Succs (2): B5 B3
+
+// CHECK: [B7]
+// CHECK-NEXT: 1: 1
+// CHECK-NEXT: 2: int j = 1;
+// CHECK-NEXT: T: goto lab;
+// CHECK-NEXT: Preds (1): B8
+// CHECK-NEXT: Succs (1): B5
+
+// CHECK: [B8]
+// CHECK-NEXT: 1: i
+// CHECK-NEXT: 2: [B8.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 10
+// CHECK-NEXT: 4: [B8.2] < [B8.3]
+// CHECK-NEXT: T: for (...; [B8.4]; ...)
+// CHECK-NEXT: Preds (2): B2 B9
+// CHECK-NEXT: Succs (2): B7 B1
+
+// CHECK: [B9]
+// CHECK-NEXT: 1: 0
+// CHECK-NEXT: 2: int i = 0;
+// CHECK-NEXT: Preds (1): B10
+// CHECK-NEXT: Succs (1): B8
+
+// CHECK: [B0 (EXIT)]
+// CHECK-NEXT: Preds (1): B1
+void check_goto3() {
+ for (int i = 0; i < 10; i++) {
+ int j = 1;
+ goto lab;
+ while (j < 12) {
+ lab:
+ j = 2;
+ }
+ }
+ return;
+}
+
+// CHECK: [B11 (ENTRY)]
+// CHECK-NEXT: Succs (1): B10
+
+// CHECK: [B1]
+// CHECK-NEXT: 1: ForStmt (LoopExit)
+// CHECK-NEXT: 2: 1
+// CHECK-NEXT: 3: return [B1.2];
+// CHECK-NEXT: Preds (1): B9
+// CHECK-NEXT: Succs (1): B0
+
+// CHECK: [B2]
+// CHECK-NEXT: 1: i
+// CHECK-NEXT: 2: [B2.1]++
+// CHECK-NEXT: Preds (1): B3
+// CHECK-NEXT: Succs (1): B9
+
+// CHECK: [B3]
+// CHECK-NEXT: 1: WhileStmt (LoopExit)
+// CHECK-NEXT: Preds (1): B7
+// CHECK-NEXT: Succs (1): B2
+
+// CHECK: [B4]
+// CHECK-NEXT: Preds (1): B6
+// CHECK-NEXT: Succs (1): B7
+
+// CHECK: [B5]
+// CHECK-NEXT: 1: WhileStmt (LoopExit)
+// CHECK-NEXT: 2: ForStmt (LoopExit)
+// CHECK-NEXT: 3: 0
+// CHECK-NEXT: 4: return [B5.3];
+// CHECK-NEXT: Preds (1): B6
+// CHECK-NEXT: Succs (1): B0
+
+// CHECK: [B6]
+// CHECK-NEXT: 1: j
+// CHECK-NEXT: 2: [B6.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 2
+// CHECK-NEXT: 4: [B6.2] % [B6.3]
+// CHECK-NEXT: 5: [B6.4] (ImplicitCastExpr, IntegralToBoolean, _Bool)
+// CHECK-NEXT: T: if [B6.5]
+// CHECK-NEXT: Preds (1): B7
+// CHECK-NEXT: Succs (2): B5 B4
+
+// CHECK: [B7]
+// CHECK-NEXT: 1: j
+// CHECK-NEXT: 2: [B7.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 12
+// CHECK-NEXT: 4: [B7.2] < [B7.3]
+// CHECK-NEXT: T: while [B7.4]
+// CHECK-NEXT: Preds (2): B4 B8
+// CHECK-NEXT: Succs (2): B6 B3
+
+// CHECK: [B8]
+// CHECK-NEXT: 1: 1
+// CHECK-NEXT: 2: int j = 1;
+// CHECK-NEXT: Preds (1): B9
+// CHECK-NEXT: Succs (1): B7
+
+// CHECK: [B9]
+// CHECK-NEXT: 1: i
+// CHECK-NEXT: 2: [B9.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 10
+// CHECK-NEXT: 4: [B9.2] < [B9.3]
+// CHECK-NEXT: T: for (...; [B9.4]; ...)
+// CHECK-NEXT: Preds (2): B2 B10
+// CHECK-NEXT: Succs (2): B8 B1
+
+// CHECK: [B10]
+// CHECK-NEXT: 1: 0
+// CHECK-NEXT: 2: int i = 0;
+// CHECK-NEXT: Preds (1): B11
+// CHECK-NEXT: Succs (1): B9
+
+// CHECK: [B0 (EXIT)]
+// CHECK-NEXT: Preds (2): B1 B5
+int check_return() {
+ for (int i = 0; i < 10; i++) {
+ int j = 1;
+ while (j < 12) {
+ if (j % 2)
+ return 0;
+ }
+ }
+ return 1;
+}
+
+// CHECK: [B10 (ENTRY)]
+// CHECK-NEXT: Succs (1): B9
+
+// CHECK: [B1]
+// CHECK-NEXT: 1: ForStmt (LoopExit)
+// CHECK-NEXT: 2: 1
+// CHECK-NEXT: 3: return [B1.2];
+// CHECK-NEXT: Preds (1): B8
+// CHECK-NEXT: Succs (1): B0
+
+// CHECK: [B2]
+// CHECK-NEXT: 1: i
+// CHECK-NEXT: 2: [B2.1]++
+// CHECK-NEXT: Succs (1): B8
+
+// CHECK: [B3]
+// CHECK-NEXT: 1: WhileStmt (LoopExit)
+// CHECK-NEXT: 2: ForStmt (LoopExit)
+// CHECK-NEXT: 3: 0
+// CHECK-NEXT: 4: return [B3.3];
+// CHECK-NEXT: Preds (1): B6
+// CHECK-NEXT: Succs (1): B0
+
+// CHECK: [B4]
+// CHECK-NEXT: Preds (1): B5
+// CHECK-NEXT: Succs (1): B6
+
+// CHECK: [B5]
+// CHECK-NEXT: 1: j
+// CHECK-NEXT: 2: [B5.1]++
+// CHECK-NEXT: Preds (1): B6
+// CHECK-NEXT: Succs (1): B4
+
+// CHECK: [B6]
+// CHECK-NEXT: 1: j
+// CHECK-NEXT: 2: [B6.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 12
+// CHECK-NEXT: 4: [B6.2] < [B6.3]
+// CHECK-NEXT: T: while [B6.4]
+// CHECK-NEXT: Preds (2): B4 B7
+// CHECK-NEXT: Succs (2): B5 B3
+
+// CHECK: [B7]
+// CHECK-NEXT: 1: 1
+// CHECK-NEXT: 2: int j = 1;
+// CHECK-NEXT: Preds (1): B8
+// CHECK-NEXT: Succs (1): B6
+
+// CHECK: [B8]
+// CHECK-NEXT: 1: i
+// CHECK-NEXT: 2: [B8.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 10
+// CHECK-NEXT: 4: [B8.2] < [B8.3]
+// CHECK-NEXT: T: for (...; [B8.4]; ...)
+// CHECK-NEXT: Preds (2): B2 B9
+// CHECK-NEXT: Succs (2): B7 B1
+
+// CHECK: [B9]
+// CHECK-NEXT: 1: 0
+// CHECK-NEXT: 2: int i = 0;
+// CHECK-NEXT: Preds (1): B10
+// CHECK-NEXT: Succs (1): B8
+
+// CHECK: [B0 (EXIT)]
+// CHECK-NEXT: Preds (2): B1 B3
+int check_return2() {
+ for (int i = 0; i < 10; i++) {
+ int j = 1;
+ while (j < 12)
+ j++;
+ return 0;
+ }
+ return 1;
+}
\ No newline at end of file
Index: lib/Analysis/CFG.cpp
===================================================================
--- lib/Analysis/CFG.cpp
+++ lib/Analysis/CFG.cpp
@@ -55,6 +55,7 @@
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <memory>
+#include <queue>
#include <string>
#include <tuple>
#include <utility>
@@ -653,6 +654,8 @@
CFGBlock *addInitializer(CXXCtorInitializer *I);
void addLoopExit(const Stmt *LoopStmt);
+ void addLoopExit(const Stmt *FromStmt, const Stmt *ToStmt);
+
void addAutomaticObjDtors(LocalScope::const_iterator B,
LocalScope::const_iterator E, Stmt *S);
void addLifetimeEnds(LocalScope::const_iterator B,
@@ -1317,14 +1320,60 @@
}
// TODO: Support adding LoopExit element to the CFG in case where the loop is
-// ended by ReturnStmt, GotoStmt or ThrowExpr.
+// ended by an IndirectGotoStmt or ThrowExpr. Since this element is consumed
+// only by the Static Analyzer which does not support modeling of ThrowExpr
+// yet, it does not causes any problem.
void CFGBuilder::addLoopExit(const Stmt *LoopStmt){
if(!BuildOpts.AddLoopExit)
return;
autoCreateBlock();
appendLoopExit(Block, LoopStmt);
}
+llvm::SmallSetVector<const Stmt *, 4>
+collectContainingLoops(const Stmt *S, ASTContext &ASTCtx) {
+ llvm::SmallSetVector<const Stmt *, 4> LoopStmts;
+
+ if (!S)
+ return LoopStmts;
+
+ std::queue<ast_type_traits::DynTypedNode> NodesToVisit;
+ NodesToVisit.push(ast_type_traits::DynTypedNode::create(*S));
+
+ while (!NodesToVisit.empty()) {
+ ast_type_traits::DynTypedNode Node = NodesToVisit.front();
+ NodesToVisit.pop();
+
+ for (auto &Parent : ASTCtx.getParents(Node)) {
+ NodesToVisit.push(Parent);
+ }
+
+ const Stmt *LoopStmt = Node.get<Stmt>();
+ if (LoopStmt && (isa<ForStmt>(LoopStmt) || isa<WhileStmt>(LoopStmt) ||
+ isa<DoStmt>(LoopStmt)))
+ LoopStmts.insert(LoopStmt);
+ }
+ return LoopStmts;
+}
+
+void CFGBuilder::addLoopExit(const Stmt *FromStmt, const Stmt *ToStmt) {
+ if (!BuildOpts.AddLoopExit)
+ return;
+
+ llvm::SmallSetVector<const Stmt *, 4> FromLoopStmts =
+ collectContainingLoops(FromStmt, *Context);
+
+ llvm::SmallSetVector<const Stmt *, 4> ToLoopStmts =
+ collectContainingLoops(ToStmt, *Context);
+
+ FromLoopStmts.set_subtract(ToLoopStmts);
+ for (llvm::SmallSetVector<const Stmt *, 4>::reverse_iterator
+ I = FromLoopStmts.rbegin(),
+ E = FromLoopStmts.rend();
+ I != E; ++I)
+ appendLoopExit(Block, *I);
+}
+
void CFGBuilder::addAutomaticObjHandling(LocalScope::const_iterator B,
LocalScope::const_iterator E,
Stmt *S) {
@@ -2524,7 +2573,9 @@
// Add the return statement to the block. This may create new blocks if R
// contains control-flow (short-circuit operations).
- return VisitStmt(R, AddStmtChoice::AlwaysAdd);
+ CFGBlock* ReturnBlock = VisitStmt(R, AddStmtChoice::AlwaysAdd);
+ addLoopExit(R, nullptr);
+ return ReturnBlock;
}
CFGBlock *CFGBuilder::VisitSEHExceptStmt(SEHExceptStmt *ES) {
@@ -2710,6 +2761,7 @@
addAutomaticObjHandling(ScopePos, JT.scopePosition, G);
addSuccessor(Block, JT.block);
}
+ addLoopExit(G, G->getLabel()->getStmt());
return Block;
}
Index: include/clang/Analysis/CFG.h
===================================================================
--- include/clang/Analysis/CFG.h
+++ include/clang/Analysis/CFG.h
@@ -177,10 +177,15 @@
/// Represents the point where a loop ends.
/// This element is is only produced when building the CFG for the static
-/// analyzer and hidden behind the 'cfg-loopexit' analyzer config flag.
+/// analyzer and hidden behind the 'cfg-loopexit' analyzer config flag. It is
+/// placed at the beginning of the block after the loop, however, in special
+/// cases it can appear different positions:
+/// - Right before a ReturnStmt inside the loop
+/// - In the end of a goto terminated block (inside the loop as well)
///
-/// Note: a loop exit element can be reached even when the loop body was never
-/// entered.
+/// Note: whenever a loop is entered a loop exit element will be encountered
+/// after leaving it. However, a loop exit element can be reached even when the
+/// loop body was never entered.
class CFGLoopExit : public CFGElement {
public:
explicit CFGLoopExit(const Stmt *stmt) : CFGElement(LoopExit, stmt) {}
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
