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

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.

Differential Revision: https://reviews.llvm.org/D35684

llvm-svn: 311346

1 files changed, 67 insertions, 79 deletions

diff --git a/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp b/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp
index df5d7925429..d9a31ef3eb4 100644
--- a/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp
+++ b/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp
@@ -8,9 +8,8 @@
 //===----------------------------------------------------------------------===//
 ///
 /// 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.
 ///
 //===----------------------------------------------------------------------===//
 
@@ -28,13 +27,41 @@ 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 {
@@ -43,6 +70,16 @@ 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("<="),
@@ -90,7 +127,7 @@ getAddrTo(internal::Matcher<Decl> 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.
@@ -174,83 +211,34 @@ bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
   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);
-  }
+  if (!isLoopStmt(LoopStmt))
+    return State;
 
-  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);
-  }
+  auto LS = State->get<LoopStack>();
+  if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() &&
+      LCtx == LS.getHead().getLocationContext())
+    return State;
 
-  void setBlocksOfLoop(const Stmt *Loop, const CFGStmtMap *M) {
-    BlockSet.clear();
-    StmtToBlockMap = M;
-    LoopStmt = Loop;
-    Visit(LoopStmt);
+  if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred)) {
+    State = State->add<LoopStack>(LoopState::getNormal(LoopStmt, LCtx));
+    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;
-
-  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;
+  State = State->add<LoopStack>(LoopState::getUnrolled(LoopStmt, LCtx));
+  return State;
 }
 
-ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State,
-                                   const FunctionDecl *FD) {
-  if (State->contains<UnrolledLoops>(Term))
-    return State;
-
-  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;
 }
 }
 }