clang-tools  15.0.0git
IdDependentBackwardBranchCheck.cpp
Go to the documentation of this file.
1 //===--- IdDependentBackwardBranchCheck.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 
10 #include "clang/AST/ASTContext.h"
11 #include "clang/ASTMatchers/ASTMatchFinder.h"
12 
13 using namespace clang::ast_matchers;
14 
15 namespace clang {
16 namespace tidy {
17 namespace altera {
18 
19 void IdDependentBackwardBranchCheck::registerMatchers(MatchFinder *Finder) {
20  // Prototype to identify all variables which hold a thread-variant ID.
21  // First Matcher just finds all the direct assignments of either ID call.
22  const auto ThreadID = expr(hasDescendant(callExpr(callee(functionDecl(
23  anyOf(hasName("get_global_id"), hasName("get_local_id")))))));
24 
25  const auto RefVarOrField = forEachDescendant(
26  stmt(anyOf(declRefExpr(to(varDecl())).bind("assign_ref_var"),
27  memberExpr(member(fieldDecl())).bind("assign_ref_field"))));
28 
29  Finder->addMatcher(
30  compoundStmt(
31  // Bind on actual get_local/global_id calls.
32  forEachDescendant(
33  stmt(
34  anyOf(declStmt(hasDescendant(varDecl(hasInitializer(ThreadID))
35  .bind("tid_dep_var"))),
36  binaryOperator(allOf(
37  isAssignmentOperator(), hasRHS(ThreadID),
38  hasLHS(anyOf(
39  declRefExpr(to(varDecl().bind("tid_dep_var"))),
40  memberExpr(member(
41  fieldDecl().bind("tid_dep_field")))))))))
42  .bind("straight_assignment"))),
43  this);
44 
45  // Bind all VarDecls that include an initializer with a variable DeclRefExpr
46  // (in case it is ID-dependent).
47  Finder->addMatcher(
48  stmt(forEachDescendant(
49  varDecl(hasInitializer(RefVarOrField)).bind("pot_tid_var"))),
50  this);
51 
52  // Bind all VarDecls that are assigned a value with a variable DeclRefExpr (in
53  // case it is ID-dependent).
54  Finder->addMatcher(
55  stmt(forEachDescendant(binaryOperator(
56  allOf(isAssignmentOperator(), hasRHS(RefVarOrField),
57  hasLHS(anyOf(
58  declRefExpr(to(varDecl().bind("pot_tid_var"))),
59  memberExpr(member(fieldDecl().bind("pot_tid_field"))))))))),
60  this);
61 
62  // Second Matcher looks for branch statements inside of loops and bind on the
63  // condition expression IF it either calls an ID function or has a variable
64  // DeclRefExpr. DeclRefExprs are checked later to confirm whether the variable
65  // is ID-dependent.
66  const auto CondExpr =
67  expr(anyOf(hasDescendant(callExpr(callee(functionDecl(
68  anyOf(hasName("get_global_id"),
69  hasName("get_local_id")))))
70  .bind("id_call")),
71  hasDescendant(stmt(anyOf(declRefExpr(to(varDecl())),
72  memberExpr(member(fieldDecl())))))))
73  .bind("cond_expr");
74  Finder->addMatcher(stmt(anyOf(forStmt(hasCondition(CondExpr)),
75  doStmt(hasCondition(CondExpr)),
76  whileStmt(hasCondition(CondExpr))))
77  .bind("backward_branch"),
78  this);
79 }
80 
81 IdDependentBackwardBranchCheck::IdDependencyRecord *
82 IdDependentBackwardBranchCheck::hasIdDepVar(const Expr *Expression) {
83  if (const auto *Declaration = dyn_cast<DeclRefExpr>(Expression)) {
84  // It is a DeclRefExpr, so check if it's an ID-dependent variable.
85  const auto *CheckVariable = dyn_cast<VarDecl>(Declaration->getDecl());
86  auto FoundVariable = IdDepVarsMap.find(CheckVariable);
87  if (FoundVariable == IdDepVarsMap.end())
88  return nullptr;
89  return &(FoundVariable->second);
90  }
91  for (const auto *Child : Expression->children())
92  if (const auto *ChildExpression = dyn_cast<Expr>(Child))
93  if (IdDependencyRecord *Result = hasIdDepVar(ChildExpression))
94  return Result;
95  return nullptr;
96 }
97 
98 IdDependentBackwardBranchCheck::IdDependencyRecord *
99 IdDependentBackwardBranchCheck::hasIdDepField(const Expr *Expression) {
100  if (const auto *MemberExpression = dyn_cast<MemberExpr>(Expression)) {
101  const auto *CheckField =
102  dyn_cast<FieldDecl>(MemberExpression->getMemberDecl());
103  auto FoundField = IdDepFieldsMap.find(CheckField);
104  if (FoundField == IdDepFieldsMap.end())
105  return nullptr;
106  return &(FoundField->second);
107  }
108  for (const auto *Child : Expression->children())
109  if (const auto *ChildExpression = dyn_cast<Expr>(Child))
110  if (IdDependencyRecord *Result = hasIdDepField(ChildExpression))
111  return Result;
112  return nullptr;
113 }
114 
115 void IdDependentBackwardBranchCheck::saveIdDepVar(const Stmt *Statement,
116  const VarDecl *Variable) {
117  // Record that this variable is thread-dependent.
118  IdDepVarsMap[Variable] =
119  IdDependencyRecord(Variable, Variable->getBeginLoc(),
120  Twine("assignment of ID-dependent variable ") +
121  Variable->getNameAsString());
122 }
123 
124 void IdDependentBackwardBranchCheck::saveIdDepField(const Stmt *Statement,
125  const FieldDecl *Field) {
126  // Record that this field is thread-dependent.
127  IdDepFieldsMap[Field] = IdDependencyRecord(
128  Field, Statement->getBeginLoc(),
129  Twine("assignment of ID-dependent field ") + Field->getNameAsString());
130 }
131 
132 void IdDependentBackwardBranchCheck::saveIdDepVarFromReference(
133  const DeclRefExpr *RefExpr, const MemberExpr *MemExpr,
134  const VarDecl *PotentialVar) {
135  // If the variable is already in IdDepVarsMap, ignore it.
136  if (IdDepVarsMap.find(PotentialVar) != IdDepVarsMap.end())
137  return;
138  std::string Message;
139  llvm::raw_string_ostream StringStream(Message);
140  StringStream << "inferred assignment of ID-dependent value from "
141  "ID-dependent ";
142  if (RefExpr) {
143  const auto *RefVar = dyn_cast<VarDecl>(RefExpr->getDecl());
144  // If variable isn't ID-dependent, but RefVar is.
145  if (IdDepVarsMap.find(RefVar) != IdDepVarsMap.end())
146  StringStream << "variable " << RefVar->getNameAsString();
147  }
148  if (MemExpr) {
149  const auto *RefField = dyn_cast<FieldDecl>(MemExpr->getMemberDecl());
150  // If variable isn't ID-dependent, but RefField is.
151  if (IdDepFieldsMap.find(RefField) != IdDepFieldsMap.end())
152  StringStream << "member " << RefField->getNameAsString();
153  }
154  IdDepVarsMap[PotentialVar] =
155  IdDependencyRecord(PotentialVar, PotentialVar->getBeginLoc(), Message);
156 }
157 
158 void IdDependentBackwardBranchCheck::saveIdDepFieldFromReference(
159  const DeclRefExpr *RefExpr, const MemberExpr *MemExpr,
160  const FieldDecl *PotentialField) {
161  // If the field is already in IdDepFieldsMap, ignore it.
162  if (IdDepFieldsMap.find(PotentialField) != IdDepFieldsMap.end())
163  return;
164  std::string Message;
165  llvm::raw_string_ostream StringStream(Message);
166  StringStream << "inferred assignment of ID-dependent member from "
167  "ID-dependent ";
168  if (RefExpr) {
169  const auto *RefVar = dyn_cast<VarDecl>(RefExpr->getDecl());
170  // If field isn't ID-dependent, but RefVar is.
171  if (IdDepVarsMap.find(RefVar) != IdDepVarsMap.end())
172  StringStream << "variable " << RefVar->getNameAsString();
173  }
174  if (MemExpr) {
175  const auto *RefField = dyn_cast<FieldDecl>(MemExpr->getMemberDecl());
176  if (IdDepFieldsMap.find(RefField) != IdDepFieldsMap.end())
177  StringStream << "member " << RefField->getNameAsString();
178  }
179  IdDepFieldsMap[PotentialField] = IdDependencyRecord(
180  PotentialField, PotentialField->getBeginLoc(), Message);
181 }
182 
183 IdDependentBackwardBranchCheck::LoopType
184 IdDependentBackwardBranchCheck::getLoopType(const Stmt *Loop) {
185  switch (Loop->getStmtClass()) {
186  case Stmt::DoStmtClass:
187  return DoLoop;
188  case Stmt::WhileStmtClass:
189  return WhileLoop;
190  case Stmt::ForStmtClass:
191  return ForLoop;
192  default:
193  return UnknownLoop;
194  }
195 }
196 
198  const MatchFinder::MatchResult &Result) {
199  // The first half of the callback only deals with identifying and storing
200  // ID-dependency information into the IdDepVars and IdDepFields maps.
201  const auto *Variable = Result.Nodes.getNodeAs<VarDecl>("tid_dep_var");
202  const auto *Field = Result.Nodes.getNodeAs<FieldDecl>("tid_dep_field");
203  const auto *Statement = Result.Nodes.getNodeAs<Stmt>("straight_assignment");
204  const auto *RefExpr = Result.Nodes.getNodeAs<DeclRefExpr>("assign_ref_var");
205  const auto *MemExpr = Result.Nodes.getNodeAs<MemberExpr>("assign_ref_field");
206  const auto *PotentialVar = Result.Nodes.getNodeAs<VarDecl>("pot_tid_var");
207  const auto *PotentialField =
208  Result.Nodes.getNodeAs<FieldDecl>("pot_tid_field");
209 
210  // Save variables and fields assigned directly through ID function calls.
211  if (Statement && (Variable || Field)) {
212  if (Variable)
213  saveIdDepVar(Statement, Variable);
214  else if (Field)
215  saveIdDepField(Statement, Field);
216  }
217 
218  // Save variables assigned to values of Id-dependent variables and fields.
219  if ((RefExpr || MemExpr) && PotentialVar)
220  saveIdDepVarFromReference(RefExpr, MemExpr, PotentialVar);
221 
222  // Save fields assigned to values of ID-dependent variables and fields.
223  if ((RefExpr || MemExpr) && PotentialField)
224  saveIdDepFieldFromReference(RefExpr, MemExpr, PotentialField);
225 
226  // The second part of the callback deals with checking if a branch inside a
227  // loop is thread dependent.
228  const auto *CondExpr = Result.Nodes.getNodeAs<Expr>("cond_expr");
229  const auto *IDCall = Result.Nodes.getNodeAs<CallExpr>("id_call");
230  const auto *Loop = Result.Nodes.getNodeAs<Stmt>("backward_branch");
231  if (!Loop)
232  return;
233  LoopType Type = getLoopType(Loop);
234  if (CondExpr) {
235  if (IDCall) { // Conditional expression calls an ID function directly.
236  diag(CondExpr->getBeginLoc(),
237  "backward branch (%select{do|while|for}0 loop) is ID-dependent due "
238  "to ID function call and may cause performance degradation")
239  << Type;
240  return;
241  }
242  // Conditional expression has DeclRefExpr(s), check ID-dependency.
243  IdDependencyRecord *IdDepVar = hasIdDepVar(CondExpr);
244  IdDependencyRecord *IdDepField = hasIdDepField(CondExpr);
245  if (IdDepVar) {
246  // Change one of these to a Note
247  diag(IdDepVar->Location, IdDepVar->Message, DiagnosticIDs::Note);
248  diag(CondExpr->getBeginLoc(),
249  "backward branch (%select{do|while|for}0 loop) is ID-dependent due "
250  "to variable reference to %1 and may cause performance degradation")
251  << Type << IdDepVar->VariableDeclaration;
252  } else if (IdDepField) {
253  diag(IdDepField->Location, IdDepField->Message, DiagnosticIDs::Note);
254  diag(CondExpr->getBeginLoc(),
255  "backward branch (%select{do|while|for}0 loop) is ID-dependent due "
256  "to member reference to %1 and may cause performance degradation")
257  << Type << IdDepField->FieldDeclaration;
258  }
259  }
260 }
261 
262 } // namespace altera
263 } // namespace tidy
264 } // namespace clang
Type
NodeType Type
Definition: HTMLGenerator.cpp:73
clang::clangd::check
bool check(llvm::StringRef File, llvm::Optional< Range > LineRange, const ThreadsafeFS &TFS, const ClangdLSPServer::Options &Opts, bool EnableCodeCompletion)
Definition: Check.cpp:273
clang::tidy::bugprone::Message
static const char Message[]
Definition: ReservedIdentifierCheck.cpp:31
clang::ast_matchers
Definition: AbseilMatcher.h:14
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
IdDependentBackwardBranchCheck.h
Field
const FieldDecl * Field
Definition: MemberwiseConstructor.cpp:260
clang::clangd::CompletionItemKind::Variable
@ Variable