PR42873: avoid dataflow oscillation in var-tracking

[Alexandre Oliva]

The testcase in the bug report no longer fails, but it's not because it
was fixed, but rather because other changes made the problem latent.

The oscillation occurs because there are 3 equivalent values in the
loop, and the value bound to one variable oscillates between two of
them.  This has to do with the way we search for equivalences when
merging location lists: we don't necessarily have canonicalized
equivalence sets in one of the inputs, so we don't search for a
canonical value.  Instead, we just take the first value in the
non-canonicalized accummulated set that happens to have a match in the
other incoming block.

As a result, some merge operations chose value 1, while others chose the
equivalent value 11, and it just so happened that the circumstances to
choose one or the other varied on subsequent iterations, so we never
converged.

This patch fixes the problem by adding a final consolidation pass to the
canonicalization at the end of a merge: for every 1-part variable, we
quickly check that it's bound to the canonical value of the equivalence
set and, if it isn't, we make it so.

Unfortunately, we can't do that as part of the star-canonicalization of
values.  We only managed to do this for values in a single pass because
values link back to each other, so, even if when we visited a value we
hadn't come across the canonical value of its set yet, if we do later
on, we go back and fix it.  However, since we can't link back to
variables (we can't refer to them in location lists), we have to adjust
variables after visiting all values.

This could improve if we switch to a different representation of
location lists for equivalence sets, say, sharing the same list for all
equivalent values and variables.  For now, it's much simpler, and not
much costly, to take this patch.

Regstrapped on x86_64-linux-gnu, i686-linux-gnu and ia64-linux-gnu.

Ok to install?

-------------- next part --------------
A non-text attachment was scrubbed...
Name: vta-bind-var-to-star-canon-value-pr42873.patch
Type: text/x-diff
Size: 2855 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20100318/9466a521/attachment.bin>
-------------- next part --------------


-- 
Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist      Red Hat Brazil Compiler Engineer