Coverage Report

Created: 2018-11-12 17:33

/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 --===========//
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
// This file contains some helper functions which try to cleanup artifacts
10
// such as G_TRUNCs/G_[ZSA]EXTENDS that were created during legalization to make
11
// the types match. This file also contains some combines of merges that happens
12
// at the end of the legalization.
13
//===----------------------------------------------------------------------===//
14
15
#include "llvm/CodeGen/GlobalISel/Legalizer.h"
16
#include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
17
#include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
18
#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
19
#include "llvm/CodeGen/GlobalISel/Utils.h"
20
#include "llvm/CodeGen/MachineRegisterInfo.h"
21
#include "llvm/Support/Debug.h"
22
23
#define DEBUG_TYPE "legalizer"
24
using namespace llvm::MIPatternMatch;
25
26
namespace llvm {
27
class LegalizationArtifactCombiner {
28
  MachineIRBuilder &Builder;
29
  MachineRegisterInfo &MRI;
30
  const LegalizerInfo &LI;
31
32
public:
33
  LegalizationArtifactCombiner(MachineIRBuilder &B, MachineRegisterInfo &MRI,
34
                    const LegalizerInfo &LI)
35
234k
      : Builder(B), MRI(MRI), LI(LI) {}
36
37
  bool tryCombineAnyExt(MachineInstr &MI,
38
227k
                        SmallVectorImpl<MachineInstr *> &DeadInsts) {
39
227k
    if (MI.getOpcode() != TargetOpcode::G_ANYEXT)
40
0
      return false;
41
227k
42
227k
    Builder.setInstr(MI);
43
227k
    unsigned DstReg = MI.getOperand(0).getReg();
44
227k
    unsigned SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
45
227k
46
227k
    // aext(trunc x) - > aext/copy/trunc x
47
227k
    unsigned TruncSrc;
48
227k
    if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
49
191k
      LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
50
191k
      Builder.buildAnyExtOrTrunc(DstReg, TruncSrc);
51
191k
      markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
52
191k
      return true;
53
191k
    }
54
35.4k
    return tryFoldImplicitDef(MI, DeadInsts);
55
35.4k
  }
56
57
  bool tryCombineZExt(MachineInstr &MI,
58
311k
                      SmallVectorImpl<MachineInstr *> &DeadInsts) {
59
311k
60
311k
    if (MI.getOpcode() != TargetOpcode::G_ZEXT)
61
0
      return false;
62
311k
63
311k
    Builder.setInstr(MI);
64
311k
    unsigned DstReg = MI.getOperand(0).getReg();
65
311k
    unsigned SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
66
311k
67
311k
    // zext(trunc x) - > and (aext/copy/trunc x), mask
68
311k
    unsigned TruncSrc;
69
311k
    if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
70
152k
      LLT DstTy = MRI.getType(DstReg);
71
152k
      if (isInstUnsupported({TargetOpcode::G_AND, {DstTy}}) ||
72
152k
          isInstUnsupported({TargetOpcode::G_CONSTANT, {DstTy}}))
73
0
        return false;
74
152k
      LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
75
152k
      LLT SrcTy = MRI.getType(SrcReg);
76
152k
      APInt Mask = APInt::getAllOnesValue(SrcTy.getSizeInBits());
77
152k
      auto MIBMask = Builder.buildConstant(DstTy, Mask.getZExtValue());
78
152k
      Builder.buildAnd(DstReg, Builder.buildAnyExtOrTrunc(DstTy, TruncSrc),
79
152k
                       MIBMask);
80
152k
      markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
81
152k
      return true;
82
152k
    }
83
158k
    return tryFoldImplicitDef(MI, DeadInsts);
84
158k
  }
85
86
  bool tryCombineSExt(MachineInstr &MI,
87
136k
                      SmallVectorImpl<MachineInstr *> &DeadInsts) {
88
136k
89
136k
    if (MI.getOpcode() != TargetOpcode::G_SEXT)
90
0
      return false;
91
136k
92
136k
    Builder.setInstr(MI);
93
136k
    unsigned DstReg = MI.getOperand(0).getReg();
94
136k
    unsigned SrcReg = lookThroughCopyInstrs(MI.getOperand(1).getReg());
95
136k
96
136k
    // sext(trunc x) - > ashr (shl (aext/copy/trunc x), c), c
97
136k
    unsigned TruncSrc;
98
136k
    if (mi_match(SrcReg, MRI, m_GTrunc(m_Reg(TruncSrc)))) {
99
22.6k
      LLT DstTy = MRI.getType(DstReg);
100
22.6k
      if (isInstUnsupported({TargetOpcode::G_SHL, {DstTy}}) ||
101
22.6k
          isInstUnsupported({TargetOpcode::G_ASHR, {DstTy}}) ||
102
22.6k
          isInstUnsupported({TargetOpcode::G_CONSTANT, {DstTy}}))
103
0
        return false;
104
22.6k
      LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
105
22.6k
      LLT SrcTy = MRI.getType(SrcReg);
106
22.6k
      unsigned ShAmt = DstTy.getSizeInBits() - SrcTy.getSizeInBits();
107
22.6k
      auto MIBShAmt = Builder.buildConstant(DstTy, ShAmt);
108
22.6k
      auto MIBShl = Builder.buildInstr(
109
22.6k
          TargetOpcode::G_SHL, DstTy,
110
22.6k
          Builder.buildAnyExtOrTrunc(DstTy, TruncSrc), MIBShAmt);
111
22.6k
      Builder.buildInstr(TargetOpcode::G_ASHR, DstReg, MIBShl, MIBShAmt);
112
22.6k
      markInstAndDefDead(MI, *MRI.getVRegDef(SrcReg), DeadInsts);
113
22.6k
      return true;
114
22.6k
    }
115
113k
    return tryFoldImplicitDef(MI, DeadInsts);
116
113k
  }
117
118
  /// Try to fold G_[ASZ]EXT (G_IMPLICIT_DEF).
119
  bool tryFoldImplicitDef(MachineInstr &MI,
120
307k
                          SmallVectorImpl<MachineInstr *> &DeadInsts) {
121
307k
    unsigned Opcode = MI.getOpcode();
122
307k
    if (Opcode != TargetOpcode::G_ANYEXT && 
Opcode != TargetOpcode::G_ZEXT272k
&&
123
307k
        
Opcode != TargetOpcode::G_SEXT113k
)
124
0
      return false;
125
307k
126
307k
    if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF,
127
16
                                           MI.getOperand(1).getReg(), MRI)) {
128
16
      Builder.setInstr(MI);
129
16
      unsigned DstReg = MI.getOperand(0).getReg();
130
16
      LLT DstTy = MRI.getType(DstReg);
131
16
132
16
      if (Opcode == TargetOpcode::G_ANYEXT) {
133
6
        // G_ANYEXT (G_IMPLICIT_DEF) -> G_IMPLICIT_DEF
134
6
        if (isInstUnsupported({TargetOpcode::G_IMPLICIT_DEF, {DstTy}}))
135
0
          return false;
136
6
        LLVM_DEBUG(dbgs() << ".. Combine G_ANYEXT(G_IMPLICIT_DEF): " << MI;);
137
6
        Builder.buildInstr(TargetOpcode::G_IMPLICIT_DEF, DstReg);
138
10
      } else {
139
10
        // G_[SZ]EXT (G_IMPLICIT_DEF) -> G_CONSTANT 0 because the top
140
10
        // bits will be 0 for G_ZEXT and 0/1 for the G_SEXT.
141
10
        if (isInstUnsupported({TargetOpcode::G_CONSTANT, {DstTy}}))
142
0
          return false;
143
10
        LLVM_DEBUG(dbgs() << ".. Combine G_[SZ]EXT(G_IMPLICIT_DEF): " << MI;);
144
10
        Builder.buildConstant(DstReg, 0);
145
10
      }
146
16
147
16
      markInstAndDefDead(MI, *DefMI, DeadInsts);
148
16
      return true;
149
307k
    }
150
307k
    return false;
151
307k
  }
152
153
  bool tryCombineMerges(MachineInstr &MI,
154
2.83k
                        SmallVectorImpl<MachineInstr *> &DeadInsts) {
155
2.83k
156
2.83k
    if (MI.getOpcode() != TargetOpcode::G_UNMERGE_VALUES)
157
0
      return false;
158
2.83k
159
2.83k
    unsigned NumDefs = MI.getNumOperands() - 1;
160
2.83k
    MachineInstr *MergeI = getOpcodeDef(TargetOpcode::G_MERGE_VALUES,
161
2.83k
                                        MI.getOperand(NumDefs).getReg(), MRI);
162
2.83k
    if (!MergeI)
163
299
      return false;
164
2.53k
165
2.53k
    const unsigned NumMergeRegs = MergeI->getNumOperands() - 1;
166
2.53k
167
2.53k
    if (NumMergeRegs < NumDefs) {
168
10
      if (NumDefs % NumMergeRegs != 0)
169
0
        return false;
170
10
171
10
      Builder.setInstr(MI);
172
10
      // Transform to UNMERGEs, for example
173
10
      //   %1 = G_MERGE_VALUES %4, %5
174
10
      //   %9, %10, %11, %12 = G_UNMERGE_VALUES %1
175
10
      // to
176
10
      //   %9, %10 = G_UNMERGE_VALUES %4
177
10
      //   %11, %12 = G_UNMERGE_VALUES %5
178
10
179
10
      const unsigned NewNumDefs = NumDefs / NumMergeRegs;
180
30
      for (unsigned Idx = 0; Idx < NumMergeRegs; 
++Idx20
) {
181
20
        SmallVector<unsigned, 2> DstRegs;
182
60
        for (unsigned j = 0, DefIdx = Idx * NewNumDefs; j < NewNumDefs;
183
40
             ++j, ++DefIdx)
184
40
          DstRegs.push_back(MI.getOperand(DefIdx).getReg());
185
20
186
20
        Builder.buildUnmerge(DstRegs, MergeI->getOperand(Idx + 1).getReg());
187
20
      }
188
10
189
2.52k
    } else if (NumMergeRegs > NumDefs) {
190
91
      if (NumMergeRegs % NumDefs != 0)
191
0
        return false;
192
91
193
91
      Builder.setInstr(MI);
194
91
      // Transform to MERGEs
195
91
      //   %6 = G_MERGE_VALUES %17, %18, %19, %20
196
91
      //   %7, %8 = G_UNMERGE_VALUES %6
197
91
      // to
198
91
      //   %7 = G_MERGE_VALUES %17, %18
199
91
      //   %8 = G_MERGE_VALUES %19, %20
200
91
201
91
      const unsigned NumRegs = NumMergeRegs / NumDefs;
202
273
      for (unsigned DefIdx = 0; DefIdx < NumDefs; 
++DefIdx182
) {
203
182
        SmallVector<unsigned, 2> Regs;
204
546
        for (unsigned j = 0, Idx = NumRegs * DefIdx + 1; j < NumRegs;
205
364
             ++j, ++Idx)
206
364
          Regs.push_back(MergeI->getOperand(Idx).getReg());
207
182
208
182
        Builder.buildMerge(MI.getOperand(DefIdx).getReg(), Regs);
209
182
      }
210
91
211
2.43k
    } else {
212
2.43k
      // FIXME: is a COPY appropriate if the types mismatch? We know both
213
2.43k
      // registers are allocatable by now.
214
2.43k
      if (MRI.getType(MI.getOperand(0).getReg()) !=
215
2.43k
          MRI.getType(MergeI->getOperand(1).getReg()))
216
0
        return false;
217
2.43k
218
8.16k
      
for (unsigned Idx = 0; 2.43k
Idx < NumDefs;
++Idx5.73k
)
219
5.73k
        MRI.replaceRegWith(MI.getOperand(Idx).getReg(),
220
5.73k
                           MergeI->getOperand(Idx + 1).getReg());
221
2.43k
    }
222
2.53k
223
2.53k
    markInstAndDefDead(MI, *MergeI, DeadInsts);
224
2.53k
    return true;
225
2.53k
  }
226
227
  /// Try to combine away MI.
228
  /// Returns true if it combined away the MI.
229
  /// Adds instructions that are dead as a result of the combine
230
  /// into DeadInsts, which can include MI.
231
  bool tryCombineInstruction(MachineInstr &MI,
232
3.00M
                             SmallVectorImpl<MachineInstr *> &DeadInsts) {
233
3.00M
    switch (MI.getOpcode()) {
234
3.00M
    default:
235
1.09M
      return false;
236
3.00M
    case TargetOpcode::G_ANYEXT:
237
227k
      return tryCombineAnyExt(MI, DeadInsts);
238
3.00M
    case TargetOpcode::G_ZEXT:
239
311k
      return tryCombineZExt(MI, DeadInsts);
240
3.00M
    case TargetOpcode::G_SEXT:
241
136k
      return tryCombineSExt(MI, DeadInsts);
242
3.00M
    case TargetOpcode::G_UNMERGE_VALUES:
243
2.83k
      return tryCombineMerges(MI, DeadInsts);
244
3.00M
    case TargetOpcode::G_TRUNC: {
245
1.23M
      bool Changed = false;
246
1.23M
      for (auto &Use : MRI.use_instructions(MI.getOperand(0).getReg()))
247
1.40M
        Changed |= tryCombineInstruction(Use, DeadInsts);
248
1.23M
      return Changed;
249
3.00M
    }
250
3.00M
    }
251
3.00M
  }
252
253
private:
254
  /// Mark MI as dead. If a def of one of MI's operands, DefMI, would also be
255
  /// dead due to MI being killed, then mark DefMI as dead too.
256
  /// Some of the combines (extends(trunc)), try to walk through redundant
257
  /// copies in between the extends and the truncs, and this attempts to collect
258
  /// the in between copies if they're dead.
259
  void markInstAndDefDead(MachineInstr &MI, MachineInstr &DefMI,
260
369k
                          SmallVectorImpl<MachineInstr *> &DeadInsts) {
261
369k
    DeadInsts.push_back(&MI);
262
369k
263
369k
    // Collect all the copy instructions that are made dead, due to deleting
264
369k
    // this instruction. Collect all of them until the Trunc(DefMI).
265
369k
    // Eg,
266
369k
    // %1(s1) = G_TRUNC %0(s32)
267
369k
    // %2(s1) = COPY %1(s1)
268
369k
    // %3(s1) = COPY %2(s1)
269
369k
    // %4(s32) = G_ANYEXT %3(s1)
270
369k
    // In this case, we would have replaced %4 with a copy of %0,
271
369k
    // and as a result, %3, %2, %1 are dead.
272
369k
    MachineInstr *PrevMI = &MI;
273
573k
    while (PrevMI != &DefMI) {
274
370k
      unsigned PrevRegSrc =
275
370k
          PrevMI->getOperand(PrevMI->getNumOperands() - 1).getReg();
276
370k
      MachineInstr *TmpDef = MRI.getVRegDef(PrevRegSrc);
277
370k
      if (MRI.hasOneUse(PrevRegSrc)) {
278
203k
        if (TmpDef != &DefMI) {
279
1.24k
          assert(TmpDef->getOpcode() == TargetOpcode::COPY &&
280
1.24k
                 "Expecting copy here");
281
1.24k
          DeadInsts.push_back(TmpDef);
282
1.24k
        }
283
203k
      } else
284
167k
        break;
285
203k
      PrevMI = TmpDef;
286
203k
    }
287
369k
    if (PrevMI == &DefMI && 
MRI.hasOneUse(DefMI.getOperand(0).getReg())202k
)
288
202k
      DeadInsts.push_back(&DefMI);
289
369k
  }
290
291
  /// Checks if the target legalizer info has specified anything about the
292
  /// instruction, or if unsupported.
293
372k
  bool isInstUnsupported(const LegalityQuery &Query) const {
294
372k
    using namespace LegalizeActions;
295
372k
    auto Step = LI.getAction(Query);
296
372k
    return Step.Action == Unsupported || Step.Action == NotFound;
297
372k
  }
298
299
  /// Looks through copy instructions and returns the actual
300
  /// source register.
301
674k
  unsigned lookThroughCopyInstrs(unsigned Reg) {
302
674k
    unsigned TmpReg;
303
675k
    while (mi_match(Reg, MRI, m_Copy(m_Reg(TmpReg)))) {
304
61.2k
      if (MRI.getType(TmpReg).isValid())
305
1.12k
        Reg = TmpReg;
306
60.1k
      else
307
60.1k
        break;
308
61.2k
    }
309
674k
    return Reg;
310
674k
  }
311
};
312
313
} // namespace llvm