Coverage Report

Created: 2018-09-23 16:00

/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/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
24
namespace llvm {
25
class LegalizationArtifactCombiner {
26
  MachineIRBuilder &Builder;
27
  MachineRegisterInfo &MRI;
28
  const LegalizerInfo &LI;
29
30
public:
31
  LegalizationArtifactCombiner(MachineIRBuilder &B, MachineRegisterInfo &MRI,
32
                    const LegalizerInfo &LI)
33
234k
      : Builder(B), MRI(MRI), LI(LI) {}
34
35
  bool tryCombineAnyExt(MachineInstr &MI,
36
232k
                        SmallVectorImpl<MachineInstr *> &DeadInsts) {
37
232k
    if (MI.getOpcode() != TargetOpcode::G_ANYEXT)
38
0
      return false;
39
232k
    if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_TRUNC,
40
194k
                                           MI.getOperand(1).getReg(), MRI)) {
41
194k
      LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
42
194k
      unsigned DstReg = MI.getOperand(0).getReg();
43
194k
      unsigned SrcReg = DefMI->getOperand(1).getReg();
44
194k
      Builder.setInstr(MI);
45
194k
      // We get a copy/trunc/extend depending on the sizes
46
194k
      Builder.buildAnyExtOrTrunc(DstReg, SrcReg);
47
194k
      markInstAndDefDead(MI, *DefMI, DeadInsts);
48
194k
      return true;
49
194k
    }
50
38.1k
    return tryFoldImplicitDef(MI, DeadInsts);
51
38.1k
  }
52
53
  bool tryCombineZExt(MachineInstr &MI,
54
332k
                      SmallVectorImpl<MachineInstr *> &DeadInsts) {
55
332k
56
332k
    if (MI.getOpcode() != TargetOpcode::G_ZEXT)
57
0
      return false;
58
332k
    if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_TRUNC,
59
145k
                                           MI.getOperand(1).getReg(), MRI)) {
60
145k
      unsigned DstReg = MI.getOperand(0).getReg();
61
145k
      LLT DstTy = MRI.getType(DstReg);
62
145k
      if (isInstUnsupported({TargetOpcode::G_AND, {DstTy}}) ||
63
145k
          isInstUnsupported({TargetOpcode::G_CONSTANT, {DstTy}}))
64
0
        return false;
65
145k
      LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
66
145k
      Builder.setInstr(MI);
67
145k
      unsigned ZExtSrc = MI.getOperand(1).getReg();
68
145k
      LLT ZExtSrcTy = MRI.getType(ZExtSrc);
69
145k
      APInt Mask = APInt::getAllOnesValue(ZExtSrcTy.getSizeInBits());
70
145k
      auto MaskCstMIB = Builder.buildConstant(DstTy, Mask.getZExtValue());
71
145k
      unsigned TruncSrc = DefMI->getOperand(1).getReg();
72
145k
      // We get a copy/trunc/extend depending on the sizes
73
145k
      auto SrcCopyOrTrunc = Builder.buildAnyExtOrTrunc(DstTy, TruncSrc);
74
145k
      Builder.buildAnd(DstReg, SrcCopyOrTrunc, MaskCstMIB);
75
145k
      markInstAndDefDead(MI, *DefMI, DeadInsts);
76
145k
      return true;
77
145k
    }
78
187k
    return tryFoldImplicitDef(MI, DeadInsts);
79
187k
  }
80
81
  bool tryCombineSExt(MachineInstr &MI,
82
144k
                      SmallVectorImpl<MachineInstr *> &DeadInsts) {
83
144k
84
144k
    if (MI.getOpcode() != TargetOpcode::G_SEXT)
85
0
      return false;
86
144k
    if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_TRUNC,
87
20.4k
                                           MI.getOperand(1).getReg(), MRI)) {
88
20.4k
      unsigned DstReg = MI.getOperand(0).getReg();
89
20.4k
      LLT DstTy = MRI.getType(DstReg);
90
20.4k
      if (isInstUnsupported({TargetOpcode::G_SHL, {DstTy}}) ||
91
20.4k
          isInstUnsupported({TargetOpcode::G_ASHR, {DstTy}}) ||
92
20.4k
          isInstUnsupported({TargetOpcode::G_CONSTANT, {DstTy}}))
93
0
        return false;
94
20.4k
      LLVM_DEBUG(dbgs() << ".. Combine MI: " << MI;);
95
20.4k
      Builder.setInstr(MI);
96
20.4k
      unsigned SExtSrc = MI.getOperand(1).getReg();
97
20.4k
      LLT SExtSrcTy = MRI.getType(SExtSrc);
98
20.4k
      unsigned SizeDiff = DstTy.getSizeInBits() - SExtSrcTy.getSizeInBits();
99
20.4k
      auto SizeDiffMIB = Builder.buildConstant(DstTy, SizeDiff);
100
20.4k
      unsigned TruncSrcReg = DefMI->getOperand(1).getReg();
101
20.4k
      // We get a copy/trunc/extend depending on the sizes
102
20.4k
      auto SrcCopyExtOrTrunc = Builder.buildAnyExtOrTrunc(DstTy, TruncSrcReg);
103
20.4k
      auto ShlMIB = Builder.buildInstr(TargetOpcode::G_SHL, DstTy,
104
20.4k
                                       SrcCopyExtOrTrunc, SizeDiffMIB);
105
20.4k
      Builder.buildInstr(TargetOpcode::G_ASHR, DstReg, ShlMIB, SizeDiffMIB);
106
20.4k
      markInstAndDefDead(MI, *DefMI, DeadInsts);
107
20.4k
      return true;
108
20.4k
    }
109
124k
    return tryFoldImplicitDef(MI, DeadInsts);
110
124k
  }
111
112
  /// Try to fold sb = EXTEND (G_IMPLICIT_DEF sa) -> sb = G_IMPLICIT_DEF
113
  bool tryFoldImplicitDef(MachineInstr &MI,
114
349k
                          SmallVectorImpl<MachineInstr *> &DeadInsts) {
115
349k
    unsigned Opcode = MI.getOpcode();
116
349k
    if (Opcode != TargetOpcode::G_ANYEXT && 
Opcode != TargetOpcode::G_ZEXT311k
&&
117
349k
        
Opcode != TargetOpcode::G_SEXT124k
)
118
0
      return false;
119
349k
120
349k
    if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF,
121
13
                                           MI.getOperand(1).getReg(), MRI)) {
122
13
      unsigned DstReg = MI.getOperand(0).getReg();
123
13
      LLT DstTy = MRI.getType(DstReg);
124
13
      if (isInstUnsupported({TargetOpcode::G_IMPLICIT_DEF, {DstTy}}))
125
0
        return false;
126
13
      LLVM_DEBUG(dbgs() << ".. Combine EXT(IMPLICIT_DEF) " << MI;);
127
13
      Builder.setInstr(MI);
128
13
      Builder.buildInstr(TargetOpcode::G_IMPLICIT_DEF, DstReg);
129
13
      markInstAndDefDead(MI, *DefMI, DeadInsts);
130
13
      return true;
131
13
    }
132
349k
    return false;
133
349k
  }
134
135
  bool tryCombineMerges(MachineInstr &MI,
136
3.39k
                        SmallVectorImpl<MachineInstr *> &DeadInsts) {
137
3.39k
138
3.39k
    if (MI.getOpcode() != TargetOpcode::G_UNMERGE_VALUES)
139
0
      return false;
140
3.39k
141
3.39k
    unsigned NumDefs = MI.getNumOperands() - 1;
142
3.39k
    MachineInstr *MergeI = getOpcodeDef(TargetOpcode::G_MERGE_VALUES,
143
3.39k
                                        MI.getOperand(NumDefs).getReg(), MRI);
144
3.39k
    if (!MergeI)
145
185
      return false;
146
3.21k
147
3.21k
    const unsigned NumMergeRegs = MergeI->getNumOperands() - 1;
148
3.21k
149
3.21k
    if (NumMergeRegs < NumDefs) {
150
10
      if (NumDefs % NumMergeRegs != 0)
151
0
        return false;
152
10
153
10
      Builder.setInstr(MI);
154
10
      // Transform to UNMERGEs, for example
155
10
      //   %1 = G_MERGE_VALUES %4, %5
156
10
      //   %9, %10, %11, %12 = G_UNMERGE_VALUES %1
157
10
      // to
158
10
      //   %9, %10 = G_UNMERGE_VALUES %4
159
10
      //   %11, %12 = G_UNMERGE_VALUES %5
160
10
161
10
      const unsigned NewNumDefs = NumDefs / NumMergeRegs;
162
30
      for (unsigned Idx = 0; Idx < NumMergeRegs; 
++Idx20
) {
163
20
        SmallVector<unsigned, 2> DstRegs;
164
60
        for (unsigned j = 0, DefIdx = Idx * NewNumDefs; j < NewNumDefs;
165
40
             ++j, ++DefIdx)
166
40
          DstRegs.push_back(MI.getOperand(DefIdx).getReg());
167
20
168
20
        Builder.buildUnmerge(DstRegs, MergeI->getOperand(Idx + 1).getReg());
169
20
      }
170
10
171
3.20k
    } else if (NumMergeRegs > NumDefs) {
172
91
      if (NumMergeRegs % NumDefs != 0)
173
0
        return false;
174
91
175
91
      Builder.setInstr(MI);
176
91
      // Transform to MERGEs
177
91
      //   %6 = G_MERGE_VALUES %17, %18, %19, %20
178
91
      //   %7, %8 = G_UNMERGE_VALUES %6
179
91
      // to
180
91
      //   %7 = G_MERGE_VALUES %17, %18
181
91
      //   %8 = G_MERGE_VALUES %19, %20
182
91
183
91
      const unsigned NumRegs = NumMergeRegs / NumDefs;
184
273
      for (unsigned DefIdx = 0; DefIdx < NumDefs; 
++DefIdx182
) {
185
182
        SmallVector<unsigned, 2> Regs;
186
546
        for (unsigned j = 0, Idx = NumRegs * DefIdx + 1; j < NumRegs;
187
364
             ++j, ++Idx)
188
364
          Regs.push_back(MergeI->getOperand(Idx).getReg());
189
182
190
182
        Builder.buildMerge(MI.getOperand(DefIdx).getReg(), Regs);
191
182
      }
192
91
193
3.11k
    } else {
194
3.11k
      // FIXME: is a COPY appropriate if the types mismatch? We know both
195
3.11k
      // registers are allocatable by now.
196
3.11k
      if (MRI.getType(MI.getOperand(0).getReg()) !=
197
3.11k
          MRI.getType(MergeI->getOperand(1).getReg()))
198
0
        return false;
199
3.11k
200
10.2k
      
for (unsigned Idx = 0; 3.11k
Idx < NumDefs;
++Idx7.09k
)
201
7.09k
        MRI.replaceRegWith(MI.getOperand(Idx).getReg(),
202
7.09k
                           MergeI->getOperand(Idx + 1).getReg());
203
3.11k
    }
204
3.21k
205
3.21k
    markInstAndDefDead(MI, *MergeI, DeadInsts);
206
3.21k
    return true;
207
3.21k
  }
208
209
  /// Try to combine away MI.
210
  /// Returns true if it combined away the MI.
211
  /// Adds instructions that are dead as a result of the combine
212
  /// into DeadInsts, which can include MI.
213
  bool tryCombineInstruction(MachineInstr &MI,
214
2.98M
                             SmallVectorImpl<MachineInstr *> &DeadInsts) {
215
2.98M
    switch (MI.getOpcode()) {
216
2.98M
    default:
217
1.06M
      return false;
218
2.98M
    case TargetOpcode::G_ANYEXT:
219
232k
      return tryCombineAnyExt(MI, DeadInsts);
220
2.98M
    case TargetOpcode::G_ZEXT:
221
332k
      return tryCombineZExt(MI, DeadInsts);
222
2.98M
    case TargetOpcode::G_SEXT:
223
144k
      return tryCombineSExt(MI, DeadInsts);
224
2.98M
    case TargetOpcode::G_UNMERGE_VALUES:
225
3.39k
      return tryCombineMerges(MI, DeadInsts);
226
2.98M
    case TargetOpcode::G_TRUNC: {
227
1.20M
      bool Changed = false;
228
1.20M
      for (auto &Use : MRI.use_instructions(MI.getOperand(0).getReg()))
229
1.38M
        Changed |= tryCombineInstruction(Use, DeadInsts);
230
1.20M
      return Changed;
231
2.98M
    }
232
2.98M
    }
233
2.98M
  }
234
235
private:
236
  /// Mark MI as dead. If a def of one of MI's operands, DefMI, would also be
237
  /// dead due to MI being killed, then mark DefMI as dead too.
238
  /// Some of the combines (extends(trunc)), try to walk through redundant
239
  /// copies in between the extends and the truncs, and this attempts to collect
240
  /// the in between copies if they're dead.
241
  void markInstAndDefDead(MachineInstr &MI, MachineInstr &DefMI,
242
363k
                          SmallVectorImpl<MachineInstr *> &DeadInsts) {
243
363k
    DeadInsts.push_back(&MI);
244
363k
245
363k
    // Collect all the copy instructions that are made dead, due to deleting
246
363k
    // this instruction. Collect all of them until the Trunc(DefMI).
247
363k
    // Eg,
248
363k
    // %1(s1) = G_TRUNC %0(s32)
249
363k
    // %2(s1) = COPY %1(s1)
250
363k
    // %3(s1) = COPY %2(s1)
251
363k
    // %4(s32) = G_ANYEXT %3(s1)
252
363k
    // In this case, we would have replaced %4 with a copy of %0,
253
363k
    // and as a result, %3, %2, %1 are dead.
254
363k
    MachineInstr *PrevMI = &MI;
255
558k
    while (PrevMI != &DefMI) {
256
365k
      unsigned PrevRegSrc =
257
365k
          PrevMI->getOperand(PrevMI->getNumOperands() - 1).getReg();
258
365k
      MachineInstr *TmpDef = MRI.getVRegDef(PrevRegSrc);
259
365k
      if (MRI.hasOneUse(PrevRegSrc)) {
260
194k
        if (TmpDef != &DefMI) {
261
1.21k
          assert(TmpDef->getOpcode() == TargetOpcode::COPY &&
262
1.21k
                 "Expecting copy here");
263
1.21k
          DeadInsts.push_back(TmpDef);
264
1.21k
        }
265
194k
      } else
266
170k
        break;
267
194k
      PrevMI = TmpDef;
268
194k
    }
269
363k
    if (PrevMI == &DefMI && 
MRI.hasOneUse(DefMI.getOperand(0).getReg())193k
)
270
193k
      DeadInsts.push_back(&DefMI);
271
363k
  }
272
273
  /// Checks if the target legalizer info has specified anything about the
274
  /// instruction, or if unsupported.
275
352k
  bool isInstUnsupported(const LegalityQuery &Query) const {
276
352k
    using namespace LegalizeActions;
277
352k
    auto Step = LI.getAction(Query);
278
352k
    return Step.Action == Unsupported || Step.Action == NotFound;
279
352k
  }
280
};
281
282
} // namespace llvm