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