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