Re: [RFA] [PATCH] Make VRP understand bitwise OR and AND (better than now)

["Richard Guenther" <richard dot guenther at gmail dot com>]

On Mon, Aug 4, 2008 at 2:02 PM, Denys Vlasenko <dvlasenk@redhat.com> wrote:
> Hello,
>
> This is a patch for bug 28632 "VRP should understand bitwise OR and AND"
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
>
> This patch is bootstrapping successfully on current gcc svn.
>
> code_diff_example.fold.c is an example program which is compiled
> differently with this patch.
>
> The difference is here:
>
>        movl    (%edx), %eax    #,
>        call    bb_simple_perror_msg    #
>  .L40:
> -       orl     $1, 12(%esp)    #, errs
> +       movl    $1, 12(%esp)    #, errs
>  .L19:
>        addl    $4, 24(%esp)    #, argv.78
>        movl    24(%esp), %eax  # argv.78,
>
> With improved VRP on (a | b), gcc now can deduce that in this program,
> errs |= 1 is always equivalent to errs = 1.
>
>
> bug28632_instrumented.patch is an instrumented version of the patch.
> Set $VDA_DEBUG to the name of a file and gcc will append debug printouts to it
> showing how it deduced value ranges for (a | b) and (a & b).
>
> // extract_range_from_binary_expr(OR)[u32]
> // a integer_nonnegative_range(unsigned int __bid_IDEC_glbflags.40_536)=0
> // b integer_nonnegative_range(_IDEC_flags[u32],[16,16])=1
>  if (a | b) < (16) || (a | b) > (4294967295)) err();
>
> [gcc inferred that since b = 16, (a | b) is always >= 16,
> despite the fact we do not know value range of a]
>
> // extract_range_from_binary_expr(AND)[u32]
> // a integer_nonnegative_range(unsigned int[u32],[0,4294967295])=1
> // b integer_nonnegative_range(_IDEC_round[u32],[1,1])=1
> // bits_always_set(0,4294967295)=[u32]0
> // bits_always_set(1,1)=[u32]1
> // bits_maybe_set(0,4294967295)=[u32]4294967295
> // bits_maybe_set(1,1)=[u32]1
>  if (a & b) < 0 || (a & b) > 1 err();
>
> [a case where both operands had known positive range]
>
>
> pr28632.c is a testcase to be added to testsuite.
> It is artificially made to not compile if VRP fails
> to predict a range:
>
>  if (a < 0x1000) return;
>  if (a > 0x1000) return;
>  if (b < 0x0110) return;
>  if (!__builtin_constant_p ((a|b) >= 0x01000))
>    asm("the.bug.is.here");
>
> Before this patch, gcc will fail to see that (a|b) >= 0x01000 is known at
> compile time, after it it will see that.
>
> I don't know how to conditionally check for -O (not -O2 or -Os, just -O).
> #if defined __OPTIMIZE__ means "-O<anything>", I need to check for
> "-O<anything> but not bare -O". Help.
> Because of this, currently gcc -O -c pr28632.c fails (-O level is not high
> enough to trigger VRP). gcc -c pr28632.c, gcc -O2 -c pr28632.c, gcc -Os -c pr28632.c
> work.
>
> Please apply.

You didnt' specify if and how this passed testing.

In extract_range_from_binary_expr it looks like the cases for
BIT_AND_EXPR and BIT_IOR_EXPR can share most (if not all) of
the code if you use the expression code instead of constant codes.

In bits_always_set and bits_maybe_set it is better to use double_ints
(see double_int.h) for intermediate calculations, as they do not involve
allocating new tree constants.

integer_nonnegative_range needs a comment.

Thanks,
Richard.