diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h @@ -25,6 +25,7 @@ #include "llvm/ADT/DenseSet.h" #include "llvm/Support/Compiler.h" #include +#include #include #include #include @@ -49,60 +50,12 @@ /// Returns the set of all fields in the type. llvm::DenseSet getObjectFields(QualType Type); -/// Owns objects that encompass the state of a program and stores context that -/// is used during dataflow analysis. -class DataflowAnalysisContext { -public: - /// Constructs a dataflow analysis context. - /// - /// Requirements: - /// - /// `S` must not be null. - DataflowAnalysisContext(std::unique_ptr S) - : S(std::move(S)), TrueVal(createAtomicBoolValue()), - FalseVal(createAtomicBoolValue()) { - assert(this->S != nullptr); - } - - /// Takes ownership of `Loc` and returns a reference to it. - /// - /// Requirements: - /// - /// `Loc` must not be null. - template - typename std::enable_if::value, T &>::type - takeOwnership(std::unique_ptr Loc) { - assert(Loc != nullptr); - Locs.push_back(std::move(Loc)); - return *cast(Locs.back().get()); - } - - /// Takes ownership of `Val` and returns a reference to it. - /// - /// Requirements: - /// - /// `Val` must not be null. - template - typename std::enable_if::value, T &>::type - takeOwnership(std::unique_ptr Val) { - assert(Val != nullptr); - Vals.push_back(std::move(Val)); - return *cast(Vals.back().get()); - } - - /// Returns a stable storage location appropriate for `Type`. - /// - /// Requirements: - /// - /// `Type` must not be null. - StorageLocation &getStableStorageLocation(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); +/// A sequence of method calls that resembles the call stack. +using CallString = std::vector; +/// Holds stable storage locations in the context of a particular `CallString`. +class StorageFrame { +public: /// Assigns `Loc` as the storage location of `D`. /// /// Requirements: @@ -154,6 +107,77 @@ return ThisPointeeLoc; } +private: + // Maps from program declarations and statements to storage locations that are + // assigned to them. These assignments are global (aggregated across all basic + // 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 DeclToLoc; + llvm::DenseMap ExprToLoc; + + StorageLocation *ThisPointeeLoc = nullptr; +}; + +/// Owns objects that encompass the state of a program and stores context that +/// is used during dataflow analysis. +class DataflowAnalysisContext { +public: + /// Constructs a dataflow analysis context. + /// + /// Requirements: + /// + /// `S` must not be null. + DataflowAnalysisContext(std::unique_ptr S) + : S(std::move(S)), TrueVal(createAtomicBoolValue()), + FalseVal(createAtomicBoolValue()) { + assert(this->S != nullptr); + } + + /// Takes ownership of `Loc` and returns a reference to it. + /// + /// Requirements: + /// + /// `Loc` must not be null. + template + typename std::enable_if::value, T &>::type + takeOwnership(std::unique_ptr Loc) { + assert(Loc != nullptr); + Locs.push_back(std::move(Loc)); + return *cast(Locs.back().get()); + } + + /// Takes ownership of `Val` and returns a reference to it. + /// + /// Requirements: + /// + /// `Val` must not be null. + template + typename std::enable_if::value, T &>::type + takeOwnership(std::unique_ptr Val) { + assert(Val != nullptr); + Vals.push_back(std::move(Val)); + return *cast(Vals.back().get()); + } + + /// Returns a stable storage location appropriate for `Type`. + /// + /// Requirements: + /// + /// `Type` must not be null. + StorageLocation &getStableStorageLocation(const CallString &CallStr, + QualType Type); + + /// Returns a stable storage location for `D`. + StorageLocation &getStableStorageLocation(const CallString &CallStr, + const VarDecl &D); + + /// Returns a stable storage location for `E`. + StorageLocation &getStableStorageLocation(const CallString &CallStr, + const Expr &E); + + StorageFrame &getFrame(const CallString &CallStr); + /// Returns a pointer value that represents a null pointer. Calls with /// `PointeeType` that are canonically equivalent will return the same result. /// A null `PointeeType` can be used for the pointee of `std::nullptr_t`. @@ -311,15 +335,7 @@ std::vector> Locs; std::vector> Vals; - // Maps from program declarations and statements to storage locations that are - // assigned to them. These assignments are global (aggregated across all basic - // 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 DeclToLoc; - llvm::DenseMap ExprToLoc; - - StorageLocation *ThisPointeeLoc = nullptr; + std::map Frames; // Null pointer values, keyed by the canonical pointee type. // diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -143,6 +143,10 @@ /// Each argument of `Call` must already have a `StorageLocation`. Environment pushCall(const CallExpr *Call) const; + /// Moves gathered information back into `this` from a `CalleeEnv` created via + /// `pushCall`. + void popCall(const Environment &CalleeEnv); + /// Returns true if and only if the environment is equivalent to `Other`, i.e /// the two environments: /// - have the same mappings from declarations to storage locations, @@ -362,6 +366,7 @@ // `DACtx` is not null and not owned by this object. DataflowAnalysisContext *DACtx; + CallString CallStr; // Maps from program declarations and statements to storage locations that are // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these diff --git a/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp b/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp --- a/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp @@ -25,14 +25,16 @@ namespace dataflow { StorageLocation & -DataflowAnalysisContext::getStableStorageLocation(QualType Type) { +DataflowAnalysisContext::getStableStorageLocation(const CallString &CallStr, + QualType Type) { if (!Type.isNull() && (Type->isStructureOrClassType() || Type->isUnionType())) { // FIXME: Explore options to avoid eager initialization of fields as some of // them might not be needed for a particular analysis. llvm::DenseMap FieldLocs; for (const FieldDecl *Field : getObjectFields(Type)) - FieldLocs.insert({Field, &getStableStorageLocation(Field->getType())}); + FieldLocs.insert( + {Field, &getStableStorageLocation(CallStr, Field->getType())}); return takeOwnership( std::make_unique(Type, std::move(FieldLocs))); } @@ -40,30 +42,39 @@ } StorageLocation & -DataflowAnalysisContext::getStableStorageLocation(const VarDecl &D) { - if (auto *Loc = getStorageLocation(D)) +DataflowAnalysisContext::getStableStorageLocation(const CallString &CallStr, + const VarDecl &D) { + StorageFrame &Frame = getFrame(CallStr); + if (auto *Loc = Frame.getStorageLocation(D)) return *Loc; - auto &Loc = getStableStorageLocation(D.getType()); - setStorageLocation(D, Loc); + auto &Loc = getStableStorageLocation(CallStr, D.getType()); + Frame.setStorageLocation(D, Loc); return Loc; } StorageLocation & -DataflowAnalysisContext::getStableStorageLocation(const Expr &E) { - if (auto *Loc = getStorageLocation(E)) +DataflowAnalysisContext::getStableStorageLocation(const CallString &CallStr, + const Expr &E) { + StorageFrame &Frame = getFrame(CallStr); + if (auto *Loc = Frame.getStorageLocation(E)) return *Loc; - auto &Loc = getStableStorageLocation(E.getType()); - setStorageLocation(E, Loc); + auto &Loc = getStableStorageLocation(CallStr, E.getType()); + Frame.setStorageLocation(E, Loc); return Loc; } +StorageFrame &DataflowAnalysisContext::getFrame(const CallString &CallStr) { + return Frames.try_emplace(CallStr).first->second; +} + PointerValue & DataflowAnalysisContext::getOrCreateNullPointerValue(QualType PointeeType) { auto CanonicalPointeeType = PointeeType.isNull() ? PointeeType : PointeeType.getCanonicalType(); auto Res = NullPointerVals.try_emplace(CanonicalPointeeType, nullptr); if (Res.second) { - auto &PointeeLoc = getStableStorageLocation(CanonicalPointeeType); + // We arbitrarily put this in the outermost context; doesn't really matter. + auto &PointeeLoc = getStableStorageLocation({}, CanonicalPointeeType); Res.first->second = &takeOwnership(std::make_unique(PointeeLoc)); } diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -154,7 +154,7 @@ : DACtx(&DACtx), FlowConditionToken(&DACtx.makeFlowConditionToken()) {} Environment::Environment(const Environment &Other) - : DACtx(Other.DACtx), DeclToLoc(Other.DeclToLoc), + : DACtx(Other.DACtx), CallStr(Other.CallStr), DeclToLoc(Other.DeclToLoc), ExprToLoc(Other.ExprToLoc), LocToVal(Other.LocToVal), MemberLocToStruct(Other.MemberLocToStruct), FlowConditionToken(&DACtx->forkFlowCondition(*Other.FlowConditionToken)) { @@ -192,7 +192,7 @@ // FIXME: Add support for union types. if (!ThisPointeeType->isUnionType()) { auto &ThisPointeeLoc = createStorageLocation(ThisPointeeType); - DACtx.setThisPointeeStorageLocation(ThisPointeeLoc); + DACtx.getFrame(CallStr).setThisPointeeStorageLocation(ThisPointeeLoc); if (Value *ThisPointeeVal = createValue(ThisPointeeType)) setValue(ThisPointeeLoc, *ThisPointeeVal); } @@ -202,6 +202,7 @@ Environment Environment::pushCall(const CallExpr *Call) const { Environment Env(*this); + Env.CallStr.push_back(Call); // FIXME: Currently this only works if the callee is never a method and the // same callee is never analyzed from multiple separate callsites. To @@ -238,6 +239,17 @@ return Env; } +void Environment::popCall(const Environment &CalleeEnv) { + // We ignore `DACtx` because it's already the same in both. We don't want the + // callee's `CallStr` because it is one level deeper than ours. We don't bring + // back `DeclToLoc` and `ExprToLoc` because their mappings are only valid for + // the `CallStr` in `CalleeEnv`, and we want to be able to later analyze the + // same callee in a different context. + this->LocToVal = std::move(CalleeEnv.LocToVal); + this->MemberLocToStruct = std::move(CalleeEnv.MemberLocToStruct); + this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken); +} + bool Environment::equivalentTo(const Environment &Other, Environment::ValueModel &Model) const { assert(DACtx == Other.DACtx); @@ -323,21 +335,21 @@ } StorageLocation &Environment::createStorageLocation(QualType Type) { - return DACtx->getStableStorageLocation(Type); + return DACtx->getStableStorageLocation(CallStr, Type); } StorageLocation &Environment::createStorageLocation(const VarDecl &D) { // Evaluated declarations are always assigned the same storage locations to // ensure that the environment stabilizes across loop iterations. Storage // locations for evaluated declarations are stored in the analysis context. - return DACtx->getStableStorageLocation(D); + return DACtx->getStableStorageLocation(CallStr, D); } StorageLocation &Environment::createStorageLocation(const Expr &E) { // Evaluated expressions are always assigned the same storage locations to // ensure that the environment stabilizes across loop iterations. Storage // locations for evaluated expressions are stored in the analysis context. - return DACtx->getStableStorageLocation(E); + return DACtx->getStableStorageLocation(CallStr, E); } void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) { @@ -365,7 +377,7 @@ } StorageLocation *Environment::getThisPointeeStorageLocation() const { - return DACtx->getThisPointeeStorageLocation(); + return DACtx->getFrame(CallStr).getThisPointeeStorageLocation(); } PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) { diff --git a/clang/lib/Analysis/FlowSensitive/Transfer.cpp b/clang/lib/Analysis/FlowSensitive/Transfer.cpp --- a/clang/lib/Analysis/FlowSensitive/Transfer.cpp +++ b/clang/lib/Analysis/FlowSensitive/Transfer.cpp @@ -534,7 +534,7 @@ auto ExitState = (*BlockToOutputState)[ExitBlock]; assert(ExitState); - Env = ExitState->Env; + Env.popCall(ExitState->Env); } } diff --git a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp --- a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp +++ b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp @@ -3960,4 +3960,45 @@ /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}}); } +TEST(TransferTest, ContextSensitiveSetBothTrueAndFalse) { + std::string Code = R"( + bool GiveBool(); + void SetBool(bool &Var, bool Val) { Var = Val; } + + void target() { + bool Foo = GiveBool(); + bool Bar = GiveBool(); + SetBool(Foo, true); + SetBool(Bar, false); + // [[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 *FooDecl = findValueDecl(ASTCtx, "Foo"); + ASSERT_THAT(FooDecl, NotNull()); + + const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar"); + ASSERT_THAT(BarDecl, NotNull()); + + auto &FooVal = + *cast(Env.getValue(*FooDecl, SkipPast::None)); + EXPECT_TRUE(Env.flowConditionImplies(FooVal)); + EXPECT_FALSE(Env.flowConditionImplies(Env.makeNot(FooVal))); + + auto &BarVal = + *cast(Env.getValue(*BarDecl, SkipPast::None)); + EXPECT_FALSE(Env.flowConditionImplies(BarVal)); + EXPECT_TRUE(Env.flowConditionImplies(Env.makeNot(BarVal))); + }, + {/*.ApplyBuiltinTransfer=*/true, + /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}}); +} + } // namespace