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