Bug 49330 - Integer arithmetic on addresses optimised with pointer arithmetic rules
Summary: Integer arithmetic on addresses optimised with pointer arithmetic rules
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: rtl-optimization (show other bugs)
Version: 4.6.1
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: wrong-code
: 52517 (view as bug list)
Depends on:
Blocks: 49140 50063
  Show dependency treegraph
 
Reported: 2011-06-08 20:14 UTC by Harald van Dijk
Modified: 2012-03-06 23:49 UTC (History)
5 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail: 4.3.5, 4.4.5, 4.5.3, 4.6.0, 4.7.0
Last reconfirmed: 2011-06-09 09:36:46


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Harald van Dijk 2011-06-08 20:14:28 UTC
#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.
Comment 1 Harald van Dijk 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).
Comment 2 Richard Biener 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.
Comment 3 Jakub Jelinek 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.
Comment 4 rguenther@suse.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.
Comment 5 Richard Biener 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
Comment 6 Jakub Jelinek 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.
Comment 7 Eric Botcazou 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.
Comment 8 Richard Biener 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.
Comment 9 Eric Botcazou 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.
Comment 10 Richard Biener 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).
Comment 11 Andrew Pinski 2012-03-06 23:49:08 UTC
*** Bug 52517 has been marked as a duplicate of this bug. ***