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   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
  68 private:
  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
  99 char BPFDAGToDAGISel::ID = 0;
 100
 101 INITIALIZE_PASS(BPFDAGToDAGISel, DEBUG_TYPE, PASS_NAME, false, false)
 102
 103 // ComplexPattern used on BPF Load/Store instructions
 104 bool 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
 138 bool 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
 161 bool 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
 182 void 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::SDIV: {
 196     if (!Subtarget->hasSdivSmod()) {
 197       DebugLoc Empty;
 198       const DebugLoc &DL = Node->getDebugLoc();
 199       if (DL != Empty)
 200         errs() << "Error at line " << DL.getLine() << ": ";
 201       else
 202         errs() << "Error: ";
 203       errs() << "Unsupport signed division for DAG: ";
 204       Node->print(errs(), CurDAG);
 205       errs() << "Please convert to unsigned div/mod.\n";
 206     }
 207     break;
 208   }
 209   case ISD::INTRINSIC_W_CHAIN: {
 210     unsigned IntNo = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue();
 211     switch (IntNo) {
 212     case Intrinsic::bpf_load_byte:
 213     case Intrinsic::bpf_load_half:
 214     case Intrinsic::bpf_load_word: {
 215       SDLoc DL(Node);
 216       SDValue Chain = Node->getOperand(0);
 217       SDValue N1 = Node->getOperand(1);
 218       SDValue Skb = Node->getOperand(2);
 219       SDValue N3 = Node->getOperand(3);
 220
 221       SDValue R6Reg = CurDAG->getRegister(BPF::R6, MVT::i64);
 222       Chain = CurDAG->getCopyToReg(Chain, DL, R6Reg, Skb, SDValue());
 223       Node = CurDAG->UpdateNodeOperands(Node, Chain, N1, R6Reg, N3);
 224       break;
 225     }
 226     }
 227     break;
 228   }
 229
 230   case ISD::FrameIndex: {
 231     int FI = cast<FrameIndexSDNode>(Node)->getIndex();
 232     EVT VT = Node->getValueType(0);
 233     SDValue TFI = CurDAG->getTargetFrameIndex(FI, VT);
 234     unsigned Opc = BPF::MOV_rr;
 235     if (Node->hasOneUse()) {
 236       CurDAG->SelectNodeTo(Node, Opc, VT, TFI);
 237       return;
 238     }
 239     ReplaceNode(Node, CurDAG->getMachineNode(Opc, SDLoc(Node), VT, TFI));
 240     return;
 241   }
 242   }
 243
 244   // Select the default instruction
 245   SelectCode(Node);
 246 }
 247
 248 void BPFDAGToDAGISel::PreprocessLoad(SDNode *Node,
 249                                      SelectionDAG::allnodes_iterator &I) {
 250   union {
 251     uint8_t c[8];
 252     uint16_t s;
 253     uint32_t i;
 254     uint64_t d;
 255   } new_val; // hold up the constant values replacing loads.
 256   bool to_replace = false;
 257   SDLoc DL(Node);
 258   const LoadSDNode *LD = cast<LoadSDNode>(Node);
 259   uint64_t size = LD->getMemOperand()->getSize();
 260
 261   if (!size || size > 8 || (size & (size - 1)) || !LD->isSimple())
 262     return;
 263
 264   SDNode *LDAddrNode = LD->getOperand(1).getNode();
 265   // Match LDAddr against either global_addr or (global_addr + offset)
 266   unsigned opcode = LDAddrNode->getOpcode();
 267   if (opcode == ISD::ADD) {
 268     SDValue OP1 = LDAddrNode->getOperand(0);
 269     SDValue OP2 = LDAddrNode->getOperand(1);
 270
 271     // We want to find the pattern global_addr + offset
 272     SDNode *OP1N = OP1.getNode();
 273     if (OP1N->getOpcode() <= ISD::BUILTIN_OP_END || OP1N->getNumOperands() == 0)
 274       return;
 275
 276     LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');
 277
 278     const GlobalAddressSDNode *GADN =
 279         dyn_cast<GlobalAddressSDNode>(OP1N->getOperand(0).getNode());
 280     const ConstantSDNode *CDN = dyn_cast<ConstantSDNode>(OP2.getNode());
 281     if (GADN && CDN)
 282       to_replace =
 283           getConstantFieldValue(GADN, CDN->getZExtValue(), size, new_val.c);
 284   } else if (LDAddrNode->getOpcode() > ISD::BUILTIN_OP_END &&
 285              LDAddrNode->getNumOperands() > 0) {
 286     LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');
 287
 288     SDValue OP1 = LDAddrNode->getOperand(0);
 289     if (const GlobalAddressSDNode *GADN =
 290             dyn_cast<GlobalAddressSDNode>(OP1.getNode()))
 291       to_replace = getConstantFieldValue(GADN, 0, size, new_val.c);
 292   }
 293
 294   if (!to_replace)
 295     return;
 296
 297   // replacing the old with a new value
 298   uint64_t val;
 299   if (size == 1)
 300     val = new_val.c[0];
 301   else if (size == 2)
 302     val = new_val.s;
 303   else if (size == 4)
 304     val = new_val.i;
 305   else {
 306     val = new_val.d;
 307   }
 308
 309   LLVM_DEBUG(dbgs() << "Replacing load of size " << size << " with constant "
 310                     << val << '\n');
 311   SDValue NVal = CurDAG->getConstant(val, DL, LD->getValueType(0));
 312
 313   // After replacement, the current node is dead, we need to
 314   // go backward one step to make iterator still work
 315   I--;
 316   SDValue From[] = {SDValue(Node, 0), SDValue(Node, 1)};
 317   SDValue To[] = {NVal, NVal};
 318   CurDAG->ReplaceAllUsesOfValuesWith(From, To, 2);
 319   I++;
 320   // It is safe to delete node now
 321   CurDAG->DeleteNode(Node);
 322 }
 323
 324 void BPFDAGToDAGISel::PreprocessISelDAG() {
 325   // Iterate through all nodes, interested in the following case:
 326   //
 327   //  . loads from ConstantStruct or ConstantArray of constructs
 328   //    which can be turns into constant itself, with this we can
 329   //    avoid reading from read-only section at runtime.
 330   //
 331   //  . Removing redundant AND for intrinsic narrow loads.
 332   for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
 333                                        E = CurDAG->allnodes_end();
 334        I != E;) {
 335     SDNode *Node = &*I++;
 336     unsigned Opcode = Node->getOpcode();
 337     if (Opcode == ISD::LOAD)
 338       PreprocessLoad(Node, I);
 339     else if (Opcode == ISD::AND)
 340       PreprocessTrunc(Node, I);
 341   }
 342 }
 343
 344 bool BPFDAGToDAGISel::getConstantFieldValue(const GlobalAddressSDNode *Node,
 345                                             uint64_t Offset, uint64_t Size,
 346                                             unsigned char *ByteSeq) {
 347   const GlobalVariable *V = dyn_cast<GlobalVariable>(Node->getGlobal());
 348
 349   if (!V || !V->hasInitializer() || !V->isConstant())
 350     return false;
 351
 352   const Constant *Init = V->getInitializer();
 353   const DataLayout &DL = CurDAG->getDataLayout();
 354   val_vec_type TmpVal;
 355
 356   auto it = cs_vals_.find(static_cast<const void *>(Init));
 357   if (it != cs_vals_.end()) {
 358     TmpVal = it->second;
 359   } else {
 360     uint64_t total_size = 0;
 361     if (const ConstantStruct *CS = dyn_cast<ConstantStruct>(Init))
 362       total_size =
 363           DL.getStructLayout(cast<StructType>(CS->getType()))->getSizeInBytes();
 364     else if (const ConstantArray *CA = dyn_cast<ConstantArray>(Init))
 365       total_size = DL.getTypeAllocSize(CA->getType()->getElementType()) *
 366                    CA->getNumOperands();
 367     else
 368       return false;
 369
 370     val_vec_type Vals(total_size, 0);
 371     if (fillGenericConstant(DL, Init, Vals, 0) == false)
 372       return false;
 373     cs_vals_[static_cast<const void *>(Init)] = Vals;
 374     TmpVal = std::move(Vals);
 375   }
 376
 377   // test whether host endianness matches target
 378   union {
 379     uint8_t c[2];
 380     uint16_t s;
 381   } test_buf;
 382   uint16_t test_val = 0x2345;
 383   if (DL.isLittleEndian())
 384     support::endian::write16le(test_buf.c, test_val);
 385   else
 386     support::endian::write16be(test_buf.c, test_val);
 387
 388   bool endian_match = test_buf.s == test_val;
 389   for (uint64_t i = Offset, j = 0; i < Offset + Size; i++, j++)
 390     ByteSeq[j] = endian_match ? TmpVal[i] : TmpVal[Offset + Size - 1 - j];
 391
 392   return true;
 393 }
 394
 395 bool BPFDAGToDAGISel::fillGenericConstant(const DataLayout &DL,
 396                                           const Constant *CV,
 397                                           val_vec_type &Vals, uint64_t Offset) {
 398   uint64_t Size = DL.getTypeAllocSize(CV->getType());
 399
 400   if (isa<ConstantAggregateZero>(CV) || isa<UndefValue>(CV))
 401     return true; // already done
 402
 403   if (const ConstantInt *CI = dyn_cast<ConstantInt>(CV)) {
 404     uint64_t val = CI->getZExtValue();
 405     LLVM_DEBUG(dbgs() << "Byte array at offset " << Offset << " with value "
 406                       << val << '\n');
 407
 408     if (Size > 8 || (Size & (Size - 1)))
 409       return false;
 410
 411     // Store based on target endian
 412     for (uint64_t i = 0; i < Size; ++i) {
 413       Vals[Offset + i] = DL.isLittleEndian()
 414                              ? ((val >> (i * 8)) & 0xFF)
 415                              : ((val >> ((Size - i - 1) * 8)) & 0xFF);
 416     }
 417     return true;
 418   }
 419
 420   if (const ConstantDataArray *CDA = dyn_cast<ConstantDataArray>(CV))
 421     return fillConstantDataArray(DL, CDA, Vals, Offset);
 422
 423   if (const ConstantArray *CA = dyn_cast<ConstantArray>(CV))
 424     return fillConstantArray(DL, CA, Vals, Offset);
 425
 426   if (const ConstantStruct *CVS = dyn_cast<ConstantStruct>(CV))
 427     return fillConstantStruct(DL, CVS, Vals, Offset);
 428
 429   return false;
 430 }
 431
 432 bool BPFDAGToDAGISel::fillConstantDataArray(const DataLayout &DL,
 433                                             const ConstantDataArray *CDA,
 434                                             val_vec_type &Vals, int Offset) {
 435   for (unsigned i = 0, e = CDA->getNumElements(); i != e; ++i) {
 436     if (fillGenericConstant(DL, CDA->getElementAsConstant(i), Vals, Offset) ==
 437         false)
 438       return false;
 439     Offset += DL.getTypeAllocSize(CDA->getElementAsConstant(i)->getType());
 440   }
 441
 442   return true;
 443 }
 444
 445 bool BPFDAGToDAGISel::fillConstantArray(const DataLayout &DL,
 446                                         const ConstantArray *CA,
 447                                         val_vec_type &Vals, int Offset) {
 448   for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) {
 449     if (fillGenericConstant(DL, CA->getOperand(i), Vals, Offset) == false)
 450       return false;
 451     Offset += DL.getTypeAllocSize(CA->getOperand(i)->getType());
 452   }
 453
 454   return true;
 455 }
 456
 457 bool BPFDAGToDAGISel::fillConstantStruct(const DataLayout &DL,
 458                                          const ConstantStruct *CS,
 459                                          val_vec_type &Vals, int Offset) {
 460   const StructLayout *Layout = DL.getStructLayout(CS->getType());
 461   for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) {
 462     const Constant *Field = CS->getOperand(i);
 463     uint64_t SizeSoFar = Layout->getElementOffset(i);
 464     if (fillGenericConstant(DL, Field, Vals, Offset + SizeSoFar) == false)
 465       return false;
 466   }
 467   return true;
 468 }
 469
 470 void BPFDAGToDAGISel::PreprocessTrunc(SDNode *Node,
 471                                       SelectionDAG::allnodes_iterator &I) {
 472   ConstantSDNode *MaskN = dyn_cast<ConstantSDNode>(Node->getOperand(1));
 473   if (!MaskN)
 474     return;
 475
 476   // The Reg operand should be a virtual register, which is defined
 477   // outside the current basic block. DAG combiner has done a pretty
 478   // good job in removing truncating inside a single basic block except
 479   // when the Reg operand comes from bpf_load_[byte | half | word] for
 480   // which the generic optimizer doesn't understand their results are
 481   // zero extended.
 482   SDValue BaseV = Node->getOperand(0);
 483   if (BaseV.getOpcode() != ISD::INTRINSIC_W_CHAIN)
 484     return;
 485
 486   unsigned IntNo = cast<ConstantSDNode>(BaseV->getOperand(1))->getZExtValue();
 487   uint64_t MaskV = MaskN->getZExtValue();
 488
 489   if (!((IntNo == Intrinsic::bpf_load_byte && MaskV == 0xFF) ||
 490         (IntNo == Intrinsic::bpf_load_half && MaskV == 0xFFFF) ||
 491         (IntNo == Intrinsic::bpf_load_word && MaskV == 0xFFFFFFFF)))
 492     return;
 493
 494   LLVM_DEBUG(dbgs() << "Remove the redundant AND operation in: ";
 495              Node->dump(); dbgs() << '\n');
 496
 497   I--;
 498   CurDAG->ReplaceAllUsesWith(SDValue(Node, 0), BaseV);
 499   I++;
 500   CurDAG->DeleteNode(Node);
 501 }
 502
 503 FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) {
 504   return new BPFDAGToDAGISel(TM);
 505 }