This is an archive of the discontinued LLVM Phabricator instance.

[Greedy RegAlloc] Fix the handling of split register in last chance re-coloring.
ClosedPublic

Authored by skatkov on Jun 8 2022, 2:57 AM.

Details

Summary

This is a fix for https://github.com/llvm/llvm-project/issues/55827.

When register we are trying to re-color is split the original register (we tried to recover)
has no uses after the split. However in rollback actions we assign back physical register to it.
Later it causes different assertions. One of them is in attached test.

This CL fixes this by avoiding assigning physical register back to register which has no usage
or its live interval now is empty.

There are alternative solution:

  1. Disable split in last chance re-coloring as soon as it always leads to rollback.
  2. Replace register we are re-coloring with registers it was split to.
  3. Move even further, (2) plus try to color split registers again.

This solution was chosen is less intrusive and fixes functional bug.

Diff Detail

Event Timeline

skatkov created this revision.Jun 8 2022, 2:57 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 8 2022, 2:57 AM
skatkov requested review of this revision.Jun 8 2022, 2:57 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 8 2022, 2:57 AM
Herald added a subscriber: wdng. · View Herald Transcript
lkail added a subscriber: lkail.Jun 8 2022, 3:11 AM
arsenm added inline comments.Jun 8 2022, 7:11 AM
llvm/test/CodeGen/AArch64/regalloc-last-chance-recolor-with-split.mir
1

Why still redirect stderr?

3

This should get some actual checks, probably should just use update_mir_test_checks

llvm/test/CodeGen/AMDGPU/remaining-virtual-register-operands.ll
8–11

This is the problem D122616 is trying to solve

arsenm added inline comments.Jun 8 2022, 10:46 AM
llvm/lib/CodeGen/RegAllocGreedy.cpp
1905–1906

The possibility for splitting during last chance recoloring confused me when I was last looking at this here. Is it a problem that the split was also not rolled back as well?

skatkov added inline comments.Jun 8 2022, 9:09 PM
llvm/lib/CodeGen/RegAllocGreedy.cpp
1905–1906

Exactly, the problems comes from the fact that register we are trying to recolor is split in splirOrSelect and split always results in no assignment to physical register, as a result register is not recolored and we should do a roll back.

Current rollback implementation just returns back register we wanted to recolor to original physical register however this register is split and has no uses now.

In an example:
We have register A to try last chance to color.
We take the physical register P and find all registers assigned to P and interfere with live interval of A. Let it be only one register R.
Then we unassign R from P and assign P to A. Fix the register P (do not use it in allocation) and try to recolor R.
As a result of selectOrSplit R is split into R1, R2, R3. R has no uses in machine instructions now, its uses are replaced with R1, R2, R3 and corresponding copy instructions are inserted to connect R1, R2, R3.
selectOrSplit always returns no assignment and R1, R2, R3 as new registers to be added again into queue and process them further on regular basis.
As soon as we are in last chance color, we get no assignment of R to physical register and states this as a failure of recoloring.
So we do a rollback. In this rollback we just return back an assignment of R to P. But R has no uses now and it leads to different assertions later when handling such registers (without uses but with assignment to physical registers).

This is a description of the problem.

Now how to solve this in rollback:

  1. This patch just avoid assignment of P to R due to R has no uses. R1, R2, R3 will go to the queue finally and will processed on next iterations (it is actually change you did recently).
  2. We can try to assign R1, R2, R3 to P. It has more complexity in implementation due to no easy way to detect that R is actually split into R1, R2, R3. So we need some preparation work.
  3. We can reject split in selectOrSplit while we are doing last chance recoloring.
  4. We can do even smarter: If we detect split R to R1, R2, R3 we can try to continue recolor R1, R2, R3 or only those Ri which still interfere with A.

May be there are other solutions. But just for bug fix I choose the less intrusive way. I hope it helps and not confuse :)

llvm/test/CodeGen/AArch64/regalloc-last-chance-recolor-with-split.mir
1

Yeah! No need for this more.

3

ok, I'll do it but the main idea here was that this does not crash anymore.

llvm/test/CodeGen/AMDGPU/remaining-virtual-register-operands.ll
8–11

Thanks for pointing me to.

skatkov updated this revision to Diff 435431.Jun 8 2022, 11:10 PM

Handled comments about tests.

To be honest update mir is overkill here. I've also needed to fix some places due to update mir does inaccurate mapping.
I would prefer just check that there is not crash actually.

arsenm added inline comments.Jun 9 2022, 6:21 PM
llvm/lib/CodeGen/RegAllocGreedy.cpp
1905–1906

Why are both checks necessary? Why isn't LI->empty sufficient?

llvm/test/CodeGen/AArch64/regalloc-last-chance-recolor-with-split.mir
2

Probably should also run virtregrewriter

skatkov added inline comments.Jun 9 2022, 8:26 PM
llvm/lib/CodeGen/RegAllocGreedy.cpp
1905–1906

Because after the split, the live interval of original virtual register does not become empty. It just remains as is.

skatkov updated this revision to Diff 435789.Jun 9 2022, 8:53 PM
arsenm accepted this revision.Jun 10 2022, 7:50 AM
arsenm added inline comments.
llvm/test/CodeGen/AArch64/regalloc-last-chance-recolor-with-split.mir
10–31

Can you drop this large IR section?

This revision is now accepted and ready to land.Jun 10 2022, 7:50 AM
qcolombet added inline comments.Jun 10 2022, 9:47 AM
llvm/lib/CodeGen/RegAllocGreedy.cpp
1905–1906

The fact that last chance recoloring allows splitting is by design.
For split regs, we should leave them unassigned when the recoloring fails.

qcolombet accepted this revision.Jun 10 2022, 9:48 AM
skatkov updated this revision to Diff 436642.Jun 13 2022, 9:49 PM

Update test before landing.

This revision was landed with ongoing or failed builds.Jun 13 2022, 10:05 PM
This revision was automatically updated to reflect the committed changes.

Awesome!

We've seen several different crashes related to splitting happening during tryLastChanceRecoloring for our out-of-tree target over the years, and I could close all such open downstream TRs now due to this patch.
Thanks @skatkov !

Awesome!

We've seen several different crashes related to splitting happening during tryLastChanceRecoloring for our out-of-tree target over the years, and I could close all such open downstream TRs now due to this patch.
Thanks @skatkov !

Nice to hear!

llvm/test/CodeGen/AArch64/regalloc-last-chance-recolor-with-split.mir
2

It helped.