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   if (MI.getOpcode() != TargetOpcode::G_UNMERGE_VALUES)
120     return false;
121 
122   unsigned NumDefs = MI.getNumOperands() - 1;
123   unsigned SrcReg = MI.getOperand(NumDefs).getReg();
124   MachineInstr &MergeI = *MRI.def_instr_begin(SrcReg);
125   if (MergeI.getOpcode() != TargetOpcode::G_MERGE_VALUES)
126     return false;
127 
128   if (MergeI.getNumOperands() - 1 != NumDefs)
129     return false;
130 
131   // FIXME: is a COPY appropriate if the types mismatch? We know both registers
132   // are allocatable by now.
133   if (MRI.getType(MI.getOperand(0).getReg()) !=
134       MRI.getType(MergeI.getOperand(1).getReg()))
135     return false;
136 
137   for (unsigned Idx = 0; Idx < NumDefs; ++Idx)
138     MRI.replaceRegWith(MI.getOperand(Idx).getReg(),
139                        MergeI.getOperand(Idx + 1).getReg());
140 
141   MI.eraseFromParent();
142   if (MRI.use_empty(MergeI.getOperand(0).getReg()))
143     MergeI.eraseFromParent();
144   return true;
145 }
146 
147 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
148   // If the ISel pipeline failed, do not bother running that pass.
149   if (MF.getProperties().hasProperty(
150           MachineFunctionProperties::Property::FailedISel))
151     return false;
152   DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
153   init(MF);
154   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
155   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
156   LegalizerHelper Helper(MF);
157 
158   // FIXME: an instruction may need more than one pass before it is legal. For
159   // example on most architectures <3 x i3> is doubly-illegal. It would
160   // typically proceed along a path like: <3 x i3> -> <3 x i8> -> <8 x i8>. We
161   // probably want a worklist of instructions rather than naive iterate until
162   // convergence for performance reasons.
163   bool Changed = false;
164   MachineBasicBlock::iterator NextMI;
165   for (auto &MBB : MF) {
166     for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
167       // Get the next Instruction before we try to legalize, because there's a
168       // good chance MI will be deleted.
169       NextMI = std::next(MI);
170 
171       // Only legalize pre-isel generic instructions: others don't have types
172       // and are assumed to be legal.
173       if (!isPreISelGenericOpcode(MI->getOpcode()))
174         continue;
175       unsigned NumNewInsns = 0;
176       SmallVector<MachineInstr *, 4> WorkList;
177       Helper.MIRBuilder.recordInsertions([&](MachineInstr *MI) {
178         // Only legalize pre-isel generic instructions.
179         // Legalization process could generate Target specific pseudo
180         // instructions with generic types. Don't record them
181         if (isPreISelGenericOpcode(MI->getOpcode())) {
182           ++NumNewInsns;
183           WorkList.push_back(MI);
184         }
185       });
186       WorkList.push_back(&*MI);
187 
188       bool Changed = false;
189       LegalizerHelper::LegalizeResult Res;
190       unsigned Idx = 0;
191       do {
192         Res = Helper.legalizeInstrStep(*WorkList[Idx]);
193         // Error out if we couldn't legalize this instruction. We may want to
194         // fall back to DAG ISel instead in the future.
195         if (Res == LegalizerHelper::UnableToLegalize) {
196           Helper.MIRBuilder.stopRecordingInsertions();
197           if (Res == LegalizerHelper::UnableToLegalize) {
198             reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
199                                "unable to legalize instruction",
200                                *WorkList[Idx]);
201             return false;
202           }
203         }
204         Changed |= Res == LegalizerHelper::Legalized;
205         ++Idx;
206 
207 #ifndef NDEBUG
208         if (NumNewInsns) {
209           DEBUG(dbgs() << ".. .. Emitted " << NumNewInsns << " insns\n");
210           for (auto I = WorkList.end() - NumNewInsns, E = WorkList.end();
211                I != E; ++I)
212             DEBUG(dbgs() << ".. .. New MI: "; (*I)->print(dbgs()));
213           NumNewInsns = 0;
214         }
215 #endif
216       } while (Idx < WorkList.size());
217 
218       Helper.MIRBuilder.stopRecordingInsertions();
219     }
220   }
221 
222   MachineRegisterInfo &MRI = MF.getRegInfo();
223   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
224   for (auto &MBB : MF) {
225     for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
226       // Get the next Instruction before we try to legalize, because there's a
227       // good chance MI will be deleted.
228       NextMI = std::next(MI);
229 
230       // combineExtracts erases MI.
231       if (combineExtracts(*MI, MRI, TII)) {
232         Changed = true;
233         continue;
234       }
235       Changed |= combineMerges(*MI, MRI, TII);
236     }
237   }
238 
239   return Changed;
240 }
241