clang  9.0.0svn
LiveVariables.cpp
Go to the documentation of this file.
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 
14 #include "clang/AST/Stmt.h"
15 #include "clang/AST/StmtVisitor.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>,
35 
36 public:
37  DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx)
38  : enqueuedBlocks(cfg.getNumBlockIDs()),
39  POV(Ctx.getAnalysis<PostOrderCFGView>()),
40  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 void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) {
51  if (block && !enqueuedBlocks[block->getBlockID()]) {
52  enqueuedBlocks[block->getBlockID()] = true;
53  worklist.push(block);
54  }
55 }
56 
57 void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) {
58  for (CFGBlock::const_pred_iterator I = block->pred_begin(),
59  E = block->pred_end(); I != E; ++I) {
60  enqueueBlock(*I);
61  }
62 }
63 
64 const CFGBlock *DataflowWorklist::dequeue() {
65  if (worklist.empty())
66  return nullptr;
67  const CFGBlock *b = worklist.top();
68  worklist.pop();
69  enqueuedBlocks[b->getBlockID()] = false;
70  return b;
71 }
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 
89 
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  killAtAssign(KillAtAssign) {}
103 };
104 }
105 
106 static LiveVariablesImpl &getImpl(void *x) {
107  return *((LiveVariablesImpl *) x);
108 }
109 
110 //===----------------------------------------------------------------------===//
111 // Operations and queries on LivenessValues.
112 //===----------------------------------------------------------------------===//
113 
115  return liveStmts.contains(S);
116 }
117 
119  if (const auto *DD = dyn_cast<DecompositionDecl>(D)) {
120  bool alive = false;
121  for (const BindingDecl *BD : DD->bindings())
122  alive |= liveBindings.contains(BD);
123  return alive;
124  }
125  return liveDecls.contains(D);
126 }
127 
128 namespace {
129  template <typename SET>
130  SET mergeSets(SET A, SET B) {
131  if (A.isEmpty())
132  return B;
133 
134  for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
135  A = A.add(*it);
136  }
137  return A;
138  }
139 }
140 
141 void LiveVariables::Observer::anchor() { }
142 
144 LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,
146 
147  llvm::ImmutableSetRef<const Stmt *>
148  SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()),
149  SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory());
150 
151 
152  llvm::ImmutableSetRef<const VarDecl *>
153  DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),
154  DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());
155 
156  llvm::ImmutableSetRef<const BindingDecl *>
157  BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()),
158  BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory());
159 
160  SSetRefA = mergeSets(SSetRefA, SSetRefB);
161  DSetRefA = mergeSets(DSetRefA, DSetRefB);
162  BSetRefA = mergeSets(BSetRefA, BSetRefB);
163 
164  // asImmutableSet() canonicalizes the tree, allowing us to do an easy
165  // comparison afterwards.
166  return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(),
167  DSetRefA.asImmutableSet(),
168  BSetRefA.asImmutableSet());
169 }
170 
172  return liveStmts == V.liveStmts && liveDecls == V.liveDecls;
173 }
174 
175 //===----------------------------------------------------------------------===//
176 // Query methods.
177 //===----------------------------------------------------------------------===//
178 
179 static bool isAlwaysAlive(const VarDecl *D) {
180  return D->hasGlobalStorage();
181 }
182 
183 bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {
184  return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);
185 }
186 
187 bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
188  return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);
189 }
190 
191 bool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) {
192  return getImpl(impl).stmtsToLiveness[Loc].isLive(S);
193 }
194 
195 //===----------------------------------------------------------------------===//
196 // Dataflow computation.
197 //===----------------------------------------------------------------------===//
198 
199 namespace {
200 class TransferFunctions : public StmtVisitor<TransferFunctions> {
201  LiveVariablesImpl &LV;
203  LiveVariables::Observer *observer;
204  const CFGBlock *currentBlock;
205 public:
206  TransferFunctions(LiveVariablesImpl &im,
209  const CFGBlock *CurrentBlock)
210  : 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 static const VariableArrayType *FindVA(QualType Ty) {
224  const Type *ty = Ty.getTypePtr();
225  while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) {
226  if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT))
227  if (VAT->getSizeExpr())
228  return VAT;
229 
230  ty = VT->getElementType().getTypePtr();
231  }
232 
233  return nullptr;
234 }
235 
236 static const Stmt *LookThroughStmt(const Stmt *S) {
237  while (S) {
238  if (const Expr *Ex = dyn_cast<Expr>(S))
239  S = Ex->IgnoreParens();
240  if (const FullExpr *FE = dyn_cast<FullExpr>(S)) {
241  S = FE->getSubExpr();
242  continue;
243  }
244  if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(S)) {
245  S = OVE->getSourceExpr();
246  continue;
247  }
248  break;
249  }
250  return S;
251 }
252 
253 static void AddLiveStmt(llvm::ImmutableSet<const Stmt *> &Set,
254  llvm::ImmutableSet<const Stmt *>::Factory &F,
255  const Stmt *S) {
256  Set = F.add(Set, LookThroughStmt(S));
257 }
258 
259 void TransferFunctions::Visit(Stmt *S) {
260  if (observer)
261  observer->observeStmt(S, currentBlock, val);
262 
264 
265  if (isa<Expr>(S)) {
266  val.liveStmts = LV.SSetFact.remove(val.liveStmts, S);
267  }
268 
269  // Mark all children expressions live.
270 
271  switch (S->getStmtClass()) {
272  default:
273  break;
274  case Stmt::StmtExprClass: {
275  // For statement expressions, look through the compound statement.
276  S = cast<StmtExpr>(S)->getSubStmt();
277  break;
278  }
279  case Stmt::CXXMemberCallExprClass: {
280  // Include the implicit "this" pointer as being live.
281  CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);
282  if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) {
283  AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj);
284  }
285  break;
286  }
287  case Stmt::ObjCMessageExprClass: {
288  // In calls to super, include the implicit "self" pointer as being live.
289  ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S);
291  val.liveDecls = LV.DSetFact.add(val.liveDecls,
292  LV.analysisContext.getSelfDecl());
293  break;
294  }
295  case Stmt::DeclStmtClass: {
296  const DeclStmt *DS = cast<DeclStmt>(S);
297  if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) {
298  for (const VariableArrayType* VA = FindVA(VD->getType());
299  VA != nullptr; VA = FindVA(VA->getElementType())) {
300  AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr());
301  }
302  }
303  break;
304  }
305  case Stmt::PseudoObjectExprClass: {
306  // A pseudo-object operation only directly consumes its result
307  // expression.
308  Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();
309  if (!child) return;
310  if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child))
311  child = OV->getSourceExpr();
312  child = child->IgnoreParens();
313  val.liveStmts = LV.SSetFact.add(val.liveStmts, child);
314  return;
315  }
316 
317  // FIXME: These cases eventually shouldn't be needed.
318  case Stmt::ExprWithCleanupsClass: {
319  S = cast<ExprWithCleanups>(S)->getSubExpr();
320  break;
321  }
322  case Stmt::CXXBindTemporaryExprClass: {
323  S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
324  break;
325  }
326  case Stmt::UnaryExprOrTypeTraitExprClass: {
327  // No need to unconditionally visit subexpressions.
328  return;
329  }
330  case Stmt::IfStmtClass: {
331  // If one of the branches is an expression rather than a compound
332  // statement, it will be bad if we mark it as live at the terminator
333  // of the if-statement (i.e., immediately after the condition expression).
334  AddLiveStmt(val.liveStmts, LV.SSetFact, cast<IfStmt>(S)->getCond());
335  return;
336  }
337  case Stmt::WhileStmtClass: {
338  // If the loop body is an expression rather than a compound statement,
339  // it will be bad if we mark it as live at the terminator of the loop
340  // (i.e., immediately after the condition expression).
341  AddLiveStmt(val.liveStmts, LV.SSetFact, cast<WhileStmt>(S)->getCond());
342  return;
343  }
344  case Stmt::DoStmtClass: {
345  // If the loop body is an expression rather than a compound statement,
346  // it will be bad if we mark it as live at the terminator of the loop
347  // (i.e., immediately after the condition expression).
348  AddLiveStmt(val.liveStmts, LV.SSetFact, cast<DoStmt>(S)->getCond());
349  return;
350  }
351  case Stmt::ForStmtClass: {
352  // If the loop body is an expression rather than a compound statement,
353  // it will be bad if we mark it as live at the terminator of the loop
354  // (i.e., immediately after the condition expression).
355  AddLiveStmt(val.liveStmts, LV.SSetFact, cast<ForStmt>(S)->getCond());
356  return;
357  }
358 
359  }
360 
361  for (Stmt *Child : S->children()) {
362  if (Child)
363  AddLiveStmt(val.liveStmts, LV.SSetFact, Child);
364  }
365 }
366 
367 static bool writeShouldKill(const VarDecl *VD) {
368  return VD && !VD->getType()->isReferenceType() &&
369  !isAlwaysAlive(VD);
370 }
371 
372 void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
373  if (B->isAssignmentOp()) {
374  if (!LV.killAtAssign)
375  return;
376 
377  // Assigning to a variable?
378  Expr *LHS = B->getLHS()->IgnoreParens();
379 
380  if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
381  const Decl* D = DR->getDecl();
382  bool Killed = false;
383 
384  if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) {
385  Killed = !BD->getType()->isReferenceType();
386  if (Killed)
387  val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
388  } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
389  Killed = writeShouldKill(VD);
390  if (Killed)
391  val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
392 
393  }
394 
395  if (Killed && observer)
396  observer->observerKill(DR);
397  }
398  }
399 }
400 
401 void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
402  for (const VarDecl *VD :
403  LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) {
404  if (isAlwaysAlive(VD))
405  continue;
406  val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
407  }
408 }
409 
410 void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
411  const Decl* D = DR->getDecl();
412  bool InAssignment = LV.inAssignment[DR];
413  if (const auto *BD = dyn_cast<BindingDecl>(D)) {
414  if (!InAssignment)
415  val.liveBindings = LV.BSetFact.add(val.liveBindings, BD);
416  } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
417  if (!InAssignment && !isAlwaysAlive(VD))
418  val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
419  }
420 }
421 
422 void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
423  for (const auto *DI : DS->decls()) {
424  if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) {
425  for (const auto *BD : DD->bindings())
426  val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
427  } else if (const auto *VD = dyn_cast<VarDecl>(DI)) {
428  if (!isAlwaysAlive(VD))
429  val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
430  }
431  }
432 }
433 
434 void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
435  // Kill the iteration variable.
436  DeclRefExpr *DR = nullptr;
437  const VarDecl *VD = nullptr;
438 
439  Stmt *element = OS->getElement();
440  if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
441  VD = cast<VarDecl>(DS->getSingleDecl());
442  }
443  else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
444  VD = cast<VarDecl>(DR->getDecl());
445  }
446 
447  if (VD) {
448  val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
449  if (observer && DR)
450  observer->observerKill(DR);
451  }
452 }
453 
454 void TransferFunctions::
455 VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
456 {
457  // While sizeof(var) doesn't technically extend the liveness of 'var', it
458  // does extent the liveness of metadata if 'var' is a VariableArrayType.
459  // We handle that special case here.
460  if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
461  return;
462 
463  const Expr *subEx = UE->getArgumentExpr();
464  if (subEx->getType()->isVariableArrayType()) {
465  assert(subEx->isLValue());
466  val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens());
467  }
468 }
469 
470 void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
471  // Treat ++/-- as a kill.
472  // Note we don't actually have to do anything if we don't have an observer,
473  // since a ++/-- acts as both a kill and a "use".
474  if (!observer)
475  return;
476 
477  switch (UO->getOpcode()) {
478  default:
479  return;
480  case UO_PostInc:
481  case UO_PostDec:
482  case UO_PreInc:
483  case UO_PreDec:
484  break;
485  }
486 
487  if (auto *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) {
488  const Decl *D = DR->getDecl();
489  if (isa<VarDecl>(D) || isa<BindingDecl>(D)) {
490  // Treat ++/-- as a kill.
491  observer->observerKill(DR);
492  }
493  }
494 }
495 
500 
501  TransferFunctions TF(*this, val, obs, block);
502 
503  // Visit the terminator (if any).
504  if (const Stmt *term = block->getTerminatorStmt())
505  TF.Visit(const_cast<Stmt*>(term));
506 
507  // Apply the transfer function for all Stmts in the block.
508  for (CFGBlock::const_reverse_iterator it = block->rbegin(),
509  ei = block->rend(); it != ei; ++it) {
510  const CFGElement &elem = *it;
511 
513  elem.getAs<CFGAutomaticObjDtor>()) {
514  val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl());
515  continue;
516  }
517 
518  if (!elem.getAs<CFGStmt>())
519  continue;
520 
521  const Stmt *S = elem.castAs<CFGStmt>().getStmt();
522  TF.Visit(const_cast<Stmt*>(S));
523  stmtsToLiveness[S] = val;
524  }
525  return val;
526 }
527 
529  const CFG *cfg = getImpl(impl).analysisContext.getCFG();
530  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
531  getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
532 }
533 
534 LiveVariables::LiveVariables(void *im) : impl(im) {}
535 
537  delete (LiveVariablesImpl*) impl;
538 }
539 
542  bool killAtAssign) {
543 
544  // No CFG? Bail out.
545  CFG *cfg = AC.getCFG();
546  if (!cfg)
547  return nullptr;
548 
549  // The analysis currently has scalability issues for very large CFGs.
550  // Bail out if it looks too large.
551  if (cfg->getNumBlockIDs() > 300000)
552  return nullptr;
553 
554  LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
555 
556  // Construct the dataflow worklist. Enqueue the exit block as the
557  // start of the analysis.
558  DataflowWorklist worklist(*cfg, AC);
559  llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
560 
561  // FIXME: we should enqueue using post order.
562  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
563  const CFGBlock *block = *it;
564  worklist.enqueueBlock(block);
565 
566  // FIXME: Scan for DeclRefExprs using in the LHS of an assignment.
567  // We need to do this because we lack context in the reverse analysis
568  // to determine if a DeclRefExpr appears in such a context, and thus
569  // doesn't constitute a "use".
570  if (killAtAssign)
571  for (CFGBlock::const_iterator bi = block->begin(), be = block->end();
572  bi != be; ++bi) {
573  if (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) {
574  const Stmt* stmt = cs->getStmt();
575  if (const auto *BO = dyn_cast<BinaryOperator>(stmt)) {
576  if (BO->getOpcode() == BO_Assign) {
577  if (const auto *DR =
578  dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
579  LV->inAssignment[DR] = 1;
580  }
581  }
582  }
583  }
584  }
585  }
586 
587  while (const CFGBlock *block = worklist.dequeue()) {
588  // Determine if the block's end value has changed. If not, we
589  // have nothing left to do for this block.
590  LivenessValues &prevVal = LV->blocksEndToLiveness[block];
591 
592  // Merge the values of all successor blocks.
593  LivenessValues val;
594  for (CFGBlock::const_succ_iterator it = block->succ_begin(),
595  ei = block->succ_end(); it != ei; ++it) {
596  if (const CFGBlock *succ = *it) {
597  val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
598  }
599  }
600 
601  if (!everAnalyzedBlock[block->getBlockID()])
602  everAnalyzedBlock[block->getBlockID()] = true;
603  else if (prevVal.equals(val))
604  continue;
605 
606  prevVal = val;
607 
608  // Update the dataflow value for the start of this block.
609  LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
610 
611  // Enqueue the value to the predecessors.
612  worklist.enqueuePredecessors(block);
613  }
614 
615  return new LiveVariables(LV);
616 }
617 
619  getImpl(impl).dumpBlockLiveness(M);
620 }
621 
622 void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
623  std::vector<const CFGBlock *> vec;
624  for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
625  it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
626  it != ei; ++it) {
627  vec.push_back(it->first);
628  }
629  llvm::sort(vec, [](const CFGBlock *A, const CFGBlock *B) {
630  return A->getBlockID() < B->getBlockID();
631  });
632 
633  std::vector<const VarDecl*> declVec;
634 
635  for (std::vector<const CFGBlock *>::iterator
636  it = vec.begin(), ei = vec.end(); it != ei; ++it) {
637  llvm::errs() << "\n[ B" << (*it)->getBlockID()
638  << " (live variables at block exit) ]\n";
639 
640  LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
641  declVec.clear();
642 
643  for (llvm::ImmutableSet<const VarDecl *>::iterator si =
644  vals.liveDecls.begin(),
645  se = vals.liveDecls.end(); si != se; ++si) {
646  declVec.push_back(*si);
647  }
648 
649  llvm::sort(declVec, [](const Decl *A, const Decl *B) {
650  return A->getBeginLoc() < B->getBeginLoc();
651  });
652 
653  for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
654  de = declVec.end(); di != de; ++di) {
655  llvm::errs() << " " << (*di)->getDeclName().getAsString()
656  << " <";
657  (*di)->getLocation().print(llvm::errs(), M);
658  llvm::errs() << ">\n";
659  }
660  }
661  llvm::errs() << "\n";
662 }
663 
665  getImpl(impl).dumpStmtLiveness(M);
666 }
667 
668 void LiveVariablesImpl::dumpStmtLiveness(const SourceManager &M) {
669  // Don't iterate over blockEndsToLiveness directly because it's not sorted.
670  for (auto I : *analysisContext.getCFG()) {
671 
672  llvm::errs() << "\n[ B" << I->getBlockID()
673  << " (live statements at block exit) ]\n";
674  for (auto S : blocksEndToLiveness[I].liveStmts) {
675  llvm::errs() << "\n";
676  S->dump();
677  }
678  llvm::errs() << "\n";
679  }
680 }
681 
682 const void *LiveVariables::getTag() { static int x; return &x; }
683 const void *RelaxedLiveVariables::getTag() { static int x; return &x; }
The receiver is the instance of the superclass object.
Definition: ExprObjC.h:1107
const BlockDecl * getBlockDecl() const
Definition: Expr.h:5555
static const VariableArrayType * FindVA(QualType Ty)
pred_iterator pred_end()
Definition: CFG.h:752
A (possibly-)qualified type.
Definition: Type.h:643
static bool isAlwaysAlive(const VarDecl *D)
static const Stmt * LookThroughStmt(const Stmt *S)
AdjacentBlocks::const_iterator const_pred_iterator
Definition: CFG.h:738
static LiveVariables * computeLiveness(AnalysisDeclContext &analysisContext, bool killAtAssign)
Compute the liveness information for a given CFG.
const internal::VariadicAllOfMatcher< Stmt > stmt
Matches statements.
succ_iterator succ_begin()
Definition: CFG.h:769
Stmt - This represents one statement.
Definition: Stmt.h:66
unsigned getBlockID() const
Definition: CFG.h:876
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:88
Expr * getImplicitObjectArgument() const
Retrieves the implicit object argument for the member call.
Definition: ExprCXX.cpp:642
SourceLocation getBeginLoc() const LLVM_READONLY
Definition: DeclBase.h:421
static void add(Kind k)
Definition: DeclBase.cpp:192
The base class of the type hierarchy.
Definition: Type.h:1418
Represents an array type, per C99 6.7.5.2 - Array Declarators.
Definition: Type.h:2829
iterator begin()
Definition: CFG.h:721
T castAs() const
Convert to the specified CFGElement type, asserting that this CFGElement is of the desired type...
Definition: CFG.h:98
static const void * getTag()
Represents a variable declaration or definition.
Definition: Decl.h:812
llvm::ImmutableSet< const BindingDecl * > liveBindings
Definition: LiveVariables.h:35
bool equals(const LivenessValues &V) const
static bool isAssignmentOp(Opcode Opc)
Definition: Expr.h:3531
bool isVariableArrayType() const
Definition: Type.h:6419
FullExpr - Represents a "full-expression" node.
Definition: Expr.h:920
AnalysisDeclContext contains the context data for the function or method under analysis.
Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...
Definition: CFG.h:383
bool isReferenceType() const
Definition: Type.h:6363
void runOnAllBlocks(Observer &obs)
iterator end()
Definition: CFG.h:1104
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:745
static bool runOnBlock(const CFGBlock *block, const CFG &cfg, AnalysisDeclContext &ac, CFGBlockValues &vals, const ClassifyRefs &classification, llvm::BitVector &wasAnalyzed, UninitVariablesHandler &handler)
child_range children()
Definition: Stmt.cpp:212
bool isLive(const CFGBlock *B, const VarDecl *D)
Return true if a variable is live at the end of a specified block.
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3405
const Type * getTypePtr() const
Retrieves a pointer to the underlying (unqualified) type.
Definition: Type.h:6127
b
Definition: emmintrin.h:321
A binding in a decomposition declaration.
Definition: DeclCXX.h:3923
reverse_iterator rend()
Definition: CFG.h:727
CFGBlockListTy::const_iterator const_iterator
Definition: CFG.h:1096
static const void * getTag()
UnaryExprOrTypeTraitExpr - expression with either a type or (unevaluated) expression operand...
Definition: Expr.h:2342
Represents a single basic block in a source-level CFG.
Definition: CFG.h:570
This represents one expression.
Definition: Expr.h:108
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1027
#define V(N, I)
Definition: ASTContext.h:2907
BlockExpr - Adaptor class for mixing a BlockDecl with expressions.
Definition: Expr.h:5541
ElementList::const_iterator const_iterator
Definition: CFG.h:714
QualType getType() const
Definition: Expr.h:137
An expression that sends a message to the given Objective-C object or class.
Definition: ExprObjC.h:950
UnaryOperator - This represents the unary-expression&#39;s (except sizeof and alignof), the postinc/postdec operators from postfix-expression, and various extensions.
Definition: Expr.h:2016
static LiveVariablesImpl & getImpl(void *x)
ReceiverKind getReceiverKind() const
Determine the kind of receiver that this message is being sent to.
Definition: ExprObjC.h:1234
ValueDecl * getDecl()
Definition: Expr.h:1217
reverse_iterator rbegin()
Definition: CFG.h:726
OpaqueValueExpr - An expression referring to an opaque object of a fixed type and value class...
Definition: Expr.h:1045
#define false
Definition: stdbool.h:17
void dumpBlockLiveness(const SourceManager &M)
Print to stderr the variable liveness information associated with each basic block.
Expr * getSubExpr() const
Definition: Expr.h:2046
static void AddLiveStmt(llvm::ImmutableSet< const Stmt *> &Set, llvm::ImmutableSet< const Stmt *>::Factory &F, const Stmt *S)
Represents a call to a member function that may be written either with member call syntax (e...
Definition: ExprCXX.h:170
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:1203
llvm::ImmutableSet< const VarDecl * > liveDecls
Definition: LiveVariables.h:34
StmtVisitor - This class implements a simple visitor for Stmt subclasses.
Definition: StmtVisitor.h:182
bool hasGlobalStorage() const
Returns true for all variables that do not have local storage.
Definition: Decl.h:1077
UnaryExprOrTypeTrait getKind() const
Definition: Expr.h:2373
bool isLValue() const
isLValue - True if this expression is an "l-value" according to the rules of the current language...
Definition: Expr.h:258
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
Definition: CFG.h:1194
iterator begin()
Definition: CFG.h:1103
succ_iterator succ_end()
Definition: CFG.h:770
bool isArgumentType() const
Definition: Expr.h:2378
Optional< T > getAs() const
Convert to the specified CFGElement type, returning None if this CFGElement is not of the desired typ...
Definition: CFG.h:109
Expr * getLHS() const
Definition: Expr.h:3445
pred_iterator pred_begin()
Definition: CFG.h:751
Dataflow Directional Tag Classes.
bool isLive(const Stmt *S) const
StmtClass getStmtClass() const
Definition: Stmt.h:1087
const Decl * getSingleDecl() const
Definition: Stmt.h:1218
Stmt * getTerminatorStmt()
Definition: CFG.h:860
llvm::ImmutableSet< const Stmt * > liveStmts
Definition: LiveVariables.h:33
void dump() const
Dumps the specified AST fragment and all subtrees to llvm::errs().
Definition: ASTDumper.cpp:243
Represents Objective-C&#39;s collection statement.
Definition: StmtObjC.h:23
Opcode getOpcode() const
Definition: Expr.h:2041
decl_range decls()
Definition: Stmt.h:1251
void dumpStmtLiveness(const SourceManager &M)
Print to stderr the statement liveness information associated with each basic block.
Represents a top-level expression in a basic block.
Definition: CFG.h:55
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:1141
QualType getType() const
Definition: Decl.h:647
Represents a C array with a specified size that is not an integer-constant-expression.
Definition: Type.h:2988
iterator end()
Definition: CFG.h:722
static bool writeShouldKill(const VarDecl *VD)
This class handles loading and caching of source files into memory.
Expr * IgnoreParens() LLVM_READONLY
Skip past any parentheses which might surround this expression until reaching a fixed point...
Definition: Expr.cpp:2937