This is an archive of the discontinued LLVM Phabricator instance.

[WebAssembly] Fix more ExceptionInfo grouping bugs
ClosedPublic

Authored by aheejin on Mar 1 2021, 3:56 AM.

Details

Summary

This fixes two bugs in WebAssemblyExceptionInfo grouping, created by
D97247. These two bugs are not easy to split into two different CLs,
because tests that fail for one also tend to fail for the other.

  • In D97247, when fixing ExceptionInfo grouping by taking out the unwind destination' exception from the unwind src's exception, we just iterated the BBs in the function order, but this was incorrect; this changes it to dominator tree preorder. Please refer to the comments in the code for the reason and an example.
  • After this subexception-taking-out fix, there still can be remaining BBs we have to take out. When Exception B is taken out of Exception A (because EHPad B is the unwind destination of EHPad A), there can still be BBs within Exception A that are reachable from Exception B, which also should be taken out. Please refer to the comments in the code for more detailed explanation on why this can happen. To make this possible, this splits WebAssemblyException::addBlock into two parts: adding to a set and adding to a vector. We need to iterate on BBs within a WebAssemblyException to fix this, so we add BBs to sets first. But we add BBs to vectors later after we fix all incorrectness because deleting BBs from vectors is expensive. I considered removing the vector from WebAssemblyException, but it was not easy because this class has to maintain a similar interface with MachineLoop to be wrapped into a single interface SortRegion, which is used in CFGSort.

Other misc. drive-by fixes:

  • Make WebAssemblyExceptionInfo do not even run when wasm EH is not used or the function doesn't have any EH pads, not to waste time
  • Add LLVM_DEBUG lines for easy debugging
  • Fix preds comments in cfg-stackify-eh.ll
  • Fix __cxa_throw's signature in cfg-stackify-eh.ll

Fixes https://github.com/emscripten-core/emscripten/issues/13554.

Diff Detail

Event Timeline

aheejin created this revision.Mar 1 2021, 3:56 AM
aheejin requested review of this revision.Mar 1 2021, 3:56 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 1 2021, 3:56 AM
aheejin edited the summary of this revision. (Show Details)Mar 1 2021, 3:57 AM
aheejin edited the summary of this revision. (Show Details)Mar 1 2021, 9:50 AM
aheejin edited the summary of this revision. (Show Details)
aheejin updated this revision to Diff 327159.Mar 1 2021, 9:54 AM

clang-tidy fix

tlively added inline comments.Mar 1 2021, 12:37 PM
llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.cpp
163
167
207

I expected to see code copying the contents of the block set to the block vector, but I don't see that. Do the set and the vector have different contents, or am I missing something else?

llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.h
48

If we expect there to be few blocks, then perhaps the cost of deleting them from the vector wouldn't be too bad? Alternatively, we could also "remove" blocks by replacing them in the vector with nullptr, then compact the vector and remove the nullptrs just once at the end. That might be more complicated then just adding this set, though.

aheejin updated this revision to Diff 327276.Mar 1 2021, 1:46 PM
aheejin marked 2 inline comments as done.

Address comments

llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.cpp
207

We can do it that way. We are just using a map from BB to exception (look at getExceptionFor below, in line 210) to do that now.

So previously the code was

for (auto DomNode : post_order(&MDT)) {
  MachineBasicBlock *MBB = DomNode->getBlock();
  WebAssemblyException *WE = getExceptionFor(MBB);
  for (; WE; WE = WE->getParentException())
    WE->addBlock(MBB);
}

And addBlock was doing this:

Blocks.push_back(MBB);
BlockSet.insert(MBB);

Now we are doing the same thing in two steps.

for (auto DomNode : post_order(&MDT)) {
  MachineBasicBlock *MBB = DomNode->getBlock();
  WebAssemblyException *WE = getExceptionFor(MBB);
  for (; WE; WE = WE->getParentException())
    WE->addToBlockSet(MBB);
}

...
... Fix incorrect mappings ...
...

for (auto DomNode : post_order(&MDT)) {
  MachineBasicBlock *MBB = DomNode->getBlock();
  WebAssemblyException *WE = getExceptionFor(MBB);
  for (; WE; WE = WE->getParentException())
    WE->addToBlockVector(MBB);
}
llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.h
48

The number of blocks varies greatly. There are many exceptions with fewer than 8 BBs so I set it to 8, but it does not mean I think that will be the median. There are functions dozens of BBs are within the catch part, and removing a block from those vectors will be expensive. Also when we remove a BB from, say, Exception A, it can involve multiple removal, because the BB's innermost containing exception might not be Exception A. If Exception A > B > C and BB belongs to C and we want to remove BB from Exception A, we have to remove BB form all A, B, and C's vectors.

Yes, I think removing things by setting them to nullptr and compressing the vector later is OK too. I just think the set is more convenient for now.. MachineLoop also keeps both a set and vector, even though it doesn't mean we should do the same. (I couldn't remove the vector because SortRegion was expecting some unified interface on it, but I think we can remove the set without affecting SortRegion, but yeah, it's just convenient to keep it..)

I also thought about removing the vector and using sets only within SortRegion but it was tricky due to some constness difference; MachineLoop's vector contains MachineBasicBlock* but its set contains const MachineBasicBlock*...

tlively accepted this revision.Mar 1 2021, 2:04 PM
tlively added inline comments.
llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.cpp
207

I see, thanks. Either way is fine with me.

llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.h
48

I agree that using a set seems reasonable, especially given the precedent in MachineBasicBlock. Thanks for the info!

This revision is now accepted and ready to land.Mar 1 2021, 2:04 PM
dschuff accepted this revision.Mar 1 2021, 2:41 PM
This revision was automatically updated to reflect the committed changes.