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

["H.J. Lu" <hjl dot tools at gmail dot com>]

On Thu, Dec 4, 2008 at 12:37 PM, H.J. Lu <hjl.tools@gmail.com> wrote:
> On Tue, Aug 26, 2008 at 2:50 AM, Paolo Bonzini <bonzini@gnu.org> wrote:
>> Paolo Bonzini wrote:
>>> 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?
>>
>> Call me "the fastest Send button of the West".
>>
>> Paolo
>>
>> 2008-08-26  Paolo Bonzini  <bonzini@gnu.org>
>>
>>        * dojump.c (do_jump) [BIT_AND_EXPR]: Move below.  Fall through to
>>        TRUTH_AND_EXPR for boolean (1-bit precision) expressions.
>>        (do_jump) [BIT_IOR_EXPR]: Compile as TRUTH_OR_EXPR.
>>
>>        * tree-flow.h (simplify_stmt_using_ranges): Accept a GSI, return a bool.
>>        * tree-ssa-propagate.c (substitute_and_fold): Pass a GSI to
>>        VRP's simplify_stmt_using_ranges.  Do simplify_stmt_using_ranges
>>        before finalizing the changes.
>>        * tree-vrp.c (extract_range_from_binary_expr): Add limited support
>>        for BIT_IOR_EXPR.
>>        (simplify_truth_ops_using_ranges): New.
>>        (simplify_div_or_mod_using_ranges, simplify_abs_using_ranges,
>>        simplify_cond_using_ranges, simplify_switch_using_ranges): Return
>>        whether a simplification was made.
>>        (simplify_stmt_using_ranges): Ditto, and accept a GSI.  For GS_ASSIGN,
>>        use a switch statement and also call simplify_truth_ops_using_ranges.
>>
>
> Hi,
>
> This patch caused:
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38405
>

This also caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38572


-- 
H.J.