[Bug c++/101701] New: GCC optimization and code generation for if-else chains vs ternary chains vs a switch

[Bug c++/101701] New: GCC optimization and code generation for if-else chains vs ternary chains vs a switch

[llvm at rifkin dot dev]

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

            Bug ID: 101701
           Summary: GCC optimization and code generation for if-else
                    chains vs ternary chains vs a switch
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: llvm at rifkin dot dev
  Target Milestone: ---

I'm looking at an example of three equivalent functions implemented with
if-else chains, ternary chains, and a switch. Gcc is not compiling them
equivalently: https://godbolt.org/z/8cjGr7M7W.

For the if-else chain, gcc does not optimize away the jumps.
For the ternary chain, gcc does its codegen well.
For the switch, gcc also does its codegen well but there is an extra mov
instruction compared to the ternary chain.

I don't think it's idealistic to say these should compile equivalently - if
someone told me to prefer one over the other for performance reasons I'd
dismiss it as a micro-optimization.

Clang does not do this perfectly either at the moment.




This bug is probably miscategorized. I am not sure the correct category for it.

[Bug tree-optimization/101701] GCC optimization and code generation for if-else chains vs ternary chains vs a switch

[pinskia at gcc dot gnu.org]

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

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
int foo(int val) {
    if     (val == 1) return val; 
    else if(val == 2) return val;
    else if(val == 3) return val;
    else if(val == 4) return val;
    else return -1;
}

int bar(int val) {
    return val == 1 ? val :
          (val == 2 ? val :
          (val == 3 ? val :
          (val == 4 ? val : -1)));
}

int baz(int val) {
    switch(val) {
        case 1:
        case 2:
        case 3:
        case 4:
            return val;
        default:
            return -1;
    }
}

[Bug tree-optimization/101701] GCC optimization and code generation for if-else chains vs ternary chains vs a switch

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-07-30
             Status|UNCONFIRMED                 |NEW
           Severity|normal                      |enhancement

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So the problem here is iftoswitch should ignore if it is profitable to convert
the ifs to a switch statement (unless there are only two ifs) and then allow
the switchlower pass to lower the switch again.

I thought there was a bug about this already too.

What is interesting is that the cost for ifs are so high on arm target
(compared to a switch), we end up with the best code already:
foo(int):
        subs    r3, r0, #1
        cmp     r3, #3
        it      hi
        movhi   r0, #-1
        bx      lr
bar(int):
        subs    r3, r0, #1
        cmp     r3, #3
        it      hi
        movhi   r0, #-1
        bx      lr
baz(int):
        subs    r3, r0, #1
        cmp     r3, #4
        it      cs
        movcs   r0, #-1
        bx      lr

:)

So x86 we get:
;; Canonical GIMPLE case clusters: 1 2 3 4 
For foo
and then for bar:
;; Canonical GIMPLE case clusters: 1 2 3 4 
;; BT can be built: BT(values:4 comparisons:8 range:4 density: 200.00%):1-4 
/app/example.cpp:10:21: optimized: Condition chain with 4 BBs transformed into
a switch statement.

[Bug tree-optimization/101701] GCC optimization and code generation for if-else chains vs ternary chains vs a switch

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Depends on|                            |94566

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Oh yes PR 94566.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94566
[Bug 94566] conversion between std::strong_ordering and int

[Bug tree-optimization/101701] GCC optimization and code generation for if-else chains vs ternary chains vs a switch

[llvm at rifkin dot dev]

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

--- Comment #4 from Jeremy R. <llvm at rifkin dot dev> ---
I see with gcc x86_64 it does get the fold correct if another term (val == 5)
is added to the if-else chain: https://godbolt.org/z/TE15Wf1bo.

[Bug tree-optimization/101701] GCC optimization and code generation for if-else chains vs ternary chains vs a switch

[marxin at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #5 from Martin Liška <marxin at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #2)
> So the problem here is iftoswitch should ignore if it is profitable to
> convert the ifs to a switch statement (unless there are only two ifs) and
> then allow the switchlower pass to lower the switch again.

This was my original intention, but Jakub wanted to make the if-to-switch
transformation
only conditionally based on the ability to make a jump table or a bit-test.
Reason is that
some optimization passes work only on series of gimple conditions.

> 
> So x86 we get:
> ;; Canonical GIMPLE case clusters: 1 2 3 4 
> For foo
> and then for bar:
> ;; Canonical GIMPLE case clusters: 1 2 3 4 
> ;; BT can be built: BT(values:4 comparisons:8 range:4 density: 200.00%):1-4 
> /app/example.cpp:10:21: optimized: Condition chain with 4 BBs transformed
> into a switch statement.

In my case, it's not transformed as we do JT at least for 5 cases:

unsigned int
default_case_values_threshold (void)
{
  return (targetm.have_casesi () ? 4 : 5);
}

That's why you see a different codegen on ARM target.