| 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 |
} |