From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1666) id 6991B385701F; Mon, 5 Sep 2022 13:15:30 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6991B385701F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1662383730; bh=lEfrsjSa2RKwaruSjnfep1FiFBjfUqR1N4PmIbCkOow=; h=From:To:Subject:Date:From; b=TDNetsj7x12q82ttpbj7fFvD/7Bd9SN2koYMXq5ejVVryxC63NFOqyt9nHNne+yiE DW/Bxrg8cSQYfBQH6H1o52lvpfymKGwzw0cYD+nTdIOY+w6Lopk3nfFNp1EDIPHH+9 QwDb7UEhReu2afNflUp40lrCnhEQzMZJY7ETVQ3s= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Richard Biener To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-2437] Remove MAX_SWITCH_CASES limit X-Act-Checkin: gcc X-Git-Author: Richard Biener X-Git-Refname: refs/heads/master X-Git-Oldrev: e9ea2688271bd0b4319bdfb1fc852169ab3cf076 X-Git-Newrev: 178447296423ff7e1072621185438c45ab5b0a1d Message-Id: <20220905131530.6991B385701F@sourceware.org> Date: Mon, 5 Sep 2022 13:15:30 +0000 (GMT) List-Id: https://gcc.gnu.org/g:178447296423ff7e1072621185438c45ab5b0a1d commit r13-2437-g178447296423ff7e1072621185438c45ab5b0a1d Author: Richard Biener Date: Mon Sep 5 14:22:51 2022 +0200 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. Diff: --- 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 *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 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; 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); }