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/MachineRegisterInfo.h"
20 #include "llvm/CodeGen/TargetPassConfig.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Target/TargetInstrInfo.h"
23 #include "llvm/Target/TargetSubtargetInfo.h"
24 
25 #define DEBUG_TYPE "legalizer"
26 
27 using namespace llvm;
28 
29 char Legalizer::ID = 0;
30 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
31                       "Legalize the Machine IR a function's Machine IR", false,
32                       false)
33 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
34 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
35                     "Legalize the Machine IR a function's Machine IR", false,
36                     false)
37 
38 Legalizer::Legalizer() : MachineFunctionPass(ID) {
39   initializeLegalizerPass(*PassRegistry::getPassRegistry());
40 }
41 
42 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
43   AU.addRequired<TargetPassConfig>();
44   MachineFunctionPass::getAnalysisUsage(AU);
45 }
46 
47 void Legalizer::init(MachineFunction &MF) {
48 }
49 
50 bool Legalizer::combineExtracts(MachineInstr &MI, MachineRegisterInfo &MRI,
51                                 const TargetInstrInfo &TII) {
52   bool Changed = false;
53   if (MI.getOpcode() != TargetOpcode::G_EXTRACT)
54     return Changed;
55 
56   unsigned NumDefs = (MI.getNumOperands() - 1) / 2;
57   unsigned SrcReg = MI.getOperand(NumDefs).getReg();
58   MachineInstr &SeqI = *MRI.def_instr_begin(SrcReg);
59   if (SeqI.getOpcode() != TargetOpcode::G_SEQUENCE)
60       return Changed;
61 
62   unsigned NumSeqSrcs = (SeqI.getNumOperands() - 1) / 2;
63   bool AllDefsReplaced = true;
64 
65   // Try to match each register extracted with a corresponding insertion formed
66   // by the G_SEQUENCE.
67   for (unsigned Idx = 0, SeqIdx = 0; Idx < NumDefs; ++Idx) {
68     MachineOperand &ExtractMO = MI.getOperand(Idx);
69     assert(ExtractMO.isReg() && ExtractMO.isDef() &&
70            "unexpected extract operand");
71 
72     unsigned ExtractReg = ExtractMO.getReg();
73     unsigned ExtractPos = MI.getOperand(NumDefs + Idx + 1).getImm();
74 
75     while (SeqIdx < NumSeqSrcs &&
76            SeqI.getOperand(2 * SeqIdx + 2).getImm() < ExtractPos)
77       ++SeqIdx;
78 
79     if (SeqIdx == NumSeqSrcs) {
80       AllDefsReplaced = false;
81       continue;
82     }
83 
84     unsigned OrigReg = SeqI.getOperand(2 * SeqIdx + 1).getReg();
85     if (SeqI.getOperand(2 * SeqIdx + 2).getImm() != ExtractPos ||
86         MRI.getType(OrigReg) != MRI.getType(ExtractReg)) {
87       AllDefsReplaced = false;
88       continue;
89     }
90 
91     assert(!TargetRegisterInfo::isPhysicalRegister(OrigReg) &&
92            "unexpected physical register in G_SEQUENCE");
93 
94     // Finally we can replace the uses.
95     for (auto &Use : MRI.use_operands(ExtractReg)) {
96       Changed = true;
97       Use.setReg(OrigReg);
98     }
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::runOnMachineFunction(MachineFunction &MF) {
118   // If the ISel pipeline failed, do not bother running that pass.
119   if (MF.getProperties().hasProperty(
120           MachineFunctionProperties::Property::FailedISel))
121     return false;
122   DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
123   init(MF);
124   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
125   const LegalizerInfo &LegalizerInfo = *MF.getSubtarget().getLegalizerInfo();
126   LegalizerHelper Helper(MF);
127 
128   // FIXME: an instruction may need more than one pass before it is legal. For
129   // example on most architectures <3 x i3> is doubly-illegal. It would
130   // typically proceed along a path like: <3 x i3> -> <3 x i8> -> <8 x i8>. We
131   // probably want a worklist of instructions rather than naive iterate until
132   // convergence for performance reasons.
133   bool Changed = false;
134   MachineBasicBlock::iterator NextMI;
135   for (auto &MBB : MF)
136     for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
137       // Get the next Instruction before we try to legalize, because there's a
138       // good chance MI will be deleted.
139       NextMI = std::next(MI);
140 
141       // Only legalize pre-isel generic instructions: others don't have types
142       // and are assumed to be legal.
143       if (!isPreISelGenericOpcode(MI->getOpcode()))
144         continue;
145 
146       auto Res = Helper.legalizeInstr(*MI, LegalizerInfo);
147 
148       // Error out if we couldn't legalize this instruction. We may want to fall
149       // back to DAG ISel instead in the future.
150       if (Res == LegalizerHelper::UnableToLegalize) {
151         if (!TPC.isGlobalISelAbortEnabled()) {
152           MF.getProperties().set(
153               MachineFunctionProperties::Property::FailedISel);
154           return false;
155         }
156         std::string Msg;
157         raw_string_ostream OS(Msg);
158         OS << "unable to legalize instruction: ";
159         MI->print(OS);
160         report_fatal_error(OS.str());
161       }
162 
163       Changed |= Res == LegalizerHelper::Legalized;
164     }
165 
166 
167   MachineRegisterInfo &MRI = MF.getRegInfo();
168   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
169   for (auto &MBB : MF) {
170     for (auto MI = MBB.begin(); MI != MBB.end(); MI = NextMI) {
171       // Get the next Instruction before we try to legalize, because there's a
172       // good chance MI will be deleted.
173       NextMI = std::next(MI);
174 
175       Changed |= combineExtracts(*MI, MRI, TII);
176     }
177   }
178 
179   return Changed;
180 }
181