clang  14.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  return alive;
76  }
77  return liveDecls.contains(D);
78 }
79 
80 namespace {
81  template <typename SET>
82  SET mergeSets(SET A, SET B) {
83  if (A.isEmpty())
84  return B;
85 
86  for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
87  A = A.add(*it);
88  }
89  return A;
90  }
91 } // namespace
92 
93 void LiveVariables::Observer::anchor() { }
94 
96 LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,
98 
99  llvm::ImmutableSetRef<const Expr *> SSetRefA(
100  valsA.liveExprs.getRootWithoutRetain(), ESetFact.getTreeFactory()),
101  SSetRefB(valsB.liveExprs.getRootWithoutRetain(),
102  ESetFact.getTreeFactory());
103 
104  llvm::ImmutableSetRef<const VarDecl *>
105  DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),
106  DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());
107 
108  llvm::ImmutableSetRef<const BindingDecl *>
109  BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()),
110  BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory());
111 
112  SSetRefA = mergeSets(SSetRefA, SSetRefB);
113  DSetRefA = mergeSets(DSetRefA, DSetRefB);
114  BSetRefA = mergeSets(BSetRefA, BSetRefB);
115 
116  // asImmutableSet() canonicalizes the tree, allowing us to do an easy
117  // comparison afterwards.
118  return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(),
119  DSetRefA.asImmutableSet(),
120  BSetRefA.asImmutableSet());
121 }
122 
124  return liveExprs == V.liveExprs && liveDecls == V.liveDecls;
125 }
126 
127 //===----------------------------------------------------------------------===//
128 // Query methods.
129 //===----------------------------------------------------------------------===//
130 
131 static bool isAlwaysAlive(const VarDecl *D) {
132  return D->hasGlobalStorage();
133 }
134 
135 bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {
136  return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);
137 }
138 
139 bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
140  return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);
141 }
142 
143 bool LiveVariables::isLive(const Stmt *Loc, const Expr *Val) {
144  return getImpl(impl).stmtsToLiveness[Loc].isLive(Val);
145 }
146 
147 //===----------------------------------------------------------------------===//
148 // Dataflow computation.
149 //===----------------------------------------------------------------------===//
150 
151 namespace {
152 class TransferFunctions : public StmtVisitor<TransferFunctions> {
153  LiveVariablesImpl &LV;
155  LiveVariables::Observer *observer;
156  const CFGBlock *currentBlock;
157 public:
158  TransferFunctions(LiveVariablesImpl &im,
160  LiveVariables::Observer *Observer,
161  const CFGBlock *CurrentBlock)
162  : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}
163 
164  void VisitBinaryOperator(BinaryOperator *BO);
165  void VisitBlockExpr(BlockExpr *BE);
166  void VisitDeclRefExpr(DeclRefExpr *DR);
167  void VisitDeclStmt(DeclStmt *DS);
168  void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS);
169  void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE);
170  void VisitUnaryOperator(UnaryOperator *UO);
171  void Visit(Stmt *S);
172 };
173 } // namespace
174 
175 static const VariableArrayType *FindVA(QualType Ty) {
176  const Type *ty = Ty.getTypePtr();
177  while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) {
178  if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT))
179  if (VAT->getSizeExpr())
180  return VAT;
181 
182  ty = VT->getElementType().getTypePtr();
183  }
184 
185  return nullptr;
186 }
187 
188 static const Expr *LookThroughExpr(const Expr *E) {
189  while (E) {
190  if (const Expr *Ex = dyn_cast<Expr>(E))
191  E = Ex->IgnoreParens();
192  if (const FullExpr *FE = dyn_cast<FullExpr>(E)) {
193  E = FE->getSubExpr();
194  continue;
195  }
196  if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(E)) {
197  E = OVE->getSourceExpr();
198  continue;
199  }
200  break;
201  }
202  return E;
203 }
204 
205 static void AddLiveExpr(llvm::ImmutableSet<const Expr *> &Set,
206  llvm::ImmutableSet<const Expr *>::Factory &F,
207  const Expr *E) {
208  Set = F.add(Set, LookThroughExpr(E));
209 }
210 
211 void TransferFunctions::Visit(Stmt *S) {
212  if (observer)
213  observer->observeStmt(S, currentBlock, val);
214 
216 
217  if (const auto *E = dyn_cast<Expr>(S)) {
218  val.liveExprs = LV.ESetFact.remove(val.liveExprs, E);
219  }
220 
221  // Mark all children expressions live.
222 
223  switch (S->getStmtClass()) {
224  default:
225  break;
226  case Stmt::StmtExprClass: {
227  // For statement expressions, look through the compound statement.
228  S = cast<StmtExpr>(S)->getSubStmt();
229  break;
230  }
231  case Stmt::CXXMemberCallExprClass: {
232  // Include the implicit "this" pointer as being live.
233  CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);
234  if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) {
235  AddLiveExpr(val.liveExprs, LV.ESetFact, ImplicitObj);
236  }
237  break;
238  }
239  case Stmt::ObjCMessageExprClass: {
240  // In calls to super, include the implicit "self" pointer as being live.
241  ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S);
243  val.liveDecls = LV.DSetFact.add(val.liveDecls,
244  LV.analysisContext.getSelfDecl());
245  break;
246  }
247  case Stmt::DeclStmtClass: {
248  const DeclStmt *DS = cast<DeclStmt>(S);
249  if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) {
250  for (const VariableArrayType* VA = FindVA(VD->getType());
251  VA != nullptr; VA = FindVA(VA->getElementType())) {
252  AddLiveExpr(val.liveExprs, LV.ESetFact, VA->getSizeExpr());
253  }
254  }
255  break;
256  }
257  case Stmt::PseudoObjectExprClass: {
258  // A pseudo-object operation only directly consumes its result
259  // expression.
260  Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();
261  if (!child) return;
262  if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child))
263  child = OV->getSourceExpr();
264  child = child->IgnoreParens();
265  val.liveExprs = LV.ESetFact.add(val.liveExprs, child);
266  return;
267  }
268 
269  // FIXME: These cases eventually shouldn't be needed.
270  case Stmt::ExprWithCleanupsClass: {
271  S = cast<ExprWithCleanups>(S)->getSubExpr();
272  break;
273  }
274  case Stmt::CXXBindTemporaryExprClass: {
275  S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
276  break;
277  }
278  case Stmt::UnaryExprOrTypeTraitExprClass: {
279  // No need to unconditionally visit subexpressions.
280  return;
281  }
282  case Stmt::IfStmtClass: {
283  // If one of the branches is an expression rather than a compound
284  // statement, it will be bad if we mark it as live at the terminator
285  // of the if-statement (i.e., immediately after the condition expression).
286  AddLiveExpr(val.liveExprs, LV.ESetFact, cast<IfStmt>(S)->getCond());
287  return;
288  }
289  case Stmt::WhileStmtClass: {
290  // If the loop body is an expression rather than a compound statement,
291  // it will be bad if we mark it as live at the terminator of the loop
292  // (i.e., immediately after the condition expression).
293  AddLiveExpr(val.liveExprs, LV.ESetFact, cast<WhileStmt>(S)->getCond());
294  return;
295  }
296  case Stmt::DoStmtClass: {
297  // If the loop body is an expression rather than a compound statement,
298  // it will be bad if we mark it as live at the terminator of the loop
299  // (i.e., immediately after the condition expression).
300  AddLiveExpr(val.liveExprs, LV.ESetFact, cast<DoStmt>(S)->getCond());
301  return;
302  }
303  case Stmt::ForStmtClass: {
304  // If the loop body is an expression rather than a compound statement,
305  // it will be bad if we mark it as live at the terminator of the loop
306  // (i.e., immediately after the condition expression).
307  AddLiveExpr(val.liveExprs, LV.ESetFact, cast<ForStmt>(S)->getCond());
308  return;
309  }
310 
311  }
312 
313  // HACK + FIXME: What is this? One could only guess that this is an attempt to
314  // fish for live values, for example, arguments from a call expression.
315  // Maybe we could take inspiration from UninitializedVariable analysis?
316  for (Stmt *Child : S->children()) {
317  if (const auto *E = dyn_cast_or_null<Expr>(Child))
318  AddLiveExpr(val.liveExprs, LV.ESetFact, E);
319  }
320 }
321 
322 static bool writeShouldKill(const VarDecl *VD) {
323  return VD && !VD->getType()->isReferenceType() &&
324  !isAlwaysAlive(VD);
325 }
326 
327 void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
328  if (LV.killAtAssign && B->getOpcode() == BO_Assign) {
329  if (const auto *DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParens())) {
330  LV.inAssignment[DR] = 1;
331  }
332  }
333  if (B->isAssignmentOp()) {
334  if (!LV.killAtAssign)
335  return;
336 
337  // Assigning to a variable?
338  Expr *LHS = B->getLHS()->IgnoreParens();
339 
340  if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
341  const Decl* D = DR->getDecl();
342  bool Killed = false;
343 
344  if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) {
345  Killed = !BD->getType()->isReferenceType();
346  if (Killed)
347  val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
348  } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
349  Killed = writeShouldKill(VD);
350  if (Killed)
351  val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
352 
353  }
354 
355  if (Killed && observer)
356  observer->observerKill(DR);
357  }
358  }
359 }
360 
361 void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
362  for (const VarDecl *VD :
363  LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) {
364  if (isAlwaysAlive(VD))
365  continue;
366  val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
367  }
368 }
369 
370 void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
371  const Decl* D = DR->getDecl();
372  bool InAssignment = LV.inAssignment[DR];
373  if (const auto *BD = dyn_cast<BindingDecl>(D)) {
374  if (!InAssignment)
375  val.liveBindings = LV.BSetFact.add(val.liveBindings, BD);
376  } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
377  if (!InAssignment && !isAlwaysAlive(VD))
378  val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
379  }
380 }
381 
382 void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
383  for (const auto *DI : DS->decls()) {
384  if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) {
385  for (const auto *BD : DD->bindings())
386  val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
387  } else if (const auto *VD = dyn_cast<VarDecl>(DI)) {
388  if (!isAlwaysAlive(VD))
389  val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
390  }
391  }
392 }
393 
394 void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
395  // Kill the iteration variable.
396  DeclRefExpr *DR = nullptr;
397  const VarDecl *VD = nullptr;
398 
399  Stmt *element = OS->getElement();
400  if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
401  VD = cast<VarDecl>(DS->getSingleDecl());
402  }
403  else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
404  VD = cast<VarDecl>(DR->getDecl());
405  }
406 
407  if (VD) {
408  val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
409  if (observer && DR)
410  observer->observerKill(DR);
411  }
412 }
413 
414 void TransferFunctions::
415 VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
416 {
417  // While sizeof(var) doesn't technically extend the liveness of 'var', it
418  // does extent the liveness of metadata if 'var' is a VariableArrayType.
419  // We handle that special case here.
420  if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
421  return;
422 
423  const Expr *subEx = UE->getArgumentExpr();
424  if (subEx->getType()->isVariableArrayType()) {
425  assert(subEx->isLValue());
426  val.liveExprs = LV.ESetFact.add(val.liveExprs, subEx->IgnoreParens());
427  }
428 }
429 
430 void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
431  // Treat ++/-- as a kill.
432  // Note we don't actually have to do anything if we don't have an observer,
433  // since a ++/-- acts as both a kill and a "use".
434  if (!observer)
435  return;
436 
437  switch (UO->getOpcode()) {
438  default:
439  return;
440  case UO_PostInc:
441  case UO_PostDec:
442  case UO_PreInc:
443  case UO_PreDec:
444  break;
445  }
446 
447  if (auto *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) {
448  const Decl *D = DR->getDecl();
449  if (isa<VarDecl>(D) || isa<BindingDecl>(D)) {
450  // Treat ++/-- as a kill.
451  observer->observerKill(DR);
452  }
453  }
454 }
455 
460 
461  TransferFunctions TF(*this, val, obs, block);
462 
463  // Visit the terminator (if any).
464  if (const Stmt *term = block->getTerminatorStmt())
465  TF.Visit(const_cast<Stmt*>(term));
466 
467  // Apply the transfer function for all Stmts in the block.
468  for (CFGBlock::const_reverse_iterator it = block->rbegin(),
469  ei = block->rend(); it != ei; ++it) {
470  const CFGElement &elem = *it;
471 
473  elem.getAs<CFGAutomaticObjDtor>()) {
474  val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl());
475  continue;
476  }
477 
478  if (!elem.getAs<CFGStmt>())
479  continue;
480 
481  const Stmt *S = elem.castAs<CFGStmt>().getStmt();
482  TF.Visit(const_cast<Stmt*>(S));
483  stmtsToLiveness[S] = val;
484  }
485  return val;
486 }
487 
489  const CFG *cfg = getImpl(impl).analysisContext.getCFG();
490  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
491  getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
492 }
493 
494 LiveVariables::LiveVariables(void *im) : impl(im) {}
495 
497  delete (LiveVariablesImpl*) impl;
498 }
499 
500 std::unique_ptr<LiveVariables>
502 
503  // No CFG? Bail out.
504  CFG *cfg = AC.getCFG();
505  if (!cfg)
506  return nullptr;
507 
508  // The analysis currently has scalability issues for very large CFGs.
509  // Bail out if it looks too large.
510  if (cfg->getNumBlockIDs() > 300000)
511  return nullptr;
512 
513  LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
514 
515  // Construct the dataflow worklist. Enqueue the exit block as the
516  // start of the analysis.
517  BackwardDataflowWorklist worklist(*cfg, AC);
518  llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
519 
520  // FIXME: we should enqueue using post order.
521  for (const CFGBlock *B : cfg->nodes()) {
522  worklist.enqueueBlock(B);
523  }
524 
525  while (const CFGBlock *block = worklist.dequeue()) {
526  // Determine if the block's end value has changed. If not, we
527  // have nothing left to do for this block.
528  LivenessValues &prevVal = LV->blocksEndToLiveness[block];
529 
530  // Merge the values of all successor blocks.
531  LivenessValues val;
532  for (CFGBlock::const_succ_iterator it = block->succ_begin(),
533  ei = block->succ_end(); it != ei; ++it) {
534  if (const CFGBlock *succ = *it) {
535  val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
536  }
537  }
538 
539  if (!everAnalyzedBlock[block->getBlockID()])
540  everAnalyzedBlock[block->getBlockID()] = true;
541  else if (prevVal.equals(val))
542  continue;
543 
544  prevVal = val;
545 
546  // Update the dataflow value for the start of this block.
547  LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
548 
549  // Enqueue the value to the predecessors.
550  worklist.enqueuePredecessors(block);
551  }
552 
553  return std::unique_ptr<LiveVariables>(new LiveVariables(LV));
554 }
555 
557  getImpl(impl).dumpBlockLiveness(M);
558 }
559 
560 void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
561  std::vector<const CFGBlock *> vec;
562  for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
563  it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
564  it != ei; ++it) {
565  vec.push_back(it->first);
566  }
567  llvm::sort(vec, [](const CFGBlock *A, const CFGBlock *B) {
568  return A->getBlockID() < B->getBlockID();
569  });
570 
571  std::vector<const VarDecl*> declVec;
572 
573  for (std::vector<const CFGBlock *>::iterator
574  it = vec.begin(), ei = vec.end(); it != ei; ++it) {
575  llvm::errs() << "\n[ B" << (*it)->getBlockID()
576  << " (live variables at block exit) ]\n";
577 
578  LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
579  declVec.clear();
580 
581  for (llvm::ImmutableSet<const VarDecl *>::iterator si =
582  vals.liveDecls.begin(),
583  se = vals.liveDecls.end(); si != se; ++si) {
584  declVec.push_back(*si);
585  }
586 
587  llvm::sort(declVec, [](const Decl *A, const Decl *B) {
588  return A->getBeginLoc() < B->getBeginLoc();
589  });
590 
591  for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
592  de = declVec.end(); di != de; ++di) {
593  llvm::errs() << " " << (*di)->getDeclName().getAsString()
594  << " <";
595  (*di)->getLocation().print(llvm::errs(), M);
596  llvm::errs() << ">\n";
597  }
598  }
599  llvm::errs() << "\n";
600 }
601 
603  getImpl(impl).dumpExprLiveness(M);
604 }
605 
606 void LiveVariablesImpl::dumpExprLiveness(const SourceManager &M) {
607  // Don't iterate over blockEndsToLiveness directly because it's not sorted.
608  for (const CFGBlock *B : *analysisContext.getCFG()) {
609 
610  llvm::errs() << "\n[ B" << B->getBlockID()
611  << " (live expressions at block exit) ]\n";
612  for (const Expr *E : blocksEndToLiveness[B].liveExprs) {
613  llvm::errs() << "\n";
614  E->dump();
615  }
616  llvm::errs() << "\n";
617  }
618 }
619 
620 const void *LiveVariables::getTag() { static int x; return &x; }
621 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:3938
clang::Decl::getBeginLoc
SourceLocation getBeginLoc() const LLVM_READONLY
Definition: DeclBase.h:422
clang::LiveVariables::LivenessValues::equals
bool equals(const LivenessValues &V) const
Definition: LiveVariables.cpp:123
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:175
clang::VarDecl::hasGlobalStorage
bool hasGlobalStorage() const
Returns true for all variables that do not have local storage.
Definition: Decl.h:1143
clang::CFG::getNumBlockIDs
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
Definition: CFG.h:1411
clang::CFGBlock::succ_begin
succ_iterator succ_begin()
Definition: CFG.h:955
AnalysisDeclContext.h
clang::BindingDecl
A binding in a decomposition declaration.
Definition: DeclCXX.h:3959
clang::LiveVariables::LivenessValues
Definition: LiveVariables.h:30
clang::CFGBlock::getBlockID
unsigned getBlockID() const
Definition: CFG.h:1074
clang::QualType
A (possibly-)qualified type.
Definition: Type.h:673
clang::Decl::add
static void add(Kind k)
Definition: DeclBase.cpp:193
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:1304
llvm::Optional
Definition: LLVM.h:40
clang::Type::isVariableArrayType
bool isVariableArrayType() const
Definition: Type.h:6754
clang::UnaryOperator
UnaryOperator - This represents the unary-expression's (except sizeof and alignof),...
Definition: Expr.h:2157
clang::ObjCForCollectionStmt
Represents Objective-C's collection statement.
Definition: StmtObjC.h:23
clang::BinaryOperator::getOpcode
Opcode getOpcode() const
Definition: Expr.h:3847
clang::UnaryExprOrTypeTraitExpr::getArgumentExpr
Expr * getArgumentExpr()
Definition: Expr.h:2593
clang::RelaxedLiveVariables::getTag
static const void * getTag()
Definition: LiveVariables.cpp:621
clang::CFGBlock::const_succ_iterator
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:931
clang::CFG
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1225
AddLiveExpr
static void AddLiveExpr(llvm::ImmutableSet< const Expr * > &Set, llvm::ImmutableSet< const Expr * >::Factory &F, const Expr *E)
Definition: LiveVariables.cpp:205
clang::SourceManager
This class handles loading and caching of source files into memory.
Definition: SourceManager.h:626
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:135
clang::OpaqueValueExpr
OpaqueValueExpr - An expression referring to an opaque object of a fixed type and value class.
Definition: Expr.h:1129
clang::Type
The base class of the type hierarchy.
Definition: Type.h:1490
clang::FullExpr
FullExpr - Represents a "full-expression" node.
Definition: Expr.h:998
clang::CFGBlock
Represents a single basic block in a source-level CFG.
Definition: CFG.h:576
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:6688
clang::LiveVariables::~LiveVariables
~LiveVariables() override
Definition: LiveVariables.cpp:496
V
#define V(N, I)
Definition: ASTContext.h:3127
clang::LiveVariables::runOnAllBlocks
void runOnAllBlocks(Observer &obs)
Definition: LiveVariables.cpp:488
clang::UnaryExprOrTypeTraitExpr
UnaryExprOrTypeTraitExpr - expression with either a type or (unevaluated) expression operand.
Definition: Expr.h:2543
clang::LiveVariables::computeLiveness
static std::unique_ptr< LiveVariables > computeLiveness(AnalysisDeclContext &analysisContext, bool killAtAssign)
Compute the liveness information for a given CFG.
Definition: LiveVariables.cpp:501
clang::CFG::nodes
llvm::iterator_range< iterator > nodes()
Definition: CFG.h:1311
clang::BinaryOperator
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3803
isAlwaysAlive
static bool isAlwaysAlive(const VarDecl *D)
Definition: LiveVariables.cpp:131
LiveVariables.h
clang::BlockExpr::getBlockDecl
const BlockDecl * getBlockDecl() const
Definition: Expr.h:5977
clang::ArrayType
Represents an array type, per C99 6.7.5.2 - Array Declarators.
Definition: Type.h:2883
clang::CFGAutomaticObjDtor
Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...
Definition: CFG.h:389
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:556
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:881
clang::DeclRefExpr::getDecl
ValueDecl * getDecl()
Definition: Expr.h:1289
clang::VarDecl
Represents a variable declaration or definition.
Definition: Decl.h:876
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:602
clang::LiveVariables::getTag
static const void * getTag()
Definition: LiveVariables.cpp:620
clang::LiveVariables
Definition: LiveVariables.h:28
clang::BackwardDataflowWorklist::enqueuePredecessors
void enqueuePredecessors(const CFGBlock *Block)
Definition: DataflowWorklist.h:86
clang::Decl::dump
void dump() const
Definition: ASTDumper.cpp:178
clang::CFGBlock::rbegin
reverse_iterator rbegin()
Definition: CFG.h:880
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:2585
clang::DeclStmt::getSingleDecl
const Decl * getSingleDecl() const
Definition: Stmt.h:1312
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:3033
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:17
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:956
clang::BinaryOperator::getLHS
Expr * getLHS() const
Definition: Expr.h:3852
clang::BackwardDataflowWorklist
A worklist implementation for backward dataflow analysis.
Definition: DataflowWorklist.h:79
clang::BlockExpr
BlockExpr - Adaptor class for mixing a BlockDecl with expressions.
Definition: Expr.h:5965
clang::Decl
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:89
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:1297
clang::UnaryExprOrTypeTraitExpr::getKind
UnaryExprOrTypeTrait getKind() const
Definition: Expr.h:2575
clang::UnaryOperator::getSubExpr
Expr * getSubExpr() const
Definition: Expr.h:2204
clang::Expr::IgnoreParens
Expr * IgnoreParens() LLVM_READONLY
Skip past any parentheses which might surround this expression until reaching a fixed point.
Definition: Expr.cpp:2912
clang
Definition: CalledOnceCheck.h:17
CFG.h
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:69
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:834
clang::UnaryOperator::getOpcode
Opcode getOpcode() const
Definition: Expr.h:2199
clang::LiveVariables::LivenessValues::liveExprs
llvm::ImmutableSet< const Expr * > liveExprs
Definition: LiveVariables.h:33
LookThroughExpr
static const Expr * LookThroughExpr(const Expr *E)
Definition: LiveVariables.cpp:188
clang::CFGBlock::getTerminatorStmt
Stmt * getTerminatorStmt()
Definition: CFG.h:1050
clang::Expr::getType
QualType getType() const
Definition: Expr.h:141
clang::DeclStmt::decls
decl_range decls()
Definition: Stmt.h:1345
clang::CFG::begin
iterator begin()
Definition: CFG.h:1303
clang::QualType::getTypePtr
const Type * getTypePtr() const
Retrieves a pointer to the underlying (unqualified) type.
Definition: Type.h:6428
Stmt.h
clang::AnalysisDeclContext::getCFG
CFG * getCFG()
Definition: AnalysisDeclContext.cpp:213
writeShouldKill
static bool writeShouldKill(const VarDecl *VD)
Definition: LiveVariables.cpp:322
clang::ValueDecl::getType
QualType getType() const
Definition: Decl.h:687
clang::Expr
This represents one expression.
Definition: Expr.h:109
clang::DeclRefExpr
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:1217
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,...