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/IR/IntrinsicsBPF.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 51 StringRef getPassName() const override { 52 return "BPF DAG->DAG Pattern Instruction Selection"; 53 } 54 55 bool runOnMachineFunction(MachineFunction &MF) override { 56 // Reset the subtarget each time through. 57 Subtarget = &MF.getSubtarget<BPFSubtarget>(); 58 return SelectionDAGISel::runOnMachineFunction(MF); 59 } 60 61 void PreprocessISelDAG() override; 62 63 bool SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintCode, 64 std::vector<SDValue> &OutOps) override; 65 66 67 private: 68 // Include the pieces autogenerated from the target description. 69 #include "BPFGenDAGISel.inc" 70 71 void Select(SDNode *N) override; 72 73 // Complex Pattern for address selection. 74 bool SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset); 75 bool SelectFIAddr(SDValue Addr, SDValue &Base, SDValue &Offset); 76 77 // Node preprocessing cases 78 void PreprocessLoad(SDNode *Node, SelectionDAG::allnodes_iterator &I); 79 void PreprocessCopyToReg(SDNode *Node); 80 void PreprocessTrunc(SDNode *Node, SelectionDAG::allnodes_iterator &I); 81 82 // Find constants from a constant structure 83 typedef std::vector<unsigned char> val_vec_type; 84 bool fillGenericConstant(const DataLayout &DL, const Constant *CV, 85 val_vec_type &Vals, uint64_t Offset); 86 bool fillConstantDataArray(const DataLayout &DL, const ConstantDataArray *CDA, 87 val_vec_type &Vals, int Offset); 88 bool fillConstantArray(const DataLayout &DL, const ConstantArray *CA, 89 val_vec_type &Vals, int Offset); 90 bool fillConstantStruct(const DataLayout &DL, const ConstantStruct *CS, 91 val_vec_type &Vals, int Offset); 92 bool getConstantFieldValue(const GlobalAddressSDNode *Node, uint64_t Offset, 93 uint64_t Size, unsigned char *ByteSeq); 94 // Mapping from ConstantStruct global value to corresponding byte-list values 95 std::map<const void *, val_vec_type> cs_vals_; 96 }; 97 } // namespace 98 99 // ComplexPattern used on BPF Load/Store instructions 100 bool BPFDAGToDAGISel::SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset) { 101 // if Address is FI, get the TargetFrameIndex. 102 SDLoc DL(Addr); 103 if (auto *FIN = dyn_cast<FrameIndexSDNode>(Addr)) { 104 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64); 105 Offset = CurDAG->getTargetConstant(0, DL, MVT::i64); 106 return true; 107 } 108 109 if (Addr.getOpcode() == ISD::TargetExternalSymbol || 110 Addr.getOpcode() == ISD::TargetGlobalAddress) 111 return false; 112 113 // Addresses of the form Addr+const or Addr|const 114 if (CurDAG->isBaseWithConstantOffset(Addr)) { 115 auto *CN = cast<ConstantSDNode>(Addr.getOperand(1)); 116 if (isInt<16>(CN->getSExtValue())) { 117 // If the first operand is a FI, get the TargetFI Node 118 if (auto *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0))) 119 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64); 120 else 121 Base = Addr.getOperand(0); 122 123 Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64); 124 return true; 125 } 126 } 127 128 Base = Addr; 129 Offset = CurDAG->getTargetConstant(0, DL, MVT::i64); 130 return true; 131 } 132 133 // ComplexPattern used on BPF FI instruction 134 bool BPFDAGToDAGISel::SelectFIAddr(SDValue Addr, SDValue &Base, 135 SDValue &Offset) { 136 SDLoc DL(Addr); 137 138 if (!CurDAG->isBaseWithConstantOffset(Addr)) 139 return false; 140 141 // Addresses of the form Addr+const or Addr|const 142 auto *CN = cast<ConstantSDNode>(Addr.getOperand(1)); 143 if (isInt<16>(CN->getSExtValue())) { 144 // If the first operand is a FI, get the TargetFI Node 145 if (auto *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0))) 146 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64); 147 else 148 return false; 149 150 Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64); 151 return true; 152 } 153 154 return false; 155 } 156 157 bool BPFDAGToDAGISel::SelectInlineAsmMemoryOperand( 158 const SDValue &Op, unsigned ConstraintCode, std::vector<SDValue> &OutOps) { 159 SDValue Op0, Op1; 160 switch (ConstraintCode) { 161 default: 162 return true; 163 case InlineAsm::Constraint_m: // memory 164 if (!SelectAddr(Op, Op0, Op1)) 165 return true; 166 break; 167 } 168 169 SDLoc DL(Op); 170 SDValue AluOp = CurDAG->getTargetConstant(ISD::ADD, DL, MVT::i32);; 171 OutOps.push_back(Op0); 172 OutOps.push_back(Op1); 173 OutOps.push_back(AluOp); 174 return false; 175 } 176 177 void BPFDAGToDAGISel::Select(SDNode *Node) { 178 unsigned Opcode = Node->getOpcode(); 179 180 // If we have a custom node, we already have selected! 181 if (Node->isMachineOpcode()) { 182 LLVM_DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << '\n'); 183 return; 184 } 185 186 // tablegen selection should be handled here. 187 switch (Opcode) { 188 default: 189 break; 190 case ISD::SDIV: { 191 DebugLoc Empty; 192 const DebugLoc &DL = Node->getDebugLoc(); 193 if (DL != Empty) 194 errs() << "Error at line " << DL.getLine() << ": "; 195 else 196 errs() << "Error: "; 197 errs() << "Unsupport signed division for DAG: "; 198 Node->print(errs(), CurDAG); 199 errs() << "Please convert to unsigned div/mod.\n"; 200 break; 201 } 202 case ISD::INTRINSIC_W_CHAIN: { 203 unsigned IntNo = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue(); 204 switch (IntNo) { 205 case Intrinsic::bpf_load_byte: 206 case Intrinsic::bpf_load_half: 207 case Intrinsic::bpf_load_word: { 208 SDLoc DL(Node); 209 SDValue Chain = Node->getOperand(0); 210 SDValue N1 = Node->getOperand(1); 211 SDValue Skb = Node->getOperand(2); 212 SDValue N3 = Node->getOperand(3); 213 214 SDValue R6Reg = CurDAG->getRegister(BPF::R6, MVT::i64); 215 Chain = CurDAG->getCopyToReg(Chain, DL, R6Reg, Skb, SDValue()); 216 Node = CurDAG->UpdateNodeOperands(Node, Chain, N1, R6Reg, N3); 217 break; 218 } 219 } 220 break; 221 } 222 223 case ISD::FrameIndex: { 224 int FI = cast<FrameIndexSDNode>(Node)->getIndex(); 225 EVT VT = Node->getValueType(0); 226 SDValue TFI = CurDAG->getTargetFrameIndex(FI, VT); 227 unsigned Opc = BPF::MOV_rr; 228 if (Node->hasOneUse()) { 229 CurDAG->SelectNodeTo(Node, Opc, VT, TFI); 230 return; 231 } 232 ReplaceNode(Node, CurDAG->getMachineNode(Opc, SDLoc(Node), VT, TFI)); 233 return; 234 } 235 } 236 237 // Select the default instruction 238 SelectCode(Node); 239 } 240 241 void BPFDAGToDAGISel::PreprocessLoad(SDNode *Node, 242 SelectionDAG::allnodes_iterator &I) { 243 union { 244 uint8_t c[8]; 245 uint16_t s; 246 uint32_t i; 247 uint64_t d; 248 } new_val; // hold up the constant values replacing loads. 249 bool to_replace = false; 250 SDLoc DL(Node); 251 const LoadSDNode *LD = cast<LoadSDNode>(Node); 252 uint64_t size = LD->getMemOperand()->getSize(); 253 254 if (!size || size > 8 || (size & (size - 1)) || !LD->isSimple()) 255 return; 256 257 SDNode *LDAddrNode = LD->getOperand(1).getNode(); 258 // Match LDAddr against either global_addr or (global_addr + offset) 259 unsigned opcode = LDAddrNode->getOpcode(); 260 if (opcode == ISD::ADD) { 261 SDValue OP1 = LDAddrNode->getOperand(0); 262 SDValue OP2 = LDAddrNode->getOperand(1); 263 264 // We want to find the pattern global_addr + offset 265 SDNode *OP1N = OP1.getNode(); 266 if (OP1N->getOpcode() <= ISD::BUILTIN_OP_END || OP1N->getNumOperands() == 0) 267 return; 268 269 LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n'); 270 271 const GlobalAddressSDNode *GADN = 272 dyn_cast<GlobalAddressSDNode>(OP1N->getOperand(0).getNode()); 273 const ConstantSDNode *CDN = dyn_cast<ConstantSDNode>(OP2.getNode()); 274 if (GADN && CDN) 275 to_replace = 276 getConstantFieldValue(GADN, CDN->getZExtValue(), size, new_val.c); 277 } else if (LDAddrNode->getOpcode() > ISD::BUILTIN_OP_END && 278 LDAddrNode->getNumOperands() > 0) { 279 LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n'); 280 281 SDValue OP1 = LDAddrNode->getOperand(0); 282 if (const GlobalAddressSDNode *GADN = 283 dyn_cast<GlobalAddressSDNode>(OP1.getNode())) 284 to_replace = getConstantFieldValue(GADN, 0, size, new_val.c); 285 } 286 287 if (!to_replace) 288 return; 289 290 // replacing the old with a new value 291 uint64_t val; 292 if (size == 1) 293 val = new_val.c[0]; 294 else if (size == 2) 295 val = new_val.s; 296 else if (size == 4) 297 val = new_val.i; 298 else { 299 val = new_val.d; 300 } 301 302 LLVM_DEBUG(dbgs() << "Replacing load of size " << size << " with constant " 303 << val << '\n'); 304 SDValue NVal = CurDAG->getConstant(val, DL, LD->getValueType(0)); 305 306 // After replacement, the current node is dead, we need to 307 // go backward one step to make iterator still work 308 I--; 309 SDValue From[] = {SDValue(Node, 0), SDValue(Node, 1)}; 310 SDValue To[] = {NVal, NVal}; 311 CurDAG->ReplaceAllUsesOfValuesWith(From, To, 2); 312 I++; 313 // It is safe to delete node now 314 CurDAG->DeleteNode(Node); 315 } 316 317 void BPFDAGToDAGISel::PreprocessISelDAG() { 318 // Iterate through all nodes, interested in the following case: 319 // 320 // . loads from ConstantStruct or ConstantArray of constructs 321 // which can be turns into constant itself, with this we can 322 // avoid reading from read-only section at runtime. 323 // 324 // . Removing redundant AND for intrinsic narrow loads. 325 for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(), 326 E = CurDAG->allnodes_end(); 327 I != E;) { 328 SDNode *Node = &*I++; 329 unsigned Opcode = Node->getOpcode(); 330 if (Opcode == ISD::LOAD) 331 PreprocessLoad(Node, I); 332 else if (Opcode == ISD::AND) 333 PreprocessTrunc(Node, I); 334 } 335 } 336 337 bool BPFDAGToDAGISel::getConstantFieldValue(const GlobalAddressSDNode *Node, 338 uint64_t Offset, uint64_t Size, 339 unsigned char *ByteSeq) { 340 const GlobalVariable *V = dyn_cast<GlobalVariable>(Node->getGlobal()); 341 342 if (!V || !V->hasInitializer() || !V->isConstant()) 343 return false; 344 345 const Constant *Init = V->getInitializer(); 346 const DataLayout &DL = CurDAG->getDataLayout(); 347 val_vec_type TmpVal; 348 349 auto it = cs_vals_.find(static_cast<const void *>(Init)); 350 if (it != cs_vals_.end()) { 351 TmpVal = it->second; 352 } else { 353 uint64_t total_size = 0; 354 if (const ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) 355 total_size = 356 DL.getStructLayout(cast<StructType>(CS->getType()))->getSizeInBytes(); 357 else if (const ConstantArray *CA = dyn_cast<ConstantArray>(Init)) 358 total_size = DL.getTypeAllocSize(CA->getType()->getElementType()) * 359 CA->getNumOperands(); 360 else 361 return false; 362 363 val_vec_type Vals(total_size, 0); 364 if (fillGenericConstant(DL, Init, Vals, 0) == false) 365 return false; 366 cs_vals_[static_cast<const void *>(Init)] = Vals; 367 TmpVal = std::move(Vals); 368 } 369 370 // test whether host endianness matches target 371 union { 372 uint8_t c[2]; 373 uint16_t s; 374 } test_buf; 375 uint16_t test_val = 0x2345; 376 if (DL.isLittleEndian()) 377 support::endian::write16le(test_buf.c, test_val); 378 else 379 support::endian::write16be(test_buf.c, test_val); 380 381 bool endian_match = test_buf.s == test_val; 382 for (uint64_t i = Offset, j = 0; i < Offset + Size; i++, j++) 383 ByteSeq[j] = endian_match ? TmpVal[i] : TmpVal[Offset + Size - 1 - j]; 384 385 return true; 386 } 387 388 bool BPFDAGToDAGISel::fillGenericConstant(const DataLayout &DL, 389 const Constant *CV, 390 val_vec_type &Vals, uint64_t Offset) { 391 uint64_t Size = DL.getTypeAllocSize(CV->getType()); 392 393 if (isa<ConstantAggregateZero>(CV) || isa<UndefValue>(CV)) 394 return true; // already done 395 396 if (const ConstantInt *CI = dyn_cast<ConstantInt>(CV)) { 397 uint64_t val = CI->getZExtValue(); 398 LLVM_DEBUG(dbgs() << "Byte array at offset " << Offset << " with value " 399 << val << '\n'); 400 401 if (Size > 8 || (Size & (Size - 1))) 402 return false; 403 404 // Store based on target endian 405 for (uint64_t i = 0; i < Size; ++i) { 406 Vals[Offset + i] = DL.isLittleEndian() 407 ? ((val >> (i * 8)) & 0xFF) 408 : ((val >> ((Size - i - 1) * 8)) & 0xFF); 409 } 410 return true; 411 } 412 413 if (const ConstantDataArray *CDA = dyn_cast<ConstantDataArray>(CV)) 414 return fillConstantDataArray(DL, CDA, Vals, Offset); 415 416 if (const ConstantArray *CA = dyn_cast<ConstantArray>(CV)) 417 return fillConstantArray(DL, CA, Vals, Offset); 418 419 if (const ConstantStruct *CVS = dyn_cast<ConstantStruct>(CV)) 420 return fillConstantStruct(DL, CVS, Vals, Offset); 421 422 return false; 423 } 424 425 bool BPFDAGToDAGISel::fillConstantDataArray(const DataLayout &DL, 426 const ConstantDataArray *CDA, 427 val_vec_type &Vals, int Offset) { 428 for (unsigned i = 0, e = CDA->getNumElements(); i != e; ++i) { 429 if (fillGenericConstant(DL, CDA->getElementAsConstant(i), Vals, Offset) == 430 false) 431 return false; 432 Offset += DL.getTypeAllocSize(CDA->getElementAsConstant(i)->getType()); 433 } 434 435 return true; 436 } 437 438 bool BPFDAGToDAGISel::fillConstantArray(const DataLayout &DL, 439 const ConstantArray *CA, 440 val_vec_type &Vals, int Offset) { 441 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) { 442 if (fillGenericConstant(DL, CA->getOperand(i), Vals, Offset) == false) 443 return false; 444 Offset += DL.getTypeAllocSize(CA->getOperand(i)->getType()); 445 } 446 447 return true; 448 } 449 450 bool BPFDAGToDAGISel::fillConstantStruct(const DataLayout &DL, 451 const ConstantStruct *CS, 452 val_vec_type &Vals, int Offset) { 453 const StructLayout *Layout = DL.getStructLayout(CS->getType()); 454 for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) { 455 const Constant *Field = CS->getOperand(i); 456 uint64_t SizeSoFar = Layout->getElementOffset(i); 457 if (fillGenericConstant(DL, Field, Vals, Offset + SizeSoFar) == false) 458 return false; 459 } 460 return true; 461 } 462 463 void BPFDAGToDAGISel::PreprocessTrunc(SDNode *Node, 464 SelectionDAG::allnodes_iterator &I) { 465 ConstantSDNode *MaskN = dyn_cast<ConstantSDNode>(Node->getOperand(1)); 466 if (!MaskN) 467 return; 468 469 // The Reg operand should be a virtual register, which is defined 470 // outside the current basic block. DAG combiner has done a pretty 471 // good job in removing truncating inside a single basic block except 472 // when the Reg operand comes from bpf_load_[byte | half | word] for 473 // which the generic optimizer doesn't understand their results are 474 // zero extended. 475 SDValue BaseV = Node->getOperand(0); 476 if (BaseV.getOpcode() != ISD::INTRINSIC_W_CHAIN) 477 return; 478 479 unsigned IntNo = cast<ConstantSDNode>(BaseV->getOperand(1))->getZExtValue(); 480 uint64_t MaskV = MaskN->getZExtValue(); 481 482 if (!((IntNo == Intrinsic::bpf_load_byte && MaskV == 0xFF) || 483 (IntNo == Intrinsic::bpf_load_half && MaskV == 0xFFFF) || 484 (IntNo == Intrinsic::bpf_load_word && MaskV == 0xFFFFFFFF))) 485 return; 486 487 LLVM_DEBUG(dbgs() << "Remove the redundant AND operation in: "; 488 Node->dump(); dbgs() << '\n'); 489 490 I--; 491 CurDAG->ReplaceAllUsesWith(SDValue(Node, 0), BaseV); 492 I++; 493 CurDAG->DeleteNode(Node); 494 } 495 496 FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) { 497 return new BPFDAGToDAGISel(TM); 498 } 499