[clang][dataflow] Add transfer functions for assignment

[sgatev]

Summary

This is part of the implementation of the dataflow analysis framework.
See "[RFC] A dataflow analysis framework for Clang AST" on cfe-dev.

[sgatev]

Extend TransferTest.

[xazax.hun]

clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h

34

I am just wondering if this is the right level of abstraction. Maybe users do think of this in terms of skipping references?
Or would they think in terms of value categories? E.g., having getLValue vs getRValue. I think we can leave this as is for now, I just like the idea of exploring alternatives.

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

95

What is the model for expressions that evaluate to different locations in every loop iterations, e.g.:

for(int *p = array; p != array + size; ++p)
  *p; // The dereference expression

Here, having *p always evaluate to the same location is not correct, we'd probably need a way to widen this.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

46

I think you probably also want to set the correct location for the whole expression. Or is that handled somewhere else?

[sgatev]

Address reviewers' comments.

[sgatev]

clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h

34

Absolutely! It makes sense to me to consider this (and other) alternatives so I added a FIXME as a reminder.

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

95

In the current model, the storage location for p is stable and the value that is assigned to it changes. So, in one iteration the value assigned to the storage location for p is val1 which is a PointerValue that points to loc1 and in another iteration the value assigned to the storage location for p is val2 which is a PointerValue that points to loc2. The storage location for *p is also stable and the value that is assigned to it is a ReferenceValue that points to either loc1 or loc2. I implemented this and added a test.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

46

You're right. I updated the code and added a test.

[ymandel]

clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h

36

I'm not sure that value categories are right here. The key is that skipping is optional, unlike value categories which are fixed. I think the problem is just that C++ references are weird (for lack of a technical term). A reference variable exists simultaneously in two different categories -- a pointer and the value it points to. That's what this is trying to capture.

So, I'd recommend just changing the name to reflect that. WDYT of something like this?

/// Indicates how to treat references, if encountered -- as a reference or the value referred to -- when retrieving
/// storage locations or values.
enum class RefTreatment {
   /// Consider the reference itself.
  AsSelf,
  /// Consider the referent.
  AsReferent,
};

113

Why have a SkipPast argument here? I understand the concept for considering var-decls - it corresponds to the weirdness of lvalue-refs themselves. But StorageLocation is a lower-level (and simpler) concept, to which this doesn't seem to map. I'm fine with resolving indirections, but what is the value of only doing so conditionally?

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

242–247

clang/lib/Analysis/FlowSensitive/Transfer.cpp

37

maybe comment as to why this is necessary? I'd have thought that CFG's flattening of expressions would handle this (why, in general, we don't need to look deep into expressions).

143

nit: might be easier to read if you invert this:

const Expr *InitExpr = D.getInit();
if (InitExpr == nullptr) return;

152–153

nit: else-if (one line)?

[xazax.hun]

clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h

36

Yeah, value categories are indeed fixed, I was thinking along the lines of treating expressions as if there was an LValueToRValue or RValueToLValue conversion. I think some of this problem might come from the ambiguity. E.g., when I want to query the analysis state about the value of *p, what do I want? Do I want the value for *p as an lvalue or *p as an rvalue? I would get a different answer in both cases. If I see *p in the source code it is fixed but when I want to query the analysis state it is not.

On the other hand I see that SkipPast is used in the transfer functions, and I am wondering if that is justified. According to the language rules, I can never observe the actual value of the reference. I can modify the pointee, (ref = val) or create a pointer to the same value (&ref), but I cannot actually read or modify what is inside the reference. So I wonder if it might be less error prone if there would be no way in the transfer functions to observe the values of the references either.

But I do not have a strong feeling about any of this at this point so feel free to leave everything as it is.

So, I'd recommend just changing the name to reflect that.

I am not sure how clear Referent is. For a non-native speaker Pointee might be clearer, although I do see how it can be confusing.

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

95

In this case, does it really make sense to materialize this mapping? If every subexpression corresponds to a unique location, and always the same location, we could use the subexpression directly as a location.

[sgatev]

Address reviewers' comments.

[sgatev]

clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h

36

Thanks both! I agree with the comments. I prefer to keep it as is for now. I updated the FIXME with a pointer to this discussion so that we remember to get back to it at some point.

113

You're right. It's not necessary here. Removed it.

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

95

True, but a StorageLocation can also be assigned to a ValueDecl, not only to Expr. We also keep some additional information in the StorageLocation sub-classes so I don't think we can replace it directly.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

37

Added a comment. The CFG does not contain ParenExpr as top-level statements in basic blocks, however sub-expressions can still be of that type.

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h

 //  dataflow analysis.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
 
 #include "clang/AST/Decl.h"
+#include "clang/AST/Expr.h"
 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/DenseMap.h"
 #include <cassert>
 #include <memory>
 #include <utility>
 #include <vector>
 
public:
 
   /// Returns the storage location assigned to `D` or null if `D` has no
   /// assigned storage location.
   StorageLocation *getStorageLocation(const ValueDecl &D) const {
     auto It = DeclToLoc.find(&D);
     return It == DeclToLoc.end() ? nullptr : It->second;
   }
 
+  /// Assigns `Loc` as the storage location of `E`.
+  ///
+  /// Requirements:
+  ///
+  ///  `E` must not be assigned a storage location.
+  void setStorageLocation(const Expr &E, StorageLocation &Loc) {
+    assert(ExprToLoc.find(&E) == ExprToLoc.end());
+    ExprToLoc[&E] = &Loc;
+  }
+
+  /// Returns the storage location assigned to `E` or null if `E` has no
+  /// assigned storage location.
+  StorageLocation *getStorageLocation(const Expr &E) const {
+    auto It = ExprToLoc.find(&E);
+    return It == ExprToLoc.end() ? nullptr : It->second;
+  }
+
 private:
   // Storage for the state of a program.
   std::vector<std::unique_ptr<StorageLocation>> Locs;
   std::vector<std::unique_ptr<Value>> Vals;
 
   // Maps from program declarations and statements to storage locations that are
   // assigned to them. These assignments are global (aggregated across all basic
   // blocks) and are used to produce stable storage locations when the same
   // basic blocks are evaluated multiple times. The storage locations that are
   // in scope for a particular basic block are stored in `Environment`.
   llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
-  // FIXME: Add `Expr` to `StorageLocation` map.
+  llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
 
   // FIXME: Add `StorageLocation` for `this`.
 
   // FIXME: Add support for boolean expressions.
 };
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H

clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h

 //  program at given program points.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
 
 #include "clang/AST/Decl.h"
+#include "clang/AST/Expr.h"
 #include "clang/AST/Type.h"
 #include "clang/AST/TypeOrdering.h"
 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 
 namespace clang {
 namespace dataflow {
 
+/// Indicates what kind of indirections should be skipped past when retrieving
+/// storage locations or values.
+///
+/// FIXME: Consider renaming this or replacing it with a more appropriate model.
+/// See the discussion in https://reviews.llvm.org/D116596 for context.
+enum class SkipPast {
+  /// No indirections should be skipped past.
+  None,
+  /// An optional reference should be skipped past.
+  Reference,
+};
+
 /// Holds the state of the program (store and heap) at a given program point.
 class Environment {
 public:
   Environment(DataflowAnalysisContext &DACtx) : DACtx(&DACtx) {}
 
   bool operator==(const Environment &) const;
 
   LatticeJoinEffect join(const Environment &);
 
   /// Creates a storage location appropriate for `Type`. Does not assign a value
   /// to the returned storage location in the environment.
   ///
   /// Requirements:
   ///
   ///  `Type` must not be null.
   StorageLocation &createStorageLocation(QualType Type);
 
   /// Creates a storage location for `D`. Does not assign the returned storage
   /// location to `D` in the environment. Does not assign a value to the
   /// returned storage location in the environment.
   StorageLocation &createStorageLocation(const VarDecl &D);
 
+  /// Creates a storage location for `E`. Does not assign the returned storage
+  /// location to `E` in the environment. Does not assign a value to the
+  /// returned storage location in the environment.
+  StorageLocation &createStorageLocation(const Expr &E);
+
   /// Assigns `Loc` as the storage location of `D` in the environment.
   ///
   /// Requirements:
   ///
   ///  `D` must not be assigned a storage location in the environment.
   void setStorageLocation(const ValueDecl &D, StorageLocation &Loc);
 
-  /// Returns the storage location assigned to `D` in the environment or null if
-  /// `D` isn't assigned a storage location in the environment.
-  StorageLocation *getStorageLocation(const ValueDecl &D) const;
+  /// Returns the storage location assigned to `D` in the environment, applying
+  /// the `SP` policy for skipping past indirections, or null if `D` isn't
+  /// assigned a storage location in the environment.
+  StorageLocation *getStorageLocation(const ValueDecl &D, SkipPast SP) const;
+
+  /// Assigns `Loc` as the storage location of `E` in the environment.
+  ///
+  /// Requirements:
+  ///
+  ///  `E` must not be assigned a storage location in the environment.
+  void setStorageLocation(const Expr &E, StorageLocation &Loc);
+
+  /// Returns the storage location assigned to `E` in the environment, applying
+  /// the `SP` policy for skipping past indirections, or null if `E` isn't
+  /// assigned a storage location in the environment.
+  StorageLocation *getStorageLocation(const Expr &E, SkipPast SP) const;
 
   /// Creates a value appropriate for `Type`, assigns it to `Loc`, and returns
   /// it, if `Type` is supported, otherwise return null. If `Type` is a pointer
   /// or reference type, creates all the necessary storage locations and values
   /// for indirections until it finds a non-pointer/non-reference type.
   ///
   /// Requirements:
   ///
   ///  `Type` must not be null.
   Value *initValueInStorageLocation(const StorageLocation &Loc, QualType Type);
 
   /// Assigns `Val` as the value of `Loc` in the environment.
   void setValue(const StorageLocation &Loc, Value &Val);
 
   /// Returns the value assigned to `Loc` in the environment or null if `Loc`
   /// isn't assigned a value in the environment.
   Value *getValue(const StorageLocation &Loc) const;
 
+  /// Equivalent to `getValue(getStorageLocation(D, SP), SkipPast::None)` if `D`
+  /// is assigned a storage location in the environment, otherwise returns null.
+  Value *getValue(const ValueDecl &D, SkipPast SP) const;
+
+  /// Equivalent to `getValue(getStorageLocation(E, SP), SkipPast::None)` if `E`
+  /// is assigned a storage location in the environment, otherwise returns null.
+  Value *getValue(const Expr &E, SkipPast SP) const;
+
+  /// Transfers ownership of `Loc` to the analysis context and returns a
+  /// reference to `Loc`.
+  StorageLocation &takeOwnership(std::unique_ptr<StorageLocation> Loc);
+
+  /// Transfers ownership of `Val` to the analysis context and returns a
+  /// reference to `Val`.
+  Value &takeOwnership(std::unique_ptr<Value> Val);
+
 private:
   /// Returns the value assigned to `Loc` in the environment or null if `Type`
   /// isn't supported.
   ///
   /// Recursively initializes storage locations and values until it sees a
   /// self-referential pointer or reference type. `Visited` is used to track
   /// which types appeared in the reference/pointer chain in order to avoid
   /// creating a cyclic dependency with self-referential pointers/references.
   ///
   /// Requirements:
   ///
   ///  `Type` must not be null.
   Value *initValueInStorageLocationUnlessSelfReferential(
       const StorageLocation &Loc, QualType Type,
       llvm::DenseSet<QualType> &Visited);
 
+  StorageLocation &skip(StorageLocation &Loc, SkipPast SP) const;
+  const StorageLocation &skip(const StorageLocation &Loc, SkipPast SP) const;
+
+  // `DACtx` is not null and not owned by this object.
   DataflowAnalysisContext *DACtx;
 
   // Maps from program declarations and statements to storage locations that are
   // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these
   // include only storage locations that are in scope for a particular basic
   // block.
   llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
-  // FIXME: Add `Expr` to `StorageLocation` map.
+  llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
 
   llvm::DenseMap<const StorageLocation *, Value *> LocToVal;
 
   // FIXME: Add flow condition constraints.
 };
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/Type.h"
 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/Support/ErrorHandling.h"
 #include <memory>
 #include <utility>
 
 namespace clang {
 namespace dataflow {
 
 /// Returns a map consisting of key-value entries that are present in both maps.
 template <typename K, typename V>
StorageLocation &Environment::createStorageLocation(QualType Type) {
   assert(!Type.isNull());
   if (Type->isStructureOrClassType()) {
     // FIXME: Explore options to avoid eager initialization of fields as some of
     // them might not be needed for a particular analysis.
     llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
     for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) {
       FieldLocs.insert({Field, &createStorageLocation(Field->getType())});
     }
-    return DACtx->takeOwnership(
+    return takeOwnership(
         std::make_unique<AggregateStorageLocation>(Type, std::move(FieldLocs)));
   }
-  return DACtx->takeOwnership(std::make_unique<ScalarStorageLocation>(Type));
+  return takeOwnership(std::make_unique<ScalarStorageLocation>(Type));
 }
 
 StorageLocation &Environment::createStorageLocation(const VarDecl &D) {
   // Evaluated declarations are always assigned the same storage locations to
   // ensure that the environment stabilizes across loop iterations. Storage
   // locations for evaluated declarations are stored in the analysis context.
   if (auto *Loc = DACtx->getStorageLocation(D))
     return *Loc;
   auto &Loc = createStorageLocation(D.getType());
   DACtx->setStorageLocation(D, Loc);
   return Loc;
 }
 
+StorageLocation &Environment::createStorageLocation(const Expr &E) {
+  // Evaluated expressions are always assigned the same storage locations to
+  // ensure that the environment stabilizes across loop iterations. Storage
+  // locations for evaluated expressions are stored in the analysis context.
+  if (auto *Loc = DACtx->getStorageLocation(E))
+    return *Loc;
+  auto &Loc = createStorageLocation(E.getType());
+  DACtx->setStorageLocation(E, Loc);
+  return Loc;
+}
+
 void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
   assert(DeclToLoc.find(&D) == DeclToLoc.end());
   DeclToLoc[&D] = &Loc;
 }
 
-StorageLocation *Environment::getStorageLocation(const ValueDecl &D) const {
+StorageLocation *Environment::getStorageLocation(const ValueDecl &D,
+                                                 SkipPast SP) const {
   auto It = DeclToLoc.find(&D);
-  return It == DeclToLoc.end() ? nullptr : It->second;
+  return It == DeclToLoc.end() ? nullptr : &skip(*It->second, SP);
+}
+
+void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) {
+  assert(ExprToLoc.find(&E) == ExprToLoc.end());
+  ExprToLoc[&E] = &Loc;
+}
+
+StorageLocation *Environment::getStorageLocation(const Expr &E,
+                                                 SkipPast SP) const {
+  auto It = ExprToLoc.find(&E);
+  return It == ExprToLoc.end() ? nullptr : &skip(*It->second, SP);
 }
 
 void Environment::setValue(const StorageLocation &Loc, Value &Value) {
   LocToVal[&Loc] = &Value;
 }
 
 Value *Environment::getValue(const StorageLocation &Loc) const {
   auto It = LocToVal.find(&Loc);
   return It == LocToVal.end() ? nullptr : It->second;
 }
 
+Value *Environment::getValue(const ValueDecl &D, SkipPast SP) const {
+  auto *Loc = getStorageLocation(D, SP);
+  if (Loc == nullptr)
+    return nullptr;
+  return getValue(*Loc);
+}
+
+Value *Environment::getValue(const Expr &E, SkipPast SP) const {
+  auto *Loc = getStorageLocation(E, SP);
+  if (Loc == nullptr)
+    return nullptr;
+  return getValue(*Loc);
+}
+
 Value *Environment::initValueInStorageLocation(const StorageLocation &Loc,
                                                QualType Type) {
   llvm::DenseSet<QualType> Visited;
   return initValueInStorageLocationUnlessSelfReferential(Loc, Type, Visited);
 }
 
 Value *Environment::initValueInStorageLocationUnlessSelfReferential(
     const StorageLocation &Loc, QualType Type,
     llvm::DenseSet<QualType> &Visited) {
   assert(!Type.isNull());
 
   if (Type->isIntegerType()) {
-    auto &Value = DACtx->takeOwnership(std::make_unique<IntegerValue>());
-    setValue(Loc, Value);
-    return &Value;
+    auto &Val = takeOwnership(std::make_unique<IntegerValue>());
+    setValue(Loc, Val);
+    return &Val;
   }
 
   if (Type->isReferenceType()) {
     QualType PointeeType = Type->getAs<ReferenceType>()->getPointeeType();
     auto &PointeeLoc = createStorageLocation(PointeeType);
 
     if (!Visited.contains(PointeeType.getCanonicalType())) {
       Visited.insert(PointeeType.getCanonicalType());
       initValueInStorageLocationUnlessSelfReferential(PointeeLoc, PointeeType,
                                                       Visited);
       Visited.erase(PointeeType.getCanonicalType());
     }
 
-    auto &Value =
-        DACtx->takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc));
-    setValue(Loc, Value);
-    return &Value;
+    auto &Val = takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc));
+    setValue(Loc, Val);
+    return &Val;
   }
 
   if (Type->isPointerType()) {
     QualType PointeeType = Type->getAs<PointerType>()->getPointeeType();
     auto &PointeeLoc = createStorageLocation(PointeeType);
 
     if (!Visited.contains(PointeeType.getCanonicalType())) {
       Visited.insert(PointeeType.getCanonicalType());
       initValueInStorageLocationUnlessSelfReferential(PointeeLoc, PointeeType,
                                                       Visited);
       Visited.erase(PointeeType.getCanonicalType());
     }
 
-    auto &Value =
-        DACtx->takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
-    setValue(Loc, Value);
-    return &Value;
+    auto &Val = takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
+    setValue(Loc, Val);
+    return &Val;
   }
 
   if (Type->isStructureOrClassType()) {
     auto *AggregateLoc = cast<AggregateStorageLocation>(&Loc);
 
     llvm::DenseMap<const ValueDecl *, Value *> FieldValues;
     for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) {
       assert(Field != nullptr);
 
       QualType FieldType = Field->getType();
       if (Visited.contains(FieldType.getCanonicalType()))
         continue;
 
       Visited.insert(FieldType.getCanonicalType());
       FieldValues.insert(
           {Field, initValueInStorageLocationUnlessSelfReferential(
                       AggregateLoc->getChild(*Field), FieldType, Visited)});
       Visited.erase(FieldType.getCanonicalType());
     }
 
-    auto &Value = DACtx->takeOwnership(
-        std::make_unique<StructValue>(std::move(FieldValues)));
-    setValue(Loc, Value);
-    return &Value;
+    auto &Val =
+        takeOwnership(std::make_unique<StructValue>(std::move(FieldValues)));
+    setValue(Loc, Val);
+    return &Val;
   }
 
   return nullptr;
 }
 
+StorageLocation &
+Environment::takeOwnership(std::unique_ptr<StorageLocation> Loc) {
+  return DACtx->takeOwnership(std::move(Loc));
+}
+
+Value &Environment::takeOwnership(std::unique_ptr<Value> Val) {
+  return DACtx->takeOwnership(std::move(Val));
+}
+
+StorageLocation &Environment::skip(StorageLocation &Loc, SkipPast SP) const {
+  switch (SP) {
+  case SkipPast::None:
+    return Loc;
+  case SkipPast::Reference:
+    // References cannot be chained so we only need to skip past one level of
+    // indirection.
+    if (auto *Val = dyn_cast_or_null<ReferenceValue>(getValue(Loc)))
+      return Val->getPointeeLoc();
+    return Loc;
+  }
+  llvm_unreachable("bad SkipPast kind");
+}
+
+const StorageLocation &Environment::skip(const StorageLocation &Loc,
+                                         SkipPast SP) const {
+  return skip(*const_cast<StorageLocation *>(&Loc), SP);
+}
+
 } // namespace dataflow
 } // namespace clang

clang/lib/Analysis/FlowSensitive/Transfer.cpp

 //  update an environment accordingly.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Analysis/FlowSensitive/Transfer.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/Expr.h"
+#include "clang/AST/OperationKinds.h"
 #include "clang/AST/Stmt.h"
 #include "clang/AST/StmtVisitor.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Basic/OperatorKinds.h"
 #include "llvm/Support/Casting.h"
 #include <cassert>
+#include <memory>
 
 namespace clang {
 namespace dataflow {
 
 class TransferVisitor : public ConstStmtVisitor<TransferVisitor> {
 public:
   TransferVisitor(Environment &Env) : Env(Env) {}
 
+  void VisitBinaryOperator(const BinaryOperator *S) {
+    if (S->getOpcode() == BO_Assign) {
+      // The CFG does not contain `ParenExpr` as top-level statements in basic
+      // blocks, however sub-expressions can still be of that type.
+      assert(S->getLHS() != nullptr);
+      const Expr *LHS = S->getLHS()->IgnoreParens();
+
+      assert(LHS != nullptr);
+      auto *LHSLoc = Env.getStorageLocation(*LHS, SkipPast::Reference);
+      if (LHSLoc == nullptr)
+        return;
+
+      // The CFG does not contain `ParenExpr` as top-level statements in basic
+      // blocks, however sub-expressions can still be of that type.
+      assert(S->getRHS() != nullptr);
+      const Expr *RHS = S->getRHS()->IgnoreParens();
+
+      assert(RHS != nullptr);
+      Value *RHSVal = Env.getValue(*RHS, SkipPast::Reference);
+      if (RHSVal == nullptr)
+        return;
+
+      // Assign a value to the storage location of the left-hand side.
+      Env.setValue(*LHSLoc, *RHSVal);
+
+      // Assign a storage location for the whole expression.
+      Env.setStorageLocation(*S, *LHSLoc);
+    }
+    // FIXME: Add support for BO_EQ, BO_NE.
+  }
+
+  void VisitDeclRefExpr(const DeclRefExpr *S) {
+    assert(S->getDecl() != nullptr);
+    auto *DeclLoc = Env.getStorageLocation(*S->getDecl(), SkipPast::None);
+    if (DeclLoc == nullptr)
+      return;
+
+    if (S->getDecl()->getType()->isReferenceType()) {
+      Env.setStorageLocation(*S, *DeclLoc);
+    } else {
+      auto &Loc = Env.createStorageLocation(*S);
+      auto &Val = Env.takeOwnership(std::make_unique<ReferenceValue>(*DeclLoc));
+      Env.setStorageLocation(*S, Loc);
+      Env.setValue(Loc, Val);
+    }
+  }
+
   void VisitDeclStmt(const DeclStmt *S) {
     // FIXME: Add support for group decls, e.g: `int a, b;`
     if (S->isSingleDecl()) {
       if (const auto *D = dyn_cast<VarDecl>(S->getSingleDecl())) {
         visitVarDecl(*D);
       }
     }
   }
 
+  void VisitImplicitCastExpr(const ImplicitCastExpr *S) {
+    if (S->getCastKind() == CK_LValueToRValue) {
+      // The CFG does not contain `ParenExpr` as top-level statements in basic
+      // blocks, however sub-expressions can still be of that type.
+      assert(S->getSubExpr() != nullptr);
+      const Expr *SubExpr = S->getSubExpr()->IgnoreParens();
+
+      assert(SubExpr != nullptr);
+      auto *SubExprVal = Env.getValue(*SubExpr, SkipPast::Reference);
+      if (SubExprVal == nullptr)
+        return;
+
+      auto &ExprLoc = Env.createStorageLocation(*S);
+      Env.setStorageLocation(*S, ExprLoc);
+      Env.setValue(ExprLoc, *SubExprVal);
+    }
+    // FIXME: Add support for CK_NoOp, CK_UserDefinedConversion,
+    // CK_ConstructorConversion, CK_UncheckedDerivedToBase.
+  }
+
+  void VisitUnaryOperator(const UnaryOperator *S) {
+    if (S->getOpcode() == UO_Deref) {
+      assert(S->getSubExpr() != nullptr);
+      const auto *SubExprVal = cast_or_null<PointerValue>(
+          Env.getValue(*S->getSubExpr(), SkipPast::Reference));
+      if (SubExprVal == nullptr)
+        return;
+
+      auto &Loc = Env.createStorageLocation(*S);
+      Env.setStorageLocation(*S, Loc);
+      Env.setValue(Loc, Env.takeOwnership(std::make_unique<ReferenceValue>(
+                            SubExprVal->getPointeeLoc())));
+    }
+    // FIXME: Add support for UO_AddrOf, UO_LNot.
+  }
+
   // FIXME: Add support for:
-  // - BinaryOperator
   // - CallExpr
   // - CXXBindTemporaryExpr
   // - CXXBoolLiteralExpr
   // - CXXConstructExpr
   // - CXXFunctionalCastExpr
   // - CXXOperatorCallExpr
   // - CXXStaticCastExpr
   // - CXXThisExpr
-  // - DeclRefExpr
-  // - ImplicitCastExpr
   // - MaterializeTemporaryExpr
   // - MemberExpr
-  // - UnaryOperator
 
 private:
   void visitVarDecl(const VarDecl &D) {
     auto &Loc = Env.createStorageLocation(D);
     Env.setStorageLocation(D, Loc);
+
+    const Expr *InitExpr = D.getInit();
+    if (InitExpr == nullptr) {
+      // No initializer expression - associate `Loc` with a new value.
+      Env.initValueInStorageLocation(Loc, D.getType());
+      return;
+    }
+
+    if (D.getType()->isReferenceType()) {
+      // Initializing a reference variable - do not create a reference to
+      // reference.
+      if (auto *InitExprLoc =
+              Env.getStorageLocation(*InitExpr, SkipPast::Reference)) {
+        auto &Val =
+            Env.takeOwnership(std::make_unique<ReferenceValue>(*InitExprLoc));
+        Env.setValue(Loc, Val);
+      } else {
+        // FIXME: The initializer expression must always be assigned a value.
+        // Replace this with an assert when we have sufficient coverage of
+        // language features.
         Env.initValueInStorageLocation(Loc, D.getType());
       }
+      return;
+    }
+
+    if (auto *InitExprVal = Env.getValue(*InitExpr, SkipPast::None)) {
+      Env.setValue(Loc, *InitExprVal);
+    } else {
+      // FIXME: The initializer expression must always be assigned a value.
+      // Replace this with an assert when we have sufficient coverage of
+      // language features.
+      Env.initValueInStorageLocation(Loc, D.getType());
+    }
+  }
 
   Environment &Env;
 };
 
 void transfer(const Stmt &S, Environment &Env) {
   assert(!isa<ParenExpr>(&S));
   TransferVisitor(Env).Visit(&S);
 }
 
 } // namespace dataflow
 } // namespace clang

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(
                    Results,
                ASTContext &ASTCtx) {
         ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
         const Environment &Env = Results[0].second.Env;
 
         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo");
         ASSERT_THAT(FooDecl, NotNull());
 
-        const StorageLocation *FooLoc = Env.getStorageLocation(*FooDecl);
+        const StorageLocation *FooLoc =
+            Env.getStorageLocation(*FooDecl, SkipPast::None);
         ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
 
         const Value *FooVal = Env.getValue(*FooLoc);
         ASSERT_TRUE(isa_and_nonnull<IntegerValue>(FooVal));
       });
 }
 
 TEST_F(TransferTest, StructVarDecl) {
runDataflow(
           if (Field->getNameAsString() == "Bar") {
             BarDecl = Field;
           } else {
             FAIL() << "Unexpected field: " << Field->getNameAsString();
           }
         }
         ASSERT_THAT(BarDecl, NotNull());
 
-        const auto *FooLoc =
-            cast<AggregateStorageLocation>(Env.getStorageLocation(*FooDecl));
+        const auto *FooLoc = cast<AggregateStorageLocation>(
+            Env.getStorageLocation(*FooDecl, SkipPast::None));
         const auto *BarLoc =
             cast<ScalarStorageLocation>(&FooLoc->getChild(*BarDecl));
 
         const auto *FooVal = cast<StructValue>(Env.getValue(*FooLoc));
         const auto *BarVal = cast<IntegerValue>(&FooVal->getChild(*BarDecl));
         ASSERT_EQ(Env.getValue(*BarLoc), BarVal);
       });
 }
runDataflow(
           if (Field->getNameAsString() == "Bar") {
             BarDecl = Field;
           } else {
             FAIL() << "Unexpected field: " << Field->getNameAsString();
           }
         }
         ASSERT_THAT(BarDecl, NotNull());
 
-        const auto *FooLoc =
-            cast<AggregateStorageLocation>(Env.getStorageLocation(*FooDecl));
+        const auto *FooLoc = cast<AggregateStorageLocation>(
+            Env.getStorageLocation(*FooDecl, SkipPast::None));
         const auto *BarLoc =
             cast<ScalarStorageLocation>(&FooLoc->getChild(*BarDecl));
 
         const auto *FooVal = cast<StructValue>(Env.getValue(*FooLoc));
         const auto *BarVal = cast<IntegerValue>(&FooVal->getChild(*BarDecl));
         ASSERT_EQ(Env.getValue(*BarLoc), BarVal);
       });
 }
runDataflow(
                    Results,
                ASTContext &ASTCtx) {
         ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
         const Environment &Env = Results[0].second.Env;
 
         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo");
         ASSERT_THAT(FooDecl, NotNull());
 
-        const StorageLocation *FooLoc = Env.getStorageLocation(*FooDecl);
+        const StorageLocation *FooLoc =
+            Env.getStorageLocation(*FooDecl, SkipPast::None);
         ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
 
         const ReferenceValue *FooVal =
             cast<ReferenceValue>(Env.getValue(*FooLoc));
         const StorageLocation &FooPointeeLoc = FooVal->getPointeeLoc();
         ASSERT_TRUE(isa<AggregateStorageLocation>(&FooPointeeLoc));
 
         const Value *FooPointeeVal = Env.getValue(FooPointeeLoc);
for (FieldDecl *Field : BarFields) {
         FAIL() << "Unexpected field: " << Field->getNameAsString();
       }
     }
     ASSERT_THAT(FooRefDecl, NotNull());
     ASSERT_THAT(FooPtrDecl, NotNull());
     ASSERT_THAT(BazRefDecl, NotNull());
     ASSERT_THAT(BazPtrDecl, NotNull());
 
-    const auto *FooLoc =
-        cast<ScalarStorageLocation>(Env.getStorageLocation(*FooDecl));
+    const auto *FooLoc = cast<ScalarStorageLocation>(
+        Env.getStorageLocation(*FooDecl, SkipPast::None));
     const auto *FooVal = cast<ReferenceValue>(Env.getValue(*FooLoc));
     const auto *FooPointeeVal =
         cast<StructValue>(Env.getValue(FooVal->getPointeeLoc()));
 
     const auto *BarVal =
         cast<ReferenceValue>(&FooPointeeVal->getChild(*BarDecl));
     const auto *BarPointeeVal =
         cast<StructValue>(Env.getValue(BarVal->getPointeeLoc()));
runDataflow(
                    Results,
                ASTContext &ASTCtx) {
         ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
         const Environment &Env = Results[0].second.Env;
 
         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo");
         ASSERT_THAT(FooDecl, NotNull());
 
-        const StorageLocation *FooLoc = Env.getStorageLocation(*FooDecl);
+        const StorageLocation *FooLoc =
+            Env.getStorageLocation(*FooDecl, SkipPast::None);
         ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
 
         const PointerValue *FooVal = cast<PointerValue>(Env.getValue(*FooLoc));
         const StorageLocation &FooPointeeLoc = FooVal->getPointeeLoc();
         ASSERT_TRUE(isa<AggregateStorageLocation>(&FooPointeeLoc));
 
         const Value *FooPointeeVal = Env.getValue(FooPointeeLoc);
         ASSERT_TRUE(isa_and_nonnull<StructValue>(FooPointeeVal));
runDataflow(
             FAIL() << "Unexpected field: " << Field->getNameAsString();
           }
         }
         ASSERT_THAT(FooRefDecl, NotNull());
         ASSERT_THAT(FooPtrDecl, NotNull());
         ASSERT_THAT(BazRefDecl, NotNull());
         ASSERT_THAT(BazPtrDecl, NotNull());
 
-        const auto *FooLoc =
-            cast<ScalarStorageLocation>(Env.getStorageLocation(*FooDecl));
+        const auto *FooLoc = cast<ScalarStorageLocation>(
+            Env.getStorageLocation(*FooDecl, SkipPast::None));
         const auto *FooVal = cast<PointerValue>(Env.getValue(*FooLoc));
         const auto *FooPointeeVal =
             cast<StructValue>(Env.getValue(FooVal->getPointeeLoc()));
 
         const auto *BarVal =
             cast<PointerValue>(&FooPointeeVal->getChild(*BarDecl));
         const auto *BarPointeeVal =
             cast<StructValue>(Env.getValue(BarVal->getPointeeLoc()));
void target(bool b) {
       } else {
         int baz;
         // [[p3]]
       }
       (void)0;
       // [[p4]]
     }
   )";
-  runDataflow(
-      Code, [](llvm::ArrayRef<
-                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+  runDataflow(Code, [](llvm::ArrayRef<std::pair<
+                           std::string, DataflowAnalysisState<NoopLattice>>>
                            Results,
                        ASTContext &ASTCtx) {
-        ASSERT_THAT(Results, ElementsAre(Pair("p4", _), Pair("p3", _),
-                                         Pair("p2", _), Pair("p1", _)));
-        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo");
-        ASSERT_THAT(FooDecl, NotNull());
 
-        const ValueDecl *BarDecl = findValueDecl(ASTCtx, "bar");
-        ASSERT_THAT(BarDecl, NotNull());
 
-        const ValueDecl *BazDecl = findValueDecl(ASTCtx, "baz");
-        ASSERT_THAT(BazDecl, NotNull());
 
-        const Environment &Env1 = Results[3].second.Env;
-        const StorageLocation *FooLoc = Env1.getStorageLocation(*FooDecl);
-        ASSERT_THAT(FooLoc, NotNull());
-        ASSERT_THAT(Env1.getStorageLocation(*BarDecl), IsNull());
-        ASSERT_THAT(Env1.getStorageLocation(*BazDecl), IsNull());
+    const StorageLocation *FooLoc =
+        Env1.getStorageLocation(*FooDecl, SkipPast::None);
+    ASSERT_THAT(Env1.getStorageLocation(*BarDecl, SkipPast::None), IsNull());
+    ASSERT_THAT(Env1.getStorageLocation(*BazDecl, SkipPast::None), IsNull());
 
-        const Environment &Env2 = Results[2].second.Env;
-        ASSERT_EQ(Env2.getStorageLocation(*FooDecl), FooLoc);
-        ASSERT_THAT(Env2.getStorageLocation(*BarDecl), NotNull());
-        ASSERT_THAT(Env2.getStorageLocation(*BazDecl), IsNull());
+    ASSERT_EQ(Env2.getStorageLocation(*FooDecl, SkipPast::None), FooLoc);
+    ASSERT_THAT(Env2.getStorageLocation(*BarDecl, SkipPast::None), NotNull());
+    ASSERT_THAT(Env2.getStorageLocation(*BazDecl, SkipPast::None), IsNull());
 
-        const Environment &Env3 = Results[1].second.Env;
-        ASSERT_EQ(Env3.getStorageLocation(*FooDecl), FooLoc);
-        ASSERT_THAT(Env3.getStorageLocation(*BarDecl), IsNull());
-        ASSERT_THAT(Env3.getStorageLocation(*BazDecl), NotNull());
+    ASSERT_EQ(Env3.getStorageLocation(*FooDecl, SkipPast::None), FooLoc);
+    ASSERT_THAT(Env3.getStorageLocation(*BarDecl, SkipPast::None), IsNull());
+    ASSERT_THAT(Env3.getStorageLocation(*BazDecl, SkipPast::None), NotNull());
 
-        const Environment &Env4 = Results[0].second.Env;
-        ASSERT_EQ(Env4.getStorageLocation(*FooDecl), FooLoc);
-        ASSERT_THAT(Env4.getStorageLocation(*BarDecl), IsNull());
-        ASSERT_THAT(Env4.getStorageLocation(*BazDecl), IsNull());
+    ASSERT_EQ(Env4.getStorageLocation(*FooDecl, SkipPast::None), FooLoc);
+    ASSERT_THAT(Env4.getStorageLocation(*BarDecl, SkipPast::None), IsNull());
+    ASSERT_THAT(Env4.getStorageLocation(*BazDecl, SkipPast::None), IsNull());
+  });
+}
+
+TEST_F(TransferTest, BinaryOperatorAssign) {
+  std::string Code = R"(
+    void target() {
+      int foo;
+      int bar;
+      (bar) = (foo);
+      // [[p]]
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const Environment &Env = Results[0].second.Env;
+
+                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo");
+                ASSERT_THAT(FooDecl, NotNull());
+
+                const Value *FooVal = Env.getValue(*FooDecl, SkipPast::None);
+                ASSERT_TRUE(isa_and_nonnull<IntegerValue>(FooVal));
+
+                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                EXPECT_EQ(Env.getValue(*BarDecl, SkipPast::None), FooVal);
+              });
+}
+
+TEST_F(TransferTest, VarDeclInitAssign) {
+  std::string Code = R"(
+    void target() {
+      int foo;
+      int bar = foo;
+      // [[p]]
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const Environment &Env = Results[0].second.Env;
+
+                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo");
+                ASSERT_THAT(FooDecl, NotNull());
+
+                const Value *FooVal = Env.getValue(*FooDecl, SkipPast::None);
+                ASSERT_TRUE(isa_and_nonnull<IntegerValue>(FooVal));
+
+                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                EXPECT_EQ(Env.getValue(*BarDecl, SkipPast::None), FooVal);
+              });
+}
+
+TEST_F(TransferTest, VarDeclInitAssignChained) {
+  std::string Code = R"(
+    void target() {
+      int foo;
+      int bar;
+      int baz = (bar = foo);
+      // [[p]]
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const Environment &Env = Results[0].second.Env;
+
+                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo");
+                ASSERT_THAT(FooDecl, NotNull());
+
+                const Value *FooVal = Env.getValue(*FooDecl, SkipPast::None);
+                ASSERT_TRUE(isa_and_nonnull<IntegerValue>(FooVal));
+
+                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                const ValueDecl *BazDecl = findValueDecl(ASTCtx, "baz");
+                ASSERT_THAT(BazDecl, NotNull());
+
+                EXPECT_EQ(Env.getValue(*BarDecl, SkipPast::None), FooVal);
+                EXPECT_EQ(Env.getValue(*BazDecl, SkipPast::None), FooVal);
+              });
+}
+
+TEST_F(TransferTest, VarDeclInitAssignPtrDeref) {
+  std::string Code = R"(
+    void target() {
+      int foo;
+      int *bar;
+      *(bar) = foo;
+      int baz = *(bar);
+      // [[p]]
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const Environment &Env = Results[0].second.Env;
+
+                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo");
+                ASSERT_THAT(FooDecl, NotNull());
+
+                const Value *FooVal = Env.getValue(*FooDecl, SkipPast::None);
+                ASSERT_TRUE(isa_and_nonnull<IntegerValue>(FooVal));
+
+                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                const auto *BarVal =
+                    cast<PointerValue>(Env.getValue(*BarDecl, SkipPast::None));
+                EXPECT_EQ(Env.getValue(BarVal->getPointeeLoc()), FooVal);
+
+                const ValueDecl *BazDecl = findValueDecl(ASTCtx, "baz");
+                ASSERT_THAT(BazDecl, NotNull());
+
+                EXPECT_EQ(Env.getValue(*BazDecl, SkipPast::None), FooVal);
+              });
+}
+
+TEST_F(TransferTest, AssignToAndFromReference) {
+  std::string Code = R"(
+    void target() {
+      int foo;
+      int bar;
+      int& baz = foo;
+      // [[p1]]
+      baz = bar;
+      int qux = baz;
+      int& quux = baz;
+      // [[p2]]
+    }
+  )";
+  runDataflow(
+      Code, [](llvm::ArrayRef<
+                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                   Results,
+               ASTContext &ASTCtx) {
+        ASSERT_THAT(Results, ElementsAre(Pair("p1", _), Pair("p2", _)));
+        const Environment &Env1 = Results[0].second.Env;
+        const Environment &Env2 = Results[1].second.Env;
+
+        const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo");
+        ASSERT_THAT(FooDecl, NotNull());
+
+        const Value *FooVal = Env1.getValue(*FooDecl, SkipPast::None);
+        ASSERT_TRUE(isa_and_nonnull<IntegerValue>(FooVal));
+
+        const ValueDecl *BarDecl = findValueDecl(ASTCtx, "bar");
+        ASSERT_THAT(BarDecl, NotNull());
+
+        const Value *BarVal = Env1.getValue(*BarDecl, SkipPast::None);
+        ASSERT_TRUE(isa_and_nonnull<IntegerValue>(BarVal));
+
+        const ValueDecl *BazDecl = findValueDecl(ASTCtx, "baz");
+        ASSERT_THAT(BazDecl, NotNull());
+
+        EXPECT_EQ(Env1.getValue(*BazDecl, SkipPast::Reference), FooVal);
+
+        EXPECT_EQ(Env2.getValue(*BazDecl, SkipPast::Reference), BarVal);
+        EXPECT_EQ(Env2.getValue(*FooDecl, SkipPast::None), BarVal);
+
+        const ValueDecl *QuxDecl = findValueDecl(ASTCtx, "qux");
+        ASSERT_THAT(QuxDecl, NotNull());
+        EXPECT_EQ(Env2.getValue(*QuxDecl, SkipPast::None), BarVal);
+
+        const ValueDecl *QuuxDecl = findValueDecl(ASTCtx, "quux");
+        ASSERT_THAT(QuuxDecl, NotNull());
+        EXPECT_EQ(Env2.getValue(*QuuxDecl, SkipPast::Reference), BarVal);
       });
 }
 
 } // namespace