llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.cpp

   1 //===--- WebAssemblyExceptionInfo.cpp - Exception Infomation --------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 ///
   9 /// \file
  10 /// \brief This file implements WebAssemblyException information analysis.
  11 ///
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "WebAssemblyExceptionInfo.h"
  15 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
  16 #include "Utils/WebAssemblyUtilities.h"
  17 #include "llvm/ADT/PostOrderIterator.h"
  18 #include "llvm/CodeGen/MachineDominanceFrontier.h"
  19 #include "llvm/CodeGen/MachineDominators.h"
  20 #include "llvm/CodeGen/WasmEHFuncInfo.h"
  21 #include "llvm/InitializePasses.h"
  22 #include "llvm/MC/MCAsmInfo.h"
  23 #include "llvm/Target/TargetMachine.h"
  24
  25 using namespace llvm;
  26
  27 #define DEBUG_TYPE "wasm-exception-info"
  28
  29 char WebAssemblyExceptionInfo::ID = 0;
  30
  31 INITIALIZE_PASS_BEGIN(WebAssemblyExceptionInfo, DEBUG_TYPE,
  32                       "WebAssembly Exception Information", true, true)
  33 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  34 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
  35 INITIALIZE_PASS_END(WebAssemblyExceptionInfo, DEBUG_TYPE,
  36                     "WebAssembly Exception Information", true, true)
  37
  38 bool WebAssemblyExceptionInfo::runOnMachineFunction(MachineFunction &MF) {
  39   LLVM_DEBUG(dbgs() << "********** Exception Info Calculation **********\n"
  40                        "********** Function: "
  41                     << MF.getName() << '\n');
  42   releaseMemory();
  43   if (MF.getTarget().getMCAsmInfo()->getExceptionHandlingType() !=
  44           ExceptionHandling::Wasm ||
  45       !MF.getFunction().hasPersonalityFn())
  46     return false;
  47   auto &MDT = getAnalysis<MachineDominatorTree>();
  48   auto &MDF = getAnalysis<MachineDominanceFrontier>();
  49   recalculate(MF, MDT, MDF);
  50   LLVM_DEBUG(dump());
  51   return false;
  52 }
  53
  54 // Check if Dst is reachable from Src using BFS. Search only within BBs
  55 // dominated by Header.
  56 static bool isReachableAmongDominated(const MachineBasicBlock *Src,
  57                                       const MachineBasicBlock *Dst,
  58                                       const MachineBasicBlock *Header,
  59                                       const MachineDominatorTree &MDT) {
  60   assert(MDT.dominates(Header, Dst));
  61   SmallVector<const MachineBasicBlock *, 8> WL;
  62   SmallPtrSet<const MachineBasicBlock *, 8> Visited;
  63   WL.push_back(Src);
  64
  65   while (!WL.empty()) {
  66     const auto *MBB = WL.pop_back_val();
  67     if (MBB == Dst)
  68       return true;
  69     Visited.insert(MBB);
  70     for (auto *Succ : MBB->successors())
  71       if (!Visited.count(Succ) && MDT.dominates(Header, Succ))
  72         WL.push_back(Succ);
  73   }
  74   return false;
  75 }
  76
  77 void WebAssemblyExceptionInfo::recalculate(
  78     MachineFunction &MF, MachineDominatorTree &MDT,
  79     const MachineDominanceFrontier &MDF) {
  80   // Postorder traversal of the dominator tree.
  81   SmallVector<std::unique_ptr<WebAssemblyException>, 8> Exceptions;
  82   for (auto DomNode : post_order(&MDT)) {
  83     MachineBasicBlock *EHPad = DomNode->getBlock();
  84     if (!EHPad->isEHPad())
  85       continue;
  86     auto WE = std::make_unique<WebAssemblyException>(EHPad);
  87     discoverAndMapException(WE.get(), MDT, MDF);
  88     Exceptions.push_back(std::move(WE));
  89   }
  90
  91   // WasmEHFuncInfo contains a map of <catchpad, its next unwind destination>,
  92   // which means, if an exception is not caught by the catchpad, it should end
  93   // up in the next unwind destination stored in this data structure. (It is
  94   // written as catchswitch's 'unwind' destination in ll files.) The below is an
  95   // intuitive example of their relationship in C++ code:
  96   // try {
  97   //   try {
  98   //   } catch (int) { // catchpad
  99   //      ...          // this catch (int) { ... } is grouped as an exception
 100   //   }
 101   // } catch (...) {   // next unwind destination
 102   // }
 103   // (The example is try-catches for illustration purpose, but the unwind
 104   // destination can be also a cleanuppad generated by destructor calls.) So the
 105   // unwind destination is in the outside of the catchpad's exception.
 106   //
 107   // We group exceptions in this analysis simply by including all BBs dominated
 108   // by an EH pad. But in case the EH pad's unwind destination does not have any
 109   // children outside of the exception, that unwind destination ends up also
 110   // being dominated by the EH pad and included in the exception, which is not
 111   // semantically correct, because it unwinds/rethrows into an inner scope.
 112   //
 113   // Here we extract those unwind destinations from their (incorrect) parent
 114   // exception. Note that the unwind destinations may not be an immediate
 115   // children of the parent exception, so we have to traverse the parent chain.
 116   //
 117   // We should traverse BBs in the preorder of the dominator tree, because
 118   // otherwise the result can be incorrect. For example, when there are three
 119   // exceptions A, B, and C and A > B > C (> is subexception relationship here),
 120   // and A's unwind destination is B and B's is C. When we visit B before A, we
 121   // end up extracting C only out of B but not out of A.
 122   const auto *EHInfo = MF.getWasmEHFuncInfo();
 123   SmallVector<std::pair<WebAssemblyException *, WebAssemblyException *>>
 124       UnwindWEVec;
 125   for (auto *DomNode : depth_first(&MDT)) {
 126     MachineBasicBlock *EHPad = DomNode->getBlock();
 127     if (!EHPad->isEHPad())
 128       continue;
 129     if (!EHInfo->hasUnwindDest(EHPad))
 130       continue;
 131     auto *UnwindDest = EHInfo->getUnwindDest(EHPad);
 132     auto *SrcWE = getExceptionFor(EHPad);
 133     auto *DstWE = getExceptionFor(UnwindDest);
 134     if (SrcWE->contains(DstWE)) {
 135       UnwindWEVec.push_back(std::make_pair(SrcWE, DstWE));
 136       LLVM_DEBUG(dbgs() << "Unwind destination ExceptionInfo fix:\n  "
 137                         << DstWE->getEHPad()->getNumber() << "."
 138                         << DstWE->getEHPad()->getName()
 139                         << "'s exception is taken out of "
 140                         << SrcWE->getEHPad()->getNumber() << "."
 141                         << SrcWE->getEHPad()->getName() << "'s exception\n");
 142       DstWE->setParentException(SrcWE->getParentException());
 143     }
 144   }
 145
 146   // After fixing subexception relationship between unwind destinations above,
 147   // there can still be remaining discrepancies.
 148   //
 149   // For example, suppose Exception A is dominated by EHPad A and Exception B is
 150   // dominated by EHPad B. EHPad A's unwind destination is EHPad B, but because
 151   // EHPad B is dominated by EHPad A, the initial grouping makes Exception B a
 152   // subexception of Exception A, and we fix it by taking Exception B out of
 153   // Exception A above. But there can still be remaining BBs within Exception A
 154   // that are reachable from Exception B. These BBs semantically don't belong
 155   // to Exception A and were not a part of this 'catch' clause or cleanup code
 156   // in the original code, but they just happened to be grouped within Exception
 157   // A because they were dominated by EHPad A. We fix this case by taking those
 158   // BBs out of the incorrect exception and all its subexceptions that it
 159   // belongs to.
 160   //
 161   // 1. First, we take out remaining incorrect subexceptions. This part is
 162   // easier, because we haven't added BBs to exceptions yet, we only need to
 163   // change parent exception pointer.
 164   for (auto *DomNode : depth_first(&MDT)) {
 165     MachineBasicBlock *EHPad = DomNode->getBlock();
 166     if (!EHPad->isEHPad())
 167       continue;
 168     auto *WE = getExceptionFor(EHPad);
 169
 170     // For each source EHPad -> unwind destination EHPad
 171     for (auto &P : UnwindWEVec) {
 172       auto *SrcWE = P.first;
 173       auto *DstWE = P.second;
 174       // If WE (the current EH pad's exception) is still contained in SrcWE but
 175       // reachable from DstWE that was taken out of SrcWE above, we have to take
 176       // out WE out of SrcWE too.
 177       if (WE != SrcWE && SrcWE->contains(WE) && !DstWE->contains(WE) &&
 178           isReachableAmongDominated(DstWE->getEHPad(), EHPad, SrcWE->getEHPad(),
 179                                     MDT)) {
 180         LLVM_DEBUG(dbgs() << "Remaining reachable ExceptionInfo fix:\n  "
 181                           << WE->getEHPad()->getNumber() << "."
 182                           << WE->getEHPad()->getName()
 183                           << "'s exception is taken out of "
 184                           << SrcWE->getEHPad()->getNumber() << "."
 185                           << SrcWE->getEHPad()->getName() << "'s exception\n");
 186         WE->setParentException(SrcWE->getParentException());
 187       }
 188     }
 189   }
 190
 191   // Add BBs to exceptions' block set. This is a preparation to take out
 192   // remaining incorect BBs from exceptions, because we need to iterate over BBs
 193   // for each exception.
 194   for (auto *DomNode : post_order(&MDT)) {
 195     MachineBasicBlock *MBB = DomNode->getBlock();
 196     WebAssemblyException *WE = getExceptionFor(MBB);
 197     for (; WE; WE = WE->getParentException())
 198       WE->addToBlocksSet(MBB);
 199   }
 200
 201   // 2. We take out remaining individual BBs out. Now we have added BBs to each
 202   // exceptions' BlockSet, when we take a BB out of an exception, we need to fix
 203   // those sets too.
 204   for (auto &P : UnwindWEVec) {
 205     auto *SrcWE = P.first;
 206     auto *DstWE = P.second;
 207
 208     for (auto *MBB : SrcWE->getBlocksSet()) {
 209       if (MBB->isEHPad()) {
 210         assert(!isReachableAmongDominated(DstWE->getEHPad(), MBB,
 211                                           SrcWE->getEHPad(), MDT) &&
 212                "We already handled EH pads above");
 213         continue;
 214       }
 215       if (isReachableAmongDominated(DstWE->getEHPad(), MBB, SrcWE->getEHPad(),
 216                                     MDT)) {
 217         LLVM_DEBUG(dbgs() << "Remainder BB: " << MBB->getNumber() << "."
 218                           << MBB->getName() << " is\n");
 219         WebAssemblyException *InnerWE = getExceptionFor(MBB);
 220         while (InnerWE != SrcWE) {
 221           LLVM_DEBUG(dbgs()
 222                      << "  removed from " << InnerWE->getEHPad()->getNumber()
 223                      << "." << InnerWE->getEHPad()->getName()
 224                      << "'s exception\n");
 225           InnerWE->removeFromBlocksSet(MBB);
 226           InnerWE = InnerWE->getParentException();
 227         }
 228         SrcWE->removeFromBlocksSet(MBB);
 229         LLVM_DEBUG(dbgs() << "  removed from " << SrcWE->getEHPad()->getNumber()
 230                           << "." << SrcWE->getEHPad()->getName()
 231                           << "'s exception\n");
 232         changeExceptionFor(MBB, SrcWE->getParentException());
 233         if (SrcWE->getParentException())
 234           SrcWE->getParentException()->addToBlocksSet(MBB);
 235       }
 236     }
 237   }
 238
 239   // Add BBs to exceptions' block vector
 240   for (auto DomNode : post_order(&MDT)) {
 241     MachineBasicBlock *MBB = DomNode->getBlock();
 242     WebAssemblyException *WE = getExceptionFor(MBB);
 243     for (; WE; WE = WE->getParentException())
 244       WE->addToBlocksVector(MBB);
 245   }
 246
 247   SmallVector<WebAssemblyException*, 8> ExceptionPointers;
 248   ExceptionPointers.reserve(Exceptions.size());
 249
 250   // Add subexceptions to exceptions
 251   for (auto &WE : Exceptions) {
 252     ExceptionPointers.push_back(WE.get());
 253     if (WE->getParentException())
 254       WE->getParentException()->getSubExceptions().push_back(std::move(WE));
 255     else
 256       addTopLevelException(std::move(WE));
 257   }
 258
 259   // For convenience, Blocks and SubExceptions are inserted in postorder.
 260   // Reverse the lists.
 261   for (auto *WE : ExceptionPointers) {
 262     WE->reverseBlock();
 263     std::reverse(WE->getSubExceptions().begin(), WE->getSubExceptions().end());
 264   }
 265 }
 266
 267 void WebAssemblyExceptionInfo::releaseMemory() {
 268   BBMap.clear();
 269   TopLevelExceptions.clear();
 270 }
 271
 272 void WebAssemblyExceptionInfo::getAnalysisUsage(AnalysisUsage &AU) const {
 273   AU.setPreservesAll();
 274   AU.addRequired<MachineDominatorTree>();
 275   AU.addRequired<MachineDominanceFrontier>();
 276   MachineFunctionPass::getAnalysisUsage(AU);
 277 }
 278
 279 void WebAssemblyExceptionInfo::discoverAndMapException(
 280     WebAssemblyException *WE, const MachineDominatorTree &MDT,
 281     const MachineDominanceFrontier &MDF) {
 282   unsigned NumBlocks = 0;
 283   unsigned NumSubExceptions = 0;
 284
 285   // Map blocks that belong to a catchpad / cleanuppad
 286   MachineBasicBlock *EHPad = WE->getEHPad();
 287   SmallVector<MachineBasicBlock *, 8> WL;
 288   WL.push_back(EHPad);
 289   while (!WL.empty()) {
 290     MachineBasicBlock *MBB = WL.pop_back_val();
 291
 292     // Find its outermost discovered exception. If this is a discovered block,
 293     // check if it is already discovered to be a subexception of this exception.
 294     WebAssemblyException *SubE = getOutermostException(MBB);
 295     if (SubE) {
 296       if (SubE != WE) {
 297         // Discover a subexception of this exception.
 298         SubE->setParentException(WE);
 299         ++NumSubExceptions;
 300         NumBlocks += SubE->getBlocksVector().capacity();
 301         // All blocks that belong to this subexception have been already
 302         // discovered. Skip all of them. Add the subexception's landing pad's
 303         // dominance frontier to the worklist.
 304         for (auto &Frontier : MDF.find(SubE->getEHPad())->second)
 305           if (MDT.dominates(EHPad, Frontier))
 306             WL.push_back(Frontier);
 307       }
 308       continue;
 309     }
 310
 311     // This is an undiscovered block. Map it to the current exception.
 312     changeExceptionFor(MBB, WE);
 313     ++NumBlocks;
 314
 315     // Add successors dominated by the current BB to the worklist.
 316     for (auto *Succ : MBB->successors())
 317       if (MDT.dominates(EHPad, Succ))
 318         WL.push_back(Succ);
 319   }
 320
 321   WE->getSubExceptions().reserve(NumSubExceptions);
 322   WE->reserveBlocks(NumBlocks);
 323 }
 324
 325 WebAssemblyException *
 326 WebAssemblyExceptionInfo::getOutermostException(MachineBasicBlock *MBB) const {
 327   WebAssemblyException *WE = getExceptionFor(MBB);
 328   if (WE) {
 329     while (WebAssemblyException *Parent = WE->getParentException())
 330       WE = Parent;
 331   }
 332   return WE;
 333 }
 334
 335 void WebAssemblyException::print(raw_ostream &OS, unsigned Depth) const {
 336   OS.indent(Depth * 2) << "Exception at depth " << getExceptionDepth()
 337                        << " containing: ";
 338
 339   for (unsigned I = 0; I < getBlocks().size(); ++I) {
 340     MachineBasicBlock *MBB = getBlocks()[I];
 341     if (I)
 342       OS << ", ";
 343     OS << "%bb." << MBB->getNumber();
 344     if (const auto *BB = MBB->getBasicBlock())
 345       if (BB->hasName())
 346         OS << "." << BB->getName();
 347
 348     if (getEHPad() == MBB)
 349       OS << " (landing-pad)";
 350   }
 351   OS << "\n";
 352
 353   for (auto &SubE : SubExceptions)
 354     SubE->print(OS, Depth + 2);
 355 }
 356
 357 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 358 LLVM_DUMP_METHOD void WebAssemblyException::dump() const { print(dbgs()); }
 359 #endif
 360
 361 raw_ostream &operator<<(raw_ostream &OS, const WebAssemblyException &WE) {
 362   WE.print(OS);
 363   return OS;
 364 }
 365
 366 void WebAssemblyExceptionInfo::print(raw_ostream &OS, const Module *) const {
 367   for (auto &WE : TopLevelExceptions)
 368     WE->print(OS);
 369 }