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