[clang][dataflow] Singleton pointer values for null pointers.

[wyt]

Summary

When a nullptr is assigned to a pointer variable, it is wrapped in a ImplicitCastExpr with cast kind CK_NullTo(Member)Pointer. This patch assigns singleton pointer values representing null to these expressions.

For each pointee type, a singleton null PointerValue is created and stored in the NullPointerVals map of the DataflowAnalysisContext class. The pointee type is retrieved from the implicit cast expression, and used to initialise the PointeeLoc field of the PointerValue. The PointeeLoc created is not mapped to any Value, reflecting the absence of value indicated by null pointers.

[xazax.hun]

I am wondering about the future plans regarding how pointers are represented.
What will be the expected behavior when the analysis discovers that the pointer has a null value? E.g.:

if (p == nullptr)
{
  ....
}

Would we expect p in this case to have the same singleton value in the then block of the if statement?

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

163

Since you always want this function to create a null pointer value, I think it would be less error prone to ask for the location instead of an arbitrary value. Currently, a confused caller could put a non-null value into a table.

166

I think getAsString is considered expensive. Could you use QualType directly as the key?

[wyt]

Use QualType as key to singleton map, implement getOrCreate factory function for retrieving null pointer values.

[wyt]

@xazax.hun

Since you always want this function to create a null pointer value, I think it would be less error prone to ask for the location instead of an arbitrary value. Currently, a confused caller could put a non-null value into a table.

Replaced with a getOrCreate factory to encapsulate pointer value creation.

I think getAsString is considered expensive. Could you use QualType directly as the key?

Done.

I am wondering about the future plans regarding how pointers are represented.
What will be the expected behavior when the analysis discovers that the pointer has a null value? E.g.:

if (p == nullptr)
{
  ....
}

Would we expect p in this case to have the same singleton value in the then block of the if statement?

This is an interesting idea.
IIUC, for non-boolean values, the core framework currently does not dissect the equality expression - p == nullptr would be represented by a symbolic boolean, but p and nullptr would not be entangled together.
However, we are working on a pointer nullability analysis on top of the framework that should add information to interrelate two pointer values and their nullability information when we do a comparison between pointers.

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

163

Since you always want this function to create a null pointer value, I think it would be less error prone to ask for the location instead of an arbitrary value. Currently, a confused caller could put a non-null value into a table.

166

I think getAsString is considered expensive. Could you use QualType directly as the key?

[xazax.hun]

clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

65

Should we have a PointerValue without PointeeLoc to represent null pointers?

[sgatev]

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

156–158

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

318–320

321

Let's move this below getThisPointeeStorageLocation so that it's closer to related members. Same for the cpp file.

[wyt]

Address comments.

[wyt]

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

311–314

@xazax.hun

Should we have a PointerValue without PointeeLoc to represent null pointers?

PointeeLoc is a reference field in the current PointerValue so it is required for now.
Creating an independent NullPointerValue class without PointeeLoc is something we are considering, but in this patch we will be using PointerValues with a PointeeLoc corresponding to the pointee type to represent null pointers.

[gribozavr2]

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

308–309

clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

59

[wyt]

Address comments.

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

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
 
 #include "clang/AST/Decl.h"
 #include "clang/AST/Expr.h"
+#include "clang/AST/TypeOrdering.h"
 #include "clang/Analysis/FlowSensitive/Solver.h"
 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include <cassert>
 #include <memory>
 #include <type_traits>
public:
   }
 
   /// Returns the storage location assigned to the `this` pointee or null if the
   /// `this` pointee has no assigned storage location.
   StorageLocation *getThisPointeeStorageLocation() const {
     return ThisPointeeLoc;
   }
 
+  /// Returns a pointer value that represents a null pointer. Calls with
+  /// `PointeeType` that are canonically equivalent will return the same result.
+  PointerValue &getOrCreateNullPointerValue(QualType PointeeType);
+
   /// Returns a symbolic boolean value that models a boolean literal equal to
   /// `Value`.
   AtomicBoolValue &getBoolLiteralValue(bool Value) const {
     return Value ? TrueVal : FalseVal;
   }
 
   /// Creates an atomic boolean value.
   AtomicBoolValue &createAtomicBoolValue() {
     return takeOwnership(std::make_unique<AtomicBoolValue>());
   }
 
   /// Returns a boolean value that represents the conjunction of `LHS` and
   /// `RHS`. Subsequent calls with the same arguments, regardless of their
   /// order, will return the same result. If the given boolean values represent
   /// the same value, the result will be the value itself.
private:
   // blocks) and are used to produce stable storage locations when the same
   // basic blocks are evaluated multiple times. The storage locations that are
   // in scope for a particular basic block are stored in `Environment`.
   llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
   llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
 
   StorageLocation *ThisPointeeLoc = nullptr;
 
+  // Null pointer values, keyed by the canonical pointee type.
+  //
+  // 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 *> NullPointerVals;
+
   AtomicBoolValue &TrueVal;
   AtomicBoolValue &FalseVal;
 
   // Indices that are used to avoid recreating the same composite boolean
   // values.
   llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, ConjunctionValue *>
       ConjunctionVals;
   llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, DisjunctionValue *>

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

public:
   /// assigned a storage location in the environment.
   StorageLocation *getStorageLocation(const Expr &E, SkipPast SP) 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 a pointer value that represents a null pointer. Calls with
+  /// `PointeeType` that are canonically equivalent will return the same result.
+  PointerValue &getOrCreateNullPointerValue(QualType PointeeType);
+
   /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
   /// return null. If `Type` is a pointer or reference type, creates all the
   /// necessary storage locations and values for indirections until it finds a
   /// non-pointer/non-reference type.
   ///
   /// Requirements:
   ///
   ///  `Type` must not be null.
public:
 
   /// Adds `Val` to the set of clauses that constitute the flow condition.
   void addToFlowCondition(BoolValue &Val);
 
   /// Returns true if and only if the clauses that constitute the flow condition
   /// imply that `Val` is true.
   bool flowConditionImplies(BoolValue &Val) const;
 
 private:
   /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
   /// return null.
   ///
   /// Recursively initializes storage locations and values until it sees a
   /// self-referential pointer or reference type. `Visited` is used to track
   /// which types appeared in the reference/pointer chain in order to avoid
   /// creating a cyclic dependency with self-referential pointers/references.
   ///
   /// Requirements:
   ///
   ///  `Type` must not be null.

clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

 DataflowAnalysisContext::getStableStorageLocation(const Expr &E) {
   if (auto *Loc = getStorageLocation(E))
     return *Loc;
   auto &Loc = getStableStorageLocation(E.getType());
   setStorageLocation(E, Loc);
   return Loc;
 }
 
+PointerValue &
+DataflowAnalysisContext::getOrCreateNullPointerValue(QualType PointeeType) {
+  assert(!PointeeType.isNull());
+  auto CanonicalPointeeType = PointeeType.getCanonicalType();
+  auto Res = NullPointerVals.try_emplace(CanonicalPointeeType, nullptr);
+  if (Res.second) {
+    auto &PointeeLoc = getStableStorageLocation(CanonicalPointeeType);
+    Res.first->second =
+        &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
+  }
+  return *Res.first->second;
+}
+
 static std::pair<BoolValue *, BoolValue *>
 makeCanonicalBoolValuePair(BoolValue &LHS, BoolValue &RHS) {
   auto Res = std::make_pair(&LHS, &RHS);
   if (&RHS < &LHS)
     std::swap(Res.first, Res.second);
   return Res;
 }
 

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

StorageLocation *Environment::getStorageLocation(const Expr &E,
   auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
   return It == ExprToLoc.end() ? nullptr : &skip(*It->second, SP);
 }
 
 StorageLocation *Environment::getThisPointeeStorageLocation() const {
   return DACtx->getThisPointeeStorageLocation();
 }
 
+PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) {
+  return DACtx->getOrCreateNullPointerValue(PointeeType);
+}
+
 void Environment::setValue(const StorageLocation &Loc, Value &Val) {
   LocToVal[&Loc] = &Val;
 
   if (auto *StructVal = dyn_cast<StructValue>(&Val)) {
     auto &AggregateLoc = *cast<AggregateStorageLocation>(&Loc);
 
     const QualType Type = AggregateLoc.getType();
     assert(Type->isStructureOrClassType());

clang/lib/Analysis/FlowSensitive/Transfer.cpp

case CK_NoOp: {
       // assigning them storage locations.
       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
       if (SubExprLoc == nullptr)
         break;
 
       Env.setStorageLocation(*S, *SubExprLoc);
       break;
     }
+    case CK_NullToPointer:
+    case CK_NullToMemberPointer: {
+      auto &Loc = Env.createStorageLocation(S->getType());
+      Env.setStorageLocation(*S, Loc);
+
+      auto &NullPointerVal =
+          Env.getOrCreateNullPointerValue(S->getType()->getPointeeType());
+      Env.setValue(Loc, NullPointerVal);
+      break;
+    }
     default:
       break;
     }
   }
 
   void VisitUnaryOperator(const UnaryOperator *S) {
     const Expr *SubExpr = S->getSubExpr();
     assert(SubExpr != nullptr);

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(Code,
                 const auto *FooVal = Env.getValue(*FooDecl, SkipPast::None);
                 const auto *BarVal = Env.getValue(*BarDecl, SkipPast::None);
                 EXPECT_TRUE(isa<BoolValue>(FooVal));
                 EXPECT_TRUE(isa<BoolValue>(BarVal));
                 EXPECT_EQ(FooVal, BarVal);
               });
 }
 
+TEST_F(TransferTest, NullToPointerCast) {
+  std::string Code = R"(
+    struct Baz {};
+    void target() {
+      int *FooX = nullptr;
+      int *FooY = nullptr;
+      bool **Bar = nullptr;
+      Baz *Baz = nullptr;
+      // [[p]]
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const Environment &Env = Results[0].second.Env;
+
+                const ValueDecl *FooXDecl = findValueDecl(ASTCtx, "FooX");
+                ASSERT_THAT(FooXDecl, NotNull());
+
+                const ValueDecl *FooYDecl = findValueDecl(ASTCtx, "FooY");
+                ASSERT_THAT(FooYDecl, NotNull());
+
+                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                const ValueDecl *BazDecl = findValueDecl(ASTCtx, "Baz");
+                ASSERT_THAT(BazDecl, NotNull());
+
+                const auto *FooXVal =
+                    cast<PointerValue>(Env.getValue(*FooXDecl, SkipPast::None));
+                const auto *FooYVal =
+                    cast<PointerValue>(Env.getValue(*FooYDecl, SkipPast::None));
+                const auto *BarVal =
+                    cast<PointerValue>(Env.getValue(*BarDecl, SkipPast::None));
+                const auto *BazVal =
+                    cast<PointerValue>(Env.getValue(*BazDecl, SkipPast::None));
+
+                EXPECT_EQ(FooXVal, FooYVal);
+                EXPECT_NE(FooXVal, BarVal);
+                EXPECT_NE(FooXVal, BazVal);
+                EXPECT_NE(BarVal, BazVal);
+
+                const StorageLocation &FooPointeeLoc = FooXVal->getPointeeLoc();
+                EXPECT_TRUE(isa<ScalarStorageLocation>(FooPointeeLoc));
+                EXPECT_THAT(Env.getValue(FooPointeeLoc), IsNull());
+
+                const StorageLocation &BarPointeeLoc = BarVal->getPointeeLoc();
+                EXPECT_TRUE(isa<ScalarStorageLocation>(BarPointeeLoc));
+                EXPECT_THAT(Env.getValue(BarPointeeLoc), IsNull());
+
+                const StorageLocation &BazPointeeLoc = BazVal->getPointeeLoc();
+                EXPECT_TRUE(isa<AggregateStorageLocation>(BazPointeeLoc));
+                EXPECT_THAT(Env.getValue(BazPointeeLoc), IsNull());
+              });
+}
+
+TEST_F(TransferTest, NullToMemberPointerCast) {
+  std::string Code = R"(
+    struct Foo {};
+    void target(Foo *Foo) {
+      int Foo::*MemberPointer = nullptr;
+      // [[p]]
+    }
+  )";
+  runDataflow(
+      Code, [](llvm::ArrayRef<
+                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                   Results,
+               ASTContext &ASTCtx) {
+        ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+        const Environment &Env = Results[0].second.Env;
+
+        const ValueDecl *MemberPointerDecl =
+            findValueDecl(ASTCtx, "MemberPointer");
+        ASSERT_THAT(MemberPointerDecl, NotNull());
+
+        const auto *MemberPointerVal = cast<PointerValue>(
+            Env.getValue(*MemberPointerDecl, SkipPast::None));
+
+        const StorageLocation &MemberLoc = MemberPointerVal->getPointeeLoc();
+        EXPECT_THAT(Env.getValue(MemberLoc), IsNull());
+      });
+}
+
 TEST_F(TransferTest, AddrOfValue) {
   std::string Code = R"(
     void target() {
       int Foo;
       int *Bar = &Foo;
       // [[p]]
     }
   )";