llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.cpp - llvm-project - Git at Google

 //===--- WebAssemblyExceptionInfo.cpp - Exception Infomation --------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// \brief This file implements WebAssemblyException information analysis.
 ///
 //===----------------------------------------------------------------------===//

 #include "WebAssemblyExceptionInfo.h"
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "Utils/WebAssemblyUtilities.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/CodeGen/MachineDominanceFrontier.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/WasmEHFuncInfo.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/Target/TargetMachine.h"

 using namespace llvm;

 #define DEBUG_TYPE "wasm-exception-info"

 char WebAssemblyExceptionInfo::ID = 0;

 INITIALIZE_PASS_BEGIN(WebAssemblyExceptionInfo, DEBUG_TYPE,
                       "WebAssembly Exception Information", true, true)
 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
 INITIALIZE_PASS_END(WebAssemblyExceptionInfo, DEBUG_TYPE,
                     "WebAssembly Exception Information", true, true)

 bool WebAssemblyExceptionInfo::runOnMachineFunction(MachineFunction &MF) {
   LLVM_DEBUG(dbgs() << "********** Exception Info Calculation **********\n"
                        "********** Function: "
                     << MF.getName() << '\n');
   releaseMemory();
   if (MF.getTarget().getMCAsmInfo()->getExceptionHandlingType() !=
           ExceptionHandling::Wasm ||
       !MF.getFunction().hasPersonalityFn())
     return false;
   auto &MDT = getAnalysis<MachineDominatorTree>();
   auto &MDF = getAnalysis<MachineDominanceFrontier>();
   recalculate(MF, MDT, MDF);
   LLVM_DEBUG(dump());
   return false;
 }

 // Check if Dst is reachable from Src using BFS. Search only within BBs
 // dominated by Header.
 static bool isReachableAmongDominated(const MachineBasicBlock *Src,
                                       const MachineBasicBlock *Dst,
                                       const MachineBasicBlock *Header,
                                       const MachineDominatorTree &MDT) {
   assert(MDT.dominates(Header, Dst));
   SmallVector<const MachineBasicBlock *, 8> WL;
   SmallPtrSet<const MachineBasicBlock *, 8> Visited;
   WL.push_back(Src);

   while (!WL.empty()) {
     const auto *MBB = WL.pop_back_val();
     if (MBB == Dst)
       return true;
     Visited.insert(MBB);
     for (auto *Succ : MBB->successors())
       if (!Visited.count(Succ) && MDT.dominates(Header, Succ))
         WL.push_back(Succ);
   }
   return false;
 }

 void WebAssemblyExceptionInfo::recalculate(
     MachineFunction &MF, MachineDominatorTree &MDT,
     const MachineDominanceFrontier &MDF) {
   // Postorder traversal of the dominator tree.
   SmallVector<std::unique_ptr<WebAssemblyException>, 8> Exceptions;
   for (auto DomNode : post_order(&MDT)) {
     MachineBasicBlock *EHPad = DomNode->getBlock();
     if (!EHPad->isEHPad())
       continue;
     auto WE = std::make_unique<WebAssemblyException>(EHPad);
     discoverAndMapException(WE.get(), MDT, MDF);
     Exceptions.push_back(std::move(WE));
   }

   // WasmEHFuncInfo contains a map of <catchpad, its next unwind destination>,
   // which means, if an exception is not caught by the catchpad, it should end
   // up in the next unwind destination stored in this data structure. (It is
   // written as catchswitch's 'unwind' destination in ll files.) The below is an
   // intuitive example of their relationship in C++ code:
   // try {
   //   try {
   //   } catch (int) { // catchpad
   //      ...          // this catch (int) { ... } is grouped as an exception
   //   }
   // } catch (...) {   // next unwind destination
   // }
   // (The example is try-catches for illustration purpose, but the unwind
   // destination can be also a cleanuppad generated by destructor calls.) So the
   // unwind destination is in the outside of the catchpad's exception.
   //
   // We group exceptions in this analysis simply by including all BBs dominated
   // by an EH pad. But in case the EH pad's unwind destination does not have any
   // children outside of the exception, that unwind destination ends up also
   // being dominated by the EH pad and included in the exception, which is not
   // semantically correct, because it unwinds/rethrows into an inner scope.
   //
   // Here we extract those unwind destinations from their (incorrect) parent
   // exception. Note that the unwind destinations may not be an immediate
   // children of the parent exception, so we have to traverse the parent chain.
   //
   // We should traverse BBs in the preorder of the dominator tree, because
   // otherwise the result can be incorrect. For example, when there are three
   // exceptions A, B, and C and A > B > C (> is subexception relationship here),
   // and A's unwind destination is B and B's is C. When we visit B before A, we
   // end up extracting C only out of B but not out of A.
   const auto *EHInfo = MF.getWasmEHFuncInfo();
   SmallVector<std::pair<WebAssemblyException *, WebAssemblyException *>>
       UnwindWEVec;
   for (auto *DomNode : depth_first(&MDT)) {
     MachineBasicBlock *EHPad = DomNode->getBlock();
     if (!EHPad->isEHPad())
       continue;
     if (!EHInfo->hasUnwindDest(EHPad))
       continue;
     auto *UnwindDest = EHInfo->getUnwindDest(EHPad);
     auto *SrcWE = getExceptionFor(EHPad);
     auto *DstWE = getExceptionFor(UnwindDest);
     if (SrcWE->contains(DstWE)) {
       UnwindWEVec.push_back(std::make_pair(SrcWE, DstWE));
       LLVM_DEBUG(dbgs() << "Unwind destination ExceptionInfo fix:\n  "
                         << DstWE->getEHPad()->getNumber() << "."
                         << DstWE->getEHPad()->getName()
                         << "'s exception is taken out of "
                         << SrcWE->getEHPad()->getNumber() << "."
                         << SrcWE->getEHPad()->getName() << "'s exception\n");
       DstWE->setParentException(SrcWE->getParentException());
     }
   }

   // After fixing subexception relationship between unwind destinations above,
   // there can still be remaining discrepancies.
   //
   // For example, suppose Exception A is dominated by EHPad A and Exception B is
   // dominated by EHPad B. EHPad A's unwind destination is EHPad B, but because
   // EHPad B is dominated by EHPad A, the initial grouping makes Exception B a
   // subexception of Exception A, and we fix it by taking Exception B out of
   // Exception A above. But there can still be remaining BBs within Exception A
   // that are reachable from Exception B. These BBs semantically don't belong
   // to Exception A and were not a part of this 'catch' clause or cleanup code
   // in the original code, but they just happened to be grouped within Exception
   // A because they were dominated by EHPad A. We fix this case by taking those
   // BBs out of the incorrect exception and all its subexceptions that it
   // belongs to.
   //
   // 1. First, we take out remaining incorrect subexceptions. This part is
   // easier, because we haven't added BBs to exceptions yet, we only need to
   // change parent exception pointer.
   for (auto *DomNode : depth_first(&MDT)) {
     MachineBasicBlock *EHPad = DomNode->getBlock();
     if (!EHPad->isEHPad())
       continue;
     auto *WE = getExceptionFor(EHPad);

     // For each source EHPad -> unwind destination EHPad
     for (auto &P : UnwindWEVec) {
       auto *SrcWE = P.first;
       auto *DstWE = P.second;
       // If WE (the current EH pad's exception) is still contained in SrcWE but
       // reachable from DstWE that was taken out of SrcWE above, we have to take
       // out WE out of SrcWE too.
       if (WE != SrcWE && SrcWE->contains(WE) && !DstWE->contains(WE) &&
           isReachableAmongDominated(DstWE->getEHPad(), EHPad, SrcWE->getEHPad(),
                                     MDT)) {
         LLVM_DEBUG(dbgs() << "Remaining reachable ExceptionInfo fix:\n  "
                           << WE->getEHPad()->getNumber() << "."
                           << WE->getEHPad()->getName()
                           << "'s exception is taken out of "
                           << SrcWE->getEHPad()->getNumber() << "."
                           << SrcWE->getEHPad()->getName() << "'s exception\n");
         WE->setParentException(SrcWE->getParentException());
       }
     }
   }

   // Add BBs to exceptions' block set. This is a preparation to take out
   // remaining incorect BBs from exceptions, because we need to iterate over BBs
   // for each exception.
   for (auto *DomNode : post_order(&MDT)) {
     MachineBasicBlock *MBB = DomNode->getBlock();
     WebAssemblyException *WE = getExceptionFor(MBB);
     for (; WE; WE = WE->getParentException())
       WE->addToBlocksSet(MBB);
   }

   // 2. We take out remaining individual BBs out. Now we have added BBs to each
   // exceptions' BlockSet, when we take a BB out of an exception, we need to fix
   // those sets too.
   for (auto &P : UnwindWEVec) {
     auto *SrcWE = P.first;
     auto *DstWE = P.second;

     for (auto *MBB : SrcWE->getBlocksSet()) {
       if (MBB->isEHPad()) {
         assert(!isReachableAmongDominated(DstWE->getEHPad(), MBB,
                                           SrcWE->getEHPad(), MDT) &&
                "We already handled EH pads above");
         continue;
       }
       if (isReachableAmongDominated(DstWE->getEHPad(), MBB, SrcWE->getEHPad(),
                                     MDT)) {
         LLVM_DEBUG(dbgs() << "Remainder BB: " << MBB->getNumber() << "."
                           << MBB->getName() << " is\n");
         WebAssemblyException *InnerWE = getExceptionFor(MBB);
         while (InnerWE != SrcWE) {
           LLVM_DEBUG(dbgs()
                      << "  removed from " << InnerWE->getEHPad()->getNumber()
                      << "." << InnerWE->getEHPad()->getName()
                      << "'s exception\n");
           InnerWE->removeFromBlocksSet(MBB);
           InnerWE = InnerWE->getParentException();
         }
         SrcWE->removeFromBlocksSet(MBB);
         LLVM_DEBUG(dbgs() << "  removed from " << SrcWE->getEHPad()->getNumber()
                           << "." << SrcWE->getEHPad()->getName()
                           << "'s exception\n");
         changeExceptionFor(MBB, SrcWE->getParentException());
         if (SrcWE->getParentException())
           SrcWE->getParentException()->addToBlocksSet(MBB);
       }
     }
   }

   // Add BBs to exceptions' block vector
   for (auto DomNode : post_order(&MDT)) {
     MachineBasicBlock *MBB = DomNode->getBlock();
     WebAssemblyException *WE = getExceptionFor(MBB);
     for (; WE; WE = WE->getParentException())
       WE->addToBlocksVector(MBB);
   }

   SmallVector<WebAssemblyException*, 8> ExceptionPointers;
   ExceptionPointers.reserve(Exceptions.size());

   // Add subexceptions to exceptions
   for (auto &WE : Exceptions) {
     ExceptionPointers.push_back(WE.get());
     if (WE->getParentException())
       WE->getParentException()->getSubExceptions().push_back(std::move(WE));
     else
       addTopLevelException(std::move(WE));
   }

   // For convenience, Blocks and SubExceptions are inserted in postorder.
   // Reverse the lists.
   for (auto *WE : ExceptionPointers) {
     WE->reverseBlock();
     std::reverse(WE->getSubExceptions().begin(), WE->getSubExceptions().end());
   }
 }

 void WebAssemblyExceptionInfo::releaseMemory() {
   BBMap.clear();
   TopLevelExceptions.clear();
 }

 void WebAssemblyExceptionInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequired<MachineDominatorTree>();
   AU.addRequired<MachineDominanceFrontier>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }

 void WebAssemblyExceptionInfo::discoverAndMapException(
     WebAssemblyException *WE, const MachineDominatorTree &MDT,
     const MachineDominanceFrontier &MDF) {
   unsigned NumBlocks = 0;
   unsigned NumSubExceptions = 0;

   // Map blocks that belong to a catchpad / cleanuppad
   MachineBasicBlock *EHPad = WE->getEHPad();
   SmallVector<MachineBasicBlock *, 8> WL;
   WL.push_back(EHPad);
   while (!WL.empty()) {
     MachineBasicBlock *MBB = WL.pop_back_val();

     // Find its outermost discovered exception. If this is a discovered block,
     // check if it is already discovered to be a subexception of this exception.
     WebAssemblyException *SubE = getOutermostException(MBB);
     if (SubE) {
       if (SubE != WE) {
         // Discover a subexception of this exception.
         SubE->setParentException(WE);
         ++NumSubExceptions;
         NumBlocks += SubE->getBlocksVector().capacity();
         // All blocks that belong to this subexception have been already
         // discovered. Skip all of them. Add the subexception's landing pad's
         // dominance frontier to the worklist.
         for (auto &Frontier : MDF.find(SubE->getEHPad())->second)
           if (MDT.dominates(EHPad, Frontier))
             WL.push_back(Frontier);
       }
       continue;
     }

     // This is an undiscovered block. Map it to the current exception.
     changeExceptionFor(MBB, WE);
     ++NumBlocks;

     // Add successors dominated by the current BB to the worklist.
     for (auto *Succ : MBB->successors())
       if (MDT.dominates(EHPad, Succ))
         WL.push_back(Succ);
   }

   WE->getSubExceptions().reserve(NumSubExceptions);
   WE->reserveBlocks(NumBlocks);
 }

 WebAssemblyException *
 WebAssemblyExceptionInfo::getOutermostException(MachineBasicBlock *MBB) const {
   WebAssemblyException *WE = getExceptionFor(MBB);
   if (WE) {
     while (WebAssemblyException *Parent = WE->getParentException())
       WE = Parent;
   }
   return WE;
 }

 void WebAssemblyException::print(raw_ostream &OS, unsigned Depth) const {
   OS.indent(Depth * 2) << "Exception at depth " << getExceptionDepth()
                        << " containing: ";

   for (unsigned I = 0; I < getBlocks().size(); ++I) {
     MachineBasicBlock *MBB = getBlocks()[I];
     if (I)
       OS << ", ";
     OS << "%bb." << MBB->getNumber();
     if (const auto *BB = MBB->getBasicBlock())
       if (BB->hasName())
         OS << "." << BB->getName();

     if (getEHPad() == MBB)
       OS << " (landing-pad)";
   }
   OS << "\n";

   for (auto &SubE : SubExceptions)
     SubE->print(OS, Depth + 2);
 }

 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void WebAssemblyException::dump() const { print(dbgs()); }
 #endif

 raw_ostream &operator<<(raw_ostream &OS, const WebAssemblyException &WE) {
   WE.print(OS);
   return OS;
 }

 void WebAssemblyExceptionInfo::print(raw_ostream &OS, const Module *) const {
   for (auto &WE : TopLevelExceptions)
     WE->print(OS);
 }
	//===--- WebAssemblyExceptionInfo.cpp - Exception Infomation --------------===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//
	///
	/// \file
	/// \brief This file implements WebAssemblyException information analysis.
	///
	//===----------------------------------------------------------------------===//

	#include "WebAssemblyExceptionInfo.h"
	#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
	#include "Utils/WebAssemblyUtilities.h"
	#include "llvm/ADT/PostOrderIterator.h"
	#include "llvm/CodeGen/MachineDominanceFrontier.h"
	#include "llvm/CodeGen/MachineDominators.h"
	#include "llvm/CodeGen/WasmEHFuncInfo.h"
	#include "llvm/InitializePasses.h"
	#include "llvm/MC/MCAsmInfo.h"
	#include "llvm/Target/TargetMachine.h"

	using namespace llvm;

	#define DEBUG_TYPE "wasm-exception-info"

	char WebAssemblyExceptionInfo::ID = 0;

	INITIALIZE_PASS_BEGIN(WebAssemblyExceptionInfo, DEBUG_TYPE,
	"WebAssembly Exception Information", true, true)
	INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
	INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
	INITIALIZE_PASS_END(WebAssemblyExceptionInfo, DEBUG_TYPE,
	"WebAssembly Exception Information", true, true)

	bool WebAssemblyExceptionInfo::runOnMachineFunction(MachineFunction &MF) {
	LLVM_DEBUG(dbgs() << "******** Exception Info Calculation ********\n"
	"********** Function: "
	<< MF.getName() << '\n');
	releaseMemory();
	if (MF.getTarget().getMCAsmInfo()->getExceptionHandlingType() !=
	ExceptionHandling::Wasm \|\|
	!MF.getFunction().hasPersonalityFn())
	return false;
	auto &MDT = getAnalysis<MachineDominatorTree>();
	auto &MDF = getAnalysis<MachineDominanceFrontier>();
	recalculate(MF, MDT, MDF);
	LLVM_DEBUG(dump());
	return false;
	}

	// Check if Dst is reachable from Src using BFS. Search only within BBs
	// dominated by Header.
	static bool isReachableAmongDominated(const MachineBasicBlock *Src,
	const MachineBasicBlock *Dst,
	const MachineBasicBlock *Header,
	const MachineDominatorTree &MDT) {
	assert(MDT.dominates(Header, Dst));
	SmallVector<const MachineBasicBlock *, 8> WL;
	SmallPtrSet<const MachineBasicBlock *, 8> Visited;
	WL.push_back(Src);

	while (!WL.empty()) {
	const auto *MBB = WL.pop_back_val();
	if (MBB == Dst)
	return true;
	Visited.insert(MBB);
	for (auto *Succ : MBB->successors())
	if (!Visited.count(Succ) && MDT.dominates(Header, Succ))
	WL.push_back(Succ);
	}
	return false;
	}

	void WebAssemblyExceptionInfo::recalculate(
	MachineFunction &MF, MachineDominatorTree &MDT,
	const MachineDominanceFrontier &MDF) {
	// Postorder traversal of the dominator tree.
	SmallVector<std::unique_ptr<WebAssemblyException>, 8> Exceptions;
	for (auto DomNode : post_order(&MDT)) {
	MachineBasicBlock *EHPad = DomNode->getBlock();
	if (!EHPad->isEHPad())
	continue;
	auto WE = std::make_unique<WebAssemblyException>(EHPad);
	discoverAndMapException(WE.get(), MDT, MDF);
	Exceptions.push_back(std::move(WE));
	}

	// WasmEHFuncInfo contains a map of <catchpad, its next unwind destination>,
	// which means, if an exception is not caught by the catchpad, it should end
	// up in the next unwind destination stored in this data structure. (It is
	// written as catchswitch's 'unwind' destination in ll files.) The below is an
	// intuitive example of their relationship in C++ code:
	// try {
	// try {
	// } catch (int) { // catchpad
	// ... // this catch (int) { ... } is grouped as an exception
	// }
	// } catch (...) { // next unwind destination
	// }
	// (The example is try-catches for illustration purpose, but the unwind
	// destination can be also a cleanuppad generated by destructor calls.) So the
	// unwind destination is in the outside of the catchpad's exception.
	//
	// We group exceptions in this analysis simply by including all BBs dominated
	// by an EH pad. But in case the EH pad's unwind destination does not have any
	// children outside of the exception, that unwind destination ends up also
	// being dominated by the EH pad and included in the exception, which is not
	// semantically correct, because it unwinds/rethrows into an inner scope.
	//
	// Here we extract those unwind destinations from their (incorrect) parent
	// exception. Note that the unwind destinations may not be an immediate
	// children of the parent exception, so we have to traverse the parent chain.
	//
	// We should traverse BBs in the preorder of the dominator tree, because
	// otherwise the result can be incorrect. For example, when there are three
	// exceptions A, B, and C and A > B > C (> is subexception relationship here),
	// and A's unwind destination is B and B's is C. When we visit B before A, we
	// end up extracting C only out of B but not out of A.
	const auto *EHInfo = MF.getWasmEHFuncInfo();
	SmallVector<std::pair<WebAssemblyException , WebAssemblyException >>
	UnwindWEVec;
	for (auto *DomNode : depth_first(&MDT)) {
	MachineBasicBlock *EHPad = DomNode->getBlock();
	if (!EHPad->isEHPad())
	continue;
	if (!EHInfo->hasUnwindDest(EHPad))
	continue;
	auto *UnwindDest = EHInfo->getUnwindDest(EHPad);
	auto *SrcWE = getExceptionFor(EHPad);
	auto *DstWE = getExceptionFor(UnwindDest);
	if (SrcWE->contains(DstWE)) {
	UnwindWEVec.push_back(std::make_pair(SrcWE, DstWE));
	LLVM_DEBUG(dbgs() << "Unwind destination ExceptionInfo fix:\n "
	<< DstWE->getEHPad()->getNumber() << "."
	<< DstWE->getEHPad()->getName()
	<< "'s exception is taken out of "
	<< SrcWE->getEHPad()->getNumber() << "."
	<< SrcWE->getEHPad()->getName() << "'s exception\n");
	DstWE->setParentException(SrcWE->getParentException());
	}
	}

	// After fixing subexception relationship between unwind destinations above,
	// there can still be remaining discrepancies.
	//
	// For example, suppose Exception A is dominated by EHPad A and Exception B is
	// dominated by EHPad B. EHPad A's unwind destination is EHPad B, but because
	// EHPad B is dominated by EHPad A, the initial grouping makes Exception B a
	// subexception of Exception A, and we fix it by taking Exception B out of
	// Exception A above. But there can still be remaining BBs within Exception A
	// that are reachable from Exception B. These BBs semantically don't belong
	// to Exception A and were not a part of this 'catch' clause or cleanup code
	// in the original code, but they just happened to be grouped within Exception
	// A because they were dominated by EHPad A. We fix this case by taking those
	// BBs out of the incorrect exception and all its subexceptions that it
	// belongs to.
	//
	// 1. First, we take out remaining incorrect subexceptions. This part is
	// easier, because we haven't added BBs to exceptions yet, we only need to
	// change parent exception pointer.
	for (auto *DomNode : depth_first(&MDT)) {
	MachineBasicBlock *EHPad = DomNode->getBlock();
	if (!EHPad->isEHPad())
	continue;
	auto *WE = getExceptionFor(EHPad);

	// For each source EHPad -> unwind destination EHPad
	for (auto &P : UnwindWEVec) {
	auto *SrcWE = P.first;
	auto *DstWE = P.second;
	// If WE (the current EH pad's exception) is still contained in SrcWE but
	// reachable from DstWE that was taken out of SrcWE above, we have to take
	// out WE out of SrcWE too.
	if (WE != SrcWE && SrcWE->contains(WE) && !DstWE->contains(WE) &&
	isReachableAmongDominated(DstWE->getEHPad(), EHPad, SrcWE->getEHPad(),
	MDT)) {
	LLVM_DEBUG(dbgs() << "Remaining reachable ExceptionInfo fix:\n "
	<< WE->getEHPad()->getNumber() << "."
	<< WE->getEHPad()->getName()
	<< "'s exception is taken out of "
	<< SrcWE->getEHPad()->getNumber() << "."
	<< SrcWE->getEHPad()->getName() << "'s exception\n");
	WE->setParentException(SrcWE->getParentException());
	}
	}
	}

	// Add BBs to exceptions' block set. This is a preparation to take out
	// remaining incorect BBs from exceptions, because we need to iterate over BBs
	// for each exception.
	for (auto *DomNode : post_order(&MDT)) {
	MachineBasicBlock *MBB = DomNode->getBlock();
	WebAssemblyException *WE = getExceptionFor(MBB);
	for (; WE; WE = WE->getParentException())
	WE->addToBlocksSet(MBB);
	}

	// 2. We take out remaining individual BBs out. Now we have added BBs to each
	// exceptions' BlockSet, when we take a BB out of an exception, we need to fix
	// those sets too.
	for (auto &P : UnwindWEVec) {
	auto *SrcWE = P.first;
	auto *DstWE = P.second;

	for (auto *MBB : SrcWE->getBlocksSet()) {
	if (MBB->isEHPad()) {
	assert(!isReachableAmongDominated(DstWE->getEHPad(), MBB,
	SrcWE->getEHPad(), MDT) &&
	"We already handled EH pads above");
	continue;
	}
	if (isReachableAmongDominated(DstWE->getEHPad(), MBB, SrcWE->getEHPad(),
	MDT)) {
	LLVM_DEBUG(dbgs() << "Remainder BB: " << MBB->getNumber() << "."
	<< MBB->getName() << " is\n");
	WebAssemblyException *InnerWE = getExceptionFor(MBB);
	while (InnerWE != SrcWE) {
	LLVM_DEBUG(dbgs()
	<< " removed from " << InnerWE->getEHPad()->getNumber()
	<< "." << InnerWE->getEHPad()->getName()
	<< "'s exception\n");
	InnerWE->removeFromBlocksSet(MBB);
	InnerWE = InnerWE->getParentException();
	}
	SrcWE->removeFromBlocksSet(MBB);
	LLVM_DEBUG(dbgs() << " removed from " << SrcWE->getEHPad()->getNumber()
	<< "." << SrcWE->getEHPad()->getName()
	<< "'s exception\n");
	changeExceptionFor(MBB, SrcWE->getParentException());
	if (SrcWE->getParentException())
	SrcWE->getParentException()->addToBlocksSet(MBB);
	}
	}
	}

	// Add BBs to exceptions' block vector
	for (auto DomNode : post_order(&MDT)) {
	MachineBasicBlock *MBB = DomNode->getBlock();
	WebAssemblyException *WE = getExceptionFor(MBB);
	for (; WE; WE = WE->getParentException())
	WE->addToBlocksVector(MBB);
	}

	SmallVector<WebAssemblyException*, 8> ExceptionPointers;
	ExceptionPointers.reserve(Exceptions.size());

	// Add subexceptions to exceptions
	for (auto &WE : Exceptions) {
	ExceptionPointers.push_back(WE.get());
	if (WE->getParentException())
	WE->getParentException()->getSubExceptions().push_back(std::move(WE));
	else
	addTopLevelException(std::move(WE));
	}

	// For convenience, Blocks and SubExceptions are inserted in postorder.
	// Reverse the lists.
	for (auto *WE : ExceptionPointers) {
	WE->reverseBlock();
	std::reverse(WE->getSubExceptions().begin(), WE->getSubExceptions().end());
	}
	}

	void WebAssemblyExceptionInfo::releaseMemory() {
	BBMap.clear();
	TopLevelExceptions.clear();
	}

	void WebAssemblyExceptionInfo::getAnalysisUsage(AnalysisUsage &AU) const {
	AU.setPreservesAll();
	AU.addRequired<MachineDominatorTree>();
	AU.addRequired<MachineDominanceFrontier>();
	MachineFunctionPass::getAnalysisUsage(AU);
	}

	void WebAssemblyExceptionInfo::discoverAndMapException(
	WebAssemblyException *WE, const MachineDominatorTree &MDT,
	const MachineDominanceFrontier &MDF) {
	unsigned NumBlocks = 0;
	unsigned NumSubExceptions = 0;

	// Map blocks that belong to a catchpad / cleanuppad
	MachineBasicBlock *EHPad = WE->getEHPad();
	SmallVector<MachineBasicBlock *, 8> WL;
	WL.push_back(EHPad);
	while (!WL.empty()) {
	MachineBasicBlock *MBB = WL.pop_back_val();

	// Find its outermost discovered exception. If this is a discovered block,
	// check if it is already discovered to be a subexception of this exception.
	WebAssemblyException *SubE = getOutermostException(MBB);
	if (SubE) {
	if (SubE != WE) {
	// Discover a subexception of this exception.
	SubE->setParentException(WE);
	++NumSubExceptions;
	NumBlocks += SubE->getBlocksVector().capacity();
	// All blocks that belong to this subexception have been already
	// discovered. Skip all of them. Add the subexception's landing pad's
	// dominance frontier to the worklist.
	for (auto &Frontier : MDF.find(SubE->getEHPad())->second)
	if (MDT.dominates(EHPad, Frontier))
	WL.push_back(Frontier);
	}
	continue;
	}

	// This is an undiscovered block. Map it to the current exception.
	changeExceptionFor(MBB, WE);
	++NumBlocks;

	// Add successors dominated by the current BB to the worklist.
	for (auto *Succ : MBB->successors())
	if (MDT.dominates(EHPad, Succ))
	WL.push_back(Succ);
	}

	WE->getSubExceptions().reserve(NumSubExceptions);
	WE->reserveBlocks(NumBlocks);
	}

	WebAssemblyException *
	WebAssemblyExceptionInfo::getOutermostException(MachineBasicBlock *MBB) const {
	WebAssemblyException *WE = getExceptionFor(MBB);
	if (WE) {
	while (WebAssemblyException *Parent = WE->getParentException())
	WE = Parent;
	}
	return WE;
	}

	void WebAssemblyException::print(raw_ostream &OS, unsigned Depth) const {
	OS.indent(Depth * 2) << "Exception at depth " << getExceptionDepth()
	<< " containing: ";

	for (unsigned I = 0; I < getBlocks().size(); ++I) {
	MachineBasicBlock *MBB = getBlocks()[I];
	if (I)
	OS << ", ";
	OS << "%bb." << MBB->getNumber();
	if (const auto *BB = MBB->getBasicBlock())
	if (BB->hasName())
	OS << "." << BB->getName();

	if (getEHPad() == MBB)
	OS << " (landing-pad)";
	}
	OS << "\n";

	for (auto &SubE : SubExceptions)
	SubE->print(OS, Depth + 2);
	}

	#if !defined(NDEBUG) \|\| defined(LLVM_ENABLE_DUMP)
	LLVM_DUMP_METHOD void WebAssemblyException::dump() const { print(dbgs()); }
	#endif

	raw_ostream &operator<<(raw_ostream &OS, const WebAssemblyException &WE) {
	WE.print(OS);
	return OS;
	}

	void WebAssemblyExceptionInfo::print(raw_ostream &OS, const Module *) const {
	for (auto &WE : TopLevelExceptions)
	WE->print(OS);
	}