LoopUnrolling.cpp Source File (original) (raw)

20#include

22using namespace clang;

23using namespace ento;

28namespace {

29struct LoopState {

30private:

31 enum Kind { Normal, Unrolled } K;

32 const Stmt *LoopStmt;

34 unsigned maxStep;

36 : K(InK), LoopStmt(S), LCtx(L), maxStep(N) {}

38public:

40 unsigned N) {

41 return LoopState(Normal, S, L, N);

42 }

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}

72namespace ento {

75 return isa_and_nonnull<ForStmt, WhileStmt, DoStmt>(S);

76}

79 auto LS = State->get();

80 if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt)

81 State = State->set(LS.getTail());

82 return State;

83}

86 StringRef RefName) {

88 anyOf(hasOperatorName("<"), hasOperatorName(">"),

89 hasOperatorName("<="), hasOperatorName(">="),

90 hasOperatorName("!=")),

91 hasEitherOperand(ignoringParenImpCasts(

93 .bind(RefName))),

94 hasEitherOperand(

95 ignoringParenImpCasts(integerLiteral().bind("boundNum"))))

96 .bind("conditionOperator");

97}

99static internal::Matcher

103 hasUnaryOperand(ignoringParenImpCasts(

106 hasLHS(ignoringParenImpCasts(

108}

109

110static internal::Matcher

111 callByRef(internal::Matcher VarNodeMatcher) {

112 return callExpr(forEachArgumentWithParam(

115}

116

117static internal::Matcher

121 hasInitializer(anyOf(

124}

125

126static internal::Matcher

127 getAddrTo(internal::Matcher VarNodeMatcher) {

129 hasOperatorName("&"),

131}

132

136

137

138

140 callByRef(equalsBoundNode(std::string(NodeName))),

141 getAddrTo(equalsBoundNode(std::string(NodeName))),

142 assignedToRef(equalsBoundNode(std::string(NodeName))))));

143}

144

147 hasCondition(simpleCondition("initVarName", "initVarRef")),

148

149 hasLoopInit(

151 varDecl(allOf(hasInitializer(ignoringParenImpCasts(

153 equalsBoundNode("initVarName"))))),

155 equalsBoundNode("initVarName"))))),

156 hasRHS(ignoringParenImpCasts(

158

159

161 anyOf(hasOperatorName("++"), hasOperatorName("--")),

163 to(varDecl(allOf(equalsBoundNode("initVarName"),

164 hasType(isInteger())))))))),

166 .bind("forLoop");

167}

168

170

171

175 const auto *MD = cast(D);

176 assert(MD && MD->getParent()->isLambda() &&

177 "Captured variable should only be seen while evaluating a lambda");

179

180

181 llvm::DenseMap<const ValueDecl *, FieldDecl *> LambdaCaptureFields;

182 FieldDecl *LambdaThisCaptureField;

183 LambdaCXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField);

184

185

187 assert(VD);

188 const FieldDecl *FD = LambdaCaptureFields[VD];

189 assert(FD && "Captured variable without a corresponding field");

191}

192

194 if (const DeclStmt *DS = dyn_cast(S)) {

195 for (const Decl *D : DS->decls()) {

196

198 return true;

199 }

200 }

201 return false;

202}

203

204

205

206

207

208

211 assert(VD);

212

214 return true;

215

216 const bool IsRefParamOrCapture =

218

222 return true;

223

225

226

228 if (!S) {

230 continue;

231 }

232

234 return false;

235 }

236

237 if (const auto *SS = dyn_cast(S)) {

238 if (const auto *CST = dyn_cast(SS->getBody())) {

239 for (const Stmt *CB : CST->body()) {

241 return false;

242 }

243 }

244 }

245

246

247

250

251 auto Match =

254 *S, ASTCtx);

255 if (!Match.empty())

256 return true;

257

259 }

260

261

262 if (IsRefParamOrCapture)

263 return false;

264

265 llvm_unreachable("Reached root without finding the declaration of VD");

266}

267

270

272 return false;

273

274

275

277 if (Matches.empty())

278 return false;

279

280 const auto *CounterVarRef = Matches[0].getNodeAs<DeclRefExpr>("initVarRef");

281 llvm::APInt BoundNum =

282 Matches[0].getNodeAs<IntegerLiteral>("boundNum")->getValue();

283 llvm::APInt InitNum =

284 Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue();

285 auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator");

286 unsigned MaxWidth = std::max(InitNum.getBitWidth(), BoundNum.getBitWidth());

287

288 InitNum = InitNum.zext(MaxWidth);

289 BoundNum = BoundNum.zext(MaxWidth);

290

291 if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE)

292 maxStep = (BoundNum - InitNum + 1).abs().getZExtValue();

293 else

294 maxStep = (BoundNum - InitNum).abs().getZExtValue();

295

296

298}

299

301 const Stmt *S = nullptr;

304 return true;

305

307 if (std::optional BE = P.getAs<BlockEntrance>())

308 S = BE->getBlock()->getTerminatorStmt();

309

310 if (S == LoopStmt)

311 return false;

312

314 }

315

316 llvm_unreachable("Reached root without encountering the previous step");

317}

318

319

321 ExplodedNode *Pred, unsigned maxVisitOnPath) {

322 auto State = Pred->getState();

324

326 return State;

327

328 auto LS = State->get();

329 if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() &&

330 LCtx == LS.getHead().getLocationContext()) {

331 if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) {

332 State = State->set(LS.getTail());

333 State = State->add(

334 LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));

335 }

336 return State;

337 }

338 unsigned maxStep;

340 State = State->add(

341 LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));

342 return State;

343 }

344

345 unsigned outerStep = (LS.isEmpty() ? 1 : LS.getHead().getMaxStep());

346

347 unsigned innerMaxStep = maxStep * outerStep;

349 State = State->add(

350 LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));

351 else

352 State = State->add(

353 LoopState::getUnrolled(LoopStmt, LCtx, innerMaxStep));

354 return State;

355}

356

358 auto LS = State->get();

359 if (LS.isEmpty() || !LS.getHead().isUnrolled())

360 return false;

361 return true;

362}

363}

364}

static const int MAXIMUM_STEP_UNROLLED

This header contains the declarations of functions which are used to decide which loops should be com...

#define REGISTER_LIST_WITH_PROGRAMSTATE(Name, Elem)

Declares an immutable list type NameTy, suitable for placement into the ProgramState.

__DEVICE__ long long abs(long long __n)

Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...

ASTContext & getASTContext() const

A builtin binary operation expression such as "x + y" or "x <= y".

Represents a C++ struct/union/class.

void getCaptureFields(llvm::DenseMap< const ValueDecl *, FieldDecl * > &Captures, FieldDecl *&ThisCapture) const

For a closure type, retrieve the mapping from captured variables and this to the non-static data memb...

DeclContext * getParent()

getParent - Returns the containing DeclContext.

A reference to a declared variable, function, enum, etc.

bool refersToEnclosingVariableOrCapture() const

Does this DeclRefExpr refer to an enclosing local or a captured variable?

DeclStmt - Adaptor class for mixing declarations with statements and expressions.

Decl - This represents one declaration (or definition), e.g.

virtual Decl * getCanonicalDecl()

Retrieves the "canonical" declaration of the given declaration.

Represents a member of a struct/union/class.

It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...

const Decl * getDecl() const

LLVM_ATTRIBUTE_RETURNS_NONNULL AnalysisDeclContext * getAnalysisDeclContext() const

Stmt - This represents one statement.

bool isReferenceType() const

Represents a variable declaration or definition.

bool hasGlobalStorage() const

Returns true for all variables that do not have local storage.

const ProgramStateRef & getState() const

const Stmt * getStmtForDiagnostics() const

If the node's program point corresponds to a statement, retrieve that statement.

ProgramPoint getLocation() const

getLocation - Returns the edge associated with the given node.

const LocationContext * getLocationContext() const

ExplodedNode * getFirstPred()

unsigned succ_size() const

const internal::VariadicDynCastAllOfMatcher< Decl, VarDecl > varDecl

Matches variable declarations.

const internal::VariadicDynCastAllOfMatcher< Stmt, DeclRefExpr > declRefExpr

Matches expressions that refer to declarations.

const internal::VariadicOperatorMatcherFunc< 1, 1 > unless

Matches if the provided matcher does not match.

const internal::ArgumentAdaptingMatcherFunc< internal::HasDescendantMatcher > hasDescendant

Matches AST nodes that have descendant AST nodes that match the provided matcher.

const internal::VariadicDynCastAllOfMatcher< Decl, ParmVarDecl > parmVarDecl

Matches parameter variable declarations.

const internal::VariadicDynCastAllOfMatcher< Stmt, ReturnStmt > returnStmt

Matches return statements.

const internal::VariadicDynCastAllOfMatcher< Stmt, CallExpr > callExpr

Matches call expressions.

SmallVector< BoundNodes, 1 > match(MatcherT Matcher, const NodeT &Node, ASTContext &Context)

Returns the results of matching Matcher on Node.

const internal::VariadicDynCastAllOfMatcher< Stmt, UnaryOperator > unaryOperator

Matches unary operator expressions.

const internal::VariadicDynCastAllOfMatcher< Stmt, InitListExpr > initListExpr

Matches init list expressions.

const internal::VariadicDynCastAllOfMatcher< Stmt, ForStmt > forStmt

Matches for statements.

const internal::VariadicDynCastAllOfMatcher< Stmt, GotoStmt > gotoStmt

Matches goto statements.

const internal::VariadicDynCastAllOfMatcher< Stmt, BinaryOperator > binaryOperator

Matches binary operator expressions.

const internal::ArgumentAdaptingMatcherFunc< internal::HasMatcher > has

Matches AST nodes that have child AST nodes that match the provided matcher.

const internal::VariadicOperatorMatcherFunc< 2, std::numeric_limits< unsigned >::max()> allOf

Matches if all given matchers match.

const internal::VariadicDynCastAllOfMatcher< Stmt, SwitchStmt > switchStmt

Matches switch statements.

const AstTypeMatcher< ReferenceType > referenceType

Matches both lvalue and rvalue reference types.

const internal::VariadicDynCastAllOfMatcher< Stmt, IntegerLiteral > integerLiteral

Matches integer literals of all sizes / encodings, e.g.

internal::PolymorphicMatcher< internal::HasDeclarationMatcher, void(internal::HasDeclarationSupportedTypes), internal::Matcher< Decl > > hasDeclaration(const internal::Matcher< Decl > &InnerMatcher)

Matches a node if the declaration associated with that node matches the given matcher.

const internal::VariadicDynCastAllOfMatcher< Stmt, DeclStmt > declStmt

Matches declaration statements.

const internal::VariadicAllOfMatcher< Stmt > stmt

Matches statements.

const internal::VariadicOperatorMatcherFunc< 2, std::numeric_limits< unsigned >::max()> anyOf

Matches if any of the given matchers matches.

const internal::VariadicAllOfMatcher< QualType > qualType

Matches QualTypes in the clang AST.

static bool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt)

static internal::Matcher< Stmt > simpleCondition(StringRef BindName, StringRef RefName)

static internal::Matcher< Stmt > hasSuspiciousStmt(StringRef NodeName)

static internal::Matcher< Stmt > callByRef(internal::Matcher< Decl > VarNodeMatcher)

static internal::Matcher< Stmt > forLoopMatcher()

static bool isPossiblyEscaped(ExplodedNode *N, const DeclRefExpr *DR)

static internal::Matcher< Stmt > getAddrTo(internal::Matcher< Decl > VarNodeMatcher)

static bool isLoopStmt(const Stmt *S)

ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State)

Updates the given ProgramState.

static bool isFoundInStmt(const Stmt *S, const VarDecl *VD)

static internal::Matcher< Stmt > assignedToRef(internal::Matcher< Decl > VarNodeMatcher)

static bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, ExplodedNode *Pred, unsigned &maxStep)

bool isUnrolledState(ProgramStateRef State)

Returns if the given State indicates that is inside a completely unrolled loop.

static bool isCapturedByReference(ExplodedNode *N, const DeclRefExpr *DR)

ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx, ExplodedNode *Pred, unsigned maxVisitOnPath)

Updates the stack of loops contained by the ProgramState.

static internal::Matcher< Stmt > changeIntBoundNode(internal::Matcher< Decl > VarNodeMatcher)

The JSON file list parser is used to communicate input to InstallAPI.

bool operator==(const CallGraphNode::CallRecord &LHS, const CallGraphNode::CallRecord &RHS)