xref: /openbsd-src/gnu/llvm/clang/lib/Analysis/LiveVariables.cpp (revision 12c855180aad702bbcca06e0398d774beeafb155)
1e5dd7070Spatrick //=- LiveVariables.cpp - Live Variable Analysis for Source CFGs ----------*-==//
2e5dd7070Spatrick //
3e5dd7070Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4e5dd7070Spatrick // See https://llvm.org/LICENSE.txt for license information.
5e5dd7070Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6e5dd7070Spatrick //
7e5dd7070Spatrick //===----------------------------------------------------------------------===//
8e5dd7070Spatrick //
9e5dd7070Spatrick // This file implements Live Variables analysis for source-level CFGs.
10e5dd7070Spatrick //
11e5dd7070Spatrick //===----------------------------------------------------------------------===//
12e5dd7070Spatrick 
13e5dd7070Spatrick #include "clang/Analysis/Analyses/LiveVariables.h"
14e5dd7070Spatrick #include "clang/AST/Stmt.h"
15e5dd7070Spatrick #include "clang/AST/StmtVisitor.h"
16e5dd7070Spatrick #include "clang/Analysis/AnalysisDeclContext.h"
17e5dd7070Spatrick #include "clang/Analysis/CFG.h"
18ec727ea7Spatrick #include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
19e5dd7070Spatrick #include "llvm/ADT/DenseMap.h"
20e5dd7070Spatrick #include "llvm/Support/raw_ostream.h"
21e5dd7070Spatrick #include <algorithm>
22*12c85518Srobert #include <optional>
23e5dd7070Spatrick #include <vector>
24e5dd7070Spatrick 
25e5dd7070Spatrick using namespace clang;
26e5dd7070Spatrick 
27e5dd7070Spatrick namespace {
28e5dd7070Spatrick class LiveVariablesImpl {
29e5dd7070Spatrick public:
30e5dd7070Spatrick   AnalysisDeclContext &analysisContext;
31a9ac8606Spatrick   llvm::ImmutableSet<const Expr *>::Factory ESetFact;
32e5dd7070Spatrick   llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;
33e5dd7070Spatrick   llvm::ImmutableSet<const BindingDecl *>::Factory BSetFact;
34e5dd7070Spatrick   llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;
35e5dd7070Spatrick   llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;
36e5dd7070Spatrick   llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness;
37e5dd7070Spatrick   llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment;
38e5dd7070Spatrick   const bool killAtAssign;
39e5dd7070Spatrick 
40e5dd7070Spatrick   LiveVariables::LivenessValues
41e5dd7070Spatrick   merge(LiveVariables::LivenessValues valsA,
42e5dd7070Spatrick         LiveVariables::LivenessValues valsB);
43e5dd7070Spatrick 
44e5dd7070Spatrick   LiveVariables::LivenessValues
45e5dd7070Spatrick   runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val,
46e5dd7070Spatrick              LiveVariables::Observer *obs = nullptr);
47e5dd7070Spatrick 
48e5dd7070Spatrick   void dumpBlockLiveness(const SourceManager& M);
49a9ac8606Spatrick   void dumpExprLiveness(const SourceManager& M);
50e5dd7070Spatrick 
LiveVariablesImpl(AnalysisDeclContext & ac,bool KillAtAssign)51e5dd7070Spatrick   LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign)
52e5dd7070Spatrick       : analysisContext(ac),
53a9ac8606Spatrick         ESetFact(false), // Do not canonicalize ImmutableSets by default.
54e5dd7070Spatrick         DSetFact(false), // This is a *major* performance win.
55a9ac8606Spatrick         BSetFact(false), killAtAssign(KillAtAssign) {}
56e5dd7070Spatrick };
57a9ac8606Spatrick } // namespace
58e5dd7070Spatrick 
getImpl(void * x)59e5dd7070Spatrick static LiveVariablesImpl &getImpl(void *x) {
60e5dd7070Spatrick   return *((LiveVariablesImpl *) x);
61e5dd7070Spatrick }
62e5dd7070Spatrick 
63e5dd7070Spatrick //===----------------------------------------------------------------------===//
64e5dd7070Spatrick // Operations and queries on LivenessValues.
65e5dd7070Spatrick //===----------------------------------------------------------------------===//
66e5dd7070Spatrick 
isLive(const Expr * E) const67a9ac8606Spatrick bool LiveVariables::LivenessValues::isLive(const Expr *E) const {
68a9ac8606Spatrick   return liveExprs.contains(E);
69e5dd7070Spatrick }
70e5dd7070Spatrick 
isLive(const VarDecl * D) const71e5dd7070Spatrick bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const {
72e5dd7070Spatrick   if (const auto *DD = dyn_cast<DecompositionDecl>(D)) {
73e5dd7070Spatrick     bool alive = false;
74e5dd7070Spatrick     for (const BindingDecl *BD : DD->bindings())
75e5dd7070Spatrick       alive |= liveBindings.contains(BD);
76*12c85518Srobert 
77*12c85518Srobert     // Note: the only known case this condition is necessary, is when a bindig
78*12c85518Srobert     // to a tuple-like structure is created. The HoldingVar initializers have a
79*12c85518Srobert     // DeclRefExpr to the DecompositionDecl.
80*12c85518Srobert     alive |= liveDecls.contains(DD);
81e5dd7070Spatrick     return alive;
82e5dd7070Spatrick   }
83e5dd7070Spatrick   return liveDecls.contains(D);
84e5dd7070Spatrick }
85e5dd7070Spatrick 
86e5dd7070Spatrick namespace {
87e5dd7070Spatrick   template <typename SET>
mergeSets(SET A,SET B)88e5dd7070Spatrick   SET mergeSets(SET A, SET B) {
89e5dd7070Spatrick     if (A.isEmpty())
90e5dd7070Spatrick       return B;
91e5dd7070Spatrick 
92e5dd7070Spatrick     for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
93e5dd7070Spatrick       A = A.add(*it);
94e5dd7070Spatrick     }
95e5dd7070Spatrick     return A;
96e5dd7070Spatrick   }
97ec727ea7Spatrick } // namespace
98e5dd7070Spatrick 
anchor()99e5dd7070Spatrick void LiveVariables::Observer::anchor() { }
100e5dd7070Spatrick 
101e5dd7070Spatrick LiveVariables::LivenessValues
merge(LiveVariables::LivenessValues valsA,LiveVariables::LivenessValues valsB)102e5dd7070Spatrick LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,
103e5dd7070Spatrick                          LiveVariables::LivenessValues valsB) {
104e5dd7070Spatrick 
105a9ac8606Spatrick   llvm::ImmutableSetRef<const Expr *> SSetRefA(
106a9ac8606Spatrick       valsA.liveExprs.getRootWithoutRetain(), ESetFact.getTreeFactory()),
107a9ac8606Spatrick       SSetRefB(valsB.liveExprs.getRootWithoutRetain(),
108a9ac8606Spatrick                ESetFact.getTreeFactory());
109e5dd7070Spatrick 
110e5dd7070Spatrick   llvm::ImmutableSetRef<const VarDecl *>
111e5dd7070Spatrick     DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),
112e5dd7070Spatrick     DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());
113e5dd7070Spatrick 
114e5dd7070Spatrick   llvm::ImmutableSetRef<const BindingDecl *>
115e5dd7070Spatrick     BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()),
116e5dd7070Spatrick     BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory());
117e5dd7070Spatrick 
118e5dd7070Spatrick   SSetRefA = mergeSets(SSetRefA, SSetRefB);
119e5dd7070Spatrick   DSetRefA = mergeSets(DSetRefA, DSetRefB);
120e5dd7070Spatrick   BSetRefA = mergeSets(BSetRefA, BSetRefB);
121e5dd7070Spatrick 
122e5dd7070Spatrick   // asImmutableSet() canonicalizes the tree, allowing us to do an easy
123e5dd7070Spatrick   // comparison afterwards.
124e5dd7070Spatrick   return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(),
125e5dd7070Spatrick                                        DSetRefA.asImmutableSet(),
126e5dd7070Spatrick                                        BSetRefA.asImmutableSet());
127e5dd7070Spatrick }
128e5dd7070Spatrick 
equals(const LivenessValues & V) const129e5dd7070Spatrick bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const {
130a9ac8606Spatrick   return liveExprs == V.liveExprs && liveDecls == V.liveDecls;
131e5dd7070Spatrick }
132e5dd7070Spatrick 
133e5dd7070Spatrick //===----------------------------------------------------------------------===//
134e5dd7070Spatrick // Query methods.
135e5dd7070Spatrick //===----------------------------------------------------------------------===//
136e5dd7070Spatrick 
isAlwaysAlive(const VarDecl * D)137e5dd7070Spatrick static bool isAlwaysAlive(const VarDecl *D) {
138e5dd7070Spatrick   return D->hasGlobalStorage();
139e5dd7070Spatrick }
140e5dd7070Spatrick 
isLive(const CFGBlock * B,const VarDecl * D)141e5dd7070Spatrick bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {
142e5dd7070Spatrick   return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);
143e5dd7070Spatrick }
144e5dd7070Spatrick 
isLive(const Stmt * S,const VarDecl * D)145e5dd7070Spatrick bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
146e5dd7070Spatrick   return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);
147e5dd7070Spatrick }
148e5dd7070Spatrick 
isLive(const Stmt * Loc,const Expr * Val)149a9ac8606Spatrick bool LiveVariables::isLive(const Stmt *Loc, const Expr *Val) {
150a9ac8606Spatrick   return getImpl(impl).stmtsToLiveness[Loc].isLive(Val);
151e5dd7070Spatrick }
152e5dd7070Spatrick 
153e5dd7070Spatrick //===----------------------------------------------------------------------===//
154e5dd7070Spatrick // Dataflow computation.
155e5dd7070Spatrick //===----------------------------------------------------------------------===//
156e5dd7070Spatrick 
157e5dd7070Spatrick namespace {
158e5dd7070Spatrick class TransferFunctions : public StmtVisitor<TransferFunctions> {
159e5dd7070Spatrick   LiveVariablesImpl &LV;
160e5dd7070Spatrick   LiveVariables::LivenessValues &val;
161e5dd7070Spatrick   LiveVariables::Observer *observer;
162e5dd7070Spatrick   const CFGBlock *currentBlock;
163e5dd7070Spatrick public:
TransferFunctions(LiveVariablesImpl & im,LiveVariables::LivenessValues & Val,LiveVariables::Observer * Observer,const CFGBlock * CurrentBlock)164e5dd7070Spatrick   TransferFunctions(LiveVariablesImpl &im,
165e5dd7070Spatrick                     LiveVariables::LivenessValues &Val,
166e5dd7070Spatrick                     LiveVariables::Observer *Observer,
167e5dd7070Spatrick                     const CFGBlock *CurrentBlock)
168e5dd7070Spatrick   : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}
169e5dd7070Spatrick 
170e5dd7070Spatrick   void VisitBinaryOperator(BinaryOperator *BO);
171e5dd7070Spatrick   void VisitBlockExpr(BlockExpr *BE);
172e5dd7070Spatrick   void VisitDeclRefExpr(DeclRefExpr *DR);
173e5dd7070Spatrick   void VisitDeclStmt(DeclStmt *DS);
174e5dd7070Spatrick   void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS);
175e5dd7070Spatrick   void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE);
176e5dd7070Spatrick   void VisitUnaryOperator(UnaryOperator *UO);
177e5dd7070Spatrick   void Visit(Stmt *S);
178e5dd7070Spatrick };
179ec727ea7Spatrick } // namespace
180e5dd7070Spatrick 
FindVA(QualType Ty)181e5dd7070Spatrick static const VariableArrayType *FindVA(QualType Ty) {
182e5dd7070Spatrick   const Type *ty = Ty.getTypePtr();
183e5dd7070Spatrick   while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) {
184e5dd7070Spatrick     if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT))
185e5dd7070Spatrick       if (VAT->getSizeExpr())
186e5dd7070Spatrick         return VAT;
187e5dd7070Spatrick 
188e5dd7070Spatrick     ty = VT->getElementType().getTypePtr();
189e5dd7070Spatrick   }
190e5dd7070Spatrick 
191e5dd7070Spatrick   return nullptr;
192e5dd7070Spatrick }
193e5dd7070Spatrick 
LookThroughExpr(const Expr * E)194a9ac8606Spatrick static const Expr *LookThroughExpr(const Expr *E) {
195a9ac8606Spatrick   while (E) {
196a9ac8606Spatrick     if (const Expr *Ex = dyn_cast<Expr>(E))
197a9ac8606Spatrick       E = Ex->IgnoreParens();
198a9ac8606Spatrick     if (const FullExpr *FE = dyn_cast<FullExpr>(E)) {
199a9ac8606Spatrick       E = FE->getSubExpr();
200e5dd7070Spatrick       continue;
201e5dd7070Spatrick     }
202a9ac8606Spatrick     if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(E)) {
203a9ac8606Spatrick       E = OVE->getSourceExpr();
204e5dd7070Spatrick       continue;
205e5dd7070Spatrick     }
206e5dd7070Spatrick     break;
207e5dd7070Spatrick   }
208a9ac8606Spatrick   return E;
209e5dd7070Spatrick }
210e5dd7070Spatrick 
AddLiveExpr(llvm::ImmutableSet<const Expr * > & Set,llvm::ImmutableSet<const Expr * >::Factory & F,const Expr * E)211a9ac8606Spatrick static void AddLiveExpr(llvm::ImmutableSet<const Expr *> &Set,
212a9ac8606Spatrick                         llvm::ImmutableSet<const Expr *>::Factory &F,
213a9ac8606Spatrick                         const Expr *E) {
214a9ac8606Spatrick   Set = F.add(Set, LookThroughExpr(E));
215e5dd7070Spatrick }
216e5dd7070Spatrick 
Visit(Stmt * S)217e5dd7070Spatrick void TransferFunctions::Visit(Stmt *S) {
218e5dd7070Spatrick   if (observer)
219e5dd7070Spatrick     observer->observeStmt(S, currentBlock, val);
220e5dd7070Spatrick 
221e5dd7070Spatrick   StmtVisitor<TransferFunctions>::Visit(S);
222e5dd7070Spatrick 
223a9ac8606Spatrick   if (const auto *E = dyn_cast<Expr>(S)) {
224a9ac8606Spatrick     val.liveExprs = LV.ESetFact.remove(val.liveExprs, E);
225e5dd7070Spatrick   }
226e5dd7070Spatrick 
227e5dd7070Spatrick   // Mark all children expressions live.
228e5dd7070Spatrick 
229e5dd7070Spatrick   switch (S->getStmtClass()) {
230e5dd7070Spatrick     default:
231e5dd7070Spatrick       break;
232e5dd7070Spatrick     case Stmt::StmtExprClass: {
233e5dd7070Spatrick       // For statement expressions, look through the compound statement.
234e5dd7070Spatrick       S = cast<StmtExpr>(S)->getSubStmt();
235e5dd7070Spatrick       break;
236e5dd7070Spatrick     }
237e5dd7070Spatrick     case Stmt::CXXMemberCallExprClass: {
238e5dd7070Spatrick       // Include the implicit "this" pointer as being live.
239e5dd7070Spatrick       CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);
240e5dd7070Spatrick       if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) {
241a9ac8606Spatrick         AddLiveExpr(val.liveExprs, LV.ESetFact, ImplicitObj);
242e5dd7070Spatrick       }
243e5dd7070Spatrick       break;
244e5dd7070Spatrick     }
245e5dd7070Spatrick     case Stmt::ObjCMessageExprClass: {
246e5dd7070Spatrick       // In calls to super, include the implicit "self" pointer as being live.
247e5dd7070Spatrick       ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S);
248e5dd7070Spatrick       if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance)
249e5dd7070Spatrick         val.liveDecls = LV.DSetFact.add(val.liveDecls,
250e5dd7070Spatrick                                         LV.analysisContext.getSelfDecl());
251e5dd7070Spatrick       break;
252e5dd7070Spatrick     }
253e5dd7070Spatrick     case Stmt::DeclStmtClass: {
254e5dd7070Spatrick       const DeclStmt *DS = cast<DeclStmt>(S);
255e5dd7070Spatrick       if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) {
256e5dd7070Spatrick         for (const VariableArrayType* VA = FindVA(VD->getType());
257e5dd7070Spatrick              VA != nullptr; VA = FindVA(VA->getElementType())) {
258a9ac8606Spatrick           AddLiveExpr(val.liveExprs, LV.ESetFact, VA->getSizeExpr());
259e5dd7070Spatrick         }
260e5dd7070Spatrick       }
261e5dd7070Spatrick       break;
262e5dd7070Spatrick     }
263e5dd7070Spatrick     case Stmt::PseudoObjectExprClass: {
264e5dd7070Spatrick       // A pseudo-object operation only directly consumes its result
265e5dd7070Spatrick       // expression.
266e5dd7070Spatrick       Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();
267e5dd7070Spatrick       if (!child) return;
268e5dd7070Spatrick       if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child))
269e5dd7070Spatrick         child = OV->getSourceExpr();
270e5dd7070Spatrick       child = child->IgnoreParens();
271a9ac8606Spatrick       val.liveExprs = LV.ESetFact.add(val.liveExprs, child);
272e5dd7070Spatrick       return;
273e5dd7070Spatrick     }
274e5dd7070Spatrick 
275e5dd7070Spatrick     // FIXME: These cases eventually shouldn't be needed.
276e5dd7070Spatrick     case Stmt::ExprWithCleanupsClass: {
277e5dd7070Spatrick       S = cast<ExprWithCleanups>(S)->getSubExpr();
278e5dd7070Spatrick       break;
279e5dd7070Spatrick     }
280e5dd7070Spatrick     case Stmt::CXXBindTemporaryExprClass: {
281e5dd7070Spatrick       S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
282e5dd7070Spatrick       break;
283e5dd7070Spatrick     }
284e5dd7070Spatrick     case Stmt::UnaryExprOrTypeTraitExprClass: {
285e5dd7070Spatrick       // No need to unconditionally visit subexpressions.
286e5dd7070Spatrick       return;
287e5dd7070Spatrick     }
288e5dd7070Spatrick     case Stmt::IfStmtClass: {
289e5dd7070Spatrick       // If one of the branches is an expression rather than a compound
290e5dd7070Spatrick       // statement, it will be bad if we mark it as live at the terminator
291e5dd7070Spatrick       // of the if-statement (i.e., immediately after the condition expression).
292a9ac8606Spatrick       AddLiveExpr(val.liveExprs, LV.ESetFact, cast<IfStmt>(S)->getCond());
293e5dd7070Spatrick       return;
294e5dd7070Spatrick     }
295e5dd7070Spatrick     case Stmt::WhileStmtClass: {
296e5dd7070Spatrick       // If the loop body is an expression rather than a compound statement,
297e5dd7070Spatrick       // it will be bad if we mark it as live at the terminator of the loop
298e5dd7070Spatrick       // (i.e., immediately after the condition expression).
299a9ac8606Spatrick       AddLiveExpr(val.liveExprs, LV.ESetFact, cast<WhileStmt>(S)->getCond());
300e5dd7070Spatrick       return;
301e5dd7070Spatrick     }
302e5dd7070Spatrick     case Stmt::DoStmtClass: {
303e5dd7070Spatrick       // If the loop body is an expression rather than a compound statement,
304e5dd7070Spatrick       // it will be bad if we mark it as live at the terminator of the loop
305e5dd7070Spatrick       // (i.e., immediately after the condition expression).
306a9ac8606Spatrick       AddLiveExpr(val.liveExprs, LV.ESetFact, cast<DoStmt>(S)->getCond());
307e5dd7070Spatrick       return;
308e5dd7070Spatrick     }
309e5dd7070Spatrick     case Stmt::ForStmtClass: {
310e5dd7070Spatrick       // If the loop body is an expression rather than a compound statement,
311e5dd7070Spatrick       // it will be bad if we mark it as live at the terminator of the loop
312e5dd7070Spatrick       // (i.e., immediately after the condition expression).
313a9ac8606Spatrick       AddLiveExpr(val.liveExprs, LV.ESetFact, cast<ForStmt>(S)->getCond());
314e5dd7070Spatrick       return;
315e5dd7070Spatrick     }
316e5dd7070Spatrick 
317e5dd7070Spatrick   }
318e5dd7070Spatrick 
319a9ac8606Spatrick   // HACK + FIXME: What is this? One could only guess that this is an attempt to
320a9ac8606Spatrick   // fish for live values, for example, arguments from a call expression.
321a9ac8606Spatrick   // Maybe we could take inspiration from UninitializedVariable analysis?
322e5dd7070Spatrick   for (Stmt *Child : S->children()) {
323a9ac8606Spatrick     if (const auto *E = dyn_cast_or_null<Expr>(Child))
324a9ac8606Spatrick       AddLiveExpr(val.liveExprs, LV.ESetFact, E);
325e5dd7070Spatrick   }
326e5dd7070Spatrick }
327e5dd7070Spatrick 
writeShouldKill(const VarDecl * VD)328e5dd7070Spatrick static bool writeShouldKill(const VarDecl *VD) {
329e5dd7070Spatrick   return VD && !VD->getType()->isReferenceType() &&
330e5dd7070Spatrick     !isAlwaysAlive(VD);
331e5dd7070Spatrick }
332e5dd7070Spatrick 
VisitBinaryOperator(BinaryOperator * B)333e5dd7070Spatrick void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
334a9ac8606Spatrick   if (LV.killAtAssign && B->getOpcode() == BO_Assign) {
335a9ac8606Spatrick     if (const auto *DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParens())) {
336a9ac8606Spatrick       LV.inAssignment[DR] = 1;
337a9ac8606Spatrick     }
338a9ac8606Spatrick   }
339e5dd7070Spatrick   if (B->isAssignmentOp()) {
340e5dd7070Spatrick     if (!LV.killAtAssign)
341e5dd7070Spatrick       return;
342e5dd7070Spatrick 
343e5dd7070Spatrick     // Assigning to a variable?
344e5dd7070Spatrick     Expr *LHS = B->getLHS()->IgnoreParens();
345e5dd7070Spatrick 
346e5dd7070Spatrick     if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
347e5dd7070Spatrick       const Decl* D = DR->getDecl();
348e5dd7070Spatrick       bool Killed = false;
349e5dd7070Spatrick 
350e5dd7070Spatrick       if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) {
351e5dd7070Spatrick         Killed = !BD->getType()->isReferenceType();
352*12c85518Srobert         if (Killed) {
353*12c85518Srobert           if (const auto *HV = BD->getHoldingVar())
354*12c85518Srobert             val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV);
355*12c85518Srobert 
356e5dd7070Spatrick           val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
357*12c85518Srobert         }
358e5dd7070Spatrick       } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
359e5dd7070Spatrick         Killed = writeShouldKill(VD);
360e5dd7070Spatrick         if (Killed)
361e5dd7070Spatrick           val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
362e5dd7070Spatrick 
363e5dd7070Spatrick       }
364e5dd7070Spatrick 
365e5dd7070Spatrick       if (Killed && observer)
366e5dd7070Spatrick         observer->observerKill(DR);
367e5dd7070Spatrick     }
368e5dd7070Spatrick   }
369e5dd7070Spatrick }
370e5dd7070Spatrick 
VisitBlockExpr(BlockExpr * BE)371e5dd7070Spatrick void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
372e5dd7070Spatrick   for (const VarDecl *VD :
373e5dd7070Spatrick        LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) {
374e5dd7070Spatrick     if (isAlwaysAlive(VD))
375e5dd7070Spatrick       continue;
376e5dd7070Spatrick     val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
377e5dd7070Spatrick   }
378e5dd7070Spatrick }
379e5dd7070Spatrick 
VisitDeclRefExpr(DeclRefExpr * DR)380e5dd7070Spatrick void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
381e5dd7070Spatrick   const Decl* D = DR->getDecl();
382e5dd7070Spatrick   bool InAssignment = LV.inAssignment[DR];
383e5dd7070Spatrick   if (const auto *BD = dyn_cast<BindingDecl>(D)) {
384*12c85518Srobert     if (!InAssignment) {
385*12c85518Srobert       if (const auto *HV = BD->getHoldingVar())
386*12c85518Srobert         val.liveDecls = LV.DSetFact.add(val.liveDecls, HV);
387*12c85518Srobert 
388e5dd7070Spatrick       val.liveBindings = LV.BSetFact.add(val.liveBindings, BD);
389*12c85518Srobert     }
390e5dd7070Spatrick   } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
391e5dd7070Spatrick     if (!InAssignment && !isAlwaysAlive(VD))
392e5dd7070Spatrick       val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
393e5dd7070Spatrick   }
394e5dd7070Spatrick }
395e5dd7070Spatrick 
VisitDeclStmt(DeclStmt * DS)396e5dd7070Spatrick void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
397e5dd7070Spatrick   for (const auto *DI : DS->decls()) {
398e5dd7070Spatrick     if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) {
399*12c85518Srobert       for (const auto *BD : DD->bindings()) {
400*12c85518Srobert         if (const auto *HV = BD->getHoldingVar())
401*12c85518Srobert           val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV);
402*12c85518Srobert 
403e5dd7070Spatrick         val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
404*12c85518Srobert       }
405*12c85518Srobert 
406*12c85518Srobert       // When a bindig to a tuple-like structure is created, the HoldingVar
407*12c85518Srobert       // initializers have a DeclRefExpr to the DecompositionDecl.
408*12c85518Srobert       val.liveDecls = LV.DSetFact.remove(val.liveDecls, DD);
409e5dd7070Spatrick     } else if (const auto *VD = dyn_cast<VarDecl>(DI)) {
410e5dd7070Spatrick       if (!isAlwaysAlive(VD))
411e5dd7070Spatrick         val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
412e5dd7070Spatrick     }
413e5dd7070Spatrick   }
414e5dd7070Spatrick }
415e5dd7070Spatrick 
VisitObjCForCollectionStmt(ObjCForCollectionStmt * OS)416e5dd7070Spatrick void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
417e5dd7070Spatrick   // Kill the iteration variable.
418e5dd7070Spatrick   DeclRefExpr *DR = nullptr;
419e5dd7070Spatrick   const VarDecl *VD = nullptr;
420e5dd7070Spatrick 
421e5dd7070Spatrick   Stmt *element = OS->getElement();
422e5dd7070Spatrick   if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
423e5dd7070Spatrick     VD = cast<VarDecl>(DS->getSingleDecl());
424e5dd7070Spatrick   }
425e5dd7070Spatrick   else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
426e5dd7070Spatrick     VD = cast<VarDecl>(DR->getDecl());
427e5dd7070Spatrick   }
428e5dd7070Spatrick 
429e5dd7070Spatrick   if (VD) {
430e5dd7070Spatrick     val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
431e5dd7070Spatrick     if (observer && DR)
432e5dd7070Spatrick       observer->observerKill(DR);
433e5dd7070Spatrick   }
434e5dd7070Spatrick }
435e5dd7070Spatrick 
436e5dd7070Spatrick void TransferFunctions::
VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr * UE)437e5dd7070Spatrick VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
438e5dd7070Spatrick {
439e5dd7070Spatrick   // While sizeof(var) doesn't technically extend the liveness of 'var', it
440e5dd7070Spatrick   // does extent the liveness of metadata if 'var' is a VariableArrayType.
441e5dd7070Spatrick   // We handle that special case here.
442e5dd7070Spatrick   if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
443e5dd7070Spatrick     return;
444e5dd7070Spatrick 
445e5dd7070Spatrick   const Expr *subEx = UE->getArgumentExpr();
446e5dd7070Spatrick   if (subEx->getType()->isVariableArrayType()) {
447e5dd7070Spatrick     assert(subEx->isLValue());
448a9ac8606Spatrick     val.liveExprs = LV.ESetFact.add(val.liveExprs, subEx->IgnoreParens());
449e5dd7070Spatrick   }
450e5dd7070Spatrick }
451e5dd7070Spatrick 
VisitUnaryOperator(UnaryOperator * UO)452e5dd7070Spatrick void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
453e5dd7070Spatrick   // Treat ++/-- as a kill.
454e5dd7070Spatrick   // Note we don't actually have to do anything if we don't have an observer,
455e5dd7070Spatrick   // since a ++/-- acts as both a kill and a "use".
456e5dd7070Spatrick   if (!observer)
457e5dd7070Spatrick     return;
458e5dd7070Spatrick 
459e5dd7070Spatrick   switch (UO->getOpcode()) {
460e5dd7070Spatrick   default:
461e5dd7070Spatrick     return;
462e5dd7070Spatrick   case UO_PostInc:
463e5dd7070Spatrick   case UO_PostDec:
464e5dd7070Spatrick   case UO_PreInc:
465e5dd7070Spatrick   case UO_PreDec:
466e5dd7070Spatrick     break;
467e5dd7070Spatrick   }
468e5dd7070Spatrick 
469e5dd7070Spatrick   if (auto *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) {
470e5dd7070Spatrick     const Decl *D = DR->getDecl();
471e5dd7070Spatrick     if (isa<VarDecl>(D) || isa<BindingDecl>(D)) {
472e5dd7070Spatrick       // Treat ++/-- as a kill.
473e5dd7070Spatrick       observer->observerKill(DR);
474e5dd7070Spatrick     }
475e5dd7070Spatrick   }
476e5dd7070Spatrick }
477e5dd7070Spatrick 
478e5dd7070Spatrick LiveVariables::LivenessValues
runOnBlock(const CFGBlock * block,LiveVariables::LivenessValues val,LiveVariables::Observer * obs)479e5dd7070Spatrick LiveVariablesImpl::runOnBlock(const CFGBlock *block,
480e5dd7070Spatrick                               LiveVariables::LivenessValues val,
481e5dd7070Spatrick                               LiveVariables::Observer *obs) {
482e5dd7070Spatrick 
483e5dd7070Spatrick   TransferFunctions TF(*this, val, obs, block);
484e5dd7070Spatrick 
485e5dd7070Spatrick   // Visit the terminator (if any).
486e5dd7070Spatrick   if (const Stmt *term = block->getTerminatorStmt())
487e5dd7070Spatrick     TF.Visit(const_cast<Stmt*>(term));
488e5dd7070Spatrick 
489e5dd7070Spatrick   // Apply the transfer function for all Stmts in the block.
490e5dd7070Spatrick   for (CFGBlock::const_reverse_iterator it = block->rbegin(),
491e5dd7070Spatrick        ei = block->rend(); it != ei; ++it) {
492e5dd7070Spatrick     const CFGElement &elem = *it;
493e5dd7070Spatrick 
494*12c85518Srobert     if (std::optional<CFGAutomaticObjDtor> Dtor =
495e5dd7070Spatrick             elem.getAs<CFGAutomaticObjDtor>()) {
496e5dd7070Spatrick       val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl());
497e5dd7070Spatrick       continue;
498e5dd7070Spatrick     }
499e5dd7070Spatrick 
500e5dd7070Spatrick     if (!elem.getAs<CFGStmt>())
501e5dd7070Spatrick       continue;
502e5dd7070Spatrick 
503e5dd7070Spatrick     const Stmt *S = elem.castAs<CFGStmt>().getStmt();
504e5dd7070Spatrick     TF.Visit(const_cast<Stmt*>(S));
505e5dd7070Spatrick     stmtsToLiveness[S] = val;
506e5dd7070Spatrick   }
507e5dd7070Spatrick   return val;
508e5dd7070Spatrick }
509e5dd7070Spatrick 
runOnAllBlocks(LiveVariables::Observer & obs)510e5dd7070Spatrick void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {
511e5dd7070Spatrick   const CFG *cfg = getImpl(impl).analysisContext.getCFG();
512e5dd7070Spatrick   for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
513e5dd7070Spatrick     getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
514e5dd7070Spatrick }
515e5dd7070Spatrick 
LiveVariables(void * im)516e5dd7070Spatrick LiveVariables::LiveVariables(void *im) : impl(im) {}
517e5dd7070Spatrick 
~LiveVariables()518e5dd7070Spatrick LiveVariables::~LiveVariables() {
519e5dd7070Spatrick   delete (LiveVariablesImpl*) impl;
520e5dd7070Spatrick }
521e5dd7070Spatrick 
522ec727ea7Spatrick std::unique_ptr<LiveVariables>
computeLiveness(AnalysisDeclContext & AC,bool killAtAssign)523ec727ea7Spatrick LiveVariables::computeLiveness(AnalysisDeclContext &AC, bool killAtAssign) {
524e5dd7070Spatrick 
525e5dd7070Spatrick   // No CFG?  Bail out.
526e5dd7070Spatrick   CFG *cfg = AC.getCFG();
527e5dd7070Spatrick   if (!cfg)
528e5dd7070Spatrick     return nullptr;
529e5dd7070Spatrick 
530e5dd7070Spatrick   // The analysis currently has scalability issues for very large CFGs.
531e5dd7070Spatrick   // Bail out if it looks too large.
532e5dd7070Spatrick   if (cfg->getNumBlockIDs() > 300000)
533e5dd7070Spatrick     return nullptr;
534e5dd7070Spatrick 
535e5dd7070Spatrick   LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
536e5dd7070Spatrick 
537e5dd7070Spatrick   // Construct the dataflow worklist.  Enqueue the exit block as the
538e5dd7070Spatrick   // start of the analysis.
539ec727ea7Spatrick   BackwardDataflowWorklist worklist(*cfg, AC);
540e5dd7070Spatrick   llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
541e5dd7070Spatrick 
542e5dd7070Spatrick   // FIXME: we should enqueue using post order.
543a9ac8606Spatrick   for (const CFGBlock *B : cfg->nodes()) {
544a9ac8606Spatrick     worklist.enqueueBlock(B);
545e5dd7070Spatrick   }
546e5dd7070Spatrick 
547e5dd7070Spatrick   while (const CFGBlock *block = worklist.dequeue()) {
548e5dd7070Spatrick     // Determine if the block's end value has changed.  If not, we
549e5dd7070Spatrick     // have nothing left to do for this block.
550e5dd7070Spatrick     LivenessValues &prevVal = LV->blocksEndToLiveness[block];
551e5dd7070Spatrick 
552e5dd7070Spatrick     // Merge the values of all successor blocks.
553e5dd7070Spatrick     LivenessValues val;
554e5dd7070Spatrick     for (CFGBlock::const_succ_iterator it = block->succ_begin(),
555e5dd7070Spatrick                                        ei = block->succ_end(); it != ei; ++it) {
556e5dd7070Spatrick       if (const CFGBlock *succ = *it) {
557e5dd7070Spatrick         val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
558e5dd7070Spatrick       }
559e5dd7070Spatrick     }
560e5dd7070Spatrick 
561e5dd7070Spatrick     if (!everAnalyzedBlock[block->getBlockID()])
562e5dd7070Spatrick       everAnalyzedBlock[block->getBlockID()] = true;
563e5dd7070Spatrick     else if (prevVal.equals(val))
564e5dd7070Spatrick       continue;
565e5dd7070Spatrick 
566e5dd7070Spatrick     prevVal = val;
567e5dd7070Spatrick 
568e5dd7070Spatrick     // Update the dataflow value for the start of this block.
569e5dd7070Spatrick     LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
570e5dd7070Spatrick 
571e5dd7070Spatrick     // Enqueue the value to the predecessors.
572e5dd7070Spatrick     worklist.enqueuePredecessors(block);
573e5dd7070Spatrick   }
574e5dd7070Spatrick 
575ec727ea7Spatrick   return std::unique_ptr<LiveVariables>(new LiveVariables(LV));
576e5dd7070Spatrick }
577e5dd7070Spatrick 
dumpBlockLiveness(const SourceManager & M)578e5dd7070Spatrick void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
579e5dd7070Spatrick   getImpl(impl).dumpBlockLiveness(M);
580e5dd7070Spatrick }
581e5dd7070Spatrick 
dumpBlockLiveness(const SourceManager & M)582e5dd7070Spatrick void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
583e5dd7070Spatrick   std::vector<const CFGBlock *> vec;
584e5dd7070Spatrick   for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
585e5dd7070Spatrick        it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
586e5dd7070Spatrick        it != ei; ++it) {
587e5dd7070Spatrick     vec.push_back(it->first);
588e5dd7070Spatrick   }
589e5dd7070Spatrick   llvm::sort(vec, [](const CFGBlock *A, const CFGBlock *B) {
590e5dd7070Spatrick     return A->getBlockID() < B->getBlockID();
591e5dd7070Spatrick   });
592e5dd7070Spatrick 
593e5dd7070Spatrick   std::vector<const VarDecl*> declVec;
594e5dd7070Spatrick 
595e5dd7070Spatrick   for (std::vector<const CFGBlock *>::iterator
596e5dd7070Spatrick         it = vec.begin(), ei = vec.end(); it != ei; ++it) {
597e5dd7070Spatrick     llvm::errs() << "\n[ B" << (*it)->getBlockID()
598e5dd7070Spatrick                  << " (live variables at block exit) ]\n";
599e5dd7070Spatrick 
600e5dd7070Spatrick     LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
601e5dd7070Spatrick     declVec.clear();
602e5dd7070Spatrick 
603e5dd7070Spatrick     for (llvm::ImmutableSet<const VarDecl *>::iterator si =
604e5dd7070Spatrick           vals.liveDecls.begin(),
605e5dd7070Spatrick           se = vals.liveDecls.end(); si != se; ++si) {
606e5dd7070Spatrick       declVec.push_back(*si);
607e5dd7070Spatrick     }
608e5dd7070Spatrick 
609e5dd7070Spatrick     llvm::sort(declVec, [](const Decl *A, const Decl *B) {
610e5dd7070Spatrick       return A->getBeginLoc() < B->getBeginLoc();
611e5dd7070Spatrick     });
612e5dd7070Spatrick 
613e5dd7070Spatrick     for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
614e5dd7070Spatrick          de = declVec.end(); di != de; ++di) {
615e5dd7070Spatrick       llvm::errs() << " " << (*di)->getDeclName().getAsString()
616e5dd7070Spatrick                    << " <";
617e5dd7070Spatrick       (*di)->getLocation().print(llvm::errs(), M);
618e5dd7070Spatrick       llvm::errs() << ">\n";
619e5dd7070Spatrick     }
620e5dd7070Spatrick   }
621e5dd7070Spatrick   llvm::errs() << "\n";
622e5dd7070Spatrick }
623e5dd7070Spatrick 
dumpExprLiveness(const SourceManager & M)624a9ac8606Spatrick void LiveVariables::dumpExprLiveness(const SourceManager &M) {
625a9ac8606Spatrick   getImpl(impl).dumpExprLiveness(M);
626e5dd7070Spatrick }
627e5dd7070Spatrick 
dumpExprLiveness(const SourceManager & M)628a9ac8606Spatrick void LiveVariablesImpl::dumpExprLiveness(const SourceManager &M) {
629e5dd7070Spatrick   // Don't iterate over blockEndsToLiveness directly because it's not sorted.
630a9ac8606Spatrick   for (const CFGBlock *B : *analysisContext.getCFG()) {
631e5dd7070Spatrick 
632a9ac8606Spatrick     llvm::errs() << "\n[ B" << B->getBlockID()
633a9ac8606Spatrick                  << " (live expressions at block exit) ]\n";
634a9ac8606Spatrick     for (const Expr *E : blocksEndToLiveness[B].liveExprs) {
635e5dd7070Spatrick       llvm::errs() << "\n";
636a9ac8606Spatrick       E->dump();
637e5dd7070Spatrick     }
638e5dd7070Spatrick     llvm::errs() << "\n";
639e5dd7070Spatrick   }
640e5dd7070Spatrick }
641e5dd7070Spatrick 
getTag()642e5dd7070Spatrick const void *LiveVariables::getTag() { static int x; return &x; }
getTag()643e5dd7070Spatrick const void *RelaxedLiveVariables::getTag() { static int x; return &x; }
644