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 } 650