[clang][dataflow] Add transfer function for VarDecl statements

[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]

Minor changes to names and comments.

[ymandel]

Nice! A few small comments on the headers...

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

57

The term "assignment" is overloaded. :) Maybe instead "Associates Loc with D"? Or, expand on the meaning of the assignment? e.g. "Assigns Loc as the storage location of D?

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

41

here and below. If it never returns null, why not return a ref?
For that matter, all of the pointer parameters with comments "must not be null" -- can we just make those refs?

clang/include/clang/Analysis/FlowSensitive/StorageLocation.h

10

Indent two spaces? (vs 1) same below.

41–43

I don't think its required, but LLVM style typically puts private field decls at the beginning of the class, without the explicit "private:" decl.

53

ref?

84

clang/include/clang/Analysis/FlowSensitive/Value.h

38–39

Move to beginning of class decl?

42

nit: Here and below. I think that "Models..." would be as good or better than "Class that models...".

[sgatev]

Address reviewers' comments.

[sgatev]

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

57

I opted for "Assigns Loc as the storage location of D."

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

41

I replaced the pointers with references where possible.

clang/include/clang/Analysis/FlowSensitive/StorageLocation.h

41–43

Ack. I prefer this order because it puts the public interface higher so the important bits can be found more easily. If this goes against the LLVM coding style I'd be happy to change it, but I prefer to do this separately because I already used this style in some of the other dataflow classes.

53

I believe this needs to accept a pointer to be compatible with operations defined in llvm/Support/Casting.h.

clang/include/clang/Analysis/FlowSensitive/Value.h

38–39

Ack. I'll apply this separately if necessary.

42

Yeap, that's better. Updated all comments.

[sgatev]

Convert pointers to references.

[xazax.hun]

Thanks! I have some questions inline.

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

62

Are other language constructs coming in a follow-up PR? (E.g.: FieldDecl, locations on the heap). I'd like to some TODO comments if that is the case. Or if they are not supported by design, I'd love to some some comments about that.

Environment is referencing ValueDecl as opposed to VarDecl. What is the reason for this asymmetry?
I think I overall find it confusing that some of the DeclToLoc mapping is here some is in the Environment.
Does this has something to do with the fact that certain mappings should be the same regardless of which basic blocks we are processing (i.e., invariant globally so we do not need to duplicate it)? If that is the case please make it clear in the comments.

77

Just curious: would it make sense to deduplicate these values?

clang/include/clang/Analysis/FlowSensitive/Value.h

34

= default;

79

I wonder if getLocation is ambiguous. (The pointer's own location vs the pointee location.) How about something like getPointeeLoc?

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

33

Shouldn't we add operator== instead?

47

I wonder if these algorithms should rather be somewhere in the support library.

89

Could this end up creating an overly large state? There might be objects with quite a lot fields but each function would only access a small subset of those. Alternatively, we could attempt to create the representations for fields on demand (this is the approach what the clang static analyzer is using).

118

I think this function implementation is better to be moved closer to the called initValueInStorageLocationUnlessSelfReferential for readability.

145

Are we planning to track float values in the near future? If not, would it make sense to defer creating these objects until then?

155

Do we want to canonicalize types before inserting into this set?

clang/lib/Analysis/FlowSensitive/Transfer.cpp

34

Maybe add a TODO for int a, b; and similar codes?

42

Instead of using a long if else and dynamic casts, don't we want to use an StmtVisitor instead?

[sgatev]

Address reviewers' comments.

[sgatev]

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

62

Are other language constructs coming in a follow-up PR? (E.g.: FieldDecl, locations on the heap). I'd like to some TODO comments if that is the case. Or if they are not supported by design, I'd love to some some comments about that.

Yes, more is coming in a follow-up. Nothing unsupported by design comes to mind at this point. I added FIXMEs to indicate the language constructs that we plan to implement first, but we will certainly need to add more going forward. Please let me know if there's something in particular that you'd like to see implemented early.

Environment is referencing ValueDecl as opposed to VarDecl. What is the reason for this asymmetry?

This is not intentional. I updated DataflowAnalysisContext to use ValueDecl as well.

I think I overall find it confusing that some of the DeclToLoc mapping is here some is in the Environment.
Does this has something to do with the fact that certain mappings should be the same regardless of which basic blocks we are processing (i.e., invariant globally so we do not need to duplicate it)? If that is the case please make it clear in the comments.

DeclToLoc in Environment holds the set of ValueDecl to StorageLocation assignments that are in scope for a particular basic block. DeclToLoc in DataflowAnalysisContext aggregates the assignments across all basic blocks and is mainly used to produce stable storage locations when the same basic blocks are evaluated multiple times. I added comments in the code explaining this.

77

I think no because even if the values are equal we'd like to track them separately as they represent different identities which is important for inference. For example:

std::optional<int> a = foo();
std::optional<int> b = bar();
std::optional<int> c = a;
// at this point we can model `a`, `b`, and `c` with the same value, however
if (a.has_value()) {
  // here we gain knowledge only about the values of `a` and `c`
  a.value(); // safe
  c.value(); // safe
  b.value(); // unsafe 
}

In our analysis we model the above by assigning the same value to the storage locations for a and c and assigning a different value to the storage location for b, even if the two values are equal.

clang/include/clang/Analysis/FlowSensitive/Value.h

79

That's much better! I also changed the StorageLocation pointer to a reference in the constructor and the getter.

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

33

I'd be happy to do that. Do we need reviews from other folks for it? Would it make sense to move the code to the other location in a follow-up PR, to limit the scope of the change?

47

I'd be happy to do that. Do we need reviews from other folks for it? Would it make sense to move the code to the other location in a follow-up PR, to limit the scope of the change?

89

That's a great point, however I don't think initialization on demand plays well with the dataflow algorithm. For example:

struct S {
  int Val;
};

void target(bool b) {
  // basic block 1:
  S Foo;
  int Bar;
  if (b) {
    // basic block 2:
    Bar = Foo.Val;
  } else {
    // basic block 3:
    Bar = Foo.Val;
  }
  // basic block 4:
  ...
}

In basic block 4 we should be able to infer that the value that is assigned to the storage location for Bar is unambiguous. However, since Foo.Value isn't created in basic block 1, this means that it's not inherited by basic block 2 and basic block 3. Each of these blocks will end up creating distinct values to assign to the storage location for Foo.Value and so in basic block 4 the value for Bar will end up being ambiguous.

Alternatively, we can do a pass over all statements in all basic blocks before running the analysis to identify which fields are used in the function. We can use this information here to initialize only parts that are being used.

What do you think?

145

No immediate plans to track floats. Removed it.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

42

Makes a lot of sense. Replaced it with a ConstStmtVisitor instance.

[sgatev]

Canonicalize types.

[xazax.hun]

I have one nit inline, and some topics that should probably be deferred to follow-up PRs. Overall, looks good to me, thanks!

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

77

I see. This makes sense, thanks!

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

33

Actually, I think DenseMaps should already have operator== so we should be able to remove this code.

47

Yep, I'm fine with moving this in a follow-up PR.

89

I am not convinced about this example. I think it should not matter where and when we create the location for Foo.Val, it always should be equivalent to the others, i.e., they should have the same identity regardless their creation. Basically, I think the identity of such a location should be determined by the base object (Foo in this case), and the access path to the subobject.

This would be a non-trivial change, so I'm ok with deferring this discussion to some follow-up PRs. But I'd love to see some alternatives explored because eagerly evaluating all fields used to bite me in the past in other static analysis tools performance-wise.

[sgatev]

Address reviewers' comments.

[sgatev]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

33

Thanks, I must have missed that. Removed the local implementation.

89

Right. I agree with the comment about storage locations. The issue I see has to do with values that are assigned to the respective storage locations. In general, different values can be assigned to the same storage location in different basic blocks. I don't see a straightforward way to incorporate on-demand initialization while preserving the behavior with respect to values. Perhaps we can achieve this by storing references to parent environments in Environment instead of merging their LocToVal maps when creating environments for successor basic blocks, but this patch is already pretty big so I'd rather defer that. I do agree that this is an important problem we should solve so I added a FIXME to remind us.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

89

The issue I see has to do with values that are assigned to the respective storage locations.

Oh, I see. Generally, Foo.Val could be the initial value (representing the lack of knowledge) in both basic blocks, so merging them would be fine. But we potentially want to assign symbols to the unknown values to be able to describe flow constraints and solve them. So the problem is, we want Foo.Val to evaluate to the same unknown symbol in both basic blocks, so we know the values at Foo.Val are actually the same in those branches.

While it might not be straightforward, I think there are ways around this problem. As far as I understand, from the values' point of view the only problematic case is when we access a value for the first time. We could either derive the unknown symbols from the location to ensure that we initialize Foo.Val to the same symbol in both cases (so the identity of the unknown symbol would describe the fact that this symbols is the initial value for that location). Alternatively, we could have a separate mapping for the initial values and use it to look the right symbol up. The problematic case is the following:

struct S {
  int Val;
};

void invalidate(S&);

void target(bool b) {
  // basic block 1:
  S Foo;
  int Bar;
  if (b) {
    // basic block 2:
    Bar = Foo.Val;
  } else {
    // basic block 3:
    invalidate(S);
    Bar = Foo.Val;
  }
  // basic block 4:
  ...
}

Whatever we come up with, we should ensure that Bar will not have the same value in block 2 and 3 in this case.

Alternatively, we can do a pass over all statements in all basic blocks before running the analysis to identify which fields are used in the function.

This is not an ideal solution. During the fixed-point iteration we might have more information, e.g. we could resolve some of the pointers/references. So in most of the cases creating Locations for fields on demand could be more precise than doing them upfront.

The issue I see has to do with values that are assigned to the respective storage locations.

I agree, we should not block this patch and this is better solved separately.

[sgatev]

Thanks for the reviews!

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

+//===-- DataflowAnalysisContext.h -------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines a DataflowAnalysisContext class that owns objects that
+//  encompass the state of a program and stores context that is used during
+//  dataflow analysis.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
+#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
+
+#include "clang/AST/Decl.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>
+
+namespace clang {
+namespace dataflow {
+
+/// Owns objects that encompass the state of a program and stores additional
+/// context that is used during dataflow analysis.
+class DataflowAnalysisContext {
+public:
+  /// Takes ownership of `Loc` and returns a pointer to it.
+  ///
+  /// Requirements:
+  ///
+  ///  `Loc` must not be null.
+  StorageLocation *takeOwnership(std::unique_ptr<StorageLocation> Loc) {
+    assert(Loc != nullptr);
+    Locs.push_back(std::move(Loc));
+    return Locs.back().get();
+  }
+
+  /// Takes ownership of `Val` and returns a pointer to it.
+  ///
+  /// Requirements:
+  ///
+  ///  `Val` must not be null.
+  Value *takeOwnership(std::unique_ptr<Value> Val) {
+    assert(Val != nullptr);
+    Values.push_back(std::move(Val));
+    return Values.back().get();
+  }
+
+  /// Assigns `Loc` to `D`.
+  ///
+  /// Requirements:
+  ///
+  ///  `D` must not be null.
+  ///
+  ///  `Loc` must not be null.
+  ///
+  ///  `D` must not be assigned a storage location.
+  void setStorageLocation(const VarDecl *D, StorageLocation *Loc) {
+    assert(D != nullptr);
+    assert(Loc != nullptr);
+    assert(VarDeclToLoc.find(D) == VarDeclToLoc.end());
+    VarDeclToLoc[D] = Loc;
+  }
+
+  /// Returns the storage location assigned to `D` or null if `D` has no
+  /// assigned storage location.
+  ///
+  /// Requirements:
+  ///
+  ///  `D` must not be null.
+  StorageLocation *getStorageLocation(const VarDecl *D) const {
+    assert(D != nullptr);
+    auto It = VarDeclToLoc.find(D);
+    return It == VarDeclToLoc.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>> Values;
+  llvm::DenseMap<const VarDecl *, StorageLocation *> VarDeclToLoc;
+};
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H

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

 //  that run over Control-Flow Graphs (CFGs) to keep track of the state of the
 //  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/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 {
 
 /// Holds the state of the program (store and heap) at a given program point.
 class Environment {
 public:
-  bool operator==(const Environment &) const { return true; }
+  Environment(DataflowAnalysisContext &DACtx) : DACtx(&DACtx) {}
 
-  LatticeJoinEffect join(const Environment &) {
-    return LatticeJoinEffect::Unchanged;
-  }
+  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. Never returns null.
+  StorageLocation *createStorageLocation(QualType Type);
+
+  /// Creates a storage location for `Decl`. Does not assign the returned
+  /// storage location to `Decl` in the environment. Does not assign a value
+  /// to the returned storage location in the environment. Never returns null.
+  ///
+  /// Requirements:
+  ///
+  ///  `D` must not be null.
+  StorageLocation *createStorageLocation(const VarDecl *D);
+
+  /// Assigns `Loc` to `D` in the environment.
+  ///
+  /// Requirements:
+  ///
+  ///  `D` must not be null.
+  ///
+  ///  `Loc` must not be null.
+  ///
+  ///  `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.
+  ///
+  /// Requirements:
+  ///
+  ///  `D` must not be null.
+  StorageLocation *getStorageLocation(const ValueDecl *D) const;
+
+  /// Creates a value appropriate for `Type` and assigns it to the given storage
+  /// location. 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:
+  ///
+  ///  `Loc` must not be null.
+  Value *initValueInStorageLocation(const StorageLocation *Loc, QualType Type);
+
+  /// Assigns `Val` to `Loc` in the environment.
+  ///
+  /// Requirements:
+  ///
+  ///  `Loc` must not be null.
+  ///
+  ///  `Val` must not be null.
+  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.
+  ///
+  /// Requirements:
+  ///
+  ///  `Loc` must not be null.
+  Value *getValue(const StorageLocation *Loc) const;
+
+private:
+  /// Recursively initializes storage locations and values unless 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:
+  ///
+  ///  `Loc` must not be null.
+  Value *initValueInStorageLocationUnlessSelfReferential(
+      const StorageLocation *Loc, QualType Type,
+      llvm::DenseSet<QualType> &Visited);
+
+  DataflowAnalysisContext *DACtx;
+  llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
+  llvm::DenseMap<const StorageLocation *, Value *> LocToVal;
 };
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H

clang/include/clang/Analysis/FlowSensitive/StorageLocation.h

+//===-- StorageLocation.h ---------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines classes that represent elements of the local variable store
+// and of the heap during dataflow analysis.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H
+#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H
+
+#include "clang/AST/Decl.h"
+#include "clang/AST/Type.h"
+#include "llvm/ADT/DenseMap.h"
+
+namespace clang {
+namespace dataflow {
+
+/// Base class for elements of the local variable store and of the heap.
+///
+/// Each storage location holds a value. The mapping from storage locations to
+/// values is stored in the environment.
+class StorageLocation {
+public:
+  enum class Kind { Scalar, Aggregate };
+
+  StorageLocation(Kind LocKind, QualType Type) : LocKind(LocKind), Type(Type) {}
+
+  virtual ~StorageLocation() = default;
+
+  Kind getKind() const { return LocKind; }
+
+  QualType getType() const { return Type; }
+
+private:
+  Kind LocKind;
+  QualType Type;
+};
+
+/// A storage location that is not subdivided further for the purposes of
+/// abstract interpretation. For example: `int`, `int*`, `int&`.
+class ScalarStorageLocation final : public StorageLocation {
+public:
+  explicit ScalarStorageLocation(QualType Type)
+      : StorageLocation(Kind::Scalar, Type) {}
+
+  static bool classof(const StorageLocation *Loc) {
+    return Loc->getKind() == Kind::Scalar;
+  }
+};
+
+/// A storage location which is subdivided into smaller storage locations that
+/// can be traced independently by abstract interpretation. For example: a
+/// struct with public members.
+class AggregateStorageLocation final : public StorageLocation {
+public:
+  explicit AggregateStorageLocation(QualType Type)
+      : AggregateStorageLocation(
+            Type, llvm::DenseMap<const ValueDecl *, StorageLocation *>()) {}
+
+  AggregateStorageLocation(
+      QualType Type,
+      llvm::DenseMap<const ValueDecl *, StorageLocation *> Children)
+      : StorageLocation(Kind::Aggregate, Type), Children(std::move(Children)) {}
+
+  static bool classof(const StorageLocation *Loc) {
+    return Loc->getKind() == Kind::Aggregate;
+  }
+
+  /// Returns the child storage location for `D`.
+  ///
+  /// Requirements:
+  ///
+  ///  `D` must not be null.
+  StorageLocation *getChild(const ValueDecl *D) const {
+    assert(D != nullptr);
+    auto It = Children.find(D);
+    // FIXME: A missing child member means that the sorage location was not
+    // created correctly. Change the following to assert(it != children_.end())
+    // once all cases are modeled correctly.
+    if (It == Children.end())
+      return nullptr;
+    return It->second;
+  }
+
+private:
+  llvm::DenseMap<const ValueDecl *, StorageLocation *> Children;
+};
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H

clang/include/clang/Analysis/FlowSensitive/Transfer.h

+//===-- Transfer.h ----------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a transfer function that evaluates a program statement and
+// updates an environment accordingly.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H
+#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H
+
+#include "clang/AST/Stmt.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+
+namespace clang {
+namespace dataflow {
+
+/// Evaluates `S` and updates `Env` accordingly.
+void transfer(const Stmt *S, Environment &Env);
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H

clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h

 //===- TypeErasedDataflowAnalysis.h -----------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines type-erased base types and functions for building dataflow
 //  analyses that run over Control-Flow Graphs (CFGs).
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
 
+#include <utility>
 #include <vector>
 
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Stmt.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"

 
 /// Type-erased model of the program at a given program point.
 struct TypeErasedDataflowAnalysisState {
   /// Type-erased model of a program property.
   TypeErasedLattice Lattice;
 
   /// Model of the state of the program (store and heap).
   Environment Env;
+
+  TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env)
+      : Lattice(std::move(Lattice)), Env(std::move(Env)) {}
 };
 
 /// Transfers the state of a basic block by evaluating each of its statements in
 /// the context of `Analysis` and the states of its predecessors that are
 /// available in `BlockStates`. `HandleTransferredStmt` (if provided) will be
 /// applied to each statement in the block, after it is evaluated.
 ///
 /// Requirements:

clang/include/clang/Analysis/FlowSensitive/Value.h

+//===-- Value.h -------------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines classes for values computed by abstract interpretation
+// during dataflow analysis.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
+#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
+
+#include "clang/AST/Decl.h"
+#include "clang/Analysis/FlowSensitive/StorageLocation.h"
+#include "llvm/ADT/DenseMap.h"
+#include <cassert>
+#include <utility>
+
+namespace clang {
+namespace dataflow {
+
+/// Base class for all values computed by abstract interpretation.
+class Value {
+public:
+  enum class Kind { Integer, Float, Reference, Pointer, Struct };
+
+  explicit Value(Kind ValKind) : ValKind(ValKind) {}
+
+  virtual ~Value() {}
+
+  Kind getKind() const { return ValKind; }
+
+private:
+  Kind ValKind;
+};
+
+/// Class that models an integer.
+class IntegerValue : public Value {
+public:
+  explicit IntegerValue() : Value(Kind::Integer) {}
+
+  static bool classof(const Value *Val) {
+    return Val->getKind() == Kind::Integer;
+  }
+};
+
+/// Class that models a float.
+class FloatValue : public Value {
+public:
+  explicit FloatValue() : Value(Kind::Float) {}
+
+  static bool classof(const Value *Val) {
+    return Val->getKind() == Kind::Float;
+  }
+};
+
+/// Base class for values that refer to storage locations.
+class IndirectionValue : public Value {
+public:
+  /// Constructs a value that refers to `Loc`.
+  ///
+  /// Requirements:
+  ///
+  ///  `Loc` must not be null.
+  explicit IndirectionValue(Kind ValueKind, StorageLocation *Loc)
+      : Value(ValueKind), Loc(Loc) {
+    assert(Loc != nullptr);
+  }
+
+  static bool classof(const Value *Val) {
+    return Val->getKind() == Kind::Reference || Val->getKind() == Kind::Pointer;
+  }
+
+  StorageLocation *getLocation() const { return Loc; }
+
+private:
+  StorageLocation *Loc;
+};
+
+/// Class that models a dereferenced pointer. For example, a reference in C++ or
+/// an lvalue in C.
+class ReferenceValue final : public IndirectionValue {
+public:
+  explicit ReferenceValue(StorageLocation *Loc)
+      : IndirectionValue(Kind::Reference, Loc) {}
+
+  static bool classof(const Value *Val) {
+    return Val->getKind() == Kind::Reference;
+  }
+};
+
+/// Class that models a symbolic pointer. Specifically, any value of type `T*`.
+class PointerValue final : public IndirectionValue {
+public:
+  explicit PointerValue(StorageLocation *Loc)
+      : IndirectionValue(Kind::Pointer, Loc) {}
+
+  static bool classof(const Value *Val) {
+    return Val->getKind() == Kind::Pointer;
+  }
+};
+
+/// Class that models a value of `struct` or `class` type.
+class StructValue final : public Value {
+public:
+  StructValue() : StructValue(llvm::DenseMap<const ValueDecl *, Value *>()) {}
+
+  explicit StructValue(llvm::DenseMap<const ValueDecl *, Value *> Children)
+      : Value(Kind::Struct), Children(std::move(Children)) {}
+
+  static bool classof(const Value *Val) {
+    return Val->getKind() == Kind::Struct;
+  }
+
+  /// Returns the child value for `D`.
+  ///
+  /// Requirements:
+  ///
+  ///  `D` must not be null.
+  Value *getChild(const ValueDecl *D) const {
+    assert(D != nullptr);
+    auto It = Children.find(D);
+    // FIXME: A missing child member means that the value was not created
+    // correctly. Change the following to assert(it != children_.end()) once all
+    // cases are modeled correctly.
+    if (It == Children.end())
+      return nullptr;
+    return It->second;
+  }
+
+private:
+  const llvm::DenseMap<const ValueDecl *, Value *> Children;
+};
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H

clang/lib/Analysis/FlowSensitive/CMakeLists.txt

 add_clang_library(clangAnalysisFlowSensitive
   ControlFlowContext.cpp
+  DataflowEnvironment.cpp
+  Transfer.cpp
   TypeErasedDataflowAnalysis.cpp
 
   LINK_LIBS
   clangAnalysis
   clangAST
   )

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

+//===-- DataflowEnvironment.cpp ---------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines an Environment class that is used by dataflow analyses
+//  that run over Control-Flow Graphs (CFGs) to keep track of the state of the
+//  program at given program points.
+//
+//===----------------------------------------------------------------------===//
+
+#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 <memory>
+
+namespace clang {
+namespace dataflow {
+
+/// Returns true if and only if the given maps contain the same set of keys, and
+/// for each key the values stored in both maps are equal.
+template <typename K, typename V>
+bool denseMapsAreEqual(const llvm::DenseMap<K, V> &Map1,
+                       const llvm::DenseMap<K, V> &Map2) {
+  if (Map1.size() != Map2.size()) {
+    return false;
+  }
+  for (auto &Entry : Map1) {
+    auto It = Map2.find(Entry.first);
+    if (It == Map2.end() || Entry.second != It->second) {
+      return false;
+    }
+  }
+  return true;
+}
+
+/// Returns a map consisting of key-value entries that are present in both maps.
+template <typename K, typename V>
+llvm::DenseMap<K, V> intersectDenseMaps(const llvm::DenseMap<K, V> &Map1,
+                                        const llvm::DenseMap<K, V> &Map2) {
+  llvm::DenseMap<K, V> Result;
+  for (auto &Entry : Map1) {
+    auto It = Map2.find(Entry.first);
+    if (It == Map2.end() || Entry.second != It->second) {
+      continue;
+    }
+    Result.insert({Entry.first, Entry.second});
+  }
+  return Result;
+}
+
+bool Environment::operator==(const Environment &Other) const {
+  assert(DACtx == Other.DACtx);
+  return denseMapsAreEqual(DeclToLoc, Other.DeclToLoc) &&
+         denseMapsAreEqual(LocToVal, Other.LocToVal);
+}
+
+LatticeJoinEffect Environment::join(const Environment &Other) {
+  assert(DACtx == Other.DACtx);
+
+  auto Effect = LatticeJoinEffect::Unchanged;
+
+  const unsigned DeclToLocSizeBefore = DeclToLoc.size();
+  DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc);
+  if (DeclToLocSizeBefore != DeclToLoc.size())
+    Effect = LatticeJoinEffect::Changed;
+
+  const unsigned LocToValSizeBefore = LocToVal.size();
+  LocToVal = intersectDenseMaps(LocToVal, Other.LocToVal);
+  if (LocToValSizeBefore != LocToVal.size())
+    Effect = LatticeJoinEffect::Changed;
+
+  return Effect;
+}
+
+StorageLocation *Environment::createStorageLocation(QualType Type) {
+  if (Type->isStructureOrClassType()) {
+    llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
+    for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) {
+      FieldLocs.insert({Field, createStorageLocation(Field->getType())});
+    }
+    return DACtx->takeOwnership(
+        std::make_unique<AggregateStorageLocation>(Type, std::move(FieldLocs)));
+  }
+  return DACtx->takeOwnership(std::make_unique<ScalarStorageLocation>(Type));
+}
+
+StorageLocation *Environment::createStorageLocation(const VarDecl *D) {
+  assert(D != nullptr);
+  // 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;
+}
+
+void Environment::setStorageLocation(const ValueDecl *D, StorageLocation *Loc) {
+  assert(D != nullptr);
+  assert(Loc != nullptr);
+  assert(DeclToLoc.find(D) == DeclToLoc.end());
+  DeclToLoc[D] = Loc;
+}
+
+StorageLocation *Environment::getStorageLocation(const ValueDecl *D) const {
+  assert(D != nullptr);
+  auto It = DeclToLoc.find(D);
+  return It == DeclToLoc.end() ? nullptr : It->second;
+}
+
+Value *Environment::initValueInStorageLocation(const StorageLocation *Loc,
+                                               QualType Type) {
+  llvm::DenseSet<QualType> Visited;
+  return initValueInStorageLocationUnlessSelfReferential(Loc, Type, Visited);
+}
+
+void Environment::setValue(const StorageLocation *Loc, Value *Value) {
+  assert(Loc != nullptr);
+  assert(Value != nullptr);
+  LocToVal[Loc] = Value;
+}
+
+Value *Environment::getValue(const StorageLocation *Loc) const {
+  assert(Loc != nullptr);
+  auto It = LocToVal.find(Loc);
+  return It == LocToVal.end() ? nullptr : It->second;
+}
+
+Value *Environment::initValueInStorageLocationUnlessSelfReferential(
+    const StorageLocation *Loc, QualType Type,
+    llvm::DenseSet<QualType> &Visited) {
+  assert(Loc != nullptr);
+
+  if (Type->isIntegerType()) {
+    auto *Value = DACtx->takeOwnership(std::make_unique<IntegerValue>());
+    setValue(Loc, Value);
+    return Value;
+  }
+
+  if (Type->isRealFloatingType()) {
+    auto *Value = DACtx->takeOwnership(std::make_unique<FloatValue>());
+    setValue(Loc, Value);
+    return Value;
+  }
+
+  if (Type->isReferenceType()) {
+    QualType PointeeType = Type->getAs<ReferenceType>()->getPointeeType();
+    auto *PointeeLoc = createStorageLocation(PointeeType);
+
+    if (!Visited.contains(PointeeType)) {
+      Visited.insert(PointeeType);
+      initValueInStorageLocationUnlessSelfReferential(PointeeLoc, PointeeType,
+                                                      Visited);
+      Visited.erase(PointeeType);
+    }
+
+    auto *Value =
+        DACtx->takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc));
+    setValue(Loc, Value);
+    return Value;
+  }
+
+  if (Type->isPointerType()) {
+    QualType PointeeType = Type->getAs<PointerType>()->getPointeeType();
+    auto *PointeeLoc = createStorageLocation(PointeeType);
+
+    if (!Visited.contains(PointeeType)) {
+      Visited.insert(PointeeType);
+      initValueInStorageLocationUnlessSelfReferential(PointeeLoc, PointeeType,
+                                                      Visited);
+      Visited.erase(PointeeType);
+    }
+
+    auto *Value =
+        DACtx->takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
+    setValue(Loc, Value);
+    return Value;
+  }
+
+  if (Type->isStructureOrClassType()) {
+    auto *AggregateLoc = cast<AggregateStorageLocation>(Loc);
+
+    llvm::DenseMap<const ValueDecl *, Value *> FieldValues;
+    for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) {
+      QualType FieldType = Field->getType();
+      if (Visited.contains(FieldType))
+        continue;
+
+      Visited.insert(FieldType);
+      FieldValues.insert(
+          {Field, initValueInStorageLocationUnlessSelfReferential(
+                      AggregateLoc->getChild(Field), FieldType, Visited)});
+      Visited.erase(FieldType);
+    }
+
+    auto *Value = DACtx->takeOwnership(
+        std::make_unique<StructValue>(std::move(FieldValues)));
+    setValue(Loc, Value);
+    return Value;
+  }
+
+  return nullptr;
+}
+
+} // namespace dataflow
+} // namespace clang

clang/lib/Analysis/FlowSensitive/Transfer.cpp

+//===-- Transfer.cpp --------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines transfer functions that evaluate program statements and
+// 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/Stmt.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "llvm/Support/Casting.h"
+#include <cassert>
+
+namespace clang {
+namespace dataflow {
+
+static void transferVarDecl(const VarDecl *D, Environment &Env) {
+  auto *Loc = Env.createStorageLocation(D);
+  Env.setStorageLocation(D, Loc);
+  Env.initValueInStorageLocation(Loc, D->getType());
+}
+
+static void transferDeclStmt(const DeclStmt *S, Environment &Env) {
+  if (const auto *D = dyn_cast<VarDecl>(S->getSingleDecl())) {
+    transferVarDecl(D, Env);
+  }
+}
+
+void transfer(const Stmt *S, Environment &Env) {
+  assert(!isa<ParenExpr>(S));
+
+  if (const auto *DS = dyn_cast<DeclStmt>(S)) {
+    transferDeclStmt(DS, Env);
+  }
+}
+
+} // namespace dataflow
+} // namespace clang

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

 
 #include <utility>
 #include <vector>
 
 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
+#include "clang/Analysis/FlowSensitive/Transfer.h"
 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace clang {
 namespace dataflow {
 
 /// Computes the input state for a given basic block by joining the output
 /// states of its predecessors.
 ///
 /// Requirements:
 ///
 ///   All predecessors of `Block` except those with loop back edges must have
 ///   already been transferred. States in `BlockStates` that are set to
 ///   `llvm::None` represent basic blocks that are not evaluated yet.
 static TypeErasedDataflowAnalysisState computeBlockInputState(
     const ControlFlowContext &CFCtx,
     std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
     const CFGBlock &Block, const Environment &InitEnv,
     TypeErasedDataflowAnalysis &Analysis) {
-  // FIXME: Consider passing `Block` to `Analysis.typeErasedInitialElement()`
-  // to enable building analyses like computation of dominators that initialize
-  // the state of each basic block differently.
-  TypeErasedDataflowAnalysisState State = {Analysis.typeErasedInitialElement(),
-                                           InitEnv};
-
   llvm::DenseSet<const CFGBlock *> Preds;
   Preds.insert(Block.pred_begin(), Block.pred_end());
   if (Block.getTerminator().isTemporaryDtorsBranch()) {
     // This handles a special case where the code that produced the CFG includes
     // a conditional operator with a branch that constructs a temporary and
     // calls a destructor annotated as noreturn. The CFG models this as follows:
     //
     // B1 (contains the condition of the conditional operator) - succs: B2, B3
if (Block.getTerminator().isTemporaryDtorsBranch()) {
     // See `NoreturnDestructorTest` for concrete examples.
     if (Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) {
       auto StmtBlock = CFCtx.getStmtToBlock().find(Block.getTerminatorStmt());
       assert(StmtBlock != CFCtx.getStmtToBlock().end());
       Preds.erase(StmtBlock->getSecond());
     }
   }
 
+  llvm::Optional<TypeErasedDataflowAnalysisState> MaybeState;
   for (const CFGBlock *Pred : Preds) {
     // Skip if the `Block` is unreachable or control flow cannot get past it.
     if (!Pred || Pred->hasNoReturnElement())
       continue;
 
     // Skip if `Pred` was not evaluated yet. This could happen if `Pred` has a
     // loop back edge to `Block`.
     const llvm::Optional<TypeErasedDataflowAnalysisState> &MaybePredState =
         BlockStates[Pred->getBlockID()];
     if (!MaybePredState.hasValue())
       continue;
 
     const TypeErasedDataflowAnalysisState &PredState =
         MaybePredState.getValue();
-    Analysis.joinTypeErased(State.Lattice, PredState.Lattice);
-    State.Env.join(PredState.Env);
+    if (MaybeState.hasValue()) {
+      Analysis.joinTypeErased(MaybeState->Lattice, PredState.Lattice);
+      MaybeState->Env.join(PredState.Env);
+    } else {
+      MaybeState = PredState;
     }
-  return State;
+  }
+  if (!MaybeState.hasValue()) {
+    // FIXME: Consider passing `Block` to `Analysis.typeErasedInitialElement()`
+    // to enable building analyses like computation of dominators that
+    // initialize the state of each basic block differently.
+    MaybeState.emplace(Analysis.typeErasedInitialElement(), InitEnv);
+  }
+  return *MaybeState;
 }
 
 TypeErasedDataflowAnalysisState transferBlock(
     const ControlFlowContext &CFCtx,
     std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
     const CFGBlock &Block, const Environment &InitEnv,
     TypeErasedDataflowAnalysis &Analysis,
     std::function<void(const CFGStmt &,
                        const TypeErasedDataflowAnalysisState &)>
         HandleTransferredStmt) {
   TypeErasedDataflowAnalysisState State =
       computeBlockInputState(CFCtx, BlockStates, Block, InitEnv, Analysis);
   for (const CFGElement &Element : Block) {
     // FIXME: Evaluate other kinds of `CFGElement`.
-    const llvm::Optional<CFGStmt> Stmt = Element.getAs<CFGStmt>();
-    if (!Stmt.hasValue())
+    const llvm::Optional<CFGStmt> CfgStmt = Element.getAs<CFGStmt>();
+    if (!CfgStmt.hasValue())
       continue;
 
-    // FIXME: Evaluate the statement contained in `Stmt`.
+    const Stmt *S = CfgStmt.getValue().getStmt();
+    transfer(S, State.Env);
+    State.Lattice = Analysis.transferTypeErased(S, State.Lattice, State.Env);
 
-    State.Lattice = Analysis.transferTypeErased(Stmt.getValue().getStmt(),
-                                                State.Lattice, State.Env);
     if (HandleTransferredStmt != nullptr)
-      HandleTransferredStmt(Stmt.getValue(), State);
+      HandleTransferredStmt(CfgStmt.getValue(), State);
   }
   return State;
 }
 
 std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>
 runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx,
                               TypeErasedDataflowAnalysis &Analysis,
                               const Environment &InitEnv) {

clang/unittests/Analysis/FlowSensitive/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_unittest(ClangAnalysisFlowSensitiveTests
   SingleVarConstantPropagationTest.cpp
   TestingSupport.cpp
   TestingSupportTest.cpp
+  TransferTest.cpp
   TypeErasedDataflowAnalysisTest.cpp
   )
 
 clang_target_link_libraries(ClangAnalysisFlowSensitiveTests
   PRIVATE
   clangAnalysis
   clangAnalysisFlowSensitive
   clangAST

clang/unittests/Analysis/FlowSensitive/NoopAnalysis.h

+//===-- NoopAnalysis.h ------------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines a NoopAnalysis class that is used by dataflow analysis
+//  tests.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_UNITTESTS_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H
+#define LLVM_CLANG_UNITTESTS_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H
+
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Stmt.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include <ostream>
+
+namespace clang {
+namespace dataflow {
+
+class NoopLattice {
+public:
+  bool operator==(const NoopLattice &) const { return true; }
+
+  LatticeJoinEffect join(const NoopLattice &) {
+    return LatticeJoinEffect::Unchanged;
+  }
+};
+
+inline std::ostream &operator<<(std::ostream &OS, const NoopLattice &) {
+  return OS << "noop";
+}
+
+class NoopAnalysis : public DataflowAnalysis<NoopAnalysis, NoopLattice> {
+public:
+  NoopAnalysis(ASTContext &Context)
+      : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context) {}
+
+  static NoopLattice initialElement() { return {}; }
+
+  NoopLattice transfer(const Stmt *S, const NoopLattice &E, Environment &Env) {
+    return {};
+  }
+};
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LLVM_CLANG_UNITTESTS_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H

clang/unittests/Analysis/FlowSensitive/TestingSupport.h

const FunctionDecl *F = ast_matchers::selectFirst<FunctionDecl>(
           ast_matchers::functionDecl(ast_matchers::isDefinition(), FuncMatcher)
               .bind("target"),
           Context));
   ASSERT_TRUE(F != nullptr) << "Could not find target function.";
 
   auto CFCtx = ControlFlowContext::build(F, F->getBody(), &F->getASTContext());
   ASSERT_TRUE((bool)CFCtx) << "Could not build ControlFlowContext.";
 
-  Environment Env;
+  DataflowAnalysisContext DACtx;
+  Environment Env(DACtx);
   auto Analysis = MakeAnalysis(Context, Env);
 
   llvm::Expected<llvm::DenseMap<const clang::Stmt *, std::string>>
       StmtToAnnotations = buildStatementToAnnotationMapping(F, AnnotatedCode);
   if (auto E = StmtToAnnotations.takeError()) {
     FAIL() << "Failed to build annotation map: "
            << llvm::toString(std::move(E));
     return;

clang/unittests/Analysis/FlowSensitive/TestingSupportTest.cpp

 #include "TestingSupport.h"
+#include "NoopAnalysis.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/Tooling/Tooling.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 using namespace clang;
 using namespace dataflow;
 
 namespace {
 
 using ::clang::ast_matchers::functionDecl;
 using ::clang::ast_matchers::hasName;
 using ::clang::ast_matchers::isDefinition;
 using ::testing::_;
 using ::testing::IsEmpty;
 using ::testing::Pair;
 using ::testing::UnorderedElementsAre;
 
-class NoopLattice {
-public:
-  bool operator==(const NoopLattice &) const { return true; }
-
-  LatticeJoinEffect join(const NoopLattice &) {
-    return LatticeJoinEffect::Unchanged;
-  }
-};
-
-std::ostream &operator<<(std::ostream &OS, const NoopLattice &S) {
-  OS << "noop";
-  return OS;
-}
-
-class NoopAnalysis : public DataflowAnalysis<NoopAnalysis, NoopLattice> {
-public:
-  NoopAnalysis(ASTContext &Context)
-      : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context) {}
-
-  static NoopLattice initialElement() { return {}; }
-
-  NoopLattice transfer(const Stmt *S, const NoopLattice &E, Environment &Env) {
-    return {};
-  }
-};
-
 template <typename T>
 const FunctionDecl *findTargetFunc(ASTContext &Context, T FunctionMatcher) {
   auto TargetMatcher =
       functionDecl(FunctionMatcher, isDefinition()).bind("target");
   for (const auto &Node : ast_matchers::match(TargetMatcher, Context)) {
     const auto *Func = Node.template getNodeAs<FunctionDecl>("target");
     if (Func == nullptr)
       continue;

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

+//===- unittests/Analysis/FlowSensitive/TransferTest.cpp ------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "NoopAnalysis.h"
+#include "TestingSupport.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Decl.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/StorageLocation.h"
+#include "clang/Analysis/FlowSensitive/Value.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Casting.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <cassert>
+#include <string>
+#include <utility>
+
+namespace {
+
+using namespace clang;
+using namespace dataflow;
+using ::testing::_;
+using ::testing::ElementsAre;
+using ::testing::IsNull;
+using ::testing::NotNull;
+using ::testing::Pair;
+
+class TransferTest : public ::testing::Test {
+protected:
+  template <typename Matcher>
+  void runDataflow(llvm::StringRef Code, Matcher Match) {
+    test::checkDataflow<NoopAnalysis>(
+        Code, "target",
+        [](ASTContext &C, Environment &) { return NoopAnalysis(C); },
+        [&Match](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) { Match(Results, ASTCtx); },
+        {"-fsyntax-only", "-std=c++17"});
+  }
+};
+
+/// Returns the `ValueDecl` for the given identifier.
+///
+/// Requirements:
+///
+///  `Name` must be unique in `ASTCtx`.
+static const ValueDecl *findValueDecl(ASTContext &ASTCtx,
+                                      llvm::StringRef Name) {
+  auto TargetNodes = ast_matchers::match(
+      ast_matchers::valueDecl(ast_matchers::hasName(Name)).bind("v"), ASTCtx);
+  assert(TargetNodes.size() == 1 && "Name must be unique");
+  auto *const Result = ast_matchers::selectFirst<ValueDecl>("v", TargetNodes);
+  assert(Result != nullptr);
+  return Result;
+}
+
+TEST_F(TransferTest, IntVarDecl) {
+  std::string Code = R"(
+    void target() {
+      int 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 StorageLocation *FooLoc = Env.getStorageLocation(FooDecl);
+                ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
+
+                const Value *FooVal = Env.getValue(FooLoc);
+                ASSERT_TRUE(isa_and_nonnull<IntegerValue>(FooVal));
+              });
+}
+
+TEST_F(TransferTest, FloatVarDecl) {
+  std::string Code = R"(
+    void target() {
+      float foo;
+      // [[p]]
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const auto Env = Results[0].second.Env;
+
+                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo");
+                ASSERT_THAT(FooDecl, NotNull());
+
+                const StorageLocation *FooLoc = Env.getStorageLocation(FooDecl);
+                ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
+
+                const Value *FooVal = Env.getValue(FooLoc);
+                ASSERT_TRUE(isa_and_nonnull<FloatValue>(FooVal));
+              });
+}
+
+TEST_F(TransferTest, DoubleVarDecl) {
+  std::string Code = R"(
+    void target() {
+      double 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 StorageLocation *FooLoc = Env.getStorageLocation(FooDecl);
+                ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
+
+                const Value *FooVal = Env.getValue(FooLoc);
+                ASSERT_TRUE(isa_and_nonnull<FloatValue>(FooVal));
+              });
+}
+
+TEST_F(TransferTest, StructVarDecl) {
+  std::string Code = R"(
+    struct Foo {
+      int Bar;
+      double Baz;
+    };
+
+    void target() {
+      Foo 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());
+
+        ASSERT_TRUE(FooDecl->getType()->isStructureType());
+        auto FooFields = FooDecl->getType()->getAsRecordDecl()->fields();
+
+        FieldDecl *BarDecl = nullptr;
+        FieldDecl *BazDecl = nullptr;
+        for (FieldDecl *Field : FooFields) {
+          if (Field->getNameAsString() == "Bar") {
+            BarDecl = Field;
+          } else if (Field->getNameAsString() == "Baz") {
+            BazDecl = Field;
+          }
+        }
+        ASSERT_THAT(BarDecl, NotNull());
+        ASSERT_THAT(BazDecl, NotNull());
+
+        const auto *FooLoc =
+            cast<AggregateStorageLocation>(Env.getStorageLocation(FooDecl));
+        const auto *BarLoc =
+            cast<ScalarStorageLocation>(FooLoc->getChild(BarDecl));
+        const auto *BazLoc =
+            cast<ScalarStorageLocation>(FooLoc->getChild(BazDecl));
+
+        const auto *FooVal = cast<StructValue>(Env.getValue(FooLoc));
+        const auto *BarVal = cast<IntegerValue>(FooVal->getChild(BarDecl));
+        const auto *BazVal = cast<FloatValue>(FooVal->getChild(BazDecl));
+
+        ASSERT_EQ(Env.getValue(BarLoc), BarVal);
+        ASSERT_EQ(Env.getValue(BazLoc), BazVal);
+      });
+}
+
+TEST_F(TransferTest, ClassVarDecl) {
+  std::string Code = R"(
+    class Foo {
+      int Bar;
+      double Baz;
+    };
+
+    void target() {
+      Foo 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());
+
+        ASSERT_TRUE(FooDecl->getType()->isClassType());
+        auto FooFields = FooDecl->getType()->getAsRecordDecl()->fields();
+
+        FieldDecl *BarDecl = nullptr;
+        FieldDecl *BazDecl = nullptr;
+        for (FieldDecl *Field : FooFields) {
+          if (Field->getNameAsString() == "Bar") {
+            BarDecl = Field;
+          } else if (Field->getNameAsString() == "Baz") {
+            BazDecl = Field;
+          } else {
+            FAIL() << "Unexpected field: " << Field->getNameAsString();
+          }
+        }
+        ASSERT_THAT(BarDecl, NotNull());
+        ASSERT_THAT(BazDecl, NotNull());
+
+        const auto *FooLoc =
+            cast<AggregateStorageLocation>(Env.getStorageLocation(FooDecl));
+        const auto *BarLoc =
+            cast<ScalarStorageLocation>(FooLoc->getChild(BarDecl));
+        const auto *BazLoc =
+            cast<ScalarStorageLocation>(FooLoc->getChild(BazDecl));
+
+        const auto *FooVal = cast<StructValue>(Env.getValue(FooLoc));
+        const auto *BarVal = cast<IntegerValue>(FooVal->getChild(BarDecl));
+        const auto *BazVal = cast<FloatValue>(FooVal->getChild(BazDecl));
+
+        ASSERT_EQ(Env.getValue(BarLoc), BarVal);
+        ASSERT_EQ(Env.getValue(BazLoc), BazVal);
+      });
+}
+
+TEST_F(TransferTest, ReferenceVarDecl) {
+  std::string Code = R"(
+    struct Foo {};
+
+    Foo& getFoo();
+
+    void target() {
+      Foo& foo = getFoo();
+      // [[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 StorageLocation *FooLoc = Env.getStorageLocation(FooDecl);
+        ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
+
+        const ReferenceValue *FooVal =
+            cast<ReferenceValue>(Env.getValue(FooLoc));
+        const StorageLocation *FooPointeeLoc = FooVal->getLocation();
+        ASSERT_TRUE(isa_and_nonnull<AggregateStorageLocation>(FooPointeeLoc));
+
+        const Value *FooPointeeVal = Env.getValue(FooPointeeLoc);
+        ASSERT_TRUE(isa_and_nonnull<StructValue>(FooPointeeVal));
+      });
+}
+
+TEST_F(TransferTest, SelfReferentialReferenceVarDecl) {
+  std::string Code = R"(
+    struct Foo;
+
+    struct Baz {};
+
+    struct Bar {
+      Foo& FooRef;
+      Foo* FooPtr;
+      Baz& BazRef;
+      Baz* BazPtr;
+    };
+
+    struct Foo {
+      Bar& Bar;
+    };
+
+    Foo& getFoo();
+
+    void target() {
+      Foo& foo = getFoo();
+      // [[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());
+
+    ASSERT_TRUE(FooDecl->getType()->isReferenceType());
+    ASSERT_TRUE(FooDecl->getType().getNonReferenceType()->isStructureType());
+    const auto FooFields =
+        FooDecl->getType().getNonReferenceType()->getAsRecordDecl()->fields();
+
+    FieldDecl *BarDecl = nullptr;
+    for (FieldDecl *Field : FooFields) {
+      if (Field->getNameAsString() == "Bar") {
+        BarDecl = Field;
+      } else {
+        FAIL() << "Unexpected field: " << Field->getNameAsString();
+      }
+    }
+    ASSERT_THAT(BarDecl, NotNull());
+
+    ASSERT_TRUE(BarDecl->getType()->isReferenceType());
+    ASSERT_TRUE(BarDecl->getType().getNonReferenceType()->isStructureType());
+    const auto BarFields =
+        BarDecl->getType().getNonReferenceType()->getAsRecordDecl()->fields();
+
+    FieldDecl *FooRefDecl = nullptr;
+    FieldDecl *FooPtrDecl = nullptr;
+    FieldDecl *BazRefDecl = nullptr;
+    FieldDecl *BazPtrDecl = nullptr;
+    for (FieldDecl *Field : BarFields) {
+      if (Field->getNameAsString() == "FooRef") {
+        FooRefDecl = Field;
+      } else if (Field->getNameAsString() == "FooPtr") {
+        FooPtrDecl = Field;
+      } else if (Field->getNameAsString() == "BazRef") {
+        BazRefDecl = Field;
+      } else if (Field->getNameAsString() == "BazPtr") {
+        BazPtrDecl = Field;
+      } else {
+        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 *FooVal = cast<ReferenceValue>(Env.getValue(FooLoc));
+    const auto *FooPointeeVal =
+        cast<StructValue>(Env.getValue(FooVal->getLocation()));
+
+    const auto *BarVal = cast<ReferenceValue>(FooPointeeVal->getChild(BarDecl));
+    const auto *BarPointeeVal =
+        cast<StructValue>(Env.getValue(BarVal->getLocation()));
+
+    const auto *FooRefVal =
+        cast<ReferenceValue>(BarPointeeVal->getChild(FooRefDecl));
+    const StorageLocation *FooRefPointeeLoc = FooRefVal->getLocation();
+    ASSERT_THAT(FooRefPointeeLoc, NotNull());
+    ASSERT_THAT(Env.getValue(FooRefPointeeLoc), IsNull());
+
+    const auto *FooPtrVal =
+        cast<PointerValue>(BarPointeeVal->getChild(FooPtrDecl));
+    const StorageLocation *FooPtrPointeeLoc = FooPtrVal->getLocation();
+    ASSERT_THAT(FooPtrPointeeLoc, NotNull());
+    ASSERT_THAT(Env.getValue(FooPtrPointeeLoc), IsNull());
+
+    const auto *BazRefVal =
+        cast<ReferenceValue>(BarPointeeVal->getChild(BazRefDecl));
+    const StorageLocation *BazRefPointeeLoc = BazRefVal->getLocation();
+    ASSERT_THAT(BazRefPointeeLoc, NotNull());
+    ASSERT_THAT(Env.getValue(BazRefPointeeLoc), NotNull());
+
+    const auto *BazPtrVal =
+        cast<PointerValue>(BarPointeeVal->getChild(BazPtrDecl));
+    const StorageLocation *BazPtrPointeeLoc = BazPtrVal->getLocation();
+    ASSERT_THAT(BazPtrPointeeLoc, NotNull());
+    ASSERT_THAT(Env.getValue(BazPtrPointeeLoc), NotNull());
+  });
+}
+
+TEST_F(TransferTest, PointerVarDecl) {
+  std::string Code = R"(
+    struct Foo {};
+
+    Foo* getFoo();
+
+    void target() {
+      Foo* foo = getFoo();
+      // [[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 StorageLocation *FooLoc = Env.getStorageLocation(FooDecl);
+        ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
+
+        const PointerValue *FooVal = cast<PointerValue>(Env.getValue(FooLoc));
+        const StorageLocation *FooPointeeLoc = FooVal->getLocation();
+        ASSERT_TRUE(isa_and_nonnull<AggregateStorageLocation>(FooPointeeLoc));
+
+        const Value *FooPointeeVal = Env.getValue(FooPointeeLoc);
+        ASSERT_TRUE(isa_and_nonnull<StructValue>(FooPointeeVal));
+      });
+}
+
+TEST_F(TransferTest, SelfReferentialPointerVarDecl) {
+  std::string Code = R"(
+    struct Foo;
+
+    struct Baz {};
+
+    struct Bar {
+      Foo& FooRef;
+      Foo* FooPtr;
+      Baz& BazRef;
+      Baz* BazPtr;
+    };
+
+    struct Foo {
+      Bar* Bar;
+    };
+
+    Foo* getFoo();
+
+    void target() {
+      Foo* foo = getFoo();
+      // [[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());
+
+        ASSERT_TRUE(FooDecl->getType()->isPointerType());
+        ASSERT_TRUE(FooDecl->getType()
+                        ->getAs<PointerType>()
+                        ->getPointeeType()
+                        ->isStructureType());
+        const auto FooFields = FooDecl->getType()
+                                   ->getAs<PointerType>()
+                                   ->getPointeeType()
+                                   ->getAsRecordDecl()
+                                   ->fields();
+
+        FieldDecl *BarDecl = nullptr;
+        for (FieldDecl *Field : FooFields) {
+          if (Field->getNameAsString() == "Bar") {
+            BarDecl = Field;
+          } else {
+            FAIL() << "Unexpected field: " << Field->getNameAsString();
+          }
+        }
+        ASSERT_THAT(BarDecl, NotNull());
+
+        ASSERT_TRUE(BarDecl->getType()->isPointerType());
+        ASSERT_TRUE(BarDecl->getType()
+                        ->getAs<PointerType>()
+                        ->getPointeeType()
+                        ->isStructureType());
+        const auto BarFields = BarDecl->getType()
+                                   ->getAs<PointerType>()
+                                   ->getPointeeType()
+                                   ->getAsRecordDecl()
+                                   ->fields();
+
+        FieldDecl *FooRefDecl = nullptr;
+        FieldDecl *FooPtrDecl = nullptr;
+        FieldDecl *BazRefDecl = nullptr;
+        FieldDecl *BazPtrDecl = nullptr;
+        for (FieldDecl *Field : BarFields) {
+          if (Field->getNameAsString() == "FooRef") {
+            FooRefDecl = Field;
+          } else if (Field->getNameAsString() == "FooPtr") {
+            FooPtrDecl = Field;
+          } else if (Field->getNameAsString() == "BazRef") {
+            BazRefDecl = Field;
+          } else if (Field->getNameAsString() == "BazPtr") {
+            BazPtrDecl = Field;
+          } else {
+            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 *FooVal = cast<PointerValue>(Env.getValue(FooLoc));
+        const auto *FooPointeeVal =
+            cast<StructValue>(Env.getValue(FooVal->getLocation()));
+
+        const auto *BarVal =
+            cast<PointerValue>(FooPointeeVal->getChild(BarDecl));
+        const auto *BarPointeeVal =
+            cast<StructValue>(Env.getValue(BarVal->getLocation()));
+
+        const auto *FooRefVal =
+            cast<ReferenceValue>(BarPointeeVal->getChild(FooRefDecl));
+        const StorageLocation *FooRefPointeeLoc = FooRefVal->getLocation();
+        ASSERT_THAT(FooRefPointeeLoc, NotNull());
+        ASSERT_THAT(Env.getValue(FooRefPointeeLoc), IsNull());
+
+        const auto *FooPtrVal =
+            cast<PointerValue>(BarPointeeVal->getChild(FooPtrDecl));
+        const StorageLocation *FooPtrPointeeLoc = FooPtrVal->getLocation();
+        ASSERT_THAT(FooPtrPointeeLoc, NotNull());
+        ASSERT_THAT(Env.getValue(FooPtrPointeeLoc), IsNull());
+
+        const auto *BazRefVal =
+            cast<ReferenceValue>(BarPointeeVal->getChild(BazRefDecl));
+        const StorageLocation *BazRefPointeeLoc = BazRefVal->getLocation();
+        ASSERT_THAT(BazRefPointeeLoc, NotNull());
+        ASSERT_THAT(Env.getValue(BazRefPointeeLoc), NotNull());
+
+        const auto *BazPtrVal =
+            cast<PointerValue>(BarPointeeVal->getChild(BazPtrDecl));
+        const StorageLocation *BazPtrPointeeLoc = BazPtrVal->getLocation();
+        ASSERT_THAT(BazPtrPointeeLoc, NotNull());
+        ASSERT_THAT(Env.getValue(BazPtrPointeeLoc), NotNull());
+      });
+}
+
+TEST_F(TransferTest, JoinVarDecl) {
+  std::string Code = R"(
+    void target(bool b) {
+      int foo;
+      // [[p1]]
+      if (b) {
+        int bar;
+        // [[p2]]
+      } else {
+        int baz;
+        // [[p3]]
+      }
+      (void)0;
+      // [[p4]]
+    }
+  )";
+  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 Environment &Env2 = Results[2].second.Env;
+        ASSERT_EQ(Env2.getStorageLocation(FooDecl), FooLoc);
+        ASSERT_THAT(Env2.getStorageLocation(BarDecl), NotNull());
+        ASSERT_THAT(Env2.getStorageLocation(BazDecl), 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());
+
+        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());
+      });
+}
+
+} // namespace

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

 //===- unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp ===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
+#include "NoopAnalysis.h"
 #include "TestingSupport.h"
 #include "clang/AST/Decl.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
 #include "clang/Tooling/Tooling.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <cassert>
 #include <memory>
 #include <ostream>
 #include <string>
 #include <utility>
 #include <vector>
 
+namespace {
+
 using namespace clang;
 using namespace dataflow;
 using ::testing::IsEmpty;
 using ::testing::Pair;
 using ::testing::UnorderedElementsAre;
 
 template <typename AnalysisT>
 class AnalysisCallback : public ast_matchers::MatchFinder::MatchCallback {
 public:
   void run(const ast_matchers::MatchFinder::MatchResult &Result) override {
     assert(BlockStates.empty());
 
     const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
     assert(Func != nullptr);
 
     Stmt *Body = Func->getBody();
     assert(Body != nullptr);
 
     auto CFCtx = llvm::cantFail(
         ControlFlowContext::build(nullptr, Body, Result.Context));
 
     AnalysisT Analysis(*Result.Context);
-    Environment Env;
+    DataflowAnalysisContext DACtx;
+    Environment Env(DACtx);
     BlockStates = runDataflowAnalysis(CFCtx, Analysis, Env);
   }
 
   std::vector<
       llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
       BlockStates;
 };
 
 template <typename AnalysisT>
 std::vector<llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
 runAnalysis(llvm::StringRef Code) {
   std::unique_ptr<ASTUnit> AST =
       tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"});
 
   AnalysisCallback<AnalysisT> Callback;
   ast_matchers::MatchFinder Finder;
   Finder.addMatcher(
       ast_matchers::functionDecl(ast_matchers::hasName("target")).bind("func"),
       &Callback);
   Finder.matchAST(AST->getASTContext());
 
   return Callback.BlockStates;
 }
 
-class NoopLattice {
-public:
-  bool operator==(const NoopLattice &) const { return true; }
-
-  LatticeJoinEffect join(const NoopLattice &) {
-    return LatticeJoinEffect::Unchanged;
-  }
-};
-
-class NoopAnalysis : public DataflowAnalysis<NoopAnalysis, NoopLattice> {
-public:
-  NoopAnalysis(ASTContext &Context)
-      : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context) {}
-
-  static NoopLattice initialElement() { return {}; }
-
-  NoopLattice transfer(const Stmt *S, const NoopLattice &E, Environment &Env) {
-    return {};
-  }
-};
-
 TEST(DataflowAnalysisTest, NoopAnalysis) {
   auto BlockStates = runAnalysis<NoopAnalysis>(R"(
     void target() {}
   )");
   EXPECT_EQ(BlockStates.size(), 2u);
   EXPECT_TRUE(BlockStates[0].hasValue());
   EXPECT_TRUE(BlockStates[1].hasValue());
 }
void target(bool b1, bool b2) {
       // [[p]]
     }
   )";
   runDataflow(Code, UnorderedElementsAre(
                         Pair("p", HoldsFunctionCallLattice(HasCalledFunctions(
                                       UnorderedElementsAre("baz", "foo"))))));
   // FIXME: Called functions at point `p` should contain only "foo".
 }
+
+} // namespace