[2/4] Switch other switch expansion methods into classes.

Message ID ef66cc24b5324fd0cd8d7b0042dda713f3b07d3c.1528462860.git.mliska@suse.cz
State New
Headers show
Series
  • Implement smart multiple switch expansion algorithms
Related show

Commit Message

Martin Liška June 5, 2018, 7:15 a.m.
gcc/ChangeLog:

2018-06-07  Martin Liska  <mliska@suse.cz>

	* tree-switch-conversion.c (switch_conversion::collect):
        Record m_uniq property.
	(switch_conversion::expand): Bail out for special conditions.
	(group_cluster::~group_cluster): New.
	(group_cluster::group_cluster): Likewise.
	(group_cluster::dump): Likewise.
	(jump_table_cluster::emit): New.
	(switch_decision_tree::fix_phi_operands_for_edges): New.
	(struct case_node): Remove struct.
	(jump_table_cluster::can_be_handled): New.
	(case_values_threshold): Moved to header.
	(reset_out_edges_aux): Likewise.
	(jump_table_cluster::is_beneficial): New.
	(bit_test_cluster::can_be_handled): Likewise.
	(add_case_node): Remove.
	(bit_test_cluster::is_beneficial): New.
	(case_bit_test::cmp): New.
	(bit_test_cluster::emit): New.
	(expand_switch_as_decision_tree_p): Remove.
	(bit_test_cluster::hoist_edge_and_branch_if_true): New.
	(fix_phi_operands_for_edge): Likewise.
	(switch_decision_tree::analyze_switch_statement): New.
	(compute_cases_per_edge): Move ...
	(switch_decision_tree::compute_cases_per_edge): ... here.
	(try_switch_expansion): Likewise.
	(switch_decision_tree::try_switch_expansion): Likewise.
	(record_phi_operand_mapping): Likewise.
	(switch_decision_tree::record_phi_operand_mapping): Likewise.
	(emit_case_decision_tree): Likewise.
	(switch_decision_tree::emit): Likewise.
	(balance_case_nodes): Likewise.
	(switch_decision_tree::balance_case_nodes): Likewise.
	(dump_case_nodes): Likewise.
	(switch_decision_tree::dump_case_nodes): Likewise.
	(emit_jump): Likewise.
	(switch_decision_tree::emit_jump): Likewise.
	(emit_cmp_and_jump_insns): Likewise.
	(switch_decision_tree::emit_cmp_and_jump_insns): Likewise.
	(emit_case_nodes): Likewise.
	(switch_decision_tree::emit_case_nodes): Likewise.
	(conditional_probability): Remove.
	* tree-switch-conversion.h (enum cluster_type): New.
	(PRINT_CASE): New.
	(struct cluster): Likewise.
	(cluster::cluster): Likewise.
	(struct simple_cluster): Likewise.
	(simple_cluster::simple_cluster): Likewise.
	(struct group_cluster): Likewise.
	(struct jump_table_cluster): Likewise.
	(struct bit_test_cluster): Likewise.
	(struct min_cluster_item): Likewise.
	(struct case_tree_node): Likewise.
	(case_tree_node::case_tree_node): Likewise.
	(jump_table_cluster::case_values_threshold): Likewise.
	(struct case_bit_test): Likewise.
	(struct switch_decision_tree): Likewise.
	(struct switch_conversion): Likewise.
	(switch_decision_tree::reset_out_edges_aux): Likewise.

gcc/testsuite/ChangeLog:

2018-06-07  Martin Liska  <mliska@suse.cz>

	* gcc.dg/tree-ssa/vrp104.c: Grep just for GIMPLE IL.
---
 gcc/testsuite/gcc.dg/tree-ssa/vrp104.c |    2 +-
 gcc/tree-switch-conversion.c           | 1343 ++++++++++++++----------
 gcc/tree-switch-conversion.h           |  545 ++++++++++
 3 files changed, 1325 insertions(+), 565 deletions(-)

Comments

Jeff Law June 12, 2018, 8:44 p.m. | #1
On 06/05/2018 01:15 AM, marxin wrote:
> gcc/ChangeLog:

> 

> 2018-06-07  Martin Liska  <mliska@suse.cz>

> 

> 	* tree-switch-conversion.c (switch_conversion::collect):

>         Record m_uniq property.

> 	(switch_conversion::expand): Bail out for special conditions.

> 	(group_cluster::~group_cluster): New.

> 	(group_cluster::group_cluster): Likewise.

> 	(group_cluster::dump): Likewise.

> 	(jump_table_cluster::emit): New.

> 	(switch_decision_tree::fix_phi_operands_for_edges): New.

> 	(struct case_node): Remove struct.

> 	(jump_table_cluster::can_be_handled): New.

> 	(case_values_threshold): Moved to header.

> 	(reset_out_edges_aux): Likewise.

> 	(jump_table_cluster::is_beneficial): New.

> 	(bit_test_cluster::can_be_handled): Likewise.

> 	(add_case_node): Remove.

> 	(bit_test_cluster::is_beneficial): New.

> 	(case_bit_test::cmp): New.

> 	(bit_test_cluster::emit): New.

> 	(expand_switch_as_decision_tree_p): Remove.

> 	(bit_test_cluster::hoist_edge_and_branch_if_true): New.

> 	(fix_phi_operands_for_edge): Likewise.

> 	(switch_decision_tree::analyze_switch_statement): New.

> 	(compute_cases_per_edge): Move ...

> 	(switch_decision_tree::compute_cases_per_edge): ... here.

> 	(try_switch_expansion): Likewise.

> 	(switch_decision_tree::try_switch_expansion): Likewise.

> 	(record_phi_operand_mapping): Likewise.

> 	(switch_decision_tree::record_phi_operand_mapping): Likewise.

> 	(emit_case_decision_tree): Likewise.

> 	(switch_decision_tree::emit): Likewise.

> 	(balance_case_nodes): Likewise.

> 	(switch_decision_tree::balance_case_nodes): Likewise.

> 	(dump_case_nodes): Likewise.

> 	(switch_decision_tree::dump_case_nodes): Likewise.

> 	(emit_jump): Likewise.

> 	(switch_decision_tree::emit_jump): Likewise.

> 	(emit_cmp_and_jump_insns): Likewise.

> 	(switch_decision_tree::emit_cmp_and_jump_insns): Likewise.

> 	(emit_case_nodes): Likewise.

> 	(switch_decision_tree::emit_case_nodes): Likewise.

> 	(conditional_probability): Remove.

> 	* tree-switch-conversion.h (enum cluster_type): New.

> 	(PRINT_CASE): New.

> 	(struct cluster): Likewise.

> 	(cluster::cluster): Likewise.

> 	(struct simple_cluster): Likewise.

> 	(simple_cluster::simple_cluster): Likewise.

> 	(struct group_cluster): Likewise.

> 	(struct jump_table_cluster): Likewise.

> 	(struct bit_test_cluster): Likewise.

> 	(struct min_cluster_item): Likewise.

> 	(struct case_tree_node): Likewise.

> 	(case_tree_node::case_tree_node): Likewise.

> 	(jump_table_cluster::case_values_threshold): Likewise.

> 	(struct case_bit_test): Likewise.

> 	(struct switch_decision_tree): Likewise.

> 	(struct switch_conversion): Likewise.

> 	(switch_decision_tree::reset_out_edges_aux): Likewise.

> 

> gcc/testsuite/ChangeLog:

> 

> 2018-06-07  Martin Liska  <mliska@suse.cz>

> 

> 	* gcc.dg/tree-ssa/vrp104.c: Grep just for GIMPLE IL.

So like the previous patch, we need to make sure functions have their
function comments.


> ---

>  gcc/testsuite/gcc.dg/tree-ssa/vrp104.c |    2 +-

>  gcc/tree-switch-conversion.c           | 1343 ++++++++++++++----------

>  gcc/tree-switch-conversion.h           |  545 ++++++++++

>  3 files changed, 1325 insertions(+), 565 deletions(-)

> 

> 

> 0002-Switch-other-switch-expansion-methods-into-classes.patch

> 

> 

> +     The definition of "much bigger" depends on whether we are

> +     optimizing for size or for speed.  If the former, the maximum

> +     ratio range/count = 3, because this was found to be the optimal

> +     ratio for size on i686-pc-linux-gnu, see PR11823.  The ratio

> +     10 is much older, and was probably selected after an extensive

> +     benchmarking investigation on numerous platforms.  Or maybe it

> +     just made sense to someone at some point in the history of GCC,

> +     who knows...  */

"much older" is an understatement.  I believe the magic "10" pre-dates
my involvement in GCC.  You can find evidence of it as far back as
gcc-0.9.  I doubt it was extensively benchmarked, and even if it was,
the targets on which it was benchmarked don't reflect modern target
reality in terms of importance.

In general this patch is much harder to de-cipher as there's little
relation between chunks of code in the unidiff.  Given your long history
with GCC, I'm going to extend a lot of leeway that you got all this
stuff right as you moved code around.  However, in the future for this
kind of change we should seriously look at a different way to break down
a patch into meaningful chunks.

So, OK with adding the missing function comments.   I think that covers
the entire set.

Thanks,
Jeff
Martin Liška June 20, 2018, 8:47 a.m. | #2
On 06/12/2018 10:44 PM, Jeff Law wrote:
> On 06/05/2018 01:15 AM, marxin wrote:

>> gcc/ChangeLog:

>>

>> 2018-06-07  Martin Liska  <mliska@suse.cz>

>>

>> 	* tree-switch-conversion.c (switch_conversion::collect):

>>         Record m_uniq property.

>> 	(switch_conversion::expand): Bail out for special conditions.

>> 	(group_cluster::~group_cluster): New.

>> 	(group_cluster::group_cluster): Likewise.

>> 	(group_cluster::dump): Likewise.

>> 	(jump_table_cluster::emit): New.

>> 	(switch_decision_tree::fix_phi_operands_for_edges): New.

>> 	(struct case_node): Remove struct.

>> 	(jump_table_cluster::can_be_handled): New.

>> 	(case_values_threshold): Moved to header.

>> 	(reset_out_edges_aux): Likewise.

>> 	(jump_table_cluster::is_beneficial): New.

>> 	(bit_test_cluster::can_be_handled): Likewise.

>> 	(add_case_node): Remove.

>> 	(bit_test_cluster::is_beneficial): New.

>> 	(case_bit_test::cmp): New.

>> 	(bit_test_cluster::emit): New.

>> 	(expand_switch_as_decision_tree_p): Remove.

>> 	(bit_test_cluster::hoist_edge_and_branch_if_true): New.

>> 	(fix_phi_operands_for_edge): Likewise.

>> 	(switch_decision_tree::analyze_switch_statement): New.

>> 	(compute_cases_per_edge): Move ...

>> 	(switch_decision_tree::compute_cases_per_edge): ... here.

>> 	(try_switch_expansion): Likewise.

>> 	(switch_decision_tree::try_switch_expansion): Likewise.

>> 	(record_phi_operand_mapping): Likewise.

>> 	(switch_decision_tree::record_phi_operand_mapping): Likewise.

>> 	(emit_case_decision_tree): Likewise.

>> 	(switch_decision_tree::emit): Likewise.

>> 	(balance_case_nodes): Likewise.

>> 	(switch_decision_tree::balance_case_nodes): Likewise.

>> 	(dump_case_nodes): Likewise.

>> 	(switch_decision_tree::dump_case_nodes): Likewise.

>> 	(emit_jump): Likewise.

>> 	(switch_decision_tree::emit_jump): Likewise.

>> 	(emit_cmp_and_jump_insns): Likewise.

>> 	(switch_decision_tree::emit_cmp_and_jump_insns): Likewise.

>> 	(emit_case_nodes): Likewise.

>> 	(switch_decision_tree::emit_case_nodes): Likewise.

>> 	(conditional_probability): Remove.

>> 	* tree-switch-conversion.h (enum cluster_type): New.

>> 	(PRINT_CASE): New.

>> 	(struct cluster): Likewise.

>> 	(cluster::cluster): Likewise.

>> 	(struct simple_cluster): Likewise.

>> 	(simple_cluster::simple_cluster): Likewise.

>> 	(struct group_cluster): Likewise.

>> 	(struct jump_table_cluster): Likewise.

>> 	(struct bit_test_cluster): Likewise.

>> 	(struct min_cluster_item): Likewise.

>> 	(struct case_tree_node): Likewise.

>> 	(case_tree_node::case_tree_node): Likewise.

>> 	(jump_table_cluster::case_values_threshold): Likewise.

>> 	(struct case_bit_test): Likewise.

>> 	(struct switch_decision_tree): Likewise.

>> 	(struct switch_conversion): Likewise.

>> 	(switch_decision_tree::reset_out_edges_aux): Likewise.

>>

>> gcc/testsuite/ChangeLog:

>>

>> 2018-06-07  Martin Liska  <mliska@suse.cz>

>>

>> 	* gcc.dg/tree-ssa/vrp104.c: Grep just for GIMPLE IL.

> So like the previous patch, we need to make sure functions have their

> function comments.

> 

> 

>> ---

>>  gcc/testsuite/gcc.dg/tree-ssa/vrp104.c |    2 +-

>>  gcc/tree-switch-conversion.c           | 1343 ++++++++++++++----------

>>  gcc/tree-switch-conversion.h           |  545 ++++++++++

>>  3 files changed, 1325 insertions(+), 565 deletions(-)

>>

>>

>> 0002-Switch-other-switch-expansion-methods-into-classes.patch

>>

>>

>> +     The definition of "much bigger" depends on whether we are

>> +     optimizing for size or for speed.  If the former, the maximum

>> +     ratio range/count = 3, because this was found to be the optimal

>> +     ratio for size on i686-pc-linux-gnu, see PR11823.  The ratio

>> +     10 is much older, and was probably selected after an extensive

>> +     benchmarking investigation on numerous platforms.  Or maybe it

>> +     just made sense to someone at some point in the history of GCC,

>> +     who knows...  */

> "much older" is an understatement.  I believe the magic "10" pre-dates

> my involvement in GCC.  You can find evidence of it as far back as

> gcc-0.9.  I doubt it was extensively benchmarked, and even if it was,

> the targets on which it was benchmarked don't reflect modern target

> reality in terms of importance.


Good, then lets decrease it to 8 and we'll see if some regression will
appear.

> 

> In general this patch is much harder to de-cipher as there's little

> relation between chunks of code in the unidiff.  Given your long history

> with GCC, I'm going to extend a lot of leeway that you got all this

> stuff right as you moved code around.  However, in the future for this

> kind of change we should seriously look at a different way to break down

> a patch into meaningful chunks.


Thank you for the trust. I tried to split it into multiple patches, but
it wasn't readable enough.

Martin

> 

> So, OK with adding the missing function comments.   I think that covers

> the entire set.

> 

> Thanks,

> Jeff

>
Steven Bosscher June 20, 2018, 11:25 a.m. | #3
On Tue, Jun 12, 2018 at 10:44 PM, Jeff Law wrote:
> On 06/05/2018 01:15 AM, marxin wrote:

>>

>> +     The definition of "much bigger" depends on whether we are

>> +     optimizing for size or for speed.  If the former, the maximum

>> +     ratio range/count = 3, because this was found to be the optimal

>> +     ratio for size on i686-pc-linux-gnu, see PR11823.  The ratio

>> +     10 is much older, and was probably selected after an extensive

>> +     benchmarking investigation on numerous platforms.  Or maybe it

>> +     just made sense to someone at some point in the history of GCC,

>> +     who knows...  */

> "much older" is an understatement.  I believe the magic "10" pre-dates

> my involvement in GCC.  You can find evidence of it as far back as

> gcc-0.9.  I doubt it was extensively benchmarked, and even if it was,

> the targets on which it was benchmarked don't reflect modern target

> reality in terms of importance.


When I added this comment
(https://gcc.gnu.org/viewcvs/gcc/trunk/gcc/stmt.c?r1=189284&r2=189285&)
it as an attempt at humor. I should have turned the number into a
PARAM at the time. Maybe that's something Martin could still do now?

Ciao!
Steven
Jeff Law June 20, 2018, 3:15 p.m. | #4
On 06/20/2018 02:47 AM, Martin Liška wrote:
> On 06/12/2018 10:44 PM, Jeff Law wrote:

>> On 06/05/2018 01:15 AM, marxin wrote:

>>> gcc/ChangeLog:

>>>

>>> 2018-06-07  Martin Liska  <mliska@suse.cz>

>>>

>>> 	* tree-switch-conversion.c (switch_conversion::collect):

>>>         Record m_uniq property.

>>> 	(switch_conversion::expand): Bail out for special conditions.

>>> 	(group_cluster::~group_cluster): New.

>>> 	(group_cluster::group_cluster): Likewise.

>>> 	(group_cluster::dump): Likewise.

>>> 	(jump_table_cluster::emit): New.

>>> 	(switch_decision_tree::fix_phi_operands_for_edges): New.

>>> 	(struct case_node): Remove struct.

>>> 	(jump_table_cluster::can_be_handled): New.

>>> 	(case_values_threshold): Moved to header.

>>> 	(reset_out_edges_aux): Likewise.

>>> 	(jump_table_cluster::is_beneficial): New.

>>> 	(bit_test_cluster::can_be_handled): Likewise.

>>> 	(add_case_node): Remove.

>>> 	(bit_test_cluster::is_beneficial): New.

>>> 	(case_bit_test::cmp): New.

>>> 	(bit_test_cluster::emit): New.

>>> 	(expand_switch_as_decision_tree_p): Remove.

>>> 	(bit_test_cluster::hoist_edge_and_branch_if_true): New.

>>> 	(fix_phi_operands_for_edge): Likewise.

>>> 	(switch_decision_tree::analyze_switch_statement): New.

>>> 	(compute_cases_per_edge): Move ...

>>> 	(switch_decision_tree::compute_cases_per_edge): ... here.

>>> 	(try_switch_expansion): Likewise.

>>> 	(switch_decision_tree::try_switch_expansion): Likewise.

>>> 	(record_phi_operand_mapping): Likewise.

>>> 	(switch_decision_tree::record_phi_operand_mapping): Likewise.

>>> 	(emit_case_decision_tree): Likewise.

>>> 	(switch_decision_tree::emit): Likewise.

>>> 	(balance_case_nodes): Likewise.

>>> 	(switch_decision_tree::balance_case_nodes): Likewise.

>>> 	(dump_case_nodes): Likewise.

>>> 	(switch_decision_tree::dump_case_nodes): Likewise.

>>> 	(emit_jump): Likewise.

>>> 	(switch_decision_tree::emit_jump): Likewise.

>>> 	(emit_cmp_and_jump_insns): Likewise.

>>> 	(switch_decision_tree::emit_cmp_and_jump_insns): Likewise.

>>> 	(emit_case_nodes): Likewise.

>>> 	(switch_decision_tree::emit_case_nodes): Likewise.

>>> 	(conditional_probability): Remove.

>>> 	* tree-switch-conversion.h (enum cluster_type): New.

>>> 	(PRINT_CASE): New.

>>> 	(struct cluster): Likewise.

>>> 	(cluster::cluster): Likewise.

>>> 	(struct simple_cluster): Likewise.

>>> 	(simple_cluster::simple_cluster): Likewise.

>>> 	(struct group_cluster): Likewise.

>>> 	(struct jump_table_cluster): Likewise.

>>> 	(struct bit_test_cluster): Likewise.

>>> 	(struct min_cluster_item): Likewise.

>>> 	(struct case_tree_node): Likewise.

>>> 	(case_tree_node::case_tree_node): Likewise.

>>> 	(jump_table_cluster::case_values_threshold): Likewise.

>>> 	(struct case_bit_test): Likewise.

>>> 	(struct switch_decision_tree): Likewise.

>>> 	(struct switch_conversion): Likewise.

>>> 	(switch_decision_tree::reset_out_edges_aux): Likewise.

>>>

>>> gcc/testsuite/ChangeLog:

>>>

>>> 2018-06-07  Martin Liska  <mliska@suse.cz>

>>>

>>> 	* gcc.dg/tree-ssa/vrp104.c: Grep just for GIMPLE IL.

>> So like the previous patch, we need to make sure functions have their

>> function comments.

>>

>>

>>> ---

>>>  gcc/testsuite/gcc.dg/tree-ssa/vrp104.c |    2 +-

>>>  gcc/tree-switch-conversion.c           | 1343 ++++++++++++++----------

>>>  gcc/tree-switch-conversion.h           |  545 ++++++++++

>>>  3 files changed, 1325 insertions(+), 565 deletions(-)

>>>

>>>

>>> 0002-Switch-other-switch-expansion-methods-into-classes.patch

>>>

>>>

>>> +     The definition of "much bigger" depends on whether we are

>>> +     optimizing for size or for speed.  If the former, the maximum

>>> +     ratio range/count = 3, because this was found to be the optimal

>>> +     ratio for size on i686-pc-linux-gnu, see PR11823.  The ratio

>>> +     10 is much older, and was probably selected after an extensive

>>> +     benchmarking investigation on numerous platforms.  Or maybe it

>>> +     just made sense to someone at some point in the history of GCC,

>>> +     who knows...  */

>> "much older" is an understatement.  I believe the magic "10" pre-dates

>> my involvement in GCC.  You can find evidence of it as far back as

>> gcc-0.9.  I doubt it was extensively benchmarked, and even if it was,

>> the targets on which it was benchmarked don't reflect modern target

>> reality in terms of importance.

> 

> Good, then lets decrease it to 8 and we'll see if some regression will

> appear.

Agreed.


>>

>> In general this patch is much harder to de-cipher as there's little

>> relation between chunks of code in the unidiff.  Given your long history

>> with GCC, I'm going to extend a lot of leeway that you got all this

>> stuff right as you moved code around.  However, in the future for this

>> kind of change we should seriously look at a different way to break down

>> a patch into meaningful chunks.

> 

> Thank you for the trust. I tried to split it into multiple patches, but

> it wasn't readable enough.

Yea, it can be painful to find the right way to structure a series.  In
fact, I'm going to be faced with that shortly for a target change my son
and I have in the works (converting v850 away from cc0).  In the end it
looks like 75% of the file changed, but a lot of it is just unidiff
presenting the changes in a particularly  bad way.

Jeff
Jeff Law June 20, 2018, 3:16 p.m. | #5
On 06/20/2018 05:25 AM, Steven Bosscher wrote:
> On Tue, Jun 12, 2018 at 10:44 PM, Jeff Law wrote:

>> On 06/05/2018 01:15 AM, marxin wrote:

>>>

>>> +     The definition of "much bigger" depends on whether we are

>>> +     optimizing for size or for speed.  If the former, the maximum

>>> +     ratio range/count = 3, because this was found to be the optimal

>>> +     ratio for size on i686-pc-linux-gnu, see PR11823.  The ratio

>>> +     10 is much older, and was probably selected after an extensive

>>> +     benchmarking investigation on numerous platforms.  Or maybe it

>>> +     just made sense to someone at some point in the history of GCC,

>>> +     who knows...  */

>> "much older" is an understatement.  I believe the magic "10" pre-dates

>> my involvement in GCC.  You can find evidence of it as far back as

>> gcc-0.9.  I doubt it was extensively benchmarked, and even if it was,

>> the targets on which it was benchmarked don't reflect modern target

>> reality in terms of importance.

> 

> When I added this comment

> (https://gcc.gnu.org/viewcvs/gcc/trunk/gcc/stmt.c?r1=189284&r2=189285&)

> it as an attempt at humor. I should have turned the number into a

> PARAM at the time. Maybe that's something Martin could still do now?

A PARAM feels like overkill, but I certainly wouldn't object.    I'd be
happy with that, a const member in the class or even the adjusted
constant.

jeff
Jakub Jelinek June 20, 2018, 3:20 p.m. | #6
On Wed, Jun 20, 2018 at 09:15:08AM -0600, Jeff Law wrote:
> > Thank you for the trust. I tried to split it into multiple patches, but

> > it wasn't readable enough.

> Yea, it can be painful to find the right way to structure a series.  In

> fact, I'm going to be faced with that shortly for a target change my son

> and I have in the works (converting v850 away from cc0).  In the end it

> looks like 75% of the file changed, but a lot of it is just unidiff

> presenting the changes in a particularly  bad way.


Have you tried diff -upd?  -d helps a lot in some cases to make diffs more
readable.

	Jakub
Jeff Law June 20, 2018, 3:24 p.m. | #7
On 06/20/2018 09:20 AM, Jakub Jelinek wrote:
> On Wed, Jun 20, 2018 at 09:15:08AM -0600, Jeff Law wrote:

>>> Thank you for the trust. I tried to split it into multiple patches, but

>>> it wasn't readable enough.

>> Yea, it can be painful to find the right way to structure a series.  In

>> fact, I'm going to be faced with that shortly for a target change my son

>> and I have in the works (converting v850 away from cc0).  In the end it

>> looks like 75% of the file changed, but a lot of it is just unidiff

>> presenting the changes in a particularly  bad way.

> 

> Have you tried diff -upd?  -d helps a lot in some cases to make diffs more

> readable.

It's one of the things I'll look at.  It may also be the case that I can
stage them in such a way as to keep the diffs reasonable.  It may mean a
couple revs in the repo where we don't optimize well, but given the
target I doubt that's a big deal.  This was mostly an exercise to keep
my son's mind occupied :-)

Jeff
Martin Liška June 22, 2018, 10:32 a.m. | #8
On 06/20/2018 05:16 PM, Jeff Law wrote:
> On 06/20/2018 05:25 AM, Steven Bosscher wrote:

>> On Tue, Jun 12, 2018 at 10:44 PM, Jeff Law wrote:

>>> On 06/05/2018 01:15 AM, marxin wrote:

>>>>

>>>> +     The definition of "much bigger" depends on whether we are

>>>> +     optimizing for size or for speed.  If the former, the maximum

>>>> +     ratio range/count = 3, because this was found to be the optimal

>>>> +     ratio for size on i686-pc-linux-gnu, see PR11823.  The ratio

>>>> +     10 is much older, and was probably selected after an extensive

>>>> +     benchmarking investigation on numerous platforms.  Or maybe it

>>>> +     just made sense to someone at some point in the history of GCC,

>>>> +     who knows...  */

>>> "much older" is an understatement.  I believe the magic "10" pre-dates

>>> my involvement in GCC.  You can find evidence of it as far back as

>>> gcc-0.9.  I doubt it was extensively benchmarked, and even if it was,

>>> the targets on which it was benchmarked don't reflect modern target

>>> reality in terms of importance.

>>

>> When I added this comment

>> (https://gcc.gnu.org/viewcvs/gcc/trunk/gcc/stmt.c?r1=189284&r2=189285&)

>> it as an attempt at humor. I should have turned the number into a

>> PARAM at the time. Maybe that's something Martin could still do now?

> A PARAM feels like overkill, but I certainly wouldn't object.    I'd be

> happy with that, a const member in the class or even the adjusted

> constant.

> 

> jeff

> 


Hi.

Agree with Jeff, there's a patch that does that.
Ready after it finishes tests?

Martin
From 27d7c87720dc464b6ed998bc7344cf2226d5f9ea Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>

Date: Fri, 22 Jun 2018 12:24:13 +0200
Subject: [PATCH] Come up with jump_table ratio constants used in
 jump_table_cluster.

gcc/ChangeLog:

2018-06-22  Martin Liska  <mliska@suse.cz>

	* tree-switch-conversion.c (jump_table_cluster::can_be_handled):
        Use newly introduced constants.
	* tree-switch-conversion.h (struct jump_table_cluster):
        Define max_ratio_for_size and max_ratio_for_speed.
---
 gcc/tree-switch-conversion.c | 3 ++-
 gcc/tree-switch-conversion.h | 6 ++++++
 2 files changed, 8 insertions(+), 1 deletion(-)

diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index ddd8cba7b98..b79f2fdb6e6 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -1180,7 +1180,8 @@ jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
   if (start == end)
     return true;
 
-  unsigned HOST_WIDE_INT max_ratio = optimize_insn_for_size_p () ? 3 : 8;
+  unsigned HOST_WIDE_INT max_ratio
+    = optimize_insn_for_size_p () ? max_ratio_for_size : max_ratio_for_speed;
   unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
 					    clusters[end]->get_high ());
   /* Check overflow.  */
diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h
index 79a1320c448..4beac785f05 100644
--- a/gcc/tree-switch-conversion.h
+++ b/gcc/tree-switch-conversion.h
@@ -257,6 +257,12 @@ struct jump_table_cluster: public group_cluster
 
   /* Return whether jump table expansion is allowed.  */
   static bool is_enabled (void);
+
+  /* Max growth ratio for code that is optimized for size.  */
+  static const unsigned HOST_WIDE_INT max_ratio_for_size = 3;
+
+  /* Max growth ratio for code that is optimized for speed.  */
+  static const unsigned HOST_WIDE_INT max_ratio_for_speed = 8;
 };
 
 /* A GIMPLE switch statement can be expanded to a short sequence of bit-wise
-- 
2.17.1
Jeff Law June 22, 2018, 4:08 p.m. | #9
On 06/22/2018 04:32 AM, Martin Liška wrote:
> On 06/20/2018 05:16 PM, Jeff Law wrote:

>> On 06/20/2018 05:25 AM, Steven Bosscher wrote:

>>> On Tue, Jun 12, 2018 at 10:44 PM, Jeff Law wrote:

>>>> On 06/05/2018 01:15 AM, marxin wrote:

>>>>> +     The definition of "much bigger" depends on whether we are

>>>>> +     optimizing for size or for speed.  If the former, the maximum

>>>>> +     ratio range/count = 3, because this was found to be the optimal

>>>>> +     ratio for size on i686-pc-linux-gnu, see PR11823.  The ratio

>>>>> +     10 is much older, and was probably selected after an extensive

>>>>> +     benchmarking investigation on numerous platforms.  Or maybe it

>>>>> +     just made sense to someone at some point in the history of GCC,

>>>>> +     who knows...  */

>>>> "much older" is an understatement.  I believe the magic "10" pre-dates

>>>> my involvement in GCC.  You can find evidence of it as far back as

>>>> gcc-0.9.  I doubt it was extensively benchmarked, and even if it was,

>>>> the targets on which it was benchmarked don't reflect modern target

>>>> reality in terms of importance.

>>> When I added this comment

>>> (https://gcc.gnu.org/viewcvs/gcc/trunk/gcc/stmt.c?r1=189284&r2=189285&)

>>> it as an attempt at humor. I should have turned the number into a

>>> PARAM at the time. Maybe that's something Martin could still do now?

>> A PARAM feels like overkill, but I certainly wouldn't object.    I'd be

>> happy with that, a const member in the class or even the adjusted

>> constant.

>>

>> jeff

>>

> Hi.

> 

> Agree with Jeff, there's a patch that does that.

> Ready after it finishes tests?

> 

> Martin

> 

> 

> 0001-Come-up-with-jump_table-ratio-constants-used-in-jump.patch

> 

> 

> From 27d7c87720dc464b6ed998bc7344cf2226d5f9ea Mon Sep 17 00:00:00 2001

> From: marxin <mliska@suse.cz>

> Date: Fri, 22 Jun 2018 12:24:13 +0200

> Subject: [PATCH] Come up with jump_table ratio constants used in

>  jump_table_cluster.

> 

> gcc/ChangeLog:

> 

> 2018-06-22  Martin Liska  <mliska@suse.cz>

> 

> 	* tree-switch-conversion.c (jump_table_cluster::can_be_handled):

>         Use newly introduced constants.

> 	* tree-switch-conversion.h (struct jump_table_cluster):

>         Define max_ratio_for_size and max_ratio_for_speed.

OK.
jeff

Patch

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
index 71fa3bfa2ca..1bef76f1a21 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 "switchlower1" } }  */
+/* { dg-final { scan-tree-dump-times "switch \\(" 2 "switchlower1" } }  */
 
 void foo (void);
 void bar (void);
diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index 2f848fcb6aa..8f3dc8fd8a4 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -175,6 +175,11 @@  switch_conversion::collect (gswitch *swtch)
 	  && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
 	m_count++;
     }
+
+  /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
+     block.  Assume a CFG cleanup would have already removed degenerate
+     switch statements, this allows us to just use EDGE_COUNT.  */
+  m_uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
 }
 
 bool
@@ -861,6 +866,22 @@  switch_conversion::expand (gswitch *swtch)
   /* A switch on a constant should have been optimized in tree-cfg-cleanup.  */
   gcc_checking_assert (!TREE_CONSTANT (m_index_expr));
 
+  /* Prefer bit test if possible.  */
+  if (tree_fits_uhwi_p (m_range_size)
+      && bit_test_cluster::can_be_handled (tree_to_uhwi (m_range_size), m_uniq)
+      && bit_test_cluster::is_beneficial (m_count, m_uniq))
+    {
+      m_reason = "expanding as bit test is preferable";
+      return;
+    }
+
+  if (m_uniq <= 2)
+    {
+      /* This will be expanded as a decision tree .  */
+      m_reason = "expanding as jumps is preferable";
+      return;
+    }
+
   /* If there is no common successor, we cannot do the transformation.  */
   if (!m_final_bb)
     {
@@ -909,409 +930,481 @@  switch_conversion::~switch_conversion ()
   XDELETEVEC (m_default_values);
 }
 
-/* The main function of the pass scans statements for switches and invokes
-   process_switch on them.  */
-
-namespace {
-
-const pass_data pass_data_convert_switch =
-{
-  GIMPLE_PASS, /* type */
-  "switchconv", /* name */
-  OPTGROUP_NONE, /* optinfo_flags */
-  TV_TREE_SWITCH_CONVERSION, /* tv_id */
-  ( PROP_cfg | PROP_ssa ), /* properties_required */
-  0, /* properties_provided */
-  0, /* properties_destroyed */
-  0, /* todo_flags_start */
-  TODO_update_ssa, /* todo_flags_finish */
-};
-
-class pass_convert_switch : public gimple_opt_pass
+group_cluster::~group_cluster ()
 {
-public:
-  pass_convert_switch (gcc::context *ctxt)
-    : gimple_opt_pass (pass_data_convert_switch, ctxt)
-  {}
+  for (unsigned i = 0; i < m_cases.length (); i++)
+    delete m_cases[i];
 
-  /* opt_pass methods: */
-  virtual bool gate (function *) { return flag_tree_switch_conversion != 0; }
-  virtual unsigned int execute (function *);
-
-}; // class pass_convert_switch
+  m_cases.release ();
+}
 
-unsigned int
-pass_convert_switch::execute (function *fun)
+group_cluster::group_cluster (vec<cluster *> &clusters,
+			      unsigned start, unsigned end)
 {
-  basic_block bb;
-  bool cfg_altered = false;
+  gcc_checking_assert (end - start + 1 >= 1);
+  m_prob = profile_probability::never ();
+  m_cases.create (end - start + 1);
+  for (unsigned i = start; i <= end; i++)
+    {
+      m_cases.quick_push (static_cast<simple_cluster *> (clusters[i]));
+      m_prob += clusters[i]->m_prob;
+    }
+  m_subtree_prob = m_prob;
+}
 
-  FOR_EACH_BB_FN (bb, fun)
-  {
-    gimple *stmt = last_stmt (bb);
-    if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
-      {
-	if (dump_file)
-	  {
-	    expanded_location loc = expand_location (gimple_location (stmt));
+void
+group_cluster::dump (FILE *f, bool details)
+{
+  unsigned total_values = 0;
+  for (unsigned i = 0; i < m_cases.length (); i++)
+    total_values += m_cases[i]->get_range (m_cases[i]->get_low (),
+					   m_cases[i]->get_high ());
 
-	    fprintf (dump_file, "beginning to process the following "
-		     "SWITCH statement (%s:%d) : ------- \n",
-		     loc.file, loc.line);
-	    print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
-	    putc ('\n', dump_file);
-	  }
+  unsigned comparison_count = 0;
+  for (unsigned i = 0; i < m_cases.length (); i++)
+    {
+      simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
+      comparison_count += sc->m_range_p ? 2 : 1;
+    }
 
-	switch_conversion sconv;
-	sconv.expand (as_a <gswitch *> (stmt));
-	cfg_altered |= sconv.m_cfg_altered;
-	if (!sconv.m_reason)
-	  {
-	    if (dump_file)
-	      {
-		fputs ("Switch converted\n", dump_file);
-		fputs ("--------------------------------\n", dump_file);
-	      }
+  unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ());
+  fprintf (f, "%s", get_type () == JUMP_TABLE ? "JT" : "BT");
 
-	    /* Make no effort to update the post-dominator tree.
-	       It is actually not that hard for the transformations
-	       we have performed, but it is not supported
-	       by iterate_fix_dominators.  */
-	    free_dominance_info (CDI_POST_DOMINATORS);
-	  }
-	else
-	  {
-	    if (dump_file)
-	      {
-		fputs ("Bailing out - ", dump_file);
-		fputs (sconv.m_reason, dump_file);
-		fputs ("\n--------------------------------\n", dump_file);
-	      }
-	  }
-      }
-  }
+  if (details)
+    fprintf (f, "(values:%d comparisons:%d range:" HOST_WIDE_INT_PRINT_DEC
+	     " density: %.2f%%)", total_values, comparison_count, range,
+	     100.0f * comparison_count / range);
 
-  return cfg_altered ? TODO_cleanup_cfg : 0;;
+  fprintf (f, ":");
+  PRINT_CASE (f, get_low ());
+  fprintf (f, "-");
+  PRINT_CASE (f, get_high ());
+  fprintf (f, " ");
 }
 
-} // anon namespace
-
-gimple_opt_pass *
-make_pass_convert_switch (gcc::context *ctxt)
+void
+jump_table_cluster::emit (tree index_expr, tree,
+			  tree default_label_expr, basic_block default_bb)
 {
-  return new pass_convert_switch (ctxt);
+  /* For jump table we just emit a new gswitch statement that will
+     be latter lowered to jump table.  */
+  auto_vec <tree> labels;
+  labels.create (m_cases.length ());
+
+  make_edge (m_case_bb, default_bb, 0);
+  for (unsigned i = 0; i < m_cases.length (); i++)
+    {
+      labels.quick_push (unshare_expr (m_cases[i]->m_case_label_expr));
+      make_edge (m_case_bb, m_cases[i]->m_case_bb, 0);
+    }
+
+  gswitch *s = gimple_build_switch (index_expr,
+				    unshare_expr (default_label_expr), labels);
+  gimple_stmt_iterator gsi = gsi_start_bb (m_case_bb);
+  gsi_insert_after (&gsi, s, GSI_NEW_STMT);
 }
 
-struct case_node
+bool
+jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
+				    unsigned start, unsigned end)
 {
-  case_node		*left;	/* Left son in binary tree.  */
-  case_node		*right;	/* Right son in binary tree;
-				   also node chain.  */
-  case_node		*parent; /* Parent of node in binary tree.  */
-  tree			low;	/* Lowest index value for this label.  */
-  tree			high;	/* Highest index value for this label.  */
-  basic_block		case_bb; /* Label to jump to when node matches.  */
-  tree			case_label; /* Label to jump to when node matches.  */
-  profile_probability   prob; /* Probability of taking this case.  */
-  profile_probability   subtree_prob;  /* Probability of reaching subtree
-					  rooted at this node.  */
-};
+  /* If the switch is relatively small such that the cost of one
+     indirect jump on the target are higher than the cost of a
+     decision tree, go with the decision tree.
 
-typedef case_node *case_node_ptr;
+     If range of values is much bigger than number of values,
+     or if it is too large to represent in a HOST_WIDE_INT,
+     make a sequence of conditional branches instead of a dispatch.
 
-static basic_block emit_case_nodes (basic_block, tree, case_node_ptr,
-				    basic_block, tree, profile_probability,
-				    tree, hash_map<tree, tree> *);
+     The definition of "much bigger" depends on whether we are
+     optimizing for size or for speed.  If the former, the maximum
+     ratio range/count = 3, because this was found to be the optimal
+     ratio for size on i686-pc-linux-gnu, see PR11823.  The ratio
+     10 is much older, and was probably selected after an extensive
+     benchmarking investigation on numerous platforms.  Or maybe it
+     just made sense to someone at some point in the history of GCC,
+     who knows...  */
+  if (!flag_jump_tables)
+    return false;
 
-/* Return the smallest number of different values for which it is best to use a
-   jump-table instead of a tree of conditional branches.  */
+  unsigned HOST_WIDE_INT max_ratio = optimize_insn_for_size_p () ? 3 : 10;
 
-static unsigned int
-case_values_threshold (void)
-{
-  unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
+  unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
+					    clusters[end]->get_high ());
+  /* Check overflow.  */
+  if (range == 0)
+    return false;
 
-  if (threshold == 0)
-    threshold = targetm.case_values_threshold ();
+  unsigned HOST_WIDE_INT comparison_count = 0;
+  for (unsigned i = start; i <= end; i++)
+    {
+      simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
+      comparison_count += sc->m_range_p ? 2 : 1;
+    }
 
-  return threshold;
+  return range <= max_ratio * comparison_count;
 }
 
-/* Reset the aux field of all outgoing edges of basic block BB.  */
-
-static inline void
-reset_out_edges_aux (basic_block bb)
+bool
+jump_table_cluster::is_beneficial (const vec<cluster *> &,
+				   unsigned start, unsigned end)
 {
-  edge e;
-  edge_iterator ei;
-  FOR_EACH_EDGE (e, ei, bb->succs)
-    e->aux = (void *) 0;
+  return end - start + 1 >= case_values_threshold ();
 }
 
-/* Compute the number of case labels that correspond to each outgoing edge of
-   STMT.  Record this information in the aux field of the edge.  */
+bool
+bit_test_cluster::can_be_handled (unsigned HOST_WIDE_INT range,
+				  unsigned int uniq)
+{
+  /* Check overflow.  */
+  if (range == 0)
+    return 0;
+
+  if (range >= GET_MODE_BITSIZE (word_mode))
+    return false;
+
+  return uniq <= 3;
+}
 
-static inline void
-compute_cases_per_edge (gswitch *stmt)
+bool
+bit_test_cluster::can_be_handled (const vec<cluster *> &clusters,
+				  unsigned start, unsigned end)
 {
-  basic_block bb = gimple_bb (stmt);
-  reset_out_edges_aux (bb);
-  int ncases = gimple_switch_num_labels (stmt);
-  for (int i = ncases - 1; i >= 1; --i)
+  unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
+					    clusters[end]->get_high ());
+  auto_bitmap dest_bbs;
+
+  for (unsigned i = start; i <= end; i++)
     {
-      tree elt = gimple_switch_label (stmt, i);
-      tree lab = CASE_LABEL (elt);
-      basic_block case_bb = label_to_block_fn (cfun, lab);
-      edge case_edge = find_edge (bb, case_bb);
-      case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1);
+      simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
+      bitmap_set_bit (dest_bbs, sc->m_case_bb->index);
     }
-}
-
-/* Do the insertion of a case label into case_list.  The labels are
-   fed to us in descending order from the sorted vector of case labels used
-   in the tree part of the middle end.  So the list we construct is
-   sorted in ascending order.
 
-   LABEL is the case label to be inserted.  LOW and HIGH are the bounds
-   against which the index is compared to jump to LABEL and PROB is the
-   estimated probability LABEL is reached from the switch statement.  */
+  return can_be_handled (range, bitmap_count_bits (dest_bbs));
+}
 
-static case_node *
-add_case_node (case_node *head, tree low, tree high, basic_block case_bb,
-	       tree case_label, profile_probability prob,
-	       object_allocator<case_node> &case_node_pool)
+bool
+bit_test_cluster::is_beneficial (unsigned count, unsigned uniq)
 {
-  case_node *r;
-
-  gcc_checking_assert (low);
-  gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high)));
-
-  /* Add this label to the chain.  */
-  r = case_node_pool.allocate ();
-  r->low = low;
-  r->high = high;
-  r->case_bb = case_bb;
-  r->case_label = case_label;
-  r->parent = r->left = NULL;
-  r->prob = prob;
-  r->subtree_prob = prob;
-  r->right = head;
-  return r;
+  return (((uniq == 1 && count >= 3)
+	   || (uniq == 2 && count >= 5)
+	   || (uniq == 3 && count >= 6)));
 }
 
-/* Dump ROOT, a list or tree of case nodes, to file.  */
-
-static void
-dump_case_nodes (FILE *f, case_node *root, int indent_step, int indent_level)
+bool
+bit_test_cluster::is_beneficial (const vec<cluster *> &clusters,
+				 unsigned start, unsigned end)
 {
-  if (root == 0)
-    return;
-  indent_level++;
+  auto_bitmap dest_bbs;
 
-  dump_case_nodes (f, root->left, indent_step, indent_level);
-
-  fputs (";; ", f);
-  fprintf (f, "%*s", indent_step * indent_level, "");
-  print_dec (wi::to_wide (root->low), f, TYPE_SIGN (TREE_TYPE (root->low)));
-  if (!tree_int_cst_equal (root->low, root->high))
+  for (unsigned i = start; i <= end; i++)
     {
-      fprintf (f, " ... ");
-      print_dec (wi::to_wide (root->high), f,
-		 TYPE_SIGN (TREE_TYPE (root->high)));
+      simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
+      bitmap_set_bit (dest_bbs, sc->m_case_bb->index);
     }
-  fputs ("\n", f);
 
-  dump_case_nodes (f, root->right, indent_step, indent_level);
+  unsigned uniq = bitmap_count_bits (dest_bbs);
+  unsigned count = end - start + 1;
+  return is_beneficial (count, uniq);
 }
 
-/* Take an ordered list of case nodes
-   and transform them into a near optimal binary tree,
-   on the assumption that any target code selection value is as
-   likely as any other.
+int
+case_bit_test::cmp (const void *p1, const void *p2)
+{
+  const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
+  const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
+
+  if (d2->bits != d1->bits)
+    return d2->bits - d1->bits;
 
-   The transformation is performed by splitting the ordered
-   list into two equal sections plus a pivot.  The parts are
-   then attached to the pivot as left and right branches.  Each
-   branch is then transformed recursively.  */
+  /* Stabilize the sort.  */
+  return (LABEL_DECL_UID (CASE_LABEL (d2->label))
+	  - LABEL_DECL_UID (CASE_LABEL (d1->label)));
+}
 
-static void
-balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
+void
+bit_test_cluster::emit (tree index_expr, tree index_type,
+			tree, basic_block default_bb)
 {
-  case_node_ptr np;
+  struct case_bit_test test[m_max_case_bit_tests] = { {} };
+  unsigned int i, j, k;
+  unsigned int count;
 
-  np = *head;
-  if (np)
-    {
-      int i = 0;
-      int ranges = 0;
-      case_node_ptr *npp;
-      case_node_ptr left;
+  tree unsigned_index_type = unsigned_type_for (index_type);
 
-      /* Count the number of entries on branch.  Also count the ranges.  */
+  gimple_stmt_iterator gsi;
+  gassign *shift_stmt;
 
-      while (np)
-	{
-	  if (!tree_int_cst_equal (np->low, np->high))
-	    ranges++;
+  tree idx, tmp, csui;
+  tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
+  tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
+  tree word_mode_one = fold_convert (word_type_node, integer_one_node);
+  int prec = TYPE_PRECISION (word_type_node);
+  wide_int wone = wi::one (prec);
 
-	  i++;
-	  np = np->right;
-	}
+  tree minval = get_low ();
+  tree maxval = get_high ();
+  tree range = int_const_binop (MINUS_EXPR, maxval, minval);
 
-      if (i > 2)
+  /* Go through all case labels, and collect the case labels, profile
+     counts, and other information we need to build the branch tests.  */
+  count = 0;
+  for (i = 0; i < m_cases.length (); i++)
+    {
+      unsigned int lo, hi;
+      simple_cluster *n = static_cast<simple_cluster *> (m_cases[i]);
+      for (k = 0; k < count; k++)
+	if (n->m_case_bb == test[k].target_bb)
+	  break;
+
+      if (k == count)
 	{
-	  /* Split this list if it is long enough for that to help.  */
-	  npp = head;
-	  left = *npp;
+	  gcc_checking_assert (count < m_max_case_bit_tests);
+	  test[k].mask = wi::zero (prec);
+	  test[k].target_bb = n->m_case_bb;
+	  test[k].label = n->m_case_label_expr;
+	  test[k].bits = 1;
+	  count++;
+	}
+      else
+	test[k].bits++;
 
-	  /* If there are just three nodes, split at the middle one.  */
-	  if (i == 3)
-	    npp = &(*npp)->right;
-	  else
-	    {
-	      /* Find the place in the list that bisects the list's total cost,
-		 where ranges count as 2.
-		 Here I gets half the total cost.  */
-	      i = (i + ranges + 1) / 2;
-	      while (1)
-		{
-		  /* Skip nodes while their cost does not reach that amount.  */
-		  if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
-		    i--;
-		  i--;
-		  if (i <= 0)
-		    break;
-		  npp = &(*npp)->right;
-		}
-	    }
-	  *head = np = *npp;
-	  *npp = 0;
-	  np->parent = parent;
-	  np->left = left;
+      lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval));
+      if (n->get_high () == NULL_TREE)
+	hi = lo;
+      else
+	hi = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_high (),
+					    minval));
 
-	  /* Optimize each of the two split parts.  */
-	  balance_case_nodes (&np->left, np);
-	  balance_case_nodes (&np->right, np);
-	  np->subtree_prob = np->prob;
-	  np->subtree_prob += np->left->subtree_prob;
-	  np->subtree_prob += np->right->subtree_prob;
+      for (j = lo; j <= hi; j++)
+	test[k].mask |= wi::lshift (wone, j);
+    }
+
+  qsort (test, count, sizeof (*test), case_bit_test::cmp);
+
+  /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
+     the minval subtractions, but it might make the mask constants more
+     expensive.  So, compare the costs.  */
+  if (compare_tree_int (minval, 0) > 0
+      && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
+    {
+      int cost_diff;
+      HOST_WIDE_INT m = tree_to_uhwi (minval);
+      rtx reg = gen_raw_REG (word_mode, 10000);
+      bool speed_p = optimize_insn_for_speed_p ();
+      cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg,
+					      GEN_INT (-m)), speed_p);
+      for (i = 0; i < count; i++)
+	{
+	  rtx r = immed_wide_int_const (test[i].mask, word_mode);
+	  cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r),
+				     word_mode, speed_p);
+	  r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode);
+	  cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r),
+				     word_mode, speed_p);
 	}
-      else
+      if (cost_diff > 0)
 	{
-	  /* Else leave this branch as one level,
-	     but fill in `parent' fields.  */
-	  np = *head;
-	  np->parent = parent;
-	  np->subtree_prob = np->prob;
-	  for (; np->right; np = np->right)
-	    {
-	      np->right->parent = np;
-	      (*head)->subtree_prob += np->right->subtree_prob;
-	    }
+	  for (i = 0; i < count; i++)
+	    test[i].mask = wi::lshift (test[i].mask, m);
+	  minval = build_zero_cst (TREE_TYPE (minval));
+	  range = maxval;
 	}
     }
-}
 
-/* Return true if a switch should be expanded as a decision tree.
-   RANGE is the difference between highest and lowest case.
-   UNIQ is number of unique case node targets, not counting the default case.
-   COUNT is the number of comparisons needed, not counting the default case.  */
+  /* Now build the test-and-branch code.  */
+
+  gsi = gsi_last_bb (m_case_bb);
+
+  /* idx = (unsigned)x - minval.  */
+  idx = fold_convert (unsigned_index_type, index_expr);
+  idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx,
+		     fold_convert (unsigned_index_type, minval));
+  idx = force_gimple_operand_gsi (&gsi, idx,
+				  /*simple=*/true, NULL_TREE,
+				  /*before=*/true, GSI_SAME_STMT);
+
+  /* if (idx > range) goto default */
+  range = force_gimple_operand_gsi (&gsi,
+				    fold_convert (unsigned_index_type, range),
+				    /*simple=*/true, NULL_TREE,
+				    /*before=*/true, GSI_SAME_STMT);
+  tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
+  basic_block new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb);
+  gsi = gsi_last_bb (new_bb);
+
+  /* csui = (1 << (word_mode) idx) */
+  csui = make_ssa_name (word_type_node);
+  tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one,
+		     fold_convert (word_type_node, idx));
+  tmp = force_gimple_operand_gsi (&gsi, tmp,
+				  /*simple=*/false, NULL_TREE,
+				  /*before=*/true, GSI_SAME_STMT);
+  shift_stmt = gimple_build_assign (csui, tmp);
+  gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
+  update_stmt (shift_stmt);
+
+  /* for each unique set of cases:
+       if (const & csui) goto target  */
+  for (k = 0; k < count; k++)
+    {
+      tmp = wide_int_to_tree (word_type_node, test[k].mask);
+      tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp);
+      tmp = force_gimple_operand_gsi (&gsi, tmp,
+				      /*simple=*/true, NULL_TREE,
+				      /*before=*/true, GSI_SAME_STMT);
+      tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
+      new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_bb);
+      gsi = gsi_last_bb (new_bb);
+    }
+
+  /* We should have removed all edges now.  */
+  gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
 
-static bool
-expand_switch_as_decision_tree_p (tree range,
-				  unsigned int uniq ATTRIBUTE_UNUSED,
-				  unsigned int count)
+  /* If nothing matched, go to the default label.  */
+  make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU);
+}
+
+basic_block
+bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
+						 tree cond, basic_block case_bb)
 {
-  int max_ratio;
+  tree tmp;
+  gcond *cond_stmt;
+  edge e_false;
+  basic_block new_bb, split_bb = gsi_bb (*gsip);
 
-  /* If neither casesi or tablejump is available, or flag_jump_tables
-     over-ruled us, we really have no choice.  */
-  if (!targetm.have_casesi () && !targetm.have_tablejump ())
-    return true;
-  if (!flag_jump_tables)
-    return true;
-#ifndef ASM_OUTPUT_ADDR_DIFF_ELT
-  if (flag_pic)
-    return true;
-#endif
+  edge e_true = make_edge (split_bb, case_bb, EDGE_TRUE_VALUE);
+  gcc_assert (e_true->src == split_bb);
 
-  /* If the switch is relatively small such that the cost of one
-     indirect jump on the target are higher than the cost of a
-     decision tree, go with the decision tree.
+  tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
+				  /*before=*/true, GSI_SAME_STMT);
+  cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
+  gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
 
-     If range of values is much bigger than number of values,
-     or if it is too large to represent in a HOST_WIDE_INT,
-     make a sequence of conditional branches instead of a dispatch.
+  e_false = split_block (split_bb, cond_stmt);
+  new_bb = e_false->dest;
+  redirect_edge_pred (e_true, split_bb);
 
-     The definition of "much bigger" depends on whether we are
-     optimizing for size or for speed.  If the former, the maximum
-     ratio range/count = 3, because this was found to be the optimal
-     ratio for size on i686-pc-linux-gnu, see PR11823.  The ratio
-     10 is much older, and was probably selected after an extensive
-     benchmarking investigation on numerous platforms.  Or maybe it
-     just made sense to someone at some point in the history of GCC,
-     who knows...  */
-  max_ratio = optimize_insn_for_size_p () ? 3 : 10;
-  if (count < case_values_threshold () || !tree_fits_uhwi_p (range)
-      || compare_tree_int (range, max_ratio * count) > 0)
-    return true;
+  e_false->flags &= ~EDGE_FALLTHRU;
+  e_false->flags |= EDGE_FALSE_VALUE;
+  e_false->probability = e_true->probability.invert ();
+  new_bb->count = e_false->count ();
 
-  return false;
+  return new_bb;
 }
 
-static void
-fix_phi_operands_for_edge (edge e, hash_map<tree, tree> *phi_mapping)
+
+void
+switch_decision_tree::compute_cases_per_edge ()
 {
-  basic_block bb = e->dest;
-  gphi_iterator gsi;
-  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+  basic_block bb = gimple_bb (m_switch);
+  reset_out_edges_aux ();
+  int ncases = gimple_switch_num_labels (m_switch);
+  for (int i = ncases - 1; i >= 1; --i)
     {
-      gphi *phi = gsi.phi ();
-
-      tree *definition = phi_mapping->get (gimple_phi_result (phi));
-      if (definition)
-	add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
+      tree elt = gimple_switch_label (m_switch, i);
+      tree lab = CASE_LABEL (elt);
+      basic_block case_bb = label_to_block_fn (cfun, lab);
+      edge case_edge = find_edge (bb, case_bb);
+      case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1);
     }
 }
 
-
-/* Add an unconditional jump to CASE_BB that happens in basic block BB.  */
-
-static void
-emit_jump (basic_block bb, basic_block case_bb,
-	   hash_map<tree, tree> *phi_mapping)
+bool
+switch_decision_tree::analyze_switch_statement ()
 {
-  edge e = single_succ_edge (bb);
-  redirect_edge_succ (e, case_bb);
-  fix_phi_operands_for_edge (e, phi_mapping);
-}
+  unsigned l = gimple_switch_num_labels (m_switch);
+  basic_block bb = gimple_bb (m_switch);
+  auto_vec<cluster *> clusters;
+  clusters.create (l - 1);
 
-/* Generate a decision tree, switching on INDEX_EXPR and jumping to
-   one of the labels in CASE_LIST or to the DEFAULT_LABEL.
-   DEFAULT_PROB is the estimated probability that it jumps to
-   DEFAULT_LABEL.
+  tree default_label = CASE_LABEL (gimple_switch_default_label (m_switch));
+  basic_block default_bb = label_to_block_fn (cfun, default_label);
+  m_case_bbs.reserve (l);
+  m_case_bbs.quick_push (default_bb);
 
-   We generate a binary decision tree to select the appropriate target
-   code.  */
-
-static void
-emit_case_decision_tree (gswitch *s, tree index_expr, tree index_type,
-			 case_node_ptr case_list, basic_block default_bb,
-			 tree default_label, profile_probability default_prob,
-			 hash_map<tree, tree> *phi_mapping)
-{
-  balance_case_nodes (&case_list, NULL);
+  compute_cases_per_edge ();
 
-  if (dump_file)
-    dump_function_to_file (current_function_decl, dump_file, dump_flags);
-  if (dump_file && (dump_flags & TDF_DETAILS))
+  for (unsigned i = 1; i < l; i++)
     {
-      int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
-      fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
-      dump_case_nodes (dump_file, case_list, indent_step, 0);
+      tree elt = gimple_switch_label (m_switch, i);
+      tree lab = CASE_LABEL (elt);
+      basic_block case_bb = label_to_block_fn (cfun, lab);
+      edge case_edge = find_edge (bb, case_bb);
+      tree low = CASE_LOW (elt);
+      tree high = CASE_HIGH (elt);
+
+      profile_probability p
+	= case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux));
+      clusters.quick_push (new simple_cluster (low, high, elt, case_bb, p));
+      m_case_bbs.quick_push (case_bb);
+    }
+
+  reset_out_edges_aux ();
+
+  vec<cluster *> output;
+  output.create (1);
+
+  /* Find whether the switch statement can be expanded with a method
+     different from decision tree.  */
+  unsigned end = clusters.length () - 1;
+  if (jump_table_cluster::can_be_handled (clusters, 0, end)
+      && jump_table_cluster::is_beneficial (clusters, 0, end))
+    output.safe_push (new jump_table_cluster (clusters, 0, end));
+  else if (bit_test_cluster::can_be_handled (clusters, 0, end)
+	   && bit_test_cluster::is_beneficial (clusters, 0, end))
+    output.safe_push (new bit_test_cluster (clusters, 0, end));
+  else
+    output = clusters;
+
+  if (dump_file)
+    {
+      fprintf (dump_file, ";; GIMPLE switch case clusters: ");
+      for (unsigned i = 0; i < output.length (); i++)
+	output[i]->dump (dump_file, dump_flags & TDF_DETAILS);
+      fprintf (dump_file, "\n");
+    }
+
+  bool expanded = try_switch_expansion (output);
+
+  for (unsigned i = 0; i < output.length (); i++)
+    delete output[i];
+
+  return expanded;
+}
+
+bool
+switch_decision_tree::try_switch_expansion (vec<cluster *> &clusters)
+{
+  tree index_expr = gimple_switch_index (m_switch);
+  tree index_type = TREE_TYPE (index_expr);
+  basic_block bb = gimple_bb (m_switch);
+
+  if (gimple_switch_num_labels (m_switch) == 1)
+    return false;
+
+  /* Find the default case target label.  */
+  tree default_label_expr = CASE_LABEL (gimple_switch_default_label (m_switch));
+  m_default_bb = label_to_block_fn (cfun, default_label_expr);
+  edge default_edge = find_edge (bb, m_default_bb);
+
+  /* Do the insertion of a case label into m_case_list.  The labels are
+     fed to us in descending order from the sorted vector of case labels used
+     in the tree part of the middle end.  So the list we construct is
+     sorted in ascending order.  */
+
+  for (int i = clusters.length () - 1; i >= 0; i--)
+    {
+      case_tree_node *r = m_case_list;
+      m_case_list = m_case_node_pool.allocate ();
+      m_case_list->m_right = r;
+      m_case_list->m_c = clusters[i];
     }
 
-  basic_block bb = gimple_bb (s);
+  record_phi_operand_mapping ();
+
+  /* Split basic block that contains the gswitch statement.  */
   gimple_stmt_iterator gsi = gsi_last_bb (bb);
   edge e;
   if (gsi_end_p (gsi))
@@ -1323,27 +1416,46 @@  emit_case_decision_tree (gswitch *s, tree index_expr, tree index_type,
     }
   bb = split_edge (e);
 
-  bb = emit_case_nodes (bb, index_expr, case_list, default_bb, default_label,
-			default_prob, index_type, phi_mapping);
+  /* Create new basic blocks for non-case clusters where specific expansion
+     needs to happen.  */
+  for (unsigned i = 0; i < clusters.length (); i++)
+    if (clusters[i]->get_type () != SIMPLE_CASE)
+      {
+	clusters[i]->m_case_bb = create_empty_bb (bb);
+	clusters[i]->m_case_bb->loop_father = bb->loop_father;
+      }
+
+  /* Do not do an extra work for a single cluster.  */
+  if (clusters.length () == 1
+      && clusters[0]->get_type () != SIMPLE_CASE)
+    clusters[0]->emit (index_expr, index_type,
+		       gimple_switch_default_label (m_switch), m_default_bb);
+  else
+    {
+      emit (bb, index_expr, default_edge->probability, index_type);
+
+      /* Emit cluster-specific switch handling.  */
+      for (unsigned i = 0; i < clusters.length (); i++)
+	if (clusters[i]->get_type () != SIMPLE_CASE)
+	  clusters[i]->emit (index_expr, index_type,
+			     gimple_switch_default_label (m_switch),
+			     m_default_bb);
+    }
 
-  if (bb)
-    emit_jump (bb, default_bb, phi_mapping);
+  fix_phi_operands_for_edges ();
 
-  /* Remove all edges and do just an edge that will reach default_bb.  */
-  gsi = gsi_last_bb (gimple_bb (s));
-  gsi_remove (&gsi, true);
+  return true;
 }
 
-static void
-record_phi_operand_mapping (const vec<basic_block> bbs, basic_block switch_bb,
-			    hash_map <tree, tree> *map)
+void
+switch_decision_tree::record_phi_operand_mapping ()
 {
+  basic_block switch_bb = gimple_bb (m_switch);
   /* Record all PHI nodes that have to be fixed after conversion.  */
-  for (unsigned i = 0; i < bbs.length (); i++)
+  for (unsigned i = 0; i < m_case_bbs.length (); i++)
     {
-      basic_block bb = bbs[i];
-
       gphi_iterator gsi;
+      basic_block bb = m_case_bbs[i];
       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 	{
 	  gphi *phi = gsi.phi ();
@@ -1355,7 +1467,7 @@  record_phi_operand_mapping (const vec<basic_block> bbs, basic_block switch_bb,
 		{
 		  tree def = gimple_phi_arg_def (phi, i);
 		  tree result = gimple_phi_result (phi);
-		  map->put (result, def);
+		  m_phi_mapping.put (result, def);
 		  break;
 		}
 	    }
@@ -1363,133 +1475,332 @@  record_phi_operand_mapping (const vec<basic_block> bbs, basic_block switch_bb,
     }
 }
 
-/* Attempt to expand gimple switch STMT to a decision tree.  */
-
-static bool
-try_switch_expansion (gswitch *stmt)
+void
+switch_decision_tree::fix_phi_operands_for_edges ()
 {
-  tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
-  basic_block default_bb;
-  unsigned int count, uniq;
-  int i;
-  int ncases = gimple_switch_num_labels (stmt);
-  tree index_expr = gimple_switch_index (stmt);
-  tree index_type = TREE_TYPE (index_expr);
-  tree elt;
-  basic_block bb = gimple_bb (stmt);
+  gphi_iterator gsi;
 
-  hash_map<tree, tree> phi_mapping;
-  auto_vec<basic_block> case_bbs;
+  for (unsigned i = 0; i < m_case_bbs.length (); i++)
+    {
+      basic_block bb = m_case_bbs[i];
+      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	{
+	  gphi *phi = gsi.phi ();
+	  for (unsigned j = 0; j < gimple_phi_num_args (phi); j++)
+	    {
+	      tree def = gimple_phi_arg_def (phi, j);
+	      if (def == NULL_TREE)
+		{
+		  edge e = gimple_phi_arg_edge (phi, j);
+		  tree *definition
+		    = m_phi_mapping.get (gimple_phi_result (phi));
+		  gcc_assert (definition);
+		  add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
+		}
+	    }
+	}
+    }
+}
 
-  /* A list of case labels; it is first built as a list and it may then
-     be rearranged into a nearly balanced binary tree.  */
-  case_node *case_list = 0;
+void
+switch_decision_tree::emit (basic_block bb, tree index_expr,
+			    profile_probability default_prob, tree index_type)
+{
+  balance_case_nodes (&m_case_list, NULL);
 
-  /* A pool for case nodes.  */
-  object_allocator<case_node> case_node_pool ("struct case_node pool");
+  if (dump_file)
+    dump_function_to_file (current_function_decl, dump_file, dump_flags);
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
+      fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
+      gcc_assert (m_case_list != NULL);
+      dump_case_nodes (dump_file, m_case_list, indent_step, 0);
+    }
 
-  /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
-     expressions being INTEGER_CST.  */
-  gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
+  bb = emit_case_nodes (bb, index_expr, m_case_list, default_prob, index_type);
 
-  if (ncases == 1)
-    return false;
+  if (bb)
+    emit_jump (bb, m_default_bb);
 
-  /* Find the default case target label.  */
-  tree default_label = CASE_LABEL (gimple_switch_default_label (stmt));
-  default_bb = label_to_block_fn (cfun, default_label);
-  edge default_edge = find_edge (bb, default_bb);
-  profile_probability default_prob = default_edge->probability;
-  case_bbs.safe_push (default_bb);
-
-  /* Get upper and lower bounds of case values.  */
-  elt = gimple_switch_label (stmt, 1);
-  minval = fold_convert (index_type, CASE_LOW (elt));
-  elt = gimple_switch_label (stmt, ncases - 1);
-  if (CASE_HIGH (elt))
-    maxval = fold_convert (index_type, CASE_HIGH (elt));
-  else
-    maxval = fold_convert (index_type, CASE_LOW (elt));
+  /* Remove all edges and do just an edge that will reach default_bb.  */
+  bb = gimple_bb (m_switch);
+  gimple_stmt_iterator gsi = gsi_last_bb (bb);
+  gsi_remove (&gsi, true);
 
-  /* Compute span of values.  */
-  range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
+  delete_basic_block (bb);
+}
 
-  /* Listify the labels queue and gather some numbers to decide
-     how to expand this switch.  */
-  uniq = 0;
-  count = 0;
-  hash_set<tree> seen_labels;
-  compute_cases_per_edge (stmt);
+void
+switch_decision_tree::balance_case_nodes (case_tree_node **head,
+					  case_tree_node *parent)
+{
+  case_tree_node *np;
 
-  for (i = ncases - 1; i >= 1; --i)
+  np = *head;
+  if (np)
     {
-      elt = gimple_switch_label (stmt, i);
-      tree low = CASE_LOW (elt);
-      gcc_assert (low);
-      tree high = CASE_HIGH (elt);
-      gcc_assert (!high || tree_int_cst_lt (low, high));
-      tree lab = CASE_LABEL (elt);
+      int i = 0;
+      int ranges = 0;
+      case_tree_node **npp;
+      case_tree_node *left;
 
-      /* Count the elements.
-	 A range counts double, since it requires two compares.  */
-      count++;
-      if (high)
-	count++;
-
-      /* If we have not seen this label yet, then increase the
-	 number of unique case node targets seen.  */
-      if (!seen_labels.add (lab))
-	uniq++;
-
-      /* The bounds on the case range, LOW and HIGH, have to be converted
-	 to case's index type TYPE.  Note that the original type of the
-	 case index in the source code is usually "lost" during
-	 gimplification due to type promotion, but the case labels retain the
-	 original type.  Make sure to drop overflow flags.  */
-      low = fold_convert (index_type, low);
-      if (TREE_OVERFLOW (low))
-	low = wide_int_to_tree (index_type, wi::to_wide (low));
-
-      /* The canonical from of a case label in GIMPLE is that a simple case
-	 has an empty CASE_HIGH.  For the casesi and tablejump expanders,
-	 the back ends want simple cases to have high == low.  */
-      if (!high)
-	high = low;
-      high = fold_convert (index_type, high);
-      if (TREE_OVERFLOW (high))
-	high = wide_int_to_tree (index_type, wi::to_wide (high));
+      /* Count the number of entries on branch.  Also count the ranges.  */
 
-      basic_block case_bb = label_to_block_fn (cfun, lab);
-      edge case_edge = find_edge (bb, case_bb);
-      case_list = add_case_node (
-	case_list, low, high, case_bb, lab,
-	case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux)),
-	case_node_pool);
+      while (np)
+	{
+	  if (!tree_int_cst_equal (np->m_c->get_low (), np->m_c->get_high ()))
+	    ranges++;
 
-      case_bbs.safe_push (case_bb);
-    }
-  reset_out_edges_aux (bb);
-  record_phi_operand_mapping (case_bbs, bb, &phi_mapping);
+	  i++;
+	  np = np->m_right;
+	}
 
-  /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
-     destination, such as one with a default case only.
-     It also removes cases that are out of range for the switch
-     type, so we should never get a zero here.  */
-  gcc_assert (count > 0);
+      if (i > 2)
+	{
+	  /* Split this list if it is long enough for that to help.  */
+	  npp = head;
+	  left = *npp;
 
-  /* Decide how to expand this switch.
-     The two options at this point are a dispatch table (casesi or
-     tablejump) or a decision tree.  */
+	  /* If there are just three nodes, split at the middle one.  */
+	  if (i == 3)
+	    npp = &(*npp)->m_right;
+	  else
+	    {
+	      /* Find the place in the list that bisects the list's total cost,
+		 where ranges count as 2.
+		 Here I gets half the total cost.  */
+	      i = (i + ranges + 1) / 2;
+	      while (1)
+		{
+		  /* Skip nodes while their cost does not reach that amount.  */
+		  if (!tree_int_cst_equal ((*npp)->m_c->get_low (),
+					   (*npp)->m_c->get_high ()))
+		    i--;
+		  i--;
+		  if (i <= 0)
+		    break;
+		  npp = &(*npp)->m_right;
+		}
+	    }
+	  *head = np = *npp;
+	  *npp = 0;
+	  np->m_parent = parent;
+	  np->m_left = left;
 
-  if (expand_switch_as_decision_tree_p (range, uniq, count))
-    {
-      emit_case_decision_tree (stmt, index_expr, index_type, case_list,
-			       default_bb, default_label, default_prob,
-			       &phi_mapping);
-      return true;
+	  /* Optimize each of the two split parts.  */
+	  balance_case_nodes (&np->m_left, np);
+	  balance_case_nodes (&np->m_right, np);
+	  np->m_c->m_subtree_prob = np->m_c->m_prob;
+	  np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob;
+	  np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
+	}
+      else
+	{
+	  /* Else leave this branch as one level,
+	     but fill in `parent' fields.  */
+	  np = *head;
+	  np->m_parent = parent;
+	  np->m_c->m_subtree_prob = np->m_c->m_prob;
+	  for (; np->m_right; np = np->m_right)
+	    {
+	      np->m_right->m_parent = np;
+	      (*head)->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
+	    }
+	}
     }
+}
+
+/* Dump ROOT, a list or tree of case nodes, to file.  */
+
+void
+switch_decision_tree::dump_case_nodes (FILE *f, case_tree_node *root,
+				       int indent_step, int indent_level)
+{
+  if (root == 0)
+    return;
+  indent_level++;
+
+  dump_case_nodes (f, root->m_left, indent_step, indent_level);
+
+  fputs (";; ", f);
+  fprintf (f, "%*s", indent_step * indent_level, "");
+  root->m_c->dump (f);
+  root->m_c->m_prob.dump (f);
+  fputs ("\n", f);
+
+  dump_case_nodes (f, root->m_right, indent_step, indent_level);
+}
+
+void
+switch_decision_tree::emit_jump (basic_block bb, basic_block case_bb)
+{
+  edge e = single_succ_edge (bb);
+  redirect_edge_succ (e, case_bb);
+}
+
+basic_block
+switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0,
+					       tree op1, tree_code comparison,
+					       basic_block label_bb,
+					       profile_probability prob)
+{
+  // TODO: it's once called with lhs != index.
+  op1 = fold_convert (TREE_TYPE (op0), op1);
+
+  gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE);
+  gimple_stmt_iterator gsi = gsi_last_bb (bb);
+  gsi_insert_after (&gsi, cond, GSI_NEW_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);
+  true_edge->probability = prob;
+
+  return false_edge->dest;
+}
+
+basic_block
+switch_decision_tree::emit_case_nodes (basic_block bb, tree index,
+				       case_tree_node *node,
+				       profile_probability default_prob,
+				       tree 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->m_right
+       ? node->m_right->m_c->m_subtree_prob : profile_probability::never ());
+  probability = ((probability + default_prob.apply_scale (1, 2))
+		 / (node->m_c->m_subtree_prob + default_prob));
+  bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), GT_EXPR,
+				test_bb, probability);
+  default_prob = default_prob.apply_scale (1, 2);
+
+  /* Value belongs to this node or to the left-hand subtree.  */
+  probability = node->m_c->m_prob /
+    (node->m_c->m_subtree_prob + default_prob);
+  bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (), GE_EXPR,
+				node->m_c->m_case_bb, probability);
 
-  return false;
+  /* Handle the left-hand subtree.  */
+  bb = emit_case_nodes (bb, index, node->m_left,
+			default_prob, index_type);
+
+  /* If the left-hand subtree fell through,
+     don't let it fall into the right-hand subtree.  */
+  if (m_default_bb)
+    emit_jump (bb, m_default_bb);
+
+  bb = emit_case_nodes (test_bb, index, node->m_right,
+			default_prob, index_type);
+
+  return bb;
+}
+
+/* The main function of the pass scans statements for switches and invokes
+   process_switch on them.  */
+
+namespace {
+
+const pass_data pass_data_convert_switch =
+{
+  GIMPLE_PASS, /* type */
+  "switchconv", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  TV_TREE_SWITCH_CONVERSION, /* tv_id */
+  ( PROP_cfg | PROP_ssa ), /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  TODO_update_ssa, /* todo_flags_finish */
+};
+
+class pass_convert_switch : public gimple_opt_pass
+{
+public:
+  pass_convert_switch (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_convert_switch, ctxt)
+  {}
+
+  /* opt_pass methods: */
+  virtual bool gate (function *) { return flag_tree_switch_conversion != 0; }
+  virtual unsigned int execute (function *);
+
+}; // class pass_convert_switch
+
+unsigned int
+pass_convert_switch::execute (function *fun)
+{
+  basic_block bb;
+  bool cfg_altered = false;
+
+  FOR_EACH_BB_FN (bb, fun)
+  {
+    gimple *stmt = last_stmt (bb);
+    if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
+      {
+	if (dump_file)
+	  {
+	    expanded_location loc = expand_location (gimple_location (stmt));
+
+	    fprintf (dump_file, "beginning to process the following "
+		     "SWITCH statement (%s:%d) : ------- \n",
+		     loc.file, loc.line);
+	    print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	    putc ('\n', dump_file);
+	  }
+
+	switch_conversion sconv;
+	sconv.expand (as_a <gswitch *> (stmt));
+	cfg_altered |= sconv.m_cfg_altered;
+	if (!sconv.m_reason)
+	  {
+	    if (dump_file)
+	      {
+		fputs ("Switch converted\n", dump_file);
+		fputs ("--------------------------------\n", dump_file);
+	      }
+
+	    /* Make no effort to update the post-dominator tree.
+	       It is actually not that hard for the transformations
+	       we have performed, but it is not supported
+	       by iterate_fix_dominators.  */
+	    free_dominance_info (CDI_POST_DOMINATORS);
+	  }
+	else
+	  {
+	    if (dump_file)
+	      {
+		fputs ("Bailing out - ", dump_file);
+		fputs (sconv.m_reason, dump_file);
+		fputs ("\n--------------------------------\n", dump_file);
+	      }
+	  }
+      }
+  }
+
+  return cfg_altered ? TODO_cleanup_cfg : 0;;
+}
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_convert_switch (gcc::context *ctxt)
+{
+  return new pass_convert_switch (ctxt);
 }
 
 /* The main function of the pass scans statements for switches and invokes
@@ -1538,23 +1849,35 @@  pass_lower_switch<O0>::execute (function *fun)
   basic_block bb;
   bool expanded = false;
 
+  auto_vec<gimple *> switch_statements;
+  switch_statements.create (1);
+
   FOR_EACH_BB_FN (bb, fun)
     {
       gimple *stmt = last_stmt (bb);
       if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
+	switch_statements.safe_push (stmt);
+    }
+
+  for (unsigned i = 0; i < switch_statements.length (); i++)
+    {
+      gimple *stmt = switch_statements[i];
+      if (dump_file)
 	{
-	  if (dump_file)
-	    {
-	      expanded_location loc = expand_location (gimple_location (stmt));
+	  expanded_location loc = expand_location (gimple_location (stmt));
 
-	      fprintf (dump_file, "beginning to process the following "
-				  "SWITCH statement (%s:%d) : ------- \n",
-		       loc.file, loc.line);
-	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
-	      putc ('\n', dump_file);
-	    }
+	  fprintf (dump_file, "beginning to process the following "
+		   "SWITCH statement (%s:%d) : ------- \n",
+		   loc.file, loc.line);
+	  print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	  putc ('\n', dump_file);
+	}
 
-	  expanded |= try_switch_expansion (as_a<gswitch *> (stmt));
+      gswitch *swtch = dyn_cast<gswitch *> (stmt);
+      if (swtch)
+	{
+	  switch_decision_tree dt (swtch);
+	  expanded |= dt.analyze_switch_statement ();
 	}
     }
 
@@ -1581,112 +1904,4 @@  make_pass_lower_switch (gcc::context *ctxt)
   return new pass_lower_switch<false> (ctxt);
 }
 
-/* Generate code to compare X with Y so that the condition codes are
-   set and to jump to LABEL if the condition is true.  If X is a
-   constant and Y is not a constant, then the comparison is swapped to
-   ensure that the comparison RTL has the canonical form.
-
-   UNSIGNEDP nonzero says that X and Y are unsigned; this matters if they
-   need to be widened.  UNSIGNEDP is also used to select the proper
-   branch condition code.
-
-   If X and Y have mode BLKmode, then SIZE specifies the size of both X and Y.
-
-   MODE is the mode of the inputs (in case they are const_int).
-
-   COMPARISON is the rtl operator to compare with (EQ, NE, GT, etc.).
-   It will be potentially converted into an unsigned variant based on
-   UNSIGNEDP to select a proper jump instruction.
-
-   PROB is the probability of jumping to LABEL.  */
-
-static basic_block
-emit_cmp_and_jump_insns (basic_block bb, tree op0, tree op1,
-			 tree_code comparison, basic_block label_bb,
-			 profile_probability prob,
-			 hash_map<tree, tree> *phi_mapping)
-{
-  gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE);
-  gimple_stmt_iterator gsi = gsi_last_bb (bb);
-  gsi_insert_after (&gsi, cond, GSI_NEW_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;
-}
-
-/* Computes the conditional probability of jumping to a target if the branch
-   instruction is executed.
-   TARGET_PROB is the estimated probability of jumping to a target relative
-   to some basic block BB.
-   BASE_PROB is the probability of reaching the branch instruction relative
-   to the same basic block BB.  */
 
-static inline profile_probability
-conditional_probability (profile_probability target_prob,
-			 profile_probability base_prob)
-{
-  return target_prob / base_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.  */
-
-static basic_block
-emit_case_nodes (basic_block bb, tree index, case_node_ptr node,
-		 basic_block default_bb, tree default_label,
-		 profile_probability default_prob, tree index_type,
-		 hash_map<tree, tree> *phi_mapping)
-{
-  /* 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);
-
-  /* Handle the left-hand subtree.  */
-  bb = emit_case_nodes (bb, index, node->left, default_bb,
-			default_label, default_prob, index_type,
-			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);
-
-  bb = emit_case_nodes (test_bb, index, node->right, default_bb,
-			default_label, default_prob, index_type,
-			phi_mapping);
-
-  return bb;
-}
diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h
index 297faec119f..54dd2c34ee8 100644
--- a/gcc/tree-switch-conversion.h
+++ b/gcc/tree-switch-conversion.h
@@ -22,6 +22,538 @@  along with GCC; see the file COPYING3.  If not see
 
 namespace tree_switch_conversion {
 
+/* Type of cluster.  */
+
+enum cluster_type
+{
+  SIMPLE_CASE,
+  JUMP_TABLE,
+  BIT_TEST
+};
+
+#define PRINT_CASE(f,c) print_generic_expr (f, c)
+
+/* Abstract base class for representing a cluster of cases.  */
+
+struct cluster
+{
+  /* Constructor.  */
+  cluster (tree case_label_expr, basic_block case_bb, profile_probability prob,
+	   profile_probability subtree_prob);
+
+  /* Destructor.  */
+  virtual ~cluster ()
+  {}
+
+  /* Return type.  */
+  virtual cluster_type get_type () = 0;
+
+  /* Get low value covered by a cluster.  */
+  virtual tree get_low () = 0;
+
+  /* Get high value covered by a cluster.  */
+  virtual tree get_high () = 0;
+
+  /* Debug content of a cluster.  */
+  virtual void debug () = 0;
+
+  /* Dump content of a cluster.  */
+  virtual void dump (FILE *f, bool details = false) = 0;
+
+  /* Emit GIMPLE code to handle the cluster.  */
+  virtual void emit (tree, tree, tree, basic_block) = 0;
+
+  /* Return range of a cluster.  If value would overflow in type of LOW,
+     then return 0.  */
+  static unsigned HOST_WIDE_INT get_range (tree low, tree high)
+  {
+    tree r = fold_build2 (MINUS_EXPR, TREE_TYPE (low), high, low);
+    if (!tree_fits_uhwi_p (r))
+      return 0;
+
+    return tree_to_uhwi (r) + 1;
+  }
+
+  /* Case label.  */
+  tree m_case_label_expr;
+
+  /* Basic block of the case.  */
+  basic_block m_case_bb;
+
+  /* Probability of taking this cluster.  */
+  profile_probability m_prob;
+
+  /* Probability of reaching subtree rooted at this node.  */
+  profile_probability m_subtree_prob;
+
+protected:
+  /* Default constructor.  */
+  cluster () {}
+};
+
+cluster::cluster (tree case_label_expr, basic_block case_bb,
+		  profile_probability prob, profile_probability subtree_prob):
+  m_case_label_expr (case_label_expr), m_case_bb (case_bb), m_prob (prob),
+  m_subtree_prob (subtree_prob)
+{
+}
+
+/* Subclass of cluster representing a simple contiguous range
+   from [low..high].  */
+
+struct simple_cluster: public cluster
+{
+  /* Constructor.  */
+  simple_cluster (tree low, tree high, tree case_label_expr,
+		  basic_block case_bb, profile_probability prob);
+
+  /* Destructor.  */
+  ~simple_cluster ()
+  {}
+
+  cluster_type
+  get_type ()
+  {
+    return SIMPLE_CASE;
+  }
+
+  tree
+  get_low ()
+  {
+    return m_low;
+  }
+
+  tree
+  get_high ()
+  {
+    return m_high;
+  }
+
+  void
+  debug ()
+  {
+    dump (stderr);
+  }
+
+  void
+  dump (FILE *f, bool details ATTRIBUTE_UNUSED = false)
+  {
+    PRINT_CASE (f, get_low ());
+    if (get_low () != get_high ())
+      {
+	fprintf (f, "-");
+	PRINT_CASE (f, get_high ());
+      }
+    fprintf (f, " ");
+  }
+
+  void emit (tree, tree, tree, basic_block)
+  {
+    gcc_unreachable ();
+  }
+
+  /* Low value of the case.  */
+  tree m_low;
+
+  /* High value of the case.  */
+  tree m_high;
+
+  /* True if case is a range.  */
+  bool m_range_p;
+};
+
+simple_cluster::simple_cluster (tree low, tree high, tree case_label_expr,
+				basic_block case_bb, profile_probability prob):
+  cluster (case_label_expr, case_bb, prob, prob),
+  m_low (low), m_high (high)
+{
+  m_range_p = m_high != NULL;
+  if (m_high == NULL)
+    m_high = m_low;
+}
+
+/* Abstract subclass of jump table and bit test cluster,
+   handling a collection of simple_cluster instances.  */
+
+struct group_cluster: public cluster
+{
+  /* Constructor.  */
+  group_cluster (vec<cluster *> &clusters, unsigned start, unsigned end);
+
+  /* Destructor.  */
+  ~group_cluster ();
+
+  tree
+  get_low ()
+  {
+    return m_cases[0]->get_low ();
+  }
+
+  tree
+  get_high ()
+  {
+    return m_cases[m_cases.length () - 1]->get_high ();
+  }
+
+  void
+  debug ()
+  {
+    dump (stderr);
+  }
+
+  void dump (FILE *f, bool details = false);
+
+  /* List of simple clusters handled by the group.  */
+  vec<simple_cluster *> m_cases;
+};
+
+/* Concrete subclass of group_cluster representing a collection
+   of cases to be implemented as a jump table.
+   The "emit" vfunc gernerates a nested switch statement which
+   is later lowered to a jump table.  */
+
+struct jump_table_cluster: public group_cluster
+{
+  /* Constructor.  */
+  jump_table_cluster (vec<cluster *> &clusters, unsigned start, unsigned end)
+  : group_cluster (clusters, start, end)
+  {}
+
+  cluster_type
+  get_type ()
+  {
+    return JUMP_TABLE;
+  }
+
+  void emit (tree index_expr, tree index_type,
+	     tree default_label_expr, basic_block default_bb);
+
+  /* Return true when cluster starting at START and ending at END (inclusive)
+     can build a jump-table.  */
+  static bool can_be_handled (const vec<cluster *> &clusters, unsigned start,
+			      unsigned end);
+
+  /* Return true if cluster starting at START and ending at END (inclusive)
+     is profitable transformation.  */
+  static bool is_beneficial (const vec<cluster *> &clusters, unsigned start,
+			     unsigned end);
+
+  /* Return the smallest number of different values for which it is best
+     to use a jump-table instead of a tree of conditional branches.  */
+  static inline unsigned int case_values_threshold (void);
+};
+
+/* A GIMPLE switch statement can be expanded to a short sequence of bit-wise
+comparisons.  "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
+where CST and MINVAL are integer constants.  This is better than a series
+of compare-and-banch insns in some cases,  e.g. we can implement:
+
+	if ((x==4) || (x==6) || (x==9) || (x==11))
+
+as a single bit test:
+
+	if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
+
+This transformation is only applied if the number of case targets is small,
+if CST constains at least 3 bits, and "1 << x" is cheap.  The bit tests are
+performed in "word_mode".
+
+The following example shows the code the transformation generates:
+
+	int bar(int x)
+	{
+		switch (x)
+		{
+		case '0':  case '1':  case '2':  case '3':  case '4':
+		case '5':  case '6':  case '7':  case '8':  case '9':
+		case 'A':  case 'B':  case 'C':  case 'D':  case 'E':
+		case 'F':
+			return 1;
+		}
+		return 0;
+	}
+
+==>
+
+	bar (int x)
+	{
+		tmp1 = x - 48;
+		if (tmp1 > (70 - 48)) goto L2;
+		tmp2 = 1 << tmp1;
+		tmp3 = 0b11111100000001111111111;
+		if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
+	L1:
+		return 1;
+	L2:
+		return 0;
+	}
+
+TODO: There are still some improvements to this transformation that could
+be implemented:
+
+* A narrower mode than word_mode could be used if that is cheaper, e.g.
+  for x86_64 where a narrower-mode shift may result in smaller code.
+
+* The compounded constant could be shifted rather than the one.  The
+  test would be either on the sign bit or on the least significant bit,
+  depending on the direction of the shift.  On some machines, the test
+  for the branch would be free if the bit to test is already set by the
+  shift operation.
+
+This transformation was contributed by Roger Sayle, see this e-mail:
+   http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
+*/
+
+struct bit_test_cluster: public group_cluster
+{
+  /* Constructor.  */
+  bit_test_cluster (vec<cluster *> &clusters, unsigned start, unsigned end)
+  :group_cluster (clusters, start, end)
+  {}
+
+  cluster_type
+  get_type ()
+  {
+    return BIT_TEST;
+  }
+
+/*  Expand a switch statement by a short sequence of bit-wise
+    comparisons.  "switch(x)" is effectively converted into
+    "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
+    integer constants.
+
+    INDEX_EXPR is the value being switched on.
+
+    MINVAL is the lowest case value of in the case nodes,
+    and RANGE is highest value minus MINVAL.  MINVAL and RANGE
+    are not guaranteed to be of the same type as INDEX_EXPR
+    (the gimplifier doesn't change the type of case label values,
+    and MINVAL and RANGE are derived from those values).
+    MAXVAL is MINVAL + RANGE.
+
+    There *MUST* be max_case_bit_tests or less unique case
+    node targets.  */
+  void emit (tree index_expr, tree index_type,
+	     tree default_label_expr, basic_block default_bb);
+
+  /* Return true when RANGE of case values with UNIQ labels
+     can build a bit test.  */
+  static bool can_be_handled (unsigned HOST_WIDE_INT range, unsigned uniq);
+
+  /* Return true when cluster starting at START and ending at END (inclusive)
+     can build a bit test.  */
+  static bool can_be_handled (const vec<cluster *> &clusters, unsigned start,
+			      unsigned end);
+
+  /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test
+     transformation.  */
+  static bool is_beneficial (unsigned count, unsigned uniq);
+
+  /* Return true if cluster starting at START and ending at END (inclusive)
+     is profitable transformation.  */
+  static bool is_beneficial (const vec<cluster *> &clusters, unsigned start,
+			     unsigned end);
+
+/* Split the basic block at the statement pointed to by GSIP, and insert
+   a branch to the target basic block of E_TRUE conditional on tree
+   expression COND.
+
+   It is assumed that there is already an edge from the to-be-split
+   basic block to E_TRUE->dest block.  This edge is removed, and the
+   profile information on the edge is re-used for the new conditional
+   jump.
+
+   The CFG is updated.  The dominator tree will not be valid after
+   this transformation, but the immediate dominators are updated if
+   UPDATE_DOMINATORS is true.
+
+   Returns the newly created basic block.  */
+  static basic_block hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
+						    tree cond,
+						    basic_block case_bb);
+
+  /* Maximum number of different basic blocks that can be handled by
+     a bit test.  */
+  static const int m_max_case_bit_tests = 3;
+};
+
+/* Helper struct to find minimal clusters.  */
+
+struct min_cluster_item
+{
+  /* Constructor.  */
+  min_cluster_item (unsigned count, unsigned start, unsigned non_jt_cases):
+    m_count (count), m_start (start), m_non_jt_cases (non_jt_cases)
+  {}
+
+  /* Count of clusters.  */
+  unsigned m_count;
+
+  /* Index where is cluster boundary.  */
+  unsigned m_start;
+
+  /* Total number of cases that will not be in a jump table.  */
+  unsigned m_non_jt_cases;
+};
+
+/* Helper struct to represent switch decision tree.  */
+
+struct case_tree_node
+{
+  /* Empty Constructor.  */
+  case_tree_node ();
+
+  /* Left son in binary tree.  */
+  case_tree_node *m_left;
+
+  /* Right son in binary tree; also node chain.  */
+  case_tree_node *m_right;
+
+  /* Parent of node in binary tree.  */
+  case_tree_node *m_parent;
+
+  /* Cluster represented by this tree node.  */
+  cluster *m_c;
+};
+
+inline
+case_tree_node::case_tree_node ():
+  m_left (NULL), m_right (NULL), m_parent (NULL), m_c (NULL)
+{
+}
+
+unsigned int
+jump_table_cluster::case_values_threshold (void)
+{
+  unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
+
+  if (threshold == 0)
+    threshold = targetm.case_values_threshold ();
+
+  return threshold;
+}
+
+/* A case_bit_test represents a set of case nodes that may be
+   selected from using a bit-wise comparison.  HI and LO hold
+   the integer to be tested against, TARGET_EDGE contains the
+   edge to the basic block to jump to upon success and BITS
+   counts the number of case nodes handled by this test,
+   typically the number of bits set in HI:LO.  The LABEL field
+   is used to quickly identify all cases in this set without
+   looking at label_to_block for every case label.  */
+
+struct case_bit_test
+{
+  wide_int mask;
+  basic_block target_bb;
+  tree label;
+  int bits;
+
+  /* Comparison function for qsort to order bit tests by decreasing
+     probability of execution.  */
+  static int cmp (const void *p1, const void *p2);
+};
+
+struct switch_decision_tree
+{
+  /* Constructor.  */
+  switch_decision_tree (gswitch *swtch): m_switch (swtch), m_phi_mapping (),
+    m_case_bbs (), m_case_node_pool ("struct case_node pool"),
+    m_case_list (NULL)
+  {
+  }
+
+  /* Analyze switch statement and return true when the statement is expanded
+     as decision tree.  */
+  bool analyze_switch_statement ();
+
+  /* Attempt to expand CLUSTERS as a decision tree.  Return true when
+     expanded.  */
+  bool try_switch_expansion (vec<cluster *> &clusters);
+
+  /* Reset the aux field of all outgoing edges of switch basic block.  */
+  inline void reset_out_edges_aux ();
+
+  /* Compute the number of case labels that correspond to each outgoing edge of
+     switch statement.  Record this information in the aux field of the edge.
+     */
+  void compute_cases_per_edge ();
+
+  /* Before switch transformation, record all SSA_NAMEs defined in switch BB
+     and used in a label basic block.  */
+  void record_phi_operand_mapping ();
+
+  /* Append new operands to PHI statements that were introduced due to
+     addition of new edges to case labels.  */
+  void fix_phi_operands_for_edges ();
+
+  /* Generate a decision tree, switching on INDEX_EXPR and jumping to
+     one of the labels in CASE_LIST or to the DEFAULT_LABEL.
+
+     We generate a binary decision tree to select the appropriate target
+     code.  */
+
+  void emit (basic_block bb, tree index_expr,
+	     profile_probability default_prob, tree index_type);
+
+  /* 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.
+     DEFAULT_PROB is probability of cases leading to default BB.
+     INDEX_TYPE is the type of the index of the switch.  */
+  basic_block emit_case_nodes (basic_block bb, tree index,
+			       case_tree_node *node,
+			       profile_probability default_prob,
+			       tree index_type);
+
+  /* Take an ordered list of case nodes
+     and transform them into a near optimal binary tree,
+     on the assumption that any target code selection value is as
+     likely as any other.
+
+     The transformation is performed by splitting the ordered
+     list into two equal sections plus a pivot.  The parts are
+     then attached to the pivot as left and right branches.  Each
+     branch is then transformed recursively.  */
+  static void balance_case_nodes (case_tree_node **head,
+				  case_tree_node *parent);
+
+  /* Dump ROOT, a list or tree of case nodes, to file F.  */
+  static void dump_case_nodes (FILE *f, case_tree_node *root, int indent_step,
+			       int indent_level);
+
+  /* Add an unconditional jump to CASE_BB that happens in basic block BB.  */
+  static void emit_jump (basic_block bb, basic_block case_bb);
+
+  /* Generate code to compare OP0 with OP1 so that the condition codes are
+     set and to jump to LABEL_BB if the condition is true.
+     COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
+     PROB is the probability of jumping to LABEL_BB.  */
+
+  static basic_block emit_cmp_and_jump_insns (basic_block bb, tree op0,
+					      tree op1, tree_code comparison,
+					      basic_block label_bb,
+					      profile_probability prob);
+
+  /* Switch statement.  */
+  gswitch *m_switch;
+
+  /* Map of PHI nodes that have to be fixed after expansion.  */
+  hash_map<tree, tree> m_phi_mapping;
+
+  /* List of basic blocks that belong to labels of the switch.  */
+  auto_vec<basic_block> m_case_bbs;
+
+  /* Basic block with default label.  */
+  basic_block m_default_bb;
+
+  /* A pool for case nodes.  */
+  object_allocator<case_tree_node> m_case_node_pool;
+
+  /* Balanced tree of case nodes.  */
+  case_tree_node *m_case_list;
+};
+
 /*
      Switch initialization conversion
 
@@ -271,6 +803,9 @@  struct switch_conversion
      labels.  */
   bool m_default_case_nonstandard;
 
+  /* Number of uniq labels for non-default edges.  */
+  unsigned int m_uniq;
+
   /* Count is number of non-default edges.  */
   unsigned int m_count;
 
@@ -278,6 +813,16 @@  struct switch_conversion
   bool m_cfg_altered;
 };
 
+void
+switch_decision_tree::reset_out_edges_aux ()
+{
+  basic_block bb = gimple_bb (m_switch);
+  edge e;
+  edge_iterator ei;
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    e->aux = (void *) 0;
+}
+
 } // tree_switch_conversion namespace
 
 #endif // TREE_SWITCH_CONVERSION_H