LoopUnrolling.cpp Source File (original) (raw)

20#include

22using namespace clang;

23using namespace ento;

26using ast_matchers::internal::Matcher;

30namespace {

31struct LoopState {

32private:

33 enum Kind { Normal, Unrolled } K;

34 const Stmt *LoopStmt;

36 unsigned maxStep;

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

40public:

42 unsigned N) {

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

44 }

46 unsigned N) {

47 return LoopState(Unrolled, S, L, N);

48 }

49 bool isUnrolled() const { return K == Unrolled; }

50 unsigned getMaxStep() const { return maxStep; }

51 const Stmt *getLoopStmt() const { return LoopStmt; }

52 const LocationContext *getLocationContext() const { return LCtx; }

53 bool operator==(const LoopState &X) const {

54 return K == X.K && LoopStmt == X.LoopStmt;

55 }

56 void Profile(llvm::FoldingSetNodeID &ID) const {

57 ID.AddInteger(K);

58 ID.AddPointer(LoopStmt);

59 ID.AddPointer(LCtx);

60 ID.AddInteger(maxStep);

61 }

62};

63}

74namespace {

76 return Node->isIntegralOrEnumerationType();

77}

78}

79namespace ento {

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

83}

86 auto LS = State->get();

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

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

89 return State;

90}

92static Matcher simpleCondition(StringRef BindName, StringRef RefName) {

93 auto LoopVariable = ignoringParenImpCasts(

95 .bind(RefName));

96 auto UpperBound = ignoringParenImpCasts(

97 expr(hasType(isIntegralOrEnumerationType())).bind("boundNum"));

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

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

102 hasOperatorName("!=")),

104 binaryOperator(hasRHS(LoopVariable), hasLHS(UpperBound))))

105 .bind("conditionOperator");

106}

107

111 hasUnaryOperand(ignoringParenImpCasts(

114 hasLHS(ignoringParenImpCasts(

116}

117

118static Matcher callByRef(Matcher VarNodeMatcher) {

119 return callExpr(forEachArgumentWithParam(

122}

123

131

132static Matcher getAddrTo(Matcher VarNodeMatcher) {

134 hasOperatorName("&"),

136}

137

141

142

143

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

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

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

148}

149

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

153

154 hasLoopInit(

156 varDecl(allOf(hasInitializer(ignoringParenImpCasts(

158 equalsBoundNode("initVarName"))))),

160 equalsBoundNode("initVarName"))))),

161 hasRHS(ignoringParenImpCasts(

163

164

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

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

169 hasType(isInteger())))))))),

171 .bind("forLoop");

172}

173

175

176

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

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

184

185

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

187 FieldDecl *LambdaThisCaptureField;

188 LambdaCXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField);

189

190

192 assert(VD);

193 const FieldDecl *FD = LambdaCaptureFields[VD];

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

196}

197

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

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

201

202 if (D->getCanonicalDecl() == VD)

203 return true;

204 }

205 }

206 return false;

207}

208

209

210

211

212

213

216 assert(VD);

217

219 return true;

220

221 const bool IsRefParamOrCapture =

223

227 return true;

228

230

231

233 if (!S) {

235 continue;

236 }

237

239 return false;

240 }

241

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

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

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

246 return false;

247 }

248 }

249 }

250

251

252

255

259 *S, ASTCtx);

260 if ( Match .empty())

261 return true;

262

264 }

265

266

267 if (IsRefParamOrCapture)

268 return false;

269

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

271}

272

275

277 return false;

278

280 if (Matches.empty())

281 return false;

282

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

284 const Expr *BoundNumExpr = Matches[0].getNodeAs<Expr>("boundNum");

285

287 if (!BoundNumExpr || !BoundNumExpr->EvaluateAsInt(BoundNumResult, ASTCtx,

289 return false;

290 }

291 llvm::APInt InitNum =

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

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

294 unsigned MaxWidth = std::max(InitNum.getBitWidth(),

295 BoundNumResult.Val.getInt().getBitWidth());

296

297 InitNum = InitNum.zext(MaxWidth);

298 llvm::APInt BoundNum = BoundNumResult.Val.getInt().zext(MaxWidth);

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

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

301 else

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

303

304

306}

307

309 const Stmt *S = nullptr;

312 return true;

313

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

317

318 if (S == LoopStmt)

319 return false;

320

322 }

323

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

325}

326

327

329 ExplodedNode *Pred, unsigned maxVisitOnPath) {

330 auto State = Pred->getState();

332

334 return State;

335

336 auto LS = State->get();

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

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

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

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

341 State = State->add(

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

343 }

344 return State;

345 }

346 unsigned maxStep;

348 State = State->add(

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

350 return State;

351 }

352

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

354

355 unsigned innerMaxStep = maxStep * outerStep;

357 State = State->add(

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

359 else

360 State = State->add(

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

362 return State;

363}

364

366 auto LS = State->get();

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

368 return false;

369 return true;

370}

371}

372}

#define AST_MATCHER(Type, DefineMatcher)

AST_MATCHER(Type, DefineMatcher) { ... } defines a zero parameter function named DefineMatcher() that...

static const int MAXIMUM_STEP_UNROLLED

Definition LoopUnrolling.cpp:28

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.

This represents one expression.

@ SE_NoSideEffects

Strictly evaluate the expression.

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

std::optional< T > getAs() const

Convert to the specified ProgramPoint type, returning std::nullopt if this ProgramPoint is not of the...

A (possibly-)qualified type.

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 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::VariadicDynCastAllOfMatcher< Stmt, Expr > expr

Matches expressions.

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.

const AstTypeMatcher< ReferenceType > referenceType

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

Definition LoopUnrolling.cpp:308

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

Definition LoopUnrolling.cpp:214

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

Definition LoopUnrolling.cpp:108

IntrusiveRefCntPtr< const ProgramState > ProgramStateRef

static bool isLoopStmt(const Stmt *S)

Definition LoopUnrolling.cpp:81

static Matcher< Stmt > forLoopMatcher()

Definition LoopUnrolling.cpp:150

ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State)

Updates the given ProgramState.

Definition LoopUnrolling.cpp:85

static Matcher< Stmt > hasSuspiciousStmt(StringRef NodeName)

Definition LoopUnrolling.cpp:138

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

Definition LoopUnrolling.cpp:132

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

Definition LoopUnrolling.cpp:198

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

Definition LoopUnrolling.cpp:273

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

Definition LoopUnrolling.cpp:92

bool isUnrolledState(ProgramStateRef State)

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

Definition LoopUnrolling.cpp:365

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

Definition LoopUnrolling.cpp:174

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

Definition LoopUnrolling.cpp:124

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

Definition LoopUnrolling.cpp:118

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

Updates the stack of loops contained by the ProgramState.

Definition LoopUnrolling.cpp:328

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

@ Match

This is not an overload because the signature exactly matches an existing declaration.

bool isa(CodeGen::Address addr)

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

U cast(CodeGen::Address addr)

EvalResult is a struct with detailed info about an evaluated expression.