contrib/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/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     curr_func_ = nullptr;
  50   }
  51
  52   StringRef getPassName() const override {
  53     return "BPF DAG->DAG Pattern Instruction Selection";
  54   }
  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, unsigned ConstraintCode,
  65                                     std::vector<SDValue> &OutOps) override;
  66
  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 PreprocessCopyToReg(SDNode *Node);
  81   void PreprocessTrunc(SDNode *Node, SelectionDAG::allnodes_iterator &I);
  82
  83   // Find constants from a constant structure
  84   typedef std::vector<unsigned char> val_vec_type;
  85   bool fillGenericConstant(const DataLayout &DL, const Constant *CV,
  86                            val_vec_type &Vals, uint64_t Offset);
  87   bool fillConstantDataArray(const DataLayout &DL, const ConstantDataArray *CDA,
  88                              val_vec_type &Vals, int Offset);
  89   bool fillConstantArray(const DataLayout &DL, const ConstantArray *CA,
  90                          val_vec_type &Vals, int Offset);
  91   bool fillConstantStruct(const DataLayout &DL, const ConstantStruct *CS,
  92                           val_vec_type &Vals, int Offset);
  93   bool getConstantFieldValue(const GlobalAddressSDNode *Node, uint64_t Offset,
  94                              uint64_t Size, unsigned char *ByteSeq);
  95   bool checkLoadDef(unsigned DefReg, unsigned match_load_op);
  96
  97   // Mapping from ConstantStruct global value to corresponding byte-list values
  98   std::map<const void *, val_vec_type> cs_vals_;
  99   // Mapping from vreg to load memory opcode
 100   std::map<unsigned, unsigned> load_to_vreg_;
 101   // Current function
 102   const Function *curr_func_;
 103 };
 104 } // namespace
 105
 106 // ComplexPattern used on BPF Load/Store instructions
 107 bool BPFDAGToDAGISel::SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset) {
 108   // if Address is FI, get the TargetFrameIndex.
 109   SDLoc DL(Addr);
 110   if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
 111     Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
 112     Offset = CurDAG->getTargetConstant(0, DL, MVT::i64);
 113     return true;
 114   }
 115
 116   if (Addr.getOpcode() == ISD::TargetExternalSymbol ||
 117       Addr.getOpcode() == ISD::TargetGlobalAddress)
 118     return false;
 119
 120   // Addresses of the form Addr+const or Addr|const
 121   if (CurDAG->isBaseWithConstantOffset(Addr)) {
 122     ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1));
 123     if (isInt<16>(CN->getSExtValue())) {
 124
 125       // If the first operand is a FI, get the TargetFI Node
 126       if (FrameIndexSDNode *FIN =
 127               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   ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1));
 152   if (isInt<16>(CN->getSExtValue())) {
 153
 154     // If the first operand is a FI, get the TargetFI Node
 155     if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))
 156       Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
 157     else
 158       return false;
 159
 160     Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);
 161     return true;
 162   }
 163
 164   return false;
 165 }
 166
 167 bool BPFDAGToDAGISel::SelectInlineAsmMemoryOperand(
 168     const SDValue &Op, unsigned ConstraintCode, std::vector<SDValue> &OutOps) {
 169   SDValue Op0, Op1;
 170   switch (ConstraintCode) {
 171   default:
 172     return true;
 173   case InlineAsm::Constraint_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::SDIV: {
 201     DebugLoc Empty;
 202     const DebugLoc &DL = Node->getDebugLoc();
 203     if (DL != Empty)
 204       errs() << "Error at line " << DL.getLine() << ": ";
 205     else
 206       errs() << "Error: ";
 207     errs() << "Unsupport signed division for DAG: ";
 208     Node->print(errs(), CurDAG);
 209     errs() << "Please convert to unsigned div/mod.\n";
 210     break;
 211   }
 212   case ISD::INTRINSIC_W_CHAIN: {
 213     unsigned IntNo = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue();
 214     switch (IntNo) {
 215     case Intrinsic::bpf_load_byte:
 216     case Intrinsic::bpf_load_half:
 217     case Intrinsic::bpf_load_word: {
 218       SDLoc DL(Node);
 219       SDValue Chain = Node->getOperand(0);
 220       SDValue N1 = Node->getOperand(1);
 221       SDValue Skb = Node->getOperand(2);
 222       SDValue N3 = Node->getOperand(3);
 223
 224       SDValue R6Reg = CurDAG->getRegister(BPF::R6, MVT::i64);
 225       Chain = CurDAG->getCopyToReg(Chain, DL, R6Reg, Skb, SDValue());
 226       Node = CurDAG->UpdateNodeOperands(Node, Chain, N1, R6Reg, N3);
 227       break;
 228     }
 229     }
 230     break;
 231   }
 232
 233   case ISD::FrameIndex: {
 234     int FI = cast<FrameIndexSDNode>(Node)->getIndex();
 235     EVT VT = Node->getValueType(0);
 236     SDValue TFI = CurDAG->getTargetFrameIndex(FI, VT);
 237     unsigned Opc = BPF::MOV_rr;
 238     if (Node->hasOneUse()) {
 239       CurDAG->SelectNodeTo(Node, Opc, VT, TFI);
 240       return;
 241     }
 242     ReplaceNode(Node, CurDAG->getMachineNode(Opc, SDLoc(Node), VT, TFI));
 243     return;
 244   }
 245   }
 246
 247   // Select the default instruction
 248   SelectCode(Node);
 249 }
 250
 251 void BPFDAGToDAGISel::PreprocessLoad(SDNode *Node,
 252                                      SelectionDAG::allnodes_iterator &I) {
 253   union {
 254     uint8_t c[8];
 255     uint16_t s;
 256     uint32_t i;
 257     uint64_t d;
 258   } new_val; // hold up the constant values replacing loads.
 259   bool to_replace = false;
 260   SDLoc DL(Node);
 261   const LoadSDNode *LD = cast<LoadSDNode>(Node);
 262   uint64_t size = LD->getMemOperand()->getSize();
 263
 264   if (!size || size > 8 || (size & (size - 1)))
 265     return;
 266
 267   SDNode *LDAddrNode = LD->getOperand(1).getNode();
 268   // Match LDAddr against either global_addr or (global_addr + offset)
 269   unsigned opcode = LDAddrNode->getOpcode();
 270   if (opcode == ISD::ADD) {
 271     SDValue OP1 = LDAddrNode->getOperand(0);
 272     SDValue OP2 = LDAddrNode->getOperand(1);
 273
 274     // We want to find the pattern global_addr + offset
 275     SDNode *OP1N = OP1.getNode();
 276     if (OP1N->getOpcode() <= ISD::BUILTIN_OP_END || OP1N->getNumOperands() == 0)
 277       return;
 278
 279     LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');
 280
 281     const GlobalAddressSDNode *GADN =
 282         dyn_cast<GlobalAddressSDNode>(OP1N->getOperand(0).getNode());
 283     const ConstantSDNode *CDN = dyn_cast<ConstantSDNode>(OP2.getNode());
 284     if (GADN && CDN)
 285       to_replace =
 286           getConstantFieldValue(GADN, CDN->getZExtValue(), size, new_val.c);
 287   } else if (LDAddrNode->getOpcode() > ISD::BUILTIN_OP_END &&
 288              LDAddrNode->getNumOperands() > 0) {
 289     LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');
 290
 291     SDValue OP1 = LDAddrNode->getOperand(0);
 292     if (const GlobalAddressSDNode *GADN =
 293             dyn_cast<GlobalAddressSDNode>(OP1.getNode()))
 294       to_replace = getConstantFieldValue(GADN, 0, size, new_val.c);
 295   }
 296
 297   if (!to_replace)
 298     return;
 299
 300   // replacing the old with a new value
 301   uint64_t val;
 302   if (size == 1)
 303     val = new_val.c[0];
 304   else if (size == 2)
 305     val = new_val.s;
 306   else if (size == 4)
 307     val = new_val.i;
 308   else {
 309     val = new_val.d;
 310   }
 311
 312   LLVM_DEBUG(dbgs() << "Replacing load of size " << size << " with constant "
 313                     << val << '\n');
 314   SDValue NVal = CurDAG->getConstant(val, DL, MVT::i64);
 315
 316   // After replacement, the current node is dead, we need to
 317   // go backward one step to make iterator still work
 318   I--;
 319   SDValue From[] = {SDValue(Node, 0), SDValue(Node, 1)};
 320   SDValue To[] = {NVal, NVal};
 321   CurDAG->ReplaceAllUsesOfValuesWith(From, To, 2);
 322   I++;
 323   // It is safe to delete node now
 324   CurDAG->DeleteNode(Node);
 325 }
 326
 327 void BPFDAGToDAGISel::PreprocessISelDAG() {
 328   // Iterate through all nodes, interested in the following cases:
 329   //
 330   //  . loads from ConstantStruct or ConstantArray of constructs
 331   //    which can be turns into constant itself, with this we can
 332   //    avoid reading from read-only section at runtime.
 333   //
 334   //  . reg truncating is often the result of 8/16/32bit->64bit or
 335   //    8/16bit->32bit conversion. If the reg value is loaded with
 336   //    masked byte width, the AND operation can be removed since
 337   //    BPF LOAD already has zero extension.
 338   //
 339   //    This also solved a correctness issue.
 340   //    In BPF socket-related program, e.g., __sk_buff->{data, data_end}
 341   //    are 32-bit registers, but later on, kernel verifier will rewrite
 342   //    it with 64-bit value. Therefore, truncating the value after the
 343   //    load will result in incorrect code.
 344
 345   // clear the load_to_vreg_ map so that we have a clean start
 346   // for this function.
 347   if (!curr_func_) {
 348     curr_func_ = FuncInfo->Fn;
 349   } else if (curr_func_ != FuncInfo->Fn) {
 350     load_to_vreg_.clear();
 351     curr_func_ = FuncInfo->Fn;
 352   }
 353
 354   for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
 355                                        E = CurDAG->allnodes_end();
 356        I != E;) {
 357     SDNode *Node = &*I++;
 358     unsigned Opcode = Node->getOpcode();
 359     if (Opcode == ISD::LOAD)
 360       PreprocessLoad(Node, I);
 361     else if (Opcode == ISD::CopyToReg)
 362       PreprocessCopyToReg(Node);
 363     else if (Opcode == ISD::AND)
 364       PreprocessTrunc(Node, I);
 365   }
 366 }
 367
 368 bool BPFDAGToDAGISel::getConstantFieldValue(const GlobalAddressSDNode *Node,
 369                                             uint64_t Offset, uint64_t Size,
 370                                             unsigned char *ByteSeq) {
 371   const GlobalVariable *V = dyn_cast<GlobalVariable>(Node->getGlobal());
 372
 373   if (!V || !V->hasInitializer())
 374     return false;
 375
 376   const Constant *Init = V->getInitializer();
 377   const DataLayout &DL = CurDAG->getDataLayout();
 378   val_vec_type TmpVal;
 379
 380   auto it = cs_vals_.find(static_cast<const void *>(Init));
 381   if (it != cs_vals_.end()) {
 382     TmpVal = it->second;
 383   } else {
 384     uint64_t total_size = 0;
 385     if (const ConstantStruct *CS = dyn_cast<ConstantStruct>(Init))
 386       total_size =
 387           DL.getStructLayout(cast<StructType>(CS->getType()))->getSizeInBytes();
 388     else if (const ConstantArray *CA = dyn_cast<ConstantArray>(Init))
 389       total_size = DL.getTypeAllocSize(CA->getType()->getElementType()) *
 390                    CA->getNumOperands();
 391     else
 392       return false;
 393
 394     val_vec_type Vals(total_size, 0);
 395     if (fillGenericConstant(DL, Init, Vals, 0) == false)
 396       return false;
 397     cs_vals_[static_cast<const void *>(Init)] = Vals;
 398     TmpVal = std::move(Vals);
 399   }
 400
 401   // test whether host endianness matches target
 402   union {
 403     uint8_t c[2];
 404     uint16_t s;
 405   } test_buf;
 406   uint16_t test_val = 0x2345;
 407   if (DL.isLittleEndian())
 408     support::endian::write16le(test_buf.c, test_val);
 409   else
 410     support::endian::write16be(test_buf.c, test_val);
 411
 412   bool endian_match = test_buf.s == test_val;
 413   for (uint64_t i = Offset, j = 0; i < Offset + Size; i++, j++)
 414     ByteSeq[j] = endian_match ? TmpVal[i] : TmpVal[Offset + Size - 1 - j];
 415
 416   return true;
 417 }
 418
 419 bool BPFDAGToDAGISel::fillGenericConstant(const DataLayout &DL,
 420                                           const Constant *CV,
 421                                           val_vec_type &Vals, uint64_t Offset) {
 422   uint64_t Size = DL.getTypeAllocSize(CV->getType());
 423
 424   if (isa<ConstantAggregateZero>(CV) || isa<UndefValue>(CV))
 425     return true; // already done
 426
 427   if (const ConstantInt *CI = dyn_cast<ConstantInt>(CV)) {
 428     uint64_t val = CI->getZExtValue();
 429     LLVM_DEBUG(dbgs() << "Byte array at offset " << Offset << " with value "
 430                       << val << '\n');
 431
 432     if (Size > 8 || (Size & (Size - 1)))
 433       return false;
 434
 435     // Store based on target endian
 436     for (uint64_t i = 0; i < Size; ++i) {
 437       Vals[Offset + i] = DL.isLittleEndian()
 438                              ? ((val >> (i * 8)) & 0xFF)
 439                              : ((val >> ((Size - i - 1) * 8)) & 0xFF);
 440     }
 441     return true;
 442   }
 443
 444   if (const ConstantDataArray *CDA = dyn_cast<ConstantDataArray>(CV))
 445     return fillConstantDataArray(DL, CDA, Vals, Offset);
 446
 447   if (const ConstantArray *CA = dyn_cast<ConstantArray>(CV))
 448     return fillConstantArray(DL, CA, Vals, Offset);
 449
 450   if (const ConstantStruct *CVS = dyn_cast<ConstantStruct>(CV))
 451     return fillConstantStruct(DL, CVS, Vals, Offset);
 452
 453   return false;
 454 }
 455
 456 bool BPFDAGToDAGISel::fillConstantDataArray(const DataLayout &DL,
 457                                             const ConstantDataArray *CDA,
 458                                             val_vec_type &Vals, int Offset) {
 459   for (unsigned i = 0, e = CDA->getNumElements(); i != e; ++i) {
 460     if (fillGenericConstant(DL, CDA->getElementAsConstant(i), Vals, Offset) ==
 461         false)
 462       return false;
 463     Offset += DL.getTypeAllocSize(CDA->getElementAsConstant(i)->getType());
 464   }
 465
 466   return true;
 467 }
 468
 469 bool BPFDAGToDAGISel::fillConstantArray(const DataLayout &DL,
 470                                         const ConstantArray *CA,
 471                                         val_vec_type &Vals, int Offset) {
 472   for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) {
 473     if (fillGenericConstant(DL, CA->getOperand(i), Vals, Offset) == false)
 474       return false;
 475     Offset += DL.getTypeAllocSize(CA->getOperand(i)->getType());
 476   }
 477
 478   return true;
 479 }
 480
 481 bool BPFDAGToDAGISel::fillConstantStruct(const DataLayout &DL,
 482                                          const ConstantStruct *CS,
 483                                          val_vec_type &Vals, int Offset) {
 484   const StructLayout *Layout = DL.getStructLayout(CS->getType());
 485   for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) {
 486     const Constant *Field = CS->getOperand(i);
 487     uint64_t SizeSoFar = Layout->getElementOffset(i);
 488     if (fillGenericConstant(DL, Field, Vals, Offset + SizeSoFar) == false)
 489       return false;
 490   }
 491   return true;
 492 }
 493
 494 void BPFDAGToDAGISel::PreprocessCopyToReg(SDNode *Node) {
 495   const RegisterSDNode *RegN = dyn_cast<RegisterSDNode>(Node->getOperand(1));
 496   if (!RegN || !TargetRegisterInfo::isVirtualRegister(RegN->getReg()))
 497     return;
 498
 499   const LoadSDNode *LD = dyn_cast<LoadSDNode>(Node->getOperand(2));
 500   if (!LD)
 501     return;
 502
 503   // Assign a load value to a virtual register. record its load width
 504   unsigned mem_load_op = 0;
 505   switch (LD->getMemOperand()->getSize()) {
 506   default:
 507     return;
 508   case 4:
 509     mem_load_op = BPF::LDW;
 510     break;
 511   case 2:
 512     mem_load_op = BPF::LDH;
 513     break;
 514   case 1:
 515     mem_load_op = BPF::LDB;
 516     break;
 517   }
 518
 519   LLVM_DEBUG(dbgs() << "Find Load Value to VReg "
 520                     << TargetRegisterInfo::virtReg2Index(RegN->getReg())
 521                     << '\n');
 522   load_to_vreg_[RegN->getReg()] = mem_load_op;
 523 }
 524
 525 void BPFDAGToDAGISel::PreprocessTrunc(SDNode *Node,
 526                                       SelectionDAG::allnodes_iterator &I) {
 527   ConstantSDNode *MaskN = dyn_cast<ConstantSDNode>(Node->getOperand(1));
 528   if (!MaskN)
 529     return;
 530
 531   // The Reg operand should be a virtual register, which is defined
 532   // outside the current basic block. DAG combiner has done a pretty
 533   // good job in removing truncating inside a single basic block except
 534   // when the Reg operand comes from bpf_load_[byte | half | word] for
 535   // which the generic optimizer doesn't understand their results are
 536   // zero extended.
 537   SDValue BaseV = Node->getOperand(0);
 538   if (BaseV.getOpcode() == ISD::INTRINSIC_W_CHAIN) {
 539     unsigned IntNo = cast<ConstantSDNode>(BaseV->getOperand(1))->getZExtValue();
 540     uint64_t MaskV = MaskN->getZExtValue();
 541
 542     if (!((IntNo == Intrinsic::bpf_load_byte && MaskV == 0xFF) ||
 543           (IntNo == Intrinsic::bpf_load_half && MaskV == 0xFFFF) ||
 544           (IntNo == Intrinsic::bpf_load_word && MaskV == 0xFFFFFFFF)))
 545       return;
 546
 547     LLVM_DEBUG(dbgs() << "Remove the redundant AND operation in: ";
 548                Node->dump(); dbgs() << '\n');
 549
 550     I--;
 551     CurDAG->ReplaceAllUsesWith(SDValue(Node, 0), BaseV);
 552     I++;
 553     CurDAG->DeleteNode(Node);
 554
 555     return;
 556   }
 557
 558   // Multiple basic blocks case.
 559   if (BaseV.getOpcode() != ISD::CopyFromReg)
 560     return;
 561
 562   unsigned match_load_op = 0;
 563   switch (MaskN->getZExtValue()) {
 564   default:
 565     return;
 566   case 0xFFFFFFFF:
 567     match_load_op = BPF::LDW;
 568     break;
 569   case 0xFFFF:
 570     match_load_op = BPF::LDH;
 571     break;
 572   case 0xFF:
 573     match_load_op = BPF::LDB;
 574     break;
 575   }
 576
 577   const RegisterSDNode *RegN =
 578       dyn_cast<RegisterSDNode>(BaseV.getNode()->getOperand(1));
 579   if (!RegN || !TargetRegisterInfo::isVirtualRegister(RegN->getReg()))
 580     return;
 581   unsigned AndOpReg = RegN->getReg();
 582   LLVM_DEBUG(dbgs() << "Examine " << printReg(AndOpReg) << '\n');
 583
 584   // Examine the PHI insns in the MachineBasicBlock to found out the
 585   // definitions of this virtual register. At this stage (DAG2DAG
 586   // transformation), only PHI machine insns are available in the machine basic
 587   // block.
 588   MachineBasicBlock *MBB = FuncInfo->MBB;
 589   MachineInstr *MII = nullptr;
 590   for (auto &MI : *MBB) {
 591     for (unsigned i = 0; i < MI.getNumOperands(); ++i) {
 592       const MachineOperand &MOP = MI.getOperand(i);
 593       if (!MOP.isReg() || !MOP.isDef())
 594         continue;
 595       unsigned Reg = MOP.getReg();
 596       if (TargetRegisterInfo::isVirtualRegister(Reg) && Reg == AndOpReg) {
 597         MII = &MI;
 598         break;
 599       }
 600     }
 601   }
 602
 603   if (MII == nullptr) {
 604     // No phi definition in this block.
 605     if (!checkLoadDef(AndOpReg, match_load_op))
 606       return;
 607   } else {
 608     // The PHI node looks like:
 609     //   %2 = PHI %0, <%bb.1>, %1, <%bb.3>
 610     // Trace each incoming definition, e.g., (%0, %bb.1) and (%1, %bb.3)
 611     // The AND operation can be removed if both %0 in %bb.1 and %1 in
 612     // %bb.3 are defined with a load matching the MaskN.
 613     LLVM_DEBUG(dbgs() << "Check PHI Insn: "; MII->dump(); dbgs() << '\n');
 614     unsigned PrevReg = -1;
 615     for (unsigned i = 0; i < MII->getNumOperands(); ++i) {
 616       const MachineOperand &MOP = MII->getOperand(i);
 617       if (MOP.isReg()) {
 618         if (MOP.isDef())
 619           continue;
 620         PrevReg = MOP.getReg();
 621         if (!TargetRegisterInfo::isVirtualRegister(PrevReg))
 622           return;
 623         if (!checkLoadDef(PrevReg, match_load_op))
 624           return;
 625       }
 626     }
 627   }
 628
 629   LLVM_DEBUG(dbgs() << "Remove the redundant AND operation in: "; Node->dump();
 630              dbgs() << '\n');
 631
 632   I--;
 633   CurDAG->ReplaceAllUsesWith(SDValue(Node, 0), BaseV);
 634   I++;
 635   CurDAG->DeleteNode(Node);
 636 }
 637
 638 bool BPFDAGToDAGISel::checkLoadDef(unsigned DefReg, unsigned match_load_op) {
 639   auto it = load_to_vreg_.find(DefReg);
 640   if (it == load_to_vreg_.end())
 641     return false; // The definition of register is not exported yet.
 642
 643   return it->second == match_load_op;
 644 }
 645
 646 FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) {
 647   return new BPFDAGToDAGISel(TM);
 648 }