This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] add VRP for bitwise OR and AND
- From: Denis Vlasenko <vda dot linux at googlemail dot com>
- To: gcc-patches at gcc dot gnu dot org
- Cc: pinskia at gcc dot gnu dot org
- Date: Mon, 7 Aug 2006 17:39:19 +0200
- Subject: [PATCH] add VRP for bitwise OR and AND
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
--- gcc-4.1.1/gcc/tree-vrp.c.orig 2006-08-06 16:07:03.000000000 +0200
+++ gcc-4.1.1/gcc/tree-vrp.c 2006-08-06 21:44:24.000000000 +0200
@@ -1086,7 +1086,7 @@ extract_range_from_ssa_name (value_range
are not using wrapping arithmetic, then adjust the result to be
-INF or +INF depending on CODE, VAL1 and VAL2. */
-static inline tree
+static tree
vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
{
tree res;
@@ -1182,6 +1182,63 @@ vrp_int_const_binop (enum tree_code code
}
+/* Example: let's say operand has:
+max = 01010010101001010010
+min = 01010010100000010010
+We can infer that these bits will be set
+in any possible value of the operand:
+ 01010010100000000000
+*/
+static tree
+find_bits1 (tree min, tree max)
+{
+ 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);
+ if(xor_hi >= 0) /* if min!=max */
+ {
+ 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);
+ }
+ return always1;
+}
+/* Example: let's say operand has:
+max = 01010010101001010010
+min = 01010010100000010010
+We can infer that these bits will be unset
+in any possible value of the operand:
+ 01010010101111111111
+*/
+static tree
+find_bits0 (tree min, tree max)
+{
+ tree xored, always0, tmp;
+ int xor_hi;
+
+ always0 = vrp_int_const_binop(BIT_IOR_EXPR, min, max);
+ xored = vrp_int_const_binop(BIT_XOR_EXPR, min, max);
+ xor_hi = tree_floor_log2(xored);
+ if(xor_hi > 0) /* if min!=max and difference is not in lowest bit only */
+ {
+ tmp = build_int_cst (NULL_TREE, xor_hi);
+ always0 = vrp_int_const_binop(RSHIFT_EXPR, always0, tmp);
+ /* Too ugly for words */
+ tmp = build_int_cst (NULL_TREE, 1);
+ do
+ {
+ always0 = vrp_int_const_binop(LSHIFT_EXPR, always0, tmp);
+ always0 = vrp_int_const_binop(PLUS_EXPR, always0, tmp);
+ xor_hi--;
+ }
+ while(xor_hi);
+ }
+ return always0;
+}
+
/* Extract range information from a binary expression EXPR based on
the ranges of each of its operands and the expression code. */
@@ -1206,6 +1263,8 @@ extract_range_from_binary_expr (value_ra
&& code != ROUND_DIV_EXPR
&& code != MIN_EXPR
&& code != MAX_EXPR
+ && code != BIT_AND_EXPR
+ && code != BIT_IOR_EXPR
&& code != TRUTH_ANDIF_EXPR
&& code != TRUTH_ORIF_EXPR
&& code != TRUTH_AND_EXPR
@@ -1234,6 +1293,72 @@ extract_range_from_binary_expr (value_ra
else
set_value_range_to_varying (&vr1);
+ /* Bitwise ops */
+ if (code == BIT_AND_EXPR)
+ {
+ if (vr0.type == VR_RANGE || vr1.type == VR_RANGE)
+ {
+ if(vr0.type == VR_RANGE)
+ {
+ if(vr1.type == VR_RANGE)
+ {
+ tree always1_0, always1_1;
+ always1_0 = find_bits1(vr0.min, vr0.max);
+ always1_1 = find_bits1(vr1.min, vr1.max);
+ min = vrp_int_const_binop(BIT_AND_EXPR, always1_0, always1_1);
+ max = vrp_int_const_binop(MIN_EXPR, vr0.max, vr1.max);
+ }
+ else
+ {
+ min = build_int_cst(TREE_TYPE(vr0.min), 0);
+ max = vr0.max;
+ }
+ set_value_range (vr, vr0.type, min, max, NULL);
+ }
+ else
+ {
+ min = build_int_cst(TREE_TYPE(vr1.min), 0);
+ max = vr1.max;
+ set_value_range (vr, vr1.type, min, max, NULL);
+ }
+ return;
+ }
+ set_value_range_to_varying (vr);
+ return;
+ }
+ if (code == BIT_IOR_EXPR)
+ {
+ if (vr0.type == VR_RANGE || vr1.type == VR_RANGE)
+ {
+ if(vr0.type == VR_RANGE)
+ {
+ if(vr1.type == VR_RANGE)
+ {
+ tree always0_0, always0_1;
+ always0_0 = find_bits0(vr0.min, vr0.max);
+ always0_1 = find_bits0(vr1.min, vr1.max);
+ min = vrp_int_const_binop(MAX_EXPR, vr0.min, vr1.min);
+ max = vrp_int_const_binop(BIT_IOR_EXPR, always0_0, always0_1);
+ }
+ else
+ {
+ min = vr0.min;
+ max = TYPE_MAX_VALUE(TREE_TYPE(vr0.max));
+ }
+ set_value_range (vr, vr0.type, min, max, NULL);
+ }
+ else
+ {
+ min = vr1.min;
+ max = TYPE_MAX_VALUE(TREE_TYPE(vr1.max));
+ set_value_range (vr, vr1.type, min, max, NULL);
+ }
+ return;
+ }
+ set_value_range_to_varying (vr);
+ return;
+ }
+
/* If either range is UNDEFINED, so is the result. */
if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
{
@@ -1244,9 +1369,8 @@ extract_range_from_binary_expr (value_ra
/* Refuse to operate on VARYING ranges, ranges of different kinds
and symbolic ranges. TODO, we may be able to derive anti-ranges
in some cases. */
- if (vr0.type == VR_VARYING
- || vr1.type == VR_VARYING
- || vr0.type != vr1.type
+ if (vr0.type != vr1.type
+ || vr0.type == VR_VARYING
|| symbolic_range_p (&vr0)
|| symbolic_range_p (&vr1))
{
/*
gcc -O2 -fdump-tree-vrp -S -fomit-frame-pointer -falign-functions=1 -falign-jumps=1 test_vrp.c
*/
void v4(unsigned a, unsigned b) {
if (a < 0x1000) return;
if (a > 0x1000) return;
if (b < 0x0110) return;
if ((a|b) >= 0x01000) f(); //always
if ((a|b) >= 0x10000) g(); //not always
}
void u4 (unsigned n) {
if (n > 0x10111) return;
if (n < 0x10101) return;
//if (n & 0x01000) h(); //never, but VRP so far is not able to figure it out
if (n & 0x00100) f(); //always
if (n & 0x00001) g(); //not always
}