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 public:
  43   explicit BPFDAGToDAGISel(BPFTargetMachine &TM) : SelectionDAGISel(TM) {
  44     curr_func_ = nullptr;
  45   }
  46
  47   StringRef getPassName() const override {
  48     return "BPF DAG->DAG Pattern Instruction Selection";
  49   }
  50
  51   void PreprocessISelDAG() override;
  52
  53   bool SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintCode,
  54                                     std::vector<SDValue> &OutOps) override;
  55
  56
  57 private:
  58 // Include the pieces autogenerated from the target description.
  59 #include "BPFGenDAGISel.inc"
  60
  61   void Select(SDNode *N) override;
  62
  63   // Complex Pattern for address selection.
  64   bool SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset);
  65   bool SelectFIAddr(SDValue Addr, SDValue &Base, SDValue &Offset);
  66
  67   // Node preprocessing cases
  68   void PreprocessLoad(SDNode *Node, SelectionDAG::allnodes_iterator I);
  69   void PreprocessCopyToReg(SDNode *Node);
  70   void PreprocessTrunc(SDNode *Node, SelectionDAG::allnodes_iterator I);
  71
  72   // Find constants from a constant structure
  73   typedef std::vector<unsigned char> val_vec_type;
  74   bool fillGenericConstant(const DataLayout &DL, const Constant *CV,
  75                            val_vec_type &Vals, uint64_t Offset);
  76   bool fillConstantDataArray(const DataLayout &DL, const ConstantDataArray *CDA,
  77                              val_vec_type &Vals, int Offset);
  78   bool fillConstantArray(const DataLayout &DL, const ConstantArray *CA,
  79                          val_vec_type &Vals, int Offset);
  80   bool fillConstantStruct(const DataLayout &DL, const ConstantStruct *CS,
  81                           val_vec_type &Vals, int Offset);
  82   bool getConstantFieldValue(const GlobalAddressSDNode *Node, uint64_t Offset,
  83                              uint64_t Size, unsigned char *ByteSeq);
  84   bool checkLoadDef(unsigned DefReg, unsigned match_load_op);
  85
  86   // Mapping from ConstantStruct global value to corresponding byte-list values
  87   std::map<const void *, val_vec_type> cs_vals_;
  88   // Mapping from vreg to load memory opcode
  89   std::map<unsigned, unsigned> load_to_vreg_;
  90   // Current function
  91   const Function *curr_func_;
  92 };
  93 } // namespace
  94
  95 // ComplexPattern used on BPF Load/Store instructions
  96 bool BPFDAGToDAGISel::SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset) {
  97   // if Address is FI, get the TargetFrameIndex.
  98   SDLoc DL(Addr);
  99   if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
 100     Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
 101     Offset = CurDAG->getTargetConstant(0, DL, MVT::i64);
 102     return true;
 103   }
 104
 105   if (Addr.getOpcode() == ISD::TargetExternalSymbol ||
 106       Addr.getOpcode() == ISD::TargetGlobalAddress)
 107     return false;
 108
 109   // Addresses of the form Addr+const or Addr|const
 110   if (CurDAG->isBaseWithConstantOffset(Addr)) {
 111     ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1));
 112     if (isInt<16>(CN->getSExtValue())) {
 113
 114       // If the first operand is a FI, get the TargetFI Node
 115       if (FrameIndexSDNode *FIN =
 116               dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))
 117         Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
 118       else
 119         Base = Addr.getOperand(0);
 120
 121       Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);
 122       return true;
 123     }
 124   }
 125
 126   Base = Addr;
 127   Offset = CurDAG->getTargetConstant(0, DL, MVT::i64);
 128   return true;
 129 }
 130
 131 // ComplexPattern used on BPF FI instruction
 132 bool BPFDAGToDAGISel::SelectFIAddr(SDValue Addr, SDValue &Base,
 133                                    SDValue &Offset) {
 134   SDLoc DL(Addr);
 135
 136   if (!CurDAG->isBaseWithConstantOffset(Addr))
 137     return false;
 138
 139   // Addresses of the form Addr+const or Addr|const
 140   ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1));
 141   if (isInt<16>(CN->getSExtValue())) {
 142
 143     // If the first operand is a FI, get the TargetFI Node
 144     if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))
 145       Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
 146     else
 147       return false;
 148
 149     Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);
 150     return true;
 151   }
 152
 153   return false;
 154 }
 155
 156 bool BPFDAGToDAGISel::SelectInlineAsmMemoryOperand(
 157     const SDValue &Op, unsigned ConstraintCode, std::vector<SDValue> &OutOps) {
 158   SDValue Op0, Op1;
 159   switch (ConstraintCode) {
 160   default:
 161     return true;
 162   case InlineAsm::Constraint_m: // memory
 163     if (!SelectAddr(Op, Op0, Op1))
 164       return true;
 165     break;
 166   }
 167
 168   SDLoc DL(Op);
 169   SDValue AluOp = CurDAG->getTargetConstant(ISD::ADD, DL, MVT::i32);;
 170   OutOps.push_back(Op0);
 171   OutOps.push_back(Op1);
 172   OutOps.push_back(AluOp);
 173   return false;
 174 }
 175
 176 void BPFDAGToDAGISel::Select(SDNode *Node) {
 177   unsigned Opcode = Node->getOpcode();
 178
 179   // Dump information about the Node being selected
 180   DEBUG(dbgs() << "Selecting: "; Node->dump(CurDAG); dbgs() << '\n');
 181
 182   // If we have a custom node, we already have selected!
 183   if (Node->isMachineOpcode()) {
 184     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     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     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   DEBUG(dbgs() << "Replacing load of size " << size << " with constant " << val
 305                << '\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 cases:
 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   //  . reg truncating is often the result of 8/16/32bit->64bit or
 327   //    8/16bit->32bit conversion. If the reg value is loaded with
 328   //    masked byte width, the AND operation can be removed since
 329   //    BPF LOAD already has zero extension.
 330   //
 331   //    This also solved a correctness issue.
 332   //    In BPF socket-related program, e.g., __sk_buff->{data, data_end}
 333   //    are 32-bit registers, but later on, kernel verifier will rewrite
 334   //    it with 64-bit value. Therefore, truncating the value after the
 335   //    load will result in incorrect code.
 336
 337   // clear the load_to_vreg_ map so that we have a clean start
 338   // for this function.
 339   if (!curr_func_) {
 340     curr_func_ = FuncInfo->Fn;
 341   } else if (curr_func_ != FuncInfo->Fn) {
 342     load_to_vreg_.clear();
 343     curr_func_ = FuncInfo->Fn;
 344   }
 345
 346   for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
 347                                        E = CurDAG->allnodes_end();
 348        I != E;) {
 349     SDNode *Node = &*I++;
 350     unsigned Opcode = Node->getOpcode();
 351     if (Opcode == ISD::LOAD)
 352       PreprocessLoad(Node, I);
 353     else if (Opcode == ISD::CopyToReg)
 354       PreprocessCopyToReg(Node);
 355     else if (Opcode == ISD::AND)
 356       PreprocessTrunc(Node, I);
 357   }
 358 }
 359
 360 bool BPFDAGToDAGISel::getConstantFieldValue(const GlobalAddressSDNode *Node,
 361                                             uint64_t Offset, uint64_t Size,
 362                                             unsigned char *ByteSeq) {
 363   const GlobalVariable *V = dyn_cast<GlobalVariable>(Node->getGlobal());
 364
 365   if (!V || !V->hasInitializer())
 366     return false;
 367
 368   const Constant *Init = V->getInitializer();
 369   const DataLayout &DL = CurDAG->getDataLayout();
 370   val_vec_type TmpVal;
 371
 372   auto it = cs_vals_.find(static_cast<const void *>(Init));
 373   if (it != cs_vals_.end()) {
 374     TmpVal = it->second;
 375   } else {
 376     uint64_t total_size = 0;
 377     if (const ConstantStruct *CS = dyn_cast<ConstantStruct>(Init))
 378       total_size =
 379           DL.getStructLayout(cast<StructType>(CS->getType()))->getSizeInBytes();
 380     else if (const ConstantArray *CA = dyn_cast<ConstantArray>(Init))
 381       total_size = DL.getTypeAllocSize(CA->getType()->getElementType()) *
 382                    CA->getNumOperands();
 383     else
 384       return false;
 385
 386     val_vec_type Vals(total_size, 0);
 387     if (fillGenericConstant(DL, Init, Vals, 0) == false)
 388       return false;
 389     cs_vals_[static_cast<const void *>(Init)] = Vals;
 390     TmpVal = std::move(Vals);
 391   }
 392
 393   // test whether host endianness matches target
 394   union {
 395     uint8_t c[2];
 396     uint16_t s;
 397   } test_buf;
 398   uint16_t test_val = 0x2345;
 399   if (DL.isLittleEndian())
 400     support::endian::write16le(test_buf.c, test_val);
 401   else
 402     support::endian::write16be(test_buf.c, test_val);
 403
 404   bool endian_match = test_buf.s == test_val;
 405   for (uint64_t i = Offset, j = 0; i < Offset + Size; i++, j++)
 406     ByteSeq[j] = endian_match ? TmpVal[i] : TmpVal[Offset + Size - 1 - j];
 407
 408   return true;
 409 }
 410
 411 bool BPFDAGToDAGISel::fillGenericConstant(const DataLayout &DL,
 412                                           const Constant *CV,
 413                                           val_vec_type &Vals, uint64_t Offset) {
 414   uint64_t Size = DL.getTypeAllocSize(CV->getType());
 415
 416   if (isa<ConstantAggregateZero>(CV) || isa<UndefValue>(CV))
 417     return true; // already done
 418
 419   if (const ConstantInt *CI = dyn_cast<ConstantInt>(CV)) {
 420     uint64_t val = CI->getZExtValue();
 421     DEBUG(dbgs() << "Byte array at offset " << Offset << " with value " << val
 422                  << '\n');
 423
 424     if (Size > 8 || (Size & (Size - 1)))
 425       return false;
 426
 427     // Store based on target endian
 428     for (uint64_t i = 0; i < Size; ++i) {
 429       Vals[Offset + i] = DL.isLittleEndian()
 430                              ? ((val >> (i * 8)) & 0xFF)
 431                              : ((val >> ((Size - i - 1) * 8)) & 0xFF);
 432     }
 433     return true;
 434   }
 435
 436   if (const ConstantDataArray *CDA = dyn_cast<ConstantDataArray>(CV))
 437     return fillConstantDataArray(DL, CDA, Vals, Offset);
 438
 439   if (const ConstantArray *CA = dyn_cast<ConstantArray>(CV))
 440     return fillConstantArray(DL, CA, Vals, Offset);
 441
 442   if (const ConstantStruct *CVS = dyn_cast<ConstantStruct>(CV))
 443     return fillConstantStruct(DL, CVS, Vals, Offset);
 444
 445   return false;
 446 }
 447
 448 bool BPFDAGToDAGISel::fillConstantDataArray(const DataLayout &DL,
 449                                             const ConstantDataArray *CDA,
 450                                             val_vec_type &Vals, int Offset) {
 451   for (unsigned i = 0, e = CDA->getNumElements(); i != e; ++i) {
 452     if (fillGenericConstant(DL, CDA->getElementAsConstant(i), Vals, Offset) ==
 453         false)
 454       return false;
 455     Offset += DL.getTypeAllocSize(CDA->getElementAsConstant(i)->getType());
 456   }
 457
 458   return true;
 459 }
 460
 461 bool BPFDAGToDAGISel::fillConstantArray(const DataLayout &DL,
 462                                         const ConstantArray *CA,
 463                                         val_vec_type &Vals, int Offset) {
 464   for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) {
 465     if (fillGenericConstant(DL, CA->getOperand(i), Vals, Offset) == false)
 466       return false;
 467     Offset += DL.getTypeAllocSize(CA->getOperand(i)->getType());
 468   }
 469
 470   return true;
 471 }
 472
 473 bool BPFDAGToDAGISel::fillConstantStruct(const DataLayout &DL,
 474                                          const ConstantStruct *CS,
 475                                          val_vec_type &Vals, int Offset) {
 476   const StructLayout *Layout = DL.getStructLayout(CS->getType());
 477   for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) {
 478     const Constant *Field = CS->getOperand(i);
 479     uint64_t SizeSoFar = Layout->getElementOffset(i);
 480     if (fillGenericConstant(DL, Field, Vals, Offset + SizeSoFar) == false)
 481       return false;
 482   }
 483   return true;
 484 }
 485
 486 void BPFDAGToDAGISel::PreprocessCopyToReg(SDNode *Node) {
 487   const RegisterSDNode *RegN = dyn_cast<RegisterSDNode>(Node->getOperand(1));
 488   if (!RegN || !TargetRegisterInfo::isVirtualRegister(RegN->getReg()))
 489     return;
 490
 491   const LoadSDNode *LD = dyn_cast<LoadSDNode>(Node->getOperand(2));
 492   if (!LD)
 493     return;
 494
 495   // Assign a load value to a virtual register. record its load width
 496   unsigned mem_load_op = 0;
 497   switch (LD->getMemOperand()->getSize()) {
 498   default:
 499     return;
 500   case 4:
 501     mem_load_op = BPF::LDW;
 502     break;
 503   case 2:
 504     mem_load_op = BPF::LDH;
 505     break;
 506   case 1:
 507     mem_load_op = BPF::LDB;
 508     break;
 509   }
 510
 511   DEBUG(dbgs() << "Find Load Value to VReg "
 512                << TargetRegisterInfo::virtReg2Index(RegN->getReg()) << '\n');
 513   load_to_vreg_[RegN->getReg()] = mem_load_op;
 514 }
 515
 516 void BPFDAGToDAGISel::PreprocessTrunc(SDNode *Node,
 517                                       SelectionDAG::allnodes_iterator I) {
 518   ConstantSDNode *MaskN = dyn_cast<ConstantSDNode>(Node->getOperand(1));
 519   if (!MaskN)
 520     return;
 521
 522   unsigned match_load_op = 0;
 523   switch (MaskN->getZExtValue()) {
 524   default:
 525     return;
 526   case 0xFFFFFFFF:
 527     match_load_op = BPF::LDW;
 528     break;
 529   case 0xFFFF:
 530     match_load_op = BPF::LDH;
 531     break;
 532   case 0xFF:
 533     match_load_op = BPF::LDB;
 534     break;
 535   }
 536
 537   // The Reg operand should be a virtual register, which is defined
 538   // outside the current basic block. DAG combiner has done a pretty
 539   // good job in removing truncating inside a single basic block.
 540   SDValue BaseV = Node->getOperand(0);
 541   if (BaseV.getOpcode() != ISD::CopyFromReg)
 542     return;
 543
 544   const RegisterSDNode *RegN =
 545       dyn_cast<RegisterSDNode>(BaseV.getNode()->getOperand(1));
 546   if (!RegN || !TargetRegisterInfo::isVirtualRegister(RegN->getReg()))
 547     return;
 548   unsigned AndOpReg = RegN->getReg();
 549   DEBUG(dbgs() << "Examine " << printReg(AndOpReg) << '\n');
 550
 551   // Examine the PHI insns in the MachineBasicBlock to found out the
 552   // definitions of this virtual register. At this stage (DAG2DAG
 553   // transformation), only PHI machine insns are available in the machine basic
 554   // block.
 555   MachineBasicBlock *MBB = FuncInfo->MBB;
 556   MachineInstr *MII = nullptr;
 557   for (auto &MI : *MBB) {
 558     for (unsigned i = 0; i < MI.getNumOperands(); ++i) {
 559       const MachineOperand &MOP = MI.getOperand(i);
 560       if (!MOP.isReg() || !MOP.isDef())
 561         continue;
 562       unsigned Reg = MOP.getReg();
 563       if (TargetRegisterInfo::isVirtualRegister(Reg) && Reg == AndOpReg) {
 564         MII = &MI;
 565         break;
 566       }
 567     }
 568   }
 569
 570   if (MII == nullptr) {
 571     // No phi definition in this block.
 572     if (!checkLoadDef(AndOpReg, match_load_op))
 573       return;
 574   } else {
 575     // The PHI node looks like:
 576     //   %2 = PHI %0, <%bb.1>, %1, <%bb.3>
 577     // Trace each incoming definition, e.g., (%0, %bb.1) and (%1, %bb.3)
 578     // The AND operation can be removed if both %0 in %bb.1 and %1 in
 579     // %bb.3 are defined with with a load matching the MaskN.
 580     DEBUG(dbgs() << "Check PHI Insn: "; MII->dump(); dbgs() << '\n');
 581     unsigned PrevReg = -1;
 582     for (unsigned i = 0; i < MII->getNumOperands(); ++i) {
 583       const MachineOperand &MOP = MII->getOperand(i);
 584       if (MOP.isReg()) {
 585         if (MOP.isDef())
 586           continue;
 587         PrevReg = MOP.getReg();
 588         if (!TargetRegisterInfo::isVirtualRegister(PrevReg))
 589           return;
 590         if (!checkLoadDef(PrevReg, match_load_op))
 591           return;
 592       }
 593     }
 594   }
 595
 596   DEBUG(dbgs() << "Remove the redundant AND operation in: "; Node->dump();
 597         dbgs() << '\n');
 598
 599   I--;
 600   CurDAG->ReplaceAllUsesWith(SDValue(Node, 0), BaseV);
 601   I++;
 602   CurDAG->DeleteNode(Node);
 603 }
 604
 605 bool BPFDAGToDAGISel::checkLoadDef(unsigned DefReg, unsigned match_load_op) {
 606   auto it = load_to_vreg_.find(DefReg);
 607   if (it == load_to_vreg_.end())
 608     return false; // The definition of register is not exported yet.
 609
 610   return it->second == match_load_op;
 611 }
 612
 613 FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) {
 614   return new BPFDAGToDAGISel(TM);
 615 }