Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-30 Thread Martin Liška 
On 08/30/2017 10:33 AM, Rainer Orth wrote:
> Hi Martin,
> 
>> Yes, sorry for the missing entries. Fixed and installed as r251412.
>> Hopefully fall out will be small.
> 
> there's
> 
> UNRESOLVED: gcc.dg/tree-ssa/vrp104.c scan-tree-dump-times switchlower 
> "switch" 1
> 
> everywhere, it seems.  gcc.log has
> 
> gcc.dg/tree-ssa/vrp104.c: dump file does not exist
> 
> For one, the testcase needs -fdump-tree-switchlower now, and on
> i386-pc-solaris2.11 I find 2 instances of switch in the dump...
> 
> Please fix.
> 
>   Rainer
> 

Sorry for the breakage. Fixed by installing attach patch, which is obvious.

Martin
>From 60fd6e2bd2927acf33f7aab2c178cbfcd268d314 Mon Sep 17 00:00:00 2001
From: marxin 
Date: Wed, 30 Aug 2017 13:06:12 +0200
Subject: [PATCH] Fix test-case vrp104.c.

gcc/testsuite/ChangeLog:

2017-08-30  Martin Liska  

	* gcc.dg/tree-ssa/vrp104.c: Change dump file name.
---
 gcc/testsuite/gcc.dg/tree-ssa/vrp104.c | 6 --
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
index aa3b00a1204..0a952267b29 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
@@ -1,6 +1,8 @@
 /* PR tree-optimization/18046  */
-/* { dg-options "-O2 -fdump-tree-optimized" }  */
-/* { dg-final { scan-tree-dump-times "switch" 1 "switchlower" } }  */
+/* { dg-options "-O2 -fdump-tree-switchlower" }  */
+/* We scan for 2 switches as the dump file reports a transformation,
+   IL really contains just a single.  */
+/* { dg-final { scan-tree-dump-times "switch" 2 "switchlower" } }  */
 
 void foo (void);
 void bar (void);
-- 
2.14.1

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-30 Thread Rainer Orth 
Hi Martin,

> Yes, sorry for the missing entries. Fixed and installed as r251412.
> Hopefully fall out will be small.

there's

UNRESOLVED: gcc.dg/tree-ssa/vrp104.c scan-tree-dump-times switchlower "switch" 1

everywhere, it seems.  gcc.log has

gcc.dg/tree-ssa/vrp104.c: dump file does not exist

For one, the testcase needs -fdump-tree-switchlower now, and on
i386-pc-solaris2.11 I find 2 instances of switch in the dump...

Please fix.

Rainer

-- 
-
Rainer Orth, Center for Biotechnology, Bielefeld University

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-29 Thread Martin Liška 
On 08/29/2017 01:42 PM, Richard Biener wrote:
> On Thu, Aug 24, 2017 at 5:35 PM, Martin Liška  wrote:
>> On 08/18/2017 12:25 PM, Martin Liška wrote:
>>> On 08/18/2017 11:30 AM, Richard Biener wrote:
 On Tue, Aug 15, 2017 at 2:37 PM, Martin Liška  wrote:
> On 08/14/2017 10:32 AM, Richard Biener wrote:
>> Hmm, but the existing "lowering" part is called from the
>> switch-conversion pass.  So
>> I'm not sure a new file is good.
>
> Good, I'm not against having that in a single file. So new version of the 
> patch
> does that.
>
> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>
> Ready to be installed?

 Hmm, I see you duplicate add_case_node for example.  Is that just 
 temporary?
 If not can you please factor out the data structure and common code?
 (case.[Ch]?)
>>>
>>> You are right. As we'll generate just jump table in stmt.c the proper fix 
>>> is to remove
>>> all usages of 'case_node' in the file because simple iteration of labels 
>>> will work fine.
>>> Let me do it incrementally to minimize fall out :)
>>
>> Hello.
>>
>> So lesson learned. I should follow your recommendation and make the clean-up 
>> in stmt.c. I didn't
>> so adding new variant of case_node with a different size caused bootstrap 
>> failure on aarch64 and
>> it was quite hard to debug. So sending updated version of the patch which 
>> has cleaned up stmt.c.
>>
>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. 
>> Same of aarch64-linux-gnu.
>>
>> Ready to be installed?
> 
> No ChangeLog entry for tree-switch-conversion.c?  At least you added
> make_pass_lower_switch
> and friends.

Hi.

Yes, sorry for the missing entries. Fixed and installed as r251412.
Hopefully fall out will be small.

Martin

> 
> Ok with a little more verbose changelog.
> 
> Thanks and sorry for the delay,
> Richard.
> 
>> Martin
>>>
>>> Martin
>>>

 Thanks,
 Richard.

> Martin
>>>
>>

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-29 Thread Richard Biener 
On Thu, Aug 24, 2017 at 5:35 PM, Martin Liška  wrote:
> On 08/18/2017 12:25 PM, Martin Liška wrote:
>> On 08/18/2017 11:30 AM, Richard Biener wrote:
>>> On Tue, Aug 15, 2017 at 2:37 PM, Martin Liška  wrote:
 On 08/14/2017 10:32 AM, Richard Biener wrote:
> Hmm, but the existing "lowering" part is called from the
> switch-conversion pass.  So
> I'm not sure a new file is good.

 Good, I'm not against having that in a single file. So new version of the 
 patch
 does that.

 Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.

 Ready to be installed?
>>>
>>> Hmm, I see you duplicate add_case_node for example.  Is that just temporary?
>>> If not can you please factor out the data structure and common code?
>>> (case.[Ch]?)
>>
>> You are right. As we'll generate just jump table in stmt.c the proper fix is 
>> to remove
>> all usages of 'case_node' in the file because simple iteration of labels 
>> will work fine.
>> Let me do it incrementally to minimize fall out :)
>
> Hello.
>
> So lesson learned. I should follow your recommendation and make the clean-up 
> in stmt.c. I didn't
> so adding new variant of case_node with a different size caused bootstrap 
> failure on aarch64 and
> it was quite hard to debug. So sending updated version of the patch which has 
> cleaned up stmt.c.
>
> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. 
> Same of aarch64-linux-gnu.
>
> Ready to be installed?

No ChangeLog entry for tree-switch-conversion.c?  At least you added
make_pass_lower_switch
and friends.

Ok with a little more verbose changelog.

Thanks and sorry for the delay,
Richard.

> Martin
>>
>> Martin
>>
>>>
>>> Thanks,
>>> Richard.
>>>
 Martin
>>
>

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-24 Thread Martin Liška 
On 08/18/2017 12:25 PM, Martin Liška wrote:
> On 08/18/2017 11:30 AM, Richard Biener wrote:
>> On Tue, Aug 15, 2017 at 2:37 PM, Martin Liška  wrote:
>>> On 08/14/2017 10:32 AM, Richard Biener wrote:
 Hmm, but the existing "lowering" part is called from the
 switch-conversion pass.  So
 I'm not sure a new file is good.
>>>
>>> Good, I'm not against having that in a single file. So new version of the 
>>> patch
>>> does that.
>>>
>>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>>>
>>> Ready to be installed?
>>
>> Hmm, I see you duplicate add_case_node for example.  Is that just temporary?
>> If not can you please factor out the data structure and common code?
>> (case.[Ch]?)
> 
> You are right. As we'll generate just jump table in stmt.c the proper fix is 
> to remove
> all usages of 'case_node' in the file because simple iteration of labels will 
> work fine.
> Let me do it incrementally to minimize fall out :)

Hello.

So lesson learned. I should follow your recommendation and make the clean-up in 
stmt.c. I didn't
so adding new variant of case_node with a different size caused bootstrap 
failure on aarch64 and
it was quite hard to debug. So sending updated version of the patch which has 
cleaned up stmt.c.

Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. Same 
of aarch64-linux-gnu.

Ready to be installed?
Martin
> 
> Martin
> 
>>
>> Thanks,
>> Richard.
>>
>>> Martin
> 

>From be0ef53761acf78108b26f71970cc44c7616b22e Mon Sep 17 00:00:00 2001
From: marxin 
Date: Mon, 31 Jul 2017 14:01:53 +0200
Subject: [PATCH] Make expansion of balanced binary trees of switches on tree
 level.

gcc/ChangeLog:

2017-07-31  Martin Liska  

	* passes.def: Include pass_lower_switch.
	* stmt.c (dump_case_nodes): Remove and move to
	tree-switch-conversion.
	(case_values_threshold): Likewise.
	(expand_switch_as_decision_tree_p): Likewise.
	(emit_case_decision_tree): Likewise.
	(expand_case): Likewise.
	(balance_case_nodes): Likewise.
	(node_has_low_bound): Likewise.
	(node_has_high_bound): Likewise.
	(node_is_bounded): Likewise.
	(emit_case_nodes): Likewise.
	(struct simple_case_node): New struct.
	(add_case_node): Remove.
	(emit_case_dispatch_table): Use vector instead of case_list.
	(reset_out_edges_aux): Remove.
	(compute_cases_per_edge): Likewise.
	(expand_case): Build list of simple_case_node.
	(expand_sjlj_dispatch_table): Use it.
	* timevar.def: Add TV_TREE_SWITCH_LOWERING.
	* tree-pass.h: Add make_pass_lower_switch.

gcc/testsuite/ChangeLog:

2017-07-31  Martin Liska  

	* gcc.dg/tree-prof/update-loopch.c: Scan patterns in
	switchlower.
	* gcc.dg/tree-ssa/vrp104.c: Likewise.
---
 gcc/passes.def |1 +
 gcc/stmt.c | 1026 +
 gcc/testsuite/gcc.dg/tree-prof/update-loopch.c |   10 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp104.c |2 +-
 gcc/timevar.def|1 +
 gcc/tree-pass.h|1 +
 gcc/tree-switch-conversion.c   | 1178 
 7 files changed, 1219 insertions(+), 1000 deletions(-)

diff --git a/gcc/passes.def b/gcc/passes.def
index 316e19d12e3..81b6e62f602 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -394,6 +394,7 @@ along with GCC; see the file COPYING3.  If not see
   NEXT_PASS (pass_lower_vaarg);
   NEXT_PASS (pass_lower_vector);
   NEXT_PASS (pass_lower_complex_O0);
+  NEXT_PASS (pass_lower_switch);
   NEXT_PASS (pass_sancov_O0);
   NEXT_PASS (pass_asan_O0);
   NEXT_PASS (pass_tsan_O0);
diff --git a/gcc/stmt.c b/gcc/stmt.c
index 73aa9b2b809..39d29ff3da9 100644
--- a/gcc/stmt.c
+++ b/gcc/stmt.c
@@ -32,7 +32,6 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple.h"
 #include "cfghooks.h"
 #include "predict.h"
-#include "alloc-pool.h"
 #include "memmodel.h"
 #include "tm_p.h"
 #include "optabs.h"
@@ -63,53 +62,30 @@ along with GCC; see the file COPYING3.  If not see
as in C, the high and low limits are the same.
 
We start with a vector of case nodes sorted in ascending order, and
-   the default label as the last element in the vector.  Before expanding
-   to RTL, we transform this vector into a list linked via the RIGHT
-   fields in the case_node struct.  Nodes with higher case values are
-   later in the list.
-
-   Switch statements can be output in three forms.  A branch table is
-   used if there are more than a few labels and the labels are dense
-   within the range between the smallest and largest case value.  If a
-   branch table is used, no further manipulations are done with the case
-   node chain.
-
-   The alternative to the use of a branch table is to generate a series
-   of compare and jump insns.  When that is done, we use the LEFT, RIGHT,
-   and PARENT fields to hold a binary tree.  Initially the tree is
-   totally unbalanced, with everything

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-18 Thread Martin Liška 
On 08/18/2017 11:30 AM, Richard Biener wrote:
> On Tue, Aug 15, 2017 at 2:37 PM, Martin Liška  wrote:
>> On 08/14/2017 10:32 AM, Richard Biener wrote:
>>> Hmm, but the existing "lowering" part is called from the
>>> switch-conversion pass.  So
>>> I'm not sure a new file is good.
>>
>> Good, I'm not against having that in a single file. So new version of the 
>> patch
>> does that.
>>
>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>>
>> Ready to be installed?
> 
> Hmm, I see you duplicate add_case_node for example.  Is that just temporary?
> If not can you please factor out the data structure and common code?
> (case.[Ch]?)

You are right. As we'll generate just jump table in stmt.c the proper fix is to 
remove
all usages of 'case_node' in the file because simple iteration of labels will 
work fine.
Let me do it incrementally to minimize fall out :)

Martin

> 
> Thanks,
> Richard.
> 
>> Martin

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-18 Thread Richard Biener 
On Tue, Aug 15, 2017 at 2:37 PM, Martin Liška  wrote:
> On 08/14/2017 10:32 AM, Richard Biener wrote:
>> Hmm, but the existing "lowering" part is called from the
>> switch-conversion pass.  So
>> I'm not sure a new file is good.
>
> Good, I'm not against having that in a single file. So new version of the 
> patch
> does that.
>
> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>
> Ready to be installed?

Hmm, I see you duplicate add_case_node for example.  Is that just temporary?
If not can you please factor out the data structure and common code?
(case.[Ch]?)

Thanks,
Richard.

> Martin

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-15 Thread Martin Liška 
On 08/14/2017 10:32 AM, Richard Biener wrote:
> Hmm, but the existing "lowering" part is called from the
> switch-conversion pass.  So
> I'm not sure a new file is good.

Good, I'm not against having that in a single file. So new version of the patch
does that.

Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.

Ready to be installed?
Martin
>From 27f5901b340e73900ef992470aa52b51ccfb86b9 Mon Sep 17 00:00:00 2001
From: marxin 
Date: Mon, 31 Jul 2017 14:01:53 +0200
Subject: [PATCH] Make expansion of balanced binary trees of switches on tree
 level.

gcc/ChangeLog:

2017-07-31  Martin Liska  

	* passes.def: Include pass_lower_switch.
	* stmt.c (dump_case_nodes): Remove and move to
	tree-switch-conversion.
	(case_values_threshold): Likewise.
	(expand_switch_as_decision_tree_p): Likewise.
	(emit_case_decision_tree): Likewise.
	(expand_case): Likewise.
	(balance_case_nodes): Likewise.
	(node_has_low_bound): Likewise.
	(node_has_high_bound): Likewise.
	(node_is_bounded): Likewise.
	(emit_case_nodes): Likewise.
	* timevar.def: Add TV_TREE_SWITCH_LOWERING.
	* tree-pass.h: Add make_pass_lower_switch.

gcc/testsuite/ChangeLog:

2017-07-31  Martin Liska  

	* gcc.dg/tree-prof/update-loopch.c: Scan patterns in
	switchlower.
	* gcc.dg/tree-ssa/vrp104.c: Likewise.
---
 gcc/passes.def |1 +
 gcc/stmt.c |  861 -
 gcc/testsuite/gcc.dg/tree-prof/update-loopch.c |   10 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp104.c |2 +-
 gcc/timevar.def|1 +
 gcc/tree-pass.h|1 +
 gcc/tree-switch-conversion.c   | 1178 
 7 files changed, 1187 insertions(+), 867 deletions(-)

diff --git a/gcc/passes.def b/gcc/passes.def
index 316e19d12e3..81b6e62f602 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -394,6 +394,7 @@ along with GCC; see the file COPYING3.  If not see
   NEXT_PASS (pass_lower_vaarg);
   NEXT_PASS (pass_lower_vector);
   NEXT_PASS (pass_lower_complex_O0);
+  NEXT_PASS (pass_lower_switch);
   NEXT_PASS (pass_sancov_O0);
   NEXT_PASS (pass_asan_O0);
   NEXT_PASS (pass_tsan_O0);
diff --git a/gcc/stmt.c b/gcc/stmt.c
index 05e24f00707..4c10b1f37d7 100644
--- a/gcc/stmt.c
+++ b/gcc/stmt.c
@@ -104,12 +104,6 @@ extern basic_block label_to_block_fn (struct function *, tree);
 
 static bool check_unique_operand_names (tree, tree, tree);
 static char *resolve_operand_name_1 (char *, tree, tree, tree);
-static void balance_case_nodes (case_node_ptr *, case_node_ptr);
-static int node_has_low_bound (case_node_ptr, tree);
-static int node_has_high_bound (case_node_ptr, tree);
-static int node_is_bounded (case_node_ptr, tree);
-static void emit_case_nodes (rtx, case_node_ptr, rtx_code_label *,
-			 profile_probability, tree);
 
 /* Return the rtx-label that corresponds to a LABEL_DECL,
creating it if necessary.  */
@@ -742,164 +736,6 @@ add_case_node (struct case_node *head, tree low, tree high,
   return r;
 }
 
-/* Dump ROOT, a list or tree of case nodes, to file.  */
-
-static void
-dump_case_nodes (FILE *f, struct case_node *root,
-		 int indent_step, int indent_level)
-{
-  if (root == 0)
-return;
-  indent_level++;
-
-  dump_case_nodes (f, root->left, indent_step, indent_level);
-
-  fputs (";; ", f);
-  fprintf (f, "%*s", indent_step * indent_level, "");
-  print_dec (root->low, f, TYPE_SIGN (TREE_TYPE (root->low)));
-  if (!tree_int_cst_equal (root->low, root->high))
-{
-  fprintf (f, " ... ");
-  print_dec (root->high, f, TYPE_SIGN (TREE_TYPE (root->high)));
-}
-  fputs ("\n", f);
-
-  dump_case_nodes (f, root->right, indent_step, indent_level);
-}
-
-/* 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 unsigned int
-case_values_threshold (void)
-{
-  unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
-
-  if (threshold == 0)
-threshold = targetm.case_values_threshold ();
-
-  return threshold;
-}
-
-/* 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.  */
-
-static bool
-expand_switch_as_decision_tree_p (tree range,
-  unsigned int uniq ATTRIBUTE_UNUSED,
-  unsigned int count)
-{
-  int max_ratio;
-
-  /* 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
-
-  /* If the switch is relatively small such that the

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-14 Thread Richard Biener 
On Thu, Aug 10, 2017 at 9:50 AM, Martin Liška  wrote:
> On 08/02/2017 01:51 PM, Richard Biener wrote:
>> On Wed, Aug 2, 2017 at 1:20 PM, Martin Liška  wrote:
>>> Hello.
>>>
>>> After some discussions with Honza, I've decided to convert current code in 
>>> stmt.c that
>>> is responsible for switch expansion. More precisely, I would like to 
>>> convert the code
>>> to expand gswitch statements on tree level. Currently the newly created 
>>> pass is executed
>>> at the end of tree optimizations.
>>>
>>> My plan for future is to inspire in [1] and come up with some more 
>>> sophisticated switch
>>> expansions. For that I've been working on a paper where I'll summarize 
>>> statistics based
>>> on what I've collected in openSUSE distribution with specially instrumented 
>>> GCC. If I'll be
>>> happy I can also fit in to schedule of this year's Cauldron with a talk.
>>>
>>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>>>
>>> Thoughts?
>>
>> First of all thanks.
>>
>> I think part of switch expansion moved to switch-conversion some time ago
>> (emit_case_bit_tests).  So maybe the full lowering should be in at least
>> the same source file and it should maybe applied earlier for a subset of
>> cases (very low number of cases for example).
>
> Hello.
>
> Agree! Eventually we should merge both files into a single one. I would 
> prefer to start
> with new generic name of file (gimple-switch-low.c), which will eventually 
> eat content
> of tree-switch-conversion.c. Is it acceptable approach?

Hmm, but the existing "lowering" part is called from the
switch-conversion pass.  So
I'm not sure a new file is good.

> As Jeff already accepted the patch, I will install it as soon as an agreement 
> in the question
> will be done.
>
> Martin
>
>>
>> Did you base the code on the RTL expansion code or did you re-write it from
>> scratch?
>>
>> No further comments sofar.
>>
>> Richard.
>>
>>> Martin
>>>
>>> [1] https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf
>>>
>>> gcc/ChangeLog:
>>>
>>> 2017-07-31  Martin Liska  
>>>
>>> * Makefile.in: Add gimple-switch-low.o.
>>> * passes.def: Include pass_lower_switch.
>>> * stmt.c (dump_case_nodes): Remove and move to
>>> gimple-switch-low.c.
>>> (case_values_threshold): Likewise.
>>> (expand_switch_as_decision_tree_p): Likewise.
>>> (emit_case_decision_tree): Likewise.
>>> (expand_case): Likewise.
>>> (balance_case_nodes): Likewise.
>>> (node_has_low_bound): Likewise.
>>> (node_has_high_bound): Likewise.
>>> (node_is_bounded): Likewise.
>>> (emit_case_nodes): Likewise.
>>> * timevar.def: Add TV_TREE_SWITCH_LOWERING.
>>> * tree-pass.h: Add make_pass_lower_switch.
>>> * gimple-switch-low.c: New file.
>>>
>>> gcc/testsuite/ChangeLog:
>>>
>>> 2017-07-31  Martin Liska  
>>>
>>> * gcc.dg/tree-prof/update-loopch.c: Scan patterns in
>>> switchlower.
>>> * gcc.dg/tree-ssa/vrp104.c: Likewise.
>>> ---
>>>  gcc/Makefile.in|1 +
>>>  gcc/gimple-switch-low.c| 1226 
>>> 
>>>  gcc/passes.def |1 +
>>>  gcc/stmt.c |  861 -
>>>  gcc/testsuite/gcc.dg/tree-prof/update-loopch.c |   10 +-
>>>  gcc/testsuite/gcc.dg/tree-ssa/vrp104.c |2 +-
>>>  gcc/timevar.def|1 +
>>>  gcc/tree-pass.h|1 +
>>>  8 files changed, 1236 insertions(+), 867 deletions(-)
>>>  create mode 100644 gcc/gimple-switch-low.c
>>>
>>>
>

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-10 Thread Martin Liška 
On 08/02/2017 01:51 PM, Richard Biener wrote:
> On Wed, Aug 2, 2017 at 1:20 PM, Martin Liška  wrote:
>> Hello.
>>
>> After some discussions with Honza, I've decided to convert current code in 
>> stmt.c that
>> is responsible for switch expansion. More precisely, I would like to convert 
>> the code
>> to expand gswitch statements on tree level. Currently the newly created pass 
>> is executed
>> at the end of tree optimizations.
>>
>> My plan for future is to inspire in [1] and come up with some more 
>> sophisticated switch
>> expansions. For that I've been working on a paper where I'll summarize 
>> statistics based
>> on what I've collected in openSUSE distribution with specially instrumented 
>> GCC. If I'll be
>> happy I can also fit in to schedule of this year's Cauldron with a talk.
>>
>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>>
>> Thoughts?
> 
> First of all thanks.
> 
> I think part of switch expansion moved to switch-conversion some time ago
> (emit_case_bit_tests).  So maybe the full lowering should be in at least
> the same source file and it should maybe applied earlier for a subset of
> cases (very low number of cases for example).

Hello.

Agree! Eventually we should merge both files into a single one. I would prefer 
to start
with new generic name of file (gimple-switch-low.c), which will eventually eat 
content
of tree-switch-conversion.c. Is it acceptable approach?

As Jeff already accepted the patch, I will install it as soon as an agreement 
in the question
will be done.

Martin

> 
> Did you base the code on the RTL expansion code or did you re-write it from
> scratch?
> 
> No further comments sofar.
> 
> Richard.
> 
>> Martin
>>
>> [1] https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf
>>
>> gcc/ChangeLog:
>>
>> 2017-07-31  Martin Liska  
>>
>> * Makefile.in: Add gimple-switch-low.o.
>> * passes.def: Include pass_lower_switch.
>> * stmt.c (dump_case_nodes): Remove and move to
>> gimple-switch-low.c.
>> (case_values_threshold): Likewise.
>> (expand_switch_as_decision_tree_p): Likewise.
>> (emit_case_decision_tree): Likewise.
>> (expand_case): Likewise.
>> (balance_case_nodes): Likewise.
>> (node_has_low_bound): Likewise.
>> (node_has_high_bound): Likewise.
>> (node_is_bounded): Likewise.
>> (emit_case_nodes): Likewise.
>> * timevar.def: Add TV_TREE_SWITCH_LOWERING.
>> * tree-pass.h: Add make_pass_lower_switch.
>> * gimple-switch-low.c: New file.
>>
>> gcc/testsuite/ChangeLog:
>>
>> 2017-07-31  Martin Liska  
>>
>> * gcc.dg/tree-prof/update-loopch.c: Scan patterns in
>> switchlower.
>> * gcc.dg/tree-ssa/vrp104.c: Likewise.
>> ---
>>  gcc/Makefile.in|1 +
>>  gcc/gimple-switch-low.c| 1226 
>> 
>>  gcc/passes.def |1 +
>>  gcc/stmt.c |  861 -
>>  gcc/testsuite/gcc.dg/tree-prof/update-loopch.c |   10 +-
>>  gcc/testsuite/gcc.dg/tree-ssa/vrp104.c |2 +-
>>  gcc/timevar.def|1 +
>>  gcc/tree-pass.h|1 +
>>  8 files changed, 1236 insertions(+), 867 deletions(-)
>>  create mode 100644 gcc/gimple-switch-low.c
>>
>>

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-04 Thread Martin Liška 
On 08/03/2017 03:27 PM, Steven Bosscher wrote:
> On Thu, Aug 3, 2017 at 2:56 PM, Richard Biener wrote:
>> I think the main reason for not doing it early is the benefit is small
>> (unless it is GIMPLE optimizations triggering)
> 
> Agree.
> 
>> and we can't get rid of
>> switches completely because we eventually have to support casei RTL 
>> expansion.
>> (and no, computed goto with an array of label addresses at GIMPLE is really
>> too ugly ;))
> 
> What I would have done, is lower all gswitch statements that are to be
> lowered to something other than a tablejump.
> So by the time you get to RTL expansion, all remaining gswitch
> statements would be tablejump or casesi.

That exactly my plan :)

> 
> Ciao!
> Steven
>

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-04 Thread Martin Liška 
On 08/03/2017 02:52 PM, Steven Bosscher wrote:
> On Wed, Aug 2, 2017 at 1:20 PM, Martin Liška wrote:
>> Hello.
>>
>> After some discussions with Honza, I've decided to convert current code in 
>> stmt.c that
>> is responsible for switch expansion. More precisely, I would like to convert 
>> the code
>> to expand gswitch statements on tree level. Currently the newly created pass 
>> is executed
>> at the end of tree optimizations.
> 
> Hah, something I promissed myself (and others) to do years ago! Thanks
> thanks thanks! :-)

Hi.

Yes, it's very interesting topic to work on. Well, if you have sparse time, 
help will be
highly appreciated ;)

> 
> The end of the gimple optimizations is seems late for the lowering.
> Before there were gimple optimizations, switch lowering was part of
> the first compiler pass (to generate RTL from the front end) *before*
> all code transformation passes ("optimizations" ;-). Because the
> lowering of switch statements was rewritten as a gimple lowering pass,
> it now runs *after* optimizations. But to be honest, I can't think of
> any optimization opportunities exposed by lowering earlier than at the
> end of gimple optimizations. Years ago there was some RTL jump
> threading still done after lowering of small switch statements, but I
> can't find the related PRs anymore.
> 
> 
>> My plan for future is to inspire in [1] and come up with some more 
>> sophisticated switch
>> expansions. For that I've been working on a paper where I'll summarize 
>> statistics based
>> on what I've collected in openSUSE distribution with specially instrumented 
>> GCC. If I'll be
>> happy I can also fit in to schedule of this year's Cauldron with a talk.
> 
> Sayle's paper is a good starting point. Also interesting:

Yes, I read that.

> 
> http://llvm.org/devmtg/2017-02-04/Efficient-clustering-of-case-statements-for-indirect-branch-prediction.pdf
> About adjusting the size of jump tables to the capabilities of the CPU
> branch predictor. Mixed results but something to consider.

I've also considered to play with jump tables and their sizes. Thanks for the 
article.

> 
> Kannan & Proebsting, "CORRECTION TO ‘PRODUCING GOOD CODE FOR THE CASE
> STATEMENT’"
> About finding "clusers" of given density within the target values of
> the switch statement. The clustering algorithm as presented is N^2 in
> the number of case labels, but the idea is interesting and a
> simplified, cheaper approach may be possible. This is already used in
> LLVM, it seems.

I'll take a look at LLVM as I'm unable to find PDF of the Kannan's article :/

> 
> The real challenge will be to figure out how to pick from all these
> different approaches the right ones to lower a single switch
> statement.

Exactly, that's why I started with porting of the balanced decision tree to 
tree level
and I've been collecting statistics. That should help us what would be 
beneficial and
what's more nice-to-have stuff.

Martin

> 
> Ciao!
> Steven
>

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-03 Thread Jeff Law 
On 08/03/2017 03:02 AM, Jan Hubicka wrote:
>> On 08/02/2017 01:51 PM, Richard Biener wrote:
>>> On Wed, Aug 2, 2017 at 1:20 PM, Martin Liška  wrote:
 Hello.

 After some discussions with Honza, I've decided to convert current code in 
 stmt.c that
 is responsible for switch expansion. More precisely, I would like to 
 convert the code
 to expand gswitch statements on tree level. Currently the newly created 
 pass is executed
 at the end of tree optimizations.

 My plan for future is to inspire in [1] and come up with some more 
 sophisticated switch
 expansions. For that I've been working on a paper where I'll summarize 
 statistics based
 on what I've collected in openSUSE distribution with specially 
 instrumented GCC. If I'll be
 happy I can also fit in to schedule of this year's Cauldron with a talk.

 Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.

 Thoughts?
>>>
>>> First of all thanks.
>>>
>>> I think part of switch expansion moved to switch-conversion some time ago
>>> (emit_case_bit_tests).  So maybe the full lowering should be in at least
>>> the same source file and it should maybe applied earlier for a subset of
>>> cases (very low number of cases for example).
>>
>> Yep, good idea. I'll take a look.
>>
>>>
>>> Did you base the code on the RTL expansion code or did you re-write it from
>>> scratch?
>>
>> It's based, I've just changed the function that create CFG.
> 
> I have talked Martin to do this in first step. Switch expansion is infinitely
> difficult problem and I think changing representation first and keeping the
> basic algorithm is easiest way to get something done.  Algorithm will be
> improved next as far as I know :)
I can support that approach :-)


jeff

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-03 Thread Steven Bosscher 
On Thu, Aug 3, 2017 at 2:56 PM, Richard Biener wrote:
> I think the main reason for not doing it early is the benefit is small
> (unless it is GIMPLE optimizations triggering)

Agree.

> and we can't get rid of
> switches completely because we eventually have to support casei RTL expansion.
> (and no, computed goto with an array of label addresses at GIMPLE is really
> too ugly ;))

What I would have done, is lower all gswitch statements that are to be
lowered to something other than a tablejump.
So by the time you get to RTL expansion, all remaining gswitch
statements would be tablejump or casesi.

Ciao!
Steven

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-03 Thread Jan Hubicka 
> On Thu, Aug 3, 2017 at 2:52 PM, Steven Bosscher  wrote:
> > On Wed, Aug 2, 2017 at 1:20 PM, Martin Liška wrote:
> >> Hello.
> >>
> >> After some discussions with Honza, I've decided to convert current code in 
> >> stmt.c that
> >> is responsible for switch expansion. More precisely, I would like to 
> >> convert the code
> >> to expand gswitch statements on tree level. Currently the newly created 
> >> pass is executed
> >> at the end of tree optimizations.
> >
> > Hah, something I promissed myself (and others) to do years ago! Thanks
> > thanks thanks! :-)
> >
> > The end of the gimple optimizations is seems late for the lowering.
> > Before there were gimple optimizations, switch lowering was part of
> > the first compiler pass (to generate RTL from the front end) *before*
> > all code transformation passes ("optimizations" ;-). Because the
> > lowering of switch statements was rewritten as a gimple lowering pass,
> > it now runs *after* optimizations. But to be honest, I can't think of
> > any optimization opportunities exposed by lowering earlier than at the
> > end of gimple optimizations. Years ago there was some RTL jump
> > threading still done after lowering of small switch statements, but I
> > can't find the related PRs anymore.
> 
> I think the main reason for not doing it early is the benefit is small
> (unless it is GIMPLE optimizations triggering) and we can't get rid of
> switches completely because we eventually have to support casei RTL expansion.
> (and no, computed goto with an array of label addresses at GIMPLE is really
> too ugly ;))

Also later in optimization you have better idea of value ranges and you can
shape the decision tree better for given context. In theory at least ;)
One thing that would benefit from earlier expansion is code size/runtime 
estimation
for inlining. But perhaps we could just run the algorithm to see how hard the
switch is when we decide on its size (what is there right now is bit lame)

Honza
> 
> Richard.

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-03 Thread Richard Biener 
On Thu, Aug 3, 2017 at 2:52 PM, Steven Bosscher  wrote:
> On Wed, Aug 2, 2017 at 1:20 PM, Martin Liška wrote:
>> Hello.
>>
>> After some discussions with Honza, I've decided to convert current code in 
>> stmt.c that
>> is responsible for switch expansion. More precisely, I would like to convert 
>> the code
>> to expand gswitch statements on tree level. Currently the newly created pass 
>> is executed
>> at the end of tree optimizations.
>
> Hah, something I promissed myself (and others) to do years ago! Thanks
> thanks thanks! :-)
>
> The end of the gimple optimizations is seems late for the lowering.
> Before there were gimple optimizations, switch lowering was part of
> the first compiler pass (to generate RTL from the front end) *before*
> all code transformation passes ("optimizations" ;-). Because the
> lowering of switch statements was rewritten as a gimple lowering pass,
> it now runs *after* optimizations. But to be honest, I can't think of
> any optimization opportunities exposed by lowering earlier than at the
> end of gimple optimizations. Years ago there was some RTL jump
> threading still done after lowering of small switch statements, but I
> can't find the related PRs anymore.

I think the main reason for not doing it early is the benefit is small
(unless it is GIMPLE optimizations triggering) and we can't get rid of
switches completely because we eventually have to support casei RTL expansion.
(and no, computed goto with an array of label addresses at GIMPLE is really
too ugly ;))

Richard.

>
>> My plan for future is to inspire in [1] and come up with some more 
>> sophisticated switch
>> expansions. For that I've been working on a paper where I'll summarize 
>> statistics based
>> on what I've collected in openSUSE distribution with specially instrumented 
>> GCC. If I'll be
>> happy I can also fit in to schedule of this year's Cauldron with a talk.
>
> Sayle's paper is a good starting point. Also interesting:
>
> http://llvm.org/devmtg/2017-02-04/Efficient-clustering-of-case-statements-for-indirect-branch-prediction.pdf
> About adjusting the size of jump tables to the capabilities of the CPU
> branch predictor. Mixed results but something to consider.
>
> Kannan & Proebsting, "CORRECTION TO ‘PRODUCING GOOD CODE FOR THE CASE
> STATEMENT’"
> About finding "clusers" of given density within the target values of
> the switch statement. The clustering algorithm as presented is N^2 in
> the number of case labels, but the idea is interesting and a
> simplified, cheaper approach may be possible. This is already used in
> LLVM, it seems.
>
> The real challenge will be to figure out how to pick from all these
> different approaches the right ones to lower a single switch
> statement.
>
> Ciao!
> Steven

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-03 Thread Steven Bosscher 
On Wed, Aug 2, 2017 at 1:20 PM, Martin Liška wrote:
> Hello.
>
> After some discussions with Honza, I've decided to convert current code in 
> stmt.c that
> is responsible for switch expansion. More precisely, I would like to convert 
> the code
> to expand gswitch statements on tree level. Currently the newly created pass 
> is executed
> at the end of tree optimizations.

Hah, something I promissed myself (and others) to do years ago! Thanks
thanks thanks! :-)

The end of the gimple optimizations is seems late for the lowering.
Before there were gimple optimizations, switch lowering was part of
the first compiler pass (to generate RTL from the front end) *before*
all code transformation passes ("optimizations" ;-). Because the
lowering of switch statements was rewritten as a gimple lowering pass,
it now runs *after* optimizations. But to be honest, I can't think of
any optimization opportunities exposed by lowering earlier than at the
end of gimple optimizations. Years ago there was some RTL jump
threading still done after lowering of small switch statements, but I
can't find the related PRs anymore.


> My plan for future is to inspire in [1] and come up with some more 
> sophisticated switch
> expansions. For that I've been working on a paper where I'll summarize 
> statistics based
> on what I've collected in openSUSE distribution with specially instrumented 
> GCC. If I'll be
> happy I can also fit in to schedule of this year's Cauldron with a talk.

Sayle's paper is a good starting point. Also interesting:

http://llvm.org/devmtg/2017-02-04/Efficient-clustering-of-case-statements-for-indirect-branch-prediction.pdf
About adjusting the size of jump tables to the capabilities of the CPU
branch predictor. Mixed results but something to consider.

Kannan & Proebsting, "CORRECTION TO ‘PRODUCING GOOD CODE FOR THE CASE
STATEMENT’"
About finding "clusers" of given density within the target values of
the switch statement. The clustering algorithm as presented is N^2 in
the number of case labels, but the idea is interesting and a
simplified, cheaper approach may be possible. This is already used in
LLVM, it seems.

The real challenge will be to figure out how to pick from all these
different approaches the right ones to lower a single switch
statement.

Ciao!
Steven

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-03 Thread Steven Bosscher 
On Wed, Aug 2, 2017 at 1:51 PM, Richard Biener wrote:
> On Wed, Aug 2, 2017 at 1:20 PM, Martin Liška wrote:
>> Hello.
>>
>> After some discussions with Honza, I've decided to convert current code in 
>> stmt.c that
>> is responsible for switch expansion. More precisely, I would like to convert 
>> the code
>> to expand gswitch statements on tree level. Currently the newly created pass 
>> is executed
>> at the end of tree optimizations.

Hah, something I promissed myself (and others) to do years ago! Thanks
thanks thanks! :-)


>> My plan for future is to inspire in [1] and come up with some more 
>> sophisticated switch
>> expansions. For that I've been working on a paper where I'll summarize 
>> statistics based
>> on what I've collected in openSUSE distribution with specially instrumented 
>> GCC. If I'll be
>> happy I can also fit in to schedule of this year's Cauldron with a talk.

Sayle's paper is a good starting point. Also interesting:



>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>>
>> Thoughts?
>
> First of all thanks.
>
> I think part of switch expansion moved to switch-conversion some time ago
> (emit_case_bit_tests).  So maybe the full lowering should be in at least
> the same source file and it should maybe applied earlier for a subset of
> cases (very low number of cases for example).
>
> Did you base the code on the RTL expansion code or did you re-write it from
> scratch?
>
> No further comments sofar.
>
> Richard.
>
>> Martin
>>
>> [1] https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf
>>
>> gcc/ChangeLog:
>>
>> 2017-07-31  Martin Liska  
>>
>> * Makefile.in: Add gimple-switch-low.o.
>> * passes.def: Include pass_lower_switch.
>> * stmt.c (dump_case_nodes): Remove and move to
>> gimple-switch-low.c.
>> (case_values_threshold): Likewise.
>> (expand_switch_as_decision_tree_p): Likewise.
>> (emit_case_decision_tree): Likewise.
>> (expand_case): Likewise.
>> (balance_case_nodes): Likewise.
>> (node_has_low_bound): Likewise.
>> (node_has_high_bound): Likewise.
>> (node_is_bounded): Likewise.
>> (emit_case_nodes): Likewise.
>> * timevar.def: Add TV_TREE_SWITCH_LOWERING.
>> * tree-pass.h: Add make_pass_lower_switch.
>> * gimple-switch-low.c: New file.
>>
>> gcc/testsuite/ChangeLog:
>>
>> 2017-07-31  Martin Liska  
>>
>> * gcc.dg/tree-prof/update-loopch.c: Scan patterns in
>> switchlower.
>> * gcc.dg/tree-ssa/vrp104.c: Likewise.
>> ---
>>  gcc/Makefile.in|1 +
>>  gcc/gimple-switch-low.c| 1226 
>> 
>>  gcc/passes.def |1 +
>>  gcc/stmt.c |  861 -
>>  gcc/testsuite/gcc.dg/tree-prof/update-loopch.c |   10 +-
>>  gcc/testsuite/gcc.dg/tree-ssa/vrp104.c |2 +-
>>  gcc/timevar.def|1 +
>>  gcc/tree-pass.h|1 +
>>  8 files changed, 1236 insertions(+), 867 deletions(-)
>>  create mode 100644 gcc/gimple-switch-low.c
>>
>>

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-03 Thread Jan Hubicka 
> On 08/02/2017 01:51 PM, Richard Biener wrote:
> > On Wed, Aug 2, 2017 at 1:20 PM, Martin Liška  wrote:
> >> Hello.
> >>
> >> After some discussions with Honza, I've decided to convert current code in 
> >> stmt.c that
> >> is responsible for switch expansion. More precisely, I would like to 
> >> convert the code
> >> to expand gswitch statements on tree level. Currently the newly created 
> >> pass is executed
> >> at the end of tree optimizations.
> >>
> >> My plan for future is to inspire in [1] and come up with some more 
> >> sophisticated switch
> >> expansions. For that I've been working on a paper where I'll summarize 
> >> statistics based
> >> on what I've collected in openSUSE distribution with specially 
> >> instrumented GCC. If I'll be
> >> happy I can also fit in to schedule of this year's Cauldron with a talk.
> >>
> >> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
> >>
> >> Thoughts?
> > 
> > First of all thanks.
> > 
> > I think part of switch expansion moved to switch-conversion some time ago
> > (emit_case_bit_tests).  So maybe the full lowering should be in at least
> > the same source file and it should maybe applied earlier for a subset of
> > cases (very low number of cases for example).
> 
> Yep, good idea. I'll take a look.
> 
> > 
> > Did you base the code on the RTL expansion code or did you re-write it from
> > scratch?
> 
> It's based, I've just changed the function that create CFG.

I have talked Martin to do this in first step. Switch expansion is infinitely
difficult problem and I think changing representation first and keeping the
basic algorithm is easiest way to get something done.  Algorithm will be
improved next as far as I know :)

Honza
> 
> Martin

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-02 Thread David Malcolm 
On Wed, 2017-08-02 at 13:20 +0200, Martin Liška wrote:
> Hello.
> 
> After some discussions with Honza, I've decided to convert current
> code in stmt.c that
> is responsible for switch expansion. More precisely, I would like to
> convert the code
> to expand gswitch statements on tree level. Currently the newly
> created pass is executed
> at the end of tree optimizations.
> 
> My plan for future is to inspire in [1] and come up with some more
> sophisticated switch
> expansions. For that I've been working on a paper where I'll
> summarize statistics based
> on what I've collected in openSUSE distribution with specially
> instrumented GCC. If I'll be
> happy I can also fit in to schedule of this year's Cauldron with a
> talk.
> 
> Patch can bootstrap on ppc64le-redhat-linux and survives regression
> tests.
> 
> Thoughts?
> Martin
> 
> [1] https://www.nextmovesoftware.com/technology/SwitchOptimization.pd
> f
> 
> gcc/ChangeLog:
> 
> 2017-07-31  Martin Liska  
> 
[...]

>   * gimple-switch-low.c: New file.

Shouldn't new files have a .cc suffix these days?

[...]

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-02 Thread Martin Liška 
On 08/02/2017 01:51 PM, Richard Biener wrote:
> On Wed, Aug 2, 2017 at 1:20 PM, Martin Liška  wrote:
>> Hello.
>>
>> After some discussions with Honza, I've decided to convert current code in 
>> stmt.c that
>> is responsible for switch expansion. More precisely, I would like to convert 
>> the code
>> to expand gswitch statements on tree level. Currently the newly created pass 
>> is executed
>> at the end of tree optimizations.
>>
>> My plan for future is to inspire in [1] and come up with some more 
>> sophisticated switch
>> expansions. For that I've been working on a paper where I'll summarize 
>> statistics based
>> on what I've collected in openSUSE distribution with specially instrumented 
>> GCC. If I'll be
>> happy I can also fit in to schedule of this year's Cauldron with a talk.
>>
>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>>
>> Thoughts?
> 
> First of all thanks.
> 
> I think part of switch expansion moved to switch-conversion some time ago
> (emit_case_bit_tests).  So maybe the full lowering should be in at least
> the same source file and it should maybe applied earlier for a subset of
> cases (very low number of cases for example).

Yep, good idea. I'll take a look.

> 
> Did you base the code on the RTL expansion code or did you re-write it from
> scratch?

It's based, I've just changed the function that create CFG.

Martin

> 
> No further comments sofar.
> 
> Richard.
> 
>> Martin
>>
>> [1] https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf
>>
>> gcc/ChangeLog:
>>
>> 2017-07-31  Martin Liska  
>>
>> * Makefile.in: Add gimple-switch-low.o.
>> * passes.def: Include pass_lower_switch.
>> * stmt.c (dump_case_nodes): Remove and move to
>> gimple-switch-low.c.
>> (case_values_threshold): Likewise.
>> (expand_switch_as_decision_tree_p): Likewise.
>> (emit_case_decision_tree): Likewise.
>> (expand_case): Likewise.
>> (balance_case_nodes): Likewise.
>> (node_has_low_bound): Likewise.
>> (node_has_high_bound): Likewise.
>> (node_is_bounded): Likewise.
>> (emit_case_nodes): Likewise.
>> * timevar.def: Add TV_TREE_SWITCH_LOWERING.
>> * tree-pass.h: Add make_pass_lower_switch.
>> * gimple-switch-low.c: New file.
>>
>> gcc/testsuite/ChangeLog:
>>
>> 2017-07-31  Martin Liska  
>>
>> * gcc.dg/tree-prof/update-loopch.c: Scan patterns in
>> switchlower.
>> * gcc.dg/tree-ssa/vrp104.c: Likewise.
>> ---
>>  gcc/Makefile.in|1 +
>>  gcc/gimple-switch-low.c| 1226 
>> 
>>  gcc/passes.def |1 +
>>  gcc/stmt.c |  861 -
>>  gcc/testsuite/gcc.dg/tree-prof/update-loopch.c |   10 +-
>>  gcc/testsuite/gcc.dg/tree-ssa/vrp104.c |2 +-
>>  gcc/timevar.def|1 +
>>  gcc/tree-pass.h|1 +
>>  8 files changed, 1236 insertions(+), 867 deletions(-)
>>  create mode 100644 gcc/gimple-switch-low.c
>>
>>

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-02 Thread Richard Biener 
On Wed, Aug 2, 2017 at 1:20 PM, Martin Liška  wrote:
> Hello.
>
> After some discussions with Honza, I've decided to convert current code in 
> stmt.c that
> is responsible for switch expansion. More precisely, I would like to convert 
> the code
> to expand gswitch statements on tree level. Currently the newly created pass 
> is executed
> at the end of tree optimizations.
>
> My plan for future is to inspire in [1] and come up with some more 
> sophisticated switch
> expansions. For that I've been working on a paper where I'll summarize 
> statistics based
> on what I've collected in openSUSE distribution with specially instrumented 
> GCC. If I'll be
> happy I can also fit in to schedule of this year's Cauldron with a talk.
>
> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>
> Thoughts?

First of all thanks.

I think part of switch expansion moved to switch-conversion some time ago
(emit_case_bit_tests).  So maybe the full lowering should be in at least
the same source file and it should maybe applied earlier for a subset of
cases (very low number of cases for example).

Did you base the code on the RTL expansion code or did you re-write it from
scratch?

No further comments sofar.

Richard.

> Martin
>
> [1] https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf
>
> gcc/ChangeLog:
>
> 2017-07-31  Martin Liska  
>
> * Makefile.in: Add gimple-switch-low.o.
> * passes.def: Include pass_lower_switch.
> * stmt.c (dump_case_nodes): Remove and move to
> gimple-switch-low.c.
> (case_values_threshold): Likewise.
> (expand_switch_as_decision_tree_p): Likewise.
> (emit_case_decision_tree): Likewise.
> (expand_case): Likewise.
> (balance_case_nodes): Likewise.
> (node_has_low_bound): Likewise.
> (node_has_high_bound): Likewise.
> (node_is_bounded): Likewise.
> (emit_case_nodes): Likewise.
> * timevar.def: Add TV_TREE_SWITCH_LOWERING.
> * tree-pass.h: Add make_pass_lower_switch.
> * gimple-switch-low.c: New file.
>
> gcc/testsuite/ChangeLog:
>
> 2017-07-31  Martin Liska  
>
> * gcc.dg/tree-prof/update-loopch.c: Scan patterns in
> switchlower.
> * gcc.dg/tree-ssa/vrp104.c: Likewise.
> ---
>  gcc/Makefile.in|1 +
>  gcc/gimple-switch-low.c| 1226 
> 
>  gcc/passes.def |1 +
>  gcc/stmt.c |  861 -
>  gcc/testsuite/gcc.dg/tree-prof/update-loopch.c |   10 +-
>  gcc/testsuite/gcc.dg/tree-ssa/vrp104.c |2 +-
>  gcc/timevar.def|1 +
>  gcc/tree-pass.h|1 +
>  8 files changed, 1236 insertions(+), 867 deletions(-)
>  create mode 100644 gcc/gimple-switch-low.c
>
>

[PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

2017-08-02 Thread Martin Liška 
Hello.

After some discussions with Honza, I've decided to convert current code in 
stmt.c that
is responsible for switch expansion. More precisely, I would like to convert 
the code
to expand gswitch statements on tree level. Currently the newly created pass is 
executed
at the end of tree optimizations.

My plan for future is to inspire in [1] and come up with some more 
sophisticated switch
expansions. For that I've been working on a paper where I'll summarize 
statistics based
on what I've collected in openSUSE distribution with specially instrumented 
GCC. If I'll be
happy I can also fit in to schedule of this year's Cauldron with a talk.

Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.

Thoughts?
Martin

[1] https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf

gcc/ChangeLog:

2017-07-31  Martin Liska  

* Makefile.in: Add gimple-switch-low.o.
* passes.def: Include pass_lower_switch.
* stmt.c (dump_case_nodes): Remove and move to
gimple-switch-low.c.
(case_values_threshold): Likewise.
(expand_switch_as_decision_tree_p): Likewise.
(emit_case_decision_tree): Likewise.
(expand_case): Likewise.
(balance_case_nodes): Likewise.
(node_has_low_bound): Likewise.
(node_has_high_bound): Likewise.
(node_is_bounded): Likewise.
(emit_case_nodes): Likewise.
* timevar.def: Add TV_TREE_SWITCH_LOWERING.
* tree-pass.h: Add make_pass_lower_switch.
* gimple-switch-low.c: New file.

gcc/testsuite/ChangeLog:

2017-07-31  Martin Liska  

* gcc.dg/tree-prof/update-loopch.c: Scan patterns in
switchlower.
* gcc.dg/tree-ssa/vrp104.c: Likewise.
---
 gcc/Makefile.in|1 +
 gcc/gimple-switch-low.c| 1226 
 gcc/passes.def |1 +
 gcc/stmt.c |  861 -
 gcc/testsuite/gcc.dg/tree-prof/update-loopch.c |   10 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp104.c |2 +-
 gcc/timevar.def|1 +
 gcc/tree-pass.h|1 +
 8 files changed, 1236 insertions(+), 867 deletions(-)
 create mode 100644 gcc/gimple-switch-low.c


diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index efca9169671..4a84f36c6b9 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1309,6 +1309,7 @@ OBJS = \
 	gimple-ssa-warn-alloca.o \
 	gimple-streamer-in.o \
 	gimple-streamer-out.o \
+	gimple-switch-low.o \
 	gimple-walk.o \
 	gimplify.o \
 	gimplify-me.o \
diff --git a/gcc/gimple-switch-low.c b/gcc/gimple-switch-low.c
new file mode 100644
index 000..a37c49b8494
--- /dev/null
+++ b/gcc/gimple-switch-low.c
@@ -0,0 +1,1226 @@
+/* Lower GIMPLE_SWITCH expressions to something more efficient than
+   a jump table.
+   Copyright (C) 2006-2017 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not, write to the Free
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA.  */
+
+/* This file handles the lowering of GIMPLE_SWITCH to an indexed
+   load, or a series of bit-test-and-branch expressions.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "insn-codes.h"
+#include "rtl.h"
+#include "tree.h"
+#include "gimple.h"
+#include "cfghooks.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "optabs-tree.h"
+#include "cgraph.h"
+#include "gimple-pretty-print.h"
+#include "params.h"
+#include "fold-const.h"
+#include "varasm.h"
+#include "stor-layout.h"
+#include "cfganal.h"
+#include "gimplify.h"
+#include "gimple-iterator.h"
+#include "gimplify-me.h"
+#include "tree-cfg.h"
+#include "cfgloop.h"
+#include "target.h"
+#include "alloc-pool.h"
+#include "tree-into-ssa.h"
+
+struct case_node
+{
+  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