[Bug c/49330] New: Integer arithmetic on addresses optimised with pointer arithmetic rules

[Bug c/49330] New: Integer arithmetic on addresses optimised with pointer arithmetic rules

[harald at gigawatt dot nl]

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

           Summary: Integer arithmetic on addresses optimised with pointer
                    arithmetic rules
           Product: gcc
           Version: 4.6.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: harald@gigawatt.nl


#include <stdint.h>
int x, y;
int main(void) {
  uintptr_t px = (uintptr_t) &x;
  uintptr_t py = (uintptr_t) &y;
  volatile uintptr_t d = px - py;
  uintptr_t p = py + d;
  x = 1;
  *(int *) p = 2;
  return x;
}

gcc 4.6(20110603) returns 1 at -O1 or higher. configure options:

--build=x86_64-pc-linux-gnu --host=x86_64-pc-linux-gnu --prefix=/usr
--sysconfdir=/etc --program-suffix=-4.6 --enable-languages=c,c++
--enable-checking --enable-build-with-cxx

As far as I can see, this program is perfectly valid and is required to return
2. gcc seems to be optimising on the assumption that an addition to &y will not
result in a pointer to a distinct object (and so stores 2 in y), but that
assumption is only correct for a pointer addition, which the above is not.

[Bug c/49330] Integer arithmetic on addresses optimised with pointer arithmetic rules

[harald at gigawatt dot nl]

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

--- Comment #1 from Harald van Dijk <harald at gigawatt dot nl> 2011-06-08 20:42:04 UTC ---
A similar example, but one which does not convert the integer back to a
pointer:

#include <stdio.h>
#include <stdlib.h>
int a;
int main() {
  unsigned long b = (unsigned long) &a - 134518548;
  volatile unsigned long c = b;
  if (c == 0) {
    if (b != 0) abort ();
  }
  printf("%lu\n", c);
  return a;
}

This should never abort. It aborts on my system (with -m32).

[Bug rtl-optimization/49330] Integer arithmetic on addresses optimised with pointer arithmetic rules

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011.06.09 09:36:46
                 CC|                            |ebotcazou at gcc dot
                   |                            |gnu.org
          Component|c                           |rtl-optimization
     Ever Confirmed|0                           |1
      Known to fail|                            |4.3.5, 4.4.5, 4.5.3, 4.6.0,
                   |                            |4.7.0

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-06-09 09:36:46 UTC ---
I can confirm the original testcase with r173419 (not the one from comment#1).
The tree level optimizers handle this ok and we expand from

<bb 2>:
  px_1 = (uintptr_t) &x;
  py_2 = (uintptr_t) &y;
  d.0_3 = px_1 - py_2;
  d ={v} d.0_3;
  d.1_4 ={v} d;
  p_5 = d.1_4 + py_2;
  x = 1;
  # PT = { x y } (glob)
  p.2_6 = (int *) p_5;
  *p.2_6 = 2;
  D.2722_7 = x;
  return D.2722_7;

where you can also see that we correctly assume that p.2_6 may point either
x or y.

CSE1 optimizes the load from x to 1.

[Bug rtl-optimization/49330] Integer arithmetic on addresses optimised with pointer arithmetic rules

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-06-09 10:04:28 UTC ---
Ugh.
base_alias_check for
(symbol_ref:DI ("x") <var_decl 0x7ffff1a32000 x>)
and
(plus:DI (reg:DI 62 [ d.1 ])
    (symbol_ref:DI ("y") <var_decl 0x7ffff1a320a0 y>))
returns 0.  I'm afraid dropping the base_alias_check call would significantly
penalize generated code, after all we still sometimes have MEM accesses without
MEM_EXPR.  Perhaps we could rely on REG_POINTER bits, extend them to SYMBOL_REF
too and only do return NULL from find_base_term if SYMBOL_REF doesn't have
SYMBOL_REF_POINTER bit set.  During CSE etc., when replacing a pseudo with its
definition REG_POINTER/SYMBOL_REF_POINTER would be kept only if it is set on
the pseudo being optimized away as well.  Thus, any casts from pointers to
correspondingly sized integers and back would be seen in the RTL.

[Bug rtl-optimization/49330] Integer arithmetic on addresses optimised with pointer arithmetic rules

[rguenther at suse dot de]

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

--- Comment #4 from rguenther at suse dot de <rguenther at suse dot de> 2011-06-09 10:08:55 UTC ---
On Thu, 9 Jun 2011, jakub at gcc dot gnu.org wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49330
> 
> Jakub Jelinek <jakub at gcc dot gnu.org> changed:
> 
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>                  CC|                            |jakub at gcc dot gnu.org
> 
> --- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-06-09 10:04:28 UTC ---
> Ugh.
> base_alias_check for
> (symbol_ref:DI ("x") <var_decl 0x7ffff1a32000 x>)
> and
> (plus:DI (reg:DI 62 [ d.1 ])
>     (symbol_ref:DI ("y") <var_decl 0x7ffff1a320a0 y>))
> returns 0.  I'm afraid dropping the base_alias_check call would significantly
> penalize generated code, after all we still sometimes have MEM accesses without
> MEM_EXPR.  Perhaps we could rely on REG_POINTER bits, extend them to SYMBOL_REF
> too and only do return NULL from find_base_term if SYMBOL_REF doesn't have
> SYMBOL_REF_POINTER bit set.  During CSE etc., when replacing a pseudo with its
> definition REG_POINTER/SYMBOL_REF_POINTER would be kept only if it is set on
> the pseudo being optimized away as well.  Thus, any casts from pointers to
> correspondingly sized integers and back would be seen in the RTL.

Maybe restrict the base_alias_check to var-decls that do not have
their address taken?  Points-to analysis should conver them.

Richard.

[Bug rtl-optimization/49330] Integer arithmetic on addresses optimised with pointer arithmetic rules

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-06-09 10:22:57 UTC ---
The testcase also fails similarly without the volatile qualification of d
when compiling with -O -fno-tree-fre -fno-tree-forwprop -fno-tree-reassoc

[Bug rtl-optimization/49330] Integer arithmetic on addresses optimised with pointer arithmetic rules

[jakub at gcc dot gnu.org]

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-06-09 10:38:37 UTC ---
find_base_value/find_base_term seem to be overly optimistic, prefer to return
something over being conservative.  E.g. if both operands of PLUS or MINUS
return non-NULL find_base_term, we just return the first one, etc.
It doesn't differentiate between "certainly not based on something" - e.g.
CONST_INT, regs only initialized by them and only incremented by constant etc.
would be such and unknown.  While the overly optimistic implementation might be
useful in some cases, at least for base_alias_check it is inappropriate.

[Bug rtl-optimization/49330] Integer arithmetic on addresses optimised with pointer arithmetic rules

[ebotcazou at gcc dot gnu.org]

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

--- Comment #7 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2011-06-10 09:50:28 UTC ---
The alias.c machinery is clearly based on the fundamental assumption of pointer
arithmetics, i.e. that you aren't allowed to compute a difference unless both
pointers point to the same enclosing object.  The testcase is a nice attempt at
smuggling the violation of this rule behind a uintptr_t based manipulation.

Not clear what to do IMO.  Richard is proposing to leverage the escape sites:

  px_1 = (uintptr_t) &x;
  py_2 = (uintptr_t) &y;

but this will pessimize.  Ideally we should leverage the one problematic line:

  p.2_6 = (int *) p_5;

which creates the pointer out of the integer, but it has already disappeared in
the very first RTL representation.

[Bug rtl-optimization/49330] Integer arithmetic on addresses optimised with pointer arithmetic rules

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-06-10 09:59:06 UTC ---
(In reply to comment #7)
> The alias.c machinery is clearly based on the fundamental assumption of pointer
> arithmetics, i.e. that you aren't allowed to compute a difference unless both
> pointers point to the same enclosing object.  The testcase is a nice attempt at
> smuggling the violation of this rule behind a uintptr_t based manipulation.
> 
> Not clear what to do IMO.  Richard is proposing to leverage the escape sites:
> 
>   px_1 = (uintptr_t) &x;
>   py_2 = (uintptr_t) &y;
> 
> but this will pessimize.  Ideally we should leverage the one problematic line:
> 
>   p.2_6 = (int *) p_5;
> 
> which creates the pointer out of the integer, but it has already disappeared in
> the very first RTL representation.

Creating that pointer is perfectly valid - you are allowed to cast a
pointer to an uintptr_t and back, which is what the code does (in some
obfuscated way of course).

p.2_6 = (int *) ((uintptr_t) &y + ((uintptr_t) &x - (uintptr_t) &y)))

which is, as is trivially obvious, (int *) (uintptr_t) &x.

Consider

int foo(uintptr_t a)
{
  uintptr_t px = (uintptr_t) &x;
  uintptr_t py = a;
  volatile uintptr_t d = px - py;
  uintptr_t p = py + d;
  x = 1;
  *(int *) p = 2;
  return x;
}

int main() { foo(&y); }

which is equivalent.

[Bug rtl-optimization/49330] Integer arithmetic on addresses optimised with pointer arithmetic rules

[ebotcazou at gcc dot gnu.org]

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

--- Comment #9 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2011-06-10 10:55:53 UTC ---
> Creating that pointer is perfectly valid - you are allowed to cast a
> pointer to an uintptr_t and back, which is what the code does (in some
> obfuscated way of course).

No disagreement, "problematic" only in the sense that it breaks the assumption
of the aliasing machinery, as you're creating a pointer out of nothing.

[Bug rtl-optimization/49330] Integer arithmetic on addresses optimised with pointer arithmetic rules

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-06-10 11:13:53 UTC ---
(In reply to comment #9)
> > Creating that pointer is perfectly valid - you are allowed to cast a
> > pointer to an uintptr_t and back, which is what the code does (in some
> > obfuscated way of course).
> 
> No disagreement, "problematic" only in the sense that it breaks the assumption
> of the aliasing machinery, as you're creating a pointer out of nothing.

Indeed.  I fixed similar bugs in tree points-to analysis, like

int x, y;
int foo (int *p)
{
  int *q = &x;
  int *p = &y;
  int i;
  for (i=0; i<sizeof(int *); ++i)
    ((char *)&q)[i] = ((char *)&p)[i];
  *p = 1;
  *q = 2;
  return *p;
}

which I suspect might work on RTL only by accident (at -O3 with the
loop unrolled).

[Bug rtl-optimization/49330] Integer arithmetic on addresses optimised with pointer arithmetic rules

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jdemeyer at cage dot
                   |                            |ugent.be

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-03-06 23:49:08 UTC ---
*** Bug 52517 has been marked as a duplicate of this bug. ***

[Bug rtl-optimization/49330] Integer arithmetic on addresses optimised with pointer arithmetic rules

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49330

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |msebor at gcc dot gnu.org

--- Comment #32 from Martin Sebor <msebor at gcc dot gnu.org> ---
*** Bug 88433 has been marked as a duplicate of this bug. ***

[Bug rtl-optimization/49330] Integer arithmetic on addresses optimised with pointer arithmetic rules

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49330

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |iii at linux dot ibm.com

--- Comment #33 from Richard Biener <rguenth at gcc dot gnu.org> ---
*** Bug 114404 has been marked as a duplicate of this bug. ***