clang-tools  15.0.0git
UnrollLoopsCheck.cpp
Go to the documentation of this file.
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 = dyn_cast<DeclStmt>(Initializer)) {
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 = dyn_cast<UnaryOperator>(Increment))
140  if (!Op->isIncrementDecrementOp())
141  return false;
142 
143  if (const auto *BinaryOp = dyn_cast<BinaryOperator>(Conditional)) {
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");
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");
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 = dyn_cast<DeclStmt>(Initializer)) {
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 = dyn_cast<UnaryOperator>(Increment)) {
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");
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
clang::tidy::ClangTidyOptions::OptionMap
llvm::StringMap< ClangTidyValue > OptionMap
Definition: ClangTidyOptions.h:115
clang::tidy::altera::UnrollLoopsCheck::registerMatchers
void registerMatchers(ast_matchers::MatchFinder *Finder) override
Override this to register AST matchers with Finder.
Definition: UnrollLoopsCheck.cpp:28
clang::tidy::ClangTidyCheck
Base class for all clang-tidy checks.
Definition: ClangTidyCheck.h:53
clang::ast_matchers
Definition: AbseilMatcher.h:14
clang::tidy::ClangTidyCheck::Options
OptionsView Options
Definition: ClangTidyCheck.h:415
clang::tidy::ClangTidyContext
Every ClangTidyCheck reports errors through a DiagnosticsEngine provided by this context.
Definition: ClangTidyDiagnosticConsumer.h:67
clang::tidy::altera::UnrollLoopsCheck::check
void check(const ast_matchers::MatchFinder::MatchResult &Result) override
ClangTidyChecks that register ASTMatchers should do the actual work in here.
Definition: UnrollLoopsCheck.cpp:40
clang::tidy::ClangTidyCheck::diag
DiagnosticBuilder diag(SourceLocation Loc, StringRef Description, DiagnosticIDs::Level Level=DiagnosticIDs::Warning)
Add a diagnostic with the check's name.
Definition: ClangTidyCheck.cpp:25
Name
Token Name
Definition: MacroToEnumCheck.cpp:89
Parent
const Node * Parent
Definition: ExtractFunction.cpp:157
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
clang::tidy::ClangTidyCheck::OptionsView::store
void store(ClangTidyOptions::OptionMap &Options, StringRef LocalName, StringRef Value) const
Stores an option with the check-local name LocalName with string value Value to Options.
Definition: ClangTidyCheck.cpp:129
clang::clangd::detail::log
void log(Logger::Level L, const char *Fmt, Ts &&... Vals)
Definition: Logger.h:47
UnrollLoopsCheck.h