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"
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 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(i: 0).getMBB()].push_back(Elt: &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(RegClass: &WebAssembly::EXNREFRegClass);
317 if (Catch->getOpcode() == WebAssembly::CATCH) {
318 MachineInstrBuilder MIB = BuildMI(BB&: *EHPad, I: InsertPos, MIMD: Catch->getDebugLoc(),
319 MCID: TII.get(Opcode: 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(RegNo: Def.getReg());
323 MIB.addDef(RegNo: 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(FnName: Use.getSymbolName());
328 break;
329 }
330 } else if (Catch->getOpcode() == WebAssembly::CATCH_ALL) {
331 BuildMI(BB&: *EHPad, I: InsertPos, MIMD: Catch->getDebugLoc(),
332 MCID: TII.get(Opcode: WebAssembly::CATCH_ALL_REF))
333 .addDef(RegNo: ExnReg);
334 } else {
335 assert(false);
336 }
337 Catch->eraseFromParent();
338
339 for (auto *Rethrow : Rethrows) {
340 auto InsertPos = std::next(x: Rethrow->getIterator());
341 BuildMI(BB&: *Rethrow->getParent(), I: InsertPos, MIMD: Rethrow->getDebugLoc(),
342 MCID: TII.get(Opcode: WebAssembly::THROW_REF))
343 .addReg(RegNo: ExnReg);
344 Rethrow->eraseFromParent();
345 }
346 }
347
348 return true;
349}
350
351// Remove unnecessary unreachables after a throw/rethrow/throw_ref.
352bool 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(I: std::next(x: MI.getIterator()), E: MBB.end());
368 SmallVector<MachineBasicBlock *, 8> Succs(MBB.successors());
369 for (auto *Succ : Succs)
370 if (!Succ->isEHPad())
371 MBB.removeSuccessor(Succ);
372 eraseDeadBBsAndChildren(MBBs: 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.
382bool 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(SrcReg: FrameLowering->getSPReg(MF), MF, MBB,
409 InsertStore&: InsertPos, DL: MBB.begin()->getDebugLoc());
410 }
411 return Changed;
412}
413