Coverage Report

Created: 2017-10-03 07:32

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