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 @@ -66,12 +66,14 @@ return Model.compareEquivalent(Type, *Val1, Env1, *Val2, Env2); } -/// Attempts to merge distinct values `Val1` and `Val1` in `Env1` and `Env2`, +/// Attempts to merge distinct values `Val1` and `Val2` in `Env1` and `Env2`, /// respectively, of the same type `Type`. Merging generally produces a single /// value that (soundly) approximates the two inputs, although the actual /// meaning depends on `Model`. -static Value *mergeDistinctValues(QualType Type, Value *Val1, Environment &Env1, - Value *Val2, const Environment &Env2, +static Value *mergeDistinctValues(QualType Type, Value *Val1, + const Environment &Env1, Value *Val2, + const Environment &Env2, + Environment &MergedEnv, Environment::ValueModel &Model) { // Join distinct boolean values preserving information about the constraints // in the respective path conditions. Note: this construction can, in @@ -94,19 +96,19 @@ // have mutually exclusive conditions. if (auto *Expr1 = dyn_cast(Val1)) { for (BoolValue *Constraint : Env1.getFlowConditionConstraints()) { - Expr1 = &Env1.makeAnd(*Expr1, *Constraint); + Expr1 = &MergedEnv.makeAnd(*Expr1, *Constraint); } auto *Expr2 = cast(Val2); for (BoolValue *Constraint : Env2.getFlowConditionConstraints()) { - Expr2 = &Env1.makeAnd(*Expr2, *Constraint); + Expr2 = &MergedEnv.makeAnd(*Expr2, *Constraint); } - return &Env1.makeOr(*Expr1, *Expr2); + return &MergedEnv.makeOr(*Expr1, *Expr2); } // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge` // returns false to avoid storing unneeded values in `DACtx`. - if (Value *MergedVal = Env1.createValue(Type)) - if (Model.merge(Type, *Val1, Env1, *Val2, Env2, *MergedVal, Env1)) + if (Value *MergedVal = MergedEnv.createValue(Type)) + if (Model.merge(Type, *Val1, Env1, *Val2, Env2, *MergedVal, MergedEnv)) return MergedVal; return nullptr; @@ -315,28 +317,29 @@ auto Effect = LatticeJoinEffect::Unchanged; - const unsigned DeclToLocSizeBefore = DeclToLoc.size(); - DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc); - if (DeclToLocSizeBefore != DeclToLoc.size()) + Environment JoinedEnv(*DACtx); + + JoinedEnv.DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc); + if (DeclToLoc.size() != JoinedEnv.DeclToLoc.size()) Effect = LatticeJoinEffect::Changed; - const unsigned ExprToLocSizeBefore = ExprToLoc.size(); - ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc); - if (ExprToLocSizeBefore != ExprToLoc.size()) + JoinedEnv.ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc); + if (ExprToLoc.size() != JoinedEnv.ExprToLoc.size()) Effect = LatticeJoinEffect::Changed; - const unsigned MemberLocToStructSizeBefore = MemberLocToStruct.size(); - MemberLocToStruct = + JoinedEnv.MemberLocToStruct = intersectDenseMaps(MemberLocToStruct, Other.MemberLocToStruct); - if (MemberLocToStructSizeBefore != MemberLocToStruct.size()) + if (MemberLocToStruct.size() != JoinedEnv.MemberLocToStruct.size()) Effect = LatticeJoinEffect::Changed; + // FIXME: set `Effect` as needed. + JoinedEnv.FlowConditionConstraints = joinConstraints( + DACtx, FlowConditionConstraints, Other.FlowConditionConstraints); + // Move `LocToVal` so that `Environment::ValueModel::merge` can safely assign // values to storage locations while this code iterates over the current // assignments. - llvm::DenseMap OldLocToVal = - std::move(LocToVal); - for (auto &Entry : OldLocToVal) { + for (auto &Entry : LocToVal) { const StorageLocation *Loc = Entry.first; assert(Loc != nullptr); @@ -349,19 +352,18 @@ assert(It->second != nullptr); if (Val == It->second) { - LocToVal.insert({Loc, Val}); + JoinedEnv.LocToVal.insert({Loc, Val}); continue; } - if (Value *MergedVal = mergeDistinctValues(Loc->getType(), Val, *this, - It->second, Other, Model)) - LocToVal.insert({Loc, MergedVal}); + if (Value *MergedVal = mergeDistinctValues( + Loc->getType(), Val, *this, It->second, Other, JoinedEnv, Model)) + JoinedEnv.LocToVal.insert({Loc, MergedVal}); } - if (OldLocToVal.size() != LocToVal.size()) + if (LocToVal.size() != JoinedEnv.LocToVal.size()) Effect = LatticeJoinEffect::Changed; - FlowConditionConstraints = joinConstraints(DACtx, FlowConditionConstraints, - Other.FlowConditionConstraints); + *this = std::move(JoinedEnv); return Effect; } diff --git a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp --- a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp +++ b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp @@ -10,6 +10,7 @@ #include "TestingSupport.h" #include "clang/AST/Decl.h" #include "clang/AST/ExprCXX.h" +#include "clang/AST/Type.h" #include "clang/ASTMatchers/ASTMatchFinder.h" #include "clang/ASTMatchers/ASTMatchers.h" #include "clang/Analysis/CFG.h" @@ -295,6 +296,161 @@ // FIXME: Called functions at point `p` should contain only "foo". } +// Models an analysis that uses the flow conditions. +class SpecialBoolAnalysis + : public DataflowAnalysis { +public: + explicit SpecialBoolAnalysis(ASTContext &Context) + : DataflowAnalysis(Context) {} + + static NoopLattice initialElement() { return {}; } + + void transfer(const Stmt *S, NoopLattice &, Environment &Env) { + auto SpecialBoolRecordDecl = recordDecl(hasName("SpecialBool")); + auto HasSpecialBoolType = hasType(SpecialBoolRecordDecl); + + if (const auto *E = selectFirst( + "call", match(cxxConstructExpr(HasSpecialBoolType).bind("call"), *S, + getASTContext()))) { + auto &ConstructorVal = *cast(Env.createValue(E->getType())); + ConstructorVal.setProperty("is_set", Env.getBoolLiteralValue(false)); + Env.setValue(*Env.getStorageLocation(*E, SkipPast::None), ConstructorVal); + } else if (const auto *E = selectFirst( + "call", match(cxxMemberCallExpr(callee(cxxMethodDecl(ofClass( + SpecialBoolRecordDecl)))) + .bind("call"), + *S, getASTContext()))) { + auto *Object = E->getImplicitObjectArgument(); + assert(Object != nullptr); + + auto *ObjectLoc = + Env.getStorageLocation(*Object, SkipPast::ReferenceThenPointer); + assert(ObjectLoc != nullptr); + + auto &ConstructorVal = + *cast(Env.createValue(Object->getType())); + ConstructorVal.setProperty("is_set", Env.getBoolLiteralValue(true)); + Env.setValue(*ObjectLoc, ConstructorVal); + } + } + + bool compareEquivalent(QualType Type, const Value &Val1, + const Environment &Env1, const Value &Val2, + const Environment &Env2) final { + if (!Type->isRecordType()) + return false; + const auto *Decl = Type->getAsCXXRecordDecl(); + if (Decl->getIdentifier() == nullptr || Decl->getName() != "SpecialBool") + return false; + + auto *V1 = cast_or_null( + cast(&Val1)->getProperty("is_set")); + if (V1 == nullptr) + return true; + + auto *V2 = cast_or_null( + cast(&Val2)->getProperty("is_set")); + if (V2 == nullptr) + return false; + + return V1 == V2 || + Env1.flowConditionImplies(*V1) == Env2.flowConditionImplies(*V2); + } + + // Always returns `true` to accept the `MergedVal`. + bool merge(QualType Type, const Value &Val1, const Environment &Env1, + const Value &Val2, const Environment &Env2, Value &MergedVal, + Environment &MergedEnv) final { + if (!Type->isRecordType()) + return true; + const auto *Decl = Type->getAsCXXRecordDecl(); + if (Decl->getIdentifier() == nullptr || Decl->getName() != "SpecialBool") + return true; + + auto *V1 = cast_or_null( + cast(&Val1)->getProperty("is_set")); + if (V1 == nullptr) + return true; + + auto *V2 = cast_or_null( + cast(&Val2)->getProperty("is_set")); + if (V2 == nullptr) + return true; + + auto &V = MergedEnv.makeAtomicBoolValue(); + cast(&MergedVal)->setProperty("is_set", V); + if (Env1.flowConditionImplies(*V1) && Env2.flowConditionImplies(*V2)) + MergedEnv.addToFlowCondition(V); + + return true; + } +}; + +class JoinFlowConditionsTest : public Test { +protected: + template + void runDataflow(llvm::StringRef Code, Matcher Match) { + ASSERT_THAT_ERROR( + test::checkDataflow( + Code, "target", + [](ASTContext &Context, Environment &Env) { + return SpecialBoolAnalysis(Context); + }, + [&Match]( + llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { Match(Results, ASTCtx); }, + {"-fsyntax-only", "-std=c++17"}), + llvm::Succeeded()); + } +}; + +TEST_F(JoinFlowConditionsTest, JoinDistinctButProvablyEquivalentValues) { + std::string Code = R"( + struct SpecialBool { + SpecialBool() = default; + void set(); + }; + void target(bool Cond) { + SpecialBool Foo; + /*[[p1]]*/ + if (Cond) { + Foo.set(); + /*[[p2]]*/ + } else { + Foo.set(); + } + (void)0; + /*[[p3]]*/ + } + )"; + runDataflow( + Code, [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, + ElementsAre(Pair("p3", _), Pair("p2", _), Pair("p1", _))); + const Environment &Env1 = Results[2].second.Env; + const Environment &Env2 = Results[1].second.Env; + const Environment &Env3 = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo"); + ASSERT_THAT(FooDecl, NotNull()); + + auto GetFooValue = [FooDecl](const Environment &Env) { + return cast( + cast(Env.getValue(*FooDecl, SkipPast::None)) + ->getProperty("is_set")); + }; + + EXPECT_FALSE(Env1.flowConditionImplies(*GetFooValue(Env1))); + EXPECT_TRUE(Env2.flowConditionImplies(*GetFooValue(Env2))); + EXPECT_TRUE(Env3.flowConditionImplies(*GetFooValue(Env3))); + }); +} + class OptionalIntAnalysis : public DataflowAnalysis { public: