RE: Improving Alias Analysis

RE: Improving Alias Analysis

[Sanjiv Kumar Gupta, Noida]

On Fri, 18 Oct 2002, Sanjiv Kumar Gupta, Noida wrote:

>Again, points-to analysis is what you're looking for.  The
>tree-alias-* files on tree-ssa branch will provide pointers to
>literature that covers this problem.


>Diego.

Thanks. I'll soon have a look into these files.

Regards
Sanjiv

Re: Improving alias analysis

[Sanjiv Kumar Gupta, Noida]

On Thu, 17 Oct 2002, Sanjiv Kumar Gupta, Noida wrote:

> I intend to improve the alias analysis so that it can handle 
> such cases. For that, I am currently thinking of possible 
> solutions. One solution could be backward traversing of the
> list of RTXs and finding out if the two pointers differ. 
> The other could be maintaining symoblic values for regsiters
> at each instruction level.
> 
>>Whatever you do, please try and use published algorithms.  Alias
>>analysis is a very well known technique and many solutions exist
>>in the literature. 

>>Diego.
I've decided to implement the following paper to solve the alias
analysis problem

http://citeseer.nj.nec.com/cache/papers/cs/1318/ftp:zSzzSzftp.cs.arizona.edu
zSzreportszSz1997zSzTR97-13.pdf/debray98alias.pdf
(long and broken URL, copy paste the complete URL in your browser)

This approach is capable of representing the address arithmatic and
can distinguish between pointer pseudos that have been computed 
using distinct displacements from a base.

To see the problem description, refer to my earlier postings
	http://gcc.gnu.org/ml/gcc/2002-10/msg01558.html	
	http://gcc.gnu.org/ml/gcc/2002-10/msg01032.html

--Sanjiv

RE: Improving Alias Analysis

[Sanjiv Kumar Gupta, Noida]

>Again, points-to analysis is what you're looking for.  The
>tree-alias-* files on tree-ssa branch will provide pointers to
>literature that covers this problem.


>Diego.

I built the tree-ssa-branch. It has the same problem. That may be
because aliasing ,GVN etc are in TODO list as of now. Also, it 
implements Steengaard's algorithm based on store locations modeling 
and type inference, which may well work as a tree optimizer but may
not suit my case of changing the exisiting RTL optimizer. 
I also want to keep the aliasing improvment changes small and
focused enough to avoid any major design changes. 
 
I am thinking in terms of approaches somewhat similiar to 
	
http://citeseer.nj.nec.com/cache/papers/cs/1318/ftp:zSzzSzftp.cs.arizona.edu
zSzreportszSz1997zSzTR97-13.pdf/debray98alias.pdf
	
http://citeseer.nj.nec.com/cache/papers/cs/10403/ftp:zSzzSzftp.inria.frzSzIN
RIAzSzpublicationzSzpubli-pdfzSzRRzSzRR-3764.pdf/amme99data.pdf

As I mentioned earlier, one other obvious solution is to back traverse
the RTXs list and finding out if the two pointers differs by different
offsets to a common base. But I am looking for lighter solution.

Any ideas would be a great help!

Best Regards
Sanjiv

Re: Improving Alias Analysis

[Diego Novillo]

On Fri, 18 Oct 2002, Sanjiv Kumar Gupta, Noida wrote:

> do not agree. For that we need to save the address arithmatic. This
> could be done by calculating possible symbolic value for each register
> at each program statement but I am still looking for good ideas here.
> 
Again, points-to analysis is what you're looking for.  The
tree-alias-* files on tree-ssa branch will provide pointers to
literature that covers this problem.


Diego.

RE: Improving Alias Analysis

[Sanjiv Kumar Gupta, Noida]

On Thu, Oct 17, 2002 at 05:48:09PM +0530, Sanjiv Kumar Gupta, Noida wrote:
>> This is primarily because it does not record sufficient
>> info for alias analysis, by which, it can know what
>> values various registers are supposed to contain
>> at a particular program point.

>This is because intended usage is not "at a particular point",
>but function-wide.  If you want the former, you'll have to 
>come up with some different infrastructure.


>r~

True, that means this case fails because it's not covered by the
design. But,IMHO, we will need to have a mechansim which tells
us the pointers contents at a desired point considering the
address arithmatic done on them so far. please correct me if you
do not agree. For that we need to save the address arithmatic. This
could be done by calculating possible symbolic value for each register
at each program statement but I am still looking for good ideas here.

Regards
Sanjiv

Re: Improving Alias Analysis

[Richard Henderson]

On Thu, Oct 17, 2002 at 05:48:09PM +0530, Sanjiv Kumar Gupta, Noida wrote:
> This is primarily because it does not record sufficient
> info for alias analysis, by which, it can know what
> values various registers are supposed to contain
> at a particular program point.

This is because intended usage is not "at a particular point",
but function-wide.  If you want the former, you'll have to 
come up with some different infrastructure.


r~

Re: Improving Alias Analysis

[Diego Novillo]

On Thu, 17 Oct 2002, Sanjiv Kumar Gupta, Noida wrote:

> I intend to improve the alias analysis so that it can handle 
> such cases. For that, I am currently thinking of possible 
> solutions. One solution could be backward traversing of the
> list of RTXs and finding out if the two pointers differ. 
> The other could be maintaining symoblic values for regsiters
> at each instruction level.
> 
Whatever you do, please try and use published algorithms.  Alias
analysis is a very well known technique and many solutions exist
in the literature.  Try a search on citeseer with terms like
points-to alias analysis.

For tree-ssa, Daniel has implemented a fairly quick points-to
analyzer.  Documentation and references are on the tree-ssa
branch files tree-alias* (http://gcc.gnu.org/projects/tree-ssa/).


Diego.

Improving Alias Analysis

[Sanjiv Kumar Gupta, Noida]

Hi,

The current alias analysis in gcc is not capable 
of disambiguating between certain obvious cases of 
memory references. For example, consider two pointers
 r101, r102 and some simple address arithmatic
	
	...
	r101 = r100 + 8;
	r102 = r100 + 32;
	64-bit dereference of r101
	64-bit dereference of r102

The present implementation says r101 and r102 aliases
each other. I noticed this problem for SH4. SH4 does
not allow register+offset addressing for floating point
load/stores. I fear that the same problem could also be 
there for IA64.

After digging into some code, I found out that gcc has
no in-built mechanism to figure out that these 
pointers have been computed to contain distinct values.
This is primarily because it does not record sufficient
info for alias analysis, by which, it can know what
values various registers are supposed to contain
at a particular program point.

In addition to the above case , there might be exisiting,
other cases of failures.

I intend to improve the alias analysis so that it can handle 
such cases. For that, I am currently thinking of possible 
solutions. One solution could be backward traversing of the
list of RTXs and finding out if the two pointers differ. 
The other could be maintaining symoblic values for regsiters
at each instruction level.

Please let me know your ideas for a good solution.

Regards
Sanjiv