llvm/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp

//===--- LoopUnrolling.cpp - Unroll loops -----------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// This file contains functions which are used to decide if a loop worth to be
/// unrolled. Moreover, these functions manages the stack of loop which is
/// tracked by the ProgramState.
///
//===----------------------------------------------------------------------===//

#include "clang/ASTMatchers/ASTMatchers.h"
#include "clang/ASTMatchers/ASTMatchFinder.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"
#include <optional>

usingnamespaceclang;
usingnamespaceento;
usingnamespaceclang::ast_matchers;

static const int MAXIMUM_STEP_UNROLLED = …;

namespace {
struct LoopState { … };
} // namespace

// 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(…)

namespace clang {
namespace ento {

static bool isLoopStmt(const Stmt *S) { … }

ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) { … }

static internal::Matcher<Stmt> simpleCondition(StringRef BindName,
                                               StringRef RefName) { … }

static internal::Matcher<Stmt>
changeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher) { … }

static internal::Matcher<Stmt>
callByRef(internal::Matcher<Decl> VarNodeMatcher) { … }

static internal::Matcher<Stmt>
assignedToRef(internal::Matcher<Decl> VarNodeMatcher) { … }

static internal::Matcher<Stmt>
getAddrTo(internal::Matcher<Decl> VarNodeMatcher) { … }

static internal::Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) { … }

static internal::Matcher<Stmt> forLoopMatcher() { … }

static bool isCapturedByReference(ExplodedNode *N, const DeclRefExpr *DR) { … }

static bool isFoundInStmt(const Stmt *S, const VarDecl *VD) { … }

// A loop counter is considered escaped if:
// case 1: It is a global variable.
// case 2: It is a reference parameter or a reference capture.
// case 3: It is assigned to a non-const reference variable or parameter.
// case 4: Has its address taken.
static bool isPossiblyEscaped(ExplodedNode *N, const DeclRefExpr *DR) { … }

static bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
                                   ExplodedNode *Pred, unsigned &maxStep) { … }

static bool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt) { … }

// updateLoopStack is called on every basic block, therefore it needs to be fast
ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx,
                                ExplodedNode *Pred, unsigned maxVisitOnPath) { … }

bool isUnrolledState(ProgramStateRef State) { … }
}
}