Coverage Report

Created: 2020-09-19 12:23

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