From: Richard Biener <rguenther@suse.de>
To: gcc-patches@gcc.gnu.org
Subject: [PATCH] Remove MAX_SWITCH_CASES limit
Date: Mon, 5 Sep 2022 14:47:19 +0200 (CEST) [thread overview]
Message-ID: <20220905124719.5341B13A66@imap2.suse-dmz.suse.de> (raw)
The following removes the MAX_SWITCH_CASES limit to fight quadraticness
when looking up case labels from edges. Instead use the
{start,end}_recording_case_labels facility for that. For it to be
usable I've exported get_cases_for_edge from tree-cfg.cc.
Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
Richard.
* tree-cfg.h (get_cases_for_edge): Declare.
* tree-cfg.cc (get_cases_for_edge): Export.
* tree-ssa-uninit.cc (execute_late_warn_uninitialized):
Start and end recording case labels.
* gimple-predicate-analysis.cc (MAX_SWITCH_CASES): Remove.
(predicate::init_from_control_deps): Use get_cases_for_edge.
---
gcc/gimple-predicate-analysis.cc | 24 ++----------------------
gcc/tree-cfg.cc | 2 +-
gcc/tree-cfg.h | 1 +
gcc/tree-ssa-uninit.cc | 4 ++++
4 files changed, 8 insertions(+), 23 deletions(-)
diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
index 6684aa6c179..681047deee7 100644
--- a/gcc/gimple-predicate-analysis.cc
+++ b/gcc/gimple-predicate-analysis.cc
@@ -52,10 +52,6 @@
#define MAX_NUM_CHAINS 8
#define MAX_CHAIN_LEN 5
-/* The limit for the number of switch cases when we do the linear search
- for the case corresponding to an edge. */
-#define MAX_SWITCH_CASES 40
-
/* Return true if X1 is the negation of X2. */
static inline bool
@@ -1751,28 +1747,12 @@ predicate::init_from_control_deps (const vec<edge> *dep_chains,
}
else if (gswitch *gs = dyn_cast<gswitch *> (cond_stmt))
{
- tree l = NULL_TREE;
/* Find the case label, but avoid quadratic behavior. */
- if (gimple_switch_num_labels (gs) <= MAX_SWITCH_CASES)
- for (unsigned idx = 0;
- idx < gimple_switch_num_labels (gs); ++idx)
- {
- tree tl = gimple_switch_label (gs, idx);
- if (e->dest == label_to_block (cfun, CASE_LABEL (tl)))
- {
- if (!l)
- l = tl;
- else
- {
- l = NULL_TREE;
- break;
- }
- }
- }
+ tree l = get_cases_for_edge (e, gs);
/* If more than one label reaches this block or the case
label doesn't have a contiguous range of values (like the
default one) fail. */
- if (!l || !CASE_LOW (l))
+ if (!l || CASE_CHAIN (l) || !CASE_LOW (l))
has_valid_pred = false;
else if (!CASE_HIGH (l)
|| operand_equal_p (CASE_LOW (l), CASE_HIGH (l)))
diff --git a/gcc/tree-cfg.cc b/gcc/tree-cfg.cc
index 91ec33c80a4..bbe08357d6e 100644
--- a/gcc/tree-cfg.cc
+++ b/gcc/tree-cfg.cc
@@ -1305,7 +1305,7 @@ end_recording_case_labels (void)
Otherwise return NULL. */
-static tree
+tree
get_cases_for_edge (edge e, gswitch *t)
{
tree *slot;
diff --git a/gcc/tree-cfg.h b/gcc/tree-cfg.h
index cb67cdf87ac..95ec93e3a91 100644
--- a/gcc/tree-cfg.h
+++ b/gcc/tree-cfg.h
@@ -33,6 +33,7 @@ extern void init_empty_tree_cfg_for_function (struct function *);
extern void init_empty_tree_cfg (void);
extern void start_recording_case_labels (void);
extern void end_recording_case_labels (void);
+extern tree get_cases_for_edge (edge, gswitch *);
extern basic_block label_to_block (struct function *, tree);
extern void cleanup_dead_labels (void);
extern bool group_case_labels_stmt (gswitch *);
diff --git a/gcc/tree-ssa-uninit.cc b/gcc/tree-ssa-uninit.cc
index 29dc48c4a29..4a1c333d9cb 100644
--- a/gcc/tree-ssa-uninit.cc
+++ b/gcc/tree-ssa-uninit.cc
@@ -1402,6 +1402,9 @@ execute_late_warn_uninitialized (function *fun)
timevar_push (TV_TREE_UNINIT);
+ /* Avoid quadratic beahvior when looking up case labels for edges. */
+ start_recording_case_labels ();
+
possibly_undefined_names = new hash_set<tree>;
defined_args = new hash_map<gphi *, uninit_analysis::func_t::phi_arg_set_t>;
@@ -1432,6 +1435,7 @@ execute_late_warn_uninitialized (function *fun)
possibly_undefined_names = NULL;
delete defined_args;
defined_args = NULL;
+ end_recording_case_labels ();
free_dominance_info (CDI_POST_DOMINATORS);
timevar_pop (TV_TREE_UNINIT);
}
--
2.35.3
reply other threads:[~2022-09-05 12:47 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20220905124719.5341B13A66@imap2.suse-dmz.suse.de \
--to=rguenther@suse.de \
--cc=gcc-patches@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).