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