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 SllMI->eraseFromParent();
234 MovMI->eraseFromParent();
235 // MI is the right shift, we can't erase it in it's own iteration.
236 // Mark it to ToErase, and erase in the next iteration.
237 ToErase = &MI;
238 ZExtElemNum++;
239 Eliminated = true;
240 }
241 }
242 }
243
244 return Eliminated;
245}
246
247bool BPFMIPeepholeImpl::eliminateZExt() {
248 MachineInstr* ToErase = nullptr;
249 bool Eliminated = false;
250
251 for (MachineBasicBlock &MBB : *MF) {
252 for (MachineInstr &MI : MBB) {
253 // If the previous instruction was marked for elimination, remove it now.
254 if (ToErase) {
255 ToErase->eraseFromParent();
256 ToErase = nullptr;
257 }
258
259 if (MI.getOpcode() != BPF::MOV_32_64)
260 continue;
261
262 // Eliminate MOV_32_64 if possible.
263 // MOV_32_64 rA, wB
264 //
265 // If wB has been zero extended, replace it with a SUBREG_TO_REG.
266 // This is to workaround BPF programs where pkt->{data, data_end}
267 // is encoded as u32, but actually the verifier populates them
268 // as 64bit pointer. The MOV_32_64 will zero out the top 32 bits.
269 LLVM_DEBUG(dbgs() << "Candidate MOV_32_64 instruction:");
270 LLVM_DEBUG(MI.dump());
271
272 if (!isMovFrom32Def(MovMI: &MI))
273 continue;
274
275 LLVM_DEBUG(dbgs() << "Removing the MOV_32_64 instruction\n");
276
277 Register dst = MI.getOperand(i: 0).getReg();
278 Register src = MI.getOperand(i: 1).getReg();
279
280 // Build a SUBREG_TO_REG instruction.
281 BuildMI(BB&: MBB, I&: MI, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: BPF::SUBREG_TO_REG), DestReg: dst)
282 .addReg(RegNo: src)
283 .addImm(Val: BPF::sub_32);
284
285 ToErase = &MI;
286 Eliminated = true;
287 }
288 }
289
290 return Eliminated;
291}
292
293} // end default namespace
294
295INITIALIZE_PASS(BPFMIPeepholeLegacy, DEBUG_TYPE,
296 "BPF MachineSSA Peephole Optimization For ZEXT Eliminate",
297 false, false)
298
299char BPFMIPeepholeLegacy::ID = 0;
300FunctionPass *llvm::createBPFMIPeepholeLegacyPass() {
301 return new BPFMIPeepholeLegacy();
302}
303
304bool BPFMIPeepholeLegacy::runOnMachineFunction(MachineFunction &MF) {
305 if (skipFunction(F: MF.getFunction()))
306 return false;
307
308 BPFMIPeepholeImpl Impl;
309 return Impl.runOnMachineFunction(MF);
310}
311
312PreservedAnalyses BPFMIPeepholePass::run(MachineFunction &MF,
313 MachineFunctionAnalysisManager &MFAM) {
314 BPFMIPeepholeImpl Impl;
315 return Impl.runOnMachineFunction(MF)
316 ? getMachineFunctionPassPreservedAnalyses()
317 .preserveSet<CFGAnalyses>()
318 : PreservedAnalyses::all();
319}
320
321STATISTIC(RedundantMovElemNum, "Number of redundant moves eliminated");
322
323namespace {
324
325struct BPFMIPreEmitPeepholeImpl {
326 MachineFunction *MF;
327 const TargetRegisterInfo *TRI;
328 const BPFInstrInfo *TII;
329 bool SupportGotol;
330
331private:
332 // Initialize class variables.
333 void initialize(MachineFunction &MFParm);
334
335 bool in16BitRange(int Num);
336 bool eliminateRedundantMov();
337 bool adjustBranch();
338 bool insertMissingCallerSavedSpills();
339 bool removeMayGotoZero();
340 bool addExitAfterUnreachable();
341
342public:
343
344 // Main entry point for this pass.
345 bool runOnMachineFunction(MachineFunction &MF) {
346 initialize(MFParm&: MF);
347 bool Changed = eliminateRedundantMov();
348 if (SupportGotol)
349 Changed |= adjustBranch();
350 Changed |= insertMissingCallerSavedSpills();
351 Changed |= removeMayGotoZero();
352 Changed |= addExitAfterUnreachable();
353 return Changed;
354 }
355};
356
357class BPFMIPreEmitPeepholeLegacy : public MachineFunctionPass {
358public:
359 static char ID;
360 BPFMIPreEmitPeepholeLegacy() : MachineFunctionPass(ID) {}
361 bool runOnMachineFunction(MachineFunction &MF) override;
362};
363
364// Initialize class variables.
365void BPFMIPreEmitPeepholeImpl::initialize(MachineFunction &MFParm) {
366 MF = &MFParm;
367 TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
368 TRI = MF->getSubtarget<BPFSubtarget>().getRegisterInfo();
369 SupportGotol = MF->getSubtarget<BPFSubtarget>().hasGotol();
370 LLVM_DEBUG(dbgs() << "*** BPF PreEmit peephole pass ***\n\n");
371}
372
373bool BPFMIPreEmitPeepholeImpl::eliminateRedundantMov() {
374 MachineInstr* ToErase = nullptr;
375 bool Eliminated = false;
376
377 for (MachineBasicBlock &MBB : *MF) {
378 for (MachineInstr &MI : MBB) {
379 // If the previous instruction was marked for elimination, remove it now.
380 if (ToErase) {
381 LLVM_DEBUG(dbgs() << " Redundant Mov Eliminated:");
382 LLVM_DEBUG(ToErase->dump());
383 ToErase->eraseFromParent();
384 ToErase = nullptr;
385 }
386
387 // Eliminate identical move:
388 //
389 // MOV rA, rA
390 //
391 // Note that we cannot remove
392 // MOV_32_64 rA, wA
393 // MOV_rr_32 wA, wA
394 // as these two instructions having side effects, zeroing out
395 // top 32 bits of rA.
396 unsigned Opcode = MI.getOpcode();
397 if (Opcode == BPF::MOV_rr) {
398 Register dst = MI.getOperand(i: 0).getReg();
399 Register src = MI.getOperand(i: 1).getReg();
400
401 if (dst != src)
402 continue;
403
404 ToErase = &MI;
405 RedundantMovElemNum++;
406 Eliminated = true;
407 }
408 }
409 }
410
411 return Eliminated;
412}
413
414bool BPFMIPreEmitPeepholeImpl::in16BitRange(int Num) {
415 // Well, the cut-off is not precisely at 16bit range since
416 // new codes are added during the transformation. So let us
417 // a little bit conservative.
418 return Num >= -GotolAbsLowBound && Num <= GotolAbsLowBound;
419}
420
421// Before cpu=v4, only 16bit branch target offset (-0x8000 to 0x7fff)
422// is supported for both unconditional (JMP) and condition (JEQ, JSGT,
423// etc.) branches. In certain cases, e.g., full unrolling, the branch
424// target offset might exceed 16bit range. If this happens, the llvm
425// will generate incorrect code as the offset is truncated to 16bit.
426//
427// To fix this rare case, a new insn JMPL is introduced. This new
428// insn supports supports 32bit branch target offset. The compiler
429// does not use this insn during insn selection. Rather, BPF backend
430// will estimate the branch target offset and do JMP -> JMPL and
431// JEQ -> JEQ + JMPL conversion if the estimated branch target offset
432// is beyond 16bit.
433bool BPFMIPreEmitPeepholeImpl::adjustBranch() {
434 bool Changed = false;
435 int CurrNumInsns = 0;
436 DenseMap<MachineBasicBlock *, int> SoFarNumInsns;
437 DenseMap<MachineBasicBlock *, MachineBasicBlock *> FollowThroughBB;
438 std::vector<MachineBasicBlock *> MBBs;
439
440 MachineBasicBlock *PrevBB = nullptr;
441 for (MachineBasicBlock &MBB : *MF) {
442 // MBB.size() is the number of insns in this basic block, including some
443 // debug info, e.g., DEBUG_VALUE, so we may over-count a little bit.
444 // Typically we have way more normal insns than DEBUG_VALUE insns.
445 // Also, if we indeed need to convert conditional branch like JEQ to
446 // JEQ + JMPL, we actually introduced some new insns like below.
447 CurrNumInsns += (int)MBB.size();
448 SoFarNumInsns[&MBB] = CurrNumInsns;
449 if (PrevBB != nullptr)
450 FollowThroughBB[PrevBB] = &MBB;
451 PrevBB = &MBB;
452 // A list of original BBs to make later traveral easier.
453 MBBs.push_back(x: &MBB);
454 }
455 FollowThroughBB[PrevBB] = nullptr;
456
457 for (unsigned i = 0; i < MBBs.size(); i++) {
458 // We have four cases here:
459 // (1). no terminator, simple follow through.
460 // (2). jmp to another bb.
461 // (3). conditional jmp to another bb or follow through.
462 // (4). conditional jmp followed by an unconditional jmp.
463 MachineInstr *CondJmp = nullptr, *UncondJmp = nullptr;
464
465 MachineBasicBlock *MBB = MBBs[i];
466 for (MachineInstr &Term : MBB->terminators()) {
467 if (Term.isConditionalBranch()) {
468 assert(CondJmp == nullptr);
469 CondJmp = &Term;
470 } else if (Term.isUnconditionalBranch()) {
471 assert(UncondJmp == nullptr);
472 UncondJmp = &Term;
473 }
474 }
475
476 // (1). no terminator, simple follow through.
477 if (!CondJmp && !UncondJmp)
478 continue;
479
480 MachineBasicBlock *CondTargetBB, *JmpBB;
481 CurrNumInsns = SoFarNumInsns[MBB];
482
483 // (2). jmp to another bb.
484 if (!CondJmp && UncondJmp) {
485 JmpBB = UncondJmp->getOperand(i: 0).getMBB();
486 if (in16BitRange(Num: SoFarNumInsns[JmpBB] - JmpBB->size() - CurrNumInsns))
487 continue;
488
489 // replace this insn as a JMPL.
490 BuildMI(BB: MBB, MIMD: UncondJmp->getDebugLoc(), MCID: TII->get(Opcode: BPF::JMPL)).addMBB(MBB: JmpBB);
491 UncondJmp->eraseFromParent();
492 Changed = true;
493 continue;
494 }
495
496 const BasicBlock *TermBB = MBB->getBasicBlock();
497 int Dist;
498
499 // (3). conditional jmp to another bb or follow through.
500 if (!UncondJmp) {
501 CondTargetBB = CondJmp->getOperand(i: 2).getMBB();
502 MachineBasicBlock *FollowBB = FollowThroughBB[MBB];
503 Dist = SoFarNumInsns[CondTargetBB] - CondTargetBB->size() - CurrNumInsns;
504 if (in16BitRange(Num: Dist))
505 continue;
506
507 // We have
508 // B2: ...
509 // if (cond) goto B5
510 // B3: ...
511 // where B2 -> B5 is beyond 16bit range.
512 //
513 // We do not have 32bit cond jmp insn. So we try to do
514 // the following.
515 // B2: ...
516 // if (cond) goto New_B1
517 // New_B0 goto B3
518 // New_B1: gotol B5
519 // B3: ...
520 // Basically two new basic blocks are created.
521 MachineBasicBlock *New_B0 = MF->CreateMachineBasicBlock(BB: TermBB);
522 MachineBasicBlock *New_B1 = MF->CreateMachineBasicBlock(BB: TermBB);
523
524 // Insert New_B0 and New_B1 into function block list.
525 MachineFunction::iterator MBB_I = ++MBB->getIterator();
526 MF->insert(MBBI: MBB_I, MBB: New_B0);
527 MF->insert(MBBI: MBB_I, MBB: New_B1);
528
529 // replace B2 cond jump
530 if (CondJmp->getOperand(i: 1).isReg())
531 BuildMI(BB&: *MBB, I: MachineBasicBlock::iterator(*CondJmp), MIMD: CondJmp->getDebugLoc(), MCID: TII->get(Opcode: CondJmp->getOpcode()))
532 .addReg(RegNo: CondJmp->getOperand(i: 0).getReg())
533 .addReg(RegNo: CondJmp->getOperand(i: 1).getReg())
534 .addMBB(MBB: New_B1);
535 else
536 BuildMI(BB&: *MBB, I: MachineBasicBlock::iterator(*CondJmp), MIMD: CondJmp->getDebugLoc(), MCID: TII->get(Opcode: CondJmp->getOpcode()))
537 .addReg(RegNo: CondJmp->getOperand(i: 0).getReg())
538 .addImm(Val: CondJmp->getOperand(i: 1).getImm())
539 .addMBB(MBB: 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 CondJmp->eraseFromParent();
556 Changed = true;
557 continue;
558 }
559
560 // (4). conditional jmp followed by an unconditional jmp.
561 CondTargetBB = CondJmp->getOperand(i: 2).getMBB();
562 JmpBB = UncondJmp->getOperand(i: 0).getMBB();
563
564 // We have
565 // B2: ...
566 // if (cond) goto B5
567 // JMP B7
568 // B3: ...
569 //
570 // If only B2->B5 is out of 16bit range, we can do
571 // B2: ...
572 // if (cond) goto new_B
573 // JMP B7
574 // New_B: gotol B5
575 // B3: ...
576 //
577 // If only 'JMP B7' is out of 16bit range, we can replace
578 // 'JMP B7' with 'JMPL B7'.
579 //
580 // If both B2->B5 and 'JMP B7' is out of range, just do
581 // both the above transformations.
582 Dist = SoFarNumInsns[CondTargetBB] - CondTargetBB->size() - CurrNumInsns;
583 if (!in16BitRange(Num: Dist)) {
584 MachineBasicBlock *New_B = MF->CreateMachineBasicBlock(BB: TermBB);
585
586 // Insert New_B0 into function block list.
587 MF->insert(MBBI: ++MBB->getIterator(), MBB: New_B);
588
589 // replace B2 cond jump
590 if (CondJmp->getOperand(i: 1).isReg())
591 BuildMI(BB&: *MBB, I: MachineBasicBlock::iterator(*CondJmp), MIMD: CondJmp->getDebugLoc(), MCID: TII->get(Opcode: CondJmp->getOpcode()))
592 .addReg(RegNo: CondJmp->getOperand(i: 0).getReg())
593 .addReg(RegNo: CondJmp->getOperand(i: 1).getReg())
594 .addMBB(MBB: New_B);
595 else
596 BuildMI(BB&: *MBB, I: MachineBasicBlock::iterator(*CondJmp), MIMD: CondJmp->getDebugLoc(), MCID: TII->get(Opcode: CondJmp->getOpcode()))
597 .addReg(RegNo: CondJmp->getOperand(i: 0).getReg())
598 .addImm(Val: CondJmp->getOperand(i: 1).getImm())
599 .addMBB(MBB: New_B);
600
601 if (CondTargetBB != JmpBB)
602 MBB->removeSuccessor(Succ: CondTargetBB);
603 MBB->addSuccessor(Succ: New_B);
604
605 // Populate insn in New_B.
606 BuildMI(BB: New_B, MIMD: CondJmp->getDebugLoc(), MCID: TII->get(Opcode: BPF::JMPL)).addMBB(MBB: CondTargetBB);
607
608 New_B->addSuccessor(Succ: CondTargetBB);
609 CondJmp->eraseFromParent();
610 Changed = true;
611 }
612
613 if (!in16BitRange(Num: SoFarNumInsns[JmpBB] - CurrNumInsns)) {
614 BuildMI(BB: MBB, MIMD: UncondJmp->getDebugLoc(), MCID: TII->get(Opcode: BPF::JMPL)).addMBB(MBB: JmpBB);
615 UncondJmp->eraseFromParent();
616 Changed = true;
617 }
618 }
619
620 return Changed;
621}
622
623static const unsigned CallerSavedRegs[] = {BPF::R0, BPF::R1, BPF::R2,
624 BPF::R3, BPF::R4, BPF::R5};
625
626struct BPFFastCall {
627 MachineInstr *MI;
628 unsigned LiveCallerSavedRegs;
629};
630
631static void collectBPFFastCalls(const TargetRegisterInfo *TRI,
632 LivePhysRegs &LiveRegs, MachineBasicBlock &BB,
633 SmallVectorImpl<BPFFastCall> &Calls) {
634 LiveRegs.init(TRI: *TRI);
635 LiveRegs.addLiveOuts(MBB: BB);
636 Calls.clear();
637 for (MachineInstr &MI : llvm::reverse(C&: BB)) {
638 if (MI.isCall()) {
639 unsigned LiveCallerSavedRegs = 0;
640 for (MCRegister R : CallerSavedRegs) {
641 bool DoSpillFill = false;
642 for (MCPhysReg SR : TRI->subregs(Reg: R))
643 DoSpillFill |= !MI.definesRegister(Reg: SR, TRI) && LiveRegs.contains(Reg: SR);
644 if (!DoSpillFill)
645 continue;
646 LiveCallerSavedRegs |= 1 << R;
647 }
648 if (LiveCallerSavedRegs)
649 Calls.push_back(Elt: {.MI: &MI, .LiveCallerSavedRegs: LiveCallerSavedRegs});
650 }
651 LiveRegs.stepBackward(MI);
652 }
653}
654
655static int64_t computeMinFixedObjOffset(MachineFrameInfo &MFI,
656 unsigned SlotSize) {
657 int64_t MinFixedObjOffset = 0;
658 // Same logic as in X86FrameLowering::adjustFrameForMsvcCxxEh()
659 for (int I = MFI.getObjectIndexBegin(); I < MFI.getObjectIndexEnd(); ++I) {
660 if (MFI.isDeadObjectIndex(ObjectIdx: I))
661 continue;
662 MinFixedObjOffset = std::min(a: MinFixedObjOffset, b: MFI.getObjectOffset(ObjectIdx: I));
663 }
664 MinFixedObjOffset -=
665 (SlotSize + MinFixedObjOffset % SlotSize) & (SlotSize - 1);
666 return MinFixedObjOffset;
667}
668
669bool BPFMIPreEmitPeepholeImpl::insertMissingCallerSavedSpills() {
670 MachineFrameInfo &MFI = MF->getFrameInfo();
671 SmallVector<BPFFastCall, 8> Calls;
672 LivePhysRegs LiveRegs;
673 const unsigned SlotSize = 8;
674 int64_t MinFixedObjOffset = computeMinFixedObjOffset(MFI, SlotSize);
675 bool Changed = false;
676 for (MachineBasicBlock &BB : *MF) {
677 collectBPFFastCalls(TRI, LiveRegs, BB, Calls);
678 Changed |= !Calls.empty();
679 for (BPFFastCall &Call : Calls) {
680 int64_t CurOffset = MinFixedObjOffset;
681 for (MCRegister Reg : CallerSavedRegs) {
682 if (((1 << Reg) & Call.LiveCallerSavedRegs) == 0)
683 continue;
684 // Allocate stack object
685 CurOffset -= SlotSize;
686 MFI.CreateFixedSpillStackObject(Size: SlotSize, SPOffset: CurOffset);
687 // Generate spill
688 BuildMI(BB, I: Call.MI->getIterator(), MIMD: Call.MI->getDebugLoc(),
689 MCID: TII->get(Opcode: BPF::STD))
690 .addReg(RegNo: Reg, Flags: RegState::Kill)
691 .addReg(RegNo: BPF::R10)
692 .addImm(Val: CurOffset);
693 // Generate fill
694 BuildMI(BB, I: ++Call.MI->getIterator(), MIMD: Call.MI->getDebugLoc(),
695 MCID: TII->get(Opcode: BPF::LDD))
696 .addReg(RegNo: Reg, Flags: RegState::Define)
697 .addReg(RegNo: BPF::R10)
698 .addImm(Val: CurOffset);
699 }
700 }
701 }
702 return Changed;
703}
704
705bool BPFMIPreEmitPeepholeImpl::removeMayGotoZero() {
706 bool Changed = false;
707 MachineBasicBlock *Prev_MBB, *Curr_MBB = nullptr;
708
709 for (MachineBasicBlock &MBB : make_early_inc_range(Range: reverse(C&: *MF))) {
710 Prev_MBB = Curr_MBB;
711 Curr_MBB = &MBB;
712 if (Prev_MBB == nullptr || Curr_MBB->empty())
713 continue;
714
715 MachineInstr &MI = Curr_MBB->back();
716 if (MI.getOpcode() != TargetOpcode::INLINEASM_BR)
717 continue;
718
719 const char *AsmStr = MI.getOperand(i: 0).getSymbolName();
720 SmallVector<StringRef, 4> AsmPieces;
721 SplitString(Source: AsmStr, OutFragments&: AsmPieces, Delimiters: ";\n");
722
723 // Do not support multiple insns in one inline asm.
724 if (AsmPieces.size() != 1)
725 continue;
726
727 // The asm insn must be a may_goto insn.
728 SmallVector<StringRef, 4> AsmOpPieces;
729 SplitString(Source: AsmPieces[0], OutFragments&: AsmOpPieces, Delimiters: " ");
730 if (AsmOpPieces.size() != 2 || AsmOpPieces[0] != "may_goto")
731 continue;
732 // Enforce the format of 'may_goto <label>'.
733 if (AsmOpPieces[1] != "${0:l}" && AsmOpPieces[1] != "$0")
734 continue;
735
736 // Get the may_goto branch target.
737 MachineOperand &MO = MI.getOperand(i: InlineAsm::MIOp_FirstOperand + 1);
738 if (!MO.isMBB() || MO.getMBB() != Prev_MBB)
739 continue;
740
741 Changed = true;
742 if (Curr_MBB->begin() == MI) {
743 // Single 'may_goto' insn in the same basic block.
744 Curr_MBB->removeSuccessor(Succ: Prev_MBB);
745 for (MachineBasicBlock *Pred : Curr_MBB->predecessors())
746 Pred->replaceSuccessor(Old: Curr_MBB, New: Prev_MBB);
747 Curr_MBB->eraseFromParent();
748 Curr_MBB = Prev_MBB;
749 } else {
750 // Remove 'may_goto' insn.
751 MI.eraseFromParent();
752 }
753 }
754
755 return Changed;
756}
757
758// If the last insn in a funciton is 'JAL &bpf_unreachable', let us add an
759// 'exit' insn after that insn. This will ensure no fallthrough at the last
760// insn, making kernel verification easier.
761bool BPFMIPreEmitPeepholeImpl::addExitAfterUnreachable() {
762 MachineBasicBlock &MBB = MF->back();
763 MachineInstr &MI = MBB.back();
764 if (MI.getOpcode() != BPF::JAL || !MI.getOperand(i: 0).isGlobal() ||
765 MI.getOperand(i: 0).getGlobal()->getName() != BPF_TRAP)
766 return false;
767
768 BuildMI(BB: &MBB, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: BPF::RET));
769 return true;
770}
771
772} // namespace
773
774INITIALIZE_PASS(BPFMIPreEmitPeepholeLegacy, "bpf-mi-pre-emit-peephole",
775 "BPF PreEmit Peephole Optimization", false, false)
776
777char BPFMIPreEmitPeepholeLegacy::ID = 0;
778FunctionPass *llvm::createBPFMIPreEmitPeepholeLegacyPass() {
779 return new BPFMIPreEmitPeepholeLegacy();
780}
781
782bool BPFMIPreEmitPeepholeLegacy::runOnMachineFunction(MachineFunction &MF) {
783 if (skipFunction(F: MF.getFunction()))
784 return false;
785 BPFMIPreEmitPeepholeImpl Impl;
786 return Impl.runOnMachineFunction(MF);
787}
788
789PreservedAnalyses
790BPFMIPreEmitPeepholePass::run(MachineFunction &MF,
791 MachineFunctionAnalysisManager &MFAM) {
792 BPFMIPreEmitPeepholeImpl Impl;
793 return Impl.runOnMachineFunction(MF)
794 ? getMachineFunctionPassPreservedAnalyses()
795 .preserveSet<CFGAnalyses>()
796 : PreservedAnalyses::all();
797}
798
799namespace {
800
801bool expandStackArgPseudos(MachineFunction &MF) {
802 bool Changed = false;
803 const BPFInstrInfo *TII = MF.getSubtarget<BPFSubtarget>().getInstrInfo();
804 for (MachineBasicBlock &MBB : MF) {
805 for (auto It = MBB.begin(), End = MBB.end(); It != End;) {
806 MachineInstr &MI = *It++;
807 DebugLoc DL = MI.getDebugLoc();
808
809 switch (MI.getOpcode()) {
810 default:
811 break;
812
813 case BPF::LOAD_STACK_ARG_PSEUDO: {
814 Register DstReg = MI.getOperand(i: 0).getReg();
815 int16_t Off = MI.getOperand(i: 1).getImm();
816
817 BuildMI(BB&: MBB, I&: MI, MIMD: DL, MCID: TII->get(Opcode: BPF::LDD), DestReg: DstReg)
818 .addReg(RegNo: BPF::R11)
819 .addImm(Val: Off);
820 MI.eraseFromParent();
821 Changed = true;
822 break;
823 }
824
825 case BPF::STORE_STACK_ARG_PSEUDO: {
826 int16_t Off = MI.getOperand(i: 0).getImm();
827 const MachineOperand &SrcMO = MI.getOperand(i: 1);
828 Register SrcReg = SrcMO.getReg();
829 bool IsKill = SrcMO.isKill();
830
831 BuildMI(BB&: MBB, I&: MI, MIMD: DL, MCID: TII->get(Opcode: BPF::STD))
832 .addReg(RegNo: SrcReg, Flags: getKillRegState(B: IsKill))
833 .addReg(RegNo: BPF::R11)
834 .addImm(Val: Off);
835 MI.eraseFromParent();
836 Changed = true;
837 break;
838 }
839
840 case BPF::STORE_STACK_ARG_IMM_PSEUDO: {
841 int16_t Off = MI.getOperand(i: 0).getImm();
842 int32_t Val = MI.getOperand(i: 1).getImm();
843
844 BuildMI(BB&: MBB, I&: MI, MIMD: DL, MCID: TII->get(Opcode: BPF::STD_imm))
845 .addImm(Val)
846 .addReg(RegNo: BPF::R11)
847 .addImm(Val: Off);
848 MI.eraseFromParent();
849 Changed = true;
850 break;
851 }
852 }
853 }
854 }
855
856 return Changed;
857}
858
859class BPFMIExpandStackArgPseudosLegacy : public MachineFunctionPass {
860public:
861 static char ID;
862 BPFMIExpandStackArgPseudosLegacy() : MachineFunctionPass(ID) {}
863 bool runOnMachineFunction(MachineFunction &MF) override;
864};
865
866} // namespace
867
868INITIALIZE_PASS(BPFMIExpandStackArgPseudosLegacy,
869 "bpf-mi-expand-stack-arg-pseudos",
870 "BPF Stack argument psuedo expansion", false, false)
871
872char BPFMIExpandStackArgPseudosLegacy::ID = 0;
873FunctionPass *llvm::createBPFMIExpandStackArgPseudosLegacyPass() {
874 return new BPFMIExpandStackArgPseudosLegacy();
875}
876
877bool BPFMIExpandStackArgPseudosLegacy::runOnMachineFunction(
878 MachineFunction &MF) {
879 return expandStackArgPseudos(MF);
880}
881
882PreservedAnalyses
883BPFMIExpandStackArgPseudosPass::run(MachineFunction &MF,
884 MachineFunctionAnalysisManager &MFAM) {
885 return expandStackArgPseudos(MF) ? getMachineFunctionPassPreservedAnalyses()
886 .preserveSet<CFGAnalyses>()
887 : PreservedAnalyses::all();
888}
889