Author: Yitzhak Mandelbaum Date: 2024-04-04T08:39:51-04:00 New Revision: bbd259af0a4cc438dd02d5ee632cb2dc1def1f6a
URL: https://github.com/llvm/llvm-project/commit/bbd259af0a4cc438dd02d5ee632cb2dc1def1f6a DIFF: https://github.com/llvm/llvm-project/commit/bbd259af0a4cc438dd02d5ee632cb2dc1def1f6a.diff LOG: [clang][dataflow] Refactor `widen` API to be explicit about change effect. (#87233) The previous API relied on pointer equality of inputs and outputs to signal whether a change occured. This was too subtle and led to bugs in practice. It was also very limiting: the override could not return an equivalent (but not identical) value. Added: Modified: clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp Removed: ################################################################################ diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h index c30bccd06674a4..9a65f76cdf56bc 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -43,6 +43,15 @@ enum class ComparisonResult { Unknown, }; +/// The result of a `widen` operation. +struct WidenResult { + /// Non-null pointer to a potentially widened version of the input value. + Value *V; + /// Whether `V` represents a "change" (that is, a diff erent value) with + /// respect to the previous value in the sequence. + LatticeEffect Effect; +}; + /// Holds the state of the program (store and heap) at a given program point. /// /// WARNING: Symbolic values that are created by the environment for static @@ -104,14 +113,17 @@ class Environment { /// serve as a comparison operation, by indicating whether the widened value /// is equivalent to the previous value. /// - /// Returns either: - /// - /// `nullptr`, if this value is not of interest to the model, or - /// - /// `&Prev`, if the widened value is equivalent to `Prev`, or - /// - /// A non-null value that approximates `Current`. `Prev` is available to - /// inform the chosen approximation. + /// Returns one of the folowing: + /// * `std::nullopt`, if this value is not of interest to the + /// model. + /// * A `WidenResult` with: + /// * A non-null `Value *` that points either to `Current` or a widened + /// version of `Current`. This value must be consistent with + /// the flow condition of `CurrentEnv`. We particularly caution + /// against using `Prev`, which is rarely consistent. + /// * A `LatticeEffect` indicating whether the value should be + /// considered a new value (`Changed`) or one *equivalent* (if not + /// necessarily equal) to `Prev` (`Unchanged`). /// /// `PrevEnv` and `CurrentEnv` can be used to query child values and path /// condition implications of `Prev` and `Current`, respectively. @@ -122,17 +134,19 @@ class Environment { /// /// `Prev` and `Current` must be assigned to the same storage location in /// `PrevEnv` and `CurrentEnv`, respectively. - virtual Value *widen(QualType Type, Value &Prev, const Environment &PrevEnv, - Value &Current, Environment &CurrentEnv) { + virtual std::optional<WidenResult> widen(QualType Type, Value &Prev, + const Environment &PrevEnv, + Value &Current, + Environment &CurrentEnv) { // The default implementation reduces to just comparison, since comparison // is required by the API, even if no widening is performed. switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) { - case ComparisonResult::Same: - return &Prev; - case ComparisonResult::Different: - return &Current; - case ComparisonResult::Unknown: - return nullptr; + case ComparisonResult::Unknown: + return std::nullopt; + case ComparisonResult::Same: + return WidenResult{&Current, LatticeEffect::Unchanged}; + case ComparisonResult::Different: + return WidenResult{&Current, LatticeEffect::Changed}; } llvm_unreachable("all cases in switch covered"); } @@ -236,8 +250,8 @@ class Environment { /// /// `PrevEnv` must be the immediate previous version of the environment. /// `PrevEnv` and `this` must use the same `DataflowAnalysisContext`. - LatticeJoinEffect widen(const Environment &PrevEnv, - Environment::ValueModel &Model); + LatticeEffect widen(const Environment &PrevEnv, + Environment::ValueModel &Model); // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`, // `getStableStorageLocation`, or something more appropriate. diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h b/clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h index 0c81e2f078c241..b262732804ed69 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h @@ -17,13 +17,13 @@ namespace clang { namespace dataflow { -/// Effect indicating whether a lattice join operation resulted in a new value. -// FIXME: Rename to `LatticeEffect` since `widen` uses it as well, and we are -// likely removing it from `join`. -enum class LatticeJoinEffect { +/// Effect indicating whether a lattice operation resulted in a new value. +enum class LatticeEffect { Unchanged, Changed, }; +// DEPRECATED. Use `LatticeEffect`. +using LatticeJoinEffect = LatticeEffect; } // namespace dataflow } // namespace clang diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp index f729d676dd0de8..70ac0764476f60 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -166,17 +166,16 @@ static Value *joinDistinctValues(QualType Type, Value &Val1, return JoinedVal; } -// When widening does not change `Current`, return value will equal `&Prev`. -static Value &widenDistinctValues(QualType Type, Value &Prev, - const Environment &PrevEnv, Value &Current, - Environment &CurrentEnv, - Environment::ValueModel &Model) { +static WidenResult widenDistinctValues(QualType Type, Value &Prev, + const Environment &PrevEnv, + Value &Current, Environment &CurrentEnv, + Environment::ValueModel &Model) { // Boolean-model widening. if (auto *PrevBool = dyn_cast<BoolValue>(&Prev)) { - // If previous value was already Top, re-use that to (implicitly) indicate - // that no change occurred. if (isa<TopBoolValue>(Prev)) - return Prev; + // Safe to return `Prev` here, because Top is never dependent on the + // environment. + return {&Prev, LatticeEffect::Unchanged}; // We may need to widen to Top, but before we do so, check whether both // values are implied to be either true or false in the current environment. @@ -185,22 +184,24 @@ static Value &widenDistinctValues(QualType Type, Value &Prev, bool TruePrev = PrevEnv.proves(PrevBool->formula()); bool TrueCur = CurrentEnv.proves(CurBool.formula()); if (TruePrev && TrueCur) - return CurrentEnv.getBoolLiteralValue(true); + return {&CurrentEnv.getBoolLiteralValue(true), LatticeEffect::Unchanged}; if (!TruePrev && !TrueCur && PrevEnv.proves(PrevEnv.arena().makeNot(PrevBool->formula())) && CurrentEnv.proves(CurrentEnv.arena().makeNot(CurBool.formula()))) - return CurrentEnv.getBoolLiteralValue(false); + return {&CurrentEnv.getBoolLiteralValue(false), LatticeEffect::Unchanged}; - return CurrentEnv.makeTopBoolValue(); + return {&CurrentEnv.makeTopBoolValue(), LatticeEffect::Changed}; } // FIXME: Add other built-in model widening. // Custom-model widening. - if (auto *W = Model.widen(Type, Prev, PrevEnv, Current, CurrentEnv)) - return *W; + if (auto Result = Model.widen(Type, Prev, PrevEnv, Current, CurrentEnv)) + return *Result; - return equateUnknownValues(Prev.getKind()) ? Prev : Current; + return {&Current, equateUnknownValues(Prev.getKind()) + ? LatticeEffect::Unchanged + : LatticeEffect::Changed}; } // Returns whether the values in `Map1` and `Map2` compare equal for those @@ -271,7 +272,7 @@ llvm::MapVector<Key, Value *> widenKeyToValueMap(const llvm::MapVector<Key, Value *> &CurMap, const llvm::MapVector<Key, Value *> &PrevMap, Environment &CurEnv, const Environment &PrevEnv, - Environment::ValueModel &Model, LatticeJoinEffect &Effect) { + Environment::ValueModel &Model, LatticeEffect &Effect) { llvm::MapVector<Key, Value *> WidenedMap; for (auto &Entry : CurMap) { Key K = Entry.first; @@ -290,11 +291,11 @@ widenKeyToValueMap(const llvm::MapVector<Key, Value *> &CurMap, continue; } - Value &WidenedVal = widenDistinctValues(K->getType(), *PrevIt->second, - PrevEnv, *Val, CurEnv, Model); - WidenedMap.insert({K, &WidenedVal}); - if (&WidenedVal != PrevIt->second) - Effect = LatticeJoinEffect::Changed; + auto [WidenedVal, ValEffect] = widenDistinctValues( + K->getType(), *PrevIt->second, PrevEnv, *Val, CurEnv, Model); + WidenedMap.insert({K, WidenedVal}); + if (ValEffect == LatticeEffect::Changed) + Effect = LatticeEffect::Changed; } return WidenedMap; @@ -617,15 +618,15 @@ bool Environment::equivalentTo(const Environment &Other, return true; } -LatticeJoinEffect Environment::widen(const Environment &PrevEnv, - Environment::ValueModel &Model) { +LatticeEffect Environment::widen(const Environment &PrevEnv, + Environment::ValueModel &Model) { assert(DACtx == PrevEnv.DACtx); assert(ReturnVal == PrevEnv.ReturnVal); assert(ReturnLoc == PrevEnv.ReturnLoc); assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc); assert(CallStack == PrevEnv.CallStack); - auto Effect = LatticeJoinEffect::Unchanged; + auto Effect = LatticeEffect::Unchanged; // By the API, `PrevEnv` is a previous version of the environment for the same // block, so we have some guarantees about its shape. In particular, it will @@ -646,7 +647,7 @@ LatticeJoinEffect Environment::widen(const Environment &PrevEnv, ExprToLoc.size() != PrevEnv.ExprToLoc.size() || ExprToVal.size() != PrevEnv.ExprToVal.size() || LocToVal.size() != PrevEnv.LocToVal.size()) - Effect = LatticeJoinEffect::Changed; + Effect = LatticeEffect::Changed; return Effect; } diff --git a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp index bea00ab1a1f062..b0b579d2bc19e3 100644 --- a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp +++ b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp @@ -805,6 +805,25 @@ class NullPointerAnalysis final else JoinedVal.setProperty("is_null", JoinedEnv.makeTopBoolValue()); } + + std::optional<WidenResult> widen(QualType Type, Value &Prev, + const Environment &PrevEnv, Value &Current, + Environment &CurrentEnv) override { + switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) { + case ComparisonResult::Same: + return WidenResult{&Current, LatticeJoinEffect::Unchanged}; + case ComparisonResult::Different: { + auto &CurPtr = cast<PointerValue>(Current); + auto &WidenedPtr = + CurrentEnv.create<PointerValue>(CurPtr.getPointeeLoc()); + WidenedPtr.setProperty("is_null", CurrentEnv.makeTopBoolValue()); + return WidenResult{&WidenedPtr, LatticeJoinEffect::Changed}; + } + case ComparisonResult::Unknown: + return std::nullopt; + } + llvm_unreachable("all cases in switch covered"); + } }; class WideningTest : public Test { @@ -846,7 +865,6 @@ TEST_F(WideningTest, JoinDistinctValuesWithDistinctProperties) { Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results, ASTContext &ASTCtx) { - ASSERT_THAT(Results.keys(), UnorderedElementsAre("p1", "p2", "p3")); const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1"); const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2"); const Environment &Env3 = getEnvironmentAtAnnotation(Results, "p3"); @@ -889,8 +907,6 @@ TEST_F(WideningTest, JoinDistinctValuesWithSameProperties) { Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results, ASTContext &ASTCtx) { - ASSERT_THAT(Results.keys(), - UnorderedElementsAre("p1", "p2", "p3", "p4")); const Environment &Env1 = getEnvironmentAtAnnotation(Results, "p1"); const Environment &Env2 = getEnvironmentAtAnnotation(Results, "p2"); const Environment &Env3 = getEnvironmentAtAnnotation(Results, "p3"); @@ -929,19 +945,11 @@ TEST_F(WideningTest, DistinctPointersToTheSameLocationAreEquivalent) { Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results, ASTContext &ASTCtx) { - ASSERT_THAT(Results.keys(), UnorderedElementsAre("p")); const Environment &Env = getEnvironmentAtAnnotation(Results, "p"); - - const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo"); - ASSERT_THAT(FooDecl, NotNull()); - - const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar"); - ASSERT_THAT(BarDecl, NotNull()); - - const auto *FooLoc = - cast<ScalarStorageLocation>(Env.getStorageLocation(*FooDecl)); - const auto *BarVal = cast<PointerValue>(Env.getValue(*BarDecl)); - EXPECT_EQ(&BarVal->getPointeeLoc(), FooLoc); + const auto &FooLoc = + getLocForDecl<ScalarStorageLocation>(ASTCtx, Env, "Foo"); + const auto &BarVal = getValueForDecl<PointerValue>(ASTCtx, Env, "Bar"); + EXPECT_EQ(&BarVal.getPointeeLoc(), &FooLoc); }); } @@ -963,18 +971,38 @@ TEST_F(WideningTest, DistinctValuesWithSamePropertiesAreEquivalent) { Code, [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results, ASTContext &ASTCtx) { - ASSERT_THAT(Results.keys(), UnorderedElementsAre("p")); const Environment &Env = getEnvironmentAtAnnotation(Results, "p"); - - const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo"); - ASSERT_THAT(FooDecl, NotNull()); - - const auto *FooVal = Env.getValue(*FooDecl); - EXPECT_EQ(FooVal->getProperty("is_null"), + const auto &FooVal = getValueForDecl<Value>(ASTCtx, Env, "Foo"); + EXPECT_EQ(FooVal.getProperty("is_null"), &Env.getBoolLiteralValue(false)); }); } +TEST_F(WideningTest, DistinctValuesWithDifferentPropertiesWidenedToTop) { + std::string Code = R"( + void target(bool Cond) { + int *Foo; + int i = 0; + Foo = nullptr; + while (Cond) { + Foo = &i; + } + (void)0; + /*[[p]]*/ + } + )"; + runDataflow( + Code, + [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results, + ASTContext &ASTCtx) { + const Environment &Env = getEnvironmentAtAnnotation(Results, "p"); + const auto &FooVal = getValueForDecl<Value>(ASTCtx, Env, "Foo"); + ASSERT_THAT(FooVal.getProperty("is_null"), NotNull()); + EXPECT_TRUE(areEquivalentValues(*FooVal.getProperty("is_null"), + Env.makeTopBoolValue())); + }); +} + class FlowConditionTest : public Test { protected: template <typename Matcher> _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
