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 (!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