Re: [vta] stabilize loop-unroll across insn uid variations

[Alexandre Oliva <aoliva at redhat dot com>]

On Oct  7, 2008, "Richard Guenther" <richard.guenther@gmail.com> wrote:

> On Tue, Oct 7, 2008 at 11:36 AM, Paolo Bonzini <bonzini@gnu.org> wrote:
>> Alexandre Oliva wrote:
>>> compare-debug detected some differences causes by RTL loop unrolling,
>>> because debug insns changed the insn uids it uses as hashes.  Because
>>> of this change, insns were walked in different orders, and different
>>> decisions were made.

>> This should also go in trunk IMO.

I don't see that it would have any noticeable effect in the trunk,
but I surely don't oppose reducing the divergence :-)

> One cheap way out is to walk a bitmap of the UIDs - I didn't look
> too closely at the patch, but maybe using bitmaps are cheaper than a
> linked list.

I actually considered that.  IIRC I even implemented something, using
DF_INSN_UID_GET, but I wasn't sure this would reach all insns at that
point.  IIRC I actually tested for that and got failures for
newly-added insns, but I'm not sure, this was almost a month ago.

Anyhow, extending the array used by DF to maintain the UID-to-INSN map
complete would waste more memory than any savings we might obtain with
a bitmap at this point.  So it would get worse performance (walking
bitmaps is worse than walking a list, even if still O(n)), possibly
worse memory (O(N) rather than O(n), with N >> n, if df->insns isn't
complete), and still somewhat impredictable ordering (UID ordering is
not necessarily the same as sequential ordering).

Nevertheless, if trunk *does* maintain a complete df->insns map,
updated on the fly, then it might make sense to use it.  Whatever
works, I don't have strong feelings either way.

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}
FSFLA Board Member       ÂSÃ Libre! => http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}