[clang][dataflow] Enable comparison of distinct values in Environment

[sgatev]

Summary

Make specializations of DataflowAnalysis extendable with domain-specific
logic for comparing distinct values when comparing environments.

This includes a breaking change to the runDataflowAnalysis interface
as the return type is now llvm::Expected<...>.

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

[sgatev]

Reformat code.

[ymandel]

Please mention the (breaking) API changes to runDataflowAnalysis, etc. in the patch description.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

155–156

Now we have multiple, slightly different versions of equality for values. One here, one in Environment::equivalentTo. I'd prefer to have one way to check value equality factored out somewhere and reused it both here and there. Also, Environment::equivalentTo works with any indirection, this snippet only works with pointers (and not with references).

It is also not clear to me at this point what is the role of compareEquivalent. Is it intentional that it is not used here?

[sgatev]

Address reviewers' comments.

[sgatev]

Update comment.

[sgatev]

Mentioned the breaking interface change in the description.

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

155–156

Good point, I updated the code. Please take a look.

[sgatev]

Update comment.

[xazax.hun]

Thanks, this looks much better!

[ymandel]

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

56

I really like this new name/API. Much clearer concept.

64

What does this comment mean, now that there's no environment? Could we say something specific to the values themselves?

[sgatev]

Address reviewers' comments.

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

64

Updated the comment and added a FIXME to consider removing the type argument.

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.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/TypeErasedDataflowAnalysis.h"
 #include "llvm/ADT/Any.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Error.h"
 
 namespace clang {
 namespace dataflow {
 
 /// Base class template for dataflow analyses built on a single lattice type.
 ///
 /// Requirements:
 ///
template <typename LatticeT> struct DataflowAnalysisState {
   LatticeT Lattice;
 
   // Model of the state of the program (store and heap).
   Environment Env;
 };
 
 /// Performs dataflow analysis and returns a mapping from basic block IDs to
 /// dataflow analysis states that model the respective basic blocks. Indices
-/// of the returned vector correspond to basic block IDs.
+/// of the returned vector correspond to basic block IDs. Returns an error if
+/// the dataflow analysis cannot be performed successfully.
 template <typename AnalysisT>
-std::vector<llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
+llvm::Expected<std::vector<
+    llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
 runDataflowAnalysis(const ControlFlowContext &CFCtx, AnalysisT &Analysis,
                     const Environment &InitEnv) {
   auto TypeErasedBlockStates =
       runTypeErasedDataflowAnalysis(CFCtx, Analysis, InitEnv);
+  if (!TypeErasedBlockStates)
+    return TypeErasedBlockStates.takeError();
+
   std::vector<
       llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
       BlockStates;
-  BlockStates.reserve(TypeErasedBlockStates.size());
-  llvm::transform(std::move(TypeErasedBlockStates),
+  BlockStates.reserve(TypeErasedBlockStates->size());
+
+  llvm::transform(std::move(*TypeErasedBlockStates),
                   std::back_inserter(BlockStates), [](auto &OptState) {
                     return std::move(OptState).map([](auto &&State) {
                       return DataflowAnalysisState<typename AnalysisT::Lattice>{
                           llvm::any_cast<typename AnalysisT::Lattice>(
                               std::move(State.Lattice.Value)),
                           std::move(State.Env)};
                     });
                   });
   return BlockStates;
 }
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H

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

enum class SkipPast {
   /// An optional reference should be skipped past, then an optional pointer
   /// should be skipped past.
   ReferenceThenPointer,
 };
 
 /// Holds the state of the program (store and heap) at a given program point.
 class Environment {
 public:
-  /// Supplements `Environment` with non-standard join operations.
-  class Merger {
+  /// Supplements `Environment` with non-standard comparison and join
+  /// operations.
+  class ValueModel {
   public:
-    virtual ~Merger() = default;
+    virtual ~ValueModel() = default;
 
-    /// Given distinct `Val1` and `Val2`, modifies `MergedVal` to approximate
-    /// both `Val1` and `Val2`. This could be a strict lattice join or a more
-    /// general widening operation. If this function returns true, `MergedVal`
-    /// will be assigned to a storage location of type `Type` in `Env`.
+    /// Returns true if and only if `Val1` is equivalent to `Val2`.
     ///
     /// Requirements:
     ///
     ///  `Val1` and `Val2` must be distinct.
+    ///
+    ///  `Val1` and `Val2` must model values of type `Type`.
+    virtual bool compareEquivalent(QualType Type, const Value &Val1,
+                                   const Value &Val2) {
+      // FIXME: Consider adding QualType to StructValue and removing the Type
+      // argument here.
+      return false;
+    }
+
+    /// Modifies `MergedVal` to approximate both `Val1` and `Val2`. This could
+    /// be a strict lattice join or a more general widening operation. If this
+    /// function returns true, `MergedVal` will be assigned to a storage
+    /// location of type `Type` in `Env`.
+    ///
+    /// Requirements:
+    ///
+    ///  `Val1` and `Val2` must be distinct.
+    ///
+    ///  `Val1`, `Val2`, and `MergedVal` must model values of type `Type`.
     virtual bool merge(QualType Type, const Value &Val1, const Value &Val2,
                        Value &MergedVal, Environment &Env) {
       return false;
     }
   };
 
   /// Creates an environment that uses `DACtx` to store objects that encompass
   /// the state of a program.
   explicit Environment(DataflowAnalysisContext &DACtx) : DACtx(&DACtx) {}
 
   /// Creates an environment that uses `DACtx` to store objects that encompass
   /// the state of a program.
   ///
   /// If `DeclCtx` is a function, initializes the environment with symbolic
   /// representations of the function parameters.
   ///
   /// If `DeclCtx` is a non-static member function, initializes the environment
   /// with a symbolic representation of the `this` pointee.
   Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx);
 
-  bool operator==(const Environment &) const;
-
-  LatticeJoinEffect join(const Environment &, Environment::Merger &);
+  /// Returns true if and only if the environment is equivalent to `Other`, i.e
+  /// the two environments:
+  ///  - have the same mappings from declarations to storage locations,
+  ///  - have the same mappings from expressions to storage locations,
+  ///  - have the same or equivalent (according to `Model`) values assigned to
+  ///    the same storage locations.
+  ///
+  /// Requirements:
+  ///
+  ///  `Other` and `this` must use the same `DataflowAnalysisContext`.
+  bool equivalentTo(const Environment &Other,
+                    Environment::ValueModel &Model) const;
+
+  /// Joins the environment with `Other` by taking the intersection of storage
+  /// locations and values that are stored in them. Distinct values that are
+  /// assigned to the same storage locations in the environment and `Other` are
+  /// merged using `Model`.
+  ///
+  /// Requirements:
+  ///
+  ///  `Other` and `this` must use the same `DataflowAnalysisContext`.
+  LatticeJoinEffect join(const Environment &Other,
+                         Environment::ValueModel &Model);
 
   // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`,
   // `getStableStorageLocation`, or something more appropriate.
 
   /// Creates a storage location appropriate for `Type`. Does not assign a value
   /// to the returned storage location in the environment.
   ///
   /// Requirements:

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

 #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"
 #include "llvm/ADT/Any.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/Support/Error.h"
 
 namespace clang {
 namespace dataflow {
 
 /// Type-erased lattice element container.
 ///
 /// Requirements:
 ///
 ///  The type of the object stored in the container must be a bounded
 ///  join-semilattice.
 struct TypeErasedLattice {
   llvm::Any Value;
 };
 
 /// Type-erased base class for dataflow analyses built on a single lattice type.
-class TypeErasedDataflowAnalysis : public Environment::Merger {
+class TypeErasedDataflowAnalysis : public Environment::ValueModel {
   /// Determines whether to apply the built-in transfer functions.
   // FIXME: Remove this option once the framework supports composing analyses
   // (at which point the built-in transfer functions can be simply a standalone
   // analysis).
   bool ApplyBuiltinTransfer;
 
 public:
   TypeErasedDataflowAnalysis() : ApplyBuiltinTransfer(true) {}
TypeErasedDataflowAnalysisState transferBlock(
     const CFGBlock &Block, const Environment &InitEnv,
     TypeErasedDataflowAnalysis &Analysis,
     std::function<void(const CFGStmt &,
                        const TypeErasedDataflowAnalysisState &)>
         HandleTransferredStmt = nullptr);
 
 /// Performs dataflow analysis and returns a mapping from basic block IDs to
 /// dataflow analysis states that model the respective basic blocks. Indices
-/// of the returned vector correspond to basic block IDs.
-std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>
+/// of the returned vector correspond to basic block IDs. Returns an error if
+/// the dataflow analysis cannot be performed successfully.
+llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>>
 runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx,
                               TypeErasedDataflowAnalysis &Analysis,
                               const Environment &InitEnv);
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

llvm::DenseMap<K, V> intersectDenseMaps(const llvm::DenseMap<K, V> &Map1,
   for (auto &Entry : Map1) {
     auto It = Map2.find(Entry.first);
     if (It != Map2.end() && Entry.second == It->second)
       Result.insert({Entry.first, Entry.second});
   }
   return Result;
 }
 
+/// Returns true if and only if `Val1` is equivalent to `Val2`.
+static bool equivalentValues(QualType Type, Value *Val1, Value *Val2,
+                             Environment::ValueModel &Model) {
+  if (Val1 == Val2)
+    return true;
+
+  if (auto *IndVal1 = dyn_cast<IndirectionValue>(Val1)) {
+    auto *IndVal2 = cast<IndirectionValue>(Val2);
+    assert(IndVal1->getKind() == IndVal2->getKind());
+    return &IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc();
+  }
+
+  return Model.compareEquivalent(Type, *Val1, *Val2);
+}
+
 Environment::Environment(DataflowAnalysisContext &DACtx,
                          const DeclContext &DeclCtx)
     : Environment(DACtx) {
   if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
     for (const auto *ParamDecl : FuncDecl->parameters()) {
       assert(ParamDecl != nullptr);
       auto &ParamLoc = createStorageLocation(*ParamDecl);
       setStorageLocation(*ParamDecl, ParamLoc);
if (!MethodDecl->isStatic()) {
         DACtx.setThisPointeeStorageLocation(ThisPointeeLoc);
         if (Value *ThisPointeeVal = createValue(ThisPointeeType))
           setValue(ThisPointeeLoc, *ThisPointeeVal);
       }
     }
   }
 }
 
-bool Environment::operator==(const Environment &Other) const {
+bool Environment::equivalentTo(const Environment &Other,
+                               Environment::ValueModel &Model) const {
   assert(DACtx == Other.DACtx);
-  return DeclToLoc == Other.DeclToLoc && LocToVal == Other.LocToVal;
+
+  if (DeclToLoc != Other.DeclToLoc)
+    return false;
+
+  if (ExprToLoc != Other.ExprToLoc)
+    return false;
+
+  if (LocToVal.size() != Other.LocToVal.size())
+    return false;
+
+  for (auto &Entry : LocToVal) {
+    const StorageLocation *Loc = Entry.first;
+    assert(Loc != nullptr);
+
+    Value *Val = Entry.second;
+    assert(Val != nullptr);
+
+    auto It = Other.LocToVal.find(Loc);
+    if (It == Other.LocToVal.end())
+      return false;
+    assert(It->second != nullptr);
+
+    if (!equivalentValues(Loc->getType(), Val, It->second, Model))
+      return false;
+  }
+
+  return true;
 }
 
 LatticeJoinEffect Environment::join(const Environment &Other,
-                                    Environment::Merger &Merger) {
+                                    Environment::ValueModel &Model) {
   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 ExprToLocSizeBefore = ExprToLoc.size();
   ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc);
   if (ExprToLocSizeBefore != ExprToLoc.size())
     Effect = LatticeJoinEffect::Changed;
 
-  // Move `LocToVal` so that `Environment::Merger::merge` can safely assign
+  // Move `LocToVal` so that `Environment::ValueModel::merge` can safely assign
   // values to storage locations while this code iterates over the current
   // assignments.
   llvm::DenseMap<const StorageLocation *, Value *> OldLocToVal =
       std::move(LocToVal);
   for (auto &Entry : OldLocToVal) {
     const StorageLocation *Loc = Entry.first;
     assert(Loc != nullptr);
 
     Value *Val = Entry.second;
     assert(Val != nullptr);
 
     auto It = Other.LocToVal.find(Loc);
     if (It == Other.LocToVal.end())
       continue;
     assert(It->second != nullptr);
 
-    if (It->second == Val) {
+    if (equivalentValues(Loc->getType(), Val, It->second, Model)) {
       LocToVal.insert({Loc, Val});
       continue;
     }
 
-    if (auto *FirstVal = dyn_cast<PointerValue>(Val)) {
-      auto *SecondVal = cast<PointerValue>(It->second);
-      if (&FirstVal->getPointeeLoc() == &SecondVal->getPointeeLoc()) {
-        LocToVal.insert({Loc, FirstVal});
-        continue;
-      }
-    }
-
-    // FIXME: Consider destroying `MergedValue` immediately if `Merger::merge`
-    // returns false to avoid storing unneeded values in `DACtx`.
+    // FIXME: Consider destroying `MergedValue` immediately if
+    // `ValueModel::merge` returns false to avoid storing unneeded values in
+    // `DACtx`.
     if (Value *MergedVal = createValue(Loc->getType()))
-      if (Merger.merge(Loc->getType(), *Val, *It->second, *MergedVal, *this))
+      if (Model.merge(Loc->getType(), *Val, *It->second, *MergedVal, *this))
         LocToVal.insert({Loc, MergedVal});
   }
   if (OldLocToVal.size() != LocToVal.size())
     Effect = LatticeJoinEffect::Changed;
 
   return Effect;
 }
 

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

 //===- TypeErasedDataflowAnalysis.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
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines type-erased base types and functions for building dataflow
 //  analyses that run over Control-Flow Graphs (CFGs).
 //
 //===----------------------------------------------------------------------===//
 
 #include <memory>
+#include <system_error>
 #include <utility>
 #include <vector>
 
 #include "clang/AST/DeclCXX.h"
 #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 "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
-#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/Error.h"
 
 namespace clang {
 namespace dataflow {
 
 /// Computes the input state for a given basic block by joining the output
 /// states of its predecessors.
 ///
 /// Requirements:
for (const CFGElement &Element : Block) {
     default:
       // FIXME: Evaluate other kinds of `CFGElement`.
       break;
     }
   }
   return State;
 }
 
-std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>
+llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>>
 runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx,
                               TypeErasedDataflowAnalysis &Analysis,
                               const Environment &InitEnv) {
   PostOrderCFGView POV(&CFCtx.getCFG());
   ForwardDataflowWorklist Worklist(CFCtx.getCFG(), &POV);
 
   std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> BlockStates;
   BlockStates.resize(CFCtx.getCFG().size(), llvm::None);
runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx,
   // limit the number of iterations.
   // FIXME: Consider making the maximum number of iterations configurable.
   // FIXME: Set up statistics (see llvm/ADT/Statistic.h) to count average number
   // of iterations, number of functions that time out, etc.
   uint32_t Iterations = 0;
   static constexpr uint32_t MaxIterations = 1 << 16;
   while (const CFGBlock *Block = Worklist.dequeue()) {
     if (++Iterations > MaxIterations) {
-      llvm::errs() << "Maximum number of iterations reached, giving up.\n";
-      break;
+      return llvm::createStringError(std::errc::timed_out,
+                                     "maximum number of iterations reached");
     }
 
     const llvm::Optional<TypeErasedDataflowAnalysisState> &OldBlockState =
         BlockStates[Block->getBlockID()];
     TypeErasedDataflowAnalysisState NewBlockState =
         transferBlock(CFCtx, BlockStates, *Block, InitEnv, Analysis);
 
     if (OldBlockState.hasValue() &&
         Analysis.isEqualTypeErased(OldBlockState.getValue().Lattice,
                                    NewBlockState.Lattice) &&
-        OldBlockState->Env == NewBlockState.Env) {
+        OldBlockState->Env.equivalentTo(NewBlockState.Env, Analysis)) {
       // The state of `Block` didn't change after transfer so there's no need to
       // revisit its successors.
       continue;
     }
 
     BlockStates[Block->getBlockID()] = std::move(NewBlockState);
 
     // Do not add unreachable successor blocks to `Worklist`.

clang/unittests/Analysis/FlowSensitive/TestingSupport.h

llvm::Error checkDataflow(
   DataflowAnalysisContext DACtx;
   Environment Env(DACtx, *F);
   auto Analysis = MakeAnalysis(Context, Env);
 
   llvm::Expected<llvm::DenseMap<const clang::Stmt *, std::string>>
       StmtToAnnotations = buildStatementToAnnotationMapping(F, AnnotatedCode);
   if (!StmtToAnnotations)
     return StmtToAnnotations.takeError();
-
   auto &Annotations = *StmtToAnnotations;
 
-  std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> BlockStates =
-      runTypeErasedDataflowAnalysis(*CFCtx, Analysis, Env);
+  llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>>
+      MaybeBlockStates = runTypeErasedDataflowAnalysis(*CFCtx, Analysis, Env);
+  if (!MaybeBlockStates)
+    return MaybeBlockStates.takeError();
+  auto &BlockStates = *MaybeBlockStates;
 
   if (BlockStates.empty()) {
     Expectations({}, Context);
     return llvm::Error::success();
   }
 
   // Compute a map from statement annotations to the state computed for
   // the program point immediately after the annotated statement.

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

 #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/Analysis/FlowSensitive/Value.h"
 #include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Testing/Support/Error.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <cassert>

 using ::testing::IsEmpty;
 using ::testing::IsNull;
 using ::testing::NotNull;
 using ::testing::Pair;
 using ::testing::Test;
 using ::testing::UnorderedElementsAre;
 
 template <typename AnalysisT>
-class AnalysisCallback : public ast_matchers::MatchFinder::MatchCallback {
-public:
-  AnalysisCallback(AnalysisT (*MakeAnalysis)(ASTContext &))
-      : MakeAnalysis(MakeAnalysis) {}
-  void run(const ast_matchers::MatchFinder::MatchResult &Result) override {
-    assert(BlockStates.empty());
+llvm::Expected<std::vector<
+    llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
+runAnalysis(llvm::StringRef Code, AnalysisT (*MakeAnalysis)(ASTContext &)) {
+  std::unique_ptr<ASTUnit> AST =
+      tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"});
 
-    const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
-    assert(Func != nullptr);
+  auto *Func = selectFirst<FunctionDecl>(
+      "func", match(functionDecl(ast_matchers::hasName("target")).bind("func"),
+                    AST->getASTContext()));
 
-    Stmt *Body = Func->getBody();
-    assert(Body != nullptr);
 
-    auto CFCtx = llvm::cantFail(
-        ControlFlowContext::build(nullptr, Body, Result.Context));
+      ControlFlowContext::build(nullptr, Body, &AST->getASTContext()));
 
-    AnalysisT Analysis = MakeAnalysis(*Result.Context);
-    DataflowAnalysisContext DACtx;
-    Environment Env(DACtx);
-    BlockStates = runDataflowAnalysis(CFCtx, Analysis, Env);
-  }
-
-  AnalysisT (*MakeAnalysis)(ASTContext &);
-  std::vector<
-      llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
-      BlockStates;
-};
+  AnalysisT Analysis = MakeAnalysis(AST->getASTContext());
 
-template <typename AnalysisT>
-std::vector<llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
-runAnalysis(llvm::StringRef Code, AnalysisT (*MakeAnalysis)(ASTContext &)) {
-  std::unique_ptr<ASTUnit> AST =
-      tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"});
-
-  AnalysisCallback<AnalysisT> Callback(MakeAnalysis);
-  ast_matchers::MatchFinder Finder;
-  Finder.addMatcher(
-      ast_matchers::functionDecl(ast_matchers::hasName("target")).bind("func"),
-      &Callback);
-  Finder.matchAST(AST->getASTContext());
-
-  return Callback.BlockStates;
+  return runDataflowAnalysis(CFCtx, Analysis, Env);
 }
 
 TEST(DataflowAnalysisTest, NoopAnalysis) {
-  auto BlockStates = runAnalysis<NoopAnalysis>(
-      "void target() {}", [](ASTContext &C) { return NoopAnalysis(C, false); });
+  auto BlockStates = llvm::cantFail(
+      runAnalysis<NoopAnalysis>("void target() {}", [](ASTContext &C) {
+        return NoopAnalysis(C, false);
+      }));
   EXPECT_EQ(BlockStates.size(), 2u);
   EXPECT_TRUE(BlockStates[0].hasValue());
   EXPECT_TRUE(BlockStates[1].hasValue());
 }
 
 struct NonConvergingLattice {
   int State;
 
public:
   static NonConvergingLattice initialElement() { return {0}; }
 
   void transfer(const Stmt *S, NonConvergingLattice &E, Environment &Env) {
     ++E.State;
   }
 };
 
 TEST(DataflowAnalysisTest, NonConvergingAnalysis) {
-  auto BlockStates = runAnalysis<NonConvergingAnalysis>(
-      R"(
+  std::string Code = R"(
     void target() {
       while(true) {}
     }
-  )",
-      [](ASTContext &C) { return NonConvergingAnalysis(C); });
-  EXPECT_EQ(BlockStates.size(), 4u);
-  EXPECT_TRUE(BlockStates[0].hasValue());
-  EXPECT_TRUE(BlockStates[1].hasValue());
-  EXPECT_TRUE(BlockStates[2].hasValue());
-  EXPECT_TRUE(BlockStates[3].hasValue());
+  )";
+  auto Res = runAnalysis<NonConvergingAnalysis>(
+      Code, [](ASTContext &C) { return NonConvergingAnalysis(C); });
+  EXPECT_EQ(llvm::toString(Res.takeError()),
+            "maximum number of iterations reached");
 }
 
 struct FunctionCallLattice {
   llvm::SmallSet<std::string, 8> CalledFunctions;
 
   bool operator==(const FunctionCallLattice &Other) const {
     return CalledFunctions == Other.CalledFunctions;
   }
runDataflow(Code, UnorderedElementsAre(
                         Pair("p", HoldsFunctionCallLattice(HasCalledFunctions(
                                       UnorderedElementsAre("baz", "foo"))))));
   // FIXME: Called functions at point `p` should contain only "foo".
 }
 
 class OptionalIntAnalysis
     : public DataflowAnalysis<OptionalIntAnalysis, NoopLattice> {
 public:
-  explicit OptionalIntAnalysis(ASTContext &Context)
-      : DataflowAnalysis<OptionalIntAnalysis, NoopLattice>(Context) {}
+  explicit OptionalIntAnalysis(ASTContext &Context, BoolValue &HasValueTop)
+      : DataflowAnalysis<OptionalIntAnalysis, NoopLattice>(Context),
+        HasValueTop(HasValueTop) {}
 
   static NoopLattice initialElement() { return {}; }
 
   void transfer(const Stmt *S, NoopLattice &, Environment &Env) {
     auto OptionalIntRecordDecl = recordDecl(hasName("OptionalInt"));
     auto HasOptionalIntType = hasType(OptionalIntRecordDecl);
 
     if (const auto *E = selectFirst<CXXConstructExpr>(
if (const auto *E = selectFirst<CXXConstructExpr>(
 
       auto &ConstructorVal =
           *cast<StructValue>(Env.createValue(Object->getType()));
       ConstructorVal.setProperty("has_value", Env.getBoolLiteralValue(true));
       Env.setValue(*ObjectLoc, ConstructorVal);
     }
   }
 
+  bool compareEquivalent(QualType Type, const Value &Val1,
+                         const Value &Val2) final {
+    // Nothing to say about a value that does not model an `OptionalInt`.
+    if (!Type->isRecordType() ||
+        Type->getAsCXXRecordDecl()->getQualifiedNameAsString() != "OptionalInt")
+      return false;
+
+    return cast<StructValue>(&Val1)->getProperty("has_value") ==
+           cast<StructValue>(&Val2)->getProperty("has_value");
+  }
+
   bool merge(QualType Type, const Value &Val1, const Value &Val2,
              Value &MergedVal, Environment &Env) final {
+    // Nothing to say about a value that does not model an `OptionalInt`.
     if (!Type->isRecordType() ||
         Type->getAsCXXRecordDecl()->getQualifiedNameAsString() != "OptionalInt")
       return false;
 
     auto *HasValue1 = cast_or_null<BoolValue>(
         cast<StructValue>(&Val1)->getProperty("has_value"));
     if (HasValue1 == nullptr)
       return false;
 
     auto *HasValue2 = cast_or_null<BoolValue>(
         cast<StructValue>(&Val2)->getProperty("has_value"));
     if (HasValue2 == nullptr)
       return false;
 
-    if (HasValue1 != HasValue2)
-      return false;
-
-    cast<StructValue>(&MergedVal)->setProperty("has_value", *HasValue1);
+    assert(HasValue1 != HasValue2);
+    cast<StructValue>(&MergedVal)->setProperty("has_value", HasValueTop);
     return true;
   }
+
+  BoolValue &HasValueTop;
 };
 
 class WideningTest : public Test {
 protected:
   template <typename Matcher>
   void runDataflow(llvm::StringRef Code, Matcher Match) {
     tooling::FileContentMappings FilesContents;
     FilesContents.push_back(
         std::make_pair<std::string, std::string>("widening_test_defs.h", R"(
       struct OptionalInt {
         OptionalInt() = default;
         OptionalInt& operator=(int);
       };
     )"));
     ASSERT_THAT_ERROR(
         test::checkDataflow<OptionalIntAnalysis>(
             Code, "target",
-            [](ASTContext &Context, Environment &Env) {
-              return OptionalIntAnalysis(Context);
+            [this](ASTContext &Context, Environment &Env) {
+              assert(HasValueTop == nullptr);
+              HasValueTop = &Env.takeOwnership(std::make_unique<BoolValue>());
+              return OptionalIntAnalysis(Context, *HasValueTop);
             },
             [&Match](
                 llvm::ArrayRef<
                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
                     Results,
                 ASTContext &ASTCtx) { Match(Results, ASTCtx); },
             {"-fsyntax-only", "-std=c++17"}, FilesContents),
         llvm::Succeeded());
   }
+
+  BoolValue *HasValueTop = nullptr;
 };
 
 TEST_F(WideningTest, JoinDistinctValuesWithDistinctProperties) {
   std::string Code = R"(
     #include "widening_test_defs.h"
 
     void target(bool Cond) {
       OptionalInt Foo;
       /*[[p1]]*/
       if (Cond) {
         Foo = 1;
         /*[[p2]]*/
       }
       (void)0;
       /*[[p3]]*/
     }
   )";
   runDataflow(
-      Code, [](llvm::ArrayRef<
-                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
-                   Results,
-               ASTContext &ASTCtx) {
+      Code,
+      [this](llvm::ArrayRef<
         ASSERT_THAT(Results,
                     ElementsAre(Pair("p3", _), Pair("p2", _), Pair("p1", _)));
         const Environment &Env1 = Results[2].second.Env;
         const Environment &Env2 = Results[1].second.Env;
         const Environment &Env3 = Results[0].second.Env;
 
         const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
         ASSERT_THAT(FooDecl, NotNull());
 
         auto GetFooValue = [FooDecl](const Environment &Env) {
           return cast<StructValue>(Env.getValue(*FooDecl, SkipPast::None));
         };
 
         EXPECT_EQ(GetFooValue(Env1)->getProperty("has_value"),
                   &Env1.getBoolLiteralValue(false));
         EXPECT_EQ(GetFooValue(Env2)->getProperty("has_value"),
                   &Env2.getBoolLiteralValue(true));
-        EXPECT_THAT(Env3.getValue(*FooDecl, SkipPast::None), IsNull());
+        EXPECT_EQ(GetFooValue(Env3)->getProperty("has_value"), HasValueTop);
       });
 }
 
 TEST_F(WideningTest, JoinDistinctValuesWithSameProperties) {
   std::string Code = R"(
     #include "widening_test_defs.h"
 
     void target(bool Cond) {
runDataflow(
                   &Env2.getBoolLiteralValue(true));
         EXPECT_EQ(GetFooValue(Env3)->getProperty("has_value"),
                   &Env3.getBoolLiteralValue(true));
         EXPECT_EQ(GetFooValue(Env4)->getProperty("has_value"),
                   &Env4.getBoolLiteralValue(true));
       });
 }
 
-TEST_F(WideningTest, DistinctPointersToTheSameLocation) {
+TEST_F(WideningTest, DistinctPointersToTheSameLocationAreEquivalent) {
   std::string Code = R"(
     void target(int Foo, bool Cond) {
       int *Bar = &Foo;
       while (Cond) {
         Bar = &Foo;
       }
       (void)0;
       // [[p]]
runDataflow(Code,
                 const auto *FooLoc = cast<ScalarStorageLocation>(
                     Env.getStorageLocation(*FooDecl, SkipPast::None));
                 const auto *BarVal =
                     cast<PointerValue>(Env.getValue(*BarDecl, SkipPast::None));
                 EXPECT_EQ(&BarVal->getPointeeLoc(), FooLoc);
               });
 }
 
+TEST_F(WideningTest, DistinctValuesWithSamePropertiesAreEquivalent) {
+  std::string Code = R"(
+    #include "widening_test_defs.h"
+
+    void target(bool Cond) {
+      OptionalInt Foo;
+      Foo = 1;
+      while (Cond) {
+        Foo = 2;
+      }
+      (void)0;
+      /*[[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 auto *FooVal =
+                    cast<StructValue>(Env.getValue(*FooDecl, SkipPast::None));
+                EXPECT_EQ(FooVal->getProperty("has_value"),
+                          &Env.getBoolLiteralValue(true));
+              });
+}
+
 } // namespace