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