From b611376e7eb5ea8bd0b32c2911e039b29828b9a8 Mon Sep 17 00:00:00 2001 From: Wei Yi Tee Date: Mon, 27 Jun 2022 14:14:01 +0200 Subject: [PATCH] [clang][dataflow] Singleton pointer values for null pointers. 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. Reviewed By: gribozavr2, sgatev, xazax.hun Differential Revision: https://reviews.llvm.org/D128056 --- .../FlowSensitive/DataflowAnalysisContext.h | 13 ++++ .../Analysis/FlowSensitive/DataflowEnvironment.h | 4 + .../FlowSensitive/DataflowAnalysisContext.cpp | 13 ++++ .../Analysis/FlowSensitive/DataflowEnvironment.cpp | 4 + clang/lib/Analysis/FlowSensitive/Transfer.cpp | 10 +++ .../Analysis/FlowSensitive/TransferTest.cpp | 87 ++++++++++++++++++++++ 6 files changed, 131 insertions(+) diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h index 2e6b8ea..c1100d8 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h @@ -17,6 +17,7 @@ #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" @@ -152,6 +153,10 @@ public: 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 { @@ -300,6 +305,14 @@ private: 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 NullPointerVals; + AtomicBoolValue &TrueVal; AtomicBoolValue &FalseVal; diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h index ac49d22..302e35d 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -203,6 +203,10 @@ public: /// 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 diff --git a/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp b/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp index de48fd7..4c7f0d1 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp @@ -55,6 +55,19 @@ DataflowAnalysisContext::getStableStorageLocation(const Expr &E) { 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(PointeeLoc)); + } + return *Res.first->second; +} + static std::pair makeCanonicalBoolValuePair(BoolValue &LHS, BoolValue &RHS) { auto Res = std::make_pair(&LHS, &RHS); diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp index 7711302..3aea670 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -332,6 +332,10 @@ 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; diff --git a/clang/lib/Analysis/FlowSensitive/Transfer.cpp b/clang/lib/Analysis/FlowSensitive/Transfer.cpp index befd3c6..500e1a7 100644 --- a/clang/lib/Analysis/FlowSensitive/Transfer.cpp +++ b/clang/lib/Analysis/FlowSensitive/Transfer.cpp @@ -251,6 +251,16 @@ public: 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; } diff --git a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp index 3a8e2ac..a0b753f 100644 --- a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp +++ b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp @@ -2214,6 +2214,93 @@ TEST_F(TransferTest, IntegralToBooleanCastFromBool) { }); } +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>> + 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(Env.getValue(*FooXDecl, SkipPast::None)); + const auto *FooYVal = + cast(Env.getValue(*FooYDecl, SkipPast::None)); + const auto *BarVal = + cast(Env.getValue(*BarDecl, SkipPast::None)); + const auto *BazVal = + cast(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(FooPointeeLoc)); + EXPECT_THAT(Env.getValue(FooPointeeLoc), IsNull()); + + const StorageLocation &BarPointeeLoc = BarVal->getPointeeLoc(); + EXPECT_TRUE(isa(BarPointeeLoc)); + EXPECT_THAT(Env.getValue(BarPointeeLoc), IsNull()); + + const StorageLocation &BazPointeeLoc = BazVal->getPointeeLoc(); + EXPECT_TRUE(isa(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>> + 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( + 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() { -- 2.7.4