[StaticAnalyzer] Completely unrolling specific loops with known bound option

[szepet]

Summary

This feature allows the analyzer to consider loops to completely unroll. New requirements/rules (for unrolling) can be added easily via ASTMatchers.

Right now it is hidden behind a flag, the aim is to find the correct heuristic and create a solution which results higher coverage % and more precise analysis, thus can be enabled by default.

Right now the blocks which belong to an unrolled loop are marked by the LoopVisitor which adds them to the ProgramState.
Then whenever we encounter a CFGBlock in the processCFGBlockEntrance which is marked then we skip its investigating. That means, it won't be considered to be visited more than the maximal bound for visiting since it won't be checked.

[xazax.hun]

Nice work! Some comments inline.

include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

548

Maybe the name should be more specific to express that it is not applied to every loop?

lib/StaticAnalyzer/Core/ExprEngine.cpp

1521

This change is not relevant for this patch.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

42

Commented code. Maybe you can transform this to an assert.

55

Prefer StringRef as argument.

127

We do not try to check the bound? E.g.: if it is larger than a big number (according to the analyzer).

177

I wonder if State is the right place to store this information. Usually, we store path sensitive information in the state, but this information tha way compute now is not path sensitive. Maybe there could be a map that is independent of the program state? Or a property of the basic blocks?

[szepet]

Small update based on comments.

[a.sidorin]

Hello Peter,

While enabling this by default looks dangerous, I think is nice to have some option for analyzer. I have some comments inline.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

45

Our team has encountered some problems with plain static matchers recently - they can randomly crash while destructing. We're investigating it right now. Possibly, ManagedStatic should be used for them, but we don't know this exactly and nobody answered in cfe-dev about this.

50

It also seems harmless to support casts from integer literals here. Example: unsigned i = 0; i < 9; ++i) // 9 should have a cast. Same for init matcher.

138

Maybe we should just use anyOf() matcher instead of this condition chain?

173

This can be nicely C++11-fied.

177

+1. I wonder if this can harm merging of ExplodedNodes due to difference in state. Maybe it should be removed at all? Nobody reads it anyway.

test/Analysis/analyzer-config.cpp

43

Missed newline.

test/Analysis/loop-unrolling.cpp

102

I see some inconsistency in formatting of this file. Could you clang-format it?

[NoQ]

Uhm, it just striked me where this is going. So, generally, we're bound to track when we're entering the loop and exiting the loop. And we have troubles with that, because just by looking at the block we can't say in what loops we are.

We technically can find out which loop we are in until IPA comes in (by ascending through parent statements, or the way Peter does it, which is the same thing "inside out" - by listing the affected blocks). It gets worse when IPA comes in, especially when recursion comes in.

Now to the eureka - am i the only one here who totally forgot about D16403/D19979?

[NoQ]

A historical retrospective for Peter: there have been quite a few people, at different moments of time, who wanted a checker callback for entering and exiting "scopes". For example, StackAddrEscapeChecker finds local variables that escape a function by reference, but doesn't find local variables that escape an if-branch or a loop body by reference. The proposed approach involved creating a ScopeContext, a counterpart of StackFrameContext that gets constructed and put on the stack of location contexts when a scope is entered and popped when the scope is exited, similarly to how StackFrameContext is put on the stack of location contexts to represent the function call. Because a lot of events occur at scope boundaries, that'd be a great addition. However, the patches i mentioned are not yet done because some corner-cases were not handled. Whether you should complete these patches, as part of your GSoC project - i do not know, it may be harder than it seems. But they'd certainly serve as a good source of inspiration.

[a.sidorin]

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

45

Oops, sorry - I have missed that it is a function. Please ignore my previous comment.

[a.sidorin]

Now to the eureka - am i the only one here who totally forgot about D16403/D19979?

We're working on bringing it back to life right now. But it takes time.

[NoQ]

In D34260#783863, @a.sidorin wrote:

Now to the eureka - am i the only one here who totally forgot about D16403/D19979?

We're working on bringing it back to life right now. But it takes time.

That's totally cool.

Do you think it'd be possible to split up ScopeContext support into small patches that handle different kinds of scopes? Like, ifs in one patch, loops in another patch, anything that involves weird gotos in the last patch. Have some obvious scopes generate the scope context, and the rest of them behave as before, and slowly grow the set of kinds of scopes that have their scope context. Then we'd be able to catch our loop entrances/exits in simple loops without needing to wait for the corner cases to be fully polished. Or do the corner cases stick themselves everywhere and spoil all the fun?

[a.sidorin]

The problem here is not in ScopeContext - it isn't going to be a huge patch. The problem is CFG-related mostly - there are many corner cases. We'll also need some help with fixing Objective-C checkers (RetainCount, for example).

[NoQ]

Yeah, right, i guess it's mostly about the CFG patch; i was just saying that if, in the end, we don't get scope contexts for all the scopes, this is probably fine - as long as we have *some* of them.

Hmm, could you remind me what was wrong with RetainCountChecker? (better in the other review^^)

[seaneveson]

Thanks for looking at this.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

46

You might want to account for != e.g. for (x = 10; x != 0; --x)

55

I think there is an edge case here, what happens if the loop variant is incremented or decremented multiple times in the body?:

while (x > 0) {
  ++x;
  // ...
  --x;
}

test/Analysis/loop-unrolling.cpp

36

Should this be // no-warning as the loop should not be unrolled? And the same for simple_no_unroll2?

[zaks.anna]

The problem here is not in ScopeContext - it isn't going to be a huge patch. The problem is CFG-related mostly - there are many corner cases. We'll also need some help with
fixing Objective-C checkers (RetainCount, for example).

@a.sidorin, please, send patches for review in small increments to make sure the patches get immediate feedback, before they get too big.
Thank you for looking into this!

[szepet]

Answered comments and made changes according to them.

Thank you for every comment and notes/guidance.

In D34260#783863, @a.sidorin wrote:

Now to the eureka - am i the only one here who totally forgot about D16403/D19979?

We're working on bringing it back to life right now. But it takes time.

As I understand these patches could possibly solve all of the problems which are correlated to the scopes of the loops. Thanks in advance for your work! As I see it will take a long time to finish it but great to know it is still developed!

include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

548

Could not come up with a more specific but short (at least not 1 km long) name. Do you might have a great idea for that?

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

55

Yes, there is a problem (thought about that) and I have to say here, that these are only initial patterns which must be improved to make the feature useful. Right now in the first patch the aim was only to have some patterns which can show the community that there are cases when it is worth to unroll. So - according to my plans - edge cases like this will be covered in a follow-up patch if it is alright.

127

Yepp, that is an important thing to work on. Evaluating these integer literals and even known integer variables will be the main part of the next patch on unrolling.

138

Sure! My idea was to use a MatchFinder but it provides me only analyzing the results via a callback function and it did not really fit into this model as I see. So if you have any other idea how to make these matchers more organized please let me know.

177

That is not exactly true that nobody reads it, the isUnrolledLoopBlock() function returns its value depending on this information. However, you (both) are right that it would be nice to use less memory and instead of storing we could look it up based on the stored LoopStmt (so I have rewritten it that way).

test/Analysis/loop-unrolling.cpp

36

As far as I see understand the Analyzer behavior it should warn since variable i is escaped (because the body of the function foo() is not known and passed it by ref). So the (symbolic) value i becomes unknown and the Analyzer inspects both possibilities when evaluating the condition. (Same below.)

However, in case simple_no_unroll3()the analyzer is able to model every step and track the value of i.

[seaneveson]

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

55

OK, sounds good.

test/Analysis/loop-unrolling.cpp

36

Ah I didn't think of that. Maybe you could also explicitly check in the test that the loop is not unrolled?

foo(i);
if (i == 8)
  int c = 22 / (k - 42); // no-warning

Or something similar?

[szepet]

test/Analysis/loop-unrolling.cpp

36

It raises the same problem. Since in the second iteration the value of i will be unknown the analyzer will consider the case in which its value is 8. So that branch will be evaluated in the second iteration.
I don't really see a way to check this explicitly like that (maybe I miss something trivial and in that case please let me know!). The best I could think about was to check these implicitly through the statistics (which check can be found at the end of the file).

[szepet]

Just ran clang-format on LoopUnrolling.cpp.

[szepet]

Updated the check of the blocks of inline analyzed functions using StackFrameContext.

[zaks.anna]

lib/StaticAnalyzer/Core/ExprEngine.cpp

1521

Would this work if you have a loop with a known bound that calls a function, which itself has a loop? (I assume that the analyzer has the body for the function and it can be inlined.)

I am concerned that even though the nested loops are outlawed by the LoopBlockVisitor, they could sneak in indirectly through an inlined function.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

155

Maybe add a comment saying "No support for nested loops right now."

[szepet]

Bug with nested loops in inlined functions fixed.
Test cases added.

lib/StaticAnalyzer/Core/ExprEngine.cpp

1521

Yes, and that case was not handled. I came up with the most simple but a little bit hacky solution to that. Added tests for this case.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

155

I could but I think it is not true, though. Exactly that line is the support for nested loops. I mean that in case of nested loops we only mark the outer loop as unrolled. I think this is the way how the feature should work. It is quite simple but in case of a complex inner loop we fall back to the conservative way in order to not simulate unnecessary things and avoid false positives.

[NoQ]

So how much of this would be thrown away once we have scopes?

The matchers will remain.
isUnrolledLoopBlock() would be rewritten.
LoopBlockVisitor would most likely be replaced with ascending location contexts, which would also cover IPA-related tricks.
processCFGBlockEntrance is already reworked in the next patch.

So this patch is adding some matchers and some proof-of-concept code to make them work.
Sounds good to me, i think we can land this. I'd have a closer look at the matchers and then accept.

[xazax.hun]

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

25

I think the formatting is off in this file. Do you need all these includes in this header?

lib/StaticAnalyzer/Core/CMakeLists.txt

59

What do you use DynamicASTMatchers for? Are you sure you need that?

lib/StaticAnalyzer/Core/ExprEngine.cpp

1504

The block is terminated by a loop? I think this comment is confusing. Maybe you wanted to say something like the blocks of loops are registered based on the terminator statement?

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

55

What about unary operators like ++/--? I think if you do not consider this deliberately, you should add a comment why.

96

Do you cover aliases?

E.g.:

for(int i = 0; i < 10; ++i) {
  int &j = i;
  --j;
}

106

I can see some code duplication e.g. the unless part of the loops.

172

Do you use this member?

[szepet]

Updated the patch according to the comments. Matchers updated.
Measured the number of matches of the pattern on various projects and it turns out that strict while/do-while patterns - which I'm looking for - are much less common than forStmts.
Detailed statistics:

Project	# of ForLoop	# of While/DoWhile Loop
Curl	419	11
Xerces	100	2
LibPNG	600	120
FFmpeg	30550	130

These are not the # of the different loops but the loops which was encountered by the analyzers and got unrolled. So I removed the while and do-while matchers from this initial patch.

[xazax.hun]

In D34260#803539, @szepet wrote:

Project	# of ForLoop	# of While/DoWhile Loop
Curl	419	11
Xerces	100	2
LibPNG	600	120
FFmpeg	30550	130

Just to be clear, both of the columns refer to the number of matches of your matchers right? So for loops that would not be unrolled are skipped.

[szepet]

Just to be clear, both of the columns refer to the number of matches of your matchers right? So for loops that would not be unrolled are skipped.

Yes.

[NoQ]

Yeah, it seems that if the same loop is encountered on different paths, it gets counted twice, but if it's encountered multiple times on the same path, it's counted once. At least this is how the new NumTimesLoopUnrolled statistic seems to work.

lib/StaticAnalyzer/Core/ExprEngine.cpp

25

Is this still used?

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

73

Hmm, does it make sense to handle escaping into brace initializers by reference?

73–77

NodeName unused.

test/Analysis/loop-unrolling.cpp

36

Would clang_analyzer_numTimesReached() be of any use?

[szepet]

Updates based on comments.

[szepet]

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

73

Yes, added the matcher and test case.

test/Analysis/loop-unrolling.cpp

36

That is exactly what I need for testing a feature like this. Unfortunately I could not really use it. Whenever I tried to call this in a function which is not the first defined function in the file then it just crashed. So right now I don't see if its a bug or a feature and I just misused it.

[NoQ]

test/Analysis/loop-unrolling.cpp

2

Hmm, just noticed this. Why does this require asserts?

36

I think we can definitely come up with a saner behavior =) If you post a crashing test, i'd gladly have a look.

[szepet]

test/Analysis/loop-unrolling.cpp

2

Since the statistics are enabled only if asserts are enabled. (At least that is how I think it is.)
http://llvm.org/doxygen/Statistic_8cpp_source.html#l0042 (Line42 says this and I think I already ran into that problem that I did not have any stat output since builded a release version.)

36

Just to make sure: to bugzilla or just leave one here?

[NoQ]

test/Analysis/loop-unrolling.cpp

2

Ok :0

36

Here's fine :)

[szepet]

test/Analysis/loop-unrolling.cpp

36

Alright! So the smallest examples I was able to came up are the following:

test1.cpp (works absolutely fine):

void clang_analyzer_numTimesReached();

void foo(){
 clang_analyzer_numTimesReached();
}

void bar(){
}

test2.cpp (crashes):

void clang_analyzer_numTimesReached();

void foo(){
}

void bar(){
 clang_analyzer_numTimesReached();
}

I have ran the following command:
clang -Xclang -analyze -Xclang -analyzer-checker=core,debug.ExprInspection -c test.cpp

(In more general I have experienced that it works iff it is used in the first defined function inside the TU.)

[NoQ]

test/Analysis/loop-unrolling.cpp

36

Ahaha, thanks! I guess you can just add ReachedStats.clear() at the end of ExprInspectionChecker::checkEndAnalysis().

It doesn't crash for the first function in the file because the first function in the file would be analyzed *last*, and the node pointer stored in that map would still be valid. But not for other functions.

[szepet]

updated the test files

[NoQ]

The new tests look great, thanks. I think it's time to land :) You do already have commit access, don't you?

[szepet]

In D34260#814856, @NoQ wrote:

The new tests look great, thanks. I think it's time to land :) You do already have commit access, don't you?

Yes, and thank you for the fast review and the solution for the bug. Unfortunately I had to revert it since it failed on clang-ppc64be-linux. Crashed while running the tests.
I was not able to reproduce the bug, so is there any way to use the buildbot for test purposes?

[szepet]

I suspect that the usage of the CFGStmtMap* caused the undefined behaviour since its lifetime was depending on its LocationContext.
In this version the isUnrolledLoopBlock creates the CFGStmtMap based on the CFG of the function which contains the unrolled loop. So the State stores FunctionDecl* instead of CFGStmtMap*.

Since clang_analyzer_numTimesReached() is a perfect tool to check the feature I removed the statistic checks.

Could you take a look?
(If you want to see a proper diff then skip Diff10. So compare Diff11 with Diff9.)

[szepet]

Removed REQUIRE ASSERT from test file.

[szepet]

Accidentally left typo removed.
OK so I am not sure but am I allowed to commit it again? I mean I made some notable changes. Not on the functionality of the feature but the stored data.
So should i wait for a quick review or could I commit it right now? (It is something that would be useful to know for future commits too.)

[NoQ]

I suspect that the usage of the CFGStmtMap* caused the undefined behaviour since its lifetime was depending on its LocationContext.

Yeah, it lives in AnalysisDeclContextManager, which lives in AnalysisManager, which lives throughout a single analysis (top-level function) and then dies (when the next top-level function is picked that wasn't covered during inlining) to clean up the allocators.

However, you store it in the program state, right? And the new analysis has new program states, which don't contain references to the old CFGStmtMaps(?)

Also the way you construct CFGStmtMap manually sounds slow to me (it's done on every path), i guess the whole point of having it in AnalysisDeclContext was to avoid this.

So i don't think this is it, but i guess you should try speculatively relanding anyway, and add the extra run-line that'd show you the backtrace. We made changes, so the issue might have been wiped out accidentally (or maybe you're actually right!), and if it wasn't, at least we'd have the backtrace for the crash.

[szepet]

In D34260#819721, @NoQ wrote:

... and add the extra run-line that'd show you the backtrace. We made changes, so the issue might have been wiped out accidentally (or maybe you're actually right!), and if it wasn't, at least we'd have the backtrace for the crash.

Hmm I removed the statistics checks so I guess it should print the stacktrace in case of a crash anyway. Am I right? (The whole point of the statistics check was to count the number of loops unrolled but 'clang_analyzer_numTimesReached();' is much more powerful.

[NoQ]

Yeah, right, good point =)

[teemperor]

If you can't reproduce, you should try running a debug build through valgrind. It points out this issue:

==29522== Invalid read of size 4
==29522==    at 0x16EBED0: clang::LocationContext::getCurrentStackFrame() const (in /opt/clang/build/bin/clang-6.0)
==29522==    by 0x1686BA9: clang::ento::isUnrolledLoopBlock(clang::CFGBlock const*, clang::ento::ExplodedNode*, clang::ento::AnalysisManager&) (in /opt/clang/build/bin/clang-6.0)
==29522==    by 0x164F009: clang::ento::ExprEngine::processCFGBlockEntrance(clang::BlockEdge const&, clang::ento::NodeBuilderWithSinks&, clang::ento::ExplodedNode*) (in /opt/clang/build/bin/clang-6.0)
==29522==    by 0x162A0B7: clang::ento::CoreEngine::HandleBlockEdge(clang::BlockEdge const&, clang::ento::ExplodedNode*) (in /opt/clang/build/bin/clang-6.0)
==29522==    by 0x162A455: clang::ento::CoreEngine::dispatchWorkItem(clang::ento::ExplodedNode*, clang::ProgramPoint, clang::ento::WorkListUnit const&) (in /opt/clang/build/bin/clang-6.0)
==29522==    by 0x162A782: clang::ento::CoreEngine::ExecuteWorkList(clang::LocationContext const*, unsigned int, llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>) (in /opt/clang/build/bin/clang-6.0)
==29522==    by 0xC6995E: (anonymous namespace)::AnalysisConsumer::ActionExprEngine(clang::Decl*, bool, clang::ento::ExprEngine::InliningModes, llvm::DenseSet<clang::Decl const*, llvm::DenseMapInfo<clang::Decl const*> >*) [clone .part.4645] (in /opt/clang/build/bin/clang-6.0)
==29522==    by 0xC6A1C9: (anonymous namespace)::AnalysisConsumer::HandleCode(clang::Decl*, unsigned int, clang::ento::ExprEngine::InliningModes, llvm::DenseSet<clang::Decl const*, llvm::DenseMapInfo<clang::Decl const*> >*) (in /opt/clang/build/bin/clang-6.0)
==29522==    by 0xC7577B: (anonymous namespace)::AnalysisConsumer::HandleTranslationUnit(clang::ASTContext&) [clone .part.4696] (in /opt/clang/build/bin/clang-6.0)
==29522==    by 0xC7EB19: clang::ParseAST(clang::Sema&, bool, bool) (in /opt/clang/build/bin/clang-6.0)
==29522==    by 0xA2CD65: clang::FrontendAction::Execute() (in /opt/clang/build/bin/clang-6.0)
==29522==    by 0x9F471D: clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (in /opt/clang/build/bin/clang-6.0)
==29522==  Address 0x10 is not stack'd, malloc'd or (recently) free'd

Try fixing this invalid read and the buildbots (and my builds :) ) should be working again.

[szepet]

In D34260#821186, @teemperor wrote:

Try fixing this invalid read and the buildbots (and my builds :) ) should be working again.

Yeah, thanks for the help! :)
I already sent a fix for that: https://reviews.llvm.org/rL309036 and another one: https://reviews.llvm.org/rL309061 which I think was not necessary but the buildbot failed on the first try (I still think it just haven't picked up the commit)
For me it seems that these fixes solved the problem as the address sanitizer tests passes as well on clang (and nobody reverted the commits^^).

[szepet]

So the fixes seem to work. The problem was the line 'StackFrame = StackFrame->getParent()->getCurrentStackFrame();' since I havent checked if the parent of the StackFrame is nullptr. (It is quite interesting that it just not crashed on my computer.)

[NoQ]

Cool, i totally forgot that we have valgrind! :)

[MTC]

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

108

Hi Peter, sorry to bother you!

I have some confusion here. Whether hasRHS(integerLiteral()) needs to added with ignoringParenImpCasts?

The given code below does not unroll the loop because i = 0; has a ImplicitCastExpr for 0. But if I change unsigned i = 0 to int i = 0, loop unrolling will happen. So I don't know if this is intentional.

int func() {
  int sum = 0;
  unsigned i;
  for (i = 0; i < 10; ++i) {
    sum++;
  }
  return sum;
}

Hope you can help me, thank you!

include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

private:
   Optional<unsigned> MaxNodesPerTopLevelFunction;
 
   /// \sa shouldInlineLambdas
   Optional<bool> InlineLambdas;
 
   /// \sa shouldWidenLoops
   Optional<bool> WidenLoops;
 
+  /// \sa shouldUnrollLoops
+  Optional<bool> UnrollLoops;
+
   /// \sa shouldDisplayNotesAsEvents
   Optional<bool> DisplayNotesAsEvents;
 
   /// A helper function that retrieves option for a given full-qualified
   /// checker name.
   /// Options for checkers can be specified via 'analyzer-config' command-line
   /// option.
   /// Example:
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 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
   /// to false when unset.
   bool shouldDisplayNotesAsEvents();
 
 public:

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

+//===--- LoopUnrolling.h - Unroll loops -------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// This header contains the declarations of functions which are used to decide
+/// which loops should be completely unrolled and mark their corresponding
+/// CFGBlocks.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_LOOPUNROLLING_H
+#define LLVM_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"
+#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+
+namespace clang {
+namespace ento {
+ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State);
+bool isUnrolledLoopBlock(const CFGBlock *Block, ProgramStateRef State,
+                         AnalysisManager &AMgr, CFGStmtMap *StmtToBlockMap);
+bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx);
+
+} // 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::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/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCore
   ExplodedGraph.cpp
   ExprEngine.cpp
   ExprEngineC.cpp
   ExprEngineCXX.cpp
   ExprEngineCallAndReturn.cpp
   ExprEngineObjC.cpp
   FunctionSummary.cpp
   HTMLDiagnostics.cpp
+  LoopUnrolling.cpp
   LoopWidening.cpp
   MemRegion.cpp
   PathDiagnostic.cpp
   PlistDiagnostics.cpp
   ProgramState.cpp
   RangeConstraintManager.cpp
   RangedConstraintManager.cpp
   RegionStore.cpp
   SValBuilder.cpp
   SVals.cpp
   SimpleConstraintManager.cpp
   SimpleSValBuilder.cpp
   Store.cpp
   SubEngine.cpp
   SymbolManager.cpp
   Z3ConstraintManager.cpp
 
   LINK_LIBS
   clangAST
+  clangASTMatchers
+  clangDynamicASTMatchers
   clangAnalysis
   clangBasic
   clangLex
   clangRewrite
   ${Z3_LINK_FILES}
   )
 
 if(CLANG_ANALYZER_WITH_Z3)
   target_include_directories(clangStaticAnalyzerCore SYSTEM
     PRIVATE
     ${Z3_INCLUDE_DIR}
     )
 endif()

lib/StaticAnalyzer/Core/ExprEngine.cpp

 //  This file defines a meta-engine for path-sensitive dataflow analysis that
 //  is built on GREngine, but provides the boilerplate to execute transfer
 //  functions and build the ExplodedGraph at the expression level.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
 #include "PrettyStackTraceLocationContext.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/AST/StmtVisitor.h"
 #include "clang/AST/CharUnits.h"
 #include "clang/AST/ParentMap.h"
+#include "clang/Analysis/CFGStmtMap.h"
 #include "clang/AST/StmtCXX.h"
+#include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/StmtObjC.h"
 #include "clang/Basic/Builtins.h"
 #include "clang/Basic/PrettyStackTrace.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Support/SaveAndRestore.h"
 #include "llvm/Support/raw_ostream.h"
 
 #ifndef NDEBUG
 #include "llvm/Support/GraphWriter.h"
 #endif
 
bool ExprEngine::replayWithoutInlining(ExplodedNode *N,
   return true;
 }
 
 /// Block entrance.  (Update counters).
 void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
                                          NodeBuilderWithSinks &nodeBuilder,
                                          ExplodedNode *Pred) {
   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
 
+  // If this block is terminated by 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())) {
+      ProgramStateRef UnrolledState =
+              markLoopAsUnrolled(Term, Pred->getState());
+      if (UnrolledState != Pred->getState())
+        nodeBuilder.generateNode(UnrolledState, Pred);
+      return;
+    }
+
+    if (isUnrolledLoopBlock(ActualBlock, Pred->getState(), AMgr,
+                            Pred->getLocationContext()
+                                    ->getAnalysisDeclContext()
+                                    ->getCFGStmtMap()))
+      return;
+    if (ActualBlock->empty())
+      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()) {
     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);
     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 =
                    nodeBuilder.generateSink(Pred->getState(), Pred, &tag);
 
     // Check if we stopped at the top level function or not.
     // Root node should have the location context of the top most function.
     const LocationContext *CalleeLC = Pred->getLocation().getLocationContext();
     const LocationContext *CalleeSF = CalleeLC->getCurrentStackFrame();
     const LocationContext *RootLC =
                         (*G.roots_begin())->getLocation().getLocationContext();
     if (RootLC->getCurrentStackFrame() != CalleeSF) {
       Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl());

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

+//===--- LoopUnrolling.cpp - Unroll loops -----------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// This file contains functions which are used to decide if a loop worth to be
+/// unrolled. Moreover contains function which mark the CFGBlocks which belongs
+/// to the unrolled loop and store them in ProgramState.
+///
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/CFGStmtMap.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/AST/ParentMap.h"
+#include "clang/AST/StmtVisitor.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"
+#include "llvm/ADT/Statistic.h"
+
+using namespace clang;
+using namespace ento;
+using namespace clang::ast_matchers;
+
+#define DEBUG_TYPE "LoopUnrolling"
+
+STATISTIC(NumTimesLoopUnrolled,
+          "The # of times a loop has got completely unrolled");
+
+REGISTER_SET_WITH_PROGRAMSTATE(UnrolledLoops, const Stmt *)
+REGISTER_SET_WITH_PROGRAMSTATE(UnrolledLoopBlocks, const CFGBlock *)
+
+namespace clang {
+namespace ento {
+
+static bool isLoopStmt(const Stmt *S) {
+  return S && (isa<ForStmt>(S) || isa<WhileStmt>(S) || isa<DoStmt>(S));
+}
+
+static internal::Matcher<Stmt> simpleCondition(std::string 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(const std::string &NodeName) {
+  return hasDescendant(binaryOperator(
+      anyOf(hasOperatorName("="), hasOperatorName("+="), hasOperatorName("/="),
+            hasOperatorName("*="), hasOperatorName("-=")),
+      hasLHS(ignoringParenImpCasts(
+          declRefExpr(to(varDecl(equalsBoundNode(NodeName))))))));
+}
+
+static internal::Matcher<Stmt> callByRef(std::string NodeName) {
+  return hasDescendant(callExpr(forEachArgumentWithParam(
+      declRefExpr(hasDeclaration(equalsBoundNode(NodeName))),
+      parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))));
+}
+
+static internal::Matcher<Stmt> getAddrTo(std::string NodeName) {
+  return hasDescendant(unaryOperator(
+      hasOperatorName("&"),
+      hasUnaryOperand(declRefExpr(hasDeclaration(equalsBoundNode(NodeName))))));
+}
+
+static internal::Matcher<Stmt> forLoopMatcher() {
+  return forStmt(
+             hasCondition(simpleCondition("initVarName")),
+             // Initialization should match the form: 'int i = 6' or 'i = 7'.
+             hasLoopInit(
+                 anyOf(declStmt(hasSingleDecl(
+                           varDecl(allOf(hasInitializer(integerLiteral()),
+                                         equalsBoundNode("initVarName"))))),
+                       binaryOperator(hasLHS(declRefExpr(to(varDecl(
+                                          equalsBoundNode("initVarName"))))),
+                                      hasRHS(integerLiteral())))),
+             // Incrementation should be a simple increment or decrement
+             // operator call.
+             hasIncrement(unaryOperator(
+                 anyOf(hasOperatorName("++"), hasOperatorName("--")),
+                 hasUnaryOperand(declRefExpr(
+                     to(varDecl(allOf(equalsBoundNode("initVarName"),
+                                      hasType(isInteger())))))))),
+             // Escaping and not known mutation of the loop counter is handled
+             // by exclusion of assigning and address-of operators and
+             // pass-by-ref function calls on the loop counter from the body.
+             unless(hasBody(anyOf(changeIntBoundNode("initVarName"),
+                                  callByRef("initVarName"),
+                                  getAddrTo("initVarName"))))).bind("forLoop");
+}
+
+static internal::Matcher<Stmt> whileLoopMatcher() {
+  return whileStmt(hasCondition(simpleCondition("initVarName")),
+                   hasBody(hasDescendant(unaryOperator(
+                       anyOf(hasOperatorName("++"), hasOperatorName("--")),
+                       hasUnaryOperand(declRefExpr(
+                           to(varDecl(allOf(equalsBoundNode("initVarName"),
+                                            hasType(isInteger()))))))))),
+                   unless(hasBody(anyOf(changeIntBoundNode("initVarName"),
+                                        callByRef("initVarName"),
+                                        getAddrTo("initVarName")))))
+      .bind("whileLoop");
+}
+
+static internal::Matcher<Stmt> doWhileLoopMatcher() {
+  return doStmt(hasCondition(simpleCondition("initVarName")),
+                hasBody(hasDescendant(unaryOperator(
+                    anyOf(hasOperatorName("++"), hasOperatorName("--")),
+                    hasUnaryOperand(declRefExpr(
+                        to(varDecl(allOf(equalsBoundNode("initVarName"),
+                                         hasType(isInteger()))))))))),
+                unless(hasBody(anyOf(
+                    changeIntBoundNode("initVarName"), callByRef("initVarName"),
+                    getAddrTo("initVarName"))))).bind("whileLoop");
+}
+
+static internal::Matcher<Stmt> loopMatcher() {
+  return anyOf(doWhileLoopMatcher(), whileLoopMatcher(), forLoopMatcher());
+}
+
+bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx) {
+
+  if (!isLoopStmt(LoopStmt))
+    return false;
+
+  // TODO: In cases of while and do..while statements the value of initVarName
+  // should be checked to be known
+  // TODO: Match the cases where the bound is not a concrete literal but an
+  // integer with known value
+
+  auto Matches = match(loopMatcher(), *LoopStmt, ASTCtx);
+  return !Matches.empty();
+}
+
+namespace {
+class LoopVisitor : public ConstStmtVisitor<LoopVisitor> {
+public:
+  LoopVisitor(ProgramStateRef St, AnalysisManager &AMgr, CFGStmtMap *M)
+      : State(St), AMgr(AMgr), StmtToBlockMap(M), Found(false) {}
+
+  void VisitChildren(const Stmt *S) {
+    for (const Stmt *Child : S->children())
+      if (Child)
+        Visit(Child);
+  }
+
+  void VisitStmt(const Stmt *S) {
+    if (!S || (isLoopStmt(S) && S != LoopStmt) || Found)
+      return;
+    assert(StmtToBlockMap->getBlock(S));
+    if(StmtToBlockMap->getBlock(S) == SearchedBlock){
+      Found = true;
+      return;
+    }
+
+    // In case of function calls investigate their CFGBlocks as well.
+    auto CallExp = dyn_cast<CallExpr>(S);
+    if (CallExp && CallExp->getCalleeDecl() &&
+        CallExp->getCalleeDecl()->getBody()) {
+      auto CalleeCFG = AMgr.getCFG(CallExp->getCalleeDecl());
+      for (auto &Block : *CalleeCFG) {
+        if(Block == SearchedBlock){
+          Found = true;
+          return;
+        }
+      }
+    }
+    VisitChildren(S);
+  }
+
+  bool isBlockOfLoop(const CFGBlock* B, const Stmt* Loop){
+    LoopStmt = Loop;
+    SearchedBlock = B;
+    Visit(LoopStmt);
+    return Found;
+  }
+
+private:
+  ProgramStateRef State;
+  AnalysisManager &AMgr;
+  CFGStmtMap *StmtToBlockMap;
+  const Stmt *LoopStmt;
+  bool Found;
+  const CFGBlock* SearchedBlock;
+};
+}
+
+bool isUnrolledLoopBlock(const CFGBlock *Block, ProgramStateRef State, AnalysisManager &AMgr,
+    CFGStmtMap *StmtToBlockMap) {
+
+  for (auto Term : State->get<UnrolledLoops>()) {
+    LoopVisitor LV(State, AMgr, StmtToBlockMap);
+    if(LV.isBlockOfLoop(Block,Term))
+      return true;
+  }
+  return false;
+
+}
+
+ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State) {
+  if (State->contains<UnrolledLoops>(Term))
+    return State;
+
+  State = State->add<UnrolledLoops>(Term);
+  ++NumTimesLoopUnrolled;
+  return State;
+}
+}
+}

test/Analysis/analyzer-config.c

 // CHECK-NEXT: ipa-always-inline-size = 3
 // CHECK-NEXT: leak-diagnostics-reference-allocation = false
 // CHECK-NEXT: max-inlinable-size = 50
 // CHECK-NEXT: max-nodes = 150000
 // 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: [stats]
-// CHECK-NEXT: num-entries = 15
-
+// CHECK-NEXT: num-entries = 16

test/Analysis/analyzer-config.cpp

 // CHECK-NEXT: ipa-always-inline-size = 3
 // CHECK-NEXT: leak-diagnostics-reference-allocation = false
 // CHECK-NEXT: max-inlinable-size = 50
 // CHECK-NEXT: max-nodes = 150000
 // 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: [stats]
-// CHECK-NEXT: num-entries = 20
+// CHECK-NEXT: num-entries = 21

test/Analysis/loop-unrolling.cpp

+// REQUIRES: asserts
+// RUN: %clang_analyze_cc1 -analyzer-checker=core -analyzer-config unroll-loops=true -analyzer-stats -verify %s 2>&1 | FileCheck %s
+
+int getNum();
+void foo(int &);
+// Testing for loops.
+int simple_unroll1() {
+  int a[9];
+  int k = 42;
+  for (int i = 0; i < 9; i++) {
+    a[i] = 42;
+  }
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
+int simple_unroll2() {
+  int a[9];
+  int k = 42;
+  int i;
+  for (i = 0; i < 9; i++) {
+    a[i] = 42;
+  }
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
+int simple_no_unroll1() {
+  int a[9];
+  int k = 42;
+  for (int i = 0; i < 9; i++) {
+    a[i] = 42;
+    foo(i);
+  }
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
+int simple_no_unroll2() {
+  int a[9];
+  int k = 42;
+  int i;
+  for (i = 0; i < 9; i++) {
+    a[i] = 42;
+    i += getNum();
+  }
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
+int simple_no_unroll3() {
+  int a[9];
+  int k = 42;
+  int i;
+  for (i = 0; i < 9; i++) {
+    a[i] = 42;
+    (void)&i;
+  }
+  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++) {
+    for (j = 0; j < getNum(); ++j) {
+      a[j] = 22;
+    }
+    a[i] = 42;
+  }
+  int b = 22 / (k - 42); // no-warning
+  return 0;
+}
+
+int nested_inner_unrolled() {
+  int a[9];
+  int k = 42;
+  int j = 0;
+  for (int i = 0; i < getNum(); i++) {
+    for (j = 0; j < 8; ++j) {
+      a[j] = 22;
+    }
+    a[i] = 42;
+  }
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
+int nested_both_unrolled() {
+  int a[9];
+  int k = 42;
+  int j = 0;
+  for (int i = 0; i < 7; i++) {
+    for (j = 0; j < 6; ++j) {
+      a[j] = 22;
+    }
+    a[i] = 42;
+  }
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
+// Testing while loops.
+int simple_unroll3() {
+  int a[9];
+  int k = 42;
+  int i = 0;
+  while (i < 9) {
+    a[i] = 42 * i;
+    ++i;
+  }
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
+int simple_unroll4() {
+  int a[22];
+  int k = 42;
+  int i = 21;
+  while (i > 7) {
+    a[i] = 42 * i;
+    --i;
+  }
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
+int simple_no_unroll4() {
+  int a[9];
+  int k = 42;
+  int i = 0;
+  while (i < 9) {
+    a[i] = 42 * i;
+  }
+  int b = 22 / (k - 42); // no-warning
+  return 0;
+}
+
+// Testing do-while loops.
+int simple_unroll5() {
+  int a[9];
+  int k = 42;
+  int i = 0;
+  do {
+    a[i] = 42 * i;
+    ++i;
+  } while (i < 9);
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
+int simple_unroll6() {
+  int a[22];
+  int k = 42;
+  int i = 21;
+  do {
+    a[i] = 42 * i;
+    --i;
+  } while (i > 7);
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
+int simple_no_unroll5() {
+  int a[9];
+  int k = 42;
+  int i = 0;
+  do {
+    a[i] = 42 * i;
+    i += getNum();
+  } while (i < 9);
+  int b = 22 / (k - 42); // expected-warning {{Division by zero}}
+  return 0;
+}
+
+// CHECK: ... Statistics Collected ...
+// CHECK: 10 LoopUnrolling    - The # of times a loop has got completely unrolled