1 //===-- llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h --===========//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
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 //===----------------------------------------------------------------------===//
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"
22 #define DEBUG_TYPE "legalizer"
25 class LegalizationArtifactCombiner {
26 MachineIRBuilder &Builder;
27 MachineRegisterInfo &MRI;
28 const LegalizerInfo &LI;
31 LegalizationArtifactCombiner(MachineIRBuilder &B, MachineRegisterInfo &MRI,
32 const LegalizerInfo &LI)
33 : Builder(B), MRI(MRI), LI(LI) {}
35 bool tryCombineAnyExt(MachineInstr &MI,
36 SmallVectorImpl<MachineInstr *> &DeadInsts) {
37 if (MI.getOpcode() != TargetOpcode::G_ANYEXT)
39 if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_TRUNC,
40 MI.getOperand(1).getReg(), MRI)) {
41 DEBUG(dbgs() << ".. Combine MI: " << MI;);
42 unsigned DstReg = MI.getOperand(0).getReg();
43 unsigned SrcReg = DefMI->getOperand(1).getReg();
45 // We get a copy/trunc/extend depending on the sizes
46 Builder.buildAnyExtOrTrunc(DstReg, SrcReg);
47 markInstAndDefDead(MI, *DefMI, DeadInsts);
50 return tryFoldImplicitDef(MI, DeadInsts);
53 bool tryCombineZExt(MachineInstr &MI,
54 SmallVectorImpl<MachineInstr *> &DeadInsts) {
56 if (MI.getOpcode() != TargetOpcode::G_ZEXT)
58 if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_TRUNC,
59 MI.getOperand(1).getReg(), MRI)) {
60 unsigned DstReg = MI.getOperand(0).getReg();
61 LLT DstTy = MRI.getType(DstReg);
62 if (isInstUnsupported(TargetOpcode::G_AND, DstTy) ||
63 isInstUnsupported(TargetOpcode::G_CONSTANT, DstTy))
65 DEBUG(dbgs() << ".. Combine MI: " << MI;);
67 unsigned ZExtSrc = MI.getOperand(1).getReg();
68 LLT ZExtSrcTy = MRI.getType(ZExtSrc);
69 APInt Mask = APInt::getAllOnesValue(ZExtSrcTy.getSizeInBits());
70 auto MaskCstMIB = Builder.buildConstant(DstTy, Mask.getZExtValue());
71 unsigned TruncSrc = DefMI->getOperand(1).getReg();
72 // We get a copy/trunc/extend depending on the sizes
73 auto SrcCopyOrTrunc = Builder.buildAnyExtOrTrunc(DstTy, TruncSrc);
74 Builder.buildAnd(DstReg, SrcCopyOrTrunc, MaskCstMIB);
75 markInstAndDefDead(MI, *DefMI, DeadInsts);
78 return tryFoldImplicitDef(MI, DeadInsts);
81 bool tryCombineSExt(MachineInstr &MI,
82 SmallVectorImpl<MachineInstr *> &DeadInsts) {
84 if (MI.getOpcode() != TargetOpcode::G_SEXT)
86 if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_TRUNC,
87 MI.getOperand(1).getReg(), MRI)) {
88 unsigned DstReg = MI.getOperand(0).getReg();
89 LLT DstTy = MRI.getType(DstReg);
90 if (isInstUnsupported(TargetOpcode::G_SHL, DstTy) ||
91 isInstUnsupported(TargetOpcode::G_ASHR, DstTy) ||
92 isInstUnsupported(TargetOpcode::G_CONSTANT, DstTy))
94 DEBUG(dbgs() << ".. Combine MI: " << MI;);
96 unsigned SExtSrc = MI.getOperand(1).getReg();
97 LLT SExtSrcTy = MRI.getType(SExtSrc);
98 unsigned SizeDiff = DstTy.getSizeInBits() - SExtSrcTy.getSizeInBits();
99 auto SizeDiffMIB = Builder.buildConstant(DstTy, SizeDiff);
100 unsigned TruncSrcReg = DefMI->getOperand(1).getReg();
101 // We get a copy/trunc/extend depending on the sizes
102 auto SrcCopyExtOrTrunc = Builder.buildAnyExtOrTrunc(DstTy, TruncSrcReg);
103 auto ShlMIB = Builder.buildInstr(TargetOpcode::G_SHL, DstTy,
104 SrcCopyExtOrTrunc, SizeDiffMIB);
105 Builder.buildInstr(TargetOpcode::G_ASHR, DstReg, ShlMIB, SizeDiffMIB);
106 markInstAndDefDead(MI, *DefMI, DeadInsts);
109 return tryFoldImplicitDef(MI, DeadInsts);
112 /// Try to fold sb = EXTEND (G_IMPLICIT_DEF sa) -> sb = G_IMPLICIT_DEF
113 bool tryFoldImplicitDef(MachineInstr &MI,
114 SmallVectorImpl<MachineInstr *> &DeadInsts) {
115 unsigned Opcode = MI.getOpcode();
116 if (Opcode != TargetOpcode::G_ANYEXT && Opcode != TargetOpcode::G_ZEXT &&
117 Opcode != TargetOpcode::G_SEXT)
120 if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF,
121 MI.getOperand(1).getReg(), MRI)) {
122 unsigned DstReg = MI.getOperand(0).getReg();
123 LLT DstTy = MRI.getType(DstReg);
124 if (isInstUnsupported(TargetOpcode::G_IMPLICIT_DEF, DstTy))
126 DEBUG(dbgs() << ".. Combine EXT(IMPLICIT_DEF) " << MI;);
127 Builder.setInstr(MI);
128 Builder.buildInstr(TargetOpcode::G_IMPLICIT_DEF, DstReg);
129 markInstAndDefDead(MI, *DefMI, DeadInsts);
135 bool tryCombineMerges(MachineInstr &MI,
136 SmallVectorImpl<MachineInstr *> &DeadInsts) {
138 if (MI.getOpcode() != TargetOpcode::G_UNMERGE_VALUES)
141 unsigned NumDefs = MI.getNumOperands() - 1;
142 unsigned SrcReg = MI.getOperand(NumDefs).getReg();
143 MachineInstr *MergeI = MRI.getVRegDef(SrcReg);
144 if (!MergeI || (MergeI->getOpcode() != TargetOpcode::G_MERGE_VALUES))
147 const unsigned NumMergeRegs = MergeI->getNumOperands() - 1;
149 if (NumMergeRegs < NumDefs) {
150 if (NumDefs % NumMergeRegs != 0)
153 Builder.setInstr(MI);
154 // Transform to UNMERGEs, for example
155 // %1 = G_MERGE_VALUES %4, %5
156 // %9, %10, %11, %12 = G_UNMERGE_VALUES %1
158 // %9, %10 = G_UNMERGE_VALUES %4
159 // %11, %12 = G_UNMERGE_VALUES %5
161 const unsigned NewNumDefs = NumDefs / NumMergeRegs;
162 for (unsigned Idx = 0; Idx < NumMergeRegs; ++Idx) {
163 SmallVector<unsigned, 2> DstRegs;
164 for (unsigned j = 0, DefIdx = Idx * NewNumDefs; j < NewNumDefs;
166 DstRegs.push_back(MI.getOperand(DefIdx).getReg());
168 Builder.buildUnmerge(DstRegs, MergeI->getOperand(Idx + 1).getReg());
171 } else if (NumMergeRegs > NumDefs) {
172 if (NumMergeRegs % NumDefs != 0)
175 Builder.setInstr(MI);
176 // Transform to MERGEs
177 // %6 = G_MERGE_VALUES %17, %18, %19, %20
178 // %7, %8 = G_UNMERGE_VALUES %6
180 // %7 = G_MERGE_VALUES %17, %18
181 // %8 = G_MERGE_VALUES %19, %20
183 const unsigned NumRegs = NumMergeRegs / NumDefs;
184 for (unsigned DefIdx = 0; DefIdx < NumDefs; ++DefIdx) {
185 SmallVector<unsigned, 2> Regs;
186 for (unsigned j = 0, Idx = NumRegs * DefIdx + 1; j < NumRegs;
188 Regs.push_back(MergeI->getOperand(Idx).getReg());
190 Builder.buildMerge(MI.getOperand(DefIdx).getReg(), Regs);
194 // FIXME: is a COPY appropriate if the types mismatch? We know both
195 // registers are allocatable by now.
196 if (MRI.getType(MI.getOperand(0).getReg()) !=
197 MRI.getType(MergeI->getOperand(1).getReg()))
200 for (unsigned Idx = 0; Idx < NumDefs; ++Idx)
201 MRI.replaceRegWith(MI.getOperand(Idx).getReg(),
202 MergeI->getOperand(Idx + 1).getReg());
205 markInstAndDefDead(MI, *MergeI, DeadInsts);
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 SmallVectorImpl<MachineInstr *> &DeadInsts) {
215 switch (MI.getOpcode()) {
218 case TargetOpcode::G_ANYEXT:
219 return tryCombineAnyExt(MI, DeadInsts);
220 case TargetOpcode::G_ZEXT:
221 return tryCombineZExt(MI, DeadInsts);
222 case TargetOpcode::G_SEXT:
223 return tryCombineSExt(MI, DeadInsts);
224 case TargetOpcode::G_UNMERGE_VALUES:
225 return tryCombineMerges(MI, DeadInsts);
226 case TargetOpcode::G_TRUNC: {
227 bool Changed = false;
228 for (auto &Use : MRI.use_instructions(MI.getOperand(0).getReg()))
229 Changed |= tryCombineInstruction(Use, DeadInsts);
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 SmallVectorImpl<MachineInstr *> &DeadInsts) {
243 DeadInsts.push_back(&MI);
245 // Collect all the copy instructions that are made dead, due to deleting
246 // this instruction. Collect all of them until the Trunc(DefMI).
248 // %1(s1) = G_TRUNC %0(s32)
249 // %2(s1) = COPY %1(s1)
250 // %3(s1) = COPY %2(s1)
251 // %4(s32) = G_ANYEXT %3(s1)
252 // In this case, we would have replaced %4 with a copy of %0,
253 // and as a result, %3, %2, %1 are dead.
254 MachineInstr *PrevMI = &MI;
255 while (PrevMI != &DefMI) {
256 // If we're dealing with G_UNMERGE_VALUES, tryCombineMerges doesn't really try
257 // to fold copies in between and we can ignore them here.
258 if (PrevMI->getOpcode() == TargetOpcode::G_UNMERGE_VALUES)
260 unsigned PrevRegSrc = PrevMI->getOperand(1).getReg();
261 MachineInstr *TmpDef = MRI.getVRegDef(PrevRegSrc);
262 if (MRI.hasOneUse(PrevRegSrc)) {
263 if (TmpDef != &DefMI) {
264 assert(TmpDef->getOpcode() == TargetOpcode::COPY &&
265 "Expecting copy here");
266 DeadInsts.push_back(TmpDef);
272 if ((PrevMI == &DefMI ||
273 DefMI.getOpcode() == TargetOpcode::G_MERGE_VALUES) &&
274 MRI.hasOneUse(DefMI.getOperand(0).getReg()))
275 DeadInsts.push_back(&DefMI);
278 /// Checks if the target legalizer info has specified anything about the
279 /// instruction, or if unsupported.
280 bool isInstUnsupported(unsigned Opcode, const LLT &DstTy) const {
281 auto Action = LI.getAction({Opcode, 0, DstTy});
282 return Action.first == LegalizerInfo::LegalizeAction::Unsupported ||
283 Action.first == LegalizerInfo::LegalizeAction::NotFound;