[clang][dataflow] Add `Strict` versions of `Value` and `StorageLocation` accessors.

[mboehme]

Summary

This is part of the gradual migration to strict handling of value categories, as described in the RFC at https://discourse.llvm.org/t/70086.

This patch migrates some representative calls of the newly deprecated accessors to the new Strict functions. Followup patches will migrate the remaining callers. (There are a large number of callers, with some subtlety involved in some of them, so it makes sense to split this up into multiple patches rather than migrating all callers in one go.)

The Strict accessors as implemented here have some differences in semantics compared to the semantics originally proposed in the RFC; specifically:

• setStorageLocationStrict(): The RFC proposes to create an intermediate ReferenceValue that then refers to the StorageLocation for the glvalue. It turns out though that, even today, most places in the code are not doing this but are instead associating glvalues directly with their StorageLocation. It therefore didn't seem to make sense to introduce new ReferenceValues where there were none previously, so I have chosen to instead make setStorageLocationStrict() simply call through to setStorageLocation(const Expr &, StorageLocation &) and merely add the assertion that the expression must be a glvalue.

• getStorageLocationStrict(): The RFC proposes that this should assert that the storage location for the glvalue expression is associated with an intermediate ReferenceValue, but, as explained, this is often not true. The current state is inconsistent: Sometimes the intermediate ReferenceValue is there, sometimes it isn't. For this reason, getStorageLocationStrict() skips past a ReferenceValue if it is there but otherwise directly returns the storage location associated with the expression. This behavior is equivalent to the existing behavior of SkipPast::Reference.

• setValueStrict(): The RFC proposes that this should always create the same StorageLocation for a given Value, but, in fact, the transfer functions that exist today don't guarantee this; almost all transfer functions unconditionally create a new StorageLocation when associating an expression with a Value.
  
  There appears to be one special case: TerminatorVisitor::extendFlowCondition() checks whether the expression is already associated with a StorageLocation and, if so, reuses the existing StorageLocation instead of creating a new one.
  
  For this reason, setValueStrict() implements this logic (preserve an existing StorageLocation) but makes no attempt to always associate the same StorageLocation with a given Value, as nothing in the framework appers to require this.
  
  As TerminatorVisitor::extendFlowCondition() is an interesting special case, the setValue() call there is among the ones that this patch migrates to setValueStrict().

[sammccall]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

644

why does it make sense to allow setStorageLocationStrict but not getStorageLocationStrict for builtin functions?

705

this isn't documented, should it be?

[ymandel]

I'm a little confused by one of the points in the description:

setValueStrict(): The RFC proposes that this should always create the same StorageLocation for a given Value, but, in fact, the transfer functions that exist today don't guarantee this; almost all transfer functions unconditionally create a new StorageLocation when associating an expression with a Value.

Since values are immutable, we (intentionally) share them between different storage locations. So, it makes sense that a single value could be associated with multiple storage locations. Now, there's a bug in that values aren't really immutable since you can update the fields, so we have a false sharing bug in the framework, but maybe that only applies to glvalues?

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

273

Use LLVM_DEPRECATED? here and below.

[mboehme]

Tweaked preconditions (in comments and code)

[mboehme]

In D150653#4345771, @ymandel wrote:

I'm a little confused by one of the points in the description:

setValueStrict(): The RFC proposes that this should always create the same StorageLocation for a given Value, but, in fact, the transfer functions that exist today don't guarantee this; almost all transfer functions unconditionally create a new StorageLocation when associating an expression with a Value.

Since values are immutable, we (intentionally) share them between different storage locations. So, it makes sense that a single value could be associated with multiple storage locations. Now, there's a bug in that values aren't really immutable since you can update the fields, so we have a false sharing bug in the framework, but maybe that only applies to glvalues?

Yes, values are and should definitely be shared between different storage locations.

The comment in the RFC is specifically in the context of the "fake" storage locations that we create for prvalues (since setValueStrict() only deals with prvalues). I call these storage locations "fake" because a prvalue doesn't actually have a storage location. During the review of the RFC, one of the reviewers asked whether we should guarantee that a given Value, when associated with a prvalue Expr, should always use the same "fake" storage location, instead of creating a new storage location every time. The idea was that this might be required for convergence. This argument made sense to me at the time, but having looked at what the existing code does, almost every place that associates a Value with a prvalue expression unconditionally create a new "fake" storage location. So this implies to me that creating durable fake storage locations isn't necessary.

Does this make sense?

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

273

There are some buildbots that are configured to produce an error (instead of a warning) when an LLVM_DEPRECATED function is used. (I've unfortunately broken builds more than once because of this.)

The functions that are being deprecated in this patch are still being used in many places, so we can only deprecate them with a comment, but not with LLVM_DEPRECATED.

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

644

Thanks for pointing this out -- this was an inconsistency that I just missed (and obviously there aren't any tests that exercise this case for getStorageLocationStrict()).

I've changed this (in comments and code) to be consistent with setStorageLocationStrict().

705

Yes! Done.

[ymandel]

In D150653#4346025, @mboehme wrote:

In D150653#4345771, @ymandel wrote:

I'm a little confused by one of the points in the description:

setValueStrict(): The RFC proposes that this should always create the same StorageLocation for a given Value, but, in fact, the transfer functions that exist today don't guarantee this; almost all transfer functions unconditionally create a new StorageLocation when associating an expression with a Value.

Since values are immutable, we (intentionally) share them between different storage locations. So, it makes sense that a single value could be associated with multiple storage locations. Now, there's a bug in that values aren't really immutable since you can update the fields, so we have a false sharing bug in the framework, but maybe that only applies to glvalues?

Yes, values are and should definitely be shared between different storage locations.

The comment in the RFC is specifically in the context of the "fake" storage locations that we create for prvalues (since setValueStrict() only deals with prvalues). I call these storage locations "fake" because a prvalue doesn't actually have a storage location. During the review of the RFC, one of the reviewers asked whether we should guarantee that a given Value, when associated with a prvalue Expr, should always use the same "fake" storage location, instead of creating a new storage location every time. The idea was that this might be required for convergence. This argument made sense to me at the time, but having looked at what the existing code does, almost every place that associates a Value with a prvalue expression unconditionally create a new "fake" storage location. So this implies to me that creating durable fake storage locations isn't necessary.

Does this make sense?

Yes, makes sense.

[mboehme]

Failing x64 debian build is due to a wrong CMake version, which is unrelated to this patch.

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

public:
   /// if `D` isn't assigned a storage location in the environment.
   ///
   /// Note that if `D` has reference type, the storage location that is returned
   /// refers directly to the referenced object, not a `ReferenceValue`.
   StorageLocation *getStorageLocation(const ValueDecl &D) const;
 
   /// Assigns `Loc` as the storage location of `E` in the environment.
   ///
+  /// This function is deprecated; prefer `setStorageLocationStrict()`.
+  /// For details, see https://discourse.llvm.org/t/70086.
+  ///
   /// Requirements:
   ///
   ///  `E` must not be assigned a storage location in the environment.
   void setStorageLocation(const Expr &E, StorageLocation &Loc);
 
+  /// Assigns `Loc` as the storage location of the glvalue `E` in the
+  /// environment.
+  ///
+  /// This function is the preferred alternative to
+  /// `setStorageLocation(const Expr &, StorageLocation &)`. Once the migration
+  /// to strict handling of value categories is complete (see
+  /// https://discourse.llvm.org/t/70086), `setStorageLocation()` will be
+  /// 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.
+  ///
+  /// 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.
+  ///
+  /// If the storage location for `E` is associated with a
+  /// `ReferenceValue RefVal`, returns `RefVal.getReferentLoc()` instead.
+  ///
+  /// This function is the preferred alternative to
+  /// `getStorageLocation(const Expr &, SkipPast)`. Once the migration
+  /// to strict handling of value categories is complete (see
+  /// https://discourse.llvm.org/t/70086), `getStorageLocation()` will be
+  /// removed and this function will be renamed to `getStorageLocation()`.
+  ///
+  /// Requirements:
+  ///  `E` must be a glvalue or a `BuiltinType::BuiltinFn`
+  StorageLocation *getStorageLocationStrict(const Expr &E) const;
+
   /// Returns the storage location assigned to the `this` pointee in the
   /// environment or null if the `this` pointee has no assigned storage location
   /// in the environment.
   StorageLocation *getThisPointeeStorageLocation() const;
 
   /// Returns the storage location of the return value or null, if unset.
   StorageLocation *getReturnStorageLocation() const;
 
public:
   /// Requirements:
   ///
   ///  `Type` must not be null.
   Value *createValue(QualType Type);
 
   /// Assigns `Val` as the value of `Loc` in the environment.
   void setValue(const StorageLocation &Loc, Value &Val);
 
+  /// Assigns `Val` as the value of the prvalue `E` in the environment.
+  ///
+  /// If `E` is not yet associated with a storage location, associates it with
+  /// a newly created storage location. In any case, associates the storage
+  /// location of `E` with `Val`.
+  ///
+  /// Once the migration to strict handling of value categories is complete
+  /// (see https://discourse.llvm.org/t/70086), this function will be renamed to
+  /// `setValue()`. At this point, prvalue expressions will be associated
+  /// directly with `Value`s, and the legacy behavior of associating prvalue
+  /// expressions with storage locations (as described above) will be
+  /// eliminated.
+  ///
+  /// Requirements:
+  ///
+  ///  `E` must be a prvalue
+  ///  `Val` must not be a `ReferenceValue`
+  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.
   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.
+  ///
+  /// 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.
+  ///
+  /// This function is the preferred alternative to
+  /// `getValue(const Expr &, SkipPast)`. Once the migration to strict handling
+  /// of value categories is complete (see https://discourse.llvm.org/t/70086),
+  /// `getValue()` will be removed and this function will be renamed to
+  /// `getValue()`.
+  ///
+  /// Requirements:
+  ///
+  ///  `E` must be a prvalue
+  Value *getValueStrict(const Expr &E) const;
+
   // FIXME: should we deprecate the following & call arena().create() directly?
 
   /// Creates a `T` (some subclass of `Value`), forwarding `args` to the
   /// constructor, and returns a reference to it.
   ///
   /// The analysis context takes ownership of the created object. The object
   /// will be destroyed when the analysis context is destroyed.
   template <typename T, typename... Args>

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

 }
 
 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);
 }
 
+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;
+}
+
 StorageLocation *Environment::getThisPointeeStorageLocation() const {
   return ThisPointeeLoc;
 }
 
 StorageLocation *Environment::getReturnStorageLocation() const {
   return ReturnLoc;
 }
 
if (It != MemberLocToStruct.end()) {
 
     assert(It->second.second != nullptr);
     const ValueDecl &Member = *It->second.second;
 
     StructVal.setChild(Member, Val);
   }
 }
 
+void Environment::setValueStrict(const Expr &E, Value &Val) {
+  assert(E.isPRValue());
+  assert(!isa<ReferenceValue>(Val));
+
+  StorageLocation *Loc = getStorageLocation(E, SkipPast::None);
+  if (Loc == nullptr) {
+    Loc = &createStorageLocation(E);
+    setStorageLocation(E, *Loc);
+  }
+  setValue(*Loc, Val);
+}
+
 Value *Environment::getValue(const StorageLocation &Loc) const {
   auto It = LocToVal.find(&Loc);
   return It == LocToVal.end() ? nullptr : It->second;
 }
 
 Value *Environment::getValue(const ValueDecl &D) const {
   auto *Loc = getStorageLocation(D);
   if (Loc == nullptr)
     return nullptr;
   return getValue(*Loc);
 }
 
 Value *Environment::getValue(const Expr &E, SkipPast SP) const {
   auto *Loc = getStorageLocation(E, SP);
   if (Loc == nullptr)
     return nullptr;
   return getValue(*Loc);
 }
 
+Value *Environment::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';

clang/lib/Analysis/FlowSensitive/Transfer.cpp

public:
 
   void VisitDeclRefExpr(const DeclRefExpr *S) {
     const ValueDecl *VD = S->getDecl();
     assert(VD != nullptr);
     auto *DeclLoc = Env.getStorageLocation(*VD);
     if (DeclLoc == nullptr)
       return;
 
-    Env.setStorageLocation(*S, *DeclLoc);
+    Env.setStorageLocationStrict(*S, *DeclLoc);
   }
 
   void VisitDeclStmt(const DeclStmt *S) {
     // Group decls are converted into single decls in the CFG so the cast below
     // is safe.
     const auto &D = *cast<VarDecl>(S->getSingleDecl());
 
     ProcessVarDecl(D);
void VisitImplicitCastExpr(const ImplicitCastExpr *S) {
     const Expr *SubExpr = S->getSubExpr();
     assert(SubExpr != nullptr);
 
     switch (S->getCastKind()) {
     case CK_IntegralToBoolean: {
       // This cast creates a new, boolean value from the integral value. We
       // model that with a fresh value in the environment, unless it's already a
       // boolean.
-      auto &Loc = Env.createStorageLocation(*S);
-      Env.setStorageLocation(*S, Loc);
-      if (auto *SubExprVal = dyn_cast_or_null<BoolValue>(
-              Env.getValue(*SubExpr, SkipPast::Reference)))
-        Env.setValue(Loc, *SubExprVal);
+      if (auto *SubExprVal =
+              dyn_cast_or_null<BoolValue>(Env.getValueStrict(*SubExpr)))
+        Env.setValueStrict(*S, *SubExprVal);
       else
         // FIXME: If integer modeling is added, then update this code to create
         // the boolean based on the integer model.
-        Env.setValue(Loc, Env.makeAtomicBoolValue());
+        Env.setValueStrict(*S, Env.makeAtomicBoolValue());
       break;
     }
 
     case CK_LValueToRValue: {
       // When an L-value is used as an R-value, it may result in sharing, so we
       // need to unpack any nested `Top`s. We also need to strip off the
       // `ReferenceValue` associated with the lvalue.
       auto *SubExprVal = maybeUnpackLValueExpr(*SubExpr, Env);
public:
 
   void VisitUnaryOperator(const UnaryOperator *S) {
     const Expr *SubExpr = S->getSubExpr();
     assert(SubExpr != nullptr);
 
     switch (S->getOpcode()) {
     case UO_Deref: {
       const auto *SubExprVal =
-          cast_or_null<PointerValue>(Env.getValue(*SubExpr, SkipPast::None));
+          cast_or_null<PointerValue>(Env.getValueStrict(*SubExpr));
       if (SubExprVal == nullptr)
         break;
 
-      auto &Loc = Env.createStorageLocation(*S);
-      Env.setStorageLocation(*S, Loc);
-      Env.setValue(Loc,
-                   Env.create<ReferenceValue>(SubExprVal->getPointeeLoc()));
+      Env.setStorageLocationStrict(*S, SubExprVal->getPointeeLoc());
       break;
     }
     case UO_AddrOf: {
       // Do not form a pointer to a reference. If `SubExpr` is assigned a
       // `ReferenceValue` then form a value that points to the location of its
       // pointee.
-      StorageLocation *PointeeLoc =
-          Env.getStorageLocation(*SubExpr, SkipPast::Reference);
+      StorageLocation *PointeeLoc = Env.getStorageLocationStrict(*SubExpr);
       if (PointeeLoc == nullptr)
         break;
 
-      auto &PointerLoc = Env.createStorageLocation(*S);
-      auto &PointerVal = Env.create<PointerValue>(*PointeeLoc);
-      Env.setStorageLocation(*S, PointerLoc);
-      Env.setValue(PointerLoc, PointerVal);
+      Env.setValueStrict(*S, Env.create<PointerValue>(*PointeeLoc));
       break;
     }
     case UO_LNot: {
       auto *SubExprVal =
           dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr, SkipPast::None));
       if (SubExprVal == nullptr)
         break;
 

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

TerminatorVisitorRetTy extendFlowCondition(const Expr &Cond) {
     // suffice.
     auto *Val =
         cast_or_null<BoolValue>(Env.getValue(Cond, SkipPast::Reference));
     // Value merging depends on flow conditions from different environments
     // being mutually exclusive -- that is, they cannot both be true in their
     // entirety (even if they may share some clauses). So, we need *some* value
     // for the condition expression, even if just an atom.
     if (Val == nullptr) {
-      // FIXME: Consider introducing a helper for this get-or-create pattern.
-      auto *Loc = Env.getStorageLocation(Cond, SkipPast::None);
-      if (Loc == nullptr) {
-        Loc = &Env.createStorageLocation(Cond);
-        Env.setStorageLocation(Cond, *Loc);
-      }
       Val = &Env.makeAtomicBoolValue();
-      Env.setValue(*Loc, *Val);
+      Env.setValueStrict(Cond, *Val);
     }
 
     bool ConditionValue = true;
     // The condition must be inverted for the successor that encompasses the
     // "else" branch, if such exists.
     if (BlockSuccIdx == 1) {
       Val = &Env.makeNot(*Val);
       ConditionValue = false;