clang  10.0.0svn
LoopUnrolling.cpp
Go to the documentation of this file.
1 //===--- LoopUnrolling.cpp - Unroll loops -----------------------*- C++ -*-===//
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 /// This file contains functions which are used to decide if a loop worth to be
10 /// unrolled. Moreover, these functions manages the stack of loop which is
11 /// tracked by the ProgramState.
12 ///
13 //===----------------------------------------------------------------------===//
14 
20 
21 using namespace clang;
22 using namespace ento;
23 using namespace clang::ast_matchers;
24 
25 static const int MAXIMUM_STEP_UNROLLED = 128;
26 
27 struct LoopState {
28 private:
29  enum Kind { Normal, Unrolled } K;
30  const Stmt *LoopStmt;
31  const LocationContext *LCtx;
32  unsigned maxStep;
33  LoopState(Kind InK, const Stmt *S, const LocationContext *L, unsigned N)
34  : K(InK), LoopStmt(S), LCtx(L), maxStep(N) {}
35 
36 public:
37  static LoopState getNormal(const Stmt *S, const LocationContext *L,
38  unsigned N) {
39  return LoopState(Normal, S, L, N);
40  }
41  static LoopState getUnrolled(const Stmt *S, const LocationContext *L,
42  unsigned N) {
43  return LoopState(Unrolled, S, L, N);
44  }
45  bool isUnrolled() const { return K == Unrolled; }
46  unsigned getMaxStep() const { return maxStep; }
47  const Stmt *getLoopStmt() const { return LoopStmt; }
48  const LocationContext *getLocationContext() const { return LCtx; }
49  bool operator==(const LoopState &X) const {
50  return K == X.K && LoopStmt == X.LoopStmt;
51  }
52  void Profile(llvm::FoldingSetNodeID &ID) const {
53  ID.AddInteger(K);
54  ID.AddPointer(LoopStmt);
55  ID.AddPointer(LCtx);
56  ID.AddInteger(maxStep);
57  }
58 };
59 
60 // The tracked stack of loops. The stack indicates that which loops the
61 // simulated element contained by. The loops are marked depending if we decided
62 // to unroll them.
63 // TODO: The loop stack should not need to be in the program state since it is
64 // lexical in nature. Instead, the stack of loops should be tracked in the
65 // LocationContext.
67 
68 namespace clang {
69 namespace ento {
70 
71 static bool isLoopStmt(const Stmt *S) {
72  return S && (isa<ForStmt>(S) || isa<WhileStmt>(S) || isa<DoStmt>(S));
73 }
74 
76  auto LS = State->get<LoopStack>();
77  if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt)
78  State = State->set<LoopStack>(LS.getTail());
79  return State;
80 }
81 
82 static internal::Matcher<Stmt> simpleCondition(StringRef BindName) {
83  return binaryOperator(anyOf(hasOperatorName("<"), hasOperatorName(">"),
84  hasOperatorName("<="), hasOperatorName(">="),
85  hasOperatorName("!=")),
86  hasEitherOperand(ignoringParenImpCasts(declRefExpr(
87  to(varDecl(hasType(isInteger())).bind(BindName))))),
88  hasEitherOperand(ignoringParenImpCasts(
89  integerLiteral().bind("boundNum"))))
90  .bind("conditionOperator");
91 }
92 
93 static internal::Matcher<Stmt>
94 changeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher) {
95  return anyOf(
96  unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")),
97  hasUnaryOperand(ignoringParenImpCasts(
98  declRefExpr(to(varDecl(VarNodeMatcher)))))),
99  binaryOperator(isAssignmentOperator(),
100  hasLHS(ignoringParenImpCasts(
101  declRefExpr(to(varDecl(VarNodeMatcher)))))));
102 }
103 
104 static internal::Matcher<Stmt>
105 callByRef(internal::Matcher<Decl> VarNodeMatcher) {
106  return callExpr(forEachArgumentWithParam(
107  declRefExpr(to(varDecl(VarNodeMatcher))),
108  parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))));
109 }
110 
111 static internal::Matcher<Stmt>
112 assignedToRef(internal::Matcher<Decl> VarNodeMatcher) {
114  allOf(hasType(referenceType()),
115  hasInitializer(anyOf(
116  initListExpr(has(declRefExpr(to(varDecl(VarNodeMatcher))))),
117  declRefExpr(to(varDecl(VarNodeMatcher)))))))));
118 }
119 
120 static internal::Matcher<Stmt>
121 getAddrTo(internal::Matcher<Decl> VarNodeMatcher) {
122  return unaryOperator(
123  hasOperatorName("&"),
124  hasUnaryOperand(declRefExpr(hasDeclaration(VarNodeMatcher))));
125 }
126 
127 static internal::Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) {
128  return hasDescendant(stmt(
130  // Escaping and not known mutation of the loop counter is handled
131  // by exclusion of assigning and address-of operators and
132  // pass-by-ref function calls on the loop counter from the body.
133  changeIntBoundNode(equalsBoundNode(NodeName)),
134  callByRef(equalsBoundNode(NodeName)),
135  getAddrTo(equalsBoundNode(NodeName)),
136  assignedToRef(equalsBoundNode(NodeName)))));
137 }
138 
139 static internal::Matcher<Stmt> forLoopMatcher() {
140  return forStmt(
141  hasCondition(simpleCondition("initVarName")),
142  // Initialization should match the form: 'int i = 6' or 'i = 42'.
143  hasLoopInit(
144  anyOf(declStmt(hasSingleDecl(
145  varDecl(allOf(hasInitializer(ignoringParenImpCasts(
146  integerLiteral().bind("initNum"))),
147  equalsBoundNode("initVarName"))))),
149  equalsBoundNode("initVarName"))))),
150  hasRHS(ignoringParenImpCasts(
151  integerLiteral().bind("initNum")))))),
152  // Incrementation should be a simple increment or decrement
153  // operator call.
154  hasIncrement(unaryOperator(
155  anyOf(hasOperatorName("++"), hasOperatorName("--")),
156  hasUnaryOperand(declRefExpr(
157  to(varDecl(allOf(equalsBoundNode("initVarName"),
158  hasType(isInteger())))))))),
159  unless(hasBody(hasSuspiciousStmt("initVarName")))).bind("forLoop");
160 }
161 
162 static bool isPossiblyEscaped(const VarDecl *VD, ExplodedNode *N) {
163  // Global variables assumed as escaped variables.
164  if (VD->hasGlobalStorage())
165  return true;
166 
167  while (!N->pred_empty()) {
169  if (!S) {
170  N = N->getFirstPred();
171  continue;
172  }
173 
174  if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) {
175  for (const Decl *D : DS->decls()) {
176  // Once we reach the declaration of the VD we can return.
177  if (D->getCanonicalDecl() == VD)
178  return false;
179  }
180  }
181  // Check the usage of the pass-by-ref function calls and adress-of operator
182  // on VD and reference initialized by VD.
183  ASTContext &ASTCtx =
185  auto Match =
186  match(stmt(anyOf(callByRef(equalsNode(VD)), getAddrTo(equalsNode(VD)),
187  assignedToRef(equalsNode(VD)))),
188  *S, ASTCtx);
189  if (!Match.empty())
190  return true;
191 
192  N = N->getFirstPred();
193  }
194  llvm_unreachable("Reached root without finding the declaration of VD");
195 }
196 
197 bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
198  ExplodedNode *Pred, unsigned &maxStep) {
199 
200  if (!isLoopStmt(LoopStmt))
201  return false;
202 
203  // TODO: Match the cases where the bound is not a concrete literal but an
204  // integer with known value
205  auto Matches = match(forLoopMatcher(), *LoopStmt, ASTCtx);
206  if (Matches.empty())
207  return false;
208 
209  auto CounterVar = Matches[0].getNodeAs<VarDecl>("initVarName");
210  llvm::APInt BoundNum =
211  Matches[0].getNodeAs<IntegerLiteral>("boundNum")->getValue();
212  llvm::APInt InitNum =
213  Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue();
214  auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator");
215  if (InitNum.getBitWidth() != BoundNum.getBitWidth()) {
216  InitNum = InitNum.zextOrSelf(BoundNum.getBitWidth());
217  BoundNum = BoundNum.zextOrSelf(InitNum.getBitWidth());
218  }
219 
220  if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE)
221  maxStep = (BoundNum - InitNum + 1).abs().getZExtValue();
222  else
223  maxStep = (BoundNum - InitNum).abs().getZExtValue();
224 
225  // Check if the counter of the loop is not escaped before.
226  return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred);
227 }
228 
229 bool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt) {
230  const Stmt *S = nullptr;
231  while (!N->pred_empty()) {
232  if (N->succ_size() > 1)
233  return true;
234 
235  ProgramPoint P = N->getLocation();
237  S = BE->getBlock()->getTerminatorStmt();
238 
239  if (S == LoopStmt)
240  return false;
241 
242  N = N->getFirstPred();
243  }
244 
245  llvm_unreachable("Reached root without encountering the previous step");
246 }
247 
248 // updateLoopStack is called on every basic block, therefore it needs to be fast
250  ExplodedNode *Pred, unsigned maxVisitOnPath) {
251  auto State = Pred->getState();
252  auto LCtx = Pred->getLocationContext();
253 
254  if (!isLoopStmt(LoopStmt))
255  return State;
256 
257  auto LS = State->get<LoopStack>();
258  if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() &&
259  LCtx == LS.getHead().getLocationContext()) {
260  if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) {
261  State = State->set<LoopStack>(LS.getTail());
262  State = State->add<LoopStack>(
263  LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
264  }
265  return State;
266  }
267  unsigned maxStep;
268  if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred, maxStep)) {
269  State = State->add<LoopStack>(
270  LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
271  return State;
272  }
273 
274  unsigned outerStep = (LS.isEmpty() ? 1 : LS.getHead().getMaxStep());
275 
276  unsigned innerMaxStep = maxStep * outerStep;
277  if (innerMaxStep > MAXIMUM_STEP_UNROLLED)
278  State = State->add<LoopStack>(
279  LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
280  else
281  State = State->add<LoopStack>(
282  LoopState::getUnrolled(LoopStmt, LCtx, innerMaxStep));
283  return State;
284 }
285 
287  auto LS = State->get<LoopStack>();
288  if (LS.isEmpty() || !LS.getHead().isUnrolled())
289  return false;
290  return true;
291 }
292 }
293 }
const internal::VariadicDynCastAllOfMatcher< Stmt, CallExpr > callExpr
Matches call expressions.
const internal::VariadicAllOfMatcher< Stmt > stmt
Matches statements.
static LoopState getUnrolled(const Stmt *S, const LocationContext *L, unsigned N)
const internal::ArgumentAdaptingMatcherFunc< internal::HasMatcher > has
Matches AST nodes that have child AST nodes that match the provided matcher.
bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx, ExplodedNode *Pred, unsigned &maxStep)
Stmt - This represents one statement.
Definition: Stmt.h:66
internal::PolymorphicMatcherWithParam1< internal::HasDeclarationMatcher, internal::Matcher< Decl >, void(internal::HasDeclarationSupportedTypes)> hasDeclaration(const internal::Matcher< Decl > &InnerMatcher)
Matches a node if the declaration associated with that node matches the given matcher.
Definition: ASTMatchers.h:2971
const internal::VariadicOperatorMatcherFunc< 2, std::numeric_limits< unsigned >::max()> anyOf
Matches if any of the given matchers matches.
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:88
__DEVICE__ long long abs(long long __n)
StringRef P
const internal::ArgumentAdaptingMatcherFunc< internal::HasDescendantMatcher > hasDescendant
Matches AST nodes that have descendant AST nodes that match the provided matcher. ...
const ProgramStateRef & getState() const
Represents a variable declaration or definition.
Definition: Decl.h:812
ASTContext & getASTContext() const
const internal::VariadicOperatorMatcherFunc< 2, std::numeric_limits< unsigned >::max()> allOf
Matches if all given matchers match.
const internal::VariadicDynCastAllOfMatcher< Stmt, BinaryOperator > binaryOperator
Matches binary operator expressions.
bool isUnrolledState(ProgramStateRef State)
Returns if the given State indicates that is inside a completely unrolled loop.
const internal::VariadicDynCastAllOfMatcher< Decl, VarDecl > varDecl
Matches variable declarations.
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:154
LineState State
ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State)
Updates the given ProgramState.
const internal::VariadicDynCastAllOfMatcher< Stmt, GotoStmt > gotoStmt
Matches goto statements.
const internal::VariadicDynCastAllOfMatcher< Stmt, DeclStmt > declStmt
Matches declaration statements.
unsigned succ_size() const
const internal::VariadicDynCastAllOfMatcher< Stmt, DeclRefExpr > declRefExpr
Matches expressions that refer to declarations.
ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx, ExplodedNode *Pred, unsigned maxVisitOnPath)
Updates the stack of loops contained by the ProgramState.
bool isUnrolled() const
const LocationContext * getLocationContext() const
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3404
ExplodedNode * getFirstPred()
SmallVector< BoundNodes, 1 > match(MatcherT Matcher, const NodeT &Node, ASTContext &Context)
Returns the results of matching Matcher on Node.
const LocationContext * getLocationContext() const
static internal::Matcher< Stmt > assignedToRef(internal::Matcher< Decl > VarNodeMatcher)
static const int MAXIMUM_STEP_UNROLLED
const internal::VariadicDynCastAllOfMatcher< Stmt, SwitchStmt > switchStmt
Matches switch statements.
#define REGISTER_LIST_WITH_PROGRAMSTATE(Name, Elem)
Declares an immutable list type NameTy, suitable for placement into the ProgramState.
static SVal getValue(SVal val, SValBuilder &svalBuilder)
const internal::VariadicDynCastAllOfMatcher< Stmt, ReturnStmt > returnStmt
Matches return statements.
const Stmt * getLoopStmt() const
static const Stmt * getStmt(const ExplodedNode *N)
Given an exploded node, retrieve the statement that should be used for the diagnostic location...
const internal::VariadicDynCastAllOfMatcher< Decl, ParmVarDecl > parmVarDecl
Matches parameter variable declarations.
unsigned getMaxStep() const
bool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt)
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:1203
const internal::VariadicDynCastAllOfMatcher< Stmt, IntegerLiteral > integerLiteral
Matches integer literals of all sizes / encodings, e.g.
bool hasGlobalStorage() const
Returns true for all variables that do not have local storage.
Definition: Decl.h:1077
const internal::VariadicAllOfMatcher< QualType > qualType
Matches QualTypes in the clang AST.
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
const internal::VariadicOperatorMatcherFunc< 1, 1 > unless
Matches if the provided matcher does not match.
const internal::VariadicDynCastAllOfMatcher< Stmt, ForStmt > forStmt
Matches for statements.
Dataflow Directional Tag Classes.
static LoopState getNormal(const Stmt *S, const LocationContext *L, unsigned N)
static bool isLoopStmt(const Stmt *S)
const internal::VariadicDynCastAllOfMatcher< Stmt, InitListExpr > initListExpr
Matches init list expressions.
static internal::Matcher< Stmt > forLoopMatcher()
internal::Matcher< BinaryOperator > hasEitherOperand(const internal::Matcher< Expr > &InnerMatcher)
Matches if either the left hand side or the right hand side of a binary operator matches.
Definition: ASTMatchers.h:4585
const internal::VariadicDynCastAllOfMatcher< Stmt, UnaryOperator > unaryOperator
Matches unary operator expressions.
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:14148
static internal::Matcher< Stmt > changeIntBoundNode(internal::Matcher< Decl > VarNodeMatcher)
static internal::Matcher< Stmt > hasSuspiciousStmt(StringRef NodeName)
static internal::Matcher< Stmt > simpleCondition(StringRef BindName)
static internal::Matcher< Stmt > callByRef(internal::Matcher< Decl > VarNodeMatcher)
static bool isPossiblyEscaped(const VarDecl *VD, ExplodedNode *N)
bool operator==(const LoopState &X) const
Optional< T > getAs() const
Convert to the specified ProgramPoint type, returning None if this ProgramPoint is not of the desired...
Definition: ProgramPoint.h:151
static internal::Matcher< Stmt > getAddrTo(internal::Matcher< Decl > VarNodeMatcher)
AnalysisDeclContext * getAnalysisDeclContext() const
const AstTypeMatcher< ReferenceType > referenceType
Matches both lvalue and rvalue reference types.
void Profile(llvm::FoldingSetNodeID &ID) const