10b57cec5SDimitry Andric //===--- LoopUnrolling.cpp - Unroll loops -----------------------*- C++ -*-===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric ///
90b57cec5SDimitry Andric /// This file contains functions which are used to decide if a loop worth to be
100b57cec5SDimitry Andric /// unrolled. Moreover, these functions manages the stack of loop which is
110b57cec5SDimitry Andric /// tracked by the ProgramState.
120b57cec5SDimitry Andric ///
130b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
140b57cec5SDimitry Andric
150b57cec5SDimitry Andric #include "clang/ASTMatchers/ASTMatchers.h"
160b57cec5SDimitry Andric #include "clang/ASTMatchers/ASTMatchFinder.h"
170b57cec5SDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
180b57cec5SDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
190b57cec5SDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"
20bdd1243dSDimitry Andric #include <optional>
210b57cec5SDimitry Andric
220b57cec5SDimitry Andric using namespace clang;
230b57cec5SDimitry Andric using namespace ento;
240b57cec5SDimitry Andric using namespace clang::ast_matchers;
250b57cec5SDimitry Andric
260b57cec5SDimitry Andric static const int MAXIMUM_STEP_UNROLLED = 128;
270b57cec5SDimitry Andric
28bdd1243dSDimitry Andric namespace {
290b57cec5SDimitry Andric struct LoopState {
300b57cec5SDimitry Andric private:
310b57cec5SDimitry Andric enum Kind { Normal, Unrolled } K;
320b57cec5SDimitry Andric const Stmt *LoopStmt;
330b57cec5SDimitry Andric const LocationContext *LCtx;
340b57cec5SDimitry Andric unsigned maxStep;
LoopState__anonf9f3a38b0111::LoopState350b57cec5SDimitry Andric LoopState(Kind InK, const Stmt *S, const LocationContext *L, unsigned N)
360b57cec5SDimitry Andric : K(InK), LoopStmt(S), LCtx(L), maxStep(N) {}
370b57cec5SDimitry Andric
380b57cec5SDimitry Andric public:
getNormal__anonf9f3a38b0111::LoopState390b57cec5SDimitry Andric static LoopState getNormal(const Stmt *S, const LocationContext *L,
400b57cec5SDimitry Andric unsigned N) {
410b57cec5SDimitry Andric return LoopState(Normal, S, L, N);
420b57cec5SDimitry Andric }
getUnrolled__anonf9f3a38b0111::LoopState430b57cec5SDimitry Andric static LoopState getUnrolled(const Stmt *S, const LocationContext *L,
440b57cec5SDimitry Andric unsigned N) {
450b57cec5SDimitry Andric return LoopState(Unrolled, S, L, N);
460b57cec5SDimitry Andric }
isUnrolled__anonf9f3a38b0111::LoopState470b57cec5SDimitry Andric bool isUnrolled() const { return K == Unrolled; }
getMaxStep__anonf9f3a38b0111::LoopState480b57cec5SDimitry Andric unsigned getMaxStep() const { return maxStep; }
getLoopStmt__anonf9f3a38b0111::LoopState490b57cec5SDimitry Andric const Stmt *getLoopStmt() const { return LoopStmt; }
getLocationContext__anonf9f3a38b0111::LoopState500b57cec5SDimitry Andric const LocationContext *getLocationContext() const { return LCtx; }
operator ==__anonf9f3a38b0111::LoopState510b57cec5SDimitry Andric bool operator==(const LoopState &X) const {
520b57cec5SDimitry Andric return K == X.K && LoopStmt == X.LoopStmt;
530b57cec5SDimitry Andric }
Profile__anonf9f3a38b0111::LoopState540b57cec5SDimitry Andric void Profile(llvm::FoldingSetNodeID &ID) const {
550b57cec5SDimitry Andric ID.AddInteger(K);
560b57cec5SDimitry Andric ID.AddPointer(LoopStmt);
570b57cec5SDimitry Andric ID.AddPointer(LCtx);
580b57cec5SDimitry Andric ID.AddInteger(maxStep);
590b57cec5SDimitry Andric }
600b57cec5SDimitry Andric };
61bdd1243dSDimitry Andric } // namespace
620b57cec5SDimitry Andric
630b57cec5SDimitry Andric // The tracked stack of loops. The stack indicates that which loops the
640b57cec5SDimitry Andric // simulated element contained by. The loops are marked depending if we decided
650b57cec5SDimitry Andric // to unroll them.
660b57cec5SDimitry Andric // TODO: The loop stack should not need to be in the program state since it is
670b57cec5SDimitry Andric // lexical in nature. Instead, the stack of loops should be tracked in the
680b57cec5SDimitry Andric // LocationContext.
690b57cec5SDimitry Andric REGISTER_LIST_WITH_PROGRAMSTATE(LoopStack, LoopState)
700b57cec5SDimitry Andric
710b57cec5SDimitry Andric namespace clang {
720b57cec5SDimitry Andric namespace ento {
730b57cec5SDimitry Andric
isLoopStmt(const Stmt * S)740b57cec5SDimitry Andric static bool isLoopStmt(const Stmt *S) {
75349cc55cSDimitry Andric return isa_and_nonnull<ForStmt, WhileStmt, DoStmt>(S);
760b57cec5SDimitry Andric }
770b57cec5SDimitry Andric
processLoopEnd(const Stmt * LoopStmt,ProgramStateRef State)780b57cec5SDimitry Andric ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) {
790b57cec5SDimitry Andric auto LS = State->get<LoopStack>();
800b57cec5SDimitry Andric if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt)
810b57cec5SDimitry Andric State = State->set<LoopStack>(LS.getTail());
820b57cec5SDimitry Andric return State;
830b57cec5SDimitry Andric }
840b57cec5SDimitry Andric
simpleCondition(StringRef BindName,StringRef RefName)85fe6060f1SDimitry Andric static internal::Matcher<Stmt> simpleCondition(StringRef BindName,
86fe6060f1SDimitry Andric StringRef RefName) {
87fe6060f1SDimitry Andric return binaryOperator(
88fe6060f1SDimitry Andric anyOf(hasOperatorName("<"), hasOperatorName(">"),
890b57cec5SDimitry Andric hasOperatorName("<="), hasOperatorName(">="),
900b57cec5SDimitry Andric hasOperatorName("!=")),
910b57cec5SDimitry Andric hasEitherOperand(ignoringParenImpCasts(
92fe6060f1SDimitry Andric declRefExpr(to(varDecl(hasType(isInteger())).bind(BindName)))
93fe6060f1SDimitry Andric .bind(RefName))),
94fe6060f1SDimitry Andric hasEitherOperand(
95fe6060f1SDimitry Andric ignoringParenImpCasts(integerLiteral().bind("boundNum"))))
960b57cec5SDimitry Andric .bind("conditionOperator");
970b57cec5SDimitry Andric }
980b57cec5SDimitry Andric
990b57cec5SDimitry Andric static internal::Matcher<Stmt>
changeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher)1000b57cec5SDimitry Andric changeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher) {
1010b57cec5SDimitry Andric return anyOf(
1020b57cec5SDimitry Andric unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")),
1030b57cec5SDimitry Andric hasUnaryOperand(ignoringParenImpCasts(
1040b57cec5SDimitry Andric declRefExpr(to(varDecl(VarNodeMatcher)))))),
1050b57cec5SDimitry Andric binaryOperator(isAssignmentOperator(),
1060b57cec5SDimitry Andric hasLHS(ignoringParenImpCasts(
1070b57cec5SDimitry Andric declRefExpr(to(varDecl(VarNodeMatcher)))))));
1080b57cec5SDimitry Andric }
1090b57cec5SDimitry Andric
1100b57cec5SDimitry Andric static internal::Matcher<Stmt>
callByRef(internal::Matcher<Decl> VarNodeMatcher)1110b57cec5SDimitry Andric callByRef(internal::Matcher<Decl> VarNodeMatcher) {
1120b57cec5SDimitry Andric return callExpr(forEachArgumentWithParam(
1130b57cec5SDimitry Andric declRefExpr(to(varDecl(VarNodeMatcher))),
1140b57cec5SDimitry Andric parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))));
1150b57cec5SDimitry Andric }
1160b57cec5SDimitry Andric
1170b57cec5SDimitry Andric static internal::Matcher<Stmt>
assignedToRef(internal::Matcher<Decl> VarNodeMatcher)1180b57cec5SDimitry Andric assignedToRef(internal::Matcher<Decl> VarNodeMatcher) {
1190b57cec5SDimitry Andric return declStmt(hasDescendant(varDecl(
1200b57cec5SDimitry Andric allOf(hasType(referenceType()),
1210b57cec5SDimitry Andric hasInitializer(anyOf(
1220b57cec5SDimitry Andric initListExpr(has(declRefExpr(to(varDecl(VarNodeMatcher))))),
1230b57cec5SDimitry Andric declRefExpr(to(varDecl(VarNodeMatcher)))))))));
1240b57cec5SDimitry Andric }
1250b57cec5SDimitry Andric
1260b57cec5SDimitry Andric static internal::Matcher<Stmt>
getAddrTo(internal::Matcher<Decl> VarNodeMatcher)1270b57cec5SDimitry Andric getAddrTo(internal::Matcher<Decl> VarNodeMatcher) {
1280b57cec5SDimitry Andric return unaryOperator(
1290b57cec5SDimitry Andric hasOperatorName("&"),
1300b57cec5SDimitry Andric hasUnaryOperand(declRefExpr(hasDeclaration(VarNodeMatcher))));
1310b57cec5SDimitry Andric }
1320b57cec5SDimitry Andric
hasSuspiciousStmt(StringRef NodeName)1330b57cec5SDimitry Andric static internal::Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) {
1340b57cec5SDimitry Andric return hasDescendant(stmt(
1350b57cec5SDimitry Andric anyOf(gotoStmt(), switchStmt(), returnStmt(),
1360b57cec5SDimitry Andric // Escaping and not known mutation of the loop counter is handled
1370b57cec5SDimitry Andric // by exclusion of assigning and address-of operators and
1380b57cec5SDimitry Andric // pass-by-ref function calls on the loop counter from the body.
1395ffd83dbSDimitry Andric changeIntBoundNode(equalsBoundNode(std::string(NodeName))),
1405ffd83dbSDimitry Andric callByRef(equalsBoundNode(std::string(NodeName))),
1415ffd83dbSDimitry Andric getAddrTo(equalsBoundNode(std::string(NodeName))),
1425ffd83dbSDimitry Andric assignedToRef(equalsBoundNode(std::string(NodeName))))));
1430b57cec5SDimitry Andric }
1440b57cec5SDimitry Andric
forLoopMatcher()1450b57cec5SDimitry Andric static internal::Matcher<Stmt> forLoopMatcher() {
1460b57cec5SDimitry Andric return forStmt(
147fe6060f1SDimitry Andric hasCondition(simpleCondition("initVarName", "initVarRef")),
1480b57cec5SDimitry Andric // Initialization should match the form: 'int i = 6' or 'i = 42'.
1490b57cec5SDimitry Andric hasLoopInit(
1500b57cec5SDimitry Andric anyOf(declStmt(hasSingleDecl(
1510b57cec5SDimitry Andric varDecl(allOf(hasInitializer(ignoringParenImpCasts(
1520b57cec5SDimitry Andric integerLiteral().bind("initNum"))),
1530b57cec5SDimitry Andric equalsBoundNode("initVarName"))))),
1540b57cec5SDimitry Andric binaryOperator(hasLHS(declRefExpr(to(varDecl(
1550b57cec5SDimitry Andric equalsBoundNode("initVarName"))))),
1560b57cec5SDimitry Andric hasRHS(ignoringParenImpCasts(
1570b57cec5SDimitry Andric integerLiteral().bind("initNum")))))),
1580b57cec5SDimitry Andric // Incrementation should be a simple increment or decrement
1590b57cec5SDimitry Andric // operator call.
1600b57cec5SDimitry Andric hasIncrement(unaryOperator(
1610b57cec5SDimitry Andric anyOf(hasOperatorName("++"), hasOperatorName("--")),
1620b57cec5SDimitry Andric hasUnaryOperand(declRefExpr(
1630b57cec5SDimitry Andric to(varDecl(allOf(equalsBoundNode("initVarName"),
1640b57cec5SDimitry Andric hasType(isInteger())))))))),
165fe6060f1SDimitry Andric unless(hasBody(hasSuspiciousStmt("initVarName"))))
166fe6060f1SDimitry Andric .bind("forLoop");
1670b57cec5SDimitry Andric }
1680b57cec5SDimitry Andric
isCapturedByReference(ExplodedNode * N,const DeclRefExpr * DR)169fe6060f1SDimitry Andric static bool isCapturedByReference(ExplodedNode *N, const DeclRefExpr *DR) {
170fe6060f1SDimitry Andric
171fe6060f1SDimitry Andric // Get the lambda CXXRecordDecl
172fe6060f1SDimitry Andric assert(DR->refersToEnclosingVariableOrCapture());
173fe6060f1SDimitry Andric const LocationContext *LocCtxt = N->getLocationContext();
174fe6060f1SDimitry Andric const Decl *D = LocCtxt->getDecl();
175fe6060f1SDimitry Andric const auto *MD = cast<CXXMethodDecl>(D);
176fe6060f1SDimitry Andric assert(MD && MD->getParent()->isLambda() &&
177fe6060f1SDimitry Andric "Captured variable should only be seen while evaluating a lambda");
178fe6060f1SDimitry Andric const CXXRecordDecl *LambdaCXXRec = MD->getParent();
179fe6060f1SDimitry Andric
180fe6060f1SDimitry Andric // Lookup the fields of the lambda
181bdd1243dSDimitry Andric llvm::DenseMap<const ValueDecl *, FieldDecl *> LambdaCaptureFields;
182fe6060f1SDimitry Andric FieldDecl *LambdaThisCaptureField;
183fe6060f1SDimitry Andric LambdaCXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField);
184fe6060f1SDimitry Andric
185fe6060f1SDimitry Andric // Check if the counter is captured by reference
186fe6060f1SDimitry Andric const VarDecl *VD = cast<VarDecl>(DR->getDecl()->getCanonicalDecl());
187fe6060f1SDimitry Andric assert(VD);
188fe6060f1SDimitry Andric const FieldDecl *FD = LambdaCaptureFields[VD];
189fe6060f1SDimitry Andric assert(FD && "Captured variable without a corresponding field");
190fe6060f1SDimitry Andric return FD->getType()->isReferenceType();
191fe6060f1SDimitry Andric }
192fe6060f1SDimitry Andric
193fe6060f1SDimitry Andric // A loop counter is considered escaped if:
194fe6060f1SDimitry Andric // case 1: It is a global variable.
195fe6060f1SDimitry Andric // case 2: It is a reference parameter or a reference capture.
196fe6060f1SDimitry Andric // case 3: It is assigned to a non-const reference variable or parameter.
197fe6060f1SDimitry Andric // case 4: Has its address taken.
isPossiblyEscaped(ExplodedNode * N,const DeclRefExpr * DR)198fe6060f1SDimitry Andric static bool isPossiblyEscaped(ExplodedNode *N, const DeclRefExpr *DR) {
199fe6060f1SDimitry Andric const VarDecl *VD = cast<VarDecl>(DR->getDecl()->getCanonicalDecl());
200fe6060f1SDimitry Andric assert(VD);
201fe6060f1SDimitry Andric // Case 1:
2020b57cec5SDimitry Andric if (VD->hasGlobalStorage())
2030b57cec5SDimitry Andric return true;
2040b57cec5SDimitry Andric
205fe6060f1SDimitry Andric const bool IsRefParamOrCapture =
206fe6060f1SDimitry Andric isa<ParmVarDecl>(VD) || DR->refersToEnclosingVariableOrCapture();
207fe6060f1SDimitry Andric // Case 2:
208fe6060f1SDimitry Andric if ((DR->refersToEnclosingVariableOrCapture() &&
209fe6060f1SDimitry Andric isCapturedByReference(N, DR)) ||
210fe6060f1SDimitry Andric (IsRefParamOrCapture && VD->getType()->isReferenceType()))
2115ffd83dbSDimitry Andric return true;
2125ffd83dbSDimitry Andric
2130b57cec5SDimitry Andric while (!N->pred_empty()) {
214a7dea167SDimitry Andric // FIXME: getStmtForDiagnostics() does nasty things in order to provide
215a7dea167SDimitry Andric // a valid statement for body farms, do we need this behavior here?
216a7dea167SDimitry Andric const Stmt *S = N->getStmtForDiagnostics();
2170b57cec5SDimitry Andric if (!S) {
2180b57cec5SDimitry Andric N = N->getFirstPred();
2190b57cec5SDimitry Andric continue;
2200b57cec5SDimitry Andric }
2210b57cec5SDimitry Andric
2220b57cec5SDimitry Andric if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) {
2230b57cec5SDimitry Andric for (const Decl *D : DS->decls()) {
2240b57cec5SDimitry Andric // Once we reach the declaration of the VD we can return.
2250b57cec5SDimitry Andric if (D->getCanonicalDecl() == VD)
2260b57cec5SDimitry Andric return false;
2270b57cec5SDimitry Andric }
2280b57cec5SDimitry Andric }
2290b57cec5SDimitry Andric // Check the usage of the pass-by-ref function calls and adress-of operator
2300b57cec5SDimitry Andric // on VD and reference initialized by VD.
2310b57cec5SDimitry Andric ASTContext &ASTCtx =
2320b57cec5SDimitry Andric N->getLocationContext()->getAnalysisDeclContext()->getASTContext();
233fe6060f1SDimitry Andric // Case 3 and 4:
2340b57cec5SDimitry Andric auto Match =
2350b57cec5SDimitry Andric match(stmt(anyOf(callByRef(equalsNode(VD)), getAddrTo(equalsNode(VD)),
2360b57cec5SDimitry Andric assignedToRef(equalsNode(VD)))),
2370b57cec5SDimitry Andric *S, ASTCtx);
2380b57cec5SDimitry Andric if (!Match.empty())
2390b57cec5SDimitry Andric return true;
2400b57cec5SDimitry Andric
2410b57cec5SDimitry Andric N = N->getFirstPred();
2420b57cec5SDimitry Andric }
2435ffd83dbSDimitry Andric
244fe6060f1SDimitry Andric // Reference parameter and reference capture will not be found.
245fe6060f1SDimitry Andric if (IsRefParamOrCapture)
2465ffd83dbSDimitry Andric return false;
2475ffd83dbSDimitry Andric
2480b57cec5SDimitry Andric llvm_unreachable("Reached root without finding the declaration of VD");
2490b57cec5SDimitry Andric }
2500b57cec5SDimitry Andric
shouldCompletelyUnroll(const Stmt * LoopStmt,ASTContext & ASTCtx,ExplodedNode * Pred,unsigned & maxStep)2510b57cec5SDimitry Andric bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
2520b57cec5SDimitry Andric ExplodedNode *Pred, unsigned &maxStep) {
2530b57cec5SDimitry Andric
2540b57cec5SDimitry Andric if (!isLoopStmt(LoopStmt))
2550b57cec5SDimitry Andric return false;
2560b57cec5SDimitry Andric
2570b57cec5SDimitry Andric // TODO: Match the cases where the bound is not a concrete literal but an
2580b57cec5SDimitry Andric // integer with known value
2590b57cec5SDimitry Andric auto Matches = match(forLoopMatcher(), *LoopStmt, ASTCtx);
2600b57cec5SDimitry Andric if (Matches.empty())
2610b57cec5SDimitry Andric return false;
2620b57cec5SDimitry Andric
263fe6060f1SDimitry Andric const auto *CounterVarRef = Matches[0].getNodeAs<DeclRefExpr>("initVarRef");
2640b57cec5SDimitry Andric llvm::APInt BoundNum =
2650b57cec5SDimitry Andric Matches[0].getNodeAs<IntegerLiteral>("boundNum")->getValue();
2660b57cec5SDimitry Andric llvm::APInt InitNum =
2670b57cec5SDimitry Andric Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue();
2680b57cec5SDimitry Andric auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator");
2690b57cec5SDimitry Andric if (InitNum.getBitWidth() != BoundNum.getBitWidth()) {
27081ad6265SDimitry Andric InitNum = InitNum.zext(BoundNum.getBitWidth());
27181ad6265SDimitry Andric BoundNum = BoundNum.zext(InitNum.getBitWidth());
2720b57cec5SDimitry Andric }
2730b57cec5SDimitry Andric
2740b57cec5SDimitry Andric if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE)
2750b57cec5SDimitry Andric maxStep = (BoundNum - InitNum + 1).abs().getZExtValue();
2760b57cec5SDimitry Andric else
2770b57cec5SDimitry Andric maxStep = (BoundNum - InitNum).abs().getZExtValue();
2780b57cec5SDimitry Andric
2790b57cec5SDimitry Andric // Check if the counter of the loop is not escaped before.
280fe6060f1SDimitry Andric return !isPossiblyEscaped(Pred, CounterVarRef);
2810b57cec5SDimitry Andric }
2820b57cec5SDimitry Andric
madeNewBranch(ExplodedNode * N,const Stmt * LoopStmt)2830b57cec5SDimitry Andric bool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt) {
2840b57cec5SDimitry Andric const Stmt *S = nullptr;
2850b57cec5SDimitry Andric while (!N->pred_empty()) {
2860b57cec5SDimitry Andric if (N->succ_size() > 1)
2870b57cec5SDimitry Andric return true;
2880b57cec5SDimitry Andric
2890b57cec5SDimitry Andric ProgramPoint P = N->getLocation();
290bdd1243dSDimitry Andric if (std::optional<BlockEntrance> BE = P.getAs<BlockEntrance>())
2910b57cec5SDimitry Andric S = BE->getBlock()->getTerminatorStmt();
2920b57cec5SDimitry Andric
2930b57cec5SDimitry Andric if (S == LoopStmt)
2940b57cec5SDimitry Andric return false;
2950b57cec5SDimitry Andric
2960b57cec5SDimitry Andric N = N->getFirstPred();
2970b57cec5SDimitry Andric }
2980b57cec5SDimitry Andric
2990b57cec5SDimitry Andric llvm_unreachable("Reached root without encountering the previous step");
3000b57cec5SDimitry Andric }
3010b57cec5SDimitry Andric
3020b57cec5SDimitry Andric // updateLoopStack is called on every basic block, therefore it needs to be fast
updateLoopStack(const Stmt * LoopStmt,ASTContext & ASTCtx,ExplodedNode * Pred,unsigned maxVisitOnPath)3030b57cec5SDimitry Andric ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx,
3040b57cec5SDimitry Andric ExplodedNode *Pred, unsigned maxVisitOnPath) {
3050b57cec5SDimitry Andric auto State = Pred->getState();
3060b57cec5SDimitry Andric auto LCtx = Pred->getLocationContext();
3070b57cec5SDimitry Andric
3080b57cec5SDimitry Andric if (!isLoopStmt(LoopStmt))
3090b57cec5SDimitry Andric return State;
3100b57cec5SDimitry Andric
3110b57cec5SDimitry Andric auto LS = State->get<LoopStack>();
3120b57cec5SDimitry Andric if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() &&
3130b57cec5SDimitry Andric LCtx == LS.getHead().getLocationContext()) {
3140b57cec5SDimitry Andric if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) {
3150b57cec5SDimitry Andric State = State->set<LoopStack>(LS.getTail());
3160b57cec5SDimitry Andric State = State->add<LoopStack>(
3170b57cec5SDimitry Andric LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
3180b57cec5SDimitry Andric }
3190b57cec5SDimitry Andric return State;
3200b57cec5SDimitry Andric }
3210b57cec5SDimitry Andric unsigned maxStep;
3220b57cec5SDimitry Andric if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred, maxStep)) {
3230b57cec5SDimitry Andric State = State->add<LoopStack>(
3240b57cec5SDimitry Andric LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
3250b57cec5SDimitry Andric return State;
3260b57cec5SDimitry Andric }
3270b57cec5SDimitry Andric
3280b57cec5SDimitry Andric unsigned outerStep = (LS.isEmpty() ? 1 : LS.getHead().getMaxStep());
3290b57cec5SDimitry Andric
3300b57cec5SDimitry Andric unsigned innerMaxStep = maxStep * outerStep;
3310b57cec5SDimitry Andric if (innerMaxStep > MAXIMUM_STEP_UNROLLED)
3320b57cec5SDimitry Andric State = State->add<LoopStack>(
3330b57cec5SDimitry Andric LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
3340b57cec5SDimitry Andric else
3350b57cec5SDimitry Andric State = State->add<LoopStack>(
3360b57cec5SDimitry Andric LoopState::getUnrolled(LoopStmt, LCtx, innerMaxStep));
3370b57cec5SDimitry Andric return State;
3380b57cec5SDimitry Andric }
3390b57cec5SDimitry Andric
isUnrolledState(ProgramStateRef State)3400b57cec5SDimitry Andric bool isUnrolledState(ProgramStateRef State) {
3410b57cec5SDimitry Andric auto LS = State->get<LoopStack>();
3420b57cec5SDimitry Andric if (LS.isEmpty() || !LS.getHead().isUnrolled())
3430b57cec5SDimitry Andric return false;
3440b57cec5SDimitry Andric return true;
3450b57cec5SDimitry Andric }
3460b57cec5SDimitry Andric }
3470b57cec5SDimitry Andric }
348