[clang][dataflow] Don't associate prvalue expressions with storage locations.

[mboehme]

Summary

Instead, map prvalue expressions directly to values in a newly introduced map Environment::ExprToVal.

This change introduces an additional member variable in Environment but is an overall win:

• It is more conceptually correctly, since prvalues don't have storage locations.

• It eliminates complexity from Environment::setValue(const Expr &E, Value &Val).

• It reduces the amount of data stored in Environment: A prvalue now has a single entry in ExprToVal instead of one in ExprToLoc and one in LocToVal.

• Not allocating StorageLocations for prvalues additionally reduces memory usage.

This patch is the last step in the migration to strict handling of value categories (see https://discourse.llvm.org/t/70086 for details). The changes here are almost entirely internal to Environment.

The only externally observable change is that when associating a RecordValue with the location returned by Environment::getResultObjectLocation() for a given expression, callers additionally need to associate the RecordValue with the expression themselves.

[xazax.hun]

Thanks! Sometimes I am wondering whether we actually need a full map for PRValues. E.g., once we processed a MaterializeTemporaryExpr, we now have a location for the value, and it feels like we represent the same thing twice, once in ExprToLoc + LocToVal and once in ExprToVal. It is probably not too bad and might be extra work to clean this up.

[mboehme]

In D158977#4623402, @xazax.hun wrote:

Thanks! Sometimes I am wondering whether we actually need a full map for PRValues. E.g., once we processed a MaterializeTemporaryExpr, we now have a location for the value, and it feels like we represent the same thing twice, once in ExprToLoc + LocToVal and once in ExprToVal. It is probably not too bad and might be extra work to clean this up.

Yes, I think it's probably not worth it. (And note that the Exprs in question are different: In the ExprToVal, we map the prvalue expression to a value, whereas in ExprToLoc, we map the MaterializeTemporaryExpr to a location.)

I'd say this is just one example of the more general case when a prvalue is consumed by some other expression. For example, when two prvalue integer operands are consumed by a + BinaryOperator, we could also say that the entries in ExprToVal for the operands are now superfluous and could be removed -- but we still keep them around. They might be superfluous, but there aren't typically enough of them to hurt performance (I think?). And they may be useful for debugging.

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

private:
   Value *ReturnVal = nullptr;
   // Storage location of the reference returned by the function (if it has
   // reference return type).
   StorageLocation *ReturnLoc = nullptr;
   // The storage location of the `this` pointee. Should only be null if the
   // function being analyzed is only a function and not a method.
   RecordStorageLocation *ThisPointeeLoc = nullptr;
 
-  // Maps from program declarations and statements to storage locations that are
+  // Maps from declarations and glvalue expression to storage locations that are
   // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these
   // include only storage locations that are in scope for a particular basic
   // block.
   llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
   llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
+  // Maps from prvalue expressions and storage locations to the values that
+  // are assigned to them.
   // We preserve insertion order so that join/widen process values in
   // deterministic sequence. This in turn produces deterministic SAT formulas.
+  llvm::MapVector<const Expr *, Value *> ExprToVal;
   llvm::MapVector<const StorageLocation *, Value *> LocToVal;
 
   Atom 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

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

static Value &widenDistinctValues(QualType Type, Value &Prev,
   // Custom-model widening.
   if (auto *W = Model.widen(Type, Prev, PrevEnv, Current, CurrentEnv))
     return *W;
 
   // Default of widening is a no-op: leave the current value unchanged.
   return Current;
 }
 
+// Returns whether the values in `Map1` and `Map2` compare equal for those
+// keys that `Map1` and `Map2` have in common.
+template <typename Key>
+bool compareKeyToValueMaps(const llvm::MapVector<Key, Value *> &Map1,
+                           const llvm::MapVector<Key, Value *> &Map2,
+                           const Environment &Env1, const Environment &Env2,
+                           Environment::ValueModel &Model) {
+  for (auto &Entry : Map1) {
+    Key K = Entry.first;
+    assert(K != nullptr);
+
+    Value *Val = Entry.second;
+    assert(Val != nullptr);
+
+    auto It = Map2.find(K);
+    if (It == Map2.end())
+      continue;
+    assert(It->second != nullptr);
+
+    if (!areEquivalentValues(*Val, *It->second) &&
+        !compareDistinctValues(K->getType(), *Val, Env1, *It->second, Env2,
+                               Model))
+      return false;
+  }
+
+  return true;
+}
+
+// Perform a join on either `LocToVal` or `ExprToVal`. `Key` must be either
+// `const StorageLocation *` or `const Expr *`.
+template <typename Key>
+llvm::MapVector<Key, Value *>
+joinKeyToValueMap(const llvm::MapVector<Key, Value *> &Map1,
+                  const llvm::MapVector<Key, Value *> &Map2,
+                  const Environment &Env1, const Environment &Env2,
+                  Environment &JoinedEnv, Environment::ValueModel &Model) {
+  llvm::MapVector<Key, Value *> MergedMap;
+  for (auto &Entry : Map1) {
+    Key K = Entry.first;
+    assert(K != nullptr);
+
+    Value *Val = Entry.second;
+    assert(Val != nullptr);
+
+    auto It = Map2.find(K);
+    if (It == Map2.end())
+      continue;
+    assert(It->second != nullptr);
+
+    if (areEquivalentValues(*Val, *It->second)) {
+      MergedMap.insert({K, Val});
+      continue;
+    }
+
+    if (Value *MergedVal = mergeDistinctValues(
+            K->getType(), *Val, Env1, *It->second, Env2, JoinedEnv, Model)) {
+      MergedMap.insert({K, MergedVal});
+    }
+  }
+
+  return MergedMap;
+}
+
+// Perform widening on either `LocToVal` or `ExprToVal`. `Key` must be either
+// `const StorageLocation *` or `const Expr *`.
+template <typename Key>
+llvm::MapVector<Key, Value *>
+widenKeyToValueMap(const llvm::MapVector<Key, Value *> &CurMap,
+                   const llvm::MapVector<Key, Value *> &PrevMap,
+                   Environment &CurEnv, const Environment &PrevEnv,
+                   Environment::ValueModel &Model, LatticeJoinEffect &Effect) {
+  llvm::MapVector<Key, Value *> WidenedMap;
+  for (auto &Entry : CurMap) {
+    Key K = Entry.first;
+    assert(K != nullptr);
+
+    Value *Val = Entry.second;
+    assert(Val != nullptr);
+
+    auto PrevIt = PrevMap.find(K);
+    if (PrevIt == PrevMap.end())
+      continue;
+    assert(PrevIt->second != nullptr);
+
+    if (areEquivalentValues(*Val, *PrevIt->second)) {
+      WidenedMap.insert({K, Val});
+      continue;
+    }
+
+    Value &WidenedVal = widenDistinctValues(K->getType(), *PrevIt->second,
+                                            PrevEnv, *Val, CurEnv, Model);
+    WidenedMap.insert({K, &WidenedVal});
+    if (&WidenedVal != PrevIt->second)
+      Effect = LatticeJoinEffect::Changed;
+  }
+
+  return WidenedMap;
+}
+
 /// Initializes a global storage value.
 static void insertIfGlobal(const Decl &D,
                            llvm::DenseSet<const VarDecl *> &Vars) {
   if (auto *V = dyn_cast<VarDecl>(&D))
     if (V->hasGlobalStorage())
       Vars.insert(V);
 }
 
void Environment::pushCallInternal(const FunctionDecl *FuncDecl,
   for (unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) {
     assert(ParamIt != FuncDecl->param_end());
     const VarDecl *Param = *ParamIt;
     setStorageLocation(*Param, createObject(*Param, Args[ArgIndex]));
   }
 }
 
 void Environment::popCall(const CallExpr *Call, const Environment &CalleeEnv) {
-  // We ignore `DACtx` because it's already the same in both. We don't want the
-  // callee's `DeclCtx`, `ReturnVal`, `ReturnLoc` or `ThisPointeeLoc`. We don't
-  // bring back `DeclToLoc` and `ExprToLoc` because we want to be able to later
-  // analyze the same callee in a different context, and `setStorageLocation`
-  // requires there to not already be a storage location assigned. Conceptually,
-  // these maps capture information from the local scope, so when popping that
-  // scope, we do not propagate the maps.
+  // We ignore some entries of `CalleeEnv`:
+  // - `DACtx` because is already the same in both
+  // - We don't want the callee's `DeclCtx`, `ReturnVal`, `ReturnLoc` or
+  //   `ThisPointeeLoc` because they don't apply to us.
+  // - `DeclToLoc`, `ExprToLoc`, and `ExprToVal` capture information from the
+  //   callee's local scope, so when popping that scope, we do not propagate
+  //   the maps.
   this->LocToVal = std::move(CalleeEnv.LocToVal);
   this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
 
   if (Call->isGLValue()) {
     if (CalleeEnv.ReturnLoc != nullptr)
       setStorageLocation(*Call, *CalleeEnv.ReturnLoc);
   } else if (!Call->getType()->isVoidType()) {
     if (CalleeEnv.ReturnVal != nullptr)
if (ThisPointeeLoc != Other.ThisPointeeLoc)
     return false;
 
   if (DeclToLoc != Other.DeclToLoc)
     return false;
 
   if (ExprToLoc != Other.ExprToLoc)
     return false;
 
-  // Compare the contents for the intersection of their domains.
-  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())
-      continue;
-    assert(It->second != nullptr);
+  if (!compareKeyToValueMaps(ExprToVal, Other.ExprToVal, *this, Other, Model))
+    return false;
 
-    if (!areEquivalentValues(*Val, *It->second) &&
-        !compareDistinctValues(Loc->getType(), *Val, *this, *It->second, Other,
-                               Model))
-      return false;
-  }
+  if (!compareKeyToValueMaps(LocToVal, Other.LocToVal, *this, Other, Model))
 
   return true;
 }
 
 LatticeJoinEffect Environment::widen(const Environment &PrevEnv,
                                      Environment::ValueModel &Model) {
   assert(DACtx == PrevEnv.DACtx);
   assert(ReturnVal == PrevEnv.ReturnVal);
   assert(ReturnLoc == PrevEnv.ReturnLoc);
   assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc);
   assert(CallStack == PrevEnv.CallStack);
 
   auto Effect = LatticeJoinEffect::Unchanged;
 
   // By the API, `PrevEnv` is a previous version of the environment for the same
   // block, so we have some guarantees about its shape. In particular, it will
   // be the result of a join or widen operation on previous values for this
-  // block. For `DeclToLoc` and `ExprToLoc`, join guarantees that these maps are
-  // subsets of the maps in `PrevEnv`. So, as long as we maintain this property
-  // here, we don't need change their current values to widen.
+  // block. For `DeclToLoc`, `ExprToVal`, and `ExprToLoc`, join guarantees that
+  // these maps are subsets of the maps in `PrevEnv`. So, as long as we maintain
+  // this property here, we don't need change their current values to widen.
   assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size());
+  assert(ExprToVal.size() <= PrevEnv.ExprToVal.size());
   assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size());
 
-  llvm::MapVector<const StorageLocation *, Value *> WidenedLocToVal;
-  for (auto &Entry : LocToVal) {
-    const StorageLocation *Loc = Entry.first;
-    assert(Loc != nullptr);
-
-    Value *Val = Entry.second;
-    assert(Val != nullptr);
-
-    auto PrevIt = PrevEnv.LocToVal.find(Loc);
-    if (PrevIt == PrevEnv.LocToVal.end())
-      continue;
-    assert(PrevIt->second != nullptr);
-
-    if (areEquivalentValues(*Val, *PrevIt->second)) {
-      WidenedLocToVal.insert({Loc, Val});
-      continue;
-    }
+  ExprToVal = widenKeyToValueMap(ExprToVal, PrevEnv.ExprToVal, *this, PrevEnv,
+                                 Model, Effect);
 
-    Value &WidenedVal = widenDistinctValues(Loc->getType(), *PrevIt->second,
-                                            PrevEnv, *Val, *this, Model);
-    WidenedLocToVal.insert({Loc, &WidenedVal});
-    if (&WidenedVal != PrevIt->second)
-      Effect = LatticeJoinEffect::Changed;
-  }
-  LocToVal = std::move(WidenedLocToVal);
+  LocToVal = widenKeyToValueMap(LocToVal, PrevEnv.LocToVal, *this, PrevEnv,
+                                Model, Effect);
   if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() ||
       ExprToLoc.size() != PrevEnv.ExprToLoc.size() ||
+      ExprToVal.size() != PrevEnv.ExprToVal.size() ||
       LocToVal.size() != PrevEnv.LocToVal.size())
     Effect = LatticeJoinEffect::Changed;
 
   return Effect;
 }
 
 Environment Environment::join(const Environment &EnvA, const Environment &EnvB,
                               Environment::ValueModel &Model) {
Environment Environment::join(const Environment &EnvA, const Environment &EnvB,
 
   JoinedEnv.ExprToLoc = intersectDenseMaps(EnvA.ExprToLoc, EnvB.ExprToLoc);
 
   // FIXME: update join to detect backedges and simplify the flow condition
   // accordingly.
   JoinedEnv.FlowConditionToken = EnvA.DACtx->joinFlowConditions(
       EnvA.FlowConditionToken, EnvB.FlowConditionToken);
 
-  for (auto &Entry : EnvA.LocToVal) {
-    const StorageLocation *Loc = Entry.first;
-    assert(Loc != nullptr);
-
-    Value *Val = Entry.second;
-    assert(Val != nullptr);
-
-    auto It = EnvB.LocToVal.find(Loc);
-    if (It == EnvB.LocToVal.end())
-      continue;
-    assert(It->second != nullptr);
-
-    if (areEquivalentValues(*Val, *It->second)) {
-      JoinedEnv.LocToVal.insert({Loc, Val});
-      continue;
-    }
+  JoinedEnv.ExprToVal = joinKeyToValueMap(EnvA.ExprToVal, EnvB.ExprToVal, EnvA,
+                                          EnvB, JoinedEnv, Model);
 
-    if (Value *MergedVal = mergeDistinctValues(
-            Loc->getType(), *Val, EnvA, *It->second, EnvB, JoinedEnv, Model)) {
-      JoinedEnv.LocToVal.insert({Loc, MergedVal});
-    }
-  }
+  JoinedEnv.LocToVal = joinKeyToValueMap(EnvA.LocToVal, EnvB.LocToVal, EnvA,
+                                         EnvB, JoinedEnv, Model);
 
   return JoinedEnv;
 }
 
 StorageLocation &Environment::createStorageLocation(QualType Type) {
   return DACtx->createStorageLocation(Type);
 }
 

 void Environment::setValue(const StorageLocation &Loc, Value &Val) {
   assert(!isa<RecordValue>(&Val) || &cast<RecordValue>(&Val)->getLoc() == &Loc);
 
   LocToVal[&Loc] = &Val;
 }
 
 void Environment::setValue(const Expr &E, Value &Val) {
   assert(E.isPRValue());
-
-  if (auto *RecordVal = dyn_cast<RecordValue>(&Val)) {
-    if ([[maybe_unused]] auto *ExistingVal =
-            cast_or_null<RecordValue>(getValue(E)))
-      assert(&ExistingVal->getLoc() == &RecordVal->getLoc());
-    if ([[maybe_unused]] StorageLocation *ExistingLoc =
-            getStorageLocationInternal(E))
-      assert(ExistingLoc == &RecordVal->getLoc());
-    else
-      setStorageLocationInternal(E, RecordVal->getLoc());
-    setValue(RecordVal->getLoc(), Val);
-    return;
-  }
-
-  StorageLocation *Loc = getStorageLocationInternal(E);
-  if (Loc == nullptr) {
-    Loc = &createStorageLocation(E);
-    setStorageLocationInternal(E, *Loc);
-  }
-  setValue(*Loc, Val);
+  ExprToVal[&E] = &Val;
 }
 
 Value *Environment::getValue(const StorageLocation &Loc) const {
   return LocToVal.lookup(&Loc);
 }
 
 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) const {
+  if (E.isPRValue()) {
+    auto It = ExprToVal.find(&ignoreCFGOmittedNodes(E));
+    return It == ExprToVal.end() ? nullptr : It->second;
+  }
+
   auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
   if (It == ExprToLoc.end())
     return nullptr;
   return getValue(*It->second);
 }
 
 Value *Environment::createValue(QualType Type) {
   llvm::DenseSet<QualType> Visited;
void Environment::dump(raw_ostream &OS) const {
   OS << "DeclToLoc:\n";
   for (auto [D, L] : DeclToLoc)
     OS << "  [" << D->getNameAsString() << ", " << L << "]\n";
 
   OS << "ExprToLoc:\n";
   for (auto [E, L] : ExprToLoc)
     OS << "  [" << E << ", " << L << "]\n";
 
+  OS << "ExprToVal:\n";
+  for (auto [E, V] : ExprToVal)
+    OS << "  [" << E << ", " << V << "]\n";
+
   OS << "LocToVal:\n";
   for (auto [L, V] : LocToVal) {
     OS << "  [" << L << ", " << V << ": " << *V << "]\n";
   }
 
   OS << "FlowConditionToken:\n";
   DACtx->dumpFlowCondition(FlowConditionToken, OS);
 }

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

if (auto *Loc = maybeInitializeOptionalValueMember(
       State.Env.setValue(*UnwrapExpr, State.Env.create<PointerValue>(*Loc));
     }
   }
 }
 
 void transferMakeOptionalCall(const CallExpr *E,
                               const MatchFinder::MatchResult &,
                               LatticeTransferState &State) {
-  createOptionalValue(State.Env.getResultObjectLocation(*E),
-                      State.Env.getBoolLiteralValue(true), State.Env);
+  State.Env.setValue(
+      *E, createOptionalValue(State.Env.getResultObjectLocation(*E),
+                              State.Env.getBoolLiteralValue(true), State.Env));
 }
 
 void transferOptionalHasValueCall(const CXXMemberCallExpr *CallExpr,
                                   const MatchFinder::MatchResult &,
                                   LatticeTransferState &State) {
   if (auto *HasValueVal = getHasValue(
           State.Env, getValueBehindPossiblePointer(
                          *CallExpr->getImplicitObjectArgument(), State.Env))) {
void transferCallReturningOptional(const CallExpr *E,
   } else {
     Loc = cast_or_null<RecordStorageLocation>(State.Env.getStorageLocation(*E));
     if (Loc == nullptr) {
       Loc = &cast<RecordStorageLocation>(State.Env.createStorageLocation(*E));
       State.Env.setStorageLocation(*E, *Loc);
     }
   }
 
+  RecordValue &Val =
       createOptionalValue(*Loc, State.Env.makeAtomicBoolValue(), State.Env);
+  if (E->isPRValue())
+    State.Env.setValue(*E, Val);
 }
 
 void constructOptionalValue(const Expr &E, Environment &Env,
                             BoolValue &HasValueVal) {
   RecordStorageLocation &Loc = Env.getResultObjectLocation(E);
   Env.setValue(E, createOptionalValue(Loc, HasValueVal, Env));
 }
 

clang/lib/Analysis/FlowSensitive/Transfer.cpp

if (ConstructorDecl->isCopyOrMoveConstructor()) {
       return;
     }
 
     // `CXXConstructExpr` can have array type if default-initializing an array
     // of records, and we currently can't create values for arrays. So check if
     // we've got a record type.
     if (S->getType()->isRecordType()) {
       auto &InitialVal = *cast<RecordValue>(Env.createValue(S->getType()));
+      Env.setValue(*S, InitialVal);
       copyRecord(InitialVal.getLoc(), Env.getResultObjectLocation(*S), Env);
     }
 
     transferInlineCall(S, ConstructorDecl);
   }
 
   void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) {
     if (S->getOperator() == OO_Equal) {