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