Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Phabricator shutdown timeline

FastRegAlloc: Fix implicit operands not rewritten

Authored by gbossu on Mar 2 2023, 9:26 AM.



This patch fixes a potential crash due to RegAllocFast not rewriting virtual registers. This essentially happens because of a call to MachineInstr::addRegisterKilled() in the process of allocating a "killed" vreg. The former can eventually delete implicit operands without RegAllocFast noticing, leading to some operands being "skipped" and not rewritten to use physical registers.

Note that I noticed this crash when working on a solution for tying a register with one/multiple of its sub-registers within an instruction. (See problem description here:

Aside from this fix, I believe there could be further improvements to the RegAllocFast when it comes to instructions with multiple uses of a same virtual register. You can see it in the added test where the implicit uses have been re-written in a somewhat surprising way because of phase ordering. Ultimately, when allocating vregs for an instruction, I believe we should iterate on the vregs it uses (and then process all the operands that use this vregs), instead of directly iterating on operands and somewhat assuming each operand uses a different vreg. This would in the end be quite close to what greedy+virtregrewriter does. If that makes sense, I would probably spin off another patch (after I get more familiar with RegAllocFast).

Diff Detail

Event Timeline

gbossu created this revision.Mar 2 2023, 9:26 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 2 2023, 9:26 AM
gbossu requested review of this revision.Mar 2 2023, 9:26 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 2 2023, 9:26 AM
gbossu edited the summary of this revision. (Show Details)Mar 2 2023, 9:27 AM
gbossu added a reviewer: arsenm.
arsenm added a comment.Mar 3 2023, 4:48 AM

Processing all uses of a register at once makes sense to me


Don't you only need to maybe repeat if you saw a kill use?

gbossu added inline comments.Mar 3 2023, 7:51 AM

At the moment, that is right. I just preferred to play it safe because some of the callees inside RegAllocFast::setPhysReg() could potentially mess around with implicit operands further. Although, to this date, I haven't found any other case :) Tbh, it's also not easy to find out whether useVirtReg() has changed any implicit operands, so I preferred to be conservative.

Any additional feedback?

qcolombet added inline comments.Apr 4 2023, 3:39 AM

TL;DR only redo the loop when something changes.

Could we modify useVirtReg to surface whether or not something changed?
It should be possible to surface addRegisterKilled and whatnot that setPhysReg uses.

Bonus point would be to differentiate when we add an operand (actually removing is the issue here) vs. when we just update one, but we can cross that bridge later if compile time is problematic.

I guess we also could be clever and instead of redoing all the iterations of the loop only tweak how the iterator moves (i.e., don't advance if there is a change), but that's probably not worth and may be being too clever for our own good.

gbossu updated this revision to Diff 513553.Apr 14 2023, 5:29 AM

Re-process MachineOperands when kill/dead flags are added. Adding those on implicit operands might re-arrange the whole list of MOs in a MachineInstr.

gbossu added inline comments.Apr 14 2023, 5:38 AM

Sorry it took me some time to get back to this patch. I changed a couple of functions to propagate whether kill/dead flags were added, in which case I assume the list of MOs might have been re-arranged.

I cannot say I'm 100% happy about the change, there are lots of nesting levels in RegAllocFast, and I'm essentially adding a new one. I could move some more logic in separate functions (like I did for findAndSortDefOperandIndexes) to help readability if needed. So far I tried to strike a balance between keeping the code readable and also not refactor too much. Suggestions are welcome for further improvements.

qcolombet accepted this revision.May 5 2023, 7:04 AM
qcolombet added inline comments.

Let's go with that for now

This revision is now accepted and ready to land.May 5 2023, 7:04 AM
gbossu added inline comments.May 8 2023, 3:58 AM

Great, thanks for the review. I believe I still do not have "write" permission. Could you maybe commit on my behalf? Here are my details: Gaëtan Bossu <>.

I'll probably do that beginning of next week.

This revision was automatically updated to reflect the committed changes.