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