clang  16.0.0git
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"
17 #include "clang/Analysis/CFG.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/Support/raw_ostream.h"
21 #include <algorithm>
22 #include <vector>
23 
24 using namespace clang;
25 
26 namespace {
27 class LiveVariablesImpl {
28 public:
29  AnalysisDeclContext &analysisContext;
30  llvm::ImmutableSet<const Expr *>::Factory ESetFact;
31  llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;
32  llvm::ImmutableSet<const BindingDecl *>::Factory BSetFact;
33  llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;
34  llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;
35  llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness;
36  llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment;
37  const bool killAtAssign;
38 
42 
45  LiveVariables::Observer *obs = nullptr);
46 
47  void dumpBlockLiveness(const SourceManager& M);
48  void dumpExprLiveness(const SourceManager& M);
49 
50  LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign)
51  : analysisContext(ac),
52  ESetFact(false), // Do not canonicalize ImmutableSets by default.
53  DSetFact(false), // This is a *major* performance win.
54  BSetFact(false), killAtAssign(KillAtAssign) {}
55 };
56 } // namespace
57 
58 static LiveVariablesImpl &getImpl(void *x) {
59  return *((LiveVariablesImpl *) x);
60 }
61 
62 //===----------------------------------------------------------------------===//
63 // Operations and queries on LivenessValues.
64 //===----------------------------------------------------------------------===//
65 
67  return liveExprs.contains(E);
68 }
69 
71  if (const auto *DD = dyn_cast<DecompositionDecl>(D)) {
72  bool alive = false;
73  for (const BindingDecl *BD : DD->bindings())
74  alive |= liveBindings.contains(BD);
75 
76  // Note: the only known case this condition is necessary, is when a bindig
77  // to a tuple-like structure is created. The HoldingVar initializers have a
78  // DeclRefExpr to the DecompositionDecl.
79  alive |= liveDecls.contains(DD);
80  return alive;
81  }
82  return liveDecls.contains(D);
83 }
84 
85 namespace {
86  template <typename SET>
87  SET mergeSets(SET A, SET B) {
88  if (A.isEmpty())
89  return B;
90 
91  for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
92  A = A.add(*it);
93  }
94  return A;
95  }
96 } // namespace
97 
98 void LiveVariables::Observer::anchor() { }
99 
101 LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,
103 
104  llvm::ImmutableSetRef<const Expr *> SSetRefA(
105  valsA.liveExprs.getRootWithoutRetain(), ESetFact.getTreeFactory()),
106  SSetRefB(valsB.liveExprs.getRootWithoutRetain(),
107  ESetFact.getTreeFactory());
108 
109  llvm::ImmutableSetRef<const VarDecl *>
110  DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),
111  DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());
112 
113  llvm::ImmutableSetRef<const BindingDecl *>
114  BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()),
115  BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory());
116 
117  SSetRefA = mergeSets(SSetRefA, SSetRefB);
118  DSetRefA = mergeSets(DSetRefA, DSetRefB);
119  BSetRefA = mergeSets(BSetRefA, BSetRefB);
120 
121  // asImmutableSet() canonicalizes the tree, allowing us to do an easy
122  // comparison afterwards.
123  return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(),
124  DSetRefA.asImmutableSet(),
125  BSetRefA.asImmutableSet());
126 }
127 
129  return liveExprs == V.liveExprs && liveDecls == V.liveDecls;
130 }
131 
132 //===----------------------------------------------------------------------===//
133 // Query methods.
134 //===----------------------------------------------------------------------===//
135 
136 static bool isAlwaysAlive(const VarDecl *D) {
137  return D->hasGlobalStorage();
138 }
139 
140 bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {
141  return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);
142 }
143 
144 bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
145  return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);
146 }
147 
148 bool LiveVariables::isLive(const Stmt *Loc, const Expr *Val) {
149  return getImpl(impl).stmtsToLiveness[Loc].isLive(Val);
150 }
151 
152 //===----------------------------------------------------------------------===//
153 // Dataflow computation.
154 //===----------------------------------------------------------------------===//
155 
156 namespace {
157 class TransferFunctions : public StmtVisitor<TransferFunctions> {
158  LiveVariablesImpl &LV;
160  LiveVariables::Observer *observer;
161  const CFGBlock *currentBlock;
162 public:
163  TransferFunctions(LiveVariablesImpl &im,
165  LiveVariables::Observer *Observer,
166  const CFGBlock *CurrentBlock)
167  : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}
168 
169  void VisitBinaryOperator(BinaryOperator *BO);
170  void VisitBlockExpr(BlockExpr *BE);
171  void VisitDeclRefExpr(DeclRefExpr *DR);
172  void VisitDeclStmt(DeclStmt *DS);
173  void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS);
174  void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE);
175  void VisitUnaryOperator(UnaryOperator *UO);
176  void Visit(Stmt *S);
177 };
178 } // namespace
179 
180 static const VariableArrayType *FindVA(QualType Ty) {
181  const Type *ty = Ty.getTypePtr();
182  while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) {
183  if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT))
184  if (VAT->getSizeExpr())
185  return VAT;
186 
187  ty = VT->getElementType().getTypePtr();
188  }
189 
190  return nullptr;
191 }
192 
193 static const Expr *LookThroughExpr(const Expr *E) {
194  while (E) {
195  if (const Expr *Ex = dyn_cast<Expr>(E))
196  E = Ex->IgnoreParens();
197  if (const FullExpr *FE = dyn_cast<FullExpr>(E)) {
198  E = FE->getSubExpr();
199  continue;
200  }
201  if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(E)) {
202  E = OVE->getSourceExpr();
203  continue;
204  }
205  break;
206  }
207  return E;
208 }
209 
210 static void AddLiveExpr(llvm::ImmutableSet<const Expr *> &Set,
211  llvm::ImmutableSet<const Expr *>::Factory &F,
212  const Expr *E) {
213  Set = F.add(Set, LookThroughExpr(E));
214 }
215 
216 void TransferFunctions::Visit(Stmt *S) {
217  if (observer)
218  observer->observeStmt(S, currentBlock, val);
219 
221 
222  if (const auto *E = dyn_cast<Expr>(S)) {
223  val.liveExprs = LV.ESetFact.remove(val.liveExprs, E);
224  }
225 
226  // Mark all children expressions live.
227 
228  switch (S->getStmtClass()) {
229  default:
230  break;
231  case Stmt::StmtExprClass: {
232  // For statement expressions, look through the compound statement.
233  S = cast<StmtExpr>(S)->getSubStmt();
234  break;
235  }
236  case Stmt::CXXMemberCallExprClass: {
237  // Include the implicit "this" pointer as being live.
238  CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);
239  if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) {
240  AddLiveExpr(val.liveExprs, LV.ESetFact, ImplicitObj);
241  }
242  break;
243  }
244  case Stmt::ObjCMessageExprClass: {
245  // In calls to super, include the implicit "self" pointer as being live.
246  ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S);
248  val.liveDecls = LV.DSetFact.add(val.liveDecls,
249  LV.analysisContext.getSelfDecl());
250  break;
251  }
252  case Stmt::DeclStmtClass: {
253  const DeclStmt *DS = cast<DeclStmt>(S);
254  if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) {
255  for (const VariableArrayType* VA = FindVA(VD->getType());
256  VA != nullptr; VA = FindVA(VA->getElementType())) {
257  AddLiveExpr(val.liveExprs, LV.ESetFact, VA->getSizeExpr());
258  }
259  }
260  break;
261  }
262  case Stmt::PseudoObjectExprClass: {
263  // A pseudo-object operation only directly consumes its result
264  // expression.
265  Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();
266  if (!child) return;
267  if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child))
268  child = OV->getSourceExpr();
269  child = child->IgnoreParens();
270  val.liveExprs = LV.ESetFact.add(val.liveExprs, child);
271  return;
272  }
273 
274  // FIXME: These cases eventually shouldn't be needed.
275  case Stmt::ExprWithCleanupsClass: {
276  S = cast<ExprWithCleanups>(S)->getSubExpr();
277  break;
278  }
279  case Stmt::CXXBindTemporaryExprClass: {
280  S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
281  break;
282  }
283  case Stmt::UnaryExprOrTypeTraitExprClass: {
284  // No need to unconditionally visit subexpressions.
285  return;
286  }
287  case Stmt::IfStmtClass: {
288  // If one of the branches is an expression rather than a compound
289  // statement, it will be bad if we mark it as live at the terminator
290  // of the if-statement (i.e., immediately after the condition expression).
291  AddLiveExpr(val.liveExprs, LV.ESetFact, cast<IfStmt>(S)->getCond());
292  return;
293  }
294  case Stmt::WhileStmtClass: {
295  // If the loop body is an expression rather than a compound statement,
296  // it will be bad if we mark it as live at the terminator of the loop
297  // (i.e., immediately after the condition expression).
298  AddLiveExpr(val.liveExprs, LV.ESetFact, cast<WhileStmt>(S)->getCond());
299  return;
300  }
301  case Stmt::DoStmtClass: {
302  // If the loop body is an expression rather than a compound statement,
303  // it will be bad if we mark it as live at the terminator of the loop
304  // (i.e., immediately after the condition expression).
305  AddLiveExpr(val.liveExprs, LV.ESetFact, cast<DoStmt>(S)->getCond());
306  return;
307  }
308  case Stmt::ForStmtClass: {
309  // If the loop body is an expression rather than a compound statement,
310  // it will be bad if we mark it as live at the terminator of the loop
311  // (i.e., immediately after the condition expression).
312  AddLiveExpr(val.liveExprs, LV.ESetFact, cast<ForStmt>(S)->getCond());
313  return;
314  }
315 
316  }
317 
318  // HACK + FIXME: What is this? One could only guess that this is an attempt to
319  // fish for live values, for example, arguments from a call expression.
320  // Maybe we could take inspiration from UninitializedVariable analysis?
321  for (Stmt *Child : S->children()) {
322  if (const auto *E = dyn_cast_or_null<Expr>(Child))
323  AddLiveExpr(val.liveExprs, LV.ESetFact, E);
324  }
325 }
326 
327 static bool writeShouldKill(const VarDecl *VD) {
328  return VD && !VD->getType()->isReferenceType() &&
329  !isAlwaysAlive(VD);
330 }
331 
332 void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
333  if (LV.killAtAssign && B->getOpcode() == BO_Assign) {
334  if (const auto *DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParens())) {
335  LV.inAssignment[DR] = 1;
336  }
337  }
338  if (B->isAssignmentOp()) {
339  if (!LV.killAtAssign)
340  return;
341 
342  // Assigning to a variable?
343  Expr *LHS = B->getLHS()->IgnoreParens();
344 
345  if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
346  const Decl* D = DR->getDecl();
347  bool Killed = false;
348 
349  if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) {
350  Killed = !BD->getType()->isReferenceType();
351  if (Killed) {
352  if (const auto *HV = BD->getHoldingVar())
353  val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV);
354 
355  val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
356  }
357  } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
358  Killed = writeShouldKill(VD);
359  if (Killed)
360  val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
361 
362  }
363 
364  if (Killed && observer)
365  observer->observerKill(DR);
366  }
367  }
368 }
369 
370 void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
371  for (const VarDecl *VD :
372  LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) {
373  if (isAlwaysAlive(VD))
374  continue;
375  val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
376  }
377 }
378 
379 void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
380  const Decl* D = DR->getDecl();
381  bool InAssignment = LV.inAssignment[DR];
382  if (const auto *BD = dyn_cast<BindingDecl>(D)) {
383  if (!InAssignment) {
384  if (const auto *HV = BD->getHoldingVar())
385  val.liveDecls = LV.DSetFact.add(val.liveDecls, HV);
386 
387  val.liveBindings = LV.BSetFact.add(val.liveBindings, BD);
388  }
389  } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
390  if (!InAssignment && !isAlwaysAlive(VD))
391  val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
392  }
393 }
394 
395 void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
396  for (const auto *DI : DS->decls()) {
397  if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) {
398  for (const auto *BD : DD->bindings()) {
399  if (const auto *HV = BD->getHoldingVar())
400  val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV);
401 
402  val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
403  }
404 
405  // When a bindig to a tuple-like structure is created, the HoldingVar
406  // initializers have a DeclRefExpr to the DecompositionDecl.
407  val.liveDecls = LV.DSetFact.remove(val.liveDecls, DD);
408  } else if (const auto *VD = dyn_cast<VarDecl>(DI)) {
409  if (!isAlwaysAlive(VD))
410  val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
411  }
412  }
413 }
414 
415 void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
416  // Kill the iteration variable.
417  DeclRefExpr *DR = nullptr;
418  const VarDecl *VD = nullptr;
419 
420  Stmt *element = OS->getElement();
421  if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
422  VD = cast<VarDecl>(DS->getSingleDecl());
423  }
424  else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
425  VD = cast<VarDecl>(DR->getDecl());
426  }
427 
428  if (VD) {
429  val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
430  if (observer && DR)
431  observer->observerKill(DR);
432  }
433 }
434 
435 void TransferFunctions::
436 VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
437 {
438  // While sizeof(var) doesn't technically extend the liveness of 'var', it
439  // does extent the liveness of metadata if 'var' is a VariableArrayType.
440  // We handle that special case here.
441  if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
442  return;
443 
444  const Expr *subEx = UE->getArgumentExpr();
445  if (subEx->getType()->isVariableArrayType()) {
446  assert(subEx->isLValue());
447  val.liveExprs = LV.ESetFact.add(val.liveExprs, subEx->IgnoreParens());
448  }
449 }
450 
451 void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
452  // Treat ++/-- as a kill.
453  // Note we don't actually have to do anything if we don't have an observer,
454  // since a ++/-- acts as both a kill and a "use".
455  if (!observer)
456  return;
457 
458  switch (UO->getOpcode()) {
459  default:
460  return;
461  case UO_PostInc:
462  case UO_PostDec:
463  case UO_PreInc:
464  case UO_PreDec:
465  break;
466  }
467 
468  if (auto *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) {
469  const Decl *D = DR->getDecl();
470  if (isa<VarDecl>(D) || isa<BindingDecl>(D)) {
471  // Treat ++/-- as a kill.
472  observer->observerKill(DR);
473  }
474  }
475 }
476 
481 
482  TransferFunctions TF(*this, val, obs, block);
483 
484  // Visit the terminator (if any).
485  if (const Stmt *term = block->getTerminatorStmt())
486  TF.Visit(const_cast<Stmt*>(term));
487 
488  // Apply the transfer function for all Stmts in the block.
489  for (CFGBlock::const_reverse_iterator it = block->rbegin(),
490  ei = block->rend(); it != ei; ++it) {
491  const CFGElement &elem = *it;
492 
494  elem.getAs<CFGAutomaticObjDtor>()) {
495  val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl());
496  continue;
497  }
498 
499  if (!elem.getAs<CFGStmt>())
500  continue;
501 
502  const Stmt *S = elem.castAs<CFGStmt>().getStmt();
503  TF.Visit(const_cast<Stmt*>(S));
504  stmtsToLiveness[S] = val;
505  }
506  return val;
507 }
508 
510  const CFG *cfg = getImpl(impl).analysisContext.getCFG();
511  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
512  getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
513 }
514 
515 LiveVariables::LiveVariables(void *im) : impl(im) {}
516 
518  delete (LiveVariablesImpl*) impl;
519 }
520 
521 std::unique_ptr<LiveVariables>
523 
524  // No CFG? Bail out.
525  CFG *cfg = AC.getCFG();
526  if (!cfg)
527  return nullptr;
528 
529  // The analysis currently has scalability issues for very large CFGs.
530  // Bail out if it looks too large.
531  if (cfg->getNumBlockIDs() > 300000)
532  return nullptr;
533 
534  LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
535 
536  // Construct the dataflow worklist. Enqueue the exit block as the
537  // start of the analysis.
538  BackwardDataflowWorklist worklist(*cfg, AC);
539  llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
540 
541  // FIXME: we should enqueue using post order.
542  for (const CFGBlock *B : cfg->nodes()) {
543  worklist.enqueueBlock(B);
544  }
545 
546  while (const CFGBlock *block = worklist.dequeue()) {
547  // Determine if the block's end value has changed. If not, we
548  // have nothing left to do for this block.
549  LivenessValues &prevVal = LV->blocksEndToLiveness[block];
550 
551  // Merge the values of all successor blocks.
552  LivenessValues val;
553  for (CFGBlock::const_succ_iterator it = block->succ_begin(),
554  ei = block->succ_end(); it != ei; ++it) {
555  if (const CFGBlock *succ = *it) {
556  val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
557  }
558  }
559 
560  if (!everAnalyzedBlock[block->getBlockID()])
561  everAnalyzedBlock[block->getBlockID()] = true;
562  else if (prevVal.equals(val))
563  continue;
564 
565  prevVal = val;
566 
567  // Update the dataflow value for the start of this block.
568  LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
569 
570  // Enqueue the value to the predecessors.
571  worklist.enqueuePredecessors(block);
572  }
573 
574  return std::unique_ptr<LiveVariables>(new LiveVariables(LV));
575 }
576 
578  getImpl(impl).dumpBlockLiveness(M);
579 }
580 
581 void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
582  std::vector<const CFGBlock *> vec;
583  for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
584  it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
585  it != ei; ++it) {
586  vec.push_back(it->first);
587  }
588  llvm::sort(vec, [](const CFGBlock *A, const CFGBlock *B) {
589  return A->getBlockID() < B->getBlockID();
590  });
591 
592  std::vector<const VarDecl*> declVec;
593 
594  for (std::vector<const CFGBlock *>::iterator
595  it = vec.begin(), ei = vec.end(); it != ei; ++it) {
596  llvm::errs() << "\n[ B" << (*it)->getBlockID()
597  << " (live variables at block exit) ]\n";
598 
599  LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
600  declVec.clear();
601 
602  for (llvm::ImmutableSet<const VarDecl *>::iterator si =
603  vals.liveDecls.begin(),
604  se = vals.liveDecls.end(); si != se; ++si) {
605  declVec.push_back(*si);
606  }
607 
608  llvm::sort(declVec, [](const Decl *A, const Decl *B) {
609  return A->getBeginLoc() < B->getBeginLoc();
610  });
611 
612  for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
613  de = declVec.end(); di != de; ++di) {
614  llvm::errs() << " " << (*di)->getDeclName().getAsString()
615  << " <";
616  (*di)->getLocation().print(llvm::errs(), M);
617  llvm::errs() << ">\n";
618  }
619  }
620  llvm::errs() << "\n";
621 }
622 
624  getImpl(impl).dumpExprLiveness(M);
625 }
626 
627 void LiveVariablesImpl::dumpExprLiveness(const SourceManager &M) {
628  // Don't iterate over blockEndsToLiveness directly because it's not sorted.
629  for (const CFGBlock *B : *analysisContext.getCFG()) {
630 
631  llvm::errs() << "\n[ B" << B->getBlockID()
632  << " (live expressions at block exit) ]\n";
633  for (const Expr *E : blocksEndToLiveness[B].liveExprs) {
634  llvm::errs() << "\n";
635  E->dump();
636  }
637  llvm::errs() << "\n";
638  }
639 }
640 
641 const void *LiveVariables::getTag() { static int x; return &x; }
642 const void *RelaxedLiveVariables::getTag() { static int x; return &x; }
clang::StmtVisitor
StmtVisitor - This class implements a simple visitor for Stmt subclasses.
Definition: StmtVisitor.h:183
clang::ObjCMessageExpr::SuperInstance
@ SuperInstance
The receiver is the instance of the superclass object.
Definition: ExprObjC.h:1097
clang::LiveVariables::LivenessValues::isLive
bool isLive(const Expr *E) const
Definition: LiveVariables.cpp:66
clang::BinaryOperator::isAssignmentOp
static bool isAssignmentOp(Opcode Opc)
Definition: Expr.h:3947
clang::Decl::getBeginLoc
SourceLocation getBeginLoc() const LLVM_READONLY
Definition: DeclBase.h:424
clang::LiveVariables::LivenessValues::equals
bool equals(const LivenessValues &V) const
Definition: LiveVariables.cpp:128
clang::Expr::isLValue
bool isLValue() const
isLValue - True if this expression is an "l-value" according to the rules of the current language.
Definition: Expr.h:270
FindVA
static const VariableArrayType * FindVA(QualType Ty)
Definition: LiveVariables.cpp:180
clang::VarDecl::hasGlobalStorage
bool hasGlobalStorage() const
Returns true for all variables that do not have local storage.
Definition: Decl.h:1173
clang::CFG::getNumBlockIDs
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
Definition: CFG.h:1413
clang::CFGBlock::succ_begin
succ_iterator succ_begin()
Definition: CFG.h:957
AnalysisDeclContext.h
clang::BindingDecl
A binding in a decomposition declaration.
Definition: DeclCXX.h:4008
clang::LiveVariables::LivenessValues
Definition: LiveVariables.h:30
clang::CFGBlock::getBlockID
unsigned getBlockID() const
Definition: CFG.h:1076
clang::QualType
A (possibly-)qualified type.
Definition: Type.h:737
clang::Decl::add
static void add(Kind k)
Definition: DeclBase.cpp:202
clang::AnalysisDeclContext
AnalysisDeclContext contains the context data for the function, method or block under analysis.
Definition: AnalysisDeclContext.h:72
clang::CFG::end
iterator end()
Definition: CFG.h:1306
llvm::Optional
Definition: LLVM.h:40
clang::Type::isVariableArrayType
bool isVariableArrayType() const
Definition: Type.h:6961
clang::UnaryOperator
UnaryOperator - This represents the unary-expression's (except sizeof and alignof),...
Definition: Expr.h:2172
clang::ObjCForCollectionStmt
Represents Objective-C's collection statement.
Definition: StmtObjC.h:23
clang::BinaryOperator::getOpcode
Opcode getOpcode() const
Definition: Expr.h:3856
clang::UnaryExprOrTypeTraitExpr::getArgumentExpr
Expr * getArgumentExpr()
Definition: Expr.h:2608
clang::RelaxedLiveVariables::getTag
static const void * getTag()
Definition: LiveVariables.cpp:642
clang::CFGBlock::const_succ_iterator
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:933
clang::CFG
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1227
AddLiveExpr
static void AddLiveExpr(llvm::ImmutableSet< const Expr * > &Set, llvm::ImmutableSet< const Expr * >::Factory &F, const Expr *E)
Definition: LiveVariables.cpp:210
clang::SourceManager
This class handles loading and caching of source files into memory.
Definition: SourceManager.h:636
clang::LiveVariables::isLive
bool isLive(const CFGBlock *B, const VarDecl *D)
Return true if a variable is live at the end of a specified block.
Definition: LiveVariables.cpp:140
clang::OpaqueValueExpr
OpaqueValueExpr - An expression referring to an opaque object of a fixed type and value class.
Definition: Expr.h:1144
clang::Type
The base class of the type hierarchy.
Definition: Type.h:1565
clang::FullExpr
FullExpr - Represents a "full-expression" node.
Definition: Expr.h:1013
clang::CFGBlock
Represents a single basic block in a source-level CFG.
Definition: CFG.h:578
clang::CXXMemberCallExpr::getImplicitObjectArgument
Expr * getImplicitObjectArgument() const
Retrieve the implicit object argument for the member call.
Definition: ExprCXX.cpp:650
clang::LiveVariables::LivenessValues::liveBindings
llvm::ImmutableSet< const BindingDecl * > liveBindings
Definition: LiveVariables.h:35
clang::Type::isReferenceType
bool isReferenceType() const
Definition: Type.h:6895
clang::LiveVariables::~LiveVariables
~LiveVariables() override
Definition: LiveVariables.cpp:517
V
#define V(N, I)
Definition: ASTContext.h:3237
clang::LiveVariables::runOnAllBlocks
void runOnAllBlocks(Observer &obs)
Definition: LiveVariables.cpp:509
clang::UnaryExprOrTypeTraitExpr
UnaryExprOrTypeTraitExpr - expression with either a type or (unevaluated) expression operand.
Definition: Expr.h:2558
clang::LiveVariables::computeLiveness
static std::unique_ptr< LiveVariables > computeLiveness(AnalysisDeclContext &analysisContext, bool killAtAssign)
Compute the liveness information for a given CFG.
Definition: LiveVariables.cpp:522
clang::CFG::nodes
llvm::iterator_range< iterator > nodes()
Definition: CFG.h:1313
clang::BinaryOperator
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3812
isAlwaysAlive
static bool isAlwaysAlive(const VarDecl *D)
Definition: LiveVariables.cpp:136
LiveVariables.h
clang::BlockExpr::getBlockDecl
const BlockDecl * getBlockDecl() const
Definition: Expr.h:5987
clang::ArrayType
Represents an array type, per C99 6.7.5.2 - Array Declarators.
Definition: Type.h:3012
clang::CFGAutomaticObjDtor
Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...
Definition: CFG.h:391
clang::StmtVisitorBase< std::add_pointer, ImplClass, void, ParamTys... >::Visit
void Visit(PTR(Stmt) S, ParamTys... P)
Definition: StmtVisitor.h:43
clang::LiveVariables::dumpBlockLiveness
void dumpBlockLiveness(const SourceManager &M)
Print to stderr the variable liveness information associated with each basic block.
Definition: LiveVariables.cpp:577
clang::ObjCMessageExpr::getReceiverKind
ReceiverKind getReceiverKind() const
Determine the kind of receiver that this message is being sent to.
Definition: ExprObjC.h:1224
clang::CFGBlock::rend
reverse_iterator rend()
Definition: CFG.h:883
clang::DeclRefExpr::getDecl
ValueDecl * getDecl()
Definition: Expr.h:1304
clang::VarDecl
Represents a variable declaration or definition.
Definition: Decl.h:906
getImpl
static LiveVariablesImpl & getImpl(void *x)
Definition: LiveVariables.cpp:58
clang::LiveVariables::dumpExprLiveness
void dumpExprLiveness(const SourceManager &M)
Print to stderr the expression liveness information associated with each basic block.
Definition: LiveVariables.cpp:623
clang::LiveVariables::getTag
static const void * getTag()
Definition: LiveVariables.cpp:641
clang::LiveVariables
Definition: LiveVariables.h:28
clang::BackwardDataflowWorklist::enqueuePredecessors
void enqueuePredecessors(const CFGBlock *Block)
Definition: DataflowWorklist.h:87
clang::Decl::dump
void dump() const
Definition: ASTDumper.cpp:206
clang::CFGBlock::rbegin
reverse_iterator rbegin()
Definition: CFG.h:882
clang::LiveVariables::Observer
Definition: LiveVariables.h:54
x
IRgen optimization opportunities The common pattern of short x
Definition: README.txt:7
DataflowWorklist.h
clang::ObjCMessageExpr
An expression that sends a message to the given Objective-C object or class.
Definition: ExprObjC.h:940
clang::DataflowWorklistBase::enqueueBlock
void enqueueBlock(const CFGBlock *Block)
Definition: DataflowWorklist.h:35
clang::UnaryExprOrTypeTraitExpr::isArgumentType
bool isArgumentType() const
Definition: Expr.h:2600
clang::DeclStmt::getSingleDecl
const Decl * getSingleDecl() const
Definition: Stmt.h:1318
clang::CFGStmt
Definition: CFG.h:132
clang::LiveVariables::LivenessValues::liveDecls
llvm::ImmutableSet< const VarDecl * > liveDecls
Definition: LiveVariables.h:34
clang::VariableArrayType
Represents a C array with a specified size that is not an integer-constant-expression.
Definition: Type.h:3162
clang::CFGElement::castAs
T castAs() const
Convert to the specified CFGElement type, asserting that this CFGElement is of the desired type.
Definition: CFG.h:98
false
#define false
Definition: stdbool.h:22
clang::CFGElement::getAs
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
clang::CFGBlock::succ_end
succ_iterator succ_end()
Definition: CFG.h:958
clang::BinaryOperator::getLHS
Expr * getLHS() const
Definition: Expr.h:3861
clang::BackwardDataflowWorklist
A worklist implementation for backward dataflow analysis.
Definition: DataflowWorklist.h:80
clang::BlockExpr
BlockExpr - Adaptor class for mixing a BlockDecl with expressions.
Definition: Expr.h:5975
clang::Decl
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:83
StmtVisitor.h
clang::DataflowWorklistBase::dequeue
const CFGBlock * dequeue()
Definition: DataflowWorklist.h:42
clang::CFGElement
Represents a top-level expression in a basic block.
Definition: CFG.h:55
clang::DeclStmt
DeclStmt - Adaptor class for mixing declarations with statements and expressions.
Definition: Stmt.h:1303
clang::UnaryExprOrTypeTraitExpr::getKind
UnaryExprOrTypeTrait getKind() const
Definition: Expr.h:2590
clang::UnaryOperator::getSubExpr
Expr * getSubExpr() const
Definition: Expr.h:2219
clang::Expr::IgnoreParens
Expr * IgnoreParens() LLVM_READONLY
Skip past any parentheses which might surround this expression until reaching a fixed point.
Definition: Expr.cpp:3031
clang
Definition: CalledOnceCheck.h:17
CFG.h
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:71
runOnBlock
static bool runOnBlock(const CFGBlock *block, const CFG &cfg, AnalysisDeclContext &ac, CFGBlockValues &vals, const ClassifyRefs &classification, llvm::BitVector &wasAnalyzed, UninitVariablesHandler &handler)
Definition: UninitializedValues.cpp:843
clang::UnaryOperator::getOpcode
Opcode getOpcode() const
Definition: Expr.h:2214
clang::LiveVariables::LivenessValues::liveExprs
llvm::ImmutableSet< const Expr * > liveExprs
Definition: LiveVariables.h:33
LookThroughExpr
static const Expr * LookThroughExpr(const Expr *E)
Definition: LiveVariables.cpp:193
clang::CFGBlock::getTerminatorStmt
Stmt * getTerminatorStmt()
Definition: CFG.h:1052
clang::Expr::getType
QualType getType() const
Definition: Expr.h:141
clang::DeclStmt::decls
decl_range decls()
Definition: Stmt.h:1351
clang::CFG::begin
iterator begin()
Definition: CFG.h:1305
clang::QualType::getTypePtr
const Type * getTypePtr() const
Retrieves a pointer to the underlying (unqualified) type.
Definition: Type.h:6622
Stmt.h
clang::AnalysisDeclContext::getCFG
CFG * getCFG()
Definition: AnalysisDeclContext.cpp:213
writeShouldKill
static bool writeShouldKill(const VarDecl *VD)
Definition: LiveVariables.cpp:327
clang::ValueDecl::getType
QualType getType() const
Definition: Decl.h:712
clang::Expr
This represents one expression.
Definition: Expr.h:109
clang::DeclRefExpr
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:1232
clang::CXXMemberCallExpr
Represents a call to a member function that may be written either with member call syntax (e....
Definition: ExprCXX.h:177
clang::ento::ObjKind::OS
@ OS
Indicates that the tracking object is a descendant of a referenced-counted OSObject,...