]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - contrib/llvm/include/llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h
MFV r329313: 8857 zio_remove_child() panic due to already destroyed parent zio
[FreeBSD/FreeBSD.git] / contrib / llvm / include / llvm / CodeGen / GlobalISel / LegalizationArtifactCombiner.h
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       : Builder(B), MRI(MRI), LI(LI) {}
34
35   bool tryCombineAnyExt(MachineInstr &MI,
36                         SmallVectorImpl<MachineInstr *> &DeadInsts) {
37     if (MI.getOpcode() != TargetOpcode::G_ANYEXT)
38       return false;
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();
44       Builder.setInstr(MI);
45       // We get a copy/trunc/extend depending on the sizes
46       Builder.buildAnyExtOrTrunc(DstReg, SrcReg);
47       markInstAndDefDead(MI, *DefMI, DeadInsts);
48       return true;
49     }
50     return tryFoldImplicitDef(MI, DeadInsts);
51   }
52
53   bool tryCombineZExt(MachineInstr &MI,
54                       SmallVectorImpl<MachineInstr *> &DeadInsts) {
55
56     if (MI.getOpcode() != TargetOpcode::G_ZEXT)
57       return false;
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))
64         return false;
65       DEBUG(dbgs() << ".. Combine MI: " << MI;);
66       Builder.setInstr(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);
76       return true;
77     }
78     return tryFoldImplicitDef(MI, DeadInsts);
79   }
80
81   bool tryCombineSExt(MachineInstr &MI,
82                       SmallVectorImpl<MachineInstr *> &DeadInsts) {
83
84     if (MI.getOpcode() != TargetOpcode::G_SEXT)
85       return false;
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))
93         return false;
94       DEBUG(dbgs() << ".. Combine MI: " << MI;);
95       Builder.setInstr(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);
107       return true;
108     }
109     return tryFoldImplicitDef(MI, DeadInsts);
110   }
111
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)
118       return false;
119
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))
125         return false;
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);
130       return true;
131     }
132     return false;
133   }
134
135   bool tryCombineMerges(MachineInstr &MI,
136                         SmallVectorImpl<MachineInstr *> &DeadInsts) {
137
138     if (MI.getOpcode() != TargetOpcode::G_UNMERGE_VALUES)
139       return false;
140
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))
145       return false;
146
147     const unsigned NumMergeRegs = MergeI->getNumOperands() - 1;
148
149     if (NumMergeRegs < NumDefs) {
150       if (NumDefs % NumMergeRegs != 0)
151         return false;
152
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
157       // to
158       //   %9, %10 = G_UNMERGE_VALUES %4
159       //   %11, %12 = G_UNMERGE_VALUES %5
160
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;
165              ++j, ++DefIdx)
166           DstRegs.push_back(MI.getOperand(DefIdx).getReg());
167
168         Builder.buildUnmerge(DstRegs, MergeI->getOperand(Idx + 1).getReg());
169       }
170
171     } else if (NumMergeRegs > NumDefs) {
172       if (NumMergeRegs % NumDefs != 0)
173         return false;
174
175       Builder.setInstr(MI);
176       // Transform to MERGEs
177       //   %6 = G_MERGE_VALUES %17, %18, %19, %20
178       //   %7, %8 = G_UNMERGE_VALUES %6
179       // to
180       //   %7 = G_MERGE_VALUES %17, %18
181       //   %8 = G_MERGE_VALUES %19, %20
182
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;
187              ++j, ++Idx)
188           Regs.push_back(MergeI->getOperand(Idx).getReg());
189
190         Builder.buildMerge(MI.getOperand(DefIdx).getReg(), Regs);
191       }
192
193     } else {
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()))
198         return false;
199
200       for (unsigned Idx = 0; Idx < NumDefs; ++Idx)
201         MRI.replaceRegWith(MI.getOperand(Idx).getReg(),
202                            MergeI->getOperand(Idx + 1).getReg());
203     }
204
205     markInstAndDefDead(MI, *MergeI, DeadInsts);
206     return true;
207   }
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                              SmallVectorImpl<MachineInstr *> &DeadInsts) {
215     switch (MI.getOpcode()) {
216     default:
217       return false;
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);
230       return Changed;
231     }
232     }
233   }
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                           SmallVectorImpl<MachineInstr *> &DeadInsts) {
243     DeadInsts.push_back(&MI);
244
245     // Collect all the copy instructions that are made dead, due to deleting
246     // this instruction. Collect all of them until the Trunc(DefMI).
247     // Eg,
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)
259         break;
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);
267         }
268       } else
269         break;
270       PrevMI = TmpDef;
271     }
272     if ((PrevMI == &DefMI ||
273          DefMI.getOpcode() == TargetOpcode::G_MERGE_VALUES) &&
274         MRI.hasOneUse(DefMI.getOperand(0).getReg()))
275       DeadInsts.push_back(&DefMI);
276   }
277
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;
284   }
285 };
286
287 } // namespace llvm