[clang] [-Wcompletion-handler] Fix a non-termination issue (PR #78380)
https://github.com/ziqingluo-90 closed https://github.com/llvm/llvm-project/pull/78380 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [-Wcompletion-handler] Fix a non-termination issue (PR #78380)
https://github.com/SavchenkoValeriy approved this pull request. Awesome! Thank you for fixing the problem and for describing it so in detail. https://github.com/llvm/llvm-project/pull/78380 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [-Wcompletion-handler] Fix a non-termination issue (PR #78380)
ziqingluo-90 wrote: @SavchenkoValeriy, sorry for the late response. Your suggested fix works for my minimal example as well as my local project where this bug was originated. And I failed to come up with a new counter-example for the fix so I believe it will also prevent future non-termination issues. I have updated the PR with respect to the simpler fix. https://github.com/llvm/llvm-project/pull/78380 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [-Wcompletion-handler] Fix a non-termination issue (PR #78380)
https://github.com/ziqingluo-90 updated
https://github.com/llvm/llvm-project/pull/78380
>From e7c3a3fc2a4f5d5714044a1c407bfe56f328680d Mon Sep 17 00:00:00 2001
From: Ziqing Luo
Date: Tue, 16 Jan 2024 17:45:01 -0800
Subject: [PATCH 1/4] [-Wcompletion-handler] Fix a non-termination issue
The Called-Once dataflow analysis could never terminate as a
consequence of non-monotonic update on states. States of kind Escape
can override states leading to non-monotonic update.
The fix uses finite state sets instead of single states to represent
CFG block outputs, which grows in uni-direction. To preserve the
behavior of the analyzer, a single state can be extracted from a state
set. The extraction follows the idea that Escape can override error
states within one block but obeys to the partial-order for join.
rdar://119671856
---
clang/lib/Analysis/CalledOnceCheck.cpp | 120 ++---
clang/test/SemaObjC/warn-called-once.m | 10 +++
2 files changed, 120 insertions(+), 10 deletions(-)
diff --git a/clang/lib/Analysis/CalledOnceCheck.cpp
b/clang/lib/Analysis/CalledOnceCheck.cpp
index 04c5f6aa9c7450..3fab93b1d09cdf 100644
--- a/clang/lib/Analysis/CalledOnceCheck.cpp
+++ b/clang/lib/Analysis/CalledOnceCheck.cpp
@@ -163,7 +163,7 @@ class ParameterStatus {
NotVisited = 0x8, /* 1000 */
// We already reported a violation and stopped tracking calls for this
// parameter.
-Reported = 0x15, /* */
+Reported = 0xF, /* */
LLVM_MARK_AS_BITMASK_ENUM(/* LargestValue = */ Reported)
};
@@ -215,6 +215,55 @@ class ParameterStatus {
const Expr *Call = nullptr;
};
+// Represents a set of `ParameterStatus`s collected in a single CFGBlock.
+class ParamStatusSet {
+private:
+ // The kinds of `States` spans from 0x0 to 0x15, so 16 bits are enough:
+ llvm::BitVector Set{16, false};
+ // Following the exisitng idea: if there are multiple calls of interest in
one
+ // block, recording one of them is good enough.
+ const Expr *Call = nullptr;
+
+public:
+ ParamStatusSet() {}
+
+ // Add a new `ParameterStatus` to the set. Returns true iff the adding
status
+ // was new to the set.
+ bool add(ParameterStatus PS) {
+assert(PS.getKind() != ParameterStatus::Kind::NotVisited &&
+ "the status cannot be NotVisited after visiting a block");
+if (Set.test(PS.getKind()))
+ return false;
+Set.set(PS.getKind());
+if (PS.seenAnyCalls())
+ Call = &PS.getCall();
+return true;
+ }
+
+ // Get one `ParameterStatus` to represent the set of them. The idea is to
+ // take a join on them but let ESCAPE overrides error statuses.
+ ParameterStatus summaryStatus() {
+unsigned Summary = 0x0;
+
+for (unsigned Idx :
+ llvm::make_range(Set.set_bits_begin(), Set.set_bits_end()))
+ Summary |= Idx;
+assert(Summary == 0x0 || Summary == 0x1 || Summary == 0x3 ||
+ Summary == 0x5 || Summary == 0x7 ||
+ Summary == 0xF && "expecting a defined value");
+
+ParameterStatus::Kind SummaryKind = ParameterStatus::Kind(Summary);
+
+if (SummaryKind > ParameterStatus::Kind::NON_ERROR_STATUS &&
+Set.test(ParameterStatus::Kind::Escaped)) {
+ SummaryKind = ParameterStatus::Kind::Escaped;
+}
+if (ParameterStatus::seenAnyCalls(SummaryKind))
+ return {SummaryKind, Call};
+return {SummaryKind};
+ }
+};
+
/// State aggregates statuses of all tracked parameters.
class State {
public:
@@ -274,6 +323,53 @@ class State {
private:
ParamSizedVector ParamData;
+
+ friend class CFGBlockOutputState;
+
+ State(ParamSizedVector ParamData) : ParamData(ParamData) {}
+
+ unsigned size() const { return ParamData.size(); }
+};
+
+// A different kind of "state" in addition to `State`. `CFGBlockOutputState`
+// are created for dealing with the non-termination issue due to `State`s are
+// not being updated monotonically at the output of each CFGBlock.
+// A `CFGBlockOutputState` is in fact a finite set of `State`s that
+// grows monotonically. One can extract a `State` from a
`CFGBlockOutputState`.
+// Note that the `State`-extraction does NOT guarantee monotone but it
+// respects the existing semantics. Specifically, ESCAPE is "greater than"
+// other error states in a single path but is "less than" them at JOIN.
+//
+// `CFGBlockOutputState` will be used to terminate the fix-point computation.
+class CFGBlockOutputState {
+private:
+ ParamSizedVector StatusSets;
+
+public:
+ CFGBlockOutputState(unsigned Size) : StatusSets{Size} {};
+
+ // Update this `CFGBlockOutputState` with a newly computed `State`. Return
+ // true iff `CFGBlockOutputState` changed.
+ bool update(const State &NewState) {
+bool Changed = false;
+
+for (unsigned Idx = 0; Idx < NewState.size(); ++Idx) {
+ if (StatusSets[Idx].add(NewState.getStatusFor(Idx))) {
+Changed = true;
+ }
+}
+return Changed;
+ }
+
+ // Return a `State` that represents the `CFGBlockOutputState`.
+ State ge
[clang] [-Wcompletion-handler] Fix a non-termination issue (PR #78380)
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 29b5f8f977af9b09aa8f56152baca04cf8750981
a4d18e63952e2b47dd97759bebbfd1095b346665 --
clang/lib/Analysis/CalledOnceCheck.cpp
``
View the diff from clang-format here.
``diff
diff --git a/clang/lib/Analysis/CalledOnceCheck.cpp
b/clang/lib/Analysis/CalledOnceCheck.cpp
index e4cb8d0f36..30cbd257b6 100644
--- a/clang/lib/Analysis/CalledOnceCheck.cpp
+++ b/clang/lib/Analysis/CalledOnceCheck.cpp
@@ -932,7 +932,7 @@ private:
ParameterStatus &CurrentParamStatus = CurrentState.getStatusFor(Index);
// Escape overrides whatever error we think happened.
-if (CurrentParamStatus.isErrorStatus() &&
+if (CurrentParamStatus.isErrorStatus() &&
CurrentParamStatus.getKind() != ParameterStatus::Kind::Reported) {
CurrentParamStatus = ParameterStatus::Escaped;
}
``
https://github.com/llvm/llvm-project/pull/78380
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [-Wcompletion-handler] Fix a non-termination issue (PR #78380)
https://github.com/ziqingluo-90 updated
https://github.com/llvm/llvm-project/pull/78380
>From e7c3a3fc2a4f5d5714044a1c407bfe56f328680d Mon Sep 17 00:00:00 2001
From: Ziqing Luo
Date: Tue, 16 Jan 2024 17:45:01 -0800
Subject: [PATCH 1/3] [-Wcompletion-handler] Fix a non-termination issue
The Called-Once dataflow analysis could never terminate as a
consequence of non-monotonic update on states. States of kind Escape
can override states leading to non-monotonic update.
The fix uses finite state sets instead of single states to represent
CFG block outputs, which grows in uni-direction. To preserve the
behavior of the analyzer, a single state can be extracted from a state
set. The extraction follows the idea that Escape can override error
states within one block but obeys to the partial-order for join.
rdar://119671856
---
clang/lib/Analysis/CalledOnceCheck.cpp | 120 ++---
clang/test/SemaObjC/warn-called-once.m | 10 +++
2 files changed, 120 insertions(+), 10 deletions(-)
diff --git a/clang/lib/Analysis/CalledOnceCheck.cpp
b/clang/lib/Analysis/CalledOnceCheck.cpp
index 04c5f6aa9c7450..3fab93b1d09cdf 100644
--- a/clang/lib/Analysis/CalledOnceCheck.cpp
+++ b/clang/lib/Analysis/CalledOnceCheck.cpp
@@ -163,7 +163,7 @@ class ParameterStatus {
NotVisited = 0x8, /* 1000 */
// We already reported a violation and stopped tracking calls for this
// parameter.
-Reported = 0x15, /* */
+Reported = 0xF, /* */
LLVM_MARK_AS_BITMASK_ENUM(/* LargestValue = */ Reported)
};
@@ -215,6 +215,55 @@ class ParameterStatus {
const Expr *Call = nullptr;
};
+// Represents a set of `ParameterStatus`s collected in a single CFGBlock.
+class ParamStatusSet {
+private:
+ // The kinds of `States` spans from 0x0 to 0x15, so 16 bits are enough:
+ llvm::BitVector Set{16, false};
+ // Following the exisitng idea: if there are multiple calls of interest in
one
+ // block, recording one of them is good enough.
+ const Expr *Call = nullptr;
+
+public:
+ ParamStatusSet() {}
+
+ // Add a new `ParameterStatus` to the set. Returns true iff the adding
status
+ // was new to the set.
+ bool add(ParameterStatus PS) {
+assert(PS.getKind() != ParameterStatus::Kind::NotVisited &&
+ "the status cannot be NotVisited after visiting a block");
+if (Set.test(PS.getKind()))
+ return false;
+Set.set(PS.getKind());
+if (PS.seenAnyCalls())
+ Call = &PS.getCall();
+return true;
+ }
+
+ // Get one `ParameterStatus` to represent the set of them. The idea is to
+ // take a join on them but let ESCAPE overrides error statuses.
+ ParameterStatus summaryStatus() {
+unsigned Summary = 0x0;
+
+for (unsigned Idx :
+ llvm::make_range(Set.set_bits_begin(), Set.set_bits_end()))
+ Summary |= Idx;
+assert(Summary == 0x0 || Summary == 0x1 || Summary == 0x3 ||
+ Summary == 0x5 || Summary == 0x7 ||
+ Summary == 0xF && "expecting a defined value");
+
+ParameterStatus::Kind SummaryKind = ParameterStatus::Kind(Summary);
+
+if (SummaryKind > ParameterStatus::Kind::NON_ERROR_STATUS &&
+Set.test(ParameterStatus::Kind::Escaped)) {
+ SummaryKind = ParameterStatus::Kind::Escaped;
+}
+if (ParameterStatus::seenAnyCalls(SummaryKind))
+ return {SummaryKind, Call};
+return {SummaryKind};
+ }
+};
+
/// State aggregates statuses of all tracked parameters.
class State {
public:
@@ -274,6 +323,53 @@ class State {
private:
ParamSizedVector ParamData;
+
+ friend class CFGBlockOutputState;
+
+ State(ParamSizedVector ParamData) : ParamData(ParamData) {}
+
+ unsigned size() const { return ParamData.size(); }
+};
+
+// A different kind of "state" in addition to `State`. `CFGBlockOutputState`
+// are created for dealing with the non-termination issue due to `State`s are
+// not being updated monotonically at the output of each CFGBlock.
+// A `CFGBlockOutputState` is in fact a finite set of `State`s that
+// grows monotonically. One can extract a `State` from a
`CFGBlockOutputState`.
+// Note that the `State`-extraction does NOT guarantee monotone but it
+// respects the existing semantics. Specifically, ESCAPE is "greater than"
+// other error states in a single path but is "less than" them at JOIN.
+//
+// `CFGBlockOutputState` will be used to terminate the fix-point computation.
+class CFGBlockOutputState {
+private:
+ ParamSizedVector StatusSets;
+
+public:
+ CFGBlockOutputState(unsigned Size) : StatusSets{Size} {};
+
+ // Update this `CFGBlockOutputState` with a newly computed `State`. Return
+ // true iff `CFGBlockOutputState` changed.
+ bool update(const State &NewState) {
+bool Changed = false;
+
+for (unsigned Idx = 0; Idx < NewState.size(); ++Idx) {
+ if (StatusSets[Idx].add(NewState.getStatusFor(Idx))) {
+Changed = true;
+ }
+}
+return Changed;
+ }
+
+ // Return a `State` that represents the `CFGBlockOutputState`.
+ State ge
[clang] [-Wcompletion-handler] Fix a non-termination issue (PR #78380)
SavchenkoValeriy wrote: Hey @ziqingluo-90, thank you for such a detailed description of the problem. It helped me to get up to speed quickly. 🙏 However, I must say that I find this change too intrusive a this point, while not being 100% convinced that it is necessary. Considering these rules (even be it for joining multiple paths), we shouldn't override `Reported` with `Escaped`. At the same time, we do that within a single block thanks to this code: https://github.com/llvm/llvm-project/blob/5fcf907b34355980f77d7665a175b05fea7a6b7b/clang/lib/Analysis/CalledOnceCheck.cpp#L935 We do consider `Reported` to be an error state, and overwrite it. Maybe changing this logic and excluding `Reported` from that condition (i.e. `x.isErrorStatus() && x != Reported`) is the way to go? The reason for that is that we already found a problem on that path and the fact that it escaped before it shouldn't affect our conclusion. Another reason is more formal, `Reported` is supposed to be a top element of the lattice and this logic defies it. Thanks again! https://github.com/llvm/llvm-project/pull/78380 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
