[Bug rtl-optimization/20367] New: alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[Bug rtl-optimization/20367] New: alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[amylaar at gcc dot gnu dot org]

This has been discussed here:

http://gcc.gnu.org/ml/gcc-patches/2004-01/msg03141.html

-- 
           Summary: alias analysis doesn't take into account that variables
                    that haven't their address taken can't alias arbitrary
                    MEMs
           Product: gcc
           Version: 3.2
            Status: UNCONFIRMED
          Keywords: alias
          Severity: normal
          Priority: P2
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: amylaar at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org
OtherBugsDependingO 17652
             nThis:


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[amylaar at gcc dot gnu dot org]

------- Additional Comments From amylaar at gcc dot gnu dot org  2005-03-07 20:01 -------
Created an attachment (id=8353)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=8353&action=view)
patch against 3.4

The previous patch had the problem that the non-existence of a MEM_EXPR was
taken
to mean that no static variable is involved.  This updated patch uses a
MEM_EXPR with the new special node unspecified_indirect_ref_node to indicate
that no
static variable is involved.  Thus, when two MEMs are merged and thus loose
their MEM_EXPR, the optimization should still be safe.


-- 


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[amylaar at gcc dot gnu dot org]

------- Additional Comments From amylaar at gcc dot gnu dot org  2005-03-07 20:27 -------
Here is an example out of the google cache:
http://66.102.9.104/search?q=cache:BGnyHfyQlSYJ:gcc.gnu.org/ml/gcc-patches/2004-02/msg01638.html+unspecified_indirect_ref_node&hl=en

RFA: alias analysis for non-addressed variables vs. INDIRECT_REF

    * From: Joern Rennecke <joern dot rennecke at superh dot com>
    * To: gcc-patches at gcc dot gnu dot org
    * Date: Wed, 18 Feb 2004 18:24:58 +0000 (GMT)
    * Subject: RFA: alias analysis for non-addressed variables vs. INDIRECT_REF

As discussed before, we are currently missing opportunities to
hoist out accesses of non-addressed variables.  I have now
modified my patch so that a special node unspecified_indirect_ref_node
is used in MEM_EXPRs to mark memory accesses that are generated
from an otherwise unspecified INDIRECT_REF.

Consider this test case:

int
f(int s, int *a)
{
  static int i;
  for (i = 0; i < 800; i++)
    s += a[i];
  return s;
}

For the inner loop, this is the code that I get for sh-elf at -O2 -m4
with mainline from 2004-02-17 without my patch:

.L5:
        mov.l   @r7,r1
        mov     r1,r0
        shll2   r0
        mov.l   @(r0,r5),r2
        add     #1,r1
        cmp/gt  r6,r1
        mov.l   r1,@r7
        bf/s    .L5
        add     r2,r3

And this with the patch; the loads and stores if the loop induction
variable 'i' (@r7) have been hoisted out, and the a[i] giv has been
strength reduced from @(r0,r5) to @r5+.

.L5:
        mov.l   @r5+,r1
        add     #1,r2
        cmp/gt  r3,r2
        bf/s    .L5
        add     r1,r0



-- 


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[giovannibajo at libero dot it]

------- Additional Comments From giovannibajo at libero dot it  2005-03-08 00:27 -------
I reckon this is already fixed by tree-ssa, or we'll be fixed by the incoming 
TARGET_MEM_REF work. Zdenek?

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rakdver at atrey dot karlin
                   |                            |dot mff dot cuni dot cz


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-03-08 00:31 -------
(In reply to comment #3)
> I reckon this is already fixed by tree-ssa, or we'll be fixed by the incoming 
> TARGET_MEM_REF work. Zdenek?

It is fixed via neither of the above but is fixed on the tree-profiling branch via the IPA statics stuff which 
Kenney Zadeck is working on.

This is also a related to PR 19905, it will most likely be solved by the same patch also.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
  BugsThisDependsOn|                            |19905


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-03-08 01:21 -------
The testcase given above is already optimizated on the mainline via some of the aliasing code on the 
tree level but still needs to be more, witness 19905 or even the following testcase which is basically 
19905 still:
void g();
int
f(int s, int *a)
{
  static int i;
  for (i = 0; i < 800; i++)
  {
    g();
    s += a[i];
  }
  return s;
}

But all of this needs to be on the tree level to be really effective.

-- 


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[dnovillo at redhat dot com]

------- Additional Comments From dnovillo at redhat dot com  2005-03-08 01:36 -------
Subject: Re:  alias analysis doesn't take into
 account that variables that haven't their address taken can't alias arbitrary
 MEMs

pinskia at gcc dot gnu dot org wrote:

> void g();
> int
> f(int s, int *a)
> {
>   static int i;
>   for (i = 0; i < 800; i++)
>   {
>     g();
>     s += a[i];
>   }
>   return s;
> }
> 
> But all of this needs to be on the tree level to be really effective.
> 
This particular case is trivial to fix inside the tree optimizers. 
Variable 'i' is a local variable with static storage that is not upward 
exposed (i.e., it has no default definition).

Once you recognize that, you can safely flip the TREE_STATIC bit on the 
variable and expose it as a gimple register.


Diego.


-- 


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

Re: [Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[Diego Novillo]

pinskia at gcc dot gnu dot org wrote:

> void g();
> int
> f(int s, int *a)
> {
>   static int i;
>   for (i = 0; i < 800; i++)
>   {
>     g();
>     s += a[i];
>   }
>   return s;
> }
> 
> But all of this needs to be on the tree level to be really effective.
> 
This particular case is trivial to fix inside the tree optimizers. 
Variable 'i' is a local variable with static storage that is not upward 
exposed (i.e., it has no default definition).

Once you recognize that, you can safely flip the TREE_STATIC bit on the 
variable and expose it as a gimple register.


Diego.

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[amylaar at gcc dot gnu dot org]

------- Additional Comments From amylaar at gcc dot gnu dot org  2005-03-08 05:08 -------
(In reply to comment #5)
> The testcase given above is already optimizated on the mainline via some of
the aliasing code on the 
> tree level but still needs to be more, witness 19905 or even the following
testcase which is basically 
> 19905 still:
> void g();
> int
> f(int s, int *a)
> {
>   static int i;
>   for (i = 0; i < 800; i++)
>   {
>     g();
>     s += a[i];
>   }
>   return s;
> }
> 
> But all of this needs to be on the tree level to be really effective.

You can't optimize this because g is not pure.  g might call f.
But I had some real-life code that did allow the optimization inside a loop,
but prevented completely changing the static variable because of non-pure
function callsabove and below the loop.  IIRC the static variable was not
initialized right before the loop, but earlier in the function, so if you
really had some recursion, fun things would happen.  As a matter of fact,
an early version of my patch failed to take recursion into account, and we
found a few months later that rm got miscompiled because it uses indirect
recusion and static variables in a rather interesting way.

-- 


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[giovannibajo at libero dot it]

------- Additional Comments From giovannibajo at libero dot it  2005-03-08 12:30 -------
So, to recap: testcase in comment #5 should not be optimized (at least, it is 
not related to this bug). Testcase in comment #2 is already optimized correctly 
in the tree-profiling-branch, which is due to be merged for 4.1.

If so, we can suspend this bug until the branch is merged. The proposed patch 
cannot be merged to release branches because this is not a regression, AFAICT. 

I also guess that on the mainline we want to fix this at the tree level.

-- 


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-03-08 14:07 -------
(In reply to comment #8)
> So, to recap: testcase in comment #5 should not be optimized (at least, it is 
> not related to this bug). Testcase in comment #2 is already optimized correctly 
> in the tree-profiling-branch, which is due to be merged for 4.1.

Nope the testcase in comment #2 is already optimizated on the mainline (and in 4.0.0) so this could be 
closed as fixed.  Now the one in Comment #5 is a dup of bug 19905 so this could be closed as fixed for 
4.0.0 and not worried about.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.0.0


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[joern dot rennecke at st dot com]

------- Additional Comments From joern dot rennecke at st dot com  2005-03-08 14:21 -------
Subject: Re:  alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

giovannibajo at libero dot it wrote:

>------- Additional Comments From giovannibajo at libero dot it  2005-03-08 12:30 -------
>So, to recap: testcase in comment #5 should not be optimized (at least, it is 
>not related to this bug).
>
Actually, it is related inasmuch as it demonstrates a pitfall you have 
to avoid.

> Testcase in comment #2 is already optimized correctly 
>in the tree-profiling-branch, which is due to be merged for 4.1.
>
>If so, we can suspend this bug until the branch is merged. The proposed patch 
>cannot be merged to release branches because this is not a regression, AFAICT. 
>
>I also guess that on the mainline we want to fix this at the tree level.
>
It still makes sense to also handle this at the rtl level, so that the 
scheduler knows that
the MEMs don't alias.  Unless you propose to convert sched1 and sched2 to do
machine-independent scheduling on trees ;-)



-- 


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[amylaar at gcc dot gnu dot org]

------- Additional Comments From amylaar at gcc dot gnu dot org  2005-03-08 15:10 -------
You have not addressed the scheduling issues.

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


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[giovannibajo at libero dot it]

------- Additional Comments From giovannibajo at libero dot it  2005-03-08 18:18 -------
(In reply to comment #10)


> >So, to recap: testcase in comment #5 should not be optimized (at least,
> >it is 
> >not related to this bug).

> Actually, it is related inasmuch as it demonstrates a pitfall you have 
> to avoid

Right. We then should prepare a testcase from this code that scans the ivopts 
dump to check that the IV is not strength reduced or something like that.

> It still makes sense to also handle this at the rtl level, so that the 
> scheduler knows that
> the MEMs don't alias.  Unless you propose to convert sched1 and sched2 to do
> machine-independent scheduling on trees ;-)

To tell you the truth, I would like the expanders to somehow preserve tree 
aliasing information while creating RTL. But this is gonna be post 4.1 anyway 
since nobody is working on it, so yes, you are right, for now we want to handle 
this at RTL level too.

Can you show us the SH code generated by mainline for the testcase in comment 
#2? Or otherwise provide another testcase where the scheduling conflict is 
visible?

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-03-08 18:18:23
               date|                            |


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[amylaar at gcc dot gnu dot org]

------- Additional Comments From amylaar at gcc dot gnu dot org  2005-03-08 20:51 -------
(In reply to comment #16)

> And that should be fixed via the structure aliasing improvements that Daniel
is working on.

Will this also work when a[0] .. a[2] are replaced with a0 .. a2 ? 



-- 


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[mmitchel at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.0.0                       |4.0.1


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.0.1                       |---


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[amylaar at gcc dot gnu dot org]

------- Additional Comments From amylaar at gcc dot gnu dot org  2005-08-02 18:59 -------
(In reply to comment #4)
> > It is fixed via neither of the above but is fixed on the tree-profiling
branch via the IPA statics stuff which 
> Kenney Zadeck is working on.
> 
> This is also a related to PR 19905, it will most likely be solved by the same
patch also.


The promote statics patch has been removed from mainline, so this issue is
open again.

-- 


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-02 19:04 -------
(In reply to comment #19)
> The promote statics patch has been removed from mainline, so this issue is
> open again.

The improved aliasing was not reverted though which is what gets most of the improvements and not 
the promote statics pass.

-- 


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[amylaar at gcc dot gnu dot org]

------- Additional Comments From amylaar at gcc dot gnu dot org  2005-08-02 19:19 -------
(In reply to comment #20)
 
> The improved aliasing was not reverted though which is what gets most of the
improvements and not 
> the promote statics pass.

The scheduling testcase still suffers from insufficient alias information.



-- 


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-08-02 22:19 -------
Subject: Re:  alias analysis doesn't take into
	account that variables that haven't their address taken can't alias
	arbitrary MEMs

On Tue, 2005-08-02 at 19:19 +0000, amylaar at gcc dot gnu dot org wrote:
> ------- Additional Comments From amylaar at gcc dot gnu dot org  2005-08-02 19:19 -------
> (In reply to comment #20)
>  
> > The improved aliasing was not reverted though which is what gets most of the
> improvements and not 
> > the promote statics pass.
> 
> The scheduling testcase still suffers from insufficient alias information.

And it will until all of the info about what variables, etc, we have is
kept through scheduling.




-- 


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20367
Bug 20367 depends on bug 19905, which changed state.

Bug 19905 Summary: Extra V_MAY_DEF on a static variable whose address is not taken (we should be able to move the load out of the loop)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19905

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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.6.0

--- Comment #27 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-01-10 15:31:09 UTC ---
Should be fixed in at least 4.6.

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[rguenth at gcc dot gnu dot org]

------- Comment #26 from rguenth at gcc dot gnu dot org  2010-05-09 17:09 -------
alias-export is now merged so the RTL level should have the same alias
information as the tree level.  And thus scheduling should be fixed.(?)


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |WAITING


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[amylaar at gcc dot gnu dot org]

------- Comment #25 from amylaar at gcc dot gnu dot org  2009-04-06 00:37 -------
(In reply to comment #24)
> Which testcase?

The second attachment, 20367-sched.c

>  This bug is mildly confusing.  Note that i is a global
> variable,

If you mean i in f of comment #2, that's not gloabal, but static.

> it may be reached via recursive invocations of the function and
> we do not have analysis that disproves this.

I suppose you mean that f may be reached via recursion, thus
clobbering i, as already mentioned in comment #7.

Unfortunately, the original testcase went into the big bit bucket in the sky,
and when you try to make up a minimal example on the spot, you are bound to
overlook the very same aspects of the problem you have overlooked in the
work on the problm so far.

But there is still code in EEMBC that genuinely benefits from load hoisting /
store sinking and scheduling which is enabled by recognizing that a static
variable that hasn't got its address taken can't alias another MEM - in some
cases, the static variable can be completely replaced by a local variable,
in other cases, it can't (without whole-program analysis) because an
indirect recursive call cannot be ruled out.


-- 


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[rguenth at gcc dot gnu dot org]

------- Comment #24 from rguenth at gcc dot gnu dot org  2009-04-05 20:17 -------
Which testcase?  This bug is mildly confusing.  Note that i is a global
variable, it may be reached via recursive invocations of the function and
we do not have analysis that disproves this.


-- 


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

[Bug rtl-optimization/20367] alias analysis doesn't take into account that variables that haven't their address taken can't alias arbitrary MEMs

[steven at gcc dot gnu dot org]

------- Comment #23 from steven at gcc dot gnu dot org  2009-04-05 12:38 -------
Could it be that this is now fixed by the a-i-b merge?


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org


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