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