| Message ID | bde90963-7695-89d5-6792-e8f803f71160@suse.cz |
|---|---|
| State | New |
| Headers | show |
| Series | Expand switch statements with a single (or none) non-default case. | expand |
On Wed, Aug 30, 2017 at 1:13 PM, Martin Liška <mliska@suse.cz> wrote: > Hi. > > Simple transformation of switch statements where degenerated switch can be interpreted > as gimple condition (or removed if having any non-default case). I originally though > that we don't have switch statements without non-default cases, but PR82032 shows we > can see it. > > Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. > > Ready to be installed? While I guess this case is ok to handle here it would be nice if CFG cleanup would do the same. I suppose find_taken_edge somehow doesn't work for this case even after my last enhancement? Or is CFG cleanup for some reason not run? Richard. > Martin > > gcc/ChangeLog: > > 2017-08-25 Martin Liska <mliska@suse.cz> > > PR tree-optimization/82032 > * tree-switch-conversion.c (generate_high_low_equality): New > function. > (expand_degenerated_switch): Likewise. > (process_switch): Call expand_degenerated_switch. > (try_switch_expansion): Likewise. > (emit_case_nodes): Use generate_high_low_equality. > > gcc/testsuite/ChangeLog: > > 2017-08-25 Martin Liska <mliska@suse.cz> > > PR tree-optimization/82032 > * gcc.dg/tree-ssa/pr68198.c: Update jump threading expectations. > * gcc.dg/tree-ssa/switch-expansion.c: New test. > * gcc.dg/tree-ssa/vrp34.c: Update scanned pattern. > * g++.dg/other/pr82032.C: New test. > --- > gcc/testsuite/g++.dg/other/pr82032.C | 36 +++++++ > gcc/testsuite/gcc.dg/tree-ssa/pr68198.c | 6 +- > gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c | 14 +++ > gcc/testsuite/gcc.dg/tree-ssa/vrp34.c | 5 +- > gcc/tree-switch-conversion.c | 123 ++++++++++++++++++----- > 5 files changed, 152 insertions(+), 32 deletions(-) > create mode 100644 gcc/testsuite/g++.dg/other/pr82032.C > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c > >
On 08/30/2017 02:28 PM, Richard Biener wrote: > On Wed, Aug 30, 2017 at 1:13 PM, Martin Liška <mliska@suse.cz> wrote: >> Hi. >> >> Simple transformation of switch statements where degenerated switch can be interpreted >> as gimple condition (or removed if having any non-default case). I originally though >> that we don't have switch statements without non-default cases, but PR82032 shows we >> can see it. >> >> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. >> >> Ready to be installed? > > While I guess this case is ok to handle here it would be nice if CFG cleanup > would do the same. I suppose find_taken_edge somehow doesn't work for > this case even after my last enhancement? Or is CFG cleanup for some reason > not run? Do you mean both with # of non-default edges equal to 0 and 1? Let me take a look. Martin > > Richard. > >> Martin >> >> gcc/ChangeLog: >> >> 2017-08-25 Martin Liska <mliska@suse.cz> >> >> PR tree-optimization/82032 >> * tree-switch-conversion.c (generate_high_low_equality): New >> function. >> (expand_degenerated_switch): Likewise. >> (process_switch): Call expand_degenerated_switch. >> (try_switch_expansion): Likewise. >> (emit_case_nodes): Use generate_high_low_equality. >> >> gcc/testsuite/ChangeLog: >> >> 2017-08-25 Martin Liska <mliska@suse.cz> >> >> PR tree-optimization/82032 >> * gcc.dg/tree-ssa/pr68198.c: Update jump threading expectations. >> * gcc.dg/tree-ssa/switch-expansion.c: New test. >> * gcc.dg/tree-ssa/vrp34.c: Update scanned pattern. >> * g++.dg/other/pr82032.C: New test. >> --- >> gcc/testsuite/g++.dg/other/pr82032.C | 36 +++++++ >> gcc/testsuite/gcc.dg/tree-ssa/pr68198.c | 6 +- >> gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c | 14 +++ >> gcc/testsuite/gcc.dg/tree-ssa/vrp34.c | 5 +- >> gcc/tree-switch-conversion.c | 123 ++++++++++++++++++----- >> 5 files changed, 152 insertions(+), 32 deletions(-) >> create mode 100644 gcc/testsuite/g++.dg/other/pr82032.C >> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c >> >>
On Wed, Aug 30, 2017 at 2:32 PM, Martin Liška <mliska@suse.cz> wrote: > On 08/30/2017 02:28 PM, Richard Biener wrote: >> On Wed, Aug 30, 2017 at 1:13 PM, Martin Liška <mliska@suse.cz> wrote: >>> Hi. >>> >>> Simple transformation of switch statements where degenerated switch can be interpreted >>> as gimple condition (or removed if having any non-default case). I originally though >>> that we don't have switch statements without non-default cases, but PR82032 shows we >>> can see it. >>> >>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. >>> >>> Ready to be installed? >> >> While I guess this case is ok to handle here it would be nice if CFG cleanup >> would do the same. I suppose find_taken_edge somehow doesn't work for >> this case even after my last enhancement? Or is CFG cleanup for some reason >> not run? > > Do you mean both with # of non-default edges equal to 0 and 1? > Let me take a look. First and foremost 0. The case of 1 non-default and a default would need extra code. Richard. > Martin > >> >> Richard. >> >>> Martin >>> >>> gcc/ChangeLog: >>> >>> 2017-08-25 Martin Liska <mliska@suse.cz> >>> >>> PR tree-optimization/82032 >>> * tree-switch-conversion.c (generate_high_low_equality): New >>> function. >>> (expand_degenerated_switch): Likewise. >>> (process_switch): Call expand_degenerated_switch. >>> (try_switch_expansion): Likewise. >>> (emit_case_nodes): Use generate_high_low_equality. >>> >>> gcc/testsuite/ChangeLog: >>> >>> 2017-08-25 Martin Liska <mliska@suse.cz> >>> >>> PR tree-optimization/82032 >>> * gcc.dg/tree-ssa/pr68198.c: Update jump threading expectations. >>> * gcc.dg/tree-ssa/switch-expansion.c: New test. >>> * gcc.dg/tree-ssa/vrp34.c: Update scanned pattern. >>> * g++.dg/other/pr82032.C: New test. >>> --- >>> gcc/testsuite/g++.dg/other/pr82032.C | 36 +++++++ >>> gcc/testsuite/gcc.dg/tree-ssa/pr68198.c | 6 +- >>> gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c | 14 +++ >>> gcc/testsuite/gcc.dg/tree-ssa/vrp34.c | 5 +- >>> gcc/tree-switch-conversion.c | 123 ++++++++++++++++++----- >>> 5 files changed, 152 insertions(+), 32 deletions(-) >>> create mode 100644 gcc/testsuite/g++.dg/other/pr82032.C >>> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c >>> >>> >
On 08/30/2017 02:56 PM, Richard Biener wrote: > On Wed, Aug 30, 2017 at 2:32 PM, Martin Liška <mliska@suse.cz> wrote: >> On 08/30/2017 02:28 PM, Richard Biener wrote: >>> On Wed, Aug 30, 2017 at 1:13 PM, Martin Liška <mliska@suse.cz> wrote: >>>> Hi. >>>> >>>> Simple transformation of switch statements where degenerated switch can be interpreted >>>> as gimple condition (or removed if having any non-default case). I originally though >>>> that we don't have switch statements without non-default cases, but PR82032 shows we >>>> can see it. >>>> >>>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. >>>> >>>> Ready to be installed? >>> >>> While I guess this case is ok to handle here it would be nice if CFG cleanup >>> would do the same. I suppose find_taken_edge somehow doesn't work for >>> this case even after my last enhancement? Or is CFG cleanup for some reason >>> not run? >> >> Do you mean both with # of non-default edges equal to 0 and 1? >> Let me take a look. > > First and foremost 0. The case of 1 non-default and a default would > need extra code. For the test-case I reduced, one needs: diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index b7593068ea9..13af516c6ac 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -8712,7 +8712,7 @@ const pass_data pass_data_split_crit_edges = PROP_no_crit_edges, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - 0, /* todo_flags_finish */ + TODO_cleanup_cfg, /* todo_flags_finish */ }; class pass_split_crit_edges : public gimple_opt_pass And the code eliminates the problematic switch statement. Do you believe it's the right approach to add the clean up and preserve the assert in tree-switch-conversion.c? For the case with # of edges == 1, should I place it to tree-cfg.c in order to trigger it as a clean-up? Thoughts? Martin > > Richard. > >> Martin >> >>> >>> Richard. >>> >>>> Martin >>>> >>>> gcc/ChangeLog: >>>> >>>> 2017-08-25 Martin Liska <mliska@suse.cz> >>>> >>>> PR tree-optimization/82032 >>>> * tree-switch-conversion.c (generate_high_low_equality): New >>>> function. >>>> (expand_degenerated_switch): Likewise. >>>> (process_switch): Call expand_degenerated_switch. >>>> (try_switch_expansion): Likewise. >>>> (emit_case_nodes): Use generate_high_low_equality. >>>> >>>> gcc/testsuite/ChangeLog: >>>> >>>> 2017-08-25 Martin Liska <mliska@suse.cz> >>>> >>>> PR tree-optimization/82032 >>>> * gcc.dg/tree-ssa/pr68198.c: Update jump threading expectations. >>>> * gcc.dg/tree-ssa/switch-expansion.c: New test. >>>> * gcc.dg/tree-ssa/vrp34.c: Update scanned pattern. >>>> * g++.dg/other/pr82032.C: New test. >>>> --- >>>> gcc/testsuite/g++.dg/other/pr82032.C | 36 +++++++ >>>> gcc/testsuite/gcc.dg/tree-ssa/pr68198.c | 6 +- >>>> gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c | 14 +++ >>>> gcc/testsuite/gcc.dg/tree-ssa/vrp34.c | 5 +- >>>> gcc/tree-switch-conversion.c | 123 ++++++++++++++++++----- >>>> 5 files changed, 152 insertions(+), 32 deletions(-) >>>> create mode 100644 gcc/testsuite/g++.dg/other/pr82032.C >>>> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c >>>> >>>> >>
On Fri, Sep 1, 2017 at 10:07 AM, Martin Liška <mliska@suse.cz> wrote: > On 08/30/2017 02:56 PM, Richard Biener wrote: >> On Wed, Aug 30, 2017 at 2:32 PM, Martin Liška <mliska@suse.cz> wrote: >>> On 08/30/2017 02:28 PM, Richard Biener wrote: >>>> On Wed, Aug 30, 2017 at 1:13 PM, Martin Liška <mliska@suse.cz> wrote: >>>>> Hi. >>>>> >>>>> Simple transformation of switch statements where degenerated switch can be interpreted >>>>> as gimple condition (or removed if having any non-default case). I originally though >>>>> that we don't have switch statements without non-default cases, but PR82032 shows we >>>>> can see it. >>>>> >>>>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. >>>>> >>>>> Ready to be installed? >>>> >>>> While I guess this case is ok to handle here it would be nice if CFG cleanup >>>> would do the same. I suppose find_taken_edge somehow doesn't work for >>>> this case even after my last enhancement? Or is CFG cleanup for some reason >>>> not run? >>> >>> Do you mean both with # of non-default edges equal to 0 and 1? >>> Let me take a look. >> >> First and foremost 0. The case of 1 non-default and a default would >> need extra code. > > For the test-case I reduced, one needs: > > diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c > index b7593068ea9..13af516c6ac 100644 > --- a/gcc/tree-cfg.c > +++ b/gcc/tree-cfg.c > @@ -8712,7 +8712,7 @@ const pass_data pass_data_split_crit_edges = > PROP_no_crit_edges, /* properties_provided */ > 0, /* properties_destroyed */ > 0, /* todo_flags_start */ > - 0, /* todo_flags_finish */ > + TODO_cleanup_cfg, /* todo_flags_finish */ > }; > > class pass_split_crit_edges : public gimple_opt_pass > > And the code eliminates the problematic switch statement. Do you believe it's the right approach > to add the clean up and preserve the assert in tree-switch-conversion.c? Eh, no. If you run cleanup-cfg after critical edge splitting they will be unsplit immediately, making it (mostly) a no-op. OTOH I wanted to eliminate that "pass" in favor of just calling split_critical_edges () where needed (that's already done in some places). > For the case with # of edges == 1, should I place it to tree-cfg.c in order to trigger it as a clean-up? I believe the code for edges == 1 can reside in cleanup_control_expr_graph. Probably easiest from a flow perspective if we do the switch -> cond transform before the existing code handling cond and switch via find-taken-edge. > Thoughts? > > Martin > >> >> Richard. >> >>> Martin >>> >>>> >>>> Richard. >>>> >>>>> Martin >>>>> >>>>> gcc/ChangeLog: >>>>> >>>>> 2017-08-25 Martin Liska <mliska@suse.cz> >>>>> >>>>> PR tree-optimization/82032 >>>>> * tree-switch-conversion.c (generate_high_low_equality): New >>>>> function. >>>>> (expand_degenerated_switch): Likewise. >>>>> (process_switch): Call expand_degenerated_switch. >>>>> (try_switch_expansion): Likewise. >>>>> (emit_case_nodes): Use generate_high_low_equality. >>>>> >>>>> gcc/testsuite/ChangeLog: >>>>> >>>>> 2017-08-25 Martin Liska <mliska@suse.cz> >>>>> >>>>> PR tree-optimization/82032 >>>>> * gcc.dg/tree-ssa/pr68198.c: Update jump threading expectations. >>>>> * gcc.dg/tree-ssa/switch-expansion.c: New test. >>>>> * gcc.dg/tree-ssa/vrp34.c: Update scanned pattern. >>>>> * g++.dg/other/pr82032.C: New test. >>>>> --- >>>>> gcc/testsuite/g++.dg/other/pr82032.C | 36 +++++++ >>>>> gcc/testsuite/gcc.dg/tree-ssa/pr68198.c | 6 +- >>>>> gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c | 14 +++ >>>>> gcc/testsuite/gcc.dg/tree-ssa/vrp34.c | 5 +- >>>>> gcc/tree-switch-conversion.c | 123 ++++++++++++++++++----- >>>>> 5 files changed, 152 insertions(+), 32 deletions(-) >>>>> create mode 100644 gcc/testsuite/g++.dg/other/pr82032.C >>>>> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c >>>>> >>>>> >>> >
On 09/01/2017 10:26 AM, Richard Biener wrote: > On Fri, Sep 1, 2017 at 10:07 AM, Martin Liška <mliska@suse.cz> wrote: >> On 08/30/2017 02:56 PM, Richard Biener wrote: >>> On Wed, Aug 30, 2017 at 2:32 PM, Martin Liška <mliska@suse.cz> wrote: >>>> On 08/30/2017 02:28 PM, Richard Biener wrote: >>>>> On Wed, Aug 30, 2017 at 1:13 PM, Martin Liška <mliska@suse.cz> wrote: >>>>>> Hi. >>>>>> >>>>>> Simple transformation of switch statements where degenerated switch can be interpreted >>>>>> as gimple condition (or removed if having any non-default case). I originally though >>>>>> that we don't have switch statements without non-default cases, but PR82032 shows we >>>>>> can see it. >>>>>> >>>>>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. >>>>>> >>>>>> Ready to be installed? >>>>> >>>>> While I guess this case is ok to handle here it would be nice if CFG cleanup >>>>> would do the same. I suppose find_taken_edge somehow doesn't work for >>>>> this case even after my last enhancement? Or is CFG cleanup for some reason >>>>> not run? >>>> >>>> Do you mean both with # of non-default edges equal to 0 and 1? >>>> Let me take a look. >>> >>> First and foremost 0. The case of 1 non-default and a default would >>> need extra code. >> >> For the test-case I reduced, one needs: >> >> diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c >> index b7593068ea9..13af516c6ac 100644 >> --- a/gcc/tree-cfg.c >> +++ b/gcc/tree-cfg.c >> @@ -8712,7 +8712,7 @@ const pass_data pass_data_split_crit_edges = >> PROP_no_crit_edges, /* properties_provided */ >> 0, /* properties_destroyed */ >> 0, /* todo_flags_start */ >> - 0, /* todo_flags_finish */ >> + TODO_cleanup_cfg, /* todo_flags_finish */ >> }; >> >> class pass_split_crit_edges : public gimple_opt_pass >> >> And the code eliminates the problematic switch statement. Do you believe it's the right approach >> to add the clean up and preserve the assert in tree-switch-conversion.c? > > Eh, no. If you run cleanup-cfg after critical edge splitting they > will be unsplit immediately, making > it (mostly) a no-op. > > OTOH I wanted to eliminate that "pass" in favor of just calling > split_critical_edges () where needed > (that's already done in some places). Good, so I will leave it to you. Should I in meantime remove the assert in tree-switch-conversion.c ? > >> For the case with # of edges == 1, should I place it to tree-cfg.c in order to trigger it as a clean-up? > > I believe the code for edges == 1 can reside in > cleanup_control_expr_graph. Probably easiest > from a flow perspective if we do the switch -> cond transform before > the existing code handling > cond and switch via find-taken-edge. Working on that, good place to do the transformation. Martin > >> Thoughts? >> >> Martin >> >>> >>> Richard. >>> >>>> Martin >>>> >>>>> >>>>> Richard. >>>>> >>>>>> Martin >>>>>> >>>>>> gcc/ChangeLog: >>>>>> >>>>>> 2017-08-25 Martin Liska <mliska@suse.cz> >>>>>> >>>>>> PR tree-optimization/82032 >>>>>> * tree-switch-conversion.c (generate_high_low_equality): New >>>>>> function. >>>>>> (expand_degenerated_switch): Likewise. >>>>>> (process_switch): Call expand_degenerated_switch. >>>>>> (try_switch_expansion): Likewise. >>>>>> (emit_case_nodes): Use generate_high_low_equality. >>>>>> >>>>>> gcc/testsuite/ChangeLog: >>>>>> >>>>>> 2017-08-25 Martin Liska <mliska@suse.cz> >>>>>> >>>>>> PR tree-optimization/82032 >>>>>> * gcc.dg/tree-ssa/pr68198.c: Update jump threading expectations. >>>>>> * gcc.dg/tree-ssa/switch-expansion.c: New test. >>>>>> * gcc.dg/tree-ssa/vrp34.c: Update scanned pattern. >>>>>> * g++.dg/other/pr82032.C: New test. >>>>>> --- >>>>>> gcc/testsuite/g++.dg/other/pr82032.C | 36 +++++++ >>>>>> gcc/testsuite/gcc.dg/tree-ssa/pr68198.c | 6 +- >>>>>> gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c | 14 +++ >>>>>> gcc/testsuite/gcc.dg/tree-ssa/vrp34.c | 5 +- >>>>>> gcc/tree-switch-conversion.c | 123 ++++++++++++++++++----- >>>>>> 5 files changed, 152 insertions(+), 32 deletions(-) >>>>>> create mode 100644 gcc/testsuite/g++.dg/other/pr82032.C >>>>>> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c >>>>>> >>>>>> >>>> >>
On Fri, Sep 1, 2017 at 12:44 PM, Martin Liška <mliska@suse.cz> wrote: > On 09/01/2017 10:26 AM, Richard Biener wrote: >> On Fri, Sep 1, 2017 at 10:07 AM, Martin Liška <mliska@suse.cz> wrote: >>> On 08/30/2017 02:56 PM, Richard Biener wrote: >>>> On Wed, Aug 30, 2017 at 2:32 PM, Martin Liška <mliska@suse.cz> wrote: >>>>> On 08/30/2017 02:28 PM, Richard Biener wrote: >>>>>> On Wed, Aug 30, 2017 at 1:13 PM, Martin Liška <mliska@suse.cz> wrote: >>>>>>> Hi. >>>>>>> >>>>>>> Simple transformation of switch statements where degenerated switch can be interpreted >>>>>>> as gimple condition (or removed if having any non-default case). I originally though >>>>>>> that we don't have switch statements without non-default cases, but PR82032 shows we >>>>>>> can see it. >>>>>>> >>>>>>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. >>>>>>> >>>>>>> Ready to be installed? >>>>>> >>>>>> While I guess this case is ok to handle here it would be nice if CFG cleanup >>>>>> would do the same. I suppose find_taken_edge somehow doesn't work for >>>>>> this case even after my last enhancement? Or is CFG cleanup for some reason >>>>>> not run? >>>>> >>>>> Do you mean both with # of non-default edges equal to 0 and 1? >>>>> Let me take a look. >>>> >>>> First and foremost 0. The case of 1 non-default and a default would >>>> need extra code. >>> >>> For the test-case I reduced, one needs: >>> >>> diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c >>> index b7593068ea9..13af516c6ac 100644 >>> --- a/gcc/tree-cfg.c >>> +++ b/gcc/tree-cfg.c >>> @@ -8712,7 +8712,7 @@ const pass_data pass_data_split_crit_edges = >>> PROP_no_crit_edges, /* properties_provided */ >>> 0, /* properties_destroyed */ >>> 0, /* todo_flags_start */ >>> - 0, /* todo_flags_finish */ >>> + TODO_cleanup_cfg, /* todo_flags_finish */ >>> }; >>> >>> class pass_split_crit_edges : public gimple_opt_pass >>> >>> And the code eliminates the problematic switch statement. Do you believe it's the right approach >>> to add the clean up and preserve the assert in tree-switch-conversion.c? >> >> Eh, no. If you run cleanup-cfg after critical edge splitting they >> will be unsplit immediately, making >> it (mostly) a no-op. >> >> OTOH I wanted to eliminate that "pass" in favor of just calling >> split_critical_edges () where needed >> (that's already done in some places). > > Good, so I will leave it to you. Should I in meantime remove the assert in tree-switch-conversion.c ? Yes, as said your patch was generally OK, I just wondered why we left the switches "unoptimized". Richard. >> >>> For the case with # of edges == 1, should I place it to tree-cfg.c in order to trigger it as a clean-up? >> >> I believe the code for edges == 1 can reside in >> cleanup_control_expr_graph. Probably easiest >> from a flow perspective if we do the switch -> cond transform before >> the existing code handling >> cond and switch via find-taken-edge. > > Working on that, good place to do the transformation. > > Martin > >> >>> Thoughts? >>> >>> Martin >>> >>>> >>>> Richard. >>>> >>>>> Martin >>>>> >>>>>> >>>>>> Richard. >>>>>> >>>>>>> Martin >>>>>>> >>>>>>> gcc/ChangeLog: >>>>>>> >>>>>>> 2017-08-25 Martin Liska <mliska@suse.cz> >>>>>>> >>>>>>> PR tree-optimization/82032 >>>>>>> * tree-switch-conversion.c (generate_high_low_equality): New >>>>>>> function. >>>>>>> (expand_degenerated_switch): Likewise. >>>>>>> (process_switch): Call expand_degenerated_switch. >>>>>>> (try_switch_expansion): Likewise. >>>>>>> (emit_case_nodes): Use generate_high_low_equality. >>>>>>> >>>>>>> gcc/testsuite/ChangeLog: >>>>>>> >>>>>>> 2017-08-25 Martin Liska <mliska@suse.cz> >>>>>>> >>>>>>> PR tree-optimization/82032 >>>>>>> * gcc.dg/tree-ssa/pr68198.c: Update jump threading expectations. >>>>>>> * gcc.dg/tree-ssa/switch-expansion.c: New test. >>>>>>> * gcc.dg/tree-ssa/vrp34.c: Update scanned pattern. >>>>>>> * g++.dg/other/pr82032.C: New test. >>>>>>> --- >>>>>>> gcc/testsuite/g++.dg/other/pr82032.C | 36 +++++++ >>>>>>> gcc/testsuite/gcc.dg/tree-ssa/pr68198.c | 6 +- >>>>>>> gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c | 14 +++ >>>>>>> gcc/testsuite/gcc.dg/tree-ssa/vrp34.c | 5 +- >>>>>>> gcc/tree-switch-conversion.c | 123 ++++++++++++++++++----- >>>>>>> 5 files changed, 152 insertions(+), 32 deletions(-) >>>>>>> create mode 100644 gcc/testsuite/g++.dg/other/pr82032.C >>>>>>> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c >>>>>>> >>>>>>> >>>>> >>> >
On 09/01/2017 12:57 PM, Richard Biener wrote: > On Fri, Sep 1, 2017 at 12:44 PM, Martin Liška <mliska@suse.cz> wrote: >> On 09/01/2017 10:26 AM, Richard Biener wrote: >>> On Fri, Sep 1, 2017 at 10:07 AM, Martin Liška <mliska@suse.cz> wrote: >>>> On 08/30/2017 02:56 PM, Richard Biener wrote: >>>>> On Wed, Aug 30, 2017 at 2:32 PM, Martin Liška <mliska@suse.cz> wrote: >>>>>> On 08/30/2017 02:28 PM, Richard Biener wrote: >>>>>>> On Wed, Aug 30, 2017 at 1:13 PM, Martin Liška <mliska@suse.cz> wrote: >>>>>>>> Hi. >>>>>>>> >>>>>>>> Simple transformation of switch statements where degenerated switch can be interpreted >>>>>>>> as gimple condition (or removed if having any non-default case). I originally though >>>>>>>> that we don't have switch statements without non-default cases, but PR82032 shows we >>>>>>>> can see it. >>>>>>>> >>>>>>>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. >>>>>>>> >>>>>>>> Ready to be installed? >>>>>>> >>>>>>> While I guess this case is ok to handle here it would be nice if CFG cleanup >>>>>>> would do the same. I suppose find_taken_edge somehow doesn't work for >>>>>>> this case even after my last enhancement? Or is CFG cleanup for some reason >>>>>>> not run? >>>>>> >>>>>> Do you mean both with # of non-default edges equal to 0 and 1? >>>>>> Let me take a look. >>>>> >>>>> First and foremost 0. The case of 1 non-default and a default would >>>>> need extra code. >>>> >>>> For the test-case I reduced, one needs: >>>> >>>> diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c >>>> index b7593068ea9..13af516c6ac 100644 >>>> --- a/gcc/tree-cfg.c >>>> +++ b/gcc/tree-cfg.c >>>> @@ -8712,7 +8712,7 @@ const pass_data pass_data_split_crit_edges = >>>> PROP_no_crit_edges, /* properties_provided */ >>>> 0, /* properties_destroyed */ >>>> 0, /* todo_flags_start */ >>>> - 0, /* todo_flags_finish */ >>>> + TODO_cleanup_cfg, /* todo_flags_finish */ >>>> }; >>>> >>>> class pass_split_crit_edges : public gimple_opt_pass >>>> >>>> And the code eliminates the problematic switch statement. Do you believe it's the right approach >>>> to add the clean up and preserve the assert in tree-switch-conversion.c? >>> >>> Eh, no. If you run cleanup-cfg after critical edge splitting they >>> will be unsplit immediately, making >>> it (mostly) a no-op. >>> >>> OTOH I wanted to eliminate that "pass" in favor of just calling >>> split_critical_edges () where needed >>> (that's already done in some places). >> >> Good, so I will leave it to you. Should I in meantime remove the assert in tree-switch-conversion.c ? > > Yes, as said your patch was generally OK, I just wondered why we left > the switches "unoptimized". Good. I'm sending v2 for single non-default case situation. Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. Ready to be installed? Martin > > Richard. > >>> >>>> For the case with # of edges == 1, should I place it to tree-cfg.c in order to trigger it as a clean-up? >>> >>> I believe the code for edges == 1 can reside in >>> cleanup_control_expr_graph. Probably easiest >>> from a flow perspective if we do the switch -> cond transform before >>> the existing code handling >>> cond and switch via find-taken-edge. >> >> Working on that, good place to do the transformation. >> >> Martin >> >>> >>>> Thoughts? >>>> >>>> Martin >>>> >>>>> >>>>> Richard. >>>>> >>>>>> Martin >>>>>> >>>>>>> >>>>>>> Richard. >>>>>>> >>>>>>>> Martin >>>>>>>> >>>>>>>> gcc/ChangeLog: >>>>>>>> >>>>>>>> 2017-08-25 Martin Liska <mliska@suse.cz> >>>>>>>> >>>>>>>> PR tree-optimization/82032 >>>>>>>> * tree-switch-conversion.c (generate_high_low_equality): New >>>>>>>> function. >>>>>>>> (expand_degenerated_switch): Likewise. >>>>>>>> (process_switch): Call expand_degenerated_switch. >>>>>>>> (try_switch_expansion): Likewise. >>>>>>>> (emit_case_nodes): Use generate_high_low_equality. >>>>>>>> >>>>>>>> gcc/testsuite/ChangeLog: >>>>>>>> >>>>>>>> 2017-08-25 Martin Liska <mliska@suse.cz> >>>>>>>> >>>>>>>> PR tree-optimization/82032 >>>>>>>> * gcc.dg/tree-ssa/pr68198.c: Update jump threading expectations. >>>>>>>> * gcc.dg/tree-ssa/switch-expansion.c: New test. >>>>>>>> * gcc.dg/tree-ssa/vrp34.c: Update scanned pattern. >>>>>>>> * g++.dg/other/pr82032.C: New test. >>>>>>>> --- >>>>>>>> gcc/testsuite/g++.dg/other/pr82032.C | 36 +++++++ >>>>>>>> gcc/testsuite/gcc.dg/tree-ssa/pr68198.c | 6 +- >>>>>>>> gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c | 14 +++ >>>>>>>> gcc/testsuite/gcc.dg/tree-ssa/vrp34.c | 5 +- >>>>>>>> gcc/tree-switch-conversion.c | 123 ++++++++++++++++++----- >>>>>>>> 5 files changed, 152 insertions(+), 32 deletions(-) >>>>>>>> create mode 100644 gcc/testsuite/g++.dg/other/pr82032.C >>>>>>>> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c >>>>>>>> >>>>>>>> >>>>>> >>>> >> From 706b76ac44a8e6359cd12d2ebaef79a2bbba707d Mon Sep 17 00:00:00 2001 From: marxin <mliska@suse.cz> Date: Fri, 1 Sep 2017 12:52:31 +0200 Subject: [PATCH] Learn CFG cleanup to transform single case switches to gcond. gcc/ChangeLog: 2017-09-01 Martin Liska <mliska@suse.cz> * tree-cfg.c (generate_high_low_equality): New function. * tree-cfg.h (generate_high_low_equality): Declared here. * tree-cfgcleanup.c (convert_single_case_switch): New function. (cleanup_control_expr_graph): Use it. * tree-switch-conversion.c (try_switch_expansion): Remove assert. (emit_case_nodes): Use generate_high_low_equality. gcc/testsuite/ChangeLog: 2017-09-01 Martin Liska <mliska@suse.cz> * g++.dg/other/pr82032.C: New test. * gcc.dg/tree-ssa/pr68198.c: Update scanned pattern. * gcc.dg/tree-ssa/vrp34.c: Likewise. * gcc.dg/switch-10.c: Likewise. --- gcc/testsuite/g++.dg/other/pr82032.C | 36 ++++++++++++++++++++++++ gcc/testsuite/gcc.dg/switch-10.c | 5 ++-- gcc/testsuite/gcc.dg/tree-ssa/pr68198.c | 6 ++-- gcc/testsuite/gcc.dg/tree-ssa/vrp34.c | 5 ++-- gcc/tree-cfg.c | 25 +++++++++++++++++ gcc/tree-cfg.h | 2 ++ gcc/tree-cfgcleanup.c | 49 +++++++++++++++++++++++++++++++++ gcc/tree-switch-conversion.c | 27 ++++-------------- 8 files changed, 126 insertions(+), 29 deletions(-) create mode 100644 gcc/testsuite/g++.dg/other/pr82032.C diff --git a/gcc/testsuite/g++.dg/other/pr82032.C b/gcc/testsuite/g++.dg/other/pr82032.C new file mode 100644 index 00000000000..607bf85c8e1 --- /dev/null +++ b/gcc/testsuite/g++.dg/other/pr82032.C @@ -0,0 +1,36 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -Wno-return-type" } */ + +template <typename a> class b +{ +public: + typename a::aa operator[] (typename a::c) { } +}; +class d +{ +public: + typedef long c; + typedef int aa; +}; +struct e +{ + int af[4]; + int ag; +}; +b<d> f; +bool +g (e &i) +{ + for (int h; h; ++h) + switch (f[h]) + { + case 'x': + case 'a': + i.af[h] = 3; + break; + default: + return false; + } + + return true; +} diff --git a/gcc/testsuite/gcc.dg/switch-10.c b/gcc/testsuite/gcc.dg/switch-10.c index 0ffc9eb5757..9e5926745b8 100644 --- a/gcc/testsuite/gcc.dg/switch-10.c +++ b/gcc/testsuite/gcc.dg/switch-10.c @@ -1,6 +1,4 @@ /* { dg-options "-O2 -fdump-tree-cfg" } */ -/* { dg-final { scan-tree-dump "case 0:" "cfg" } } */ -/* { dg-final { scan-tree-dump-not "case 1 ... 255:" "cfg" } } */ #include <stdint.h> void foo (void); @@ -20,3 +18,6 @@ test (uint8_t ch) break; } } + +/* Switch statement is converted to GIMPLE condition. */ +/* { dg-final { scan-tree-dump-not "switch" "cfg" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c b/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c index 16097d7e2bc..59d562e156c 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c @@ -37,7 +37,5 @@ c_finish_omp_clauses (tree clauses) } } -/* There are 3 FSM jump threading opportunities, two of which will - get filtered out. */ -/* { dg-final { scan-tree-dump-times "Registering FSM" 1 "thread1"} } */ -/* { dg-final { scan-tree-dump-times "FSM Thread through multiway branch without threading a multiway branch" 2 "thread1"} } */ +/* There are 3 FSM jump threading opportunities. */ +/* { dg-final { scan-tree-dump-times "Registering FSM" 3 "thread1"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c index 142e56c1641..d2a36a706f2 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c @@ -15,5 +15,6 @@ foo (int a) } } -/* Both ifs should be optimized. */ -/* { dg-final { scan-tree-dump-times "if \\\(" 0 "vrp1" } } */ +/* Both ifs should be optimized (and switch statement will be the only if + in the function). */ +/* { dg-final { scan-tree-dump-times "if \\\(" 1 "vrp1" } } */ diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index b7593068ea9..8ab509bf0cb 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -8927,7 +8927,32 @@ extract_true_false_controlled_edges (basic_block dom, basic_block phiblock, return true; } +/* Generate GIMPLE IL to basic block BB which compares whether INDEX + value is within range LOW ... HIGH. We create a LHS and RHS that + can be then compared in order to hit the interval or not. */ +void +generate_high_low_equality (basic_block bb, tree index, tree low, tree high, + tree *lhs, tree *rhs) +{ + tree type = TREE_TYPE (index); + tree utype = unsigned_type_for (type); + + low = fold_convert (type, low); + high = fold_convert (type, high); + + tree tmp = make_ssa_name (type); + gassign *sub1 + = gimple_build_assign (tmp, MINUS_EXPR, index, low); + + *lhs = make_ssa_name (utype); + gassign *a = gimple_build_assign (*lhs, NOP_EXPR, tmp); + + *rhs = fold_build2 (MINUS_EXPR, utype, high, low); + gimple_stmt_iterator gsi = gsi_last_bb (bb); + gsi_insert_before (&gsi, sub1, GSI_SAME_STMT); + gsi_insert_before (&gsi, a, GSI_SAME_STMT); +} /* Emit return warnings. */ diff --git a/gcc/tree-cfg.h b/gcc/tree-cfg.h index 66be43657bc..ad52c448947 100644 --- a/gcc/tree-cfg.h +++ b/gcc/tree-cfg.h @@ -109,6 +109,8 @@ extern basic_block insert_cond_bb (basic_block, gimple *, gimple *, extern bool gimple_find_sub_bbs (gimple_seq, gimple_stmt_iterator *); extern bool extract_true_false_controlled_edges (basic_block, basic_block, edge *, edge *); +extern void generate_high_low_equality (basic_block bb, tree index, tree low, + tree high, tree *lhs, tree *rhs); /* Return true if the LHS of a call should be removed. */ diff --git a/gcc/tree-cfgcleanup.c b/gcc/tree-cfgcleanup.c index c6e5c8da03c..67f392c97dd 100644 --- a/gcc/tree-cfgcleanup.c +++ b/gcc/tree-cfgcleanup.c @@ -74,6 +74,49 @@ remove_fallthru_edge (vec<edge, va_gc> *ev) return false; } +/* Convert a SWTCH with single non-default case to gcond and replace it + at GSI. */ + +static bool +convert_single_case_switch (gswitch *swtch, gimple_stmt_iterator &gsi) +{ + if (gimple_switch_num_labels (swtch) != 2) + return false; + + tree index = gimple_switch_index (swtch); + tree default_label = CASE_LABEL (gimple_switch_default_label (swtch)); + tree label = gimple_switch_label (swtch, 1); + tree low = CASE_LOW (label); + tree high = CASE_HIGH (label); + + basic_block default_bb = label_to_block_fn (cfun, default_label); + basic_block case_bb = label_to_block_fn (cfun, CASE_LABEL (label)); + + basic_block bb = gimple_bb (swtch); + gcond *cond; + + /* Replace switch statement with condition statement. */ + if (high) + { + tree lhs, rhs; + generate_high_low_equality (bb, index, low, high, &lhs, &rhs); + cond = gimple_build_cond (LE_EXPR, lhs, rhs, NULL_TREE, NULL_TREE); + } + else + cond = gimple_build_cond (EQ_EXPR, index, + fold_convert (TREE_TYPE (index), low), + NULL_TREE, NULL_TREE); + + gsi_replace (&gsi, cond, true); + + /* Update edges. */ + edge case_edge = find_edge (bb, case_bb); + edge default_edge = find_edge (bb, default_bb); + + case_edge->flags |= EDGE_TRUE_VALUE; + default_edge->flags |= EDGE_FALSE_VALUE; + return true; +} /* Disconnect an unreachable block in the control expression starting at block BB. */ @@ -93,6 +136,12 @@ cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi, bool warned; tree val = NULL_TREE; + /* Try to convert a switch with just a single non-default case to + GIMPLE condition. */ + if (gimple_code (stmt) == GIMPLE_SWITCH + && convert_single_case_switch (as_a<gswitch *> (stmt), gsi)) + stmt = gsi_stmt (gsi); + fold_defer_overflow_warnings (); switch (gimple_code (stmt)) { diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index d0d08972804..36bac0dd1e5 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -2057,9 +2057,8 @@ try_switch_expansion (gswitch *stmt) expressions being INTEGER_CST. */ gcc_assert (TREE_CODE (index_expr) != INTEGER_CST); - /* Optimization of switch statements with only one label has already - occurred, so we should never see them at this point. */ - gcc_assert (ncases > 1); + if (ncases == 1) + return false; /* Find the default case target label. */ tree default_label = CASE_LABEL (gimple_switch_default_label (stmt)); @@ -2701,27 +2700,13 @@ emit_case_nodes (basic_block bb, tree index, case_node_ptr node, } else if (!low_bound && !high_bound) { - tree type = TREE_TYPE (index); - tree utype = unsigned_type_for (type); - - tree lhs = make_ssa_name (type); - gassign *sub1 - = gimple_build_assign (lhs, MINUS_EXPR, index, node->low); - - tree converted = make_ssa_name (utype); - gassign *a = gimple_build_assign (converted, NOP_EXPR, lhs); - - tree rhs = fold_build2 (MINUS_EXPR, utype, - fold_convert (type, node->high), - fold_convert (type, node->low)); - gimple_stmt_iterator gsi = gsi_last_bb (bb); - gsi_insert_before (&gsi, sub1, GSI_SAME_STMT); - gsi_insert_before (&gsi, a, GSI_SAME_STMT); - + tree lhs, rhs; + generate_high_low_equality (bb, index, node->low, node->high, + &lhs, &rhs); probability = conditional_probability (default_prob, subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, converted, rhs, GT_EXPR, + bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR, default_bb, probability, phi_mapping); }
On Fri, Sep 1, 2017 at 3:01 PM, Martin Liška <mliska@suse.cz> wrote: > On 09/01/2017 12:57 PM, Richard Biener wrote: >> On Fri, Sep 1, 2017 at 12:44 PM, Martin Liška <mliska@suse.cz> wrote: >>> On 09/01/2017 10:26 AM, Richard Biener wrote: >>>> On Fri, Sep 1, 2017 at 10:07 AM, Martin Liška <mliska@suse.cz> wrote: >>>>> On 08/30/2017 02:56 PM, Richard Biener wrote: >>>>>> On Wed, Aug 30, 2017 at 2:32 PM, Martin Liška <mliska@suse.cz> wrote: >>>>>>> On 08/30/2017 02:28 PM, Richard Biener wrote: >>>>>>>> On Wed, Aug 30, 2017 at 1:13 PM, Martin Liška <mliska@suse.cz> wrote: >>>>>>>>> Hi. >>>>>>>>> >>>>>>>>> Simple transformation of switch statements where degenerated switch can be interpreted >>>>>>>>> as gimple condition (or removed if having any non-default case). I originally though >>>>>>>>> that we don't have switch statements without non-default cases, but PR82032 shows we >>>>>>>>> can see it. >>>>>>>>> >>>>>>>>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. >>>>>>>>> >>>>>>>>> Ready to be installed? >>>>>>>> >>>>>>>> While I guess this case is ok to handle here it would be nice if CFG cleanup >>>>>>>> would do the same. I suppose find_taken_edge somehow doesn't work for >>>>>>>> this case even after my last enhancement? Or is CFG cleanup for some reason >>>>>>>> not run? >>>>>>> >>>>>>> Do you mean both with # of non-default edges equal to 0 and 1? >>>>>>> Let me take a look. >>>>>> >>>>>> First and foremost 0. The case of 1 non-default and a default would >>>>>> need extra code. >>>>> >>>>> For the test-case I reduced, one needs: >>>>> >>>>> diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c >>>>> index b7593068ea9..13af516c6ac 100644 >>>>> --- a/gcc/tree-cfg.c >>>>> +++ b/gcc/tree-cfg.c >>>>> @@ -8712,7 +8712,7 @@ const pass_data pass_data_split_crit_edges = >>>>> PROP_no_crit_edges, /* properties_provided */ >>>>> 0, /* properties_destroyed */ >>>>> 0, /* todo_flags_start */ >>>>> - 0, /* todo_flags_finish */ >>>>> + TODO_cleanup_cfg, /* todo_flags_finish */ >>>>> }; >>>>> >>>>> class pass_split_crit_edges : public gimple_opt_pass >>>>> >>>>> And the code eliminates the problematic switch statement. Do you believe it's the right approach >>>>> to add the clean up and preserve the assert in tree-switch-conversion.c? >>>> >>>> Eh, no. If you run cleanup-cfg after critical edge splitting they >>>> will be unsplit immediately, making >>>> it (mostly) a no-op. >>>> >>>> OTOH I wanted to eliminate that "pass" in favor of just calling >>>> split_critical_edges () where needed >>>> (that's already done in some places). >>> >>> Good, so I will leave it to you. Should I in meantime remove the assert in tree-switch-conversion.c ? >> >> Yes, as said your patch was generally OK, I just wondered why we left >> the switches "unoptimized". > > Good. > > I'm sending v2 for single non-default case situation. > Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. > > Ready to be installed? Some style nits. generate_high_low_equality is a bit cumbersome I think and I'd prefer /* Generate a range test LHS CODE RHS that determines whether INDEX is in the range [low, high]. Place associated stmts before *GSI. */ void generate_range_test (gimple_stmt_iterator *gsi, tree index, wide_int low, wide_int high, enum tree_code *code, tree *lhs, tree *rhs) { } this captures the implicit requirement of constant low/high (otherwise you'll generate invalid GIMPLE) and it makes the comparison code explicit -- otherwise a user has to inspect users or decipher the function. Note you'll need to use wi::from (low, TYPE_PRECISION (TREE_TYPE (index)), SIGNED/UNSIGNED) to get at the promoted wide-ints/trees. Otherwise it looks reasonable. Not super-happy with the tree-cfg.c location for the helper but I don't have anything more appropriate either. Thanks, Richard. > Martin > >> >> Richard. >> >>>> >>>>> For the case with # of edges == 1, should I place it to tree-cfg.c in order to trigger it as a clean-up? >>>> >>>> I believe the code for edges == 1 can reside in >>>> cleanup_control_expr_graph. Probably easiest >>>> from a flow perspective if we do the switch -> cond transform before >>>> the existing code handling >>>> cond and switch via find-taken-edge. >>> >>> Working on that, good place to do the transformation. >>> >>> Martin >>> >>>> >>>>> Thoughts? >>>>> >>>>> Martin >>>>> >>>>>> >>>>>> Richard. >>>>>> >>>>>>> Martin >>>>>>> >>>>>>>> >>>>>>>> Richard. >>>>>>>> >>>>>>>>> Martin >>>>>>>>> >>>>>>>>> gcc/ChangeLog: >>>>>>>>> >>>>>>>>> 2017-08-25 Martin Liska <mliska@suse.cz> >>>>>>>>> >>>>>>>>> PR tree-optimization/82032 >>>>>>>>> * tree-switch-conversion.c (generate_high_low_equality): New >>>>>>>>> function. >>>>>>>>> (expand_degenerated_switch): Likewise. >>>>>>>>> (process_switch): Call expand_degenerated_switch. >>>>>>>>> (try_switch_expansion): Likewise. >>>>>>>>> (emit_case_nodes): Use generate_high_low_equality. >>>>>>>>> >>>>>>>>> gcc/testsuite/ChangeLog: >>>>>>>>> >>>>>>>>> 2017-08-25 Martin Liska <mliska@suse.cz> >>>>>>>>> >>>>>>>>> PR tree-optimization/82032 >>>>>>>>> * gcc.dg/tree-ssa/pr68198.c: Update jump threading expectations. >>>>>>>>> * gcc.dg/tree-ssa/switch-expansion.c: New test. >>>>>>>>> * gcc.dg/tree-ssa/vrp34.c: Update scanned pattern. >>>>>>>>> * g++.dg/other/pr82032.C: New test. >>>>>>>>> --- >>>>>>>>> gcc/testsuite/g++.dg/other/pr82032.C | 36 +++++++ >>>>>>>>> gcc/testsuite/gcc.dg/tree-ssa/pr68198.c | 6 +- >>>>>>>>> gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c | 14 +++ >>>>>>>>> gcc/testsuite/gcc.dg/tree-ssa/vrp34.c | 5 +- >>>>>>>>> gcc/tree-switch-conversion.c | 123 ++++++++++++++++++----- >>>>>>>>> 5 files changed, 152 insertions(+), 32 deletions(-) >>>>>>>>> create mode 100644 gcc/testsuite/g++.dg/other/pr82032.C >>>>>>>>> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c >>>>>>>>> >>>>>>>>> >>>>>>> >>>>> >>> >
diff --git a/gcc/testsuite/g++.dg/other/pr82032.C b/gcc/testsuite/g++.dg/other/pr82032.C new file mode 100644 index 00000000000..607bf85c8e1 --- /dev/null +++ b/gcc/testsuite/g++.dg/other/pr82032.C @@ -0,0 +1,36 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -Wno-return-type" } */ + +template <typename a> class b +{ +public: + typename a::aa operator[] (typename a::c) { } +}; +class d +{ +public: + typedef long c; + typedef int aa; +}; +struct e +{ + int af[4]; + int ag; +}; +b<d> f; +bool +g (e &i) +{ + for (int h; h; ++h) + switch (f[h]) + { + case 'x': + case 'a': + i.af[h] = 3; + break; + default: + return false; + } + + return true; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c b/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c index 16097d7e2bc..59d562e156c 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr68198.c @@ -37,7 +37,5 @@ c_finish_omp_clauses (tree clauses) } } -/* There are 3 FSM jump threading opportunities, two of which will - get filtered out. */ -/* { dg-final { scan-tree-dump-times "Registering FSM" 1 "thread1"} } */ -/* { dg-final { scan-tree-dump-times "FSM Thread through multiway branch without threading a multiway branch" 2 "thread1"} } */ +/* There are 3 FSM jump threading opportunities. */ +/* { dg-final { scan-tree-dump-times "Registering FSM" 3 "thread1"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c b/gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c new file mode 100644 index 00000000000..306253f3f9c --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/switch-expansion.c @@ -0,0 +1,14 @@ +/* { dg-options "-O2 -fdump-tree-switchconv" } */ + +int check(int param) +{ + switch (param) + { + case -2: + return 1; + default: + return 0; + } +} + +/* { dg-final { scan-tree-dump "Expanding GIMPLE switch as condition" "switchconv" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c index 142e56c1641..d2a36a706f2 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp34.c @@ -15,5 +15,6 @@ foo (int a) } } -/* Both ifs should be optimized. */ -/* { dg-final { scan-tree-dump-times "if \\\(" 0 "vrp1" } } */ +/* Both ifs should be optimized (and switch statement will be the only if + in the function). */ +/* { dg-final { scan-tree-dump-times "if \\\(" 1 "vrp1" } } */ diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index 5a827a6f1f9..b1cc203aba2 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -1486,6 +1486,88 @@ gen_inbound_check (gswitch *swtch, struct switch_conv_info *info) } } +/* Generate GIMPLE IL to basic block BB which compares whether INDEX + value is within range LOW ... HIGH. We create a LHS and RHS that + can be then compared in order to hit the interval or not. */ + +static void +generate_high_low_equality (basic_block bb, tree index, tree low, tree high, + tree *lhs, tree *rhs) +{ + tree type = TREE_TYPE (index); + tree utype = unsigned_type_for (type); + + low = fold_convert (type, low); + high = fold_convert (type, high); + + tree tmp = make_ssa_name (type); + gassign *sub1 + = gimple_build_assign (tmp, MINUS_EXPR, index, low); + + *lhs = make_ssa_name (utype); + gassign *a = gimple_build_assign (*lhs, NOP_EXPR, tmp); + + *rhs = fold_build2 (MINUS_EXPR, utype, high, low); + gimple_stmt_iterator gsi = gsi_last_bb (bb); + gsi_insert_before (&gsi, sub1, GSI_SAME_STMT); + gsi_insert_before (&gsi, a, GSI_SAME_STMT); +} + +/* Expand SWTCH with at maximum a single non-default edge to simple gimple + condition. */ + +static void +expand_degenerated_switch (gswitch *swtch) +{ + tree index = gimple_switch_index (swtch); + gimple_stmt_iterator gsi = gsi_for_stmt (swtch); + + if (gimple_switch_num_labels (swtch) == 1) + { + gsi_remove (&gsi, true); + + if (dump_file) + fprintf (dump_file, ";; Removing GIMPLE switch:\n"); + } + else + { + tree default_label = CASE_LABEL (gimple_switch_default_label (swtch)); + tree label = gimple_switch_label (swtch, 1); + tree low = CASE_LOW (label); + tree high = CASE_HIGH (label); + + basic_block default_bb = label_to_block_fn (cfun, default_label); + basic_block case_bb = label_to_block_fn (cfun, CASE_LABEL (label)); + + basic_block bb = gimple_bb (swtch); + gcond *cond; + + /* Replace switch statement with condition statement. */ + if (high) + { + tree lhs, rhs; + generate_high_low_equality (bb, index, low, high, &lhs, &rhs); + cond = gimple_build_cond (LE_EXPR, lhs, rhs, NULL_TREE, NULL_TREE); + } + else + cond = gimple_build_cond (EQ_EXPR, index, + fold_convert (TREE_TYPE (index), low), + NULL_TREE, NULL_TREE); + + gsi_replace (&gsi, cond, true); + + /* Update edges. */ + edge case_edge = find_edge (bb, case_bb); + edge default_edge = find_edge (bb, default_bb); + + case_edge->flags |= EDGE_TRUE_VALUE; + default_edge->flags |= EDGE_FALSE_VALUE; + + if (dump_file) + fprintf (dump_file, ";; Expanding GIMPLE switch as condition:\n"); + } +} + /* The following function is invoked on every switch statement (the current one is given in SWTCH) and runs the individual phases of switch conversion on it one after another until one fails or the conversion is completed. @@ -1501,10 +1583,11 @@ process_switch (gswitch *swtch) that decide on the code generation approach for this switch. */ group_case_labels_stmt (swtch); - /* If this switch is now a degenerate case with only a default label, - there is nothing left for us to do. */ - if (gimple_switch_num_labels (swtch) < 2) - return "switch is a degenerate case"; + if (gimple_switch_num_labels (swtch) <= 2) + { + expand_degenerated_switch (swtch); + return NULL; + } collect_switch_conv_info (swtch, &info); @@ -2047,6 +2130,12 @@ try_switch_expansion (gswitch *stmt) hash_map<tree, tree> phi_mapping; auto_vec<basic_block> case_bbs; + if (gimple_switch_num_labels (stmt) <= 2) + { + expand_degenerated_switch (stmt); + return true; + } + /* 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; @@ -2058,10 +2147,6 @@ try_switch_expansion (gswitch *stmt) expressions being INTEGER_CST. */ gcc_assert (TREE_CODE (index_expr) != INTEGER_CST); - /* Optimization of switch statements with only one label has already - occurred, so we should never see them at this point. */ - gcc_assert (ncases > 1); - /* 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); @@ -2702,27 +2787,13 @@ emit_case_nodes (basic_block bb, tree index, case_node_ptr node, } else if (!low_bound && !high_bound) { - tree type = TREE_TYPE (index); - tree utype = unsigned_type_for (type); - - tree lhs = make_ssa_name (type); - gassign *sub1 - = gimple_build_assign (lhs, MINUS_EXPR, index, node->low); - - tree converted = make_ssa_name (utype); - gassign *a = gimple_build_assign (converted, NOP_EXPR, lhs); - - tree rhs = fold_build2 (MINUS_EXPR, utype, - fold_convert (type, node->high), - fold_convert (type, node->low)); - gimple_stmt_iterator gsi = gsi_last_bb (bb); - gsi_insert_before (&gsi, sub1, GSI_SAME_STMT); - gsi_insert_before (&gsi, a, GSI_SAME_STMT); - + tree lhs, rhs; + generate_high_low_equality (bb, index, node->low, node->high, + &lhs, &rhs); probability = conditional_probability (default_prob, subtree_prob + default_prob); - bb = emit_cmp_and_jump_insns (bb, converted, rhs, GT_EXPR, + bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR, default_bb, probability, phi_mapping); }