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