Bug Summary

File:build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/clang-tools-extra/clang-tidy/altera/UnrollLoopsCheck.cpp
Warning:line 199, column 29
The right operand of '-' is a garbage value

Annotated Source Code

Press '?' to see keyboard shortcuts

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/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-16/lib/clang/16.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I tools/clang/tools/extra/clang-tidy/altera -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/clang-tools-extra/clang-tidy/altera -I tools/clang/tools/extra/clang-tidy -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/clang/include -I tools/clang/include -I include -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/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-16/lib/clang/16.0.0/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/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -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/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -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-2022-10-03-140002-15933-1 -x c++ /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/clang-tools-extra/clang-tidy/altera/UnrollLoopsCheck.cpp
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
18using namespace clang::ast_matchers;
19
20namespace clang {
21namespace tidy {
22namespace altera {
23
24UnrollLoopsCheck::UnrollLoopsCheck(StringRef Name, ClangTidyContext *Context)
25 : ClangTidyCheck(Name, Context),
26 MaxLoopIterations(Options.get("MaxLoopIterations", 100U)) {}
27
28void 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
40void 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)) {
1
Control jumps to 'case FullyUnrolled:' at line 54
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)) {
2
Calling 'UnrollLoopsCheck::hasKnownBounds'
20
Returning from 'UnrollLoopsCheck::hasKnownBounds'
21
Taking true branch
56 if (hasLargeNumIterations(Loop, CXXLoopBound, Context)) {
22
Calling 'UnrollLoopsCheck::hasLargeNumIterations'
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
81enum UnrollLoopsCheck::UnrollType
82UnrollLoopsCheck::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
113bool UnrollLoopsCheck::hasKnownBounds(const Stmt *Statement,
114 const IntegerLiteral *CXXLoopBound,
115 const ASTContext *Context) {
116 if (isa<CXXForRangeStmt>(Statement))
3
Assuming 'Statement' is not a 'CXXForRangeStmt'
4
Taking false branch
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))
5
Assuming 'Statement' is neither a 'WhileStmt' nor a 'DoStmt'
6
Taking false branch
121 return false;
122 // The last loop type is a for loop.
123 const auto *ForLoop = cast<ForStmt>(Statement);
7
'Statement' is a 'CastReturnType'
124 const Stmt *Initializer = ForLoop->getInit();
125 const Expr *Conditional = ForLoop->getCond();
126 const Expr *Increment = ForLoop->getInc();
127 if (!Initializer || !Conditional || !Increment)
8
Assuming 'Initializer' is non-null
9
Assuming 'Conditional' is non-null
10
Assuming 'Increment' is non-null
11
Taking false branch
128 return false;
129 // If the loop variable value isn't known, loop bounds are unknown.
130 if (const auto *InitDeclStatement
12.1
'InitDeclStatement' is null
= dyn_cast<DeclStmt>(Initializer)) {
12
Assuming 'Initializer' is not a 'CastReturnType'
13
Taking false branch
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
14.1
'Op' is non-null
= dyn_cast<UnaryOperator>(Increment))
14
Assuming 'Increment' is a 'CastReturnType'
15
Taking true branch
140 if (!Op->isIncrementDecrementOp())
16
Taking false branch
141 return false;
142
143 if (const auto *BinaryOp
17.1
'BinaryOp' is non-null
= dyn_cast<BinaryOperator>(Conditional)) {
17
Assuming 'Conditional' is a 'CastReturnType'
18
Taking true branch
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);
19
Assuming the condition is true
148 }
149 return false; // If it's not a binary operator, loop bounds are unknown.
150}
151
152const 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
164bool 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)) {
23
Assuming 'Statement' is not a 'CXXForRangeStmt'
24
Taking false branch
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);
25
'Statement' is a 'ForStmt'
174 const Stmt *Initializer = ForLoop->getInit();
175 const Expr *Conditional = ForLoop->getCond();
176 const Expr *Increment = ForLoop->getInc();
177 int InitValue;
26
'InitValue' declared without an initial value
178 // If the loop variable value isn't known, we can't know the loop bounds.
179 if (const auto *InitDeclStatement
27.1
'InitDeclStatement' is null
= dyn_cast<DeclStmt>(Initializer)) {
27
'Initializer' is not a 'DeclStmt'
28
Taking false branch
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);
29
'Conditional' is a 'BinaryOperator'
191 if (!extractValue(EndValue, BinaryOp, Context))
30
Taking false branch
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
31.1
'Op' is non-null
= dyn_cast<UnaryOperator>(Increment)) {
31
'Increment' is a 'UnaryOperator'
32
Taking true branch
198 if (Op->isIncrementOp())
33
Taking true branch
199 Iterations = EndValue - InitValue;
34
The right operand of '-' is a garbage value
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
233bool 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
251bool 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
266void UnrollLoopsCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
267 Options.store(Opts, "MaxLoopIterations", MaxLoopIterations);
268}
269
270} // namespace altera
271} // namespace tidy
272} // namespace clang