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