GCC Bugzilla has been upgraded from version 4.4.9 to 5.0rc3. If you see any problem, please report it to bug 64968.
Bug 28778 - [4.1 Regression] alias bug with cast and call clobbered
Summary: [4.1 Regression] alias bug with cast and call clobbered
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.2.0
: P1 blocker
Target Milestone: 4.2.0
Assignee: Daniel Berlin
URL:
Keywords: alias, monitored, wrong-code
Depends on:
Blocks:
 
Reported: 2006-08-18 21:07 UTC by Mike Stump
Modified: 2008-07-04 15:50 UTC (History)
13 users (show)

See Also:
Host:
Target:
Build:
Known to work: 3.4.0 4.2.0 4.3.0
Known to fail: 4.0.0 4.0.4 4.1.0 4.1.1 4.1.2 4.1.3
Last reconfirmed: 2006-10-13 17:50:04


Attachments
Aliasing fix. (380 bytes, patch)
2006-08-25 20:50 UTC, Daniel Jacobowitz
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Mike Stump 2006-08-18 21:07:42 UTC
mrs $ cat /tmp/t2.cc
typedef long GLint;
void aglChoosePixelFormat(const GLint *);

void find(const int *alistp) {
  const int *blist;
  int list[32];
  if (alistp)
    blist = alistp;
  else {
    list[3] = 42;       /* this store disappears with -fstrict-aliasing */
    blist = list;
  }
  aglChoosePixelFormat((GLint*)blist);
}
mrs $ ./xgcc -B./ -S -O1 /tmp/t2.cc -fno-strict-aliasing && grep 42 t2.s
        li r0,42
mrs $ ./xgcc -B./ -S -O1 /tmp/t2.cc -fstrict-aliasing && grep 42 t2.s
mrs $ 

The store cannot be removed, as the converted pointer can be used inside the aglChoosePixelFormat function to access the value.  Since the optimizer can't see that it isn't used, the optimizer must assume it can as the function isn't marked pure.  If it had been, then the optimization would be ok.

t2.cc.035t.dce1 is the first pass that doesn't have the store, t2.cc.034t.fre has the store.

This worked in 3.3, but not 4.0.1.  This doesn't work in gcc version 4.2.0 20060815 (experimental) on powerpc-apple-darwin9.0.0d1, nor on i686-apple-darwin8.
Comment 1 Andrew Pinski 2006-08-18 21:11:24 UTC
As long as aglChoosePixelFormat only access the argument as int and not long, this should be ok.
Comment 2 Mike Stump 2006-08-18 21:12:11 UTC
radr://4658741
Comment 3 Andrew Pinski 2006-08-18 21:15:51 UTC
Here is a full testcase:

typedef long GLint;
void aglChoosePixelFormat(const GLint *);

void find(const int *alistp) {
  const int *blist;
  int list[32];
  if (alistp)
    blist = alistp;
  else {
    list[3] = 42;
    blist = list;
  }
  aglChoosePixelFormat((GLint*)blist);
}
void aglChoosePixelFormat(const GLint *a)
{
  int *b = (int*)a;
  if (b[3] != 42)
    __builtin_abort ();
}

int main(void)
{
  find(0);
  return 0;
}
Comment 4 Andrew Pinski 2006-08-18 21:17:52 UTC
Confirmed.
Comment 5 Richard Biener 2006-08-19 10:15:14 UTC
dce1 removes the store, after fre we have:

find (alistp)
{
  int list[32];
  const int * blist;
  const GLint * blist.0;

  # BLOCK 2
  # PRED: ENTRY (fallthru,exec)
  if (alistp_2 != 0B) goto <L0>; else goto <L1>;
  # SUCC: 3 (true,exec) 4 (false,exec)

  # BLOCK 3
  # PRED: 2 (true,exec)
<L0>:;
  blist_3 = alistp_2;
  goto <bb 5> (<L2>);
  # SUCC: 5 (fallthru,exec)

  # BLOCK 4
  # PRED: 2 (false,exec)
<L1>:;
  #   list_5 = V_MAY_DEF <list_4>;
  list[3] = 42;
  blist_6 = &list;
  # SUCC: 5 (fallthru,exec)

  # BLOCK 5
  # PRED: 3 (fallthru,exec) 4 (fallthru,exec)
  # blist_1 = PHI <blist_3(3), &list(4)>;
<L2>:;
  blist.0_7 = (const GLint *) blist_1;
  #   SMT.30_9 = V_MAY_DEF <SMT.30_8>;
  aglChoosePixelFormat (blist.0_7);
  return;
  # SUCC: EXIT

}

and dce possibly gets confused about the blist_1 def (where I wonder
why in the phi we have &list and not blist_6 -- ccp propagates &list
into the phi).
Comment 6 Richard Biener 2006-08-19 10:44:39 UTC
But alias information is wrong, which is the problem here.
Comment 7 Daniel Berlin 2006-08-19 14:10:33 UTC
This looks like it has been broken for a long time.
Can someone add an alias dump?

Comment 8 Richard Biener 2006-08-19 14:27:31 UTC
;; Function find (find)

Points-to analysis

Constraints:

ANYTHING = &ANYTHING
READONLY = &ANYTHING
INTEGER = &ANYTHING
alistp = &ANYTHING
blist_3 = alistp
blist_6 = &list
blist_1 = blist_3
blist_1 = blist_6
blist.0_7 = blist_1

Collapsing static cycles and doing variable substitution:
Collapsing blist_3 into alistp
Collapsing blist.0_7 into blist_1

Solving graph:

Points-to sets

NULL = { }
ANYTHING = { ANYTHING }
READONLY = { ANYTHING }
INTEGER = { ANYTHING }
alistp = { ANYTHING }
blist_3 = { ANYTHING }
blist_6 = { list }
list = { }
blist_1 = { ANYTHING list }
blist.0_7 = { ANYTHING list }

find: Total number of aliased vops: 0

Referenced variables in find: 5

Variable: alistp, UID 1523, const int *, default def: alistp_2

Variable: blist, UID 1526, const int *

Variable: list, UID 1527, int[32], is addressable, default def: list_4

Variable: blist.0, UID 1528, const GLint *, symbol memory tag: SMT.30

Variable: SMT.30, UID 1575, const GLint, is addressable, is global, call clobbered (, passed to call, is global var )



Pointed-to sets for pointers in find

alistp_2, its value escapes, points-to anything
blist_3, points-to anything
blist_6, points-to vars: { list }
blist_1, points-to anything
blist.0_7, is dereferenced, its value escapes, points-to anything


Flow-insensitive alias information for find

Aliased symbols

list, UID 1527, int[32], is addressable, default def: list_4
SMT.30, UID 1575, const GLint, is addressable, is global, call clobbered (, passed to call, is global var )

Dereferenced pointers

blist.0, UID 1528, const GLint *, symbol memory tag: SMT.30

Symbol memory tags

SMT.30, UID 1575, const GLint, is addressable, is global, call clobbered (, passed to call, is global var )


Flow-sensitive alias information for find

SSA_NAME pointers


Name memory tags




Registering new PHI nodes in block #0



Registering new PHI nodes in block #2



Registering new PHI nodes in block #3



Registering new PHI nodes in block #4

Updating SSA information for statement list[3] = 42;



Registering new PHI nodes in block #5

Updating SSA information for statement aglChoosePixelFormat (blist.0_7);


Symbols to be put in SSA form

list SMT.30
 Incremental SSA update started at block: 0

Number of blocks in CFG: 6
Number of blocks to update: 5 ( 83%)

Affected blocks: 0 2 3 4 5


find (alistp)
{
  int list[32];
  const int * blist;
  const GLint * blist.0;

  # BLOCK 2
  # PRED: ENTRY (fallthru)
  if (alistp_2 != 0B) goto <L0>; else goto <L1>;
  # SUCC: 3 (true) 4 (false)

  # BLOCK 3
  # PRED: 2 (true)
<L0>:;
  blist_3 = alistp_2;
  goto <bb 5> (<L2>);
  # SUCC: 5 (fallthru)

  # BLOCK 4
  # PRED: 2 (false)
<L1>:;
  #   list_5 = V_MAY_DEF <list_4>;
  list[3] = 42;
  blist_6 = &list;
  # SUCC: 5 (fallthru)

  # BLOCK 5
  # PRED: 3 (fallthru) 4 (fallthru)
  # blist_1 = PHI <blist_3(3), blist_6(4)>;
<L2>:;
  blist.0_7 = (const GLint *) blist_1;
  #   SMT.30_9 = V_MAY_DEF <SMT.30_8>;
  aglChoosePixelFormat (blist.0_7);
  return;
  # SUCC: EXIT

}
Comment 9 Daniel Berlin 2006-08-21 01:34:21 UTC
Subject: Re:  [4.0/4.1/4.2 Regression] alias
 bug with cast and call clobbered

If you look at the alias dump, we don't think anything is aliased at all.

Comment 10 Janis Johnson 2006-08-21 16:34:03 UTC
A regression hunt on powerpc-linux using the testcase from comment #3 identified this patch:

    http://gcc.gnu.org/viewcvs?view=rev&rev=91097

    r91097 | kazu | 2004-11-23 17:45:50 +0000 (Tue, 23 Nov 2004)
Comment 11 Daniel Jacobowitz 2006-08-25 19:57:09 UTC
I am looking at this.

The difference between those two compilers in t16.ssa is:

-  # blist_1 = PHI <blist_6(2), blist_7(1)>;
+  # blist_1 = PHI <blist_7(1), blist_6(2)>;

The difference in t17.alias1 is that, plus:

-Variable: list, UID 2, int[31], is addressable, call clobbered, default def: list_4
+Variable: list, UID 2, int[31], is addressable, default def: list_4

-blist_1, points-to anything, points-to vars: { list }
+blist_1, points-to anything

-list, UID 2, int[31], is addressable, call clobbered, default def: list_4
+list, UID 2, int[31], is addressable, default def: list_4

I'm pretty positive the patch shouldn't have changed what's call clobbered!  This should be easy to track down.
Comment 12 Daniel Jacobowitz 2006-08-25 20:50:57 UTC
Created attachment 12141 [details]
Aliasing fix.

Thank you Janis for the reghunt!  Not too hard to track down given that.

I haven't tested this patch on HEAD yet, only on the revision where the bug first appeared.  I will do that now.
Comment 13 Daniel Jacobowitz 2006-08-25 20:57:05 UTC
Unfortunately Diego's gone and rewritten a bunch of aliasing code since that revision.  And there's no code corresponding to where the fix went 21 months ago.  So, congratulations: we've broken this testcase twice!

I will go hunt down where we've broken it now.
Comment 14 Daniel Jacobowitz 2006-08-25 22:11:44 UTC
Testing a patch.

Comment 15 Daniel Jacobowitz 2006-08-26 15:14:54 UTC
I don't understand aliasing well enough to fix this correctly.  See for more:
  http://gcc.gnu.org/ml/gcc-patches/2006-08/msg00965.html
Comment 16 Richard Biener 2006-08-26 20:30:20 UTC
If you change the prototype to take char* as argument we figure out clobbering
correctly:

--- t.i.030t.alias1     2006-08-26 22:28:40.000000000 +0200
+++ t.i.030t.alias1.ok  2006-08-26 22:27:33.000000000 +0200
@@ -33,7 +33,7 @@

 Variable: SMT.5, UID 1550, int, is addressable, is global, call clobbered (, is global var )

-Variable: a, UID 1529, const GLint *, default def: a_1
+Variable: a, UID 1529, char *, default def: a_1

 Variable: b, UID 1532, int *

@@ -174,11 +174,11 @@

 Variable: blist, UID 1526, const int *

-Variable: list, UID 1527, int[32], is addressable, default def: list_4
+Variable: list, UID 1527, int[32], is aliased, is addressable, call clobbered (, passed to call, is global var ), default def: list_4

-Variable: blist.0, UID 1528, const GLint *, symbol memory tag: SMT.30
+Variable: blist.0, UID 1528, char *, symbol memory tag: SMT.30

-Variable: SMT.30, UID 1575, const GLint, is addressable, is global, call clobbered (, passed to call, is global var )
+Variable: SMT.30, UID 1575, char, is addressable, is global, call clobbered (, passed to call, is global var ), may aliases: { list }



@@ -195,16 +195,16 @@

 Aliased symbols

-list, UID 1527, int[32], is addressable, default def: list_4
-SMT.30, UID 1575, const GLint, is addressable, is global, call clobbered (, passed to call, is global var )
+list, UID 1527, int[32], is aliased, is addressable, call clobbered (, passed to call, is global var ), default def: list_4
+SMT.30, UID 1575, char, is addressable, is global, call clobbered (, passed to call, is global var ), may aliases: { list }

 Dereferenced pointers

-blist.0, UID 1528, const GLint *, symbol memory tag: SMT.30
+blist.0, UID 1528, char *, symbol memory tag: SMT.30

 Symbol memory tags

-SMT.30, UID 1575, const GLint, is addressable, is global, call clobbered (, passed to call, is global var )
+SMT.30, UID 1575, char, is addressable, is global, call clobbered (, passed to call, is global var ), may aliases: { list }


 Flow-sensitive alias information for find
@@ -257,7 +257,7 @@
 {
   int list[32];
   const int * blist;
-  const GLint * blist.0;
+  char * blist.0;

 <bb 2>:
   if (alistp_2 != 0B) goto <L0>; else goto <L1>;
@@ -271,10 +271,11 @@
   list[3] = 42;
   blist_6 = &list;

+  # list_8 = PHI <list_4(3), list_5(4)>;
   # blist_1 = PHI <blist_3(3), blist_6(4)>;
 <L2>:;
-  blist.0_7 = (const GLint *) blist_1;
-  #   SMT.30_9 = V_MAY_DEF <SMT.30_8>;
+  blist.0_7 = (char *) blist_1;
+  #   list_9 = V_MAY_DEF <list_8>;
   aglChoosePixelFormat (blist.0_7);
   return;

Comment 17 Richard Biener 2006-08-26 20:42:49 UTC
So, making pointer arguments effectively using alias-set zero for alias and call clobbering computation would fix this.
Comment 18 Daniel Jacobowitz 2006-08-26 23:25:14 UTC
Subject: Re:  [4.0/4.1/4.2 Regression] alias bug with cast and call clobbered

On Sat, Aug 26, 2006 at 08:42:50PM -0000, rguenth at gcc dot gnu dot org wrote:
> So, making pointer arguments effectively using alias-set zero for alias and
> call clobbering computation would fix this.

True - but how much will this pessimize us?

Comment 19 Daniel Berlin 2006-08-27 04:12:08 UTC
Subject: Re:  [4.0/4.1/4.2 Regression] alias
 bug with cast and call clobbered

rguenth at gcc dot gnu dot org wrote:
> ------- Comment #17 from rguenth at gcc dot gnu dot org  2006-08-26 20:42 -------
> So, making pointer arguments effectively using alias-set zero for alias and
> call clobbering computation would fix this.
> 

Yes, if you change it so *everything passed to calls* is assumed to be
aliasing every variable with it's address taken, you will get the right
result in this case.

So what do you think will happen when you add one level of indirection
to the mess, and TBAA now prunes out *that* alias instead, so you miss
it again? (IE break the chain of clobber transitivity one link in the
other direcftion).

IMHO, i'd rather just see this bug, which has been in our compiler for 3
releases now, fixed properly in the next one, than hacked around.

It's relatively easy to fix this testcase in some hacky way, but i'm not
sure why we'd want to, when we know it will only fix this testcase, and
not the underlying problem.




Comment 20 Richard Biener 2006-08-27 14:20:21 UTC
So I have a patch that produces (diff typedef long GLint __attribute__((may_alias)) resunts vs. patch):

--- t.i.030t.alias1.ok  2006-08-27 16:13:54.000000000 +0200
+++ t.i.030t.alias1     2006-08-27 16:14:17.000000000 +0200
@@ -174,11 +174,11 @@

 Variable: blist, UID 1526, const int *

-Variable: list, UID 1527, int[32], is aliased, is addressable, call clobbered (, passed to call, is global var ), default def: list_4
+Variable: list, UID 1527, int[32], is addressable, call clobbered (, passed to call, is incoming pointer ), default def: list_4

 Variable: blist.0, UID 1528, const GLint *, symbol memory tag: SMT.30

-Variable: SMT.30, UID 1575, const GLint, is addressable, is global, call clobbered (, passed to call, is global var ), may aliases: { list }
+Variable: SMT.30, UID 1575, const GLint, is addressable, is global, call clobbered (, passed to call, is global var )



@@ -195,8 +195,8 @@

 Aliased symbols

-list, UID 1527, int[32], is aliased, is addressable, call clobbered (, passed to call, is global var ), default def: list_4
-SMT.30, UID 1575, const GLint, is addressable, is global, call clobbered (, passed to call, is global var ), may aliases: { list }
+list, UID 1527, int[32], is addressable, call clobbered (, passed to call, is incoming pointer ), default def: list_4
+SMT.30, UID 1575, const GLint, is addressable, is global, call clobbered (, passed to call, is global var )

 Dereferenced pointers

@@ -204,7 +204,7 @@

 Symbol memory tags

-SMT.30, UID 1575, const GLint, is addressable, is global, call clobbered (, passed to call, is global var ), may aliases: { list }
+SMT.30, UID 1575, const GLint, is addressable, is global, call clobbered (, passed to call, is global var )


 Flow-sensitive alias information for find
@@ -275,7 +275,8 @@
   # blist_1 = PHI <blist_3(3), blist_6(4)>;
 <L2>:;
   blist.0_7 = (const GLint *) blist_1;
-  #   list_9 = V_MAY_DEF <list_8>;
+  #   list_10 = V_MAY_DEF <list_8>;
+  #   SMT.30_11 = V_MAY_DEF <SMT.30_9>;
   aglChoosePixelFormat (blist.0_7);
   return;

by noticing that if pt_anything is set, we indeed need to include all addressable vars in the clobbering:

Index: tree-ssa-alias.c
===================================================================
*** tree-ssa-alias.c    (revision 116488)
--- tree-ssa-alias.c    (working copy)
*************** set_initial_properties (struct alias_inf
*** 359,364 ****
--- 359,373 ----
                if (!unmodifiable_var_p (referenced_var (j)))
                  mark_call_clobbered (referenced_var (j), pi->escape_mask);
            }
+
+         if (pi->pt_anything)
+           {
+             bitmap_iterator bi;
+             unsigned int j;
+             EXECUTE_IF_SET_IN_BITMAP (addressable_vars, 0, j, bi)
+               if (!unmodifiable_var_p (referenced_var (j)))
+                 mark_call_clobbered (referenced_var (j), pi->escape_mask);
+           }
        }

        /* If the name tag is call clobbered, so is the symbol tag


> So what do you think will happen when you add one level of indirection
> to the mess, and TBAA now prunes out *that* alias instead, so you miss
> it again? (IE break the chain of clobber transitivity one link in the
> other direcftion).

Do you have a testcase in mind?
Comment 21 Daniel Berlin 2006-08-27 15:41:37 UTC
Subject: Re:  [4.0/4.1/4.2 Regression] alias bug with cast and call clobbered

> by noticing that if pt_anything is set, we indeed need to include all
> addressable vars in the clobbering:
>
This is also equivalent to marking every addressable variable as
clobbered whenever a function has any incoming pointers, as they will
point to anything, and escape.

I listed this as a conservatively correct solution in the email i sent
to mark (Mark everything clobbered).

> > So what do you think will happen when you add one level of indirection
> > to the mess, and TBAA now prunes out *that* alias instead, so you miss
> > it again? (IE break the chain of clobber transitivity one link in the
> > other direcftion).
>
> Do you have a testcase in mind?

Do you really want me to construct one?
Hopefully this will suffice:

Clobbering is a transitive property.

given
b = &e
a = b
c = a
d = c

a store to *d clobbers the values held by c, d, a, and b.
We will start with the solution that *d is clobbered, and attempt to
propagate it up the chain by following may-alias sets, till we mark e
as clobbered.  In this case, d, c, a, and b wll have e in their alias
set, so we only need to see the alias-set of any one of them to get
this correct.

However, if you add levels of indirection, like

b = &e
a = &b
c = &a
d = &c

The only way we will get to the fact that e can be clobbered is by
following the may-alias sets of each variable, d->c->a->b until we get
to something with e in the ma-yalias set.

If you add the right casts in, TBAA will prune the addresses from the
may-alias set of different variables, and you won't ever get all the
way to marking e clobbered.
Comment 22 Richard Biener 2006-08-27 15:49:11 UTC
Well, yes.  If we still had pt_vars at the time of add_call_clobber_ops () we might only do it if one of the actual params of a CALL_EXPR has pt_anything set.
But call clobbering is not per call-site or flow-sensitive (yet).
Comment 23 Daniel Berlin 2006-08-27 16:00:18 UTC
Subject: Re:  [4.0/4.1/4.2 Regression] alias bug with cast and call clobbered

> ------- Comment #22 from rguenth at gcc dot gnu dot org  2006-08-27 15:49 -------
> Well, yes.  If we still had pt_vars at the time of add_call_clobber_ops () we
> might only do it if one of the actual params of a CALL_EXPR has pt_anything
> set.
> But call clobbering is not per call-site or flow-sensitive (yet).

So just to be clear

Given:
The workaround is  that any function which has *incoming* pointer
arguments will have every addressable variable *in that function*
marked as call clobbering (IE regardless of what the call), as with
your patch.  This will also be true with any function that has a store
to a global pointer, any function that casts between pointers and
ints, and any function that passes pointers to a call.
Relatively speaking, this is a very large percentage of all functions
written, IMHO.

Then all of the following are true (this really is a question, not a statement)?
1. You believe this is a good idea for 4.2, even though it will
probably cause a very marked decrease in performance of generated code
compared to every previous 4.x series.

2. Even though this bug has been here for all 4.x versions and only
reported now, you believe it affects a large enough number of users to
make #1 acceptable.

As is clear by now, I don't believe #2 is true, which is why i
proposed fixing it properly (computing the clobbering sets
independently of aliasing, which is going to be some moderate amount
of code) in 4.3, and leaving this bug open, as a better solution.
Comment 24 Daniel Jacobowitz 2006-08-27 17:56:09 UTC
Subject: Re:  [4.0/4.1/4.2 Regression] alias bug with cast and call clobbered

On Sun, Aug 27, 2006 at 04:00:19PM -0000, dberlin at dberlin dot org wrote:
> 1. You believe this is a good idea for 4.2, even though it will
> probably cause a very marked decrease in performance of generated code
> compared to every previous 4.x series.

I don't think this conversation is going to make any forward progress
unless someone tests it.  Anyone want to volunteer?

Comment 25 Mark Mitchell 2006-08-27 20:25:26 UTC
Dan Berlin believes that Richard's patch in Comment #20 is the conservative fix.
Comment 26 Mark Mitchell 2006-08-27 20:28:46 UTC
I don't understand how TBAA is interacting with the may-alias information.

In particular, TBAA doesn't say anything about casts; it says something about loads and stores.  In particular, TBAA forbids accessing storage of type A through a pointer to type B, given certain constraints on A and B.  It does not forbid casting an A* to a B*.

Why are the optimizers pruning may-alias sets on casts?  Why isn't the fix just to stop them from doing that?
Comment 27 Daniel Berlin 2006-08-27 20:51:37 UTC
Subject: Re:  [4.0/4.1/4.2 Regression] alias bug with cast and call clobbered

> I don't understand how TBAA is interacting with the may-alias information.

Given a pointer, and some aliases, we ask TBAA, for each alias, "is it
possible for a load or store of this type to access this variable, of
this other type".  We use the results to answer a different question,
"is it possible for a call to function foo, which is being passed this
pointer, to access this variable".

>

> In particular, TBAA doesn't say anything about casts; it says something about
> loads and stores.  In particular, TBAA forbids accessing storage of type A
> through a pointer to type B, given certain constraints on A and B.  It does not
> forbid casting an A* to a B*.

Correct.

>
> Why are the optimizers pruning may-alias sets on casts?
They are not..

>  Why isn't the fix just to stop them from doing that?
Because they are not doing that..

If you look at Andrew's complete, reduced, testcase, you will see that
what is happening is that pretty much the same as what will happen
given:

int bar(void)
{
float a;
float *b1;
int *b2;

a = 5.0;
b1 = &a;
b2 = (int *)b1;
foo(b2);
}

void foo(int *a)
{
  float *b = a;
  printf ("%f", *b); /* Or some other use of b */
  *b = 9.0;
}

I'm going to use clobbering here to mean both mod and ref, because for
our purposes, it doesn't matter.

What happens is that call clobbering is using the may-alias sets to
try to determine call clobbering.

However, the may-alias set of "b2" in function "bar" will *not*
include "a", because a dereference of b2 can *not* validly access "a"
according to TBAA.

Thus, we will claim variable "a" is *not* clobbered by the call to
foo, because it won't appear in the may-alias set of "b2", and we
compute answers to clobbering questions using alias sets.  However, it
*is* validly clobbered, because it is casted back to the right type in
foo, and stored into.

The effect of not marking it clobbered in the *actual testcase* (not
above) will be that DCE will delete the initial store, because it
appears entirely local, due to missing that it could be dereferenced
by the call.

This testcase has been failing since we started using may-alias sets
for determining call-clobbering, which is 4.0.

This is just a subtle difference between aliasing and clobbering.
Aliasing asks about stores and loads, Clobbering asks about calls.

In the context of "can a load or store to b2 access a" (the aliasing
question), the answer is no.
In the context of "can the call to foo do something that uses or
modifies our local variable a" (the clobbering question) ,the answer
is yes, *even though it can't happen directly through an access to
b2*.

Thus, the correct solution is to compute the sets used to answer the
question "what can be read/modified by a call to a function" separate
from the sets used to answer the question "what can be loaded/stored
by a dereference of this variable".

Since we have never done that before, it does require new code.
Comment 28 Daniel Berlin 2006-08-27 21:09:42 UTC
Subject: Re:  [4.0/4.1/4.2 Regression] alias bug with cast and call clobbered

> Since we have never done that before, it does require new code.
>

And to answer what may be a followup, which is "why hasn't this broken
anything else before", it iss because even though the clobbering
question and the alias question are subtly different, the answers are
almost always the same.  It is only because we prune the local answers
using TBAAthat we get different answers depending on context.

If you exclude strict type-based rules, the answer to "what can foo
clobber" in the example is the same as asking "what can the first
argument of foo access in foo and its callees".  Because of the
type-based rules, we end up with a disconnect.  It would be undefined
to dereference the first argument of foo without casting it first.  In
effect, the strict-type rules allow you can take an unaliased pointer
in a caller, and validly turn it back into an aliased pointer in the
callee.

In order to account for this, you need to build the sets without
accounting for the type-based rules,  and if you want to apply the
type-based rules to clobbering, use them on a context-sensitive basis
(IE at the point of dereference, determine what could be accessed, and
propagate that back up through other functions to get the a better
clobber answer).
Comment 29 Richard Biener 2006-08-28 08:42:56 UTC
I completely agree with Dan's analysis.  Note that for the patch in comment #20 we can hoist the loop adding all addressable vars to the call clobbering list out of the loop iterating over all analyzed pointers by only remembering if one had pt_anything set.

My preferred solution would be to develop the correct fix for 4.3 and eventually allow backporting that to the release branch(es) and not hold the release of 4.2 for this bug.  In fact, the usual try of adding "-fno-strict-aliasing" if one faces a subtle bug will fix it, so it's not harder to detect than a strict aliasing violation by the user.
Comment 30 Daniel Berlin 2006-09-09 17:55:04 UTC
Subject: Re:  [4.0/4.1/4.2 Regression] alias bug with cast and call clobbered

Patch coming in a sec

On 9 Sep 2006 15:02:37 -0000, reichelt at gcc dot gnu dot org
<gcc-bugzilla@gcc.gnu.org> wrote:
>
>
> --
Comment 31 Steven Bosscher 2006-09-16 18:09:42 UTC
sec has passed.
ping!
Comment 32 Daniel Berlin 2006-09-16 20:03:12 UTC
Subject: Re:  [4.0/4.1/4.2 Regression] alias bug with cast and call clobbered

> ------- Comment #31 from steven at gcc dot gnu dot org  2006-09-16 18:09 -------
> sec has passed.
> ping!
>

I'm down to two testsuite failures (pr20100 failures).
Sorry it's taking so long.
Comment 33 Albert Cahalan 2006-09-26 04:44:08 UTC
(In reply to comment #28)
> If you exclude strict type-based rules, the answer to "what can foo
> clobber" in the example is the same as asking "what can the first
> argument of foo access in foo and its callees".  Because of the
> type-based rules, we end up with a disconnect.  It would be undefined
> to dereference the first argument of foo without casting it first.  In
> effect, the strict-type rules allow you can take an unaliased pointer
> in a caller, and validly turn it back into an aliased pointer in the
> callee.

Although it wouldn't work for the example code, extending the aliasing behavior of (char*) to (void*) would fix the problem for LOTS of code out in the wild. People normally use a (void*) when they want a generic pointer type to play casting games with. This is a case where the C standard is very far from the reality of how people write code. The example code is fairly unusual.
Comment 34 Andrew Pinski 2006-09-26 04:56:39 UTC
Subject: Re:  [4.0/4.1/4.2 Regression] alias
	bug with cast and call clobbered

On Tue, 2006-09-26 at 04:44 +0000, acahalan at gmail dot com wrote:
> 
> Although it wouldn't work for the example code, extending the aliasing behavior
> of (char*) to (void*) would fix the problem for LOTS of code out in the wild.
> People normally use a (void*) when they want a generic pointer type to play
> casting games with. This is a case where the C standard is very far from the
> reality of how people write code. The example code is fairly unusual.

But C aliasing is not based on pointers but on accesses so it is wrong
to it that way.

-- Pinski

Comment 35 Albert Cahalan 2006-09-26 14:16:49 UTC
(In reply to comment #34)
> Subject: Re:  [4.0/4.1/4.2 Regression] alias
>         bug with cast and call clobbered
> 
> On Tue, 2006-09-26 at 04:44 +0000, acahalan at gmail dot com wrote:
> > 
> > Although it wouldn't work for the example code, extending the aliasing behavior
> > of (char*) to (void*) would fix the problem for LOTS of code out in the wild.
> > People normally use a (void*) when they want a generic pointer type to play
> > casting games with. This is a case where the C standard is very far from the
> > reality of how people write code. The example code is fairly unusual.
> 
> But C aliasing is not based on pointers but on accesses so it is wrong
> to it that way.

It's also wrong to assume that unions can be used for type punning, but so what? It is allowed by gcc.

Most real-world code doesn't use unions and definitely doesn't do like the example above. Typically (void*) is used for passing things around, and there are also the trivial aliasing cases which gcc can warn about. (if you can warn about it, you can instead do what the programmer wanted)

Evidence: this bug has existed for ages, meanwhile aliasing violations keep getting reported as compiler bugs.

Since gcc introduced strict aliasing, I've worked at three places doing software development. All were embedded/OS related, so I would say the people are/were hard-core programmers with a clue. Everybody is shocked when I explain strict-aliasing, and all but one have been horrified.

So, to get back to this bug specifically: treating a (void*) arg the same as a (char*) arg will cover up the problem for nearly everyone. Sadly it won't fix the example given, which is legit to a language lawyer and a nonsense piece of shit to any normal programmer. Oh well. By treating (void*) the same as (char*), you can demote the bug severity greatly and move on.

BTW, in the testcase, the following line should generate a warning:

glChoosePixelFormat((GLint*)blist);

I don't get any warning at all, even with -Wstrict-aliasing=2.
Comment 36 Andrew Pinski 2006-09-26 14:32:01 UTC
> It's also wrong to assume that unions can be used for type punning, but so
> what? It is allowed by gcc.

No, it is less there as the behavior with unions is unspecified and not undefined unlike type punning via an address/type cast.


> Evidence: this bug has existed for ages, meanwhile aliasing violations keep
> getting reported as compiler bugs.
This bug (PR28778) has only existed for the last two major releases which is not ages.
 
> Since gcc introduced strict aliasing, I've worked at three places doing
> software development. All were embedded/OS related, so I would say the people
> are/were hard-core programmers with a clue. Everybody is shocked when I explain
> strict-aliasing, and all but one have been horrified.

And Aliasing rules in C have existed now for at least 17 years.  It is not like it magically was added either.  Yes GCC is one of the few compiler that uses the information produced by type based aliasing anyalsis but that does not mean GCC is wrong.  Yes GCC turned on "strict" aliasing only 7 years ago but the aliasing rules have been around for 10 years longer than that.

 
> So, to get back to this bug specifically: treating a (void*) arg the same as a
> (char*) arg will cover up the problem for nearly everyone. Sadly it won't fix
> the example given, which is legit to a language lawyer and a nonsense piece of
> shit to any normal programmer. Oh well. By treating (void*) the same as
> (char*), you can demote the bug severity greatly and move on.

Again, aliasing in C has to do with accesses and nothing to the type of pointers.  In fact this is aliasing rules in all languages have to do with accesses and not the type.  Look at Fortran (which have existed since at least 1977) aliasing rules wich basically say no two arguments alias which makes people write undefined code easier than with C aliasing.
> 
> BTW, in the testcase, the following line should generate a warning:
> 
> glChoosePixelFormat((GLint*)blist);

Why there is nothing questionable about it until glChoosePixelFormat deferences the agrument in the wrong type.
Comment 37 Albert Cahalan 2006-09-26 15:33:27 UTC
(In reply to comment #36)

> > Evidence: this bug has existed for ages, meanwhile aliasing violations keep
> > getting reported as compiler bugs.
> This bug (PR28778) has only existed for the last two major releases which is
> not ages.

IMHO that qualifies as "ages". If the bug has survived that long, it
can't be all that major. People have learned that -fno-strict-aliasing
is the cure-all for mystery bugs.

> > Since gcc introduced strict aliasing, I've worked at three places doing
> > software development. All were embedded/OS related, so I would say the people
> > are/were hard-core programmers with a clue. Everybody is shocked when I explain
> > strict-aliasing, and all but one have been horrified.
> 
> And Aliasing rules in C have existed now for at least 17 years.

Your point?

Fact: strict aliasing horrifies most software developers.

The wording in a seriously expensive ISO document doesn't
change the simple fact that people don't write code that way.
Books intended to teach the language don't mention this
"feature" of the language. I don't just mean "Learn C in
5 days", but college textbooks as well.

> > So, to get back to this bug specifically: treating a (void*) arg the same as a
> > (char*) arg will cover up the problem for nearly everyone. Sadly it won't fix
> > the example given, which is legit to a language lawyer and a nonsense piece of
> > shit to any normal programmer. Oh well. By treating (void*) the same as
> > (char*), you can demote the bug severity greatly and move on.
> 
> Again, aliasing in C has to do with accesses and nothing to the type of
> pointers.

I know. I'm perfectly clear on that. You don't need to remind me.

If the example code had used (char*), the bug would not have shown
itself. Great. Most real-world code would use (void*) for this.
That breaks. If (void*) is treated the same as (char*) though, the
bug goes away. That is, an access to "void" (which is pretty much
impossible except for computed goto) should be considered to be
something which could happen and which could alias with anything.
Probably this fixes 99% of the real-world occurances of this bug.

Given such a change, the remaining bug is an insignificant
violation of the C standard. For the next release it can be
either ignored or addressed by having both -std=c99 and -std=c89
disable strict aliasing.

> > BTW, in the testcase, the following line should generate a warning:
> > 
> > glChoosePixelFormat((GLint*)blist);
> 
> Why there is nothing questionable about it until glChoosePixelFormat deferences
> the agrument in the wrong type.

It's not illegal, and thus not an error, but it damn well is questionable. Normal people cast to/from (void*), because this comes free in C or because it seems clean to use (void*) as the generic pointer type. People trying to avoid aliasing problems cast to/form (char*), and use (char*) as the generic pointer type. Other casts between pointers to types not allowed to alias are highly suspect.
Comment 38 Daniel Berlin 2006-09-26 15:47:33 UTC
Subject: Re:  [4.0/4.1/4.2 Regression] alias bug with cast and call clobbered

On 26 Sep 2006 15:33:29 -0000, acahalan at gmail dot com
<gcc-bugzilla@gcc.gnu.org> wrote:
>
>
> ------- Comment #37 from acahalan at gmail dot com  2006-09-26 15:33 -------
> (In reply to comment #36)
>
> > > Evidence: this bug has existed for ages, meanwhile aliasing violations keep
> > > getting reported as compiler bugs.
> > This bug (PR28778) has only existed for the last two major releases which is
> > not ages.
>
> IMHO that qualifies as "ages". If the bug has survived that long, it
> can't be all that major. People have learned that -fno-strict-aliasing
> is the cure-all for mystery bugs.

Okay, how do i put this gently:

If you want to argue about strict aliasing and enabling it by default,
please don't do it in a bug
report.
We use bug reports to track the status of very specific bugs.
Even if we were to perform the behavior you request (and I highly
doubt we will), it would be a separate enhancement request, and should
be filed as such (and probably discussed on the gcc mailing list prior
to filing a report).
We have our reasons to enable strict aliasing by default.  People have
their reasons they don't like it.

Acting as if one viewpoint is simply invalid because you don't like it
isn't going to help.
Comment 39 Andrew Pinski 2006-09-26 15:49:15 UTC
(In reply to comment #37)
> Your point?

That aliasing rules in C is older than my girl friend and that they have been around for a lot longer than people give credit for.
 
> Fact: strict aliasing horrifies most software developers.

Fact:  most developers are taught right to begin with.
But is that a GCC issue, no.
Fact: aliasing rules in C are easy to understand if you don't take pointer types into account.
 
> The wording in a seriously expensive ISO document doesn't
> change the simple fact that people don't write code that way.
> Books intended to teach the language don't mention this
> "feature" of the language. I don't just mean "Learn C in
> 5 days", but college textbooks as well.

Well those books should be punished in the open market but is that a GCC issue, no.  And if those books are not mentioning this problem, well someone should complain to them and not to GCC that they don't get something correct.

> I know. I'm perfectly clear on that. You don't need to remind me.

It is to remind all the people who look into this bug later on to see why their code is wrong or correct.  Anyways embedded people should be using type based aliasing to their benifit instead of working around it as type based aliasing can help code size and speed of their program.
Comment 40 Paolo Carlini 2006-09-26 15:57:25 UTC
(In reply to comment #38)
> We have our reasons to enable strict aliasing by default.

In my opinion, this is a central point. I think we should try to explain what strict aliasing buys from the point of view of the optimizers. In my experience, quite a few people do not quite understand *why* those aliasing rules are there in the first place and why lately GCC (or any modern compiler, for that matter, of course, that's the point) tries to be as strict as possible: otherwise, those people would be more willing to learn the rules and appreciate our (I should say, yours, Danny and compiler people) hard efforts in this area.
Comment 41 Daniel Berlin 2006-09-27 02:12:46 UTC
Subject: Re:  [4.0/4.1/4.2 Regression] alias bug with cast and call clobbered

On 26 Sep 2006 15:57:28 -0000, pcarlini at suse dot de
<gcc-bugzilla@gcc.gnu.org> wrote:
>
>
> ------- Comment #40 from pcarlini at suse dot de  2006-09-26 15:57 -------
> (In reply to comment #38)
> > We have our reasons to enable strict aliasing by default.
>
> In my opinion, this is a central point. I think we should try to explain what
> strict aliasing buys from the point of view of the optimizers. In my
> experience, quite a few people do not quite understand *why* those aliasing
> rules are there in the first place and why lately GCC (or any modern compiler,
> for that matter, of course, that's the point) tries to be as strict as
> possible: otherwise, those people would be more willing to learn the rules and
> appreciate our (I should say, yours, Danny and compiler people) hard efforts in
> this area.
>

And I would be more than happy to discuss this (there is plenty of
empirical evidence as to how much it buys us, etc), just not in a bug
report :)
Bring it to gcc@
Comment 42 Daniel Berlin 2006-10-13 17:50:04 UTC
mine
Comment 43 Daniel Berlin 2006-10-19 23:06:06 UTC
Subject: Bug 28778

Author: dberlin
Date: Thu Oct 19 23:05:53 2006
New Revision: 117891

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=117891
Log:
2006-10-19  Daniel Berlin  <dberlin@dberlin.org>

	Fix PR tree-optimization/28778
	Fix PR tree-optimization/29156
	Fix PR tree-optimization/29415
	* tree.h (DECL_PTA_ARTIFICIAL): New macro.
	(tree_decl_with_vis): Add artificial_pta_var flag.
	* tree-ssa-alias.c (is_escape_site): Remove alias info argument,
	pushed into callers.
	* tree-ssa-structalias.c (nonlocal_for_type): New variable.
	(nonlocal_all): Ditto.
	(struct variable_info): Add directly_dereferenced member.
	(var_escaped_vars): New variable.
	(escaped_vars_tree): Ditto.
	(escaped_vars_id): Ditto.
	(nonlocal_vars_id): Ditto.
	(new_var_info): Set directly_dereferenced.
	(graph_size): New variable
	(build_constraint_graph): Use graph_size.
	(solve_graph): Don't process constraints that cannot change the
	solution, don't try to propagate an empty solution to our
	successors.
	(process_constraint): Set directly_dereferenced.
	(could_have_pointers): New function.
	(get_constraint_for_component_ref): Don't process STRING_CST.
	(nonlocal_lookup): New function.
	(nonlocal_insert): Ditto.
	(create_nonlocal_var): Ditto.
	(get_nonlocal_id_for_type): Ditto.
	(get_constraint_for): Allow results vector to be empty in the case
	of string constants.
	Handle results of calls properly.
	(update_alias_info): Update alias info stats on number and type of
	calls.
	(find_func_aliases): Use could_have_pointers.
	(make_constraint_from_escaped): Renamed from
	make_constraint_to_anything, and changed to make constraints from
	escape variable.
	(make_constraint_to_escaped): New function.
	(find_global_initializers): Ditto.
	(create_variable_info_for): Make constraint from escaped to any
	global variable, and from any global variable to the set of
	escaped vars.
	(intra_create_variable_infos): Deal with escaped instead of
	pointing to anything.
	(set_uids_in_ptset): Do type pruning on directly dereferenced
	variables.
	(find_what_p_points_to): Adjust call to set_uids_with_ptset.
	(init_base_vars): Fix comment, and initialize escaped_vars.
	(need_to_solve): Removed.
	(find_escape_constraints): New function.
	(expand_nonlocal_solutions): Ditto.
	(compute_points_to_sets): Call find_escape_constraints and
	expand_nonlocal_solutions.
	(delete_points_to_sets): Don't fall off the end of the graph.
	(init_alias_heapvars): Initialize nonlocal_for_type and
	nonlocal_all.
	(delete_alias_heapvars): Free nonlocal_for_type and null out
	nonlocal_all. 


Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr28778.c
    trunk/gcc/testsuite/gcc.c-torture/execute/pr29156.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pta-fp.c
    trunk/gcc/tree-ssa-alias.c
    trunk/gcc/tree-ssa-operands.c
    trunk/gcc/tree-ssa-structalias.c
    trunk/gcc/tree-ssa-structalias.h
    trunk/gcc/tree.h

Comment 44 Daniel Berlin 2006-10-19 23:07:00 UTC
Fixed.
Comment 45 Richard Biener 2006-10-20 08:24:54 UTC
Still not fixed on the branches.
Comment 46 Chuck Bear 2006-11-05 22:17:14 UTC
Folks, can anyone please tell me if this is the same problem as I am seeing here using gcc 4.0.2 for x86_64:

#include <stdio.h>

inline long long Vgetbytes(double f) {
   return *reinterpret_cast<const long long *>(&f);
}

int main (int argc, char **argv)
{
    double dd = 2.0;

    printf ("%llx\n", Vgetbytes(dd));
    printf ("%llx\n", Vgetbytes(dd));
}

When compiled with -02 I get:
build0:/home/cbear $ g++4 --version
g++4 (GCC) 4.0.2 20051130 (Red Hat 4.0.2-14.EL4)
build0:/home/cbear $ g++4 -O2 ftp.cpp
build0:/home/cbear $ ./a.out
0
4000000000000000

When I look at the disassemby I see the problem:
main:
.LFB14:
	pushq	%rbx	# Save EBX as required
.LCFI0:
	movl	$.LC1, %edi	#, Load format string for printf. edi = arg 0
	movabsq	$4611686018427387904, %rbx	# rbx gets 2.0.
	xorl	%eax, %eax	# irrelevant
	subq	$16, %rsp	# Stack frame for calling printf
.LCFI1:
	movq	8(%rsp), %rsi	# ERROR second argument to printf call wrong
	movq	%rbx, 8(%rsp)	# ERROR if this line came before prior we would be OK
	call	printf          # printf gets rdi and rsi as args.  rsi bad.
	movq	8(%rsp), %rsi	# Better luck this time, rsi set properly
	movl	$.LC1, %edi	# rdi initialized againg
	xorl	%eax, %eax	# irrelevant
	movq	%rbx, 8(%rsp)	# extraneous, rbx need not be preserved
	call	printf          # This one will work
	addq	$16, %rsp	# Clean up the printf stack
	xorl	%eax, %eax	# <result>
	popq	%rbx            # restore rbx for caller
	ret                     # done

If I compile with -fno-strict-aliasing I do get valid code and right answers.

However I like the assembly code produced by gcc 3.4.4 much better because it doesn't bother to allocate stack space, and just uses rbx:
build0:/home/cbear $ g++ --version
g++ (GCC) 3.4.4 20050721 (Red Hat 3.4.4-2)
build0:/home/cbear $ g++ -O2 -S -fverbose-asm ftp.cpp

main:
.LFB14:
	pushq	%rbx	#
.LCFI0:
	movabsq	$4611686018427387904, %rbx	#, <anonymous>
	movl	$.LC1, %edi	#,
	movq	%rbx, %rsi	# <anonymous>, <anonymous>
	xorl	%eax, %eax	#
	call	printf	#
	movq	%rbx, %rsi	# <anonymous>, <anonymous>
	movl	$.LC1, %edi	#,
	xorl	%eax, %eax	#
	call	printf	#
	popq	%rbx	#
	xorl	%eax, %eax	# <result>
	ret

Comment 47 Daniel Jacobowitz 2006-11-05 22:25:49 UTC
Subject: Re:  [4.0/4.1 Regression] alias bug with cast and call clobbered

On Sun, Nov 05, 2006 at 10:17:16PM -0000, chuck at vertica dot com wrote:
> Folks, can anyone please tell me if this is the same problem as I am seeing
> here using gcc 4.0.2 for x86_64:

No.  Your code is simply invalid; this is a FAQ.

> inline long long Vgetbytes(double f) {
>    return *reinterpret_cast<const long long *>(&f);
> }

"f" is an object of type double and may not be accessed through a
pointer to "const long long".

Comment 48 Andrew Pinski 2006-11-05 22:26:12 UTC
(In reply to comment #46)
> Folks, can anyone please tell me if this is the same problem as I am seeing
> here using gcc 4.0.2 for x86_64:
> inline long long Vgetbytes(double f) {
>    return *reinterpret_cast<const long long *>(&f);
> }

No that is not the same problem, in fact the above is just plainly violating C++ aliasing rules.
Comment 49 Chuck Bear 2006-11-05 23:39:23 UTC
Sorry.

But maybe it is a FAQ because even with "-Wall" or "-Wstrict-aliasing=2" g++ 4.0.2 generates invalid code for this without so much as a peep.  I here 4.1 is better about giving a warning.

I guess it was too much to think "reinterpret_cast means I know what I'm asking for, so just do what I say".
Comment 50 Gabriel Dos Reis 2007-01-25 15:51:38 UTC
This is not going to be fixed for GCC-4.0.4, so adjusting milestone.
Comment 51 Joseph S. Myers 2008-07-04 15:50:35 UTC
Closing 4.1 branch.