[Bug c/30364] New: Wrong variable ranges due to constant folding

[Bug c/30364] New: Wrong variable ranges due to constant folding

[guillaume dot melquiond at ens-lyon dot fr]

Testcase: (compiled with -O2 at least)

int f(int a, int b)
{
  if (a > 0x7FFFFFF0) return 0;
  if (b > 0x7FFFFFF0) return 0;

  int c = (a - 20) + (b - 20);
  return c > 0x7FFFFFF0;
}

GCC 4.1.2 and 4.3.0 (snapshot from 2006-12-17) optimizes the whole function to
a single "return 0;". This would be correct if the function was actually
written with "c = a + b - 40" under a non-overflow assumption. GCC could indeed
deduce that c is no bigger than 0x7FFFFFFF - 40.

But as the function was originally written, this property does not hold any
longer. For example, a = 0x7FFFFFF0 and b = 41 will not cause any overflow
during computations, and the last conditional shall hence evaluate to true.

The problem is that GCC performs VRP with C language semantic (undefined
behavior on overflow) on code that is no longer the input as written by the
user; so this semantic is not valid at that point. The user input should not
have undergone a transformation based on associativity.

Tested with Debian packages. GCC 3.3.6, 3.4.6, and 4.0.4 generate correct code.
GCC 4.1.2 and 4.3.0 generates wrong code. As the expression "a + b - 40" is
generated early, I suppose any GCC with VRP would produce wrong code for this
testcase.


-- 
           Summary: Wrong variable ranges due to constant folding
           Product: gcc
           Version: 4.1.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: guillaume dot melquiond at ens-lyon dot fr


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant folding

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
          Component|c                           |middle-end
           Keywords|                            |wrong-code
            Summary|Wrong variable ranges due to|[4.1/4.2/4.3 Regression]
                   |constant folding            |Wrong variable ranges due to
                   |                            |constant folding
   Target Milestone|---                         |4.1.2


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant folding

[guillaume dot melquiond at ens-lyon dot fr]

------- Comment #1 from guillaume dot melquiond at ens-lyon dot fr  2007-01-04 10:15 -------
Is it really a middle-end issue?

It could also be seen as a front-end issue, as it does produce "a + b - 40",
doesn't it? If the front-end had given "(a - 20) + (b - 20)" to the middle-end,
then the correct ranges would have been computed. When adjusting the testcase
in such a way, GCC does generate correct code:

int f(int a, int b)
{
  if (a > 0x7FFFFFF0) return 0;
  if (b > 0x7FFFFFF0) return 0;

  int d = a - 20;
  int e = b - 20;
  int c = d + e;
  return c > 0x7FFFFFF0;
}


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant folding

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2007-01-04 10:23 -------
(In reply to comment #1)
> Is it really a middle-end issue?
Yes because fold is part of the middle-end that is most likely causing this
being translated into "a + b - 40".

And this is the reason why the way wrote it the second way works is because
fold does not see the full expression so it does not do the folding.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant folding

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2007-01-04 10:26 -------
This most likely comes from the "    associate:" case in fold_binary where we
reassociate the PLUS_EXPR and MINUS_EXPR and then fold the -20 + -20 into -40.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant folding

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |blocker


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant folding

[guillaume dot melquiond at ens-lyon dot fr]

------- Comment #4 from guillaume dot melquiond at ens-lyon dot fr  2007-01-04 11:25 -------
Just for the sake of completeness. Wrong code is also generated when addition
and multiplication are mixed, because of distributivity:

int f(int a)
{
  if (a > 0x7FFFFFF0) return 0;
  int b = (a - 20) * 2;
  return b > 0x7FFFFFF0;
}


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant folding

[jakub at gcc dot gnu dot org]

------- Comment #5 from jakub at gcc dot gnu dot org  2007-01-05 19:06 -------
Do the parenthesis matter in C?  They do matter in say Fortran, but in C I
think
(a - 20) + (b - 20) can be evaluated as (a + b) + (-20 + -20) or a - 20 - 20 +
b
etc.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant folding

[pinskia at gcc dot gnu dot org]

------- Comment #6 from pinskia at gcc dot gnu dot org  2007-01-05 19:58 -------
(In reply to comment #5)
> Do the parenthesis matter in C?  They do matter in say Fortran, but in C I
> think
> (a - 20) + (b - 20) can be evaluated as (a + b) + (-20 + -20) or a - 20 - 20 +
> b
> etc.

In fact, a-20 + c will be valid even if a+c overflows but (a-20) + c does not. 
There are comments in the standard somewhere which makes a mention of this. 


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant folding

[pinskia at gcc dot gnu dot org]

------- Comment #7 from pinskia at gcc dot gnu dot org  2007-01-05 20:32 -------
>From C99, 5.1.2.3/14:
14 EXAMPLE 6 To illustrate the grouping behavior of expressions, in the
following fragment
int a, b;
/* ... */
a = a + 32760 + b + 5;
the expression statement behaves exactly the same as
a = (((a + 32760) + b) + 5);
due to the associativity and precedence of these operators. Thus, the result of
the sum (a + 32760) is
next added to b, and that result is then added to 5 which results in the value
assigned to a. On a machine in
which overflows produce an explicit trap and in which the range of values
representable by an int is
[−32768, +32767], the implementation cannot rewrite this expression as
a = ((a + b) + 32765);
since if the values for a and b were, respectively, −32754 and −15,
the sum a + b would produce a trap
while the original expression would not; nor can the expression be rewritten
either as
a = ((a + 32765) + b);
or
a = (a + (b + 32765));
since the values for a and b might have been, respectively, 4 and −8 or
−17 and 12. However, on a machine
in which overflow silently generates some value and where positive and negative
overflows cancel, the
above expression statement can be rewritten by the implementation in any of the
above ways because the
same result will occur.

That is most explict thing about overflow and groupping.  In C, every
expression has an implicate parenthesises.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant folding

[gdr at integrable-solutions dot net]

------- Comment #8 from gdr at integrable-solutions dot net  2007-01-05 21:06 -------
Subject: Re:  [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant
folding

"jakub at gcc dot gnu dot org" <gcc-bugzilla@gcc.gnu.org> writes:

| Do the parenthesis matter in C?

Yes, see paragraphes 11 dowward in the section 5.1.2.3.

|  They do matter in say Fortran, but in C I
| think
| (a - 20) + (b - 20) can be evaluated as (a + b) + (-20 + -20) or a - 20 - 20
+
| b

while that is permitted by the fortran standard, it is my understanding
that *existing* practice has fortran compilers refrain from messing
with parenthesis.

However, this has become a middle-end issue; so I guess I must voice
the concern for languages where unconditional re-association is not
permitted.  The C and C++ languages are example of those.


-- Gaby


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant folding

[gdr at integrable-solutions dot net]

------- Comment #9 from gdr at integrable-solutions dot net  2007-01-05 21:09 -------
Subject: Re:  [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant
folding

"pinskia at gcc dot gnu dot org" <gcc-bugzilla@gcc.gnu.org> writes:


[...]

| That is most explict thing about overflow and groupping.  In C, every
| expression has an implicate parenthesises.

Yes.

Note. however, that if people don't insist on signed integer
arithmetic overflow being undefined, but intead define it as wrapping,
they can reassociate and as they wish and the result won't change.

-- Gaby


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant folding

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant folding

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.1.2                       |4.1.3


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant folding

[rguenth at gcc dot gnu dot org]

------- Comment #10 from rguenth at gcc dot gnu dot org  2007-02-21 14:24 -------
Mine.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-02-21 14:24:36
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2/4.3 Regression] Wrong variable ranges due to constant folding

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2007-02-28 21:56 -------
Subject: Bug 30364

Author: rguenth
Date: Wed Feb 28 21:56:41 2007
New Revision: 122414

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=122414
Log:
2007-02-28  Richard Guenther  <rguenther@suse.de>

        PR middle-end/30364
        * fold-const.c (fold_binary): Do not associate expressions
        with more than one variable for integer types that do not wrap.

        * gcc.dg/torture/pr30364-1.c: New testcase.
        * gcc.dg/torture/pr30364-2.c: Likewise.
        * gcc.dg/torture/pr30364-3.c: Likewise.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr30364-1.c
    trunk/gcc/testsuite/gcc.dg/torture/pr30364-2.c
    trunk/gcc/testsuite/gcc.dg/torture/pr30364-3.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/fold-const.c
    trunk/gcc/testsuite/ChangeLog


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2 Regression] Wrong variable ranges due to constant folding

[rguenth at gcc dot gnu dot org]

------- Comment #12 from rguenth at gcc dot gnu dot org  2007-02-28 23:03 -------
Fixed on the mainline.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[4.1/4.2/4.3 Regression]    |[4.1/4.2 Regression] Wrong
                   |Wrong variable ranges due to|variable ranges due to
                   |constant folding            |constant folding


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1/4.2 Regression] Wrong variable ranges due to constant folding

[rguenth at gcc dot gnu dot org]

------- Comment #13 from rguenth at gcc dot gnu dot org  2007-03-05 13:15 -------
Subject: Bug 30364

Author: rguenth
Date: Mon Mar  5 13:15:25 2007
New Revision: 122548

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=122548
Log:
2007-03-05  Richard Guenther  <rguenther@suse.de>

        Backport from mainline:
        2007-02-28  Richard Guenther  <rguenther@suse.de>

        PR middle-end/30364
        * fold-const.c (fold_binary): Do not associate expressions
        with more than one variable for integer types that do not wrap.

        * gcc.dg/torture/pr30364-1.c: New testcase.
        * gcc.dg/torture/pr30364-2.c: Likewise.
        * gcc.dg/torture/pr30364-3.c: Likewise.

Added:
    branches/gcc-4_2-branch/gcc/testsuite/gcc.dg/torture/pr30364-1.c
      - copied unchanged from r122414,
trunk/gcc/testsuite/gcc.dg/torture/pr30364-1.c
    branches/gcc-4_2-branch/gcc/testsuite/gcc.dg/torture/pr30364-2.c
      - copied unchanged from r122414,
trunk/gcc/testsuite/gcc.dg/torture/pr30364-2.c
    branches/gcc-4_2-branch/gcc/testsuite/gcc.dg/torture/pr30364-3.c
      - copied unchanged from r122414,
trunk/gcc/testsuite/gcc.dg/torture/pr30364-3.c
Modified:
    branches/gcc-4_2-branch/gcc/ChangeLog
    branches/gcc-4_2-branch/gcc/fold-const.c
    branches/gcc-4_2-branch/gcc/testsuite/ChangeLog


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1 Regression] Wrong variable ranges due to constant folding

[rguenth at gcc dot gnu dot org]

------- Comment #14 from rguenth at gcc dot gnu dot org  2007-03-05 13:16 -------
And the 4.2 branch.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |4.1.2
            Summary|[4.1/4.2 Regression] Wrong  |[4.1 Regression] Wrong
                   |variable ranges due to      |variable ranges due to
                   |constant folding            |constant folding


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1 Regression] Wrong variable ranges due to constant folding

[rguenth at gcc dot gnu dot org]

------- Comment #15 from rguenth at gcc dot gnu dot org  2007-03-15 18:09 -------
Subject: Bug 30364

Author: rguenth
Date: Thu Mar 15 18:09:26 2007
New Revision: 122956

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=122956
Log:
2007-03-15  Richard Guenther  <rguenther@suse.de>

        Backport from mainline
        2007-02-28  Richard Guenther  <rguenther@suse.de>

        PR middle-end/30364
        * fold-const.c (fold_binary): Do not associate expressions
        with more than one variable for integer types that do not wrap.

        * gcc.dg/torture/pr30364-1.c: New testcase.
        * gcc.dg/torture/pr30364-2.c: Likewise.
        * gcc.dg/torture/pr30364-3.c: Likewise.

Added:
    branches/gcc-4_1-branch/gcc/testsuite/gcc.dg/torture/pr30364-1.c
      - copied unchanged from r122548,
branches/gcc-4_2-branch/gcc/testsuite/gcc.dg/torture/pr30364-1.c
    branches/gcc-4_1-branch/gcc/testsuite/gcc.dg/torture/pr30364-2.c
      - copied unchanged from r122548,
branches/gcc-4_2-branch/gcc/testsuite/gcc.dg/torture/pr30364-2.c
    branches/gcc-4_1-branch/gcc/testsuite/gcc.dg/torture/pr30364-3.c
      - copied unchanged from r122548,
branches/gcc-4_2-branch/gcc/testsuite/gcc.dg/torture/pr30364-3.c
Modified:
    branches/gcc-4_1-branch/gcc/ChangeLog
    branches/gcc-4_1-branch/gcc/fold-const.c
    branches/gcc-4_1-branch/gcc/testsuite/ChangeLog


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1 Regression] Wrong variable ranges due to constant folding

[rguenth at gcc dot gnu dot org]

------- Comment #16 from rguenth at gcc dot gnu dot org  2007-03-15 18:10 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1 Regression] Wrong variable ranges due to constant folding

[jakub at gcc dot gnu dot org]

------- Comment #17 from jakub at gcc dot gnu dot org  2007-08-24 16:33 -------
Does this make sense to do this for POINTER_TYPE_P in 4.1/4.2, which
reassociate
in many other places?
I belive in 4.3 that changed with POINTER_PLUS_EXPR stuff.

struct A { int i; int v[10000]; };
int *foo (struct A *a, int x)
{
  return &a->v[x - 2147483646];
}

in 4.2/4.1 gives:

foo (a, x)
{
<bb 2>:
  return &a->v[0] - 4294967288B + (int *) ((unsigned int) x * 4);

}

so it will overflow (well, underflow).

E.g. on Linux kernel code this commit causes some stack size usage regressions.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364

[Bug middle-end/30364] [4.1 Regression] Wrong variable ranges due to constant folding

[rguenth at gcc dot gnu dot org]

------- Comment #18 from rguenth at gcc dot gnu dot org  2007-08-24 16:40 -------
Maybe - I was just conservative here to not possibly introduce new overflow
with the re-association as elsewhere we may rely on the undefinedness of
overflow.

Another way to fix this particular regression is to disable the decomposing
of &a->v[x - 2147483646] to pointer arithmetic in the C frontend here:

      /* For &x[y], return x+y */
      if (TREE_CODE (arg) == ARRAY_REF)
        {
          tree op0 = TREE_OPERAND (arg, 0);
          if (!c_mark_addressable (op0))
            return error_mark_node;
          return build_binary_op (PLUS_EXPR,
                                  (TREE_CODE (TREE_TYPE (op0)) == ARRAY_TYPE
                                   ? array_to_pointer_conversion (op0)
                                   : op0),
                                  TREE_OPERAND (arg, 1), 1);
        }

like I tried a couple of times.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30364