1326941Sdim//===--- LoopUnrolling.cpp - Unroll loops -----------------------*- C++ -*-===// 2326941Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6326941Sdim// 7326941Sdim//===----------------------------------------------------------------------===// 8326941Sdim/// 9326941Sdim/// This file contains functions which are used to decide if a loop worth to be 10326941Sdim/// unrolled. Moreover, these functions manages the stack of loop which is 11326941Sdim/// tracked by the ProgramState. 12326941Sdim/// 13326941Sdim//===----------------------------------------------------------------------===// 14326941Sdim 15326941Sdim#include "clang/ASTMatchers/ASTMatchers.h" 16326941Sdim#include "clang/ASTMatchers/ASTMatchFinder.h" 17326941Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 18326941Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 19326941Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h" 20326941Sdim 21326941Sdimusing namespace clang; 22326941Sdimusing namespace ento; 23326941Sdimusing namespace clang::ast_matchers; 24326941Sdim 25326941Sdimstatic const int MAXIMUM_STEP_UNROLLED = 128; 26326941Sdim 27326941Sdimstruct LoopState { 28326941Sdimprivate: 29326941Sdim enum Kind { Normal, Unrolled } K; 30326941Sdim const Stmt *LoopStmt; 31326941Sdim const LocationContext *LCtx; 32326941Sdim unsigned maxStep; 33326941Sdim LoopState(Kind InK, const Stmt *S, const LocationContext *L, unsigned N) 34326941Sdim : K(InK), LoopStmt(S), LCtx(L), maxStep(N) {} 35326941Sdim 36326941Sdimpublic: 37326941Sdim static LoopState getNormal(const Stmt *S, const LocationContext *L, 38326941Sdim unsigned N) { 39326941Sdim return LoopState(Normal, S, L, N); 40326941Sdim } 41326941Sdim static LoopState getUnrolled(const Stmt *S, const LocationContext *L, 42326941Sdim unsigned N) { 43326941Sdim return LoopState(Unrolled, S, L, N); 44326941Sdim } 45326941Sdim bool isUnrolled() const { return K == Unrolled; } 46326941Sdim unsigned getMaxStep() const { return maxStep; } 47326941Sdim const Stmt *getLoopStmt() const { return LoopStmt; } 48326941Sdim const LocationContext *getLocationContext() const { return LCtx; } 49326941Sdim bool operator==(const LoopState &X) const { 50326941Sdim return K == X.K && LoopStmt == X.LoopStmt; 51326941Sdim } 52326941Sdim void Profile(llvm::FoldingSetNodeID &ID) const { 53326941Sdim ID.AddInteger(K); 54326941Sdim ID.AddPointer(LoopStmt); 55326941Sdim ID.AddPointer(LCtx); 56326941Sdim ID.AddInteger(maxStep); 57326941Sdim } 58326941Sdim}; 59326941Sdim 60326941Sdim// The tracked stack of loops. The stack indicates that which loops the 61326941Sdim// simulated element contained by. The loops are marked depending if we decided 62326941Sdim// to unroll them. 63326941Sdim// TODO: The loop stack should not need to be in the program state since it is 64326941Sdim// lexical in nature. Instead, the stack of loops should be tracked in the 65326941Sdim// LocationContext. 66326941SdimREGISTER_LIST_WITH_PROGRAMSTATE(LoopStack, LoopState) 67326941Sdim 68326941Sdimnamespace clang { 69326941Sdimnamespace ento { 70326941Sdim 71326941Sdimstatic bool isLoopStmt(const Stmt *S) { 72326941Sdim return S && (isa<ForStmt>(S) || isa<WhileStmt>(S) || isa<DoStmt>(S)); 73326941Sdim} 74326941Sdim 75326941SdimProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) { 76326941Sdim auto LS = State->get<LoopStack>(); 77326941Sdim if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt) 78326941Sdim State = State->set<LoopStack>(LS.getTail()); 79326941Sdim return State; 80326941Sdim} 81326941Sdim 82326941Sdimstatic internal::Matcher<Stmt> simpleCondition(StringRef BindName) { 83326941Sdim return binaryOperator(anyOf(hasOperatorName("<"), hasOperatorName(">"), 84326941Sdim hasOperatorName("<="), hasOperatorName(">="), 85326941Sdim hasOperatorName("!=")), 86326941Sdim hasEitherOperand(ignoringParenImpCasts(declRefExpr( 87326941Sdim to(varDecl(hasType(isInteger())).bind(BindName))))), 88326941Sdim hasEitherOperand(ignoringParenImpCasts( 89326941Sdim integerLiteral().bind("boundNum")))) 90326941Sdim .bind("conditionOperator"); 91326941Sdim} 92326941Sdim 93326941Sdimstatic internal::Matcher<Stmt> 94326941SdimchangeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher) { 95326941Sdim return anyOf( 96326941Sdim unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")), 97326941Sdim hasUnaryOperand(ignoringParenImpCasts( 98326941Sdim declRefExpr(to(varDecl(VarNodeMatcher)))))), 99341825Sdim binaryOperator(isAssignmentOperator(), 100326941Sdim hasLHS(ignoringParenImpCasts( 101326941Sdim declRefExpr(to(varDecl(VarNodeMatcher))))))); 102326941Sdim} 103326941Sdim 104326941Sdimstatic internal::Matcher<Stmt> 105326941SdimcallByRef(internal::Matcher<Decl> VarNodeMatcher) { 106326941Sdim return callExpr(forEachArgumentWithParam( 107326941Sdim declRefExpr(to(varDecl(VarNodeMatcher))), 108326941Sdim parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))); 109326941Sdim} 110326941Sdim 111326941Sdimstatic internal::Matcher<Stmt> 112326941SdimassignedToRef(internal::Matcher<Decl> VarNodeMatcher) { 113326941Sdim return declStmt(hasDescendant(varDecl( 114326941Sdim allOf(hasType(referenceType()), 115326941Sdim hasInitializer(anyOf( 116326941Sdim initListExpr(has(declRefExpr(to(varDecl(VarNodeMatcher))))), 117326941Sdim declRefExpr(to(varDecl(VarNodeMatcher))))))))); 118326941Sdim} 119326941Sdim 120326941Sdimstatic internal::Matcher<Stmt> 121326941SdimgetAddrTo(internal::Matcher<Decl> VarNodeMatcher) { 122326941Sdim return unaryOperator( 123326941Sdim hasOperatorName("&"), 124326941Sdim hasUnaryOperand(declRefExpr(hasDeclaration(VarNodeMatcher)))); 125326941Sdim} 126326941Sdim 127326941Sdimstatic internal::Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) { 128326941Sdim return hasDescendant(stmt( 129326941Sdim anyOf(gotoStmt(), switchStmt(), returnStmt(), 130326941Sdim // Escaping and not known mutation of the loop counter is handled 131326941Sdim // by exclusion of assigning and address-of operators and 132326941Sdim // pass-by-ref function calls on the loop counter from the body. 133326941Sdim changeIntBoundNode(equalsBoundNode(NodeName)), 134326941Sdim callByRef(equalsBoundNode(NodeName)), 135326941Sdim getAddrTo(equalsBoundNode(NodeName)), 136326941Sdim assignedToRef(equalsBoundNode(NodeName))))); 137326941Sdim} 138326941Sdim 139326941Sdimstatic internal::Matcher<Stmt> forLoopMatcher() { 140326941Sdim return forStmt( 141326941Sdim hasCondition(simpleCondition("initVarName")), 142326941Sdim // Initialization should match the form: 'int i = 6' or 'i = 42'. 143341825Sdim hasLoopInit( 144341825Sdim anyOf(declStmt(hasSingleDecl( 145341825Sdim varDecl(allOf(hasInitializer(ignoringParenImpCasts( 146341825Sdim integerLiteral().bind("initNum"))), 147341825Sdim equalsBoundNode("initVarName"))))), 148341825Sdim binaryOperator(hasLHS(declRefExpr(to(varDecl( 149341825Sdim equalsBoundNode("initVarName"))))), 150341825Sdim hasRHS(ignoringParenImpCasts( 151341825Sdim integerLiteral().bind("initNum")))))), 152326941Sdim // Incrementation should be a simple increment or decrement 153326941Sdim // operator call. 154326941Sdim hasIncrement(unaryOperator( 155326941Sdim anyOf(hasOperatorName("++"), hasOperatorName("--")), 156326941Sdim hasUnaryOperand(declRefExpr( 157326941Sdim to(varDecl(allOf(equalsBoundNode("initVarName"), 158326941Sdim hasType(isInteger())))))))), 159326941Sdim unless(hasBody(hasSuspiciousStmt("initVarName")))).bind("forLoop"); 160326941Sdim} 161326941Sdim 162326941Sdimstatic bool isPossiblyEscaped(const VarDecl *VD, ExplodedNode *N) { 163326941Sdim // Global variables assumed as escaped variables. 164326941Sdim if (VD->hasGlobalStorage()) 165326941Sdim return true; 166326941Sdim 167326941Sdim while (!N->pred_empty()) { 168360784Sdim // FIXME: getStmtForDiagnostics() does nasty things in order to provide 169360784Sdim // a valid statement for body farms, do we need this behavior here? 170360784Sdim const Stmt *S = N->getStmtForDiagnostics(); 171326941Sdim if (!S) { 172326941Sdim N = N->getFirstPred(); 173326941Sdim continue; 174326941Sdim } 175326941Sdim 176326941Sdim if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) { 177326941Sdim for (const Decl *D : DS->decls()) { 178326941Sdim // Once we reach the declaration of the VD we can return. 179326941Sdim if (D->getCanonicalDecl() == VD) 180326941Sdim return false; 181326941Sdim } 182326941Sdim } 183326941Sdim // Check the usage of the pass-by-ref function calls and adress-of operator 184326941Sdim // on VD and reference initialized by VD. 185326941Sdim ASTContext &ASTCtx = 186326941Sdim N->getLocationContext()->getAnalysisDeclContext()->getASTContext(); 187326941Sdim auto Match = 188326941Sdim match(stmt(anyOf(callByRef(equalsNode(VD)), getAddrTo(equalsNode(VD)), 189326941Sdim assignedToRef(equalsNode(VD)))), 190326941Sdim *S, ASTCtx); 191326941Sdim if (!Match.empty()) 192326941Sdim return true; 193326941Sdim 194326941Sdim N = N->getFirstPred(); 195326941Sdim } 196326941Sdim llvm_unreachable("Reached root without finding the declaration of VD"); 197326941Sdim} 198326941Sdim 199326941Sdimbool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, 200326941Sdim ExplodedNode *Pred, unsigned &maxStep) { 201326941Sdim 202326941Sdim if (!isLoopStmt(LoopStmt)) 203326941Sdim return false; 204326941Sdim 205326941Sdim // TODO: Match the cases where the bound is not a concrete literal but an 206326941Sdim // integer with known value 207326941Sdim auto Matches = match(forLoopMatcher(), *LoopStmt, ASTCtx); 208326941Sdim if (Matches.empty()) 209326941Sdim return false; 210326941Sdim 211326941Sdim auto CounterVar = Matches[0].getNodeAs<VarDecl>("initVarName"); 212326941Sdim llvm::APInt BoundNum = 213326941Sdim Matches[0].getNodeAs<IntegerLiteral>("boundNum")->getValue(); 214326941Sdim llvm::APInt InitNum = 215326941Sdim Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue(); 216326941Sdim auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator"); 217326941Sdim if (InitNum.getBitWidth() != BoundNum.getBitWidth()) { 218326941Sdim InitNum = InitNum.zextOrSelf(BoundNum.getBitWidth()); 219326941Sdim BoundNum = BoundNum.zextOrSelf(InitNum.getBitWidth()); 220326941Sdim } 221326941Sdim 222326941Sdim if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE) 223326941Sdim maxStep = (BoundNum - InitNum + 1).abs().getZExtValue(); 224326941Sdim else 225326941Sdim maxStep = (BoundNum - InitNum).abs().getZExtValue(); 226326941Sdim 227326941Sdim // Check if the counter of the loop is not escaped before. 228326941Sdim return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred); 229326941Sdim} 230326941Sdim 231326941Sdimbool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt) { 232326941Sdim const Stmt *S = nullptr; 233326941Sdim while (!N->pred_empty()) { 234326941Sdim if (N->succ_size() > 1) 235326941Sdim return true; 236326941Sdim 237326941Sdim ProgramPoint P = N->getLocation(); 238326941Sdim if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) 239353358Sdim S = BE->getBlock()->getTerminatorStmt(); 240326941Sdim 241326941Sdim if (S == LoopStmt) 242326941Sdim return false; 243326941Sdim 244326941Sdim N = N->getFirstPred(); 245326941Sdim } 246326941Sdim 247326941Sdim llvm_unreachable("Reached root without encountering the previous step"); 248326941Sdim} 249326941Sdim 250326941Sdim// updateLoopStack is called on every basic block, therefore it needs to be fast 251326941SdimProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx, 252326941Sdim ExplodedNode *Pred, unsigned maxVisitOnPath) { 253326941Sdim auto State = Pred->getState(); 254326941Sdim auto LCtx = Pred->getLocationContext(); 255326941Sdim 256326941Sdim if (!isLoopStmt(LoopStmt)) 257326941Sdim return State; 258326941Sdim 259326941Sdim auto LS = State->get<LoopStack>(); 260326941Sdim if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() && 261326941Sdim LCtx == LS.getHead().getLocationContext()) { 262326941Sdim if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) { 263326941Sdim State = State->set<LoopStack>(LS.getTail()); 264326941Sdim State = State->add<LoopStack>( 265326941Sdim LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); 266326941Sdim } 267326941Sdim return State; 268326941Sdim } 269326941Sdim unsigned maxStep; 270326941Sdim if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred, maxStep)) { 271326941Sdim State = State->add<LoopStack>( 272326941Sdim LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); 273326941Sdim return State; 274326941Sdim } 275326941Sdim 276326941Sdim unsigned outerStep = (LS.isEmpty() ? 1 : LS.getHead().getMaxStep()); 277326941Sdim 278326941Sdim unsigned innerMaxStep = maxStep * outerStep; 279326941Sdim if (innerMaxStep > MAXIMUM_STEP_UNROLLED) 280326941Sdim State = State->add<LoopStack>( 281326941Sdim LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); 282326941Sdim else 283326941Sdim State = State->add<LoopStack>( 284326941Sdim LoopState::getUnrolled(LoopStmt, LCtx, innerMaxStep)); 285326941Sdim return State; 286326941Sdim} 287326941Sdim 288326941Sdimbool isUnrolledState(ProgramStateRef State) { 289326941Sdim auto LS = State->get<LoopStack>(); 290326941Sdim if (LS.isEmpty() || !LS.getHead().isUnrolled()) 291326941Sdim return false; 292326941Sdim return true; 293326941Sdim} 294326941Sdim} 295326941Sdim} 296