[StaticAnalyzer] LoopWidening: Invalidate only the possibly changed regions

[szepet]

Summary

The current widening option in the Clang Static Analyzer invalidates (almost) all of the MemRegions when a loop reach its last visit (see: maxBlockVisitOnPath config) and then continue the analysis.

My aim is to create a solution where widening only invalidates the MemRegions which is possibly to affected by the loop. So in case of pointers it requires more effort to track the possible values which can be changed. In this initial patch only specific loops will be invalidated which does not contains (complex, therefore) unhandled statements. (e.g. pointer operations).

In the invalidation process we check the possibly changed variables via ASTMatchers.

In general case the difference between the two approach is:

widen-loops-old	Invalidate everything
widen-loops-new	Only invalidate modified variables

But there is another difference when there are pointers (more precisely if it encounters a statement which can result a modified variable but it is not handled yet):

widen-loops-old	Invalidate everything
widen-loops-new	Invalidate nothing (don't widen)

[NoQ]

Yay!

Do i understand correctly that your code does widening for simple loops but leaves complex loops intact, unless the old widening is also turned on?

Hmm, i guess some tests got lost on their way here.

Can matchers from LoopUnrolling.cpp be re-used anyhow?

include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

582

Not sure, but i suspect that your approach is actually less conservative than the old one(?) Like, it drops less information.

I think we should try to express more here - these approaches are very different.

lib/StaticAnalyzer/Core/LoopWidening.cpp

45–46

Do we actually put statements that aren't loops into this function?

[szepet]

include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

582

Yepp, I meant to say its more conservative from the aspect that it only widen specific loops. I will update it more clearly but if you have any suggestion on the name of the flag don't hesitate to say! :)

lib/StaticAnalyzer/Core/LoopWidening.cpp

45–46

Not really, just wanted to be consistent with the getLoopCondition function above. (I accidently marked it as Done and cant undo it. Would you like to remove this case?)

[szepet]

Test cases added.

[seaneveson]

Nice! Thanks again for working on this.

Personally I would prefer modifying or replacing widen-loops, so we don't end up with two different approaches (and options) at the same time. Certainly that should be the end goal, but I think it might be worth doing now.

At a glance I would say that the behavior difference when there are no pointers is:

widen-loops	Invalidate everything
widen-loops-conservative	Only invalidate modified variables

And when there are pointers the difference is:

widen-loops	Invalidate everything
widen-loops-conservative	Invalidate nothing

As far as I can tell widen-loops-conservative is better (in every sense) in the no pointer case. If we can agree on what to do when there are pointers (Invalidate everything or nothing), then we would only need one option. I would guess we want to invalidate nothing, which will probably give less false positives, rather than everything which probably gives more coverage.

lib/StaticAnalyzer/Core/LoopWidening.cpp

90

There are some more compound assignment operators:

a %= b
a &= b
a |= b
a ^= b
a <<= b
a >>= b

105

I think you could ignore const pointers/arrays here without too much effort, or would checking for casts make that a pain (and thus work for a future patch)?

111

Style nit, you could return Matches.empty();.

[szepet]

In D36690#841033, @seaneveson wrote:

Nice! Thanks again for working on this.

Personally I would prefer modifying or replacing widen-loops, so we don't end up with two different approaches (and options) at the same time. Certainly that should be the end goal, but I think it might be worth doing now.

Thanks for the comments and the summary of the differences! If you don't mind I've added it to the description. I believe its not the best to replace it since (as you pointed out) it behaves differently enough in cases which is not handled in the 'conservative' solution. So I am not sure about the users of the current widening option but it could result a drawback on its performance (eg.: on the coverage %).
But when further measurements are done (yepp, its on me) and you and the community in general is still OK with that change, then it will happen.

[szepet]

Added a more general approach for collecting changed variables.

The main problem could be nested loops where the coverage is suboptimal. We do not invalidate the outer loop information so (in case of known bound) the execution path will be aborted because of the maxBlockVisitOnPath check. It results in not analyzing the code after the outer loop.

[szepet]

Format test file.

[seaneveson]

I would still personally rather replace widen-loops, but if its just me I'm happy for it to be a separate option for now.

Otherwise I just have a few minor comments.

lib/StaticAnalyzer/Core/ExprEngine.cpp

1556–1560

The behavior when giving giving both flags is not obvious to the user. You might want to add something to the help or disallow doing both at the same time.

lib/StaticAnalyzer/Core/LoopWidening.cpp

63

Naming the function something like changedByIncrementOrDecrement or changedByUnaryOperator would make it clearer that this checks for ++ AND --.

test/Analysis/loop-widening-conservative.cpp

270

You should also test for modifications of the value being pointed at e.g. *p = 1; *p++ etc.

[szepet]

Addressed comments.

[szepet]

Update patch to not add a new flag but change the functionality of the old one. (If Sean still agrees.)

[seaneveson]

LGTM, Thanks :)

[szepet]

ping

[szepet]

ping~2

[seaneveson]

I didn't mark this as accepted in case anyone else wanted/needed to review this before you put it in, but I'm happy with it.

[zaks.anna]

Hi Peter,

The loop widening is a fundamental change to the analyzer and we'd like to discuss the overall design for this feature before committing patches. Can we start with design discussions on the list?

If I recall correctly, Devin thought that we need to build widening on top of better loop modeling in the CFG, which has not happened yet.

In your design, please include the details on how nested loops will be handled. Another particular issue that we anticipate is that the loop guard statement's location is arbitrary with respect to the place where the block count gets incremented. (These are some of the issues that would be addressed if this work was based on the proper loop modeling in the CFG.)

include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

private:
   Optional<unsigned> MaxNodesPerTopLevelFunction;
 
   /// \sa shouldInlineLambdas
   Optional<bool> InlineLambdas;
 
   /// \sa shouldWidenLoops
   Optional<bool> WidenLoops;
 
+  /// \sa shouldWidenLoops
+  Optional<bool> ConservativelyWidenLoops;
+
   /// \sa shouldUnrollLoops
   Optional<bool> UnrollLoops;
 
   /// \sa shouldDisplayNotesAsEvents
   Optional<bool> DisplayNotesAsEvents;
 
   /// A helper function that retrieves option for a given full-qualified
   /// checker name.
public:
   /// Returns true if lambdas should be inlined. Otherwise a sink node will be
   /// generated each time a LambdaExpr is visited.
   bool shouldInlineLambdas();
 
   /// Returns true if the analysis should try to widen loops.
   /// This is controlled by the 'widen-loops' config option.
   bool shouldWidenLoops();
 
+  /// Returns true if the analysis should try to widen loops in a conservative
+  /// manner (only widen loops which meets specific requirements).
+  /// This is controlled by the 'widen-loops-conservative' config option.
+  bool shouldConservativelyWidenLoops();
+
     /// Returns true if the analysis should try to unroll loops with known bounds.
   /// This is controlled by the 'unroll-loops' config option.
   bool shouldUnrollLoops();
 
   /// Returns true if the bug reporter should transparently treat extra note
   /// diagnostic pieces as event diagnostic pieces. Useful when the diagnostic
   /// consumer doesn't support the extra note pieces.
   ///
   /// This is controlled by the 'extra-notes-as-events' option, which defaults

include/clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h

 /// \brief Get the states that result from widening the loop.
 ///
 /// Widen the loop by invalidating anything that might be modified
 /// by the loop body in any iteration.
 ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState,
                                     const LocationContext *LCtx,
                                     unsigned BlockCount, const Stmt *LoopStmt);
 
+ProgramStateRef getConservativelyWidenedLoopState(ProgramStateRef State,
+                                                  ASTContext &ASTCtx,
+                                                  const LocationContext *LCtx,
+                                                  unsigned BlockCount,
+                                                  const Stmt *LoopStmt);
+
 } // end namespace ento
 } // end namespace clang
 
 #endif

lib/StaticAnalyzer/Core/AnalyzerOptions.cpp

 }
 
 bool AnalyzerOptions::shouldWidenLoops() {
   if (!WidenLoops.hasValue())
     WidenLoops = getBooleanOption("widen-loops", /*Default=*/false);
   return WidenLoops.getValue();
 }
 
+bool AnalyzerOptions::shouldConservativelyWidenLoops() {
+  if (!ConservativelyWidenLoops.hasValue())
+    ConservativelyWidenLoops = getBooleanOption("widen-loops-conservative", false);
+  return ConservativelyWidenLoops.getValue();
+}
+
 bool AnalyzerOptions::shouldUnrollLoops() {
   if (!UnrollLoops.hasValue())
     UnrollLoops = getBooleanOption("unroll-loops", /*Default=*/false);
   return UnrollLoops.getValue();
 }
 
 bool AnalyzerOptions::shouldDisplayNotesAsEvents() {
   if (!DisplayNotesAsEvents.hasValue())
     DisplayNotesAsEvents =
         getBooleanOption("notes-as-events", /*Default=*/false);
   return DisplayNotesAsEvents.getValue();
 }

lib/StaticAnalyzer/Core/ExprEngine.cpp

if(AMgr.options.shouldUnrollLoops()) {
     if(isUnrolledState(Pred->getState()))
       return;
   }
 
   // If this block is terminated by a loop and it has already been visited the
   // maximum number of times, widen the loop.
   unsigned int BlockCount = nodeBuilder.getContext().blockCount();
   if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 &&
-      AMgr.options.shouldWidenLoops()) {
+      (AMgr.options.shouldWidenLoops() ||
+       AMgr.options.shouldConservativelyWidenLoops())) {
     const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator();
     if (!(Term &&
           (isa<ForStmt>(Term) || isa<WhileStmt>(Term) || isa<DoStmt>(Term))))
       return;
     // Widen.
     const LocationContext *LCtx = Pred->getLocationContext();
     ProgramStateRef WidenedState =
-        getWidenedLoopState(Pred->getState(), LCtx, BlockCount, Term);
+            AMgr.options.shouldConservativelyWidenLoops()
+            ? getConservativelyWidenedLoopState(Pred->getState(),
+                                                AMgr.getASTContext(), LCtx,
+                                                BlockCount, Term)
+            : getWidenedLoopState(Pred->getState(), LCtx, BlockCount, Term);
     nodeBuilder.generateNode(WidenedState, Pred);
     return;
   }
 
   // FIXME: Refactor this into a checker.
   if (BlockCount >= AMgr.options.maxBlockVisitOnPath) {
     static SimpleProgramPointTag tag(TagProviderName, "Block count exceeded");
     const ExplodedNode *Sink =

lib/StaticAnalyzer/Core/LoopWidening.cpp

 /// This file contains functions which are used to widen loops. A loop may be
 /// widened to approximate the exit state(s), without analyzing every
 /// iteration. The widening is done by invalidating anything which might be
 /// modified by the body of the loop.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
+#include "clang/AST/AST.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
+#include "llvm/ADT/SmallSet.h"
 
 using namespace clang;
 using namespace ento;
+using namespace clang::ast_matchers;
 
 /// Return the loops condition Stmt or NULL if LoopStmt is not a loop
 static const Expr *getLoopCondition(const Stmt *LoopStmt) {
   switch (LoopStmt->getStmtClass()) {
   default:
     return nullptr;
   case Stmt::ForStmtClass:
     return cast<ForStmt>(LoopStmt)->getCond();
   case Stmt::WhileStmtClass:
     return cast<WhileStmt>(LoopStmt)->getCond();
   case Stmt::DoStmtClass:
     return cast<DoStmt>(LoopStmt)->getCond();
   }
 }
 
+static internal::Matcher<Stmt> callByRef(StringRef NodeName) {
+  return callExpr(forEachArgumentWithParam(
+      expr().bind(NodeName),
+      parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))));
+}
+
+static internal::Matcher<Stmt> cxxNonConstCall(StringRef NodeName) {
+  return anyOf(cxxMemberCallExpr(on(expr().bind("changedExpr")),
+                                 unless(callee(cxxMethodDecl(isConst())))),
+               cxxOperatorCallExpr(
+                   hasArgument(0, ignoringImpCasts(expr().bind(NodeName))),
+                   unless(callee(cxxMethodDecl(isConst())))));
+}
+static internal::Matcher<Stmt> changedByAssignement(StringRef NodeName) {
+  return binaryOperator(
+      anyOf(hasOperatorName("="), hasOperatorName("+="), hasOperatorName("/="),
+            hasOperatorName("*="), hasOperatorName("-="), hasOperatorName("%="),
+            hasOperatorName("&="), hasOperatorName("|="), hasOperatorName("^="),
+            hasOperatorName("<<="), hasOperatorName(">>=")),
+      hasLHS(ignoringParenImpCasts(expr().bind(NodeName))));
+}
+static internal::Matcher<Stmt>
+changedByIncrementOrDecrement(StringRef NodeName) {
+  return unaryOperator(
+      anyOf(hasOperatorName("--"), hasOperatorName("++")),
+      hasUnaryOperand(ignoringParenImpCasts(expr().bind(NodeName))));
+}
+
+static internal::Matcher<Stmt> changeVariable() {
+  return anyOf(changedByIncrementOrDecrement("changedExpr"),
+               changedByAssignement("changedExpr"), callByRef("changedExpr"),
+               cxxNonConstCall("changedExpr"));
+}
+
 namespace clang {
 namespace ento {
 
+bool collectRegion(const Expr *E,
+                   llvm::SmallSet<const MemRegion *, 16> &RegionsToInvalidate,
+                   ProgramStateRef State, const LocationContext *LCtx) {
+  const VarDecl *VD = nullptr;
+  while (true) {
+    E = E->IgnoreParenImpCasts();
+    switch (E->getStmtClass()) {
+    case Stmt::DeclRefExprClass:
+      VD = dyn_cast<VarDecl>(cast<DeclRefExpr>(E)->getDecl());
+      if (!VD || VD->getType()->isAnyPointerType() ||
+          VD->getType()->isReferenceType())
+        return false;
+      RegionsToInvalidate.insert(State->getLValue(VD, LCtx).getAsRegion());
+      return true;
+    case Stmt::MemberExprClass:
+      E = cast<MemberExpr>(E)->getBase();
+      break;
+    case Stmt::CXXDependentScopeMemberExprClass:
+      E = cast<CXXDependentScopeMemberExpr>(E)->getBase();
+      break;
+    case Stmt::ArraySubscriptExprClass:
+      E = cast<ArraySubscriptExpr>(E)->getBase();
+      break;
+    default:
+      return false;
+    }
+  }
+}
+
+ProgramStateRef getConservativelyWidenedLoopState(ProgramStateRef State,
+                                                  ASTContext &ASTCtx,
+                                                  const LocationContext *LCtx,
+                                                  unsigned BlockCount,
+                                                  const Stmt *LoopStmt) {
+
+  llvm::SmallSet<const MemRegion *, 16> RegionsToInvalidate;
+  auto Matches = match(findAll(changeVariable()), *LoopStmt, ASTCtx);
+  for (auto &Match : Matches) {
+    auto E = Match.getNodeAs<Expr>("changedExpr");
+    bool Success = collectRegion(E, RegionsToInvalidate, State, LCtx);
+    if (!Success)
+      return State;
+  }
+  llvm::SmallVector<const MemRegion *, 16> Regions;
+  Regions.reserve(RegionsToInvalidate.size());
+  for (auto E : RegionsToInvalidate)
+    Regions.push_back(E);
+
+  return State->invalidateRegions(llvm::makeArrayRef(Regions),
+                                  getLoopCondition(LoopStmt), BlockCount, LCtx,
+                                  true);
+}
+
 ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState,
                                     const LocationContext *LCtx,
                                     unsigned BlockCount, const Stmt *LoopStmt) {
 
   assert(isa<ForStmt>(LoopStmt) || isa<WhileStmt>(LoopStmt) ||
          isa<DoStmt>(LoopStmt));
 
   // Invalidate values in the current state.

lib/StaticAnalyzer/Core/PathDiagnostic.cpp

 
 PathDiagnosticLocation
 PathDiagnosticLocation::create(const ProgramPoint& P,
                                const SourceManager &SMng) {
   const Stmt* S = nullptr;
   if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
     const CFGBlock *BSrc = BE->getSrc();
     S = BSrc->getTerminatorCondition();
+  } else if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) {
+    const CFGBlock *BSrc = BE->getBlock();
+    S = BSrc->getTerminatorCondition();
   } else if (Optional<StmtPoint> SP = P.getAs<StmtPoint>()) {
     S = SP->getStmt();
     if (P.getAs<PostStmtPurgeDeadSymbols>())
       return PathDiagnosticLocation::createEnd(S, SMng, P.getLocationContext());
   } else if (Optional<PostInitializer> PIP = P.getAs<PostInitializer>()) {
     return PathDiagnosticLocation(PIP->getInitializer()->getSourceLocation(),
                                   SMng);
   } else if (Optional<PostImplicitCall> PIE = P.getAs<PostImplicitCall>()) {

test/Analysis/analyzer-config.c

 // CHECK-NEXT: max-inlinable-size = 100
 // CHECK-NEXT: max-nodes = 225000
 // CHECK-NEXT: max-times-inline-large = 32
 // CHECK-NEXT: min-cfg-size-treat-functions-as-large = 14
 // CHECK-NEXT: mode = deep
 // CHECK-NEXT: region-store-small-struct-limit = 2
 // CHECK-NEXT: unroll-loops = false
 // CHECK-NEXT: widen-loops = false
+// CHECK-NEXT: widen-loops-conservative = false
 // CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 19
+// CHECK-NEXT: num-entries = 20

test/Analysis/analyzer-config.cpp

 // CHECK-NEXT: max-inlinable-size = 100
 // CHECK-NEXT: max-nodes = 225000
 // CHECK-NEXT: max-times-inline-large = 32
 // CHECK-NEXT: min-cfg-size-treat-functions-as-large = 14
 // CHECK-NEXT: mode = deep
 // CHECK-NEXT: region-store-small-struct-limit = 2
 // CHECK-NEXT: unroll-loops = false
 // CHECK-NEXT: widen-loops = false
+// CHECK-NEXT: widen-loops-conservative = false
 // CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 24
+// CHECK-NEXT: num-entries = 25

test/Analysis/loop-widening-conservative.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,unix.Malloc,debug.ExprInspection -analyzer-max-loop 4 -analyzer-config widen-loops-conservative=true -verify -std=c++11 %s
+
+void clang_analyzer_eval(int);
+void clang_analyzer_warnIfReached();
+
+typedef __typeof(sizeof(int)) size_t;
+void *malloc(size_t);
+void free(void *);
+
+void loop_which_iterates_limit_times_not_widened() {
+  int i;
+  int x = 1;
+  // Check loop isn't widened by checking x isn't invalidated
+  for (i = 0; i < 1; ++i) {
+  }
+  clang_analyzer_eval(x == 1); // expected-warning {{TRUE}}
+  for (i = 0; i < 2; ++i) {
+  }
+  clang_analyzer_eval(x == 1); // expected-warning {{TRUE}}
+  for (i = 0; i < 3; ++i) {
+  }
+  clang_analyzer_eval(x == 1); // expected-warning {{TRUE}}
+  for (i = 0; i < 4; ++i) {
+  }
+  clang_analyzer_eval(x == 1); // expected-warning {{TRUE}}
+}
+
+int a_global;
+
+void loop_evaluated_before_widening() {
+  int i;
+  a_global = 1;
+  for (i = 0; i < 10; ++i) {
+    if (i == 2) {
+      // True before widening then unknown after.
+      clang_analyzer_eval(a_global == 1); // expected-warning{{TRUE}}
+    }
+  }
+  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void warnings_after_loop() {
+  int i;
+  for (i = 0; i < 10; ++i) {
+  }
+  char *m = (char *)malloc(12);
+} // expected-warning {{Potential leak of memory pointed to by 'm'}}
+
+void for_loop_exits() {
+  int i;
+  for (i = 0; i < 10; ++i) {
+  }
+  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void invariably_infinite_loop() {
+  int i = 0;
+  for (;;) {
+    ++i;
+  }
+  clang_analyzer_warnIfReached(); // no-warning
+}
+
+void invariably_infinite_break_loop() {
+  int i = 0;
+  while (1) {
+    ++i;
+    int x = 1;
+    if (!x)
+      break;
+  }
+  clang_analyzer_warnIfReached(); // no-warning
+}
+
+void reachable_break_loop() {
+  int i = 0;
+  while (1) {
+    ++i;
+    if (i == 100)
+      break;
+  }
+  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void condition_constrained_true_in_loop() {
+  int i = 0;
+  while (i < 50) {
+    clang_analyzer_eval(i < 50); // expected-warning {{TRUE}}
+    ++i;
+  }
+  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void condition_constrained_false_after_loop() {
+  int i = 0;
+  while (i < 50) {
+    ++i;
+  }
+  clang_analyzer_eval(i >= 50);   // expected-warning {{TRUE}}
+  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+}
+
+void multiple_exit_test() {
+  int x = 0;
+  int i = 0;
+  while (i < 50) {
+    if (x) {
+      i = 10;
+      break;
+    }
+    ++i;
+  }
+  // Reachable by 'normal' exit.
+  if (i == 50)
+    clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
+  // x is known to be 0, not reachable from break.
+  if (i == 10)
+    clang_analyzer_warnIfReached(); // no-warning
+  // Not reachable.
+  if (i < 10)
+    clang_analyzer_warnIfReached(); // no-warning
+  if (i > 10 && i < 50)
+    clang_analyzer_warnIfReached(); // no-warning
+}
+
+void pointer_doesnt_leak_from_loop() {
+  int *h_ptr = (int *)malloc(sizeof(int));
+  for (int i = 0; i < 2; ++i) {
+  }
+  for (int i = 0; i < 10; ++i) {
+  } // no-warning
+  free(h_ptr);
+}
+
+int g_global;
+
+void unknown_after_loop(int s_arg) {
+  g_global = 0;
+  s_arg = 1;
+  int s_local = 2;
+  int *h_ptr = (int *)malloc(sizeof(int));
+  int change_var = 1;
+  int nochange_var = 10;
+  for (int i = 0; i < 10; ++i) {
+    change_var *= nochange_var + nochange_var;
+  }
+
+  clang_analyzer_eval(change_var == 1);    // expected-warning {{UNKNOWN}}
+  clang_analyzer_eval(nochange_var == 10); // expected-warning {{TRUE}}
+
+  clang_analyzer_eval(g_global);     // expected-warning {{UNKNOWN}}
+  clang_analyzer_eval(s_arg == 1);   // expected-warning {{TRUE}}
+  clang_analyzer_eval(s_local == 2); // expected-warning {{TRUE}}
+  clang_analyzer_eval(h_ptr == 0);   // expected-warning {{UNKNOWN}}
+  free(h_ptr);
+}
+
+void nested_loop_outer_widen() {
+  int i = 0, j = 0;
+  for (i = 0; i < 10; i++) {
+    clang_analyzer_eval(i < 10); // expected-warning {{TRUE}}
+    for (j = 0; j < 2; j++) {
+      clang_analyzer_eval(j < 2); // expected-warning {{TRUE}}
+    }
+    clang_analyzer_eval(j >= 2); // expected-warning {{TRUE}}
+  }
+  clang_analyzer_warnIfReached(); // no-warning
+}
+
+void nested_loop_inner_widen() {
+  int i = 0, j = 0;
+  for (i = 0; i < 2; i++) {
+    clang_analyzer_eval(i < 2); // expected-warning {{TRUE}}
+    for (j = 0; j < 10; j++) {
+      clang_analyzer_eval(j < 10); // expected-warning {{TRUE}}
+    }
+    clang_analyzer_eval(j >= 10); // expected-warning {{TRUE}}
+  }
+  clang_analyzer_warnIfReached(); // no-warning
+}
+
+struct A {
+  A(int n) : num(n){};
+  int num;
+  void foo();
+  void bar() const;
+  bool operator==(const A &other) const;
+  void operator=(const A &other);
+  void assign(const A &other) { num = other.num; }
+};
+
+void non_const_method_call() {
+  A a(42);
+  for (int i = 0; i < 10; ++i) {
+    a.foo();
+  }
+  clang_analyzer_eval(a.num == 42); // expected-warning {{UNKNOWN}}
+}
+
+void const_method_call() {
+  A a(42);
+  for (int i = 0; i < 10; ++i) {
+    a.bar();
+  }
+  clang_analyzer_eval(a.num == 42); // expected-warning {{TRUE}}
+}
+
+void knwon_method_call() {
+  A a(42);
+  A b(10);
+  for (int i = 0; i < 10; ++i) {
+    a.assign(b);
+  }
+  // Loss of precision. It could be worth to simulate the last iteration after
+  // widening as well.
+  clang_analyzer_eval(a.num == 10); // expected-warning {{UNKNOWN}}
+}
+
+void non_const_operator_call() {
+  A a(42);
+  A b(10);
+  for (int i = 0; i < 10; ++i) {
+    a = b;
+  }
+  clang_analyzer_eval(a.num == 42); // expected-warning {{UNKNOWN}}
+}
+
+void const_operator_call() {
+  A a(42);
+  A b(10);
+  for (int i = 0; i < 10; ++i) {
+    if (a == b)
+      continue;
+  }
+  clang_analyzer_eval(a.num == 42); // expected-warning {{TRUE}}
+}
+
+void passByRef(int &n);
+void passByConstRef(const int &n);
+
+void widen_escape() {
+  int n = 2;
+  for (int i = 0; i < 10; ++i) {
+    passByRef(n);
+  }
+  clang_analyzer_eval(n == 2); // expected-warning {{UNKNOWN}}
+}
+
+void widen_const_escape() {
+  int n = 2;
+  for (int i = 0; i < 10; ++i) {
+    passByConstRef(n);
+  }
+  clang_analyzer_eval(n == 2); // expected-warning {{TRUE}}
+}
+
+void widen_array() {
+  int arr[10];
+  for (int i = 0; i < 10; ++i) {
+    arr[i] = i;
+  }
+  clang_analyzer_eval(arr[5] == 5); // expected-warning {{UNKNOWN}}
+}
+
+void no_widen_pointer() {
+  int *r = nullptr;
+  for (int i = 0; i < 10; ++i) {
+    int *p;
+    p = r;
+  }
+  clang_analyzer_warnIfReached(); // no-warning
+}
+
+void no_widen_pointer1() {
+  int a = 1;
+  int *p = &a;
+  for (int i = 0; i < 10; ++i) {
+    (*p)++;
+  }
+  clang_analyzer_warnIfReached(); // no-warning
+}
+
+void no_widen_pointer2() {
+  int a = 1;
+  int *p = &a;
+  for (int i = 0; i < 10; ++i) {
+    *p = 2;
+  }
+  clang_analyzer_warnIfReached(); // no-warning
+}