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 | |
34 | using namespace llvm; |
35 | |
36 | #define DEBUG_TYPE "bpf-isel" |
37 | #define PASS_NAME "BPF DAG->DAG Pattern Instruction Selection" |
38 | |
39 | // Instruction Selector Implementation |
40 | namespace { |
41 | |
42 | class 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 | |
48 | public: |
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 | |
68 | private: |
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 | |
99 | char BPFDAGToDAGISel::ID = 0; |
100 | |
101 | INITIALIZE_PASS(BPFDAGToDAGISel, DEBUG_TYPE, PASS_NAME, false, false) |
102 | |
103 | // ComplexPattern used on BPF Load/Store instructions |
104 | bool 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 |
138 | bool 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 | |
161 | bool 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 | |
182 | void 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 | |
234 | void 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 | |
312 | void 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 | |
332 | bool 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 | |
383 | bool 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 | |
420 | bool 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 | |
433 | bool 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 | |
445 | bool 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 | |
458 | void 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 | |
491 | FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) { |
492 | return new BPFDAGToDAGISel(TM); |
493 | } |
494 | |