Re: [tree-ssa, RFC] new, very experimental ssa-vn

[Steven Bosscher <s dot bosscher at student dot tudelft dot nl>]

On Monday 05 January 2004 02:28, Daniel Berlin wrote:
> On Jan 4, 2004, at 8:24 PM, Steven Bosscher wrote:
> > Hi,
> >
> > Here's a first shot at SCC-based SSA GVN.  It still needs a lot of
> > work,
> > and cleanups to the "older" parts, but it's (too) slowly getting into
> > something usable :-).
> >
> > Much of this code is already several months old, but I just never took
> > the
> > time to finish it, because the existing GVN that is part of the
> > dominator
> > optimizations just rules and this new pass doesn't find many
> > opportunities
> > for further redundancy elimination.
>
> I should point out that Simpson and others claim that doing congruence
> partitioning based GVN catches things hash based GVN doesn't.

Simpson also claims that SCC-based GVN "combines the advantages of
hash-based value numbering and value partitioning", and he proves
that SCC-VN finds at least those congruences that hash-based VN or
value partitioning would find.  In his thesis, Simpson even bluntly
dismisses value partitioning as a serious option for implementation
in a compiler.

In practice, I see this patch catches a few, but only a few, extra
redundancies in a GCC bootstrap.  I still need to look at it closer
and see where the pass misses some opportunities, of course ;-) 

Gr.
Steven