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