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