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