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 (const auto *Declaration = dyn_cast<DeclRefExpr>(Val: Expression)) {
82 // It is a DeclRefExpr, so check if it's an ID-dependent variable.
83 const auto *CheckVariable = dyn_cast<VarDecl>(Val: Declaration->getDecl());
84 auto FoundVariable = IdDepVarsMap.find(x: CheckVariable);
85 if (FoundVariable == IdDepVarsMap.end())
86 return nullptr;
87 return &(FoundVariable->second);
88 }
89 for (const auto *Child : Expression->children())
90 if (const auto *ChildExpression = dyn_cast<Expr>(Child))
91 if (IdDependencyRecord *Result = hasIdDepVar(ChildExpression))
92 return Result;
93 return nullptr;
94}
95
96IdDependentBackwardBranchCheck::IdDependencyRecord *
97IdDependentBackwardBranchCheck::hasIdDepField(const Expr *Expression) {
98 if (const auto *MemberExpression = dyn_cast<MemberExpr>(Val: Expression)) {
99 const auto *CheckField =
100 dyn_cast<FieldDecl>(Val: MemberExpression->getMemberDecl());
101 auto FoundField = IdDepFieldsMap.find(x: CheckField);
102 if (FoundField == IdDepFieldsMap.end())
103 return nullptr;
104 return &(FoundField->second);
105 }
106 for (const auto *Child : Expression->children())
107 if (const auto *ChildExpression = dyn_cast<Expr>(Child))
108 if (IdDependencyRecord *Result = hasIdDepField(ChildExpression))
109 return Result;
110 return nullptr;
111}
112
113void IdDependentBackwardBranchCheck::saveIdDepVar(const Stmt *Statement,
114 const VarDecl *Variable) {
115 // Record that this variable is thread-dependent.
116 IdDepVarsMap[Variable] =
117 IdDependencyRecord(Variable, Variable->getBeginLoc(),
118 Twine("assignment of ID-dependent variable ") +
119 Variable->getNameAsString());
120}
121
122void IdDependentBackwardBranchCheck::saveIdDepField(const Stmt *Statement,
123 const FieldDecl *Field) {
124 // Record that this field is thread-dependent.
125 IdDepFieldsMap[Field] = IdDependencyRecord(
126 Field, Statement->getBeginLoc(),
127 Twine("assignment of ID-dependent field ") + Field->getNameAsString());
128}
129
130void IdDependentBackwardBranchCheck::saveIdDepVarFromReference(
131 const DeclRefExpr *RefExpr, const MemberExpr *MemExpr,
132 const VarDecl *PotentialVar) {
133 // If the variable is already in IdDepVarsMap, ignore it.
134 if (IdDepVarsMap.find(x: PotentialVar) != IdDepVarsMap.end())
135 return;
136 std::string Message;
137 llvm::raw_string_ostream StringStream(Message);
138 StringStream << "inferred assignment of ID-dependent value from "
139 "ID-dependent ";
140 if (RefExpr) {
141 const auto *RefVar = dyn_cast<VarDecl>(Val: RefExpr->getDecl());
142 // If variable isn't ID-dependent, but RefVar is.
143 if (IdDepVarsMap.find(x: RefVar) != IdDepVarsMap.end())
144 StringStream << "variable " << RefVar->getNameAsString();
145 }
146 if (MemExpr) {
147 const auto *RefField = dyn_cast<FieldDecl>(Val: MemExpr->getMemberDecl());
148 // If variable isn't ID-dependent, but RefField is.
149 if (IdDepFieldsMap.find(x: RefField) != IdDepFieldsMap.end())
150 StringStream << "member " << RefField->getNameAsString();
151 }
152 IdDepVarsMap[PotentialVar] =
153 IdDependencyRecord(PotentialVar, PotentialVar->getBeginLoc(), Message);
154}
155
156void IdDependentBackwardBranchCheck::saveIdDepFieldFromReference(
157 const DeclRefExpr *RefExpr, const MemberExpr *MemExpr,
158 const FieldDecl *PotentialField) {
159 // If the field is already in IdDepFieldsMap, ignore it.
160 if (IdDepFieldsMap.find(x: PotentialField) != IdDepFieldsMap.end())
161 return;
162 std::string Message;
163 llvm::raw_string_ostream StringStream(Message);
164 StringStream << "inferred assignment of ID-dependent member from "
165 "ID-dependent ";
166 if (RefExpr) {
167 const auto *RefVar = dyn_cast<VarDecl>(Val: RefExpr->getDecl());
168 // If field isn't ID-dependent, but RefVar is.
169 if (IdDepVarsMap.find(x: RefVar) != IdDepVarsMap.end())
170 StringStream << "variable " << RefVar->getNameAsString();
171 }
172 if (MemExpr) {
173 const auto *RefField = dyn_cast<FieldDecl>(Val: MemExpr->getMemberDecl());
174 if (IdDepFieldsMap.find(x: RefField) != IdDepFieldsMap.end())
175 StringStream << "member " << RefField->getNameAsString();
176 }
177 IdDepFieldsMap[PotentialField] = IdDependencyRecord(
178 PotentialField, PotentialField->getBeginLoc(), Message);
179}
180
181IdDependentBackwardBranchCheck::LoopType
182IdDependentBackwardBranchCheck::getLoopType(const Stmt *Loop) {
183 switch (Loop->getStmtClass()) {
184 case Stmt::DoStmtClass:
185 return DoLoop;
186 case Stmt::WhileStmtClass:
187 return WhileLoop;
188 case Stmt::ForStmtClass:
189 return ForLoop;
190 default:
191 return UnknownLoop;
192 }
193}
194
195void IdDependentBackwardBranchCheck::check(
196 const MatchFinder::MatchResult &Result) {
197 // The first half of the callback only deals with identifying and storing
198 // ID-dependency information into the IdDepVars and IdDepFields maps.
199 const auto *Variable = Result.Nodes.getNodeAs<VarDecl>(ID: "tid_dep_var");
200 const auto *Field = Result.Nodes.getNodeAs<FieldDecl>(ID: "tid_dep_field");
201 const auto *Statement = Result.Nodes.getNodeAs<Stmt>(ID: "straight_assignment");
202 const auto *RefExpr = Result.Nodes.getNodeAs<DeclRefExpr>(ID: "assign_ref_var");
203 const auto *MemExpr = Result.Nodes.getNodeAs<MemberExpr>(ID: "assign_ref_field");
204 const auto *PotentialVar = Result.Nodes.getNodeAs<VarDecl>(ID: "pot_tid_var");
205 const auto *PotentialField =
206 Result.Nodes.getNodeAs<FieldDecl>(ID: "pot_tid_field");
207
208 // Save variables and fields assigned directly through ID function calls.
209 if (Statement && (Variable || Field)) {
210 if (Variable)
211 saveIdDepVar(Statement, Variable);
212 else if (Field)
213 saveIdDepField(Statement, Field);
214 }
215
216 // Save variables assigned to values of Id-dependent variables and fields.
217 if ((RefExpr || MemExpr) && PotentialVar)
218 saveIdDepVarFromReference(RefExpr, MemExpr, PotentialVar);
219
220 // Save fields assigned to values of ID-dependent variables and fields.
221 if ((RefExpr || MemExpr) && PotentialField)
222 saveIdDepFieldFromReference(RefExpr, MemExpr, PotentialField);
223
224 // The second part of the callback deals with checking if a branch inside a
225 // loop is thread dependent.
226 const auto *CondExpr = Result.Nodes.getNodeAs<Expr>(ID: "cond_expr");
227 const auto *IDCall = Result.Nodes.getNodeAs<CallExpr>(ID: "id_call");
228 const auto *Loop = Result.Nodes.getNodeAs<Stmt>(ID: "backward_branch");
229 if (!Loop)
230 return;
231 LoopType Type = getLoopType(Loop);
232 if (CondExpr) {
233 if (IDCall) { // Conditional expression calls an ID function directly.
234 diag(CondExpr->getBeginLoc(),
235 "backward branch (%select{do|while|for}0 loop) is ID-dependent due "
236 "to ID function call and may cause performance degradation")
237 << Type;
238 return;
239 }
240 // Conditional expression has DeclRefExpr(s), check ID-dependency.
241 IdDependencyRecord *IdDepVar = hasIdDepVar(Expression: CondExpr);
242 IdDependencyRecord *IdDepField = hasIdDepField(Expression: CondExpr);
243 if (IdDepVar) {
244 diag(CondExpr->getBeginLoc(),
245 "backward branch (%select{do|while|for}0 loop) is ID-dependent due "
246 "to variable reference to %1 and may cause performance degradation")
247 << Type << IdDepVar->VariableDeclaration;
248 diag(Loc: IdDepVar->Location, Description: IdDepVar->Message, Level: DiagnosticIDs::Note);
249 } else if (IdDepField) {
250 diag(CondExpr->getBeginLoc(),
251 "backward branch (%select{do|while|for}0 loop) is ID-dependent due "
252 "to member reference to %1 and may cause performance degradation")
253 << Type << IdDepField->FieldDeclaration;
254 diag(Loc: IdDepField->Location, Description: IdDepField->Message, Level: DiagnosticIDs::Note);
255 }
256 }
257}
258
259} // namespace clang::tidy::altera
260

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