[PATCH] add VRP for bitwise OR and AND

Denis Vlasenko vda.linux@googlemail.com
Mon Aug 7 15:43:00 GMT 2006


This patch adds value range propagation for (a&b), (a|b) operations.

tree-vrp.c.diff is the patch itself, test_vrp.c is a test program.
 
Differences in *.vrp (-fdump-tree-vrp output) and assembly generated
with stock 4.1.1 and with patched one out of test program test_vrp.c
are below the sig.

I am not familiar with gcc internals, so please review carefully before 
applying. For example, I construct integer contants like this:

  tmp = build_int_cst (NULL_TREE, 1);

while Andrew Pinski does it like this:

  max = build_int_cst (TREE_TYPE (expr), 1);

Why? Is there a FAQ on this somewhere?

And, more broadly, I do some arithmetic on compile time constants here:

  tree xored, shift, always1;
  int xor_hi;
  always1 = vrp_int_const_binop(BIT_AND_EXPR, min, max);
  xored = vrp_int_const_binop(BIT_XOR_EXPR, min, max);
  xor_hi = tree_floor_log2(xored);
  shift = build_int_cst (NULL_TREE, xor_hi+1);
  always1 = vrp_int_const_binop(RSHIFT_EXPR, always1, shift);
  always1 = vrp_int_const_binop(LSHIFT_EXPR, always1, shift);

Well, it works, but do I really need to do it that complex?
Can I just directly express it in C? That would be much
faster/simpler:

  ...
  xor_hi++;
  always1 = (always1 >> xor_hi) << xor_hi;

And, btw, is it okay to reuse "tree" variables like I did
wiht always1 in that piece of code? Do I need to "free"
them somehow?

I can attempt adding VRP for shifts after I will get
some cluebatting on this one.

Meanwhile I'll rediff/retest it against gcc-4.1-20060804.

Andrew, please do not hesitate to point me to any
stupid mistakes in my code. I *am* unfamiliar with gcc
internals.
--
vda

--- test_vrp.c.t36-411org.vrp   2006-08-06 22:40:04.000000000 +0200
+++ test_vrp.c.t36-411new.vrp   2006-08-06 22:40:20.000000000 +0200
@@ -26,12 +26,15 @@
 Value ranges after VRP:

 n_1: VARYING
-D.1286_2: VARYING
-D.1287_3: VARYING
+D.1286_2: [256, 256]  EQUIVALENCES: { } (0 elements)
+D.1287_3: [0, 1]  EQUIVALENCES: { } (0 elements)
 n_5: [65793, 65809]  EQUIVALENCES: { n_1 n_6 } (2 elements)
 n_6: [0, 65809]  EQUIVALENCES: { n_1 } (1 elements)


+Folding predicate D.1286_2 != 0 to 1
+Merging blocks 2 and 3
+Merging blocks 2 and 4
 u4 (n)
 {
   _Bool D.1288;
@@ -46,12 +49,7 @@

 <L1>:;
   D.1286_2 = n_1 & 256;
-  if (D.1286_2 != 0) goto <L2>; else goto <L3>;
-
-<L2>:;
   f ();
-
-<L3>:;
   D.1287_3 = n_1 & 1;
   if (D.1287_3 != 0) goto <L4>; else goto <L5>;

@@ -95,16 +93,18 @@

 a_1: VARYING
 b_2: VARYING
-D.1282_3: VARYING
-D.1282_4: [D.1282_3, D.1282_3]  EQUIVALENCES: { D.1282_3 } (1 elements)
+D.1282_3: [4096, +INF]  EQUIVALENCES: { } (0 elements)
+D.1282_4: [4096, +INF]  EQUIVALENCES: { D.1282_3 } (1 elements)
 a_5: [4096, 4096]  EQUIVALENCES: { a_1 a_6 } (2 elements)
 a_6: [4096, +INF]  EQUIVALENCES: { a_1 } (1 elements)
 b_7: [272, +INF]  EQUIVALENCES: { b_2 } (1 elements)
-D.1282_8: [0, 4095]  EQUIVALENCES: { D.1282_3 } (1 elements)


 Simplified relational a_6 > 4096 into a_6 != 4096
+Folding predicate D.1282_3 > 4095 to 1
 Removing basic block 8
+Merging blocks 3 and 4
+Merging blocks 3 and 5
 v4 (a, b)
 {
   unsigned int D.1282;
@@ -120,12 +120,7 @@

 <L2>:;
   D.1282_3 = b_2 | 4096;
-  if (D.1282_3 > 4095) goto <L3>; else goto <L4>;
-
-<L3>:;
   f ();
-
-<L4>:;
   D.1282_4 = D.1282_3;
   if (D.1282_3 > 65535) goto <L5>; else goto <L6>;

--- test_vrp-411org.s   2006-08-06 22:40:04.000000000 +0200
+++ test_vrp-411new.s   2006-08-06 22:40:20.000000000 +0200
@@ -7,24 +7,20 @@
        subl    $8, %esp
        movl    16(%esp), %ebx
        cmpl    $65809, %ebx
-       ja      .L8
+       ja      .L6
        cmpl    $65792, %ebx
-       jbe     .L8
-       testb   $1, %bh
-       jne     .L10
-.L5:
-       andl    $1, %ebx
-       je      .L8
+       ja      .L8
+.L6:
        addl    $8, %esp
        popl    %ebx
-       jmp     g
+       ret
 .L8:
+       call    f
+       andl    $1, %ebx
+       je      .L6
        addl    $8, %esp
        popl    %ebx
-       ret
-.L10:
-       call    f
-       jmp     .L5
+       jmp     g
        .size   u4, .-u4
 .globl v4
        .type   v4, @function
@@ -32,31 +28,25 @@
        pushl   %ebx
        subl    $8, %esp
        movl    16(%esp), %eax
-       movl    20(%esp), %edx
+       movl    20(%esp), %ebx
        cmpl    $4095, %eax
-       jbe     .L19
+       jbe     .L15
        cmpl    $4096, %eax
-       je      .L20
-.L19:
+       je      .L16
+.L15:
        addl    $8, %esp
        popl    %ebx
        ret
-.L20:
-       cmpl    $271, %edx
-       jbe     .L19
-       movl    %edx, %ebx
-       orb     $16, %bh
-       cmpl    $4095, %ebx
-       ja      .L21
 .L16:
+       cmpl    $271, %ebx
+       jbe     .L15
+       call    f
+       orb     $16, %bh
        cmpl    $65535, %ebx
-       jbe     .L19
+       jbe     .L15
        addl    $8, %esp
        popl    %ebx
        jmp     g
-.L21:
-       call    f
-       jmp     .L16
        .size   v4, .-v4
        .ident  "GCC: (GNU) 4.1.1"
        .section        .note.GNU-stack,"",@progbits
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tree-vrp.c.diff
Type: text/x-diff
Size: 5516 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20060807/a085d66c/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test_vrp.c
Type: text/x-csrc
Size: 524 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20060807/a085d66c/attachment-0001.bin>


More information about the Gcc-patches mailing list