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
13using namespace clang::ast_matchers;
14
15namespace clang::tidy::altera {
16
17void 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(InnerMatcher: functionDecl(
21 anyOf(hasName(Name: "get_global_id"), hasName(Name: "get_local_id")))))));
22
23 const auto RefVarOrField = forEachDescendant(
24 stmt(anyOf(declRefExpr(to(InnerMatcher: varDecl())).bind(ID: "assign_ref_var"),
25 memberExpr(member(InnerMatcher: fieldDecl())).bind(ID: "assign_ref_field"))));
26
27 Finder->addMatcher(
28 NodeMatch: compoundStmt(
29 // Bind on actual get_local/global_id calls.
30 forEachDescendant(
31 stmt(
32 anyOf(declStmt(hasDescendant(varDecl(hasInitializer(InnerMatcher: ThreadID))
33 .bind(ID: "tid_dep_var"))),
34 binaryOperator(
35 isAssignmentOperator(), hasRHS(InnerMatcher: ThreadID),
36 hasLHS(InnerMatcher: anyOf(
37 declRefExpr(to(InnerMatcher: varDecl().bind(ID: "tid_dep_var"))),
38 memberExpr(member(
39 InnerMatcher: fieldDecl().bind(ID: "tid_dep_field"))))))))
40 .bind(ID: "straight_assignment"))),
41 Action: 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 NodeMatch: stmt(forEachDescendant(
47 varDecl(hasInitializer(InnerMatcher: RefVarOrField)).bind(ID: "pot_tid_var"))),
48 Action: 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 NodeMatch: stmt(forEachDescendant(binaryOperator(
54 allOf(isAssignmentOperator(), hasRHS(InnerMatcher: RefVarOrField),
55 hasLHS(InnerMatcher: anyOf(
56 declRefExpr(to(InnerMatcher: varDecl().bind(ID: "pot_tid_var"))),
57 memberExpr(member(InnerMatcher: fieldDecl().bind(ID: "pot_tid_field"))))))))),
58 Action: 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(InnerMatcher: functionDecl(
66 anyOf(hasName(Name: "get_global_id"),
67 hasName(Name: "get_local_id")))))
68 .bind(ID: "id_call")),
69 hasDescendant(stmt(anyOf(declRefExpr(to(InnerMatcher: varDecl())),
70 memberExpr(member(InnerMatcher: fieldDecl())))))))
71 .bind(ID: "cond_expr");
72 Finder->addMatcher(NodeMatch: stmt(anyOf(forStmt(hasCondition(InnerMatcher: CondExpr)),
73 doStmt(hasCondition(InnerMatcher: CondExpr)),
74 whileStmt(hasCondition(InnerMatcher: CondExpr))))
75 .bind(ID: "backward_branch"),
76 Action: this);
77}
78
79IdDependentBackwardBranchCheck::IdDependencyRecord *
80IdDependentBackwardBranchCheck::hasIdDepVar(const Expr *Expression) {
81 if (!Expression)
82 return nullptr;
83
84 if (const auto *Declaration = dyn_cast<DeclRefExpr>(Val: 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>(Val: Declaration->getDecl());
88 if (!CheckVariable)
89 return nullptr;
90 auto FoundVariable = IdDepVarsMap.find(x: 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
102IdDependentBackwardBranchCheck::IdDependencyRecord *
103IdDependentBackwardBranchCheck::hasIdDepField(const Expr *Expression) {
104 if (!Expression)
105 return nullptr;
106
107 if (const auto *MemberExpression = dyn_cast<MemberExpr>(Val: Expression)) {
108 const auto *CheckField =
109 dyn_cast_if_present<FieldDecl>(Val: MemberExpression->getMemberDecl());
110 if (!CheckField)
111 return nullptr;
112 auto FoundField = IdDepFieldsMap.find(x: 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
124void 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
133void 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
141void 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(x: 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>(Val: RefExpr->getDecl());
153 // If variable isn't ID-dependent, but RefVar is.
154 if (IdDepVarsMap.find(x: RefVar) != IdDepVarsMap.end())
155 StringStream << "variable " << RefVar->getNameAsString();
156 }
157 if (MemExpr) {
158 const auto *RefField = dyn_cast<FieldDecl>(Val: MemExpr->getMemberDecl());
159 // If variable isn't ID-dependent, but RefField is.
160 if (IdDepFieldsMap.find(x: RefField) != IdDepFieldsMap.end())
161 StringStream << "member " << RefField->getNameAsString();
162 }
163 IdDepVarsMap[PotentialVar] =
164 IdDependencyRecord(PotentialVar, PotentialVar->getBeginLoc(), Message);
165}
166
167void 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(x: 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>(Val: RefExpr->getDecl());
179 // If field isn't ID-dependent, but RefVar is.
180 if (IdDepVarsMap.find(x: RefVar) != IdDepVarsMap.end())
181 StringStream << "variable " << RefVar->getNameAsString();
182 }
183 if (MemExpr) {
184 const auto *RefField = dyn_cast<FieldDecl>(Val: MemExpr->getMemberDecl());
185 if (IdDepFieldsMap.find(x: RefField) != IdDepFieldsMap.end())
186 StringStream << "member " << RefField->getNameAsString();
187 }
188 IdDepFieldsMap[PotentialField] = IdDependencyRecord(
189 PotentialField, PotentialField->getBeginLoc(), Message);
190}
191
192IdDependentBackwardBranchCheck::LoopType
193IdDependentBackwardBranchCheck::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
206void 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>(ID: "tid_dep_var");
211 const auto *Field = Result.Nodes.getNodeAs<FieldDecl>(ID: "tid_dep_field");
212 const auto *Statement = Result.Nodes.getNodeAs<Stmt>(ID: "straight_assignment");
213 const auto *RefExpr = Result.Nodes.getNodeAs<DeclRefExpr>(ID: "assign_ref_var");
214 const auto *MemExpr = Result.Nodes.getNodeAs<MemberExpr>(ID: "assign_ref_field");
215 const auto *PotentialVar = Result.Nodes.getNodeAs<VarDecl>(ID: "pot_tid_var");
216 const auto *PotentialField =
217 Result.Nodes.getNodeAs<FieldDecl>(ID: "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>(ID: "cond_expr");
238 const auto *IDCall = Result.Nodes.getNodeAs<CallExpr>(ID: "id_call");
239 const auto *Loop = Result.Nodes.getNodeAs<Stmt>(ID: "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(Expression: CondExpr);
253 IdDependencyRecord *IdDepField = hasIdDepField(Expression: 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(Loc: IdDepVar->Location, Description: IdDepVar->Message, Level: 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(Loc: IdDepField->Location, Description: IdDepField->Message, Level: DiagnosticIDs::Note);
266 }
267 }
268}
269
270} // namespace clang::tidy::altera
271

source code of clang-tools-extra/clang-tidy/altera/IdDependentBackwardBranchCheck.cpp