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