This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH 3/3] Improve switch code emission for a balanced tree (PR tree-optimization/86847).

On 08/07/2018 05:50 AM, marxin wrote:
> This is the most complex patch. It follows original implementation and
> does following improvements that were part of original code:
> a) for a node with both children (that don't have children) and only single case
> values handled: emit series of 3 compares and jump to default
> b) for a node with only one child (that doesn't have a child) and only single
> case values handled: emit 2 compares and jump to default
> c) for a node of a range without a child, emit if (index - low) <= (high - low))
> d) profile emission is precise, taken also from previous implementation
> These changes + VRP should move us back to code quality we had in GCC 8.
> gcc/ChangeLog:
> 2018-08-13  Martin Liska  <>
>         PR tree-optimization/86847
> 	* tree-switch-conversion.c (switch_decision_tree::dump_case_nodes):
>         Dump also subtree probability.
> 	(switch_decision_tree::do_jump_if_equal): New function.
> 	(switch_decision_tree::emit_case_nodes): Handle special
>         situations in balanced tree that can be emitted much simpler.
>         Fix calculation of probabilities that happen in tree expansion.
> 	* tree-switch-conversion.h (struct cluster): Add
>         is_single_value_p.
> 	(struct simple_cluster): Likewise.
> 	(struct case_tree_node): Add new function has_child.
> 	(do_jump_if_equal): New.
> gcc/testsuite/ChangeLog:
> 2018-08-13  Martin Liska  <>
> 	* gcc.dg/tree-ssa/switch-3.c: New test.
> 	* gcc.dg/tree-ssa/vrp105.c: Remove.
Presumably the new expansion strategies totally compromise vrp105.  Too
bad, that test has actually caught oversights a few times for me in
recent history.   But I can live with it disappearing.

> diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
> index cd771438214..78914bbe81a 100644
> --- a/gcc/tree-switch-conversion.c
> +++ b/gcc/tree-switch-conversion.c
> @@ -2054,6 +2056,33 @@ switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0,
>    return false_edge->dest;
>  }
> +/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
> +   PROB is the probability of jumping to LABEL_BB.  */
> +
> +basic_block
> +switch_decision_tree::do_jump_if_equal (basic_block bb, tree op0, tree op1,
> +					basic_block label_bb,
> +					profile_probability prob)
MODE isn't a parameter and probably shouldn't show up in the function
comment.  Please document BB in the function comment.

OK with the comment fix.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]