474 lines · cpp
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-exception6//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 30using namespace llvm;31 32#define DEBUG_TYPE "bpf-isel"33#define PASS_NAME "BPF DAG->DAG Pattern Instruction Selection"34 35// Instruction Selector Implementation36namespace {37 38class BPFDAGToDAGISel : public SelectionDAGISel {39 40 /// Subtarget - Keep a pointer to the BPFSubtarget around so that we can41 /// make the right decision when generating code for different subtargets.42 const BPFSubtarget *Subtarget;43 44public: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 62private: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 cases73 void PreprocessLoad(SDNode *Node, SelectionDAG::allnodes_iterator &I);74 void PreprocessTrunc(SDNode *Node, SelectionDAG::allnodes_iterator &I);75 76 // Find constants from a constant structure77 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 values89 std::map<const void *, val_vec_type> cs_vals_;90};91 92class BPFDAGToDAGISelLegacy : public SelectionDAGISelLegacy {93public:94 static char ID;95 BPFDAGToDAGISelLegacy(BPFTargetMachine &TM)96 : SelectionDAGISelLegacy(ID, std::make_unique<BPFDAGToDAGISel>(TM)) {}97};98} // namespace99 100char BPFDAGToDAGISelLegacy::ID = 0;101 102INITIALIZE_PASS(BPFDAGToDAGISelLegacy, DEBUG_TYPE, PASS_NAME, false, false)103 104// ComplexPattern used on BPF Load/Store instructions105bool 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|const119 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 Node123 if (auto *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))124 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);125 else126 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 instruction139bool 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|const147 auto *CN = cast<ConstantSDNode>(Addr.getOperand(1));148 if (isInt<16>(CN->getSExtValue())) {149 // If the first operand is a FI, get the TargetFI Node150 if (auto *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))151 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);152 else153 return false;154 155 Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);156 return true;157 }158 159 return false;160}161 162bool 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: // memory170 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 183void 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::FrameIndex: {197 int FI = cast<FrameIndexSDNode>(Node)->getIndex();198 EVT VT = Node->getValueType(0);199 SDValue TFI = CurDAG->getTargetFrameIndex(FI, VT);200 unsigned Opc = BPF::MOV_rr;201 if (Node->hasOneUse()) {202 CurDAG->SelectNodeTo(Node, Opc, VT, TFI);203 return;204 }205 ReplaceNode(Node, CurDAG->getMachineNode(Opc, SDLoc(Node), VT, TFI));206 return;207 }208 }209 210 // Select the default instruction211 SelectCode(Node);212}213 214void BPFDAGToDAGISel::PreprocessLoad(SDNode *Node,215 SelectionDAG::allnodes_iterator &I) {216 union {217 uint8_t c[8];218 uint16_t s;219 uint32_t i;220 uint64_t d;221 } new_val; // hold up the constant values replacing loads.222 bool to_replace = false;223 SDLoc DL(Node);224 const LoadSDNode *LD = cast<LoadSDNode>(Node);225 if (!LD->getMemOperand()->getSize().hasValue())226 return;227 uint64_t size = LD->getMemOperand()->getSize().getValue();228 229 if (!size || size > 8 || (size & (size - 1)) || !LD->isSimple())230 return;231 232 SDNode *LDAddrNode = LD->getOperand(1).getNode();233 // Match LDAddr against either global_addr or (global_addr + offset)234 unsigned opcode = LDAddrNode->getOpcode();235 if (opcode == ISD::ADD) {236 SDValue OP1 = LDAddrNode->getOperand(0);237 SDValue OP2 = LDAddrNode->getOperand(1);238 239 // We want to find the pattern global_addr + offset240 SDNode *OP1N = OP1.getNode();241 if (OP1N->getOpcode() <= ISD::BUILTIN_OP_END || OP1N->getNumOperands() == 0)242 return;243 244 LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');245 246 const GlobalAddressSDNode *GADN =247 dyn_cast<GlobalAddressSDNode>(OP1N->getOperand(0).getNode());248 const ConstantSDNode *CDN = dyn_cast<ConstantSDNode>(OP2.getNode());249 if (GADN && CDN)250 to_replace =251 getConstantFieldValue(GADN, CDN->getZExtValue(), size, new_val.c);252 } else if (LDAddrNode->getOpcode() > ISD::BUILTIN_OP_END &&253 LDAddrNode->getNumOperands() > 0) {254 LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');255 256 SDValue OP1 = LDAddrNode->getOperand(0);257 if (const GlobalAddressSDNode *GADN =258 dyn_cast<GlobalAddressSDNode>(OP1.getNode()))259 to_replace = getConstantFieldValue(GADN, 0, size, new_val.c);260 }261 262 if (!to_replace)263 return;264 265 // replacing the old with a new value266 uint64_t val;267 if (size == 1)268 val = new_val.c[0];269 else if (size == 2)270 val = new_val.s;271 else if (size == 4)272 val = new_val.i;273 else {274 val = new_val.d;275 }276 277 LLVM_DEBUG(dbgs() << "Replacing load of size " << size << " with constant "278 << val << '\n');279 SDValue NVal = CurDAG->getConstant(val, DL, LD->getValueType(0));280 281 // After replacement, the current node is dead, we need to282 // go backward one step to make iterator still work283 I--;284 SDValue From[] = {SDValue(Node, 0), SDValue(Node, 1)};285 SDValue To[] = {NVal, NVal};286 CurDAG->ReplaceAllUsesOfValuesWith(From, To, 2);287 I++;288 // It is safe to delete node now289 CurDAG->DeleteNode(Node);290}291 292void BPFDAGToDAGISel::PreprocessISelDAG() {293 // Iterate through all nodes, interested in the following case:294 //295 // . loads from ConstantStruct or ConstantArray of constructs296 // which can be turns into constant itself, with this we can297 // avoid reading from read-only section at runtime.298 //299 // . Removing redundant AND for intrinsic narrow loads.300 for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),301 E = CurDAG->allnodes_end();302 I != E;) {303 SDNode *Node = &*I++;304 unsigned Opcode = Node->getOpcode();305 if (Opcode == ISD::LOAD)306 PreprocessLoad(Node, I);307 else if (Opcode == ISD::AND)308 PreprocessTrunc(Node, I);309 }310}311 312bool BPFDAGToDAGISel::getConstantFieldValue(const GlobalAddressSDNode *Node,313 uint64_t Offset, uint64_t Size,314 unsigned char *ByteSeq) {315 const GlobalVariable *V = dyn_cast<GlobalVariable>(Node->getGlobal());316 317 if (!V || !V->hasInitializer() || !V->isConstant())318 return false;319 320 const Constant *Init = V->getInitializer();321 const DataLayout &DL = CurDAG->getDataLayout();322 val_vec_type TmpVal;323 324 auto it = cs_vals_.find(static_cast<const void *>(Init));325 if (it != cs_vals_.end()) {326 TmpVal = it->second;327 } else {328 uint64_t total_size = 0;329 if (const ConstantStruct *CS = dyn_cast<ConstantStruct>(Init))330 total_size =331 DL.getStructLayout(cast<StructType>(CS->getType()))->getSizeInBytes();332 else if (const ConstantArray *CA = dyn_cast<ConstantArray>(Init))333 total_size = DL.getTypeAllocSize(CA->getType()->getElementType()) *334 CA->getNumOperands();335 else336 return false;337 338 val_vec_type Vals(total_size, 0);339 if (fillGenericConstant(DL, Init, Vals, 0) == false)340 return false;341 cs_vals_[static_cast<const void *>(Init)] = Vals;342 TmpVal = std::move(Vals);343 }344 345 // test whether host endianness matches target346 union {347 uint8_t c[2];348 uint16_t s;349 } test_buf;350 uint16_t test_val = 0x2345;351 if (DL.isLittleEndian())352 support::endian::write16le(test_buf.c, test_val);353 else354 support::endian::write16be(test_buf.c, test_val);355 356 bool endian_match = test_buf.s == test_val;357 for (uint64_t i = Offset, j = 0; i < Offset + Size; i++, j++)358 ByteSeq[j] = endian_match ? TmpVal[i] : TmpVal[Offset + Size - 1 - j];359 360 return true;361}362 363bool BPFDAGToDAGISel::fillGenericConstant(const DataLayout &DL,364 const Constant *CV,365 val_vec_type &Vals, uint64_t Offset) {366 uint64_t Size = DL.getTypeAllocSize(CV->getType());367 368 if (isa<ConstantAggregateZero>(CV) || isa<UndefValue>(CV))369 return true; // already done370 371 if (const ConstantInt *CI = dyn_cast<ConstantInt>(CV)) {372 uint64_t val = CI->getZExtValue();373 LLVM_DEBUG(dbgs() << "Byte array at offset " << Offset << " with value "374 << val << '\n');375 376 if (Size > 8 || (Size & (Size - 1)))377 return false;378 379 // Store based on target endian380 for (uint64_t i = 0; i < Size; ++i) {381 Vals[Offset + i] = DL.isLittleEndian()382 ? ((val >> (i * 8)) & 0xFF)383 : ((val >> ((Size - i - 1) * 8)) & 0xFF);384 }385 return true;386 }387 388 if (const ConstantDataArray *CDA = dyn_cast<ConstantDataArray>(CV))389 return fillConstantDataArray(DL, CDA, Vals, Offset);390 391 if (const ConstantArray *CA = dyn_cast<ConstantArray>(CV))392 return fillConstantArray(DL, CA, Vals, Offset);393 394 if (const ConstantStruct *CVS = dyn_cast<ConstantStruct>(CV))395 return fillConstantStruct(DL, CVS, Vals, Offset);396 397 return false;398}399 400bool BPFDAGToDAGISel::fillConstantDataArray(const DataLayout &DL,401 const ConstantDataArray *CDA,402 val_vec_type &Vals, int Offset) {403 for (unsigned i = 0, e = CDA->getNumElements(); i != e; ++i) {404 if (fillGenericConstant(DL, CDA->getElementAsConstant(i), Vals, Offset) ==405 false)406 return false;407 Offset += DL.getTypeAllocSize(CDA->getElementAsConstant(i)->getType());408 }409 410 return true;411}412 413bool BPFDAGToDAGISel::fillConstantArray(const DataLayout &DL,414 const ConstantArray *CA,415 val_vec_type &Vals, int Offset) {416 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) {417 if (fillGenericConstant(DL, CA->getOperand(i), Vals, Offset) == false)418 return false;419 Offset += DL.getTypeAllocSize(CA->getOperand(i)->getType());420 }421 422 return true;423}424 425bool BPFDAGToDAGISel::fillConstantStruct(const DataLayout &DL,426 const ConstantStruct *CS,427 val_vec_type &Vals, int Offset) {428 const StructLayout *Layout = DL.getStructLayout(CS->getType());429 for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) {430 const Constant *Field = CS->getOperand(i);431 uint64_t SizeSoFar = Layout->getElementOffset(i);432 if (fillGenericConstant(DL, Field, Vals, Offset + SizeSoFar) == false)433 return false;434 }435 return true;436}437 438void BPFDAGToDAGISel::PreprocessTrunc(SDNode *Node,439 SelectionDAG::allnodes_iterator &I) {440 ConstantSDNode *MaskN = dyn_cast<ConstantSDNode>(Node->getOperand(1));441 if (!MaskN)442 return;443 444 // The Reg operand should be a virtual register, which is defined445 // outside the current basic block. DAG combiner has done a pretty446 // good job in removing truncating inside a single basic block except447 // when the Reg operand comes from bpf_load_[byte | half | word] for448 // which the generic optimizer doesn't understand their results are449 // zero extended.450 SDValue BaseV = Node->getOperand(0);451 if (BaseV.getOpcode() != ISD::INTRINSIC_W_CHAIN)452 return;453 454 unsigned IntNo = BaseV->getConstantOperandVal(1);455 uint64_t MaskV = MaskN->getZExtValue();456 457 if (!((IntNo == Intrinsic::bpf_load_byte && MaskV == 0xFF) ||458 (IntNo == Intrinsic::bpf_load_half && MaskV == 0xFFFF) ||459 (IntNo == Intrinsic::bpf_load_word && MaskV == 0xFFFFFFFF)))460 return;461 462 LLVM_DEBUG(dbgs() << "Remove the redundant AND operation in: ";463 Node->dump(); dbgs() << '\n');464 465 I--;466 CurDAG->ReplaceAllUsesWith(SDValue(Node, 0), BaseV);467 I++;468 CurDAG->DeleteNode(Node);469}470 471FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) {472 return new BPFDAGToDAGISelLegacy(TM);473}474