BPFISelDAGToDAG.cpp revision 353358
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 33using namespace llvm; 34 35#define DEBUG_TYPE "bpf-isel" 36 37// Instruction Selector Implementation 38namespace { 39 40class 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 46public: 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 68private: 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 107bool 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 143bool 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 167bool 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 187void 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 251void 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 327void 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 368bool 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 419bool 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 456bool 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 469bool 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 481bool 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 494void 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 525void 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 638bool 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 646FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) { 647 return new BPFDAGToDAGISel(TM); 648} 649