Bug Summary

File:build/source/clang-tools-extra/clang-tidy/altera/UnrollLoopsCheck.cpp
Warning:line 199, column 30
The left 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/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-17/lib/clang/17 -D CLANG_REPOSITORY_STRING="++20230322120329+2b21327fee50-1~exp1~20230322000449.1178" -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 1679443490 -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-03-22-005342-16304-1 -x c++ /build/source/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::tidy::altera {
21
22UnrollLoopsCheck::UnrollLoopsCheck(StringRef Name, ClangTidyContext *Context)
23 : ClangTidyCheck(Name, Context),
24 MaxLoopIterations(Options.get("MaxLoopIterations", 100U)) {}
25
26void 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
38void 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)) {
1
Control jumps to 'case FullyUnrolled:' at line 52
→
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)) {
2
←
Calling 'UnrollLoopsCheck::hasKnownBounds'
→
20
←
Returning from 'UnrollLoopsCheck::hasKnownBounds'
→
21
←
Taking true branch
→
54 if (hasLargeNumIterations(Loop, CXXLoopBound, Context)) {
22
←
Calling 'UnrollLoopsCheck::hasLargeNumIterations'
→
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
79enum UnrollLoopsCheck::UnrollType
80UnrollLoopsCheck::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
111bool UnrollLoopsCheck::hasKnownBounds(const Stmt *Statement,
112 const IntegerLiteral *CXXLoopBound,
113 const ASTContext *Context) {
114 if (isa<CXXForRangeStmt>(Statement))
3
←
Assuming 'Statement' is not a 'CXXForRangeStmt'
→
4
←
Taking false branch
→
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))
5
←
Assuming 'Statement' is neither a 'WhileStmt' nor a 'DoStmt'
→
6
←
Taking false branch
→
119 return false;
120 // The last loop type is a for loop.
121 const auto *ForLoop = cast<ForStmt>(Statement);
7
←
'Statement' is a 'CastReturnType'
→
122 const Stmt *Initializer = ForLoop->getInit();
123 const Expr *Conditional = ForLoop->getCond();
124 const Expr *Increment = ForLoop->getInc();
125 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
→
126 return false;
127 // If the loop variable value isn't known, loop bounds are unknown.
128 if (const auto *InitDeclStatement
12.1
'InitDeclStatement' is null
 = dyn_cast<DeclStmt>(Initializer)) {
12
←
Assuming 'Initializer' is not a 'CastReturnType'
→
13
←
Taking false branch
→
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
14.1
'Op' is non-null
 = dyn_cast<UnaryOperator>(Increment))
14
←
Assuming 'Increment' is a 'CastReturnType'
→
15
←
Taking true branch
→
138 if (!Op->isIncrementDecrementOp())
16
←
Taking false branch
→
139 return false;
140
141 if (const auto *BinaryOp
17.1
'BinaryOp' is non-null
 = dyn_cast<BinaryOperator>(Conditional)) {
17
←
Assuming 'Conditional' is a 'CastReturnType'
→
18
←
Taking true branch
→
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);
19
←
Assuming the condition is true
→
146 }
147 return false; // If it's not a binary operator, loop bounds are unknown.
148}
149
150const 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")::llvm::llvm_unreachable_internal("Unknown loop", "clang-tools-extra/clang-tidy/altera/UnrollLoopsCheck.cpp"
, 159);
160}
161
162bool 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)) {
23
←
Assuming 'Statement' is not a 'CXXForRangeStmt'
→
24
←
Taking false branch
→
168 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",
168, __extension__ __PRETTY_FUNCTION__));
169 return exprHasLargeNumIterations(CXXLoopBound, Context);
170 }
171 const auto *ForLoop = cast<ForStmt>(Statement);
25
←
'Statement' is a 'ForStmt'
→
172 const Stmt *Initializer = ForLoop->getInit();
173 const Expr *Conditional = ForLoop->getCond();
174 const Expr *Increment = ForLoop->getInc();
175 int InitValue;
26
←
'InitValue' declared without an initial value
→
176 // If the loop variable value isn't known, we can't know the loop bounds.
177 if (const auto *InitDeclStatement
27.1
'InitDeclStatement' is null
 = dyn_cast<DeclStmt>(Initializer)) {
27
←
'Initializer' is not a 'DeclStmt'
→
28
←
Taking false branch
→
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);
29
←
'Conditional' is a 'BinaryOperator'
→
189 if (!extractValue(EndValue, BinaryOp, Context))
30
←
Taking false branch
→
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
31.1
'Op' is non-null
 = dyn_cast<UnaryOperator>(Increment)) {
31
←
'Increment' is a 'UnaryOperator'
→
32
←
Taking true branch
→
196 if (Op->isIncrementOp())
33
←
Taking false branch
→
197 Iterations = EndValue - InitValue;
198 else if (Op->isDecrementOp())
34
←
Taking true branch
→
199 Iterations = InitValue - EndValue;
35
←
The left operand of '-' is a garbage value
200 else
201 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",
201);
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
231bool 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
249bool 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
264void UnrollLoopsCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
265 Options.store(Opts, "MaxLoopIterations", MaxLoopIterations);
266}
267
268} // namespace clang::tidy::altera