Skip to content

Commit

Permalink
[StaticAnalyzer] LoopUnrolling: Excluding loops which splits the state
Browse files Browse the repository at this point in the history
Added check if the execution of the last step of the given unrolled loop has
generated more branches. If yes, than treat it as a normal (non-unrolled) loop
in the remaining part of the analysis.

Differential Revision: https://reviews.llvm.org/D36962

llvm-svn: 311881
szepet committed Aug 28, 2017
1 parent d91554b commit d0604ac
Showing 2 changed files with 81 additions and 15 deletions.
27 changes: 26 additions & 1 deletion clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp
Original file line number Diff line number Diff line change
@@ -204,6 +204,26 @@ bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred);
}

bool madeNewBranch(ExplodedNode* N, const Stmt* LoopStmt) {
const Stmt* S = nullptr;
while (!N->pred_empty())
{
if (N->succ_size() > 1)
return true;

ProgramPoint P = N->getLocation();
if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>())
S = BE->getBlock()->getTerminator();

if (S == LoopStmt)
return false;

N = N->getFirstPred();
}

llvm_unreachable("Reached root without encountering the previous step");
}

// updateLoopStack is called on every basic block, therefore it needs to be fast
ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx,
ExplodedNode* Pred) {
@@ -215,8 +235,13 @@ ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx,

auto LS = State->get<LoopStack>();
if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() &&
LCtx == LS.getHead().getLocationContext())
LCtx == LS.getHead().getLocationContext()) {
if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) {
State = State->set<LoopStack>(LS.getTail());
State = State->add<LoopStack>(LoopState::getNormal(LoopStmt, LCtx));
}
return State;
}

if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred)) {
State = State->add<LoopStack>(LoopState::getNormal(LoopStmt, LCtx));
69 changes: 55 additions & 14 deletions clang/test/Analysis/loop-unrolling.cpp
Original file line number Diff line number Diff line change
@@ -1,6 +1,7 @@
// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true -verify -std=c++11 %s

void clang_analyzer_numTimesReached();
void clang_analyzer_warnIfReached();

int getNum();
void foo(int &);
@@ -62,8 +63,7 @@ int simple_no_unroll2() {
int simple_no_unroll3() {
int a[9];
int k = 42;
int i;
for (i = 0; i < 9; i++) {
for (int i = 0; i < 9; i++) {
clang_analyzer_numTimesReached(); // expected-warning {{4}}
a[i] = 42;
(void)&i;
@@ -98,6 +98,44 @@ int simple_no_unroll5() {
return 0;
}

int make_new_branches_loop_cached() {
for (int i = 0; i < 8; i++) {
clang_analyzer_numTimesReached(); // expected-warning {{4}}
if(getNum()){
(void) i; // Since this Stmt does not change the State the analyzer
// won't make a new execution path but reuse the earlier nodes.
}
}
clang_analyzer_warnIfReached(); // no-warning
return 0;
}

int make_new_branches_loop_uncached() {
int l = 2;
for (int i = 0; i < 8; i++) {
clang_analyzer_numTimesReached(); // expected-warning {{10}}
if(getNum()){
++l;
}
}
clang_analyzer_warnIfReached(); // no-warning
return 0;
}

int make_new_branches_loop_uncached2() {
int l = 2;
for (int i = 0; i < 8; i++) {
clang_analyzer_numTimesReached(); // expected-warning {{10}}
if(getNum()){
++l;
}
(void)&i; // This ensures that the loop won't be unrolled.
}
clang_analyzer_warnIfReached(); // no-warning
return 0;
}


int escape_before_loop_no_unroll1() {
int a[9];
int k = 42;
@@ -142,10 +180,11 @@ int nested_outer_unrolled() {
int k = 42;
int j = 0;
for (int i = 0; i < 9; i++) {
clang_analyzer_numTimesReached(); // expected-warning {{16}}
for (j = 0; j < getNum(); ++j) {
clang_analyzer_numTimesReached(); // expected-warning {{15}}
clang_analyzer_numTimesReached(); // expected-warning {{1}}
for (j = 0; j < 9; ++j) {
clang_analyzer_numTimesReached(); // expected-warning {{4}}
a[j] = 22;
(void) &j; // ensures that the inner loop won't be unrolled
}
a[i] = 42;
}
@@ -213,8 +252,8 @@ int nested_inlined_unroll1() {
int nested_inlined_no_unroll1() {
int k;
for (int i = 0; i < 9; i++) {
clang_analyzer_numTimesReached(); // expected-warning {{26}}
k = simple_unknown_bound_loop(); // reevaluation without inlining
clang_analyzer_numTimesReached(); // expected-warning {{15}}
k = simple_unknown_bound_loop(); // reevaluation without inlining, splits the state as well
}
int a = 22 / k; // no-warning
return 0;
@@ -224,10 +263,11 @@ int nested_inlined_no_unroll1() {
int recursion_unroll1(bool b) {
int k = 2;
for (int i = 0; i < 5; i++) {
clang_analyzer_numTimesReached(); // expected-warning {{14}}
if(i == 0 && b)
clang_analyzer_numTimesReached(); // expected-warning {{13}}
if(i == 0 && b) // Splits the state in the first iteration but the recursion
// call will be unrolled anyway since the condition is known there.
recursion_unroll1(false);
clang_analyzer_numTimesReached(); // expected-warning {{15}}
clang_analyzer_numTimesReached(); // expected-warning {{14}}
}
int a = 22 / k; // no-warning
return 0;
@@ -236,10 +276,10 @@ int recursion_unroll1(bool b) {
int recursion_unroll2(bool b) {
int k = 0;
for (int i = 0; i < 5; i++) {
clang_analyzer_numTimesReached(); // expected-warning {{10}}
clang_analyzer_numTimesReached(); // expected-warning {{9}}
if(i == 0 && b)
recursion_unroll2(false);
clang_analyzer_numTimesReached(); // expected-warning {{10}}
clang_analyzer_numTimesReached(); // expected-warning {{9}}
}
int a = 22 / k; // expected-warning {{Division by zero}}
return 0;
@@ -262,12 +302,12 @@ int recursion_unroll3(bool b) {
int recursion_unroll4(bool b) {
int k = 2;
for (int i = 0; i < 5; i++) {
clang_analyzer_numTimesReached(); // expected-warning {{14}}
clang_analyzer_numTimesReached(); // expected-warning {{13}}
if(i == 0 && b) {
recursion_unroll4(false);
continue;
}
clang_analyzer_numTimesReached(); // expected-warning {{14}}
clang_analyzer_numTimesReached(); // expected-warning {{13}}
}
int a = 22 / k;
return 0;
@@ -279,3 +319,4 @@ int loop_exit_while_empty_loop_stack() {
;
return 0;
}

0 comments on commit d0604ac

Please sign in to comment.