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