1 //===-- BPFISelDAGToDAG.cpp - A dag to dag inst selector for BPF ----------===//
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 file defines a DAG pattern matching instruction selector for BPF,
10 // converting from a legalized dag to a BPF dag.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "BPF.h"
15 #include "BPFRegisterInfo.h"
16 #include "BPFSubtarget.h"
17 #include "BPFTargetMachine.h"
18 #include "llvm/CodeGen/FunctionLoweringInfo.h"
19 #include "llvm/CodeGen/MachineConstantPool.h"
20 #include "llvm/CodeGen/MachineFrameInfo.h"
21 #include "llvm/CodeGen/MachineFunction.h"
22 #include "llvm/CodeGen/MachineInstrBuilder.h"
23 #include "llvm/CodeGen/MachineRegisterInfo.h"
24 #include "llvm/CodeGen/SelectionDAGISel.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/IntrinsicInst.h"
27 #include "llvm/IR/IntrinsicsBPF.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/Endian.h"
30 #include "llvm/Support/ErrorHandling.h"
31 #include "llvm/Support/raw_ostream.h"
32 #include "llvm/Target/TargetMachine.h"
33 
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "bpf-isel"
37 #define PASS_NAME "BPF DAG->DAG Pattern Instruction Selection"
38 
39 // Instruction Selector Implementation
40 namespace {
41 
42 class BPFDAGToDAGISel : public SelectionDAGISel {
43 
44   /// Subtarget - Keep a pointer to the BPFSubtarget around so that we can
45   /// make the right decision when generating code for different subtargets.
46   const BPFSubtarget *Subtarget;
47 
48 public:
49   static char ID;
50 
51   BPFDAGToDAGISel() = delete;
52 
BPFDAGToDAGISel(BPFTargetMachine & TM)53   explicit BPFDAGToDAGISel(BPFTargetMachine &TM)
54       : SelectionDAGISel(ID, TM), Subtarget(nullptr) {}
55 
runOnMachineFunction(MachineFunction & MF)56   bool runOnMachineFunction(MachineFunction &MF) override {
57     // Reset the subtarget each time through.
58     Subtarget = &MF.getSubtarget<BPFSubtarget>();
59     return SelectionDAGISel::runOnMachineFunction(MF);
60   }
61 
62   void PreprocessISelDAG() override;
63 
64   bool SelectInlineAsmMemoryOperand(const SDValue &Op,
65                                     InlineAsm::ConstraintCode ConstraintCode,
66                                     std::vector<SDValue> &OutOps) override;
67 
68 private:
69 // Include the pieces autogenerated from the target description.
70 #include "BPFGenDAGISel.inc"
71 
72   void Select(SDNode *N) override;
73 
74   // Complex Pattern for address selection.
75   bool SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset);
76   bool SelectFIAddr(SDValue Addr, SDValue &Base, SDValue &Offset);
77 
78   // Node preprocessing cases
79   void PreprocessLoad(SDNode *Node, SelectionDAG::allnodes_iterator &I);
80   void PreprocessTrunc(SDNode *Node, SelectionDAG::allnodes_iterator &I);
81 
82   // Find constants from a constant structure
83   typedef std::vector<unsigned char> val_vec_type;
84   bool fillGenericConstant(const DataLayout &DL, const Constant *CV,
85                            val_vec_type &Vals, uint64_t Offset);
86   bool fillConstantDataArray(const DataLayout &DL, const ConstantDataArray *CDA,
87                              val_vec_type &Vals, int Offset);
88   bool fillConstantArray(const DataLayout &DL, const ConstantArray *CA,
89                          val_vec_type &Vals, int Offset);
90   bool fillConstantStruct(const DataLayout &DL, const ConstantStruct *CS,
91                           val_vec_type &Vals, int Offset);
92   bool getConstantFieldValue(const GlobalAddressSDNode *Node, uint64_t Offset,
93                              uint64_t Size, unsigned char *ByteSeq);
94   // Mapping from ConstantStruct global value to corresponding byte-list values
95   std::map<const void *, val_vec_type> cs_vals_;
96 };
97 } // namespace
98 
99 char BPFDAGToDAGISel::ID = 0;
100 
INITIALIZE_PASS(BPFDAGToDAGISel,DEBUG_TYPE,PASS_NAME,false,false)101 INITIALIZE_PASS(BPFDAGToDAGISel, DEBUG_TYPE, PASS_NAME, false, false)
102 
103 // ComplexPattern used on BPF Load/Store instructions
104 bool BPFDAGToDAGISel::SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset) {
105   // if Address is FI, get the TargetFrameIndex.
106   SDLoc DL(Addr);
107   if (auto *FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
108     Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
109     Offset = CurDAG->getTargetConstant(0, DL, MVT::i64);
110     return true;
111   }
112 
113   if (Addr.getOpcode() == ISD::TargetExternalSymbol ||
114       Addr.getOpcode() == ISD::TargetGlobalAddress)
115     return false;
116 
117   // Addresses of the form Addr+const or Addr|const
118   if (CurDAG->isBaseWithConstantOffset(Addr)) {
119     auto *CN = cast<ConstantSDNode>(Addr.getOperand(1));
120     if (isInt<16>(CN->getSExtValue())) {
121       // If the first operand is a FI, get the TargetFI Node
122       if (auto *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))
123         Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
124       else
125         Base = Addr.getOperand(0);
126 
127       Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);
128       return true;
129     }
130   }
131 
132   Base = Addr;
133   Offset = CurDAG->getTargetConstant(0, DL, MVT::i64);
134   return true;
135 }
136 
137 // ComplexPattern used on BPF FI instruction
SelectFIAddr(SDValue Addr,SDValue & Base,SDValue & Offset)138 bool BPFDAGToDAGISel::SelectFIAddr(SDValue Addr, SDValue &Base,
139                                    SDValue &Offset) {
140   SDLoc DL(Addr);
141 
142   if (!CurDAG->isBaseWithConstantOffset(Addr))
143     return false;
144 
145   // Addresses of the form Addr+const or Addr|const
146   auto *CN = cast<ConstantSDNode>(Addr.getOperand(1));
147   if (isInt<16>(CN->getSExtValue())) {
148     // If the first operand is a FI, get the TargetFI Node
149     if (auto *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))
150       Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
151     else
152       return false;
153 
154     Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);
155     return true;
156   }
157 
158   return false;
159 }
160 
SelectInlineAsmMemoryOperand(const SDValue & Op,InlineAsm::ConstraintCode ConstraintCode,std::vector<SDValue> & OutOps)161 bool BPFDAGToDAGISel::SelectInlineAsmMemoryOperand(
162     const SDValue &Op, InlineAsm::ConstraintCode ConstraintCode,
163     std::vector<SDValue> &OutOps) {
164   SDValue Op0, Op1;
165   switch (ConstraintCode) {
166   default:
167     return true;
168   case InlineAsm::ConstraintCode::m: // memory
169     if (!SelectAddr(Op, Op0, Op1))
170       return true;
171     break;
172   }
173 
174   SDLoc DL(Op);
175   SDValue AluOp = CurDAG->getTargetConstant(ISD::ADD, DL, MVT::i32);
176   OutOps.push_back(Op0);
177   OutOps.push_back(Op1);
178   OutOps.push_back(AluOp);
179   return false;
180 }
181 
Select(SDNode * Node)182 void BPFDAGToDAGISel::Select(SDNode *Node) {
183   unsigned Opcode = Node->getOpcode();
184 
185   // If we have a custom node, we already have selected!
186   if (Node->isMachineOpcode()) {
187     LLVM_DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << '\n');
188     return;
189   }
190 
191   // tablegen selection should be handled here.
192   switch (Opcode) {
193   default:
194     break;
195   case ISD::INTRINSIC_W_CHAIN: {
196     unsigned IntNo = Node->getConstantOperandVal(1);
197     switch (IntNo) {
198     case Intrinsic::bpf_load_byte:
199     case Intrinsic::bpf_load_half:
200     case Intrinsic::bpf_load_word: {
201       SDLoc DL(Node);
202       SDValue Chain = Node->getOperand(0);
203       SDValue N1 = Node->getOperand(1);
204       SDValue Skb = Node->getOperand(2);
205       SDValue N3 = Node->getOperand(3);
206 
207       SDValue R6Reg = CurDAG->getRegister(BPF::R6, MVT::i64);
208       Chain = CurDAG->getCopyToReg(Chain, DL, R6Reg, Skb, SDValue());
209       Node = CurDAG->UpdateNodeOperands(Node, Chain, N1, R6Reg, N3);
210       break;
211     }
212     }
213     break;
214   }
215 
216   case ISD::FrameIndex: {
217     int FI = cast<FrameIndexSDNode>(Node)->getIndex();
218     EVT VT = Node->getValueType(0);
219     SDValue TFI = CurDAG->getTargetFrameIndex(FI, VT);
220     unsigned Opc = BPF::MOV_rr;
221     if (Node->hasOneUse()) {
222       CurDAG->SelectNodeTo(Node, Opc, VT, TFI);
223       return;
224     }
225     ReplaceNode(Node, CurDAG->getMachineNode(Opc, SDLoc(Node), VT, TFI));
226     return;
227   }
228   }
229 
230   // Select the default instruction
231   SelectCode(Node);
232 }
233 
PreprocessLoad(SDNode * Node,SelectionDAG::allnodes_iterator & I)234 void BPFDAGToDAGISel::PreprocessLoad(SDNode *Node,
235                                      SelectionDAG::allnodes_iterator &I) {
236   union {
237     uint8_t c[8];
238     uint16_t s;
239     uint32_t i;
240     uint64_t d;
241   } new_val; // hold up the constant values replacing loads.
242   bool to_replace = false;
243   SDLoc DL(Node);
244   const LoadSDNode *LD = cast<LoadSDNode>(Node);
245   uint64_t size = LD->getMemOperand()->getSize();
246 
247   if (!size || size > 8 || (size & (size - 1)) || !LD->isSimple())
248     return;
249 
250   SDNode *LDAddrNode = LD->getOperand(1).getNode();
251   // Match LDAddr against either global_addr or (global_addr + offset)
252   unsigned opcode = LDAddrNode->getOpcode();
253   if (opcode == ISD::ADD) {
254     SDValue OP1 = LDAddrNode->getOperand(0);
255     SDValue OP2 = LDAddrNode->getOperand(1);
256 
257     // We want to find the pattern global_addr + offset
258     SDNode *OP1N = OP1.getNode();
259     if (OP1N->getOpcode() <= ISD::BUILTIN_OP_END || OP1N->getNumOperands() == 0)
260       return;
261 
262     LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');
263 
264     const GlobalAddressSDNode *GADN =
265         dyn_cast<GlobalAddressSDNode>(OP1N->getOperand(0).getNode());
266     const ConstantSDNode *CDN = dyn_cast<ConstantSDNode>(OP2.getNode());
267     if (GADN && CDN)
268       to_replace =
269           getConstantFieldValue(GADN, CDN->getZExtValue(), size, new_val.c);
270   } else if (LDAddrNode->getOpcode() > ISD::BUILTIN_OP_END &&
271              LDAddrNode->getNumOperands() > 0) {
272     LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');
273 
274     SDValue OP1 = LDAddrNode->getOperand(0);
275     if (const GlobalAddressSDNode *GADN =
276             dyn_cast<GlobalAddressSDNode>(OP1.getNode()))
277       to_replace = getConstantFieldValue(GADN, 0, size, new_val.c);
278   }
279 
280   if (!to_replace)
281     return;
282 
283   // replacing the old with a new value
284   uint64_t val;
285   if (size == 1)
286     val = new_val.c[0];
287   else if (size == 2)
288     val = new_val.s;
289   else if (size == 4)
290     val = new_val.i;
291   else {
292     val = new_val.d;
293   }
294 
295   LLVM_DEBUG(dbgs() << "Replacing load of size " << size << " with constant "
296                     << val << '\n');
297   SDValue NVal = CurDAG->getConstant(val, DL, LD->getValueType(0));
298 
299   // After replacement, the current node is dead, we need to
300   // go backward one step to make iterator still work
301   I--;
302   SDValue From[] = {SDValue(Node, 0), SDValue(Node, 1)};
303   SDValue To[] = {NVal, NVal};
304   CurDAG->ReplaceAllUsesOfValuesWith(From, To, 2);
305   I++;
306   // It is safe to delete node now
307   CurDAG->DeleteNode(Node);
308 }
309 
PreprocessISelDAG()310 void BPFDAGToDAGISel::PreprocessISelDAG() {
311   // Iterate through all nodes, interested in the following case:
312   //
313   //  . loads from ConstantStruct or ConstantArray of constructs
314   //    which can be turns into constant itself, with this we can
315   //    avoid reading from read-only section at runtime.
316   //
317   //  . Removing redundant AND for intrinsic narrow loads.
318   for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
319                                        E = CurDAG->allnodes_end();
320        I != E;) {
321     SDNode *Node = &*I++;
322     unsigned Opcode = Node->getOpcode();
323     if (Opcode == ISD::LOAD)
324       PreprocessLoad(Node, I);
325     else if (Opcode == ISD::AND)
326       PreprocessTrunc(Node, I);
327   }
328 }
329 
getConstantFieldValue(const GlobalAddressSDNode * Node,uint64_t Offset,uint64_t Size,unsigned char * ByteSeq)330 bool BPFDAGToDAGISel::getConstantFieldValue(const GlobalAddressSDNode *Node,
331                                             uint64_t Offset, uint64_t Size,
332                                             unsigned char *ByteSeq) {
333   const GlobalVariable *V = dyn_cast<GlobalVariable>(Node->getGlobal());
334 
335   if (!V || !V->hasInitializer() || !V->isConstant())
336     return false;
337 
338   const Constant *Init = V->getInitializer();
339   const DataLayout &DL = CurDAG->getDataLayout();
340   val_vec_type TmpVal;
341 
342   auto it = cs_vals_.find(static_cast<const void *>(Init));
343   if (it != cs_vals_.end()) {
344     TmpVal = it->second;
345   } else {
346     uint64_t total_size = 0;
347     if (const ConstantStruct *CS = dyn_cast<ConstantStruct>(Init))
348       total_size =
349           DL.getStructLayout(cast<StructType>(CS->getType()))->getSizeInBytes();
350     else if (const ConstantArray *CA = dyn_cast<ConstantArray>(Init))
351       total_size = DL.getTypeAllocSize(CA->getType()->getElementType()) *
352                    CA->getNumOperands();
353     else
354       return false;
355 
356     val_vec_type Vals(total_size, 0);
357     if (fillGenericConstant(DL, Init, Vals, 0) == false)
358       return false;
359     cs_vals_[static_cast<const void *>(Init)] = Vals;
360     TmpVal = std::move(Vals);
361   }
362 
363   // test whether host endianness matches target
364   union {
365     uint8_t c[2];
366     uint16_t s;
367   } test_buf;
368   uint16_t test_val = 0x2345;
369   if (DL.isLittleEndian())
370     support::endian::write16le(test_buf.c, test_val);
371   else
372     support::endian::write16be(test_buf.c, test_val);
373 
374   bool endian_match = test_buf.s == test_val;
375   for (uint64_t i = Offset, j = 0; i < Offset + Size; i++, j++)
376     ByteSeq[j] = endian_match ? TmpVal[i] : TmpVal[Offset + Size - 1 - j];
377 
378   return true;
379 }
380 
fillGenericConstant(const DataLayout & DL,const Constant * CV,val_vec_type & Vals,uint64_t Offset)381 bool BPFDAGToDAGISel::fillGenericConstant(const DataLayout &DL,
382                                           const Constant *CV,
383                                           val_vec_type &Vals, uint64_t Offset) {
384   uint64_t Size = DL.getTypeAllocSize(CV->getType());
385 
386   if (isa<ConstantAggregateZero>(CV) || isa<UndefValue>(CV))
387     return true; // already done
388 
389   if (const ConstantInt *CI = dyn_cast<ConstantInt>(CV)) {
390     uint64_t val = CI->getZExtValue();
391     LLVM_DEBUG(dbgs() << "Byte array at offset " << Offset << " with value "
392                       << val << '\n');
393 
394     if (Size > 8 || (Size & (Size - 1)))
395       return false;
396 
397     // Store based on target endian
398     for (uint64_t i = 0; i < Size; ++i) {
399       Vals[Offset + i] = DL.isLittleEndian()
400                              ? ((val >> (i * 8)) & 0xFF)
401                              : ((val >> ((Size - i - 1) * 8)) & 0xFF);
402     }
403     return true;
404   }
405 
406   if (const ConstantDataArray *CDA = dyn_cast<ConstantDataArray>(CV))
407     return fillConstantDataArray(DL, CDA, Vals, Offset);
408 
409   if (const ConstantArray *CA = dyn_cast<ConstantArray>(CV))
410     return fillConstantArray(DL, CA, Vals, Offset);
411 
412   if (const ConstantStruct *CVS = dyn_cast<ConstantStruct>(CV))
413     return fillConstantStruct(DL, CVS, Vals, Offset);
414 
415   return false;
416 }
417 
fillConstantDataArray(const DataLayout & DL,const ConstantDataArray * CDA,val_vec_type & Vals,int Offset)418 bool BPFDAGToDAGISel::fillConstantDataArray(const DataLayout &DL,
419                                             const ConstantDataArray *CDA,
420                                             val_vec_type &Vals, int Offset) {
421   for (unsigned i = 0, e = CDA->getNumElements(); i != e; ++i) {
422     if (fillGenericConstant(DL, CDA->getElementAsConstant(i), Vals, Offset) ==
423         false)
424       return false;
425     Offset += DL.getTypeAllocSize(CDA->getElementAsConstant(i)->getType());
426   }
427 
428   return true;
429 }
430 
fillConstantArray(const DataLayout & DL,const ConstantArray * CA,val_vec_type & Vals,int Offset)431 bool BPFDAGToDAGISel::fillConstantArray(const DataLayout &DL,
432                                         const ConstantArray *CA,
433                                         val_vec_type &Vals, int Offset) {
434   for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) {
435     if (fillGenericConstant(DL, CA->getOperand(i), Vals, Offset) == false)
436       return false;
437     Offset += DL.getTypeAllocSize(CA->getOperand(i)->getType());
438   }
439 
440   return true;
441 }
442 
fillConstantStruct(const DataLayout & DL,const ConstantStruct * CS,val_vec_type & Vals,int Offset)443 bool BPFDAGToDAGISel::fillConstantStruct(const DataLayout &DL,
444                                          const ConstantStruct *CS,
445                                          val_vec_type &Vals, int Offset) {
446   const StructLayout *Layout = DL.getStructLayout(CS->getType());
447   for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) {
448     const Constant *Field = CS->getOperand(i);
449     uint64_t SizeSoFar = Layout->getElementOffset(i);
450     if (fillGenericConstant(DL, Field, Vals, Offset + SizeSoFar) == false)
451       return false;
452   }
453   return true;
454 }
455 
PreprocessTrunc(SDNode * Node,SelectionDAG::allnodes_iterator & I)456 void BPFDAGToDAGISel::PreprocessTrunc(SDNode *Node,
457                                       SelectionDAG::allnodes_iterator &I) {
458   ConstantSDNode *MaskN = dyn_cast<ConstantSDNode>(Node->getOperand(1));
459   if (!MaskN)
460     return;
461 
462   // The Reg operand should be a virtual register, which is defined
463   // outside the current basic block. DAG combiner has done a pretty
464   // good job in removing truncating inside a single basic block except
465   // when the Reg operand comes from bpf_load_[byte | half | word] for
466   // which the generic optimizer doesn't understand their results are
467   // zero extended.
468   SDValue BaseV = Node->getOperand(0);
469   if (BaseV.getOpcode() != ISD::INTRINSIC_W_CHAIN)
470     return;
471 
472   unsigned IntNo = BaseV->getConstantOperandVal(1);
473   uint64_t MaskV = MaskN->getZExtValue();
474 
475   if (!((IntNo == Intrinsic::bpf_load_byte && MaskV == 0xFF) ||
476         (IntNo == Intrinsic::bpf_load_half && MaskV == 0xFFFF) ||
477         (IntNo == Intrinsic::bpf_load_word && MaskV == 0xFFFFFFFF)))
478     return;
479 
480   LLVM_DEBUG(dbgs() << "Remove the redundant AND operation in: ";
481              Node->dump(); dbgs() << '\n');
482 
483   I--;
484   CurDAG->ReplaceAllUsesWith(SDValue(Node, 0), BaseV);
485   I++;
486   CurDAG->DeleteNode(Node);
487 }
488 
createBPFISelDag(BPFTargetMachine & TM)489 FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) {
490   return new BPFDAGToDAGISel(TM);
491 }
492