BPFISelDAGToDAG.cpp revision 327952
1218885Sdim//===-- BPFISelDAGToDAG.cpp - A dag to dag inst selector for BPF ----------===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// This file defines a DAG pattern matching instruction selector for BPF, 11218885Sdim// converting from a legalized dag to a BPF dag. 12218885Sdim// 13218885Sdim//===----------------------------------------------------------------------===// 14218885Sdim 15218885Sdim#include "BPF.h" 16218885Sdim#include "BPFRegisterInfo.h" 17218885Sdim#include "BPFSubtarget.h" 18218885Sdim#include "BPFTargetMachine.h" 19218885Sdim#include "llvm/CodeGen/FunctionLoweringInfo.h" 20218885Sdim#include "llvm/CodeGen/MachineConstantPool.h" 21218885Sdim#include "llvm/CodeGen/MachineFrameInfo.h" 22226633Sdim#include "llvm/CodeGen/MachineFunction.h" 23226633Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 24226633Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 25218885Sdim#include "llvm/CodeGen/SelectionDAGISel.h" 26218885Sdim#include "llvm/IR/Constants.h" 27263508Sdim#include "llvm/IR/IntrinsicInst.h" 28263508Sdim#include "llvm/Support/Debug.h" 29218885Sdim#include "llvm/Support/Endian.h" 30263508Sdim#include "llvm/Support/ErrorHandling.h" 31263508Sdim#include "llvm/Support/raw_ostream.h" 32218885Sdim#include "llvm/Target/TargetMachine.h" 33234353Sdim 34218885Sdimusing namespace llvm; 35218885Sdim 36263508Sdim#define DEBUG_TYPE "bpf-isel" 37218885Sdim 38218885Sdim// Instruction Selector Implementation 39218885Sdimnamespace { 40218885Sdim 41218885Sdimclass BPFDAGToDAGISel : public SelectionDAGISel { 42263508Sdimpublic: 43263508Sdim explicit BPFDAGToDAGISel(BPFTargetMachine &TM) : SelectionDAGISel(TM) { 44263508Sdim curr_func_ = nullptr; 45263508Sdim } 46263508Sdim 47263508Sdim StringRef getPassName() const override { 48263508Sdim return "BPF DAG->DAG Pattern Instruction Selection"; 49263508Sdim } 50218885Sdim 51263508Sdim void PreprocessISelDAG() override; 52218885Sdim 53218885Sdim bool SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintCode, 54234353Sdim std::vector<SDValue> &OutOps) override; 55234353Sdim 56234353Sdim 57234353Sdimprivate: 58218885Sdim// Include the pieces autogenerated from the target description. 59234353Sdim#include "BPFGenDAGISel.inc" 60234353Sdim 61218885Sdim void Select(SDNode *N) override; 62234353Sdim 63234353Sdim // Complex Pattern for address selection. 64218885Sdim bool SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset); 65234353Sdim bool SelectFIAddr(SDValue Addr, SDValue &Base, SDValue &Offset); 66234353Sdim 67234353Sdim // Node preprocessing cases 68234353Sdim void PreprocessLoad(SDNode *Node, SelectionDAG::allnodes_iterator I); 69234353Sdim void PreprocessCopyToReg(SDNode *Node); 70234353Sdim void PreprocessTrunc(SDNode *Node, SelectionDAG::allnodes_iterator I); 71218885Sdim 72218885Sdim // Find constants from a constant structure 73234353Sdim typedef std::vector<unsigned char> val_vec_type; 74234353Sdim bool fillGenericConstant(const DataLayout &DL, const Constant *CV, 75234353Sdim val_vec_type &Vals, uint64_t Offset); 76234353Sdim bool fillConstantDataArray(const DataLayout &DL, const ConstantDataArray *CDA, 77218885Sdim val_vec_type &Vals, int Offset); 78218885Sdim bool fillConstantArray(const DataLayout &DL, const ConstantArray *CA, 79234353Sdim val_vec_type &Vals, int Offset); 80234353Sdim bool fillConstantStruct(const DataLayout &DL, const ConstantStruct *CS, 81234353Sdim val_vec_type &Vals, int Offset); 82234353Sdim bool getConstantFieldValue(const GlobalAddressSDNode *Node, uint64_t Offset, 83218885Sdim uint64_t Size, unsigned char *ByteSeq); 84218885Sdim bool checkLoadDef(unsigned DefReg, unsigned match_load_op); 85234353Sdim 86234353Sdim // Mapping from ConstantStruct global value to corresponding byte-list values 87263508Sdim std::map<const void *, val_vec_type> cs_vals_; 88234353Sdim // Mapping from vreg to load memory opcode 89234353Sdim std::map<unsigned, unsigned> load_to_vreg_; 90234353Sdim // Current function 91234353Sdim const Function *curr_func_; 92234353Sdim}; 93234353Sdim} // namespace 94218885Sdim 95218885Sdim// ComplexPattern used on BPF Load/Store instructions 96234353Sdimbool BPFDAGToDAGISel::SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset) { 97234353Sdim // if Address is FI, get the TargetFrameIndex. 98218885Sdim SDLoc DL(Addr); 99234353Sdim if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr)) { 100234353Sdim Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64); 101234353Sdim Offset = CurDAG->getTargetConstant(0, DL, MVT::i64); 102218885Sdim return true; 103234353Sdim } 104234353Sdim 105218885Sdim if (Addr.getOpcode() == ISD::TargetExternalSymbol || 106218885Sdim Addr.getOpcode() == ISD::TargetGlobalAddress) 107234353Sdim return false; 108234353Sdim 109218885Sdim // Addresses of the form Addr+const or Addr|const 110234353Sdim if (CurDAG->isBaseWithConstantOffset(Addr)) { 111218885Sdim ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1)); 112234353Sdim if (isInt<16>(CN->getSExtValue())) { 113234353Sdim 114234353Sdim // If the first operand is a FI, get the TargetFI Node 115234353Sdim if (FrameIndexSDNode *FIN = 116234353Sdim dyn_cast<FrameIndexSDNode>(Addr.getOperand(0))) 117218885Sdim Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64); 118234353Sdim else 119234353Sdim Base = Addr.getOperand(0); 120234353Sdim 121234353Sdim Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64); 122234353Sdim return true; 123218885Sdim } 124218885Sdim } 125234353Sdim 126234353Sdim Base = Addr; 127234353Sdim Offset = CurDAG->getTargetConstant(0, DL, MVT::i64); 128218885Sdim return true; 129234353Sdim} 130234353Sdim 131218885Sdim// ComplexPattern used on BPF FI instruction 132234353Sdimbool BPFDAGToDAGISel::SelectFIAddr(SDValue Addr, SDValue &Base, 133218885Sdim SDValue &Offset) { 134234353Sdim SDLoc DL(Addr); 135234353Sdim 136234353Sdim if (!CurDAG->isBaseWithConstantOffset(Addr)) 137218885Sdim return false; 138218885Sdim 139218885Sdim // Addresses of the form Addr+const or Addr|const 140234353Sdim ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1)); 141218885Sdim if (isInt<16>(CN->getSExtValue())) { 142234353Sdim 143234353Sdim // If the first operand is a FI, get the TargetFI Node 144234353Sdim if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0))) 145234353Sdim Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64); 146234353Sdim else 147234353Sdim return false; 148218885Sdim 149218885Sdim Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64); 150218885Sdim return true; 151218885Sdim } 152218885Sdim 153218885Sdim return false; 154218885Sdim} 155218885Sdim 156218885Sdimbool BPFDAGToDAGISel::SelectInlineAsmMemoryOperand( 157218885Sdim const SDValue &Op, unsigned ConstraintCode, std::vector<SDValue> &OutOps) { 158218885Sdim SDValue Op0, Op1; 159263508Sdim switch (ConstraintCode) { 160263508Sdim default: 161263508Sdim return true; 162263508Sdim case InlineAsm::Constraint_m: // memory 163263508Sdim if (!SelectAddr(Op, Op0, Op1)) 164263508Sdim return true; 165263508Sdim break; 166263508Sdim } 167263508Sdim 168218885Sdim 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 176void 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 243void 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 319void 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 360bool 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 411bool 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 448bool 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 461bool 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 473bool 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 486void 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 516void 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 605bool 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 613FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) { 614 return new BPFDAGToDAGISel(TM); 615} 616