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 33 using namespace llvm; 34 35 #define DEBUG_TYPE "bpf-isel" 36 37 // Instruction Selector Implementation 38 namespace { 39 40 class 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 46 public: 47 explicit BPFDAGToDAGISel(BPFTargetMachine &TM) 48 : SelectionDAGISel(TM), Subtarget(nullptr) {} 49 50 StringRef getPassName() const override { 51 return "BPF DAG->DAG Pattern Instruction Selection"; 52 } 53 54 bool runOnMachineFunction(MachineFunction &MF) override { 55 // Reset the subtarget each time through. 56 Subtarget = &MF.getSubtarget<BPFSubtarget>(); 57 return SelectionDAGISel::runOnMachineFunction(MF); 58 } 59 60 void PreprocessISelDAG() override; 61 62 bool SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintCode, 63 std::vector<SDValue> &OutOps) override; 64 65 66 private: 67 // Include the pieces autogenerated from the target description. 68 #include "BPFGenDAGISel.inc" 69 70 void Select(SDNode *N) override; 71 72 // Complex Pattern for address selection. 73 bool SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset); 74 bool SelectFIAddr(SDValue Addr, SDValue &Base, SDValue &Offset); 75 76 // Node preprocessing cases 77 void PreprocessLoad(SDNode *Node, SelectionDAG::allnodes_iterator &I); 78 void PreprocessCopyToReg(SDNode *Node); 79 void PreprocessTrunc(SDNode *Node, SelectionDAG::allnodes_iterator &I); 80 81 // Find constants from a constant structure 82 typedef std::vector<unsigned char> val_vec_type; 83 bool fillGenericConstant(const DataLayout &DL, const Constant *CV, 84 val_vec_type &Vals, uint64_t Offset); 85 bool fillConstantDataArray(const DataLayout &DL, const ConstantDataArray *CDA, 86 val_vec_type &Vals, int Offset); 87 bool fillConstantArray(const DataLayout &DL, const ConstantArray *CA, 88 val_vec_type &Vals, int Offset); 89 bool fillConstantStruct(const DataLayout &DL, const ConstantStruct *CS, 90 val_vec_type &Vals, int Offset); 91 bool getConstantFieldValue(const GlobalAddressSDNode *Node, uint64_t Offset, 92 uint64_t Size, unsigned char *ByteSeq); 93 // Mapping from ConstantStruct global value to corresponding byte-list values 94 std::map<const void *, val_vec_type> cs_vals_; 95 }; 96 } // namespace 97 98 // ComplexPattern used on BPF Load/Store instructions 99 bool BPFDAGToDAGISel::SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset) { 100 // if Address is FI, get the TargetFrameIndex. 101 SDLoc DL(Addr); 102 if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr)) { 103 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64); 104 Offset = CurDAG->getTargetConstant(0, DL, MVT::i64); 105 return true; 106 } 107 108 if (Addr.getOpcode() == ISD::TargetExternalSymbol || 109 Addr.getOpcode() == ISD::TargetGlobalAddress) 110 return false; 111 112 // Addresses of the form Addr+const or Addr|const 113 if (CurDAG->isBaseWithConstantOffset(Addr)) { 114 ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1)); 115 if (isInt<16>(CN->getSExtValue())) { 116 117 // If the first operand is a FI, get the TargetFI Node 118 if (FrameIndexSDNode *FIN = 119 dyn_cast<FrameIndexSDNode>(Addr.getOperand(0))) 120 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64); 121 else 122 Base = Addr.getOperand(0); 123 124 Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64); 125 return true; 126 } 127 } 128 129 Base = Addr; 130 Offset = CurDAG->getTargetConstant(0, DL, MVT::i64); 131 return true; 132 } 133 134 // ComplexPattern used on BPF FI instruction 135 bool BPFDAGToDAGISel::SelectFIAddr(SDValue Addr, SDValue &Base, 136 SDValue &Offset) { 137 SDLoc DL(Addr); 138 139 if (!CurDAG->isBaseWithConstantOffset(Addr)) 140 return false; 141 142 // Addresses of the form Addr+const or Addr|const 143 ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1)); 144 if (isInt<16>(CN->getSExtValue())) { 145 146 // If the first operand is a FI, get the TargetFI Node 147 if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0))) 148 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64); 149 else 150 return false; 151 152 Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64); 153 return true; 154 } 155 156 return false; 157 } 158 159 bool BPFDAGToDAGISel::SelectInlineAsmMemoryOperand( 160 const SDValue &Op, unsigned ConstraintCode, std::vector<SDValue> &OutOps) { 161 SDValue Op0, Op1; 162 switch (ConstraintCode) { 163 default: 164 return true; 165 case InlineAsm::Constraint_m: // memory 166 if (!SelectAddr(Op, Op0, Op1)) 167 return true; 168 break; 169 } 170 171 SDLoc DL(Op); 172 SDValue AluOp = CurDAG->getTargetConstant(ISD::ADD, DL, MVT::i32);; 173 OutOps.push_back(Op0); 174 OutOps.push_back(Op1); 175 OutOps.push_back(AluOp); 176 return false; 177 } 178 179 void BPFDAGToDAGISel::Select(SDNode *Node) { 180 unsigned Opcode = Node->getOpcode(); 181 182 // If we have a custom node, we already have selected! 183 if (Node->isMachineOpcode()) { 184 LLVM_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 LLVM_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 LLVM_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 LLVM_DEBUG(dbgs() << "Replacing load of size " << size << " with constant " 305 << val << '\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 case: 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 // . Removing redundant AND for intrinsic narrow loads. 327 for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(), 328 E = CurDAG->allnodes_end(); 329 I != E;) { 330 SDNode *Node = &*I++; 331 unsigned Opcode = Node->getOpcode(); 332 if (Opcode == ISD::LOAD) 333 PreprocessLoad(Node, I); 334 else if (Opcode == ISD::AND) 335 PreprocessTrunc(Node, I); 336 } 337 } 338 339 bool BPFDAGToDAGISel::getConstantFieldValue(const GlobalAddressSDNode *Node, 340 uint64_t Offset, uint64_t Size, 341 unsigned char *ByteSeq) { 342 const GlobalVariable *V = dyn_cast<GlobalVariable>(Node->getGlobal()); 343 344 if (!V || !V->hasInitializer()) 345 return false; 346 347 const Constant *Init = V->getInitializer(); 348 const DataLayout &DL = CurDAG->getDataLayout(); 349 val_vec_type TmpVal; 350 351 auto it = cs_vals_.find(static_cast<const void *>(Init)); 352 if (it != cs_vals_.end()) { 353 TmpVal = it->second; 354 } else { 355 uint64_t total_size = 0; 356 if (const ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) 357 total_size = 358 DL.getStructLayout(cast<StructType>(CS->getType()))->getSizeInBytes(); 359 else if (const ConstantArray *CA = dyn_cast<ConstantArray>(Init)) 360 total_size = DL.getTypeAllocSize(CA->getType()->getElementType()) * 361 CA->getNumOperands(); 362 else 363 return false; 364 365 val_vec_type Vals(total_size, 0); 366 if (fillGenericConstant(DL, Init, Vals, 0) == false) 367 return false; 368 cs_vals_[static_cast<const void *>(Init)] = Vals; 369 TmpVal = std::move(Vals); 370 } 371 372 // test whether host endianness matches target 373 union { 374 uint8_t c[2]; 375 uint16_t s; 376 } test_buf; 377 uint16_t test_val = 0x2345; 378 if (DL.isLittleEndian()) 379 support::endian::write16le(test_buf.c, test_val); 380 else 381 support::endian::write16be(test_buf.c, test_val); 382 383 bool endian_match = test_buf.s == test_val; 384 for (uint64_t i = Offset, j = 0; i < Offset + Size; i++, j++) 385 ByteSeq[j] = endian_match ? TmpVal[i] : TmpVal[Offset + Size - 1 - j]; 386 387 return true; 388 } 389 390 bool BPFDAGToDAGISel::fillGenericConstant(const DataLayout &DL, 391 const Constant *CV, 392 val_vec_type &Vals, uint64_t Offset) { 393 uint64_t Size = DL.getTypeAllocSize(CV->getType()); 394 395 if (isa<ConstantAggregateZero>(CV) || isa<UndefValue>(CV)) 396 return true; // already done 397 398 if (const ConstantInt *CI = dyn_cast<ConstantInt>(CV)) { 399 uint64_t val = CI->getZExtValue(); 400 LLVM_DEBUG(dbgs() << "Byte array at offset " << Offset << " with value " 401 << val << '\n'); 402 403 if (Size > 8 || (Size & (Size - 1))) 404 return false; 405 406 // Store based on target endian 407 for (uint64_t i = 0; i < Size; ++i) { 408 Vals[Offset + i] = DL.isLittleEndian() 409 ? ((val >> (i * 8)) & 0xFF) 410 : ((val >> ((Size - i - 1) * 8)) & 0xFF); 411 } 412 return true; 413 } 414 415 if (const ConstantDataArray *CDA = dyn_cast<ConstantDataArray>(CV)) 416 return fillConstantDataArray(DL, CDA, Vals, Offset); 417 418 if (const ConstantArray *CA = dyn_cast<ConstantArray>(CV)) 419 return fillConstantArray(DL, CA, Vals, Offset); 420 421 if (const ConstantStruct *CVS = dyn_cast<ConstantStruct>(CV)) 422 return fillConstantStruct(DL, CVS, Vals, Offset); 423 424 return false; 425 } 426 427 bool BPFDAGToDAGISel::fillConstantDataArray(const DataLayout &DL, 428 const ConstantDataArray *CDA, 429 val_vec_type &Vals, int Offset) { 430 for (unsigned i = 0, e = CDA->getNumElements(); i != e; ++i) { 431 if (fillGenericConstant(DL, CDA->getElementAsConstant(i), Vals, Offset) == 432 false) 433 return false; 434 Offset += DL.getTypeAllocSize(CDA->getElementAsConstant(i)->getType()); 435 } 436 437 return true; 438 } 439 440 bool BPFDAGToDAGISel::fillConstantArray(const DataLayout &DL, 441 const ConstantArray *CA, 442 val_vec_type &Vals, int Offset) { 443 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) { 444 if (fillGenericConstant(DL, CA->getOperand(i), Vals, Offset) == false) 445 return false; 446 Offset += DL.getTypeAllocSize(CA->getOperand(i)->getType()); 447 } 448 449 return true; 450 } 451 452 bool BPFDAGToDAGISel::fillConstantStruct(const DataLayout &DL, 453 const ConstantStruct *CS, 454 val_vec_type &Vals, int Offset) { 455 const StructLayout *Layout = DL.getStructLayout(CS->getType()); 456 for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) { 457 const Constant *Field = CS->getOperand(i); 458 uint64_t SizeSoFar = Layout->getElementOffset(i); 459 if (fillGenericConstant(DL, Field, Vals, Offset + SizeSoFar) == false) 460 return false; 461 } 462 return true; 463 } 464 465 void BPFDAGToDAGISel::PreprocessTrunc(SDNode *Node, 466 SelectionDAG::allnodes_iterator &I) { 467 ConstantSDNode *MaskN = dyn_cast<ConstantSDNode>(Node->getOperand(1)); 468 if (!MaskN) 469 return; 470 471 // The Reg operand should be a virtual register, which is defined 472 // outside the current basic block. DAG combiner has done a pretty 473 // good job in removing truncating inside a single basic block except 474 // when the Reg operand comes from bpf_load_[byte | half | word] for 475 // which the generic optimizer doesn't understand their results are 476 // zero extended. 477 SDValue BaseV = Node->getOperand(0); 478 if (BaseV.getOpcode() != ISD::INTRINSIC_W_CHAIN) 479 return; 480 481 unsigned IntNo = cast<ConstantSDNode>(BaseV->getOperand(1))->getZExtValue(); 482 uint64_t MaskV = MaskN->getZExtValue(); 483 484 if (!((IntNo == Intrinsic::bpf_load_byte && MaskV == 0xFF) || 485 (IntNo == Intrinsic::bpf_load_half && MaskV == 0xFFFF) || 486 (IntNo == Intrinsic::bpf_load_word && MaskV == 0xFFFFFFFF))) 487 return; 488 489 LLVM_DEBUG(dbgs() << "Remove the redundant AND operation in: "; 490 Node->dump(); dbgs() << '\n'); 491 492 I--; 493 CurDAG->ReplaceAllUsesWith(SDValue(Node, 0), BaseV); 494 I++; 495 CurDAG->DeleteNode(Node); 496 497 return; 498 } 499 500 FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) { 501 return new BPFDAGToDAGISel(TM); 502 } 503