Debian Codegraph @

llvm-project/clang-tools-extra/clang-tidy/altera/UnrollLoopsCheck.cpp

raw
1 //===--- UnrollLoopsCheck.cpp - clang-tidy --------------------------------===//
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 #include "UnrollLoopsCheck.h"
10 #include "clang/AST/APValue.h"
11 #include "clang/AST/ASTContext.h"
12 #include "clang/AST/ASTTypeTraits.h"
13 #include "clang/AST/OperationKinds.h"
14 #include "clang/AST/ParentMapContext.h"
15 #include "clang/ASTMatchers/ASTMatchFinder.h"
16 #include <math.h>
17
18 using namespace clang::ast_matchers;
19
20 namespace clang::tidy::altera {
21
22 UnrollLoopsCheck::UnrollLoopsCheck(StringRef Name, ClangTidyContext *Context)
23 : ClangTidyCheck(Name, Context),
24 MaxLoopIterations(Options.get("MaxLoopIterations", 100U)) {}
25
26 void UnrollLoopsCheck::registerMatchers(MatchFinder *Finder) {
27 const auto HasLoopBound = hasDescendant(
28 varDecl(allOf(matchesName("__end*"),
29 hasDescendant(integerLiteral().bind("cxx_loop_bound")))));
30 const auto CXXForRangeLoop =
31 cxxForRangeStmt(anyOf(HasLoopBound, unless(HasLoopBound)));
32 const auto AnyLoop = anyOf(forStmt(), whileStmt(), doStmt(), CXXForRangeLoop);
33 Finder->addMatcher(
34 stmt(allOf(AnyLoop, unless(hasDescendant(stmt(AnyLoop))))).bind("loop"),
35 this);
36 }
37
38 void UnrollLoopsCheck::check(const MatchFinder::MatchResult &Result) {
39 const auto *Loop = Result.Nodes.getNodeAs<Stmt>("loop");
40 const auto *CXXLoopBound =
41 Result.Nodes.getNodeAs<IntegerLiteral>("cxx_loop_bound");
42 const ASTContext *Context = Result.Context;
43 switch (unrollType(Loop, Result.Context)) {
44 case NotUnrolled:
45 diag(Loop->getBeginLoc(),
46 "kernel performance could be improved by unrolling this loop with a "
47 "'#pragma unroll' directive");
48 break;
49 case PartiallyUnrolled:
50 // Loop already partially unrolled, do nothing.
51 break;
52 case FullyUnrolled:
53 if (hasKnownBounds(Loop, CXXLoopBound, Context)) {
54 if (hasLargeNumIterations(Loop, CXXLoopBound, Context)) {
55 diag(Loop->getBeginLoc(),
56 "loop likely has a large number of iterations and thus "
57 "cannot be fully unrolled; to partially unroll this loop, use "
58 "the '#pragma unroll <num>' directive");
59 return;
60 }
61 return;
62 }
63 if (isa<WhileStmt, DoStmt>(Loop)) {
64 diag(Loop->getBeginLoc(),
65 "full unrolling requested, but loop bounds may not be known; to "
66 "partially unroll this loop, use the '#pragma unroll <num>' "
67 "directive",
68 DiagnosticIDs::Note);
69 break;
70 }
71 diag(Loop->getBeginLoc(),
72 "full unrolling requested, but loop bounds are not known; to "
73 "partially unroll this loop, use the '#pragma unroll <num>' "
74 "directive");
75 break;
76 }
77 }
78
79 enum UnrollLoopsCheck::UnrollType
80 UnrollLoopsCheck::unrollType(const Stmt *Statement, ASTContext *Context) {
81 const DynTypedNodeList Parents = Context->getParents<Stmt>(*Statement);
82 for (const DynTypedNode &Parent : Parents) {
83 const auto *ParentStmt = Parent.get<AttributedStmt>();
84 if (!ParentStmt)
85 continue;
86 for (const Attr *Attribute : ParentStmt->getAttrs()) {
87 const auto *LoopHint = dyn_cast<LoopHintAttr>(Attribute);
88 if (!LoopHint)
89 continue;
90 switch (LoopHint->getState()) {
91 case LoopHintAttr::Numeric:
92 return PartiallyUnrolled;
93 case LoopHintAttr::Disable:
94 return NotUnrolled;
95 case LoopHintAttr::Full:
96 return FullyUnrolled;
97 case LoopHintAttr::Enable:
98 return FullyUnrolled;
99 case LoopHintAttr::AssumeSafety:
100 return NotUnrolled;
101 case LoopHintAttr::FixedWidth:
102 return NotUnrolled;
103 case LoopHintAttr::ScalableWidth:
104 return NotUnrolled;
105 }
106 }
107 }
108 return NotUnrolled;
109 }
110
111 bool UnrollLoopsCheck::hasKnownBounds(const Stmt *Statement,
112 const IntegerLiteral *CXXLoopBound,
113 const ASTContext *Context) {
114 if (isa<CXXForRangeStmt>(Statement))
115 return CXXLoopBound != nullptr;
116 // Too many possibilities in a while statement, so always recommend partial
117 // unrolling for these.
118 if (isa<WhileStmt, DoStmt>(Statement))
119 return false;
120 // The last loop type is a for loop.
121 const auto *ForLoop = cast<ForStmt>(Statement);
122 const Stmt *Initializer = ForLoop->getInit();
123 const Expr *Conditional = ForLoop->getCond();
124 const Expr *Increment = ForLoop->getInc();
125 if (!Initializer || !Conditional || !Increment)
126 return false;
127 // If the loop variable value isn't known, loop bounds are unknown.
128 if (const auto *InitDeclStatement = dyn_cast<DeclStmt>(Initializer)) {
129 if (const auto *VariableDecl =
130 dyn_cast<VarDecl>(InitDeclStatement->getSingleDecl())) {
131 APValue *Evaluation = VariableDecl->evaluateValue();
132 if (!Evaluation || !Evaluation->hasValue())
133 return false;
134 }
135 }
136 // If increment is unary and not one of ++ and --, loop bounds are unknown.
137 if (const auto *Op = dyn_cast<UnaryOperator>(Increment))
138 if (!Op->isIncrementDecrementOp())
139 return false;
140
141 if (const auto *BinaryOp = dyn_cast<BinaryOperator>(Conditional)) {
142 const Expr *LHS = BinaryOp->getLHS();
143 const Expr *RHS = BinaryOp->getRHS();
144 // If both sides are value dependent or constant, loop bounds are unknown.
145 return LHS->isEvaluatable(*Context) != RHS->isEvaluatable(*Context);
146 }
147 return false; // If it's not a binary operator, loop bounds are unknown.
148 }
149
150 const Expr *UnrollLoopsCheck::getCondExpr(const Stmt *Statement) {
151 if (const auto *ForLoop = dyn_cast<ForStmt>(Statement))
152 return ForLoop->getCond();
153 if (const auto *WhileLoop = dyn_cast<WhileStmt>(Statement))
154 return WhileLoop->getCond();
155 if (const auto *DoWhileLoop = dyn_cast<DoStmt>(Statement))
156 return DoWhileLoop->getCond();
157 if (const auto *CXXRangeLoop = dyn_cast<CXXForRangeStmt>(Statement))
158 return CXXRangeLoop->getCond();
159 llvm_unreachable("Unknown loop");
160 }
161
162 bool UnrollLoopsCheck::hasLargeNumIterations(const Stmt *Statement,
163 const IntegerLiteral *CXXLoopBound,
164 const ASTContext *Context) {
165 // Because hasKnownBounds is called before this, if this is true, then
166 // CXXLoopBound is also matched.
167 if (isa<CXXForRangeStmt>(Statement)) {
168 assert(CXXLoopBound && "CXX ranged for loop has no loop bound");
169 return exprHasLargeNumIterations(CXXLoopBound, Context);
170 }
171 const auto *ForLoop = cast<ForStmt>(Statement);
172 const Stmt *Initializer = ForLoop->getInit();
173 const Expr *Conditional = ForLoop->getCond();
174 const Expr *Increment = ForLoop->getInc();
175 int InitValue;
176 // If the loop variable value isn't known, we can't know the loop bounds.
177 if (const auto *InitDeclStatement = dyn_cast<DeclStmt>(Initializer)) {
178 if (const auto *VariableDecl =
179 dyn_cast<VarDecl>(InitDeclStatement->getSingleDecl())) {
180 APValue *Evaluation = VariableDecl->evaluateValue();
181 if (!Evaluation || !Evaluation->isInt())
182 return true;
183 InitValue = Evaluation->getInt().getExtValue();
184 }
185 }
186
187 int EndValue;
188 const auto *BinaryOp = cast<BinaryOperator>(Conditional);
189 if (!extractValue(EndValue, BinaryOp, Context))
190 return true;
191
192 double Iterations;
193
194 // If increment is unary and not one of ++, --, we can't know the loop bounds.
195 if (const auto *Op = dyn_cast<UnaryOperator>(Increment)) {
196 if (Op->isIncrementOp())
197 Iterations = EndValue - InitValue;
198 else if (Op->isDecrementOp())
199 Iterations = InitValue - EndValue;
200 else
201 llvm_unreachable("Unary operator neither increment nor decrement");
202 }
203
204 // If increment is binary and not one of +, -, *, /, we can't know the loop
205 // bounds.
206 if (const auto *Op = dyn_cast<BinaryOperator>(Increment)) {
207 int ConstantValue;
208 if (!extractValue(ConstantValue, Op, Context))
209 return true;
210 switch (Op->getOpcode()) {
211 case (BO_AddAssign):
212 Iterations = ceil(float(EndValue - InitValue) / ConstantValue);
213 break;
214 case (BO_SubAssign):
215 Iterations = ceil(float(InitValue - EndValue) / ConstantValue);
216 break;
217 case (BO_MulAssign):
218 Iterations = 1 + (log(EndValue) - log(InitValue)) / log(ConstantValue);
219 break;
220 case (BO_DivAssign):
221 Iterations = 1 + (log(InitValue) - log(EndValue)) / log(ConstantValue);
222 break;
223 default:
224 // All other operators are not handled; assume large bounds.
225 return true;
226 }
227 }
228 return Iterations > MaxLoopIterations;
229 }
230
231 bool UnrollLoopsCheck::extractValue(int &Value, const BinaryOperator *Op,
232 const ASTContext *Context) {
233 const Expr *LHS = Op->getLHS();
234 const Expr *RHS = Op->getRHS();
235 Expr::EvalResult Result;
236 if (LHS->isEvaluatable(*Context))
237 LHS->EvaluateAsRValue(Result, *Context);
238 else if (RHS->isEvaluatable(*Context))
239 RHS->EvaluateAsRValue(Result, *Context);
240 else
241 return false; // Cannot evaluate either side.
242 if (!Result.Val.isInt())
243 return false; // Cannot check number of iterations, return false to be
244 // safe.
245 Value = Result.Val.getInt().getExtValue();
246 return true;
247 }
248
249 bool UnrollLoopsCheck::exprHasLargeNumIterations(const Expr *Expression,
250 const ASTContext *Context) {
251 Expr::EvalResult Result;
252 if (Expression->EvaluateAsRValue(Result, *Context)) {
253 if (!Result.Val.isInt())
254 return false; // Cannot check number of iterations, return false to be
255 // safe.
256 // The following assumes values go from 0 to Val in increments of 1.
257 return Result.Val.getInt() > MaxLoopIterations;
258 }
259 // Cannot evaluate Expression as an r-value, so cannot check number of
260 // iterations.
261 return false;
262 }
263
264 void UnrollLoopsCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
265 Options.store(Opts, "MaxLoopIterations", MaxLoopIterations);
266 }
267
268 } // namespace clang::tidy::altera