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