[clang][dataflow][WIP] Prototype for pointer value widening ("unknown storage location" flavor)

[mboehme]

Summary

DO NOT REVIEW

This is a WIP for discussion only.

[mboehme]

Added comment on self-referential data structurs.

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h

public:
   StorageLocation &createStorageLocation(QualType Type);
 
   /// Returns a stable storage location for `D`.
   StorageLocation &getStableStorageLocation(const VarDecl &D);
 
   /// Returns a stable storage location for `E`.
   StorageLocation &getStableStorageLocation(const Expr &E);
 
+  StorageLocation &getUnknownStorageLocation(QualType Ty);
+
+  bool isUnknownStorageLocation(const StorageLocation &Loc) const;
+
   /// Assigns `Loc` as the storage location of `D`.
   ///
   /// Requirements:
   ///
   ///  `D` must not be assigned a storage location.
   void setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
     assert(!DeclToLoc.contains(&D));
     DeclToLoc[&D] = &Loc;
private:
   //
   // FIXME: The pointer values are indexed by the pointee types which are
   // required to initialize the `PointeeLoc` field in `PointerValue`. Consider
   // creating a type-independent `NullPointerValue` without a `PointeeLoc`
   // field.
   llvm::DenseMap<QualType, PointerValue *, NullableQualTypeDenseMapInfo>
       NullPointerVals;
 
+  llvm::DenseMap<QualType, StorageLocation *> UnknownStorageLocations;
+
   Options Opts;
 
   // Flow conditions are tracked symbolically: each unique flow condition is
   // associated with a fresh symbolic variable (token), bound to the clause that
   // defines the flow condition. Conceptually, each binding corresponds to an
   // "iff" of the form `FC <=> (C1 ^ C2 ^ ...)` where `FC` is a flow condition
   // token (an atomic boolean) and `Ci`s are the set of constraints in the flow
   // flow condition clause. The set of constraints (C1 ^ C2 ^ ...) are stored in

clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

 DataflowAnalysisContext::getStableStorageLocation(const Expr &E) {
   if (auto *Loc = getStorageLocation(E))
     return *Loc;
   auto &Loc = createStorageLocation(E.getType());
   setStorageLocation(E, Loc);
   return Loc;
 }
 
+StorageLocation &
+DataflowAnalysisContext::getUnknownStorageLocation(QualType Ty) {
+  // FIXME: Deal with self-referential data structures correctly.
+  // e.g. `struct S { S& s; };` will currently cause an infinite loop in this
+  // function, I think.
+  auto Res = UnknownStorageLocations.try_emplace(Ty, nullptr);
+  if (Res.second) {
+    if (!Ty.isNull() && Ty->isRecordType()) {
+      llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
+      for (const FieldDecl *Field : getModeledFields(Ty))
+        FieldLocs.insert({Field, &getUnknownStorageLocation(
+                                     Field->getType().getNonReferenceType())});
+      Res.first->second =
+          &arena().create<RecordStorageLocation>(Ty, std::move(FieldLocs));
+    } else {
+      Res.first->second = &arena().create<ScalarStorageLocation>(Ty);
+    }
+  }
+  return *Res.first->second;
+}
+
+bool DataflowAnalysisContext::isUnknownStorageLocation(
+    const StorageLocation &Loc) const {
+  auto Iter = UnknownStorageLocations.find(Loc.getType());
+  if (Iter == UnknownStorageLocations.end())
+    return false;
+  return Iter->second == &Loc;
+}
+
 PointerValue &
 DataflowAnalysisContext::getOrCreateNullPointerValue(QualType PointeeType) {
   auto CanonicalPointeeType =
       PointeeType.isNull() ? PointeeType : PointeeType.getCanonicalType();
   auto Res = NullPointerVals.try_emplace(CanonicalPointeeType, nullptr);
   if (Res.second) {
     auto &PointeeLoc = createStorageLocation(CanonicalPointeeType);
     Res.first->second = &arena().create<PointerValue>(PointeeLoc);

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

if (isa<BoolValue>(&Prev)) {
     assert(isa<BoolValue>(Current));
     // Widen to Top, because we know they are different values. If previous was
     // already Top, re-use that to (implicitly) indicate that no change occured.
     if (isa<TopBoolValue>(Prev))
       return Prev;
     return CurrentEnv.makeTopBoolValue();
   }
 
+  if (auto *PrevPtr = dyn_cast<PointerValue>(&Prev)) {
+    auto &CurPtr = cast<PointerValue>(Current);
+
+    if (&PrevPtr->getPointeeLoc() != &CurPtr.getPointeeLoc())
+      // TODO: Widen properties
+      return CurrentEnv.create<PointerValue>(
+          CurrentEnv.getDataflowAnalysisContext().getUnknownStorageLocation(
+              CurPtr.getPointeeLoc().getType()));
+  }
+
   // FIXME: Add other built-in model widening.
 
   // 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;

 
 PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) {
   return DACtx->getOrCreateNullPointerValue(PointeeType);
 }
 
 void Environment::setValue(const StorageLocation &Loc, Value &Val) {
   assert(!isa<RecordValue>(&Val) || &cast<RecordValue>(&Val)->getLoc() == &Loc);
 
+  // TODO: Currently, if `Loc` is an unknown storage location, just bail out.
+  // But is this the right thing to do?
+  // Alternatives:
+  // - Assert that `Loc` is not an unknown storage location. But then that
+  //   potentially puts the burden of testing on the caller. And what else would
+  //   they do except not set the value?
+  // - Because the unknown storage location is conceptually a "top", it
+  //   effectively refers to the set of _all_ possible storage locations. So,
+  //   because we could be potentially setting the value of any storage,
+  //   maybe we should blow away _all_ of the entries in `LocToVal`? Or at least
+  //   those whose type is one that is compatible with `Loc` in the sense that
+  //   it can refer to a value of type `Loc.getType()`?
+  if (getDataflowAnalysisContext().isUnknownStorageLocation(Loc))
+    return;
   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 =
void Environment::setValue(const Expr &E, Value &Val) {
   if (Loc == nullptr) {
     Loc = &createStorageLocation(E);
     setStorageLocationInternal(E, *Loc);
   }
   setValue(*Loc, Val);
 }
 
 Value *Environment::getValue(const StorageLocation &Loc) const {
+  if (getDataflowAnalysisContext().isUnknownStorageLocation(Loc))
+    return nullptr;
   return LocToVal.lookup(&Loc);
 }
 
 Value *Environment::getValue(const ValueDecl &D) const {
   auto *Loc = getStorageLocation(D);
   if (Loc == nullptr)
     return nullptr;
   return getValue(*Loc);

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

void target(int i1, int i2) {
         (void)*p;
         if (some_condition())
           p = &i1;
         else
           p = &i2;
       }
     }
   )cc";
-  // FIXME: Implement pointer value widening to make analysis converge.
-  ASSERT_THAT_ERROR(
-      checkDataflowWithNoopAnalysis(Code),
-      llvm::FailedWithMessage("maximum number of iterations reached"));
+  ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded());
 }
 
 TEST(TransferTest, LoopDereferencingChangingRecordPointerConverges) {
   std::string Code = R"cc(
     struct Lookup {
       int x;
     };
 
     bool some_condition();
 
     void target(Lookup l1, Lookup l2) {
       Lookup *l = &l1;
       while (true) {
         (void)l->x;
         if (some_condition())
           l = &l1;
         else
           l = &l2;
       }
     }
   )cc";
-  // FIXME: Implement pointer value widening to make analysis converge.
-  ASSERT_THAT_ERROR(
-      checkDataflowWithNoopAnalysis(Code),
-      llvm::FailedWithMessage("maximum number of iterations reached"));
+  ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded());
 }
 
 TEST(TransferTest, DoesNotCrashOnUnionThisExpr) {
   std::string Code = R"(
     union Union {
       int A;
       float B;
     };