[PATCH] Use bitwise AND/OR/XOR if possible to implement &&, ||, !

[Manuel López-Ibáñez]

Wouldn't it be great if mailers asked for attachments?

2008/8/26 Paolo Bonzini <bonzini@gnu.org>:
> This patch allows GCC to compile boolean &&, ||, ! to simple bitwise
> AND, OR and XOR operations, when the operands are known to be truth
> values.  For example, this sequence
>
>        testl   %eax, %eax
>        setne   %dl
>        xorl    %eax, %eax
>        testl   %ecx, %ecx
>        setne   %al
>        andl    %edx, %eax
>
> becomes simply
>
>        andl    %ecx, %eax
>
> Or this sequence
>
>        orl     12(%ebp), %eax
>        setne   %al
>        movzbl  %al, %eax
>
> becomes just a single orl.  Likewise, compiling ! changes from
> these four instructions:
>
>        movl    8(%ebp), %edx
>        xorl    %eax, %eax
>        testl   %edx, %edx
>        sete    %al
>
> to just two:
>
>        movl    8(%ebp), %eax
>        xorl    $1, %eax
>
> One problem is that folding TRUTH_NOT_EXPR to BIT_XOR_EXPR requires
> reallocating the statement, and this in turn requires reordering the
> code in tree-ssa-propagate.c's substitute_and_fold to update the
> immediate uses properly.
>
> The new usage of BIT_AND_EXPR and BIT_IOR_EXPR also requires a little
> tweaking here and there.  We need to extract simple ranges from bitwise
> ORs (I restricted it to positive ranges for simplicity); this part can
> go away if the more complete patch from Denis goes in.
>
> We also need to cope with "if" conditions being BIT_AND_EXPR or
> BIT_IOR_EXPR, and compile them efficiently.  Luckily, the code is
> already there as part of the fix for PR tree-optimization/19672
> (which I had fixed in 2005): we just have "convert" them back to
> TRUTH_AND_EXPR and TRUTH_OR_EXPR just by falling through to the
> appropriate part of do_jump.  The BIT_AND_EXPR case is restricted to
> boolean arguments, while the BIT_IOR_EXPR part applies in general:
>
>        while (a | b)
>          f ();
>
> can always be compiled to
>
>       xx:
>        if (a == 0) goto end;
>        if (b == 0) goto end;
>        f ();
>        goto xx;
>
> which is beneficial if the BRANCH_COST is low enough.
>
> The testcase is duplicated in gcc.dg/tree-ssa and gcc.target/i386,
> meaning the first one to test tree-* changes, and the second to test
> dojump.c changes too.  The original testcase is in a well-known
> proprietary embedded systems benchmark.
>
> Bootstrapped/regtested i686-pc-linux-gnu, all languages including Ada, ok?
>
> Paolo
>
>