[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

Maybe check here that the counter variable is local?

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

54

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

68

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

[szepet]

Requested changes made.
Description updated.

[NoQ]

Looks great now!

include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.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

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;
     }
 

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

static bool isLoopStmt(const Stmt *S) {
   return S && (isa<ForStmt>(S) || isa<WhileStmt>(S) || isa<DoStmt>(S));
 }
 
 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("++")),
                    hasUnaryOperand(ignoringParenImpCasts(
                        declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))))),
                hasDescendant(binaryOperator(
                    anyOf(hasOperatorName("="), hasOperatorName("+="),
                          hasOperatorName("/="), hasOperatorName("*="),
                          hasOperatorName("-=")),
                    hasLHS(ignoringParenImpCasts(
                        declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))))));
 }
 
-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> EqualityCheck) {
+  return callExpr(forEachArgumentWithParam(
+      declRefExpr(to(varDecl(EqualityCheck))),
+      parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))));
 }
 
-static internal::Matcher<Stmt> assignedToRef(StringRef NodeName) {
-  return hasDescendant(varDecl(
+static internal::Matcher<Stmt>
+assignedToRef(internal::Matcher<Decl> EqualityCheck) {
+  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(EqualityCheck))))),
+                declRefExpr(to(varDecl(EqualityCheck)))))))));
 }
 
-static internal::Matcher<Stmt> getAddrTo(StringRef NodeName) {
-  return hasDescendant(unaryOperator(
+static internal::Matcher<Stmt>
+getAddrTo(internal::Matcher<Decl> EqualityCheck) {
+  return unaryOperator(
       hasOperatorName("&"),
-      hasUnaryOperand(declRefExpr(hasDeclaration(equalsBoundNode(NodeName))))));
+      hasUnaryOperand(declRefExpr(hasDeclaration(EqualityCheck))));
 }
 
 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));
+               changeIntBoundNode(NodeName),
+               hasDescendant(callByRef(equalsBoundNode(NodeName))),
+               hasDescendant(getAddrTo(equalsBoundNode(NodeName))),
+               hasDescendant(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) {
+  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;

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}}