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

[Denys Vlasenko]

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.
--
vda
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bug28632.patch
Type: text/x-diff
Size: 8485 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20080804/041bf45b/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bug28632_instrumented.patch
Type: text/x-diff
Size: 13580 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20080804/041bf45b/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: code_diff_example.fold.c
Type: text/x-csrc
Size: 3815 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20080804/041bf45b/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: code_diff_example.diff
Type: text/x-diff
Size: 731 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20080804/041bf45b/attachment-0003.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pr28632.c
Type: text/x-csrc
Size: 1266 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20080804/041bf45b/attachment-0004.bin>