[WebAssembly] Fix getBottom for loops

Authored by aheejin on Jul 29 2020, 1:19 AM.


[WebAssembly] Fix getBottom for loops

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:


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:

end_loop         <-- misplaced!

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.

Reviewed By: dschuff

Differential Revision: https://reviews.llvm.org/D84724


aheejinJul 29 2020, 10:36 AM
Differential Revision
D84724: [WebAssembly] Fix getBottom for loops
rG4add853647b3: [lldb] Improve platform handling in CreateTargetInternal