| //===--- 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> | |
| using namespace clang; | |
| using namespace ento; | |
| using namespace clang::ast_matchers; | |
| using ast_matchers::internal::Matcher; | |
| static const int MAXIMUM_STEP_UNROLLED = 128; | |
| namespace { | |
| struct LoopState { | |
| private: | |
| enum Kind { Normal, Unrolled } K; | |
| const Stmt *LoopStmt; | |
| const LocationContext *LCtx; | |
| unsigned maxStep; | |
| LoopState(Kind InK, const Stmt *S, const LocationContext *L, unsigned N) | |
| : K(InK), LoopStmt(S), LCtx(L), maxStep(N) {} | |
| public: | |
| static LoopState getNormal(const Stmt *S, const LocationContext *L, | |
| unsigned N) { | |
| return LoopState(Normal, S, L, N); | |
| } | |
| static LoopState getUnrolled(const Stmt *S, const LocationContext *L, | |
| unsigned N) { | |
| return LoopState(Unrolled, S, L, N); | |
| } | |
| bool isUnrolled() const { return K == Unrolled; } | |
| unsigned getMaxStep() const { return maxStep; } | |
| 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); | |
| ID.AddInteger(maxStep); | |
| } | |
| }; | |
| } // 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(LoopStack, LoopState) | |
| namespace clang { | |
| namespace { | |
| AST_MATCHER(QualType, isIntegralOrEnumerationType) { | |
| return Node->isIntegralOrEnumerationType(); | |
| } | |
| } // namespace | |
| namespace ento { | |
| static bool isLoopStmt(const Stmt *S) { | |
| return isa_and_nonnull<ForStmt, WhileStmt, DoStmt>(S); | |
| } | |
| ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) { | |
| auto LS = State->get<LoopStack>(); | |
| if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt) | |
| State = State->set<LoopStack>(LS.getTail()); | |
| return State; | |
| } | |
| static Matcher<Stmt> simpleCondition(StringRef BindName, StringRef RefName) { | |
| auto LoopVariable = ignoringParenImpCasts( | |
| declRefExpr(to(varDecl(hasType(isInteger())).bind(BindName))) | |
| .bind(RefName)); | |
| auto UpperBound = ignoringParenImpCasts( | |
| expr(hasType(isIntegralOrEnumerationType())).bind("boundNum")); | |
| return binaryOperator( | |
| anyOf(hasOperatorName("<"), hasOperatorName(">"), | |
| hasOperatorName("<="), hasOperatorName(">="), | |
| hasOperatorName("!=")), | |
| anyOf(binaryOperator(hasLHS(LoopVariable), hasRHS(UpperBound)), | |
| binaryOperator(hasRHS(LoopVariable), hasLHS(UpperBound)))) | |
| .bind("conditionOperator"); | |
| } | |
| static Matcher<Stmt> changeIntBoundNode(Matcher<Decl> VarNodeMatcher) { | |
| return anyOf( | |
| unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")), | |
| hasUnaryOperand(ignoringParenImpCasts( | |
| declRefExpr(to(varDecl(VarNodeMatcher)))))), | |
| binaryOperator(isAssignmentOperator(), | |
| hasLHS(ignoringParenImpCasts( | |
| declRefExpr(to(varDecl(VarNodeMatcher))))))); | |
| } | |
| static Matcher<Stmt> callByRef(Matcher<Decl> VarNodeMatcher) { | |
| return callExpr(forEachArgumentWithParam( | |
| declRefExpr(to(varDecl(VarNodeMatcher))), | |
| parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))); | |
| } | |
| static Matcher<Stmt> assignedToRef(Matcher<Decl> VarNodeMatcher) { | |
| return declStmt(hasDescendant(varDecl( | |
| allOf(hasType(referenceType()), | |
| hasInitializer(anyOf( | |
| initListExpr(has(declRefExpr(to(varDecl(VarNodeMatcher))))), | |
| declRefExpr(to(varDecl(VarNodeMatcher))))))))); | |
| } | |
| static Matcher<Stmt> getAddrTo(Matcher<Decl> VarNodeMatcher) { | |
| return unaryOperator( | |
| hasOperatorName("&"), | |
| hasUnaryOperand(declRefExpr(hasDeclaration(VarNodeMatcher)))); | |
| } | |
| static Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) { | |
| return hasDescendant(stmt( | |
| 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(std::string(NodeName))), | |
| callByRef(equalsBoundNode(std::string(NodeName))), | |
| getAddrTo(equalsBoundNode(std::string(NodeName))), | |
| assignedToRef(equalsBoundNode(std::string(NodeName)))))); | |
| } | |
| static Matcher<Stmt> forLoopMatcher() { | |
| return forStmt( | |
| hasCondition(simpleCondition("initVarName", "initVarRef")), | |
| // Initialization should match the form: 'int i = 6' or 'i = 42'. | |
| hasLoopInit( | |
| anyOf(declStmt(hasSingleDecl( | |
| varDecl(allOf(hasInitializer(ignoringParenImpCasts( | |
| integerLiteral().bind("initNum"))), | |
| equalsBoundNode("initVarName"))))), | |
| binaryOperator(hasLHS(declRefExpr(to(varDecl( | |
| equalsBoundNode("initVarName"))))), | |
| hasRHS(ignoringParenImpCasts( | |
| integerLiteral().bind("initNum")))))), | |
| // Incrementation should be a simple increment or decrement | |
| // operator call. | |
| hasIncrement(unaryOperator( | |
| anyOf(hasOperatorName("++"), hasOperatorName("--")), | |
| hasUnaryOperand(declRefExpr( | |
| to(varDecl(allOf(equalsBoundNode("initVarName"), | |
| hasType(isInteger())))))))), | |
| unless(hasBody(hasSuspiciousStmt("initVarName")))) | |
| .bind("forLoop"); | |
| } | |
| static bool isCapturedByReference(ExplodedNode *N, const DeclRefExpr *DR) { | |
| // Get the lambda CXXRecordDecl | |
| assert(DR->refersToEnclosingVariableOrCapture()); | |
| const LocationContext *LocCtxt = N->getLocationContext(); | |
| const Decl *D = LocCtxt->getDecl(); | |
| const auto *MD = cast<CXXMethodDecl>(D); | |
| assert(MD && MD->getParent()->isLambda() && | |
| "Captured variable should only be seen while evaluating a lambda"); | |
| const CXXRecordDecl *LambdaCXXRec = MD->getParent(); | |
| // Lookup the fields of the lambda | |
| llvm::DenseMap<const ValueDecl *, FieldDecl *> LambdaCaptureFields; | |
| FieldDecl *LambdaThisCaptureField; | |
| LambdaCXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField); | |
| // Check if the counter is captured by reference | |
| const VarDecl *VD = cast<VarDecl>(DR->getDecl()->getCanonicalDecl()); | |
| assert(VD); | |
| const FieldDecl *FD = LambdaCaptureFields[VD]; | |
| assert(FD && "Captured variable without a corresponding field"); | |
| return FD->getType()->isReferenceType(); | |
| } | |
| static bool isFoundInStmt(const Stmt *S, const VarDecl *VD) { | |
| if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) { | |
| for (const Decl *D : DS->decls()) { | |
| // Once we reach the declaration of the VD we can return. | |
| if (D->getCanonicalDecl() == VD) | |
| return true; | |
| } | |
| } | |
| return false; | |
| } | |
| // 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) { | |
| const VarDecl *VD = cast<VarDecl>(DR->getDecl()->getCanonicalDecl()); | |
| assert(VD); | |
| // Case 1: | |
| if (VD->hasGlobalStorage()) | |
| return true; | |
| const bool IsRefParamOrCapture = | |
| isa<ParmVarDecl>(VD) || DR->refersToEnclosingVariableOrCapture(); | |
| // Case 2: | |
| if ((DR->refersToEnclosingVariableOrCapture() && | |
| isCapturedByReference(N, DR)) || | |
| (IsRefParamOrCapture && VD->getType()->isReferenceType())) | |
| return true; | |
| while (!N->pred_empty()) { | |
| // FIXME: getStmtForDiagnostics() does nasty things in order to provide | |
| // a valid statement for body farms, do we need this behavior here? | |
| const Stmt *S = N->getStmtForDiagnostics(); | |
| if (!S) { | |
| N = N->getFirstPred(); | |
| continue; | |
| } | |
| if (isFoundInStmt(S, VD)) { | |
| return false; | |
| } | |
| if (const auto *SS = dyn_cast<SwitchStmt>(S)) { | |
| if (const auto *CST = dyn_cast<CompoundStmt>(SS->getBody())) { | |
| for (const Stmt *CB : CST->body()) { | |
| if (isFoundInStmt(CB, VD)) | |
| return false; | |
| } | |
| } | |
| } | |
| // Check the usage of the pass-by-ref function calls and adress-of operator | |
| // on VD and reference initialized by VD. | |
| ASTContext &ASTCtx = | |
| N->getLocationContext()->getAnalysisDeclContext()->getASTContext(); | |
| // Case 3 and 4: | |
| auto Match = | |
| match(stmt(anyOf(callByRef(equalsNode(VD)), getAddrTo(equalsNode(VD)), | |
| assignedToRef(equalsNode(VD)))), | |
| *S, ASTCtx); | |
| if (!Match.empty()) | |
| return true; | |
| N = N->getFirstPred(); | |
| } | |
| // Reference parameter and reference capture will not be found. | |
| if (IsRefParamOrCapture) | |
| return false; | |
| llvm_unreachable("Reached root without finding the declaration of VD"); | |
| } | |
| static bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, | |
| ExplodedNode *Pred, unsigned &maxStep) { | |
| if (!isLoopStmt(LoopStmt)) | |
| return false; | |
| auto Matches = match(forLoopMatcher(), *LoopStmt, ASTCtx); | |
| if (Matches.empty()) | |
| return false; | |
| const auto *CounterVarRef = Matches[0].getNodeAs<DeclRefExpr>("initVarRef"); | |
| const Expr *BoundNumExpr = Matches[0].getNodeAs<Expr>("boundNum"); | |
| Expr::EvalResult BoundNumResult; | |
| if (!BoundNumExpr || !BoundNumExpr->EvaluateAsInt(BoundNumResult, ASTCtx, | |
| Expr::SE_NoSideEffects)) { | |
| return false; | |
| } | |
| llvm::APInt InitNum = | |
| Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue(); | |
| auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator"); | |
| unsigned MaxWidth = std::max(InitNum.getBitWidth(), | |
| BoundNumResult.Val.getInt().getBitWidth()); | |
| InitNum = InitNum.zext(MaxWidth); | |
| llvm::APInt BoundNum = BoundNumResult.Val.getInt().zext(MaxWidth); | |
| if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE) | |
| maxStep = (BoundNum - InitNum + 1).abs().getZExtValue(); | |
| else | |
| maxStep = (BoundNum - InitNum).abs().getZExtValue(); | |
| // Check if the counter of the loop is not escaped before. | |
| return !isPossiblyEscaped(Pred, CounterVarRef); | |
| } | |
| static bool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt) { | |
| const Stmt *S = nullptr; | |
| while (!N->pred_empty()) { | |
| if (N->succ_size() > 1) | |
| return true; | |
| ProgramPoint P = N->getLocation(); | |
| if (std::optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) | |
| S = BE->getBlock()->getTerminatorStmt(); | |
| if (S == LoopStmt) | |
| return false; | |
| N = N->getFirstPred(); | |
| } | |
| llvm_unreachable("Reached root without encountering the previous step"); | |
| } | |
| // updateLoopStack is called on every basic block, therefore it needs to be fast | |
| ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx, | |
| ExplodedNode *Pred, unsigned maxVisitOnPath) { | |
| auto State = Pred->getState(); | |
| auto LCtx = Pred->getLocationContext(); | |
| if (!isLoopStmt(LoopStmt)) | |
| return State; | |
| auto LS = State->get<LoopStack>(); | |
| if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() && | |
| LCtx == LS.getHead().getLocationContext()) { | |
| if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) { | |
| State = State->set<LoopStack>(LS.getTail()); | |
| State = State->add<LoopStack>( | |
| LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); | |
| } | |
| return State; | |
| } | |
| unsigned maxStep; | |
| if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred, maxStep)) { | |
| State = State->add<LoopStack>( | |
| LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); | |
| return State; | |
| } | |
| unsigned outerStep = (LS.isEmpty() ? 1 : LS.getHead().getMaxStep()); | |
| unsigned innerMaxStep = maxStep * outerStep; | |
| if (innerMaxStep > MAXIMUM_STEP_UNROLLED) | |
| State = State->add<LoopStack>( | |
| LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); | |
| else | |
| State = State->add<LoopStack>( | |
| LoopState::getUnrolled(LoopStmt, LCtx, innerMaxStep)); | |
| return State; | |
| } | |
| bool isUnrolledState(ProgramStateRef State) { | |
| auto LS = State->get<LoopStack>(); | |
| if (LS.isEmpty() || !LS.getHead().isUnrolled()) | |
| return false; | |
| return true; | |
| } | |
| } | |
| } |