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