llvm/lib/Target/WebAssembly/WebAssemblyLateEHPrepare.cpp

   1 //=== WebAssemblyLateEHPrepare.cpp - WebAssembly Exception Preparation -===//
   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 Does various transformations for exception handling.
  11 ///
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
  15 #include "WebAssembly.h"
  16 #include "WebAssemblySubtarget.h"
  17 #include "WebAssemblyUtilities.h"
  18 #include "llvm/ADT/SmallPtrSet.h"
  19 #include "llvm/CodeGen/MachineFunctionPass.h"
  20 #include "llvm/CodeGen/MachineInstrBuilder.h"
  21 #include "llvm/CodeGen/WasmEHFuncInfo.h"
  22 #include "llvm/MC/MCAsmInfo.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 using namespace llvm;
  26
  27 #define DEBUG_TYPE "wasm-late-eh-prepare"
  28
  29 namespace {
  30 class WebAssemblyLateEHPrepare final : public MachineFunctionPass {
  31   StringRef getPassName() const override {
  32     return "WebAssembly Late Prepare Exception";
  33   }
  34
  35   bool runOnMachineFunction(MachineFunction &MF) override;
  36   bool removeUnreachableEHPads(MachineFunction &MF);
  37   void recordCatchRetBBs(MachineFunction &MF);
  38   bool hoistCatches(MachineFunction &MF);
  39   bool addCatchAlls(MachineFunction &MF);
  40   bool addCatchRefsAndThrowRefs(MachineFunction &MF);
  41   bool replaceFuncletReturns(MachineFunction &MF);
  42   bool removeUnnecessaryUnreachables(MachineFunction &MF);
  43   bool restoreStackPointer(MachineFunction &MF);
  44
  45   MachineBasicBlock *getMatchingEHPad(MachineInstr *MI);
  46   SmallPtrSet<MachineBasicBlock *, 8> CatchRetBBs;
  47
  48 public:
  49   static char ID; // Pass identification, replacement for typeid
  50   WebAssemblyLateEHPrepare() : MachineFunctionPass(ID) {}
  51 };
  52 } // end anonymous namespace
  53
  54 char WebAssemblyLateEHPrepare::ID = 0;
  55 INITIALIZE_PASS(WebAssemblyLateEHPrepare, DEBUG_TYPE,
  56                 "WebAssembly Late Exception Preparation", false, false)
  57
  58 FunctionPass *llvm::createWebAssemblyLateEHPrepare() {
  59   return new WebAssemblyLateEHPrepare();
  60 }
  61
  62 // Returns the nearest EH pad that dominates this instruction. This does not use
  63 // dominator analysis; it just does BFS on its predecessors until arriving at an
  64 // EH pad. This assumes valid EH scopes so the first EH pad it arrives in all
  65 // possible search paths should be the same.
  66 // Returns nullptr in case it does not find any EH pad in the search, or finds
  67 // multiple different EH pads.
  68 MachineBasicBlock *
  69 WebAssemblyLateEHPrepare::getMatchingEHPad(MachineInstr *MI) {
  70   MachineFunction *MF = MI->getParent()->getParent();
  71   SmallVector<MachineBasicBlock *, 2> WL;
  72   SmallPtrSet<MachineBasicBlock *, 2> Visited;
  73   WL.push_back(MI->getParent());
  74   MachineBasicBlock *EHPad = nullptr;
  75   while (!WL.empty()) {
  76     MachineBasicBlock *MBB = WL.pop_back_val();
  77     if (!Visited.insert(MBB).second)
  78       continue;
  79     if (MBB->isEHPad()) {
  80       if (EHPad && EHPad != MBB)
  81         return nullptr;
  82       EHPad = MBB;
  83       continue;
  84     }
  85     if (MBB == &MF->front())
  86       return nullptr;
  87     for (auto *Pred : MBB->predecessors())
  88       if (!CatchRetBBs.count(Pred)) // We don't go into child scopes
  89         WL.push_back(Pred);
  90   }
  91   return EHPad;
  92 }
  93
  94 // Erase the specified BBs if the BB does not have any remaining predecessors,
  95 // and also all its dead children.
  96 template <typename Container>
  97 static void eraseDeadBBsAndChildren(const Container &MBBs) {
  98   SmallVector<MachineBasicBlock *, 8> WL(MBBs.begin(), MBBs.end());
  99   SmallPtrSet<MachineBasicBlock *, 8> Deleted;
 100   while (!WL.empty()) {
 101     MachineBasicBlock *MBB = WL.pop_back_val();
 102     if (Deleted.count(MBB) || !MBB->pred_empty())
 103       continue;
 104     SmallVector<MachineBasicBlock *, 4> Succs(MBB->successors());
 105     WL.append(MBB->succ_begin(), MBB->succ_end());
 106     for (auto *Succ : Succs)
 107       MBB->removeSuccessor(Succ);
 108     // To prevent deleting the same BB multiple times, which can happen when
 109     // 'MBBs' contain both a parent and a child
 110     Deleted.insert(MBB);
 111     MBB->eraseFromParent();
 112   }
 113 }
 114
 115 bool WebAssemblyLateEHPrepare::runOnMachineFunction(MachineFunction &MF) {
 116   LLVM_DEBUG(dbgs() << "********** Late EH Prepare **********\n"
 117                        "********** Function: "
 118                     << MF.getName() << '\n');
 119
 120   if (MF.getTarget().getMCAsmInfo()->getExceptionHandlingType() !=
 121       ExceptionHandling::Wasm)
 122     return false;
 123
 124   bool Changed = false;
 125   if (MF.getFunction().hasPersonalityFn()) {
 126     Changed |= removeUnreachableEHPads(MF);
 127     recordCatchRetBBs(MF);
 128     Changed |= hoistCatches(MF);
 129     Changed |= addCatchAlls(MF);
 130     Changed |= replaceFuncletReturns(MF);
 131     if (WebAssembly::WasmEnableExnref)
 132       Changed |= addCatchRefsAndThrowRefs(MF);
 133   }
 134   Changed |= removeUnnecessaryUnreachables(MF);
 135   if (MF.getFunction().hasPersonalityFn())
 136     Changed |= restoreStackPointer(MF);
 137   return Changed;
 138 }
 139
 140 // Remove unreachable EH pads and its children. If they remain, CFG
 141 // stackification can be tricky.
 142 bool WebAssemblyLateEHPrepare::removeUnreachableEHPads(MachineFunction &MF) {
 143   SmallVector<MachineBasicBlock *, 4> ToDelete;
 144   for (auto &MBB : MF)
 145     if (MBB.isEHPad() && MBB.pred_empty())
 146       ToDelete.push_back(&MBB);
 147   eraseDeadBBsAndChildren(ToDelete);
 148   return !ToDelete.empty();
 149 }
 150
 151 // Record which BB ends with catchret instruction, because this will be replaced
 152 // with 'br's later. This set of catchret BBs is necessary in 'getMatchingEHPad'
 153 // function.
 154 void WebAssemblyLateEHPrepare::recordCatchRetBBs(MachineFunction &MF) {
 155   CatchRetBBs.clear();
 156   for (auto &MBB : MF) {
 157     auto Pos = MBB.getFirstTerminator();
 158     if (Pos == MBB.end())
 159       continue;
 160     MachineInstr *TI = &*Pos;
 161     if (TI->getOpcode() == WebAssembly::CATCHRET)
 162       CatchRetBBs.insert(&MBB);
 163   }
 164 }
 165
 166 // Hoist catch instructions to the beginning of their matching EH pad BBs in
 167 // case,
 168 // (1) catch instruction is not the first instruction in EH pad.
 169 // ehpad:
 170 //   some_other_instruction
 171 //   ...
 172 //   %exn = catch 0
 173 // (2) catch instruction is in a non-EH pad BB. For example,
 174 // ehpad:
 175 //   br bb0
 176 // bb0:
 177 //   %exn = catch 0
 178 bool WebAssemblyLateEHPrepare::hoistCatches(MachineFunction &MF) {
 179   bool Changed = false;
 180   SmallVector<MachineInstr *, 16> Catches;
 181   for (auto &MBB : MF)
 182     for (auto &MI : MBB)
 183       if (WebAssembly::isCatch(MI.getOpcode()))
 184         Catches.push_back(&MI);
 185
 186   for (auto *Catch : Catches) {
 187     MachineBasicBlock *EHPad = getMatchingEHPad(Catch);
 188     assert(EHPad && "No matching EH pad for catch");
 189     auto InsertPos = EHPad->begin();
 190     // Skip EH_LABELs in the beginning of an EH pad if present. We don't use
 191     // these labels at the moment, but other targets also seem to have an
 192     // EH_LABEL instruction in the beginning of an EH pad.
 193     while (InsertPos != EHPad->end() && InsertPos->isEHLabel())
 194       InsertPos++;
 195     if (InsertPos == Catch)
 196       continue;
 197     Changed = true;
 198     EHPad->insert(InsertPos, Catch->removeFromParent());
 199   }
 200   return Changed;
 201 }
 202
 203 // Add catch_all to beginning of cleanup pads.
 204 bool WebAssemblyLateEHPrepare::addCatchAlls(MachineFunction &MF) {
 205   bool Changed = false;
 206   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
 207
 208   for (auto &MBB : MF) {
 209     if (!MBB.isEHPad())
 210       continue;
 211     auto InsertPos = MBB.begin();
 212     // Skip EH_LABELs in the beginning of an EH pad if present.
 213     while (InsertPos != MBB.end() && InsertPos->isEHLabel())
 214       InsertPos++;
 215     // This runs after hoistCatches(), so we assume that if there is a catch,
 216     // that should be the first non-EH-label instruction in an EH pad.
 217     if (InsertPos == MBB.end() ||
 218         !WebAssembly::isCatch(InsertPos->getOpcode())) {
 219       Changed = true;
 220       unsigned CatchAllOpcode = WebAssembly::WasmEnableExnref
 221                                     ? WebAssembly::CATCH_ALL
 222                                     : WebAssembly::CATCH_ALL_LEGACY;
 223       BuildMI(MBB, InsertPos,
 224               InsertPos == MBB.end() ? DebugLoc() : InsertPos->getDebugLoc(),
 225               TII.get(CatchAllOpcode));
 226     }
 227   }
 228   return Changed;
 229 }
 230
 231 // Replace pseudo-instructions catchret and cleanupret with br and rethrow
 232 // respectively.
 233 bool WebAssemblyLateEHPrepare::replaceFuncletReturns(MachineFunction &MF) {
 234   bool Changed = false;
 235   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
 236
 237   for (auto &MBB : MF) {
 238     auto Pos = MBB.getFirstTerminator();
 239     if (Pos == MBB.end())
 240       continue;
 241     MachineInstr *TI = &*Pos;
 242
 243     switch (TI->getOpcode()) {
 244     case WebAssembly::CATCHRET: {
 245       // Replace a catchret with a branch
 246       MachineBasicBlock *TBB = TI->getOperand(0).getMBB();
 247       if (!MBB.isLayoutSuccessor(TBB))
 248         BuildMI(MBB, TI, TI->getDebugLoc(), TII.get(WebAssembly::BR))
 249             .addMBB(TBB);
 250       TI->eraseFromParent();
 251       Changed = true;
 252       break;
 253     }
 254     case WebAssembly::RETHROW:
 255       // These RETHROWs here were lowered from llvm.wasm.rethrow() intrinsics,
 256       // generated in Clang for when an exception is not caught by the given
 257       // type (e.g. catch (int)).
 258       //
 259       // RETHROW's BB argument is the EH pad where the exception to rethrow has
 260       // been caught. (Until this point, RETHROW has just a '0' as a placeholder
 261       // argument.) For these llvm.wasm.rethrow()s, we can safely assume the
 262       // exception comes from the nearest dominating EH pad, because catch.start
 263       // EH pad is structured like this:
 264       //
 265       // catch.start:
 266       //   catchpad ...
 267       //   %matches = compare ehselector with typeid
 268       //   br i1 %matches, label %catch, label %rethrow
 269       //
 270       // rethrow:
 271       //   ;; rethrows the exception caught in 'catch.start'
 272       //   call @llvm.wasm.rethrow()
 273       TI->removeOperand(0);
 274       TI->addOperand(MachineOperand::CreateMBB(getMatchingEHPad(TI)));
 275       Changed = true;
 276       break;
 277     case WebAssembly::CLEANUPRET: {
 278       // CLEANUPRETs have the EH pad BB the exception to rethrow has been caught
 279       // as an argument. Use it and change the instruction opcode to 'RETHROW'
 280       // to make rethrowing instructions consistent.
 281       //
 282       // This is because we cannot safely assume that it is always the nearest
 283       // dominating EH pad, in case there are code transformations such as
 284       // inlining.
 285       BuildMI(MBB, TI, TI->getDebugLoc(), TII.get(WebAssembly::RETHROW))
 286           .addMBB(TI->getOperand(0).getMBB());
 287       TI->eraseFromParent();
 288       Changed = true;
 289       break;
 290     }
 291     }
 292   }
 293   return Changed;
 294 }
 295
 296 // Add CATCH_REF and CATCH_ALL_REF pseudo instructions to EH pads, and convert
 297 // RETHROWs to THROW_REFs.
 298 bool WebAssemblyLateEHPrepare::addCatchRefsAndThrowRefs(MachineFunction &MF) {
 299   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
 300   auto &MRI = MF.getRegInfo();
 301   DenseMap<MachineBasicBlock *, SmallVector<MachineInstr *, 2>> EHPadToRethrows;
 302
 303   // Create a map of <EH pad, a vector of RETHROWs rethrowing its exception>
 304   for (auto &MBB : MF)
 305     for (auto &MI : MBB)
 306       if (MI.getOpcode() == WebAssembly::RETHROW)
 307         EHPadToRethrows[MI.getOperand(0).getMBB()].push_back(&MI);
 308   if (EHPadToRethrows.empty())
 309     return false;
 310
 311   // Convert CATCH into CATCH_REF and CATCH_ALL into CATCH_ALL_REF, when the
 312   // caught exception is rethrown. And convert RETHROWs to THROW_REFs.
 313   for (auto &[EHPad, Rethrows] : EHPadToRethrows) {
 314     auto *Catch = WebAssembly::findCatch(EHPad);
 315     auto *InsertPos = Catch->getIterator()->getNextNode();
 316     auto ExnReg = MRI.createVirtualRegister(&WebAssembly::EXNREFRegClass);
 317     if (Catch->getOpcode() == WebAssembly::CATCH) {
 318       MachineInstrBuilder MIB = BuildMI(*EHPad, InsertPos, Catch->getDebugLoc(),
 319                                         TII.get(WebAssembly::CATCH_REF));
 320       // Copy defs (= extracted values) from the old CATCH to the new CATCH_REF
 321       for (const auto &Def : Catch->defs())
 322         MIB.addDef(Def.getReg());
 323       MIB.addDef(ExnReg); // Attach the exnref def after extracted values
 324       // Copy the tag symbol (The only use operand a CATCH can have is the tag
 325       // symbol)
 326       for (const auto &Use : Catch->uses()) {
 327         MIB.addExternalSymbol(Use.getSymbolName());
 328         break;
 329       }
 330     } else if (Catch->getOpcode() == WebAssembly::CATCH_ALL) {
 331       BuildMI(*EHPad, InsertPos, Catch->getDebugLoc(),
 332               TII.get(WebAssembly::CATCH_ALL_REF))
 333           .addDef(ExnReg);
 334     } else {
 335       assert(false);
 336     }
 337     Catch->eraseFromParent();
 338
 339     for (auto *Rethrow : Rethrows) {
 340       auto InsertPos = std::next(Rethrow->getIterator());
 341       BuildMI(*Rethrow->getParent(), InsertPos, Rethrow->getDebugLoc(),
 342               TII.get(WebAssembly::THROW_REF))
 343           .addReg(ExnReg);
 344       Rethrow->eraseFromParent();
 345     }
 346   }
 347
 348   return true;
 349 }
 350
 351 // Remove unnecessary unreachables after a throw/rethrow/throw_ref.
 352 bool WebAssemblyLateEHPrepare::removeUnnecessaryUnreachables(
 353     MachineFunction &MF) {
 354   bool Changed = false;
 355   for (auto &MBB : MF) {
 356     for (auto &MI : MBB) {
 357       if (MI.getOpcode() != WebAssembly::THROW &&
 358           MI.getOpcode() != WebAssembly::RETHROW &&
 359           MI.getOpcode() != WebAssembly::THROW_REF)
 360         continue;
 361       Changed = true;
 362
 363       // The instruction after the throw should be an unreachable or a branch to
 364       // another BB that should eventually lead to an unreachable. Delete it
 365       // because throw itself is a terminator, and also delete successors if
 366       // any.
 367       MBB.erase(std::next(MI.getIterator()), MBB.end());
 368       SmallVector<MachineBasicBlock *, 8> Succs(MBB.successors());
 369       for (auto *Succ : Succs)
 370         if (!Succ->isEHPad())
 371           MBB.removeSuccessor(Succ);
 372       eraseDeadBBsAndChildren(Succs);
 373     }
 374   }
 375
 376   return Changed;
 377 }
 378
 379 // After the stack is unwound due to a thrown exception, the __stack_pointer
 380 // global can point to an invalid address. This inserts instructions that
 381 // restore __stack_pointer global.
 382 bool WebAssemblyLateEHPrepare::restoreStackPointer(MachineFunction &MF) {
 383   const auto *FrameLowering = static_cast<const WebAssemblyFrameLowering *>(
 384       MF.getSubtarget().getFrameLowering());
 385   if (!FrameLowering->needsPrologForEH(MF))
 386     return false;
 387   bool Changed = false;
 388
 389   for (auto &MBB : MF) {
 390     if (!MBB.isEHPad())
 391       continue;
 392     Changed = true;
 393
 394     // Insert __stack_pointer restoring instructions at the beginning of each EH
 395     // pad, after the catch instruction. Here it is safe to assume that SP32
 396     // holds the latest value of __stack_pointer, because the only exception for
 397     // this case is when a function uses the red zone, but that only happens
 398     // with leaf functions, and we don't restore __stack_pointer in leaf
 399     // functions anyway.
 400     auto InsertPos = MBB.begin();
 401     // Skip EH_LABELs in the beginning of an EH pad if present.
 402     while (InsertPos != MBB.end() && InsertPos->isEHLabel())
 403       InsertPos++;
 404     assert(InsertPos != MBB.end() &&
 405            WebAssembly::isCatch(InsertPos->getOpcode()) &&
 406            "catch/catch_all should be present in every EH pad at this point");
 407     ++InsertPos; // Skip the catch instruction
 408     FrameLowering->writeSPToGlobal(FrameLowering->getSPReg(MF), MF, MBB,
 409                                    InsertPos, MBB.begin()->getDebugLoc());
 410   }
 411   return Changed;
 412 }