clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name UnrollLoopsCheck.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -relaxed-aliasing -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-17/lib/clang/17 -D CLANG_REPOSITORY_STRING="++20230510111145+7df43bdb42ae-1~exp1~20230510111303.1288" -D _DEBUG -D _GLIBCXX_ASSERTIONS -D _GNU_SOURCE -D _LIBCPP_ENABLE_ASSERTIONS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I tools/clang/tools/extra/clang-tidy/altera -I /build/source/clang-tools-extra/clang-tidy/altera -I tools/clang/tools/extra/clang-tidy -I /build/source/clang/include -I tools/clang/include -I include -I /build/source/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-17/lib/clang/17/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/source/= -source-date-epoch 1683717183 -O2 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2023-05-10-133810-16478-1 -x c++ /build/source/clang-tools-extra/clang-tidy/altera/UnrollLoopsCheck.cpp
1 | |
2 | |
3 | |
4 | |
5 | |
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(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(AnyLoop, unless(hasDescendant(stmt(AnyLoop)))).bind("loop"), this); |
35 | } |
36 | |
37 | void UnrollLoopsCheck::check(const MatchFinder::MatchResult &Result) { |
38 | const auto *Loop = Result.Nodes.getNodeAs<Stmt>("loop"); |
39 | const auto *CXXLoopBound = |
40 | Result.Nodes.getNodeAs<IntegerLiteral>("cxx_loop_bound"); |
41 | const ASTContext *Context = Result.Context; |
42 | switch (unrollType(Loop, Result.Context)) { |
| 1 | Control jumps to 'case FullyUnrolled:' at line 51 | |
|
43 | case NotUnrolled: |
44 | diag(Loop->getBeginLoc(), |
45 | "kernel performance could be improved by unrolling this loop with a " |
46 | "'#pragma unroll' directive"); |
47 | break; |
48 | case PartiallyUnrolled: |
49 | |
50 | break; |
51 | case FullyUnrolled: |
52 | if (hasKnownBounds(Loop, CXXLoopBound, Context)) { |
| 2 | | Calling 'UnrollLoopsCheck::hasKnownBounds' | |
|
| 19 | | Returning from 'UnrollLoopsCheck::hasKnownBounds' | |
|
| |
53 | if (hasLargeNumIterations(Loop, CXXLoopBound, Context)) { |
| 21 | | Calling 'UnrollLoopsCheck::hasLargeNumIterations' | |
|
54 | diag(Loop->getBeginLoc(), |
55 | "loop likely has a large number of iterations and thus " |
56 | "cannot be fully unrolled; to partially unroll this loop, use " |
57 | "the '#pragma unroll <num>' directive"); |
58 | return; |
59 | } |
60 | return; |
61 | } |
62 | if (isa<WhileStmt, DoStmt>(Loop)) { |
63 | diag(Loop->getBeginLoc(), |
64 | "full unrolling requested, but loop bounds may not be known; to " |
65 | "partially unroll this loop, use the '#pragma unroll <num>' " |
66 | "directive", |
67 | DiagnosticIDs::Note); |
68 | break; |
69 | } |
70 | diag(Loop->getBeginLoc(), |
71 | "full unrolling requested, but loop bounds are not known; to " |
72 | "partially unroll this loop, use the '#pragma unroll <num>' " |
73 | "directive"); |
74 | break; |
75 | } |
76 | } |
77 | |
78 | enum UnrollLoopsCheck::UnrollType |
79 | UnrollLoopsCheck::unrollType(const Stmt *Statement, ASTContext *Context) { |
80 | const DynTypedNodeList Parents = Context->getParents<Stmt>(*Statement); |
81 | for (const DynTypedNode &Parent : Parents) { |
82 | const auto *ParentStmt = Parent.get<AttributedStmt>(); |
83 | if (!ParentStmt) |
84 | continue; |
85 | for (const Attr *Attribute : ParentStmt->getAttrs()) { |
86 | const auto *LoopHint = dyn_cast<LoopHintAttr>(Attribute); |
87 | if (!LoopHint) |
88 | continue; |
89 | switch (LoopHint->getState()) { |
90 | case LoopHintAttr::Numeric: |
91 | return PartiallyUnrolled; |
92 | case LoopHintAttr::Disable: |
93 | return NotUnrolled; |
94 | case LoopHintAttr::Full: |
95 | return FullyUnrolled; |
96 | case LoopHintAttr::Enable: |
97 | return FullyUnrolled; |
98 | case LoopHintAttr::AssumeSafety: |
99 | return NotUnrolled; |
100 | case LoopHintAttr::FixedWidth: |
101 | return NotUnrolled; |
102 | case LoopHintAttr::ScalableWidth: |
103 | return NotUnrolled; |
104 | } |
105 | } |
106 | } |
107 | return NotUnrolled; |
108 | } |
109 | |
110 | bool UnrollLoopsCheck::hasKnownBounds(const Stmt *Statement, |
111 | const IntegerLiteral *CXXLoopBound, |
112 | const ASTContext *Context) { |
113 | if (isa<CXXForRangeStmt>(Statement)) |
| 3 | | Assuming 'Statement' is not a 'CXXForRangeStmt' | |
|
| |
114 | return CXXLoopBound != nullptr; |
115 | |
116 | |
117 | if (isa<WhileStmt, DoStmt>(Statement)) |
| 5 | | Assuming 'Statement' is neither a 'WhileStmt' nor a 'DoStmt' | |
|
| |
118 | return false; |
119 | |
120 | const auto *ForLoop = cast<ForStmt>(Statement); |
| 7 | | 'Statement' is a 'CastReturnType' | |
|
121 | const Stmt *Initializer = ForLoop->getInit(); |
122 | const Expr *Conditional = ForLoop->getCond(); |
123 | const Expr *Increment = ForLoop->getInc(); |
124 | if (!Initializer || !Conditional || !Increment) |
| 8 | | Assuming 'Initializer' is non-null | |
|
| 9 | | Assuming 'Conditional' is non-null | |
|
| 10 | | Assuming 'Increment' is non-null | |
|
| |
125 | return false; |
126 | |
127 | if (const auto *InitDeclStatement = dyn_cast<DeclStmt>(Initializer)) { |
| 12 | | Assuming 'Initializer' is not a 'CastReturnType' | |
|
| |
128 | if (const auto *VariableDecl = |
129 | dyn_cast<VarDecl>(InitDeclStatement->getSingleDecl())) { |
130 | APValue *Evaluation = VariableDecl->evaluateValue(); |
131 | if (!Evaluation || !Evaluation->hasValue()) |
132 | return false; |
133 | } |
134 | } |
135 | |
136 | if (const auto *Op = dyn_cast<UnaryOperator>(Increment)) |
| 14 | | Assuming 'Increment' is not a 'CastReturnType' | |
|
| |
137 | if (!Op->isIncrementDecrementOp()) |
138 | return false; |
139 | |
140 | if (const auto *BinaryOp = dyn_cast<BinaryOperator>(Conditional)) { |
| 16 | | Assuming 'Conditional' is a 'CastReturnType' | |
|
| |
141 | const Expr *LHS = BinaryOp->getLHS(); |
142 | const Expr *RHS = BinaryOp->getRHS(); |
143 | |
144 | return LHS->isEvaluatable(*Context) != RHS->isEvaluatable(*Context); |
| 18 | | Assuming the condition is true | |
|
145 | } |
146 | return false; |
147 | } |
148 | |
149 | const Expr *UnrollLoopsCheck::getCondExpr(const Stmt *Statement) { |
150 | if (const auto *ForLoop = dyn_cast<ForStmt>(Statement)) |
151 | return ForLoop->getCond(); |
152 | if (const auto *WhileLoop = dyn_cast<WhileStmt>(Statement)) |
153 | return WhileLoop->getCond(); |
154 | if (const auto *DoWhileLoop = dyn_cast<DoStmt>(Statement)) |
155 | return DoWhileLoop->getCond(); |
156 | if (const auto *CXXRangeLoop = dyn_cast<CXXForRangeStmt>(Statement)) |
157 | return CXXRangeLoop->getCond(); |
158 | llvm_unreachable("Unknown loop"); |
159 | } |
160 | |
161 | bool UnrollLoopsCheck::hasLargeNumIterations(const Stmt *Statement, |
162 | const IntegerLiteral *CXXLoopBound, |
163 | const ASTContext *Context) { |
164 | |
165 | |
166 | if (isa<CXXForRangeStmt>(Statement)) { |
| 22 | | Assuming 'Statement' is not a 'CXXForRangeStmt' | |
|
| |
167 | assert(CXXLoopBound && "CXX ranged for loop has no loop bound"); |
168 | return exprHasLargeNumIterations(CXXLoopBound, Context); |
169 | } |
170 | const auto *ForLoop = cast<ForStmt>(Statement); |
| 24 | | 'Statement' is a 'ForStmt' | |
|
171 | const Stmt *Initializer = ForLoop->getInit(); |
172 | const Expr *Conditional = ForLoop->getCond(); |
173 | const Expr *Increment = ForLoop->getInc(); |
174 | int InitValue; |
| 25 | | 'InitValue' declared without an initial value | |
|
175 | |
176 | if (const auto *InitDeclStatement = dyn_cast<DeclStmt>(Initializer)) { |
| 26 | | 'Initializer' is not a 'DeclStmt' | |
|
| |
177 | if (const auto *VariableDecl = |
178 | dyn_cast<VarDecl>(InitDeclStatement->getSingleDecl())) { |
179 | APValue *Evaluation = VariableDecl->evaluateValue(); |
180 | if (!Evaluation || !Evaluation->isInt()) |
181 | return true; |
182 | InitValue = Evaluation->getInt().getExtValue(); |
183 | } |
184 | } |
185 | |
186 | int EndValue; |
187 | const auto *BinaryOp = cast<BinaryOperator>(Conditional); |
| 28 | | 'Conditional' is a 'BinaryOperator' | |
|
188 | if (!extractValue(EndValue, BinaryOp, Context)) |
| |
189 | return true; |
190 | |
191 | double Iterations; |
192 | |
193 | |
194 | if (const auto *Op = dyn_cast<UnaryOperator>(Increment)) { |
| 30 | | 'Increment' is not a 'UnaryOperator' | |
|
| |
195 | if (Op->isIncrementOp()) |
196 | Iterations = EndValue - InitValue; |
197 | else if (Op->isDecrementOp()) |
198 | Iterations = InitValue - EndValue; |
199 | else |
200 | llvm_unreachable("Unary operator neither increment nor decrement"); |
201 | } |
202 | |
203 | |
204 | |
205 | if (const auto *Op = dyn_cast<BinaryOperator>(Increment)) { |
| 32 | | Assuming 'Increment' is a 'CastReturnType' | |
|
| |
206 | int ConstantValue; |
207 | if (!extractValue(ConstantValue, Op, Context)) |
| |
208 | return true; |
209 | switch (Op->getOpcode()) { |
| 35 | | Control jumps to 'case BO_MulAssign:' at line 216 | |
|
210 | case (BO_AddAssign): |
211 | Iterations = ceil(float(EndValue - InitValue) / ConstantValue); |
212 | break; |
213 | case (BO_SubAssign): |
214 | Iterations = ceil(float(InitValue - EndValue) / ConstantValue); |
215 | break; |
216 | case (BO_MulAssign): |
217 | Iterations = 1 + (log(EndValue) - log(InitValue)) / log(ConstantValue); |
| 36 | | 1st function call argument is an uninitialized value |
|
218 | break; |
219 | case (BO_DivAssign): |
220 | Iterations = 1 + (log(InitValue) - log(EndValue)) / log(ConstantValue); |
221 | break; |
222 | default: |
223 | |
224 | return true; |
225 | } |
226 | } |
227 | return Iterations > MaxLoopIterations; |
228 | } |
229 | |
230 | bool UnrollLoopsCheck::extractValue(int &Value, const BinaryOperator *Op, |
231 | const ASTContext *Context) { |
232 | const Expr *LHS = Op->getLHS(); |
233 | const Expr *RHS = Op->getRHS(); |
234 | Expr::EvalResult Result; |
235 | if (LHS->isEvaluatable(*Context)) |
236 | LHS->EvaluateAsRValue(Result, *Context); |
237 | else if (RHS->isEvaluatable(*Context)) |
238 | RHS->EvaluateAsRValue(Result, *Context); |
239 | else |
240 | return false; |
241 | if (!Result.Val.isInt()) |
242 | return false; |
243 | |
244 | Value = Result.Val.getInt().getExtValue(); |
245 | return true; |
246 | } |
247 | |
248 | bool UnrollLoopsCheck::exprHasLargeNumIterations(const Expr *Expression, |
249 | const ASTContext *Context) { |
250 | Expr::EvalResult Result; |
251 | if (Expression->EvaluateAsRValue(Result, *Context)) { |
252 | if (!Result.Val.isInt()) |
253 | return false; |
254 | |
255 | |
256 | return Result.Val.getInt() > MaxLoopIterations; |
257 | } |
258 | |
259 | |
260 | return false; |
261 | } |
262 | |
263 | void UnrollLoopsCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) { |
264 | Options.store(Opts, "MaxLoopIterations", MaxLoopIterations); |
265 | } |
266 | |
267 | } |