Re: [PATCH] Speed up FRE (~10% on PR34683)

[Richard Guenther <rguenther at suse dot de>]

On Mon, 7 Jan 2008, Daniel Berlin wrote:

> On Jan 7, 2008 4:31 PM, Andrew MacLeod <amacleod@redhat.com> wrote:
> > Daniel Berlin wrote:
> > > On Jan 7, 2008 12:05 PM, Richard Guenther <rguenther@suse.de> wrote:
> > >
> > >> This speeds up compile of PR34683 (-O -fstrict-aliasing
> > >> -fno-tree-loop-optimize) by ~10% by avoiding to sort already
> > >> sorted VUSEs -- which requires changing sort order from SSA_NAME versions
> > >> to DECL_UIDs, the same as the operand scanner uses.  The patch
> > >> cuts the number of qsorts of a vector of 256 elements by an order
> > >> of magnitude.
> > >>
> > >> Danny, was there a particular reason for the sort order of VOPs in
> > >> tree-vn?
> > >>
> > >
> > > To compare the vops arrays in linear time.
> > >
> > > If you only sort by DECL_UID, now two lists of vops, like
> > >
> > > SMT.3_4
> > > SMT.3_7
> > >
> > > SMT.3_7
> > > SMT.3_4
> > >
> > > won't be sorted right anymore, no?
> > >
> >
> > you should never see that should you?  Virtual operands can never
> > overlap, they must go dead at a VDEF.

Which is what I thought as well.

> We value number memory states in SCCVN, so through memory copies, we
> can determine two vuses are equivalent, and give each vuse a value
> number itself (named after the vdef result it is equivalent to).
> When you transform the vops list into their value numbered vops list
> you can end up with situations where we have a vop list like the
> above.
> 
> This actually happens more than one would think.

So I thought about this and figured we never will change the DECL_UID
of a VOP we value number.  In fact, operand_build_cmp contains:

  /* We want to sort in ascending order.  They can never be equal.  */
#ifdef ENABLE_CHECKING
  gcc_assert (u1 != u2);
#endif

and this didn't trigger during bootstrap and test either.

So, how do you think we can value number a VOP to a different one?

Thanks,
Richard.