[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

44–45

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

44–45

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

69

There are some more compound assignment operators:

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

84

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)?

90

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

1552–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

62

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/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"
 
 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();
   }
 }
 
+/// Return the loops body Stmt or NULL if LoopStmt is not a loop
+static const Stmt *getLoopBody(const Stmt *LoopStmt) {
+  switch (LoopStmt->getStmtClass()) {
+  default:
+    return nullptr;
+  case Stmt::ForStmtClass:
+    return cast<ForStmt>(LoopStmt)->getBody();
+  case Stmt::WhileStmtClass:
+    return cast<WhileStmt>(LoopStmt)->getBody();
+  case Stmt::DoStmtClass:
+    return cast<DoStmt>(LoopStmt)->getBody();
+  }
+}
+
 namespace clang {
 namespace ento {
 
+static internal::Matcher<Stmt> callByRef(StringRef NodeName) {
+  return callExpr(forEachArgumentWithParam(
+      declRefExpr(to(varDecl().bind(NodeName))),
+      parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))));
+}
+
+static internal::Matcher<Stmt> changeVariable() {
+  return anyOf(
+      unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")),
+                    hasUnaryOperand(ignoringParenImpCasts(
+                        declRefExpr(to(varDecl().bind("changedVar")))))),
+      binaryOperator(anyOf(hasOperatorName("="), hasOperatorName("+="),
+                           hasOperatorName("/="), hasOperatorName("*="),
+                           hasOperatorName("-=")),
+                     hasLHS(ignoringParenImpCasts(
+                         declRefExpr(to(varDecl().bind("changedVar")))))),
+      callByRef("changedVar"),
+      cxxMemberCallExpr(
+          anyOf(on(declRefExpr(to(varDecl().bind("changedDecl")))),
+                unless(callee(cxxMethodDecl(isConst()))))),
+      cxxOperatorCallExpr(hasArgument(0, ignoringImpCasts(declRefExpr(to(
+                                             varDecl().bind("changedVar"))))),
+                          unless(callee(cxxMethodDecl(isConst())))));
+}
+
+static internal::Matcher<Stmt> hasPointerStmt() {
+  return hasDescendant(declRefExpr(
+      to(varDecl(anyOf(hasType(isAnyPointer()), hasType(arrayType()))))));
+}
+
+bool shouldWiden(const Stmt *LoopStmt, ASTContext &ASTCtx) {
+  auto Matches = match(hasPointerStmt(), *LoopStmt, ASTCtx);
+  if (!Matches.empty())
+    return false;
+
+  return true;
+}
+
+ProgramStateRef getConservativelyWidenedLoopState(ProgramStateRef State,
+                                                  ASTContext &ASTCtx,
+                                                  const LocationContext *LCtx,
+                                                  unsigned BlockCount,
+                                                  const Stmt *LoopStmt) {
+  if (!shouldWiden(LoopStmt, ASTCtx))
+    return State;
+
+  std::set<const VarDecl *> LoopVars;
+  auto Matches =
+      match(findAll(varDecl().bind("varDecl")), *getLoopBody(LoopStmt), ASTCtx);
+  for (auto &Match : Matches)
+    LoopVars.insert(Match.getNodeAs<VarDecl>("varDecl"));
+
+  std::set<const MemRegion *> RegionsToInvalidate;
+  Matches = match(findAll(changeVariable()), *LoopStmt, ASTCtx);
+  for (auto &Match : Matches) {
+    auto VD = Match.getNodeAs<VarDecl>("changedVar");
+    if (!VD || LoopVars.find(VD) != LoopVars.end())
+      continue;
+    if (auto Region = State->getLValue(VD, LCtx).getAsRegion())
+      RegionsToInvalidate.insert(Region);
+  }
+  std::vector<const MemRegion *> 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.

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