[analyzer] Fix liveness calculation for C++17 structured bindings

[george.karpenkov]

Summary

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.
Fortunately, the parent of a BindingDecl, the DecompositionDecl *is* a VarDecl, but it seems there's no direct way to get a pointer from a BindingDecl to a DecompositionDecl.

Applying this patch should be very safe: the behavior for VarDecl's remains the same, the behavior for binding decls would be either fixed, or in the worst case we would say that the variable is always dead.

Note that the patch should not cause crashes even if pre-processing computation fails, as all usages of bindingParentMap are guarded against.

rdar://36912381

[george.karpenkov]

Moreover, LiveVariables.cpp is only used by the analyzer, so it should not affect any other parts of the compiler.

[NoQ]

I guess the interesting part here is what happens if only a but not b is used (or vice versa).

[george.karpenkov]

I guess the interesting part here is what happens if only a but not b is used (or vice versa).

Fixed

[NoQ]

lib/Analysis/LiveVariables.cpp

367–368

I want a comment here. Why can BindingDecl's killability be derived from the parent DecompositionDecl's killability?

test/Analysis/live-bindings-test.cpp

47–51

Could you also add:

int kill_one_binding() {
  auto [a, b] = GetNumbers();
  a = 100;
  return a;
}

(i guess it should warn but it's not too bad if it doesn't)

[george.karpenkov]

Removed parent map.

[NoQ]

LGTM!

test/Analysis/live-bindings-test.cpp

61

Should we, as a FIXME, specify that only 'b' is unused?

[george.karpenkov]

test/Analysis/live-bindings-test.cpp

61

I'm not sure what do you mean; Here both variables are dead?

[NoQ]

test/Analysis/live-bindings-test.cpp

61

Whoops right.

include/clang/Analysis/Analyses/LiveVariables.h

   
 class LiveVariables : public ManagedAnalysis {
 public:
   class LivenessValues {
   public:
 
     llvm::ImmutableSet<const Stmt *> liveStmts;
     llvm::ImmutableSet<const VarDecl *> liveDecls;
+    llvm::ImmutableSet<const BindingDecl *> liveBindings;
     
     bool equals(const LivenessValues &V) const;
 
     LivenessValues()
-      : liveStmts(nullptr), liveDecls(nullptr) {}
+      : liveStmts(nullptr), liveDecls(nullptr), liveBindings(nullptr) {}
 
     LivenessValues(llvm::ImmutableSet<const Stmt *> LiveStmts,
-                   llvm::ImmutableSet<const VarDecl *> LiveDecls)
-      : liveStmts(LiveStmts), liveDecls(LiveDecls) {}
+                   llvm::ImmutableSet<const VarDecl *> LiveDecls,
+                   llvm::ImmutableSet<const BindingDecl *> LiveBindings)
+        : liveStmts(LiveStmts), liveDecls(LiveDecls),
+          liveBindings(LiveBindings) {}
 
     bool isLive(const Stmt *S) const;
     bool isLive(const VarDecl *D) const;
     
     friend class LiveVariables;    
   };
   
   class Observer {

lib/Analysis/LiveVariables.cpp

 }
 
 namespace {
 class LiveVariablesImpl {
 public:  
   AnalysisDeclContext &analysisContext;
   llvm::ImmutableSet<const Stmt *>::Factory SSetFact;
   llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;
+  llvm::ImmutableSet<const BindingDecl *>::Factory BSetFact;
   llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;
   llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;
   llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness;
   llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment;
+
+  // Binding decl does not have a parent pointer to the decomposition decl.
+  // We are adding those in the pre-processing step.
+  llvm::DenseMap<const BindingDecl *, const DecompositionDecl *>
+      bindingParentMap;
   const bool killAtAssign;
   
   LiveVariables::LivenessValues
   merge(LiveVariables::LivenessValues valsA,
         LiveVariables::LivenessValues valsB);
 
   LiveVariables::LivenessValues
   runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val,
              LiveVariables::Observer *obs = nullptr);
 
   void dumpBlockLiveness(const SourceManager& M);
 
   LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign)
     : analysisContext(ac),
       SSetFact(false), // Do not canonicalize ImmutableSets by default.
       DSetFact(false), // This is a *major* performance win.
+      BSetFact(false),
       killAtAssign(KillAtAssign) {}
 };
 }
 
 static LiveVariablesImpl &getImpl(void *x) {
   return *((LiveVariablesImpl *) x);
 }
 
 //===----------------------------------------------------------------------===//
 // Operations and queries on LivenessValues.
 //===----------------------------------------------------------------------===//
 
 bool LiveVariables::LivenessValues::isLive(const Stmt *S) const {
   return liveStmts.contains(S);
 }
 
 bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const {
+  if (const auto *DD = dyn_cast<DecompositionDecl>(D)) {
+    bool alive = false;
+    for (const BindingDecl *BD : DD->bindings())
+      alive |= liveBindings.contains(BD);
+    return alive;
+  }
   return liveDecls.contains(D);
 }
 
 namespace {
   template <typename SET>
   SET mergeSets(SET A, SET B) {
     if (A.isEmpty())
       return B;
llvm::ImmutableSetRef<const Stmt *>
     SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()),
     SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory());
                                                 
   
   llvm::ImmutableSetRef<const VarDecl *>
     DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),
     DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());
   
+  llvm::ImmutableSetRef<const BindingDecl *>
+    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 {
   return liveStmts == V.liveStmts && liveDecls == V.liveDecls;
 }
 
 //===----------------------------------------------------------------------===//
 // Query methods.
void TransferFunctions::Visit(Stmt *S) {
   }
 
   for (Stmt *Child : S->children()) {
     if (Child)
       AddLiveStmt(val.liveStmts, LV.SSetFact, Child);
   }
 }
 
+static bool writeShouldKill(const VarDecl *VD) {
+  return VD && !VD->getType()->isReferenceType() &&
+    !isAlwaysAlive(VD);
+}
+
 void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
   if (B->isAssignmentOp()) {
     if (!LV.killAtAssign)
       return;
     
     // Assigning to a variable?
     Expr *LHS = B->getLHS()->IgnoreParens();
-    
-    if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS))
-      if (const VarDecl *VD = dyn_cast<VarDecl>(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<DeclRefExpr>(LHS)) {
+      const Decl* D = DR->getDecl();
+      bool Killed = false;
+
+      if (const auto *VD = dyn_cast<VarDecl>(D)) {
+        Killed = writeShouldKill(VD);
+        if (Killed)
           val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
-        }
+
+      } else if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) {
+
+        const DecompositionDecl *DD = LV.bindingParentMap[BD];
+        Killed = writeShouldKill(DD);
+        if (Killed)
+          val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
 
-        if (observer)
-          observer->observerKill(DR);
-      }
+      if (Killed && observer)
   }
 }
 
 void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
   for (const VarDecl *VD :
        LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) {
     if (isAlwaysAlive(VD))
       continue;
     val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
   }
 }
 
 void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
-  if (const VarDecl *D = dyn_cast<VarDecl>(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();
+  const auto *VD = dyn_cast<VarDecl>(D);
+  if (const auto *BD = dyn_cast<BindingDecl>(D)) {
+    VD = LV.bindingParentMap[BD];
+  }
+
+  if (VD && !isAlwaysAlive(VD) && !LV.inAssignment[DR]) {
+    val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
+    if (const auto *DD = dyn_cast<DecompositionDecl>(VD))
+      for (const auto *BD : DD->bindings())
+        val.liveBindings = LV.BSetFact.add(val.liveBindings, BD);
+  }
 }
 
 void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
-  for (const auto *DI : DS->decls())
-    if (const auto *VD = dyn_cast<VarDecl>(DI)) {
-      if (!isAlwaysAlive(VD))
-        val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
-    }
+  for (const auto *DI : DS->decls()) {
+    const auto *VD = dyn_cast<VarDecl>(DI);
+    if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) {
+      if (DD->bindings().size() >= 1) {
+        VD = LV.bindingParentMap[DD->bindings()[0]];
+      }
+    }
+
+    if (VD && !isAlwaysAlive(VD)) {
+      if (const auto *DD = dyn_cast<DecompositionDecl>(VD))
+        for (const auto *BD : DD->bindings())
+          val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
+    }
 }
 
 void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
   // Kill the iteration variable.
   DeclRefExpr *DR = nullptr;
   const VarDecl *VD = nullptr;
 
   Stmt *element = OS->getElement();
void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
   default:
     return;
   case UO_PostInc:
   case UO_PostDec:    
   case UO_PreInc:
   case UO_PreDec:
     break;
   }
-  
-  if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens()))
-    if (isa<VarDecl>(DR->getDecl())) {
+  if (auto *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) {
+    const Decl *D = DR->getDecl();
+    if (isa<VarDecl>(D) || isa<BindingDecl>(D)) {
       // Treat ++/-- as a kill.
       observer->observerKill(DR);
     }
   }
+}
 
 LiveVariables::LivenessValues
 LiveVariablesImpl::runOnBlock(const CFGBlock *block,
                               LiveVariables::LivenessValues val,
                               LiveVariables::Observer *obs) {
 
   TransferFunctions TF(*this, val, obs, block);
   
for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
     // FIXME: Scan for DeclRefExprs using in the LHS of an assignment.
     // We need to do this because we lack context in the reverse analysis
     // to determine if a DeclRefExpr appears in such a context, and thus
     // doesn't constitute a "use".
     if (killAtAssign)
       for (CFGBlock::const_iterator bi = block->begin(), be = block->end();
            bi != be; ++bi) {
         if (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) {
-          if (const BinaryOperator *BO =
-                  dyn_cast<BinaryOperator>(cs->getStmt())) {
+          const Stmt* stmt = cs->getStmt();
+          if (const auto *BO = dyn_cast<BinaryOperator>(stmt)) {
             if (BO->getOpcode() == BO_Assign) {
-              if (const DeclRefExpr *DR =
+              if (const auto *DR =
                     dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
                 LV->inAssignment[DR] = 1;
               }
             }
+          } else if (const auto *DS = dyn_cast<DeclStmt>(stmt)) {
+
+            // Pre-construct parent pointers for binding declarations.
+            // Note that all usages of `bindingParentMap` results
+            // should ideally be checked for nullability,
+            // in case preconstruction misses cases.
+            for (const auto *DI : DS->decls()) {
+              if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) {
+                for (BindingDecl *BD : DD->bindings()) {
+                  LV->bindingParentMap[BD] = DD;
+                }
+              }
+            }
           }
         }
       }
   }
   
   while (const CFGBlock *block = worklist.dequeue()) {
     // Determine if the block's end value has changed.  If not, we
     // have nothing left to do for this block.

test/Analysis/live-bindings-test.cpp

+// RUN: %clang_analyze_cc1 -std=c++17 -analyzer-checker=core,deadcode -verify %s
+
+typedef unsigned long size_t;
+
+// Machinery for 
+namespace std {
+template <class T> class tuple_size;
+template <class T>
+ constexpr size_t tuple_size_v = tuple_size<T>::value;
+template <size_t I, class T> class tuple_element;
+
+template<class T, T v>
+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();
+    return a + b; // 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 [a, b] = GetNumbers(); // expected-warning{{Value stored to '[a, b]' during its initialization is never read}}
+    a = 10;
+    b = 20;
+    return a + b;
+}
+
+int kill_one_binding() {
+  auto [a, b] = GetNumbers(); // no-warning
+  a = 100;
+  return a + b;
+}
+
+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 <size_t N>
+  int get() const {
+    if      constexpr (N == 0) return a;
+    else if constexpr (N == 1) return b;
+  }
+};
+
+namespace std {
+    template<>
+    struct tuple_size<Mytuple>
+        : std::integral_constant<size_t, 2> {};
+
+    template<size_t N>
+    struct tuple_element<N, Mytuple> {
+        using type = int;
+    };
+}
+
+void no_warning_on_tuple_types(Mytuple t) {
+  auto [a, b] = t; // no-warning
+}