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::combineMerges(MachineInstr &MI, MachineRegisterInfo &MRI,
54                               const TargetInstrInfo &TII,
55                               MachineIRBuilder &MIRBuilder) {
56   if (MI.getOpcode() != TargetOpcode::G_UNMERGE_VALUES)
57     return false;
58 
59   unsigned NumDefs = MI.getNumOperands() - 1;
60   unsigned SrcReg = MI.getOperand(NumDefs).getReg();
61   MachineInstr &MergeI = *MRI.def_instr_begin(SrcReg);
62   if (MergeI.getOpcode() != TargetOpcode::G_MERGE_VALUES)
63     return false;
64 
65   const unsigned NumMergeRegs = MergeI.getNumOperands() - 1;
66 
67   if (NumMergeRegs < NumDefs) {
68     if (NumDefs % NumMergeRegs != 0)
69       return false;
70 
71     MIRBuilder.setInstr(MI);
72     // Transform to UNMERGEs, for example
73     //   %1 = G_MERGE_VALUES %4, %5
74     //   %9, %10, %11, %12 = G_UNMERGE_VALUES %1
75     // to
76     //   %9, %10 = G_UNMERGE_VALUES %4
77     //   %11, %12 = G_UNMERGE_VALUES %5
78 
79     const unsigned NewNumDefs = NumDefs / NumMergeRegs;
80     for (unsigned Idx = 0; Idx < NumMergeRegs; ++Idx) {
81       SmallVector<unsigned, 2> DstRegs;
82       for (unsigned j = 0, DefIdx = Idx * NewNumDefs; j < NewNumDefs;
83            ++j, ++DefIdx)
84         DstRegs.push_back(MI.getOperand(DefIdx).getReg());
85 
86       MIRBuilder.buildUnmerge(DstRegs, MergeI.getOperand(Idx + 1).getReg());
87     }
88 
89   } else if (NumMergeRegs > NumDefs) {
90     if (NumMergeRegs % NumDefs != 0)
91       return false;
92 
93     MIRBuilder.setInstr(MI);
94     // Transform to MERGEs
95     //   %6 = G_MERGE_VALUES %17, %18, %19, %20
96     //   %7, %8 = G_UNMERGE_VALUES %6
97     // to
98     //   %7 = G_MERGE_VALUES %17, %18
99     //   %8 = G_MERGE_VALUES %19, %20
100 
101     const unsigned NumRegs = NumMergeRegs / NumDefs;
102     for (unsigned DefIdx = 0; DefIdx < NumDefs; ++DefIdx) {
103       SmallVector<unsigned, 2> Regs;
104       for (unsigned j = 0, Idx = NumRegs * DefIdx + 1; j < NumRegs; ++j, ++Idx)
105         Regs.push_back(MergeI.getOperand(Idx).getReg());
106 
107       MIRBuilder.buildMerge(MI.getOperand(DefIdx).getReg(), Regs);
108     }
109 
110   } else {
111     // FIXME: is a COPY appropriate if the types mismatch? We know both
112     // registers are allocatable by now.
113     if (MRI.getType(MI.getOperand(0).getReg()) !=
114         MRI.getType(MergeI.getOperand(1).getReg()))
115       return false;
116 
117     for (unsigned Idx = 0; Idx < NumDefs; ++Idx)
118       MRI.replaceRegWith(MI.getOperand(Idx).getReg(),
119                          MergeI.getOperand(Idx + 1).getReg());
120   }
121 
122   MI.eraseFromParent();
123   if (MRI.use_empty(MergeI.getOperand(0).getReg()))
124     MergeI.eraseFromParent();
125   return true;
126 }
127 
128 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
129   // If the ISel pipeline failed, do not bother running that pass.
130   if (MF.getProperties().hasProperty(
131           MachineFunctionProperties::Property::FailedISel))
132     return false;
133   DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
134   init(MF);
135   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
136   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
137   LegalizerHelper Helper(MF);
138 
139   // FIXME: an instruction may need more than one pass before it is legal. For
140   // example on most architectures <3 x i3> is doubly-illegal. It would
141   // typically proceed along a path like: <3 x i3> -> <3 x i8> -> <8 x i8>. We
142   // probably want a worklist of instructions rather than naive iterate until
143   // convergence for performance reasons.
144   bool Changed = false;
145   MachineBasicBlock::iterator NextMI;
146   for (auto &MBB : MF) {
147     for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
148       // Get the next Instruction before we try to legalize, because there's a
149       // good chance MI will be deleted.
150       NextMI = std::next(MI);
151 
152       // Only legalize pre-isel generic instructions: others don't have types
153       // and are assumed to be legal.
154       if (!isPreISelGenericOpcode(MI->getOpcode()))
155         continue;
156       unsigned NumNewInsns = 0;
157       SmallVector<MachineInstr *, 4> WorkList;
158       Helper.MIRBuilder.recordInsertions([&](MachineInstr *MI) {
159         // Only legalize pre-isel generic instructions.
160         // Legalization process could generate Target specific pseudo
161         // instructions with generic types. Don't record them
162         if (isPreISelGenericOpcode(MI->getOpcode())) {
163           ++NumNewInsns;
164           WorkList.push_back(MI);
165         }
166       });
167       WorkList.push_back(&*MI);
168 
169       bool Changed = false;
170       LegalizerHelper::LegalizeResult Res;
171       unsigned Idx = 0;
172       do {
173         Res = Helper.legalizeInstrStep(*WorkList[Idx]);
174         // Error out if we couldn't legalize this instruction. We may want to
175         // fall back to DAG ISel instead in the future.
176         if (Res == LegalizerHelper::UnableToLegalize) {
177           Helper.MIRBuilder.stopRecordingInsertions();
178           if (Res == LegalizerHelper::UnableToLegalize) {
179             reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
180                                "unable to legalize instruction",
181                                *WorkList[Idx]);
182             return false;
183           }
184         }
185         Changed |= Res == LegalizerHelper::Legalized;
186         ++Idx;
187 
188 #ifndef NDEBUG
189         if (NumNewInsns) {
190           DEBUG(dbgs() << ".. .. Emitted " << NumNewInsns << " insns\n");
191           for (auto I = WorkList.end() - NumNewInsns, E = WorkList.end();
192                I != E; ++I)
193             DEBUG(dbgs() << ".. .. New MI: "; (*I)->print(dbgs()));
194           NumNewInsns = 0;
195         }
196 #endif
197       } while (Idx < WorkList.size());
198 
199       Helper.MIRBuilder.stopRecordingInsertions();
200     }
201   }
202 
203   MachineRegisterInfo &MRI = MF.getRegInfo();
204   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
205   for (auto &MBB : MF) {
206     for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
207       // Get the next Instruction before we try to legalize, because there's a
208       // good chance MI will be deleted.
209       NextMI = std::next(MI);
210       Changed |= combineMerges(*MI, MRI, TII, Helper.MIRBuilder);
211     }
212   }
213 
214   return Changed;
215 }
216