[clang][dataflow] Eliminate `ReferenceValue`.

[mboehme]

Summary

There are no remaining uses of this class in the framework.

This patch is part of the ongoing migration to strict handling of value categories (see https://discourse.llvm.org/t/70086 for details).

[mboehme]

Rebase to head

[mboehme]

Pre-merge failure looks unrelated. It's in AST/Interp/literals.cpp, and this patch shouldn't affect that in any way.

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

 /// storage locations or values.
 ///
 /// FIXME: Consider renaming this or replacing it with a more appropriate model.
 /// See the discussion in https://reviews.llvm.org/D116596 for context.
 enum class SkipPast {
   /// No indirections should be skipped past.
   None,
   /// An optional reference should be skipped past.
+  /// This is deprecated; it is equivalent to `None` and will be removed.
   Reference,
 };
 
 /// Indicates the result of a tentative comparison.
 enum class ComparisonResult {
   Same,
   Different,
   Unknown,
public:
   /// removed and this function will be renamed to `setStorageLocation()`.
   ///
   /// Requirements:
   ///
   ///  `E` must not be assigned a storage location in the environment.
   ///  `E` must be a glvalue or a `BuiltinType::BuiltinFn`
   void setStorageLocationStrict(const Expr &E, StorageLocation &Loc);
 
-  /// Returns the storage location assigned to `E` in the environment, applying
-  /// the `SP` policy for skipping past indirections, or null if `E` isn't
-  /// assigned a storage location in the environment.
+  /// Returns the storage location assigned to `E` in the environment, or null
+  /// if `E` isn't assigned a storage location in the environment.
+  ///
+  /// The `SP` parameter has no effect.
   ///
   /// This function is deprecated; prefer `getStorageLocationStrict()`.
   /// For details, see https://discourse.llvm.org/t/70086.
   StorageLocation *getStorageLocation(const Expr &E, SkipPast SP) const;
 
   /// Returns the storage location assigned to the glvalue `E` in the
   /// environment, or null if `E` isn't assigned a storage location in the
   /// environment.
public:
   ///  `E`. This is to guarantee that the result object initialized by a prvalue
   ///  `StructValue` has a durable storage location.
   void setValueStrict(const Expr &E, Value &Val);
 
   /// Returns the value assigned to `Loc` in the environment or null if `Loc`
   /// isn't assigned a value in the environment.
   Value *getValue(const StorageLocation &Loc) const;
 
-  /// Equivalent to `getValue(getStorageLocation(D, SP), SkipPast::None)` if `D`
-  /// is assigned a storage location in the environment, otherwise returns null.
+  /// Equivalent to `getValue(getStorageLocation(D))` if `D` is assigned a
+  /// storage location in the environment, otherwise returns null.
   Value *getValue(const ValueDecl &D) const;
 
-  /// Equivalent to `getValue(getStorageLocation(E, SP), SkipPast::None)` if `E`
-  /// is assigned a storage location in the environment, otherwise returns null.
+  /// Equivalent to `getValue(getStorageLocation(E, SP))` if `E` is assigned a
+  /// storage location in the environment, otherwise returns null.
+  ///
+  /// The `SP` parameter has no effect.
   ///
   /// This function is deprecated; prefer `getValueStrict()`. For details, see
   /// https://discourse.llvm.org/t/70086.
   Value *getValue(const Expr &E, SkipPast SP) const;
 
   /// Returns the `Value` assigned to the prvalue `E` in the environment, or
   /// null if `E` isn't assigned a value in the environment.
   ///
StorageLocation &createLocAndMaybeValue(QualType Ty,
                                           llvm::DenseSet<QualType> &Visited,
                                           int Depth, int &CreatedValuesCount);
 
   /// Shared implementation of `createObject()` overloads.
   /// `D` and `InitExpr` may be null.
   StorageLocation &createObjectInternal(const VarDecl *D, QualType Ty,
                                         const Expr *InitExpr);
 
-  StorageLocation &skip(StorageLocation &Loc, SkipPast SP) const;
-  const StorageLocation &skip(const StorageLocation &Loc, SkipPast SP) const;
-
   /// Shared implementation of `pushCall` overloads. Note that unlike
   /// `pushCall`, this member is invoked on the environment of the callee, not
   /// of the caller.
   void pushCallInternal(const FunctionDecl *FuncDecl,
                         ArrayRef<const Expr *> Args);
 
   /// Assigns storage locations and values to all global variables, fields
   /// and functions referenced in `FuncDecl`. `FuncDecl` must have a body.

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

 /// Base class for all values computed by abstract interpretation.
 ///
 /// Don't use `Value` instances by value. All `Value` instances are allocated
 /// and owned by `DataflowAnalysisContext`.
 class Value {
 public:
   enum class Kind {
     Integer,
-    Reference,
     Pointer,
     Struct,
 
     // TODO: Top values should not be need to be type-specific.
     TopBool,
     AtomicBool,
     FormulaBool,
   };

 public:
   explicit IntegerValue() : Value(Kind::Integer) {}
 
   static bool classof(const Value *Val) {
     return Val->getKind() == Kind::Integer;
   }
 };
 
-/// Models a dereferenced pointer. For example, a reference in C++ or an lvalue
-/// in C.
-class ReferenceValue final : public Value {
-public:
-  explicit ReferenceValue(StorageLocation &ReferentLoc)
-      : Value(Kind::Reference), ReferentLoc(ReferentLoc) {}
-
-  static bool classof(const Value *Val) {
-    return Val->getKind() == Kind::Reference;
-  }
-
-  StorageLocation &getReferentLoc() const { return ReferentLoc; }
-
-private:
-  StorageLocation &ReferentLoc;
-};
-
 /// Models a symbolic pointer. Specifically, any value of type `T*`.
 class PointerValue final : public Value {
 public:
   explicit PointerValue(StorageLocation &PointeeLoc)
       : Value(Kind::Pointer), PointeeLoc(PointeeLoc) {}
 
   static bool classof(const Value *Val) {
     return Val->getKind() == Kind::Pointer;

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

static bool compareDistinctValues(QualType Type, Value &Val1,
   switch (Model.compare(Type, Val1, Env1, Val2, Env2)) {
   case ComparisonResult::Same:
     return true;
   case ComparisonResult::Different:
     return false;
   case ComparisonResult::Unknown:
     switch (Val1.getKind()) {
     case Value::Kind::Integer:
-    case Value::Kind::Reference:
     case Value::Kind::Pointer:
     case Value::Kind::Struct:
       // FIXME: this choice intentionally introduces unsoundness to allow
       // for convergence. Once we have widening support for the
       // reference/pointer and struct built-in models, this should be
       // `false`.
       return true;
     default:
if (auto *StructVal1 = dyn_cast<StructValue>(&Val1)) {
     // properties, it should do so in `DataflowAnalysis::merge()`.
     MergedVal = &MergedEnv.create<StructValue>(StructVal1->getAggregateLoc());
   } else {
     MergedVal = MergedEnv.createValue(Type);
   }
 
   // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge`
   // returns false to avoid storing unneeded values in `DACtx`.
-  // FIXME: Creating the value based on the type alone creates misshapen values
-  // for lvalues, since the type does not reflect the need for `ReferenceValue`.
-  // This issue will be resolved when `ReferenceValue` is eliminated as part
-  // of the ongoing migration to strict handling of value categories (see
-  // https://discourse.llvm.org/t/70086 for details).
   if (MergedVal)
     if (Model.merge(Type, Val1, Env1, Val2, Env2, *MergedVal, MergedEnv))
       return MergedVal;
 
   return nullptr;
 }
 
 // When widening does not change `Current`, return value will equal `&Prev`.
StorageLocation &Environment::createStorageLocation(const Expr &E) {
   // Evaluated expressions are always assigned the same storage locations to
   // ensure that the environment stabilizes across loop iterations. Storage
   // locations for evaluated expressions are stored in the analysis context.
   return DACtx->getStableStorageLocation(E);
 }
 
 void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
   assert(!DeclToLoc.contains(&D));
-  assert(!isa_and_nonnull<ReferenceValue>(getValue(Loc)));
   DeclToLoc[&D] = &Loc;
 }
 
 StorageLocation *Environment::getStorageLocation(const ValueDecl &D) const {
   auto It = DeclToLoc.find(&D);
   if (It == DeclToLoc.end())
     return nullptr;
 
   StorageLocation *Loc = It->second;
 
-  assert(!isa_and_nonnull<ReferenceValue>(getValue(*Loc)));
-
   return Loc;
 }
 
 void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) {
   const Expr &CanonE = ignoreCFGOmittedNodes(E);
   assert(!ExprToLoc.contains(&CanonE));
   ExprToLoc[&CanonE] = &Loc;
 }
 
 void Environment::setStorageLocationStrict(const Expr &E,
                                            StorageLocation &Loc) {
   // `DeclRefExpr`s to builtin function types aren't glvalues, for some reason,
   // but we still want to be able to associate a `StorageLocation` with them,
   // so allow these as an exception.
   assert(E.isGLValue() ||
          E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
   setStorageLocation(E, Loc);
 }
 
 StorageLocation *Environment::getStorageLocation(const Expr &E,
                                                  SkipPast SP) const {
   // FIXME: Add a test with parens.
   auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
-  return It == ExprToLoc.end() ? nullptr : &skip(*It->second, SP);
+  return It == ExprToLoc.end() ? nullptr : &*It->second;
 }
 
 StorageLocation *Environment::getStorageLocationStrict(const Expr &E) const {
   // See comment in `setStorageLocationStrict()`.
   assert(E.isGLValue() ||
          E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
   StorageLocation *Loc = getStorageLocation(E, SkipPast::None);
 
   if (Loc == nullptr)
     return nullptr;
 
-  if (auto *RefVal = dyn_cast_or_null<ReferenceValue>(getValue(*Loc)))
-    return &RefVal->getReferentLoc();
-
   return Loc;
 }
 
 AggregateStorageLocation *Environment::getThisPointeeStorageLocation() const {
   return ThisPointeeLoc;
 }
 
 AggregateStorageLocation &
void Environment::setValue(const StorageLocation &Loc, Value &Val) {
   assert(!isa<StructValue>(&Val) ||
          &cast<StructValue>(&Val)->getAggregateLoc() == &Loc);
 
   LocToVal[&Loc] = &Val;
 }
 
 void Environment::setValueStrict(const Expr &E, Value &Val) {
   assert(E.isPRValue());
-  assert(!isa<ReferenceValue>(Val));
 
   if (auto *StructVal = dyn_cast<StructValue>(&Val)) {
     if (auto *ExistingVal = cast_or_null<StructValue>(getValueStrict(E)))
       assert(&ExistingVal->getAggregateLoc() == &StructVal->getAggregateLoc());
     if (StorageLocation *ExistingLoc = getStorageLocation(E, SkipPast::None))
       assert(ExistingLoc == &StructVal->getAggregateLoc());
     else
       setStorageLocation(E, StructVal->getAggregateLoc());
if (Loc == nullptr)
     return nullptr;
   return getValue(*Loc);
 }
 
 Value *Environment::getValueStrict(const Expr &E) const {
   assert(E.isPRValue());
   Value *Val = getValue(E, SkipPast::None);
 
-  assert(Val == nullptr || !isa<ReferenceValue>(Val));
-
   return Val;
 }
 
 Value *Environment::createValue(QualType Type) {
   llvm::DenseSet<QualType> Visited;
   int CreatedValuesCount = 0;
   Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0,
                                                 CreatedValuesCount);
   if (CreatedValuesCount > MaxCompositeValueSize) {
     llvm::errs() << "Attempting to initialize a huge value of type: " << Type
                  << '\n';
   }
   return Val;
 }
 
 Value *Environment::createValueUnlessSelfReferential(
     QualType Type, llvm::DenseSet<QualType> &Visited, int Depth,
     int &CreatedValuesCount) {
   assert(!Type.isNull());
+  assert(!Type->isReferenceType());
 
   // Allow unlimited fields at depth 1; only cap at deeper nesting levels.
   if ((Depth > 1 && CreatedValuesCount > MaxCompositeValueSize) ||
       Depth > MaxCompositeValueDepth)
     return nullptr;
 
   if (Type->isBooleanType()) {
     CreatedValuesCount++;
     return &makeAtomicBoolValue();
   }
 
   if (Type->isIntegerType()) {
     // FIXME: consider instead `return nullptr`, given that we do nothing useful
     // with integers, and so distinguishing them serves no purpose, but could
     // prevent convergence.
     CreatedValuesCount++;
     return &arena().create<IntegerValue>();
   }
 
-  if (Type->isReferenceType() || Type->isPointerType()) {
+  if (Type->isPointerType()) {
     CreatedValuesCount++;
     QualType PointeeType = Type->getPointeeType();
     StorageLocation &PointeeLoc =
         createLocAndMaybeValue(PointeeType, Visited, Depth, CreatedValuesCount);
 
-    if (Type->isReferenceType())
-      return &arena().create<ReferenceValue>(PointeeLoc);
-    else
-      return &arena().create<PointerValue>(PointeeLoc);
   }
 
   if (Type->isRecordType()) {
     CreatedValuesCount++;
     llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
     for (const FieldDecl *Field : DACtx->getModeledFields(Type)) {
       assert(Field != nullptr);
 
StorageLocation &Loc =
       D ? createStorageLocation(*D) : createStorageLocation(Ty);
 
   if (Val)
     setValue(Loc, *Val);
 
   return Loc;
 }
 
-StorageLocation &Environment::skip(StorageLocation &Loc, SkipPast SP) const {
-  switch (SP) {
-  case SkipPast::None:
-    return Loc;
-  case SkipPast::Reference:
-    // References cannot be chained so we only need to skip past one level of
-    // indirection.
-    if (auto *Val = dyn_cast_or_null<ReferenceValue>(getValue(Loc)))
-      return Val->getReferentLoc();
-    return Loc;
-  }
-  llvm_unreachable("bad SkipPast kind");
-}
-
-const StorageLocation &Environment::skip(const StorageLocation &Loc,
-                                         SkipPast SP) const {
-  return skip(*const_cast<StorageLocation *>(&Loc), SP);
-}
-
 void Environment::addToFlowCondition(const Formula &Val) {
   DACtx->addFlowConditionConstraint(FlowConditionToken, Val);
 }
 
 bool Environment::flowConditionImplies(const Formula &Val) const {
   return DACtx->flowConditionImplies(FlowConditionToken, Val);
 }
 

clang/lib/Analysis/FlowSensitive/DebugSupport.cpp

 
 namespace clang {
 namespace dataflow {
 
 llvm::StringRef debugString(Value::Kind Kind) {
   switch (Kind) {
   case Value::Kind::Integer:
     return "Integer";
-  case Value::Kind::Reference:
-    return "Reference";
   case Value::Kind::Pointer:
     return "Pointer";
   case Value::Kind::Struct:
     return "Struct";
   case Value::Kind::AtomicBool:
     return "AtomicBool";
   case Value::Kind::TopBool:
     return "TopBool";

clang/lib/Analysis/FlowSensitive/HTMLLogger.cpp

void dump(Value &V) {
     JOS.attribute("kind", debugString(V.getKind()));
 
     switch (V.getKind()) {
     case Value::Kind::Integer:
     case Value::Kind::TopBool:
     case Value::Kind::AtomicBool:
     case Value::Kind::FormulaBool:
       break;
-    case Value::Kind::Reference:
-      JOS.attributeObject(
-          "referent", [&] { dump(cast<ReferenceValue>(V).getReferentLoc()); });
-      break;
     case Value::Kind::Pointer:
       JOS.attributeObject(
           "pointee", [&] { dump(cast<PointerValue>(V).getPointeeLoc()); });
       break;
     case Value::Kind::Struct:
       for (const auto &Child :
            cast<StructValue>(V).getAggregateLoc().children())
         JOS.attributeObject("f:" + Child.first->getNameAsString(), [&] {

clang/lib/Analysis/FlowSensitive/Value.cpp

 #include "clang/Analysis/FlowSensitive/DebugSupport.h"
 #include "llvm/Support/Casting.h"
 
 namespace clang {
 namespace dataflow {
 
 static bool areEquivalentIndirectionValues(const Value &Val1,
                                            const Value &Val2) {
-  if (auto *IndVal1 = dyn_cast<ReferenceValue>(&Val1)) {
-    auto *IndVal2 = cast<ReferenceValue>(&Val2);
-    return &IndVal1->getReferentLoc() == &IndVal2->getReferentLoc();
-  }
   if (auto *IndVal1 = dyn_cast<PointerValue>(&Val1)) {
     auto *IndVal2 = cast<PointerValue>(&Val2);
     return &IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc();
   }
   return false;
 }
 
 bool areEquivalentValues(const Value &Val1, const Value &Val2) {
   return &Val1 == &Val2 || (Val1.getKind() == Val2.getKind() &&
                             (isa<TopBoolValue>(&Val1) ||
                              areEquivalentIndirectionValues(Val1, Val2)));
 }
 
 raw_ostream &operator<<(raw_ostream &OS, const Value &Val) {
   switch (Val.getKind()) {
-  case Value::Kind::Reference: {
-    const auto *RV = cast<ReferenceValue>(&Val);
-    return OS << "Reference(" << &RV->getReferentLoc() << ")";
-  }
   case Value::Kind::Pointer: {
     const auto *PV = dyn_cast<PointerValue>(&Val);
     return OS << "Pointer(" << &PV->getPointeeLoc() << ")";
   }
   // FIXME: support remaining cases.
   default:
     return OS << debugString(Val.getKind());
   }
 }
 
 } // namespace dataflow
 } // namespace clang

clang/unittests/Analysis/FlowSensitive/ValueTest.cpp

 }
 
 TEST(ValueTest, DifferentIntegerValuesNotEquivalent) {
   IntegerValue V1;
   IntegerValue V2;
   EXPECT_FALSE(areEquivalentValues(V1, V2));
 }
 
-TEST(ValueTest, AliasedReferencesEquivalent) {
-  auto L = ScalarStorageLocation(QualType());
-  ReferenceValue V1(L);
-  ReferenceValue V2(L);
-  EXPECT_TRUE(areEquivalentValues(V1, V2));
-  EXPECT_TRUE(areEquivalentValues(V2, V1));
-}
-
 TEST(ValueTest, AliasedPointersEquivalent) {
   auto L = ScalarStorageLocation(QualType());
   PointerValue V1(L);
   PointerValue V2(L);
   EXPECT_TRUE(areEquivalentValues(V1, V2));
   EXPECT_TRUE(areEquivalentValues(V2, V1));
 }
 
TEST(ValueTest, EquivalentValuesWithDifferentPropsEquivalent) {
   V2.setProperty("bar", Prop2);
   EXPECT_TRUE(areEquivalentValues(V1, V2));
   EXPECT_TRUE(areEquivalentValues(V2, V1));
 }
 
 TEST(ValueTest, DifferentKindsNotEquivalent) {
   Arena A;
   auto L = ScalarStorageLocation(QualType());
-  ReferenceValue V1(L);
+  PointerValue V1(L);
   TopBoolValue V2(A.makeAtomRef(Atom(0)));
   EXPECT_FALSE(areEquivalentValues(V1, V2));
   EXPECT_FALSE(areEquivalentValues(V2, V1));
 }
 
-TEST(ValueTest, NotAliasedReferencesNotEquivalent) {
-  auto L1 = ScalarStorageLocation(QualType());
-  ReferenceValue V1(L1);
-  auto L2 = ScalarStorageLocation(QualType());
-  ReferenceValue V2(L2);
-  EXPECT_FALSE(areEquivalentValues(V1, V2));
-  EXPECT_FALSE(areEquivalentValues(V2, V1));
-}
-
 TEST(ValueTest, NotAliasedPointersNotEquivalent) {
   auto L1 = ScalarStorageLocation(QualType());
   PointerValue V1(L1);
   auto L2 = ScalarStorageLocation(QualType());
   PointerValue V2(L2);
   EXPECT_FALSE(areEquivalentValues(V1, V2));
   EXPECT_FALSE(areEquivalentValues(V2, V1));
 }
 
 } // namespace