[analyzer] LoopUnrolling: fix crash when a loop counter is captured in a lambda by reference

[steakhal]

I'm gonna have a look at this tomorrow.

[vsavchenko]

Great job on the patch! Thanks!

clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

166–199

One thought here.
I think it's better to not have implicit connections between parameters that are not obvious to the user of the function (or to the person who is going to modify this function in the future). Here we always have VD = DR->getDecl()->getCanonicalDecl(). So, IMO, the interface of this function will be much cleaner if we accept only a DeclRefExpr.

185–186

But actually, it's a bit different with this one. I don't know exact details and rules how clang sema fills in the class for lambda.
According to cppreference:

For the entities that are captured by reference (with the default capture [&] or when using the character &, e.g. [&a, &b, &c]), it is unspecified if additional data members are declared in the closure type

It can be pretty much specified in clang, that's true, but it looks like in DeadStoreChecker we have a very similar situation and we do not assume that captured variable always have a corresponding field.

188–191

There is a general rule in LLVM's style guide of trying to minimize nestedness of if's, forms and so on.
In this particular situation this assertion can be more local: assert(MD && MD->getParent()->isLambda() & ...);.
This way it is more obvious what it checks and we avoid confusion while reading this function because if (condition) automatically means that !condition is something that might happen.
The same applies to another assertion here.

202–203

I think that this comment has to be updated now.

202–203

I think this whole section is less obvious now and requires one good solid comment explaining what are the different situations here, what is "entry" and so on.

[steakhal]

By checking the line coverage of the LoopUnrolling.cpp test file, looks like all lines are covered you touched.

There are only two return statements uncovered though: L200, L251.
We should consider extending this test file to cover them as well in a follow-up patch.

[AbbasSabra]

Updating D102273: [analyzer] Apply code review

[AbbasSabra]

clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

185–186

Yes, I based this on the fact that DeadStoreChecker considers it possible, but I have never faced a case where it does not have a corresponding field.

[vsavchenko]

Thanks for addressing my comments! I still have some left though

clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

171

dyn_cast_or_null also tells the reader that D can be null and can be not CXXMethodDecl. So it's better to use cast here if you are sure about D and have assertions about it.

175–178

Body of this function seems to be too dense. It is usually hard to read something that doesn't have rest places for eyes. You can think of it as paragraphs in the written text.
In this particular situation, you can split all these statements and declarations in groups of 3-4. It would be perfect if they are grouped semantically (like good paragraphs).

179

We can just do cast here

185–186

I still think that we should do something about this else

192–193

I think it's a great idea to list all the cases. I think we can go even further: enumerate them and actually pinpoint in the implementation where we cover which case. With numbers it can be much easier.

194

Can we not introduce new terms and simply call it a reference?

197

This should be also modified then

[vsavchenko]

clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

185–186

It still would be good to have some proof that it is indeed like this or simply fallback into returning true (which you already do when in doubt).

[AbbasSabra]

Updating D102273: [analyzer] Apply code review part 2

[AbbasSabra]

clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

185–186

As I said, I believe it cannot happen but I assumed based on the other checker that there is something I don't know.
I think based on getCaptureFields the implementation we are iterating over all captures. For that algorithm to work number of captures should be equal to number of fields

void CXXRecordDecl::getCaptureFields(
       llvm::DenseMap<const VarDecl *, FieldDecl *> &Captures,
       FieldDecl *&ThisCapture) const {
  Captures.clear();
  ThisCapture = nullptr;

  LambdaDefinitionData &Lambda = getLambdaData();
  RecordDecl::field_iterator Field = field_begin();
  for (const LambdaCapture *C = Lambda.Captures, *CEnd = C + Lambda.NumCaptures;
       C != CEnd; ++C, ++Field) {
    if (C->capturesThis())
      ThisCapture = *Field;
    else if (C->capturesVariable())
      Captures[C->getCapturedVar()] = *Field;
  }
  assert(Field == field_end());
}

I dropped the defensive code

[AbbasSabra]

Updating D102273: [analyzer] Update comments + fix typos

[NoQ]

I've just been patching up clang-tidy's infinite loop checker and the problem sounds soooo similar. Maybe we should move clang-tidy's alias analysis into libAnalysis and re-use it?

[AbbasSabra]

In D102273#2766531, @NoQ wrote:

I've just been patching up clang-tidy's infinite loop checker and the problem sounds soooo similar. Maybe we should move clang-tidy's alias analysis into libAnalysis and re-use it?

I'm not familiar with clang-tidy's alias analysis. Do you think it should be part of this patch? or a follow-up one?

[AbbasSabra]

Note: I don't have the right to re-run the failed build/test. I assume that it is not related to my change since the test compile and runs omp code(Static analyzer doesn't run on that test)

[AbbasSabra]

ping

[AbbasSabra]

ping

[AbbasSabra]

@vsavchenko any update on this?

[vsavchenko]

Great! Thanks for addressing all of the comments!

clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

185–186

OK, sounds reasonable!

[AbbasSabra]

In D102273#2866532, @vsavchenko wrote:

Great! Thanks for addressing all of the comments!

Thank you for the review! Can you take care of merging it? I don't have the required permission.

clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

 
 ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) {
   auto LS = State->get<LoopStack>();
   if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt)
     State = State->set<LoopStack>(LS.getTail());
   return State;
 }
 
-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().bind("boundNum"))))
+static internal::Matcher<Stmt> simpleCondition(StringRef BindName,
+                                               StringRef RefName) {
+  return binaryOperator(
+             anyOf(hasOperatorName("<"), hasOperatorName(">"),
+                 declRefExpr(to(varDecl(hasType(isInteger())).bind(BindName)))
+                     .bind(RefName))),
+             hasEitherOperand(
+                 ignoringParenImpCasts(integerLiteral().bind("boundNum"))))
       .bind("conditionOperator");
 }
 
 static internal::Matcher<Stmt>
 changeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher) {
   return anyOf(
       unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")),
                     hasUnaryOperand(ignoringParenImpCasts(
return hasDescendant(stmt(
             changeIntBoundNode(equalsBoundNode(std::string(NodeName))),
             callByRef(equalsBoundNode(std::string(NodeName))),
             getAddrTo(equalsBoundNode(std::string(NodeName))),
             assignedToRef(equalsBoundNode(std::string(NodeName))))));
 }
 
 static internal::Matcher<Stmt> forLoopMatcher() {
   return forStmt(
-             hasCondition(simpleCondition("initVarName")),
+             hasCondition(simpleCondition("initVarName", "initVarRef")),
              // Initialization should match the form: 'int i = 6' or 'i = 42'.
              hasLoopInit(
                  anyOf(declStmt(hasSingleDecl(
                            varDecl(allOf(hasInitializer(ignoringParenImpCasts(
                                              integerLiteral().bind("initNum"))),
                                          equalsBoundNode("initVarName"))))),
                        binaryOperator(hasLHS(declRefExpr(to(varDecl(
                                           equalsBoundNode("initVarName"))))),
                                       hasRHS(ignoringParenImpCasts(
                                           integerLiteral().bind("initNum")))))),
              // 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");
+             unless(hasBody(hasSuspiciousStmt("initVarName"))))
+      .bind("forLoop");
 }
 
-static bool isPossiblyEscaped(const VarDecl *VD, ExplodedNode *N) {
+static bool isCapturedByReference(ExplodedNode *N, const DeclRefExpr *DR) {
+  assert(DR->refersToEnclosingVariableOrCapture());
+
+  const LocationContext *LocCtxt = N->getLocationContext();
+  const Decl *D = LocCtxt->getDecl();
+  const auto *MD = dyn_cast_or_null<CXXMethodDecl>(D);
+  assert(MD && MD->getParent()->isLambda() &&
+         "Captured variable should only be seen while evaluating a lambda");
+  // Lookup the field of the lambda.
+  const CXXRecordDecl *CXXRec = MD->getParent();
+  llvm::DenseMap<const VarDecl *, FieldDecl *> LambdaCaptureFields;
+  FieldDecl *LambdaThisCaptureField;
+  CXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField);
+  const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()->getCanonicalDecl());
+  assert(VD);
+  // Sema follows a sequence of complex rules to determine whether the
+  // variable should be captured.
+  if (const FieldDecl *FD = LambdaCaptureFields[VD]) {
+    return FD->getType()->isReferenceType();
+  } else {
+    assert(false && "Unknown captured variable");
+  }
+  return true; // When in doubt, assume the most conservative answer, which will
+               // disable loop unrolling
+}
+
+// A loop counter is considered escaped if:
+// - It is a global variable.
+// - It is an entry value: a reference parameter or a reference capture.
+// - It is assigned to a non-const reference variable or parameter.
+// - Has its address taken.
+static bool isPossiblyEscaped(const VarDecl *VD, ExplodedNode *N,
+                              const DeclRefExpr *DR) {
   // Global variables assumed as escaped variables.
   if (VD->hasGlobalStorage())
     return true;
 
-  const bool isParm = isa<ParmVarDecl>(VD);
-  // Reference parameters are assumed as escaped variables.
-  if (isParm && VD->getType()->isReferenceType())
+  const bool IsEntryValue =
+      isa<ParmVarDecl>(VD) || DR->refersToEnclosingVariableOrCapture();
+  // Entry values are assumed as escaped variables.
+  if ((DR->refersToEnclosingVariableOrCapture() &&
+       isCapturedByReference(N, DR)) ||
+      (IsEntryValue && VD->getType()->isReferenceType()))
     return true;
 
   while (!N->pred_empty()) {
     // FIXME: getStmtForDiagnostics() does nasty things in order to provide
     // a valid statement for body farms, do we need this behavior here?
     const Stmt *S = N->getStmtForDiagnostics();
     if (!S) {
       N = N->getFirstPred();
auto Match =
                          assignedToRef(equalsNode(VD)))),
               *S, ASTCtx);
     if (!Match.empty())
       return true;
 
     N = N->getFirstPred();
   }
 
-  // Parameter declaration will not be found.
-  if (isParm)
+  // Entry values will not be found.
+  if (IsEntryValue)
     return false;
 
   llvm_unreachable("Reached root without finding the declaration of VD");
 }
 
 bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
                             ExplodedNode *Pred, unsigned &maxStep) {
 
   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);
   if (Matches.empty())
     return false;
 
   auto CounterVar = Matches[0].getNodeAs<VarDecl>("initVarName");
+  const auto *CounterVarRef = Matches[0].getNodeAs<DeclRefExpr>("initVarRef");
   llvm::APInt BoundNum =
       Matches[0].getNodeAs<IntegerLiteral>("boundNum")->getValue();
   llvm::APInt InitNum =
       Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue();
   auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator");
   if (InitNum.getBitWidth() != BoundNum.getBitWidth()) {
     InitNum = InitNum.zextOrSelf(BoundNum.getBitWidth());
     BoundNum = BoundNum.zextOrSelf(InitNum.getBitWidth());
   }
 
   if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE)
     maxStep = (BoundNum - InitNum + 1).abs().getZExtValue();
   else
     maxStep = (BoundNum - InitNum).abs().getZExtValue();
 
   // Check if the counter of the loop is not escaped before.
-  return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred);
+  return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred,
+                            CounterVarRef);
 }
 
 bool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt) {
   const Stmt *S = nullptr;
   while (!N->pred_empty()) {
     if (N->succ_size() > 1)
       return true;
 

clang/test/Analysis/loop-unrolling.cpp

-// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true -verify -std=c++11 -analyzer-config exploration_strategy=unexplored_first_queue %s
-// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true,exploration_strategy=dfs -verify -std=c++11 -DDFS=1 %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true -verify -std=c++14 -analyzer-config exploration_strategy=unexplored_first_queue %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true,exploration_strategy=dfs -verify -std=c++14 -DDFS=1 %s
 
 void clang_analyzer_numTimesReached();
 void clang_analyzer_warnIfReached();
 
 int getNum();
 void foo(int &);
 
 int simple_unroll1() {
void parm_by_value_as_loop_counter(int i) {
   }
 }
 
 void parm_by_ref_as_loop_counter(int &i) {
   for (i = 0; i < 10; ++i) {
     clang_analyzer_numTimesReached(); // expected-warning {{4}}
   }
 }
+
+void capture_by_value_as_loop_counter() {
+  int out = 0;
+  auto l = [i = out]() mutable {
+    for (i = 0; i < 10; ++i) {
+      clang_analyzer_numTimesReached(); // expected-warning {{10}}
+    }
+  };
+}
+
+void capture_by_ref_as_loop_counter() {
+  int out = 0;
+  auto l = [&i = out]() {
+    for (i = 0; i < 10; ++i) {
+      clang_analyzer_numTimesReached(); // expected-warning {{4}}
+    }
+  };
+}
+
+void capture_implicitly_by_value_as_loop_counter() {
+  int i = 0;
+  auto l = [=]() mutable {
+    for (i = 0; i < 10; ++i) {
+      clang_analyzer_numTimesReached(); // expected-warning {{10}}
+    }
+  };
+}
+
+void capture_implicitly_by_ref_as_loop_counter() {
+  int i = 0;
+  auto l = [&]() mutable {
+    for (i = 0; i < 10; ++i) {
+      clang_analyzer_numTimesReached(); // expected-warning {{4}}
+    }
+  };
+}