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

source code of llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp