1 //===-- BPFISelDAGToDAG.cpp - A dag to dag inst selector for BPF ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines a DAG pattern matching instruction selector for BPF,
11 // converting from a legalized dag to a BPF dag.
13 //===----------------------------------------------------------------------===//
16 #include "BPFRegisterInfo.h"
17 #include "BPFSubtarget.h"
18 #include "BPFTargetMachine.h"
19 #include "llvm/CodeGen/FunctionLoweringInfo.h"
20 #include "llvm/CodeGen/MachineConstantPool.h"
21 #include "llvm/CodeGen/MachineFrameInfo.h"
22 #include "llvm/CodeGen/MachineFunction.h"
23 #include "llvm/CodeGen/MachineInstrBuilder.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/CodeGen/SelectionDAGISel.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/IntrinsicInst.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"
36 #define DEBUG_TYPE "bpf-isel"
38 // Instruction Selector Implementation
41 class BPFDAGToDAGISel : public SelectionDAGISel {
43 explicit BPFDAGToDAGISel(BPFTargetMachine &TM) : SelectionDAGISel(TM) {}
45 StringRef getPassName() const override {
46 return "BPF DAG->DAG Pattern Instruction Selection";
49 void PreprocessISelDAG() override;
52 // Include the pieces autogenerated from the target description.
53 #include "BPFGenDAGISel.inc"
55 void Select(SDNode *N) override;
57 // Complex Pattern for address selection.
58 bool SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset);
59 bool SelectFIAddr(SDValue Addr, SDValue &Base, SDValue &Offset);
61 // Node preprocessing cases
62 void PreprocessLoad(SDNode *Node, SelectionDAG::allnodes_iterator I);
63 void PreprocessCopyToReg(SDNode *Node);
64 void PreprocessTrunc(SDNode *Node, SelectionDAG::allnodes_iterator I);
66 // Find constants from a constant structure
67 typedef std::vector<unsigned char> val_vec_type;
68 bool fillGenericConstant(const DataLayout &DL, const Constant *CV,
69 val_vec_type &Vals, uint64_t Offset);
70 bool fillConstantDataArray(const DataLayout &DL, const ConstantDataArray *CDA,
71 val_vec_type &Vals, int Offset);
72 bool fillConstantArray(const DataLayout &DL, const ConstantArray *CA,
73 val_vec_type &Vals, int Offset);
74 bool fillConstantStruct(const DataLayout &DL, const ConstantStruct *CS,
75 val_vec_type &Vals, int Offset);
76 bool getConstantFieldValue(const GlobalAddressSDNode *Node, uint64_t Offset,
77 uint64_t Size, unsigned char *ByteSeq);
78 bool checkLoadDef(unsigned DefReg, unsigned match_load_op);
80 // Mapping from ConstantStruct global value to corresponding byte-list values
81 std::map<const void *, val_vec_type> cs_vals_;
82 // Mapping from vreg to load memory opcode
83 std::map<unsigned, unsigned> load_to_vreg_;
87 // ComplexPattern used on BPF Load/Store instructions
88 bool BPFDAGToDAGISel::SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset) {
89 // if Address is FI, get the TargetFrameIndex.
91 if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
92 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
93 Offset = CurDAG->getTargetConstant(0, DL, MVT::i64);
97 if (Addr.getOpcode() == ISD::TargetExternalSymbol ||
98 Addr.getOpcode() == ISD::TargetGlobalAddress)
101 // Addresses of the form Addr+const or Addr|const
102 if (CurDAG->isBaseWithConstantOffset(Addr)) {
103 ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1));
104 if (isInt<16>(CN->getSExtValue())) {
106 // If the first operand is a FI, get the TargetFI Node
107 if (FrameIndexSDNode *FIN =
108 dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))
109 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
111 Base = Addr.getOperand(0);
113 Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);
119 Offset = CurDAG->getTargetConstant(0, DL, MVT::i64);
123 // ComplexPattern used on BPF FI instruction
124 bool BPFDAGToDAGISel::SelectFIAddr(SDValue Addr, SDValue &Base,
128 if (!CurDAG->isBaseWithConstantOffset(Addr))
131 // Addresses of the form Addr+const or Addr|const
132 ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1));
133 if (isInt<16>(CN->getSExtValue())) {
135 // If the first operand is a FI, get the TargetFI Node
136 if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))
137 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
141 Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);
148 void BPFDAGToDAGISel::Select(SDNode *Node) {
149 unsigned Opcode = Node->getOpcode();
151 // Dump information about the Node being selected
152 DEBUG(dbgs() << "Selecting: "; Node->dump(CurDAG); dbgs() << '\n');
154 // If we have a custom node, we already have selected!
155 if (Node->isMachineOpcode()) {
156 DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << '\n');
160 // tablegen selection should be handled here.
166 const DebugLoc &DL = Node->getDebugLoc();
168 errs() << "Error at line " << DL.getLine() << ": ";
171 errs() << "Unsupport signed division for DAG: ";
172 Node->print(errs(), CurDAG);
173 errs() << "Please convert to unsigned div/mod.\n";
176 case ISD::INTRINSIC_W_CHAIN: {
177 unsigned IntNo = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue();
179 case Intrinsic::bpf_load_byte:
180 case Intrinsic::bpf_load_half:
181 case Intrinsic::bpf_load_word: {
183 SDValue Chain = Node->getOperand(0);
184 SDValue N1 = Node->getOperand(1);
185 SDValue Skb = Node->getOperand(2);
186 SDValue N3 = Node->getOperand(3);
188 SDValue R6Reg = CurDAG->getRegister(BPF::R6, MVT::i64);
189 Chain = CurDAG->getCopyToReg(Chain, DL, R6Reg, Skb, SDValue());
190 Node = CurDAG->UpdateNodeOperands(Node, Chain, N1, R6Reg, N3);
197 case ISD::FrameIndex: {
198 int FI = cast<FrameIndexSDNode>(Node)->getIndex();
199 EVT VT = Node->getValueType(0);
200 SDValue TFI = CurDAG->getTargetFrameIndex(FI, VT);
201 unsigned Opc = BPF::MOV_rr;
202 if (Node->hasOneUse()) {
203 CurDAG->SelectNodeTo(Node, Opc, VT, TFI);
206 ReplaceNode(Node, CurDAG->getMachineNode(Opc, SDLoc(Node), VT, TFI));
211 // Select the default instruction
215 void BPFDAGToDAGISel::PreprocessLoad(SDNode *Node,
216 SelectionDAG::allnodes_iterator I) {
222 } new_val; // hold up the constant values replacing loads.
223 bool to_replace = false;
225 const LoadSDNode *LD = cast<LoadSDNode>(Node);
226 uint64_t size = LD->getMemOperand()->getSize();
228 if (!size || size > 8 || (size & (size - 1)))
231 SDNode *LDAddrNode = LD->getOperand(1).getNode();
232 // Match LDAddr against either global_addr or (global_addr + offset)
233 unsigned opcode = LDAddrNode->getOpcode();
234 if (opcode == ISD::ADD) {
235 SDValue OP1 = LDAddrNode->getOperand(0);
236 SDValue OP2 = LDAddrNode->getOperand(1);
238 // We want to find the pattern global_addr + offset
239 SDNode *OP1N = OP1.getNode();
240 if (OP1N->getOpcode() <= ISD::BUILTIN_OP_END || OP1N->getNumOperands() == 0)
243 DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');
245 const GlobalAddressSDNode *GADN =
246 dyn_cast<GlobalAddressSDNode>(OP1N->getOperand(0).getNode());
247 const ConstantSDNode *CDN = dyn_cast<ConstantSDNode>(OP2.getNode());
250 getConstantFieldValue(GADN, CDN->getZExtValue(), size, new_val.c);
251 } else if (LDAddrNode->getOpcode() > ISD::BUILTIN_OP_END &&
252 LDAddrNode->getNumOperands() > 0) {
253 DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');
255 SDValue OP1 = LDAddrNode->getOperand(0);
256 if (const GlobalAddressSDNode *GADN =
257 dyn_cast<GlobalAddressSDNode>(OP1.getNode()))
258 to_replace = getConstantFieldValue(GADN, 0, size, new_val.c);
264 // replacing the old with a new value
276 DEBUG(dbgs() << "Replacing load of size " << size << " with constant " << val
278 SDValue NVal = CurDAG->getConstant(val, DL, MVT::i64);
280 // After replacement, the current node is dead, we need to
281 // go backward one step to make iterator still work
283 SDValue From[] = {SDValue(Node, 0), SDValue(Node, 1)};
284 SDValue To[] = {NVal, NVal};
285 CurDAG->ReplaceAllUsesOfValuesWith(From, To, 2);
287 // It is safe to delete node now
288 CurDAG->DeleteNode(Node);
291 void BPFDAGToDAGISel::PreprocessISelDAG() {
292 // Iterate through all nodes, interested in the following cases:
294 // . loads from ConstantStruct or ConstantArray of constructs
295 // which can be turns into constant itself, with this we can
296 // avoid reading from read-only section at runtime.
298 // . reg truncating is often the result of 8/16/32bit->64bit or
299 // 8/16bit->32bit conversion. If the reg value is loaded with
300 // masked byte width, the AND operation can be removed since
301 // BPF LOAD already has zero extension.
303 // This also solved a correctness issue.
304 // In BPF socket-related program, e.g., __sk_buff->{data, data_end}
305 // are 32-bit registers, but later on, kernel verifier will rewrite
306 // it with 64-bit value. Therefore, truncating the value after the
307 // load will result in incorrect code.
308 for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
309 E = CurDAG->allnodes_end();
311 SDNode *Node = &*I++;
312 unsigned Opcode = Node->getOpcode();
313 if (Opcode == ISD::LOAD)
314 PreprocessLoad(Node, I);
315 else if (Opcode == ISD::CopyToReg)
316 PreprocessCopyToReg(Node);
317 else if (Opcode == ISD::AND)
318 PreprocessTrunc(Node, I);
322 bool BPFDAGToDAGISel::getConstantFieldValue(const GlobalAddressSDNode *Node,
323 uint64_t Offset, uint64_t Size,
324 unsigned char *ByteSeq) {
325 const GlobalVariable *V = dyn_cast<GlobalVariable>(Node->getGlobal());
327 if (!V || !V->hasInitializer())
330 const Constant *Init = V->getInitializer();
331 const DataLayout &DL = CurDAG->getDataLayout();
334 auto it = cs_vals_.find(static_cast<const void *>(Init));
335 if (it != cs_vals_.end()) {
338 uint64_t total_size = 0;
339 if (const ConstantStruct *CS = dyn_cast<ConstantStruct>(Init))
341 DL.getStructLayout(cast<StructType>(CS->getType()))->getSizeInBytes();
342 else if (const ConstantArray *CA = dyn_cast<ConstantArray>(Init))
343 total_size = DL.getTypeAllocSize(CA->getType()->getElementType()) *
344 CA->getNumOperands();
348 val_vec_type Vals(total_size, 0);
349 if (fillGenericConstant(DL, Init, Vals, 0) == false)
351 cs_vals_[static_cast<const void *>(Init)] = Vals;
352 TmpVal = std::move(Vals);
355 // test whether host endianness matches target
360 uint16_t test_val = 0x2345;
361 if (DL.isLittleEndian())
362 support::endian::write16le(test_buf.c, test_val);
364 support::endian::write16be(test_buf.c, test_val);
366 bool endian_match = test_buf.s == test_val;
367 for (uint64_t i = Offset, j = 0; i < Offset + Size; i++, j++)
368 ByteSeq[j] = endian_match ? TmpVal[i] : TmpVal[Offset + Size - 1 - j];
373 bool BPFDAGToDAGISel::fillGenericConstant(const DataLayout &DL,
375 val_vec_type &Vals, uint64_t Offset) {
376 uint64_t Size = DL.getTypeAllocSize(CV->getType());
378 if (isa<ConstantAggregateZero>(CV) || isa<UndefValue>(CV))
379 return true; // already done
381 if (const ConstantInt *CI = dyn_cast<ConstantInt>(CV)) {
382 uint64_t val = CI->getZExtValue();
383 DEBUG(dbgs() << "Byte array at offset " << Offset << " with value " << val
386 if (Size > 8 || (Size & (Size - 1)))
389 // Store based on target endian
390 for (uint64_t i = 0; i < Size; ++i) {
391 Vals[Offset + i] = DL.isLittleEndian()
392 ? ((val >> (i * 8)) & 0xFF)
393 : ((val >> ((Size - i - 1) * 8)) & 0xFF);
398 if (const ConstantDataArray *CDA = dyn_cast<ConstantDataArray>(CV))
399 return fillConstantDataArray(DL, CDA, Vals, Offset);
401 if (const ConstantArray *CA = dyn_cast<ConstantArray>(CV))
402 return fillConstantArray(DL, CA, Vals, Offset);
404 if (const ConstantStruct *CVS = dyn_cast<ConstantStruct>(CV))
405 return fillConstantStruct(DL, CVS, Vals, Offset);
410 bool BPFDAGToDAGISel::fillConstantDataArray(const DataLayout &DL,
411 const ConstantDataArray *CDA,
412 val_vec_type &Vals, int Offset) {
413 for (unsigned i = 0, e = CDA->getNumElements(); i != e; ++i) {
414 if (fillGenericConstant(DL, CDA->getElementAsConstant(i), Vals, Offset) ==
417 Offset += DL.getTypeAllocSize(CDA->getElementAsConstant(i)->getType());
423 bool BPFDAGToDAGISel::fillConstantArray(const DataLayout &DL,
424 const ConstantArray *CA,
425 val_vec_type &Vals, int Offset) {
426 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) {
427 if (fillGenericConstant(DL, CA->getOperand(i), Vals, Offset) == false)
429 Offset += DL.getTypeAllocSize(CA->getOperand(i)->getType());
435 bool BPFDAGToDAGISel::fillConstantStruct(const DataLayout &DL,
436 const ConstantStruct *CS,
437 val_vec_type &Vals, int Offset) {
438 const StructLayout *Layout = DL.getStructLayout(CS->getType());
439 for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) {
440 const Constant *Field = CS->getOperand(i);
441 uint64_t SizeSoFar = Layout->getElementOffset(i);
442 if (fillGenericConstant(DL, Field, Vals, Offset + SizeSoFar) == false)
448 void BPFDAGToDAGISel::PreprocessCopyToReg(SDNode *Node) {
449 const RegisterSDNode *RegN = dyn_cast<RegisterSDNode>(Node->getOperand(1));
450 if (!RegN || !TargetRegisterInfo::isVirtualRegister(RegN->getReg()))
453 const LoadSDNode *LD = dyn_cast<LoadSDNode>(Node->getOperand(2));
457 // Assign a load value to a virtual register. record its load width
458 unsigned mem_load_op = 0;
459 switch (LD->getMemOperand()->getSize()) {
463 mem_load_op = BPF::LDW;
466 mem_load_op = BPF::LDH;
469 mem_load_op = BPF::LDB;
473 DEBUG(dbgs() << "Find Load Value to VReg "
474 << TargetRegisterInfo::virtReg2Index(RegN->getReg()) << '\n');
475 load_to_vreg_[RegN->getReg()] = mem_load_op;
478 void BPFDAGToDAGISel::PreprocessTrunc(SDNode *Node,
479 SelectionDAG::allnodes_iterator I) {
480 ConstantSDNode *MaskN = dyn_cast<ConstantSDNode>(Node->getOperand(1));
484 unsigned match_load_op = 0;
485 switch (MaskN->getZExtValue()) {
489 match_load_op = BPF::LDW;
492 match_load_op = BPF::LDH;
495 match_load_op = BPF::LDB;
499 // The Reg operand should be a virtual register, which is defined
500 // outside the current basic block. DAG combiner has done a pretty
501 // good job in removing truncating inside a single basic block.
502 SDValue BaseV = Node->getOperand(0);
503 if (BaseV.getOpcode() != ISD::CopyFromReg)
506 const RegisterSDNode *RegN =
507 dyn_cast<RegisterSDNode>(BaseV.getNode()->getOperand(1));
508 if (!RegN || !TargetRegisterInfo::isVirtualRegister(RegN->getReg()))
510 unsigned AndOpReg = RegN->getReg();
511 DEBUG(dbgs() << "Examine %vreg" << TargetRegisterInfo::virtReg2Index(AndOpReg)
514 // Examine the PHI insns in the MachineBasicBlock to found out the
515 // definitions of this virtual register. At this stage (DAG2DAG
516 // transformation), only PHI machine insns are available in the machine basic
518 MachineBasicBlock *MBB = FuncInfo->MBB;
519 MachineInstr *MII = nullptr;
520 for (auto &MI : *MBB) {
521 for (unsigned i = 0; i < MI.getNumOperands(); ++i) {
522 const MachineOperand &MOP = MI.getOperand(i);
523 if (!MOP.isReg() || !MOP.isDef())
525 unsigned Reg = MOP.getReg();
526 if (TargetRegisterInfo::isVirtualRegister(Reg) && Reg == AndOpReg) {
533 if (MII == nullptr) {
534 // No phi definition in this block.
535 if (!checkLoadDef(AndOpReg, match_load_op))
538 // The PHI node looks like:
539 // %vreg2<def> = PHI %vreg0, <BB#1>, %vreg1, <BB#3>
540 // Trace each incoming definition, e.g., (%vreg0, BB#1) and (%vreg1, BB#3)
541 // The AND operation can be removed if both %vreg0 in BB#1 and %vreg1 in
542 // BB#3 are defined with with a load matching the MaskN.
543 DEBUG(dbgs() << "Check PHI Insn: "; MII->dump(); dbgs() << '\n');
544 unsigned PrevReg = -1;
545 for (unsigned i = 0; i < MII->getNumOperands(); ++i) {
546 const MachineOperand &MOP = MII->getOperand(i);
550 PrevReg = MOP.getReg();
551 if (!TargetRegisterInfo::isVirtualRegister(PrevReg))
553 if (!checkLoadDef(PrevReg, match_load_op))
559 DEBUG(dbgs() << "Remove the redundant AND operation in: "; Node->dump();
563 CurDAG->ReplaceAllUsesWith(SDValue(Node, 0), BaseV);
565 CurDAG->DeleteNode(Node);
568 bool BPFDAGToDAGISel::checkLoadDef(unsigned DefReg, unsigned match_load_op) {
569 auto it = load_to_vreg_.find(DefReg);
570 if (it == load_to_vreg_.end())
571 return false; // The definition of register is not exported yet.
573 return it->second == match_load_op;
576 FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) {
577 return new BPFDAGToDAGISel(TM);