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 BPFISD::LOAD_STACK_ARG: {
197 SDValue Chain = Node->getOperand(Num: 0);
198 auto *CN = cast<ConstantSDNode>(Val: Node->getOperand(Num: 1));
199 SDValue Off =
200 CurDAG->getTargetConstant(Val: CN->getSExtValue(), DL: SDLoc(Node), VT: MVT::i64);
201 EVT ValVT = Node->getValueType(ResNo: 0);
202 CurDAG->SelectNodeTo(N: Node, MachineOpc: BPF::LOAD_STACK_ARG_PSEUDO, VT1: ValVT, VT2: MVT::Other,
203 Op1: Off, Op2: Chain);
204 return;
205 }
206
207 case BPFISD::STORE_STACK_ARG: {
208 SDValue Chain = Node->getOperand(Num: 0);
209 auto *CN = cast<ConstantSDNode>(Val: Node->getOperand(Num: 1));
210 SDValue Off =
211 CurDAG->getTargetConstant(Val: CN->getSExtValue(), DL: SDLoc(Node), VT: MVT::i64);
212 SDValue Val = Node->getOperand(Num: 2);
213
214 // Use store-immediate when the value is a constant that fits in 32 bits.
215 if (auto *ValCN = dyn_cast<ConstantSDNode>(Val);
216 ValCN && Subtarget->hasStoreImm() && isInt<32>(x: ValCN->getSExtValue())) {
217 SDValue Imm = CurDAG->getTargetConstant(Val: ValCN->getSExtValue(),
218 DL: SDLoc(Node), VT: MVT::i64);
219 CurDAG->SelectNodeTo(N: Node, MachineOpc: BPF::STORE_STACK_ARG_IMM_PSEUDO, VT: MVT::Other,
220 Op1: Off, Op2: Imm, Op3: Chain);
221 } else {
222 CurDAG->SelectNodeTo(N: Node, MachineOpc: BPF::STORE_STACK_ARG_PSEUDO, VT: MVT::Other, Op1: Off,
223 Op2: Val, Op3: Chain);
224 }
225 return;
226 }
227
228 case ISD::FrameIndex: {
229 int FI = cast<FrameIndexSDNode>(Val: Node)->getIndex();
230 EVT VT = Node->getValueType(ResNo: 0);
231 SDValue TFI = CurDAG->getTargetFrameIndex(FI, VT);
232 unsigned Opc = BPF::MOV_rr;
233 if (Node->hasOneUse()) {
234 CurDAG->SelectNodeTo(N: Node, MachineOpc: Opc, VT, Op1: TFI);
235 return;
236 }
237 ReplaceNode(F: Node, T: CurDAG->getMachineNode(Opcode: Opc, dl: SDLoc(Node), VT, Op1: TFI));
238 return;
239 }
240 }
241
242 // Select the default instruction
243 SelectCode(N: Node);
244}
245
246void 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>(Val: Node);
257 if (!LD->getMemOperand()->getSize().hasValue())
258 return;
259 uint64_t size = LD->getMemOperand()->getSize().getValue();
260
261 if (!size || size > 8 || (size & (size - 1)) || !LD->isSimple())
262 return;
263
264 SDNode *LDAddrNode = LD->getOperand(Num: 1).getNode();
265 // Match LDAddr against either global_addr or (global_addr + offset)
266 unsigned opcode = LDAddrNode->getOpcode();
267 if (opcode == ISD::ADD) {
268 SDValue OP1 = LDAddrNode->getOperand(Num: 0);
269 SDValue OP2 = LDAddrNode->getOperand(Num: 1);
270
271 // We want to find the pattern global_addr + offset
272 SDNode *OP1N = OP1.getNode();
273 if (OP1N->getOpcode() <= ISD::BUILTIN_OP_END || OP1N->getNumOperands() == 0)
274 return;
275
276 LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');
277
278 const GlobalAddressSDNode *GADN =
279 dyn_cast<GlobalAddressSDNode>(Val: OP1N->getOperand(Num: 0).getNode());
280 const ConstantSDNode *CDN = dyn_cast<ConstantSDNode>(Val: OP2.getNode());
281 if (GADN && CDN)
282 to_replace =
283 getConstantFieldValue(Node: GADN, Offset: CDN->getZExtValue(), Size: size, ByteSeq: new_val.c);
284 } else if (LDAddrNode->getOpcode() > ISD::BUILTIN_OP_END &&
285 LDAddrNode->getNumOperands() > 0) {
286 LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');
287
288 SDValue OP1 = LDAddrNode->getOperand(Num: 0);
289 if (const GlobalAddressSDNode *GADN =
290 dyn_cast<GlobalAddressSDNode>(Val: OP1.getNode()))
291 to_replace = getConstantFieldValue(Node: GADN, Offset: 0, Size: size, ByteSeq: new_val.c);
292 }
293
294 if (!to_replace)
295 return;
296
297 // replacing the old with a new value
298 uint64_t val;
299 if (size == 1)
300 val = new_val.c[0];
301 else if (size == 2)
302 val = new_val.s;
303 else if (size == 4)
304 val = new_val.i;
305 else {
306 val = new_val.d;
307 }
308
309 LLVM_DEBUG(dbgs() << "Replacing load of size " << size << " with constant "
310 << val << '\n');
311 SDValue NVal = CurDAG->getConstant(Val: val, DL, VT: LD->getValueType(ResNo: 0));
312
313 // After replacement, the current node is dead, we need to
314 // go backward one step to make iterator still work
315 I--;
316 SDValue From[] = {SDValue(Node, 0), SDValue(Node, 1)};
317 SDValue To[] = {NVal, NVal};
318 CurDAG->ReplaceAllUsesOfValuesWith(From, To, Num: 2);
319 I++;
320 // It is safe to delete node now
321 CurDAG->DeleteNode(N: Node);
322}
323
324void BPFDAGToDAGISel::PreprocessISelDAG() {
325 // Iterate through all nodes, interested in the following case:
326 //
327 // . loads from ConstantStruct or ConstantArray of constructs
328 // which can be turns into constant itself, with this we can
329 // avoid reading from read-only section at runtime.
330 //
331 // . Removing redundant AND for intrinsic narrow loads.
332 for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
333 E = CurDAG->allnodes_end();
334 I != E;) {
335 SDNode *Node = &*I++;
336 unsigned Opcode = Node->getOpcode();
337 if (Opcode == ISD::LOAD)
338 PreprocessLoad(Node, I);
339 else if (Opcode == ISD::AND)
340 PreprocessTrunc(Node, I);
341 }
342}
343
344bool BPFDAGToDAGISel::getConstantFieldValue(const GlobalAddressSDNode *Node,
345 uint64_t Offset, uint64_t Size,
346 unsigned char *ByteSeq) {
347 const GlobalVariable *V = dyn_cast<GlobalVariable>(Val: Node->getGlobal());
348
349 if (!V || !V->hasInitializer() || !V->isConstant())
350 return false;
351
352 const Constant *Init = V->getInitializer();
353 const DataLayout &DL = CurDAG->getDataLayout();
354 val_vec_type TmpVal;
355
356 auto it = cs_vals_.find(x: static_cast<const void *>(Init));
357 if (it != cs_vals_.end()) {
358 TmpVal = it->second;
359 } else {
360 uint64_t total_size = 0;
361 if (const ConstantStruct *CS = dyn_cast<ConstantStruct>(Val: Init))
362 total_size =
363 DL.getStructLayout(Ty: cast<StructType>(Val: CS->getType()))->getSizeInBytes();
364 else if (const ConstantArray *CA = dyn_cast<ConstantArray>(Val: Init))
365 total_size = DL.getTypeAllocSize(Ty: CA->getType()->getElementType()) *
366 CA->getNumOperands();
367 else
368 return false;
369
370 val_vec_type Vals(total_size, 0);
371 if (fillGenericConstant(DL, CV: Init, Vals, Offset: 0) == false)
372 return false;
373 cs_vals_[static_cast<const void *>(Init)] = Vals;
374 TmpVal = std::move(Vals);
375 }
376
377 // test whether host endianness matches target
378 union {
379 uint8_t c[2];
380 uint16_t s;
381 } test_buf;
382 uint16_t test_val = 0x2345;
383 if (DL.isLittleEndian())
384 support::endian::write16le(P: test_buf.c, V: test_val);
385 else
386 support::endian::write16be(P: test_buf.c, V: test_val);
387
388 bool endian_match = test_buf.s == test_val;
389 for (uint64_t i = Offset, j = 0; i < Offset + Size; i++, j++)
390 ByteSeq[j] = endian_match ? TmpVal[i] : TmpVal[Offset + Size - 1 - j];
391
392 return true;
393}
394
395bool BPFDAGToDAGISel::fillGenericConstant(const DataLayout &DL,
396 const Constant *CV,
397 val_vec_type &Vals, uint64_t Offset) {
398 uint64_t Size = DL.getTypeAllocSize(Ty: CV->getType());
399
400 if (isa<ConstantAggregateZero>(Val: CV) || isa<UndefValue>(Val: CV))
401 return true; // already done
402
403 if (const ConstantInt *CI = dyn_cast<ConstantInt>(Val: CV)) {
404 uint64_t val = CI->getZExtValue();
405 LLVM_DEBUG(dbgs() << "Byte array at offset " << Offset << " with value "
406 << val << '\n');
407
408 if (Size > 8 || (Size & (Size - 1)))
409 return false;
410
411 // Store based on target endian
412 for (uint64_t i = 0; i < Size; ++i) {
413 Vals[Offset + i] = DL.isLittleEndian()
414 ? ((val >> (i * 8)) & 0xFF)
415 : ((val >> ((Size - i - 1) * 8)) & 0xFF);
416 }
417 return true;
418 }
419
420 if (const ConstantDataArray *CDA = dyn_cast<ConstantDataArray>(Val: CV))
421 return fillConstantDataArray(DL, CDA, Vals, Offset);
422
423 if (const ConstantArray *CA = dyn_cast<ConstantArray>(Val: CV))
424 return fillConstantArray(DL, CA, Vals, Offset);
425
426 if (const ConstantStruct *CVS = dyn_cast<ConstantStruct>(Val: CV))
427 return fillConstantStruct(DL, CS: CVS, Vals, Offset);
428
429 return false;
430}
431
432bool BPFDAGToDAGISel::fillConstantDataArray(const DataLayout &DL,
433 const ConstantDataArray *CDA,
434 val_vec_type &Vals, int Offset) {
435 for (unsigned i = 0, e = CDA->getNumElements(); i != e; ++i) {
436 if (fillGenericConstant(DL, CV: CDA->getElementAsConstant(i), Vals, Offset) ==
437 false)
438 return false;
439 Offset += DL.getTypeAllocSize(Ty: CDA->getElementAsConstant(i)->getType());
440 }
441
442 return true;
443}
444
445bool BPFDAGToDAGISel::fillConstantArray(const DataLayout &DL,
446 const ConstantArray *CA,
447 val_vec_type &Vals, int Offset) {
448 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) {
449 if (fillGenericConstant(DL, CV: CA->getOperand(i_nocapture: i), Vals, Offset) == false)
450 return false;
451 Offset += DL.getTypeAllocSize(Ty: CA->getOperand(i_nocapture: i)->getType());
452 }
453
454 return true;
455}
456
457bool BPFDAGToDAGISel::fillConstantStruct(const DataLayout &DL,
458 const ConstantStruct *CS,
459 val_vec_type &Vals, int Offset) {
460 const StructLayout *Layout = DL.getStructLayout(Ty: CS->getType());
461 for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) {
462 const Constant *Field = CS->getOperand(i_nocapture: i);
463 uint64_t SizeSoFar = Layout->getElementOffset(Idx: i);
464 if (fillGenericConstant(DL, CV: Field, Vals, Offset: Offset + SizeSoFar) == false)
465 return false;
466 }
467 return true;
468}
469
470void BPFDAGToDAGISel::PreprocessTrunc(SDNode *Node,
471 SelectionDAG::allnodes_iterator &I) {
472 ConstantSDNode *MaskN = dyn_cast<ConstantSDNode>(Val: Node->getOperand(Num: 1));
473 if (!MaskN)
474 return;
475
476 // The Reg operand should be a virtual register, which is defined
477 // outside the current basic block. DAG combiner has done a pretty
478 // good job in removing truncating inside a single basic block except
479 // when the Reg operand comes from bpf_load_[byte | half | word] for
480 // which the generic optimizer doesn't understand their results are
481 // zero extended.
482 SDValue BaseV = Node->getOperand(Num: 0);
483 if (BaseV.getOpcode() != ISD::INTRINSIC_W_CHAIN)
484 return;
485
486 unsigned IntNo = BaseV->getConstantOperandVal(Num: 1);
487 uint64_t MaskV = MaskN->getZExtValue();
488
489 if (!((IntNo == Intrinsic::bpf_load_byte && MaskV == 0xFF) ||
490 (IntNo == Intrinsic::bpf_load_half && MaskV == 0xFFFF) ||
491 (IntNo == Intrinsic::bpf_load_word && MaskV == 0xFFFFFFFF)))
492 return;
493
494 LLVM_DEBUG(dbgs() << "Remove the redundant AND operation in: ";
495 Node->dump(); dbgs() << '\n');
496
497 I--;
498 CurDAG->ReplaceAllUsesWith(From: SDValue(Node, 0), To: BaseV);
499 I++;
500 CurDAG->DeleteNode(N: Node);
501}
502
503FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) {
504 return new BPFDAGToDAGISelLegacy(TM);
505}
506