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#define PASS_NAME "BPF DAG->DAG Pattern Instruction Selection"
38
39// Instruction Selector Implementation
40namespace {
41
42class 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
48public:
49  static char ID;
50
51  BPFDAGToDAGISel() = delete;
52
53  explicit BPFDAGToDAGISel(BPFTargetMachine &TM)
54      : SelectionDAGISel(ID, TM), Subtarget(nullptr) {}
55
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
68private:
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
99char BPFDAGToDAGISel::ID = 0;
100
101INITIALIZE_PASS(BPFDAGToDAGISel, DEBUG_TYPE, PASS_NAME, false, false)
102
103// ComplexPattern used on BPF Load/Store instructions
104bool 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
138bool 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
161bool 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
182void 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
234void 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
310void 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
330bool 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
381bool 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
418bool 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
431bool 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
443bool 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
456void 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
489FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) {
490  return new BPFDAGToDAGISel(TM);
491}
492