[tree-ssa] alias analysis

[Daniel Berlin]

On Thursday, February 13, 2003, at 11:21  AM, Diego Novillo wrote:

> On Thu, 2003-02-13 at 10:59, Daniel Berlin wrote:
>
>> We shouldn't be having an analyzer that *only* uses PTA or *only* uses
>> TBAA.
>> That's silly.
>> They can work in concert, as they do now.
>> PTA is still used to disambiguate the aliases.
>>
> OK, so what I didn't understand is the model we use for PTA then.  We
> don't actively call may_alias_p() from the optimizers.  What we do is
> collect alias information before hand so that the optimizers can call
> 'may_aliases (var)' and get a list of all the variables that may alias
> with 'var'.

I've not yet figured out whether this model is going to be usable in 
terms of speed/space.
Tell ya what.
Let me commit the SSAPRE stuff, and while i'm waiting for the insertion 
framework (which it needs for me to continue debugging bootstraps), 
i'll work on something that uses it so i can tell if it's usable this 
way.

>
> Perhaps that's not a good model?  When I suggested making may_alias_p
> static I had that model in mind.  We pre-compute all the alias
> relationships before building SSA and then the optimizers can traverse
> 'may_aliases (var)'.  If this is not a good model for doing PTA, then
> let's change it.

The thing is that i'm not sure.   PTA info is currently cheap to both 
query (because it caches it properly) and update (because it's flow 
insensitive, and thus, we can just throw new and changed statements at 
it regardless of where they actually appear. Of course, doing it this 
way makes it more conservative, so after some large number of updates 
we could recompute it fully if it makes sense or something).

That said, right now (well, in my tree with the hash table lookups and 
other overhead removed), in computing alias sets, we ask PTA to 
disambiguate aliases (in 20001226-1.c) 260 million times.
That's right.  260,160,770 times.
( 18.03     35.62    35.62 260160770     0.00     0.00  
ptr_may_alias_var)
It takes 35 seconds.

I can't make ptr_may_alias_var any faster, it already takes less than a 
millisecond.
Quick math shows it takes 1.3691533787422801e-07 seconds per call, 
which is good. :).

This means TBAA, addressable determination, etc, is failing to 
determine things don't alias 260 million times (since PTA is a last 
resort call).

 From a different perspective, this also means if our optimizers are 
going to make less than 260 million PTA queries, it's a win to have 
*them* query the PTA info when they want to, even though this means an 
uncleaner interface. (IE they would walk may_aliases, which wouldn't be 
PTA disambiguated, and if they see some variable alias they really 
don't want, they call PTA to try to disambiguate it).

Without some optimizers that use the info, it's impossible for me to 
really even guess which makes sense, since I have no figures on "how 
often an optimizer runs into an alias it really doesn't want to exist 
(IE is preventing an optimization) that PTA can disambiguate".

 From an interface perspective, a PTA query isn't very difficult or 
unclean or anything like that.  Personally, I don't think code that 
looks like

for (i = 0; i < VARRAY_ACTIVE_SIZE (may_aliases (var)); i++)
{
	tree alias = VARRAY_TREE (may_aliases (var), i);
	if (I think this alias prevents me from doing what i want)
        {
		if (!ptr_may_alias_var (ptr, var))
			<but it really doesn't>
		else
			<it really does>
	  }
}

is going to be horrifically ugly compared to:
for (i = 0; i < VARRAY_ACTIVE_SIZE (may_aliases (var)); i++)
{
	tree alias = VARRAY_TREE (may_aliases (var), i);
	if (this alias prevents me from doing what i want)
        {
			<it really does>
	  }
}

if it doesn't occur too often.

But if it's everywhere that an optimizer needs to do this, ...

Trying to draw on guidance from other compilers, i'll say i have yet to 
see a single one where the PTA info isn't integrated with the other 
alias set info (IE they effectively have just a single may_aliases 
array per variable).

But those that use PTA info all do some combination of
1. Have alias info backed by a file, so that they aren't keeping it all 
in memory at once if they don't have to (granularity varies).
2. Use some kind of indexing and bitmaps so that their queries are bit 
testing and their memory usage is smaller.

IE In one case they assign each variable an index, and use a sparse 
triangular bitmatrix to tell what numbers alias.

If they want to determine the entire list of aliases (not often) for a 
variable, they just walk the bitmatrix row for that index, and use a 
reverse mapping to map the numbers back into variables.

>
>>>   I thought I had neatly separated what we do when
>>> -ftree-points-to is given and when it's not.  I don't know why you
>>> removed it.
>>
>> Because it's broken that way (Jeff's changes broke it, AFAICT), and
>> because it's too memory intensive if you create explicit may-alias 
>> sets
>> because of global var aliasing.  It's not usable that way.  I've got
>> figures, but they aren't pretty.
>> It's not a fixable problem.  We'll have to create some kind of set to
>> reduce the memory requirements.
>>
> OK, this one is different.  I'm starting to believe that we should not
> model call-clobbering with a forced alias to *.GLOBAL_VAR.  It seemed
> like a neat trick, but it creates problems:
>
> (1) Since *.GLOBAL_VAR aliases every type, functions that have
> call-clobbered variables also have a single alias set where everything
> aliases everything.  Too pessimistic.
>
> (2) As you point out, *.GLOBAL_VAR blows up together with PTA.

Blows up is an understatement.
It's more like a nuclear holocaust.
>
> I've been thinking that instead of having this silly aliasing model, we
> should actually insert a VDEF for every variable that may be clobbered
> at a call site.

>
>> You seem to think we don't use PTA anymore.
>> This is not the case at all.
>>
> Right, sorry about this one.  This is just me reading every other line
> of a message.
>
>
> Thoughts?   Diego.
>