contrib/llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp

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