[Bug tree-optimization/103429] Optimization of Auto-generated condition chain is not giving good lookup tables.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429 Richard Biener changed: What|Removed |Added Target Milestone|13.2|13.3 --- Comment #6 from Richard Biener --- 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.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429 Richard Biener changed: What|Removed |Added Target Milestone|13.0|13.2 --- Comment #5 from Richard Biener --- 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.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429 Martin Liška 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.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429 Martin Liška changed: What|Removed |Added Target Milestone|--- |13.0
[Bug tree-optimization/103429] Optimization of Auto-generated condition chain is not giving good lookup tables.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429 Andrew Pinski changed: What|Removed |Added Severity|normal |enhancement
[Bug tree-optimization/103429] Optimization of Auto-generated condition chain is not giving good lookup tables.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429 --- Comment #4 from Martin Liška --- 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) { : if (i_2(D) == 4) goto ; [INV] else goto ; [INV] : f<4> (); goto ; [INV] : switch (i_2(D)) [16.67%], case 5: [16.67%], case 6: [16.67%], case 7: [16.67%], case 8: [16.67%], case 9: [16.67%]> : : f<5> (); goto ; [100.00%] : : f<6> (); goto ; [100.00%] : : f<7> (); goto ; [100.00%] : : f<8> (); goto ; [100.00%] : : f<9> (); : : 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.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429 Martin Liška 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 --- Looking into it.
[Bug tree-optimization/103429] Optimization of Auto-generated condition chain is not giving good lookup tables.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429 --- Comment #2 from Edward Rosten --- 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): testedi, 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.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103429 Richard Biener changed: What|Removed |Added Component|c++ |tree-optimization CC||marxin at gcc dot gnu.org --- Comment #1 from Richard Biener --- Sounds like if-to-switch / switch conversion could help. Note that GCC converts large switches into binary if trees in some cases as well.