Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// This file implements Live Variables analysis for source-level CFGs.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "clang/Analysis/Analyses/LiveVariables.h"
15
#include "clang/AST/Stmt.h"
16
#include "clang/AST/StmtVisitor.h"
17
#include "clang/Analysis/Analyses/PostOrderCFGView.h"
18
#include "clang/Analysis/AnalysisDeclContext.h"
19
#include "clang/Analysis/CFG.h"
20
#include "llvm/ADT/DenseMap.h"
21
#include "llvm/ADT/PostOrderIterator.h"
22
#include "llvm/ADT/PriorityQueue.h"
23
#include "llvm/Support/raw_ostream.h"
24
#include <algorithm>
25
#include <vector>
26
27
using namespace clang;
28
29
namespace {
30
31
class DataflowWorklist {
32
  llvm::BitVector enqueuedBlocks;
33
  PostOrderCFGView *POV;
34
  llvm::PriorityQueue<const CFGBlock *, SmallVector<const CFGBlock *, 20>,
35
                      PostOrderCFGView::BlockOrderCompare> worklist;
36
37
public:
38
  DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx)
39
    : enqueuedBlocks(cfg.getNumBlockIDs()),
40
      POV(Ctx.getAnalysis<PostOrderCFGView>()),
41
9.68k
      worklist(POV->getComparator()) {}
42
  
43
  void enqueueBlock(const CFGBlock *block);
44
  void enqueuePredecessors(const CFGBlock *block);
45
46
  const CFGBlock *dequeue();
47
};
48
49
}
50
51
70.7k
void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) {
52
70.7k
  if (
block && 70.7k
!enqueuedBlocks[block->getBlockID()]70.4k
) {
53
39.4k
    enqueuedBlocks[block->getBlockID()] = true;
54
39.4k
    worklist.push(block);
55
39.4k
  }
56
70.7k
}
57
58
38.7k
void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) {
59
38.7k
  for (CFGBlock::const_pred_iterator I = block->pred_begin(),
60
72.4k
       E = block->pred_end(); 
I != E72.4k
;
++I33.7k
) {
61
33.7k
    enqueueBlock(*I);
62
33.7k
  }
63
38.7k
}
64
65
49.1k
const CFGBlock *DataflowWorklist::dequeue() {
66
49.1k
  if (worklist.empty())
67
9.68k
    return nullptr;
68
39.4k
  const CFGBlock *b = worklist.top();
69
39.4k
  worklist.pop();
70
39.4k
  enqueuedBlocks[b->getBlockID()] = false;
71
39.4k
  return b;
72
39.4k
}
73
74
namespace {
75
class LiveVariablesImpl {
76
public:  
77
  AnalysisDeclContext &analysisContext;
78
  llvm::ImmutableSet<const Stmt *>::Factory SSetFact;
79
  llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;
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
96
  LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign)
97
    : analysisContext(ac),
98
      SSetFact(false), // Do not canonicalize ImmutableSets by default.
99
      DSetFact(false), // This is a *major* performance win.
100
9.68k
      killAtAssign(KillAtAssign) {}
101
};
102
}
103
104
1.12M
static LiveVariablesImpl &getImpl(void *x) {
105
1.12M
  return *((LiveVariablesImpl *) x);
106
1.12M
}
107
108
//===----------------------------------------------------------------------===//
109
// Operations and queries on LivenessValues.
110
//===----------------------------------------------------------------------===//
111
112
908k
bool LiveVariables::LivenessValues::isLive(const Stmt *S) const {
113
908k
  return liveStmts.contains(S);
114
908k
}
115
116
213k
bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const {
117
213k
  return liveDecls.contains(D);
118
213k
}
119
120
namespace {
121
  template <typename SET>
122
68.4k
  SET mergeSets(SET A, SET B) {
123
68.4k
    if (A.isEmpty())
124
63.7k
      return B;
125
4.64k
    
126
10.9k
    
for (typename SET::iterator it = B.begin(), ei = B.end(); 4.64k
it != ei10.9k
;
++it6.31k
) {
127
6.31k
      A = A.add(*it);
128
6.31k
    }
129
68.4k
    return A;
130
68.4k
  }
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
122
34.2k
  SET mergeSets(SET A, SET B) {
123
34.2k
    if (A.isEmpty())
124
32.4k
      return B;
125
1.70k
    
126
5.39k
    
for (typename SET::iterator it = B.begin(), ei = B.end(); 1.70k
it != ei5.39k
;
++it3.68k
) {
127
3.68k
      A = A.add(*it);
128
3.68k
    }
129
34.2k
    return A;
130
34.2k
  }
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
122
34.2k
  SET mergeSets(SET A, SET B) {
123
34.2k
    if (A.isEmpty())
124
31.2k
      return B;
125
2.93k
    
126
5.56k
    
for (typename SET::iterator it = B.begin(), ei = B.end(); 2.93k
it != ei5.56k
;
++it2.62k
) {
127
2.62k
      A = A.add(*it);
128
2.62k
    }
129
34.2k
    return A;
130
34.2k
  }
131
}
132
133
0
void LiveVariables::Observer::anchor() { }
134
135
LiveVariables::LivenessValues
136
LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,
137
34.2k
                         LiveVariables::LivenessValues valsB) {  
138
34.2k
  
139
34.2k
  llvm::ImmutableSetRef<const Stmt *>
140
34.2k
    SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()),
141
34.2k
    SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory());
142
34.2k
                                                
143
34.2k
  
144
34.2k
  llvm::ImmutableSetRef<const VarDecl *>
145
34.2k
    DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),
146
34.2k
    DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());
147
34.2k
  
148
34.2k
149
34.2k
  SSetRefA = mergeSets(SSetRefA, SSetRefB);
150
34.2k
  DSetRefA = mergeSets(DSetRefA, DSetRefB);
151
34.2k
  
152
34.2k
  // asImmutableSet() canonicalizes the tree, allowing us to do an easy
153
34.2k
  // comparison afterwards.
154
34.2k
  return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(),
155
34.2k
                                       DSetRefA.asImmutableSet());  
156
34.2k
}
157
158
2.41k
bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const {
159
703
  return liveStmts == V.liveStmts && liveDecls == V.liveDecls;
160
2.41k
}
161
162
//===----------------------------------------------------------------------===//
163
// Query methods.
164
//===----------------------------------------------------------------------===//
165
166
251k
static bool isAlwaysAlive(const VarDecl *D) {
167
251k
  return D->hasGlobalStorage();
168
251k
}
169
170
0
bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {
171
0
  return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);
172
0
}
173
174
213k
bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
175
213k
  return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);
176
213k
}
177
178
908k
bool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) {
179
908k
  return getImpl(impl).stmtsToLiveness[Loc].isLive(S);
180
908k
}
181
182
//===----------------------------------------------------------------------===//
183
// Dataflow computation.
184
//===----------------------------------------------------------------------===//
185
186
namespace {
187
class TransferFunctions : public StmtVisitor<TransferFunctions> {
188
  LiveVariablesImpl &LV;
189
  LiveVariables::LivenessValues &val;
190
  LiveVariables::Observer *observer;
191
  const CFGBlock *currentBlock;
192
public:
193
  TransferFunctions(LiveVariablesImpl &im,
194
                    LiveVariables::LivenessValues &Val,
195
                    LiveVariables::Observer *Observer,
196
                    const CFGBlock *CurrentBlock)
197
40.8k
  : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}
198
199
  void VisitBinaryOperator(BinaryOperator *BO);
200
  void VisitBlockExpr(BlockExpr *BE);
201
  void VisitDeclRefExpr(DeclRefExpr *DR);  
202
  void VisitDeclStmt(DeclStmt *DS);
203
  void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS);
204
  void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE);
205
  void VisitUnaryOperator(UnaryOperator *UO);
206
  void Visit(Stmt *S);
207
};
208
}
209
210
9.64k
static const VariableArrayType *FindVA(QualType Ty) {
211
9.64k
  const Type *ty = Ty.getTypePtr();
212
10.4k
  while (const ArrayType *
VT10.4k
= dyn_cast<ArrayType>(ty)) {
213
892
    if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT))
214
43
      
if (43
VAT->getSizeExpr()43
)
215
43
        return VAT;
216
849
    
217
849
    ty = VT->getElementType().getTypePtr();
218
849
  }
219
9.64k
220
9.60k
  return nullptr;
221
9.64k
}
222
223
155k
static const Stmt *LookThroughStmt(const Stmt *S) {
224
156k
  while (
S156k
) {
225
156k
    if (const Expr *Ex = dyn_cast<Expr>(S))
226
152k
      S = Ex->IgnoreParens();    
227
156k
    if (const ExprWithCleanups *
EWC156k
= dyn_cast<ExprWithCleanups>(S)) {
228
402
      S = EWC->getSubExpr();
229
402
      continue;
230
402
    }
231
156k
    
if (const OpaqueValueExpr *156k
OVE156k
= dyn_cast<OpaqueValueExpr>(S)) {
232
572
      S = OVE->getSourceExpr();
233
572
      continue;
234
572
    }
235
155k
    break;
236
155k
  }
237
155k
  return S;
238
155k
}
239
240
static void AddLiveStmt(llvm::ImmutableSet<const Stmt *> &Set,
241
                        llvm::ImmutableSet<const Stmt *>::Factory &F,
242
155k
                        const Stmt *S) {
243
155k
  Set = F.add(Set, LookThroughStmt(S));
244
155k
}
245
246
182k
void TransferFunctions::Visit(Stmt *S) {
247
182k
  if (observer)
248
8.00k
    observer->observeStmt(S, currentBlock, val);
249
182k
  
250
182k
  StmtVisitor<TransferFunctions>::Visit(S);
251
182k
  
252
182k
  if (
isa<Expr>(S)182k
) {
253
164k
    val.liveStmts = LV.SSetFact.remove(val.liveStmts, S);
254
164k
  }
255
182k
256
182k
  // Mark all children expressions live.
257
182k
  
258
182k
  switch (S->getStmtClass()) {
259
167k
    default:
260
167k
      break;
261
120
    case Stmt::StmtExprClass: {
262
120
      // For statement expressions, look through the compound statement.
263
120
      S = cast<StmtExpr>(S)->getSubStmt();
264
120
      break;
265
182k
    }
266
677
    case Stmt::CXXMemberCallExprClass: {
267
677
      // Include the implicit "this" pointer as being live.
268
677
      CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);
269
677
      if (Expr *
ImplicitObj677
= CE->getImplicitObjectArgument()) {
270
677
        AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj);
271
677
      }
272
677
      break;
273
182k
    }
274
3.48k
    case Stmt::ObjCMessageExprClass: {
275
3.48k
      // In calls to super, include the implicit "self" pointer as being live.
276
3.48k
      ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S);
277
3.48k
      if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance)
278
273
        val.liveDecls = LV.DSetFact.add(val.liveDecls,
279
273
                                        LV.analysisContext.getSelfDecl());
280
3.48k
      break;
281
182k
    }
282
9.60k
    case Stmt::DeclStmtClass: {
283
9.60k
      const DeclStmt *DS = cast<DeclStmt>(S);
284
9.60k
      if (const VarDecl *
VD9.60k
= dyn_cast<VarDecl>(DS->getSingleDecl())) {
285
9.60k
        for (const VariableArrayType* VA = FindVA(VD->getType());
286
9.64k
             
VA != nullptr9.64k
;
VA = FindVA(VA->getElementType())43
) {
287
43
          AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr());
288
43
        }
289
9.60k
      }
290
9.60k
      break;
291
182k
    }
292
342
    case Stmt::PseudoObjectExprClass: {
293
342
      // A pseudo-object operation only directly consumes its result
294
342
      // expression.
295
342
      Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();
296
342
      if (
!child342
)
return0
;
297
342
      
if (OpaqueValueExpr *342
OV342
= dyn_cast<OpaqueValueExpr>(child))
298
77
        child = OV->getSourceExpr();
299
342
      child = child->IgnoreParens();
300
342
      val.liveStmts = LV.SSetFact.add(val.liveStmts, child);
301
342
      return;
302
342
    }
303
342
304
342
    // FIXME: These cases eventually shouldn't be needed.
305
0
    case Stmt::ExprWithCleanupsClass: {
306
0
      S = cast<ExprWithCleanups>(S)->getSubExpr();
307
0
      break;
308
342
    }
309
213
    case Stmt::CXXBindTemporaryExprClass: {
310
213
      S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
311
213
      break;
312
342
    }
313
376
    case Stmt::UnaryExprOrTypeTraitExprClass: {
314
376
      // No need to unconditionally visit subexpressions.
315
376
      return;
316
181k
    }
317
181k
  }
318
181k
319
181k
  
for (Stmt *Child : S->children()) 181k
{
320
164k
    if (Child)
321
155k
      AddLiveStmt(val.liveStmts, LV.SSetFact, Child);
322
164k
  }
323
182k
}
324
325
12.9k
void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
326
12.9k
  if (
B->isAssignmentOp()12.9k
) {
327
4.75k
    if (!LV.killAtAssign)
328
3.97k
      return;
329
784
    
330
784
    // Assigning to a variable?
331
784
    Expr *LHS = B->getLHS()->IgnoreParens();
332
784
    
333
784
    if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS))
334
507
      
if (const VarDecl *507
VD507
= dyn_cast<VarDecl>(DR->getDecl())) {
335
507
        // Assignments to references don't kill the ref's address
336
507
        if (VD->getType()->isReferenceType())
337
10
          return;
338
497
339
497
        
if (497
!isAlwaysAlive(VD)497
) {
340
483
          // The variable is now dead.
341
483
          val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
342
483
        }
343
497
344
497
        if (observer)
345
228
          observer->observerKill(DR);
346
507
      }
347
4.75k
  }
348
12.9k
}
349
350
318
void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
351
318
  for (const VarDecl *VD :
352
264
       LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) {
353
264
    if (isAlwaysAlive(VD))
354
40
      continue;
355
224
    val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
356
224
  }
357
318
}
358
359
40.3k
void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
360
40.3k
  if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl()))
361
28.2k
    
if (28.2k
!isAlwaysAlive(D) && 28.2k
LV.inAssignment.find(DR) == LV.inAssignment.end()26.9k
)
362
26.4k
      val.liveDecls = LV.DSetFact.add(val.liveDecls, D);
363
40.3k
}
364
365
9.60k
void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
366
9.60k
  for (const auto *DI : DS->decls())
367
9.60k
    
if (const auto *9.60k
VD9.60k
= dyn_cast<VarDecl>(DI)) {
368
9.60k
      if (!isAlwaysAlive(VD))
369
9.24k
        val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
370
9.60k
    }
371
9.60k
}
372
373
228
void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
374
228
  // Kill the iteration variable.
375
228
  DeclRefExpr *DR = nullptr;
376
228
  const VarDecl *VD = nullptr;
377
228
378
228
  Stmt *element = OS->getElement();
379
228
  if (DeclStmt *
DS228
= dyn_cast<DeclStmt>(element)) {
380
190
    VD = cast<VarDecl>(DS->getSingleDecl());
381
190
  }
382
38
  else 
if (38
(DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))38
) {
383
38
    VD = cast<VarDecl>(DR->getDecl());
384
38
  }
385
228
  
386
228
  if (
VD228
) {
387
228
    val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
388
228
    if (
observer && 228
DR12
)
389
2
      observer->observerKill(DR);
390
228
  }
391
228
}
392
393
void TransferFunctions::
394
VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
395
376
{
396
376
  // While sizeof(var) doesn't technically extend the liveness of 'var', it
397
376
  // does extent the liveness of metadata if 'var' is a VariableArrayType.
398
376
  // We handle that special case here.
399
376
  if (
UE->getKind() != UETT_SizeOf || 376
UE->isArgumentType()373
)
400
292
    return;
401
84
402
84
  const Expr *subEx = UE->getArgumentExpr();
403
84
  if (
subEx->getType()->isVariableArrayType()84
) {
404
5
    assert(subEx->isLValue());
405
5
    val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens());
406
5
  }
407
376
}
408
409
6.01k
void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
410
6.01k
  // Treat ++/-- as a kill.
411
6.01k
  // Note we don't actually have to do anything if we don't have an observer,
412
6.01k
  // since a ++/-- acts as both a kill and a "use".
413
6.01k
  if (!observer)
414
5.68k
    return;
415
328
  
416
328
  switch (UO->getOpcode()) {
417
220
  default:
418
220
    return;
419
108
  case UO_PostInc:
420
108
  case UO_PostDec:    
421
108
  case UO_PreInc:
422
108
  case UO_PreDec:
423
108
    break;
424
108
  }
425
108
  
426
108
  
if (DeclRefExpr *108
DR108
= dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens()))
427
102
    
if (102
isa<VarDecl>(DR->getDecl())102
) {
428
102
      // Treat ++/-- as a kill.
429
102
      observer->observerKill(DR);
430
102
    }
431
6.01k
}
432
433
LiveVariables::LivenessValues
434
LiveVariablesImpl::runOnBlock(const CFGBlock *block,
435
                              LiveVariables::LivenessValues val,
436
40.8k
                              LiveVariables::Observer *obs) {
437
40.8k
438
40.8k
  TransferFunctions TF(*this, val, obs, block);
439
40.8k
  
440
40.8k
  // Visit the terminator (if any).
441
40.8k
  if (const Stmt *term = block->getTerminator())
442
5.39k
    TF.Visit(const_cast<Stmt*>(term));
443
40.8k
  
444
40.8k
  // Apply the transfer function for all Stmts in the block.
445
40.8k
  for (CFGBlock::const_reverse_iterator it = block->rbegin(),
446
219k
       ei = block->rend(); 
it != ei219k
;
++it178k
) {
447
178k
    const CFGElement &elem = *it;
448
178k
449
178k
    if (Optional<CFGAutomaticObjDtor> Dtor =
450
163
            elem.getAs<CFGAutomaticObjDtor>()) {
451
163
      val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl());
452
163
      continue;
453
163
    }
454
178k
455
178k
    
if (178k
!elem.getAs<CFGStmt>()178k
)
456
1.18k
      continue;
457
177k
    
458
177k
    const Stmt *S = elem.castAs<CFGStmt>().getStmt();
459
177k
    TF.Visit(const_cast<Stmt*>(S));
460
177k
    stmtsToLiveness[S] = val;
461
177k
  }
462
40.8k
  return val;
463
40.8k
}
464
465
416
void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {
466
416
  const CFG *cfg = getImpl(impl).analysisContext.getCFG();
467
2.52k
  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); 
it != ei2.52k
;
++it2.11k
)
468
2.11k
    getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);    
469
416
}
470
471
9.68k
LiveVariables::LiveVariables(void *im) : impl(im) {} 
472
473
9.68k
LiveVariables::~LiveVariables() {
474
9.68k
  delete (LiveVariablesImpl*) impl;
475
9.68k
}
476
477
LiveVariables *
478
LiveVariables::computeLiveness(AnalysisDeclContext &AC,
479
9.68k
                                 bool killAtAssign) {
480
9.68k
481
9.68k
  // No CFG?  Bail out.
482
9.68k
  CFG *cfg = AC.getCFG();
483
9.68k
  if (!cfg)
484
0
    return nullptr;
485
9.68k
486
9.68k
  // The analysis currently has scalability issues for very large CFGs.
487
9.68k
  // Bail out if it looks too large.
488
9.68k
  
if (9.68k
cfg->getNumBlockIDs() > 3000009.68k
)
489
0
    return nullptr;
490
9.68k
491
9.68k
  LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
492
9.68k
493
9.68k
  // Construct the dataflow worklist.  Enqueue the exit block as the
494
9.68k
  // start of the analysis.
495
9.68k
  DataflowWorklist worklist(*cfg, AC);
496
9.68k
  llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
497
9.68k
498
9.68k
  // FIXME: we should enqueue using post order.
499
46.7k
  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); 
it != ei46.7k
;
++it37.0k
) {
500
37.0k
    const CFGBlock *block = *it;
501
37.0k
    worklist.enqueueBlock(block);
502
37.0k
    
503
37.0k
    // FIXME: Scan for DeclRefExprs using in the LHS of an assignment.
504
37.0k
    // We need to do this because we lack context in the reverse analysis
505
37.0k
    // to determine if a DeclRefExpr appears in such a context, and thus
506
37.0k
    // doesn't constitute a "use".
507
37.0k
    if (killAtAssign)
508
2.11k
      for (CFGBlock::const_iterator bi = block->begin(), be = block->end();
509
9.71k
           
bi != be9.71k
;
++bi7.60k
) {
510
7.60k
        if (Optional<CFGStmt> 
cs7.60k
= bi->getAs<CFGStmt>()) {
511
7.59k
          if (const BinaryOperator *BO =
512
737
                  dyn_cast<BinaryOperator>(cs->getStmt())) {
513
737
            if (
BO->getOpcode() == BO_Assign737
) {
514
338
              if (const DeclRefExpr *DR =
515
215
                    dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
516
215
                LV->inAssignment[DR] = 1;
517
215
              }
518
338
            }
519
737
          }
520
7.59k
        }
521
2.11k
      }
522
37.0k
  }
523
9.68k
  
524
49.1k
  while (const CFGBlock *
block49.1k
= worklist.dequeue()) {
525
39.4k
    // Determine if the block's end value has changed.  If not, we
526
39.4k
    // have nothing left to do for this block.
527
39.4k
    LivenessValues &prevVal = LV->blocksEndToLiveness[block];
528
39.4k
    
529
39.4k
    // Merge the values of all successor blocks.
530
39.4k
    LivenessValues val;
531
39.4k
    for (CFGBlock::const_succ_iterator it = block->succ_begin(),
532
74.0k
                                       ei = block->succ_end(); 
it != ei74.0k
;
++it34.6k
) {
533
34.6k
      if (const CFGBlock *
succ34.6k
= *it) {
534
34.2k
        val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
535
34.2k
      }
536
34.6k
    }
537
39.4k
    
538
39.4k
    if (!everAnalyzedBlock[block->getBlockID()])
539
37.0k
      everAnalyzedBlock[block->getBlockID()] = true;
540
2.41k
    else 
if (2.41k
prevVal.equals(val)2.41k
)
541
665
      continue;
542
38.7k
543
38.7k
    prevVal = val;
544
38.7k
    
545
38.7k
    // Update the dataflow value for the start of this block.
546
38.7k
    LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
547
38.7k
    
548
38.7k
    // Enqueue the value to the predecessors.
549
38.7k
    worklist.enqueuePredecessors(block);
550
38.7k
  }
551
9.68k
  
552
9.68k
  return new LiveVariables(LV);
553
9.68k
}
554
555
0
void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
556
0
  getImpl(impl).dumpBlockLiveness(M);
557
0
}
558
559
0
void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
560
0
  std::vector<const CFGBlock *> vec;
561
0
  for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
562
0
       it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
563
0
       
it != ei0
;
++it0
) {
564
0
    vec.push_back(it->first);    
565
0
  }
566
0
  std::sort(vec.begin(), vec.end(), [](const CFGBlock *A, const CFGBlock *B) {
567
0
    return A->getBlockID() < B->getBlockID();
568
0
  });
569
0
570
0
  std::vector<const VarDecl*> declVec;
571
0
572
0
  for (std::vector<const CFGBlock *>::iterator
573
0
        it = vec.begin(), ei = vec.end(); 
it != ei0
;
++it0
) {
574
0
    llvm::errs() << "\n[ B" << (*it)->getBlockID()
575
0
                 << " (live variables at block exit) ]\n";
576
0
    
577
0
    LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
578
0
    declVec.clear();
579
0
    
580
0
    for (llvm::ImmutableSet<const VarDecl *>::iterator si =
581
0
          vals.liveDecls.begin(),
582
0
          se = vals.liveDecls.end(); 
si != se0
;
++si0
) {
583
0
      declVec.push_back(*si);      
584
0
    }
585
0
586
0
    std::sort(declVec.begin(), declVec.end(), [](const Decl *A, const Decl *B) {
587
0
      return A->getLocStart() < B->getLocStart();
588
0
    });
589
0
590
0
    for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
591
0
         de = declVec.end(); 
di != de0
;
++di0
) {
592
0
      llvm::errs() << " " << (*di)->getDeclName().getAsString()
593
0
                   << " <";
594
0
      (*di)->getLocation().dump(M);
595
0
      llvm::errs() << ">\n";
596
0
    }
597
0
  }
598
0
  llvm::errs() << "\n";  
599
0
}
600
601
416
const void *LiveVariables::getTag() { static int x; return &x; }
602
1.13M
const void *RelaxedLiveVariables::getTag() { static int x; return &x; }