| 1 | //===-- BPFUnwind.cpp - Lower unwinding to unwind_goto and unwind_exit ----===// |
| 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 | // There are two ways to leave a frame, and a call that may unwind is followed |
| 10 | // by an insn that tells them apart: |
| 11 | // ret exit |
| 12 | // invoke f() unwind pad call f; unwind_goto pad |
| 13 | // resume r0 = 0; unwind_exit |
| 14 | // call llvm.bpf.unwind.exit r0 = 0; unwind_exit |
| 15 | // invoke llvm.bpf.unwind.exit goto pad |
| 16 | // unwind_goto is taken when the callee left with unwind_exit. No register says |
| 17 | // so: how one insn tells the other is up to the JIT. Otherwise unwind_exit is |
| 18 | // exit, hence r0, and r2 as well in a function that returns more than 8 bytes. |
| 19 | // A pad expects the exception object in r0. There is none, so a pad that looks |
| 20 | // at it starts with r0 = 0. |
| 21 | // |
| 22 | // There is no unwinder library. A runtime starts an unwind by calling |
| 23 | // llvm.bpf.unwind.exit, which leaves the frame with unwind_exit. resume, which |
| 24 | // continues an unwind into the caller, does the same, so BPFUnwindPrepare |
| 25 | // replaces it with the intrinsic. |
| 26 | // |
| 27 | // There are no tables and nothing for a loader to do. |
| 28 | // |
| 29 | //===----------------------------------------------------------------------===// |
| 30 | |
| 31 | #include "BPF.h" |
| 32 | #include "BPFSubtarget.h" |
| 33 | #include "llvm/ADT/DepthFirstIterator.h" |
| 34 | #include "llvm/ADT/SetVector.h" |
| 35 | #include "llvm/CodeGen/LivePhysRegs.h" |
| 36 | #include "llvm/CodeGen/MachineFunctionPass.h" |
| 37 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
| 38 | #include "llvm/IR/DiagnosticInfo.h" |
| 39 | #include "llvm/IR/IRBuilder.h" |
| 40 | #include "llvm/IR/InstIterator.h" |
| 41 | #include "llvm/IR/IntrinsicInst.h" |
| 42 | #include "llvm/IR/IntrinsicsBPF.h" |
| 43 | #include "llvm/IR/Module.h" |
| 44 | #include "llvm/Transforms/Utils/Local.h" |
| 45 | |
| 46 | using namespace llvm; |
| 47 | |
| 48 | /// Not being nounwind is the default in IR, so that alone is not enough: |
| 49 | /// uwtable is how a frontend asks for unwinding through a function to work. |
| 50 | static bool canUnwind(const Function &F) { |
| 51 | return F.hasUWTable() && !F.doesNotThrow(); |
| 52 | } |
| 53 | |
| 54 | namespace { |
| 55 | |
| 56 | /// Turn resume into llvm.bpf.unwind.exit, and calls that may unwind into |
| 57 | /// invokes. |
| 58 | struct BPFUnwindPrepare : public ModulePass { |
| 59 | static char ID; |
| 60 | BPFUnwindPrepare() : ModulePass(ID) {} |
| 61 | StringRef getPassName() const override { return "BPF Unwind Prepare" ; } |
| 62 | |
| 63 | Function *UnwindExit = nullptr; |
| 64 | |
| 65 | Function *getUnwindExit(Module &M) { |
| 66 | if (!UnwindExit) |
| 67 | UnwindExit = |
| 68 | Intrinsic::getOrInsertDeclaration(M: &M, id: Intrinsic::bpf_unwind_exit); |
| 69 | return UnwindExit; |
| 70 | } |
| 71 | |
| 72 | static bool mayUnwind(const Instruction &I) { |
| 73 | const auto *CB = dyn_cast<CallBase>(Val: &I); |
| 74 | return CB && !CB->doesNotThrow() && !CB->isInlineAsm() && |
| 75 | !isa<IntrinsicInst>(Val: CB); |
| 76 | } |
| 77 | |
| 78 | bool runOnModule(Module &M) override { |
| 79 | bool Changed = false; |
| 80 | LLVMContext &C = M.getContext(); |
| 81 | UnwindExit = nullptr; |
| 82 | |
| 83 | for (Function &F : M) { |
| 84 | if (F.isDeclaration()) |
| 85 | continue; |
| 86 | |
| 87 | // Replace resume even if F cannot unwind, so BPFUnwindLower reports it. |
| 88 | for (BasicBlock &BB : F) { |
| 89 | if (auto *RI = dyn_cast<ResumeInst>(Val: BB.getTerminator())) { |
| 90 | CallInst::Create(Func: getUnwindExit(M), NameStr: "" , InsertBefore: RI->getIterator()) |
| 91 | ->setDebugLoc(RI->getDebugLoc()); |
| 92 | changeToUnreachable(I: RI); |
| 93 | Changed = true; |
| 94 | } |
| 95 | } |
| 96 | |
| 97 | if (!canUnwind(F)) |
| 98 | continue; |
| 99 | SmallVector<CallInst *, 8> Calls; |
| 100 | for (Instruction &I : instructions(F)) { |
| 101 | if (isa<CallInst>(Val: I) && mayUnwind(I)) |
| 102 | Calls.push_back(Elt: cast<CallInst>(Val: &I)); |
| 103 | } |
| 104 | |
| 105 | if (Calls.empty()) |
| 106 | continue; |
| 107 | |
| 108 | if (!F.hasPersonalityFn()) |
| 109 | F.setPersonalityFn(cast<Constant>( |
| 110 | Val: M.getOrInsertFunction(Name: "__gcc_personality_v0" , |
| 111 | T: FunctionType::get(Result: Type::getInt32Ty(C), isVarArg: true)) |
| 112 | .getCallee())); |
| 113 | BasicBlock *Pad = BasicBlock::Create(Context&: C, Name: "unwind.resume" , Parent: &F); |
| 114 | IRBuilder<> B(Pad); |
| 115 | LandingPadInst *LP = B.CreateLandingPad( |
| 116 | Ty: StructType::get(elt1: PointerType::getUnqual(C), elts: Type::getInt32Ty(C)), NumClauses: 0); |
| 117 | LP->setCleanup(true); |
| 118 | B.CreateCall(Callee: getUnwindExit(M)); |
| 119 | B.CreateUnreachable(); |
| 120 | for (CallInst *CI : Calls) |
| 121 | changeToInvokeAndSplitBasicBlock(CI, UnwindEdge: Pad); |
| 122 | Changed = true; |
| 123 | } |
| 124 | return Changed; |
| 125 | } |
| 126 | }; |
| 127 | |
| 128 | /// After register allocation, turn edges to landing pads into branches. |
| 129 | struct BPFUnwindLower : public MachineFunctionPass { |
| 130 | static char ID; |
| 131 | BPFUnwindLower() : MachineFunctionPass(ID) {} |
| 132 | StringRef getPassName() const override { return "BPF Unwind Lower" ; } |
| 133 | |
| 134 | /// Nothing after \p MI in its block runs: \p Succ, if any, is what follows. |
| 135 | static void endBlockAfter(MachineInstr &MI, MachineBasicBlock *Succ) { |
| 136 | MachineBasicBlock &MBB = *MI.getParent(); |
| 137 | MBB.erase(I: std::next(x: MI.getIterator()), E: MBB.end()); |
| 138 | while (!MBB.succ_empty()) |
| 139 | MBB.removeSuccessor(I: MBB.succ_begin()); |
| 140 | if (Succ) |
| 141 | MBB.addSuccessor(Succ); |
| 142 | } |
| 143 | |
| 144 | static const char *unsupported(const MachineFunction &MF) { |
| 145 | if (MF.getLandingPads().empty()) |
| 146 | return nullptr; |
| 147 | // Not canUnwind(): a function that catches everything is nounwind. |
| 148 | if (!MF.getFunction().hasUWTable()) |
| 149 | return "BPF needs uwtable on a function with a landing pad" ; |
| 150 | // Every pad is a catch-all: the branch is taken whatever was thrown. |
| 151 | for (const LandingPadInfo &LP : MF.getLandingPads()) { |
| 152 | for (int TId : LP.TypeIds) { |
| 153 | if (TId > 0 && MF.getTypeInfos()[TId - 1]) |
| 154 | return "BPF does not support type-specific exception catches yet" ; |
| 155 | // An empty filter lets nothing through, so it is a catch-all too. rustc |
| 156 | // guards every function that must not unwind with one. |
| 157 | if (TId < 0 && MF.getFilterIds()[-1 - TId]) |
| 158 | return "BPF does not support exception filters yet" ; |
| 159 | } |
| 160 | } |
| 161 | return nullptr; |
| 162 | } |
| 163 | |
| 164 | bool runOnMachineFunction(MachineFunction &MF) override { |
| 165 | const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo(); |
| 166 | const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); |
| 167 | DenseMap<MCSymbol *, MachineBasicBlock *> Begin; |
| 168 | SmallVector<std::pair<MachineInstr *, MachineBasicBlock *>, 8> Sites; |
| 169 | SmallVector<MachineInstr *, 8> Labels, Resumes; |
| 170 | SmallSetVector<MachineBasicBlock *, 8> Pads; |
| 171 | |
| 172 | const char *Msg = unsupported(MF); |
| 173 | if (Msg) { |
| 174 | const Function &F = MF.getFunction(); |
| 175 | F.getContext().diagnose(DI: DiagnosticInfoUnsupported(F, Msg)); |
| 176 | } |
| 177 | |
| 178 | for (const LandingPadInfo &LP : MF.getLandingPads()) |
| 179 | for (MCSymbol *Sym : LP.BeginLabels) |
| 180 | Begin[Sym] = LP.LandingPadBlock; |
| 181 | |
| 182 | // The call is not always in the block of the label: an argument that is |
| 183 | // a select is computed after the label and takes blocks of its own. |
| 184 | SmallPtrSet<MachineInstr *, 8> Invokes; |
| 185 | for (MachineBasicBlock &MBB : MF) { |
| 186 | for (MachineInstr &Label : MBB) { |
| 187 | if (!Label.isEHLabel()) |
| 188 | continue; |
| 189 | Labels.push_back(Elt: &Label); |
| 190 | MachineBasicBlock *Pad = |
| 191 | Begin.lookup(Val: Label.getOperand(i: 0).getMCSymbol()); |
| 192 | if (!Pad) |
| 193 | continue; |
| 194 | SmallVector<std::pair<MachineBasicBlock *, MachineBasicBlock::iterator>, |
| 195 | 4> |
| 196 | Work{{&MBB, std::next(x: Label.getIterator())}}; |
| 197 | SmallPtrSet<MachineBasicBlock *, 4> Seen; |
| 198 | while (!Work.empty()) { |
| 199 | auto [Cur, I] = Work.pop_back_val(); |
| 200 | // The next label ends the range. |
| 201 | for (; I != Cur->end() && !I->isEHLabel(); ++I) |
| 202 | if (I->isCall() && Invokes.insert(Ptr: &*I).second) |
| 203 | Sites.push_back(Elt: {&*I, Pad}); |
| 204 | if (I != Cur->end()) |
| 205 | continue; |
| 206 | for (MachineBasicBlock *Succ : Cur->successors()) |
| 207 | if (!Succ->isEHPad() && Seen.insert(Ptr: Succ).second) |
| 208 | Work.push_back(Elt: {Succ, Succ->begin()}); |
| 209 | } |
| 210 | } |
| 211 | } |
| 212 | for (MachineBasicBlock &MBB : MF) |
| 213 | for (MachineInstr &MI : MBB) |
| 214 | if (MI.getOpcode() == BPF::UNWIND_EXIT_PSEUDO && !Invokes.count(Ptr: &MI)) |
| 215 | Resumes.push_back(Elt: &MI); |
| 216 | if (Labels.empty() && Resumes.empty()) |
| 217 | return false; |
| 218 | // There is no unwind_goto after the calls of it. |
| 219 | if (!Msg && !Resumes.empty() && !canUnwind(F: MF.getFunction())) { |
| 220 | const Function &F = MF.getFunction(); |
| 221 | F.getContext().diagnose(DI: DiagnosticInfoUnsupported( |
| 222 | F, "BPF cannot unwind out of a function that is nounwind or has no " |
| 223 | "uwtable" )); |
| 224 | } |
| 225 | for (MachineInstr *MI : Labels) |
| 226 | MI->eraseFromParent(); |
| 227 | |
| 228 | for (auto [Call, Pad] : Sites) { |
| 229 | MachineBasicBlock *MBB = Call->getParent(); |
| 230 | DebugLoc DL = Call->getDebugLoc(); |
| 231 | const auto *II = |
| 232 | dyn_cast_or_null<InvokeInst>(Val: MBB->getBasicBlock()->getTerminator()); |
| 233 | |
| 234 | Pads.insert(X: Pad); |
| 235 | if (Call->getOpcode() == BPF::UNWIND_EXIT_PSEUDO) { |
| 236 | endBlockAfter(MI&: *Call, Succ: Pad); |
| 237 | BuildMI(BB: MBB, MIMD: DL, MCID: TII.get(Opcode: BPF::JMP)).addMBB(MBB: Pad); |
| 238 | Call->eraseFromParent(); |
| 239 | } else if (II && II->doesNotReturn()) { |
| 240 | // Nothing sensible follows the call, but something has to. |
| 241 | endBlockAfter(MI&: *Call, Succ: Pad); |
| 242 | BuildMI(BB: MBB, MIMD: DL, MCID: TII.get(Opcode: BPF::UNWIND_GOTO)).addMBB(MBB: Pad); |
| 243 | BuildMI(BB: MBB, MIMD: DL, MCID: TII.get(Opcode: BPF::JMP)).addMBB(MBB: Pad); |
| 244 | } else { |
| 245 | MachineBasicBlock *Rest = MBB->splitAt(SplitInst&: *Call); |
| 246 | if (Rest != MBB) { |
| 247 | Rest->removeSuccessor(Succ: Pad); |
| 248 | MBB->addSuccessor(Succ: Pad); |
| 249 | } |
| 250 | BuildMI(BB: MBB, MIMD: DL, MCID: TII.get(Opcode: BPF::UNWIND_GOTO)).addMBB(MBB: Pad); |
| 251 | } |
| 252 | } |
| 253 | |
| 254 | for (MachineBasicBlock *Pad : Pads) { |
| 255 | LivePhysRegs Live(TRI); |
| 256 | Live.addLiveOuts(MBB: *Pad); |
| 257 | for (MachineInstr &MI : reverse(C&: *Pad)) |
| 258 | Live.stepBackward(MI); |
| 259 | if (!Live.available(MRI: MF.getRegInfo(), Reg: BPF::R0)) |
| 260 | BuildMI(BB&: *Pad, I: Pad->begin(), MIMD: DebugLoc(), MCID: TII.get(Opcode: BPF::MOV_ri), DestReg: BPF::R0) |
| 261 | .addImm(Val: 0); |
| 262 | Pad->removeLiveIn(Reg: BPF::R0); |
| 263 | } |
| 264 | |
| 265 | // unwind_exit returns what exit returns: a value of more than 8 bytes is in |
| 266 | // r0 and r2. |
| 267 | SmallVector<ISD::OutputArg, 2> Outs; |
| 268 | const Function &F = MF.getFunction(); |
| 269 | GetReturnInfo(CC: F.getCallingConv(), ReturnType: F.getReturnType(), attr: F.getAttributes(), |
| 270 | Outs, TLI: *MF.getSubtarget().getTargetLowering(), |
| 271 | DL: MF.getDataLayout()); |
| 272 | |
| 273 | for (MachineInstr *Call : Resumes) { |
| 274 | MachineBasicBlock *MBB = Call->getParent(); |
| 275 | DebugLoc DL = Call->getDebugLoc(); |
| 276 | |
| 277 | BuildMI(BB&: *MBB, I: Call, MIMD: DL, MCID: TII.get(Opcode: BPF::MOV_ri), DestReg: BPF::R0).addImm(Val: 0); |
| 278 | MachineInstrBuilder Exit = |
| 279 | BuildMI(BB&: *MBB, I: Call, MIMD: DL, MCID: TII.get(Opcode: BPF::UNWIND_EXIT)) |
| 280 | .addReg(RegNo: BPF::R0, Flags: RegState::Implicit); |
| 281 | if (Outs.size() > 1) { |
| 282 | BuildMI(BB&: *MBB, I&: *Exit, MIMD: DL, MCID: TII.get(Opcode: BPF::MOV_ri), DestReg: BPF::R2).addImm(Val: 0); |
| 283 | Exit.addReg(RegNo: BPF::R2, Flags: RegState::Implicit); |
| 284 | } |
| 285 | endBlockAfter(MI&: *Exit, Succ: nullptr); |
| 286 | } |
| 287 | |
| 288 | // The pads are plain blocks now and there is no table to emit. |
| 289 | for (MachineBasicBlock &MBB : MF) |
| 290 | MBB.setIsEHPad(false); |
| 291 | MF.clearLandingPads(); |
| 292 | |
| 293 | // What was behind a call that does not return. It can be a loop. |
| 294 | df_iterator_default_set<MachineBasicBlock *> Reachable; |
| 295 | for (MachineBasicBlock *MBB : depth_first_ext(G: &MF, S&: Reachable)) |
| 296 | (void)MBB; |
| 297 | for (MachineBasicBlock &MBB : make_early_inc_range(Range&: MF)) { |
| 298 | if (Reachable.count(Ptr: &MBB) || MBB.hasAddressTaken()) |
| 299 | continue; |
| 300 | while (!MBB.succ_empty()) |
| 301 | MBB.removeSuccessor(I: MBB.succ_begin()); |
| 302 | MBB.eraseFromParent(); |
| 303 | } |
| 304 | for (MachineBasicBlock &MBB : MF) |
| 305 | if (!MBB.empty() && MBB.back().getOpcode() == BPF::JMP && |
| 306 | MBB.isLayoutSuccessor(MBB: MBB.back().getOperand(i: 0).getMBB())) |
| 307 | MBB.back().eraseFromParent(); |
| 308 | return true; |
| 309 | } |
| 310 | }; |
| 311 | |
| 312 | } // namespace |
| 313 | |
| 314 | char BPFUnwindPrepare::ID = 0; |
| 315 | char BPFUnwindLower::ID = 0; |
| 316 | |
| 317 | INITIALIZE_PASS(BPFUnwindPrepare, "bpf-unwind-prepare" , "BPF Unwind Prepare" , |
| 318 | false, false) |
| 319 | INITIALIZE_PASS(BPFUnwindLower, "bpf-unwind-lower" , "BPF Unwind Lower" , false, |
| 320 | false) |
| 321 | |
| 322 | ModulePass *llvm::createBPFUnwindPreparePass() { |
| 323 | return new BPFUnwindPrepare(); |
| 324 | } |
| 325 | FunctionPass *llvm::createBPFUnwindLowerPass() { return new BPFUnwindLower(); } |
| 326 | |