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 replaceFuncletReturns(MachineFunction &MF); 41 bool removeUnnecessaryUnreachables(MachineFunction &MF); 42 bool restoreStackPointer(MachineFunction &MF); 43 44 MachineBasicBlock *getMatchingEHPad(MachineInstr *MI); 45 SmallPtrSet<MachineBasicBlock *, 8> CatchRetBBs; 46 47 public: 48 static char ID; // Pass identification, replacement for typeid 49 WebAssemblyLateEHPrepare() : MachineFunctionPass(ID) {} 50 }; 51 } // end anonymous namespace 52 53 char WebAssemblyLateEHPrepare::ID = 0; 54 INITIALIZE_PASS(WebAssemblyLateEHPrepare, DEBUG_TYPE, 55 "WebAssembly Late Exception Preparation", false, false) 56 57 FunctionPass *llvm::createWebAssemblyLateEHPrepare() { 58 return new WebAssemblyLateEHPrepare(); 59 } 60 61 // Returns the nearest EH pad that dominates this instruction. This does not use 62 // dominator analysis; it just does BFS on its predecessors until arriving at an 63 // EH pad. This assumes valid EH scopes so the first EH pad it arrives in all 64 // possible search paths should be the same. 65 // Returns nullptr in case it does not find any EH pad in the search, or finds 66 // multiple different EH pads. 67 MachineBasicBlock * 68 WebAssemblyLateEHPrepare::getMatchingEHPad(MachineInstr *MI) { 69 MachineFunction *MF = MI->getParent()->getParent(); 70 SmallVector<MachineBasicBlock *, 2> WL; 71 SmallPtrSet<MachineBasicBlock *, 2> Visited; 72 WL.push_back(MI->getParent()); 73 MachineBasicBlock *EHPad = nullptr; 74 while (!WL.empty()) { 75 MachineBasicBlock *MBB = WL.pop_back_val(); 76 if (!Visited.insert(MBB).second) 77 continue; 78 if (MBB->isEHPad()) { 79 if (EHPad && EHPad != MBB) 80 return nullptr; 81 EHPad = MBB; 82 continue; 83 } 84 if (MBB == &MF->front()) 85 return nullptr; 86 for (auto *Pred : MBB->predecessors()) 87 if (!CatchRetBBs.count(Pred)) // We don't go into child scopes 88 WL.push_back(Pred); 89 } 90 return EHPad; 91 } 92 93 // Erase the specified BBs if the BB does not have any remaining predecessors, 94 // and also all its dead children. 95 template <typename Container> 96 static void eraseDeadBBsAndChildren(const Container &MBBs) { 97 SmallVector<MachineBasicBlock *, 8> WL(MBBs.begin(), MBBs.end()); 98 SmallPtrSet<MachineBasicBlock *, 8> Deleted; 99 while (!WL.empty()) { 100 MachineBasicBlock *MBB = WL.pop_back_val(); 101 if (Deleted.count(MBB) || !MBB->pred_empty()) 102 continue; 103 SmallVector<MachineBasicBlock *, 4> Succs(MBB->successors()); 104 WL.append(MBB->succ_begin(), MBB->succ_end()); 105 for (auto *Succ : Succs) 106 MBB->removeSuccessor(Succ); 107 // To prevent deleting the same BB multiple times, which can happen when 108 // 'MBBs' contain both a parent and a child 109 Deleted.insert(MBB); 110 MBB->eraseFromParent(); 111 } 112 } 113 114 bool WebAssemblyLateEHPrepare::runOnMachineFunction(MachineFunction &MF) { 115 LLVM_DEBUG(dbgs() << "********** Late EH Prepare **********\n" 116 "********** Function: " 117 << MF.getName() << '\n'); 118 119 if (MF.getTarget().getMCAsmInfo()->getExceptionHandlingType() != 120 ExceptionHandling::Wasm) 121 return false; 122 123 bool Changed = false; 124 if (MF.getFunction().hasPersonalityFn()) { 125 Changed |= removeUnreachableEHPads(MF); 126 recordCatchRetBBs(MF); 127 Changed |= hoistCatches(MF); 128 Changed |= addCatchAlls(MF); 129 Changed |= replaceFuncletReturns(MF); 130 } 131 Changed |= removeUnnecessaryUnreachables(MF); 132 if (MF.getFunction().hasPersonalityFn()) 133 Changed |= restoreStackPointer(MF); 134 return Changed; 135 } 136 137 // Remove unreachable EH pads and its children. If they remain, CFG 138 // stackification can be tricky. 139 bool WebAssemblyLateEHPrepare::removeUnreachableEHPads(MachineFunction &MF) { 140 SmallVector<MachineBasicBlock *, 4> ToDelete; 141 for (auto &MBB : MF) 142 if (MBB.isEHPad() && MBB.pred_empty()) 143 ToDelete.push_back(&MBB); 144 eraseDeadBBsAndChildren(ToDelete); 145 return !ToDelete.empty(); 146 } 147 148 // Record which BB ends with catchret instruction, because this will be replaced 149 // with 'br's later. This set of catchret BBs is necessary in 'getMatchingEHPad' 150 // function. 151 void WebAssemblyLateEHPrepare::recordCatchRetBBs(MachineFunction &MF) { 152 CatchRetBBs.clear(); 153 for (auto &MBB : MF) { 154 auto Pos = MBB.getFirstTerminator(); 155 if (Pos == MBB.end()) 156 continue; 157 MachineInstr *TI = &*Pos; 158 if (TI->getOpcode() == WebAssembly::CATCHRET) 159 CatchRetBBs.insert(&MBB); 160 } 161 } 162 163 // Hoist catch instructions to the beginning of their matching EH pad BBs in 164 // case, 165 // (1) catch instruction is not the first instruction in EH pad. 166 // ehpad: 167 // some_other_instruction 168 // ... 169 // %exn = catch 0 170 // (2) catch instruction is in a non-EH pad BB. For example, 171 // ehpad: 172 // br bb0 173 // bb0: 174 // %exn = catch 0 175 bool WebAssemblyLateEHPrepare::hoistCatches(MachineFunction &MF) { 176 bool Changed = false; 177 SmallVector<MachineInstr *, 16> Catches; 178 for (auto &MBB : MF) 179 for (auto &MI : MBB) 180 if (WebAssembly::isCatch(MI.getOpcode())) 181 Catches.push_back(&MI); 182 183 for (auto *Catch : Catches) { 184 MachineBasicBlock *EHPad = getMatchingEHPad(Catch); 185 assert(EHPad && "No matching EH pad for catch"); 186 auto InsertPos = EHPad->begin(); 187 // Skip EH_LABELs in the beginning of an EH pad if present. We don't use 188 // these labels at the moment, but other targets also seem to have an 189 // EH_LABEL instruction in the beginning of an EH pad. 190 while (InsertPos != EHPad->end() && InsertPos->isEHLabel()) 191 InsertPos++; 192 if (InsertPos == Catch) 193 continue; 194 Changed = true; 195 EHPad->insert(InsertPos, Catch->removeFromParent()); 196 } 197 return Changed; 198 } 199 200 // Add catch_all to beginning of cleanup pads. 201 bool WebAssemblyLateEHPrepare::addCatchAlls(MachineFunction &MF) { 202 bool Changed = false; 203 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 204 205 for (auto &MBB : MF) { 206 if (!MBB.isEHPad()) 207 continue; 208 auto InsertPos = MBB.begin(); 209 // Skip EH_LABELs in the beginning of an EH pad if present. 210 while (InsertPos != MBB.end() && InsertPos->isEHLabel()) 211 InsertPos++; 212 // This runs after hoistCatches(), so we assume that if there is a catch, 213 // that should be the first non-EH-label instruction in an EH pad. 214 if (InsertPos == MBB.end() || 215 !WebAssembly::isCatch(InsertPos->getOpcode())) { 216 Changed = true; 217 BuildMI(MBB, InsertPos, 218 InsertPos == MBB.end() ? DebugLoc() : InsertPos->getDebugLoc(), 219 TII.get(WebAssembly::CATCH_ALL)); 220 } 221 } 222 return Changed; 223 } 224 225 // Replace pseudo-instructions catchret and cleanupret with br and rethrow 226 // respectively. 227 bool WebAssemblyLateEHPrepare::replaceFuncletReturns(MachineFunction &MF) { 228 bool Changed = false; 229 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 230 231 for (auto &MBB : MF) { 232 auto Pos = MBB.getFirstTerminator(); 233 if (Pos == MBB.end()) 234 continue; 235 MachineInstr *TI = &*Pos; 236 237 switch (TI->getOpcode()) { 238 case WebAssembly::CATCHRET: { 239 // Replace a catchret with a branch 240 MachineBasicBlock *TBB = TI->getOperand(0).getMBB(); 241 if (!MBB.isLayoutSuccessor(TBB)) 242 BuildMI(MBB, TI, TI->getDebugLoc(), TII.get(WebAssembly::BR)) 243 .addMBB(TBB); 244 TI->eraseFromParent(); 245 Changed = true; 246 break; 247 } 248 case WebAssembly::CLEANUPRET: { 249 // Replace a cleanupret with a rethrow. For C++ support, currently 250 // rethrow's immediate argument is always 0 (= the latest exception). 251 BuildMI(MBB, TI, TI->getDebugLoc(), TII.get(WebAssembly::RETHROW)) 252 .addImm(0); 253 TI->eraseFromParent(); 254 Changed = true; 255 break; 256 } 257 } 258 } 259 return Changed; 260 } 261 262 // Remove unnecessary unreachables after a throw or rethrow. 263 bool WebAssemblyLateEHPrepare::removeUnnecessaryUnreachables( 264 MachineFunction &MF) { 265 bool Changed = false; 266 for (auto &MBB : MF) { 267 for (auto &MI : MBB) { 268 if (MI.getOpcode() != WebAssembly::THROW && 269 MI.getOpcode() != WebAssembly::RETHROW) 270 continue; 271 Changed = true; 272 273 // The instruction after the throw should be an unreachable or a branch to 274 // another BB that should eventually lead to an unreachable. Delete it 275 // because throw itself is a terminator, and also delete successors if 276 // any. 277 MBB.erase(std::next(MI.getIterator()), MBB.end()); 278 SmallVector<MachineBasicBlock *, 8> Succs(MBB.successors()); 279 for (auto *Succ : Succs) 280 if (!Succ->isEHPad()) 281 MBB.removeSuccessor(Succ); 282 eraseDeadBBsAndChildren(Succs); 283 } 284 } 285 286 return Changed; 287 } 288 289 // After the stack is unwound due to a thrown exception, the __stack_pointer 290 // global can point to an invalid address. This inserts instructions that 291 // restore __stack_pointer global. 292 bool WebAssemblyLateEHPrepare::restoreStackPointer(MachineFunction &MF) { 293 const auto *FrameLowering = static_cast<const WebAssemblyFrameLowering *>( 294 MF.getSubtarget().getFrameLowering()); 295 if (!FrameLowering->needsPrologForEH(MF)) 296 return false; 297 bool Changed = false; 298 299 for (auto &MBB : MF) { 300 if (!MBB.isEHPad()) 301 continue; 302 Changed = true; 303 304 // Insert __stack_pointer restoring instructions at the beginning of each EH 305 // pad, after the catch instruction. Here it is safe to assume that SP32 306 // holds the latest value of __stack_pointer, because the only exception for 307 // this case is when a function uses the red zone, but that only happens 308 // with leaf functions, and we don't restore __stack_pointer in leaf 309 // functions anyway. 310 auto InsertPos = MBB.begin(); 311 // Skip EH_LABELs in the beginning of an EH pad if present. 312 while (InsertPos != MBB.end() && InsertPos->isEHLabel()) 313 InsertPos++; 314 assert(InsertPos != MBB.end() && 315 WebAssembly::isCatch(InsertPos->getOpcode()) && 316 "catch/catch_all should be present in every EH pad at this point"); 317 ++InsertPos; // Skip the catch instruction 318 FrameLowering->writeSPToGlobal(FrameLowering->getSPReg(MF), MF, MBB, 319 InsertPos, MBB.begin()->getDebugLoc()); 320 } 321 return Changed; 322 } 323