szepet created this revision.
Herald added subscribers: baloghadamsoftware, whisperity.
This patch adds a LoopExit element to the CFG whenever a loop is exited by a
ReturnStmt, GotoStmt or IndirectGotoStmt.
The LoopExit element is consumed by the Static Analyzer in order to simulate
the loops more precisely. This patch aims to ensure that the simulation will be
always consistent. So, whenever a loop is entered a loop exit element will be
encountered after leaving it.
The idea is the following: In cases where a 'jump' is made we check (by walking
up on the AST) the containing loops for both (From and To) locations. Then,
generate the LoopExit element for the exited loops (which is the difference of
the two "containing loop" set.
Note: In case of IndirectGotoStmt, it could happen that we generate LoopExit
elements even for loops which is not exited by that jump. However, it does not
seem to be a problem. This could result that we can not apply some more precise
modeling feature (like unrolling and widening) but not any more - as I can see.
(Also, this is a rare case.)
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,540 @@
// 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: 0
+// CHECK-NEXT: 2: return [B5.1];
+// CHECK-NEXT: 3: WhileStmt (LoopExit)
+// CHECK-NEXT: 4: ForStmt (LoopExit)
+// 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: 0
+// CHECK-NEXT: 3: return [B3.2];
+// CHECK-NEXT: 4: ForStmt (LoopExit)
+// 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;
+}
+
+// CHECK: [B14 (ENTRY)]
+// CHECK-NEXT: Succs (1): B13
+
+// CHECK: [B1]
+// CHECK-NEXT: lab3:
+// CHECK-NEXT: 1: return;
+// CHECK-NEXT: Preds (2): B2 B6
+// CHECK-NEXT: Succs (1): B0
+
+// CHECK: [B2]
+// CHECK-NEXT: 1: ForStmt (LoopExit)
+// CHECK-NEXT: Preds (1): B10
+// CHECK-NEXT: Succs (1): B1
+
+// CHECK: [B3]
+// CHECK-NEXT: 1: i
+// CHECK-NEXT: 2: [B3.1]++
+// CHECK-NEXT: Preds (1): B4
+// CHECK-NEXT: Succs (1): B10
+
+// CHECK: [B4]
+// CHECK-NEXT: 1: WhileStmt (LoopExit)
+// CHECK-NEXT: Preds (1): B8
+// CHECK-NEXT: Succs (1): B3
+
+// CHECK: [B5]
+// CHECK-NEXT: Succs (1): B8
+
+// CHECK: [B6 (INDIRECT GOTO DISPATCH)]
+// CHECK-NEXT: Preds (1): B7
+// CHECK-NEXT: Succs (3): B1 B9 B11
+
+// CHECK: [B7]
+// CHECK-NEXT: 1: lab
+// CHECK-NEXT: 2: [B7.1] (ImplicitCastExpr, LValueToRValue, void *)
+// CHECK-NEXT: 3: [B7.2] (ImplicitCastExpr, NoOp, const void *)
+// CHECK-NEXT: 4: WhileStmt (LoopExit)
+// CHECK-NEXT: 5: ForStmt (LoopExit)
+// CHECK-NEXT: T: goto *[B7.3]
+// CHECK-NEXT: Preds (1): B8
+// CHECK-NEXT: Succs (1): B6
+
+// CHECK: [B8]
+// CHECK-NEXT: 1: j
+// CHECK-NEXT: 2: [B8.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 12
+// CHECK-NEXT: 4: [B8.2] < [B8.3]
+// CHECK-NEXT: T: while [B8.4]
+// CHECK-NEXT: Preds (2): B5 B9
+// CHECK-NEXT: Succs (2): B7 B4
+
+// CHECK: [B9]
+// CHECK-NEXT: lab2:
+// CHECK-NEXT: 1: 1
+// CHECK-NEXT: 2: int j = 1;
+// CHECK-NEXT: 3: labels
+// CHECK-NEXT: 4: [B9.3] (ImplicitCastExpr, ArrayToPointerDecay, void **)
+// CHECK-NEXT: 5: i
+// CHECK-NEXT: 6: [B9.5] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 7: [B9.4] + [B9.6]
+// CHECK-NEXT: 8: *([B9.7])
+// CHECK-NEXT: 9: [B9.8] (ImplicitCastExpr, LValueToRValue, void *)
+// CHECK-NEXT: 10: void *lab = *(labels + i);
+// CHECK-NEXT: Preds (2): B10 B6
+// CHECK-NEXT: Succs (1): B8
+
+// CHECK: [B10]
+// CHECK-NEXT: 1: i
+// CHECK-NEXT: 2: [B10.1] (ImplicitCastExpr, LValueToRValue, int)
+// CHECK-NEXT: 3: 10
+// CHECK-NEXT: 4: [B10.2] < [B10.3]
+// CHECK-NEXT: T: for (...; [B10.4]; ...)
+// CHECK-NEXT: Preds (2): B3 B11
+// CHECK-NEXT: Succs (2): B9 B2
+
+// CHECK: [B11]
+// CHECK-NEXT: lab1:
+// CHECK-NEXT: 1: 0
+// CHECK-NEXT: 2: int i = 0;
+// CHECK-NEXT: Preds (3): B12 B13 B6
+// CHECK-NEXT: Succs (1): B10
+
+// CHECK: [B12]
+// CHECK-NEXT: 1: &&lab1
+// CHECK-NEXT: 2: &&lab2
+// CHECK-NEXT: 3: &&lab3
+// CHECK-NEXT: 4: {[B12.1], [B12.2], [B12.3]}
+// CHECK-NEXT: 5: static void *labels[] = {&&lab1, &&lab2, &&lab3};
+// CHECK-NEXT: Preds (1): B13
+// CHECK-NEXT: Succs (1): B11
+
+// CHECK: [B13]
+// CHECK-NEXT: T: static init labels
+// CHECK-NEXT: Preds (1): B14
+// CHECK-NEXT: Succs (2): B11 B12
+
+// CHECK: [B0 (EXIT)]
+// CHECK-NEXT: Preds (1): B1
+void check_indirect_goto() {
+ static void *labels[] = {&&lab1, &&lab2, &&lab3};
+lab1:
+ for (int i = 0; i < 10; i++) {
+ lab2:
+ int j = 1;
+ void *lab = *(labels + i);
+ while (j < 12)
+ goto *lab;
+ }
+lab3:
return;
}
Index: lib/Analysis/CFG.cpp
===================================================================
--- lib/Analysis/CFG.cpp
+++ lib/Analysis/CFG.cpp
@@ -21,12 +21,13 @@
#include "clang/AST/StmtVisitor.h"
#include "clang/Basic/Builtins.h"
#include "llvm/ADT/DenseMap.h"
-#include <memory>
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/SaveAndRestore.h"
+#include <memory>
+#include <queue>
using namespace clang;
@@ -610,6 +611,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,
@@ -1267,14 +1270,60 @@
// TODO: Support adding LoopExit element to the CFG in case where the loop is
-// ended by ReturnStmt, GotoStmt or ThrowExpr.
+// ended by a ThrowExpr. Since this element is consumed only by the Static
+// Analyzer - which does not support modeling of ThrowExpr yet - this 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) {
@@ -2470,7 +2519,7 @@
Block = createBlock(false);
addAutomaticObjHandling(ScopePos, LocalScope::const_iterator(), R);
-
+ addLoopExit(R, nullptr);
// If the one of the destructors does not return, we already have the Exit
// block as a successor.
if (!Block->hasNoReturnElement())
@@ -2664,6 +2713,7 @@
addAutomaticObjHandling(ScopePos, JT.scopePosition, G);
addSuccessor(Block, JT.block);
}
+ addLoopExit(G, G->getLabel()->getStmt());
return Block;
}
@@ -3164,6 +3214,7 @@
// The Exit block is the only successor.
addSuccessor(Block, &cfg->getExit());
+ addLoopExit(S, nullptr);
// Add the statement to the block. This may create new blocks if S contains
// control-flow (short-circuit operations).
@@ -3178,13 +3229,15 @@
// Create the new block.
Block = createBlock(false);
- if (TryTerminatedBlock)
+ if (TryTerminatedBlock) {
// The current try statement is the only successor.
addSuccessor(Block, TryTerminatedBlock);
- else
+ addLoopExit(T, TryTerminatedBlock->getTerminator().getStmt());
+ } else {
// otherwise the Exit block is the only successor.
addSuccessor(Block, &cfg->getExit());
-
+ addLoopExit(T, nullptr);
+ }
// Add the statement to the block. This may create new blocks if S contains
// control-flow (short-circuit operations).
return VisitStmt(T, AddStmtChoice::AlwaysAdd);
@@ -3915,6 +3968,7 @@
Block = createBlock(false);
Block->setTerminator(I);
addSuccessor(Block, IBlock);
+ addLoopExit(I, nullptr);
return addStmt(I->getTarget());
}
Index: include/clang/Analysis/CFG.h
===================================================================
--- include/clang/Analysis/CFG.h
+++ include/clang/Analysis/CFG.h
@@ -173,8 +173,9 @@
/// This element is is only produced when building the CFG for the static
/// analyzer and hidden behind the 'cfg-loopexit' analyzer config flag.
///
-/// 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)
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
