Re: [Bug tree-optimization/29680] [4.3 Regression] Misscompilation of spec2006 gcc

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

A detailed proposal:

So here is what i was thinking of.  When i say symbols below, I mean
"some VAR_DECL or structure that has a name" (like our memory tags
do).  A symbol is *not* a real variable that occurred in the user
program.  When I say "varaible" i mean a variable that occurred in the
user program.

The real problem with our alias system in terms of precision, and
often in terms of number of useless vops, is that we are trying to use
real, existing, variables, to approximate the portions of the heap a
statement accesses.

When things access portions of the heap we can't see (nonlocal
variables), we fall down badly in terms of precision because we can
eliminate every single local variable as an alias, and need to then
just say it accesses "some nonlocal variable".  This causes precision
problems because it means that statements accessing nonlocal variables
that we can *prove* don't interfere, still currently share a VUSE
between them.

We also have useless vops whenever we have points-to sets that
intersect between all statements that interfere, because we end up
adding aliases for you can eliminate the members of the alias set

We also currently rely on operand-scan time pruning, which is very ugly.

There is a way to get the minimal number of vuses/vdefs necessary to
represent  completely precise (in terms of info we have) aliasing,
while still being able to degrade the precision gracefully in order to
enable the vuses/vdefs necessary to go down

The scheme i propose *never* has overlapping live ranges of the
individual symbols, even though the symbols may represent pieces of
the same heap.

In other words, you can rely on the fact that once an individual
symbol has a new version, there will never be a vuse of an old version
of that symbol.



The current vdef/vuse scheme consists of creating memory tags to
represent portions of the heap.  When a memory tag has aliases, we use
it's alias list to generate virtual operands.  When a memory tag does
not have aliases, we generate a virtual operand of the base symbol.

The basic idea in the new scheme is to never have a list of aliases
for a symbol representing portions of the heap.  The symbols
representing portions of the heap are themselves always the target of
a vuse/vdef.  The aliases they represent is immaterial (though we can
keep a list if something wants it).

This enables us to have a smaller number of vops, and have something
else generate the set of symbols in a precise manner, rather than have
things like the operand scanner try to post process it.

The symbols are also attached to the load/store statements, and not to
the variables.

The operand renamer only has to add vuses/vdefs for all the symbols
attached to a statement, and it is done.

In the simplest, dumb, non-precise version of this scheme, this means
you only have one symbol, called "MEM", and generate vuse/vdefs
linking every load/store together.

In the absolute most-precise version of this scheme, you partition the
loads/store conflicts in statements into symbols that represent
statement conflictingness.

In a completely naive, O(N^3) version, the following algorithm will
work and generate completely precise results:

Collect all loads and stores into a list (lslist)
for each statement in lslist (x):
 for each statement in lslist (y):
   if x conflicts with y:
      if there is no partition for x, y, create a new one containing x and y.
      otherwise
       for every partition y belongs to:
             if all members of this partition have memory access that
conflicts with x:
              add x to this partition
            otherwise
             create a new partition containing all members of the
partition except the ones x does not conflict with.
             add x to this partition


This is a very very slow way to do it, but it should be clear (there
are much much much faster ways to do this).

Basically, a single load/store statement can belong to multiple
partitions.  All members of a given partition conflict with each
other.

given the following set of memory accesses statements:

a, b, c, d

where:
a conflicts with b and c
b conflicts with c and d
c conflicts with a and b
d conflicts with a and c

you will end up with 3 partitions:
part1: {a, b, c}
part2: {b, c, d}
part3: {d, a, c}

statement c will conflict with every member of partition 1 and thus
get partition 1, rather than a new partition.

You now create symbols for each partition, and for each statement in
the partition, add the symbol to it's list.

Thus, in the above example we get

statement a - symbols: MEM.PART1, MEM.PART3
statement b - symbols: MEM.PART1, MEM.PART2
statement c - symbols: MEM.PART1, MEM.PART2, MEM.PART3
statement d - symbols MEM.PART2, MEM.PART3

As mentioned before, the operand renamer simply adds a vdef/vuse for
each symbol in the statement list.

Note that this is the minimal number of symbols necessary to precisely
represent the conflicting accesses.

If the number of partitions grows large (and thus requires too many
symbols), you can simply union any partitions you like.

As long as the partitions contain *at least* the real conflicts for
those statements, all you would do is add false aliasing.

Note that while the symbols partitioning the heap are not necessarily
disjoint in terms of parts of the heap they represent, the vuse/vdefs
for an individual symbol will never overlap, just like our current
representation.