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