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/MachineFunctionPass.h"
21#include "llvm/CodeGen/MachineInstrBuilder.h"
22#include "llvm/MC/MCAsmInfo.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/Target/TargetMachine.h"
25using namespace llvm;
26
27#define DEBUG_TYPE "wasm-late-eh-prepare"
28
29namespace {
30class 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
48public:
49 static char ID; // Pass identification, replacement for typeid
50 WebAssemblyLateEHPrepare() : MachineFunctionPass(ID) {}
51};
52} // end anonymous namespace
53
54char WebAssemblyLateEHPrepare::ID = 0;
55INITIALIZE_PASS(WebAssemblyLateEHPrepare, DEBUG_TYPE,
56 "WebAssembly Late Exception Preparation", false, false)
57
58FunctionPass *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.
68MachineBasicBlock *
69WebAssemblyLateEHPrepare::getMatchingEHPad(MachineInstr *MI) {
70 MachineFunction *MF = MI->getParent()->getParent();
71 SmallVector<MachineBasicBlock *, 2> WL;
72 SmallPtrSet<MachineBasicBlock *, 2> Visited;
73 WL.push_back(Elt: MI->getParent());
74 MachineBasicBlock *EHPad = nullptr;
75 while (!WL.empty()) {
76 MachineBasicBlock *MBB = WL.pop_back_val();
77 if (!Visited.insert(Ptr: 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(Ptr: Pred)) // We don't go into child scopes
89 WL.push_back(Elt: 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.
96template <typename Container>
97static 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(Ptr: MBB) || !MBB->pred_empty())
103 continue;
104 SmallVector<MachineBasicBlock *, 4> Succs(MBB->successors());
105 WL.append(in_start: MBB->succ_begin(), in_end: 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(Ptr: MBB);
111 MBB->eraseFromParent();
112 }
113}
114
115bool 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::WasmUseLegacyEH)
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.
142bool 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(Elt: &MBB);
147 eraseDeadBBsAndChildren(MBBs: 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.
154void 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(Ptr: &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
178bool 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(Opc: MI.getOpcode()))
184 Catches.push_back(Elt: &MI);
185
186 for (auto *Catch : Catches) {
187 MachineBasicBlock *EHPad = getMatchingEHPad(MI: 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(I: InsertPos, MI: Catch->removeFromParent());
199 }
200 return Changed;
201}
202
203// Add catch_all to beginning of cleanup pads.
204bool 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(Opc: InsertPos->getOpcode())) {
219 Changed = true;
220 unsigned CatchAllOpcode = WebAssembly::WasmUseLegacyEH
221 ? WebAssembly::CATCH_ALL_LEGACY
222 : WebAssembly::CATCH_ALL;
223 BuildMI(BB&: MBB, I: InsertPos,
224 MIMD: InsertPos == MBB.end() ? DebugLoc() : InsertPos->getDebugLoc(),
225 MCID: TII.get(Opcode: CatchAllOpcode));
226 }
227 }
228 return Changed;
229}
230
231// Replace pseudo-instructions catchret and cleanupret with br and rethrow
232// respectively.
233bool 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(i: 0).getMBB();
247 if (!MBB.isLayoutSuccessor(MBB: TBB))
248 BuildMI(BB&: MBB, I: TI, MIMD: TI->getDebugLoc(), MCID: TII.get(Opcode: WebAssembly::BR))
249 .addMBB(MBB: 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(OpNo: 0);
274 TI->addOperand(Op: MachineOperand::CreateMBB(MBB: getMatchingEHPad(MI: 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(BB&: MBB, I: TI, MIMD: TI->getDebugLoc(), MCID: TII.get(Opcode: WebAssembly::RETHROW))
286 .addMBB(MBB: TI->getOperand(i: 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.
298bool WebAssemblyLateEHPrepare::addCatchRefsAndThrowRefs(MachineFunction &MF) {
299 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
300 auto &MRI = MF.getRegInfo();
301 MapVector<MachineBasicBlock *, SmallVector<MachineInstr *, 2>>
302 EHPadToRethrows;
303
304 // Create a map of <EH pad, a vector of RETHROWs rethrowing its exception>
305 for (auto &MBB : MF)
306 for (auto &MI : MBB)
307 if (MI.getOpcode() == WebAssembly::RETHROW)
308 EHPadToRethrows[MI.getOperand(i: 0).getMBB()].push_back(Elt: &MI);
309 if (EHPadToRethrows.empty())
310 return false;
311
312 // Convert CATCH into CATCH_REF and CATCH_ALL into CATCH_ALL_REF, when the
313 // caught exception is rethrown. And convert RETHROWs to THROW_REFs.
314 for (auto &[EHPad, Rethrows] : EHPadToRethrows) {
315 auto *Catch = WebAssembly::findCatch(EHPad);
316 assert(Catch && "CATCH not found in EHPad");
317 auto InsertPos = std::next(x: Catch->getIterator());
318 auto ExnReg = MRI.createVirtualRegister(RegClass: &WebAssembly::EXNREFRegClass);
319 if (Catch->getOpcode() == WebAssembly::CATCH) {
320 MachineInstrBuilder MIB = BuildMI(BB&: *EHPad, I: InsertPos, MIMD: Catch->getDebugLoc(),
321 MCID: TII.get(Opcode: WebAssembly::CATCH_REF));
322 // Copy defs (= extracted values) from the old CATCH to the new CATCH_REF
323 for (const auto &Def : Catch->defs())
324 MIB.addDef(RegNo: Def.getReg());
325 MIB.addDef(RegNo: ExnReg); // Attach the exnref def after extracted values
326 // Copy the tag symbol (The only use operand a CATCH can have is the tag
327 // symbol)
328 for (const auto &Use : Catch->uses()) {
329 MIB.addExternalSymbol(FnName: Use.getSymbolName());
330 break;
331 }
332 } else if (Catch->getOpcode() == WebAssembly::CATCH_ALL) {
333 BuildMI(BB&: *EHPad, I: InsertPos, MIMD: Catch->getDebugLoc(),
334 MCID: TII.get(Opcode: WebAssembly::CATCH_ALL_REF))
335 .addDef(RegNo: ExnReg);
336 } else {
337 assert(false);
338 }
339 Catch->eraseFromParent();
340
341 for (auto *Rethrow : Rethrows) {
342 auto InsertPos = std::next(x: Rethrow->getIterator());
343 BuildMI(BB&: *Rethrow->getParent(), I: InsertPos, MIMD: Rethrow->getDebugLoc(),
344 MCID: TII.get(Opcode: WebAssembly::THROW_REF))
345 .addReg(RegNo: ExnReg);
346 Rethrow->eraseFromParent();
347 }
348 }
349
350 return true;
351}
352
353// Remove unnecessary unreachables after a throw/rethrow/throw_ref.
354bool WebAssemblyLateEHPrepare::removeUnnecessaryUnreachables(
355 MachineFunction &MF) {
356 bool Changed = false;
357 for (auto &MBB : MF) {
358 for (auto &MI : MBB) {
359 if (MI.getOpcode() != WebAssembly::THROW &&
360 MI.getOpcode() != WebAssembly::RETHROW &&
361 MI.getOpcode() != WebAssembly::THROW_REF)
362 continue;
363 Changed = true;
364
365 // The instruction after the throw should be an unreachable or a branch to
366 // another BB that should eventually lead to an unreachable. Delete it
367 // because throw itself is a terminator, and also delete successors if
368 // any.
369 MBB.erase(I: std::next(x: MI.getIterator()), E: MBB.end());
370 SmallVector<MachineBasicBlock *, 8> Succs(MBB.successors());
371 for (auto *Succ : Succs)
372 if (!Succ->isEHPad())
373 MBB.removeSuccessor(Succ);
374 eraseDeadBBsAndChildren(MBBs: Succs);
375 }
376 }
377
378 return Changed;
379}
380
381// After the stack is unwound due to a thrown exception, the __stack_pointer
382// global/__wasm_get_stack_pointer() can point to an invalid address. This
383// inserts instructions that restore the stack pointer state.
384bool WebAssemblyLateEHPrepare::restoreStackPointer(MachineFunction &MF) {
385 const auto *FrameLowering = static_cast<const WebAssemblyFrameLowering *>(
386 MF.getSubtarget().getFrameLowering());
387 if (!FrameLowering->needsPrologForEH(MF))
388 return false;
389 bool Changed = false;
390
391 for (auto &MBB : MF) {
392 if (!MBB.isEHPad())
393 continue;
394 Changed = true;
395
396 // Insert stack pointer restoring instructions at the beginning of each EH
397 // pad, after the catch instruction. Here it is safe to assume that SP32
398 // holds the latest value of the stack pointer, because the only exception
399 // for this case is when a function uses the red zone, but that only happens
400 // with leaf functions, and we don't restore the stack pointer in leaf
401 // functions anyway.
402 auto InsertPos = MBB.begin();
403 // Skip EH_LABELs in the beginning of an EH pad if present.
404 while (InsertPos != MBB.end() && InsertPos->isEHLabel())
405 InsertPos++;
406 assert(InsertPos != MBB.end() &&
407 WebAssembly::isCatch(InsertPos->getOpcode()) &&
408 "catch/catch_all should be present in every EH pad at this point");
409 ++InsertPos; // Skip the catch instruction
410 FrameLowering->writeBackSP(SrcReg: FrameLowering->getSPReg(MF), MF, MBB, InsertStore&: InsertPos,
411 DL: MBB.begin()->getDebugLoc());
412 }
413 return Changed;
414}
415