This is an archive of the discontinued LLVM Phabricator instance.

[RegAllocGreedy] Take last chance recoloring into account in evicting.
ClosedPublic

Authored by rudkx on Feb 13 2019, 12:24 PM.

Details

Summary

Last chance recoloring inserts into FixedRegisters those virtual
registers it is attempting to assign a physical register to.

We must consider these when we consider candidates for eviction so that
we do not end up evicting something while we are attempting to recolor
to assign it.

This is hitting in an out-of-tree target and no longer reproduces on
trunk. That does not appear to be a result of it having been fixed, but
rather, it appears that optimization changes and/or other changes to
register allocation mask the problem.

I haven't found a way to come up with a reasonable test case for this
(i.e. one that I can actually commit to open source, is reasonable
in size, and actually reproduces the issue).

rdar://problem/45708741

Diff Detail

Event Timeline

rudkx created this revision.Feb 13 2019, 12:24 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 13 2019, 12:24 PM
rudkx edited the summary of this revision. (Show Details)Feb 13 2019, 12:26 PM
rudkx edited the summary of this revision. (Show Details)
qcolombet added a comment.EditedFeb 13 2019, 1:24 PM

Hi Mark,

I am not sure that's the right fix, because by design, last chance recoloring was allowed to evict things that got scavenged.
To elaborate a bit on that, it is supposed to be fine to split the value (by spilling or copy insertion) but it is not fine to have it appears twice in the "moving part" (the fixedRegisters set).

If you evict something, the idea was the evicted register would still be here but with a smaller live-range, e.g.,

reg1(Rx) =
...
= reg1(Rx)

During last chance recoloring, if we were to scavenge reg1 and then evict it, we would end up with something like:

reg1(unassigned) =
Tmp(unassigned) = live-rangeSplittingOp reg1(unassigned)
...
regNew(unassigned) = live-rangeSplittingOp Tmp(unassigned)
= regNew(unassigned)

Which is fine.
When reverting the last coloring changes if it fails, reg1 can get back to its old assignment (Rx here) with no problem.

IIRC there was a bug with the order in which we assign them back, but I thought it was fixed.

What is the problem you're seeing?

Cheers,
-Quentin

qcolombet accepted this revision.Feb 13 2019, 1:52 PM

Hi Mark,

Actually, re-reading through the code (it's been a while since I touched it), you're right, the intent was to freeze those regs when we scavenge them but do whatever we want to the others.
Bottom line, the fix looks good to me.

Nitpick below.

Cheers,
-Quentin

llvm/lib/CodeGen/RegAllocGreedy.cpp
2626

IIRC ::insert returns a boolean that says whether or not it has been inserted.
Thus, we can avoid the call to count and assert on the result of ::insert.

This revision is now accepted and ready to land.Feb 13 2019, 1:52 PM
rudkx added inline comments.Feb 13 2019, 2:23 PM
llvm/lib/CodeGen/RegAllocGreedy.cpp
2626

Yes, I realize, but that would require assigning the result of ::insert, asserting on it, and then doing something like (void) inserted; to avoid a warning, so this seemed cleaner and simpler to me.

Having said that, if you feel strongly about doing that rather than calling ::count I'm more than happy to fix it up.

qcolombet added inline comments.Feb 13 2019, 2:27 PM
llvm/lib/CodeGen/RegAllocGreedy.cpp
2626

I don't feel strongly either way.
The only reason I brought it up is because ::count is not free. But given that's in anyway in any critical path plus that's just assert, up to you :).

qcolombet closed this revision.Feb 13 2019, 3:56 PM

Hi!

Nice to see this fix get in because we've seen the need for such a change for our out-of-tree target as well.

However, we've added a FixedRegisters argument to tryAssign and trySplit too.
It was a while since we did that change locally but would it make sense to push that into trunk too?

Hi!

Nice to see this fix get in because we've seen the need for such a change for our out-of-tree target as well.

However, we've added a FixedRegisters argument to tryAssign and trySplit too.
It was a while since we did that change locally but would it make sense to push that into trunk too?

I created a patch for that:
https://reviews.llvm.org/D58376