Page MenuHomePhabricator

[WebAssembly] CFG sort support for exception handling
ClosedPublic

Authored by aheejin on May 5 2018, 9:45 PM.

Details

Summary

This patch extends CFGSort pass to support exception handling. Once it
places a loop header, it does not place blocks that are not dominated by
the loop header until all the loop blocks are sorted. This patch extends
the same algorithm to exception 'catch' part, using the information
calculated by WebAssemblyExceptionInfo class.

Diff Detail

Repository
rL LLVM

Event Timeline

aheejin created this revision.May 5 2018, 9:45 PM
aheejin updated this revision to Diff 145395.May 5 2018, 9:48 PM
  • Delete debugging code
aheejin updated this revision to Diff 145611.May 7 2018, 6:22 PM
  • clang-tidy
aheejin updated this revision to Diff 146945.May 15 2018, 3:40 PM

test fixes

aheejin updated this revision to Diff 147701.May 19 2018, 9:54 PM
  • clang-format
aheejin updated this revision to Diff 148128.May 22 2018, 4:25 PM
  • Use unique_ptr for containers and delete destructors
  • Make wasm.get.exception/ehselector intrinsic take a token argument
aheejin planned changes to this revision.Jun 2 2018, 1:32 AM

This change is really quite nice and minimal other than the renaming.

lib/Target/WebAssembly/WebAssemblyCFGSort.cpp
41 ↗(On Diff #151642)

'SortUnit' to me implies that this is a thing that is being sorted, i.e. compared against other units, which isn't correct. What about if we called this a 'Region'?

200 ↗(On Diff #151642)

Even when comparing backwards? I don't quite understand why this shouldn't just be the inverse of forward comparison.

aheejin updated this revision to Diff 154348.Jul 5 2018, 8:52 PM
  • SortUnit -> Region
aheejin updated this revision to Diff 154349.Jul 5 2018, 9:07 PM
  • More unit -> region
aheejin added inline comments.Jul 5 2018, 9:14 PM
lib/Target/WebAssembly/WebAssemblyCFGSort.cpp
200 ↗(On Diff #151642)

For some reason I don't fully understand, for Ready list later BBs are selected first. But my intention here is no matter whether the list is Preferred (which uses CompareBlockNumbers) or Ready (which uses CompareBlockNumbersBackwards), whenever we have an EH pad ready, we want to pick it first.

So CompareBlockNumbersBackwards doesn't mean its results will be used in the reverse direction. Regardless of the comparison function, a BB indicated by the function as having higher priority is placed before when sorting.

dschuff accepted this revision.Jul 9 2018, 9:10 AM
dschuff added inline comments.
lib/Target/WebAssembly/WebAssemblyCFGSort.cpp
200 ↗(On Diff #151642)

OK. This whole bit with the comparison functions still seems a little awkward to me though. At the very least there should be a comment here saying something about the usage or why it's not just the inverse of the above (especially since the name seems to imply that it is). Or maybe it just needs a better name?

Perhaps @sunfish knows why the queues sort in the opposite directions.

Or, stepping back, more, would it make more sense to just have separate queue (alongside Preferred and Ready) for EH pads? Preferred and Ready are basically 2 different priority classes, and we are now adding a third, but we are handling its prioritization differently from the other 2.

85 ↗(On Diff #154349)

We could also assert that ML and WE aren't both set.

This revision is now accepted and ready to land.Jul 9 2018, 9:10 AM
sunfish accepted this revision.Jul 11 2018, 10:06 AM
sunfish added inline comments.
lib/Target/WebAssembly/WebAssemblyCFGSort.cpp
14 ↗(On Diff #151642)

This "and" should be "or".

70 ↗(On Diff #151642)

Could you add a comment for this class that briefly describes its purpose? Do I understand correctly that this is essentially the SortUnit analog of what LoopInfo is for loops?

200 ↗(On Diff #151642)

It was an early attempt at balancing two concerns: preserving the original code layout to the extent possible, while also keeping contiguous sequences contiguous. It worked on some simple testcases. It's probably not optimal.

aheejin updated this revision to Diff 155716.Jul 16 2018, 10:39 AM
aheejin marked 3 inline comments as done.
  • Address comments
  • Add +mattr=exception-handling flag
aheejin added inline comments.Jul 16 2018, 11:32 AM
lib/Target/WebAssembly/WebAssemblyCFGSort.cpp
70 ↗(On Diff #151642)

Yes that's what it is. And I renamed them to Region and RegionInfo per @dschuff's suggestion.

200 ↗(On Diff #151642)

@dschuff Let me clarify a bit. You can think of those two queue as just queue Alpha and queue Beta or something. Here they happen to be CompareBlockNumbersForward and CompareBlockNumbersBackward and they sound like they have some opposite relationship and thus confusing, but they are just different ways to pick a block. What I want is, I want to impose a universal rule of "pick an EH pad first whenever it is available" for all queues available. So why the queues sort in the opposite direction doesn't really matter. And also having a separate queue for EH pads wouldn't do what I want (I want impose a universal rule for all queues, as I said). If we make this as a separate queue, it is unclear how we should modify the logic itself to figure out when we should switch to this specific queue.

For comment-wise, I'm not sure what I should add more to what's already there. Should I add what I described here?

85 ↗(On Diff #154349)

They can be both set. In that case we return the smaller one.

@dschuff I added some more clarification to your questions. PTAL

LGTM With those changes.

lib/Target/WebAssembly/WebAssemblyCFGSort.cpp
200 ↗(On Diff #151642)

Maybe the long comment about EH pad handling could go outside both comparators, and it could note that EH pads are selected first regardless of the block comparison order. I also actually think that changing the name to CompareBlockNumbersAndEHPad doesn't really make them more understandable, and I'd probably just leave the names the same (while keeping the comments).

252 ↗(On Diff #155716)

Could also add one note here like 'EH blocks are picked first from both queues.'

aheejin updated this revision to Diff 159583.Aug 7 2018, 1:15 PM
aheejin marked 2 inline comments as done.

Address comments

This revision was automatically updated to reflect the committed changes.