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/ADT/PostOrderIterator.h"
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/CodeGen/GlobalISel/CSEInfo.h"
20 #include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
21 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
22 #include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
23 #include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
24 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
25 #include "llvm/CodeGen/GlobalISel/Utils.h"
26 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
27 #include "llvm/CodeGen/MachineRegisterInfo.h"
28 #include "llvm/CodeGen/TargetPassConfig.h"
29 #include "llvm/CodeGen/TargetSubtargetInfo.h"
30 #include "llvm/Support/Debug.h"
31
32 #include <iterator>
33
34 #define DEBUG_TYPE "legalizer"
35
36 using namespace llvm;
37
38 static cl::opt<bool>
39 EnableCSEInLegalizer("enable-cse-in-legalizer",
40 cl::desc("Should enable CSE in Legalizer"),
41 cl::Optional, cl::init(false));
42
43 char Legalizer::ID = 0;
44 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
45 "Legalize the Machine IR a function's Machine IR", false,
46 false)
INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)47 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
48 INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
49 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
50 "Legalize the Machine IR a function's Machine IR", false,
51 false)
52
53 Legalizer::Legalizer() : MachineFunctionPass(ID) {
54 initializeLegalizerPass(*PassRegistry::getPassRegistry());
55 }
56
getAnalysisUsage(AnalysisUsage & AU) const57 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
58 AU.addRequired<TargetPassConfig>();
59 AU.addRequired<GISelCSEAnalysisWrapperPass>();
60 AU.addPreserved<GISelCSEAnalysisWrapperPass>();
61 getSelectionDAGFallbackAnalysisUsage(AU);
62 MachineFunctionPass::getAnalysisUsage(AU);
63 }
64
init(MachineFunction & MF)65 void Legalizer::init(MachineFunction &MF) {
66 }
67
isArtifact(const MachineInstr & MI)68 static bool isArtifact(const MachineInstr &MI) {
69 switch (MI.getOpcode()) {
70 default:
71 return false;
72 case TargetOpcode::G_TRUNC:
73 case TargetOpcode::G_ZEXT:
74 case TargetOpcode::G_ANYEXT:
75 case TargetOpcode::G_SEXT:
76 case TargetOpcode::G_MERGE_VALUES:
77 case TargetOpcode::G_UNMERGE_VALUES:
78 case TargetOpcode::G_CONCAT_VECTORS:
79 case TargetOpcode::G_BUILD_VECTOR:
80 return true;
81 }
82 }
83 using InstListTy = GISelWorkList<256>;
84 using ArtifactListTy = GISelWorkList<128>;
85
86 namespace {
87 class LegalizerWorkListManager : public GISelChangeObserver {
88 InstListTy &InstList;
89 ArtifactListTy &ArtifactList;
90
91 public:
LegalizerWorkListManager(InstListTy & Insts,ArtifactListTy & Arts)92 LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
93 : InstList(Insts), ArtifactList(Arts) {}
94
createdInstr(MachineInstr & MI)95 void createdInstr(MachineInstr &MI) override {
96 // Only legalize pre-isel generic instructions.
97 // Legalization process could generate Target specific pseudo
98 // instructions with generic types. Don't record them
99 if (isPreISelGenericOpcode(MI.getOpcode())) {
100 if (isArtifact(MI))
101 ArtifactList.insert(&MI);
102 else
103 InstList.insert(&MI);
104 }
105 LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI);
106 }
107
erasingInstr(MachineInstr & MI)108 void erasingInstr(MachineInstr &MI) override {
109 LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
110 InstList.remove(&MI);
111 ArtifactList.remove(&MI);
112 }
113
changingInstr(MachineInstr & MI)114 void changingInstr(MachineInstr &MI) override {
115 LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
116 }
117
changedInstr(MachineInstr & MI)118 void changedInstr(MachineInstr &MI) override {
119 // When insts change, we want to revisit them to legalize them again.
120 // We'll consider them the same as created.
121 LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
122 createdInstr(MI);
123 }
124 };
125 } // namespace
126
runOnMachineFunction(MachineFunction & MF)127 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
128 // If the ISel pipeline failed, do not bother running that pass.
129 if (MF.getProperties().hasProperty(
130 MachineFunctionProperties::Property::FailedISel))
131 return false;
132 LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
133 init(MF);
134 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
135 GISelCSEAnalysisWrapper &Wrapper =
136 getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
137 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
138
139 const size_t NumBlocks = MF.size();
140 MachineRegisterInfo &MRI = MF.getRegInfo();
141
142 // Populate Insts
143 InstListTy InstList;
144 ArtifactListTy ArtifactList;
145 ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
146 // Perform legalization bottom up so we can DCE as we legalize.
147 // Traverse BB in RPOT and within each basic block, add insts top down,
148 // so when we pop_back_val in the legalization process, we traverse bottom-up.
149 for (auto *MBB : RPOT) {
150 if (MBB->empty())
151 continue;
152 for (MachineInstr &MI : *MBB) {
153 // Only legalize pre-isel generic instructions: others don't have types
154 // and are assumed to be legal.
155 if (!isPreISelGenericOpcode(MI.getOpcode()))
156 continue;
157 if (isArtifact(MI))
158 ArtifactList.insert(&MI);
159 else
160 InstList.insert(&MI);
161 }
162 }
163 std::unique_ptr<MachineIRBuilder> MIRBuilder;
164 GISelCSEInfo *CSEInfo = nullptr;
165 bool IsO0 = TPC.getOptLevel() == CodeGenOpt::Level::None;
166 // Disable CSE for O0.
167 bool EnableCSE = !IsO0 && EnableCSEInLegalizer;
168 if (EnableCSE) {
169 MIRBuilder = make_unique<CSEMIRBuilder>();
170 std::unique_ptr<CSEConfig> Config = make_unique<CSEConfig>();
171 CSEInfo = &Wrapper.get(std::move(Config));
172 MIRBuilder->setCSEInfo(CSEInfo);
173 } else
174 MIRBuilder = make_unique<MachineIRBuilder>();
175 // This observer keeps the worklist updated.
176 LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
177 // We want both WorkListObserver as well as CSEInfo to observe all changes.
178 // Use the wrapper observer.
179 GISelObserverWrapper WrapperObserver(&WorkListObserver);
180 if (EnableCSE && CSEInfo)
181 WrapperObserver.addObserver(CSEInfo);
182 // Now install the observer as the delegate to MF.
183 // This will keep all the observers notified about new insertions/deletions.
184 RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
185 LegalizerHelper Helper(MF, WrapperObserver, *MIRBuilder.get());
186 const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
187 LegalizationArtifactCombiner ArtCombiner(*MIRBuilder.get(), MF.getRegInfo(),
188 LInfo);
189 auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
190 WrapperObserver.erasingInstr(*DeadMI);
191 };
192 bool Changed = false;
193 do {
194 while (!InstList.empty()) {
195 MachineInstr &MI = *InstList.pop_back_val();
196 assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
197 if (isTriviallyDead(MI, MRI)) {
198 LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
199 MI.eraseFromParentAndMarkDBGValuesForRemoval();
200 continue;
201 }
202
203 // Do the legalization for this instruction.
204 auto Res = Helper.legalizeInstrStep(MI);
205 // Error out if we couldn't legalize this instruction. We may want to
206 // fall back to DAG ISel instead in the future.
207 if (Res == LegalizerHelper::UnableToLegalize) {
208 Helper.MIRBuilder.stopObservingChanges();
209 reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
210 "unable to legalize instruction", MI);
211 return false;
212 }
213 Changed |= Res == LegalizerHelper::Legalized;
214 }
215 while (!ArtifactList.empty()) {
216 MachineInstr &MI = *ArtifactList.pop_back_val();
217 assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
218 if (isTriviallyDead(MI, MRI)) {
219 LLVM_DEBUG(dbgs() << MI << "Is dead\n");
220 RemoveDeadInstFromLists(&MI);
221 MI.eraseFromParentAndMarkDBGValuesForRemoval();
222 continue;
223 }
224 SmallVector<MachineInstr *, 4> DeadInstructions;
225 if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions)) {
226 for (auto *DeadMI : DeadInstructions) {
227 LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
228 RemoveDeadInstFromLists(DeadMI);
229 DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
230 }
231 Changed = true;
232 continue;
233 }
234 // If this was not an artifact (that could be combined away), this might
235 // need special handling. Add it to InstList, so when it's processed
236 // there, it has to be legal or specially handled.
237 else
238 InstList.insert(&MI);
239 }
240 } while (!InstList.empty());
241
242 // For now don't support if new blocks are inserted - we would need to fix the
243 // outerloop for that.
244 if (MF.size() != NumBlocks) {
245 MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
246 MF.getFunction().getSubprogram(),
247 /*MBB=*/nullptr);
248 R << "inserting blocks is not supported yet";
249 reportGISelFailure(MF, TPC, MORE, R);
250 return false;
251 }
252
253 return Changed;
254 }
255