Bug 21173 - [4.0/4.1 regression] miscompiled pointer subtraction broke Linux kernel
[4.0/4.1 regression] miscompiled pointer subtraction broke Linux kernel
Status: RESOLVED FIXED
Product: gcc
Classification: Unclassified
Component: tree-optimization
4.0.0
: P1 critical
: 4.0.1
Assigned To: Steven Bosscher
: patch, wrong-code
: 21167 21175 21248 21482 21505 21511 21618 21640 21711 22032 26811 26903 (view as bug list)
Depends on:
Blocks: 21167
  Show dependency treegraph
 
Reported: 2005-04-23 09:23 UTC by Mikael Pettersson
Modified: 2014-01-06 01:30 UTC (History)
18 users (show)

See Also:
Host:
Target:
Build:
Known to work: 3.4.4
Known to fail: 4.0.0 4.1.0
Last reconfirmed: 2005-04-23 12:30:26


Attachments
Patch I'm about to bootstrap/regtest (1.99 KB, patch)
2005-04-23 17:53 UTC, Jakub Jelinek
Details | Diff
patch (6.51 KB, patch)
2005-04-23 19:37 UTC, Steven Bosscher
Details | Diff
4.0 patch (7.64 KB, patch)
2005-04-23 22:37 UTC, Jakub Jelinek
Details | Diff
prediff.diff (1.33 KB, patch)
2005-04-24 03:36 UTC, Daniel Berlin
Details | Diff
Revised patch (6.23 KB, patch)
2005-04-24 10:31 UTC, Steven Bosscher
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Mikael Pettersson 2005-04-23 09:23:34 UTC
/* gcc4pointersubtractionbug.c
 * Written by Mikael Pettersson, mikpe@csd.uu.se, 2005-04-23.
 *
 * This program illustrates a code optimisation bug in
 * gcc-4.0.0 (final) and gcc-4.0.0-20050417, where a pointer
 * subtraction operation is compiled as a pointer addition.
 * Observed at -O2. gcc was configured for i686-pc-linux-gnu.
 *
 * This bug broke net/ipv4/devinet.c:devinet_sysctl_register()
 * in the linux-2.6.12-rc2 Linux kernel, causing /sbin/sysctl
 * to trigger kernel oopses.
 *
 * gcc-4.0.0-20050416 and earlier prereleases do not have this bug.
 */
#include <stdio.h>
#include <string.h>

#define NRVARS  5

struct ipv4_devconf {
    int var[NRVARS];
};
struct ipv4_devconf ipv4_devconf[2];

struct ctl_table {
    void *data;
};

struct devinet_sysctl_table {
    struct ctl_table devinet_vars[NRVARS];
};

void devinet_sysctl_relocate(struct devinet_sysctl_table *t,
                             struct ipv4_devconf *p)
{
    int i;

    for (i = 0; i < NRVARS; i++)
        /* Initially data points to a field in ipv4_devconf[0].
           This code relocates it to the corresponding field in *p.
           At -O2, gcc-4.0.0-20050417 and gcc-4.0.0 (final)
           miscompile this pointer subtraction as a pointer addition. */
        t->devinet_vars[i].data += (char *)p - (char *)&ipv4_devconf[0];
}

struct devinet_sysctl_table devinet_sysctl;

int main(void)
{
    struct devinet_sysctl_table t;
    int i;

    for(i = 0; i < NRVARS; i++)
        devinet_sysctl.devinet_vars[i].data = &ipv4_devconf[0].var[i];

    memcpy(&t, &devinet_sysctl, sizeof t);
    devinet_sysctl_relocate(&t, &ipv4_devconf[1]);

    for(i = 0; i < NRVARS; i++)
        if (t.devinet_vars[i].data != &ipv4_devconf[1].var[i]) {
            fprintf(stderr, "t.devinet_vars[%u].data == %p, should be %p\n",
                    i,
                    t.devinet_vars[i].data,
                    &ipv4_devconf[1].var[i]);
            return 1;
        }

    printf("all ok\n");
    return 0;
}
Comment 1 Serge Belyshev 2005-04-23 11:56:20 UTC
*** Bug 21175 has been marked as a duplicate of this bug. ***
Comment 2 Serge Belyshev 2005-04-23 12:30:24 UTC
// Confirmed on amd64 too, smaller testcase (compile with -O2):

void abort (void);

char q;
void *a[2];

void foo (char *p)
{
  int i;
  for (i = 0; i < 2; i++)
    a[i] += p - &q;
}

int main (void)
{
  int i;
  foo (&q);
  for (i = 0; i < 2; i ++)
    if (a[i])
      abort ();
  return 0;
}
Comment 3 Serge Belyshev 2005-04-23 12:51:47 UTC
-O1 -ftree-pre causing this.
Comment 4 Andrew Pinski 2005-04-23 13:18:28 UTC
Hmm, is -&a legal gimple, if it is then it is a PRE bug, otherwise it is a bug in the gimplifier.
Comment 5 Steven Bosscher 2005-04-23 13:24:50 UTC
.crited dump: 
 
foo (p) 
{ 
  int i; 
  void * D.1576; 
  char * D.1575; 
  void * D.1574; 
  void * D.1573; 
  int i.0; 
 
<bb 0>: 
 
  # i_16 = PHI <i_13(3), 0(0)>; 
<L0>:; 
  D.1573_7 = a[i_16]; 
  D.1574_9 = D.1573_7 + p_8; 
  D.1575_10 = -&q; 
  D.1576_11 = D.1574_9 + D.1575_10; 
  a[i_16] = D.1576_11; 
  i_13 = i_16 + 1; 
  if (i_13 <= 1) goto <L6>; else goto <L2>; 
 
<L6>:; 
  goto <bb 1> (<L0>); 
 
<L2>:; 
  return; 
 
} 
 
.pre dump: 
foo (p) 
{ 
  int pretmp.3; 
  char * pretmp.2; 
  int i; 
  void * D.1576; 
  char * D.1575; 
  void * D.1574; 
  void * D.1573; 
  int i.0; 
 
<bb 0>: 
  pretmp.2_6 = &q; 
 
  # i_16 = PHI <i_13(3), 0(0)>; 
<L0>:; 
  D.1573_7 = a[i_16]; 
  D.1574_9 = D.1573_7 + p_8; 
  D.1575_10 = pretmp.2_6; 
  D.1576_11 = D.1574_9 + D.1575_10; 
  a[i_16] = D.1576_11; 
  i_13 = i_16 + 1; 
  if (i_13 <= 1) goto <L6>; else goto <L2>; 
 
<L6>:; 
  goto <bb 1> (<L0>); 
 
<L2>:; 
  return; 
 
} 
 
Comment 6 Steven Bosscher 2005-04-23 13:36:19 UTC
This could be the same bug as the one reported on the mailing list here: 
http://gcc.gnu.org/ml/gcc/2005-04/msg01260.html 
Comment 7 Steven Bosscher 2005-04-23 13:39:12 UTC
ob-vi-ous... 
 
Index: tree-ssa-pre.c 
=================================================================== 
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-pre.c,v 
retrieving revision 2.80 
diff -u -3 -p -r2.80 tree-ssa-pre.c 
--- tree-ssa-pre.c      21 Apr 2005 18:05:27 -0000      2.80 
+++ tree-ssa-pre.c      23 Apr 2005 13:38:52 -0000 
@@ -1391,7 +1391,7 @@ create_expression_by_pieces (basic_block 
        if (!is_gimple_min_invariant (genop1)) 
          newexpr = force_gimple_operand (folded, &forced_stmts, false, NULL); 
        else 
-         newexpr = genop1; 
+         newexpr = folded; 
        if (forced_stmts) 
          { 
            tsi = tsi_start (forced_stmts); 
 
Comment 8 Jakub Jelinek 2005-04-23 14:59:19 UTC
Shouldn't that be then also:
-  if (!is_gimple_min_invariant (genop1))
+  if (!is_gimple_min_invariant (folded))
?
Comment 9 Daniel Berlin 2005-04-23 15:09:01 UTC
Subject: Re:  [4.0/4.1 regression] miscompiled
	pointer subtraction broke Linux kernel

On Sat, 2005-04-23 at 14:59 +0000, jakub at gcc dot gnu dot org wrote:
> ------- Additional Comments From jakub at gcc dot gnu dot org  2005-04-23 14:59 -------
> Shouldn't that be then also:
> -  if (!is_gimple_min_invariant (genop1))
> +  if (!is_gimple_min_invariant (folded))
> ?
> 
> 

yes

In fact, the error actually makes no sense (IE you guys are overlooking
an important fact).

is_gimple_min_invariants are legal operands to unary expressions,
regardless of whether they are "complex" or not, or so i was told.

So if genop1 is is_gimple_min_invariant, it should be fine there, and
you shouldn't need to use folded.

If it wasn't, we'd force_gimple_operand it.

I'm pretty sure you are just covering up a disconnect in what we allow
as gimple and what we handle.


Comment 10 Daniel Berlin 2005-04-23 15:13:12 UTC
Subject: Re:  [4.0/4.1 regression] miscompiled
	pointer subtraction broke Linux kernel

> yes
> 
> In fact, the error actually makes no sense (IE you guys are overlooking
> an important fact).
> 
> is_gimple_min_invariants are legal operands to unary expressions,
> regardless of whether they are "complex" or not, or so i was told.
> 
> So if genop1 is is_gimple_min_invariant, it should be fine there, and
> you shouldn't need to use folded.
> 

Forget it, genop1 doens't include the operation, and folded does. 
I forgot about that


Comment 11 Martin Schlemmer 2005-04-23 17:19:34 UTC
Patch from comment #7 seems to work here (doing make check now to verify).  I
assume the change Jakub asked about is not needed?
Comment 12 Jakub Jelinek 2005-04-23 17:53:39 UTC
Created attachment 8717 [details]
Patch I'm about to bootstrap/regtest
Comment 13 Daniel Berlin 2005-04-23 19:21:10 UTC
Subject: Re:  [4.0/4.1 regression] miscompiled
	pointer subtraction broke Linux kernel

On Sat, 2005-04-23 at 17:53 +0000, jakub at gcc dot gnu dot org wrote:
> ------- Additional Comments From jakub at gcc dot gnu dot org  2005-04-23 17:53 -------
> Created an attachment (id=8717)
>  --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=8717&action=view)
> Patch I'm about to bootstrap/regtest
> 
> 

As steven and i worked out, checking folded is wrong, so your patch is
wrong.

folded includes the unary operation, genop1 does not

IE folded = operation<genop1>

unary<min_invariant> is always okay

Thus, you want to check genop1 to see whether it is min_invariant, and
if so, use *folded*, which is operation<genop1>

Checking folded for invariantness is useless, and will just cause the
regression that caused the check in the first place to appear.


Comment 14 Steven Bosscher 2005-04-23 19:37:07 UTC
Created attachment 8718 [details]
patch

Jakub, your patch is wrong.  Try this one.
Comment 15 Jakub Jelinek 2005-04-23 22:37:08 UTC
Created attachment 8720 [details]
4.0 patch

Oops, right.  Your patch doesn't apply cleanly to 4.0 branch though, so here is
a backported one, bootstrapped/regtested on {i386,x86_64,s390,s390x,ppc}-linux
so far (no regressions there; ppc64 and ia64 still regtesting).
Comment 16 Steven Bosscher 2005-04-23 23:01:41 UTC
Subject: Re:  [4.0/4.1 regression] miscompiled pointer subtraction broke Linux kernel

Yeah, well, ehm...

The original bug resurfaces with my patch.  This happens because
is_gimple_reg_rhs only looks at the outermost level of the expression,
e.g. it happily accepts "(intD.0) -xD.1566_4" as a valid GIMPLE rhs.

Obviously this is wrong.

I'm testing a new patch that simply always runs force_gimple_operand
on folded, it's not clear to me why we don't do that anyway (it is
cheap and safer).

Comment 17 Daniel Berlin 2005-04-24 03:36:30 UTC
Subject: Re:  [4.0/4.1 regression] miscompiled
	pointer subtraction broke Linux kernel

On Sat, 2005-04-23 at 23:01 +0000, stevenb at suse dot de wrote:
> ------- Additional Comments From stevenb at suse dot de  2005-04-23 23:01 -------
> Subject: Re:  [4.0/4.1 regression] miscompiled pointer subtraction broke Linux kernel
> 
> Yeah, well, ehm...
> 
> The original bug resurfaces with my patch.  This happens because
> is_gimple_reg_rhs only looks at the outermost level of the expression,
> e.g. it happily accepts "(intD.0) -xD.1566_4" as a valid GIMPLE rhs.
> 
> Obviously this is wrong.
> 
> I'm testing a new patch that simply always runs force_gimple_operand
> on folded, it's not clear to me why we don't do that anyway (it is
> cheap and safer).
> 
> 

Uh, because it causes things to become non-invariant when they were
originally invariant (because it will *always* create a new name for
them).

We expect that an expression that was originally invariant is still
invariant when regenerated, which is a perfectly reasonable expectation.

The particular bug that occurred (20963) was that we had

folded = (charD.3 *) &0B->typeD.1931 

force_gimple_operand on folded (which is already valid GIMPLE) gave us
D.1970_10 = 0B; 
D.1971_2 = &D.1970_10->typeD.1931; 
newexpr = (charD.3 *) D.1971_2 

This later screwed up our antic set, which thinking about it, doesn't make sense it was never put there, it came from there.

Actually, i just discovered why this is.
It's because force_gimple_operand enjoys destructively changing trees you give it, instead of making new ones for you.
Yay for undocumented semantics!

The attached patch should fix all of these problems at once (though it will increase memory usage a bit :( ) without causing regressions.

Please give it a try

Comment 18 Daniel Berlin 2005-04-24 03:36:31 UTC
Created attachment 8721 [details]
prediff.diff
Comment 19 Steven Bosscher 2005-04-24 09:23:42 UTC
Subject: Re:  [4.0/4.1 regression] miscompiled pointer subtraction broke Linux kernel

On Sunday 24 April 2005 05:36, dberlin at dberlin dot org wrote:
> Uh, because it causes things to become non-invariant when they were
> originally invariant (because it will *always* create a new name for
> them).

Well, the comment before force_gimple_operand says it should not:

/* Expands EXPR to list of gimple statements STMTS.  If SIMPLE is true,
   force the result to be either ssa_name or an invariant, otherwise
   just force it to be a rhs expression.  If VAR is not NULL, make the
   base variable of the final destination be VAR if suitable.  */

tree
force_gimple_operand (tree expr, tree *stmts, bool simple, tree var)
{


tree-ssa-pre uses force_gimple_operand with SIMPLE==false, so if
expr is already a valid rhs, force_gimple_operand should do nothing.
If it does, I consider that to be a bug.

Your patch to use unshare_expr is IMHO unnecessarily expensive.

Comment 20 Steven Bosscher 2005-04-24 10:31:33 UTC
Created attachment 8722 [details]
Revised patch

This is what I've booted/tested...  Dan, can you give an example where
this would do the wrong thing for invariants?
Comment 21 Daniel Berlin 2005-04-24 15:19:48 UTC
Please compile the testcase from 20963, with and without the unshare_expr in the
patch i posted, and you'll see the bug.  force_gimple_operand replaces
TREE_OPERAND (folded, 0) with something else. folded came directly from the
ANTIC set, so we can't touch it like that (we'd have to make it copy first).

force_gimple_operand is replacing operands in what we pass it, which causes
errors for us.
You *need* to either fix it, or pass it a copy of the expression.
Comment 22 Daniel Berlin 2005-04-24 15:27:39 UTC
Subject: Re:  [4.0/4.1 regression] miscompiled
	pointer subtraction broke Linux kernel


> tree-ssa-pre uses force_gimple_operand with SIMPLE==false, so if
> expr is already a valid rhs, force_gimple_operand should do nothing.
> If it does, I consider that to be a bug.
> 
> Your patch to use unshare_expr is IMHO unnecessarily expensive.
> 
> 
> 

Here's the gdb trace, btw:

 Breakpoint 3, create_expression_by_pieces (block=0x400c4870,
expr=0x88403f0, stmts=0x400c6510) at tree-ssa-pre.c:1322

expr came from a node in ANTIC_IN, we *can't* modify it, because it's
not a copy.


(gdb) p debug_generic_stmt (expr)
(charD.3 *) &0B->typeD.1681;
...

1388            newexpr = force_gimple_operand (folded,
(gdb) n
1390            if (forced_stmts)
(gdb) p debug_generic_stmt (expr)
(charD.3 *) &D.1708_3->typeD.1681;

tada!


This is the reason we have to unshare it before passing it in.


Comment 23 CVS Commits 2005-04-25 13:59:59 UTC
Subject: Bug 21173

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	dberlin@gcc.gnu.org	2005-04-25 13:59:39

Modified files:
	gcc            : ChangeLog tree-ssa-pre.c 

Log message:
	2005-04-25  Steven Bosscher  <stevenb@suse.de>
	
	Fix PR tree-optimization/21173
	
	* tree-ssa-pre.c (create_expression_by_pieces): Simplify code.
	Unshare expression we pass to force_gimple_operand.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.8450&r2=2.8451
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-pre.c.diff?cvsroot=gcc&r1=2.81&r2=2.82

Comment 24 CVS Commits 2005-04-25 14:03:08 UTC
Subject: Bug 21173

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	gcc-4_0-branch
Changes by:	dberlin@gcc.gnu.org	2005-04-25 14:02:38

Modified files:
	gcc            : ChangeLog tree-ssa-pre.c 

Log message:
	2005-04-25  Daniel Berlin  <dberlin@dberlin.org>
	
	Fix PR tree-optimization/21173
	
	* tree-ssa-pre.c (create_expression_by_pieces): Call unshare_expr
	on things we pass to force_gimple_operand.  Don't try to special
	case min_invariants.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=2.7592.2.192&r2=2.7592.2.193
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-pre.c.diff?cvsroot=gcc&only_with_tag=gcc-4_0-branch&r1=2.65.4.2&r2=2.65.4.3

Comment 25 CVS Commits 2005-04-25 14:18:41 UTC
Subject: Bug 21173

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	dberlin@gcc.gnu.org	2005-04-25 14:18:31

Added files:
	gcc/testsuite/gcc.c-torture/execute: pr21173.c 

Log message:
	Testcase for pr 21173

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.c-torture/execute/pr21173.c.diff?cvsroot=gcc&r1=NONE&r2=1.1

Comment 26 Andrew Pinski 2005-04-25 14:47:20 UTC
*** Bug 21167 has been marked as a duplicate of this bug. ***
Comment 27 Jakub Jelinek 2005-04-25 14:49:47 UTC
Are you going to commit the testcase to the branch as well?
Comment 28 Daniel Berlin 2005-04-25 15:18:14 UTC
Subject: Re:  [4.0/4.1 regression] miscompiled
	pointer subtraction broke Linux kernel

On Mon, 2005-04-25 at 14:49 +0000, jakub at gcc dot gnu dot org wrote:
> ------- Additional Comments From jakub at gcc dot gnu dot org  2005-04-25 14:49 -------
> Are you going to commit the testcase to the branch as well?
> 
> 
Yes

i'm waiting for a lock


Comment 29 Daniel Berlin 2005-04-26 12:35:55 UTC
Fixed
Comment 30 Serge Belyshev 2005-04-28 02:34:56 UTC
*** Bug 21248 has been marked as a duplicate of this bug. ***
Comment 31 CVS Commits 2005-04-28 23:38:23 UTC
Subject: Bug 21173

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	apple-local-200502-branch
Changes by:	dalej@gcc.gnu.org	2005-04-28 23:38:11

Modified files:
	gcc            : ChangeLog.apple-ppc tree-ssa-pre.c 

Log message:
	2005-04-28  Dale Johannesen  <dalej@apple.com>
	
	Radar 4100712 (PR 21173, Dan Berlin's patch)
	
	* tree-ssa-pre.c (create_expression_by_pieces): Call unshare_expr
	on things we pass to force_gimple_operand.  Don't try to special
	case min_invariants.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.apple-ppc.diff?cvsroot=gcc&only_with_tag=apple-local-200502-branch&r1=1.1.4.53&r2=1.1.4.54
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-pre.c.diff?cvsroot=gcc&only_with_tag=apple-local-200502-branch&r1=2.64.2.2&r2=2.64.2.3

Comment 32 Andrew Pinski 2005-05-10 17:32:26 UTC
*** Bug 21482 has been marked as a duplicate of this bug. ***
Comment 33 Andrew Pinski 2005-05-10 22:31:42 UTC
*** Bug 21505 has been marked as a duplicate of this bug. ***
Comment 34 Andrew Pinski 2005-05-11 10:51:10 UTC
*** Bug 21511 has been marked as a duplicate of this bug. ***
Comment 35 Andrew Pinski 2005-05-17 11:34:05 UTC
*** Bug 21618 has been marked as a duplicate of this bug. ***
Comment 36 Andrew Pinski 2005-05-18 06:04:29 UTC
*** Bug 21640 has been marked as a duplicate of this bug. ***
Comment 37 Andrew Pinski 2005-05-22 18:47:44 UTC
*** Bug 21711 has been marked as a duplicate of this bug. ***
Comment 38 Andrew Pinski 2005-06-12 13:24:17 UTC
*** Bug 22032 has been marked as a duplicate of this bug. ***
Comment 39 Andrew Pinski 2006-03-22 20:54:00 UTC
*** Bug 26811 has been marked as a duplicate of this bug. ***
Comment 40 Andrew Pinski 2006-03-28 17:40:34 UTC
*** Bug 26903 has been marked as a duplicate of this bug. ***