[StaticAnalyzer] LoopUnrolling: Exclude cases where the counter is escaped before the loop

[szepet]

Summary

Adding escape check for the counter variable of the loop.
It is achieved by jumping back on the ExplodedGraph to its declStmt.
When the analyzer encounters a Stmt which can result pointer escape then we not considering unrolling the given loop.

[NoQ]

Hmm, what prevents us from reusing existing matchers against S in isPossiblyEscaped()? Also i'd probably prefer to avoid recursion (we don't want stack traces of 225k frames).

Otherwise looks great, this should work!

[szepet]

Because I was not sure about the implementation detail of that. I dont want to write duplicated code so I tried to come up with a solution that the parameter of the matchers could be llvm::PointerUnion<const Decl *, const char *>. So I could define an equalsNode function which seems something like this: static internal::Matcher<Decl> equalsNode(llvm::PointerUnion<const Decl *, const char *> PU){..} and returns the suitable matcher and this could be used by the other matchers. However, PointerUnion does not let me to store char*. (This triggers the following assert in /home/Project/gsoc/llvm/include/llvm/ADT/PointerIntPair.h :
static_assert(IntBits <= PtrTraits::NumLowBitsAvailable, ,"PointerIntPair with integer size too large for pointer");)

I could use a simple union and an enum value as parameter but if you have better idea or know how to use PointerUnion correctly in this case please let me know!

[NoQ]

Maybe use decl matcher as the parameter, and pass either equalsNode(Foo) or equalsBoundNode("foo") as argument value?

[szepet]

Good idea, thanks!
Using matchers to identify possible escape stmts.
Test cases updated.

[NoQ]

Yay, looks cool.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

50 ↗

(On Diff #108443)

Maybe check here that the counter variable is local?

Or in isPossiblyEscaped(). Because globals are always escaped.

54 ↗

(On Diff #108443)

Can we use the same trick with decl matcher here and in hasSuspiciousStmt(), for consistency? I suspect it'd even be nicer.

68 ↗

(On Diff #108443)

Suggesting VarNodeMatcher as parameter name. EqualityCheck makes me imagine something that involves == or !=.

[szepet]

Requested changes made.
Description updated.

[NoQ]

Looks great now!

cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h

 //===--- LoopUnrolling.h - Unroll loops -------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// This header contains the declarations of functions which are used to decide
-/// which loops should be completely unrolled and mark their corresponding
-/// CFGBlocks.
+/// which loops should be completely unrolled and mark them.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_LOOPUNROLLING_H
 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_LOOPUNROLLING_H
 
 #include "clang/Analysis/CFG.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
 
 namespace clang {
 namespace ento {
 class AnalysisManager;
 
 ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State,
                                    const FunctionDecl *FD);
 bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Pred,
                          AnalysisManager &AMgr);
-bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx);
+bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
+                            ExplodedNode *Pred);
 
 } // end namespace ento
 } // end namespace clang
 
 #endif

cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp

void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
                                          NodeBuilderWithSinks &nodeBuilder,
                                          ExplodedNode *Pred) {
   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
   // If we reach a loop which has a known bound (and meets
   // other constraints) then consider completely unrolling it.
   if (AMgr.options.shouldUnrollLoops()) {
     const CFGBlock *ActualBlock = nodeBuilder.getContext().getBlock();
     const Stmt *Term = ActualBlock->getTerminator();
-    if (Term && shouldCompletelyUnroll(Term, AMgr.getASTContext())) {
+    if (Term && shouldCompletelyUnroll(Term, AMgr.getASTContext(), Pred)) {
       ProgramStateRef UnrolledState = markLoopAsUnrolled(
               Term, Pred->getState(),
               cast<FunctionDecl>(Pred->getStackFrame()->getDecl()));
       if (UnrolledState != Pred->getState())
         nodeBuilder.generateNode(UnrolledState, Pred);
       return;
     }
 

cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

 //===--- LoopUnrolling.cpp - Unroll loops -----------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// This file contains functions which are used to decide if a loop worth to be
-/// unrolled. Moreover contains function which mark the CFGBlocks which belongs
-/// to the unrolled loop and store them in ProgramState.
+/// unrolled. Moreover contains function which mark the loops which are unrolled
+/// and store them in ProgramState. During the analysis we check the analyzed
+/// blocks if they are part of an unrolled loop or reached from one.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "clang/Analysis/CFGStmtMap.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/AST/ParentMap.h"
 #include "clang/AST/StmtVisitor.h"
static internal::Matcher<Stmt> simpleCondition(StringRef BindName) {
   return binaryOperator(
       anyOf(hasOperatorName("<"), hasOperatorName(">"), hasOperatorName("<="),
             hasOperatorName(">="), hasOperatorName("!=")),
       hasEitherOperand(ignoringParenImpCasts(
           declRefExpr(to(varDecl(hasType(isInteger())).bind(BindName))))),
       hasEitherOperand(ignoringParenImpCasts(integerLiteral())));
 }
 
-static internal::Matcher<Stmt> changeIntBoundNode(StringRef NodeName) {
-  return anyOf(hasDescendant(unaryOperator(
-                   anyOf(hasOperatorName("--"), hasOperatorName("++")),
+static internal::Matcher<Stmt>
+changeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher) {
+  return anyOf(
+      unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")),
                     hasUnaryOperand(ignoringParenImpCasts(
-                       declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))))),
-               hasDescendant(binaryOperator(
-                   anyOf(hasOperatorName("="), hasOperatorName("+="),
+                        declRefExpr(to(varDecl(VarNodeMatcher)))))),
+      binaryOperator(anyOf(hasOperatorName("="), hasOperatorName("+="),
                            hasOperatorName("/="), hasOperatorName("*="),
                            hasOperatorName("-=")),
                      hasLHS(ignoringParenImpCasts(
-                       declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))))));
+                         declRefExpr(to(varDecl(VarNodeMatcher)))))));
 }
 
-static internal::Matcher<Stmt> callByRef(StringRef NodeName) {
-  return hasDescendant(callExpr(forEachArgumentWithParam(
-      declRefExpr(to(varDecl(equalsBoundNode(NodeName)))),
-      parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))));
+static internal::Matcher<Stmt>
+callByRef(internal::Matcher<Decl> VarNodeMatcher) {
+  return callExpr(forEachArgumentWithParam(
+      declRefExpr(to(varDecl(VarNodeMatcher))),
+      parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))));
 }
 
-static internal::Matcher<Stmt> assignedToRef(StringRef NodeName) {
-  return hasDescendant(varDecl(
+static internal::Matcher<Stmt>
+assignedToRef(internal::Matcher<Decl> VarNodeMatcher) {
+  return declStmt(hasDescendant(varDecl(
       allOf(hasType(referenceType()),
-            hasInitializer(
-                anyOf(initListExpr(has(
-                          declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))),
-                      declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))))));
+            hasInitializer(anyOf(
+                initListExpr(has(declRefExpr(to(varDecl(VarNodeMatcher))))),
+                declRefExpr(to(varDecl(VarNodeMatcher)))))))));
 }
 
-static internal::Matcher<Stmt> getAddrTo(StringRef NodeName) {
-  return hasDescendant(unaryOperator(
+static internal::Matcher<Stmt>
+getAddrTo(internal::Matcher<Decl> VarNodeMatcher) {
+  return unaryOperator(
       hasOperatorName("&"),
-      hasUnaryOperand(declRefExpr(hasDeclaration(equalsBoundNode(NodeName))))));
+      hasUnaryOperand(declRefExpr(hasDeclaration(VarNodeMatcher))));
 }
 
 static internal::Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) {
-  return anyOf(hasDescendant(gotoStmt()), hasDescendant(switchStmt()),
-               // Escaping and not known mutation of the loop counter is handled
-               // by exclusion of assigning and address-of operators and
-               // pass-by-ref function calls on the loop counter from the body.
-               changeIntBoundNode(NodeName), callByRef(NodeName),
-               getAddrTo(NodeName), assignedToRef(NodeName));
+  return hasDescendant(stmt(
+      anyOf(gotoStmt(), switchStmt(),
+            changeIntBoundNode(equalsBoundNode(NodeName)),
+            callByRef(equalsBoundNode(NodeName)),
+            getAddrTo(equalsBoundNode(NodeName)),
+            assignedToRef(equalsBoundNode(NodeName)))));
 }
 
 static internal::Matcher<Stmt> forLoopMatcher() {
   return forStmt(
              hasCondition(simpleCondition("initVarName")),
              // Initialization should match the form: 'int i = 6' or 'i = 42'.
              hasLoopInit(
                  anyOf(declStmt(hasSingleDecl(
                            varDecl(allOf(hasInitializer(integerLiteral()),
                                          equalsBoundNode("initVarName"))))),
                        binaryOperator(hasLHS(declRefExpr(to(varDecl(
                                           equalsBoundNode("initVarName"))))),
                                       hasRHS(integerLiteral())))),
              // Incrementation should be a simple increment or decrement
              // operator call.
              hasIncrement(unaryOperator(
                  anyOf(hasOperatorName("++"), hasOperatorName("--")),
                  hasUnaryOperand(declRefExpr(
                      to(varDecl(allOf(equalsBoundNode("initVarName"),
                                       hasType(isInteger())))))))),
              unless(hasBody(hasSuspiciousStmt("initVarName")))).bind("forLoop");
 }
 
-bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx) {
+static bool isPossiblyEscaped(const VarDecl *VD, ExplodedNode *N) {
+  // Global variables assumed as escaped variables.
+  if (VD->hasGlobalStorage())
+    return true;
+
+  while (!N->pred_empty()) {
+    const Stmt *S = PathDiagnosticLocation::getStmt(N);
+    if (!S) {
+      N = N->getFirstPred();
+      continue;
+    }
+
+    if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) {
+      for (const Decl *D : DS->decls()) {
+        // Once we reach the declaration of the VD we can return.
+        if (D->getCanonicalDecl() == VD)
+          return false;
+      }
+    }
+    // Check the usage of the pass-by-ref function calls and adress-of operator
+    // on VD and reference initialized by VD.
+    ASTContext &ASTCtx =
+        N->getLocationContext()->getAnalysisDeclContext()->getASTContext();
+    auto Match =
+        match(stmt(anyOf(callByRef(equalsNode(VD)), getAddrTo(equalsNode(VD)),
+                         assignedToRef(equalsNode(VD)))),
+              *S, ASTCtx);
+    if (!Match.empty())
+      return true;
+
+    N = N->getFirstPred();
+  }
+  llvm_unreachable("Reached root without finding the declaration of VD");
+}
+
+bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
+                            ExplodedNode *Pred) {
 
   if (!isLoopStmt(LoopStmt))
     return false;
 
   // TODO: Match the cases where the bound is not a concrete literal but an
   // integer with known value
-
   auto Matches = match(forLoopMatcher(), *LoopStmt, ASTCtx);
-  return !Matches.empty();
+  if (Matches.empty())
+    return false;
+
+  auto CounterVar = Matches[0].getNodeAs<VarDecl>("initVarName");
+
+  // Check if the counter of the loop is not escaped before.
+  return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred);
 }
 
 namespace {
 class LoopBlockVisitor : public ConstStmtVisitor<LoopBlockVisitor> {
 public:
   LoopBlockVisitor(llvm::SmallPtrSet<const CFGBlock *, 8> &BS) : BlockSet(BS) {}
 
   void VisitChildren(const Stmt *S) {
for (auto &E : State->get<UnrolledLoops>()) {
     const StackFrameContext *StackFrame = Pred->getStackFrame();
     ParentMap PM(E.second->getBody());
     CFGStmtMap *M = CFGStmtMap::Build(AMgr.getCFG(E.second), &PM);
     LBV.setBlocksOfLoop(E.first, M);
     // In case of an inlined function call check if any of its callSiteBlock is
     // marked.
     while (BlockSet.find(SearchedBlock) == BlockSet.end() && StackFrame) {
       SearchedBlock = StackFrame->getCallSiteBlock();
-      if(!SearchedBlock || StackFrame->inTopFrame())
+      if (!SearchedBlock || StackFrame->inTopFrame())
         break;
       StackFrame = StackFrame->getParent()->getCurrentStackFrame();
     }
     delete M;
     if (SearchedBlock)
       return true;
   }
   return false;

cfe/trunk/test/Analysis/loop-unrolling.cpp

-// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true -analyzer-stats -verify -std=c++11 %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-max-loop 4 -analyzer-config unroll-loops=true -verify -std=c++11 %s
 
 void clang_analyzer_numTimesReached();
 
 int getNum();
 void foo(int &);
 // Testing for loops.
 int simple_unroll1() {
   int a[9];

 int simple_unroll2() {
   int a[9];
   int k = 42;
   int i;
   for (i = 0; i < 9; i++) {
     clang_analyzer_numTimesReached(); // expected-warning {{9}}
     a[i] = 42;
   }
+
+  for (int j = 0; j <= 9; ++j) {
+    clang_analyzer_numTimesReached(); // expected-warning {{10}}
+    a[j] = 42;
+  }
+
   int b = 22 / (k - 42); // expected-warning {{Division by zero}}
   return 0;
 }
 
 int simple_no_unroll1() {
   int a[9];
   int k = 42;
   for (int i = 0; i < 9; i++) {
for (i = 0; i < 9; i++) {
     clang_analyzer_numTimesReached(); // expected-warning {{4}}
     a[i] = 42;
     int &j{i};
   }
   int b = 22 / (k - 42); // no-warning
   return 0;
 }
 
+int escape_before_loop_no_unroll1() {
+  int a[9];
+  int k = 42;
+  int i;
+  int &j = i;
+  for (i = 0; i < 9; i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{4}}
+    a[i] = 42;
+  }
+  int b = 22 / (k - 42); // no-warning
+  return 0;
+}
+
+int escape_before_loop_no_unroll2() {
+  int a[9];
+  int k = 42;
+  int i;
+  int *p = &i;
+  for (i = 0; i < 9; i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{4}}
+    a[i] = 42;
+  }
+  int b = 22 / (k - 42); // no-warning
+  return 0;
+}
+
+int escape_before_loop_no_unroll3() {
+  int a[9];
+  int k = 42;
+  int i;
+  foo(i);
+  for (i = 0; i < 9; i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{4}}
+    a[i] = 42;
+  }
+  int b = 22 / (k - 42); // no-warning
+  return 0;
+}
+
 int nested_outer_unrolled() {
   int a[9];
   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}}