clang-tools-extra/clang-tidy/altera/IdDependentBackwardBranchCheck.cpp

   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 (const auto *Declaration = dyn_cast<DeclRefExpr>(Expression)) {
  82     // It is a DeclRefExpr, so check if it's an ID-dependent variable.
  83     const auto *CheckVariable = dyn_cast<VarDecl>(Declaration->getDecl());
  84     auto FoundVariable = IdDepVarsMap.find(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
  96 IdDependentBackwardBranchCheck::IdDependencyRecord *
  97 IdDependentBackwardBranchCheck::hasIdDepField(const Expr *Expression) {
  98   if (const auto *MemberExpression = dyn_cast<MemberExpr>(Expression)) {
  99     const auto *CheckField =
 100         dyn_cast<FieldDecl>(MemberExpression->getMemberDecl());
 101     auto FoundField = IdDepFieldsMap.find(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
 113 void 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
 122 void 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
 130 void 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(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>(RefExpr->getDecl());
 142     // If variable isn't ID-dependent, but RefVar is.
 143     if (IdDepVarsMap.find(RefVar) != IdDepVarsMap.end())
 144       StringStream << "variable " << RefVar->getNameAsString();
 145   }
 146   if (MemExpr) {
 147     const auto *RefField = dyn_cast<FieldDecl>(MemExpr->getMemberDecl());
 148     // If variable isn't ID-dependent, but RefField is.
 149     if (IdDepFieldsMap.find(RefField) != IdDepFieldsMap.end())
 150       StringStream << "member " << RefField->getNameAsString();
 151   }
 152   IdDepVarsMap[PotentialVar] =
 153       IdDependencyRecord(PotentialVar, PotentialVar->getBeginLoc(), Message);
 154 }
 155
 156 void 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(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>(RefExpr->getDecl());
 168     // If field isn't ID-dependent, but RefVar is.
 169     if (IdDepVarsMap.find(RefVar) != IdDepVarsMap.end())
 170       StringStream << "variable " << RefVar->getNameAsString();
 171   }
 172   if (MemExpr) {
 173     const auto *RefField = dyn_cast<FieldDecl>(MemExpr->getMemberDecl());
 174     if (IdDepFieldsMap.find(RefField) != IdDepFieldsMap.end())
 175       StringStream << "member " << RefField->getNameAsString();
 176   }
 177   IdDepFieldsMap[PotentialField] = IdDependencyRecord(
 178       PotentialField, PotentialField->getBeginLoc(), Message);
 179 }
 180
 181 IdDependentBackwardBranchCheck::LoopType
 182 IdDependentBackwardBranchCheck::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
 195 void 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>("tid_dep_var");
 200   const auto *Field = Result.Nodes.getNodeAs<FieldDecl>("tid_dep_field");
 201   const auto *Statement = Result.Nodes.getNodeAs<Stmt>("straight_assignment");
 202   const auto *RefExpr = Result.Nodes.getNodeAs<DeclRefExpr>("assign_ref_var");
 203   const auto *MemExpr = Result.Nodes.getNodeAs<MemberExpr>("assign_ref_field");
 204   const auto *PotentialVar = Result.Nodes.getNodeAs<VarDecl>("pot_tid_var");
 205   const auto *PotentialField =
 206       Result.Nodes.getNodeAs<FieldDecl>("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>("cond_expr");
 227   const auto *IDCall = Result.Nodes.getNodeAs<CallExpr>("id_call");
 228   const auto *Loop = Result.Nodes.getNodeAs<Stmt>("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(CondExpr);
 242     IdDependencyRecord *IdDepField = hasIdDepField(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(IdDepVar->Location, IdDepVar->Message, 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(IdDepField->Location, IdDepField->Message, DiagnosticIDs::Note);
 255     }
 256   }
 257 }
 258
 259 } // namespace clang::tidy::altera