[tree-ssa] alias analysis

[Diego Novillo]

On Tue, 11 Feb 2003, Diego Novillo wrote:

> On Tue, 11 Feb 2003, Jeff Law wrote:
> 
> >  >>   int x = 5;
> >  >>   int y = 10;
> >  >> 
> >  >>   foo (&x, &y);
> >  >> 
> >  >> 
> >  >> We'd have distinct tags for x & y, even though they have the same alias
> >  >> set.
> >  >> 
> >  >Now you lost me.  I thought you were separating load from store
> >  >aliases?  Aren't x and y store aliases here?  Or is it load
> >  >aliases?  I think I need a step-by-step description again :)
> > They are stores, but they are stores to distinct VAR_DECLs.  There's no
> > way they can actually alias each other as the underlying objects will
> > always be distinct.  Ie, there is no way that x = foo will every modify
> > y.
> > 
> Oh, I see.  Do you want to be able to rewrite X and Y in this
> case?  The problem is that since X and Y are aliased, regardless
> of what their alias is, SSA will refuse to rewrite them.  What we
> will re-write are the VDEFs to their alias tag.
> 
> In this case we would want to split alias sets whose members
> cannot alias each other.  But this could quickly take us back to
> quadratic behaviour.  Say we have this initial alias set for X
> and Y:
> 
> *p: { x y }
> 
> What you can do is traverse this alias set and make X and Y alias
> only those members of the set that can actually point to them.
> That is, any other INDIRECT_REFs in the set and themselves.
> 
> In the case above, X and Y only alias themselves and *P.  I know
> it's a bit absurd to think that an addressable aliases itself,
> but it's a tautology and happens to fit in the existing framework :)
> 
> At this point we can introduce the asymmetry of loads and stores.
> For each variable V, we distinguish between V's store-aliases and
> load-aliases:
> 
> (1) We create a VDEF for every store-alias of V everytime V is
>     assigned a new value.
> 
> (2) We create a VUSE for every load-alias of V everytime V is
>     used.
> 
> In this case we will have:
> 
> x: store-alias: *p, load-alias: x
> y: store-alias: *p, load-alias: y
> *p: store-alias: x, y, load-alias: x, y
> 
> Normal Form			SSA Form
> 
> {		  	  	   {
>   p = &x or &y		   	 	p = &x or &y
>   ...		    			...
> 	
> 			    		# (*p)_2 = VDEF<(*p)_1>
>   x = 5;	   	 		x_1 = 5;
> 
> 		    			# (*p)_3 = VDEF<(*p)_2>
>   y = 3;	   	 		y_2 = 3;
> 
> 		    			# x_2 = VDEF<x_1>
> 		   		 	# y_3 = VDEF<y_2>
>   *p = *p + 8;			    	(*p)_5 = (*p)_3 + 8;
>   ... = x + y;			    	... = x_2 + y_3;
> }			     	   }
> 
> 
> Is this something along the lines you had in mind.  Apologies if
> it makes little sense.  I'm on my way out and I'll probably have
> little connectivity until next week.  I'll think about it some
> more in the meantime.
> 
One thing I forgot.  This has the potential of being a memory and
performance pig.  These alias sets tend to have many variables
clustered together.


Diego.