271 lines · cpp
1//===----------------------------------------------------------------------===//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-exception6//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(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 DeclRefExpr44 // (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 (in51 // 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 the61 // condition expression IF it either calls an ID function or has a variable62 // DeclRefExpr. DeclRefExprs are checked later to confirm whether the variable63 // 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 79const IdDependentBackwardBranchCheck::IdDependencyRecord *80IdDependentBackwardBranchCheck::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 (const IdDependencyRecord *Result = hasIdDepVar(ChildExpression))98 return Result;99 return nullptr;100}101 102const IdDependentBackwardBranchCheck::IdDependencyRecord *103IdDependentBackwardBranchCheck::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 (const 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(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 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(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 192IdDependentBackwardBranchCheck::LoopType193IdDependentBackwardBranchCheck::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 storing209 // 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 a236 // 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 const 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 const IdDependencyRecord *IdDepVar = hasIdDepVar(CondExpr);253 const 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::altera271