[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/ymand created https://github.com/llvm/llvm-project/pull/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.
>From 6889df911a11fc5c27149f138176166aef3e1f73 Mon Sep 17 00:00:00 2001
From: Yitzhak Mandelbaum
Date: Mon, 1 Apr 2024 12:13:39 +
Subject: [PATCH] [clang][dataflow] Refactor `widen` API to be explicit about
change effect.
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.
---
.../FlowSensitive/DataflowEnvironment.h | 43 +--
.../FlowSensitive/DataflowEnvironment.cpp | 42 ++
2 files changed, 53 insertions(+), 32 deletions(-)
diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
index c30bccd06674a4..8e4e846e594f5b 100644
--- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
+++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
@@ -97,6 +97,16 @@ class Environment {
const Value &Val2, const Environment &Env2,
Value &JoinedVal, Environment &JoinedEnv) {}
+/// The result of the `widen` operation.
+struct WidenResult {
+ /// Non-null pointer to a potentially widened version of the widening
+ /// input.
+ Value *V;
+ /// Whether `V` represents a "change" (that is, a different value) with
+ /// respect to the previous value in the sequence.
+ LatticeJoinEffect Effect;
+};
+
/// This function may widen the current value -- replace it with an
/// approximation that can reach a fixed point more quickly than iterated
/// application of the transfer function alone. The previous value is
@@ -104,14 +114,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 `LatticeJoinEffect` 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 +135,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 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::Unknown:
+ return std::nullopt;
case ComparisonResult::Same:
- return &Prev;
+ return WidenResult{&Current, LatticeJoinEffect::Unchanged};
case ComparisonResult::Different:
- return &Current;
-case ComparisonResult::Unknown:
- return nullptr;
+ return WidenResult{&Current, LatticeJoinEffect::Changed};
}
llvm_unreachable("all cases in switch covered");
}
diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
index f729d676dd0de8..d41f03262ecf4c 100644
--- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ b/clang/lib/An
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
llvmbot wrote:
@llvm/pr-subscribers-clang
Author: Yitzhak Mandelbaum (ymand)
Changes
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.
---
Full diff: https://github.com/llvm/llvm-project/pull/87233.diff
2 Files Affected:
- (modified) clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
(+29-14)
- (modified) clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp (+24-18)
``diff
diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
index c30bccd06674a4..8e4e846e594f5b 100644
--- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
+++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
@@ -97,6 +97,16 @@ class Environment {
const Value &Val2, const Environment &Env2,
Value &JoinedVal, Environment &JoinedEnv) {}
+/// The result of the `widen` operation.
+struct WidenResult {
+ /// Non-null pointer to a potentially widened version of the widening
+ /// input.
+ Value *V;
+ /// Whether `V` represents a "change" (that is, a different value) with
+ /// respect to the previous value in the sequence.
+ LatticeJoinEffect Effect;
+};
+
/// This function may widen the current value -- replace it with an
/// approximation that can reach a fixed point more quickly than iterated
/// application of the transfer function alone. The previous value is
@@ -104,14 +114,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 `LatticeJoinEffect` 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 +135,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 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::Unknown:
+ return std::nullopt;
case ComparisonResult::Same:
- return &Prev;
+ return WidenResult{&Current, LatticeJoinEffect::Unchanged};
case ComparisonResult::Different:
- return &Current;
-case ComparisonResult::Unknown:
- return nullptr;
+ return WidenResult{&Current, LatticeJoinEffect::Changed};
}
llvm_unreachable("all cases in switch covered");
}
diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
index f729d676dd0de8..d41f03262ecf4c 100644
--- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
@@ -166,17 +166,19 @@ 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,
-
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
github-actions[bot] wrote:
:warning: C/C++ code formatter, clang-format found issues in your code.
:warning:
You can test this locally with the following command:
``bash
git-clang-format --diff a1a8bb1d3ae9a535526aba9514e87f76e2d040fa
6889df911a11fc5c27149f138176166aef3e1f73 --
clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
``
View the diff from clang-format here.
``diff
diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
index 8e4e846e59..0a37d9d68e 100644
--- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
+++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
@@ -142,12 +142,12 @@ public:
// 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::Unknown:
- return std::nullopt;
-case ComparisonResult::Same:
- return WidenResult{&Current, LatticeJoinEffect::Unchanged};
-case ComparisonResult::Different:
- return WidenResult{&Current, LatticeJoinEffect::Changed};
+ case ComparisonResult::Unknown:
+return std::nullopt;
+ case ComparisonResult::Same:
+return WidenResult{&Current, LatticeJoinEffect::Unchanged};
+ case ComparisonResult::Different:
+return WidenResult{&Current, LatticeJoinEffect::Changed};
}
llvm_unreachable("all cases in switch covered");
}
diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
index d41f03262e..8ae51b7cdb 100644
--- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
@@ -170,9 +170,10 @@ namespace {
using WidenResult = Environment::ValueModel::WidenResult;
}
-static WidenResult 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(&Prev)) {
if (isa(Prev))
``
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/87233
>From b7f63ed7ca3c503f55eccc215f0a66368e2c5e5e Mon Sep 17 00:00:00 2001
From: Yitzhak Mandelbaum
Date: Mon, 1 Apr 2024 12:13:39 +
Subject: [PATCH] [clang][dataflow] Refactor `widen` API to be explicit about
change effect.
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.
---
.../FlowSensitive/DataflowEnvironment.h | 47 ---
.../FlowSensitive/DataflowEnvironment.cpp | 43 ++---
2 files changed, 56 insertions(+), 34 deletions(-)
diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
index c30bccd06674a4..0a37d9d68e2898 100644
--- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
+++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
@@ -97,6 +97,16 @@ class Environment {
const Value &Val2, const Environment &Env2,
Value &JoinedVal, Environment &JoinedEnv) {}
+/// The result of the `widen` operation.
+struct WidenResult {
+ /// Non-null pointer to a potentially widened version of the widening
+ /// input.
+ Value *V;
+ /// Whether `V` represents a "change" (that is, a different value) with
+ /// respect to the previous value in the sequence.
+ LatticeJoinEffect Effect;
+};
+
/// This function may widen the current value -- replace it with an
/// approximation that can reach a fixed point more quickly than iterated
/// application of the transfer function alone. The previous value is
@@ -104,14 +114,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 `LatticeJoinEffect` 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 +135,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 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, LatticeJoinEffect::Unchanged};
+ case ComparisonResult::Different:
+return WidenResult{&Current, LatticeJoinEffect::Changed};
}
llvm_unreachable("all cases in switch covered");
}
diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
index f729d676dd0de8..8ae51b7cdb444d 100644
--- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
@@ -166,17 +166,20 @@ static Value *joinDistinctValues(QualType Type, Value
&Val1,
return JoinedVal;
}
-// When widening does not c
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/87233
>From d8d875271bd47b71701143afb06ea654546e2b7c Mon Sep 17 00:00:00 2001
From: Yitzhak Mandelbaum
Date: Mon, 1 Apr 2024 12:13:39 +
Subject: [PATCH] [clang][dataflow] Refactor `widen` API to be explicit about
change effect.
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.
---
.../FlowSensitive/DataflowEnvironment.h | 47 +++---
.../FlowSensitive/DataflowEnvironment.cpp | 43 ++---
.../TypeErasedDataflowAnalysisTest.cpp| 48 +++
3 files changed, 104 insertions(+), 34 deletions(-)
diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
index c30bccd06674a4..0a37d9d68e2898 100644
--- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
+++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
@@ -97,6 +97,16 @@ class Environment {
const Value &Val2, const Environment &Env2,
Value &JoinedVal, Environment &JoinedEnv) {}
+/// The result of the `widen` operation.
+struct WidenResult {
+ /// Non-null pointer to a potentially widened version of the widening
+ /// input.
+ Value *V;
+ /// Whether `V` represents a "change" (that is, a different value) with
+ /// respect to the previous value in the sequence.
+ LatticeJoinEffect Effect;
+};
+
/// This function may widen the current value -- replace it with an
/// approximation that can reach a fixed point more quickly than iterated
/// application of the transfer function alone. The previous value is
@@ -104,14 +114,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 `LatticeJoinEffect` 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 +135,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 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, LatticeJoinEffect::Unchanged};
+ case ComparisonResult::Different:
+return WidenResult{&Current, LatticeJoinEffect::Changed};
}
llvm_unreachable("all cases in switch covered");
}
diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
index f729d676dd0de8..8ae51b7cdb444d 100644
--- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
@@ -166,17 +166,20 @@ static Value *joinDistinctValues(QualType Ty
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -97,21 +97,34 @@ class Environment {
const Value &Val2, const Environment &Env2,
Value &JoinedVal, Environment &JoinedEnv) {}
+/// The result of the `widen` operation.
+struct WidenResult {
+ /// Non-null pointer to a potentially widened version of the widening
+ /// input.
martinboehme wrote:
```suggestion
/// Non-null pointer to a potentially widened version of the input
/// value.
```
("Widening input" is intended to mean "input to widening" but could also be
misinterpreted as "input that widens". As it's clear that the context is
widening, maybe just "input value"?)
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/martinboehme requested changes to this pull request. Nice. This is _much_ clearer! Mostly nits, the only substantive question I have is how we will migrate existing overrides. https://github.com/llvm/llvm-project/pull/87233 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/martinboehme edited https://github.com/llvm/llvm-project/pull/87233 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -975,6 +994,35 @@ TEST_F(WideningTest,
DistinctValuesWithSamePropertiesAreEquivalent) {
});
}
+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> &Results,
+ ASTContext &ASTCtx) {
+ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
martinboehme wrote:
We do this in a lot of existing tests, but it's unnecessary:
`getEnvironmentAtAnnotation()` itself asserts that the annotation exists.
```suggestion
```
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -975,6 +994,35 @@ TEST_F(WideningTest,
DistinctValuesWithSamePropertiesAreEquivalent) {
});
}
+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> &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_TRUE(areEquivalentValues(*FooVal->getProperty("is_null"),
martinboehme wrote:
I think we also want to test that `getProperty()` returns non-null?
Easiest way might be `*cast(FooVal->getProperty("is_null"))`.
(`cast` asserts that its argument is non-null.)
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -122,17 +135,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 widen(QualType Type, Value &Prev,
martinboehme wrote:
How are we going to deal with the fact that this API change breaks existing
overrides? (There's an existing
[override](https://github.com/google/crubit/blob/d51d5d004caa1d7c6cf5341d1fab22f5bae02018/nullability/pointer_nullability_analysis.cc#L1752)
in Crubit's nullability check.)
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -166,17 +166,20 @@ 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) {
+namespace {
+using WidenResult = Environment::ValueModel::WidenResult;
+}
+
+static WidenResult widenDistinctValues(QualType Type, Value &Prev,
martinboehme wrote:
```suggestion
static Environment::ValueModel::WidenResult widenDistinctValues(QualType Type,
Value &Prev,
```
AFAICT, this is used exactly once. Maybe just spell it out?
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -975,6 +994,35 @@ TEST_F(WideningTest,
DistinctValuesWithSamePropertiesAreEquivalent) {
});
}
+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> &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);
martinboehme wrote:
```suggestion
const auto &FooVal = getValueForDecl(ASTCtx, Env, "Foo");
```
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -805,6 +805,25 @@ class NullPointerAnalysis final
else
JoinedVal.setProperty("is_null", JoinedEnv.makeTopBoolValue());
}
+
+ std::optional widen(QualType Type, Value &Prev,
+ const Environment &PrevEnv, Value &Current,
+ Environment &CurrentEnv) override {
martinboehme wrote:
This appears to be more than an API change in that this model didn't have a
widening operation at all before. Can you explain why this has been added? (Is
it necessary as part of this patch, or just an additional embellishment?)
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -122,17 +135,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 widen(QualType Type, Value &Prev,
ymand wrote:
That's the *only* override I could find. So, I think we'll just prepare a patch
to crubit to coincide with pushing this.
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -805,6 +805,25 @@ class NullPointerAnalysis final
else
JoinedVal.setProperty("is_null", JoinedEnv.makeTopBoolValue());
}
+
+ std::optional widen(QualType Type, Value &Prev,
+ const Environment &PrevEnv, Value &Current,
+ Environment &CurrentEnv) override {
ymand wrote:
I added this so that we can test the widening functionality. Turns out we had
no tests for framework calls to `widen`.
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -975,6 +994,35 @@ TEST_F(WideningTest,
DistinctValuesWithSamePropertiesAreEquivalent) {
});
}
+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> &Results,
+ ASTContext &ASTCtx) {
+ASSERT_THAT(Results.keys(), UnorderedElementsAre("p"));
ymand wrote:
Great. I've removed it here and in all other cases of WideningTest.
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -975,6 +994,35 @@ TEST_F(WideningTest,
DistinctValuesWithSamePropertiesAreEquivalent) {
});
}
+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> &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_TRUE(areEquivalentValues(*FooVal->getProperty("is_null"),
ymand wrote:
I prefer direct assertion, because it results in a cleaner error message on
failure (crashing the test process vs exiting the test with a test-assertion
failure).
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/87233
>From d8d875271bd47b71701143afb06ea654546e2b7c Mon Sep 17 00:00:00 2001
From: Yitzhak Mandelbaum
Date: Mon, 1 Apr 2024 12:13:39 +
Subject: [PATCH 1/2] [clang][dataflow] Refactor `widen` API to be explicit
about change effect.
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.
---
.../FlowSensitive/DataflowEnvironment.h | 47 +++---
.../FlowSensitive/DataflowEnvironment.cpp | 43 ++---
.../TypeErasedDataflowAnalysisTest.cpp| 48 +++
3 files changed, 104 insertions(+), 34 deletions(-)
diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
index c30bccd06674a4..0a37d9d68e2898 100644
--- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
+++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
@@ -97,6 +97,16 @@ class Environment {
const Value &Val2, const Environment &Env2,
Value &JoinedVal, Environment &JoinedEnv) {}
+/// The result of the `widen` operation.
+struct WidenResult {
+ /// Non-null pointer to a potentially widened version of the widening
+ /// input.
+ Value *V;
+ /// Whether `V` represents a "change" (that is, a different value) with
+ /// respect to the previous value in the sequence.
+ LatticeJoinEffect Effect;
+};
+
/// This function may widen the current value -- replace it with an
/// approximation that can reach a fixed point more quickly than iterated
/// application of the transfer function alone. The previous value is
@@ -104,14 +114,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 `LatticeJoinEffect` 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 +135,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 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, LatticeJoinEffect::Unchanged};
+ case ComparisonResult::Different:
+return WidenResult{&Current, LatticeJoinEffect::Changed};
}
llvm_unreachable("all cases in switch covered");
}
diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
index f729d676dd0de8..8ae51b7cdb444d 100644
--- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
@@ -166,17 +166,20 @@ static Value *joinDistinctValues(QualTyp
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/87233
>From d8d875271bd47b71701143afb06ea654546e2b7c Mon Sep 17 00:00:00 2001
From: Yitzhak Mandelbaum
Date: Mon, 1 Apr 2024 12:13:39 +
Subject: [PATCH 1/3] [clang][dataflow] Refactor `widen` API to be explicit
about change effect.
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.
---
.../FlowSensitive/DataflowEnvironment.h | 47 +++---
.../FlowSensitive/DataflowEnvironment.cpp | 43 ++---
.../TypeErasedDataflowAnalysisTest.cpp| 48 +++
3 files changed, 104 insertions(+), 34 deletions(-)
diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
index c30bccd06674a4..0a37d9d68e2898 100644
--- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
+++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
@@ -97,6 +97,16 @@ class Environment {
const Value &Val2, const Environment &Env2,
Value &JoinedVal, Environment &JoinedEnv) {}
+/// The result of the `widen` operation.
+struct WidenResult {
+ /// Non-null pointer to a potentially widened version of the widening
+ /// input.
+ Value *V;
+ /// Whether `V` represents a "change" (that is, a different value) with
+ /// respect to the previous value in the sequence.
+ LatticeJoinEffect Effect;
+};
+
/// This function may widen the current value -- replace it with an
/// approximation that can reach a fixed point more quickly than iterated
/// application of the transfer function alone. The previous value is
@@ -104,14 +114,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 `LatticeJoinEffect` 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 +135,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 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, LatticeJoinEffect::Unchanged};
+ case ComparisonResult::Different:
+return WidenResult{&Current, LatticeJoinEffect::Changed};
}
llvm_unreachable("all cases in switch covered");
}
diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
index f729d676dd0de8..8ae51b7cdb444d 100644
--- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
@@ -166,17 +166,20 @@ static Value *joinDistinctValues(QualTyp
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -975,6 +994,35 @@ TEST_F(WideningTest,
DistinctValuesWithSamePropertiesAreEquivalent) {
});
}
+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> &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);
ymand wrote:
Done
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
ymand wrote: Martin, I've addressed all of your comments. PTAL. https://github.com/llvm/llvm-project/pull/87233 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -805,6 +805,25 @@ class NullPointerAnalysis final
else
JoinedVal.setProperty("is_null", JoinedEnv.makeTopBoolValue());
}
+
+ std::optional widen(QualType Type, Value &Prev,
+ const Environment &PrevEnv, Value &Current,
+ Environment &CurrentEnv) override {
martinboehme wrote:
Wow -- makes sense to add this then!
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -122,17 +135,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 widen(QualType Type, Value &Prev,
martinboehme wrote:
Makes sense, thanks for the explanation.
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -975,6 +989,35 @@ TEST_F(WideningTest,
DistinctValuesWithSamePropertiesAreEquivalent) {
});
}
+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> &Results,
+ ASTContext &ASTCtx) {
+const Environment &Env = getEnvironmentAtAnnotation(Results, "p");
+
+const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+ASSERT_THAT(FooDecl, NotNull());
+
martinboehme wrote:
```suggestion
```
`getValueForDecl()` asserts that the declaration exists.
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/martinboehme edited https://github.com/llvm/llvm-project/pull/87233 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/martinboehme approved this pull request. https://github.com/llvm/llvm-project/pull/87233 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -975,6 +994,35 @@ TEST_F(WideningTest,
DistinctValuesWithSamePropertiesAreEquivalent) {
});
}
+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> &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_TRUE(areEquivalentValues(*FooVal->getProperty("is_null"),
martinboehme wrote:
Looks good!
https://github.com/llvm/llvm-project/pull/87233
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/87233
>From d8d875271bd47b71701143afb06ea654546e2b7c Mon Sep 17 00:00:00 2001
From: Yitzhak Mandelbaum
Date: Mon, 1 Apr 2024 12:13:39 +
Subject: [PATCH 1/4] [clang][dataflow] Refactor `widen` API to be explicit
about change effect.
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.
---
.../FlowSensitive/DataflowEnvironment.h | 47 +++---
.../FlowSensitive/DataflowEnvironment.cpp | 43 ++---
.../TypeErasedDataflowAnalysisTest.cpp| 48 +++
3 files changed, 104 insertions(+), 34 deletions(-)
diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
index c30bccd06674a4..0a37d9d68e2898 100644
--- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
+++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h
@@ -97,6 +97,16 @@ class Environment {
const Value &Val2, const Environment &Env2,
Value &JoinedVal, Environment &JoinedEnv) {}
+/// The result of the `widen` operation.
+struct WidenResult {
+ /// Non-null pointer to a potentially widened version of the widening
+ /// input.
+ Value *V;
+ /// Whether `V` represents a "change" (that is, a different value) with
+ /// respect to the previous value in the sequence.
+ LatticeJoinEffect Effect;
+};
+
/// This function may widen the current value -- replace it with an
/// approximation that can reach a fixed point more quickly than iterated
/// application of the transfer function alone. The previous value is
@@ -104,14 +114,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 `LatticeJoinEffect` 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 +135,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 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, LatticeJoinEffect::Unchanged};
+ case ComparisonResult::Different:
+return WidenResult{&Current, LatticeJoinEffect::Changed};
}
llvm_unreachable("all cases in switch covered");
}
diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
index f729d676dd0de8..8ae51b7cdb444d 100644
--- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
@@ -166,17 +166,20 @@ static Value *joinDistinctValues(QualTyp
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
ymand wrote: I also fixed up the other tests to use `getValue/LocForDecl` to be consistent. https://github.com/llvm/llvm-project/pull/87233 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
martinboehme wrote: > I also fixed up the other tests to use `getValue/LocForDecl` to be consistent. That's great -- thanks for doing this! I have always been meaning to do a cleanup but have never gotten round to it. https://github.com/llvm/llvm-project/pull/87233 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
