[PATCH]: Fix alias slowdown

["Daniel Berlin" <dberlin at dberlin dot org>]

This somewhat large patch is a continuation of the code to fix our
aliasing slowdown.

Since the last patch was posted, i've gotten entirely rid of nonlocal_var.
This is more or less a half-reversion to the way things were before
the set of patches that used escaped_vars.  The main difference is
that, instead of falling back to using only SMT's for variables that
may have pointed-to anything, we now just merge the SMT alias sets
into these variables.

This is 95% of the way towards removing SMT's, the only case that ever
uses them now is grouping and bare global variables.

I've removed verify_name_tags because it turns out it gets the wrong
answer after grouping (the may-alias list of an NMT and pt_vars no
longer match, because we don't update pt_vars during grouping).  I'm
somewhat surprised we haven't hit a failure in there before, but it
was only a matter of time.

It doesn't verify anything truly interesting anyway.

The only interesting thing is that i discovered two latent bugs:

1. Pointers that escaped to globals were not marked as possibly
written to.  We only did so for calls, which is wrong.
2.  SMT's were being dealt with wrong when we pruned all the variables away.

In particular, this is the real cause of a few bugs.   What happens is
that it is not enough to just use a bare SMT when you prune away all
the possible aliases, you must also add a vdef/vuse of the SMT's that
are a subset of that SMT.

Consider:
struct test1
{
 int a;
 int b;
};
struct test2
{
 float d;
 struct test1 sub;
};

int global;

int bla(struct test1 *xa, struct test2 *xb)
{
 global = 1;
 xb->sub.a = 1;
 xa->a = 8;
 return xb->sub.a;
}

We will prune away all possible aliases of the accesses to xa and xb
because they only access variables we can't see.

However, it is not enough, in the case of xa->a = 8 to only add the
SMT for test1 to the vdef list.  the SMT for test2 (xb) is a subset of
the alias set for SMT, and needs to be there too.  If we didn't prune,
they would both have the false alias "global", and thus, would
conflict.  However, because we prune, we need to figure out the
subsets and add them appropriately.

We thus compute what SMT's need to be added to points-to variables for
each set, and add those as well (this in turn causes them to be added
to the SMT for the variable automatically).

As part of fixing this, I redid what is currently the SMT_USED_ALONE
stuff so that it is not necessary for passes to recompute it.
I will remove it in a followup patch.

This patch brings the PTA time for cpgram.ii down to 1.57 seconds, and
the alias analysis time to 22 seconds.  All of the alias analysis time
is actually spent walking the alias lists in add_may_alias, searching
for duplicates.  The memory usage is reasonable again too.

I will fix the add_may_alias time later.

For now, I will commit this patch to mainline, and after a few weeks, to 4.2.

Note that this patch is going to have memory and performance impact.
Memory impact should be positive on *most* cases, but may be
regressing up to 10% on others .  We should gain back some performance
(in particular, loadpre14 and 15 are now fixed).
The only real way to get that memory back is to stop pruning at all,
there is no way to do pruning correctly if we don't do subsetting of
SMT's in the current system.

Bootstrapped and regtested on i686-pc-linux-gnu.

Bootstrapped and regtest

Attachment: aliasfixup.diff.txt
Description: Text document