This is an archive of the discontinued LLVM Phabricator instance.

NewGVN: Move leaders around properly to ensure we have a canonical dominating leader. Fixes PR 31613.
ClosedPublic

Authored by dberlin on Jan 11 2017, 9:01 PM.

Details

Summary

This is a testcase where phi node cycling happens, and because we do
not order the leaders by domination or anything similar, the leader
keeps changing.

Using std::set for the members is too expensive, and we actually don't
need them sorted all the time, only at leader changes.

We could keep both a set and a vector, and keep them mostly sorted and
resort as necessary, or use a set and a fibheap, but all of this seems
premature.

After running some statistics, we are able to avoid the vast majority
of sorting by keeping a "next leader" field. Most congruence classes only have
leader changes once or twice during GVN.

Event Timeline

dberlin retitled this revision from to NewGVN: Move leaders around properly to ensure we have a canonical dominating leader. Fixes PR 31613..
dberlin updated this object.
dberlin added a reviewer: davide.
dberlin added a subscriber: llvm-commits.
  • Update testcase with comment, revert gratuitous formatting change

Also, this was 3-staged on darwin and linux

lib/Transforms/Scalar/NewGVN.cpp
331–332

These are only ever called with instructions, and doing this saves us a ton of work in the new work on moveValueToNewCongruenceClass.

I can split out the change if we want.

1079

(IE the reverse check)

davide edited edge metadata.Jan 11 2017, 10:29 PM

Some comments inline, this looks correct but I'd like to run some tests tomorrow morning once I'm back to my workstation. Quick question, I can see how a set/vector can help here but I didn't think about the fib heap. Why did you mention such a variant and not let's say binomial/trinomial?

lib/Transforms/Scalar/NewGVN.cpp
148

~0U ?

1074

~0U ?

1080–1084

Can you please add a messahge to this assertion?

1131

X can probably be passed by reference?
I'm always in doubt with auto (I try to never rely on the implicit referenceness/pointerness of auto and always be explicit to avoid accidental copies)

1203

spurious whiteline

1220

auto *

1562–1563

unrelated I assume?

test/Transforms/NewGVN/pr31613.ll
68

this moduleId here crept in?

Some comments inline, this looks correct but I'd like to run some tests tomorrow morning once I'm back to my workstation. Quick question, I can see how a set/vector can help here but I didn't think about the fib heap. Why did you mention such a variant and not let's say binomial/trinomial?

Fibheaps have O(1) insert/delete. We don't want to pay any cost until we actually extract. So when we add/remove members, we just do that, and then when we actually change leaders, we pay the cost of extracting the min.
You could also use weak rank heaps.

(Note that delete on a fibheap/rank paired heap is basically tombstoning by just "decrease-key to negative infinity", special case them on extract/etc)

dberlin marked 6 inline comments as done.Jan 12 2017, 9:14 AM
dberlin added inline comments.
lib/Transforms/Scalar/NewGVN.cpp
1131

The members are already value *'s :)

1562–1563

Yes, i'll revert it.

dberlin edited edge metadata.
  • Fix for review comments and revert spurious formatting changes
davide accepted this revision.Jan 12 2017, 10:35 AM
davide edited edge metadata.

Did my testing, LGTM, let's try to get this in before the branch =)

This revision is now accepted and ready to land.Jan 12 2017, 10:35 AM
This revision was automatically updated to reflect the committed changes.