[Bug c++/103429] New: Optimization of Auto-generated condition chain is not giving good lookup tables.

[Bug c++/103429] New: Optimization of Auto-generated condition chain is not giving good lookup tables.

[ed at edwardrosten dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429

            Bug ID: 103429
           Summary: Optimization of Auto-generated condition chain is not
                    giving good lookup tables.
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: ed at edwardrosten dot com
  Target Milestone: ---

I've got come generated condition chains (using recursive templates) and am
getting some odd/suboptimal optimization results. Code is provided below and
with a godbolt link.

In the first case (without a force inline), the compiler inlines the functions
but does not perform condition chain optimization. In the second case
(identical code but with force inline), it will optimize condition chains but
only with exactly 5 elements. Otherwise it will end up with an if-else
structure indexing optimized 5 element condition chains, and an if-else chain
for anything spare.

It only attempts the optimization from gcc 11 onwards, I checked on trunk too.


Example:
https://godbolt.org/z/c9xbPqq7r

Here's the code:
template<int I> void f();

constexpr int N=5;

template<int I=0> 
static inline void f_dispatch(int i){
    if constexpr (I == N)
        return;
    else if(i == I)
        f<I>();
    else
        f_dispatch<I+1>(i);
}

template<int I=0> __attribute__((always_inline)) 
static inline void f_dispatch_always_inline(int i){
    if constexpr (I == N)
        return;
    else if(i == I)
        f<I>();
    else
        f_dispatch_always_inline<I+1>(i);
}

void run(int i){
    f_dispatch<>(i);
}

void run_inline(int i){
    f_dispatch_always_inline<>(i);
}

[Bug tree-optimization/103429] Optimization of Auto-generated condition chain is not giving good lookup tables.

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c++                         |tree-optimization
                 CC|                            |marxin at gcc dot gnu.org

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Sounds like if-to-switch / switch conversion could help.  Note that GCC
converts large switches into binary if trees in some cases as well.

[Bug tree-optimization/103429] Optimization of Auto-generated condition chain is not giving good lookup tables.

[ed at edwardrosten dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429

--- Comment #2 from Edward Rosten <ed at edwardrosten dot com> ---
It is doing if-to-switch, but only really with N=5, and only if force-inline is
set. I think this are two problems, one is that you need to force-inline in
order to trigger if-to-switch.

The other problem is that the if-to-switch conversion triggered only works well
for exactly 5 conditions, otherwise it uses a mix of converted and unconverted.
It doesn't appear to be doing binary tree generation, more like linear search
Here's the asm for N=7:

run(int):
        ret
run_inline(int):
        test    edi, edi
        je      .L13
        cmp     edi, 1
        je      .L14
        cmp     edi, 6
        ja      .L3
        mov     edi, edi
        jmp     [QWORD PTR .L8[0+rdi*8]]
.L8:
        .quad   .L3
        .quad   .L3
        .quad   .L12
        .quad   .L11
        .quad   .L10
        .quad   .L9
        .quad   .L7
.L13:
        jmp     void f<0>()
.L7:
        jmp     void f<6>()
.L12:
        jmp     void f<2>()
.L11:
        jmp     void f<3>()
.L10:
        jmp     void f<4>()
.L9:
        jmp     void f<5>()
.L14:
        jmp     void f<1>()
.L3:
        ret

Note, it's essentially doing:

if(i==0)
    f<0>();
else if(i==1)
    f<1>();
else if(i > 6)
    return;
else switch(i){
    case 0:
    case 1:   
        return;
    case 2: f<2>(); return;
    case 3: f<3>(); return;
    case 4: f<4>(); return;
    case 5: f<5>(); return;
    case 6: f<6>(); return;
}

It's not doing binary searches. For, e.g. N%5 == 1, the structure is more like:

if(i==0)
    f<0>();
else if(i > 5){
    if(i-5 > 4){
        if(i-11>4){
            if(i-16 > 4){ 
                 // and so on, linearly
            }
            else switch(i-16){
                 //...
            }
        }
        else switch(i-11){
           //...
        }
    }
    else switch(i-6){
      //...
    }

}
else switch(i){
    case 0:
        return;
    case 1: f<1>(); return;  
    case 2: f<2>(); return;
    case 3: f<3>(); return;
    case 4: f<4>(); return;
    case 5: f<5>(); return;
}

[Bug tree-optimization/103429] Optimization of Auto-generated condition chain is not giving good lookup tables.

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-11-25
           Assignee|unassigned at gcc dot gnu.org      |marxin at gcc dot gnu.org
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |ASSIGNED

--- Comment #3 from Martin Liška <marxin at gcc dot gnu.org> ---
Looking into it.

[Bug tree-optimization/103429] Optimization of Auto-generated condition chain is not giving good lookup tables.

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429

--- Comment #4 from Martin Liška <marxin at gcc dot gnu.org> ---
So it's very funny what's happening here. iftoswitch pass is called for all
e.g.
f_dispatch_always_inline<10>, f_dispatch_always_inline<9> and so on until
f_dispatch_always_inline<5> which is converted to switch.
And then all early passes are called for f_dispatch_always_inline<4> which
include einline and we end up with:

__attribute__((always_inline))
void f_dispatch_always_inline<4> (int i)
{
  <bb 2> :
  if (i_2(D) == 4)
    goto <bb 3>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 3> :
  f<4> ();
  goto <bb 11>; [INV]

  <bb 4> :
  switch (i_2(D)) <default: <L9> [16.67%], case 5: <L3> [16.67%], case 6: <L4>
[16.67%], case 7: <L5> [16.67%], case 8: <L6> [16.67%], case 9: <L7> [16.67%]>

  <bb 5> :
<L3>:
  f<5> ();
  goto <bb 11>; [100.00%]

  <bb 6> :
<L4>:
  f<6> ();
  goto <bb 11>; [100.00%]

  <bb 7> :
<L5>:
  f<7> ();
  goto <bb 11>; [100.00%]

  <bb 8> :
<L6>:
  f<8> ();
  goto <bb 11>; [100.00%]

  <bb 9> :
<L7>:
  f<9> ();

  <bb 11> :
<L9>:
  return;

}

which is a mixture of if and switch statements.

So what we basically need is if-to-switch hybrid support for if-else chain
combined with switches.

[Bug tree-optimization/103429] Optimization of Auto-generated condition chain is not giving good lookup tables.

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

[Bug tree-optimization/103429] Optimization of Auto-generated condition chain is not giving good lookup tables.

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |13.0

[Bug tree-optimization/103429] Optimization of Auto-generated condition chain is not giving good lookup tables.

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|marxin at gcc dot gnu.org          |unassigned at gcc dot gnu.org
             Status|ASSIGNED                    |NEW

[Bug tree-optimization/103429] Optimization of Auto-generated condition chain is not giving good lookup tables.

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|13.0                        |13.2

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 13.1 is being released, retargeting bugs to GCC 13.2.

[Bug tree-optimization/103429] Optimization of Auto-generated condition chain is not giving good lookup tables.

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|13.2                        |13.3

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 13.2 is being released, retargeting bugs to GCC 13.3.

[Bug tree-optimization/103429] Optimization of Auto-generated condition chain is not giving good lookup tables.

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|13.3                        |13.4

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 13.3 is being released, retargeting bugs to GCC 13.4.