1 //===-- BPFInstrInfo.cpp - BPF Instruction Information ----------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains the BPF implementation of the TargetInstrInfo class.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "BPFInstrInfo.h"
15 #include "BPF.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/CodeGen/MachineBasicBlock.h"
18 #include "llvm/CodeGen/MachineInstrBuilder.h"
19 #include "llvm/IR/DebugLoc.h"
20 #include "llvm/Support/ErrorHandling.h"
21 #include <cassert>
22 #include <iterator>
23 
24 #define GET_INSTRINFO_CTOR_DTOR
25 #include "BPFGenInstrInfo.inc"
26 
27 using namespace llvm;
28 
29 BPFInstrInfo::BPFInstrInfo()
30     : BPFGenInstrInfo(BPF::ADJCALLSTACKDOWN, BPF::ADJCALLSTACKUP) {}
31 
32 void BPFInstrInfo::copyPhysReg(MachineBasicBlock &MBB,
33                                MachineBasicBlock::iterator I,
34                                const DebugLoc &DL, unsigned DestReg,
35                                unsigned SrcReg, bool KillSrc) const {
36   if (BPF::GPRRegClass.contains(DestReg, SrcReg))
37     BuildMI(MBB, I, DL, get(BPF::MOV_rr), DestReg)
38         .addReg(SrcReg, getKillRegState(KillSrc));
39   else if (BPF::GPR32RegClass.contains(DestReg, SrcReg))
40     BuildMI(MBB, I, DL, get(BPF::MOV_rr_32), DestReg)
41         .addReg(SrcReg, getKillRegState(KillSrc));
42   else
43     llvm_unreachable("Impossible reg-to-reg copy");
44 }
45 
46 void BPFInstrInfo::expandMEMCPY(MachineBasicBlock::iterator MI) const {
47   unsigned DstReg = MI->getOperand(0).getReg();
48   unsigned SrcReg = MI->getOperand(1).getReg();
49   uint64_t CopyLen = MI->getOperand(2).getImm();
50   uint64_t Alignment = MI->getOperand(3).getImm();
51   unsigned ScratchReg = MI->getOperand(4).getReg();
52   MachineBasicBlock *BB = MI->getParent();
53   DebugLoc dl = MI->getDebugLoc();
54   unsigned LdOpc, StOpc;
55 
56   switch (Alignment) {
57   case 1:
58     LdOpc = BPF::LDB;
59     StOpc = BPF::STB;
60     break;
61   case 2:
62     LdOpc = BPF::LDH;
63     StOpc = BPF::STH;
64     break;
65   case 4:
66     LdOpc = BPF::LDW;
67     StOpc = BPF::STW;
68     break;
69   case 8:
70     LdOpc = BPF::LDD;
71     StOpc = BPF::STD;
72     break;
73   default:
74     llvm_unreachable("unsupported memcpy alignment");
75   }
76 
77   unsigned IterationNum = CopyLen >> Log2_64(Alignment);
78   for(unsigned I = 0; I < IterationNum; ++I) {
79     BuildMI(*BB, MI, dl, get(LdOpc))
80             .addReg(ScratchReg, RegState::Define).addReg(SrcReg)
81             .addImm(I * Alignment);
82     BuildMI(*BB, MI, dl, get(StOpc))
83             .addReg(ScratchReg, RegState::Kill).addReg(DstReg)
84             .addImm(I * Alignment);
85   }
86 
87   unsigned BytesLeft = CopyLen & (Alignment - 1);
88   unsigned Offset = IterationNum * Alignment;
89   bool Hanging4Byte = BytesLeft & 0x4;
90   bool Hanging2Byte = BytesLeft & 0x2;
91   bool Hanging1Byte = BytesLeft & 0x1;
92   if (Hanging4Byte) {
93     BuildMI(*BB, MI, dl, get(BPF::LDW))
94             .addReg(ScratchReg, RegState::Define).addReg(SrcReg).addImm(Offset);
95     BuildMI(*BB, MI, dl, get(BPF::STW))
96             .addReg(ScratchReg, RegState::Kill).addReg(DstReg).addImm(Offset);
97     Offset += 4;
98   }
99   if (Hanging2Byte) {
100     BuildMI(*BB, MI, dl, get(BPF::LDH))
101             .addReg(ScratchReg, RegState::Define).addReg(SrcReg).addImm(Offset);
102     BuildMI(*BB, MI, dl, get(BPF::STH))
103             .addReg(ScratchReg, RegState::Kill).addReg(DstReg).addImm(Offset);
104     Offset += 2;
105   }
106   if (Hanging1Byte) {
107     BuildMI(*BB, MI, dl, get(BPF::LDB))
108             .addReg(ScratchReg, RegState::Define).addReg(SrcReg).addImm(Offset);
109     BuildMI(*BB, MI, dl, get(BPF::STB))
110             .addReg(ScratchReg, RegState::Kill).addReg(DstReg).addImm(Offset);
111   }
112 
113   BB->erase(MI);
114 }
115 
116 bool BPFInstrInfo::expandPostRAPseudo(MachineInstr &MI) const {
117   if (MI.getOpcode() == BPF::MEMCPY) {
118     expandMEMCPY(MI);
119     return true;
120   }
121 
122   return false;
123 }
124 
125 void BPFInstrInfo::storeRegToStackSlot(MachineBasicBlock &MBB,
126                                        MachineBasicBlock::iterator I,
127                                        unsigned SrcReg, bool IsKill, int FI,
128                                        const TargetRegisterClass *RC,
129                                        const TargetRegisterInfo *TRI) const {
130   DebugLoc DL;
131   if (I != MBB.end())
132     DL = I->getDebugLoc();
133 
134   if (RC == &BPF::GPRRegClass)
135     BuildMI(MBB, I, DL, get(BPF::STD))
136         .addReg(SrcReg, getKillRegState(IsKill))
137         .addFrameIndex(FI)
138         .addImm(0);
139   else if (RC == &BPF::GPR32RegClass)
140     BuildMI(MBB, I, DL, get(BPF::STW32))
141         .addReg(SrcReg, getKillRegState(IsKill))
142         .addFrameIndex(FI)
143         .addImm(0);
144   else
145     llvm_unreachable("Can't store this register to stack slot");
146 }
147 
148 void BPFInstrInfo::loadRegFromStackSlot(MachineBasicBlock &MBB,
149                                         MachineBasicBlock::iterator I,
150                                         unsigned DestReg, int FI,
151                                         const TargetRegisterClass *RC,
152                                         const TargetRegisterInfo *TRI) const {
153   DebugLoc DL;
154   if (I != MBB.end())
155     DL = I->getDebugLoc();
156 
157   if (RC == &BPF::GPRRegClass)
158     BuildMI(MBB, I, DL, get(BPF::LDD), DestReg).addFrameIndex(FI).addImm(0);
159   else if (RC == &BPF::GPR32RegClass)
160     BuildMI(MBB, I, DL, get(BPF::LDW32), DestReg).addFrameIndex(FI).addImm(0);
161   else
162     llvm_unreachable("Can't load this register from stack slot");
163 }
164 
165 bool BPFInstrInfo::analyzeBranch(MachineBasicBlock &MBB,
166                                  MachineBasicBlock *&TBB,
167                                  MachineBasicBlock *&FBB,
168                                  SmallVectorImpl<MachineOperand> &Cond,
169                                  bool AllowModify) const {
170   // Start from the bottom of the block and work up, examining the
171   // terminator instructions.
172   MachineBasicBlock::iterator I = MBB.end();
173   while (I != MBB.begin()) {
174     --I;
175     if (I->isDebugInstr())
176       continue;
177 
178     // Working from the bottom, when we see a non-terminator
179     // instruction, we're done.
180     if (!isUnpredicatedTerminator(*I))
181       break;
182 
183     // A terminator that isn't a branch can't easily be handled
184     // by this analysis.
185     if (!I->isBranch())
186       return true;
187 
188     // Handle unconditional branches.
189     if (I->getOpcode() == BPF::JMP) {
190       if (!AllowModify) {
191         TBB = I->getOperand(0).getMBB();
192         continue;
193       }
194 
195       // If the block has any instructions after a J, delete them.
196       while (std::next(I) != MBB.end())
197         std::next(I)->eraseFromParent();
198       Cond.clear();
199       FBB = nullptr;
200 
201       // Delete the J if it's equivalent to a fall-through.
202       if (MBB.isLayoutSuccessor(I->getOperand(0).getMBB())) {
203         TBB = nullptr;
204         I->eraseFromParent();
205         I = MBB.end();
206         continue;
207       }
208 
209       // TBB is used to indicate the unconditinal destination.
210       TBB = I->getOperand(0).getMBB();
211       continue;
212     }
213     // Cannot handle conditional branches
214     return true;
215   }
216 
217   return false;
218 }
219 
220 unsigned BPFInstrInfo::insertBranch(MachineBasicBlock &MBB,
221                                     MachineBasicBlock *TBB,
222                                     MachineBasicBlock *FBB,
223                                     ArrayRef<MachineOperand> Cond,
224                                     const DebugLoc &DL,
225                                     int *BytesAdded) const {
226   assert(!BytesAdded && "code size not handled");
227 
228   // Shouldn't be a fall through.
229   assert(TBB && "insertBranch must not be told to insert a fallthrough");
230 
231   if (Cond.empty()) {
232     // Unconditional branch
233     assert(!FBB && "Unconditional branch with multiple successors!");
234     BuildMI(&MBB, DL, get(BPF::JMP)).addMBB(TBB);
235     return 1;
236   }
237 
238   llvm_unreachable("Unexpected conditional branch");
239 }
240 
241 unsigned BPFInstrInfo::removeBranch(MachineBasicBlock &MBB,
242                                     int *BytesRemoved) const {
243   assert(!BytesRemoved && "code size not handled");
244 
245   MachineBasicBlock::iterator I = MBB.end();
246   unsigned Count = 0;
247 
248   while (I != MBB.begin()) {
249     --I;
250     if (I->isDebugInstr())
251       continue;
252     if (I->getOpcode() != BPF::JMP)
253       break;
254     // Remove the branch.
255     I->eraseFromParent();
256     I = MBB.end();
257     ++Count;
258   }
259 
260   return Count;
261 }
262