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