blob: af9045ecf2a1095de92035696f4e77d140e50903 [file] [log] [blame]
Alexei Starovoitove4c8c802015-01-24 17:51:26 +00001//===-- BPFISelDAGToDAG.cpp - A dag to dag inst selector for BPF ----------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines a DAG pattern matching instruction selector for BPF,
11// converting from a legalized dag to a BPF dag.
12//
13//===----------------------------------------------------------------------===//
14
15#include "BPF.h"
16#include "BPFRegisterInfo.h"
17#include "BPFSubtarget.h"
18#include "BPFTargetMachine.h"
Yonghong Song5fbe01b2017-06-29 15:18:54 +000019#include "llvm/CodeGen/FunctionLoweringInfo.h"
Alexei Starovoitove4c8c802015-01-24 17:51:26 +000020#include "llvm/CodeGen/MachineConstantPool.h"
Alexei Starovoitove4c8c802015-01-24 17:51:26 +000021#include "llvm/CodeGen/MachineFrameInfo.h"
Benjamin Kramer799003b2015-03-23 19:32:43 +000022#include "llvm/CodeGen/MachineFunction.h"
Alexei Starovoitove4c8c802015-01-24 17:51:26 +000023#include "llvm/CodeGen/MachineInstrBuilder.h"
24#include "llvm/CodeGen/MachineRegisterInfo.h"
25#include "llvm/CodeGen/SelectionDAGISel.h"
Yonghong Songac2e2502017-06-16 15:41:16 +000026#include "llvm/IR/Constants.h"
Benjamin Kramer799003b2015-03-23 19:32:43 +000027#include "llvm/IR/IntrinsicInst.h"
Alexei Starovoitove4c8c802015-01-24 17:51:26 +000028#include "llvm/Support/Debug.h"
Yonghong Songac2e2502017-06-16 15:41:16 +000029#include "llvm/Support/Endian.h"
Alexei Starovoitove4c8c802015-01-24 17:51:26 +000030#include "llvm/Support/ErrorHandling.h"
31#include "llvm/Support/raw_ostream.h"
Benjamin Kramer799003b2015-03-23 19:32:43 +000032#include "llvm/Target/TargetMachine.h"
Yonghong Songac2e2502017-06-16 15:41:16 +000033
Alexei Starovoitove4c8c802015-01-24 17:51:26 +000034using namespace llvm;
35
36#define DEBUG_TYPE "bpf-isel"
37
38// Instruction Selector Implementation
39namespace {
40
41class BPFDAGToDAGISel : public SelectionDAGISel {
42public:
43 explicit BPFDAGToDAGISel(BPFTargetMachine &TM) : SelectionDAGISel(TM) {}
44
Mehdi Amini117296c2016-10-01 02:56:57 +000045 StringRef getPassName() const override {
Alexei Starovoitove4c8c802015-01-24 17:51:26 +000046 return "BPF DAG->DAG Pattern Instruction Selection";
47 }
48
Yonghong Songac2e2502017-06-16 15:41:16 +000049 void PreprocessISelDAG() override;
50
Yonghong Song9ef85f02017-09-18 23:29:36 +000051 bool SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintCode,
52 std::vector<SDValue> &OutOps) override;
53
54
Alexei Starovoitove4c8c802015-01-24 17:51:26 +000055private:
56// Include the pieces autogenerated from the target description.
57#include "BPFGenDAGISel.inc"
58
Justin Bognerf076e792016-05-12 21:14:47 +000059 void Select(SDNode *N) override;
Alexei Starovoitove4c8c802015-01-24 17:51:26 +000060
61 // Complex Pattern for address selection.
62 bool SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset);
Alexei Starovoitov4e01a382015-10-06 04:00:53 +000063 bool SelectFIAddr(SDValue Addr, SDValue &Base, SDValue &Offset);
Yonghong Songac2e2502017-06-16 15:41:16 +000064
Yonghong Song5fbe01b2017-06-29 15:18:54 +000065 // Node preprocessing cases
66 void PreprocessLoad(SDNode *Node, SelectionDAG::allnodes_iterator I);
67 void PreprocessCopyToReg(SDNode *Node);
68 void PreprocessTrunc(SDNode *Node, SelectionDAG::allnodes_iterator I);
69
Yonghong Songac2e2502017-06-16 15:41:16 +000070 // Find constants from a constant structure
71 typedef std::vector<unsigned char> val_vec_type;
72 bool fillGenericConstant(const DataLayout &DL, const Constant *CV,
73 val_vec_type &Vals, uint64_t Offset);
74 bool fillConstantDataArray(const DataLayout &DL, const ConstantDataArray *CDA,
75 val_vec_type &Vals, int Offset);
76 bool fillConstantArray(const DataLayout &DL, const ConstantArray *CA,
77 val_vec_type &Vals, int Offset);
78 bool fillConstantStruct(const DataLayout &DL, const ConstantStruct *CS,
79 val_vec_type &Vals, int Offset);
80 bool getConstantFieldValue(const GlobalAddressSDNode *Node, uint64_t Offset,
81 uint64_t Size, unsigned char *ByteSeq);
Yonghong Song5fbe01b2017-06-29 15:18:54 +000082 bool checkLoadDef(unsigned DefReg, unsigned match_load_op);
Yonghong Songac2e2502017-06-16 15:41:16 +000083
84 // Mapping from ConstantStruct global value to corresponding byte-list values
85 std::map<const void *, val_vec_type> cs_vals_;
Yonghong Song5fbe01b2017-06-29 15:18:54 +000086 // Mapping from vreg to load memory opcode
87 std::map<unsigned, unsigned> load_to_vreg_;
Yonghong Songee68d8e2017-10-24 18:21:10 +000088 // Current function
89 const Function *curr_func_;
Alexei Starovoitove4c8c802015-01-24 17:51:26 +000090};
Yonghong Songac2e2502017-06-16 15:41:16 +000091} // namespace
Alexei Starovoitove4c8c802015-01-24 17:51:26 +000092
93// ComplexPattern used on BPF Load/Store instructions
94bool BPFDAGToDAGISel::SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset) {
95 // if Address is FI, get the TargetFrameIndex.
Alexei Starovoitov659ece92015-04-28 20:38:56 +000096 SDLoc DL(Addr);
Alexei Starovoitove4c8c802015-01-24 17:51:26 +000097 if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
Yonghong Songac2e2502017-06-16 15:41:16 +000098 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
Alexei Starovoitov659ece92015-04-28 20:38:56 +000099 Offset = CurDAG->getTargetConstant(0, DL, MVT::i64);
Alexei Starovoitove4c8c802015-01-24 17:51:26 +0000100 return true;
101 }
102
103 if (Addr.getOpcode() == ISD::TargetExternalSymbol ||
104 Addr.getOpcode() == ISD::TargetGlobalAddress)
105 return false;
106
Alexei Starovoitov4e01a382015-10-06 04:00:53 +0000107 // Addresses of the form Addr+const or Addr|const
Alexei Starovoitove4c8c802015-01-24 17:51:26 +0000108 if (CurDAG->isBaseWithConstantOffset(Addr)) {
109 ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1));
Alexei Starovoitov56db1452017-04-13 22:24:13 +0000110 if (isInt<16>(CN->getSExtValue())) {
Alexei Starovoitove4c8c802015-01-24 17:51:26 +0000111
112 // If the first operand is a FI, get the TargetFI Node
113 if (FrameIndexSDNode *FIN =
114 dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))
115 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
116 else
117 Base = Addr.getOperand(0);
118
Alexei Starovoitov659ece92015-04-28 20:38:56 +0000119 Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);
Alexei Starovoitove4c8c802015-01-24 17:51:26 +0000120 return true;
121 }
122 }
123
Yonghong Songac2e2502017-06-16 15:41:16 +0000124 Base = Addr;
Alexei Starovoitov659ece92015-04-28 20:38:56 +0000125 Offset = CurDAG->getTargetConstant(0, DL, MVT::i64);
Alexei Starovoitove4c8c802015-01-24 17:51:26 +0000126 return true;
127}
128
Alexei Starovoitov4e01a382015-10-06 04:00:53 +0000129// ComplexPattern used on BPF FI instruction
Yonghong Songac2e2502017-06-16 15:41:16 +0000130bool BPFDAGToDAGISel::SelectFIAddr(SDValue Addr, SDValue &Base,
131 SDValue &Offset) {
Alexei Starovoitov4e01a382015-10-06 04:00:53 +0000132 SDLoc DL(Addr);
133
134 if (!CurDAG->isBaseWithConstantOffset(Addr))
135 return false;
136
137 // Addresses of the form Addr+const or Addr|const
138 ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1));
Alexei Starovoitov56db1452017-04-13 22:24:13 +0000139 if (isInt<16>(CN->getSExtValue())) {
Alexei Starovoitov4e01a382015-10-06 04:00:53 +0000140
141 // If the first operand is a FI, get the TargetFI Node
Yonghong Songac2e2502017-06-16 15:41:16 +0000142 if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))
Alexei Starovoitov4e01a382015-10-06 04:00:53 +0000143 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
144 else
145 return false;
146
147 Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);
148 return true;
149 }
150
151 return false;
152}
153
Yonghong Song9ef85f02017-09-18 23:29:36 +0000154bool BPFDAGToDAGISel::SelectInlineAsmMemoryOperand(
155 const SDValue &Op, unsigned ConstraintCode, std::vector<SDValue> &OutOps) {
156 SDValue Op0, Op1;
157 switch (ConstraintCode) {
158 default:
159 return true;
160 case InlineAsm::Constraint_m: // memory
161 if (!SelectAddr(Op, Op0, Op1))
162 return true;
163 break;
164 }
165
166 SDLoc DL(Op);
167 SDValue AluOp = CurDAG->getTargetConstant(ISD::ADD, DL, MVT::i32);;
168 OutOps.push_back(Op0);
169 OutOps.push_back(Op1);
170 OutOps.push_back(AluOp);
171 return false;
172}
173
Justin Bognerf076e792016-05-12 21:14:47 +0000174void BPFDAGToDAGISel::Select(SDNode *Node) {
Alexei Starovoitove4c8c802015-01-24 17:51:26 +0000175 unsigned Opcode = Node->getOpcode();
176
177 // Dump information about the Node being selected
178 DEBUG(dbgs() << "Selecting: "; Node->dump(CurDAG); dbgs() << '\n');
179
180 // If we have a custom node, we already have selected!
181 if (Node->isMachineOpcode()) {
182 DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << '\n');
Justin Bognerf076e792016-05-12 21:14:47 +0000183 return;
Alexei Starovoitove4c8c802015-01-24 17:51:26 +0000184 }
185
186 // tablegen selection should be handled here.
187 switch (Opcode) {
Yonghong Songac2e2502017-06-16 15:41:16 +0000188 default:
189 break;
Alexei Starovoitov7e453bb2016-03-18 22:02:47 +0000190 case ISD::SDIV: {
191 DebugLoc Empty;
192 const DebugLoc &DL = Node->getDebugLoc();
193 if (DL != Empty)
194 errs() << "Error at line " << DL.getLine() << ": ";
195 else
196 errs() << "Error: ";
197 errs() << "Unsupport signed division for DAG: ";
Matthias Braun8c209aa2017-01-28 02:02:38 +0000198 Node->print(errs(), CurDAG);
Alexei Starovoitov7e453bb2016-03-18 22:02:47 +0000199 errs() << "Please convert to unsigned div/mod.\n";
200 break;
201 }
Alexei Starovoitove4c8c802015-01-24 17:51:26 +0000202 case ISD::INTRINSIC_W_CHAIN: {
203 unsigned IntNo = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue();
204 switch (IntNo) {
205 case Intrinsic::bpf_load_byte:
206 case Intrinsic::bpf_load_half:
207 case Intrinsic::bpf_load_word: {
208 SDLoc DL(Node);
209 SDValue Chain = Node->getOperand(0);
210 SDValue N1 = Node->getOperand(1);
211 SDValue Skb = Node->getOperand(2);
212 SDValue N3 = Node->getOperand(3);
213
214 SDValue R6Reg = CurDAG->getRegister(BPF::R6, MVT::i64);
215 Chain = CurDAG->getCopyToReg(Chain, DL, R6Reg, Skb, SDValue());
216 Node = CurDAG->UpdateNodeOperands(Node, Chain, N1, R6Reg, N3);
217 break;
218 }
219 }
220 break;
221 }
222
223 case ISD::FrameIndex: {
Benjamin Kramer619c4e52015-04-10 11:24:51 +0000224 int FI = cast<FrameIndexSDNode>(Node)->getIndex();
Alexei Starovoitove4c8c802015-01-24 17:51:26 +0000225 EVT VT = Node->getValueType(0);
226 SDValue TFI = CurDAG->getTargetFrameIndex(FI, VT);
227 unsigned Opc = BPF::MOV_rr;
Justin Bognerf076e792016-05-12 21:14:47 +0000228 if (Node->hasOneUse()) {
229 CurDAG->SelectNodeTo(Node, Opc, VT, TFI);
230 return;
231 }
232 ReplaceNode(Node, CurDAG->getMachineNode(Opc, SDLoc(Node), VT, TFI));
233 return;
Alexei Starovoitove4c8c802015-01-24 17:51:26 +0000234 }
235 }
236
237 // Select the default instruction
Justin Bognerf076e792016-05-12 21:14:47 +0000238 SelectCode(Node);
Alexei Starovoitove4c8c802015-01-24 17:51:26 +0000239}
240
Yonghong Song5fbe01b2017-06-29 15:18:54 +0000241void BPFDAGToDAGISel::PreprocessLoad(SDNode *Node,
242 SelectionDAG::allnodes_iterator I) {
243 union {
244 uint8_t c[8];
245 uint16_t s;
246 uint32_t i;
247 uint64_t d;
248 } new_val; // hold up the constant values replacing loads.
249 bool to_replace = false;
250 SDLoc DL(Node);
251 const LoadSDNode *LD = cast<LoadSDNode>(Node);
252 uint64_t size = LD->getMemOperand()->getSize();
253
254 if (!size || size > 8 || (size & (size - 1)))
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 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 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 DEBUG(dbgs() << "Replacing load of size " << size << " with constant " << val
303 << '\n');
304 SDValue NVal = CurDAG->getConstant(val, DL, MVT::i64);
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
Yonghong Songac2e2502017-06-16 15:41:16 +0000317void BPFDAGToDAGISel::PreprocessISelDAG() {
Yonghong Song5fbe01b2017-06-29 15:18:54 +0000318 // Iterate through all nodes, interested in the following cases:
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 // . reg truncating is often the result of 8/16/32bit->64bit or
325 // 8/16bit->32bit conversion. If the reg value is loaded with
326 // masked byte width, the AND operation can be removed since
327 // BPF LOAD already has zero extension.
328 //
329 // This also solved a correctness issue.
330 // In BPF socket-related program, e.g., __sk_buff->{data, data_end}
331 // are 32-bit registers, but later on, kernel verifier will rewrite
332 // it with 64-bit value. Therefore, truncating the value after the
333 // load will result in incorrect code.
Yonghong Song0f836d52017-10-24 17:29:03 +0000334
335 // clear the load_to_vreg_ map so that we have a clean start
336 // for this function.
Yonghong Songee68d8e2017-10-24 18:21:10 +0000337 if (!curr_func_) {
338 curr_func_ = FuncInfo->Fn;
339 } else if (curr_func_ != FuncInfo->Fn) {
340 load_to_vreg_.clear();
341 curr_func_ = FuncInfo->Fn;
342 }
Yonghong Song0f836d52017-10-24 17:29:03 +0000343
Yonghong Songac2e2502017-06-16 15:41:16 +0000344 for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
345 E = CurDAG->allnodes_end();
346 I != E;) {
347 SDNode *Node = &*I++;
348 unsigned Opcode = Node->getOpcode();
Yonghong Song5fbe01b2017-06-29 15:18:54 +0000349 if (Opcode == ISD::LOAD)
350 PreprocessLoad(Node, I);
351 else if (Opcode == ISD::CopyToReg)
352 PreprocessCopyToReg(Node);
353 else if (Opcode == ISD::AND)
354 PreprocessTrunc(Node, I);
Yonghong Songac2e2502017-06-16 15:41:16 +0000355 }
356}
357
358bool BPFDAGToDAGISel::getConstantFieldValue(const GlobalAddressSDNode *Node,
359 uint64_t Offset, uint64_t Size,
360 unsigned char *ByteSeq) {
361 const GlobalVariable *V = dyn_cast<GlobalVariable>(Node->getGlobal());
362
363 if (!V || !V->hasInitializer())
364 return false;
365
366 const Constant *Init = V->getInitializer();
367 const DataLayout &DL = CurDAG->getDataLayout();
368 val_vec_type TmpVal;
369
370 auto it = cs_vals_.find(static_cast<const void *>(Init));
371 if (it != cs_vals_.end()) {
372 TmpVal = it->second;
373 } else {
374 uint64_t total_size = 0;
375 if (const ConstantStruct *CS = dyn_cast<ConstantStruct>(Init))
376 total_size =
377 DL.getStructLayout(cast<StructType>(CS->getType()))->getSizeInBytes();
378 else if (const ConstantArray *CA = dyn_cast<ConstantArray>(Init))
379 total_size = DL.getTypeAllocSize(CA->getType()->getElementType()) *
380 CA->getNumOperands();
381 else
382 return false;
383
384 val_vec_type Vals(total_size, 0);
385 if (fillGenericConstant(DL, Init, Vals, 0) == false)
386 return false;
387 cs_vals_[static_cast<const void *>(Init)] = Vals;
388 TmpVal = std::move(Vals);
389 }
390
391 // test whether host endianness matches target
Yonghong Songa63178f2017-06-16 23:28:04 +0000392 union {
393 uint8_t c[2];
394 uint16_t s;
395 } test_buf;
Yonghong Songac2e2502017-06-16 15:41:16 +0000396 uint16_t test_val = 0x2345;
397 if (DL.isLittleEndian())
Yonghong Songa63178f2017-06-16 23:28:04 +0000398 support::endian::write16le(test_buf.c, test_val);
Yonghong Songac2e2502017-06-16 15:41:16 +0000399 else
Yonghong Songa63178f2017-06-16 23:28:04 +0000400 support::endian::write16be(test_buf.c, test_val);
Yonghong Songac2e2502017-06-16 15:41:16 +0000401
Yonghong Songa63178f2017-06-16 23:28:04 +0000402 bool endian_match = test_buf.s == test_val;
Yonghong Songac2e2502017-06-16 15:41:16 +0000403 for (uint64_t i = Offset, j = 0; i < Offset + Size; i++, j++)
404 ByteSeq[j] = endian_match ? TmpVal[i] : TmpVal[Offset + Size - 1 - j];
405
406 return true;
407}
408
409bool BPFDAGToDAGISel::fillGenericConstant(const DataLayout &DL,
410 const Constant *CV,
411 val_vec_type &Vals, uint64_t Offset) {
412 uint64_t Size = DL.getTypeAllocSize(CV->getType());
413
414 if (isa<ConstantAggregateZero>(CV) || isa<UndefValue>(CV))
415 return true; // already done
416
417 if (const ConstantInt *CI = dyn_cast<ConstantInt>(CV)) {
418 uint64_t val = CI->getZExtValue();
419 DEBUG(dbgs() << "Byte array at offset " << Offset << " with value " << val
420 << '\n');
421
422 if (Size > 8 || (Size & (Size - 1)))
423 return false;
424
425 // Store based on target endian
426 for (uint64_t i = 0; i < Size; ++i) {
427 Vals[Offset + i] = DL.isLittleEndian()
428 ? ((val >> (i * 8)) & 0xFF)
429 : ((val >> ((Size - i - 1) * 8)) & 0xFF);
430 }
431 return true;
432 }
433
434 if (const ConstantDataArray *CDA = dyn_cast<ConstantDataArray>(CV))
435 return fillConstantDataArray(DL, CDA, Vals, Offset);
436
437 if (const ConstantArray *CA = dyn_cast<ConstantArray>(CV))
438 return fillConstantArray(DL, CA, Vals, Offset);
439
440 if (const ConstantStruct *CVS = dyn_cast<ConstantStruct>(CV))
441 return fillConstantStruct(DL, CVS, Vals, Offset);
442
443 return false;
444}
445
446bool BPFDAGToDAGISel::fillConstantDataArray(const DataLayout &DL,
447 const ConstantDataArray *CDA,
448 val_vec_type &Vals, int Offset) {
449 for (unsigned i = 0, e = CDA->getNumElements(); i != e; ++i) {
450 if (fillGenericConstant(DL, CDA->getElementAsConstant(i), Vals, Offset) ==
451 false)
452 return false;
453 Offset += DL.getTypeAllocSize(CDA->getElementAsConstant(i)->getType());
454 }
455
456 return true;
457}
458
459bool BPFDAGToDAGISel::fillConstantArray(const DataLayout &DL,
460 const ConstantArray *CA,
461 val_vec_type &Vals, int Offset) {
462 for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) {
463 if (fillGenericConstant(DL, CA->getOperand(i), Vals, Offset) == false)
464 return false;
465 Offset += DL.getTypeAllocSize(CA->getOperand(i)->getType());
466 }
467
468 return true;
469}
470
471bool BPFDAGToDAGISel::fillConstantStruct(const DataLayout &DL,
472 const ConstantStruct *CS,
473 val_vec_type &Vals, int Offset) {
474 const StructLayout *Layout = DL.getStructLayout(CS->getType());
475 for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) {
476 const Constant *Field = CS->getOperand(i);
477 uint64_t SizeSoFar = Layout->getElementOffset(i);
478 if (fillGenericConstant(DL, Field, Vals, Offset + SizeSoFar) == false)
479 return false;
480 }
481 return true;
482}
483
Yonghong Song5fbe01b2017-06-29 15:18:54 +0000484void BPFDAGToDAGISel::PreprocessCopyToReg(SDNode *Node) {
485 const RegisterSDNode *RegN = dyn_cast<RegisterSDNode>(Node->getOperand(1));
486 if (!RegN || !TargetRegisterInfo::isVirtualRegister(RegN->getReg()))
487 return;
488
489 const LoadSDNode *LD = dyn_cast<LoadSDNode>(Node->getOperand(2));
490 if (!LD)
491 return;
492
493 // Assign a load value to a virtual register. record its load width
494 unsigned mem_load_op = 0;
495 switch (LD->getMemOperand()->getSize()) {
496 default:
497 return;
498 case 4:
499 mem_load_op = BPF::LDW;
500 break;
501 case 2:
502 mem_load_op = BPF::LDH;
503 break;
504 case 1:
505 mem_load_op = BPF::LDB;
506 break;
507 }
508
509 DEBUG(dbgs() << "Find Load Value to VReg "
510 << TargetRegisterInfo::virtReg2Index(RegN->getReg()) << '\n');
511 load_to_vreg_[RegN->getReg()] = mem_load_op;
512}
513
514void BPFDAGToDAGISel::PreprocessTrunc(SDNode *Node,
515 SelectionDAG::allnodes_iterator I) {
516 ConstantSDNode *MaskN = dyn_cast<ConstantSDNode>(Node->getOperand(1));
517 if (!MaskN)
518 return;
519
520 unsigned match_load_op = 0;
521 switch (MaskN->getZExtValue()) {
522 default:
523 return;
524 case 0xFFFFFFFF:
525 match_load_op = BPF::LDW;
526 break;
527 case 0xFFFF:
528 match_load_op = BPF::LDH;
529 break;
530 case 0xFF:
531 match_load_op = BPF::LDB;
532 break;
533 }
534
535 // The Reg operand should be a virtual register, which is defined
536 // outside the current basic block. DAG combiner has done a pretty
537 // good job in removing truncating inside a single basic block.
538 SDValue BaseV = Node->getOperand(0);
539 if (BaseV.getOpcode() != ISD::CopyFromReg)
540 return;
541
542 const RegisterSDNode *RegN =
543 dyn_cast<RegisterSDNode>(BaseV.getNode()->getOperand(1));
544 if (!RegN || !TargetRegisterInfo::isVirtualRegister(RegN->getReg()))
545 return;
546 unsigned AndOpReg = RegN->getReg();
547 DEBUG(dbgs() << "Examine %vreg" << TargetRegisterInfo::virtReg2Index(AndOpReg)
548 << '\n');
549
550 // Examine the PHI insns in the MachineBasicBlock to found out the
551 // definitions of this virtual register. At this stage (DAG2DAG
552 // transformation), only PHI machine insns are available in the machine basic
553 // block.
554 MachineBasicBlock *MBB = FuncInfo->MBB;
555 MachineInstr *MII = nullptr;
556 for (auto &MI : *MBB) {
557 for (unsigned i = 0; i < MI.getNumOperands(); ++i) {
558 const MachineOperand &MOP = MI.getOperand(i);
559 if (!MOP.isReg() || !MOP.isDef())
560 continue;
561 unsigned Reg = MOP.getReg();
562 if (TargetRegisterInfo::isVirtualRegister(Reg) && Reg == AndOpReg) {
563 MII = &MI;
564 break;
565 }
566 }
567 }
568
569 if (MII == nullptr) {
570 // No phi definition in this block.
571 if (!checkLoadDef(AndOpReg, match_load_op))
572 return;
573 } else {
574 // The PHI node looks like:
575 // %vreg2<def> = PHI %vreg0, <BB#1>, %vreg1, <BB#3>
576 // Trace each incoming definition, e.g., (%vreg0, BB#1) and (%vreg1, BB#3)
577 // The AND operation can be removed if both %vreg0 in BB#1 and %vreg1 in
578 // BB#3 are defined with with a load matching the MaskN.
579 DEBUG(dbgs() << "Check PHI Insn: "; MII->dump(); dbgs() << '\n');
580 unsigned PrevReg = -1;
581 for (unsigned i = 0; i < MII->getNumOperands(); ++i) {
582 const MachineOperand &MOP = MII->getOperand(i);
583 if (MOP.isReg()) {
584 if (MOP.isDef())
585 continue;
586 PrevReg = MOP.getReg();
587 if (!TargetRegisterInfo::isVirtualRegister(PrevReg))
588 return;
589 if (!checkLoadDef(PrevReg, match_load_op))
590 return;
591 }
592 }
593 }
594
595 DEBUG(dbgs() << "Remove the redundant AND operation in: "; Node->dump();
596 dbgs() << '\n');
597
598 I--;
599 CurDAG->ReplaceAllUsesWith(SDValue(Node, 0), BaseV);
600 I++;
601 CurDAG->DeleteNode(Node);
602}
603
604bool BPFDAGToDAGISel::checkLoadDef(unsigned DefReg, unsigned match_load_op) {
605 auto it = load_to_vreg_.find(DefReg);
606 if (it == load_to_vreg_.end())
607 return false; // The definition of register is not exported yet.
608
609 return it->second == match_load_op;
610}
611
Alexei Starovoitove4c8c802015-01-24 17:51:26 +0000612FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) {
613 return new BPFDAGToDAGISel(TM);
614}