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