[PATCH] Remove MAX_SWITCH_CASES limit

[PATCH] Remove MAX_SWITCH_CASES limit

[Richard Biener]

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