Coverage Report

Created: 2020-09-15 12:33

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Core/LoopUnrolling.cpp
Line
Count
Source (jump to first uncovered line)
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
15
#include "clang/ASTMatchers/ASTMatchers.h"
16
#include "clang/ASTMatchers/ASTMatchFinder.h"
17
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
18
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
19
#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"
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
189
      : K(InK), LoopStmt(S), LCtx(L), maxStep(N) {}
35
36
public:
37
  static LoopState getNormal(const Stmt *S, const LocationContext *L,
38
87
                             unsigned N) {
39
87
    return LoopState(Normal, S, L, N);
40
87
  }
41
  static LoopState getUnrolled(const Stmt *S, const LocationContext *L,
42
102
                               unsigned N) {
43
102
    return LoopState(Unrolled, S, L, N);
44
102
  }
45
7.32k
  bool isUnrolled() const { return K == Unrolled; }
46
64
  unsigned getMaxStep() const { return maxStep; }
47
1.91k
  const Stmt *getLoopStmt() const { return LoopStmt; }
48
1.70k
  const LocationContext *getLocationContext() const { return LCtx; }
49
0
  bool operator==(const LoopState &X) const {
50
0
    return K == X.K && LoopStmt == X.LoopStmt;
51
0
  }
52
228
  void Profile(llvm::FoldingSetNodeID &ID) const {
53
228
    ID.AddInteger(K);
54
228
    ID.AddPointer(LoopStmt);
55
228
    ID.AddPointer(LCtx);
56
228
    ID.AddInteger(maxStep);
57
228
  }
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.
66
REGISTER_LIST_WITH_PROGRAMSTATE(LoopStack, LoopState)
67
68
namespace clang {
69
namespace ento {
70
71
2.18k
static bool isLoopStmt(const Stmt *S) {
72
2.18k
  return S && (isa<ForStmt>(S) || 
isa<WhileStmt>(S)160
||
isa<DoStmt>(S)160
);
73
2.18k
}
74
75
144
ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) {
76
144
  auto LS = State->get<LoopStack>();
77
144
  if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt)
78
144
    State = State->set<LoopStack>(LS.getTail());
79
144
  return State;
80
144
}
81
82
165
static internal::Matcher<Stmt> simpleCondition(StringRef BindName) {
83
165
  return binaryOperator(anyOf(hasOperatorName("<"), hasOperatorName(">"),
84
165
                              hasOperatorName("<="), hasOperatorName(">="),
85
165
                              hasOperatorName("!=")),
86
165
                        hasEitherOperand(ignoringParenImpCasts(declRefExpr(
87
165
                            to(varDecl(hasType(isInteger())).bind(BindName))))),
88
165
                        hasEitherOperand(ignoringParenImpCasts(
89
165
                            integerLiteral().bind("boundNum"))))
90
165
      .bind("conditionOperator");
91
165
}
92
93
static internal::Matcher<Stmt>
94
165
changeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher) {
95
165
  return anyOf(
96
165
      unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")),
97
165
                    hasUnaryOperand(ignoringParenImpCasts(
98
165
                        declRefExpr(to(varDecl(VarNodeMatcher)))))),
99
165
      binaryOperator(isAssignmentOperator(),
100
165
                     hasLHS(ignoringParenImpCasts(
101
165
                         declRefExpr(to(varDecl(VarNodeMatcher)))))));
102
165
}
103
104
static internal::Matcher<Stmt>
105
16.1k
callByRef(internal::Matcher<Decl> VarNodeMatcher) {
106
16.1k
  return callExpr(forEachArgumentWithParam(
107
16.1k
      declRefExpr(to(varDecl(VarNodeMatcher))),
108
16.1k
      parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))));
109
16.1k
}
110
111
static internal::Matcher<Stmt>
112
16.1k
assignedToRef(internal::Matcher<Decl> VarNodeMatcher) {
113
16.1k
  return declStmt(hasDescendant(varDecl(
114
16.1k
      allOf(hasType(referenceType()),
115
16.1k
            hasInitializer(anyOf(
116
16.1k
                initListExpr(has(declRefExpr(to(varDecl(VarNodeMatcher))))),
117
16.1k
                declRefExpr(to(varDecl(VarNodeMatcher)))))))));
118
16.1k
}
119
120
static internal::Matcher<Stmt>
121
16.1k
getAddrTo(internal::Matcher<Decl> VarNodeMatcher) {
122
16.1k
  return unaryOperator(
123
16.1k
      hasOperatorName("&"),
124
16.1k
      hasUnaryOperand(declRefExpr(hasDeclaration(VarNodeMatcher))));
125
16.1k
}
126
127
165
static internal::Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) {
128
165
  return hasDescendant(stmt(
129
165
      anyOf(gotoStmt(), switchStmt(), returnStmt(),
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
165
            changeIntBoundNode(equalsBoundNode(std::string(NodeName))),
134
165
            callByRef(equalsBoundNode(std::string(NodeName))),
135
165
            getAddrTo(equalsBoundNode(std::string(NodeName))),
136
165
            assignedToRef(equalsBoundNode(std::string(NodeName))))));
137
165
}
138
139
165
static internal::Matcher<Stmt> forLoopMatcher() {
140
165
  return forStmt(
141
165
             hasCondition(simpleCondition("initVarName")),
142
             // Initialization should match the form: 'int i = 6' or 'i = 42'.
143
165
             hasLoopInit(
144
165
                 anyOf(declStmt(hasSingleDecl(
145
165
                           varDecl(allOf(hasInitializer(ignoringParenImpCasts(
146
165
                                             integerLiteral().bind("initNum"))),
147
165
                                         equalsBoundNode("initVarName"))))),
148
165
                       binaryOperator(hasLHS(declRefExpr(to(varDecl(
149
165
                                          equalsBoundNode("initVarName"))))),
150
165
                                      hasRHS(ignoringParenImpCasts(
151
165
                                          integerLiteral().bind("initNum")))))),
152
             // Incrementation should be a simple increment or decrement
153
             // operator call.
154
165
             hasIncrement(unaryOperator(
155
165
                 anyOf(hasOperatorName("++"), hasOperatorName("--")),
156
165
                 hasUnaryOperand(declRefExpr(
157
165
                     to(varDecl(allOf(equalsBoundNode("initVarName"),
158
165
                                      hasType(isInteger())))))))),
159
165
             unless(hasBody(hasSuspiciousStmt("initVarName")))).bind("forLoop");
160
165
}
161
162
114
static bool isPossiblyEscaped(const VarDecl *VD, ExplodedNode *N) {
163
  // Global variables assumed as escaped variables.
164
114
  if (VD->hasGlobalStorage())
165
0
    return true;
166
114
167
114
  const bool isParm = isa<ParmVarDecl>(VD);
168
  // Reference parameters are assumed as escaped variables.
169
114
  if (isParm && 
VD->getType()->isReferenceType()2
)
170
0
    return true;
171
114
172
18.4k
  
while (114
!N->pred_empty()) {
173
    // FIXME: getStmtForDiagnostics() does nasty things in order to provide
174
    // a valid statement for body farms, do we need this behavior here?
175
18.4k
    const Stmt *S = N->getStmtForDiagnostics();
176
18.4k
    if (!S) {
177
2.40k
      N = N->getFirstPred();
178
2.40k
      continue;
179
2.40k
    }
180
16.0k
181
16.0k
    if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) {
182
180
      for (const Decl *D : DS->decls()) {
183
        // Once we reach the declaration of the VD we can return.
184
180
        if (D->getCanonicalDecl() == VD)
185
106
          return false;
186
180
      }
187
180
    }
188
    // Check the usage of the pass-by-ref function calls and adress-of operator
189
    // on VD and reference initialized by VD.
190
15.9k
    ASTContext &ASTCtx =
191
15.9k
        N->getLocationContext()->getAnalysisDeclContext()->getASTContext();
192
15.9k
    auto Match =
193
15.9k
        match(stmt(anyOf(callByRef(equalsNode(VD)), getAddrTo(equalsNode(VD)),
194
15.9k
                         assignedToRef(equalsNode(VD)))),
195
15.9k
              *S, ASTCtx);
196
15.9k
    if (!Match.empty())
197
6
      return true;
198
15.9k
199
15.9k
    N = N->getFirstPred();
200
15.9k
  }
201
114
202
  // Parameter declaration will not be found.
203
2
  if (isParm)
204
2
    return false;
205
0
206
0
  llvm_unreachable("Reached root without finding the declaration of VD");
207
0
}
208
209
bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
210
165
                            ExplodedNode *Pred, unsigned &maxStep) {
211
165
212
165
  if (!isLoopStmt(LoopStmt))
213
0
    return false;
214
165
215
  // TODO: Match the cases where the bound is not a concrete literal but an
216
  // integer with known value
217
165
  auto Matches = match(forLoopMatcher(), *LoopStmt, ASTCtx);
218
165
  if (Matches.empty())
219
51
    return false;
220
114
221
114
  auto CounterVar = Matches[0].getNodeAs<VarDecl>("initVarName");
222
114
  llvm::APInt BoundNum =
223
114
      Matches[0].getNodeAs<IntegerLiteral>("boundNum")->getValue();
224
114
  llvm::APInt InitNum =
225
114
      Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue();
226
114
  auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator");
227
114
  if (InitNum.getBitWidth() != BoundNum.getBitWidth()) {
228
2
    InitNum = InitNum.zextOrSelf(BoundNum.getBitWidth());
229
2
    BoundNum = BoundNum.zextOrSelf(InitNum.getBitWidth());
230
2
  }
231
114
232
114
  if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE)
233
4
    maxStep = (BoundNum - InitNum + 1).abs().getZExtValue();
234
110
  else
235
110
    maxStep = (BoundNum - InitNum).abs().getZExtValue();
236
114
237
  // Check if the counter of the loop is not escaped before.
238
114
  return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred);
239
114
}
240
241
1.36k
bool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt) {
242
1.36k
  const Stmt *S = nullptr;
243
56.8k
  while (!N->pred_empty()) {
244
56.8k
    if (N->succ_size() > 1)
245
24
      return true;
246
56.8k
247
56.8k
    ProgramPoint P = N->getLocation();
248
56.8k
    if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>())
249
5.76k
      S = BE->getBlock()->getTerminatorStmt();
250
56.8k
251
56.8k
    if (S == LoopStmt)
252
1.33k
      return false;
253
55.4k
254
55.4k
    N = N->getFirstPred();
255
55.4k
  }
256
1.36k
257
1.36k
  
llvm_unreachable0
("Reached root without encountering the previous step");
258
1.36k
}
259
260
// updateLoopStack is called on every basic block, therefore it needs to be fast
261
ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx,
262
2.02k
                                ExplodedNode *Pred, unsigned maxVisitOnPath) {
263
2.02k
  auto State = Pred->getState();
264
2.02k
  auto LCtx = Pred->getLocationContext();
265
2.02k
266
2.02k
  if (!isLoopStmt(LoopStmt))
267
160
    return State;
268
1.86k
269
1.86k
  auto LS = State->get<LoopStack>();
270
1.86k
  if (!LS.isEmpty() && 
LoopStmt == LS.getHead().getLoopStmt()1.77k
&&
271
1.70k
      LCtx == LS.getHead().getLocationContext()) {
272
1.69k
    if (LS.getHead().isUnrolled() && 
madeNewBranch(Pred, LoopStmt)1.36k
) {
273
24
      State = State->set<LoopStack>(LS.getTail());
274
24
      State = State->add<LoopStack>(
275
24
          LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
276
24
    }
277
1.69k
    return State;
278
1.69k
  }
279
165
  unsigned maxStep;
280
165
  if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred, maxStep)) {
281
57
    State = State->add<LoopStack>(
282
57
        LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
283
57
    return State;
284
57
  }
285
108
286
108
  unsigned outerStep = (LS.isEmpty() ? 
144
:
LS.getHead().getMaxStep()64
);
287
108
288
108
  unsigned innerMaxStep = maxStep * outerStep;
289
108
  if (innerMaxStep > MAXIMUM_STEP_UNROLLED)
290
6
    State = State->add<LoopStack>(
291
6
        LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
292
102
  else
293
102
    State = State->add<LoopStack>(
294
102
        LoopState::getUnrolled(LoopStmt, LCtx, innerMaxStep));
295
108
  return State;
296
108
}
297
298
5.72k
bool isUnrolledState(ProgramStateRef State) {
299
5.72k
  auto LS = State->get<LoopStack>();
300
5.72k
  if (LS.isEmpty() || 
!LS.getHead().isUnrolled()5.62k
)
301
1.36k
    return false;
302
4.36k
  return true;
303
4.36k
}
304
}
305
}