272 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 "UnrollLoopsCheck.h"10#include "clang/AST/APValue.h"11#include "clang/AST/ASTContext.h"12#include "clang/AST/ASTTypeTraits.h"13#include "clang/AST/OperationKinds.h"14#include "clang/AST/ParentMapContext.h"15#include "clang/ASTMatchers/ASTMatchFinder.h"16#include <cmath>17 18using namespace clang::ast_matchers;19 20namespace clang::tidy::altera {21 22UnrollLoopsCheck::UnrollLoopsCheck(StringRef Name, ClangTidyContext *Context)23 : ClangTidyCheck(Name, Context),24 MaxLoopIterations(Options.get("MaxLoopIterations", 100U)) {}25 26void UnrollLoopsCheck::registerMatchers(MatchFinder *Finder) {27 const auto HasLoopBound = hasDescendant(28 varDecl(matchesName("__end*"),29 hasDescendant(integerLiteral().bind("cxx_loop_bound"))));30 const auto CXXForRangeLoop =31 cxxForRangeStmt(anyOf(HasLoopBound, unless(HasLoopBound)));32 const auto AnyLoop = anyOf(forStmt(), whileStmt(), doStmt(), CXXForRangeLoop);33 Finder->addMatcher(34 stmt(AnyLoop, unless(hasDescendant(stmt(AnyLoop)))).bind("loop"), this);35}36 37void UnrollLoopsCheck::check(const MatchFinder::MatchResult &Result) {38 const auto *Loop = Result.Nodes.getNodeAs<Stmt>("loop");39 const auto *CXXLoopBound =40 Result.Nodes.getNodeAs<IntegerLiteral>("cxx_loop_bound");41 const ASTContext *Context = Result.Context;42 switch (unrollType(Loop, Result.Context)) {43 case NotUnrolled:44 diag(Loop->getBeginLoc(),45 "kernel performance could be improved by unrolling this loop with a "46 "'#pragma unroll' directive");47 break;48 case PartiallyUnrolled:49 // Loop already partially unrolled, do nothing.50 break;51 case FullyUnrolled:52 if (hasKnownBounds(Loop, CXXLoopBound, Context)) {53 if (hasLargeNumIterations(Loop, CXXLoopBound, Context)) {54 diag(Loop->getBeginLoc(),55 "loop likely has a large number of iterations and thus "56 "cannot be fully unrolled; to partially unroll this loop, use "57 "the '#pragma unroll <num>' directive");58 return;59 }60 return;61 }62 if (isa<WhileStmt, DoStmt>(Loop)) {63 diag(Loop->getBeginLoc(),64 "full unrolling requested, but loop bounds may not be known; to "65 "partially unroll this loop, use the '#pragma unroll <num>' "66 "directive",67 DiagnosticIDs::Note);68 break;69 }70 diag(Loop->getBeginLoc(),71 "full unrolling requested, but loop bounds are not known; to "72 "partially unroll this loop, use the '#pragma unroll <num>' "73 "directive");74 break;75 }76}77 78enum UnrollLoopsCheck::UnrollType79UnrollLoopsCheck::unrollType(const Stmt *Statement, ASTContext *Context) {80 const DynTypedNodeList Parents = Context->getParents<Stmt>(*Statement);81 for (const DynTypedNode &Parent : Parents) {82 const auto *ParentStmt = Parent.get<AttributedStmt>();83 if (!ParentStmt)84 continue;85 for (const Attr *Attribute : ParentStmt->getAttrs()) {86 const auto *LoopHint = dyn_cast<LoopHintAttr>(Attribute);87 if (!LoopHint)88 continue;89 switch (LoopHint->getState()) {90 case LoopHintAttr::Numeric:91 return PartiallyUnrolled;92 case LoopHintAttr::Disable:93 return NotUnrolled;94 case LoopHintAttr::Full:95 return FullyUnrolled;96 case LoopHintAttr::Enable:97 return FullyUnrolled;98 case LoopHintAttr::AssumeSafety:99 return NotUnrolled;100 case LoopHintAttr::FixedWidth:101 return NotUnrolled;102 case LoopHintAttr::ScalableWidth:103 return NotUnrolled;104 }105 }106 }107 return NotUnrolled;108}109 110bool UnrollLoopsCheck::hasKnownBounds(const Stmt *Statement,111 const IntegerLiteral *CXXLoopBound,112 const ASTContext *Context) {113 if (isa<CXXForRangeStmt>(Statement))114 return CXXLoopBound != nullptr;115 // Too many possibilities in a while statement, so always recommend partial116 // unrolling for these.117 if (isa<WhileStmt, DoStmt>(Statement))118 return false;119 // The last loop type is a for loop.120 const auto *ForLoop = cast<ForStmt>(Statement);121 const Stmt *Initializer = ForLoop->getInit();122 const Expr *Conditional = ForLoop->getCond();123 const Expr *Increment = ForLoop->getInc();124 if (!Initializer || !Conditional || !Increment)125 return false;126 // If the loop variable value isn't known, loop bounds are unknown.127 if (const auto *InitDeclStatement = dyn_cast<DeclStmt>(Initializer)) {128 if (const auto *VariableDecl =129 dyn_cast<VarDecl>(InitDeclStatement->getSingleDecl())) {130 const APValue *Evaluation = VariableDecl->evaluateValue();131 if (!Evaluation || !Evaluation->hasValue())132 return false;133 }134 }135 // If increment is unary and not one of ++ and --, loop bounds are unknown.136 if (const auto *Op = dyn_cast<UnaryOperator>(Increment))137 if (!Op->isIncrementDecrementOp())138 return false;139 140 if (const auto *BinaryOp = dyn_cast<BinaryOperator>(Conditional)) {141 const Expr *LHS = BinaryOp->getLHS();142 const Expr *RHS = BinaryOp->getRHS();143 // If both sides are value dependent or constant, loop bounds are unknown.144 return LHS->isEvaluatable(*Context) != RHS->isEvaluatable(*Context);145 }146 return false; // If it's not a binary operator, loop bounds are unknown.147}148 149const Expr *UnrollLoopsCheck::getCondExpr(const Stmt *Statement) {150 if (const auto *ForLoop = dyn_cast<ForStmt>(Statement))151 return ForLoop->getCond();152 if (const auto *WhileLoop = dyn_cast<WhileStmt>(Statement))153 return WhileLoop->getCond();154 if (const auto *DoWhileLoop = dyn_cast<DoStmt>(Statement))155 return DoWhileLoop->getCond();156 if (const auto *CXXRangeLoop = dyn_cast<CXXForRangeStmt>(Statement))157 return CXXRangeLoop->getCond();158 llvm_unreachable("Unknown loop");159}160 161bool UnrollLoopsCheck::hasLargeNumIterations(const Stmt *Statement,162 const IntegerLiteral *CXXLoopBound,163 const ASTContext *Context) {164 // Because hasKnownBounds is called before this, if this is true, then165 // CXXLoopBound is also matched.166 if (isa<CXXForRangeStmt>(Statement)) {167 assert(CXXLoopBound && "CXX ranged for loop has no loop bound");168 return exprHasLargeNumIterations(CXXLoopBound, Context);169 }170 const auto *ForLoop = cast<ForStmt>(Statement);171 const Stmt *Initializer = ForLoop->getInit();172 const Expr *Conditional = ForLoop->getCond();173 const Expr *Increment = ForLoop->getInc();174 int InitValue = 0;175 // If the loop variable value isn't known, we can't know the loop bounds.176 if (const auto *InitDeclStatement = dyn_cast<DeclStmt>(Initializer)) {177 if (const auto *VariableDecl =178 dyn_cast<VarDecl>(InitDeclStatement->getSingleDecl())) {179 APValue *Evaluation = VariableDecl->evaluateValue();180 if (!Evaluation || !Evaluation->isInt())181 return true;182 InitValue = Evaluation->getInt().getExtValue();183 }184 }185 186 int EndValue = 0;187 const auto *BinaryOp = cast<BinaryOperator>(Conditional);188 if (!extractValue(EndValue, BinaryOp, Context))189 return true;190 191 double Iterations = 0.0;192 193 // If increment is unary and not one of ++, --, we can't know the loop bounds.194 if (const auto *Op = dyn_cast<UnaryOperator>(Increment)) {195 if (Op->isIncrementOp())196 Iterations = EndValue - InitValue;197 else if (Op->isDecrementOp())198 Iterations = InitValue - EndValue;199 else200 llvm_unreachable("Unary operator neither increment nor decrement");201 }202 203 // If increment is binary and not one of +, -, *, /, we can't know the loop204 // bounds.205 if (const auto *Op = dyn_cast<BinaryOperator>(Increment)) {206 int ConstantValue = 0;207 if (!extractValue(ConstantValue, Op, Context))208 return true;209 switch (Op->getOpcode()) {210 case (BO_AddAssign):211 Iterations = std::ceil(float(EndValue - InitValue) / ConstantValue);212 break;213 case (BO_SubAssign):214 Iterations = std::ceil(float(InitValue - EndValue) / ConstantValue);215 break;216 case (BO_MulAssign):217 Iterations =218 1 + ((std::log((double)EndValue) - std::log((double)InitValue)) /219 std::log((double)ConstantValue));220 break;221 case (BO_DivAssign):222 Iterations =223 1 + ((std::log((double)InitValue) - std::log((double)EndValue)) /224 std::log((double)ConstantValue));225 break;226 default:227 // All other operators are not handled; assume large bounds.228 return true;229 }230 }231 return Iterations > MaxLoopIterations;232}233 234bool UnrollLoopsCheck::extractValue(int &Value, const BinaryOperator *Op,235 const ASTContext *Context) {236 const Expr *LHS = Op->getLHS();237 const Expr *RHS = Op->getRHS();238 Expr::EvalResult Result;239 if (LHS->isEvaluatable(*Context))240 LHS->EvaluateAsRValue(Result, *Context);241 else if (RHS->isEvaluatable(*Context))242 RHS->EvaluateAsRValue(Result, *Context);243 else244 return false; // Cannot evaluate either side.245 if (!Result.Val.isInt())246 return false; // Cannot check number of iterations, return false to be247 // safe.248 Value = Result.Val.getInt().getExtValue();249 return true;250}251 252bool UnrollLoopsCheck::exprHasLargeNumIterations(253 const Expr *Expression, const ASTContext *Context) const {254 Expr::EvalResult Result;255 if (Expression->EvaluateAsRValue(Result, *Context)) {256 if (!Result.Val.isInt())257 return false; // Cannot check number of iterations, return false to be258 // safe.259 // The following assumes values go from 0 to Val in increments of 1.260 return Result.Val.getInt() > MaxLoopIterations;261 }262 // Cannot evaluate Expression as an r-value, so cannot check number of263 // iterations.264 return false;265}266 267void UnrollLoopsCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {268 Options.store(Opts, "MaxLoopIterations", MaxLoopIterations);269}270 271} // namespace clang::tidy::altera272