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
46using 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.
50static bool canUnwind(const Function &F) {
51 return F.hasUWTable() && !F.doesNotThrow();
52}
53
54namespace {
55
56/// Turn resume into llvm.bpf.unwind.exit, and calls that may unwind into
57/// invokes.
58struct 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.
129struct 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
314char BPFUnwindPrepare::ID = 0;
315char BPFUnwindLower::ID = 0;
316
317INITIALIZE_PASS(BPFUnwindPrepare, "bpf-unwind-prepare", "BPF Unwind Prepare",
318 false, false)
319INITIALIZE_PASS(BPFUnwindLower, "bpf-unwind-lower", "BPF Unwind Lower", false,
320 false)
321
322ModulePass *llvm::createBPFUnwindPreparePass() {
323 return new BPFUnwindPrepare();
324}
325FunctionPass *llvm::createBPFUnwindLowerPass() { return new BPFUnwindLower(); }
326