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