1 //===-- llvm/CodeGen/GlobalISel/Legalizer.cpp -----------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file This file implements the LegalizerHelper class to legalize individual
10 /// instructions and the LegalizePass wrapper pass for the primary
11 /// legalization.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "llvm/CodeGen/GlobalISel/Legalizer.h"
16 #include "llvm/ADT/PostOrderIterator.h"
17 #include "llvm/ADT/SetVector.h"
18 #include "llvm/CodeGen/GlobalISel/CSEInfo.h"
19 #include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
20 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
21 #include "llvm/CodeGen/GlobalISel/GISelWorkList.h"
22 #include "llvm/CodeGen/GlobalISel/LegalizationArtifactCombiner.h"
23 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
24 #include "llvm/CodeGen/GlobalISel/LostDebugLocObserver.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/InitializePasses.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/Error.h"
33 #include "llvm/Target/TargetMachine.h"
34
35 #include <iterator>
36
37 #define DEBUG_TYPE "legalizer"
38
39 using namespace llvm;
40
41 static cl::opt<bool>
42 EnableCSEInLegalizer("enable-cse-in-legalizer",
43 cl::desc("Should enable CSE in Legalizer"),
44 cl::Optional, cl::init(false));
45
46 enum class DebugLocVerifyLevel {
47 None,
48 Legalizations,
49 LegalizationsAndArtifactCombiners,
50 };
51 #ifndef NDEBUG
52 static cl::opt<DebugLocVerifyLevel> VerifyDebugLocs(
53 "verify-legalizer-debug-locs",
54 cl::desc("Verify that debug locations are handled"),
55 cl::values(
56 clEnumValN(DebugLocVerifyLevel::None, "none", "No verification"),
57 clEnumValN(DebugLocVerifyLevel::Legalizations, "legalizations",
58 "Verify legalizations"),
59 clEnumValN(DebugLocVerifyLevel::LegalizationsAndArtifactCombiners,
60 "legalizations+artifactcombiners",
61 "Verify legalizations and artifact combines")),
62 cl::init(DebugLocVerifyLevel::Legalizations));
63 #else
64 // Always disable it for release builds by preventing the observer from being
65 // installed.
66 static const DebugLocVerifyLevel VerifyDebugLocs = DebugLocVerifyLevel::None;
67 #endif
68
69 char Legalizer::ID = 0;
70 INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE,
71 "Legalize the Machine IR a function's Machine IR", false,
72 false)
INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)73 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
74 INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
75 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
76 "Legalize the Machine IR a function's Machine IR", false,
77 false)
78
79 Legalizer::Legalizer() : MachineFunctionPass(ID) { }
80
getAnalysisUsage(AnalysisUsage & AU) const81 void Legalizer::getAnalysisUsage(AnalysisUsage &AU) const {
82 AU.addRequired<TargetPassConfig>();
83 AU.addRequired<GISelCSEAnalysisWrapperPass>();
84 AU.addPreserved<GISelCSEAnalysisWrapperPass>();
85 getSelectionDAGFallbackAnalysisUsage(AU);
86 MachineFunctionPass::getAnalysisUsage(AU);
87 }
88
init(MachineFunction & MF)89 void Legalizer::init(MachineFunction &MF) {
90 }
91
isArtifact(const MachineInstr & MI)92 static bool isArtifact(const MachineInstr &MI) {
93 switch (MI.getOpcode()) {
94 default:
95 return false;
96 case TargetOpcode::G_TRUNC:
97 case TargetOpcode::G_ZEXT:
98 case TargetOpcode::G_ANYEXT:
99 case TargetOpcode::G_SEXT:
100 case TargetOpcode::G_MERGE_VALUES:
101 case TargetOpcode::G_UNMERGE_VALUES:
102 case TargetOpcode::G_CONCAT_VECTORS:
103 case TargetOpcode::G_BUILD_VECTOR:
104 case TargetOpcode::G_EXTRACT:
105 return true;
106 }
107 }
108 using InstListTy = GISelWorkList<256>;
109 using ArtifactListTy = GISelWorkList<128>;
110
111 namespace {
112 class LegalizerWorkListManager : public GISelChangeObserver {
113 InstListTy &InstList;
114 ArtifactListTy &ArtifactList;
115 #ifndef NDEBUG
116 SmallVector<MachineInstr *, 4> NewMIs;
117 #endif
118
119 public:
LegalizerWorkListManager(InstListTy & Insts,ArtifactListTy & Arts)120 LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
121 : InstList(Insts), ArtifactList(Arts) {}
122
createdOrChangedInstr(MachineInstr & MI)123 void createdOrChangedInstr(MachineInstr &MI) {
124 // Only legalize pre-isel generic instructions.
125 // Legalization process could generate Target specific pseudo
126 // instructions with generic types. Don't record them
127 if (isPreISelGenericOpcode(MI.getOpcode())) {
128 if (isArtifact(MI))
129 ArtifactList.insert(&MI);
130 else
131 InstList.insert(&MI);
132 }
133 }
134
createdInstr(MachineInstr & MI)135 void createdInstr(MachineInstr &MI) override {
136 LLVM_DEBUG(NewMIs.push_back(&MI));
137 createdOrChangedInstr(MI);
138 }
139
printNewInstrs()140 void printNewInstrs() {
141 LLVM_DEBUG({
142 for (const auto *MI : NewMIs)
143 dbgs() << ".. .. New MI: " << *MI;
144 NewMIs.clear();
145 });
146 }
147
erasingInstr(MachineInstr & MI)148 void erasingInstr(MachineInstr &MI) override {
149 LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
150 InstList.remove(&MI);
151 ArtifactList.remove(&MI);
152 }
153
changingInstr(MachineInstr & MI)154 void changingInstr(MachineInstr &MI) override {
155 LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
156 }
157
changedInstr(MachineInstr & MI)158 void changedInstr(MachineInstr &MI) override {
159 // When insts change, we want to revisit them to legalize them again.
160 // We'll consider them the same as created.
161 LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
162 createdOrChangedInstr(MI);
163 }
164 };
165 } // namespace
166
167 Legalizer::MFResult
legalizeMachineFunction(MachineFunction & MF,const LegalizerInfo & LI,ArrayRef<GISelChangeObserver * > AuxObservers,LostDebugLocObserver & LocObserver,MachineIRBuilder & MIRBuilder)168 Legalizer::legalizeMachineFunction(MachineFunction &MF, const LegalizerInfo &LI,
169 ArrayRef<GISelChangeObserver *> AuxObservers,
170 LostDebugLocObserver &LocObserver,
171 MachineIRBuilder &MIRBuilder) {
172 MIRBuilder.setMF(MF);
173 MachineRegisterInfo &MRI = MF.getRegInfo();
174
175 // Populate worklists.
176 InstListTy InstList;
177 ArtifactListTy ArtifactList;
178 ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
179 // Perform legalization bottom up so we can DCE as we legalize.
180 // Traverse BB in RPOT and within each basic block, add insts top down,
181 // so when we pop_back_val in the legalization process, we traverse bottom-up.
182 for (auto *MBB : RPOT) {
183 if (MBB->empty())
184 continue;
185 for (MachineInstr &MI : *MBB) {
186 // Only legalize pre-isel generic instructions: others don't have types
187 // and are assumed to be legal.
188 if (!isPreISelGenericOpcode(MI.getOpcode()))
189 continue;
190 if (isArtifact(MI))
191 ArtifactList.deferred_insert(&MI);
192 else
193 InstList.deferred_insert(&MI);
194 }
195 }
196 ArtifactList.finalize();
197 InstList.finalize();
198
199 // This observer keeps the worklists updated.
200 LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
201 // We want both WorkListObserver as well as all the auxiliary observers (e.g.
202 // CSEInfo) to observe all changes. Use the wrapper observer.
203 GISelObserverWrapper WrapperObserver(&WorkListObserver);
204 for (GISelChangeObserver *Observer : AuxObservers)
205 WrapperObserver.addObserver(Observer);
206
207 // Now install the observer as the delegate to MF.
208 // This will keep all the observers notified about new insertions/deletions.
209 RAIIMFObsDelInstaller Installer(MF, WrapperObserver);
210 LegalizerHelper Helper(MF, LI, WrapperObserver, MIRBuilder);
211 LegalizationArtifactCombiner ArtCombiner(MIRBuilder, MRI, LI);
212 auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
213 WrapperObserver.erasingInstr(*DeadMI);
214 };
215 bool Changed = false;
216 SmallVector<MachineInstr *, 128> RetryList;
217 do {
218 LLVM_DEBUG(dbgs() << "=== New Iteration ===\n");
219 assert(RetryList.empty() && "Expected no instructions in RetryList");
220 unsigned NumArtifacts = ArtifactList.size();
221 while (!InstList.empty()) {
222 MachineInstr &MI = *InstList.pop_back_val();
223 assert(isPreISelGenericOpcode(MI.getOpcode()) &&
224 "Expecting generic opcode");
225 if (isTriviallyDead(MI, MRI)) {
226 LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
227 MI.eraseFromParentAndMarkDBGValuesForRemoval();
228 LocObserver.checkpoint(false);
229 continue;
230 }
231
232 // Do the legalization for this instruction.
233 auto Res = Helper.legalizeInstrStep(MI);
234 // Error out if we couldn't legalize this instruction. We may want to
235 // fall back to DAG ISel instead in the future.
236 if (Res == LegalizerHelper::UnableToLegalize) {
237 // Move illegal artifacts to RetryList instead of aborting because
238 // legalizing InstList may generate artifacts that allow
239 // ArtifactCombiner to combine away them.
240 if (isArtifact(MI)) {
241 LLVM_DEBUG(dbgs() << ".. Not legalized, moving to artifacts retry\n");
242 assert(NumArtifacts == 0 &&
243 "Artifacts are only expected in instruction list starting the "
244 "second iteration, but each iteration starting second must "
245 "start with an empty artifacts list");
246 (void)NumArtifacts;
247 RetryList.push_back(&MI);
248 continue;
249 }
250 Helper.MIRBuilder.stopObservingChanges();
251 return {Changed, &MI};
252 }
253 WorkListObserver.printNewInstrs();
254 LocObserver.checkpoint();
255 Changed |= Res == LegalizerHelper::Legalized;
256 }
257 // Try to combine the instructions in RetryList again if there
258 // are new artifacts. If not, stop legalizing.
259 if (!RetryList.empty()) {
260 if (!ArtifactList.empty()) {
261 while (!RetryList.empty())
262 ArtifactList.insert(RetryList.pop_back_val());
263 } else {
264 LLVM_DEBUG(dbgs() << "No new artifacts created, not retrying!\n");
265 Helper.MIRBuilder.stopObservingChanges();
266 return {Changed, RetryList.front()};
267 }
268 }
269 LocObserver.checkpoint();
270 while (!ArtifactList.empty()) {
271 MachineInstr &MI = *ArtifactList.pop_back_val();
272 assert(isPreISelGenericOpcode(MI.getOpcode()) &&
273 "Expecting generic opcode");
274 if (isTriviallyDead(MI, MRI)) {
275 LLVM_DEBUG(dbgs() << MI << "Is dead\n");
276 RemoveDeadInstFromLists(&MI);
277 MI.eraseFromParentAndMarkDBGValuesForRemoval();
278 LocObserver.checkpoint(false);
279 continue;
280 }
281 SmallVector<MachineInstr *, 4> DeadInstructions;
282 LLVM_DEBUG(dbgs() << "Trying to combine: " << MI);
283 if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
284 WrapperObserver)) {
285 WorkListObserver.printNewInstrs();
286 for (auto *DeadMI : DeadInstructions) {
287 LLVM_DEBUG(dbgs() << "Is dead: " << *DeadMI);
288 RemoveDeadInstFromLists(DeadMI);
289 DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
290 }
291 LocObserver.checkpoint(
292 VerifyDebugLocs ==
293 DebugLocVerifyLevel::LegalizationsAndArtifactCombiners);
294 Changed = true;
295 continue;
296 }
297 // If this was not an artifact (that could be combined away), this might
298 // need special handling. Add it to InstList, so when it's processed
299 // there, it has to be legal or specially handled.
300 else {
301 LLVM_DEBUG(dbgs() << ".. Not combined, moving to instructions list\n");
302 InstList.insert(&MI);
303 }
304 }
305 } while (!InstList.empty());
306
307 return {Changed, /*FailedOn*/ nullptr};
308 }
309
runOnMachineFunction(MachineFunction & MF)310 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
311 // If the ISel pipeline failed, do not bother running that pass.
312 if (MF.getProperties().hasProperty(
313 MachineFunctionProperties::Property::FailedISel))
314 return false;
315 LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
316 init(MF);
317 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
318 GISelCSEAnalysisWrapper &Wrapper =
319 getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
320 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
321
322 const size_t NumBlocks = MF.size();
323
324 std::unique_ptr<MachineIRBuilder> MIRBuilder;
325 GISelCSEInfo *CSEInfo = nullptr;
326 bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
327 ? EnableCSEInLegalizer
328 : TPC.isGISelCSEEnabled();
329 if (EnableCSE) {
330 MIRBuilder = std::make_unique<CSEMIRBuilder>();
331 CSEInfo = &Wrapper.get(TPC.getCSEConfig());
332 MIRBuilder->setCSEInfo(CSEInfo);
333 } else
334 MIRBuilder = std::make_unique<MachineIRBuilder>();
335
336 SmallVector<GISelChangeObserver *, 1> AuxObservers;
337 if (EnableCSE && CSEInfo) {
338 // We want CSEInfo in addition to WorkListObserver to observe all changes.
339 AuxObservers.push_back(CSEInfo);
340 }
341 assert(!CSEInfo || !errorToBool(CSEInfo->verify()));
342 LostDebugLocObserver LocObserver(DEBUG_TYPE);
343 if (VerifyDebugLocs > DebugLocVerifyLevel::None)
344 AuxObservers.push_back(&LocObserver);
345
346 const LegalizerInfo &LI = *MF.getSubtarget().getLegalizerInfo();
347 MFResult Result =
348 legalizeMachineFunction(MF, LI, AuxObservers, LocObserver, *MIRBuilder);
349
350 if (Result.FailedOn) {
351 reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
352 "unable to legalize instruction", *Result.FailedOn);
353 return false;
354 }
355 // For now don't support if new blocks are inserted - we would need to fix the
356 // outer loop for that.
357 if (MF.size() != NumBlocks) {
358 MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
359 MF.getFunction().getSubprogram(),
360 /*MBB=*/nullptr);
361 R << "inserting blocks is not supported yet";
362 reportGISelFailure(MF, TPC, MORE, R);
363 return false;
364 }
365
366 if (LocObserver.getNumLostDebugLocs()) {
367 MachineOptimizationRemarkMissed R("gisel-legalize", "LostDebugLoc",
368 MF.getFunction().getSubprogram(),
369 /*MBB=*/&*MF.begin());
370 R << "lost "
371 << ore::NV("NumLostDebugLocs", LocObserver.getNumLostDebugLocs())
372 << " debug locations during pass";
373 reportGISelWarning(MF, TPC, MORE, R);
374 // Example remark:
375 // --- !Missed
376 // Pass: gisel-legalize
377 // Name: GISelFailure
378 // DebugLoc: { File: '.../legalize-urem.mir', Line: 1, Column: 0 }
379 // Function: test_urem_s32
380 // Args:
381 // - String: 'lost '
382 // - NumLostDebugLocs: '1'
383 // - String: ' debug locations during pass'
384 // ...
385 }
386
387 // If for some reason CSE was not enabled, make sure that we invalidate the
388 // CSEInfo object (as we currently declare that the analysis is preserved).
389 // The next time get on the wrapper is called, it will force it to recompute
390 // the analysis.
391 if (!EnableCSE)
392 Wrapper.setComputed(false);
393 return Result.Changed;
394 }
395