This is an archive of the discontinued LLVM Phabricator instance.

[WebAssembly] Fix getBottom for loops
ClosedPublic

Authored by aheejin on Jul 27 2020, 9:58 PM.

Details

Summary

When it was first created, CFGSort only made sure BBs in each
MachineLoop are sorted together. After we added exception support,
CFGSort now also sorts BBs in each WebAssemblyException, which
represents a catch block, together, and
Region class was introduced to be a thin wrapper for both
MachineLoop and WebAssemblyException.

But how we compute those loops and exceptions is different.
MachineLoopInfo is constructed using the standard loop computation
algorithm in LLVM; the definition of loop is "a set of BBs that are
dominated by a loop header and have a path back to the loop header". So
even if some BBs are semantically contained by a loop in the original
program, or in other words dominated by a loop header, if they don't
have a path back to the loop header, they are not considered a part of
the loop. For example, if a BB is dominated by a loop header but
contains call abort() or rethrow, it wouldn't have a path back to
the header, so it is not included in the loop.

But WebAssemblyException is wasm-specific data structure, and its
algorithm is simple: a WebAssemblyException consists of an EH pad and
all BBs dominated by the EH pad. So this scenario is possible: (This is
also the situation in the newly added test in cfg-stackify-eh.ll)

Loop L: header, A, ehpad, latch
Exception E: ehpad, latch, B

(B contains abort(), so it does not have a path back to the loop
header, so it is not included in L.)

And it is sorted in this order:

header
A
ehpad
latch
B

And when CFGStackify places end_loop or end_try markers, it
previously used WebAssembly::getBottom(), which returns the latest BB
in the sorted order, and placed the marker there. So in this case the
marker placements will be like this:

loop
  header
  try
    A
  catch
    ehpad
    latch
end_loop         <-- misplaced!
    B
  end_try

in which nesting between the loop and the exception is not correct.
end_loop marker has to be placed after B, and also after end_try.

Maybe the fundamental way to solve this problem is to come up with our
own algorithm for computing loop region too, in which we include all BBs
dominated by a loop header in a loop. But this takes a lot more effort.
The only thing we need to fix is actually, getBottom(). If we make it
return the right BB, which means in case of a loop, the latest BB of the
loop itself and all exceptions contained in there, we are good.

This renames Region and RegionInfo to SortRegion and
SortRegionInfo and extracts them into their own file. And add
getBottom to SortRegionInfo class, from which it can access
WebAssemblyExceptionInfo, so that it can compute a correct bottom
block for loops.

Diff Detail

Event Timeline

aheejin created this revision.Jul 27 2020, 9:58 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 27 2020, 9:58 PM
aheejin edited the summary of this revision. (Show Details)Jul 27 2020, 9:59 PM
aheejin edited the summary of this revision. (Show Details)
aheejin added inline comments.Jul 27 2020, 10:05 PM
llvm/lib/Target/WebAssembly/WebAssemblySortRegion.cpp
48–66

Most of WebAssemblySortRegion.h and cpp was preexisting and only moved, except for this method.

Harbormaster returned this revision to the author for changes because remote builds failed.Jul 27 2020, 10:27 PM
Harbormaster failed remote builds in B65956: Diff 281110!
This comment was removed by aheejin.
aheejin requested review of this revision.Jul 27 2020, 10:43 PM
aheejin edited the summary of this revision. (Show Details)Jul 27 2020, 10:51 PM
aheejin edited the summary of this revision. (Show Details)
dschuff accepted this revision.Jul 28 2020, 11:05 AM

LGTM!

This revision is now accepted and ready to land.Jul 28 2020, 11:05 AM
This revision was landed with ongoing or failed builds.Jul 29 2020, 10:36 AM
This revision was automatically updated to reflect the committed changes.