public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND
@ 2006-08-07 11:12 vda dot linux at googlemail dot com
2006-08-07 11:13 ` [Bug tree-optimization/28632] " vda dot linux at googlemail dot com
` (23 more replies)
0 siblings, 24 replies; 26+ messages in thread
From: vda dot linux at googlemail dot com @ 2006-08-07 11:12 UTC (permalink / raw)
To: gcc-bugs
This patch adds value range propagation for (a&b), (a|b) operations.
I am not familiar with gcc internals, so please review carefully before
applying.
--
Summary: [PATCH] add VRP for bitwise OR and AND
Product: gcc
Version: 4.1.1
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: vda dot linux at googlemail dot com
GCC build triplet: i386-pc-linux-gnu
GCC host triplet: i386-pc-linux-gnu
GCC target triplet: i386-pc-linux-gnu
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] [PATCH] add VRP for bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
@ 2006-08-07 11:13 ` vda dot linux at googlemail dot com
2006-08-07 11:14 ` vda dot linux at googlemail dot com
` (22 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: vda dot linux at googlemail dot com @ 2006-08-07 11:13 UTC (permalink / raw)
To: gcc-bugs
------- Comment #1 from vda dot linux at googlemail dot com 2006-08-07 11:13 -------
Created an attachment (id=12035)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=12035&action=view)
The patch relative to 4.1.1
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] [PATCH] add VRP for bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
2006-08-07 11:13 ` [Bug tree-optimization/28632] " vda dot linux at googlemail dot com
@ 2006-08-07 11:14 ` vda dot linux at googlemail dot com
2006-08-07 11:26 ` vda dot linux at googlemail dot com
` (21 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: vda dot linux at googlemail dot com @ 2006-08-07 11:14 UTC (permalink / raw)
To: gcc-bugs
------- Comment #2 from vda dot linux at googlemail dot com 2006-08-07 11:14 -------
Created an attachment (id=12036)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=12036&action=view)
Test program which demonstrates how VRP generates simpler code
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] [PATCH] add VRP for bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
2006-08-07 11:13 ` [Bug tree-optimization/28632] " vda dot linux at googlemail dot com
2006-08-07 11:14 ` vda dot linux at googlemail dot com
@ 2006-08-07 11:26 ` vda dot linux at googlemail dot com
2006-08-07 14:54 ` pinskia at gcc dot gnu dot org
` (20 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: vda dot linux at googlemail dot com @ 2006-08-07 11:26 UTC (permalink / raw)
To: gcc-bugs
------- Comment #3 from vda dot linux at googlemail dot com 2006-08-07 11:26 -------
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
--- 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
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] [PATCH] add VRP for bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (2 preceding siblings ...)
2006-08-07 11:26 ` vda dot linux at googlemail dot com
@ 2006-08-07 14:54 ` pinskia at gcc dot gnu dot org
2006-08-08 0:37 ` [Bug tree-optimization/28632] VRP should understand " pinskia at gcc dot gnu dot org
` (19 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2006-08-07 14:54 UTC (permalink / raw)
To: gcc-bugs
------- Comment #4 from pinskia at gcc dot gnu dot org 2006-08-07 14:54 -------
First patches should be off of the mainline. Second Patchs should be sent to
gcc-patches@gcc.gnu.org.
Third and this should be able to fix PR 18031 which I added a patch already
(though not officially sent it because I had not tested it).
--
pinskia at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
OtherBugsDependingO| |18031
nThis| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (4 preceding siblings ...)
2006-08-08 0:37 ` [Bug tree-optimization/28632] VRP should understand " pinskia at gcc dot gnu dot org
@ 2006-08-08 0:37 ` pinskia at gcc dot gnu dot org
2006-08-11 14:17 ` vda dot linux at googlemail dot com
` (17 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2006-08-08 0:37 UTC (permalink / raw)
To: gcc-bugs
------- Comment #5 from pinskia at gcc dot gnu dot org 2006-08-08 00:37 -------
Confirmed.
--
pinskia at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|UNCONFIRMED |NEW
Ever Confirmed|0 |1
Last reconfirmed|0000-00-00 00:00:00 |2006-08-08 00:37:24
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (3 preceding siblings ...)
2006-08-07 14:54 ` pinskia at gcc dot gnu dot org
@ 2006-08-08 0:37 ` pinskia at gcc dot gnu dot org
2006-08-08 0:37 ` pinskia at gcc dot gnu dot org
` (18 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2006-08-08 0:37 UTC (permalink / raw)
To: gcc-bugs
--
pinskia at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Severity|normal |enhancement
Keywords| |missed-optimization
Summary|[PATCH] add VRP for bitwise |VRP should understand
|OR and AND |bitwise OR and AND
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (5 preceding siblings ...)
2006-08-08 0:37 ` pinskia at gcc dot gnu dot org
@ 2006-08-11 14:17 ` vda dot linux at googlemail dot com
2008-08-04 11:27 ` vda dot linux at googlemail dot com
` (16 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: vda dot linux at googlemail dot com @ 2006-08-11 14:17 UTC (permalink / raw)
To: gcc-bugs
------- Comment #6 from vda dot linux at googlemail dot com 2006-08-11 14:17 -------
Created an attachment (id=12067)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=12067&action=view)
New version of the patch. 4.1.1 bootstraps with it.
--
vda dot linux at googlemail dot com changed:
What |Removed |Added
----------------------------------------------------------------------------
Attachment #12035|0 |1
is obsolete| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (6 preceding siblings ...)
2006-08-11 14:17 ` vda dot linux at googlemail dot com
@ 2008-08-04 11:27 ` vda dot linux at googlemail dot com
2008-08-04 11:29 ` vda dot linux at googlemail dot com
` (15 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: vda dot linux at googlemail dot com @ 2008-08-04 11:27 UTC (permalink / raw)
To: gcc-bugs
------- Comment #7 from vda dot linux at googlemail dot com 2008-08-04 11:25 -------
Created an attachment (id=16009)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16009&action=view)
Updated patch against current svn
This patch is bootstrapping successfully on current gcc svn.
--
vda dot linux at googlemail dot com changed:
What |Removed |Added
----------------------------------------------------------------------------
Attachment #12067|0 |1
is obsolete| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (7 preceding siblings ...)
2008-08-04 11:27 ` vda dot linux at googlemail dot com
@ 2008-08-04 11:29 ` vda dot linux at googlemail dot com
2008-08-04 11:36 ` vda dot linux at googlemail dot com
` (14 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: vda dot linux at googlemail dot com @ 2008-08-04 11:29 UTC (permalink / raw)
To: gcc-bugs
------- Comment #8 from vda dot linux at googlemail dot com 2008-08-04 11:28 -------
Created an attachment (id=16010)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16010&action=view)
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.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (8 preceding siblings ...)
2008-08-04 11:29 ` vda dot linux at googlemail dot com
@ 2008-08-04 11:36 ` vda dot linux at googlemail dot com
2008-08-04 11:56 ` vda dot linux at googlemail dot com
` (13 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: vda dot linux at googlemail dot com @ 2008-08-04 11:36 UTC (permalink / raw)
To: gcc-bugs
------- Comment #9 from vda dot linux at googlemail dot com 2008-08-04 11:34 -------
Created an attachment (id=16011)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16011&action=view)
The 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]
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (9 preceding siblings ...)
2008-08-04 11:36 ` vda dot linux at googlemail dot com
@ 2008-08-04 11:56 ` vda dot linux at googlemail dot com
2008-08-11 12:47 ` vda dot linux at googlemail dot com
` (12 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: vda dot linux at googlemail dot com @ 2008-08-04 11:56 UTC (permalink / raw)
To: gcc-bugs
------- Comment #10 from vda dot linux at googlemail dot com 2008-08-04 11:55 -------
Created an attachment (id=16012)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16012&action=view)
Testcase to be added to testsuite
This program 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.
Currently gcc -O -c pr28632.c fails (-O level is not high enough to trigger
VRP).
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (10 preceding siblings ...)
2008-08-04 11:56 ` vda dot linux at googlemail dot com
@ 2008-08-11 12:47 ` vda dot linux at googlemail dot com
2008-08-18 13:04 ` vda dot linux at googlemail dot com
` (11 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: vda dot linux at googlemail dot com @ 2008-08-11 12:47 UTC (permalink / raw)
To: gcc-bugs
------- Comment #11 from vda dot linux at googlemail dot com 2008-08-11 12:46 -------
Created an attachment (id=16050)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16050&action=view)
Updated patch. Uses double_int calculations instead of trees.
On Mon, 2008-08-04 at 14:26 +0200, Richard Guenther wrote:
> 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.
The updated patch is attached (with instrumentation code present but
#defined out).
--
vda dot linux at googlemail dot com changed:
What |Removed |Added
----------------------------------------------------------------------------
Attachment #16009|0 |1
is obsolete| |
Attachment #16011|0 |1
is obsolete| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (11 preceding siblings ...)
2008-08-11 12:47 ` vda dot linux at googlemail dot com
@ 2008-08-18 13:04 ` vda dot linux at googlemail dot com
2008-08-20 14:58 ` vda dot linux at googlemail dot com
` (10 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: vda dot linux at googlemail dot com @ 2008-08-18 13:04 UTC (permalink / raw)
To: gcc-bugs
------- Comment #12 from vda dot linux at googlemail dot com 2008-08-18 13:02 -------
Bootstrap with -O2 on current svn fails. Bootstrap with -Os works.
Bootstrap with -O2 on 4.3.1 works.
Instrumented patch emits C code which can be used to test for incorrect VRP
predictions.
I ran such tests and found no such incorrect predictions. Either patch is buggy
in some subtle way or it exposes a latent bug elsewhere :(
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (12 preceding siblings ...)
2008-08-18 13:04 ` vda dot linux at googlemail dot com
@ 2008-08-20 14:58 ` vda dot linux at googlemail dot com
2008-08-20 14:59 ` vda dot linux at googlemail dot com
` (9 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: vda dot linux at googlemail dot com @ 2008-08-20 14:58 UTC (permalink / raw)
To: gcc-bugs
------- Comment #13 from vda dot linux at googlemail dot com 2008-08-20 14:57 -------
Created an attachment (id=16113)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16113&action=view)
Updated doubleint-based patch. DOES NOT PASS TESTSUITE.
--
vda dot linux at googlemail dot com changed:
What |Removed |Added
----------------------------------------------------------------------------
Attachment #12036|0 |1
is obsolete| |
Attachment #16050|0 |1
is obsolete| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (13 preceding siblings ...)
2008-08-20 14:58 ` vda dot linux at googlemail dot com
@ 2008-08-20 14:59 ` vda dot linux at googlemail dot com
2008-08-20 15:08 ` vda dot linux at googlemail dot com
` (8 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: vda dot linux at googlemail dot com @ 2008-08-20 14:59 UTC (permalink / raw)
To: gcc-bugs
------- Comment #14 from vda dot linux at googlemail dot com 2008-08-20 14:58 -------
Created an attachment (id=16114)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16114&action=view)
Tree based patch. Passes bootstrap.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (14 preceding siblings ...)
2008-08-20 14:59 ` vda dot linux at googlemail dot com
@ 2008-08-20 15:08 ` vda dot linux at googlemail dot com
2009-06-05 16:27 ` aldot at gcc dot gnu dot org
` (7 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: vda dot linux at googlemail dot com @ 2008-08-20 15:08 UTC (permalink / raw)
To: gcc-bugs
------- Comment #15 from vda dot linux at googlemail dot com 2008-08-20 15:07 -------
(In reply to comment #13)
> Created an attachment (id=16113)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16113&action=view) [edit]
> Updated doubleint-based patch. DOES NOT PASS TESTSUITE.
I meant "does not bootstrap".
Anyway. Something strange is going on. Last two patches:
bug28632_doubleint_based.patch
bug28632_tree_based.patch
are identical in their basic algorithm, but one uses trees and other uses
double_ints for intermediate calculations. I did a bootstrap with them
and on 4.3.1 both work, whereas on current-ish svn doubleint-based patch
fails.
Bootstrap with both patches was done with debugging output enabled
and OUTPUT IS THE SAME! Entire ~7Mb output has the same ranges predicted
by both patches, up to the point where gcc stage 2 is reached.
Then newly built compiles mispredicts a range and compile fails
(again only for bug28632_doubleint_based.patch).
This practically rules out that I have some silly bug
in bug28632_doubleint_based.patch which miscalculates ranges - that would make
bug28632_tree_based.patch to fail as well.
I also ran a test program which tested predictions for random (a | b)
and (a & b) and it didn't find any errors.
Looks like this problem is more difficult than I can handle.
Putting it on hold for now.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (15 preceding siblings ...)
2008-08-20 15:08 ` vda dot linux at googlemail dot com
@ 2009-06-05 16:27 ` aldot at gcc dot gnu dot org
2009-06-10 16:48 ` aldot at gcc dot gnu dot org
` (6 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: aldot at gcc dot gnu dot org @ 2009-06-05 16:27 UTC (permalink / raw)
To: gcc-bugs
------- Comment #16 from aldot at gcc dot gnu dot org 2009-06-05 16:27 -------
(In reply to comment #15)
> (In reply to comment #13)
> > Created an attachment (id=16113)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16113&action=view) [edit]
> > Updated doubleint-based patch. DOES NOT PASS TESTSUITE.
>
> I meant "does not bootstrap".
>
> Anyway. Something strange is going on. Last two patches:
I have a reimplementation (for BIT_AND_EXPR only, BIT_IOR_EXPR seem to work ok
on trunk) in testing that i intend to submit for inclusion.
--
aldot at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |aldot at gcc dot gnu dot org
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (16 preceding siblings ...)
2009-06-05 16:27 ` aldot at gcc dot gnu dot org
@ 2009-06-10 16:48 ` aldot at gcc dot gnu dot org
2009-06-22 8:29 ` aldot at gcc dot gnu dot org
` (5 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: aldot at gcc dot gnu dot org @ 2009-06-10 16:48 UTC (permalink / raw)
To: gcc-bugs
--
aldot at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
AssignedTo|unassigned at gcc dot gnu |aldot at gcc dot gnu dot org
|dot org |
Status|NEW |ASSIGNED
Last reconfirmed|2006-08-08 00:37:24 |2009-06-10 16:48:37
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (17 preceding siblings ...)
2009-06-10 16:48 ` aldot at gcc dot gnu dot org
@ 2009-06-22 8:29 ` aldot at gcc dot gnu dot org
2010-01-02 1:00 ` steven at gcc dot gnu dot org
` (4 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: aldot at gcc dot gnu dot org @ 2009-06-22 8:29 UTC (permalink / raw)
To: gcc-bugs
------- Comment #17 from aldot at gcc dot gnu dot org 2009-06-22 08:28 -------
Created an attachment (id=18044)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18044&action=view)
Bootstraps and regtests
bootstrapped and regtested all default languages with no new regressions.
TODO:
- split out to helper function
- unite the two (unrelated) gcc_asserts and send them separately
- drop debugging stuff
--
aldot at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Attachment #16113|0 |1
is obsolete| |
Attachment #16114|0 |1
is obsolete| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (18 preceding siblings ...)
2009-06-22 8:29 ` aldot at gcc dot gnu dot org
@ 2010-01-02 1:00 ` steven at gcc dot gnu dot org
2010-07-09 7:53 ` aldot at gcc dot gnu dot org
` (3 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: steven at gcc dot gnu dot org @ 2010-01-02 1:00 UTC (permalink / raw)
To: gcc-bugs
------- Comment #18 from steven at gcc dot gnu dot org 2010-01-02 01:00 -------
Re. comment #17: Any plans to finish this for GCC 4.6 stage 1?
--
steven at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Last reconfirmed|2009-06-10 16:48:37 |2010-01-02 01:00:42
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (19 preceding siblings ...)
2010-01-02 1:00 ` steven at gcc dot gnu dot org
@ 2010-07-09 7:53 ` aldot at gcc dot gnu dot org
2010-07-09 8:10 ` aldot at gcc dot gnu dot org
` (2 subsequent siblings)
23 siblings, 0 replies; 26+ messages in thread
From: aldot at gcc dot gnu dot org @ 2010-07-09 7:53 UTC (permalink / raw)
To: gcc-bugs
------- Comment #19 from aldot at gcc dot gnu dot org 2010-07-09 07:53 -------
Created an attachment (id=21156)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=21156&action=view)
gcc/testsuite/gcc.dg/tree-ssa/vrp50-PR28632.c
--
aldot at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Attachment #16012|0 |1
is obsolete| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (20 preceding siblings ...)
2010-07-09 7:53 ` aldot at gcc dot gnu dot org
@ 2010-07-09 8:10 ` aldot at gcc dot gnu dot org
2010-07-09 17:12 ` jakub at gcc dot gnu dot org
2010-07-09 19:40 ` jakub at gcc dot gnu dot org
23 siblings, 0 replies; 26+ messages in thread
From: aldot at gcc dot gnu dot org @ 2010-07-09 8:10 UTC (permalink / raw)
To: gcc-bugs
--
aldot at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
AssignedTo|aldot at gcc dot gnu dot org|unassigned at gcc dot gnu
| |dot org
Status|ASSIGNED |NEW
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (21 preceding siblings ...)
2010-07-09 8:10 ` aldot at gcc dot gnu dot org
@ 2010-07-09 17:12 ` jakub at gcc dot gnu dot org
2010-07-09 19:40 ` jakub at gcc dot gnu dot org
23 siblings, 0 replies; 26+ messages in thread
From: jakub at gcc dot gnu dot org @ 2010-07-09 17:12 UTC (permalink / raw)
To: gcc-bugs
------- Comment #20 from jakub at gcc dot gnu dot org 2010-07-09 17:12 -------
Created an attachment (id=21162)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=21162&action=view)
gcc46-pr28632.patch
Sorry, I haven't been aware of this PR. The attached patch brings in some of
the ideas from these patches and even goes beyond that. Tested so far just on
tree-ssa.exp=vrp*.c though, going to bootstrap/regtest it now.
--
jakub at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
AssignedTo|unassigned at gcc dot gnu |jakub at gcc dot gnu dot org
|dot org |
Status|NEW |ASSIGNED
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
` (22 preceding siblings ...)
2010-07-09 17:12 ` jakub at gcc dot gnu dot org
@ 2010-07-09 19:40 ` jakub at gcc dot gnu dot org
23 siblings, 0 replies; 26+ messages in thread
From: jakub at gcc dot gnu dot org @ 2010-07-09 19:40 UTC (permalink / raw)
To: gcc-bugs
------- Comment #21 from jakub at gcc dot gnu dot org 2010-07-09 19:40 -------
Subject: Bug 28632
Author: jakub
Date: Fri Jul 9 19:40:03 2010
New Revision: 162009
URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=162009
Log:
PR tree-optimization/28632
* tree-vrp.c (zero_nonzero_bits_from_vr): New function.
(extract_range_from_binary_expr): Further optimize
BIT_AND_EXPR and BIT_IOR_EXPR.
* gcc.dg/tree-ssa/vrp51.c: New test.
* gcc.dg/tree-ssa/vrp52.c: New test.
Added:
trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp51.c
trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp52.c
Modified:
trunk/gcc/ChangeLog
trunk/gcc/testsuite/ChangeLog
trunk/gcc/tree-vrp.c
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
^ permalink raw reply [flat|nested] 26+ messages in thread
* [Bug tree-optimization/28632] VRP should understand bitwise OR and AND
[not found] <bug-28632-4@http.gcc.gnu.org/bugzilla/>
@ 2010-09-24 11:36 ` jakub at gcc dot gnu.org
0 siblings, 0 replies; 26+ messages in thread
From: jakub at gcc dot gnu.org @ 2010-09-24 11:36 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28632
Jakub Jelinek <jakub at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|ASSIGNED |RESOLVED
Resolution| |FIXED
--- Comment #22 from Jakub Jelinek <jakub at gcc dot gnu.org> 2010-09-24 11:30:52 UTC ---
Fixed.
--
Configure bugmail: http://gcc.gnu.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.
^ permalink raw reply [flat|nested] 26+ messages in thread
end of thread, other threads:[~2010-09-24 11:31 UTC | newest]
Thread overview: 26+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2006-08-07 11:12 [Bug tree-optimization/28632] New: [PATCH] add VRP for bitwise OR and AND vda dot linux at googlemail dot com
2006-08-07 11:13 ` [Bug tree-optimization/28632] " vda dot linux at googlemail dot com
2006-08-07 11:14 ` vda dot linux at googlemail dot com
2006-08-07 11:26 ` vda dot linux at googlemail dot com
2006-08-07 14:54 ` pinskia at gcc dot gnu dot org
2006-08-08 0:37 ` [Bug tree-optimization/28632] VRP should understand " pinskia at gcc dot gnu dot org
2006-08-08 0:37 ` pinskia at gcc dot gnu dot org
2006-08-11 14:17 ` vda dot linux at googlemail dot com
2008-08-04 11:27 ` vda dot linux at googlemail dot com
2008-08-04 11:29 ` vda dot linux at googlemail dot com
2008-08-04 11:36 ` vda dot linux at googlemail dot com
2008-08-04 11:56 ` vda dot linux at googlemail dot com
2008-08-11 12:47 ` vda dot linux at googlemail dot com
2008-08-18 13:04 ` vda dot linux at googlemail dot com
2008-08-20 14:58 ` vda dot linux at googlemail dot com
2008-08-20 14:59 ` vda dot linux at googlemail dot com
2008-08-20 15:08 ` vda dot linux at googlemail dot com
2009-06-05 16:27 ` aldot at gcc dot gnu dot org
2009-06-10 16:48 ` aldot at gcc dot gnu dot org
2009-06-22 8:29 ` aldot at gcc dot gnu dot org
2010-01-02 1:00 ` steven at gcc dot gnu dot org
2010-07-09 7:53 ` aldot at gcc dot gnu dot org
2010-07-09 8:10 ` aldot at gcc dot gnu dot org
2010-07-09 17:12 ` jakub at gcc dot gnu dot org
2010-07-09 19:40 ` jakub at gcc dot gnu dot org
[not found] <bug-28632-4@http.gcc.gnu.org/bugzilla/>
2010-09-24 11:36 ` jakub at gcc dot gnu.org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).