public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH][RFC] Radically simplify emission of balanced tree for switch statements.
@ 2017-09-14 12:17 Martin Liška
  2017-09-15 22:19 ` Jeff Law
  0 siblings, 1 reply; 31+ messages in thread
From: Martin Liška @ 2017-09-14 12:17 UTC (permalink / raw)
  To: gcc-patches; +Cc: Patrick Palka

[-- Attachment #1: Type: text/plain, Size: 2271 bytes --]

Hello.

As mentioned at Cauldron 2017, second step in switch lowering should be massive
simplification in code that does expansion of balanced tree. Basically it includes
VRP and DCE, which we can for obvious reason do by our own.

The patch does that, and introduces a separate pass for -O0 that's responsible
for lowering at the end of tree pass.

There's a small fallback that I would like to discuss:

1) vrp105.c - there's no longer catches threading opportunity in between default cases:
adding Patrick who can probably help why is the opportunity skipped with expanded tree

2) uninit-18.c where we currently report:

/home/marxin/Programming/gcc/gcc/testsuite/gcc.dg/uninit-18.c:13:12: warning: ‘tmp’ may be used uninitialized in this function [-Wmaybe-uninitialized]
     tmp[5] = 7;    /* { dg-bogus "may be used uninitialized" } */

Am I right that the pass uses VRP?

Last question is whether the pass is properly moved in optimization pipeline?
Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.

Thanks,
Martin

gcc/ChangeLog:

2017-09-14  Martin Liska  <mliska@suse.cz>

	* passes.def: Add pass_lower_switch and pass_lower_switch_O0.
	* tree-pass.h (make_pass_lower_switch_O0): New function.
	* tree-switch-conversion.c (node_has_low_bound): Remove.
	(node_has_high_bound): Likewise.
	(node_is_bounded): Likewise.
	(class pass_lower_switch): Make it a template type and create
	two instances.
	(pass_lower_switch::execute): Add template argument.
	(make_pass_lower_switch): New function.
	(make_pass_lower_switch_O0): New function.
	(do_jump_if_equal): Remove.
	(emit_case_nodes): Simplify to just handle all 3 cases and leave
	all the hard work to tree optimization passes.

gcc/testsuite/ChangeLog:

2017-09-14  Martin Liska  <mliska@suse.cz>

	* gcc.dg/tree-ssa/vrp104.c: Adjust dump file that is scanned.
	* gcc.dg/tree-prof/update-loopch.c: Likewise.
---
 gcc/passes.def                                 |   4 +-
 gcc/testsuite/gcc.dg/tree-prof/update-loopch.c |   2 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp104.c         |   2 +-
 gcc/tree-pass.h                                |   1 +
 gcc/tree-switch-conversion.c                   | 604 +++----------------------
 5 files changed, 72 insertions(+), 541 deletions(-)



[-- Attachment #2: 0001-Radically-simplify-emission-of-balanced-tree-for-swi.patch --]
[-- Type: text/x-patch, Size: 26516 bytes --]

diff --git a/gcc/passes.def b/gcc/passes.def
index 00e75d2b55a..bb371d9bde5 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -314,6 +314,7 @@ along with GCC; see the file COPYING3.  If not see
       POP_INSERT_PASSES ()
       NEXT_PASS (pass_simduid_cleanup);
       NEXT_PASS (pass_lower_vector_ssa);
+      NEXT_PASS (pass_lower_switch);
       NEXT_PASS (pass_cse_reciprocals);
       NEXT_PASS (pass_sprintf_length, true);
       NEXT_PASS (pass_reassoc, false /* insert_powi_p */);
@@ -358,6 +359,7 @@ along with GCC; see the file COPYING3.  If not see
       /* Lower remaining pieces of GIMPLE.  */
       NEXT_PASS (pass_lower_complex);
       NEXT_PASS (pass_lower_vector_ssa);
+      NEXT_PASS (pass_lower_switch);
       /* Perform simple scalar cleanup which is constant/copy propagation.  */
       NEXT_PASS (pass_ccp, true /* nonzero_p */);
       NEXT_PASS (pass_post_ipa_warn);
@@ -393,7 +395,7 @@ along with GCC; see the file COPYING3.  If not see
   NEXT_PASS (pass_lower_vaarg);
   NEXT_PASS (pass_lower_vector);
   NEXT_PASS (pass_lower_complex_O0);
-  NEXT_PASS (pass_lower_switch);
+  NEXT_PASS (pass_lower_switch_O0);
   NEXT_PASS (pass_sancov_O0);
   NEXT_PASS (pass_asan_O0);
   NEXT_PASS (pass_tsan_O0);
diff --git a/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c b/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c
index 73efc878ec0..15baada1081 100644
--- a/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c
+++ b/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c
@@ -1,4 +1,4 @@
-/* { dg-options "-O2 -fdump-ipa-profile-blocks-details -fdump-tree-switchlower-blocks-details" } */
+/* { dg-options "-O2 -fdump-ipa-profile-blocks-details -fdump-tree-switchlower1-blocks-details" } */
 int max = 33333;
 int a[8];
 int
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
index 0a952267b29..71fa3bfa2ca 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
@@ -2,7 +2,7 @@
 /* { dg-options "-O2 -fdump-tree-switchlower" }  */
 /* We scan for 2 switches as the dump file reports a transformation,
    IL really contains just a single.  */
-/* { dg-final { scan-tree-dump-times "switch" 2 "switchlower" } }  */
+/* { dg-final { scan-tree-dump-times "switch" 2 "switchlower1" } }  */
 
 void foo (void);
 void bar (void);
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 9f76d822abc..6ae65765431 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -410,6 +410,7 @@ extern gimple_opt_pass *make_pass_strip_predict_hints (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_complex_O0 (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_complex (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_switch (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_lower_switch_O0 (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_vector (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_vector_ssa (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_omp (gcc::context *ctxt);
diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index 6d7c2c4902f..f67531b2620 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -1685,9 +1685,6 @@ typedef case_node *case_node_ptr;
 static basic_block emit_case_nodes (basic_block, tree, case_node_ptr,
 				    basic_block, tree, profile_probability,
 				    tree, hash_map<tree, tree> *);
-static bool node_has_low_bound (case_node_ptr, tree);
-static bool node_has_high_bound (case_node_ptr, tree);
-static bool node_is_bounded (case_node_ptr, tree);
 
 /* Return the smallest number of different values for which it is best to use a
    jump-table instead of a tree of conditional branches.  */
@@ -2162,10 +2159,31 @@ try_switch_expansion (gswitch *stmt)
 
 namespace {
 
-const pass_data pass_data_lower_switch =
+template <bool O0> class pass_lower_switch: public gimple_opt_pass
 {
-  GIMPLE_PASS, /* type */
-  "switchlower", /* name */
+public:
+  pass_lower_switch (gcc::context *ctxt) : gimple_opt_pass (data, ctxt) {}
+
+  static const pass_data data;
+  opt_pass *
+  clone ()
+  {
+    return new pass_lower_switch<O0> (m_ctxt);
+  }
+
+  virtual bool
+  gate (function *)
+  {
+    return !O0 || !optimize;
+  }
+
+  virtual unsigned int execute (function *fun);
+}; // class pass_lower_switch
+
+template <bool O0>
+const pass_data pass_lower_switch<O0>::data = {
+  GIMPLE_PASS,		       /* type */
+  O0 ? "switchlower_O0" : "switchlower", /* name */
   OPTGROUP_NONE, /* optinfo_flags */
   TV_TREE_SWITCH_LOWERING, /* tv_id */
   ( PROP_cfg | PROP_ssa ), /* properties_required */
@@ -2175,21 +2193,9 @@ const pass_data pass_data_lower_switch =
   TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
 };
 
-class pass_lower_switch : public gimple_opt_pass
-{
-public:
-  pass_lower_switch (gcc::context *ctxt)
-    : gimple_opt_pass (pass_data_lower_switch, ctxt)
-  {}
-
-  /* opt_pass methods: */
-  virtual bool gate (function *) { return true; }
-  virtual unsigned int execute (function *);
-
-}; // class pass_lower_switch
-
+template <bool O0>
 unsigned int
-pass_lower_switch::execute (function *fun)
+pass_lower_switch<O0>::execute (function *fun)
 {
   basic_block bb;
   bool expanded = false;
@@ -2227,33 +2233,14 @@ pass_lower_switch::execute (function *fun)
 } // anon namespace
 
 gimple_opt_pass *
-make_pass_lower_switch (gcc::context *ctxt)
+make_pass_lower_switch_O0 (gcc::context *ctxt)
 {
-  return new pass_lower_switch (ctxt);
+  return new pass_lower_switch<true> (ctxt);
 }
-
-/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
-   PROB is the probability of jumping to LABEL.  */
-static basic_block
-do_jump_if_equal (basic_block bb, tree op0, tree op1, basic_block label_bb,
-		  profile_probability prob, hash_map<tree, tree> *phi_mapping)
+gimple_opt_pass *
+make_pass_lower_switch (gcc::context *ctxt)
 {
-  gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE);
-  gimple_stmt_iterator gsi = gsi_last_bb (bb);
-  gsi_insert_before (&gsi, cond, GSI_SAME_STMT);
-
-  gcc_assert (single_succ_p (bb));
-
-  /* Make a new basic block where false branch will take place.  */
-  edge false_edge = split_block (bb, cond);
-  false_edge->flags = EDGE_FALSE_VALUE;
-  false_edge->probability = prob.invert ();
-
-  edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
-  fix_phi_operands_for_edge (true_edge, phi_mapping);
-  true_edge->probability = prob;
-
-  return false_edge->dest;
+  return new pass_lower_switch<false> (ctxt);
 }
 
 /* Generate code to compare X with Y so that the condition codes are
@@ -2316,28 +2303,7 @@ conditional_probability (profile_probability target_prob,
 /* Emit step-by-step code to select a case for the value of INDEX.
    The thus generated decision tree follows the form of the
    case-node binary tree NODE, whose nodes represent test conditions.
-   INDEX_TYPE is the type of the index of the switch.
-
-   Care is taken to prune redundant tests from the decision tree
-   by detecting any boundary conditions already checked by
-   emitted rtx.  (See node_has_high_bound, node_has_low_bound
-   and node_is_bounded, above.)
-
-   Where the test conditions can be shown to be redundant we emit
-   an unconditional jump to the target code.  As a further
-   optimization, the subordinates of a tree node are examined to
-   check for bounded nodes.  In this case conditional and/or
-   unconditional jumps as a result of the boundary check for the
-   current node are arranged to target the subordinates associated
-   code for out of bound conditions on the current node.
-
-   We can assume that when control reaches the code generated here,
-   the index value has already been compared with the parents
-   of this node, and determined to be on the same side of each parent
-   as this node is.  Thus, if this node tests for the value 51,
-   and a parent tested for 52, we don't need to consider
-   the possibility of a value greater than 51.  If another parent
-   tests for the value 50, then this node need not test anything.  */
+   INDEX_TYPE is the type of the index of the switch.  */
 
 static basic_block
 emit_case_nodes (basic_block bb, tree index, case_node_ptr node,
@@ -2345,482 +2311,44 @@ emit_case_nodes (basic_block bb, tree index, case_node_ptr node,
 		 profile_probability default_prob, tree index_type,
 		 hash_map<tree, tree> *phi_mapping)
 {
-  /* If INDEX has an unsigned type, we must make unsigned branches.  */
-  profile_probability probability;
-  profile_probability prob = node->prob, subtree_prob = node->subtree_prob;
-
-  /* See if our parents have already tested everything for us.
-     If they have, emit an unconditional jump for this node.  */
-  if (node_is_bounded (node, index_type))
-    {
-      emit_jump (bb, node->case_bb, phi_mapping);
-      return NULL;
-    }
-
-  else if (tree_int_cst_equal (node->low, node->high))
-    {
-      probability = conditional_probability (prob, subtree_prob + default_prob);
-      /* Node is single valued.  First see if the index expression matches
-	 this node and then check our children, if any.  */
-      bb = do_jump_if_equal (bb, index, node->low, node->case_bb, probability,
-			     phi_mapping);
-      /* Since this case is taken at this point, reduce its weight from
-	 subtree_weight.  */
-      subtree_prob -= prob;
-      if (node->right != 0 && node->left != 0)
-	{
-	  /* This node has children on both sides.
-	     Dispatch to one side or the other
-	     by comparing the index value with this node's value.
-	     If one subtree is bounded, check that one first,
-	     so we can avoid real branches in the tree.  */
-
-	  if (node_is_bounded (node->right, index_type))
-	    {
-	      probability
-		= conditional_probability (node->right->prob,
-					   subtree_prob + default_prob);
-	      bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
-					    node->right->case_bb, probability,
-					    phi_mapping);
-	      bb = emit_case_nodes (bb, index, node->left, default_bb,
-				    default_label, default_prob, index_type,
-				    phi_mapping);
-	    }
-
-	  else if (node_is_bounded (node->left, index_type))
-	    {
-	      probability
-		= conditional_probability (node->left->prob,
-					   subtree_prob + default_prob);
-	      bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
-					    node->left->case_bb, probability,
-					    phi_mapping);
-	      bb = emit_case_nodes (bb, index, node->right, default_bb,
-				    default_label, default_prob, index_type,
-				    phi_mapping);
-	    }
-
-	  /* If both children are single-valued cases with no
-	     children, finish up all the work.  This way, we can save
-	     one ordered comparison.  */
-	  else if (tree_int_cst_equal (node->right->low, node->right->high)
-		   && node->right->left == 0 && node->right->right == 0
-		   && tree_int_cst_equal (node->left->low, node->left->high)
-		   && node->left->left == 0 && node->left->right == 0)
-	    {
-	      /* Neither node is bounded.  First distinguish the two sides;
-		 then emit the code for one side at a time.  */
-
-	      /* See if the value matches what the right hand side
-		 wants.  */
-	      probability
-		= conditional_probability (node->right->prob,
-					   subtree_prob + default_prob);
-	      bb = do_jump_if_equal (bb, index, node->right->low,
-				     node->right->case_bb, probability,
-				     phi_mapping);
-
-	      /* See if the value matches what the left hand side
-		 wants.  */
-	      probability
-		= conditional_probability (node->left->prob,
-					   subtree_prob + default_prob);
-	      bb = do_jump_if_equal (bb, index, node->left->low,
-				     node->left->case_bb, probability,
-				     phi_mapping);
-	    }
-
-	  else
-	    {
-	      /* Neither node is bounded.  First distinguish the two sides;
-		 then emit the code for one side at a time.  */
-
-	      basic_block test_bb = split_edge (single_succ_edge (bb));
-	      redirect_edge_succ (single_pred_edge (test_bb),
-				  single_succ_edge (bb)->dest);
-
-	      /* The default label could be reached either through the right
-		 subtree or the left subtree.  Divide the probability
-		 equally.  */
-	      probability
-		= conditional_probability (node->right->subtree_prob
-					     + default_prob.apply_scale (1, 2),
-					   subtree_prob + default_prob);
-	      /* See if the value is on the right.  */
-	      bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
-					    test_bb, probability, phi_mapping);
-	      default_prob = default_prob.apply_scale (1, 2);
-
-	      /* Value must be on the left.
-		 Handle the left-hand subtree.  */
-	      bb = emit_case_nodes (bb, index, node->left, default_bb,
-				    default_label, default_prob, index_type,
-				    phi_mapping);
-	      /* If left-hand subtree does nothing,
-		 go to default.  */
-
-	      if (bb && default_bb)
-		emit_jump (bb, default_bb, phi_mapping);
-
-	      /* Code branches here for the right-hand subtree.  */
-	      bb = emit_case_nodes (test_bb, index, node->right, default_bb,
-				    default_label, default_prob, index_type,
-				    phi_mapping);
-	    }
-	}
-      else if (node->right != 0 && node->left == 0)
-	{
-	  /* Here we have a right child but no left so we issue a conditional
-	     branch to default and process the right child.
-
-	     Omit the conditional branch to default if the right child
-	     does not have any children and is single valued; it would
-	     cost too much space to save so little time.  */
-
-	  if (node->right->right || node->right->left
-	      || !tree_int_cst_equal (node->right->low, node->right->high))
-	    {
-	      if (!node_has_low_bound (node, index_type))
-		{
-		  probability
-		    = conditional_probability (default_prob.apply_scale (1, 2),
-					       subtree_prob + default_prob);
-		  bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
-						default_bb, probability,
-						phi_mapping);
-		  default_prob = default_prob.apply_scale (1, 2);
-		}
-
-	      bb = emit_case_nodes (bb, index, node->right, default_bb,
-				    default_label, default_prob, index_type,
-				    phi_mapping);
-	    }
-	  else
-	    {
-	      probability
-		= conditional_probability (node->right->subtree_prob,
-					   subtree_prob + default_prob);
-	      /* We cannot process node->right normally
-		 since we haven't ruled out the numbers less than
-		 this node's value.  So handle node->right explicitly.  */
-	      bb = do_jump_if_equal (bb, index, node->right->low,
-				     node->right->case_bb, probability,
-				     phi_mapping);
-	    }
-	}
-
-      else if (node->right == 0 && node->left != 0)
-	{
-	  /* Just one subtree, on the left.  */
-	  if (node->left->left || node->left->right
-	      || !tree_int_cst_equal (node->left->low, node->left->high))
-	    {
-	      if (!node_has_high_bound (node, index_type))
-		{
-		  probability
-		    = conditional_probability (default_prob.apply_scale (1, 2),
-					       subtree_prob + default_prob);
-		  bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
-						default_bb, probability,
-						phi_mapping);
-		  default_prob = default_prob.apply_scale (1, 2);
-		}
-
-	      bb = emit_case_nodes (bb, index, node->left, default_bb,
-				    default_label, default_prob, index_type,
-				    phi_mapping);
-	    }
-	  else
-	    {
-	      probability
-		= conditional_probability (node->left->subtree_prob,
-					   subtree_prob + default_prob);
-	      /* We cannot process node->left normally
-		 since we haven't ruled out the numbers less than
-		 this node's value.  So handle node->left explicitly.  */
-	      do_jump_if_equal (bb, index, node->left->low, node->left->case_bb,
-				probability, phi_mapping);
-	    }
-	}
-    }
-  else
-    {
-      /* Node is a range.  These cases are very similar to those for a single
-	 value, except that we do not start by testing whether this node
-	 is the one to branch to.  */
-
-      if (node->right != 0 && node->left != 0)
-	{
-	  /* Node has subtrees on both sides.
-	     If the right-hand subtree is bounded,
-	     test for it first, since we can go straight there.
-	     Otherwise, we need to make a branch in the control structure,
-	     then handle the two subtrees.  */
-	  basic_block test_bb = NULL;
-
-	  if (node_is_bounded (node->right, index_type))
-	    {
-	      /* Right hand node is fully bounded so we can eliminate any
-		 testing and branch directly to the target code.  */
-	      probability
-		= conditional_probability (node->right->subtree_prob,
-					   subtree_prob + default_prob);
-	      bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
-					    node->right->case_bb, probability,
-					    phi_mapping);
-	    }
-	  else
-	    {
-	      /* Right hand node requires testing.
-		 Branch to a label where we will handle it later.  */
-
-	      test_bb = split_edge (single_succ_edge (bb));
-	      redirect_edge_succ (single_pred_edge (test_bb),
-				  single_succ_edge (bb)->dest);
-
-	      probability
-		= conditional_probability (node->right->subtree_prob
-					     + default_prob.apply_scale (1, 2),
-					   subtree_prob + default_prob);
-	      bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
-					    test_bb, probability, phi_mapping);
-	      default_prob = default_prob.apply_scale (1, 2);
-	    }
-
-	  /* Value belongs to this node or to the left-hand subtree.  */
-
-	  probability
-	    = conditional_probability (prob, subtree_prob + default_prob);
-	  bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
-					node->case_bb, probability,
-					phi_mapping);
-
-	  /* Handle the left-hand subtree.  */
-	  bb = emit_case_nodes (bb, index, node->left, default_bb,
-				default_label, default_prob, index_type,
+  /* If node is null, we are done.  */
+  if (node == NULL)
+    return bb;
+
+  /* Branch to a label where we will handle it later.  */
+  basic_block test_bb = split_edge (single_succ_edge (bb));
+  redirect_edge_succ (single_pred_edge (test_bb),
+		      single_succ_edge (bb)->dest);
+
+  profile_probability probability
+    = node->right ? node->right->subtree_prob : profile_probability::never ();
+  probability
+    = conditional_probability (probability + default_prob.apply_scale (1, 2),
+			       node->subtree_prob + default_prob);
+  bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
+				test_bb, probability, phi_mapping);
+  default_prob = default_prob.apply_scale (1, 2);
+
+  /* Value belongs to this node or to the left-hand subtree.  */
+  probability
+    = conditional_probability (node->prob, node->subtree_prob + default_prob);
+  bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
+				node->case_bb, probability,
 				phi_mapping);
 
-	  /* If right node had to be handled later, do that now.  */
-	  if (test_bb)
-	    {
-	      /* If the left-hand subtree fell through,
-		 don't let it fall into the right-hand subtree.  */
-	      if (bb && default_bb)
-		emit_jump (bb, default_bb, phi_mapping);
-
-	      bb = emit_case_nodes (test_bb, index, node->right, default_bb,
-				    default_label, default_prob, index_type,
-				    phi_mapping);
-	    }
-	}
-
-      else if (node->right != 0 && node->left == 0)
-	{
-	  /* Deal with values to the left of this node,
-	     if they are possible.  */
-	  if (!node_has_low_bound (node, index_type))
-	    {
-	      probability
-		= conditional_probability (default_prob.apply_scale (1, 2),
-					   subtree_prob + default_prob);
-	      bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
-					    default_bb, probability,
-					    phi_mapping);
-	      default_prob = default_prob.apply_scale (1, 2);
-	    }
-
-	  /* Value belongs to this node or to the right-hand subtree.  */
-
-	  probability
-	    = conditional_probability (prob, subtree_prob + default_prob);
-	  bb = emit_cmp_and_jump_insns (bb, index, node->high, LE_EXPR,
-					node->case_bb, probability,
-					phi_mapping);
-
-	  bb = emit_case_nodes (bb, index, node->right, default_bb,
-				default_label, default_prob, index_type,
-				phi_mapping);
-	}
-
-      else if (node->right == 0 && node->left != 0)
-	{
-	  /* Deal with values to the right of this node,
-	     if they are possible.  */
-	  if (!node_has_high_bound (node, index_type))
-	    {
-	      probability
-		= conditional_probability (default_prob.apply_scale (1, 2),
-					   subtree_prob + default_prob);
-	      bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
-					    default_bb, probability,
-					    phi_mapping);
-	      default_prob = default_prob.apply_scale (1, 2);
-	    }
-
-	  /* Value belongs to this node or to the left-hand subtree.  */
+  /* Handle the left-hand subtree.  */
+  bb = emit_case_nodes (bb, index, node->left, default_bb,
+			default_label, default_prob, index_type,
+			phi_mapping);
 
-	  probability
-	    = conditional_probability (prob, subtree_prob + default_prob);
-	  bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
-					node->case_bb, probability,
-					phi_mapping);
-
-	  bb = emit_case_nodes (bb, index, node->left, default_bb,
-				default_label, default_prob, index_type,
-				phi_mapping);
-	}
-
-      else
-	{
-	  /* Node has no children so we check low and high bounds to remove
-	     redundant tests.  Only one of the bounds can exist,
-	     since otherwise this node is bounded--a case tested already.  */
-	  bool high_bound = node_has_high_bound (node, index_type);
-	  bool low_bound = node_has_low_bound (node, index_type);
-
-	  if (!high_bound && low_bound)
-	    {
-	      probability
-		= conditional_probability (default_prob,
-					   subtree_prob + default_prob);
-	      bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
-					    default_bb, probability,
-					    phi_mapping);
-	    }
-
-	  else if (!low_bound && high_bound)
-	    {
-	      probability
-		= conditional_probability (default_prob,
-					   subtree_prob + default_prob);
-	      bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
-					    default_bb, probability,
-					    phi_mapping);
-	    }
-	  else if (!low_bound && !high_bound)
-	    {
-	      tree lhs, rhs;
-	      generate_range_test (bb, index, node->low, node->high,
-				   &lhs, &rhs);
-	      probability
-		= conditional_probability (default_prob,
-					   subtree_prob + default_prob);
-	      bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,
-					    default_bb, probability,
-					    phi_mapping);
-	    }
+  /* If the left-hand subtree fell through,
+     don't let it fall into the right-hand subtree.  */
+  if (default_bb)
+    emit_jump (bb, default_bb, phi_mapping);
 
-	  emit_jump (bb, node->case_bb, phi_mapping);
-	  return NULL;
-	}
-    }
+  bb = emit_case_nodes (test_bb, index, node->right, default_bb,
+			default_label, default_prob, index_type,
+			phi_mapping);
 
   return bb;
 }
-
-/* Search the parent sections of the case node tree
-   to see if a test for the lower bound of NODE would be redundant.
-   INDEX_TYPE is the type of the index expression.
-
-   The instructions to generate the case decision tree are
-   output in the same order as nodes are processed so it is
-   known that if a parent node checks the range of the current
-   node minus one that the current node is bounded at its lower
-   span.  Thus the test would be redundant.  */
-
-static bool
-node_has_low_bound (case_node_ptr node, tree index_type)
-{
-  tree low_minus_one;
-  case_node_ptr pnode;
-
-  /* If the lower bound of this node is the lowest value in the index type,
-     we need not test it.  */
-
-  if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
-    return true;
-
-  /* If this node has a left branch, the value at the left must be less
-     than that at this node, so it cannot be bounded at the bottom and
-     we need not bother testing any further.  */
-
-  if (node->left)
-    return false;
-
-  low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), node->low,
-			       build_int_cst (TREE_TYPE (node->low), 1));
-
-  /* If the subtraction above overflowed, we can't verify anything.
-     Otherwise, look for a parent that tests our value - 1.  */
-
-  if (!tree_int_cst_lt (low_minus_one, node->low))
-    return false;
-
-  for (pnode = node->parent; pnode; pnode = pnode->parent)
-    if (tree_int_cst_equal (low_minus_one, pnode->high))
-      return true;
-
-  return false;
-}
-
-/* Search the parent sections of the case node tree
-   to see if a test for the upper bound of NODE would be redundant.
-   INDEX_TYPE is the type of the index expression.
-
-   The instructions to generate the case decision tree are
-   output in the same order as nodes are processed so it is
-   known that if a parent node checks the range of the current
-   node plus one that the current node is bounded at its upper
-   span.  Thus the test would be redundant.  */
-
-static bool
-node_has_high_bound (case_node_ptr node, tree index_type)
-{
-  tree high_plus_one;
-  case_node_ptr pnode;
-
-  /* If there is no upper bound, obviously no test is needed.  */
-
-  if (TYPE_MAX_VALUE (index_type) == NULL)
-    return true;
-
-  /* If the upper bound of this node is the highest value in the type
-     of the index expression, we need not test against it.  */
-
-  if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
-    return true;
-
-  /* If this node has a right branch, the value at the right must be greater
-     than that at this node, so it cannot be bounded at the top and
-     we need not bother testing any further.  */
-
-  if (node->right)
-    return false;
-
-  high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), node->high,
-			       build_int_cst (TREE_TYPE (node->high), 1));
-
-  /* If the addition above overflowed, we can't verify anything.
-     Otherwise, look for a parent that tests our value + 1.  */
-
-  if (!tree_int_cst_lt (node->high, high_plus_one))
-    return false;
-
-  for (pnode = node->parent; pnode; pnode = pnode->parent)
-    if (tree_int_cst_equal (high_plus_one, pnode->low))
-      return true;
-
-  return false;
-}
-
-/* Search the parent sections of the
-   case node tree to see if both tests for the upper and lower
-   bounds of NODE would be redundant.  */
-
-static bool
-node_is_bounded (case_node_ptr node, tree index_type)
-{
-  return (node_has_low_bound (node, index_type)
-	  && node_has_high_bound (node, index_type));
-}


^ permalink raw reply	[flat|nested] 31+ messages in thread
* Re: [PATCH] Implement smart multiple switch expansion algorithms.
@ 2017-10-06 13:46 Wilco Dijkstra
  2017-10-06 17:31 ` Mikhail Maltsev
  2017-12-29 14:43 ` Martin Liška
  0 siblings, 2 replies; 31+ messages in thread
From: Wilco Dijkstra @ 2017-10-06 13:46 UTC (permalink / raw)
  To: mliska; +Cc: nd, GCC Patches, Jeff Law, Jan Hubicka

Martin Liska wrote:

> There are some numbers for cc1plus:
>
> $ bloaty ./objdir2/gcc/cc1plus -- ./objdir/gcc/cc1plus
>     VM SIZE                      FILE SIZE
>   +3.8% +1.11Mi TOTAL          +1.03Mi  +0.5%

> insn-attrtab.o:
>     VM SIZE                          FILE SIZE
>   +214%  +682Ki .rodata             +682Ki  +214%
>  -50.1% -63.3Ki .text              -63.3Ki -50.1%

So is that a 3.8% codesize increase or decrease? If an increase,
I can't see how replacing 63KB of instructions with 682KB of data
is a good tradeoff... There should be an accurate calculation
of the density, taking the switch table width into account (really small
tables can use 1-byte offsets, large tables are typically forced to
use 4-byte offsets). This may need new target callbacks - I changed
PARAM_CASE_VALUES_THRESHOLD on AArch64 to get smaller
code and better performance since the current density calculations
are hardcoded and quite wrong for big tables...

Also what is the codesize difference on SPEC2006/2017? I don't see
any mention of performance impact either...

Wilco

^ permalink raw reply	[flat|nested] 31+ messages in thread
end of thread, other threads:[~2018-05-25 10:10 UTC | newest]

Thread overview: 31+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-09-14 12:17 [PATCH][RFC] Radically simplify emission of balanced tree for switch statements Martin Liška
2017-09-15 22:19 ` Jeff Law
2017-09-20  7:24   ` Martin Liška
2017-09-20 15:00     ` Jeff Law
2017-09-21 23:12       ` Bernhard Reutner-Fischer
2018-01-09 14:46       ` Martin Liška
2018-01-09 18:31         ` Jeff Law
2018-01-10 13:14           ` Richard Biener
2018-01-10 15:04             ` Martin Liška
2018-01-14 23:23               ` Bernhard Reutner-Fischer
2018-05-17 10:39                 ` Martin Liška
2018-05-18 13:57                   ` Rainer Orth
2018-05-18 14:19                     ` Martin Liška
2018-05-21 11:29                       ` Rainer Orth
2018-05-21 14:00                         ` Martin Liška
2018-05-21 14:10                           ` Rainer Orth
2018-05-21 14:54                             ` Sudakshina Das
2018-05-24 19:59                               ` Martin Liška
2018-05-25 10:01                               ` Martin Liška
2018-05-25 10:12                                 ` Sudakshina Das
2018-05-24 12:52                           ` Rainer Orth
2018-05-24 20:10                             ` Martin Liška
2017-10-06 12:26   ` [PATCH] Implement smart multiple switch expansion algorithms Martin Liška
2017-10-06 16:20     ` [PATCH] Add selftest for vec::reverse David Malcolm
2017-12-29 14:39       ` Martin Liška
2017-12-29 17:09         ` David Malcolm
2017-10-06 17:24     ` [PATCH] Implement smart multiple switch expansion algorithms David Malcolm
2017-12-29 14:38       ` Martin Liška
2017-10-06 13:46 Wilco Dijkstra
2017-10-06 17:31 ` Mikhail Maltsev
2017-12-29 14:43 ` Martin Liška

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).