Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/DetectDeadLanes.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- DetectDeadLanes.cpp - SubRegister Lane Usage Analysis --*- C++ -*---===//
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
/// \file
10
/// Analysis that tracks defined/used subregister lanes across COPY instructions
11
/// and instructions that get lowered to a COPY (PHI, REG_SEQUENCE,
12
/// INSERT_SUBREG, EXTRACT_SUBREG).
13
/// The information is used to detect dead definitions and the usage of
14
/// (completely) undefined values and mark the operands as such.
15
/// This pass is necessary because the dead/undef status is not obvious anymore
16
/// when subregisters are involved.
17
///
18
/// Example:
19
///    %0 = some definition
20
///    %1 = IMPLICIT_DEF
21
///    %2 = REG_SEQUENCE %0, sub0, %1, sub1
22
///    %3 = EXTRACT_SUBREG %2, sub1
23
///       = use %3
24
/// The %0 definition is dead and %3 contains an undefined value.
25
//
26
//===----------------------------------------------------------------------===//
27
28
#include <deque>
29
#include <vector>
30
31
#include "llvm/ADT/BitVector.h"
32
#include "llvm/ADT/SetVector.h"
33
#include "llvm/CodeGen/MachineFunctionPass.h"
34
#include "llvm/CodeGen/MachineRegisterInfo.h"
35
#include "llvm/CodeGen/Passes.h"
36
#include "llvm/CodeGen/TargetRegisterInfo.h"
37
#include "llvm/CodeGen/TargetSubtargetInfo.h"
38
#include "llvm/InitializePasses.h"
39
#include "llvm/Pass.h"
40
#include "llvm/PassRegistry.h"
41
#include "llvm/Support/Debug.h"
42
#include "llvm/Support/raw_ostream.h"
43
44
using namespace llvm;
45
46
#define DEBUG_TYPE "detect-dead-lanes"
47
48
namespace {
49
50
/// Contains a bitmask of which lanes of a given virtual register are
51
/// defined and which ones are actually used.
52
struct VRegInfo {
53
  LaneBitmask UsedLanes;
54
  LaneBitmask DefinedLanes;
55
};
56
57
class DetectDeadLanes : public MachineFunctionPass {
58
public:
59
  bool runOnMachineFunction(MachineFunction &MF) override;
60
61
  static char ID;
62
34.2k
  DetectDeadLanes() : MachineFunctionPass(ID) {}
63
64
522k
  StringRef getPassName() const override { return "Detect Dead Lanes"; }
65
66
34.0k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
67
34.0k
    AU.setPreservesCFG();
68
34.0k
    MachineFunctionPass::getAnalysisUsage(AU);
69
34.0k
  }
70
71
private:
72
  /// Add used lane bits on the register used by operand \p MO. This translates
73
  /// the bitmask based on the operands subregister, and puts the register into
74
  /// the worklist if any new bits were added.
75
  void addUsedLanesOnOperand(const MachineOperand &MO, LaneBitmask UsedLanes);
76
77
  /// Given a bitmask \p UsedLanes for the used lanes on a def output of a
78
  /// COPY-like instruction determine the lanes used on the use operands
79
  /// and call addUsedLanesOnOperand() for them.
80
  void transferUsedLanesStep(const MachineInstr &MI, LaneBitmask UsedLanes);
81
82
  /// Given a use regiser operand \p Use and a mask of defined lanes, check
83
  /// if the operand belongs to a lowersToCopies() instruction, transfer the
84
  /// mask to the def and put the instruction into the worklist.
85
  void transferDefinedLanesStep(const MachineOperand &Use,
86
                                LaneBitmask DefinedLanes);
87
88
  /// Given a mask \p DefinedLanes of lanes defined at operand \p OpNum
89
  /// of COPY-like instruction, determine which lanes are defined at the output
90
  /// operand \p Def.
91
  LaneBitmask transferDefinedLanes(const MachineOperand &Def, unsigned OpNum,
92
                                   LaneBitmask DefinedLanes) const;
93
94
  /// Given a mask \p UsedLanes used from the output of instruction \p MI
95
  /// determine which lanes are used from operand \p MO of this instruction.
96
  LaneBitmask transferUsedLanes(const MachineInstr &MI, LaneBitmask UsedLanes,
97
                                const MachineOperand &MO) const;
98
99
  bool runOnce(MachineFunction &MF);
100
101
  LaneBitmask determineInitialDefinedLanes(unsigned Reg);
102
  LaneBitmask determineInitialUsedLanes(unsigned Reg);
103
104
  bool isUndefRegAtInput(const MachineOperand &MO,
105
                         const VRegInfo &RegInfo) const;
106
107
  bool isUndefInput(const MachineOperand &MO, bool *CrossCopy) const;
108
109
  const MachineRegisterInfo *MRI;
110
  const TargetRegisterInfo *TRI;
111
112
392k
  void PutInWorklist(unsigned RegIdx) {
113
392k
    if (WorklistMembers.test(RegIdx))
114
93.1k
      return;
115
299k
    WorklistMembers.set(RegIdx);
116
299k
    Worklist.push_back(RegIdx);
117
299k
  }
118
119
  VRegInfo *VRegInfos;
120
  /// Worklist containing virtreg indexes.
121
  std::deque<unsigned> Worklist;
122
  BitVector WorklistMembers;
123
  /// This bitvector is set for each vreg index where the vreg is defined
124
  /// by an instruction where lowersToCopies()==true.
125
  BitVector DefinedByCopy;
126
};
127
128
} // end anonymous namespace
129
130
char DetectDeadLanes::ID = 0;
131
char &llvm::DetectDeadLanesID = DetectDeadLanes::ID;
132
133
INITIALIZE_PASS(DetectDeadLanes, DEBUG_TYPE, "Detect Dead Lanes", false, false)
134
135
/// Returns true if \p MI will get lowered to a series of COPY instructions.
136
/// We call this a COPY-like instruction.
137
2.38M
static bool lowersToCopies(const MachineInstr &MI) {
138
2.38M
  // Note: We could support instructions with MCInstrDesc::isRegSequenceLike(),
139
2.38M
  // isExtractSubRegLike(), isInsertSubregLike() in the future even though they
140
2.38M
  // are not lowered to a COPY.
141
2.38M
  switch (MI.getOpcode()) {
142
2.38M
  case TargetOpcode::COPY:
143
1.20M
  case TargetOpcode::PHI:
144
1.20M
  case TargetOpcode::INSERT_SUBREG:
145
1.20M
  case TargetOpcode::REG_SEQUENCE:
146
1.20M
  case TargetOpcode::EXTRACT_SUBREG:
147
1.20M
    return true;
148
1.18M
  }
149
1.18M
  return false;
150
1.18M
}
151
152
static bool isCrossCopy(const MachineRegisterInfo &MRI,
153
                        const MachineInstr &MI,
154
                        const TargetRegisterClass *DstRC,
155
579k
                        const MachineOperand &MO) {
156
579k
  assert(lowersToCopies(MI));
157
579k
  unsigned SrcReg = MO.getReg();
158
579k
  const TargetRegisterClass *SrcRC = MRI.getRegClass(SrcReg);
159
579k
  if (DstRC == SrcRC)
160
56.3k
    return false;
161
522k
162
522k
  unsigned SrcSubIdx = MO.getSubReg();
163
522k
164
522k
  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
165
522k
  unsigned DstSubIdx = 0;
166
522k
  switch (MI.getOpcode()) {
167
522k
  case TargetOpcode::INSERT_SUBREG:
168
1.26k
    if (MI.getOperandNo(&MO) == 2)
169
1.24k
      DstSubIdx = MI.getOperand(3).getImm();
170
1.26k
    break;
171
522k
  case TargetOpcode::REG_SEQUENCE: {
172
316k
    unsigned OpNum = MI.getOperandNo(&MO);
173
316k
    DstSubIdx = MI.getOperand(OpNum+1).getImm();
174
316k
    break;
175
522k
  }
176
522k
  case TargetOpcode::EXTRACT_SUBREG: {
177
10
    unsigned SubReg = MI.getOperand(2).getImm();
178
10
    SrcSubIdx = TRI.composeSubRegIndices(SubReg, SrcSubIdx);
179
10
  }
180
522k
  }
181
522k
182
522k
  unsigned PreA, PreB; // Unused.
183
522k
  if (SrcSubIdx && 
DstSubIdx120k
)
184
5.10k
    return !TRI.getCommonSuperRegClass(SrcRC, SrcSubIdx, DstRC, DstSubIdx, PreA,
185
5.10k
                                       PreB);
186
517k
  if (SrcSubIdx)
187
115k
    return !TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSubIdx);
188
402k
  if (DstSubIdx)
189
312k
    return !TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSubIdx);
190
89.6k
  return !TRI.getCommonSubClass(SrcRC, DstRC);
191
89.6k
}
192
193
void DetectDeadLanes::addUsedLanesOnOperand(const MachineOperand &MO,
194
355k
                                            LaneBitmask UsedLanes) {
195
355k
  if (!MO.readsReg())
196
20
    return;
197
355k
  unsigned MOReg = MO.getReg();
198
355k
  if (!TargetRegisterInfo::isVirtualRegister(MOReg))
199
0
    return;
200
355k
201
355k
  unsigned MOSubReg = MO.getSubReg();
202
355k
  if (MOSubReg != 0)
203
105k
    UsedLanes = TRI->composeSubRegIndexLaneMask(MOSubReg, UsedLanes);
204
355k
  UsedLanes &= MRI->getMaxLaneMaskForVReg(MOReg);
205
355k
206
355k
  unsigned MORegIdx = TargetRegisterInfo::virtReg2Index(MOReg);
207
355k
  VRegInfo &MORegInfo = VRegInfos[MORegIdx];
208
355k
  LaneBitmask PrevUsedLanes = MORegInfo.UsedLanes;
209
355k
  // Any change at all?
210
355k
  if ((UsedLanes & ~PrevUsedLanes).none())
211
133k
    return;
212
222k
213
222k
  // Set UsedLanes and remember instruction for further propagation.
214
222k
  MORegInfo.UsedLanes = PrevUsedLanes | UsedLanes;
215
222k
  if (DefinedByCopy.test(MORegIdx))
216
79.5k
    PutInWorklist(MORegIdx);
217
222k
}
218
219
void DetectDeadLanes::transferUsedLanesStep(const MachineInstr &MI,
220
299k
                                            LaneBitmask UsedLanes) {
221
661k
  for (const MachineOperand &MO : MI.uses()) {
222
661k
    if (!MO.isReg() || 
!TargetRegisterInfo::isVirtualRegister(MO.getReg())441k
)
223
305k
      continue;
224
355k
    LaneBitmask UsedOnMO = transferUsedLanes(MI, UsedLanes, MO);
225
355k
    addUsedLanesOnOperand(MO, UsedOnMO);
226
355k
  }
227
299k
}
228
229
LaneBitmask DetectDeadLanes::transferUsedLanes(const MachineInstr &MI,
230
                                               LaneBitmask UsedLanes,
231
636k
                                               const MachineOperand &MO) const {
232
636k
  unsigned OpNum = MI.getOperandNo(&MO);
233
636k
  assert(lowersToCopies(MI) && DefinedByCopy[
234
636k
           TargetRegisterInfo::virtReg2Index(MI.getOperand(0).getReg())]);
235
636k
236
636k
  switch (MI.getOpcode()) {
237
636k
  case TargetOpcode::COPY:
238
260k
  case TargetOpcode::PHI:
239
260k
    return UsedLanes;
240
373k
  case TargetOpcode::REG_SEQUENCE: {
241
373k
    assert(OpNum % 2 == 1);
242
373k
    unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();
243
373k
    return TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);
244
260k
  }
245
260k
  case TargetOpcode::INSERT_SUBREG: {
246
2.90k
    unsigned SubIdx = MI.getOperand(3).getImm();
247
2.90k
    LaneBitmask MO2UsedLanes =
248
2.90k
        TRI->reverseComposeSubRegIndexLaneMask(SubIdx, UsedLanes);
249
2.90k
    if (OpNum == 2)
250
1.58k
      return MO2UsedLanes;
251
1.32k
252
1.32k
    const MachineOperand &Def = MI.getOperand(0);
253
1.32k
    unsigned DefReg = Def.getReg();
254
1.32k
    const TargetRegisterClass *RC = MRI->getRegClass(DefReg);
255
1.32k
    LaneBitmask MO1UsedLanes;
256
1.32k
    if (RC->CoveredBySubRegs)
257
1.14k
      MO1UsedLanes = UsedLanes & ~TRI->getSubRegIndexLaneMask(SubIdx);
258
184
    else
259
184
      MO1UsedLanes = RC->LaneMask;
260
1.32k
261
1.32k
    assert(OpNum == 1);
262
1.32k
    return MO1UsedLanes;
263
1.32k
  }
264
1.32k
  case TargetOpcode::EXTRACT_SUBREG: {
265
10
    assert(OpNum == 1);
266
10
    unsigned SubIdx = MI.getOperand(2).getImm();
267
10
    return TRI->composeSubRegIndexLaneMask(SubIdx, UsedLanes);
268
1.32k
  }
269
1.32k
  default:
270
0
    llvm_unreachable("function must be called with COPY-like instruction");
271
636k
  }
272
636k
}
273
274
void DetectDeadLanes::transferDefinedLanesStep(const MachineOperand &Use,
275
356k
                                               LaneBitmask DefinedLanes) {
276
356k
  if (!Use.readsReg())
277
108
    return;
278
356k
  // Check whether the operand writes a vreg and is part of a COPY-like
279
356k
  // instruction.
280
356k
  const MachineInstr &MI = *Use.getParent();
281
356k
  if (MI.getDesc().getNumDefs() != 1)
282
71.4k
    return;
283
285k
  // FIXME: PATCHPOINT instructions announce a Def that does not always exist,
284
285k
  // they really need to be modeled differently!
285
285k
  if (MI.getOpcode() == TargetOpcode::PATCHPOINT)
286
0
    return;
287
285k
  const MachineOperand &Def = *MI.defs().begin();
288
285k
  unsigned DefReg = Def.getReg();
289
285k
  if (!TargetRegisterInfo::isVirtualRegister(DefReg))
290
8.52k
    return;
291
276k
  unsigned DefRegIdx = TargetRegisterInfo::virtReg2Index(DefReg);
292
276k
  if (!DefinedByCopy.test(DefRegIdx))
293
105k
    return;
294
170k
295
170k
  unsigned OpNum = MI.getOperandNo(&Use);
296
170k
  DefinedLanes =
297
170k
      TRI->reverseComposeSubRegIndexLaneMask(Use.getSubReg(), DefinedLanes);
298
170k
  DefinedLanes = transferDefinedLanes(Def, OpNum, DefinedLanes);
299
170k
300
170k
  VRegInfo &RegInfo = VRegInfos[DefRegIdx];
301
170k
  LaneBitmask PrevDefinedLanes = RegInfo.DefinedLanes;
302
170k
  // Any change at all?
303
170k
  if ((DefinedLanes & ~PrevDefinedLanes).none())
304
90.0k
    return;
305
80.6k
306
80.6k
  RegInfo.DefinedLanes = PrevDefinedLanes | DefinedLanes;
307
80.6k
  PutInWorklist(DefRegIdx);
308
80.6k
}
309
310
LaneBitmask DetectDeadLanes::transferDefinedLanes(const MachineOperand &Def,
311
434k
    unsigned OpNum, LaneBitmask DefinedLanes) const {
312
434k
  const MachineInstr &MI = *Def.getParent();
313
434k
  // Translate DefinedLanes if necessary.
314
434k
  switch (MI.getOpcode()) {
315
434k
  case TargetOpcode::REG_SEQUENCE: {
316
225k
    unsigned SubIdx = MI.getOperand(OpNum + 1).getImm();
317
225k
    DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
318
225k
    DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);
319
225k
    break;
320
434k
  }
321
434k
  case TargetOpcode::INSERT_SUBREG: {
322
1.32k
    unsigned SubIdx = MI.getOperand(3).getImm();
323
1.32k
    if (OpNum == 2) {
324
622
      DefinedLanes = TRI->composeSubRegIndexLaneMask(SubIdx, DefinedLanes);
325
622
      DefinedLanes &= TRI->getSubRegIndexLaneMask(SubIdx);
326
704
    } else {
327
704
      assert(OpNum == 1 && "INSERT_SUBREG must have two operands");
328
704
      // Ignore lanes defined by operand 2.
329
704
      DefinedLanes &= ~TRI->getSubRegIndexLaneMask(SubIdx);
330
704
    }
331
1.32k
    break;
332
434k
  }
333
434k
  case TargetOpcode::EXTRACT_SUBREG: {
334
6
    unsigned SubIdx = MI.getOperand(2).getImm();
335
6
    assert(OpNum == 1 && "EXTRACT_SUBREG must have one register operand only");
336
6
    DefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(SubIdx, DefinedLanes);
337
6
    break;
338
434k
  }
339
434k
  case TargetOpcode::COPY:
340
207k
  case TargetOpcode::PHI:
341
207k
    break;
342
207k
  default:
343
0
    llvm_unreachable("function must be called with COPY-like instruction");
344
434k
  }
345
434k
346
434k
  assert(Def.getSubReg() == 0 &&
347
434k
         "Should not have subregister defs in machine SSA phase");
348
434k
  DefinedLanes &= MRI->getMaxLaneMaskForVReg(Def.getReg());
349
434k
  return DefinedLanes;
350
434k
}
351
352
951k
LaneBitmask DetectDeadLanes::determineInitialDefinedLanes(unsigned Reg) {
353
951k
  // Live-In or unused registers have no definition but are considered fully
354
951k
  // defined.
355
951k
  if (!MRI->hasOneDef(Reg))
356
429k
    return LaneBitmask::getAll();
357
522k
358
522k
  const MachineOperand &Def = *MRI->def_begin(Reg);
359
522k
  const MachineInstr &DefMI = *Def.getParent();
360
522k
  if (lowersToCopies(DefMI)) {
361
232k
    // Start optimisatically with no used or defined lanes for copy
362
232k
    // instructions. The following dataflow analysis will add more bits.
363
232k
    unsigned RegIdx = TargetRegisterInfo::virtReg2Index(Reg);
364
232k
    DefinedByCopy.set(RegIdx);
365
232k
    PutInWorklist(RegIdx);
366
232k
367
232k
    if (Def.isDead())
368
4
      return LaneBitmask::getNone();
369
232k
370
232k
    // COPY/PHI can copy across unrelated register classes (example: float/int)
371
232k
    // with incompatible subregister structure. Do not include these in the
372
232k
    // dataflow analysis since we cannot transfer lanemasks in a meaningful way.
373
232k
    const TargetRegisterClass *DefRC = MRI->getRegClass(Reg);
374
232k
375
232k
    // Determine initially DefinedLanes.
376
232k
    LaneBitmask DefinedLanes;
377
540k
    for (const MachineOperand &MO : DefMI.uses()) {
378
540k
      if (!MO.isReg() || 
!MO.readsReg()353k
)
379
186k
        continue;
380
353k
      unsigned MOReg = MO.getReg();
381
353k
      if (!MOReg)
382
0
        continue;
383
353k
384
353k
      LaneBitmask MODefinedLanes;
385
353k
      if (TargetRegisterInfo::isPhysicalRegister(MOReg)) {
386
61.6k
        MODefinedLanes = LaneBitmask::getAll();
387
291k
      } else if (isCrossCopy(*MRI, DefMI, DefRC, MO)) {
388
40.9k
        MODefinedLanes = LaneBitmask::getAll();
389
250k
      } else {
390
250k
        assert(TargetRegisterInfo::isVirtualRegister(MOReg));
391
250k
        if (MRI->hasOneDef(MOReg)) {
392
250k
          const MachineOperand &MODef = *MRI->def_begin(MOReg);
393
250k
          const MachineInstr &MODefMI = *MODef.getParent();
394
250k
          // Bits from copy-like operations will be added later.
395
250k
          if (lowersToCopies(MODefMI) || 
MODefMI.isImplicitDef()165k
)
396
89.5k
            continue;
397
161k
        }
398
161k
        unsigned MOSubReg = MO.getSubReg();
399
161k
        MODefinedLanes = MRI->getMaxLaneMaskForVReg(MOReg);
400
161k
        MODefinedLanes = TRI->reverseComposeSubRegIndexLaneMask(
401
161k
            MOSubReg, MODefinedLanes);
402
161k
      }
403
353k
404
353k
      unsigned OpNum = DefMI.getOperandNo(&MO);
405
263k
      DefinedLanes |= transferDefinedLanes(Def, OpNum, MODefinedLanes);
406
263k
    }
407
232k
    return DefinedLanes;
408
232k
  }
409
289k
  if (DefMI.isImplicitDef() || 
Def.isDead()281k
)
410
16.0k
    return LaneBitmask::getNone();
411
273k
412
273k
  assert(Def.getSubReg() == 0 &&
413
273k
         "Should not have subregister defs in machine SSA phase");
414
273k
  return MRI->getMaxLaneMaskForVReg(Reg);
415
273k
}
416
417
951k
LaneBitmask DetectDeadLanes::determineInitialUsedLanes(unsigned Reg) {
418
951k
  LaneBitmask UsedLanes = LaneBitmask::getNone();
419
951k
  for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
420
615k
    if (!MO.readsReg())
421
98
      continue;
422
615k
423
615k
    const MachineInstr &UseMI = *MO.getParent();
424
615k
    if (UseMI.isKill())
425
1
      continue;
426
615k
427
615k
    unsigned SubReg = MO.getSubReg();
428
615k
    if (lowersToCopies(UseMI)) {
429
301k
      assert(UseMI.getDesc().getNumDefs() == 1);
430
301k
      const MachineOperand &Def = *UseMI.defs().begin();
431
301k
      unsigned DefReg = Def.getReg();
432
301k
      // The used lanes of COPY-like instruction operands are determined by the
433
301k
      // following dataflow analysis.
434
301k
      if (TargetRegisterInfo::isVirtualRegister(DefReg)) {
435
287k
        // But ignore copies across incompatible register classes.
436
287k
        bool CrossCopy = false;
437
287k
        if (lowersToCopies(UseMI)) {
438
287k
          const TargetRegisterClass *DstRC = MRI->getRegClass(DefReg);
439
287k
          CrossCopy = isCrossCopy(*MRI, UseMI, DstRC, MO);
440
287k
          if (CrossCopy)
441
287k
            LLVM_DEBUG(dbgs() << "Copy across incompatible classes: " << UseMI);
442
287k
        }
443
287k
444
287k
        if (!CrossCopy)
445
247k
          continue;
446
368k
      }
447
301k
    }
448
368k
449
368k
    // Shortcut: All lanes are used.
450
368k
    if (SubReg == 0)
451
323k
      return MRI->getMaxLaneMaskForVReg(Reg);
452
44.9k
453
44.9k
    UsedLanes |= TRI->getSubRegIndexLaneMask(SubReg);
454
44.9k
  }
455
951k
  
return UsedLanes627k
;
456
951k
}
457
458
bool DetectDeadLanes::isUndefRegAtInput(const MachineOperand &MO,
459
717k
                                        const VRegInfo &RegInfo) const {
460
717k
  unsigned SubReg = MO.getSubReg();
461
717k
  LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
462
717k
  return (RegInfo.DefinedLanes & RegInfo.UsedLanes & Mask).none();
463
717k
}
464
465
bool DetectDeadLanes::isUndefInput(const MachineOperand &MO,
466
704k
                                   bool *CrossCopy) const {
467
704k
  if (!MO.isUse())
468
0
    return false;
469
704k
  const MachineInstr &MI = *MO.getParent();
470
704k
  if (!lowersToCopies(MI))
471
410k
    return false;
472
294k
  const MachineOperand &Def = MI.getOperand(0);
473
294k
  unsigned DefReg = Def.getReg();
474
294k
  if (!TargetRegisterInfo::isVirtualRegister(DefReg))
475
13.8k
    return false;
476
280k
  unsigned DefRegIdx = TargetRegisterInfo::virtReg2Index(DefReg);
477
280k
  if (!DefinedByCopy.test(DefRegIdx))
478
0
    return false;
479
280k
480
280k
  const VRegInfo &DefRegInfo = VRegInfos[DefRegIdx];
481
280k
  LaneBitmask UsedLanes = transferUsedLanes(MI, DefRegInfo.UsedLanes, MO);
482
280k
  if (UsedLanes.any())
483
280k
    return false;
484
121
485
121
  unsigned MOReg = MO.getReg();
486
121
  if (TargetRegisterInfo::isVirtualRegister(MOReg)) {
487
121
    const TargetRegisterClass *DstRC = MRI->getRegClass(DefReg);
488
121
    *CrossCopy = isCrossCopy(*MRI, MI, DstRC, MO);
489
121
  }
490
121
  return true;
491
121
}
492
493
30.9k
bool DetectDeadLanes::runOnce(MachineFunction &MF) {
494
30.9k
  // First pass: Populate defs/uses of vregs with initial values
495
30.9k
  unsigned NumVirtRegs = MRI->getNumVirtRegs();
496
982k
  for (unsigned RegIdx = 0; RegIdx < NumVirtRegs; 
++RegIdx951k
) {
497
951k
    unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
498
951k
499
951k
    // Determine used/defined lanes and add copy instructions to worklist.
500
951k
    VRegInfo &Info = VRegInfos[RegIdx];
501
951k
    Info.DefinedLanes = determineInitialDefinedLanes(Reg);
502
951k
    Info.UsedLanes = determineInitialUsedLanes(Reg);
503
951k
  }
504
30.9k
505
30.9k
  // Iterate as long as defined lanes/used lanes keep changing.
506
330k
  while (!Worklist.empty()) {
507
299k
    unsigned RegIdx = Worklist.front();
508
299k
    Worklist.pop_front();
509
299k
    WorklistMembers.reset(RegIdx);
510
299k
    VRegInfo &Info = VRegInfos[RegIdx];
511
299k
    unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
512
299k
513
299k
    // Transfer UsedLanes to operands of DefMI (backwards dataflow).
514
299k
    MachineOperand &Def = *MRI->def_begin(Reg);
515
299k
    const MachineInstr &MI = *Def.getParent();
516
299k
    transferUsedLanesStep(MI, Info.UsedLanes);
517
299k
    // Transfer DefinedLanes to users of Reg (forward dataflow).
518
299k
    for (const MachineOperand &MO : MRI->use_nodbg_operands(Reg))
519
356k
      transferDefinedLanesStep(MO, Info.DefinedLanes);
520
299k
  }
521
30.9k
522
30.9k
  LLVM_DEBUG(dbgs() << "Defined/Used lanes:\n"; for (unsigned RegIdx = 0;
523
30.9k
                                                     RegIdx < NumVirtRegs;
524
30.9k
                                                     ++RegIdx) {
525
30.9k
    unsigned Reg = TargetRegisterInfo::index2VirtReg(RegIdx);
526
30.9k
    const VRegInfo &Info = VRegInfos[RegIdx];
527
30.9k
    dbgs() << printReg(Reg, nullptr)
528
30.9k
           << " Used: " << PrintLaneMask(Info.UsedLanes)
529
30.9k
           << " Def: " << PrintLaneMask(Info.DefinedLanes) << '\n';
530
30.9k
  } dbgs() << "\n";);
531
30.9k
532
30.9k
  bool Again = false;
533
30.9k
  // Mark operands as dead/unused.
534
36.6k
  for (MachineBasicBlock &MBB : MF) {
535
622k
    for (MachineInstr &MI : MBB) {
536
3.19M
      for (MachineOperand &MO : MI.operands()) {
537
3.19M
        if (!MO.isReg())
538
1.50M
          continue;
539
1.69M
        unsigned Reg = MO.getReg();
540
1.69M
        if (!TargetRegisterInfo::isVirtualRegister(Reg))
541
452k
          continue;
542
1.23M
        unsigned RegIdx = TargetRegisterInfo::virtReg2Index(Reg);
543
1.23M
        const VRegInfo &RegInfo = VRegInfos[RegIdx];
544
1.23M
        if (MO.isDef() && 
!MO.isDead()522k
&&
RegInfo.UsedLanes.none()513k
) {
545
1.47k
          LLVM_DEBUG(dbgs()
546
1.47k
                     << "Marking operand '" << MO << "' as dead in " << MI);
547
1.47k
          MO.setIsDead();
548
1.47k
        }
549
1.23M
        if (MO.readsReg()) {
550
717k
          bool CrossCopy = false;
551
717k
          if (isUndefRegAtInput(MO, RegInfo)) {
552
12.5k
            LLVM_DEBUG(dbgs()
553
12.5k
                       << "Marking operand '" << MO << "' as undef in " << MI);
554
12.5k
            MO.setIsUndef();
555
704k
          } else if (isUndefInput(MO, &CrossCopy)) {
556
121
            LLVM_DEBUG(dbgs()
557
121
                       << "Marking operand '" << MO << "' as undef in " << MI);
558
121
            MO.setIsUndef();
559
121
            if (CrossCopy)
560
3
              Again = true;
561
121
          }
562
717k
        }
563
1.23M
      }
564
622k
    }
565
36.6k
  }
566
30.9k
567
30.9k
  return Again;
568
30.9k
}
569
570
488k
bool DetectDeadLanes::runOnMachineFunction(MachineFunction &MF) {
571
488k
  // Don't bother if we won't track subregister liveness later.  This pass is
572
488k
  // required for correctness if subregister liveness is enabled because the
573
488k
  // register coalescer cannot deal with hidden dead defs. However without
574
488k
  // subregister liveness enabled, the expected benefits of this pass are small
575
488k
  // so we safe the compile time.
576
488k
  MRI = &MF.getRegInfo();
577
488k
  if (!MRI->subRegLivenessEnabled()) {
578
457k
    LLVM_DEBUG(dbgs() << "Skipping Detect dead lanes pass\n");
579
457k
    return false;
580
457k
  }
581
30.9k
582
30.9k
  TRI = MRI->getTargetRegisterInfo();
583
30.9k
584
30.9k
  unsigned NumVirtRegs = MRI->getNumVirtRegs();
585
30.9k
  VRegInfos = new VRegInfo[NumVirtRegs];
586
30.9k
  WorklistMembers.resize(NumVirtRegs);
587
30.9k
  DefinedByCopy.resize(NumVirtRegs);
588
30.9k
589
30.9k
  bool Again;
590
30.9k
  do {
591
30.9k
    Again = runOnce(MF);
592
30.9k
  } while(Again);
593
30.9k
594
30.9k
  DefinedByCopy.clear();
595
30.9k
  WorklistMembers.clear();
596
30.9k
  delete[] VRegInfos;
597
30.9k
  return true;
598
30.9k
}