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 }