BPFISelDAGToDAG.cpp revision 363496 
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
34using namespace llvm;
35
36#define DEBUG_TYPE "bpf-isel"
37
38// Instruction Selector Implementation
39namespace {
40
41class 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
47public:
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
67private:
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
100bool 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
136bool 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
160bool 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
180void 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
244void 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
320void 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
340bool 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
391bool 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
428bool 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
441bool 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
453bool 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
466void 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
501FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) {
502  return new BPFDAGToDAGISel(TM);
503}
504