Coverage Report

Created: 2019-07-24 05:18

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