[clang][dataflow] Eliminate `SkipPast::ReferenceThenPointer`.

[mboehme]

Summary

As a replacement, we provide the accessors getImplicitObjectLocation() and
getBaseObjectLocation(), which are higher-level constructs that cover the use
cases in which SkipPast::ReferenceThenPointer was typically used.

Unfortunately, it isn't possible to use these accessors in
UncheckedOptionalAccessModel.cpp; I've added a FIXME to the code explaining the
details. I initially attempted to resolve the issue as part of this patch, but
it turned out to be non-trivial to fix. Instead, I have therefore added a
lower-level replacement for SkipPast::ReferenceThenPointer that is used only
within this file.

The wider context of this change is that SkipPast will be going away entirely.
See also the RFC at https://discourse.llvm.org/t/70086.

[mboehme]

Rebase to head

[ymandel]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

840

nit: no need for else since if branch always returns

[mboehme]

Eliminate unnecessary else.

[mboehme]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

840

Good point -- done. (Also below.)

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

 ///
 /// 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.
   Reference,
-  /// An optional reference should be skipped past, then an optional pointer
-  /// should be skipped past.
-  ReferenceThenPointer,
 };
 
 /// Indicates the result of a tentative comparison.
 enum class ComparisonResult {
   Same,
   Different,
   Unknown,
 };
private:
   // them and the decls of the struct members.
   llvm::DenseMap<const StorageLocation *,
                  std::pair<StructValue *, const ValueDecl *>>
       MemberLocToStruct;
 
   AtomicBoolValue *FlowConditionToken;
 };
 
+/// Returns the storage location for the implicit object of a
+/// `CXXMemberCallExpr`, or null if none is defined in the environment.
+/// Dereferences the pointer if the member call expression was written using
+/// `->`.
+AggregateStorageLocation *
+getImplicitObjectLocation(const CXXMemberCallExpr &MCE, const Environment &Env);
+
+/// Returns the storage location for the base object of a `MemberExpr`, or null
+/// if none is defined in the environment. Dereferences the pointer if the
+/// member expression was written using `->`.
+AggregateStorageLocation *getBaseObjectLocation(const MemberExpr &ME,
+                                                const Environment &Env);
+
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

StorageLocation &Environment::skip(StorageLocation &Loc, SkipPast SP) const {
   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;
-  case SkipPast::ReferenceThenPointer:
-    StorageLocation &LocPastRef = skip(Loc, SkipPast::Reference);
-    if (auto *Val = dyn_cast_or_null<PointerValue>(getValue(LocPastRef)))
-      return Val->getPointeeLoc();
-    return LocPastRef;
   }
   llvm_unreachable("bad SkipPast kind");
 }
 
 const StorageLocation &Environment::skip(const StorageLocation &Loc,
                                          SkipPast SP) const {
   return skip(*const_cast<StorageLocation *>(&Loc), SP);
 }
void Environment::dump(raw_ostream &OS) const {
   OS << "FlowConditionToken:\n";
   DACtx->dumpFlowCondition(*FlowConditionToken, OS);
 }
 
 void Environment::dump() const {
   dump(llvm::dbgs());
 }
 
+AggregateStorageLocation *
+getImplicitObjectLocation(const CXXMemberCallExpr &MCE,
+                          const Environment &Env) {
+  Expr *ImplicitObject = MCE.getImplicitObjectArgument();
+  if (ImplicitObject == nullptr)
+    return nullptr;
+  StorageLocation *Loc =
+      Env.getStorageLocation(*ImplicitObject, SkipPast::Reference);
+  if (Loc == nullptr)
+    return nullptr;
+  if (ImplicitObject->getType()->isPointerType()) {
+    if (auto *Val = cast_or_null<PointerValue>(Env.getValue(*Loc)))
+      return &cast<AggregateStorageLocation>(Val->getPointeeLoc());
+    return nullptr;
+  }
+  return cast<AggregateStorageLocation>(Loc);
+}
+
+AggregateStorageLocation *getBaseObjectLocation(const MemberExpr &ME,
+                                                const Environment &Env) {
+  Expr *Base = ME.getBase();
+  if (Base == nullptr)
+    return nullptr;
+  StorageLocation *Loc = Env.getStorageLocation(*Base, SkipPast::Reference);
+  if (Loc == nullptr)
+    return nullptr;
+  if (ME.isArrow()) {
+    if (auto *Val = cast_or_null<PointerValue>(Env.getValue(*Loc)))
+      return &cast<AggregateStorageLocation>(Val->getPointeeLoc());
+    return nullptr;
+  }
+  return cast<AggregateStorageLocation>(Loc);
+}
+
 } // namespace dataflow
 } // namespace clang

clang/lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp

 /// Returns true if and only if `OptionalVal` is initialized and known to be
 /// non-empty in `Env.
 bool isNonEmptyOptional(const Value &OptionalVal, const Environment &Env) {
   auto *HasValueVal =
       cast_or_null<BoolValue>(OptionalVal.getProperty("has_value"));
   return HasValueVal != nullptr && Env.flowConditionImplies(*HasValueVal);
 }
 
+StorageLocation *maybeSkipPointer(StorageLocation *Loc,
+                                  const Environment &Env) {
+  if (Loc == nullptr)
+    return nullptr;
+  if (auto *Val = dyn_cast_or_null<PointerValue>(Env.getValue(*Loc)))
+    return &Val->getPointeeLoc();
+  return Loc;
+}
+
+Value *getValueBehindPossiblePointer(const Expr &E, const Environment &Env) {
+  Value *Val = Env.getValue(E, SkipPast::Reference);
+  if (auto *PointerVal = dyn_cast_or_null<PointerValue>(Val))
+    return Env.getValue(PointerVal->getPointeeLoc());
+  return Val;
+}
+
 void transferUnwrapCall(const Expr *UnwrapExpr, const Expr *ObjectExpr,
                         LatticeTransferState &State) {
   if (auto *OptionalVal =
-          State.Env.getValue(*ObjectExpr, SkipPast::ReferenceThenPointer)) {
+          getValueBehindPossiblePointer(*ObjectExpr, State.Env)) {
     if (State.Env.getStorageLocation(*UnwrapExpr, SkipPast::None) == nullptr)
       if (auto *Loc = maybeInitializeOptionalValueMember(
               UnwrapExpr->getType(), *OptionalVal, State.Env))
         State.Env.setStorageLocation(*UnwrapExpr, *Loc);
   }
 }
 
 void transferMakeOptionalCall(const CallExpr *E,
                               const MatchFinder::MatchResult &,
                               LatticeTransferState &State) {
   auto &Loc = State.Env.createStorageLocation(*E);
   State.Env.setStorageLocation(*E, Loc);
   State.Env.setValue(
       Loc, createOptionalValue(State.Env, State.Env.getBoolLiteralValue(true)));
 }
 
 void transferOptionalHasValueCall(const CXXMemberCallExpr *CallExpr,
                                   const MatchFinder::MatchResult &,
                                   LatticeTransferState &State) {
   if (auto *HasValueVal = getHasValue(
-          State.Env, State.Env.getValue(*CallExpr->getImplicitObjectArgument(),
-                                        SkipPast::ReferenceThenPointer))) {
+          State.Env, getValueBehindPossiblePointer(
+                         *CallExpr->getImplicitObjectArgument(), State.Env))) {
     auto &CallExprLoc = State.Env.createStorageLocation(*CallExpr);
     State.Env.setValue(CallExprLoc, *HasValueVal);
     State.Env.setStorageLocation(*CallExpr, CallExprLoc);
   }
 }
 
 /// `ModelPred` builds a logical formula relating the predicate in
 /// `ValueOrPredExpr` to the optional's `has_value` property.
 void transferValueOrImpl(const clang::Expr *ValueOrPredExpr,
                          const MatchFinder::MatchResult &Result,
                          LatticeTransferState &State,
                          BoolValue &(*ModelPred)(Environment &Env,
                                                  BoolValue &ExprVal,
                                                  BoolValue &HasValueVal)) {
   auto &Env = State.Env;
 
   const auto *ObjectArgumentExpr =
       Result.Nodes.getNodeAs<clang::CXXMemberCallExpr>(ValueOrCallID)
           ->getImplicitObjectArgument();
 
   auto *HasValueVal = getHasValue(
-      State.Env,
-      State.Env.getValue(*ObjectArgumentExpr, SkipPast::ReferenceThenPointer));
+      State.Env, getValueBehindPossiblePointer(*ObjectArgumentExpr, State.Env));
   if (HasValueVal == nullptr)
     return;
 
   Env.addToFlowCondition(
       ModelPred(Env, forceBoolValue(Env, *ValueOrPredExpr), *HasValueVal));
 }
 
 void transferValueOrStringEmptyCall(const clang::Expr *ComparisonExpr,
void transferCallReturningOptional(const CallExpr *E,
   auto &Loc = State.Env.createStorageLocation(*E);
   State.Env.setStorageLocation(*E, Loc);
   State.Env.setValue(
       Loc, createOptionalValue(State.Env, State.Env.makeAtomicBoolValue()));
 }
 
 void assignOptionalValue(const Expr &E, Environment &Env,
                          BoolValue &HasValueVal) {
-  if (auto *OptionalLoc =
-          Env.getStorageLocation(E, SkipPast::ReferenceThenPointer)) {
+  if (auto *OptionalLoc = maybeSkipPointer(
+          Env.getStorageLocation(E, SkipPast::Reference), Env)) {
     Env.setValue(*OptionalLoc, createOptionalValue(Env, HasValueVal));
   }
 }
 
 /// Returns a symbolic value for the "has_value" property of an `optional<T>`
 /// value that is constructed/assigned from a value of type `U` or `optional<U>`
 /// where `T` is constructible from `U`.
 BoolValue &valueOrConversionHasValue(const FunctionDecl &F, const Expr &E,

 }
 
 void transferNulloptAssignment(const CXXOperatorCallExpr *E,
                                const MatchFinder::MatchResult &,
                                LatticeTransferState &State) {
   transferAssignment(E, State.Env.getBoolLiteralValue(false), State);
 }
 
-void transferSwap(const Expr &E1, SkipPast E1Skip, const Expr &E2,
+void transferSwap(StorageLocation *Loc1, StorageLocation *Loc2,
                   Environment &Env) {
   // We account for cases where one or both of the optionals are not modeled,
   // either lacking associated storage locations, or lacking values associated
   // to such storage locations.
-  auto *Loc1 = Env.getStorageLocation(E1, E1Skip);
-  auto *Loc2 = Env.getStorageLocation(E2, SkipPast::Reference);
 
   if (Loc1 == nullptr) {
     if (Loc2 != nullptr)
       Env.setValue(*Loc2, createOptionalValue(Env, Env.makeAtomicBoolValue()));
     return;
   }
   if (Loc2 == nullptr) {
     Env.setValue(*Loc1, createOptionalValue(Env, Env.makeAtomicBoolValue()));
void transferSwap(StorageLocation *Loc1, StorageLocation *Loc2,
   Env.setValue(*Loc1, *Val2);
   Env.setValue(*Loc2, *Val1);
 }
 
 void transferSwapCall(const CXXMemberCallExpr *E,
                       const MatchFinder::MatchResult &,
                       LatticeTransferState &State) {
   assert(E->getNumArgs() == 1);
-  transferSwap(*E->getImplicitObjectArgument(), SkipPast::ReferenceThenPointer,
-               *E->getArg(0), State.Env);
+  transferSwap(maybeSkipPointer(
+                   State.Env.getStorageLocation(*E->getImplicitObjectArgument(),
+                                                SkipPast::Reference),
+                   State.Env),
+               State.Env.getStorageLocation(*E->getArg(0), SkipPast::Reference),
+               State.Env);
 }
 
 void transferStdSwapCall(const CallExpr *E, const MatchFinder::MatchResult &,
                          LatticeTransferState &State) {
   assert(E->getNumArgs() == 2);
-  transferSwap(*E->getArg(0), SkipPast::Reference, *E->getArg(1), State.Env);
+  transferSwap(State.Env.getStorageLocation(*E->getArg(0), SkipPast::Reference),
+               State.Env.getStorageLocation(*E->getArg(1), SkipPast::Reference),
+               State.Env);
 }
 
 void transferStdForwardCall(const CallExpr *E, const MatchFinder::MatchResult &,
                             LatticeTransferState &State) {
   assert(E->getNumArgs() == 1);
 
   StorageLocation *LocRet = State.Env.getStorageLocation(*E, SkipPast::None);
   if (LocRet != nullptr)
return CFGMatchSwitchBuilder<LatticeTransferState>()
       .CaseOfCFGStmt<CXXMemberCallExpr>(
           valueCall(std::nullopt),
           [](const CXXMemberCallExpr *E, const MatchFinder::MatchResult &,
              LatticeTransferState &State) {
             transferUnwrapCall(E, E->getImplicitObjectArgument(), State);
           })
 
       // optional::operator*, optional::operator->
+      // FIXME: This does something slightly strange for `operator->`.
+      // `transferUnwrapCall()` may create a new value of type `T` for the
+      // `optional<T>`, and it associates that value with `E`. In the case of
+      // `operator->`, `E` is a pointer. As a result, we associate an
+      // expression of pointer type with a storage location of non-pointer type
+      // `T`. This can confound other code that expects expressions of
+      // pointer type to be associated with `PointerValue`s, such as the
+      // centrally provided accessors `getImplicitObjectLocation()` and
+      // `getBaseObjectLocation()`, and this is the reason we need to use our
+      // own 'maybeSkipPointer()` and `getValueBehindPossiblePointer()` instead
+      // of these accessors.
       .CaseOfCFGStmt<CallExpr>(valueOperatorCall(std::nullopt),
                                [](const CallExpr *E,
                                   const MatchFinder::MatchResult &,
                                   LatticeTransferState &State) {
                                  transferUnwrapCall(E, E->getArg(0), State);
                                })
 
       // optional::has_value
return CFGMatchSwitchBuilder<LatticeTransferState>()
                                transferCallReturningOptional)
 
       .Build();
 }
 
 std::vector<SourceLocation> diagnoseUnwrapCall(const Expr *UnwrapExpr,
                                                const Expr *ObjectExpr,
                                                const Environment &Env) {
-  if (auto *OptionalVal =
-          Env.getValue(*ObjectExpr, SkipPast::ReferenceThenPointer)) {
+  if (auto *OptionalVal = getValueBehindPossiblePointer(*ObjectExpr, Env)) {
     auto *Prop = OptionalVal->getProperty("has_value");
     if (auto *HasValueVal = cast_or_null<BoolValue>(Prop)) {
       if (Env.flowConditionImplies(*HasValueVal))
         return {};
     }
   }
 
   // Record that this unwrap is *not* provably safe.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

if (auto *D = dyn_cast<VarDecl>(Member)) {
         if (VarDeclLoc == nullptr)
           return;
 
         Env.setStorageLocation(*S, *VarDeclLoc);
         return;
       }
     }
 
-    // The receiver can be either a value or a pointer to a value. Skip past the
-    // indirection to handle both cases.
-    auto *BaseLoc = cast_or_null<AggregateStorageLocation>(
-        Env.getStorageLocation(*S->getBase(), SkipPast::ReferenceThenPointer));
+    AggregateStorageLocation *BaseLoc = getBaseObjectLocation(*S, Env);
     if (BaseLoc == nullptr)
       return;
 
     auto &MemberLoc = BaseLoc->getChild(*Member);
     if (MemberLoc.getType()->isReferenceType()) {
       // Based on its type, `MemberLoc` must be mapped either to nothing or to a
       // `ReferenceValue`. For the former, we won't set a storage location for
       // this expression, so as to maintain an invariant lvalue expressions;

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

void transfer(const CFGElement &Elt, NoopLattice &, Environment &Env) {
     } else if (const auto *E = selectFirst<CXXMemberCallExpr>(
                    "call", match(cxxMemberCallExpr(callee(cxxMethodDecl(ofClass(
                                                        SpecialBoolRecordDecl))))
                                      .bind("call"),
                                  *S, getASTContext()))) {
       auto *Object = E->getImplicitObjectArgument();
       assert(Object != nullptr);
 
-      auto *ObjectLoc =
-          Env.getStorageLocation(*Object, SkipPast::ReferenceThenPointer);
+      auto *ObjectLoc = getImplicitObjectLocation(*E, Env);
       assert(ObjectLoc != nullptr);
 
       auto &ConstructorVal = *Env.createValue(Object->getType());
       ConstructorVal.setProperty("is_set", Env.getBoolLiteralValue(true));
       Env.setValue(*ObjectLoc, ConstructorVal);
     }
   }
 
if (const auto *E = selectFirst<CXXConstructExpr>(
       ConstructorVal.setProperty("has_value", Env.getBoolLiteralValue(false));
       Env.setValue(*Env.getStorageLocation(*E, SkipPast::None), ConstructorVal);
     } else if (const auto *E =
                    selectFirst<CXXOperatorCallExpr>("operator", Matches)) {
       assert(E->getNumArgs() > 0);
       auto *Object = E->getArg(0);
       assert(Object != nullptr);
 
-      auto *ObjectLoc =
-          Env.getStorageLocation(*Object, SkipPast::ReferenceThenPointer);
+      auto *ObjectLoc = Env.getStorageLocation(*Object, SkipPast::Reference);
       assert(ObjectLoc != nullptr);
 
       auto &ConstructorVal = *Env.createValue(Object->getType());
       ConstructorVal.setProperty("has_value", Env.getBoolLiteralValue(true));
       Env.setValue(*ObjectLoc, ConstructorVal);
     }
   }