Bug Summary

File:build/source/clang-tools-extra/clang-tidy/altera/UnrollLoopsCheck.cpp
Warning:line 196, 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/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//===--- 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(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
37void 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 // Loop already partially unrolled, do nothing.
50 break;
51 case FullyUnrolled:
52 if (hasKnownBounds(Loop, CXXLoopBound, Context)) {
2
←
Calling 'UnrollLoopsCheck::hasKnownBounds'
→
20
←
Returning from 'UnrollLoopsCheck::hasKnownBounds'
→
21
←
Taking true branch
→
53 if (hasLargeNumIterations(Loop, CXXLoopBound, Context)) {
22
←
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
78enum UnrollLoopsCheck::UnrollType
79UnrollLoopsCheck::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
110bool 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'
→
4
←
Taking false branch
→
114 return CXXLoopBound != nullptr;
115 // Too many possibilities in a while statement, so always recommend partial
116 // unrolling for these.
117 if (isa<WhileStmt, DoStmt>(Statement))
5
←
Assuming 'Statement' is neither a 'WhileStmt' nor a 'DoStmt'
→
6
←
Taking false branch
→
118 return false;
119 // The last loop type is a for loop.
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
→
11
←
Taking false branch
→
125 return false;
126 // If the loop variable value isn't known, loop bounds are unknown.
127 if (const auto *InitDeclStatement
12.1
'InitDeclStatement' is null
 = dyn_cast<DeclStmt>(Initializer)) {
12
←
Assuming 'Initializer' is not a 'CastReturnType'
→
13
←
Taking false branch
→
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 // If increment is unary and not one of ++ and --, loop bounds are unknown.
136 if (const auto *Op
14.1
'Op' is non-null
 = dyn_cast<UnaryOperator>(Increment))
14
←
Assuming 'Increment' is a 'CastReturnType'
→
15
←
Taking true branch
→
137 if (!Op->isIncrementDecrementOp())
16
←
Taking false branch
→
138 return false;
139
140 if (const auto *BinaryOp
17.1
'BinaryOp' is non-null
 = dyn_cast<BinaryOperator>(Conditional)) {
17
←
Assuming 'Conditional' is a 'CastReturnType'
→
18
←
Taking true branch
→
141 const Expr *LHS = BinaryOp->getLHS();
142 const Expr *RHS = BinaryOp->getRHS();
143 // If both sides are value dependent or constant, loop bounds are unknown.
144 return LHS->isEvaluatable(*Context) != RHS->isEvaluatable(*Context);
19
←
Assuming the condition is true
→
145 }
146 return false; // If it's not a binary operator, loop bounds are unknown.
147}
148
149const 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")::llvm::llvm_unreachable_internal("Unknown loop", "clang-tools-extra/clang-tidy/altera/UnrollLoopsCheck.cpp"
, 158);
159}
160
161bool UnrollLoopsCheck::hasLargeNumIterations(const Stmt *Statement,
162 const IntegerLiteral *CXXLoopBound,
163 const ASTContext *Context) {
164 // Because hasKnownBounds is called before this, if this is true, then
165 // CXXLoopBound is also matched.
166 if (isa<CXXForRangeStmt>(Statement)) {
23
←
Assuming 'Statement' is not a 'CXXForRangeStmt'
→
24
←
Taking false branch
→
167 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",
167, __extension__ __PRETTY_FUNCTION__));
168 return exprHasLargeNumIterations(CXXLoopBound, Context);
169 }
170 const auto *ForLoop = cast<ForStmt>(Statement);
25
←
'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;
26
←
'InitValue' declared without an initial value
→
175 // If the loop variable value isn't known, we can't know the loop bounds.
176 if (const auto *InitDeclStatement
27.1
'InitDeclStatement' is null
 = dyn_cast<DeclStmt>(Initializer)) {
27
←
'Initializer' is not a 'DeclStmt'
→
28
←
Taking false branch
→
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);
29
←
'Conditional' is a 'BinaryOperator'
→
188 if (!extractValue(EndValue, BinaryOp, Context))
30
←
Taking false branch
→
189 return true;
190
191 double Iterations;
192
193 // If increment is unary and not one of ++, --, we can't know the loop bounds.
194 if (const auto *Op
31.1
'Op' is non-null
 = dyn_cast<UnaryOperator>(Increment)) {
31
←
'Increment' is a 'UnaryOperator'
→
32
←
Taking true branch
→
195 if (Op->isIncrementOp())
33
←
Taking true branch
→
196 Iterations = EndValue - InitValue;
34
←
The right operand of '-' is a garbage value
197 else if (Op->isDecrementOp())
198 Iterations = InitValue - EndValue;
199 else
200 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",
200);
201 }
202
203 // If increment is binary and not one of +, -, *, /, we can't know the loop
204 // bounds.
205 if (const auto *Op = dyn_cast<BinaryOperator>(Increment)) {
206 int ConstantValue;
207 if (!extractValue(ConstantValue, Op, Context))
208 return true;
209 switch (Op->getOpcode()) {
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);
218 break;
219 case (BO_DivAssign):
220 Iterations = 1 + (log(InitValue) - log(EndValue)) / log(ConstantValue);
221 break;
222 default:
223 // All other operators are not handled; assume large bounds.
224 return true;
225 }
226 }
227 return Iterations > MaxLoopIterations;
228}
229
230bool 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; // Cannot evaluate either side.
241 if (!Result.Val.isInt())
242 return false; // Cannot check number of iterations, return false to be
243 // safe.
244 Value = Result.Val.getInt().getExtValue();
245 return true;
246}
247
248bool 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; // Cannot check number of iterations, return false to be
254 // safe.
255 // The following assumes values go from 0 to Val in increments of 1.
256 return Result.Val.getInt() > MaxLoopIterations;
257 }
258 // Cannot evaluate Expression as an r-value, so cannot check number of
259 // iterations.
260 return false;
261}
262
263void UnrollLoopsCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
264 Options.store(Opts, "MaxLoopIterations", MaxLoopIterations);
265}
266
267} // namespace clang::tidy::altera