[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

49

Maybe check here that the counter variable is local?

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

53

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

70

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

 #include "clang/Analysis/CFG.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
 
 namespace clang {
 namespace ento {
 ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State,
                                    CFGStmtMap *StmtToBlockMap);
-bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Prev);
-bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx);
+bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Pred);
+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(),
                                  Pred->getLocationContext()
                                          ->getAnalysisDeclContext()
                                          ->getCFGStmtMap());
       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(const Decl *D) {
+  return callExpr(forEachArgumentWithParam(
+      declRefExpr(to(varDecl(equalsNode(D)))),
+      parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))));
+}
+
 static internal::Matcher<Stmt> assignedToRef(StringRef NodeName) {
   return hasDescendant(varDecl(
       allOf(hasType(referenceType()),
-            hasInitializer(anyOf(
-                initListExpr(has(
+            hasInitializer(
+                anyOf(initListExpr(has(
                           declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))),
                       declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))))));
 }
 
 static internal::Matcher<Stmt> getAddrTo(StringRef NodeName) {
   return hasDescendant(unaryOperator(
       hasOperatorName("&"),
       hasUnaryOperand(declRefExpr(hasDeclaration(equalsBoundNode(NodeName))))));
 }
 
return forStmt(
              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) {
+  if (N->pred_empty())
+    assert("Reached root without finding the declaration of VD");
+  const Stmt *S = PathDiagnosticLocation::getStmt(N);
+  if (!S)
+    return isPossiblyEscaped(VD, N->getFirstPred());
+
+  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 if a reference is initialized by the variable.
+      if (auto V = dyn_cast<VarDecl>(D)) {
+        if (!V->getInit())
+          continue;
+        auto DRE = dyn_cast<DeclRefExpr>(V->getInit()->IgnoreParenImpCasts());
+        if (DRE && isa<ReferenceType>(V->getType()) &&
+            DRE->getDecl()->getCanonicalDecl() == VD)
+          return true;
+      }
+    }
+  }
+  // Check the usage of the adress-of operator on VD.
+  do {
+    auto UO = dyn_cast<UnaryOperator>(S);
+    if (!UO || UO->getOpcode() != UO_AddrOf)
+      break;
+    auto DRE = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParenImpCasts());
+    if (DRE && DRE->getDecl()->getCanonicalDecl() == VD)
+      return true;
+  } while (false);
 
+  // Check for pass-by-ref function calls.
+  auto Match =
+      match(callByRef(VD), *S,
+            N->getLocationContext()->getAnalysisDeclContext()->getASTContext());
+  if (!Match.empty())
+    return true;
+
+  return isPossiblyEscaped(VD, N->getFirstPred());
+}
+
+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) {
public:
   }
 
 private:
   llvm::SmallPtrSet<const CFGBlock *, 8> &BlockSet;
   const CFGStmtMap *StmtToBlockMap;
   const Stmt *LoopStmt;
 };
 }
-// TODO: refactor this function using ScopeContext - once we have the
-// information when the simulation reaches the end of the loop we can cleanup
-// the state
-bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Prev) {
+
+bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Pred) {
   const Stmt *Term = Block->getTerminator();
-  auto State = Prev->getState();
+  auto State = Pred->getState();
   // In case of nested loops in an inlined function should not be unrolled only
   // if the inner loop is marked.
   if (Term && isLoopStmt(Term) && !State->contains<UnrolledLoops>(Term))
     return false;
 
   const CFGBlock *SearchedBlock;
   llvm::SmallPtrSet<const CFGBlock *, 8> BlockSet;
   LoopBlockVisitor LBV(BlockSet);
   // Check the CFGBlocks of every marked loop.
   for (auto &E : State->get<UnrolledLoops>()) {
     SearchedBlock = Block;
-    const StackFrameContext *StackFrame = Prev->getStackFrame();
+    const StackFrameContext *StackFrame = Pred->getStackFrame();
     LBV.setBlocksOfLoop(E.first, E.second);
     // In case of an inlined function call check if any of its callSiteBlock is
     // marked.
     while (SearchedBlock && BlockSet.find(SearchedBlock) == BlockSet.end()) {
       SearchedBlock = StackFrame->getCallSiteBlock();
       StackFrame = StackFrame->getParent()->getCurrentStackFrame();
     }
 

test/Analysis/loop-unrolling.cpp

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}}
int simple_unknown_bound_loop() {
   }
   return 0;
 }
 
 int nested_inlined_unroll1() {
   int k;
   for (int i = 0; i < 9; i++) {
     clang_analyzer_numTimesReached(); // expected-warning {{9}}
-    k = simple_known_bound_loop(); // no reevaluation without inlining
+    k = simple_known_bound_loop();    // no reevaluation without inlining
   }
   int a = 22 / k; // expected-warning {{Division by zero}}
   return 0;
 }
 
 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
+    k = simple_unknown_bound_loop();  // reevaluation without inlining
   }
   int a = 22 / k; // no-warning
   return 0;
 }
 
 // CHECK: ... Statistics Collected ...
 // CHECK: 5 ExprEngine       - The # of times we re-evaluated a call without inlining
 // CHECK: 9 LoopUnrolling    - The # of times a loop has got completely unrolled