Coverage Report

Created: 2020-02-15 09:57

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Analysis/LiveVariables.cpp
Line
Count
Source (jump to first uncovered line)
1
//=- LiveVariables.cpp - Live Variable Analysis for Source CFGs ----------*-==//
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 implements Live Variables analysis for source-level CFGs.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "clang/Analysis/Analyses/LiveVariables.h"
14
#include "clang/AST/Stmt.h"
15
#include "clang/AST/StmtVisitor.h"
16
#include "clang/Analysis/AnalysisDeclContext.h"
17
#include "clang/Analysis/CFG.h"
18
#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
19
#include "llvm/ADT/DenseMap.h"
20
#include "llvm/Support/raw_ostream.h"
21
#include <algorithm>
22
#include <vector>
23
24
using namespace clang;
25
26
namespace {
27
class LiveVariablesImpl {
28
public:
29
  AnalysisDeclContext &analysisContext;
30
  llvm::ImmutableSet<const Stmt *>::Factory SSetFact;
31
  llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;
32
  llvm::ImmutableSet<const BindingDecl *>::Factory BSetFact;
33
  llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;
34
  llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;
35
  llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness;
36
  llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment;
37
  const bool killAtAssign;
38
39
  LiveVariables::LivenessValues
40
  merge(LiveVariables::LivenessValues valsA,
41
        LiveVariables::LivenessValues valsB);
42
43
  LiveVariables::LivenessValues
44
  runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val,
45
             LiveVariables::Observer *obs = nullptr);
46
47
  void dumpBlockLiveness(const SourceManager& M);
48
  void dumpStmtLiveness(const SourceManager& M);
49
50
  LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign)
51
    : analysisContext(ac),
52
      SSetFact(false), // Do not canonicalize ImmutableSets by default.
53
      DSetFact(false), // This is a *major* performance win.
54
      BSetFact(false),
55
21.7k
      killAtAssign(KillAtAssign) {}
56
};
57
}
58
59
1.77M
static LiveVariablesImpl &getImpl(void *x) {
60
1.77M
  return *((LiveVariablesImpl *) x);
61
1.77M
}
62
63
//===----------------------------------------------------------------------===//
64
// Operations and queries on LivenessValues.
65
//===----------------------------------------------------------------------===//
66
67
1.31M
bool LiveVariables::LivenessValues::isLive(const Stmt *S) const {
68
1.31M
  return liveStmts.contains(S);
69
1.31M
}
70
71
456k
bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const {
72
456k
  if (const auto *DD = dyn_cast<DecompositionDecl>(D)) {
73
30
    bool alive = false;
74
30
    for (const BindingDecl *BD : DD->bindings())
75
60
      alive |= liveBindings.contains(BD);
76
30
    return alive;
77
30
  }
78
456k
  return liveDecls.contains(D);
79
456k
}
80
81
namespace {
82
  template <typename SET>
83
202k
  SET mergeSets(SET A, SET B) {
84
202k
    if (A.isEmpty())
85
196k
      return B;
86
6.57k
87
13.3k
    
for (typename SET::iterator it = B.begin(), ei = B.end(); 6.57k
it != ei;
++it6.78k
) {
88
6.78k
      A = A.add(*it);
89
6.78k
    }
90
6.57k
    return A;
91
6.57k
  }
LiveVariables.cpp:llvm::ImmutableSetRef<clang::Stmt const*, llvm::ImutContainerInfo<clang::Stmt const*> > (anonymous namespace)::mergeSets<llvm::ImmutableSetRef<clang::Stmt const*, llvm::ImutContainerInfo<clang::Stmt const*> > >(llvm::ImmutableSetRef<clang::Stmt const*, llvm::ImutContainerInfo<clang::Stmt const*> >, llvm::ImmutableSetRef<clang::Stmt const*, llvm::ImutContainerInfo<clang::Stmt const*> >)
Line
Count
Source
83
67.6k
  SET mergeSets(SET A, SET B) {
84
67.6k
    if (A.isEmpty())
85
66.1k
      return B;
86
1.52k
87
4.34k
    
for (typename SET::iterator it = B.begin(), ei = B.end(); 1.52k
it != ei;
++it2.82k
) {
88
2.82k
      A = A.add(*it);
89
2.82k
    }
90
1.52k
    return A;
91
1.52k
  }
LiveVariables.cpp:llvm::ImmutableSetRef<clang::VarDecl const*, llvm::ImutContainerInfo<clang::VarDecl const*> > (anonymous namespace)::mergeSets<llvm::ImmutableSetRef<clang::VarDecl const*, llvm::ImutContainerInfo<clang::VarDecl const*> > >(llvm::ImmutableSetRef<clang::VarDecl const*, llvm::ImutContainerInfo<clang::VarDecl const*> >, llvm::ImmutableSetRef<clang::VarDecl const*, llvm::ImutContainerInfo<clang::VarDecl const*> >)
Line
Count
Source
83
67.6k
  SET mergeSets(SET A, SET B) {
84
67.6k
    if (A.isEmpty())
85
62.6k
      return B;
86
5.05k
87
9.01k
    
for (typename SET::iterator it = B.begin(), ei = B.end(); 5.05k
it != ei;
++it3.96k
) {
88
3.96k
      A = A.add(*it);
89
3.96k
    }
90
5.05k
    return A;
91
5.05k
  }
LiveVariables.cpp:llvm::ImmutableSetRef<clang::BindingDecl const*, llvm::ImutContainerInfo<clang::BindingDecl const*> > (anonymous namespace)::mergeSets<llvm::ImmutableSetRef<clang::BindingDecl const*, llvm::ImutContainerInfo<clang::BindingDecl const*> > >(llvm::ImmutableSetRef<clang::BindingDecl const*, llvm::ImutContainerInfo<clang::BindingDecl const*> >, llvm::ImmutableSetRef<clang::BindingDecl const*, llvm::ImutContainerInfo<clang::BindingDecl const*> >)
Line
Count
Source
83
67.6k
  SET mergeSets(SET A, SET B) {
84
67.6k
    if (A.isEmpty())
85
67.6k
      return B;
86
0
87
0
    for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
88
0
      A = A.add(*it);
89
0
    }
90
0
    return A;
91
0
  }
92
} // namespace
93
94
0
void LiveVariables::Observer::anchor() { }
95
96
LiveVariables::LivenessValues
97
LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,
98
67.6k
                         LiveVariables::LivenessValues valsB) {
99
67.6k
100
67.6k
  llvm::ImmutableSetRef<const Stmt *>
101
67.6k
    SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()),
102
67.6k
    SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory());
103
67.6k
104
67.6k
105
67.6k
  llvm::ImmutableSetRef<const VarDecl *>
106
67.6k
    DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),
107
67.6k
    DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());
108
67.6k
109
67.6k
  llvm::ImmutableSetRef<const BindingDecl *>
110
67.6k
    BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()),
111
67.6k
    BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory());
112
67.6k
113
67.6k
  SSetRefA = mergeSets(SSetRefA, SSetRefB);
114
67.6k
  DSetRefA = mergeSets(DSetRefA, DSetRefB);
115
67.6k
  BSetRefA = mergeSets(BSetRefA, BSetRefB);
116
67.6k
117
67.6k
  // asImmutableSet() canonicalizes the tree, allowing us to do an easy
118
67.6k
  // comparison afterwards.
119
67.6k
  return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(),
120
67.6k
                                       DSetRefA.asImmutableSet(),
121
67.6k
                                       BSetRefA.asImmutableSet());
122
67.6k
}
123
124
3.41k
bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const {
125
3.41k
  return liveStmts == V.liveStmts && 
liveDecls == V.liveDecls2.76k
;
126
3.41k
}
127
128
//===----------------------------------------------------------------------===//
129
// Query methods.
130
//===----------------------------------------------------------------------===//
131
132
529k
static bool isAlwaysAlive(const VarDecl *D) {
133
529k
  return D->hasGlobalStorage();
134
529k
}
135
136
0
bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {
137
0
  return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);
138
0
}
139
140
456k
bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
141
456k
  return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);
142
456k
}
143
144
1.31M
bool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) {
145
1.31M
  return getImpl(impl).stmtsToLiveness[Loc].isLive(S);
146
1.31M
}
147
148
//===----------------------------------------------------------------------===//
149
// Dataflow computation.
150
//===----------------------------------------------------------------------===//
151
152
namespace {
153
class TransferFunctions : public StmtVisitor<TransferFunctions> {
154
  LiveVariablesImpl &LV;
155
  LiveVariables::LivenessValues &val;
156
  LiveVariables::Observer *observer;
157
  const CFGBlock *currentBlock;
158
public:
159
  TransferFunctions(LiveVariablesImpl &im,
160
                    LiveVariables::LivenessValues &Val,
161
                    LiveVariables::Observer *Observer,
162
                    const CFGBlock *CurrentBlock)
163
83.1k
  : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}
164
165
  void VisitBinaryOperator(BinaryOperator *BO);
166
  void VisitBlockExpr(BlockExpr *BE);
167
  void VisitDeclRefExpr(DeclRefExpr *DR);
168
  void VisitDeclStmt(DeclStmt *DS);
169
  void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS);
170
  void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE);
171
  void VisitUnaryOperator(UnaryOperator *UO);
172
  void Visit(Stmt *S);
173
};
174
} // namespace
175
176
17.9k
static const VariableArrayType *FindVA(QualType Ty) {
177
17.9k
  const Type *ty = Ty.getTypePtr();
178
19.0k
  while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) {
179
1.16k
    if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT))
180
49
      if (VAT->getSizeExpr())
181
49
        return VAT;
182
1.11k
183
1.11k
    ty = VT->getElementType().getTypePtr();
184
1.11k
  }
185
17.9k
186
17.9k
  
return nullptr17.9k
;
187
17.9k
}
188
189
306k
static const Stmt *LookThroughStmt(const Stmt *S) {
190
309k
  while (S) {
191
309k
    if (const Expr *Ex = dyn_cast<Expr>(S))
192
308k
      S = Ex->IgnoreParens();
193
309k
    if (const FullExpr *FE = dyn_cast<FullExpr>(S)) {
194
3.07k
      S = FE->getSubExpr();
195
3.07k
      continue;
196
3.07k
    }
197
306k
    if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(S)) {
198
701
      S = OVE->getSourceExpr();
199
701
      continue;
200
701
    }
201
305k
    break;
202
305k
  }
203
306k
  return S;
204
306k
}
205
206
static void AddLiveStmt(llvm::ImmutableSet<const Stmt *> &Set,
207
                        llvm::ImmutableSet<const Stmt *>::Factory &F,
208
306k
                        const Stmt *S) {
209
306k
  Set = F.add(Set, LookThroughStmt(S));
210
306k
}
211
212
366k
void TransferFunctions::Visit(Stmt *S) {
213
366k
  if (observer)
214
8.62k
    observer->observeStmt(S, currentBlock, val);
215
366k
216
366k
  StmtVisitor<TransferFunctions>::Visit(S);
217
366k
218
366k
  if (isa<Expr>(S)) {
219
333k
    val.liveStmts = LV.SSetFact.remove(val.liveStmts, S);
220
333k
  }
221
366k
222
366k
  // Mark all children expressions live.
223
366k
224
366k
  switch (S->getStmtClass()) {
225
331k
    default:
226
331k
      break;
227
130
    case Stmt::StmtExprClass: {
228
130
      // For statement expressions, look through the compound statement.
229
130
      S = cast<StmtExpr>(S)->getSubStmt();
230
130
      break;
231
0
    }
232
4.25k
    case Stmt::CXXMemberCallExprClass: {
233
4.25k
      // Include the implicit "this" pointer as being live.
234
4.25k
      CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);
235
4.25k
      if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) {
236
4.25k
        AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj);
237
4.25k
      }
238
4.25k
      break;
239
0
    }
240
3.97k
    case Stmt::ObjCMessageExprClass: {
241
3.97k
      // In calls to super, include the implicit "self" pointer as being live.
242
3.97k
      ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S);
243
3.97k
      if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance)
244
295
        val.liveDecls = LV.DSetFact.add(val.liveDecls,
245
295
                                        LV.analysisContext.getSelfDecl());
246
3.97k
      break;
247
0
    }
248
17.9k
    case Stmt::DeclStmtClass: {
249
17.9k
      const DeclStmt *DS = cast<DeclStmt>(S);
250
17.9k
      if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) {
251
17.9k
        for (const VariableArrayType* VA = FindVA(VD->getType());
252
17.9k
             VA != nullptr; 
VA = FindVA(VA->getElementType())49
) {
253
49
          AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr());
254
49
        }
255
17.9k
      }
256
17.9k
      break;
257
0
    }
258
375
    case Stmt::PseudoObjectExprClass: {
259
375
      // A pseudo-object operation only directly consumes its result
260
375
      // expression.
261
375
      Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();
262
375
      if (!child) 
return0
;
263
375
      if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child))
264
80
        child = OV->getSourceExpr();
265
375
      child = child->IgnoreParens();
266
375
      val.liveStmts = LV.SSetFact.add(val.liveStmts, child);
267
375
      return;
268
375
    }
269
375
270
375
    // FIXME: These cases eventually shouldn't be needed.
271
375
    case Stmt::ExprWithCleanupsClass: {
272
0
      S = cast<ExprWithCleanups>(S)->getSubExpr();
273
0
      break;
274
375
    }
275
1.70k
    case Stmt::CXXBindTemporaryExprClass: {
276
1.70k
      S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
277
1.70k
      break;
278
375
    }
279
703
    case Stmt::UnaryExprOrTypeTraitExprClass: {
280
703
      // No need to unconditionally visit subexpressions.
281
703
      return;
282
375
    }
283
4.28k
    case Stmt::IfStmtClass: {
284
4.28k
      // If one of the branches is an expression rather than a compound
285
4.28k
      // statement, it will be bad if we mark it as live at the terminator
286
4.28k
      // of the if-statement (i.e., immediately after the condition expression).
287
4.28k
      AddLiveStmt(val.liveStmts, LV.SSetFact, cast<IfStmt>(S)->getCond());
288
4.28k
      return;
289
375
    }
290
375
    case Stmt::WhileStmtClass: {
291
319
      // If the loop body is an expression rather than a compound statement,
292
319
      // it will be bad if we mark it as live at the terminator of the loop
293
319
      // (i.e., immediately after the condition expression).
294
319
      AddLiveStmt(val.liveStmts, LV.SSetFact, cast<WhileStmt>(S)->getCond());
295
319
      return;
296
375
    }
297
375
    case Stmt::DoStmtClass: {
298
174
      // If the loop body is an expression rather than a compound statement,
299
174
      // it will be bad if we mark it as live at the terminator of the loop
300
174
      // (i.e., immediately after the condition expression).
301
174
      AddLiveStmt(val.liveStmts, LV.SSetFact, cast<DoStmt>(S)->getCond());
302
174
      return;
303
375
    }
304
703
    case Stmt::ForStmtClass: {
305
703
      // If the loop body is an expression rather than a compound statement,
306
703
      // it will be bad if we mark it as live at the terminator of the loop
307
703
      // (i.e., immediately after the condition expression).
308
703
      AddLiveStmt(val.liveStmts, LV.SSetFact, cast<ForStmt>(S)->getCond());
309
703
      return;
310
359k
    }
311
359k
312
359k
  }
313
359k
314
359k
  for (Stmt *Child : S->children()) {
315
296k
    if (Child)
316
296k
      AddLiveStmt(val.liveStmts, LV.SSetFact, Child);
317
296k
  }
318
359k
}
319
320
541
static bool writeShouldKill(const VarDecl *VD) {
321
541
  return VD && !VD->getType()->isReferenceType() &&
322
541
    
!isAlwaysAlive(VD)529
;
323
541
}
324
325
21.4k
void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
326
21.4k
  if (B->isAssignmentOp()) {
327
7.67k
    if (!LV.killAtAssign)
328
6.82k
      return;
329
853
330
853
    // Assigning to a variable?
331
853
    Expr *LHS = B->getLHS()->IgnoreParens();
332
853
333
853
    if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
334
555
      const Decl* D = DR->getDecl();
335
555
      bool Killed = false;
336
555
337
555
      if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) {
338
14
        Killed = !BD->getType()->isReferenceType();
339
14
        if (Killed)
340
14
          val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
341
541
      } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
342
541
        Killed = writeShouldKill(VD);
343
541
        if (Killed)
344
513
          val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
345
541
346
541
      }
347
555
348
555
      if (Killed && 
observer527
)
349
246
        observer->observerKill(DR);
350
555
    }
351
853
  }
352
21.4k
}
353
354
416
void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
355
416
  for (const VarDecl *VD :
356
416
       LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) {
357
367
    if (isAlwaysAlive(VD))
358
44
      continue;
359
323
    val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
360
323
  }
361
416
}
362
363
83.0k
void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
364
83.0k
  const Decl* D = DR->getDecl();
365
83.0k
  bool InAssignment = LV.inAssignment[DR];
366
83.0k
  if (const auto *BD = dyn_cast<BindingDecl>(D)) {
367
52
    if (!InAssignment)
368
38
      val.liveBindings = LV.BSetFact.add(val.liveBindings, BD);
369
82.9k
  } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
370
54.6k
    if (!InAssignment && 
!isAlwaysAlive(VD)54.1k
)
371
51.9k
      val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
372
54.6k
  }
373
83.0k
}
374
375
17.9k
void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
376
17.9k
  for (const auto *DI : DS->decls()) {
377
17.9k
    if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) {
378
37
      for (const auto *BD : DD->bindings())
379
73
        val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
380
17.8k
    } else if (const auto *VD = dyn_cast<VarDecl>(DI)) {
381
17.8k
      if (!isAlwaysAlive(VD))
382
17.4k
        val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
383
17.8k
    }
384
17.9k
  }
385
17.9k
}
386
387
240
void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
388
240
  // Kill the iteration variable.
389
240
  DeclRefExpr *DR = nullptr;
390
240
  const VarDecl *VD = nullptr;
391
240
392
240
  Stmt *element = OS->getElement();
393
240
  if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
394
202
    VD = cast<VarDecl>(DS->getSingleDecl());
395
202
  }
396
38
  else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
397
38
    VD = cast<VarDecl>(DR->getDecl());
398
38
  }
399
240
400
240
  if (VD) {
401
240
    val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
402
240
    if (observer && 
DR12
)
403
2
      observer->observerKill(DR);
404
240
  }
405
240
}
406
407
void TransferFunctions::
408
VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
409
703
{
410
703
  // While sizeof(var) doesn't technically extend the liveness of 'var', it
411
703
  // does extent the liveness of metadata if 'var' is a VariableArrayType.
412
703
  // We handle that special case here.
413
703
  if (UE->getKind() != UETT_SizeOf || 
UE->isArgumentType()700
)
414
513
    return;
415
190
416
190
  const Expr *subEx = UE->getArgumentExpr();
417
190
  if (subEx->getType()->isVariableArrayType()) {
418
5
    assert(subEx->isLValue());
419
5
    val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens());
420
5
  }
421
190
}
422
423
10.4k
void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
424
10.4k
  // Treat ++/-- as a kill.
425
10.4k
  // Note we don't actually have to do anything if we don't have an observer,
426
10.4k
  // since a ++/-- acts as both a kill and a "use".
427
10.4k
  if (!observer)
428
10.0k
    return;
429
357
430
357
  switch (UO->getOpcode()) {
431
243
  default:
432
243
    return;
433
114
  case UO_PostInc:
434
114
  case UO_PostDec:
435
114
  case UO_PreInc:
436
114
  case UO_PreDec:
437
114
    break;
438
114
  }
439
114
440
114
  if (auto *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) {
441
107
    const Decl *D = DR->getDecl();
442
107
    if (isa<VarDecl>(D) || 
isa<BindingDecl>(D)0
) {
443
107
      // Treat ++/-- as a kill.
444
107
      observer->observerKill(DR);
445
107
    }
446
107
  }
447
114
}
448
449
LiveVariables::LivenessValues
450
LiveVariablesImpl::runOnBlock(const CFGBlock *block,
451
                              LiveVariables::LivenessValues val,
452
83.1k
                              LiveVariables::Observer *obs) {
453
83.1k
454
83.1k
  TransferFunctions TF(*this, val, obs, block);
455
83.1k
456
83.1k
  // Visit the terminator (if any).
457
83.1k
  if (const Stmt *term = block->getTerminatorStmt())
458
8.39k
    TF.Visit(const_cast<Stmt*>(term));
459
83.1k
460
83.1k
  // Apply the transfer function for all Stmts in the block.
461
83.1k
  for (CFGBlock::const_reverse_iterator it = block->rbegin(),
462
447k
       ei = block->rend(); it != ei; 
++it364k
) {
463
364k
    const CFGElement &elem = *it;
464
364k
465
364k
    if (Optional<CFGAutomaticObjDtor> Dtor =
466
614
            elem.getAs<CFGAutomaticObjDtor>()) {
467
614
      val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl());
468
614
      continue;
469
614
    }
470
363k
471
363k
    if (!elem.getAs<CFGStmt>())
472
6.32k
      continue;
473
357k
474
357k
    const Stmt *S = elem.castAs<CFGStmt>().getStmt();
475
357k
    TF.Visit(const_cast<Stmt*>(S));
476
357k
    stmtsToLiveness[S] = val;
477
357k
  }
478
83.1k
  return val;
479
83.1k
}
480
481
483
void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {
482
483
  const CFG *cfg = getImpl(impl).analysisContext.getCFG();
483
2.83k
  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; 
++it2.35k
)
484
2.35k
    getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
485
483
}
486
487
21.7k
LiveVariables::LiveVariables(void *im) : impl(im) {}
488
489
21.7k
LiveVariables::~LiveVariables() {
490
21.7k
  delete (LiveVariablesImpl*) impl;
491
21.7k
}
492
493
LiveVariables *
494
LiveVariables::computeLiveness(AnalysisDeclContext &AC,
495
21.7k
                                 bool killAtAssign) {
496
21.7k
497
21.7k
  // No CFG?  Bail out.
498
21.7k
  CFG *cfg = AC.getCFG();
499
21.7k
  if (!cfg)
500
0
    return nullptr;
501
21.7k
502
21.7k
  // The analysis currently has scalability issues for very large CFGs.
503
21.7k
  // Bail out if it looks too large.
504
21.7k
  if (cfg->getNumBlockIDs() > 300000)
505
0
    return nullptr;
506
21.7k
507
21.7k
  LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
508
21.7k
509
21.7k
  // Construct the dataflow worklist.  Enqueue the exit block as the
510
21.7k
  // start of the analysis.
511
21.7k
  BackwardDataflowWorklist worklist(*cfg, AC);
512
21.7k
  llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
513
21.7k
514
21.7k
  // FIXME: we should enqueue using post order.
515
100k
  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; 
++it78.5k
) {
516
78.5k
    const CFGBlock *block = *it;
517
78.5k
    worklist.enqueueBlock(block);
518
78.5k
519
78.5k
    // FIXME: Scan for DeclRefExprs using in the LHS of an assignment.
520
78.5k
    // We need to do this because we lack context in the reverse analysis
521
78.5k
    // to determine if a DeclRefExpr appears in such a context, and thus
522
78.5k
    // doesn't constitute a "use".
523
78.5k
    if (killAtAssign)
524
2.35k
      for (CFGBlock::const_iterator bi = block->begin(), be = block->end();
525
10.5k
           bi != be; 
++bi8.20k
) {
526
8.20k
        if (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) {
527
8.18k
          const Stmt* stmt = cs->getStmt();
528
8.18k
          if (const auto *BO = dyn_cast<BinaryOperator>(stmt)) {
529
788
            if (BO->getOpcode() == BO_Assign) {
530
374
              if (const auto *DR =
531
239
                    dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
532
239
                LV->inAssignment[DR] = 1;
533
239
              }
534
374
            }
535
788
          }
536
8.18k
        }
537
8.20k
      }
538
78.5k
  }
539
21.7k
540
103k
  while (const CFGBlock *block = worklist.dequeue()) {
541
81.9k
    // Determine if the block's end value has changed.  If not, we
542
81.9k
    // have nothing left to do for this block.
543
81.9k
    LivenessValues &prevVal = LV->blocksEndToLiveness[block];
544
81.9k
545
81.9k
    // Merge the values of all successor blocks.
546
81.9k
    LivenessValues val;
547
81.9k
    for (CFGBlock::const_succ_iterator it = block->succ_begin(),
548
150k
                                       ei = block->succ_end(); it != ei; 
++it68.7k
) {
549
68.7k
      if (const CFGBlock *succ = *it) {
550
67.6k
        val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
551
67.6k
      }
552
68.7k
    }
553
81.9k
554
81.9k
    if (!everAnalyzedBlock[block->getBlockID()])
555
78.5k
      everAnalyzedBlock[block->getBlockID()] = true;
556
3.41k
    else if (prevVal.equals(val))
557
1.15k
      continue;
558
80.8k
559
80.8k
    prevVal = val;
560
80.8k
561
80.8k
    // Update the dataflow value for the start of this block.
562
80.8k
    LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
563
80.8k
564
80.8k
    // Enqueue the value to the predecessors.
565
80.8k
    worklist.enqueuePredecessors(block);
566
80.8k
  }
567
21.7k
568
21.7k
  return new LiveVariables(LV);
569
21.7k
}
570
571
0
void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
572
0
  getImpl(impl).dumpBlockLiveness(M);
573
0
}
574
575
0
void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
576
0
  std::vector<const CFGBlock *> vec;
577
0
  for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
578
0
       it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
579
0
       it != ei; ++it) {
580
0
    vec.push_back(it->first);
581
0
  }
582
0
  llvm::sort(vec, [](const CFGBlock *A, const CFGBlock *B) {
583
0
    return A->getBlockID() < B->getBlockID();
584
0
  });
585
0
586
0
  std::vector<const VarDecl*> declVec;
587
0
588
0
  for (std::vector<const CFGBlock *>::iterator
589
0
        it = vec.begin(), ei = vec.end(); it != ei; ++it) {
590
0
    llvm::errs() << "\n[ B" << (*it)->getBlockID()
591
0
                 << " (live variables at block exit) ]\n";
592
0
593
0
    LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
594
0
    declVec.clear();
595
0
596
0
    for (llvm::ImmutableSet<const VarDecl *>::iterator si =
597
0
          vals.liveDecls.begin(),
598
0
          se = vals.liveDecls.end(); si != se; ++si) {
599
0
      declVec.push_back(*si);
600
0
    }
601
0
602
0
    llvm::sort(declVec, [](const Decl *A, const Decl *B) {
603
0
      return A->getBeginLoc() < B->getBeginLoc();
604
0
    });
605
0
606
0
    for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
607
0
         de = declVec.end(); di != de; ++di) {
608
0
      llvm::errs() << " " << (*di)->getDeclName().getAsString()
609
0
                   << " <";
610
0
      (*di)->getLocation().print(llvm::errs(), M);
611
0
      llvm::errs() << ">\n";
612
0
    }
613
0
  }
614
0
  llvm::errs() << "\n";
615
0
}
616
617
5
void LiveVariables::dumpStmtLiveness(const SourceManager &M) {
618
5
  getImpl(impl).dumpStmtLiveness(M);
619
5
}
620
621
5
void LiveVariablesImpl::dumpStmtLiveness(const SourceManager &M) {
622
5
  // Don't iterate over blockEndsToLiveness directly because it's not sorted.
623
36
  for (auto I : *analysisContext.getCFG()) {
624
36
625
36
    llvm::errs() << "\n[ B" << I->getBlockID()
626
36
                 << " (live statements at block exit) ]\n";
627
36
    for (auto S : blocksEndToLiveness[I].liveStmts) {
628
11
      llvm::errs() << "\n";
629
11
      S->dump();
630
11
    }
631
36
    llvm::errs() << "\n";
632
36
  }
633
5
}
634
635
483
const void *LiveVariables::getTag() { static int x; return &x; }
636
1.78M
const void *RelaxedLiveVariables::getTag() { static int x; return &x; }