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