From 178447296423ff7e1072621185438c45ab5b0a1d Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Mon, 5 Sep 2022 14:22:51 +0200 Subject: [PATCH] Remove MAX_SWITCH_CASES limit 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. * 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 6684aa6..681047d 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 *dep_chains, } else if (gswitch *gs = dyn_cast (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 91ec33c..bbe0835 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 cb67cdf..95ec93e 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 29dc48c..4a1c333 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; defined_args = new hash_map; @@ -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.7.4