1 //===-- llvm/CodeGen/GlobalISel/Legalizer.cpp -----------------------------===//
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 //
10 /// \file This file implements the LegalizerHelper class to legalize individual
11 /// instructions and the LegalizePass wrapper pass for the primary
12 /// legalization.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/CodeGen/GlobalISel/Legalizer.h"
17 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
18 #include "llvm/CodeGen/GlobalISel/Utils.h"
19 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
20 #include "llvm/CodeGen/MachineRegisterInfo.h"
21 #include "llvm/CodeGen/TargetPassConfig.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Target/TargetInstrInfo.h"
24 #include "llvm/Target/TargetSubtargetInfo.h"
25 
26 #include <iterator>
27 
28 #define DEBUG_TYPE "legalizer"
29 
30 using namespace llvm;
31 
32 char Legalizer::ID = 0;
33 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
34                       "Legalize the Machine IR a function's Machine IR", false,
35                       false)
36 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
37 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
38                     "Legalize the Machine IR a function's Machine IR", false,
39                     false)
40 
41 Legalizer::Legalizer() : MachineFunctionPass(ID) {
42   initializeLegalizerPass(*PassRegistry::getPassRegistry());
43 }
44 
45 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
46   AU.addRequired<TargetPassConfig>();
47   MachineFunctionPass::getAnalysisUsage(AU);
48 }
49 
50 void Legalizer::init(MachineFunction &MF) {
51 }
52 
53 bool Legalizer::combineExtracts(MachineInstr &MI, MachineRegisterInfo &MRI,
54                                 const TargetInstrInfo &TII) {
55   bool Changed = false;
56   if (MI.getOpcode() != TargetOpcode::G_EXTRACT)
57     return Changed;
58 
59   unsigned NumDefs = (MI.getNumOperands() - 1) / 2;
60   unsigned SrcReg = MI.getOperand(NumDefs).getReg();
61   MachineInstr &SeqI = *MRI.def_instr_begin(SrcReg);
62   if (SeqI.getOpcode() != TargetOpcode::G_SEQUENCE)
63     return Changed;
64 
65   unsigned NumSeqSrcs = (SeqI.getNumOperands() - 1) / 2;
66   bool AllDefsReplaced = true;
67 
68   // Try to match each register extracted with a corresponding insertion formed
69   // by the G_SEQUENCE.
70   for (unsigned Idx = 0, SeqIdx = 0; Idx < NumDefs; ++Idx) {
71     MachineOperand &ExtractMO = MI.getOperand(Idx);
72     assert(ExtractMO.isReg() && ExtractMO.isDef() &&
73            "unexpected extract operand");
74 
75     unsigned ExtractReg = ExtractMO.getReg();
76     unsigned ExtractPos = MI.getOperand(NumDefs + Idx + 1).getImm();
77 
78     while (SeqIdx < NumSeqSrcs &&
79            SeqI.getOperand(2 * SeqIdx + 2).getImm() < ExtractPos)
80       ++SeqIdx;
81 
82     if (SeqIdx == NumSeqSrcs) {
83       AllDefsReplaced = false;
84       continue;
85     }
86 
87     unsigned OrigReg = SeqI.getOperand(2 * SeqIdx + 1).getReg();
88     if (SeqI.getOperand(2 * SeqIdx + 2).getImm() != ExtractPos ||
89         MRI.getType(OrigReg) != MRI.getType(ExtractReg)) {
90       AllDefsReplaced = false;
91       continue;
92     }
93 
94     assert(!TargetRegisterInfo::isPhysicalRegister(OrigReg) &&
95            "unexpected physical register in G_SEQUENCE");
96 
97     // Finally we can replace the uses.
98     MRI.replaceRegWith(ExtractReg, OrigReg);
99   }
100 
101   if (AllDefsReplaced) {
102     // If SeqI was the next instruction in the BB and we removed it, we'd break
103     // the outer iteration.
104     assert(std::next(MachineBasicBlock::iterator(MI)) != SeqI &&
105            "G_SEQUENCE does not dominate G_EXTRACT");
106 
107     MI.eraseFromParent();
108 
109     if (MRI.use_empty(SrcReg))
110       SeqI.eraseFromParent();
111     Changed = true;
112   }
113 
114   return Changed;
115 }
116 
117 bool Legalizer::combineMerges(MachineInstr &MI, MachineRegisterInfo &MRI,
118                               const TargetInstrInfo &TII,
119                               MachineIRBuilder &MIRBuilder) {
120   if (MI.getOpcode() != TargetOpcode::G_UNMERGE_VALUES)
121     return false;
122 
123   unsigned NumDefs = MI.getNumOperands() - 1;
124   unsigned SrcReg = MI.getOperand(NumDefs).getReg();
125   MachineInstr &MergeI = *MRI.def_instr_begin(SrcReg);
126   if (MergeI.getOpcode() != TargetOpcode::G_MERGE_VALUES)
127     return false;
128 
129   const unsigned NumMergeRegs = MergeI.getNumOperands() - 1;
130 
131   if (NumMergeRegs < NumDefs) {
132     if (NumDefs % NumMergeRegs != 0)
133       return false;
134 
135     MIRBuilder.setInstr(MI);
136     // Transform to UNMERGEs, for example
137     //   %1 = G_MERGE_VALUES %4, %5
138     //   %9, %10, %11, %12 = G_UNMERGE_VALUES %1
139     // to
140     //   %9, %10 = G_UNMERGE_VALUES %4
141     //   %11, %12 = G_UNMERGE_VALUES %5
142 
143     const unsigned NewNumDefs = NumDefs / NumMergeRegs;
144     for (unsigned Idx = 0; Idx < NumMergeRegs; ++Idx) {
145       SmallVector<unsigned, 2> DstRegs;
146       for (unsigned j = 0, DefIdx = Idx * NewNumDefs; j < NewNumDefs;
147            ++j, ++DefIdx)
148         DstRegs.push_back(MI.getOperand(DefIdx).getReg());
149 
150       MIRBuilder.buildUnmerge(DstRegs, MergeI.getOperand(Idx + 1).getReg());
151     }
152 
153   } else if (NumMergeRegs > NumDefs) {
154     if (NumMergeRegs % NumDefs != 0)
155       return false;
156 
157     MIRBuilder.setInstr(MI);
158     // Transform to MERGEs
159     //   %6 = G_MERGE_VALUES %17, %18, %19, %20
160     //   %7, %8 = G_UNMERGE_VALUES %6
161     // to
162     //   %7 = G_MERGE_VALUES %17, %18
163     //   %8 = G_MERGE_VALUES %19, %20
164 
165     const unsigned NumRegs = NumMergeRegs / NumDefs;
166     for (unsigned DefIdx = 0; DefIdx < NumDefs; ++DefIdx) {
167       SmallVector<unsigned, 2> Regs;
168       for (unsigned j = 0, Idx = NumRegs * DefIdx + 1; j < NumRegs; ++j, ++Idx)
169         Regs.push_back(MergeI.getOperand(Idx).getReg());
170 
171       MIRBuilder.buildMerge(MI.getOperand(DefIdx).getReg(), Regs);
172     }
173 
174   } else {
175     // FIXME: is a COPY appropriate if the types mismatch? We know both
176     // registers are allocatable by now.
177     if (MRI.getType(MI.getOperand(0).getReg()) !=
178         MRI.getType(MergeI.getOperand(1).getReg()))
179       return false;
180 
181     for (unsigned Idx = 0; Idx < NumDefs; ++Idx)
182       MRI.replaceRegWith(MI.getOperand(Idx).getReg(),
183                          MergeI.getOperand(Idx + 1).getReg());
184   }
185 
186   MI.eraseFromParent();
187   if (MRI.use_empty(MergeI.getOperand(0).getReg()))
188     MergeI.eraseFromParent();
189   return true;
190 }
191 
192 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
193   // If the ISel pipeline failed, do not bother running that pass.
194   if (MF.getProperties().hasProperty(
195           MachineFunctionProperties::Property::FailedISel))
196     return false;
197   DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
198   init(MF);
199   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
200   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
201   LegalizerHelper Helper(MF);
202 
203   // FIXME: an instruction may need more than one pass before it is legal. For
204   // example on most architectures <3 x i3> is doubly-illegal. It would
205   // typically proceed along a path like: <3 x i3> -> <3 x i8> -> <8 x i8>. We
206   // probably want a worklist of instructions rather than naive iterate until
207   // convergence for performance reasons.
208   bool Changed = false;
209   MachineBasicBlock::iterator NextMI;
210   for (auto &MBB : MF) {
211     for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
212       // Get the next Instruction before we try to legalize, because there's a
213       // good chance MI will be deleted.
214       NextMI = std::next(MI);
215 
216       // Only legalize pre-isel generic instructions: others don't have types
217       // and are assumed to be legal.
218       if (!isPreISelGenericOpcode(MI->getOpcode()))
219         continue;
220       unsigned NumNewInsns = 0;
221       SmallVector<MachineInstr *, 4> WorkList;
222       Helper.MIRBuilder.recordInsertions([&](MachineInstr *MI) {
223         // Only legalize pre-isel generic instructions.
224         // Legalization process could generate Target specific pseudo
225         // instructions with generic types. Don't record them
226         if (isPreISelGenericOpcode(MI->getOpcode())) {
227           ++NumNewInsns;
228           WorkList.push_back(MI);
229         }
230       });
231       WorkList.push_back(&*MI);
232 
233       bool Changed = false;
234       LegalizerHelper::LegalizeResult Res;
235       unsigned Idx = 0;
236       do {
237         Res = Helper.legalizeInstrStep(*WorkList[Idx]);
238         // Error out if we couldn't legalize this instruction. We may want to
239         // fall back to DAG ISel instead in the future.
240         if (Res == LegalizerHelper::UnableToLegalize) {
241           Helper.MIRBuilder.stopRecordingInsertions();
242           if (Res == LegalizerHelper::UnableToLegalize) {
243             reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
244                                "unable to legalize instruction",
245                                *WorkList[Idx]);
246             return false;
247           }
248         }
249         Changed |= Res == LegalizerHelper::Legalized;
250         ++Idx;
251 
252 #ifndef NDEBUG
253         if (NumNewInsns) {
254           DEBUG(dbgs() << ".. .. Emitted " << NumNewInsns << " insns\n");
255           for (auto I = WorkList.end() - NumNewInsns, E = WorkList.end();
256                I != E; ++I)
257             DEBUG(dbgs() << ".. .. New MI: "; (*I)->print(dbgs()));
258           NumNewInsns = 0;
259         }
260 #endif
261       } while (Idx < WorkList.size());
262 
263       Helper.MIRBuilder.stopRecordingInsertions();
264     }
265   }
266 
267   MachineRegisterInfo &MRI = MF.getRegInfo();
268   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
269   for (auto &MBB : MF) {
270     for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
271       // Get the next Instruction before we try to legalize, because there's a
272       // good chance MI will be deleted.
273       NextMI = std::next(MI);
274 
275       // combineExtracts erases MI.
276       if (combineExtracts(*MI, MRI, TII)) {
277         Changed = true;
278         continue;
279       }
280       Changed |= combineMerges(*MI, MRI, TII, Helper.MIRBuilder);
281     }
282   }
283 
284   return Changed;
285 }
286