1//===-------------- BPFMIPeephole.cpp - MI Peephole Cleanups -------------===//
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// This pass performs peephole optimizations to cleanup ugly code sequences at
10// MachineInstruction layer.
11//
12// Currently, there are two optimizations implemented:
13// - One pre-RA MachineSSA pass to eliminate type promotion sequences, those
14// zero extend 32-bit subregisters to 64-bit registers, if the compiler
15// could prove the subregisters is defined by 32-bit operations in which
16// case the upper half of the underlying 64-bit registers were zeroed
17// implicitly.
18//
19// - One post-RA PreEmit pass to do final cleanup on some redundant
20// instructions generated due to bad RA on subregister.
21//===----------------------------------------------------------------------===//
22
23#include "BPF.h"
24#include "BPFInstrInfo.h"
25#include "BPFTargetMachine.h"
26#include "llvm/ADT/Statistic.h"
27#include "llvm/ADT/StringExtras.h"
28#include "llvm/CodeGen/LivePhysRegs.h"
29#include "llvm/CodeGen/MachineFrameInfo.h"
30#include "llvm/CodeGen/MachineFunction.h"
31#include "llvm/CodeGen/MachineFunctionAnalysisManager.h"
32#include "llvm/CodeGen/MachineFunctionPass.h"
33#include "llvm/CodeGen/MachineInstrBuilder.h"
34#include "llvm/CodeGen/MachinePassManager.h"
35#include "llvm/CodeGen/MachineRegisterInfo.h"
36#include "llvm/CodeGen/TargetInstrInfo.h"
37#include "llvm/IR/Analysis.h"
38#include "llvm/Support/Debug.h"
39#include <set>
40
41using namespace llvm;
42
43#define DEBUG_TYPE "bpf-mi-zext-elim"
44
45static cl::opt<int> GotolAbsLowBound("gotol-abs-low-bound", cl::Hidden,
46 cl::init(INT16_MAX >> 1), cl::desc("Specify gotol lower bound"));
47
48STATISTIC(ZExtElemNum, "Number of zero extension shifts eliminated");
49
50namespace {
51
52struct BPFMIPeepholeImpl {
53 const BPFInstrInfo *TII;
54 MachineFunction *MF;
55 MachineRegisterInfo *MRI;
56
57private:
58 // Initialize class variables.
59 void initialize(MachineFunction &MFParm);
60
61 bool isCopyFrom32Def(MachineInstr *CopyMI);
62 bool isInsnFrom32Def(MachineInstr *DefInsn);
63 bool isPhiFrom32Def(MachineInstr *MovMI);
64 bool isMovFrom32Def(MachineInstr *MovMI);
65 bool eliminateZExtSeq();
66 bool eliminateZExt();
67
68 std::set<MachineInstr *> PhiInsns;
69
70public:
71
72 // Main entry point for this pass.
73 bool runOnMachineFunction(MachineFunction &MF) {
74 initialize(MFParm&: MF);
75
76 // First try to eliminate (zext, lshift, rshift) and then
77 // try to eliminate zext.
78 bool ZExtSeqExist, ZExtExist;
79 ZExtSeqExist = eliminateZExtSeq();
80 ZExtExist = eliminateZExt();
81 return ZExtSeqExist || ZExtExist;
82 }
83};
84
85class BPFMIPeepholeLegacy : public MachineFunctionPass {
86public:
87 static char ID;
88 BPFMIPeepholeLegacy() : MachineFunctionPass(ID) {}
89 bool runOnMachineFunction(MachineFunction &MF) override;
90};
91
92// Initialize class variables.
93void BPFMIPeepholeImpl::initialize(MachineFunction &MFParm) {
94 MF = &MFParm;
95 MRI = &MF->getRegInfo();
96 TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
97 LLVM_DEBUG(dbgs() << "*** BPF MachineSSA ZEXT Elim peephole pass ***\n\n");
98}
99
100bool BPFMIPeepholeImpl::isCopyFrom32Def(MachineInstr *CopyMI) {
101 MachineOperand &opnd = CopyMI->getOperand(i: 1);
102
103 // Return false if getting value from a 32bit physical register.
104 // Most likely, this physical register is aliased to
105 // function call return value or current function parameters.
106 Register Reg = opnd.getReg();
107 if (!Reg.isVirtual())
108 return false;
109
110 if (MRI->getRegClass(Reg) == &BPF::GPRRegClass)
111 return false;
112
113 MachineInstr *DefInsn = MRI->getVRegDef(Reg);
114 if (!isInsnFrom32Def(DefInsn))
115 return false;
116
117 return true;
118}
119
120bool BPFMIPeepholeImpl::isPhiFrom32Def(MachineInstr *PhiMI) {
121 for (unsigned i = 1, e = PhiMI->getNumOperands(); i < e; i += 2) {
122 MachineOperand &opnd = PhiMI->getOperand(i);
123
124 MachineInstr *PhiDef = MRI->getVRegDef(Reg: opnd.getReg());
125 if (!PhiDef)
126 return false;
127 if (PhiDef->isPHI()) {
128 if (!PhiInsns.insert(x: PhiDef).second)
129 return false;
130 if (!isPhiFrom32Def(PhiMI: PhiDef))
131 return false;
132 }
133 if (PhiDef->getOpcode() == BPF::COPY && !isCopyFrom32Def(CopyMI: PhiDef))
134 return false;
135 }
136
137 return true;
138}
139
140// The \p DefInsn instruction defines a virtual register.
141bool BPFMIPeepholeImpl::isInsnFrom32Def(MachineInstr *DefInsn) {
142 if (!DefInsn)
143 return false;
144
145 if (DefInsn->isPHI()) {
146 if (!PhiInsns.insert(x: DefInsn).second)
147 return false;
148 if (!isPhiFrom32Def(PhiMI: DefInsn))
149 return false;
150 } else if (DefInsn->getOpcode() == BPF::COPY) {
151 if (!isCopyFrom32Def(CopyMI: DefInsn))
152 return false;
153 }
154
155 return true;
156}
157
158bool BPFMIPeepholeImpl::isMovFrom32Def(MachineInstr *MovMI)
159{
160 const MachineOperand &Src = MovMI->getOperand(i: 1);
161 if (Src.getSubReg())
162 return false;
163
164 MachineInstr *DefInsn = MRI->getVRegDef(Reg: Src.getReg());
165
166 LLVM_DEBUG(dbgs() << " Def of Mov Src:");
167 LLVM_DEBUG(DefInsn->dump());
168
169 PhiInsns.clear();
170 if (!isInsnFrom32Def(DefInsn))
171 return false;
172
173 LLVM_DEBUG(dbgs() << " One ZExt elim sequence identified.\n");
174
175 return true;
176}
177
178bool BPFMIPeepholeImpl::eliminateZExtSeq() {
179 MachineInstr* ToErase = nullptr;
180 bool Eliminated = false;
181
182 for (MachineBasicBlock &MBB : *MF) {
183 for (MachineInstr &MI : MBB) {
184 // If the previous instruction was marked for elimination, remove it now.
185 if (ToErase) {
186 ToErase->eraseFromParent();
187 ToErase = nullptr;
188 }
189
190 // Eliminate the 32-bit to 64-bit zero extension sequence when possible.
191 //
192 // MOV_32_64 rB, wA
193 // SLL_ri rB, rB, 32
194 // SRL_ri rB, rB, 32
195 if (MI.getOpcode() == BPF::SRL_ri &&
196 MI.getOperand(i: 2).getImm() == 32) {
197 Register DstReg = MI.getOperand(i: 0).getReg();
198 Register ShfReg = MI.getOperand(i: 1).getReg();
199 MachineInstr *SllMI = MRI->getVRegDef(Reg: ShfReg);
200
201 LLVM_DEBUG(dbgs() << "Starting SRL found:");
202 LLVM_DEBUG(MI.dump());
203
204 if (!SllMI ||
205 SllMI->isPHI() ||
206 SllMI->getOpcode() != BPF::SLL_ri ||
207 SllMI->getOperand(i: 2).getImm() != 32)
208 continue;
209
210 LLVM_DEBUG(dbgs() << " SLL found:");
211 LLVM_DEBUG(SllMI->dump());
212
213 MachineInstr *MovMI = MRI->getVRegDef(Reg: SllMI->getOperand(i: 1).getReg());
214 if (!MovMI ||
215 MovMI->isPHI() ||
216 MovMI->getOpcode() != BPF::MOV_32_64)
217 continue;
218
219 LLVM_DEBUG(dbgs() << " Type cast Mov found:");
220 LLVM_DEBUG(MovMI->dump());
221
222 Register SubReg = MovMI->getOperand(i: 1).getReg();
223 if (!isMovFrom32Def(MovMI)) {
224 LLVM_DEBUG(dbgs()
225 << " One ZExt elim sequence failed qualifying elim.\n");
226 continue;
227 }
228
229 BuildMI(BB&: MBB, I&: MI, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: BPF::SUBREG_TO_REG), DestReg: DstReg)
230 .addReg(RegNo: SubReg)
231 .addImm(Val: BPF::sub_32);
232
233 // The results of the mov and of the left shift can have other users.
234 if (MRI->hasOneNonDBGUse(RegNo: ShfReg)) {
235 bool MovIsDead = MRI->hasOneNonDBGUse(RegNo: MovMI->getOperand(i: 0).getReg());
236
237 SllMI->eraseFromParent();
238 if (MovIsDead)
239 MovMI->eraseFromParent();
240 }
241 // MI is the right shift, we can't erase it in it's own iteration.
242 // Mark it to ToErase, and erase in the next iteration.
243 ToErase = &MI;
244 ZExtElemNum++;
245 Eliminated = true;
246 }
247 }
248 }
249
250 return Eliminated;
251}
252
253bool BPFMIPeepholeImpl::eliminateZExt() {
254 MachineInstr* ToErase = nullptr;
255 bool Eliminated = false;
256
257 for (MachineBasicBlock &MBB : *MF) {
258 for (MachineInstr &MI : MBB) {
259 // If the previous instruction was marked for elimination, remove it now.
260 if (ToErase) {
261 ToErase->eraseFromParent();
262 ToErase = nullptr;
263 }
264
265 if (MI.getOpcode() != BPF::MOV_32_64)
266 continue;
267
268 // Eliminate MOV_32_64 if possible.
269 // MOV_32_64 rA, wB
270 //
271 // If wB has been zero extended, replace it with a SUBREG_TO_REG.
272 // This is to workaround BPF programs where pkt->{data, data_end}
273 // is encoded as u32, but actually the verifier populates them
274 // as 64bit pointer. The MOV_32_64 will zero out the top 32 bits.
275 LLVM_DEBUG(dbgs() << "Candidate MOV_32_64 instruction:");
276 LLVM_DEBUG(MI.dump());
277
278 if (!isMovFrom32Def(MovMI: &MI))
279 continue;
280
281 LLVM_DEBUG(dbgs() << "Removing the MOV_32_64 instruction\n");
282
283 Register dst = MI.getOperand(i: 0).getReg();
284 Register src = MI.getOperand(i: 1).getReg();
285
286 // Build a SUBREG_TO_REG instruction.
287 BuildMI(BB&: MBB, I&: MI, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: BPF::SUBREG_TO_REG), DestReg: dst)
288 .addReg(RegNo: src)
289 .addImm(Val: BPF::sub_32);
290
291 ToErase = &MI;
292 Eliminated = true;
293 }
294 }
295
296 return Eliminated;
297}
298
299} // end default namespace
300
301INITIALIZE_PASS(BPFMIPeepholeLegacy, DEBUG_TYPE,
302 "BPF MachineSSA Peephole Optimization For ZEXT Eliminate",
303 false, false)
304
305char BPFMIPeepholeLegacy::ID = 0;
306FunctionPass *llvm::createBPFMIPeepholeLegacyPass() {
307 return new BPFMIPeepholeLegacy();
308}
309
310bool BPFMIPeepholeLegacy::runOnMachineFunction(MachineFunction &MF) {
311 if (skipFunction(F: MF.getFunction()))
312 return false;
313
314 BPFMIPeepholeImpl Impl;
315 return Impl.runOnMachineFunction(MF);
316}
317
318PreservedAnalyses BPFMIPeepholePass::run(MachineFunction &MF,
319 MachineFunctionAnalysisManager &MFAM) {
320 BPFMIPeepholeImpl Impl;
321 return Impl.runOnMachineFunction(MF)
322 ? getMachineFunctionPassPreservedAnalyses()
323 .preserveSet<CFGAnalyses>()
324 : PreservedAnalyses::all();
325}
326
327STATISTIC(RedundantMovElemNum, "Number of redundant moves eliminated");
328
329namespace {
330
331struct BPFMIPreEmitPeepholeImpl {
332 MachineFunction *MF;
333 const TargetRegisterInfo *TRI;
334 const BPFInstrInfo *TII;
335 bool SupportGotol;
336
337private:
338 // Initialize class variables.
339 void initialize(MachineFunction &MFParm);
340
341 bool in16BitRange(int Num);
342 bool eliminateRedundantMov();
343 bool adjustBranch();
344 bool insertMissingCallerSavedSpills();
345 bool removeMayGotoZero();
346 bool addExitAfterUnreachable();
347
348public:
349
350 // Main entry point for this pass.
351 bool runOnMachineFunction(MachineFunction &MF) {
352 initialize(MFParm&: MF);
353 bool Changed = eliminateRedundantMov();
354 if (SupportGotol)
355 Changed |= adjustBranch();
356 Changed |= insertMissingCallerSavedSpills();
357 Changed |= removeMayGotoZero();
358 Changed |= addExitAfterUnreachable();
359 return Changed;
360 }
361};
362
363class BPFMIPreEmitPeepholeLegacy : public MachineFunctionPass {
364public:
365 static char ID;
366 BPFMIPreEmitPeepholeLegacy() : MachineFunctionPass(ID) {}
367 bool runOnMachineFunction(MachineFunction &MF) override;
368};
369
370// Initialize class variables.
371void BPFMIPreEmitPeepholeImpl::initialize(MachineFunction &MFParm) {
372 MF = &MFParm;
373 TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
374 TRI = MF->getSubtarget<BPFSubtarget>().getRegisterInfo();
375 SupportGotol = MF->getSubtarget<BPFSubtarget>().hasGotol();
376 LLVM_DEBUG(dbgs() << "*** BPF PreEmit peephole pass ***\n\n");
377}
378
379bool BPFMIPreEmitPeepholeImpl::eliminateRedundantMov() {
380 MachineInstr* ToErase = nullptr;
381 bool Eliminated = false;
382
383 for (MachineBasicBlock &MBB : *MF) {
384 for (MachineInstr &MI : MBB) {
385 // If the previous instruction was marked for elimination, remove it now.
386 if (ToErase) {
387 LLVM_DEBUG(dbgs() << " Redundant Mov Eliminated:");
388 LLVM_DEBUG(ToErase->dump());
389 ToErase->eraseFromParent();
390 ToErase = nullptr;
391 }
392
393 // Eliminate identical move:
394 //
395 // MOV rA, rA
396 //
397 // Note that we cannot remove
398 // MOV_32_64 rA, wA
399 // MOV_rr_32 wA, wA
400 // as these two instructions having side effects, zeroing out
401 // top 32 bits of rA.
402 unsigned Opcode = MI.getOpcode();
403 if (Opcode == BPF::MOV_rr) {
404 Register dst = MI.getOperand(i: 0).getReg();
405 Register src = MI.getOperand(i: 1).getReg();
406
407 if (dst != src)
408 continue;
409
410 ToErase = &MI;
411 RedundantMovElemNum++;
412 Eliminated = true;
413 }
414 }
415 }
416
417 return Eliminated;
418}
419
420bool BPFMIPreEmitPeepholeImpl::in16BitRange(int Num) {
421 // Well, the cut-off is not precisely at 16bit range since
422 // new codes are added during the transformation. So let us
423 // a little bit conservative.
424 return Num >= -GotolAbsLowBound && Num <= GotolAbsLowBound;
425}
426
427// Before cpu=v4, only 16bit branch target offset (-0x8000 to 0x7fff)
428// is supported for both unconditional (JMP) and condition (JEQ, JSGT,
429// etc.) branches. In certain cases, e.g., full unrolling, the branch
430// target offset might exceed 16bit range. If this happens, the llvm
431// will generate incorrect code as the offset is truncated to 16bit.
432//
433// To fix this rare case, a new insn JMPL is introduced. This new
434// insn supports supports 32bit branch target offset. The compiler
435// does not use this insn during insn selection. Rather, BPF backend
436// will estimate the branch target offset and do JMP -> JMPL and
437// JEQ -> JEQ + JMPL conversion if the estimated branch target offset
438// is beyond 16bit.
439bool BPFMIPreEmitPeepholeImpl::adjustBranch() {
440 bool Changed = false;
441 int CurrNumInsns = 0;
442 DenseMap<MachineBasicBlock *, int> SoFarNumInsns;
443 DenseMap<MachineBasicBlock *, MachineBasicBlock *> FollowThroughBB;
444 std::vector<MachineBasicBlock *> MBBs;
445
446 MachineBasicBlock *PrevBB = nullptr;
447 for (MachineBasicBlock &MBB : *MF) {
448 // MBB.size() is the number of insns in this basic block, including some
449 // debug info, e.g., DEBUG_VALUE, so we may over-count a little bit.
450 // Typically we have way more normal insns than DEBUG_VALUE insns.
451 // Also, if we indeed need to convert conditional branch like JEQ to
452 // JEQ + JMPL, we actually introduced some new insns like below.
453 CurrNumInsns += (int)MBB.size();
454 SoFarNumInsns[&MBB] = CurrNumInsns;
455 if (PrevBB != nullptr)
456 FollowThroughBB[PrevBB] = &MBB;
457 PrevBB = &MBB;
458 // A list of original BBs to make later traveral easier.
459 MBBs.push_back(x: &MBB);
460 }
461 FollowThroughBB[PrevBB] = nullptr;
462
463 for (unsigned i = 0; i < MBBs.size(); i++) {
464 // We have four cases here:
465 // (1). no terminator, simple follow through.
466 // (2). jmp to another bb.
467 // (3). conditional jmp to another bb or follow through.
468 // (4). conditional jmp followed by an unconditional jmp.
469 MachineInstr *CondJmp = nullptr, *UncondJmp = nullptr;
470
471 MachineBasicBlock *MBB = MBBs[i];
472 for (MachineInstr &Term : MBB->terminators()) {
473 if (Term.isConditionalBranch()) {
474 assert(CondJmp == nullptr);
475 CondJmp = &Term;
476 } else if (Term.isUnconditionalBranch()) {
477 assert(UncondJmp == nullptr);
478 UncondJmp = &Term;
479 }
480 }
481
482 // (1). no terminator, simple follow through.
483 if (!CondJmp && !UncondJmp)
484 continue;
485
486 MachineBasicBlock *CondTargetBB, *JmpBB;
487 CurrNumInsns = SoFarNumInsns[MBB];
488
489 // (2). jmp to another bb.
490 if (!CondJmp && UncondJmp) {
491 JmpBB = UncondJmp->getOperand(i: 0).getMBB();
492 if (in16BitRange(Num: SoFarNumInsns[JmpBB] - JmpBB->size() - CurrNumInsns))
493 continue;
494
495 // replace this insn as a JMPL.
496 BuildMI(BB: MBB, MIMD: UncondJmp->getDebugLoc(), MCID: TII->get(Opcode: BPF::JMPL)).addMBB(MBB: JmpBB);
497 UncondJmp->eraseFromParent();
498 Changed = true;
499 continue;
500 }
501
502 const BasicBlock *TermBB = MBB->getBasicBlock();
503 // 'if r1 == r2 goto' has three operands, 'unwind_goto' has one.
504 MachineOperand &CondTarget =
505 CondJmp->getOperand(i: CondJmp->getNumExplicitOperands() - 1);
506 int Dist;
507
508 // (3). conditional jmp to another bb or follow through.
509 if (!UncondJmp) {
510 CondTargetBB = CondTarget.getMBB();
511 MachineBasicBlock *FollowBB = FollowThroughBB[MBB];
512 Dist = SoFarNumInsns[CondTargetBB] - CondTargetBB->size() - CurrNumInsns;
513 if (in16BitRange(Num: Dist))
514 continue;
515
516 // We have
517 // B2: ...
518 // if (cond) goto B5
519 // B3: ...
520 // where B2 -> B5 is beyond 16bit range.
521 //
522 // We do not have 32bit cond jmp insn. So we try to do
523 // the following.
524 // B2: ...
525 // if (cond) goto New_B1
526 // New_B0 goto B3
527 // New_B1: gotol B5
528 // B3: ...
529 // Basically two new basic blocks are created.
530 MachineBasicBlock *New_B0 = MF->CreateMachineBasicBlock(BB: TermBB);
531 MachineBasicBlock *New_B1 = MF->CreateMachineBasicBlock(BB: TermBB);
532
533 // Insert New_B0 and New_B1 into function block list.
534 MachineFunction::iterator MBB_I = ++MBB->getIterator();
535 MF->insert(MBBI: MBB_I, MBB: New_B0);
536 MF->insert(MBBI: MBB_I, MBB: New_B1);
537
538 // replace B2 cond jump
539 CondTarget.setMBB(New_B1);
540
541 // it is possible that CondTargetBB and FollowBB are the same. But the
542 // above Dist checking should already filtered this case.
543 MBB->removeSuccessor(Succ: CondTargetBB);
544 MBB->removeSuccessor(Succ: FollowBB);
545 MBB->addSuccessor(Succ: New_B0);
546 MBB->addSuccessor(Succ: New_B1);
547
548 // Populate insns in New_B0 and New_B1.
549 BuildMI(BB: New_B0, MIMD: CondJmp->getDebugLoc(), MCID: TII->get(Opcode: BPF::JMP)).addMBB(MBB: FollowBB);
550 BuildMI(BB: New_B1, MIMD: CondJmp->getDebugLoc(), MCID: TII->get(Opcode: BPF::JMPL))
551 .addMBB(MBB: CondTargetBB);
552
553 New_B0->addSuccessor(Succ: FollowBB);
554 New_B1->addSuccessor(Succ: CondTargetBB);
555 Changed = true;
556 continue;
557 }
558
559 // (4). conditional jmp followed by an unconditional jmp.
560 CondTargetBB = CondTarget.getMBB();
561 JmpBB = UncondJmp->getOperand(i: 0).getMBB();
562
563 // We have
564 // B2: ...
565 // if (cond) goto B5
566 // JMP B7
567 // B3: ...
568 //
569 // If only B2->B5 is out of 16bit range, we can do
570 // B2: ...
571 // if (cond) goto new_B
572 // JMP B7
573 // New_B: gotol B5
574 // B3: ...
575 //
576 // If only 'JMP B7' is out of 16bit range, we can replace
577 // 'JMP B7' with 'JMPL B7'.
578 //
579 // If both B2->B5 and 'JMP B7' is out of range, just do
580 // both the above transformations.
581 Dist = SoFarNumInsns[CondTargetBB] - CondTargetBB->size() - CurrNumInsns;
582 if (!in16BitRange(Num: Dist)) {
583 MachineBasicBlock *New_B = MF->CreateMachineBasicBlock(BB: TermBB);
584
585 // Insert New_B0 into function block list.
586 MF->insert(MBBI: ++MBB->getIterator(), MBB: New_B);
587
588 // replace B2 cond jump
589 CondTarget.setMBB(New_B);
590
591 if (CondTargetBB != JmpBB)
592 MBB->removeSuccessor(Succ: CondTargetBB);
593 MBB->addSuccessor(Succ: New_B);
594
595 // Populate insn in New_B.
596 BuildMI(BB: New_B, MIMD: CondJmp->getDebugLoc(), MCID: TII->get(Opcode: BPF::JMPL)).addMBB(MBB: CondTargetBB);
597
598 New_B->addSuccessor(Succ: CondTargetBB);
599 Changed = true;
600 }
601
602 if (!in16BitRange(Num: SoFarNumInsns[JmpBB] - CurrNumInsns)) {
603 BuildMI(BB: MBB, MIMD: UncondJmp->getDebugLoc(), MCID: TII->get(Opcode: BPF::JMPL)).addMBB(MBB: JmpBB);
604 UncondJmp->eraseFromParent();
605 Changed = true;
606 }
607 }
608
609 return Changed;
610}
611
612static const unsigned CallerSavedRegs[] = {BPF::R0, BPF::R1, BPF::R2,
613 BPF::R3, BPF::R4, BPF::R5};
614
615struct BPFFastCall {
616 MachineInstr *MI;
617 unsigned LiveCallerSavedRegs;
618};
619
620static void collectBPFFastCalls(const TargetRegisterInfo *TRI,
621 LivePhysRegs &LiveRegs, MachineBasicBlock &BB,
622 SmallVectorImpl<BPFFastCall> &Calls) {
623 LiveRegs.init(TRI: *TRI);
624 LiveRegs.addLiveOuts(MBB: BB);
625 Calls.clear();
626 for (MachineInstr &MI : llvm::reverse(C&: BB)) {
627 if (MI.isCall()) {
628 unsigned LiveCallerSavedRegs = 0;
629 for (MCRegister R : CallerSavedRegs) {
630 bool DoSpillFill = false;
631 for (MCPhysReg SR : TRI->subregs(Reg: R))
632 DoSpillFill |= !MI.definesRegister(Reg: SR, TRI) && LiveRegs.contains(Reg: SR);
633 if (!DoSpillFill)
634 continue;
635 LiveCallerSavedRegs |= 1 << R;
636 }
637 if (LiveCallerSavedRegs)
638 Calls.push_back(Elt: {.MI: &MI, .LiveCallerSavedRegs: LiveCallerSavedRegs});
639 }
640 LiveRegs.stepBackward(MI);
641 }
642}
643
644static int64_t computeMinFixedObjOffset(MachineFrameInfo &MFI,
645 unsigned SlotSize) {
646 int64_t MinFixedObjOffset = 0;
647 // Same logic as in X86FrameLowering::adjustFrameForMsvcCxxEh()
648 for (int I = MFI.getObjectIndexBegin(); I < MFI.getObjectIndexEnd(); ++I) {
649 if (MFI.isDeadObjectIndex(ObjectIdx: I))
650 continue;
651 MinFixedObjOffset = std::min(a: MinFixedObjOffset, b: MFI.getObjectOffset(ObjectIdx: I));
652 }
653 MinFixedObjOffset -=
654 (SlotSize + MinFixedObjOffset % SlotSize) & (SlotSize - 1);
655 return MinFixedObjOffset;
656}
657
658bool BPFMIPreEmitPeepholeImpl::insertMissingCallerSavedSpills() {
659 MachineFrameInfo &MFI = MF->getFrameInfo();
660 SmallVector<BPFFastCall, 8> Calls;
661 LivePhysRegs LiveRegs;
662 const unsigned SlotSize = 8;
663 int64_t MinFixedObjOffset = computeMinFixedObjOffset(MFI, SlotSize);
664 bool Changed = false;
665 for (MachineBasicBlock &BB : *MF) {
666 collectBPFFastCalls(TRI, LiveRegs, BB, Calls);
667 Changed |= !Calls.empty();
668 for (BPFFastCall &Call : Calls) {
669 int64_t CurOffset = MinFixedObjOffset;
670 for (MCRegister Reg : CallerSavedRegs) {
671 if (((1 << Reg) & Call.LiveCallerSavedRegs) == 0)
672 continue;
673 // Allocate stack object
674 CurOffset -= SlotSize;
675 MFI.CreateFixedSpillStackObject(Size: SlotSize, SPOffset: CurOffset);
676 // Generate spill
677 BuildMI(BB, I: Call.MI->getIterator(), MIMD: Call.MI->getDebugLoc(),
678 MCID: TII->get(Opcode: BPF::STD))
679 .addReg(RegNo: Reg, Flags: RegState::Kill)
680 .addReg(RegNo: BPF::R10)
681 .addImm(Val: CurOffset);
682 // Generate fill
683 BuildMI(BB, I: ++Call.MI->getIterator(), MIMD: Call.MI->getDebugLoc(),
684 MCID: TII->get(Opcode: BPF::LDD))
685 .addReg(RegNo: Reg, Flags: RegState::Define)
686 .addReg(RegNo: BPF::R10)
687 .addImm(Val: CurOffset);
688 }
689 }
690 }
691 return Changed;
692}
693
694bool BPFMIPreEmitPeepholeImpl::removeMayGotoZero() {
695 bool Changed = false;
696 MachineBasicBlock *Prev_MBB, *Curr_MBB = nullptr;
697
698 for (MachineBasicBlock &MBB : make_early_inc_range(Range: reverse(C&: *MF))) {
699 Prev_MBB = Curr_MBB;
700 Curr_MBB = &MBB;
701 if (Prev_MBB == nullptr || Curr_MBB->empty())
702 continue;
703
704 MachineInstr &MI = Curr_MBB->back();
705 if (MI.getOpcode() != TargetOpcode::INLINEASM_BR)
706 continue;
707
708 const char *AsmStr = MI.getOperand(i: 0).getSymbolName();
709 SmallVector<StringRef, 4> AsmPieces;
710 SplitString(Source: AsmStr, OutFragments&: AsmPieces, Delimiters: ";\n");
711
712 // Do not support multiple insns in one inline asm.
713 if (AsmPieces.size() != 1)
714 continue;
715
716 // The asm insn must be a may_goto insn.
717 SmallVector<StringRef, 4> AsmOpPieces;
718 SplitString(Source: AsmPieces[0], OutFragments&: AsmOpPieces, Delimiters: " ");
719 if (AsmOpPieces.size() != 2 || AsmOpPieces[0] != "may_goto")
720 continue;
721 // Enforce the format of 'may_goto <label>'.
722 if (AsmOpPieces[1] != "${0:l}" && AsmOpPieces[1] != "$0")
723 continue;
724
725 // Get the may_goto branch target.
726 MachineOperand &MO = MI.getOperand(i: InlineAsm::MIOp_FirstOperand + 1);
727 if (!MO.isMBB() || MO.getMBB() != Prev_MBB)
728 continue;
729
730 Changed = true;
731 if (Curr_MBB->begin() == MI) {
732 // Single 'may_goto' insn in the same basic block.
733 Curr_MBB->removeSuccessor(Succ: Prev_MBB);
734 for (MachineBasicBlock *Pred : Curr_MBB->predecessors())
735 Pred->replaceSuccessor(Old: Curr_MBB, New: Prev_MBB);
736 Curr_MBB->eraseFromParent();
737 Curr_MBB = Prev_MBB;
738 } else {
739 // Remove 'may_goto' insn.
740 MI.eraseFromParent();
741 }
742 }
743
744 return Changed;
745}
746
747// If the last non-debug insn in a function is 'JAL &bpf_unreachable', let us
748// add an 'exit' insn after it. This will ensure no fallthrough at the last
749// insn, making kernel verification easier.
750bool BPFMIPreEmitPeepholeImpl::addExitAfterUnreachable() {
751 MachineBasicBlock &MBB = MF->back();
752 auto MBBI = MBB.getLastNonDebugInstr(/*SkipPseudoOp=*/false);
753 if (MBBI == MBB.end() || MBBI->getOpcode() != BPF::JAL ||
754 !MBBI->getOperand(i: 0).isGlobal() ||
755 MBBI->getOperand(i: 0).getGlobal()->getName() != BPF_TRAP)
756 return false;
757
758 BuildMI(BB: &MBB, MIMD: MBBI->getDebugLoc(), MCID: TII->get(Opcode: BPF::RET));
759 return true;
760}
761
762} // namespace
763
764INITIALIZE_PASS(BPFMIPreEmitPeepholeLegacy, "bpf-mi-pre-emit-peephole",
765 "BPF PreEmit Peephole Optimization", false, false)
766
767char BPFMIPreEmitPeepholeLegacy::ID = 0;
768FunctionPass *llvm::createBPFMIPreEmitPeepholeLegacyPass() {
769 return new BPFMIPreEmitPeepholeLegacy();
770}
771
772bool BPFMIPreEmitPeepholeLegacy::runOnMachineFunction(MachineFunction &MF) {
773 if (skipFunction(F: MF.getFunction()))
774 return false;
775 BPFMIPreEmitPeepholeImpl Impl;
776 return Impl.runOnMachineFunction(MF);
777}
778
779PreservedAnalyses
780BPFMIPreEmitPeepholePass::run(MachineFunction &MF,
781 MachineFunctionAnalysisManager &MFAM) {
782 BPFMIPreEmitPeepholeImpl Impl;
783 return Impl.runOnMachineFunction(MF)
784 ? getMachineFunctionPassPreservedAnalyses()
785 .preserveSet<CFGAnalyses>()
786 : PreservedAnalyses::all();
787}
788
789namespace {
790
791bool expandStackArgPseudos(MachineFunction &MF) {
792 bool Changed = false;
793 const BPFInstrInfo *TII = MF.getSubtarget<BPFSubtarget>().getInstrInfo();
794 for (MachineBasicBlock &MBB : MF) {
795 for (auto It = MBB.begin(), End = MBB.end(); It != End;) {
796 MachineInstr &MI = *It++;
797 DebugLoc DL = MI.getDebugLoc();
798
799 switch (MI.getOpcode()) {
800 default:
801 break;
802
803 case BPF::LOAD_STACK_ARG_PSEUDO: {
804 Register DstReg = MI.getOperand(i: 0).getReg();
805 int16_t Off = MI.getOperand(i: 1).getImm();
806
807 BuildMI(BB&: MBB, I&: MI, MIMD: DL, MCID: TII->get(Opcode: BPF::LDD), DestReg: DstReg)
808 .addReg(RegNo: BPF::R11)
809 .addImm(Val: Off);
810 MI.eraseFromParent();
811 Changed = true;
812 break;
813 }
814
815 case BPF::STORE_STACK_ARG_PSEUDO: {
816 int16_t Off = MI.getOperand(i: 0).getImm();
817 const MachineOperand &SrcMO = MI.getOperand(i: 1);
818 Register SrcReg = SrcMO.getReg();
819 bool IsKill = SrcMO.isKill();
820
821 BuildMI(BB&: MBB, I&: MI, MIMD: DL, MCID: TII->get(Opcode: BPF::STD))
822 .addReg(RegNo: SrcReg, Flags: getKillRegState(B: IsKill))
823 .addReg(RegNo: BPF::R11)
824 .addImm(Val: Off);
825 MI.eraseFromParent();
826 Changed = true;
827 break;
828 }
829
830 case BPF::STORE_STACK_ARG_IMM_PSEUDO: {
831 int16_t Off = MI.getOperand(i: 0).getImm();
832 int32_t Val = MI.getOperand(i: 1).getImm();
833
834 BuildMI(BB&: MBB, I&: MI, MIMD: DL, MCID: TII->get(Opcode: BPF::STD_imm))
835 .addImm(Val)
836 .addReg(RegNo: BPF::R11)
837 .addImm(Val: Off);
838 MI.eraseFromParent();
839 Changed = true;
840 break;
841 }
842 }
843 }
844 }
845
846 return Changed;
847}
848
849class BPFMIExpandStackArgPseudosLegacy : public MachineFunctionPass {
850public:
851 static char ID;
852 BPFMIExpandStackArgPseudosLegacy() : MachineFunctionPass(ID) {}
853 bool runOnMachineFunction(MachineFunction &MF) override;
854};
855
856} // namespace
857
858INITIALIZE_PASS(BPFMIExpandStackArgPseudosLegacy,
859 "bpf-mi-expand-stack-arg-pseudos",
860 "BPF Stack argument psuedo expansion", false, false)
861
862char BPFMIExpandStackArgPseudosLegacy::ID = 0;
863FunctionPass *llvm::createBPFMIExpandStackArgPseudosLegacyPass() {
864 return new BPFMIExpandStackArgPseudosLegacy();
865}
866
867bool BPFMIExpandStackArgPseudosLegacy::runOnMachineFunction(
868 MachineFunction &MF) {
869 return expandStackArgPseudos(MF);
870}
871
872PreservedAnalyses
873BPFMIExpandStackArgPseudosPass::run(MachineFunction &MF,
874 MachineFunctionAnalysisManager &MFAM) {
875 return expandStackArgPseudos(MF) ? getMachineFunctionPassPreservedAnalyses()
876 .preserveSet<CFGAnalyses>()
877 : PreservedAnalyses::all();
878}
879