Page MenuHomePhabricator

[WebAssembly] Run PEI before register allocation.

Authored by sunfish on Apr 20 2016, 5:38 PM.



This patch changes the pass ordering to run PEI *before* register allocation. That's unconventional; normally PEI runs after register allocation to knows how much space to allocate for spills. However, on WebAssembly we're using register coloring rather than allocation, so we never spill anything.

This fixes a tricky case where code at the end of the function is stackified, and then later an epilogue gets inserted into the middle of it, because LLVM doesn't know that it can't insert code there. Similarly, it obviates the need for the tricky code to insert frame index code in the right place.

Another benefit of running it early is that it exposes prologue, epilogue, and frame-index code to register stackifying and coloring. In PR27357 I suggested that perhaps we could run the stackifier twice, however with the patch here we don't need to do that.

The patch here makes the following additional changes to make this work:

  • It introduces a ReplacePhysRegs pass which replaces phys regs like SP32 and FP32 with virtual registers. This is done after PEI, at which point we don't need them as physical registers anymore, and making them virtual registers exposes them to stackification.
  • It makes wasm's PEI code maintain SSA form, because it now runs before SSA lowering. There were a few places where it reused registers; I fixed it to create a new register for each def.
  • It removes the explicit stackifying from prolog/epilog/frame-index expansion code. I know I previously advocated for having that code there, but with the approach in this patch, it's not needed anymore.
  • It eliminates the physreg numbering support, because there are no more phys regs after the ReplacePhysRegs pass.

Diff Detail


Event Timeline

sunfish updated this revision to Diff 54443.Apr 20 2016, 5:38 PM
sunfish retitled this revision from to [WebAssembly] Run PEI before register allocation..
sunfish updated this object.
sunfish set the repository for this revision to rL LLVM.
sunfish added subscribers: dschuff, azakai.
sunfish updated this revision to Diff 54500.Apr 21 2016, 9:31 AM
sunfish updated this object.
sunfish added a reviewer: dschuff.

The main changes from the previous patch are:

  • Do real SSA updating when replacing physical registers with virtual registers.
  • Update all the tests.
  • I added an optimization to fold an add of a frame address with a constant into a single add with a constant.

Also, as an additional benefit to not running the stackifier twice, this patch doesn't require the stackifier to handle previously stackified code.

dschuff edited edge metadata.Apr 21 2016, 9:41 AM

So I haven't looked in detail yet, but I do like the idea in general. It seems like it simplifies quite a few things. Replacing the physregs was surprising to me but I actually like that idea too because it was kind of weird having that distinction before. I do think we will eventually have to do something for MCPhysReg but that's another problem entirely.
We do want to make sure it would work once D18366 lands and we are using the real PEI instead of our own, but I don't know of any reason why it wouldn't.

sunfish updated this revision to Diff 54520.Apr 21 2016, 9:49 AM
sunfish updated this object.
sunfish edited edge metadata.

Upload the correct version of the patch.

sunfish updated this revision to Diff 54566.Apr 21 2016, 1:14 PM

Minor cleanups.

The good news is that this patch doesn't require any changes to WebAssemblyPEI.cpp, so it ought to be independent of that file being refactored away.

The bad news is, means that we don't do our own addPass for the PEI pass anymore, so we can't just move it earlier. One option would be to reintroduce the disablePass to disable the default placement and do our own addPass of the generic PrologEpilogCodeInserterID at the new point in the pass sequence.

Thinking about this issue more, I'm no longer convinced this patch is the right approach. It does seem to make sense to run stackification after PEI, however it seems that what we really want to do is run stackification later, rather than moving PEI earlier. For example, tail duplication exposes opportunities to do more stackificaiton, but it doesn't run (in full strength mode) until after PEI.

The main constraint on stackification is that it wants to run before coloring. So, perhaps we should move both stackification and coloring very late. The main downside of this is that we wouldn't be able to use LiveIntervals (unless we jump through hoops). Stackification doesn't care about full LiveIntervals, but coloring does, so this might require us to come up with our own liveness analysis. That's unfortunate, but it might be better than the alternatives.

sunfish abandoned this revision.May 9 2016, 11:08 AM

I now think is a better approach.