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