1 //===-------------- BPFMIChecking.cpp - MI Checking Legality -------------===//
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 checking to signal errors for certain illegal usages at
10 // MachineInstruction layer. Specially, the result of XADD{32,64} insn should
11 // not be used. The pass is done at the PreEmit pass right before the
12 // machine code is emitted at which point the register liveness information
13 // is still available.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "BPF.h"
18 #include "BPFInstrInfo.h"
19 #include "BPFTargetMachine.h"
20 #include "llvm/CodeGen/MachineFunctionPass.h"
21 #include "llvm/CodeGen/MachineInstrBuilder.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
23 #include "llvm/Support/Debug.h"
24 
25 using namespace llvm;
26 
27 #define DEBUG_TYPE "bpf-mi-checking"
28 
29 namespace {
30 
31 struct BPFMIPreEmitChecking : public MachineFunctionPass {
32 
33   static char ID;
34   MachineFunction *MF;
35   const TargetRegisterInfo *TRI;
36 
37   BPFMIPreEmitChecking() : MachineFunctionPass(ID) {
38     initializeBPFMIPreEmitCheckingPass(*PassRegistry::getPassRegistry());
39   }
40 
41 private:
42   // Initialize class variables.
43   void initialize(MachineFunction &MFParm);
44 
45   bool processAtomicInsts();
46 
47 public:
48 
49   // Main entry point for this pass.
50   bool runOnMachineFunction(MachineFunction &MF) override {
51     if (!skipFunction(MF.getFunction())) {
52       initialize(MF);
53       return processAtomicInsts();
54     }
55     return false;
56   }
57 };
58 
59 // Initialize class variables.
60 void BPFMIPreEmitChecking::initialize(MachineFunction &MFParm) {
61   MF = &MFParm;
62   TRI = MF->getSubtarget<BPFSubtarget>().getRegisterInfo();
63   LLVM_DEBUG(dbgs() << "*** BPF PreEmit checking pass ***\n\n");
64 }
65 
66 // Make sure all Defs of XADD are dead, meaning any result of XADD insn is not
67 // used.
68 //
69 // NOTE: BPF backend hasn't enabled sub-register liveness track, so when the
70 // source and destination operands of XADD are GPR32, there is no sub-register
71 // dead info. If we rely on the generic MachineInstr::allDefsAreDead, then we
72 // will raise false alarm on GPR32 Def.
73 //
74 // To support GPR32 Def, ideally we could just enable sub-registr liveness track
75 // on BPF backend, then allDefsAreDead could work on GPR32 Def. This requires
76 // implementing TargetSubtargetInfo::enableSubRegLiveness on BPF.
77 //
78 // However, sub-register liveness tracking module inside LLVM is actually
79 // designed for the situation where one register could be split into more than
80 // one sub-registers for which case each sub-register could have their own
81 // liveness and kill one of them doesn't kill others. So, tracking liveness for
82 // each make sense.
83 //
84 // For BPF, each 64-bit register could only have one 32-bit sub-register. This
85 // is exactly the case which LLVM think brings no benefits for doing
86 // sub-register tracking, because the live range of sub-register must always
87 // equal to its parent register, therefore liveness tracking is disabled even
88 // the back-end has implemented enableSubRegLiveness. The detailed information
89 // is at r232695:
90 //
91 //   Author: Matthias Braun <matze@braunis.de>
92 //   Date:   Thu Mar 19 00:21:58 2015 +0000
93 //   Do not track subregister liveness when it brings no benefits
94 //
95 // Hence, for BPF, we enhance MachineInstr::allDefsAreDead. Given the solo
96 // sub-register always has the same liveness as its parent register, LLVM is
97 // already attaching a implicit 64-bit register Def whenever the there is
98 // a sub-register Def. The liveness of the implicit 64-bit Def is available.
99 // For example, for "lock *(u32 *)(r0 + 4) += w9", the MachineOperand info could
100 // be:
101 //
102 //   $w9 = XADDW32 killed $r0, 4, $w9(tied-def 0),
103 //                        implicit killed $r9, implicit-def dead $r9
104 //
105 // Even though w9 is not marked as Dead, the parent register r9 is marked as
106 // Dead correctly, and it is safe to use such information or our purpose.
107 static bool hasLiveDefs(const MachineInstr &MI, const TargetRegisterInfo *TRI) {
108   const MCRegisterClass *GPR64RegClass =
109     &BPFMCRegisterClasses[BPF::GPRRegClassID];
110   std::vector<unsigned> GPR32LiveDefs;
111   std::vector<unsigned> GPR64DeadDefs;
112 
113   for (const MachineOperand &MO : MI.operands()) {
114     bool RegIsGPR64;
115 
116     if (!MO.isReg() || MO.isUse())
117       continue;
118 
119     RegIsGPR64 = GPR64RegClass->contains(MO.getReg());
120     if (!MO.isDead()) {
121       // It is a GPR64 live Def, we are sure it is live. */
122       if (RegIsGPR64)
123         return true;
124       // It is a GPR32 live Def, we are unsure whether it is really dead due to
125       // no sub-register liveness tracking. Push it to vector for deferred
126       // check.
127       GPR32LiveDefs.push_back(MO.getReg());
128       continue;
129     }
130 
131     // Record any GPR64 dead Def as some unmarked GPR32 could be alias of its
132     // low 32-bit.
133     if (RegIsGPR64)
134       GPR64DeadDefs.push_back(MO.getReg());
135   }
136 
137   // No GPR32 live Def, safe to return false.
138   if (GPR32LiveDefs.empty())
139     return false;
140 
141   // No GPR64 dead Def, so all those GPR32 live Def can't have alias, therefore
142   // must be truely live, safe to return true.
143   if (GPR64DeadDefs.empty())
144     return true;
145 
146   // Otherwise, return true if any aliased SuperReg of GPR32 is not dead.
147   for (auto I : GPR32LiveDefs)
148     for (MCPhysReg SR : TRI->superregs(I))
149       if (!llvm::is_contained(GPR64DeadDefs, SR))
150         return true;
151 
152   return false;
153 }
154 
155 bool BPFMIPreEmitChecking::processAtomicInsts() {
156   for (MachineBasicBlock &MBB : *MF) {
157     for (MachineInstr &MI : MBB) {
158       if (MI.getOpcode() != BPF::XADDW &&
159           MI.getOpcode() != BPF::XADDD &&
160           MI.getOpcode() != BPF::XADDW32)
161         continue;
162 
163       LLVM_DEBUG(MI.dump());
164       if (hasLiveDefs(MI, TRI)) {
165         DebugLoc Empty;
166         const DebugLoc &DL = MI.getDebugLoc();
167         if (DL != Empty)
168           report_fatal_error(Twine("line ") + std::to_string(DL.getLine()) +
169                              ": Invalid usage of the XADD return value", false);
170         else
171           report_fatal_error("Invalid usage of the XADD return value", false);
172       }
173     }
174   }
175 
176   // Check return values of atomic_fetch_and_{add,and,or,xor}.
177   // If the return is not used, the atomic_fetch_and_<op> instruction
178   // is replaced with atomic_<op> instruction.
179   MachineInstr *ToErase = nullptr;
180   bool Changed = false;
181   const BPFInstrInfo *TII = MF->getSubtarget<BPFSubtarget>().getInstrInfo();
182   for (MachineBasicBlock &MBB : *MF) {
183     for (MachineInstr &MI : MBB) {
184       if (ToErase) {
185         ToErase->eraseFromParent();
186         ToErase = nullptr;
187       }
188 
189       if (MI.getOpcode() != BPF::XFADDW32 && MI.getOpcode() != BPF::XFADDD &&
190           MI.getOpcode() != BPF::XFANDW32 && MI.getOpcode() != BPF::XFANDD &&
191           MI.getOpcode() != BPF::XFXORW32 && MI.getOpcode() != BPF::XFXORD &&
192           MI.getOpcode() != BPF::XFORW32 && MI.getOpcode() != BPF::XFORD)
193         continue;
194 
195       if (hasLiveDefs(MI, TRI))
196         continue;
197 
198       LLVM_DEBUG(dbgs() << "Transforming "; MI.dump());
199       unsigned newOpcode;
200       switch (MI.getOpcode()) {
201       case BPF::XFADDW32:
202         newOpcode = BPF::XADDW32;
203         break;
204       case BPF::XFADDD:
205         newOpcode = BPF::XADDD;
206         break;
207       case BPF::XFANDW32:
208         newOpcode = BPF::XANDW32;
209         break;
210       case BPF::XFANDD:
211         newOpcode = BPF::XANDD;
212         break;
213       case BPF::XFXORW32:
214         newOpcode = BPF::XXORW32;
215         break;
216       case BPF::XFXORD:
217         newOpcode = BPF::XXORD;
218         break;
219       case BPF::XFORW32:
220         newOpcode = BPF::XORW32;
221         break;
222       case BPF::XFORD:
223         newOpcode = BPF::XORD;
224         break;
225       default:
226         llvm_unreachable("Incorrect Atomic Instruction Opcode");
227       }
228 
229       BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(newOpcode))
230           .add(MI.getOperand(0))
231           .add(MI.getOperand(1))
232           .add(MI.getOperand(2))
233           .add(MI.getOperand(3));
234 
235       ToErase = &MI;
236       Changed = true;
237     }
238   }
239 
240   return Changed;
241 }
242 
243 } // end default namespace
244 
245 INITIALIZE_PASS(BPFMIPreEmitChecking, "bpf-mi-pemit-checking",
246                 "BPF PreEmit Checking", false, false)
247 
248 char BPFMIPreEmitChecking::ID = 0;
249 FunctionPass* llvm::createBPFMIPreEmitCheckingPass()
250 {
251   return new BPFMIPreEmitChecking();
252 }
253