From a6ddc68487823d48c0ec0ddd649ace4a2732d0b0 Mon Sep 17 00:00:00 2001 From: Sam Estep Date: Fri, 29 Jul 2022 19:39:52 +0000 Subject: [PATCH] [clang][dataflow] Handle multiple context-sensitive calls to the same function This patch enables context-sensitive analysis of multiple different calls to the same function (see the `ContextSensitiveSetBothTrueAndFalse` example in the `TransferTest` suite) by replacing the `Environment` copy-assignment with a call to the new `popCall` method, which `std::move`s some fields but specifically does not move `DeclToLoc` and `ExprToLoc` from the callee back to the caller. To enable this, the `StorageLocation` for a given parameter needs to be stable across different calls to the same function, so this patch also improves the modeling of parameter initialization, using `ReferenceValue` when necessary (for arguments passed by reference). This approach explicitly does not work for recursive calls, because we currently only plan to use this context-sensitive machinery to support specialized analysis models we write, not analysis of arbitrary callees. Reviewed By: ymandel, xazax.hun Differential Revision: https://reviews.llvm.org/D130726 --- .../Analysis/FlowSensitive/DataflowEnvironment.h | 4 + .../clang/Analysis/FlowSensitive/Transfer.h | 5 +- .../Analysis/FlowSensitive/DataflowEnvironment.cpp | 36 +++-- clang/lib/Analysis/FlowSensitive/Transfer.cpp | 6 +- .../Analysis/FlowSensitive/TransferTest.cpp | 161 +++++++++++++++++++++ 5 files changed, 200 insertions(+), 12 deletions(-) diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h index 2e9c088..9ba73d9 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -143,6 +143,10 @@ public: /// 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, diff --git a/clang/include/clang/Analysis/FlowSensitive/Transfer.h b/clang/include/clang/Analysis/FlowSensitive/Transfer.h index cbb6254..8babc57 100644 --- a/clang/include/clang/Analysis/FlowSensitive/Transfer.h +++ b/clang/include/clang/Analysis/FlowSensitive/Transfer.h @@ -22,7 +22,10 @@ namespace dataflow { struct TransferOptions { /// Determines whether to analyze function bodies when present in the - /// translation unit. + /// translation unit. Note: this is currently only meant to be used for + /// inlining of specialized model code, not for context-sensitive analysis of + /// arbitrary subject code. In particular, some fundamentals such as recursion + /// are explicitly unsupported. bool ContextSensitive = false; }; diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp index f6f71e3..1bb4e19 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -203,14 +203,6 @@ Environment::Environment(DataflowAnalysisContext &DACtx, Environment Environment::pushCall(const CallExpr *Call) const { Environment Env(*this); - // FIXME: Currently this only works if the callee is never a method and the - // same callee is never analyzed from multiple separate callsites. To - // generalize this, we'll need to store a "context" field (probably a stack of - // `const CallExpr *`s) in the `Environment`, and then change the - // `DataflowAnalysisContext` class to hold a map from contexts to "frames", - // where each frame stores its own version of what are currently the - // `DeclToLoc`, `ExprToLoc`, and `ThisPointeeLoc` fields. - const auto *FuncDecl = Call->getDirectCallee(); assert(FuncDecl != nullptr); assert(FuncDecl->getBody() != nullptr); @@ -226,16 +218,40 @@ Environment Environment::pushCall(const CallExpr *Call) const { for (; ArgIt != ArgEnd; ++ParamIt, ++ArgIt) { assert(ParamIt != FuncDecl->param_end()); - const VarDecl *Param = *ParamIt; const Expr *Arg = *ArgIt; auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::Reference); assert(ArgLoc != nullptr); - Env.setStorageLocation(*Param, *ArgLoc); + + const VarDecl *Param = *ParamIt; + auto &Loc = Env.createStorageLocation(*Param); + Env.setStorageLocation(*Param, Loc); + + QualType ParamType = Param->getType(); + if (ParamType->isReferenceType()) { + auto &Val = Env.takeOwnership(std::make_unique(*ArgLoc)); + Env.setValue(Loc, Val); + } else if (auto *ArgVal = Env.getValue(*ArgLoc)) { + Env.setValue(Loc, *ArgVal); + } else if (Value *Val = Env.createValue(ParamType)) { + Env.setValue(Loc, *Val); + } } return Env; } +void Environment::popCall(const Environment &CalleeEnv) { + // We ignore `DACtx` because it's already the same in both. We don't bring + // back `DeclToLoc` and `ExprToLoc` because we want to be able to later + // analyze the same callee in a different context, and `setStorageLocation` + // requires there to not already be a storage location assigned. Conceptually, + // these maps capture information from the local scope, so when popping that + // scope, we do not propagate the maps. + 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); diff --git a/clang/lib/Analysis/FlowSensitive/Transfer.cpp b/clang/lib/Analysis/FlowSensitive/Transfer.cpp index bbf7526..06053e5 100644 --- a/clang/lib/Analysis/FlowSensitive/Transfer.cpp +++ b/clang/lib/Analysis/FlowSensitive/Transfer.cpp @@ -512,6 +512,10 @@ public: if (!Options.ContextSensitive || F->getBody() == nullptr) return; + // FIXME: We don't support context-sensitive analysis of recursion, so + // we should return early here if `F` is the same as the `FunctionDecl` + // holding `S` itself. + auto &ASTCtx = F->getASTContext(); // FIXME: Cache these CFGs. @@ -534,7 +538,7 @@ public: 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 index 41e4252..d617176 100644 --- a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp +++ b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp @@ -3960,4 +3960,165 @@ TEST(TransferTest, ContextSensitiveSetFalse) { /*.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}}); +} + +TEST(TransferTest, ContextSensitiveSetTwoLayers) { + std::string Code = R"( + bool GiveBool(); + void SetBool1(bool &Var) { Var = true; } + void SetBool2(bool &Var) { SetBool1(Var); } + + void target() { + bool Foo = GiveBool(); + SetBool2(Foo); + // [[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()); + + auto &FooVal = + *cast(Env.getValue(*FooDecl, SkipPast::None)); + EXPECT_FALSE(Env.flowConditionImplies(FooVal)); + EXPECT_FALSE(Env.flowConditionImplies(Env.makeNot(FooVal))); + }, + {/*.ApplyBuiltinTransfer=*/true, + /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}}); +} + +TEST(TransferTest, ContextSensitiveSetMultipleLines) { + std::string Code = R"( + void SetBools(bool &Var1, bool &Var2) { + Var1 = true; + Var2 = false; + } + + void target() { + bool Foo = false; + bool Bar = true; + SetBools(Foo, Bar); + // [[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}}); +} + +TEST(TransferTest, ContextSensitiveSetMultipleBlocks) { + std::string Code = R"( + void IfCond(bool Cond, bool &Then, bool &Else) { + if (Cond) { + Then = true; + } else { + Else = true; + } + } + + void target() { + bool Foo = false; + bool Bar = false; + bool Baz = false; + IfCond(Foo, Bar, Baz); + // [[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 *BarDecl = findValueDecl(ASTCtx, "Bar"); + ASSERT_THAT(BarDecl, NotNull()); + + const ValueDecl *BazDecl = findValueDecl(ASTCtx, "Baz"); + ASSERT_THAT(BazDecl, NotNull()); + + auto &BarVal = + *cast(Env.getValue(*BarDecl, SkipPast::None)); + EXPECT_FALSE(Env.flowConditionImplies(BarVal)); + EXPECT_TRUE(Env.flowConditionImplies(Env.makeNot(BarVal))); + + auto &BazVal = + *cast(Env.getValue(*BazDecl, SkipPast::None)); + EXPECT_TRUE(Env.flowConditionImplies(BazVal)); + EXPECT_FALSE(Env.flowConditionImplies(Env.makeNot(BazVal))); + }, + {/*.ApplyBuiltinTransfer=*/true, + /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}}); +} + } // namespace -- 2.7.4