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