[clang][dataflow] Remove IndirectionValue class, moving PointeeLoc field into PointerValue and ReferenceValue

[wyt]

Summary

This patch precedes a future patch to make PointeeLoc for PointerValue possibly empty (for nullptr), by using a pointer instead of a reference type.
ReferenceValue should maintain a non-empty PointeeLoc reference.

[gribozavr2]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

53

WDYT about "areEquivalentIndirectionValues"?

63

This assert was lost in the new implementation.

[wyt]

Rename function as suggested

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

63

The assertion was to ensure that the values were either both Reference or both Pointer, as an IndirectionValue could be either.
Since we've removed IndirectionVal and have separate casts for ReferenceVal/PointerVal, the assertion is not neccessary.

[gribozavr2]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

63

Ah I see, the cast now plays the role of the assert.

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

 public:
   explicit IntegerValue() : Value(Kind::Integer) {}
 
   static bool classof(const Value *Val) {
     return Val->getKind() == Kind::Integer;
   }
 };
 
-/// Base class for values that refer to storage locations.
-class IndirectionValue : public Value {
+/// Models a dereferenced pointer. For example, a reference in C++ or an lvalue
+/// in C.
+class ReferenceValue final : public Value {
 public:
-  /// Constructs a value that refers to `PointeeLoc`.
-  explicit IndirectionValue(Kind ValueKind, StorageLocation &PointeeLoc)
-      : Value(ValueKind), PointeeLoc(PointeeLoc) {}
+  explicit ReferenceValue(StorageLocation &PointeeLoc)
+      : Value(Kind::Reference), PointeeLoc(PointeeLoc) {}
 
   static bool classof(const Value *Val) {
-    return Val->getKind() == Kind::Reference || Val->getKind() == Kind::Pointer;
+    return Val->getKind() == Kind::Reference;
   }
 
   StorageLocation &getPointeeLoc() const { return PointeeLoc; }
 
 private:
   StorageLocation &PointeeLoc;
 };
 
-/// Models a dereferenced pointer. For example, a reference in C++ or an lvalue
-/// in C.
-class ReferenceValue final : public IndirectionValue {
-public:
-  explicit ReferenceValue(StorageLocation &PointeeLoc)
-      : IndirectionValue(Kind::Reference, PointeeLoc) {}
-
-  static bool classof(const Value *Val) {
-    return Val->getKind() == Kind::Reference;
-  }
-};
-
 /// Models a symbolic pointer. Specifically, any value of type `T*`.
-class PointerValue final : public IndirectionValue {
+class PointerValue final : public Value {
 public:
   explicit PointerValue(StorageLocation &PointeeLoc)
-      : IndirectionValue(Kind::Pointer, PointeeLoc) {}
+      : Value(Kind::Pointer), PointeeLoc(PointeeLoc) {}
 
   static bool classof(const Value *Val) {
     return Val->getKind() == Kind::Pointer;
   }
+
+  StorageLocation &getPointeeLoc() const { return PointeeLoc; }
+
+private:
+  StorageLocation &PointeeLoc;
 };
 
 /// Models a value of `struct` or `class` type, with a flat map of fields to
 /// child storage locations, containing all accessible members of base struct
 /// and class types.
 class StructValue final : public Value {
 public:
   StructValue() : StructValue(llvm::DenseMap<const ValueDecl *, Value *>()) {}

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;
 }
 
+static bool areEquivalentIndirectionValues(Value *Val1, Value *Val2) {
+  if (auto *IndVal1 = dyn_cast<ReferenceValue>(Val1)) {
+    auto *IndVal2 = cast<ReferenceValue>(Val2);
+    return &IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc();
+  }
+  if (auto *IndVal1 = dyn_cast<PointerValue>(Val1)) {
+    auto *IndVal2 = cast<PointerValue>(Val2);
+    return &IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc();
+  }
+  return false;
+}
+
 /// Returns true if and only if `Val1` is equivalent to `Val2`.
 static bool equivalentValues(QualType Type, Value *Val1,
                              const Environment &Env1, Value *Val2,
                              const Environment &Env2,
                              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());
-    if (&IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc())
-      return true;
-  }
-
-  return Model.compareEquivalent(Type, *Val1, Env1, *Val2, Env2);
+  return Val1 == Val2 || areEquivalentIndirectionValues(Val1, Val2) ||
+         Model.compareEquivalent(Type, *Val1, Env1, *Val2, Env2);
 }
 
 /// Attempts to merge distinct values `Val1` and `Val2` in `Env1` and `Env2`,
 /// respectively, of the same type `Type`. Merging generally produces a single
 /// value that (soundly) approximates the two inputs, although the actual
 /// meaning depends on `Model`.
 static Value *mergeDistinctValues(QualType Type, Value *Val1,
                                   const Environment &Env1, Value *Val2,
                                   const Environment &Env2,
                                   Environment &MergedEnv,
                                   Environment::ValueModel &Model) {
   // Join distinct boolean values preserving information about the constraints
   // in the respective path conditions.
   //
   // FIXME: Does not work for backedges, since the two (or more) paths will not
   // have mutually exclusive conditions.
   if (auto *Expr1 = dyn_cast<BoolValue>(Val1)) {
     auto *Expr2 = cast<BoolValue>(Val2);
     return &Env1.makeOr(Env1.makeAnd(Env1.getFlowConditionToken(), *Expr1),
                         Env1.makeAnd(Env2.getFlowConditionToken(), *Expr2));
   }
 
   // FIXME: add unit tests that cover this statement.
-  if (auto *IndVal1 = dyn_cast<IndirectionValue>(Val1)) {
-    auto *IndVal2 = cast<IndirectionValue>(Val2);
-    assert(IndVal1->getKind() == IndVal2->getKind());
-    if (&IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc()) {
-      return Val1;
-    }
-  }
+  if (areEquivalentIndirectionValues(Val1, Val2)) {
 
   // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge`
   // returns false to avoid storing unneeded values in `DACtx`.
   if (Value *MergedVal = MergedEnv.createValue(Type))
     if (Model.merge(Type, *Val1, Env1, *Val2, Env2, *MergedVal, MergedEnv))
       return MergedVal;
 
   return nullptr;

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

 
 TEST_F(TransferTest, IntVarDecl) {
   std::string Code = R"(
     void target() {
       int Foo;
       // [[p]]
     }
   )";
-  runDataflow(
-      Code, [](llvm::ArrayRef<
+  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, SkipPast::None);
                 ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
 
                 const Value *FooVal = Env.getValue(*FooLoc);
                 EXPECT_TRUE(isa_and_nonnull<IntegerValue>(FooVal));
               });
 }
 
 TEST_F(TransferTest, StructVarDecl) {
   std::string Code = R"(
     struct A {
       int Bar;
     };
 
std::string Code = R"(
 
     A &getA();
 
     void target() {
       A &Foo = getA();
       // [[p]]
     }
   )";
-  runDataflow(
-      Code, [](llvm::ArrayRef<
+  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, SkipPast::None);
                 ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
 
                 const ReferenceValue *FooVal =
                     cast<ReferenceValue>(Env.getValue(*FooLoc));
                 const StorageLocation &FooPointeeLoc = FooVal->getPointeeLoc();
                 EXPECT_TRUE(isa<AggregateStorageLocation>(&FooPointeeLoc));
 
                 const Value *FooPointeeVal = Env.getValue(FooPointeeLoc);
                 EXPECT_TRUE(isa_and_nonnull<StructValue>(FooPointeeVal));
               });
 }
 
 TEST_F(TransferTest, SelfReferentialReferenceVarDecl) {
   std::string Code = R"(
     struct A;
 
     struct B {};
 
runDataflow(
 
         const ValueDecl *ValDecl = findValueDecl(ASTCtx, "val");
         ASSERT_THAT(ValDecl, NotNull());
 
         const ValueDecl *LDecl = findValueDecl(ASTCtx, "l");
         ASSERT_THAT(LDecl, NotNull());
 
         // Inner.
-        auto *LVal = dyn_cast<IndirectionValue>(
-            InnerEnv.getValue(*LDecl, SkipPast::None));
+        auto *LVal =
+            dyn_cast<PointerValue>(InnerEnv.getValue(*LDecl, SkipPast::None));
         ASSERT_THAT(LVal, NotNull());
 
         EXPECT_EQ(&LVal->getPointeeLoc(),
                   InnerEnv.getStorageLocation(*ValDecl, SkipPast::Reference));
 
         // Outer.
-        LVal = dyn_cast<IndirectionValue>(
-            OuterEnv.getValue(*LDecl, SkipPast::None));
+        LVal =
+            dyn_cast<PointerValue>(OuterEnv.getValue(*LDecl, SkipPast::None));
         ASSERT_THAT(LVal, NotNull());
 
         // The loop body may not have been executed, so we should not conclude
         // that `l` points to `val`.
         EXPECT_NE(&LVal->getPointeeLoc(),
                   OuterEnv.getStorageLocation(*ValDecl, SkipPast::Reference));
       });
 }
 
 TEST_F(TransferTest, DoesNotCrashOnUnionThisExpr) {
   std::string Code = R"(
     union Union {
       int A;
       float B;
     };