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 
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 ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(S)) {
241  S = EWC->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  }
331 
332  for (Stmt *Child : S->children()) {
333  if (Child)
334  AddLiveStmt(val.liveStmts, LV.SSetFact, Child);
335  }
336 }
337 
338 static bool writeShouldKill(const VarDecl *VD) {
339  return VD && !VD->getType()->isReferenceType() &&
340  !isAlwaysAlive(VD);
341 }
342 
343 void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
344  if (B->isAssignmentOp()) {
345  if (!LV.killAtAssign)
346  return;
347 
348  // Assigning to a variable?
349  Expr *LHS = B->getLHS()->IgnoreParens();
350 
351  if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
352  const Decl* D = DR->getDecl();
353  bool Killed = false;
354 
355  if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) {
356  Killed = !BD->getType()->isReferenceType();
357  if (Killed)
358  val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
359  } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
360  Killed = writeShouldKill(VD);
361  if (Killed)
362  val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
363 
364  }
365 
366  if (Killed && observer)
367  observer->observerKill(DR);
368  }
369  }
370 }
371 
372 void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
373  for (const VarDecl *VD :
374  LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) {
375  if (isAlwaysAlive(VD))
376  continue;
377  val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
378  }
379 }
380 
381 void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
382  const Decl* D = DR->getDecl();
383  bool InAssignment = LV.inAssignment[DR];
384  if (const auto *BD = dyn_cast<BindingDecl>(D)) {
385  if (!InAssignment)
386  val.liveBindings = LV.BSetFact.add(val.liveBindings, BD);
387  } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
388  if (!InAssignment && !isAlwaysAlive(VD))
389  val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
390  }
391 }
392 
393 void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
394  for (const auto *DI : DS->decls()) {
395  if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) {
396  for (const auto *BD : DD->bindings())
397  val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
398  } else if (const auto *VD = dyn_cast<VarDecl>(DI)) {
399  if (!isAlwaysAlive(VD))
400  val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
401  }
402  }
403 }
404 
405 void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
406  // Kill the iteration variable.
407  DeclRefExpr *DR = nullptr;
408  const VarDecl *VD = nullptr;
409 
410  Stmt *element = OS->getElement();
411  if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
412  VD = cast<VarDecl>(DS->getSingleDecl());
413  }
414  else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
415  VD = cast<VarDecl>(DR->getDecl());
416  }
417 
418  if (VD) {
419  val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
420  if (observer && DR)
421  observer->observerKill(DR);
422  }
423 }
424 
425 void TransferFunctions::
426 VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
427 {
428  // While sizeof(var) doesn't technically extend the liveness of 'var', it
429  // does extent the liveness of metadata if 'var' is a VariableArrayType.
430  // We handle that special case here.
431  if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
432  return;
433 
434  const Expr *subEx = UE->getArgumentExpr();
435  if (subEx->getType()->isVariableArrayType()) {
436  assert(subEx->isLValue());
437  val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens());
438  }
439 }
440 
441 void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
442  // Treat ++/-- as a kill.
443  // Note we don't actually have to do anything if we don't have an observer,
444  // since a ++/-- acts as both a kill and a "use".
445  if (!observer)
446  return;
447 
448  switch (UO->getOpcode()) {
449  default:
450  return;
451  case UO_PostInc:
452  case UO_PostDec:
453  case UO_PreInc:
454  case UO_PreDec:
455  break;
456  }
457 
458  if (auto *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) {
459  const Decl *D = DR->getDecl();
460  if (isa<VarDecl>(D) || isa<BindingDecl>(D)) {
461  // Treat ++/-- as a kill.
462  observer->observerKill(DR);
463  }
464  }
465 }
466 
471 
472  TransferFunctions TF(*this, val, obs, block);
473 
474  // Visit the terminator (if any).
475  if (const Stmt *term = block->getTerminator())
476  TF.Visit(const_cast<Stmt*>(term));
477 
478  // Apply the transfer function for all Stmts in the block.
479  for (CFGBlock::const_reverse_iterator it = block->rbegin(),
480  ei = block->rend(); it != ei; ++it) {
481  const CFGElement &elem = *it;
482 
484  elem.getAs<CFGAutomaticObjDtor>()) {
485  val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl());
486  continue;
487  }
488 
489  if (!elem.getAs<CFGStmt>())
490  continue;
491 
492  const Stmt *S = elem.castAs<CFGStmt>().getStmt();
493  TF.Visit(const_cast<Stmt*>(S));
494  stmtsToLiveness[S] = val;
495  }
496  return val;
497 }
498 
500  const CFG *cfg = getImpl(impl).analysisContext.getCFG();
501  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
502  getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
503 }
504 
505 LiveVariables::LiveVariables(void *im) : impl(im) {}
506 
508  delete (LiveVariablesImpl*) impl;
509 }
510 
513  bool killAtAssign) {
514 
515  // No CFG? Bail out.
516  CFG *cfg = AC.getCFG();
517  if (!cfg)
518  return nullptr;
519 
520  // The analysis currently has scalability issues for very large CFGs.
521  // Bail out if it looks too large.
522  if (cfg->getNumBlockIDs() > 300000)
523  return nullptr;
524 
525  LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
526 
527  // Construct the dataflow worklist. Enqueue the exit block as the
528  // start of the analysis.
529  DataflowWorklist worklist(*cfg, AC);
530  llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
531 
532  // FIXME: we should enqueue using post order.
533  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
534  const CFGBlock *block = *it;
535  worklist.enqueueBlock(block);
536 
537  // FIXME: Scan for DeclRefExprs using in the LHS of an assignment.
538  // We need to do this because we lack context in the reverse analysis
539  // to determine if a DeclRefExpr appears in such a context, and thus
540  // doesn't constitute a "use".
541  if (killAtAssign)
542  for (CFGBlock::const_iterator bi = block->begin(), be = block->end();
543  bi != be; ++bi) {
544  if (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) {
545  const Stmt* stmt = cs->getStmt();
546  if (const auto *BO = dyn_cast<BinaryOperator>(stmt)) {
547  if (BO->getOpcode() == BO_Assign) {
548  if (const auto *DR =
549  dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
550  LV->inAssignment[DR] = 1;
551  }
552  }
553  }
554  }
555  }
556  }
557 
558  while (const CFGBlock *block = worklist.dequeue()) {
559  // Determine if the block's end value has changed. If not, we
560  // have nothing left to do for this block.
561  LivenessValues &prevVal = LV->blocksEndToLiveness[block];
562 
563  // Merge the values of all successor blocks.
564  LivenessValues val;
565  for (CFGBlock::const_succ_iterator it = block->succ_begin(),
566  ei = block->succ_end(); it != ei; ++it) {
567  if (const CFGBlock *succ = *it) {
568  val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
569  }
570  }
571 
572  if (!everAnalyzedBlock[block->getBlockID()])
573  everAnalyzedBlock[block->getBlockID()] = true;
574  else if (prevVal.equals(val))
575  continue;
576 
577  prevVal = val;
578 
579  // Update the dataflow value for the start of this block.
580  LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
581 
582  // Enqueue the value to the predecessors.
583  worklist.enqueuePredecessors(block);
584  }
585 
586  return new LiveVariables(LV);
587 }
588 
590  getImpl(impl).dumpBlockLiveness(M);
591 }
592 
593 void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
594  std::vector<const CFGBlock *> vec;
595  for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
596  it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
597  it != ei; ++it) {
598  vec.push_back(it->first);
599  }
600  llvm::sort(vec.begin(), vec.end(), [](const CFGBlock *A, const CFGBlock *B) {
601  return A->getBlockID() < B->getBlockID();
602  });
603 
604  std::vector<const VarDecl*> declVec;
605 
606  for (std::vector<const CFGBlock *>::iterator
607  it = vec.begin(), ei = vec.end(); it != ei; ++it) {
608  llvm::errs() << "\n[ B" << (*it)->getBlockID()
609  << " (live variables at block exit) ]\n";
610 
611  LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
612  declVec.clear();
613 
614  for (llvm::ImmutableSet<const VarDecl *>::iterator si =
615  vals.liveDecls.begin(),
616  se = vals.liveDecls.end(); si != se; ++si) {
617  declVec.push_back(*si);
618  }
619 
620  llvm::sort(declVec.begin(), declVec.end(),
621  [](const Decl *A, const Decl *B) {
622  return A->getBeginLoc() < B->getBeginLoc();
623  });
624 
625  for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
626  de = declVec.end(); di != de; ++di) {
627  llvm::errs() << " " << (*di)->getDeclName().getAsString()
628  << " <";
629  (*di)->getLocation().print(llvm::errs(), M);
630  llvm::errs() << ">\n";
631  }
632  }
633  llvm::errs() << "\n";
634 }
635 
636 const void *LiveVariables::getTag() { static int x; return &x; }
637 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:4988
static const VariableArrayType * FindVA(QualType Ty)
pred_iterator pred_end()
Definition: CFG.h:734
A (possibly-)qualified type.
Definition: Type.h:642
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:86
Expr * getImplicitObjectArgument() const
Retrieves the implicit object argument for the member call.
Definition: ExprCXX.cpp:505
SourceLocation getBeginLoc() const LLVM_READONLY
Definition: DeclBase.h:409
static void add(Kind k)
Definition: DeclBase.cpp:193
The base class of the type hierarchy.
Definition: Type.h:1415
Represents an array type, per C99 6.7.5.2 - Array Declarators.
Definition: Type.h:2786
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:812
llvm::ImmutableSet< const BindingDecl * > liveBindings
Definition: LiveVariables.h:36
bool equals(const LivenessValues &V) const
Represents an expression – generally a full-expression – that introduces cleanups to be run at the ...
Definition: ExprCXX.h:3033
static bool isAssignmentOp(Opcode Opc)
Definition: Expr.h:3225
bool isVariableArrayType() const
Definition: Type.h:6238
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:6189
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:229
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:3102
const Type * getTypePtr() const
Retrieves a pointer to the underlying (unqualified) type.
Definition: Type.h:5953
A binding in a decomposition declaration.
Definition: DeclCXX.h:3786
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:2107
Represents a single basic block in a source-level CFG.
Definition: CFG.h:552
This represents one expression.
Definition: Expr.h:105
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:4974
ElementList::const_iterator const_iterator
Definition: CFG.h:696
QualType getType() const
Definition: Expr.h:127
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:1784
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:1056
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:874
#define false
Definition: stdbool.h:33
void dumpBlockLiveness(const SourceManager &M)
Print to stderr the liveness information associated with each basic block.
Expr * getSubExpr() const
Definition: Expr.h:1811
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:164
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:505
llvm::ImmutableSet< const VarDecl * > liveDecls
Definition: LiveVariables.h:35
StmtVisitor - This class implements a simple visitor for Stmt subclasses.
Definition: StmtVisitor.h:186
bool hasGlobalStorage() const
Returns true for all variables that do not have local storage.
Definition: Decl.h:1075
UnaryExprOrTypeTrait getKind() const
Definition: Expr.h:2138
bool isLValue() const
isLValue - True if this expression is an "l-value" according to the rules of the current language...
Definition: Expr.h:248
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:2143
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:3146
pred_iterator pred_begin()
Definition: CFG.h:733
Dataflow Directional Tag Classes.
bool isLive(const Stmt *S) const
StmtClass getStmtClass() const
Definition: Stmt.h:391
const Decl * getSingleDecl() const
Definition: Stmt.h:522
llvm::ImmutableSet< const Stmt * > liveStmts
Definition: LiveVariables.h:34
Represents Objective-C&#39;s collection statement.
Definition: StmtObjC.h:24
Opcode getOpcode() const
Definition: Expr.h:1808
decl_range decls()
Definition: Stmt.h:550
Represents a top-level expression in a basic block.
Definition: CFG.h:56
SourceLocation getBeginLoc() const LLVM_READONLY
Definition: Expr.h:3151
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:971
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:2945
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:2513