Coverage Report

Created: 2019-02-20 00:17

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h
Line
Count
Source (jump to first uncovered line)
1
//===-- llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h -----*- 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
// This file contains some helper functions which try to cleanup artifacts
9
// such as G_TRUNCs/G_[ZSA]EXTENDS that were created during legalization to make
10
// the types match. This file also contains some combines of merges that happens
11
// at the end of the legalization.
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/CodeGen/GlobalISel/Legalizer.h"
15
#include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
16
#include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
17
#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
18
#include "llvm/CodeGen/GlobalISel/Utils.h"
19
#include "llvm/CodeGen/MachineRegisterInfo.h"
20
#include "llvm/Support/Debug.h"
21
22
#define DEBUG_TYPE "legalizer"
23
using namespace llvm::MIPatternMatch;
24
25
namespace llvm {
26
class LegalizationArtifactCombiner {
27
  MachineIRBuilder &Builder;
28
  MachineRegisterInfo &MRI;
29
  const LegalizerInfo &LI;
30
31
public:
32
  LegalizationArtifactCombiner(MachineIRBuilder &B, MachineRegisterInfo &MRI,
33
                    const LegalizerInfo &LI)
34
236k
      : Builder(B), MRI(MRI), LI(LI) {}
35
36
  bool tryCombineAnyExt(MachineInstr &MI,
37
245k
                        SmallVectorImpl<MachineInstr *> &DeadInsts) {
38
245k
    if (MI.getOpcode() != TargetOpcode::G_ANYEXT)
39
0
      return false;
40
245k
41
245k
    Builder.setInstr(MI);
42
245k
    unsigned DstReg = MI.getOperand(0).getReg();
43
245k
    unsigned SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
44
245k
45
245k
    // aext(trunc x) - > aext/copy/trunc x
46
245k
    unsigned TruncSrc;
47
245k
    if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
48
208k
      LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
49
208k
      Builder.buildAnyExtOrTrunc(DstReg, TruncSrc);
50
208k
      markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
51
208k
      return true;
52
208k
    }
53
36.6k
54
36.6k
    // aext([asz]ext x) -> [asz]ext x
55
36.6k
    unsigned ExtSrc;
56
36.6k
    MachineInstr *ExtMI;
57
36.6k
    if (mi_match(SrcReg, MRI,
58
36.6k
                 m_all_of(m_MInstr(ExtMI), m_any_of(m_GAnyExt(m_Reg(ExtSrc)),
59
36.6k
                                                    m_GSExt(m_Reg(ExtSrc)),
60
36.6k
                                                    m_GZExt(m_Reg(ExtSrc)))))) {
61
106
      Builder.buildInstr(ExtMI->getOpcode(), {DstReg}, {ExtSrc});
62
106
      markInstAndDefDead(MI, *ExtMI, DeadInsts);
63
106
      return true;
64
106
    }
65
36.5k
    return tryFoldImplicitDef(MI, DeadInsts);
66
36.5k
  }
67
68
  bool tryCombineZExt(MachineInstr &MI,
69
315k
                      SmallVectorImpl<MachineInstr *> &DeadInsts) {
70
315k
71
315k
    if (MI.getOpcode() != TargetOpcode::G_ZEXT)
72
0
      return false;
73
315k
74
315k
    Builder.setInstr(MI);
75
315k
    unsigned DstReg = MI.getOperand(0).getReg();
76
315k
    unsigned SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
77
315k
78
315k
    // zext(trunc x) - > and (aext/copy/trunc x), mask
79
315k
    unsigned TruncSrc;
80
315k
    if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
81
154k
      LLT DstTy = MRI.getType(DstReg);
82
154k
      if (isInstUnsupported({TargetOpcode::G_AND, {DstTy}}) ||
83
154k
          isConstantUnsupported(DstTy))
84
0
        return false;
85
154k
      LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
86
154k
      LLT SrcTy = MRI.getType(SrcReg);
87
154k
      APInt Mask = APInt::getAllOnesValue(SrcTy.getScalarSizeInBits());
88
154k
      auto MIBMask = Builder.buildConstant(DstTy, Mask.getZExtValue());
89
154k
      Builder.buildAnd(DstReg, Builder.buildAnyExtOrTrunc(DstTy, TruncSrc),
90
154k
                       MIBMask);
91
154k
      markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
92
154k
      return true;
93
154k
    }
94
161k
    return tryFoldImplicitDef(MI, DeadInsts);
95
161k
  }
96
97
  bool tryCombineSExt(MachineInstr &MI,
98
154k
                      SmallVectorImpl<MachineInstr *> &DeadInsts) {
99
154k
100
154k
    if (MI.getOpcode() != TargetOpcode::G_SEXT)
101
0
      return false;
102
154k
103
154k
    Builder.setInstr(MI);
104
154k
    unsigned DstReg = MI.getOperand(0).getReg();
105
154k
    unsigned SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
106
154k
107
154k
    // sext(trunc x) - > ashr (shl (aext/copy/trunc x), c), c
108
154k
    unsigned TruncSrc;
109
154k
    if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
110
26.2k
      LLT DstTy = MRI.getType(DstReg);
111
26.2k
      // Guess on the RHS shift amount type, which should be re-legalized if
112
26.2k
      // applicable.
113
26.2k
      if (isInstUnsupported({TargetOpcode::G_SHL, {DstTy, DstTy}}) ||
114
26.2k
          isInstUnsupported({TargetOpcode::G_ASHR, {DstTy, DstTy}}) ||
115
26.2k
          isConstantUnsupported(DstTy))
116
0
        return false;
117
26.2k
      LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
118
26.2k
      LLT SrcTy = MRI.getType(SrcReg);
119
26.2k
      unsigned ShAmt = DstTy.getScalarSizeInBits() - SrcTy.getScalarSizeInBits();
120
26.2k
      auto MIBShAmt = Builder.buildConstant(DstTy, ShAmt);
121
26.2k
      auto MIBShl = Builder.buildInstr(
122
26.2k
          TargetOpcode::G_SHL, {DstTy},
123
26.2k
          {Builder.buildAnyExtOrTrunc(DstTy, TruncSrc), MIBShAmt});
124
26.2k
      Builder.buildInstr(TargetOpcode::G_ASHR, {DstReg}, {MIBShl, MIBShAmt});
125
26.2k
      markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
126
26.2k
      return true;
127
26.2k
    }
128
128k
    return tryFoldImplicitDef(MI, DeadInsts);
129
128k
  }
130
131
  /// Try to fold G_[ASZ]EXT (G_IMPLICIT_DEF).
132
  bool tryFoldImplicitDef(MachineInstr &MI,
133
326k
                          SmallVectorImpl<MachineInstr *> &DeadInsts) {
134
326k
    unsigned Opcode = MI.getOpcode();
135
326k
    if (Opcode != TargetOpcode::G_ANYEXT && 
Opcode != TargetOpcode::G_ZEXT289k
&&
136
326k
        
Opcode != TargetOpcode::G_SEXT128k
)
137
0
      return false;
138
326k
139
326k
    if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF,
140
21
                                           MI.getOperand(1).getReg(), MRI)) {
141
21
      Builder.setInstr(MI);
142
21
      unsigned DstReg = MI.getOperand(0).getReg();
143
21
      LLT DstTy = MRI.getType(DstReg);
144
21
145
21
      if (Opcode == TargetOpcode::G_ANYEXT) {
146
11
        // G_ANYEXT (G_IMPLICIT_DEF) -> G_IMPLICIT_DEF
147
11
        if (isInstUnsupported({TargetOpcode::G_IMPLICIT_DEF, {DstTy}}))
148
0
          return false;
149
11
        LLVM_DEBUG(dbgs() << ".. Combine G_ANYEXT(G_IMPLICIT_DEF): " << MI;);
150
11
        Builder.buildInstr(TargetOpcode::G_IMPLICIT_DEF, {DstReg}, {});
151
11
      } else {
152
10
        // G_[SZ]EXT (G_IMPLICIT_DEF) -> G_CONSTANT 0 because the top
153
10
        // bits will be 0 for G_ZEXT and 0/1 for the G_SEXT.
154
10
        if (isConstantUnsupported(DstTy))
155
0
          return false;
156
10
        LLVM_DEBUG(dbgs() << ".. Combine G_[SZ]EXT(G_IMPLICIT_DEF): " << MI;);
157
10
        Builder.buildConstant(DstReg, 0);
158
10
      }
159
21
160
21
      markInstAndDefDead(MI, *DefMI, DeadInsts);
161
21
      return true;
162
326k
    }
163
326k
    return false;
164
326k
  }
165
166
14.0k
  static unsigned getMergeOpcode(LLT OpTy, LLT DestTy) {
167
14.0k
    if (OpTy.isVector() && 
DestTy.isVector()11.8k
)
168
6.68k
      return TargetOpcode::G_CONCAT_VECTORS;
169
7.34k
170
7.34k
    if (OpTy.isVector() && 
!DestTy.isVector()5.18k
)
171
5.18k
      return TargetOpcode::G_BUILD_VECTOR;
172
2.16k
173
2.16k
    return TargetOpcode::G_MERGE_VALUES;
174
2.16k
  }
175
176
  bool tryCombineMerges(MachineInstr &MI,
177
14.0k
                        SmallVectorImpl<MachineInstr *> &DeadInsts) {
178
14.0k
179
14.0k
    if (MI.getOpcode() != TargetOpcode::G_UNMERGE_VALUES)
180
0
      return false;
181
14.0k
182
14.0k
    unsigned NumDefs = MI.getNumOperands() - 1;
183
14.0k
184
14.0k
    LLT OpTy = MRI.getType(MI.getOperand(NumDefs).getReg());
185
14.0k
    LLT DestTy = MRI.getType(MI.getOperand(0).getReg());
186
14.0k
187
14.0k
    unsigned MergingOpcode = getMergeOpcode(OpTy, DestTy);
188
14.0k
    MachineInstr *MergeI =
189
14.0k
        getOpcodeDef(MergingOpcode, MI.getOperand(NumDefs).getReg(), MRI);
190
14.0k
191
14.0k
    if (!MergeI)
192
8.04k
      return false;
193
5.98k
194
5.98k
    const unsigned NumMergeRegs = MergeI->getNumOperands() - 1;
195
5.98k
196
5.98k
    if (NumMergeRegs < NumDefs) {
197
11
      if (NumDefs % NumMergeRegs != 0)
198
0
        return false;
199
11
200
11
      Builder.setInstr(MI);
201
11
      // Transform to UNMERGEs, for example
202
11
      //   %1 = G_MERGE_VALUES %4, %5
203
11
      //   %9, %10, %11, %12 = G_UNMERGE_VALUES %1
204
11
      // to
205
11
      //   %9, %10 = G_UNMERGE_VALUES %4
206
11
      //   %11, %12 = G_UNMERGE_VALUES %5
207
11
208
11
      const unsigned NewNumDefs = NumDefs / NumMergeRegs;
209
33
      for (unsigned Idx = 0; Idx < NumMergeRegs; 
++Idx22
) {
210
22
        SmallVector<unsigned, 2> DstRegs;
211
70
        for (unsigned j = 0, DefIdx = Idx * NewNumDefs; j < NewNumDefs;
212
48
             ++j, ++DefIdx)
213
48
          DstRegs.push_back(MI.getOperand(DefIdx).getReg());
214
22
215
22
        Builder.buildUnmerge(DstRegs, MergeI->getOperand(Idx + 1).getReg());
216
22
      }
217
11
218
5.97k
    } else if (NumMergeRegs > NumDefs) {
219
5
      if (NumMergeRegs % NumDefs != 0)
220
0
        return false;
221
5
222
5
      Builder.setInstr(MI);
223
5
      // Transform to MERGEs
224
5
      //   %6 = G_MERGE_VALUES %17, %18, %19, %20
225
5
      //   %7, %8 = G_UNMERGE_VALUES %6
226
5
      // to
227
5
      //   %7 = G_MERGE_VALUES %17, %18
228
5
      //   %8 = G_MERGE_VALUES %19, %20
229
5
230
5
      const unsigned NumRegs = NumMergeRegs / NumDefs;
231
15
      for (unsigned DefIdx = 0; DefIdx < NumDefs; 
++DefIdx10
) {
232
10
        SmallVector<unsigned, 2> Regs;
233
30
        for (unsigned j = 0, Idx = NumRegs * DefIdx + 1; j < NumRegs;
234
20
             ++j, ++Idx)
235
20
          Regs.push_back(MergeI->getOperand(Idx).getReg());
236
10
237
10
        Builder.buildMerge(MI.getOperand(DefIdx).getReg(), Regs);
238
10
      }
239
5
240
5.97k
    } else {
241
5.97k
      // FIXME: is a COPY appropriate if the types mismatch? We know both
242
5.97k
      // registers are allocatable by now.
243
5.97k
      if (MRI.getType(MI.getOperand(0).getReg()) !=
244
5.97k
          MRI.getType(MergeI->getOperand(1).getReg()))
245
0
        return false;
246
5.97k
247
18.3k
      
for (unsigned Idx = 0; 5.97k
Idx < NumDefs;
++Idx12.4k
)
248
12.4k
        MRI.replaceRegWith(MI.getOperand(Idx).getReg(),
249
12.4k
                           MergeI->getOperand(Idx + 1).getReg());
250
5.97k
    }
251
5.98k
252
5.98k
    markInstAndDefDead(MI, *MergeI, DeadInsts);
253
5.98k
    return true;
254
5.98k
  }
255
256
2.59k
  static bool isMergeLikeOpcode(unsigned Opc) {
257
2.59k
    switch (Opc) {
258
2.59k
    case TargetOpcode::G_MERGE_VALUES:
259
1.64k
    case TargetOpcode::G_BUILD_VECTOR:
260
1.64k
    case TargetOpcode::G_CONCAT_VECTORS:
261
1.64k
      return true;
262
1.64k
    default:
263
957
      return false;
264
2.59k
    }
265
2.59k
  }
266
267
  bool tryCombineExtract(MachineInstr &MI,
268
2.59k
                         SmallVectorImpl<MachineInstr *> &DeadInsts) {
269
2.59k
    assert(MI.getOpcode() == TargetOpcode::G_EXTRACT);
270
2.59k
271
2.59k
    // Try to use the source registers from a G_MERGE_VALUES
272
2.59k
    //
273
2.59k
    // %2 = G_MERGE_VALUES %0, %1
274
2.59k
    // %3 = G_EXTRACT %2, N
275
2.59k
    // =>
276
2.59k
    //
277
2.59k
    // for N < %2.getSizeInBits() / 2
278
2.59k
    //     %3 = G_EXTRACT %0, N
279
2.59k
    //
280
2.59k
    // for N >= %2.getSizeInBits() / 2
281
2.59k
    //    %3 = G_EXTRACT %1, (N - %0.getSizeInBits()
282
2.59k
283
2.59k
    unsigned Src = lookThroughCopyInstrs(MI.getOperand(1).getReg());
284
2.59k
    MachineInstr *MergeI = MRI.getVRegDef(Src);
285
2.59k
    if (!MergeI || !isMergeLikeOpcode(MergeI->getOpcode()))
286
957
      return false;
287
1.64k
288
1.64k
    LLT DstTy = MRI.getType(MI.getOperand(0).getReg());
289
1.64k
    LLT SrcTy = MRI.getType(Src);
290
1.64k
291
1.64k
    // TODO: Do we need to check if the resulting extract is supported?
292
1.64k
    unsigned ExtractDstSize = DstTy.getSizeInBits();
293
1.64k
    unsigned Offset = MI.getOperand(2).getImm();
294
1.64k
    unsigned NumMergeSrcs = MergeI->getNumOperands() - 1;
295
1.64k
    unsigned MergeSrcSize = SrcTy.getSizeInBits() / NumMergeSrcs;
296
1.64k
    unsigned MergeSrcIdx = Offset / MergeSrcSize;
297
1.64k
298
1.64k
    // Compute the offset of the last bit the extract needs.
299
1.64k
    unsigned EndMergeSrcIdx = (Offset + ExtractDstSize - 1) / MergeSrcSize;
300
1.64k
301
1.64k
    // Can't handle the case where the extract spans multiple inputs.
302
1.64k
    if (MergeSrcIdx != EndMergeSrcIdx)
303
10
      return false;
304
1.63k
305
1.63k
    // TODO: We could modify MI in place in most cases.
306
1.63k
    Builder.setInstr(MI);
307
1.63k
    Builder.buildExtract(
308
1.63k
      MI.getOperand(0).getReg(),
309
1.63k
      MergeI->getOperand(MergeSrcIdx + 1).getReg(),
310
1.63k
      Offset - MergeSrcIdx * MergeSrcSize);
311
1.63k
    markInstAndDefDead(MI, *MergeI, DeadInsts);
312
1.63k
    return true;
313
1.63k
  }
314
315
  /// Try to combine away MI.
316
  /// Returns true if it combined away the MI.
317
  /// Adds instructions that are dead as a result of the combine
318
  /// into DeadInsts, which can include MI.
319
  bool tryCombineInstruction(MachineInstr &MI,
320
3.40M
                             SmallVectorImpl<MachineInstr *> &DeadInsts) {
321
3.40M
    switch (MI.getOpcode()) {
322
3.40M
    default:
323
1.27M
      return false;
324
3.40M
    case TargetOpcode::G_ANYEXT:
325
245k
      return tryCombineAnyExt(MI, DeadInsts);
326
3.40M
    case TargetOpcode::G_ZEXT:
327
315k
      return tryCombineZExt(MI, DeadInsts);
328
3.40M
    case TargetOpcode::G_SEXT:
329
154k
      return tryCombineSExt(MI, DeadInsts);
330
3.40M
    case TargetOpcode::G_UNMERGE_VALUES:
331
14.0k
      return tryCombineMerges(MI, DeadInsts);
332
3.40M
    case TargetOpcode::G_EXTRACT:
333
2.59k
      return tryCombineExtract(MI, DeadInsts);
334
3.40M
    case TargetOpcode::G_TRUNC: {
335
1.39M
      bool Changed = false;
336
1.39M
      for (auto &Use : MRI.use_instructions(MI.getOperand(0).getReg()))
337
1.59M
        Changed |= tryCombineInstruction(Use, DeadInsts);
338
1.39M
      return Changed;
339
3.40M
    }
340
3.40M
    }
341
3.40M
  }
342
343
private:
344
345
399k
  static unsigned getArtifactSrcReg(const MachineInstr &MI) {
346
399k
    switch (MI.getOpcode()) {
347
399k
    case TargetOpcode::COPY:
348
397k
    case TargetOpcode::G_TRUNC:
349
397k
    case TargetOpcode::G_ZEXT:
350
397k
    case TargetOpcode::G_ANYEXT:
351
397k
    case TargetOpcode::G_SEXT:
352
397k
    case TargetOpcode::G_UNMERGE_VALUES:
353
397k
      return MI.getOperand(MI.getNumOperands() - 1).getReg();
354
397k
    case TargetOpcode::G_EXTRACT:
355
1.63k
      return MI.getOperand(1).getReg();
356
397k
    default:
357
0
      llvm_unreachable("Not a legalization artifact happen");
358
399k
    }
359
399k
  }
360
361
  /// Mark MI as dead. If a def of one of MI's operands, DefMI, would also be
362
  /// dead due to MI being killed, then mark DefMI as dead too.
363
  /// Some of the combines (extends(trunc)), try to walk through redundant
364
  /// copies in between the extends and the truncs, and this attempts to collect
365
  /// the in between copies if they're dead.
366
  void markInstAndDefDead(MachineInstr &MI, MachineInstr &DefMI,
367
397k
                          SmallVectorImpl<MachineInstr *> &DeadInsts) {
368
397k
    DeadInsts.push_back(&MI);
369
397k
370
397k
    // Collect all the copy instructions that are made dead, due to deleting
371
397k
    // this instruction. Collect all of them until the Trunc(DefMI).
372
397k
    // Eg,
373
397k
    // %1(s1) = G_TRUNC %0(s32)
374
397k
    // %2(s1) = COPY %1(s1)
375
397k
    // %3(s1) = COPY %2(s1)
376
397k
    // %4(s32) = G_ANYEXT %3(s1)
377
397k
    // In this case, we would have replaced %4 with a copy of %0,
378
397k
    // and as a result, %3, %2, %1 are dead.
379
397k
    MachineInstr *PrevMI = &MI;
380
627k
    while (PrevMI != &DefMI) {
381
399k
      unsigned PrevRegSrc = getArtifactSrcReg(*PrevMI);
382
399k
383
399k
      MachineInstr *TmpDef = MRI.getVRegDef(PrevRegSrc);
384
399k
      if (MRI.hasOneUse(PrevRegSrc)) {
385
229k
        if (TmpDef != &DefMI) {
386
1.51k
          assert(TmpDef->getOpcode() == TargetOpcode::COPY &&
387
1.51k
                 "Expecting copy here");
388
1.51k
          DeadInsts.push_back(TmpDef);
389
1.51k
        }
390
229k
      } else
391
169k
        break;
392
229k
      PrevMI = TmpDef;
393
229k
    }
394
397k
    if (PrevMI == &DefMI && 
MRI.hasOneUse(DefMI.getOperand(0).getReg())228k
)
395
228k
      DeadInsts.push_back(&DefMI);
396
397k
  }
397
398
  /// Checks if the target legalizer info has specified anything about the
399
  /// instruction, or if unsupported.
400
388k
  bool isInstUnsupported(const LegalityQuery &Query) const {
401
388k
    using namespace LegalizeActions;
402
388k
    auto Step = LI.getAction(Query);
403
388k
    return Step.Action == Unsupported || Step.Action == NotFound;
404
388k
  }
405
406
181k
  bool isConstantUnsupported(LLT Ty) const {
407
181k
    if (!Ty.isVector())
408
180k
      return isInstUnsupported({TargetOpcode::G_CONSTANT, {Ty}});
409
11
410
11
    LLT EltTy = Ty.getElementType();
411
11
    return isInstUnsupported({TargetOpcode::G_CONSTANT, {EltTy}}) ||
412
11
           isInstUnsupported({TargetOpcode::G_BUILD_VECTOR, {Ty, EltTy}});
413
11
  }
414
415
  /// Looks through copy instructions and returns the actual
416
  /// source register.
417
719k
  unsigned lookThroughCopyInstrs(unsigned Reg) {
418
719k
    unsigned TmpReg;
419
720k
    while (mi_match(Reg, MRI, m_Copy(m_Reg(TmpReg)))) {
420
63.9k
      if (MRI.getType(TmpReg).isValid())
421
1.75k
        Reg = TmpReg;
422
62.1k
      else
423
62.1k
        break;
424
63.9k
    }
425
719k
    return Reg;
426
719k
  }
427
};
428
429
} // namespace llvm