[StaticAnalyzer] LoopUnrolling: Track a LoopStack in order to completely unroll specific loops

[szepet]

Summary

The LoopExit CFG information provides the opportunity to not mark the loops but having a stack which tracks if a loop is unrolled or not. So in case of simulating a loop we just add it and the information if it meets the requirements to be unrolled to the top of the stack.

[szepet]

Update to fit to the trunk.
All tests passed. Only marking loops as unrolled (1) and not unrolled (0). Keep track of 2 stack in the ProgramState (1 for the loopstmt, 1 for the mark if its unrolled or not).

[NoQ]

Woohoo, looks much nicer and cleaner :3

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

10–12 ↗

(On Diff #108337)

This is already getting a bit outdated (we're no longer marking blocks). But generally having these comments is great, we need to make a new one.

30 ↗

(On Diff #108337)

Hmm, what was wrong with the regular unsigned int?

142 ↗

(On Diff #108337)

Is this the only reason why we need UnrolledLoopStack? How does this interact with possible recursion?

[dcoughlin]

This looks a lot more clean and is likely to be a lot faster! I think it is really important to document this new functionality. I realize we haven't always done a good job of this, but I'd like to document everything we add to Core so that folks who are new to the project can get up to speed by reading the source code.

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

27 ↗

(On Diff #108337)

Since these are designed to be exposed to other translation units, I think it would be a good idea to add doxygen comments describing what they do.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

30 ↗

(On Diff #108337)

Can you add comments describing what these program state elements track? This will help future maintainers understand their purpose.

31 ↗

(On Diff #108337)

Also, it would be good to add a TODO indicating that the unrolled loop stack should not need to be in the program state since it is lexical in nature. Instead, the stack of loops should be tracked in the location context.

145 ↗

(On Diff #108337)

Super tiny nit: Missing space here.

[szepet]

• Descriptions updated.
• The structure of LoopStack made more clear and recursion bug fixed by storing LocationContext.
• other updates and TODOs added based on comments.

[dcoughlin]

Looks good to me. I requested an additional comment (sorry for not doing that before!) and I think you need to extend Profile() to handle the LocationContext.

lib/StaticAnalyzer/Core/LoopUnrolling.cpp

35 ↗

(On Diff #110985)

I don't see a way around it without additional core work, but it is not ideal that this checker keeps a stack of LoopStates each of which contains a LocationContext (which is itself a stack).

53 ↗

(On Diff #110985)

Should the Profile be updated to include the LCtx?

215 ↗

(On Diff #110985)

Can you add a comment here stating that updateLoopStack() is called on every basic block and so needs to be fast?

cfe/trunk/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 them.
+/// which loops should be completely unrolled and mark their corresponding
+/// CFGBlocks. It is done by tracking a stack of loops in the ProgramState. This
+/// way specific loops can be marked as completely unrolled. For considering a
+/// loop to be completely unrolled it has to fulfill the following requirements:
+/// - Currently only forStmts can be considered.
+/// - The bound has to be known.
+/// - The counter variable has not escaped before/in the body of the loop and
+///   changed only in the increment statement corresponding to the loop. It also
+///   has to be initialized by a literal in the corresponding initStmt.
+/// - Does not contain goto, switch and returnStmt.
+///
 ///
 //===----------------------------------------------------------------------===//
 
 #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"
-
 namespace clang {
 namespace ento {
 class AnalysisManager;
 
-ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State,
-                                   const FunctionDecl *FD);
-bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Pred,
-                         AnalysisManager &AMgr);
-bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
-                            ExplodedNode *Pred);
+/// Returns if the given State indicates that is inside a completely unrolled
+/// loop.
+bool isUnrolledState(ProgramStateRef State);
+
+/// Updates the stack of loops contained by the ProgramState.
+ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx,
+                                ExplodedNode* Pred);
 
+/// Updates the given ProgramState. In current implementation it removes the top
+/// element of the stack of loops.
+ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State);
+
 } // end namespace ento
 } // end namespace clang
 
 #endif

cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp

 
 void ExprEngine::ProcessLoopExit(const Stmt* S, ExplodedNode *Pred) {
   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
                                 S->getLocStart(),
                                 "Error evaluating end of the loop");
   ExplodedNodeSet Dst;
   Dst.Add(Pred);
   NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
+  ProgramStateRef NewState = Pred->getState();
 
-  LoopExit PP(S, Pred->getLocationContext());
-  Bldr.generateNode(PP, Pred->getState(), Pred);
+  if(AMgr.options.shouldUnrollLoops())
+    NewState = processLoopEnd(S, NewState);
 
+  LoopExit PP(S, Pred->getLocationContext());
+  Bldr.generateNode(PP, NewState, Pred);
   // Enqueue the new nodes onto the work list.
   Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
 }
 
 void ExprEngine::ProcessInitializer(const CFGInitializer Init,
                                     ExplodedNode *Pred) {
   const CXXCtorInitializer *BMI = Init.getInitializer();
 

 
 /// Block entrance.  (Update counters).
 void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
                                          NodeBuilderWithSinks &nodeBuilder,
                                          ExplodedNode *Pred) {
   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
   // If we reach 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(), Pred)) {
-      ProgramStateRef UnrolledState = markLoopAsUnrolled(
-              Term, Pred->getState(),
-              cast<FunctionDecl>(Pred->getStackFrame()->getDecl()));
-      if (UnrolledState != Pred->getState())
-        nodeBuilder.generateNode(UnrolledState, Pred);
-      return;
+  if(AMgr.options.shouldUnrollLoops()) {
+    const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator();
+    if (Term) {
+      ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(),
+                                                 Pred);
+      if (NewState != Pred->getState()){
+        Pred = nodeBuilder.generateNode(NewState, Pred);
       }
-
-    if (ActualBlock->empty())
-      return;
-
-    if (isUnrolledLoopBlock(ActualBlock, Pred, AMgr))
+    }
+    // Is we are inside an unrolled loop then no need the check the counters.
+    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()) {

cfe/trunk/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 loops which are unrolled
-/// and store them in ProgramState. During the analysis we check the analyzed
-/// blocks if they are part of an unrolled loop or reached from one.
+/// unrolled. Moreover, these functions manages the stack of loop which is
+/// tracked by the 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/CheckerContext.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"
+struct LoopState {
+private:
+  enum Kind { Normal, Unrolled } K;
+  const Stmt *LoopStmt;
+  const LocationContext *LCtx;
+  LoopState(Kind InK, const Stmt *S, const LocationContext *L)
+      : K(InK), LoopStmt(S), LCtx(L) {}
 
-STATISTIC(NumTimesLoopUnrolled,
-          "The # of times a loop has got completely unrolled");
+public:
+  static LoopState getNormal(const Stmt *S, const LocationContext *L) {
+    return LoopState(Normal, S, L);
+  }
+  static LoopState getUnrolled(const Stmt *S, const LocationContext *L) {
+    return LoopState(Unrolled, S, L);
+  }
+  bool isUnrolled() const { return K == Unrolled; }
+  const Stmt *getLoopStmt() const { return LoopStmt; }
+  const LocationContext *getLocationContext() const { return LCtx; }
+  bool operator==(const LoopState &X) const {
+    return K == X.K && LoopStmt == X.LoopStmt;
+  }
+  void Profile(llvm::FoldingSetNodeID &ID) const {
+    ID.AddInteger(K);
+    ID.AddPointer(LoopStmt);
+    ID.AddPointer(LCtx);
+  }
+};
 
-REGISTER_MAP_WITH_PROGRAMSTATE(UnrolledLoops, const Stmt *,
-                               const FunctionDecl *)
+// The tracked stack of loops. The stack indicates that which loops the
+// simulated element contained by. The loops are marked depending if we decided
+// to unroll them.
+// TODO: The loop stack should not need to be in the program state since it is
+// lexical in nature. Instead, the stack of loops should be tracked in the
+// LocationContext.
+REGISTER_LIST_WITH_PROGRAMSTATE(LoopStack, LoopState)
 
 namespace clang {
 namespace ento {
 
 static bool isLoopStmt(const Stmt *S) {
   return S && (isa<ForStmt>(S) || isa<WhileStmt>(S) || isa<DoStmt>(S));
 }
 
+ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) {
+  auto LS = State->get<LoopStack>();
+  assert(!LS.isEmpty() && "Loop not added to the stack.");
+  assert(LoopStmt == LS.getHead().getLoopStmt() &&
+         "Loop is not on top of the stack.");
+
+  State = State->set<LoopStack>(LS.getTail());
+  return State;
+}
+
 static internal::Matcher<Stmt> simpleCondition(StringRef BindName) {
   return binaryOperator(
       anyOf(hasOperatorName("<"), hasOperatorName(">"), hasOperatorName("<="),
             hasOperatorName(">="), hasOperatorName("!=")),
       hasEitherOperand(ignoringParenImpCasts(
           declRefExpr(to(varDecl(hasType(isInteger())).bind(BindName))))),
       hasEitherOperand(ignoringParenImpCasts(integerLiteral())));
 }

 getAddrTo(internal::Matcher<Decl> VarNodeMatcher) {
   return unaryOperator(
       hasOperatorName("&"),
       hasUnaryOperand(declRefExpr(hasDeclaration(VarNodeMatcher))));
 }
 
 static internal::Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) {
   return hasDescendant(stmt(
-      anyOf(gotoStmt(), switchStmt(),
+      anyOf(gotoStmt(), switchStmt(), returnStmt(),
             // 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.
             changeIntBoundNode(equalsBoundNode(NodeName)),
             callByRef(equalsBoundNode(NodeName)),
             getAddrTo(equalsBoundNode(NodeName)),
             assignedToRef(equalsBoundNode(NodeName)))));
 }
if (Matches.empty())
     return false;
 
   auto CounterVar = Matches[0].getNodeAs<VarDecl>("initVarName");
 
   // Check if the counter of the loop is not escaped before.
   return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred);
 }
 
-namespace {
-class LoopBlockVisitor : public ConstStmtVisitor<LoopBlockVisitor> {
-public:
-  LoopBlockVisitor(llvm::SmallPtrSet<const CFGBlock *, 8> &BS) : BlockSet(BS) {}
+// updateLoopStack is called on every basic block, therefore it needs to be fast
+ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx,
+                                ExplodedNode* Pred) {
+  auto State = Pred->getState();
+  auto LCtx = Pred->getLocationContext();
 
-  void VisitChildren(const Stmt *S) {
-    for (const Stmt *Child : S->children())
-      if (Child)
-        Visit(Child);
-  }
-
-  void VisitStmt(const Stmt *S) {
-    // In case of nested loops we only unroll the inner loop if it's marked too.
-    if (!S || (isLoopStmt(S) && S != LoopStmt))
-      return;
-    BlockSet.insert(StmtToBlockMap->getBlock(S));
-    VisitChildren(S);
-  }
-
-  void setBlocksOfLoop(const Stmt *Loop, const CFGStmtMap *M) {
-    BlockSet.clear();
-    StmtToBlockMap = M;
-    LoopStmt = Loop;
-    Visit(LoopStmt);
-  }
+  if (!isLoopStmt(LoopStmt))
+    return State;
 
-private:
-  llvm::SmallPtrSet<const CFGBlock *, 8> &BlockSet;
-  const CFGStmtMap *StmtToBlockMap;
-  const Stmt *LoopStmt;
-};
-}
-// TODO: refactor this function using LoopExit CFG element - once we have the
-// information when the simulation reaches the end of the loop we can cleanup
-// the state
-bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Pred,
-                         AnalysisManager &AMgr) {
-  const Stmt *Term = Block->getTerminator();
-  auto State = Pred->getState();
-  // In case of nested loops in an inlined function should not be unrolled only
-  // if the inner loop is marked.
-  if (Term && isLoopStmt(Term) && !State->contains<UnrolledLoops>(Term))
-    return false;
+  auto LS = State->get<LoopStack>();
+  if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() &&
+      LCtx == LS.getHead().getLocationContext())
+    return State;
 
-  const CFGBlock *SearchedBlock;
-  llvm::SmallPtrSet<const CFGBlock *, 8> BlockSet;
-  LoopBlockVisitor LBV(BlockSet);
-  // Check the CFGBlocks of every marked loop.
-  for (auto &E : State->get<UnrolledLoops>()) {
-    SearchedBlock = Block;
-    const StackFrameContext *StackFrame = Pred->getStackFrame();
-    ParentMap PM(E.second->getBody());
-    CFGStmtMap *M = CFGStmtMap::Build(AMgr.getCFG(E.second), &PM);
-    LBV.setBlocksOfLoop(E.first, M);
-    // In case of an inlined function call check if any of its callSiteBlock is
-    // marked.
-    while (BlockSet.find(SearchedBlock) == BlockSet.end() && StackFrame) {
-      SearchedBlock = StackFrame->getCallSiteBlock();
-      if (!SearchedBlock || StackFrame->inTopFrame())
-        break;
-      StackFrame = StackFrame->getParent()->getCurrentStackFrame();
-    }
-    delete M;
-    if (SearchedBlock)
-      return true;
-  }
-  return false;
+  if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred)) {
+    State = State->add<LoopStack>(LoopState::getNormal(LoopStmt, LCtx));
+    return State;
   }
 
-ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State,
-                                   const FunctionDecl *FD) {
-  if (State->contains<UnrolledLoops>(Term))
-    return State;
+  State = State->add<LoopStack>(LoopState::getUnrolled(LoopStmt, LCtx));
+}
 
-  State = State->set<UnrolledLoops>(Term, FD);
-  ++NumTimesLoopUnrolled;
-  return State;
+bool isUnrolledState(ProgramStateRef State) {
+  auto LS = State->get<LoopStack>();
+  if (LS.isEmpty() || !LS.getHead().isUnrolled())
+    return false;
+  return true;
 }
 }
 }

cfe/trunk/test/Analysis/loop-unrolling.cpp

-// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-max-loop 4 -analyzer-config unroll-loops=true -verify -std=c++11 %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true,cfg-loopexit=true -verify -std=c++11 %s
 
 void clang_analyzer_numTimesReached();
 
 int getNum();
 void foo(int &);
 // Testing for loops.
 int simple_unroll1() {
   int a[9];
int nested_inlined_no_unroll1() {
   int k;
   for (int i = 0; i < 9; i++) {
     clang_analyzer_numTimesReached(); // expected-warning {{26}}
     k = simple_unknown_bound_loop();  // reevaluation without inlining
   }
   int a = 22 / k; // no-warning
   return 0;
 }
+
+
+int recursion_unroll1(bool b) {
+  int k = 2;
+  for (int i = 0; i < 5; i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{14}}
+    if(i == 0 && b)
+      recursion_unroll1(false);
+    clang_analyzer_numTimesReached(); // expected-warning {{15}}
+  }
+  int a = 22 / k; // no-warning
+  return 0;
+}
+
+int recursion_unroll2(bool b) {
+  int k = 0;
+  for (int i = 0; i < 5; i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{10}}
+    if(i == 0 && b)
+      recursion_unroll2(false);
+    clang_analyzer_numTimesReached(); // expected-warning {{10}}
+  }
+  int a = 22 / k; // expected-warning {{Division by zero}}
+  return 0;
+}
+
+int recursion_unroll3(bool b) {
+  int k = 2;
+  for (int i = 0; i < 5; i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{10}}
+    if(i == 4 && b) {
+      recursion_unroll3(false);
+      break;
+    }
+    clang_analyzer_numTimesReached(); // expected-warning {{10}}
+  }
+  int a = 22 / k;
+  return 0;
+}
+
+int recursion_unroll4(bool b) {
+  int k = 2;
+  for (int i = 0; i < 5; i++) {
+    clang_analyzer_numTimesReached(); // expected-warning {{14}}
+    if(i == 0 && b) {
+      recursion_unroll4(false);
+      continue;
+    }
+    clang_analyzer_numTimesReached(); // expected-warning {{14}}
+  }
+  int a = 22 / k;
+  return 0;
+}