From 137ca91f52e0eccd866da5f877563d930df30079 Mon Sep 17 00:00:00 2001 From: George Karpenkov Date: Sat, 31 Mar 2018 01:20:06 +0000 Subject: [PATCH] [analyzer] Fix liveness calculation for C++17 structured bindings C++ structured bindings for non-tuple-types are defined in a peculiar way, where the resulting declaration is not a VarDecl, but a BindingDecl. That means a lot of existing machinery stops working. rdar://36912381 Differential Revision: https://reviews.llvm.org/D44956 llvm-svn: 328910 --- .../clang/Analysis/Analyses/LiveVariables.h | 9 +- clang/lib/Analysis/LiveVariables.cpp | 83 ++++++++++---- clang/test/Analysis/live-bindings-test.cpp | 124 +++++++++++++++++++++ 3 files changed, 189 insertions(+), 27 deletions(-) create mode 100644 clang/test/Analysis/live-bindings-test.cpp diff --git a/clang/include/clang/Analysis/Analyses/LiveVariables.h b/clang/include/clang/Analysis/Analyses/LiveVariables.h index 6a12223..21c3ba2 100644 --- a/clang/include/clang/Analysis/Analyses/LiveVariables.h +++ b/clang/include/clang/Analysis/Analyses/LiveVariables.h @@ -33,15 +33,18 @@ public: llvm::ImmutableSet liveStmts; llvm::ImmutableSet liveDecls; + llvm::ImmutableSet liveBindings; bool equals(const LivenessValues &V) const; LivenessValues() - : liveStmts(nullptr), liveDecls(nullptr) {} + : liveStmts(nullptr), liveDecls(nullptr), liveBindings(nullptr) {} LivenessValues(llvm::ImmutableSet LiveStmts, - llvm::ImmutableSet LiveDecls) - : liveStmts(LiveStmts), liveDecls(LiveDecls) {} + llvm::ImmutableSet LiveDecls, + llvm::ImmutableSet LiveBindings) + : liveStmts(LiveStmts), liveDecls(LiveDecls), + liveBindings(LiveBindings) {} bool isLive(const Stmt *S) const; bool isLive(const VarDecl *D) const; diff --git a/clang/lib/Analysis/LiveVariables.cpp b/clang/lib/Analysis/LiveVariables.cpp index f557a74..d03d2a0 100644 --- a/clang/lib/Analysis/LiveVariables.cpp +++ b/clang/lib/Analysis/LiveVariables.cpp @@ -77,6 +77,7 @@ public: AnalysisDeclContext &analysisContext; llvm::ImmutableSet::Factory SSetFact; llvm::ImmutableSet::Factory DSetFact; + llvm::ImmutableSet::Factory BSetFact; llvm::DenseMap blocksEndToLiveness; llvm::DenseMap blocksBeginToLiveness; llvm::DenseMap stmtsToLiveness; @@ -97,6 +98,7 @@ public: : analysisContext(ac), SSetFact(false), // Do not canonicalize ImmutableSets by default. DSetFact(false), // This is a *major* performance win. + BSetFact(false), killAtAssign(KillAtAssign) {} }; } @@ -114,6 +116,12 @@ bool LiveVariables::LivenessValues::isLive(const Stmt *S) const { } bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { + if (const auto *DD = dyn_cast(D)) { + bool alive = false; + for (const BindingDecl *BD : DD->bindings()) + alive |= liveBindings.contains(BD); + return alive; + } return liveDecls.contains(D); } @@ -145,14 +153,19 @@ LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()), DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()); + llvm::ImmutableSetRef + BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()), + BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()); SSetRefA = mergeSets(SSetRefA, SSetRefB); DSetRefA = mergeSets(DSetRefA, DSetRefB); + BSetRefA = mergeSets(BSetRefA, BSetRefB); // asImmutableSet() canonicalizes the tree, allowing us to do an easy // comparison afterwards. return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(), - DSetRefA.asImmutableSet()); + DSetRefA.asImmutableSet(), + BSetRefA.asImmutableSet()); } bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const { @@ -322,6 +335,11 @@ void TransferFunctions::Visit(Stmt *S) { } } +static bool writeShouldKill(const VarDecl *VD) { + return VD && !VD->getType()->isReferenceType() && + !isAlwaysAlive(VD); +} + void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { if (B->isAssignmentOp()) { if (!LV.killAtAssign) @@ -329,21 +347,25 @@ void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { // Assigning to a variable? Expr *LHS = B->getLHS()->IgnoreParens(); - - if (DeclRefExpr *DR = dyn_cast(LHS)) - if (const VarDecl *VD = dyn_cast(DR->getDecl())) { - // Assignments to references don't kill the ref's address - if (VD->getType()->isReferenceType()) - return; - - if (!isAlwaysAlive(VD)) { - // The variable is now dead. + + if (DeclRefExpr *DR = dyn_cast(LHS)) { + const Decl* D = DR->getDecl(); + bool Killed = false; + + if (const BindingDecl* BD = dyn_cast(D)) { + Killed = !BD->getType()->isReferenceType(); + if (Killed) + val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD); + } else if (const auto *VD = dyn_cast(D)) { + Killed = writeShouldKill(VD); + if (Killed) val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); - } - if (observer) - observer->observerKill(DR); } + + if (Killed && observer) + observer->observerKill(DR); + } } } @@ -357,17 +379,28 @@ void TransferFunctions::VisitBlockExpr(BlockExpr *BE) { } void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { - if (const VarDecl *D = dyn_cast(DR->getDecl())) - if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end()) - val.liveDecls = LV.DSetFact.add(val.liveDecls, D); + const Decl* D = DR->getDecl(); + bool InAssignment = LV.inAssignment[DR]; + if (const auto *BD = dyn_cast(D)) { + if (!InAssignment) + val.liveBindings = + LV.BSetFact.add(val.liveBindings, cast(D)); + } else if (const auto *VD = dyn_cast(D)) { + if (!InAssignment && !isAlwaysAlive(VD)) + val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); + } } void TransferFunctions::VisitDeclStmt(DeclStmt *DS) { - for (const auto *DI : DS->decls()) - if (const auto *VD = dyn_cast(DI)) { + for (const auto *DI : DS->decls()) { + if (const auto *DD = dyn_cast(DI)) { + for (const auto *BD : DD->bindings()) + val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD); + } else if (const auto *VD = dyn_cast(DI)) { if (!isAlwaysAlive(VD)) val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); } + } } void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) { @@ -422,12 +455,14 @@ void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) { case UO_PreDec: break; } - - if (DeclRefExpr *DR = dyn_cast(UO->getSubExpr()->IgnoreParens())) - if (isa(DR->getDecl())) { + + if (auto *DR = dyn_cast(UO->getSubExpr()->IgnoreParens())) { + const Decl *D = DR->getDecl(); + if (isa(D) || isa(D)) { // Treat ++/-- as a kill. observer->observerKill(DR); } + } } LiveVariables::LivenessValues @@ -508,10 +543,10 @@ LiveVariables::computeLiveness(AnalysisDeclContext &AC, for (CFGBlock::const_iterator bi = block->begin(), be = block->end(); bi != be; ++bi) { if (Optional cs = bi->getAs()) { - if (const BinaryOperator *BO = - dyn_cast(cs->getStmt())) { + const Stmt* stmt = cs->getStmt(); + if (const auto *BO = dyn_cast(stmt)) { if (BO->getOpcode() == BO_Assign) { - if (const DeclRefExpr *DR = + if (const auto *DR = dyn_cast(BO->getLHS()->IgnoreParens())) { LV->inAssignment[DR] = 1; } diff --git a/clang/test/Analysis/live-bindings-test.cpp b/clang/test/Analysis/live-bindings-test.cpp new file mode 100644 index 0000000..afbb1b3 --- /dev/null +++ b/clang/test/Analysis/live-bindings-test.cpp @@ -0,0 +1,124 @@ +// RUN: %clang_analyze_cc1 -std=c++17 -analyzer-checker=core,deadcode -verify %s + +typedef unsigned long size_t; + +// Machinery required for custom structured bindings decomposition. +namespace std { +template class tuple_size; +template + constexpr size_t tuple_size_v = tuple_size::value; +template class tuple_element; + +template +struct integral_constant { + static constexpr T value = v; + typedef T value_type; + typedef integral_constant type; + constexpr operator value_type() const noexcept { return value; } +}; +} + +struct S { + int a; + double b; + S(int a, double b) : a(a), b(b) {}; +}; + +S GetNumbers(); + +int used_binding() { + const auto [a, b] = GetNumbers(); // no-warning + return a + b; +} + +void no_warning_on_copy(S s) { + // Copy constructor might have side effects. + const auto [a, b] = s; // no-warning +} + + +int unused_binding_ignored() { + const auto [a, b] = GetNumbers(); // expected-warning{{Value stored to '[a, b]' during its initialization is never read}} + return 0; +} + +int unused_binding_liveness_required() { + auto [a2, b2] = GetNumbers(); // expected-warning{{Value stored to '[a2, b2]' during its initialization is never read}} + a2 = 10; + b2 = 20; + return a2 + b2; +} + +int kill_one_binding() { + auto [a, b] = GetNumbers(); // no-warning + a = 100; + return a + b; + +} + +int kill_one_binding2() { + auto [a, b] = GetNumbers(); // expected-warning{{Value stored to '[a, b]' during its initialization is never read}} + a = 100; + return a; +} + +void use_const_reference_bindings() { + const auto &[a, b] = GetNumbers(); // no-warning +} + +void use_reference_bindings() { + S s(0, 0); + auto &[a, b] = s; // no-warning + a = 200; +} + +int read_through_pointer() { + auto [a, b] = GetNumbers(); // no-warning + int *z = &a; + return *z; +} + +auto [globalA, globalB] = GetNumbers(); // no-warning, globals +auto [globalC, globalD] = GetNumbers(); // no-warning, globals + +void use_globals() { + globalA = 300; // no-warning + globalB = 200; +} + +struct Mytuple { + int a; + int b; + + template + int get() const { + if constexpr (N == 0) return a; + else if constexpr (N == 1) return b; + } +}; + +namespace std { + template<> + struct tuple_size + : std::integral_constant {}; + + template + struct tuple_element { + using type = int; + }; +} + +void no_warning_on_tuple_types_copy(Mytuple t) { + auto [a, b] = t; // no-warning +} + +Mytuple getMytuple(); + +void deconstruct_tuple_types_warning() { + auto [a, b] = getMytuple(); // expected-warning{{Value stored to '[a, b]' during its initialization is never read}} +} + +int deconstruct_tuple_types_no_warning() { + auto [a, b] = getMytuple(); // no-warning + return a + b; +} -- 2.7.4