Index: lib/Target/WebAssembly/CMakeLists.txt =================================================================== --- lib/Target/WebAssembly/CMakeLists.txt +++ lib/Target/WebAssembly/CMakeLists.txt @@ -15,6 +15,7 @@ WebAssemblyCallIndirectFixup.cpp WebAssemblyCFGStackify.cpp WebAssemblyCFGSort.cpp + WebAssemblyExceptionInfo.cpp WebAssemblyExplicitLocals.cpp WebAssemblyFastISel.cpp WebAssemblyFixIrreducibleControlFlow.cpp Index: lib/Target/WebAssembly/WebAssembly.h =================================================================== --- lib/Target/WebAssembly/WebAssembly.h +++ lib/Target/WebAssembly/WebAssembly.h @@ -47,6 +47,7 @@ FunctionPass *createWebAssemblyRegColoring(); FunctionPass *createWebAssemblyExplicitLocals(); FunctionPass *createWebAssemblyFixIrreducibleControlFlow(); +void initializeWebAssemblyExceptionInfoPass(PassRegistry &); FunctionPass *createWebAssemblyCFGSort(); FunctionPass *createWebAssemblyCFGStackify(); FunctionPass *createWebAssemblyLowerBrUnless(); Index: lib/Target/WebAssembly/WebAssemblyExceptionInfo.h =================================================================== --- /dev/null +++ lib/Target/WebAssembly/WebAssemblyExceptionInfo.h @@ -0,0 +1,150 @@ +//= WebAssemblyExceptionInfo.h - WebAssembly Exception Info -*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// \brief This file implements WebAssemblyException information analysis. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYEXCEPTIONINFO_H +#define LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYEXCEPTIONINFO_H + +#include "WebAssembly.h" +#include "llvm/CodeGen/MachineFunctionPass.h" + +namespace llvm { + +class WebAssemblyException { + MachineBasicBlock *LPad = nullptr; // Landing pad + + WebAssemblyException *ParentException = nullptr; + std::vector SubExceptions; + std::vector Blocks; + SmallPtrSet BlockSet; + + WebAssemblyException(const WebAssemblyException &) = delete; + const WebAssemblyException &operator=(const WebAssemblyException &) = delete; + +public: + WebAssemblyException(MachineBasicBlock *LPad) + : LPad(LPad), ParentException(nullptr) {} + ~WebAssemblyException() { + for (size_t i = 0, e = SubExceptions.size(); i != e; ++i) + delete SubExceptions[i]; + } + + MachineBasicBlock *getLandingPad() const { return LPad; } + WebAssemblyException *getParentException() const { return ParentException; } + void setParentException(WebAssemblyException *WE) { ParentException = WE; } + + bool contains(const WebAssemblyException *WE) const { + if (WE == this) + return true; + if (!WE) + return false; + return contains(WE->getParentException()); + } + bool contains(const MachineBasicBlock *MBB) const { + return BlockSet.count(MBB); + } + + void addBlock(MachineBasicBlock *MBB) { + Blocks.push_back(MBB); + BlockSet.insert(MBB); + } + const std::vector &getBlocks() const { return Blocks; } + typedef + typename std::vector::const_iterator block_iterator; + block_iterator block_begin() const { return Blocks.begin(); } + block_iterator block_end() const { return Blocks.end(); } + inline iterator_range blocks() const { + return make_range(block_begin(), block_end()); + } + unsigned getNumBlocks() const { return Blocks.size(); } + + const std::vector &getSubExceptions() const { + return SubExceptions; + } + std::vector &getSubExceptions() { + return SubExceptions; + } + void addSubException(WebAssemblyException *E) { SubExceptions.push_back(E); } + typedef typename std::vector::const_iterator iterator; + iterator begin() const { return SubExceptions.begin(); } + iterator end() const { return SubExceptions.end(); } + + void reserveBlocks(unsigned Size) { Blocks.reserve(Size); } + void reverseBlock(unsigned From = 0) { + std::reverse(Blocks.begin() + From, Blocks.end()); + } + + // Return the nesting level. An outermost one has depth 1. + unsigned getExceptionDepth() const { + unsigned D = 1; + for (const WebAssemblyException *CurException = ParentException; + CurException; CurException = CurException->ParentException) + ++D; + return D; + } + + void print(raw_ostream &OS, unsigned Depth = 0, bool Verbose = false) const; + void dump() const; +}; + +raw_ostream &operator<<(raw_ostream &OS, const WebAssemblyException &WE); + +class WebAssemblyExceptionInfo : public MachineFunctionPass { + // Mapping of basic blocks to the innermost exception they occur in + DenseMap BBMap; + std::vector TopLevelExceptions; + WebAssemblyExceptionInfo(const WebAssemblyExceptionInfo &) = delete; + WebAssemblyExceptionInfo & + operator=(const WebAssemblyExceptionInfo &) = delete; + + void discoverAndMapException(WebAssemblyException *WE); + WebAssemblyException *getOutermostException(MachineBasicBlock *MBB) const; + +public: + static char ID; + WebAssemblyExceptionInfo() : MachineFunctionPass(ID) { + initializeWebAssemblyExceptionInfoPass(*PassRegistry::getPassRegistry()); + } + ~WebAssemblyExceptionInfo() { releaseMemory(); } + + bool runOnMachineFunction(MachineFunction &) override; + void releaseMemory() override; + void getAnalysisUsage(AnalysisUsage &AU) const override; + + bool empty() const { return TopLevelExceptions.empty(); } + + // Return the innermost exception that MBB lives in. If the block is not in an + // exception, null is returned. + WebAssemblyException *getExceptionFor(const MachineBasicBlock *MBB) const { + return BBMap.lookup(MBB); + } + + void changeExceptionFor(MachineBasicBlock *MBB, WebAssemblyException *WE) { + if (!WE) { + BBMap.erase(MBB); + return; + } + BBMap[MBB] = WE; + } + + void addTopLevelException(WebAssemblyException *WE) { + assert(!WE->getParentException() && "Not a top level exception!"); + TopLevelExceptions.push_back(WE); + } + + void print(raw_ostream &OS, const Module *M = nullptr) const override; +}; + +} // end namespace llvm + +#endif Index: lib/Target/WebAssembly/WebAssemblyExceptionInfo.cpp =================================================================== --- /dev/null +++ lib/Target/WebAssembly/WebAssemblyExceptionInfo.cpp @@ -0,0 +1,206 @@ +//===--- WebAssemblyExceptionInfo.cpp - Exception Infomation --------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// \brief This file implements WebAssemblyException information analysis. +/// +/// +/// WebAssembly instructions for exception handling are structured as follows: +/// try +/// instructions* +/// catch ----| +/// instructions* | -> This part consists of WebAssemblyException +/// end ----| +// +/// A WebAssemblyException object contains BBs that belong to a 'catch' part of +/// the try-catch-end structure. ('end' is not included) 'try' and 'end' markers +/// are not present at this stage and will be generated in CFGStackify pass. +/// Because CFGSort requires all the BBs within a catch part to be sorted +/// together as it does for loops, this pass calculates the nesting structure of +/// catch part of exceptions in a function. +/// +/// An exception catch part is defined as a BB with catch instruction and all +/// other BBs dominated by this BB. +/// +//===----------------------------------------------------------------------===// + +#include "WebAssemblyExceptionInfo.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/CodeGen/MachineDominanceFrontier.h" +#include "llvm/CodeGen/MachineDominators.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/Support/Debug.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 &F) { + releaseMemory(); + + // Postorder traversal of the dominator tree. + auto &MDT = getAnalysis(); + SmallVector Exceptions; + for (auto DomNode : post_order(&MDT)) { + MachineBasicBlock *LPad = DomNode->getBlock(); + if (!LPad->isEHPad()) + continue; + auto *WE = new WebAssemblyException(LPad); + discoverAndMapException(WE); + Exceptions.push_back(WE); + } + + // Add BBs to exceptions + for (auto DomNode : post_order(&MDT)) { + MachineBasicBlock *MBB = DomNode->getBlock(); + WebAssemblyException *WE = getExceptionFor(MBB); + for (; WE; WE = WE->getParentException()) + WE->addBlock(MBB); + } + + // Add subexceptions to exceptions + for (auto *WE : Exceptions) { + if (WE->getParentException()) + WE->getParentException()->getSubExceptions().push_back(WE); + else + addTopLevelException(WE); + } + + // For convenience, Blocks and SubExceptions are inserted in postorder. + // Reverse the lists. + for (auto *WE : Exceptions) { + WE->reverseBlock(); + std::reverse(WE->getSubExceptions().begin(), WE->getSubExceptions().end()); + } + + return false; +} + +void WebAssemblyExceptionInfo::releaseMemory() { + BBMap.clear(); + for (auto *WE : TopLevelExceptions) + delete WE; + TopLevelExceptions.clear(); +} + +void WebAssemblyExceptionInfo::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired(); + AU.addRequired(); + MachineFunctionPass::getAnalysisUsage(AU); +} + +// Discover a subexception +void WebAssemblyExceptionInfo::discoverAndMapException( + WebAssemblyException *WE) { + auto &MDT = getAnalysis(); + auto &MDF = getAnalysis(); + unsigned NumBlocks = 0; + unsigned NumSubExceptions = 0; + + // Map blocks that belong to the catch block: map all the blocks dominated by + // the landing pad + MachineBasicBlock *LPad = WE->getLandingPad(); + SmallVector WL; + WL.push_back(LPad); + 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->getBlocks().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->getLandingPad())->second) + if (MDT.dominates(LPad, 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 landing pad to the worklist. + for (auto *Succ : MBB->successors()) { + if (MDT.dominates(LPad, 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, + bool Verbose) const { + OS.indent(Depth * 2) << "Exception at depth " << getExceptionDepth() + << " containing: "; + + for (unsigned I = 0; I < getBlocks().size(); ++I) { + MachineBasicBlock *MBB = getBlocks()[I]; + if (!Verbose) { + if (I) + OS << ", "; + MBB->printAsOperand(OS, false); + OS << "/" << MBB->getName(); + } else + OS << "\n"; + + if (getLandingPad() == MBB) + OS << ""; + if (Verbose) + MBB->print(OS); + } + 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); +} Index: lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp =================================================================== --- lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp +++ lib/Target/WebAssembly/WebAssemblyTargetMachine.cpp @@ -51,6 +51,8 @@ // Register exception handling pass to opt initializeWebAssemblyLowerEmscriptenEHSjLjPass( *PassRegistry::getPassRegistry()); + + initializeWebAssemblyExceptionInfoPass(*PassRegistry::getPassRegistry()); } //===----------------------------------------------------------------------===//