[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 ↗

(On Diff #110989)

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 ↗

(On Diff #110989)

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

1554–1556

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

269 ↗

(On Diff #112551)

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/PathSensitive/LoopWidening.h

 
 namespace clang {
 namespace ento {
 
 /// \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,
+ProgramStateRef getWidenedLoopState(ProgramStateRef State, ASTContext &ASTCtx,
                                     const LocationContext *LCtx,
                                     unsigned BlockCount, const Stmt *LoopStmt);
 
 } // end namespace ento
 } // end namespace clang
 
 #endif

lib/StaticAnalyzer/Core/ExprEngine.cpp

void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
   if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 &&
       AMgr.options.shouldWidenLoops()) {
     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);
+    ProgramStateRef WidenedState = getWidenedLoopState(Pred->getState(),
+                                                       AMgr.getASTContext(),
+                                                       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 {
 
-ProgramStateRef getWidenedLoopState(ProgramStateRef PrevState,
+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 getWidenedLoopState(ProgramStateRef State, ASTContext &ASTCtx,
                                     const LocationContext *LCtx,
                                     unsigned BlockCount, const Stmt *LoopStmt) {
 
-  assert(isa<ForStmt>(LoopStmt) || isa<WhileStmt>(LoopStmt) ||
-         isa<DoStmt>(LoopStmt));
-
-  // Invalidate values in the current state.
-  // TODO Make this more conservative by only invalidating values that might
-  //      be modified by the body of the loop.
-  // TODO Nested loops are currently widened as a result of the invalidation
-  //      being so inprecise. When the invalidation is improved, the handling
-  //      of nested loops will also need to be improved.
-  const StackFrameContext *STC = LCtx->getCurrentStackFrame();
-  MemRegionManager &MRMgr = PrevState->getStateManager().getRegionManager();
-  const MemRegion *Regions[] = {MRMgr.getStackLocalsRegion(STC),
-                                MRMgr.getStackArgumentsRegion(STC),
-                                MRMgr.getGlobalsRegion()};
-  RegionAndSymbolInvalidationTraits ITraits;
-  for (auto *Region : Regions) {
-    ITraits.setTrait(Region,
-                     RegionAndSymbolInvalidationTraits::TK_EntireMemSpace);
-  }
-  return PrevState->invalidateRegions(Regions, getLoopCondition(LoopStmt),
-                                      BlockCount, LCtx, true, nullptr, nullptr,
-                                      &ITraits);
+  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);
 }
 
 } // end namespace ento
 } // end namespace clang

test/Analysis/loop-widening.c

-// RUN: %clang_analyze_cc1 -analyzer-checker=core,unix.Malloc,debug.ExprInspection -analyzer-max-loop 4 -analyzer-config widen-loops=true -verify %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) {}
-  // FIXME loss of precision as a result of evaluating the widened loop body
-  //       *instead* of the last iteration.
-  clang_analyzer_eval(x == 1); // expected-warning {{UNKNOWN}}
-}
-
-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}} expected-warning{{UNKNOWN}}
-    }
-  }
-  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 while_loop_exits() {
-  int i = 0;
-  while (i < 10) {++i;}
-  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-}
-
-void do_while_loop_exits() {
-  int i = 0;
-  do {++i;} while (i < 10);
-  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-}
-
-void loop_body_is_widened() {
-  int i = 0;
-  while (i < 100) {
-    if (i > 10) {
-      clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-    }
-    ++i;
-  }
-  clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-}
-
-void invariably_infinite_loop() {
-  int i = 0;
-  while (1) { ++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}}
-  // Reachable by break point
-  if (i == 10) clang_analyzer_warnIfReached(); // expected-warning{{REACHABLE}}
-  // 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 = malloc(sizeof(int));
-
-  for (int i = 0; i < 10; ++i) {}
-
-  clang_analyzer_eval(g_global); // expected-warning {{UNKNOWN}}
-  clang_analyzer_eval(s_arg); // expected-warning {{UNKNOWN}}
-  clang_analyzer_eval(s_local); // expected-warning {{UNKNOWN}}
-  clang_analyzer_eval(h_ptr == 0); // expected-warning {{UNKNOWN}}
-  free(h_ptr);
-}
-
-void variable_bound_exiting_loops_widened(int x) {
-  int i = 0;
-  int t = 1;
-  while (i < x) {
-    ++i;
-  }
-  clang_analyzer_eval(t == 1); // expected-warning {{TRUE}} // expected-warning {{UNKNOWN}}
-}
-
-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_eval(i >= 10); // expected-warning {{TRUE}}
-}
-
-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_eval(i >= 2); // expected-warning {{TRUE}}
-}

test/Analysis/loop-widening.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,unix.Malloc,debug.ExprInspection -analyzer-max-loop 4 -analyzer-config widen-loops=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_pointer2() {
+  int a = 1;
+  int *p = &a;
+  for (int i = 0; i < 10; ++i) {
+    (*p)++;
+  }
+  clang_analyzer_warnIfReached(); // no-warning
+}
+
+void no_widen_pointer3() {
+  int a = 1;
+  int *p = &a;
+  for (int i = 0; i < 10; ++i) {
+    *p = 2;
+  }
+  clang_analyzer_warnIfReached(); // no-warning
+}