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