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