Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp
Line
Count
Source (jump to first uncovered line)
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/Support/Debug.h"
28
#include "llvm/Support/Endian.h"
29
#include "llvm/Support/ErrorHandling.h"
30
#include "llvm/Support/raw_ostream.h"
31
#include "llvm/Target/TargetMachine.h"
32
33
using namespace llvm;
34
35
#define DEBUG_TYPE "bpf-isel"
36
37
// Instruction Selector Implementation
38
namespace {
39
40
class BPFDAGToDAGISel : public SelectionDAGISel {
41
42
  /// Subtarget - Keep a pointer to the BPFSubtarget around so that we can
43
  /// make the right decision when generating code for different subtargets.
44
  const BPFSubtarget *Subtarget;
45
46
public:
47
  explicit BPFDAGToDAGISel(BPFTargetMachine &TM)
48
206
      : SelectionDAGISel(TM), Subtarget(nullptr) {
49
206
    curr_func_ = nullptr;
50
206
  }
51
52
285
  StringRef getPassName() const override {
53
285
    return "BPF DAG->DAG Pattern Instruction Selection";
54
285
  }
55
56
285
  bool runOnMachineFunction(MachineFunction &MF) override {
57
285
    // Reset the subtarget each time through.
58
285
    Subtarget = &MF.getSubtarget<BPFSubtarget>();
59
285
    return SelectionDAGISel::runOnMachineFunction(MF);
60
285
  }
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
  bool checkLoadDef(unsigned DefReg, unsigned match_load_op);
96
97
  // Mapping from ConstantStruct global value to corresponding byte-list values
98
  std::map<const void *, val_vec_type> cs_vals_;
99
  // Mapping from vreg to load memory opcode
100
  std::map<unsigned, unsigned> load_to_vreg_;
101
  // Current function
102
  const Function *curr_func_;
103
};
104
} // namespace
105
106
// ComplexPattern used on BPF Load/Store instructions
107
303
bool BPFDAGToDAGISel::SelectAddr(SDValue Addr, SDValue &Base, SDValue &Offset) {
108
303
  // if Address is FI, get the TargetFrameIndex.
109
303
  SDLoc DL(Addr);
110
303
  if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
111
36
    Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
112
36
    Offset = CurDAG->getTargetConstant(0, DL, MVT::i64);
113
36
    return true;
114
36
  }
115
267
116
267
  if (Addr.getOpcode() == ISD::TargetExternalSymbol ||
117
267
      Addr.getOpcode() == ISD::TargetGlobalAddress)
118
0
    return false;
119
267
120
267
  // Addresses of the form Addr+const or Addr|const
121
267
  if (CurDAG->isBaseWithConstantOffset(Addr)) {
122
90
    ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1));
123
90
    if (isInt<16>(CN->getSExtValue())) {
124
88
125
88
      // If the first operand is a FI, get the TargetFI Node
126
88
      if (FrameIndexSDNode *FIN =
127
47
              dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))
128
47
        Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
129
41
      else
130
41
        Base = Addr.getOperand(0);
131
88
132
88
      Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);
133
88
      return true;
134
88
    }
135
179
  }
136
179
137
179
  Base = Addr;
138
179
  Offset = CurDAG->getTargetConstant(0, DL, MVT::i64);
139
179
  return true;
140
179
}
141
142
// ComplexPattern used on BPF FI instruction
143
bool BPFDAGToDAGISel::SelectFIAddr(SDValue Addr, SDValue &Base,
144
140
                                   SDValue &Offset) {
145
140
  SDLoc DL(Addr);
146
140
147
140
  if (!CurDAG->isBaseWithConstantOffset(Addr))
148
88
    return false;
149
52
150
52
  // Addresses of the form Addr+const or Addr|const
151
52
  ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1));
152
52
  if (isInt<16>(CN->getSExtValue())) {
153
50
154
50
    // If the first operand is a FI, get the TargetFI Node
155
50
    if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr.getOperand(0)))
156
1
      Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i64);
157
49
    else
158
49
      return false;
159
1
160
1
    Offset = CurDAG->getTargetConstant(CN->getSExtValue(), DL, MVT::i64);
161
1
    return true;
162
1
  }
163
2
164
2
  return false;
165
2
}
166
167
bool BPFDAGToDAGISel::SelectInlineAsmMemoryOperand(
168
4
    const SDValue &Op, unsigned ConstraintCode, std::vector<SDValue> &OutOps) {
169
4
  SDValue Op0, Op1;
170
4
  switch (ConstraintCode) {
171
4
  default:
172
0
    return true;
173
4
  case InlineAsm::Constraint_m: // memory
174
4
    if (!SelectAddr(Op, Op0, Op1))
175
0
      return true;
176
4
    break;
177
4
  }
178
4
179
4
  SDLoc DL(Op);
180
4
  SDValue AluOp = CurDAG->getTargetConstant(ISD::ADD, DL, MVT::i32);;
181
4
  OutOps.push_back(Op0);
182
4
  OutOps.push_back(Op1);
183
4
  OutOps.push_back(AluOp);
184
4
  return false;
185
4
}
186
187
4.97k
void BPFDAGToDAGISel::Select(SDNode *Node) {
188
4.97k
  unsigned Opcode = Node->getOpcode();
189
4.97k
190
4.97k
  // If we have a custom node, we already have selected!
191
4.97k
  if (Node->isMachineOpcode()) {
192
0
    LLVM_DEBUG(dbgs() << "== "; Node->dump(CurDAG); dbgs() << '\n');
193
0
    return;
194
0
  }
195
4.97k
196
4.97k
  // tablegen selection should be handled here.
197
4.97k
  switch (Opcode) {
198
4.97k
  default:
199
4.88k
    break;
200
4.97k
  case ISD::SDIV: {
201
1
    DebugLoc Empty;
202
1
    const DebugLoc &DL = Node->getDebugLoc();
203
1
    if (DL != Empty)
204
0
      errs() << "Error at line " << DL.getLine() << ": ";
205
1
    else
206
1
      errs() << "Error: ";
207
1
    errs() << "Unsupport signed division for DAG: ";
208
1
    Node->print(errs(), CurDAG);
209
1
    errs() << "Please convert to unsigned div/mod.\n";
210
1
    break;
211
4.97k
  }
212
4.97k
  case ISD::INTRINSIC_W_CHAIN: {
213
66
    unsigned IntNo = cast<ConstantSDNode>(Node->getOperand(1))->getZExtValue();
214
66
    switch (IntNo) {
215
66
    case Intrinsic::bpf_load_byte:
216
62
    case Intrinsic::bpf_load_half:
217
62
    case Intrinsic::bpf_load_word: {
218
62
      SDLoc DL(Node);
219
62
      SDValue Chain = Node->getOperand(0);
220
62
      SDValue N1 = Node->getOperand(1);
221
62
      SDValue Skb = Node->getOperand(2);
222
62
      SDValue N3 = Node->getOperand(3);
223
62
224
62
      SDValue R6Reg = CurDAG->getRegister(BPF::R6, MVT::i64);
225
62
      Chain = CurDAG->getCopyToReg(Chain, DL, R6Reg, Skb, SDValue());
226
62
      Node = CurDAG->UpdateNodeOperands(Node, Chain, N1, R6Reg, N3);
227
62
      break;
228
66
    }
229
66
    }
230
66
    break;
231
66
  }
232
66
233
66
  case ISD::FrameIndex: {
234
24
    int FI = cast<FrameIndexSDNode>(Node)->getIndex();
235
24
    EVT VT = Node->getValueType(0);
236
24
    SDValue TFI = CurDAG->getTargetFrameIndex(FI, VT);
237
24
    unsigned Opc = BPF::MOV_rr;
238
24
    if (Node->hasOneUse()) {
239
24
      CurDAG->SelectNodeTo(Node, Opc, VT, TFI);
240
24
      return;
241
24
    }
242
0
    ReplaceNode(Node, CurDAG->getMachineNode(Opc, SDLoc(Node), VT, TFI));
243
0
    return;
244
0
  }
245
4.95k
  }
246
4.95k
247
4.95k
  // Select the default instruction
248
4.95k
  SelectCode(Node);
249
4.95k
}
250
251
void BPFDAGToDAGISel::PreprocessLoad(SDNode *Node,
252
181
                                     SelectionDAG::allnodes_iterator &I) {
253
181
  union {
254
181
    uint8_t c[8];
255
181
    uint16_t s;
256
181
    uint32_t i;
257
181
    uint64_t d;
258
181
  } new_val; // hold up the constant values replacing loads.
259
181
  bool to_replace = false;
260
181
  SDLoc DL(Node);
261
181
  const LoadSDNode *LD = cast<LoadSDNode>(Node);
262
181
  uint64_t size = LD->getMemOperand()->getSize();
263
181
264
181
  if (!size || size > 8 || (size & (size - 1)))
265
0
    return;
266
181
267
181
  SDNode *LDAddrNode = LD->getOperand(1).getNode();
268
181
  // Match LDAddr against either global_addr or (global_addr + offset)
269
181
  unsigned opcode = LDAddrNode->getOpcode();
270
181
  if (opcode == ISD::ADD) {
271
46
    SDValue OP1 = LDAddrNode->getOperand(0);
272
46
    SDValue OP2 = LDAddrNode->getOperand(1);
273
46
274
46
    // We want to find the pattern global_addr + offset
275
46
    SDNode *OP1N = OP1.getNode();
276
46
    if (OP1N->getOpcode() <= ISD::BUILTIN_OP_END || 
OP1N->getNumOperands() == 036
)
277
10
      return;
278
36
279
36
    LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');
280
36
281
36
    const GlobalAddressSDNode *GADN =
282
36
        dyn_cast<GlobalAddressSDNode>(OP1N->getOperand(0).getNode());
283
36
    const ConstantSDNode *CDN = dyn_cast<ConstantSDNode>(OP2.getNode());
284
36
    if (GADN && CDN)
285
36
      to_replace =
286
36
          getConstantFieldValue(GADN, CDN->getZExtValue(), size, new_val.c);
287
135
  } else if (LDAddrNode->getOpcode() > ISD::BUILTIN_OP_END &&
288
135
             
LDAddrNode->getNumOperands() > 089
) {
289
89
    LLVM_DEBUG(dbgs() << "Check candidate load: "; LD->dump(); dbgs() << '\n');
290
89
291
89
    SDValue OP1 = LDAddrNode->getOperand(0);
292
89
    if (const GlobalAddressSDNode *GADN =
293
89
            dyn_cast<GlobalAddressSDNode>(OP1.getNode()))
294
89
      to_replace = getConstantFieldValue(GADN, 0, size, new_val.c);
295
89
  }
296
181
297
181
  
if (171
!to_replace171
)
298
127
    return;
299
44
300
44
  // replacing the old with a new value
301
44
  uint64_t val;
302
44
  if (size == 1)
303
6
    val = new_val.c[0];
304
38
  else if (size == 2)
305
6
    val = new_val.s;
306
32
  else if (size == 4)
307
32
    val = new_val.i;
308
0
  else {
309
0
    val = new_val.d;
310
0
  }
311
44
312
44
  LLVM_DEBUG(dbgs() << "Replacing load of size " << size << " with constant "
313
44
                    << val << '\n');
314
44
  SDValue NVal = CurDAG->getConstant(val, DL, MVT::i64);
315
44
316
44
  // After replacement, the current node is dead, we need to
317
44
  // go backward one step to make iterator still work
318
44
  I--;
319
44
  SDValue From[] = {SDValue(Node, 0), SDValue(Node, 1)};
320
44
  SDValue To[] = {NVal, NVal};
321
44
  CurDAG->ReplaceAllUsesOfValuesWith(From, To, 2);
322
44
  I++;
323
44
  // It is safe to delete node now
324
44
  CurDAG->DeleteNode(Node);
325
44
}
326
327
392
void BPFDAGToDAGISel::PreprocessISelDAG() {
328
392
  // Iterate through all nodes, interested in the following cases:
329
392
  //
330
392
  //  . loads from ConstantStruct or ConstantArray of constructs
331
392
  //    which can be turns into constant itself, with this we can
332
392
  //    avoid reading from read-only section at runtime.
333
392
  //
334
392
  //  . reg truncating is often the result of 8/16/32bit->64bit or
335
392
  //    8/16bit->32bit conversion. If the reg value is loaded with
336
392
  //    masked byte width, the AND operation can be removed since
337
392
  //    BPF LOAD already has zero extension.
338
392
  //
339
392
  //    This also solved a correctness issue.
340
392
  //    In BPF socket-related program, e.g., __sk_buff->{data, data_end}
341
392
  //    are 32-bit registers, but later on, kernel verifier will rewrite
342
392
  //    it with 64-bit value. Therefore, truncating the value after the
343
392
  //    load will result in incorrect code.
344
392
345
392
  // clear the load_to_vreg_ map so that we have a clean start
346
392
  // for this function.
347
392
  if (!curr_func_) {
348
136
    curr_func_ = FuncInfo->Fn;
349
256
  } else if (curr_func_ != FuncInfo->Fn) {
350
149
    load_to_vreg_.clear();
351
149
    curr_func_ = FuncInfo->Fn;
352
149
  }
353
392
354
392
  for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
355
392
                                       E = CurDAG->allnodes_end();
356
6.25k
       I != E;) {
357
5.86k
    SDNode *Node = &*I++;
358
5.86k
    unsigned Opcode = Node->getOpcode();
359
5.86k
    if (Opcode == ISD::LOAD)
360
181
      PreprocessLoad(Node, I);
361
5.68k
    else if (Opcode == ISD::CopyToReg)
362
494
      PreprocessCopyToReg(Node);
363
5.18k
    else if (Opcode == ISD::AND)
364
78
      PreprocessTrunc(Node, I);
365
5.86k
  }
366
392
}
367
368
bool BPFDAGToDAGISel::getConstantFieldValue(const GlobalAddressSDNode *Node,
369
                                            uint64_t Offset, uint64_t Size,
370
125
                                            unsigned char *ByteSeq) {
371
125
  const GlobalVariable *V = dyn_cast<GlobalVariable>(Node->getGlobal());
372
125
373
125
  if (!V || !V->hasInitializer())
374
23
    return false;
375
102
376
102
  const Constant *Init = V->getInitializer();
377
102
  const DataLayout &DL = CurDAG->getDataLayout();
378
102
  val_vec_type TmpVal;
379
102
380
102
  auto it = cs_vals_.find(static_cast<const void *>(Init));
381
102
  if (it != cs_vals_.end()) {
382
33
    TmpVal = it->second;
383
69
  } else {
384
69
    uint64_t total_size = 0;
385
69
    if (const ConstantStruct *CS = dyn_cast<ConstantStruct>(Init))
386
9
      total_size =
387
9
          DL.getStructLayout(cast<StructType>(CS->getType()))->getSizeInBytes();
388
60
    else if (const ConstantArray *CA = dyn_cast<ConstantArray>(Init))
389
2
      total_size = DL.getTypeAllocSize(CA->getType()->getElementType()) *
390
2
                   CA->getNumOperands();
391
58
    else
392
58
      return false;
393
11
394
11
    val_vec_type Vals(total_size, 0);
395
11
    if (fillGenericConstant(DL, Init, Vals, 0) == false)
396
0
      return false;
397
11
    cs_vals_[static_cast<const void *>(Init)] = Vals;
398
11
    TmpVal = std::move(Vals);
399
11
  }
400
102
401
102
  // test whether host endianness matches target
402
102
  union {
403
44
    uint8_t c[2];
404
44
    uint16_t s;
405
44
  } test_buf;
406
44
  uint16_t test_val = 0x2345;
407
44
  if (DL.isLittleEndian())
408
24
    support::endian::write16le(test_buf.c, test_val);
409
20
  else
410
20
    support::endian::write16be(test_buf.c, test_val);
411
44
412
44
  bool endian_match = test_buf.s == test_val;
413
190
  for (uint64_t i = Offset, j = 0; i < Offset + Size; 
i++, j++146
)
414
146
    ByteSeq[j] = endian_match ? 
TmpVal[i]81
:
TmpVal[Offset + Size - 1 - j]65
;
415
44
416
44
  return true;
417
102
}
418
419
bool BPFDAGToDAGISel::fillGenericConstant(const DataLayout &DL,
420
                                          const Constant *CV,
421
111
                                          val_vec_type &Vals, uint64_t Offset) {
422
111
  uint64_t Size = DL.getTypeAllocSize(CV->getType());
423
111
424
111
  if (isa<ConstantAggregateZero>(CV) || 
isa<UndefValue>(CV)109
)
425
2
    return true; // already done
426
109
427
109
  if (const ConstantInt *CI = dyn_cast<ConstantInt>(CV)) {
428
82
    uint64_t val = CI->getZExtValue();
429
82
    LLVM_DEBUG(dbgs() << "Byte array at offset " << Offset << " with value "
430
82
                      << val << '\n');
431
82
432
82
    if (Size > 8 || (Size & (Size - 1)))
433
0
      return false;
434
82
435
82
    // Store based on target endian
436
252
    
for (uint64_t i = 0; 82
i < Size;
++i170
) {
437
170
      Vals[Offset + i] = DL.isLittleEndian()
438
170
                             ? 
((val >> (i * 8)) & 0xFF)90
439
170
                             : 
((val >> ((Size - i - 1) * 8)) & 0xFF)80
;
440
170
    }
441
82
    return true;
442
82
  }
443
27
444
27
  if (const ConstantDataArray *CDA = dyn_cast<ConstantDataArray>(CV))
445
4
    return fillConstantDataArray(DL, CDA, Vals, Offset);
446
23
447
23
  if (const ConstantArray *CA = dyn_cast<ConstantArray>(CV))
448
4
    return fillConstantArray(DL, CA, Vals, Offset);
449
19
450
19
  if (const ConstantStruct *CVS = dyn_cast<ConstantStruct>(CV))
451
19
    return fillConstantStruct(DL, CVS, Vals, Offset);
452
0
453
0
  return false;
454
0
}
455
456
bool BPFDAGToDAGISel::fillConstantDataArray(const DataLayout &DL,
457
                                            const ConstantDataArray *CDA,
458
4
                                            val_vec_type &Vals, int Offset) {
459
28
  for (unsigned i = 0, e = CDA->getNumElements(); i != e; 
++i24
) {
460
24
    if (fillGenericConstant(DL, CDA->getElementAsConstant(i), Vals, Offset) ==
461
24
        false)
462
0
      return false;
463
24
    Offset += DL.getTypeAllocSize(CDA->getElementAsConstant(i)->getType());
464
24
  }
465
4
466
4
  return true;
467
4
}
468
469
bool BPFDAGToDAGISel::fillConstantArray(const DataLayout &DL,
470
                                        const ConstantArray *CA,
471
4
                                        val_vec_type &Vals, int Offset) {
472
16
  for (unsigned i = 0, e = CA->getNumOperands(); i != e; 
++i12
) {
473
12
    if (fillGenericConstant(DL, CA->getOperand(i), Vals, Offset) == false)
474
0
      return false;
475
12
    Offset += DL.getTypeAllocSize(CA->getOperand(i)->getType());
476
12
  }
477
4
478
4
  return true;
479
4
}
480
481
bool BPFDAGToDAGISel::fillConstantStruct(const DataLayout &DL,
482
                                         const ConstantStruct *CS,
483
19
                                         val_vec_type &Vals, int Offset) {
484
19
  const StructLayout *Layout = DL.getStructLayout(CS->getType());
485
83
  for (unsigned i = 0, e = CS->getNumOperands(); i != e; 
++i64
) {
486
64
    const Constant *Field = CS->getOperand(i);
487
64
    uint64_t SizeSoFar = Layout->getElementOffset(i);
488
64
    if (fillGenericConstant(DL, Field, Vals, Offset + SizeSoFar) == false)
489
0
      return false;
490
64
  }
491
19
  return true;
492
19
}
493
494
494
void BPFDAGToDAGISel::PreprocessCopyToReg(SDNode *Node) {
495
494
  const RegisterSDNode *RegN = dyn_cast<RegisterSDNode>(Node->getOperand(1));
496
494
  if (!RegN || !TargetRegisterInfo::isVirtualRegister(RegN->getReg()))
497
361
    return;
498
133
499
133
  const LoadSDNode *LD = dyn_cast<LoadSDNode>(Node->getOperand(2));
500
133
  if (!LD)
501
124
    return;
502
9
503
9
  // Assign a load value to a virtual register. record its load width
504
9
  unsigned mem_load_op = 0;
505
9
  switch (LD->getMemOperand()->getSize()) {
506
9
  default:
507
2
    return;
508
9
  case 4:
509
6
    mem_load_op = BPF::LDW;
510
6
    break;
511
9
  case 2:
512
0
    mem_load_op = BPF::LDH;
513
0
    break;
514
9
  case 1:
515
1
    mem_load_op = BPF::LDB;
516
1
    break;
517
7
  }
518
7
519
7
  LLVM_DEBUG(dbgs() << "Find Load Value to VReg "
520
7
                    << TargetRegisterInfo::virtReg2Index(RegN->getReg())
521
7
                    << '\n');
522
7
  load_to_vreg_[RegN->getReg()] = mem_load_op;
523
7
}
524
525
void BPFDAGToDAGISel::PreprocessTrunc(SDNode *Node,
526
78
                                      SelectionDAG::allnodes_iterator &I) {
527
78
  ConstantSDNode *MaskN = dyn_cast<ConstantSDNode>(Node->getOperand(1));
528
78
  if (!MaskN)
529
8
    return;
530
70
531
70
  // The Reg operand should be a virtual register, which is defined
532
70
  // outside the current basic block. DAG combiner has done a pretty
533
70
  // good job in removing truncating inside a single basic block except
534
70
  // when the Reg operand comes from bpf_load_[byte | half | word] for
535
70
  // which the generic optimizer doesn't understand their results are
536
70
  // zero extended.
537
70
  SDValue BaseV = Node->getOperand(0);
538
70
  if (BaseV.getOpcode() == ISD::INTRINSIC_W_CHAIN) {
539
6
    unsigned IntNo = cast<ConstantSDNode>(BaseV->getOperand(1))->getZExtValue();
540
6
    uint64_t MaskV = MaskN->getZExtValue();
541
6
542
6
    if (!((IntNo == Intrinsic::bpf_load_byte && 
MaskV == 0xFF1
) ||
543
6
          
(5
IntNo == Intrinsic::bpf_load_half5
&&
MaskV == 0xFFFF5
) ||
544
6
          
(4
IntNo == Intrinsic::bpf_load_word4
&&
MaskV == 0xFFFFFFFF0
)))
545
4
      return;
546
2
547
2
    LLVM_DEBUG(dbgs() << "Remove the redundant AND operation in: ";
548
2
               Node->dump(); dbgs() << '\n');
549
2
550
2
    I--;
551
2
    CurDAG->ReplaceAllUsesWith(SDValue(Node, 0), BaseV);
552
2
    I++;
553
2
    CurDAG->DeleteNode(Node);
554
2
555
2
    return;
556
2
  }
557
64
558
64
  // Multiple basic blocks case.
559
64
  if (BaseV.getOpcode() != ISD::CopyFromReg)
560
20
    return;
561
44
562
44
  unsigned match_load_op = 0;
563
44
  switch (MaskN->getZExtValue()) {
564
44
  default:
565
2
    return;
566
44
  case 0xFFFFFFFF:
567
10
    match_load_op = BPF::LDW;
568
10
    break;
569
44
  case 0xFFFF:
570
30
    match_load_op = BPF::LDH;
571
30
    break;
572
44
  case 0xFF:
573
2
    match_load_op = BPF::LDB;
574
2
    break;
575
42
  }
576
42
577
42
  const RegisterSDNode *RegN =
578
42
      dyn_cast<RegisterSDNode>(BaseV.getNode()->getOperand(1));
579
42
  if (!RegN || !TargetRegisterInfo::isVirtualRegister(RegN->getReg()))
580
2
    return;
581
40
  unsigned AndOpReg = RegN->getReg();
582
40
  LLVM_DEBUG(dbgs() << "Examine " << printReg(AndOpReg) << '\n');
583
40
584
40
  // Examine the PHI insns in the MachineBasicBlock to found out the
585
40
  // definitions of this virtual register. At this stage (DAG2DAG
586
40
  // transformation), only PHI machine insns are available in the machine basic
587
40
  // block.
588
40
  MachineBasicBlock *MBB = FuncInfo->MBB;
589
40
  MachineInstr *MII = nullptr;
590
40
  for (auto &MI : *MBB) {
591
6
    for (unsigned i = 0; i < MI.getNumOperands(); 
++i0
) {
592
6
      const MachineOperand &MOP = MI.getOperand(i);
593
6
      if (!MOP.isReg() || !MOP.isDef())
594
0
        continue;
595
6
      unsigned Reg = MOP.getReg();
596
6
      if (TargetRegisterInfo::isVirtualRegister(Reg) && Reg == AndOpReg) {
597
6
        MII = &MI;
598
6
        break;
599
6
      }
600
6
    }
601
6
  }
602
40
603
40
  if (MII == nullptr) {
604
34
    // No phi definition in this block.
605
34
    if (!checkLoadDef(AndOpReg, match_load_op))
606
32
      return;
607
6
  } else {
608
6
    // The PHI node looks like:
609
6
    //   %2 = PHI %0, <%bb.1>, %1, <%bb.3>
610
6
    // Trace each incoming definition, e.g., (%0, %bb.1) and (%1, %bb.3)
611
6
    // The AND operation can be removed if both %0 in %bb.1 and %1 in
612
6
    // %bb.3 are defined with a load matching the MaskN.
613
6
    LLVM_DEBUG(dbgs() << "Check PHI Insn: "; MII->dump(); dbgs() << '\n');
614
6
    unsigned PrevReg = -1;
615
16
    for (unsigned i = 0; i < MII->getNumOperands(); 
++i10
) {
616
15
      const MachineOperand &MOP = MII->getOperand(i);
617
15
      if (MOP.isReg()) {
618
13
        if (MOP.isDef())
619
6
          continue;
620
7
        PrevReg = MOP.getReg();
621
7
        if (!TargetRegisterInfo::isVirtualRegister(PrevReg))
622
0
          return;
623
7
        if (!checkLoadDef(PrevReg, match_load_op))
624
5
          return;
625
7
      }
626
15
    }
627
6
  }
628
40
629
40
  
LLVM_DEBUG3
(dbgs() << "Remove the redundant AND operation in: "; Node->dump();
630
3
             dbgs() << '\n');
631
3
632
3
  I--;
633
3
  CurDAG->ReplaceAllUsesWith(SDValue(Node, 0), BaseV);
634
3
  I++;
635
3
  CurDAG->DeleteNode(Node);
636
3
}
637
638
41
bool BPFDAGToDAGISel::checkLoadDef(unsigned DefReg, unsigned match_load_op) {
639
41
  auto it = load_to_vreg_.find(DefReg);
640
41
  if (it == load_to_vreg_.end())
641
37
    return false; // The definition of register is not exported yet.
642
4
643
4
  return it->second == match_load_op;
644
4
}
645
646
206
FunctionPass *llvm::createBPFISelDag(BPFTargetMachine &TM) {
647
206
  return new BPFDAGToDAGISel(TM);
648
206
}