[Bug tree-optimization/104292] New: [missed optimization] boolean addition generates suboptimal code

[Bug tree-optimization/104292] New: [missed optimization] boolean addition generates suboptimal code

[avi at scylladb dot com]

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

            Bug ID: 104292
           Summary: [missed optimization] boolean addition generates
                    suboptimal code
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: avi at scylladb dot com
  Target Milestone: ---

bool bool_or(bool b1, bool b2) {
    return b1 + b2;
}

generates

bool_or(bool, bool):
        movzbl  %dil, %edi
        movzbl  %sil, %esi
        addl    %esi, %edi
        setne   %al
        ret

Whereas it could generate

bool_or(bool, bool):
        or   %edi, %esi
        mov  %esi, %eax
        ret

For a net gain of two instructions (and the final mov can often be elided, so
up to three).

I encountered this while using std::plus<> with boolean types. It could be
optimized as a specialization of std::plus, but I think a magic transformation
in the optimizer would make it apply in more places.

[Bug tree-optimization/104292] [missed optimization] boolean addition generates suboptimal code

[avi at scylladb dot com]

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

--- Comment #1 from Avi Kivity <avi at scylladb dot com> ---
btw, I see that the equivalent bool_and generates optimal code.

bool_and(bool, bool):
        movl    %esi, %eax
        andl    %edi, %eax
        ret

Perhaps bool is written with the expectation that any non-zero value is true?
But aren't non-zero values other than 1 undefined behavior?

[Bug tree-optimization/104292] [missed optimization] boolean addition generates suboptimal code

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
           Keywords|                            |missed-optimization

[Bug tree-optimization/104292] [missed optimization] boolean addition generates suboptimal code

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2022-01-30
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed, I thought I saw one which was asking about bool + bool == 2 also ...

[Bug tree-optimization/104292] [missed optimization] boolean addition generates suboptimal code

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=101703

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Found it, PR 101703.

[Bug tree-optimization/104292] (bool)(bool0 + bool1) should be simplified into bool0 | bool1

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
This should do it I think:

(for neeq (ne eq)
 (simplify
  (neeq (plus zero_one_valued_p@0 zero_one_valued_p@1) INTEGER_CST@2)
  (with {
    tree_code newcode = ERROR_MARK;
    bool notatend = false;
    tree cst1 = build_one_cst (type);
    wide_int cst = wi::to_wide (@2);
    // a + b == 2 -> a & b
    // a + b != 2 -> ~(a & b)
    if (cst == 2)
      newcode = BIT_AND_EXPR, notatend = neeq == NE_EXPR;
    // a + b == 1 -> a ^ b
    // a + b != 1 -> ~(a ^ b) -> a == b
    else if (cst == 1)
      newcode = BIT_XOR_EXPR, notatend = neeq == NE_EXPR;
    // a + b == 0 -> ~(a | b)
    // a + b != 0 -> a | b
    else if (cst == 0)
      newcode = BIT_IOR_EXPR, notatend = neeq == EQ_EXPR;
   }
  (if (notatend)
   (switch
    (if (newcode == BIT_IOR_EXPR)
     (bit_xor (bit_ior @0 @1) { cst1; }))
    (if (newcode == BIT_AND_EXPR)
     (bit_xor (bit_and @0 @1) { cst1; }))
    (if (newcode == BIT_XOR_EXPR)
     (eq @0 @1)))
   (switch
    (if (newcode == BIT_IOR_EXPR)
     (bit_ior @0 @1))
    (if (newcode == BIT_AND_EXPR)
     (bit_and @0 @1))
    (if (newcode == BIT_XOR_EXPR)
     (bit_xor @0 @1)))
  )
 )
)

[Bug tree-optimization/104292] (bool)(bool0 + bool1) should be simplified into bool0 | bool1

[pinskia at gcc dot gnu.org]

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

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

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

[Bug tree-optimization/104292] (bool)(bool0 + bool1) should be simplified into bool0 | bool1

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note LLVM started to do this "trick" in 17.1.0.