[PATCH] Add if-chain to switch conversion pass.

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

[PATCH] Add if-chain to switch conversion pass.

Martin Liška-2
Hello.

The patch adds a new pass that identifies a series of if-elseif
statements and transform then into a GIMPLE switch (if possible).
The pass runs right after tree-ssa pass and I decided to implement
matching of various forms that are introduced by folder (fold_range_test):

1) if condition with equal operation:

   <bb 2> :
   if (argc_8(D) == 1)
     goto <bb 3>; [INV]
   else
     goto <bb 4>; [INV]

2) if condition with a range check:

   <bb 3> :
   _4 = c_13(D) + 198;
   if (_4 <= 1)
     goto <bb 7>; [INV]
   else
     goto <bb 4>; [INV]

3) mixture of 1) and 2) with a or condition:

   <bb 2> :
   _1 = aChar_8(D) == 1;
   _2 = aChar_8(D) == 10;
   _3 = _1 | _2;
   if (_3 != 0)
     goto <bb 5>; [INV]
   else
     goto <bb 3>; [INV]

   or:

   <bb 2> :
   aChar.1_1 = (unsigned int) aChar_10(D);
   _2 = aChar.1_1 + 4294967287;
   _3 = _2 <= 1;
   _4 = aChar_10(D) == 12;
   _5 = _3 | _4;
   if (_5 != 0)
     goto <bb 5>; [INV]
   else
     goto <bb 3>; [INV]

The motivation example in PR88702 is transformed now into:

IsHTMLWhitespace (int aChar)
{
   int iftmp.0_1;

   <bb 2> [local count: 1073741824]:
   switch (aChar_2(D)) <default: <L6> [50.00%], case 9 ... 10: <L7> [50.00%], case 12 ... 13: <L7> [50.00%], case 32: <L7> [50.00%]>

   <bb 3> [local count: 536870913]:
<L6>:

   <bb 4> [local count: 1073741824]:
   # iftmp.0_1 = PHI <1(2), 0(3)>
<L7>:
   return iftmp.0_1;

}

I'm also attaching if-elseif chains that are transformed in make all-host of the GCC compiler.
There are ~800 such transformations. The most beautiful transformation is this one:

$ cat -n gcc/c-family/c-common.c
...
   2895        /* This used to be a switch, but Genix compiler can't handle that.  */
   2896        if (code == NE_EXPR)
   2897          {
   2898            if (max_lt || min_gt)
   2899              val = truthvalue_true_node;
   2900          }
   2901        else if (code == EQ_EXPR)
   2902          {
   2903            if (max_lt || min_gt)
   2904              val = truthvalue_false_node;
   2905          }
...

Patch can bootstrap on x86_64-linux-gnu and survives regression tests.

Thoughts?
Thanks,
Martin


gcc/ChangeLog:

2019-11-04  Martin Liska  <[hidden email]>

        PR tree-optimization/14799
        PR ipa/88702
        * Makefile.in: Include new tree-if-to-switch.o.
        * common.opt: Document -ftree-if-to-switch.
        * doc/invoke.texi: Likewise.
        * opts.c: Enable the pass with -O2+.
        * passes.def: Add ne pass.
        * timevar.def (TV_TREE_IF_TO_SWITCH): Add new
        timevar.
        * tree-if-to-switch.c: New file.
        * tree-pass.h (make_pass_if_to_switch): New.

gcc/testsuite/ChangeLog:

2019-11-04  Martin Liska  <[hidden email]>

        PR tree-optimization/14799
        PR ipa/88702
        * gcc.dg/tree-ssa/if-to-switch-1.c: New test.
        * gcc.dg/tree-ssa/if-to-switch-2.c: New test.
        * gcc.dg/tree-ssa/if-to-switch-3.c: New test.
        * gcc.dg/tree-ssa/if-to-switch-4.c: New test.
        * gcc.dg/tree-ssa/if-to-switch-5.c: New test.
        * gcc.dg/tree-ssa/reassoc-32.c: Disable tree-if-to-switch
        in order to transform the range test.
        * gcc.dg/tree-ssa/reassoc-33.c: Likewise.
---
  gcc/Makefile.in                               |   1 +
  gcc/common.opt                                |   4 +
  gcc/doc/invoke.texi                           |  10 +-
  gcc/opts.c                                    |   1 +
  gcc/passes.def                                |   1 +
  .../gcc.dg/tree-ssa/if-to-switch-1.c          |  35 +
  .../gcc.dg/tree-ssa/if-to-switch-2.c          |  11 +
  .../gcc.dg/tree-ssa/if-to-switch-3.c          |  11 +
  .../gcc.dg/tree-ssa/if-to-switch-4.c          |  35 +
  .../gcc.dg/tree-ssa/if-to-switch-5.c          |  12 +
  gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c    |   2 +-
  gcc/testsuite/gcc.dg/tree-ssa/reassoc-33.c    |   2 +-
  gcc/timevar.def                               |   1 +
  gcc/tree-if-to-switch.c                       | 611 ++++++++++++++++++
  gcc/tree-pass.h                               |   1 +
  15 files changed, 735 insertions(+), 3 deletions(-)
  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c
  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c
  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c
  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c
  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c
  create mode 100644 gcc/tree-if-to-switch.c



0001-Add-if-chain-to-switch-conversion-pass.patch (27K) Download Attachment
if-to-switch-in-gcc.txt (125K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Add if-chain to switch conversion pass.

Jakub Jelinek
On Mon, Nov 04, 2019 at 03:23:20PM +0100, Martin Liška wrote:
> The patch adds a new pass that identifies a series of if-elseif
> statements and transform then into a GIMPLE switch (if possible).
> The pass runs right after tree-ssa pass and I decided to implement
> matching of various forms that are introduced by folder (fold_range_test):

Not a review, just a few questions:

1) what does it do if __builtin_expect* has been used, does it preserve
   the probabilities and if in the end decides to expand as ifs, are those
   probabilities retained through it?
2) for the reassoc-*.c testcases, do you get identical or better code
   with the patch?
3) shouldn't it be gimple-if-to-switch.c instead?
4) what code size effect does the patch have say on cc1plus (if you don't
   count the code changes of the patch itself, i.e. revert the patch in the
   stage3 and rebuild just the stage3)?

> +struct case_range
> +{
> +  /* Default constructor.  */
> +  case_range ():
> +    m_min (NULL_TREE), m_max (NULL_TREE)

I admit I'm never sure about coding conventions for C++,
but shouldn't there be a space before :, or even better :
be on the next line before m_min ?

        Jakub

Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Add if-chain to switch conversion pass.

Richard Biener-2
On Mon, Nov 4, 2019 at 3:49 PM Jakub Jelinek <[hidden email]> wrote:
>
> On Mon, Nov 04, 2019 at 03:23:20PM +0100, Martin Liška wrote:
> > The patch adds a new pass that identifies a series of if-elseif
> > statements and transform then into a GIMPLE switch (if possible).
> > The pass runs right after tree-ssa pass and I decided to implement
> > matching of various forms that are introduced by folder (fold_range_test):
>
> Not a review, just a few questions:

Likewise - please do not name switches -ftree-*, 'tree' doens't add anything
but confusion to users.  Thus use -fif-to-switch or -fconvert-if-to-switch

+The transformation can help to produce a faster code for
+the switch statement.

produce faster code.

Doesn't it also produce smaller code eventually?

Please to not put code transform passes into build_ssa_passes (why did
you choose this place)?  The pass should go into pass_all_early_optimizations
instead, and I'm quite sure you want to run _after_ CSE.  I'd even say
that the pass should run as part of switch-conversion, so we build
a representation of a switch internally and then code-generate the optimal
form directly.  For now just put the pass before switch-conversion.

There are functions without comments in the patch and you copied
from DSE which shows in confusing comments left over from the original.

+  mark_virtual_operands_for_renaming (cfun);

if you did nothing renaming all vops is expensive.

I'm missing an overall comment - you are using a dominator walk
but do nothing in the after hook which means you are not really
gathering any data?  You're also setting visited bits on BBs which
means you are visiting alternate BBs during the DOM walk.

> 1) what does it do if __builtin_expect* has been used, does it preserve
>    the probabilities and if in the end decides to expand as ifs, are those
>    probabilities retained through it?
> 2) for the reassoc-*.c testcases, do you get identical or better code
>    with the patch?
> 3) shouldn't it be gimple-if-to-switch.c instead?
> 4) what code size effect does the patch have say on cc1plus (if you don't
>    count the code changes of the patch itself, i.e. revert the patch in the
>    stage3 and rebuild just the stage3)?
>
> > +struct case_range
> > +{
> > +  /* Default constructor.  */
> > +  case_range ():
> > +    m_min (NULL_TREE), m_max (NULL_TREE)
>
> I admit I'm never sure about coding conventions for C++,
> but shouldn't there be a space before :, or even better :
> be on the next line before m_min ?
>
>         Jakub
>
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Add if-chain to switch conversion pass.

Bernhard Reutner-Fischer
On Tue, 5 Nov 2019 13:38:27 +0100
Richard Biener <[hidden email]> wrote:

> On Mon, Nov 4, 2019 at 3:49 PM Jakub Jelinek <[hidden email]> wrote:
> >
> > On Mon, Nov 04, 2019 at 03:23:20PM +0100, Martin Liška wrote:  
> > > The patch adds a new pass that identifies a series of if-elseif
> > > statements and transform then into a GIMPLE switch (if possible).
> > > The pass runs right after tree-ssa pass and I decided to implement
> > > matching of various forms that are introduced by folder (fold_range_test):  
> >
> > Not a review, just a few questions:  
>
> Likewise - please do not name switches -ftree-*, 'tree' doens't add anything
> but confusion to users.  Thus use -fif-to-switch or -fconvert-if-to-switch
>
> +The transformation can help to produce a faster code for
> +the switch statement.
>
> produce faster code.
>
> Doesn't it also produce smaller code eventually?
>
> Please to not put code transform passes into build_ssa_passes (why did
> you choose this place)?  The pass should go into pass_all_early_optimizations
> instead, and I'm quite sure you want to run _after_ CSE.  I'd even say
> that the pass should run as part of switch-conversion, so we build
> a representation of a switch internally and then code-generate the optimal
> form directly.  For now just put the pass before switch-conversion.

Also why do you punt on duplicate conditions like in

> +++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c

> +int main(int argc, char **argv)
> +{
> +  if (argc == 1)
> +  else if (argc == 2)
> +  else if (argc == 3)
> +  else if (argc == 4)
> +  else if (argc == 1)
> +    {

This block is dead, isn't it. Why don't you just discard it but punt?

> +      global = 2;
> +    }
> +  else
> +    global -= 123;

thanks,

>
> There are functions without comments in the patch and you copied
> from DSE which shows in confusing comments left over from the original.
>
> +  mark_virtual_operands_for_renaming (cfun);
>
> if you did nothing renaming all vops is expensive.
>
> I'm missing an overall comment - you are using a dominator walk
> but do nothing in the after hook which means you are not really
> gathering any data?  You're also setting visited bits on BBs which
> means you are visiting alternate BBs during the DOM walk.
>
> > 1) what does it do if __builtin_expect* has been used, does it preserve
> >    the probabilities and if in the end decides to expand as ifs, are those
> >    probabilities retained through it?
> > 2) for the reassoc-*.c testcases, do you get identical or better code
> >    with the patch?
> > 3) shouldn't it be gimple-if-to-switch.c instead?
> > 4) what code size effect does the patch have say on cc1plus (if you don't
> >    count the code changes of the patch itself, i.e. revert the patch in the
> >    stage3 and rebuild just the stage3)?
> >  
> > > +struct case_range
> > > +{
> > > +  /* Default constructor.  */
> > > +  case_range ():
> > > +    m_min (NULL_TREE), m_max (NULL_TREE)  
> >
> > I admit I'm never sure about coding conventions for C++,
> > but shouldn't there be a space before :, or even better :
> > be on the next line before m_min ?
> >
> >         Jakub
> >  

Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Add if-chain to switch conversion pass.

Martin Liška-2
In reply to this post by Jakub Jelinek
On 11/4/19 3:48 PM, Jakub Jelinek wrote:
> On Mon, Nov 04, 2019 at 03:23:20PM +0100, Martin Liška wrote:
>> The patch adds a new pass that identifies a series of if-elseif
>> statements and transform then into a GIMPLE switch (if possible).
>> The pass runs right after tree-ssa pass and I decided to implement
>> matching of various forms that are introduced by folder (fold_range_test):
>
> Not a review, just a few questions:

Hello.

Thank you for it.

>
> 1) what does it do if __builtin_expect* has been used, does it preserve
>     the probabilities and if in the end decides to expand as ifs, are those
>     probabilities retained through it?

No, it's currently not supported. I can consider adding that as a follow up.

> 2) for the reassoc-*.c testcases, do you get identical or better code
>     with the patch?

The code is the following:

Before:
Optimizing range tests a_5(D) -[10, 10] and -[26, 26]
  into (a_5(D) & -17) != 10

   <bb 2> [local count: 1073741823]:
   _11 = a_5(D) & -17;
   _12 = _11 == 10;
   _1 = a_5(D) == 10;
   _2 = a_5(D) == 12;
   _10 = a_5(D) == 26;
   _9 = _2 | _12;
   if (_9 != 0)
     goto <bb 4>; [56.44%]
   else
     goto <bb 3>; [43.56%]

After:

   <bb 2> [local count: 1073741824]:
   switch (a_2(D)) <default: <L5> [50.00%], case 10: <L6> [50.00%], case 12: <L6> [50.00%], case 26: <L6> [50.00%]>

As seen, reassoc can generate a different range check and then it's about cmp1 | cmp2 | ..
I bet the explicit gswitch is quite equal representation.

> 3) shouldn't it be gimple-if-to-switch.c instead?

Yes, I renamed that.

> 4) what code size effect does the patch have say on cc1plus (if you don't
>     count the code changes of the patch itself, i.e. revert the patch in the
>     stage3 and rebuild just the stage3)?

I've just measures that and it's about:

      VM SIZE                      FILE SIZE
  ++++++++++++++ GROWING        ++++++++++++++
   +0.3% +24.8Ki .rodata        +24.8Ki  +0.3%
   [ = ]       0 .debug_loc     +17.4Ki  +0.0%
   [ = ]       0 .debug_line    +8.77Ki  +0.0%
   +0.0% +2.52Ki .text          +2.52Ki  +0.0%
   +0.1% +1.66Ki .eh_frame      +1.66Ki  +0.1%
   [ = ]       0 .symtab           +216  +0.0%
   [ = ]       0 .debug_abbrev      +32  +0.0%
   +0.0%     +16 .eh_frame_hdr      +16  +0.0%

   +0.1% +29.0Ki TOTAL          +44.7Ki  +0.0%

Martin

>
>> +struct case_range
>> +{
>> +  /* Default constructor.  */
>> +  case_range ():
>> +    m_min (NULL_TREE), m_max (NULL_TREE)
>
> I admit I'm never sure about coding conventions for C++,
> but shouldn't there be a space before :, or even better :
> be on the next line before m_min ?
>
> Jakub
>

Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Add if-chain to switch conversion pass.

Michael Matz
Hi,

On Wed, 13 Nov 2019, Martin Liška wrote:

> > Not a review, just a few questions:
>
> Hello.
>
> Thank you for it.
>
> >
> > 1) what does it do if __builtin_expect* has been used, does it preserve
> >     the probabilities and if in the end decides to expand as ifs, are those
> >     probabilities retained through it?
>
> No, it's currently not supported. I can consider adding that as a follow up.
But given that you apply the transformation even to small if ladders this
looses quite some info then.

> > 2) for the reassoc-*.c testcases, do you get identical or better code
> >     with the patch?
>
> The code is the following:
>
> Before:
> Optimizing range tests a_5(D) -[10, 10] and -[26, 26]
>  into (a_5(D) & -17) != 10
>
>   <bb 2> [local count: 1073741823]:
>   _11 = a_5(D) & -17;
>   _12 = _11 == 10;
>   _1 = a_5(D) == 10;
>   _2 = a_5(D) == 12;
>   _10 = a_5(D) == 26;
>   _9 = _2 | _12;
>   if (_9 != 0)
>     goto <bb 4>; [56.44%]
>   else
>     goto <bb 3>; [43.56%]
>
> After:
>
>   <bb 2> [local count: 1073741824]:
>   switch (a_2(D)) <default: <L5> [50.00%], case 10: <L6> [50.00%], case 12:
>   <L6> [50.00%], case 26: <L6> [50.00%]>
And here I bet that Jakub was asking for final code, not intermediate
code.  In particular the bit trick with transforming a test for
a \in {10,26} into (a&-17)==10.  The switch still tests for 10,26, and in
the end it should be ensured that the same trickery is employed to
actually implement the switch.

> As seen, reassoc can generate a different range check and then it's about cmp1
> | cmp2 | ..
> I bet the explicit gswitch is quite equal representation.

As long as the final code is the same or better, sure.  Otherwise it's a
more canonical representation with suboptimal expansion, and the latter
should be fixed otherwise it's introducing a regression.


Ciao,
Michael.
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Add if-chain to switch conversion pass.

Martin Liška-2
In reply to this post by Richard Biener-2
On 11/5/19 1:38 PM, Richard Biener wrote:
> On Mon, Nov 4, 2019 at 3:49 PM Jakub Jelinek <[hidden email]> wrote:
>>
>> On Mon, Nov 04, 2019 at 03:23:20PM +0100, Martin Liška wrote:
>>> The patch adds a new pass that identifies a series of if-elseif
>>> statements and transform then into a GIMPLE switch (if possible).
>>> The pass runs right after tree-ssa pass and I decided to implement
>>> matching of various forms that are introduced by folder (fold_range_test):
>>
>> Not a review, just a few questions:

Hello.

>
> Likewise - please do not name switches -ftree-*, 'tree' doens't add anything
> but confusion to users.  Thus use -fif-to-switch or -fconvert-if-to-switch

Agree with you, I selected the later option.

>
> +The transformation can help to produce a faster code for
> +the switch statement.
>
> produce faster code.

Fixed.

>
> Doesn't it also produce smaller code eventually?

In some situation yes, but generally it leads to more jump tables
(which are bigger when expanded).

>
> Please to not put code transform passes into build_ssa_passes (why did
> you choose this place)?

Well, that was my initial pass selection as I wanted to have a GIMPLE
code close to what FEs produce.

>  The pass should go into pass_all_early_optimizations
> instead, and I'm quite sure you want to run _after_ CSE.  I'd even say
> that the pass should run as part of switch-conversion, so we build
> a representation of a switch internally and then code-generate the optimal
> form directly.  For now just put the pass before switch-conversion.

But yes, the suggested place is much better place and we can benefit from
VRP (that will kill dead conditions in a if-else chain)

>
> There are functions without comments in the patch and you copied
> from DSE which shows in confusing comments left over from the original.
>
> +  mark_virtual_operands_for_renaming (cfun);
>
> if you did nothing renaming all vops is expensive.

This one is needed for situations like:

fn1 ()
{
   <unnamed type> a.0_1;

   <bb 2> :
   # VUSE <.MEM_5(D)>
   a.0_1 = a;
   if (a.0_1 == 0)
     goto <bb 6>; [INV]
   else
     goto <bb 3>; [INV]

   <bb 3> :
   if (a.0_1 == 1)
     goto <bb 6>; [INV]
   else
     goto <bb 4>; [INV]

   <bb 4> :
   if (a.0_1 == 2)
     goto <bb 5>; [INV]
   else
     goto <bb 6>; [INV]

   <bb 5> :
   # .MEM_6 = VDEF <.MEM_5(D)>
   fn2 ();

   <bb 6> :
   # .MEM_4 = PHI <.MEM_5(D)(2), .MEM_5(D)(3), .MEM_5(D)(4), .MEM_6(5)>
   # VUSE <.MEM_4>
   return;

}

where without the call, I end up with:

   <bb 2> :
   # VUSE <.MEM_5(D)>
   a.0_1 = a;
   switch (a.0_1) <default: <L8> [INV], case 0: <L8> [INV], case 1: <L8> [INV], case 2: <L9> [INV]>

   <bb 3> :
<L9>:
   # .MEM_6 = VDEF <.MEM_5(D)>
   fn2 ();

   <bb 4> :
   # .MEM_4 = PHI <.MEM_6(3), (2)>


>
> I'm missing an overall comment - you are using a dominator walk
> but do nothing in the after hook which means you are not really
> gathering any data?  You're also setting visited bits on BBs which
> means you are visiting alternate BBs during the DOM walk.

You are right, I'm a bit cheating with the DOM walk as I also mark visited BBs.
What I want is for each if-else condition, I want to visit the first IF in such
chain. That's why I decided to iterate in DOMINATOR order.
Can I do it simpler?

Thanks,
Martin

>
>> 1) what does it do if __builtin_expect* has been used, does it preserve
>>     the probabilities and if in the end decides to expand as ifs, are those
>>     probabilities retained through it?
>> 2) for the reassoc-*.c testcases, do you get identical or better code
>>     with the patch?
>> 3) shouldn't it be gimple-if-to-switch.c instead?
>> 4) what code size effect does the patch have say on cc1plus (if you don't
>>     count the code changes of the patch itself, i.e. revert the patch in the
>>     stage3 and rebuild just the stage3)?
>>
>>> +struct case_range
>>> +{
>>> +  /* Default constructor.  */
>>> +  case_range ():
>>> +    m_min (NULL_TREE), m_max (NULL_TREE)
>>
>> I admit I'm never sure about coding conventions for C++,
>> but shouldn't there be a space before :, or even better :
>> be on the next line before m_min ?
>>
>>          Jakub
>>

Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Add if-chain to switch conversion pass.

Martin Liška-2
In reply to this post by Bernhard Reutner-Fischer
On 11/6/19 10:02 PM, Bernhard Reutner-Fischer wrote:

> Also why do you punt on duplicate conditions like in
>
>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c
>> +int main(int argc, char **argv)
>> +{
>> +  if (argc == 1)
>> +  else if (argc == 2)
>> +  else if (argc == 3)
>> +  else if (argc == 4)
>> +  else if (argc == 1)
>> +    {
> This block is dead, isn't it. Why don't you just discard it but punt?
>

Hello.

After I moved the pass later in optimization pipeline, such dead conditions
are already gone. What's remaining are situations like:

if (argc >= 1 && argc <= 10)
...
else if (argc >= 8 && argc <= 15)

which are overlapping intervals. I'm not planning to handle these in the first
iteration of the patch.

Martin
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Add if-chain to switch conversion pass.

Martin Liška-2
In reply to this post by Michael Matz
On 11/13/19 4:43 PM, Michael Matz wrote:

> Hi,
>
> On Wed, 13 Nov 2019, Martin Liška wrote:
>
>>> Not a review, just a few questions:
>>
>> Hello.
>>
>> Thank you for it.
>>
>>>
>>> 1) what does it do if __builtin_expect* has been used, does it preserve
>>>      the probabilities and if in the end decides to expand as ifs, are those
>>>      probabilities retained through it?
>>
>> No, it's currently not supported. I can consider adding that as a follow up.
>
> But given that you apply the transformation even to small if ladders this
> looses quite some info then.

Yes. Based on my experiments, the patch does not convert if-else chain
with __builtin_expect* right now.

>
>>> 2) for the reassoc-*.c testcases, do you get identical or better code
>>>      with the patch?
>>
>> The code is the following:
>>
>> Before:
>> Optimizing range tests a_5(D) -[10, 10] and -[26, 26]
>>   into (a_5(D) & -17) != 10
>>
>>    <bb 2> [local count: 1073741823]:
>>    _11 = a_5(D) & -17;
>>    _12 = _11 == 10;
>>    _1 = a_5(D) == 10;
>>    _2 = a_5(D) == 12;
>>    _10 = a_5(D) == 26;
>>    _9 = _2 | _12;
>>    if (_9 != 0)
>>      goto <bb 4>; [56.44%]
>>    else
>>      goto <bb 3>; [43.56%]
>>
>> After:
>>
>>    <bb 2> [local count: 1073741824]:
>>    switch (a_2(D)) <default: <L5> [50.00%], case 10: <L6> [50.00%], case 12:
>>    <L6> [50.00%], case 26: <L6> [50.00%]>
>
> And here I bet that Jakub was asking for final code, not intermediate
> code.  In particular the bit trick with transforming a test for
> a \in {10,26} into (a&-17)==10.  The switch still tests for 10,26, and in
> the end it should be ensured that the same trickery is employed to
> actually implement the switch.

I agree that (a&-17)==10 is more elegant trick here ...

>
>> As seen, reassoc can generate a different range check and then it's about cmp1
>> | cmp2 | ..
>> I bet the explicit gswitch is quite equal representation.
>
> As long as the final code is the same or better, sure.  Otherwise it's a
> more canonical representation with suboptimal expansion, and the latter
> should be fixed otherwise it's introducing a regression.

... and yes, the gswitch expansion is not capable of such smart interval tests.
We can improve that in the future.

Martin

>
>
> Ciao,
> Michael.
>

Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Add if-chain to switch conversion pass.

Richard Biener-2
In reply to this post by Martin Liška-2
On Thu, Nov 14, 2019 at 10:39 AM Martin Liška <[hidden email]> wrote:

>
> On 11/5/19 1:38 PM, Richard Biener wrote:
> > On Mon, Nov 4, 2019 at 3:49 PM Jakub Jelinek <[hidden email]> wrote:
> >>
> >> On Mon, Nov 04, 2019 at 03:23:20PM +0100, Martin Liška wrote:
> >>> The patch adds a new pass that identifies a series of if-elseif
> >>> statements and transform then into a GIMPLE switch (if possible).
> >>> The pass runs right after tree-ssa pass and I decided to implement
> >>> matching of various forms that are introduced by folder (fold_range_test):
> >>
> >> Not a review, just a few questions:
>
> Hello.
>
> >
> > Likewise - please do not name switches -ftree-*, 'tree' doens't add anything
> > but confusion to users.  Thus use -fif-to-switch or -fconvert-if-to-switch
>
> Agree with you, I selected the later option.
>
> >
> > +The transformation can help to produce a faster code for
> > +the switch statement.
> >
> > produce faster code.
>
> Fixed.
>
> >
> > Doesn't it also produce smaller code eventually?
>
> In some situation yes, but generally it leads to more jump tables
> (which are bigger when expanded).
>
> >
> > Please to not put code transform passes into build_ssa_passes (why did
> > you choose this place)?
>
> Well, that was my initial pass selection as I wanted to have a GIMPLE
> code close to what FEs produce.
>
> >  The pass should go into pass_all_early_optimizations
> > instead, and I'm quite sure you want to run _after_ CSE.  I'd even say
> > that the pass should run as part of switch-conversion, so we build
> > a representation of a switch internally and then code-generate the optimal
> > form directly.  For now just put the pass before switch-conversion.
>
> But yes, the suggested place is much better place and we can benefit from
> VRP (that will kill dead conditions in a if-else chain)
>
> >
> > There are functions without comments in the patch and you copied
> > from DSE which shows in confusing comments left over from the original.
> >
> > +  mark_virtual_operands_for_renaming (cfun);
> >
> > if you did nothing renaming all vops is expensive.
>
> This one is needed for situations like:
>
> fn1 ()
> {
>    <unnamed type> a.0_1;
>
>    <bb 2> :
>    # VUSE <.MEM_5(D)>
>    a.0_1 = a;
>    if (a.0_1 == 0)
>      goto <bb 6>; [INV]
>    else
>      goto <bb 3>; [INV]
>
>    <bb 3> :
>    if (a.0_1 == 1)
>      goto <bb 6>; [INV]
>    else
>      goto <bb 4>; [INV]
>
>    <bb 4> :
>    if (a.0_1 == 2)
>      goto <bb 5>; [INV]
>    else
>      goto <bb 6>; [INV]
>
>    <bb 5> :
>    # .MEM_6 = VDEF <.MEM_5(D)>
>    fn2 ();
>
>    <bb 6> :
>    # .MEM_4 = PHI <.MEM_5(D)(2), .MEM_5(D)(3), .MEM_5(D)(4), .MEM_6(5)>
>    # VUSE <.MEM_4>
>    return;
>
> }
>
> where without the call, I end up with:
>
>    <bb 2> :
>    # VUSE <.MEM_5(D)>
>    a.0_1 = a;
>    switch (a.0_1) <default: <L8> [INV], case 0: <L8> [INV], case 1: <L8> [INV], case 2: <L9> [INV]>
>
>    <bb 3> :
> <L9>:
>    # .MEM_6 = VDEF <.MEM_5(D)>
>    fn2 ();
>
>    <bb 4> :
>    # .MEM_4 = PHI <.MEM_6(3), (2)>

I meant you are doing it unconditionally even if you didn't transform
any if-then-else chain.

>
> >
> > I'm missing an overall comment - you are using a dominator walk
> > but do nothing in the after hook which means you are not really
> > gathering any data?  You're also setting visited bits on BBs which
> > means you are visiting alternate BBs during the DOM walk.
>
> You are right, I'm a bit cheating with the DOM walk as I also mark visited BBs.
> What I want is for each if-else condition, I want to visit the first IF in such
> chain. That's why I decided to iterate in DOMINATOR order.
> Can I do it simpler?

Put that in a comment, do away with domwalk and instead start from
ENTRY_BLOCK, using a worklist seeded by {first,next}_dom_son ()
and avoid putting visited blocks on that worklist.

Btw, what about if-chains nested in another if-chain?  Don't you want to
transform "inner" chains first or does it really not matter (you're adjusting
the CFG, doing that inside the domwalk is fishy since that also uses
pre-computed RPO order; the simple dom-son walking should work
but you of course might miss some blocks depending on how you set up
things).

Richard.

> Thanks,
> Martin
>
> >
> >> 1) what does it do if __builtin_expect* has been used, does it preserve
> >>     the probabilities and if in the end decides to expand as ifs, are those
> >>     probabilities retained through it?
> >> 2) for the reassoc-*.c testcases, do you get identical or better code
> >>     with the patch?
> >> 3) shouldn't it be gimple-if-to-switch.c instead?
> >> 4) what code size effect does the patch have say on cc1plus (if you don't
> >>     count the code changes of the patch itself, i.e. revert the patch in the
> >>     stage3 and rebuild just the stage3)?
> >>
> >>> +struct case_range
> >>> +{
> >>> +  /* Default constructor.  */
> >>> +  case_range ():
> >>> +    m_min (NULL_TREE), m_max (NULL_TREE)
> >>
> >> I admit I'm never sure about coding conventions for C++,
> >> but shouldn't there be a space before :, or even better :
> >> be on the next line before m_min ?
> >>
> >>          Jakub
> >>
>
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Add if-chain to switch conversion pass.

Bernhard Reutner-Fischer
In reply to this post by Martin Liška-2
On Thu, 14 Nov 2019 10:41:25 +0100
Martin Liška <[hidden email]> wrote:

> On 11/6/19 10:02 PM, Bernhard Reutner-Fischer wrote:
> > Also why do you punt on duplicate conditions like in
> >  
> >> +++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c
> >> +int main(int argc, char **argv)
> >> +{
> >> +  if (argc == 1)
> >> +  else if (argc == 2)
> >> +  else if (argc == 3)
> >> +  else if (argc == 4)
> >> +  else if (argc == 1)
> >> +    {  
> > This block is dead, isn't it. Why don't you just discard it but punt?
> >  
>
> Hello.
>
> After I moved the pass later in optimization pipeline, such dead conditions

nice

> are already gone. What's remaining are situations like:
>
> if (argc >= 1 && argc <= 10)
> ...
> else if (argc >= 8 && argc <= 15)
>
> which are overlapping intervals. I'm not planning to handle these in the first
> iteration of the patch.

yea. Later when we see a new interval overlapping old, we can adjust
the new to clamp to the intersection of old and new. We'd need to
generate one or more artificial intervals covering the delta interval
with the body of new if we find intervening previous intervals, which
complicates things more than a first attempt of a patch should
supposedly do, agree. One step at a time :)

thanks for moving it later in the pipeline!
cheers,
Reply | Threaded
Open this post in threaded view
|

Re: [PATCH] Add if-chain to switch conversion pass.

Martin Liška-2
In reply to this post by Richard Biener-2
On 11/14/19 11:37 AM, Richard Biener wrote:

> On Thu, Nov 14, 2019 at 10:39 AM Martin Liška <[hidden email]> wrote:
>>
>> On 11/5/19 1:38 PM, Richard Biener wrote:
>>> On Mon, Nov 4, 2019 at 3:49 PM Jakub Jelinek <[hidden email]> wrote:
>>>>
>>>> On Mon, Nov 04, 2019 at 03:23:20PM +0100, Martin Liška wrote:
>>>>> The patch adds a new pass that identifies a series of if-elseif
>>>>> statements and transform then into a GIMPLE switch (if possible).
>>>>> The pass runs right after tree-ssa pass and I decided to implement
>>>>> matching of various forms that are introduced by folder (fold_range_test):
>>>>
>>>> Not a review, just a few questions:
>>
>> Hello.
>>
>>>
>>> Likewise - please do not name switches -ftree-*, 'tree' doens't add anything
>>> but confusion to users.  Thus use -fif-to-switch or -fconvert-if-to-switch
>>
>> Agree with you, I selected the later option.
>>
>>>
>>> +The transformation can help to produce a faster code for
>>> +the switch statement.
>>>
>>> produce faster code.
>>
>> Fixed.
>>
>>>
>>> Doesn't it also produce smaller code eventually?
>>
>> In some situation yes, but generally it leads to more jump tables
>> (which are bigger when expanded).
>>
>>>
>>> Please to not put code transform passes into build_ssa_passes (why did
>>> you choose this place)?
>>
>> Well, that was my initial pass selection as I wanted to have a GIMPLE
>> code close to what FEs produce.
>>
>>>   The pass should go into pass_all_early_optimizations
>>> instead, and I'm quite sure you want to run _after_ CSE.  I'd even say
>>> that the pass should run as part of switch-conversion, so we build
>>> a representation of a switch internally and then code-generate the optimal
>>> form directly.  For now just put the pass before switch-conversion.
>>
>> But yes, the suggested place is much better place and we can benefit from
>> VRP (that will kill dead conditions in a if-else chain)
>>
>>>
>>> There are functions without comments in the patch and you copied
>>> from DSE which shows in confusing comments left over from the original.
>>>
>>> +  mark_virtual_operands_for_renaming (cfun);
>>>
>>> if you did nothing renaming all vops is expensive.
>>
>> This one is needed for situations like:
>>
>> fn1 ()
>> {
>>     <unnamed type> a.0_1;
>>
>>     <bb 2> :
>>     # VUSE <.MEM_5(D)>
>>     a.0_1 = a;
>>     if (a.0_1 == 0)
>>       goto <bb 6>; [INV]
>>     else
>>       goto <bb 3>; [INV]
>>
>>     <bb 3> :
>>     if (a.0_1 == 1)
>>       goto <bb 6>; [INV]
>>     else
>>       goto <bb 4>; [INV]
>>
>>     <bb 4> :
>>     if (a.0_1 == 2)
>>       goto <bb 5>; [INV]
>>     else
>>       goto <bb 6>; [INV]
>>
>>     <bb 5> :
>>     # .MEM_6 = VDEF <.MEM_5(D)>
>>     fn2 ();
>>
>>     <bb 6> :
>>     # .MEM_4 = PHI <.MEM_5(D)(2), .MEM_5(D)(3), .MEM_5(D)(4), .MEM_6(5)>
>>     # VUSE <.MEM_4>
>>     return;
>>
>> }
>>
>> where without the call, I end up with:
>>
>>     <bb 2> :
>>     # VUSE <.MEM_5(D)>
>>     a.0_1 = a;
>>     switch (a.0_1) <default: <L8> [INV], case 0: <L8> [INV], case 1: <L8> [INV], case 2: <L9> [INV]>
>>
>>     <bb 3> :
>> <L9>:
>>     # .MEM_6 = VDEF <.MEM_5(D)>
>>     fn2 ();
>>
>>     <bb 4> :
>>     # .MEM_4 = PHI <.MEM_6(3), (2)>
>
> I meant you are doing it unconditionally even if you didn't transform
> any if-then-else chain.
Ah, I've got it ;)

>
>>
>>>
>>> I'm missing an overall comment - you are using a dominator walk
>>> but do nothing in the after hook which means you are not really
>>> gathering any data?  You're also setting visited bits on BBs which
>>> means you are visiting alternate BBs during the DOM walk.
>>
>> You are right, I'm a bit cheating with the DOM walk as I also mark visited BBs.
>> What I want is for each if-else condition, I want to visit the first IF in such
>> chain. That's why I decided to iterate in DOMINATOR order.
>> Can I do it simpler?
>
> Put that in a comment, do away with domwalk and instead start from
> ENTRY_BLOCK, using a worklist seeded by {first,next}_dom_son ()
> and avoid putting visited blocks on that worklist.
Rewritten to that pattern. Thank you for it, the code is much smaller as
the dom walker is really not needed.

>
> Btw, what about if-chains nested in another if-chain?

Yes, it's supported. Actually the comparison BBs in a pair of if-chains
can't overlap, so all is fine and we can't mess up CFG. Moreover, I first
walk the DOM, analyze all if-chains and later then all the candidates are
transformed.

> Don't you want to
> transform "inner" chains first or does it really not matter (you're adjusting
> the CFG, doing that inside the domwalk is fishy since that also uses
> pre-computed RPO order; the simple dom-son walking should work
> but you of course might miss some blocks depending on how you set up
> things).

As explained, it's not a deal.

Patch can bootstrap on x86_64-linux-gnu and survives regression tests. I'm also sending
dump for make all-host.

Ready to be installed?
Thanks,
Martin

>
> Richard.
>
>> Thanks,
>> Martin
>>
>>>
>>>> 1) what does it do if __builtin_expect* has been used, does it preserve
>>>>      the probabilities and if in the end decides to expand as ifs, are those
>>>>      probabilities retained through it?
>>>> 2) for the reassoc-*.c testcases, do you get identical or better code
>>>>      with the patch?
>>>> 3) shouldn't it be gimple-if-to-switch.c instead?
>>>> 4) what code size effect does the patch have say on cc1plus (if you don't
>>>>      count the code changes of the patch itself, i.e. revert the patch in the
>>>>      stage3 and rebuild just the stage3)?
>>>>
>>>>> +struct case_range
>>>>> +{
>>>>> +  /* Default constructor.  */
>>>>> +  case_range ():
>>>>> +    m_min (NULL_TREE), m_max (NULL_TREE)
>>>>
>>>> I admit I'm never sure about coding conventions for C++,
>>>> but shouldn't there be a space before :, or even better :
>>>> be on the next line before m_min ?
>>>>
>>>>           Jakub
>>>>
>>


if-to-switch-in-gcc.txt (302K) Download Attachment
0001-Add-if-chain-to-switch-conversion-pass.patch (35K) Download Attachment