1 //===--- LoopUnrolling.cpp - Unroll loops -----------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// This file contains functions which are used to decide if a loop worth to be 10 /// unrolled. Moreover, these functions manages the stack of loop which is 11 /// tracked by the ProgramState. 12 /// 13 //===----------------------------------------------------------------------===// 14 15 #include "clang/ASTMatchers/ASTMatchers.h" 16 #include "clang/ASTMatchers/ASTMatchFinder.h" 17 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 18 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 19 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h" 20 #include <optional> 21 22 using namespace clang; 23 using namespace ento; 24 using namespace clang::ast_matchers; 25 26 static const int MAXIMUM_STEP_UNROLLED = 128; 27 28 namespace { 29 struct LoopState { 30 private: 31 enum Kind { Normal, Unrolled } K; 32 const Stmt *LoopStmt; 33 const LocationContext *LCtx; 34 unsigned maxStep; 35 LoopState(Kind InK, const Stmt *S, const LocationContext *L, unsigned N) 36 : K(InK), LoopStmt(S), LCtx(L), maxStep(N) {} 37 38 public: 39 static LoopState getNormal(const Stmt *S, const LocationContext *L, 40 unsigned N) { 41 return LoopState(Normal, S, L, N); 42 } 43 static LoopState getUnrolled(const Stmt *S, const LocationContext *L, 44 unsigned N) { 45 return LoopState(Unrolled, S, L, N); 46 } 47 bool isUnrolled() const { return K == Unrolled; } 48 unsigned getMaxStep() const { return maxStep; } 49 const Stmt *getLoopStmt() const { return LoopStmt; } 50 const LocationContext *getLocationContext() const { return LCtx; } 51 bool operator==(const LoopState &X) const { 52 return K == X.K && LoopStmt == X.LoopStmt; 53 } 54 void Profile(llvm::FoldingSetNodeID &ID) const { 55 ID.AddInteger(K); 56 ID.AddPointer(LoopStmt); 57 ID.AddPointer(LCtx); 58 ID.AddInteger(maxStep); 59 } 60 }; 61 } // namespace 62 63 // The tracked stack of loops. The stack indicates that which loops the 64 // simulated element contained by. The loops are marked depending if we decided 65 // to unroll them. 66 // TODO: The loop stack should not need to be in the program state since it is 67 // lexical in nature. Instead, the stack of loops should be tracked in the 68 // LocationContext. 69 REGISTER_LIST_WITH_PROGRAMSTATE(LoopStack, LoopState) 70 71 namespace clang { 72 namespace ento { 73 74 static bool isLoopStmt(const Stmt *S) { 75 return isa_and_nonnull<ForStmt, WhileStmt, DoStmt>(S); 76 } 77 78 ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) { 79 auto LS = State->get<LoopStack>(); 80 if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt) 81 State = State->set<LoopStack>(LS.getTail()); 82 return State; 83 } 84 85 static internal::Matcher<Stmt> simpleCondition(StringRef BindName, 86 StringRef RefName) { 87 return binaryOperator( 88 anyOf(hasOperatorName("<"), hasOperatorName(">"), 89 hasOperatorName("<="), hasOperatorName(">="), 90 hasOperatorName("!=")), 91 hasEitherOperand(ignoringParenImpCasts( 92 declRefExpr(to(varDecl(hasType(isInteger())).bind(BindName))) 93 .bind(RefName))), 94 hasEitherOperand( 95 ignoringParenImpCasts(integerLiteral().bind("boundNum")))) 96 .bind("conditionOperator"); 97 } 98 99 static internal::Matcher<Stmt> 100 changeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher) { 101 return anyOf( 102 unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")), 103 hasUnaryOperand(ignoringParenImpCasts( 104 declRefExpr(to(varDecl(VarNodeMatcher)))))), 105 binaryOperator(isAssignmentOperator(), 106 hasLHS(ignoringParenImpCasts( 107 declRefExpr(to(varDecl(VarNodeMatcher))))))); 108 } 109 110 static internal::Matcher<Stmt> 111 callByRef(internal::Matcher<Decl> VarNodeMatcher) { 112 return callExpr(forEachArgumentWithParam( 113 declRefExpr(to(varDecl(VarNodeMatcher))), 114 parmVarDecl(hasType(references(qualType(unless(isConstQualified()))))))); 115 } 116 117 static internal::Matcher<Stmt> 118 assignedToRef(internal::Matcher<Decl> VarNodeMatcher) { 119 return declStmt(hasDescendant(varDecl( 120 allOf(hasType(referenceType()), 121 hasInitializer(anyOf( 122 initListExpr(has(declRefExpr(to(varDecl(VarNodeMatcher))))), 123 declRefExpr(to(varDecl(VarNodeMatcher))))))))); 124 } 125 126 static internal::Matcher<Stmt> 127 getAddrTo(internal::Matcher<Decl> VarNodeMatcher) { 128 return unaryOperator( 129 hasOperatorName("&"), 130 hasUnaryOperand(declRefExpr(hasDeclaration(VarNodeMatcher)))); 131 } 132 133 static internal::Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) { 134 return hasDescendant(stmt( 135 anyOf(gotoStmt(), switchStmt(), returnStmt(), 136 // Escaping and not known mutation of the loop counter is handled 137 // by exclusion of assigning and address-of operators and 138 // pass-by-ref function calls on the loop counter from the body. 139 changeIntBoundNode(equalsBoundNode(std::string(NodeName))), 140 callByRef(equalsBoundNode(std::string(NodeName))), 141 getAddrTo(equalsBoundNode(std::string(NodeName))), 142 assignedToRef(equalsBoundNode(std::string(NodeName)))))); 143 } 144 145 static internal::Matcher<Stmt> forLoopMatcher() { 146 return forStmt( 147 hasCondition(simpleCondition("initVarName", "initVarRef")), 148 // Initialization should match the form: 'int i = 6' or 'i = 42'. 149 hasLoopInit( 150 anyOf(declStmt(hasSingleDecl( 151 varDecl(allOf(hasInitializer(ignoringParenImpCasts( 152 integerLiteral().bind("initNum"))), 153 equalsBoundNode("initVarName"))))), 154 binaryOperator(hasLHS(declRefExpr(to(varDecl( 155 equalsBoundNode("initVarName"))))), 156 hasRHS(ignoringParenImpCasts( 157 integerLiteral().bind("initNum")))))), 158 // Incrementation should be a simple increment or decrement 159 // operator call. 160 hasIncrement(unaryOperator( 161 anyOf(hasOperatorName("++"), hasOperatorName("--")), 162 hasUnaryOperand(declRefExpr( 163 to(varDecl(allOf(equalsBoundNode("initVarName"), 164 hasType(isInteger())))))))), 165 unless(hasBody(hasSuspiciousStmt("initVarName")))) 166 .bind("forLoop"); 167 } 168 169 static bool isCapturedByReference(ExplodedNode *N, const DeclRefExpr *DR) { 170 171 // Get the lambda CXXRecordDecl 172 assert(DR->refersToEnclosingVariableOrCapture()); 173 const LocationContext *LocCtxt = N->getLocationContext(); 174 const Decl *D = LocCtxt->getDecl(); 175 const auto *MD = cast<CXXMethodDecl>(D); 176 assert(MD && MD->getParent()->isLambda() && 177 "Captured variable should only be seen while evaluating a lambda"); 178 const CXXRecordDecl *LambdaCXXRec = MD->getParent(); 179 180 // Lookup the fields of the lambda 181 llvm::DenseMap<const ValueDecl *, FieldDecl *> LambdaCaptureFields; 182 FieldDecl *LambdaThisCaptureField; 183 LambdaCXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField); 184 185 // Check if the counter is captured by reference 186 const VarDecl *VD = cast<VarDecl>(DR->getDecl()->getCanonicalDecl()); 187 assert(VD); 188 const FieldDecl *FD = LambdaCaptureFields[VD]; 189 assert(FD && "Captured variable without a corresponding field"); 190 return FD->getType()->isReferenceType(); 191 } 192 193 // A loop counter is considered escaped if: 194 // case 1: It is a global variable. 195 // case 2: It is a reference parameter or a reference capture. 196 // case 3: It is assigned to a non-const reference variable or parameter. 197 // case 4: Has its address taken. 198 static bool isPossiblyEscaped(ExplodedNode *N, const DeclRefExpr *DR) { 199 const VarDecl *VD = cast<VarDecl>(DR->getDecl()->getCanonicalDecl()); 200 assert(VD); 201 // Case 1: 202 if (VD->hasGlobalStorage()) 203 return true; 204 205 const bool IsRefParamOrCapture = 206 isa<ParmVarDecl>(VD) || DR->refersToEnclosingVariableOrCapture(); 207 // Case 2: 208 if ((DR->refersToEnclosingVariableOrCapture() && 209 isCapturedByReference(N, DR)) || 210 (IsRefParamOrCapture && VD->getType()->isReferenceType())) 211 return true; 212 213 while (!N->pred_empty()) { 214 // FIXME: getStmtForDiagnostics() does nasty things in order to provide 215 // a valid statement for body farms, do we need this behavior here? 216 const Stmt *S = N->getStmtForDiagnostics(); 217 if (!S) { 218 N = N->getFirstPred(); 219 continue; 220 } 221 222 if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) { 223 for (const Decl *D : DS->decls()) { 224 // Once we reach the declaration of the VD we can return. 225 if (D->getCanonicalDecl() == VD) 226 return false; 227 } 228 } 229 // Check the usage of the pass-by-ref function calls and adress-of operator 230 // on VD and reference initialized by VD. 231 ASTContext &ASTCtx = 232 N->getLocationContext()->getAnalysisDeclContext()->getASTContext(); 233 // Case 3 and 4: 234 auto Match = 235 match(stmt(anyOf(callByRef(equalsNode(VD)), getAddrTo(equalsNode(VD)), 236 assignedToRef(equalsNode(VD)))), 237 *S, ASTCtx); 238 if (!Match.empty()) 239 return true; 240 241 N = N->getFirstPred(); 242 } 243 244 // Reference parameter and reference capture will not be found. 245 if (IsRefParamOrCapture) 246 return false; 247 248 llvm_unreachable("Reached root without finding the declaration of VD"); 249 } 250 251 bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, 252 ExplodedNode *Pred, unsigned &maxStep) { 253 254 if (!isLoopStmt(LoopStmt)) 255 return false; 256 257 // TODO: Match the cases where the bound is not a concrete literal but an 258 // integer with known value 259 auto Matches = match(forLoopMatcher(), *LoopStmt, ASTCtx); 260 if (Matches.empty()) 261 return false; 262 263 const auto *CounterVarRef = Matches[0].getNodeAs<DeclRefExpr>("initVarRef"); 264 llvm::APInt BoundNum = 265 Matches[0].getNodeAs<IntegerLiteral>("boundNum")->getValue(); 266 llvm::APInt InitNum = 267 Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue(); 268 auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator"); 269 if (InitNum.getBitWidth() != BoundNum.getBitWidth()) { 270 InitNum = InitNum.zext(BoundNum.getBitWidth()); 271 BoundNum = BoundNum.zext(InitNum.getBitWidth()); 272 } 273 274 if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE) 275 maxStep = (BoundNum - InitNum + 1).abs().getZExtValue(); 276 else 277 maxStep = (BoundNum - InitNum).abs().getZExtValue(); 278 279 // Check if the counter of the loop is not escaped before. 280 return !isPossiblyEscaped(Pred, CounterVarRef); 281 } 282 283 bool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt) { 284 const Stmt *S = nullptr; 285 while (!N->pred_empty()) { 286 if (N->succ_size() > 1) 287 return true; 288 289 ProgramPoint P = N->getLocation(); 290 if (std::optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) 291 S = BE->getBlock()->getTerminatorStmt(); 292 293 if (S == LoopStmt) 294 return false; 295 296 N = N->getFirstPred(); 297 } 298 299 llvm_unreachable("Reached root without encountering the previous step"); 300 } 301 302 // updateLoopStack is called on every basic block, therefore it needs to be fast 303 ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx, 304 ExplodedNode *Pred, unsigned maxVisitOnPath) { 305 auto State = Pred->getState(); 306 auto LCtx = Pred->getLocationContext(); 307 308 if (!isLoopStmt(LoopStmt)) 309 return State; 310 311 auto LS = State->get<LoopStack>(); 312 if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() && 313 LCtx == LS.getHead().getLocationContext()) { 314 if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) { 315 State = State->set<LoopStack>(LS.getTail()); 316 State = State->add<LoopStack>( 317 LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); 318 } 319 return State; 320 } 321 unsigned maxStep; 322 if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred, maxStep)) { 323 State = State->add<LoopStack>( 324 LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); 325 return State; 326 } 327 328 unsigned outerStep = (LS.isEmpty() ? 1 : LS.getHead().getMaxStep()); 329 330 unsigned innerMaxStep = maxStep * outerStep; 331 if (innerMaxStep > MAXIMUM_STEP_UNROLLED) 332 State = State->add<LoopStack>( 333 LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath)); 334 else 335 State = State->add<LoopStack>( 336 LoopState::getUnrolled(LoopStmt, LCtx, innerMaxStep)); 337 return State; 338 } 339 340 bool isUnrolledState(ProgramStateRef State) { 341 auto LS = State->get<LoopStack>(); 342 if (LS.isEmpty() || !LS.getHead().isUnrolled()) 343 return false; 344 return true; 345 } 346 } 347 } 348