LLVM 19.0.0git
Legalizer.cpp
Go to the documentation of this file.
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
31#include "llvm/Support/Debug.h"
32#include "llvm/Support/Error.h"
33
34#define DEBUG_TYPE "legalizer"
35
36using namespace llvm;
37
38static 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// This is a temporary hack, should be removed soon.
45 "allow-ginsert-as-artifact",
46 cl::desc("Allow G_INSERT to be considered an artifact. Hack around AMDGPU "
47 "test infinite loops."),
48 cl::Optional, cl::init(true));
49
51 None,
54};
55#ifndef NDEBUG
57 "verify-legalizer-debug-locs",
58 cl::desc("Verify that debug locations are handled"),
60 clEnumValN(DebugLocVerifyLevel::None, "none", "No verification"),
62 "Verify legalizations"),
64 "legalizations+artifactcombiners",
65 "Verify legalizations and artifact combines")),
67#else
68// Always disable it for release builds by preventing the observer from being
69// installed.
71#endif
72
73char Legalizer::ID = 0;
75 "Legalize the Machine IR a function's Machine IR", false,
76 false)
81 "Legalize the Machine IR a function's Machine IR", false,
82 false)
83
85
94}
95
96void Legalizer::init(MachineFunction &MF) {
97}
98
99static bool isArtifact(const MachineInstr &MI) {
100 switch (MI.getOpcode()) {
101 default:
102 return false;
103 case TargetOpcode::G_TRUNC:
104 case TargetOpcode::G_ZEXT:
105 case TargetOpcode::G_ANYEXT:
106 case TargetOpcode::G_SEXT:
107 case TargetOpcode::G_MERGE_VALUES:
108 case TargetOpcode::G_UNMERGE_VALUES:
109 case TargetOpcode::G_CONCAT_VECTORS:
110 case TargetOpcode::G_BUILD_VECTOR:
111 case TargetOpcode::G_EXTRACT:
112 return true;
113 case TargetOpcode::G_INSERT:
115 }
116}
119
120namespace {
121class LegalizerWorkListManager : public GISelChangeObserver {
122 InstListTy &InstList;
123 ArtifactListTy &ArtifactList;
124#ifndef NDEBUG
126#endif
127
128public:
129 LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
130 : InstList(Insts), ArtifactList(Arts) {}
131
132 void createdOrChangedInstr(MachineInstr &MI) {
133 // Only legalize pre-isel generic instructions.
134 // Legalization process could generate Target specific pseudo
135 // instructions with generic types. Don't record them
136 if (isPreISelGenericOpcode(MI.getOpcode())) {
137 if (isArtifact(MI))
138 ArtifactList.insert(&MI);
139 else
140 InstList.insert(&MI);
141 }
142 }
143
144 void createdInstr(MachineInstr &MI) override {
145 LLVM_DEBUG(NewMIs.push_back(&MI));
146 createdOrChangedInstr(MI);
147 }
148
149 void printNewInstrs() {
150 LLVM_DEBUG({
151 for (const auto *MI : NewMIs)
152 dbgs() << ".. .. New MI: " << *MI;
153 NewMIs.clear();
154 });
155 }
156
157 void erasingInstr(MachineInstr &MI) override {
158 LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
159 InstList.remove(&MI);
160 ArtifactList.remove(&MI);
161 }
162
163 void changingInstr(MachineInstr &MI) override {
164 LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
165 }
166
167 void changedInstr(MachineInstr &MI) override {
168 // When insts change, we want to revisit them to legalize them again.
169 // We'll consider them the same as created.
170 LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
171 createdOrChangedInstr(MI);
172 }
173};
174} // namespace
175
179 LostDebugLocObserver &LocObserver,
180 MachineIRBuilder &MIRBuilder,
181 GISelKnownBits *KB) {
182 MIRBuilder.setMF(MF);
184
185 // Populate worklists.
186 InstListTy InstList;
187 ArtifactListTy ArtifactList;
189 // Perform legalization bottom up so we can DCE as we legalize.
190 // Traverse BB in RPOT and within each basic block, add insts top down,
191 // so when we pop_back_val in the legalization process, we traverse bottom-up.
192 for (auto *MBB : RPOT) {
193 if (MBB->empty())
194 continue;
195 for (MachineInstr &MI : *MBB) {
196 // Only legalize pre-isel generic instructions: others don't have types
197 // and are assumed to be legal.
198 if (!isPreISelGenericOpcode(MI.getOpcode()))
199 continue;
200 if (isArtifact(MI))
201 ArtifactList.deferred_insert(&MI);
202 else
203 InstList.deferred_insert(&MI);
204 }
205 }
206 ArtifactList.finalize();
207 InstList.finalize();
208
209 // This observer keeps the worklists updated.
210 LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
211 // We want both WorkListObserver as well as all the auxiliary observers (e.g.
212 // CSEInfo) to observe all changes. Use the wrapper observer.
213 GISelObserverWrapper WrapperObserver(&WorkListObserver);
214 for (GISelChangeObserver *Observer : AuxObservers)
215 WrapperObserver.addObserver(Observer);
216
217 // Now install the observer as the delegate to MF.
218 // This will keep all the observers notified about new insertions/deletions.
219 RAIIMFObsDelInstaller Installer(MF, WrapperObserver);
220 LegalizerHelper Helper(MF, LI, WrapperObserver, MIRBuilder, KB);
221 LegalizationArtifactCombiner ArtCombiner(MIRBuilder, MRI, LI, KB);
222 bool Changed = false;
224 do {
225 LLVM_DEBUG(dbgs() << "=== New Iteration ===\n");
226 assert(RetryList.empty() && "Expected no instructions in RetryList");
227 unsigned NumArtifacts = ArtifactList.size();
228 while (!InstList.empty()) {
229 MachineInstr &MI = *InstList.pop_back_val();
230 assert(isPreISelGenericOpcode(MI.getOpcode()) &&
231 "Expecting generic opcode");
232 if (isTriviallyDead(MI, MRI)) {
234 eraseInstr(MI, MRI, &LocObserver);
235 continue;
236 }
237
238 // Do the legalization for this instruction.
239 auto Res = Helper.legalizeInstrStep(MI, LocObserver);
240 // Error out if we couldn't legalize this instruction. We may want to
241 // fall back to DAG ISel instead in the future.
243 // Move illegal artifacts to RetryList instead of aborting because
244 // legalizing InstList may generate artifacts that allow
245 // ArtifactCombiner to combine away them.
246 if (isArtifact(MI)) {
247 LLVM_DEBUG(dbgs() << ".. Not legalized, moving to artifacts retry\n");
248 assert(NumArtifacts == 0 &&
249 "Artifacts are only expected in instruction list starting the "
250 "second iteration, but each iteration starting second must "
251 "start with an empty artifacts list");
252 (void)NumArtifacts;
253 RetryList.push_back(&MI);
254 continue;
255 }
257 return {Changed, &MI};
258 }
259 WorkListObserver.printNewInstrs();
260 LocObserver.checkpoint();
261 Changed |= Res == LegalizerHelper::Legalized;
262 }
263 // Try to combine the instructions in RetryList again if there
264 // are new artifacts. If not, stop legalizing.
265 if (!RetryList.empty()) {
266 if (!ArtifactList.empty()) {
267 while (!RetryList.empty())
268 ArtifactList.insert(RetryList.pop_back_val());
269 } else {
270 LLVM_DEBUG(dbgs() << "No new artifacts created, not retrying!\n");
272 return {Changed, RetryList.front()};
273 }
274 }
275 LocObserver.checkpoint();
276 while (!ArtifactList.empty()) {
277 MachineInstr &MI = *ArtifactList.pop_back_val();
278 assert(isPreISelGenericOpcode(MI.getOpcode()) &&
279 "Expecting generic opcode");
280 if (isTriviallyDead(MI, MRI)) {
282 eraseInstr(MI, MRI, &LocObserver);
283 continue;
284 }
285 SmallVector<MachineInstr *, 4> DeadInstructions;
286 LLVM_DEBUG(dbgs() << "Trying to combine: " << MI);
287 if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
288 WrapperObserver)) {
289 WorkListObserver.printNewInstrs();
290 eraseInstrs(DeadInstructions, MRI, &LocObserver);
291 LocObserver.checkpoint(
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
311 // If the ISel pipeline failed, do not bother running that pass.
312 if (MF.getProperties().hasProperty(
314 return false;
315 LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
316 init(MF);
317 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
319 getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
320 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
321
322 std::unique_ptr<MachineIRBuilder> MIRBuilder;
323 GISelCSEInfo *CSEInfo = nullptr;
324 bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
326 : TPC.isGISelCSEEnabled();
327 if (EnableCSE) {
328 MIRBuilder = std::make_unique<CSEMIRBuilder>();
329 CSEInfo = &Wrapper.get(TPC.getCSEConfig());
330 MIRBuilder->setCSEInfo(CSEInfo);
331 } else
332 MIRBuilder = std::make_unique<MachineIRBuilder>();
333
335 if (EnableCSE && CSEInfo) {
336 // We want CSEInfo in addition to WorkListObserver to observe all changes.
337 AuxObservers.push_back(CSEInfo);
338 }
339 assert(!CSEInfo || !errorToBool(CSEInfo->verify()));
340 LostDebugLocObserver LocObserver(DEBUG_TYPE);
341 if (VerifyDebugLocs > DebugLocVerifyLevel::None)
342 AuxObservers.push_back(&LocObserver);
343
344 // This allows Known Bits Analysis in the legalizer.
345 GISelKnownBits *KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF);
346
347 const LegalizerInfo &LI = *MF.getSubtarget().getLegalizerInfo();
348 MFResult Result = legalizeMachineFunction(MF, LI, AuxObservers, LocObserver,
349 *MIRBuilder, KB);
350
351 if (Result.FailedOn) {
352 reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
353 "unable to legalize instruction", *Result.FailedOn);
354 return false;
355 }
356
357 if (LocObserver.getNumLostDebugLocs()) {
358 MachineOptimizationRemarkMissed R("gisel-legalize", "LostDebugLoc",
360 /*MBB=*/&*MF.begin());
361 R << "lost "
362 << ore::NV("NumLostDebugLocs", LocObserver.getNumLostDebugLocs())
363 << " debug locations during pass";
364 reportGISelWarning(MF, TPC, MORE, R);
365 // Example remark:
366 // --- !Missed
367 // Pass: gisel-legalize
368 // Name: GISelFailure
369 // DebugLoc: { File: '.../legalize-urem.mir', Line: 1, Column: 0 }
370 // Function: test_urem_s32
371 // Args:
372 // - String: 'lost '
373 // - NumLostDebugLocs: '1'
374 // - String: ' debug locations during pass'
375 // ...
376 }
377
378 // If for some reason CSE was not enabled, make sure that we invalidate the
379 // CSEInfo object (as we currently declare that the analysis is preserved).
380 // The next time get on the wrapper is called, it will force it to recompute
381 // the analysis.
382 if (!EnableCSE)
383 Wrapper.setComputed(false);
384 return Result.Changed;
385}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
amdgpu aa AMDGPU Address space based Alias Analysis Wrapper
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:371
Provides analysis for continuously CSEing during GISel passes.
This file implements a version of MachineIRBuilder which CSEs insts within a MachineBasicBlock.
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:693
Performs the initial survey of the specified function
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This contains common code to allow clients to notify changes to machine instr.
Provides analysis for querying information about KnownBits during GISel passes.
#define DEBUG_TYPE
IRTranslator LLVM IR MI
Legalize the Machine IR a function s Machine IR
Definition: Legalizer.cpp:81
DebugLocVerifyLevel
Definition: Legalizer.cpp:50
static cl::opt< DebugLocVerifyLevel > VerifyDebugLocs("verify-legalizer-debug-locs", cl::desc("Verify that debug locations are handled"), cl::values(clEnumValN(DebugLocVerifyLevel::None, "none", "No verification"), clEnumValN(DebugLocVerifyLevel::Legalizations, "legalizations", "Verify legalizations"), clEnumValN(DebugLocVerifyLevel::LegalizationsAndArtifactCombiners, "legalizations+artifactcombiners", "Verify legalizations and artifact combines")), cl::init(DebugLocVerifyLevel::Legalizations))
static cl::opt< bool > EnableCSEInLegalizer("enable-cse-in-legalizer", cl::desc("Should enable CSE in Legalizer"), cl::Optional, cl::init(false))
static cl::opt< bool > AllowGInsertAsArtifact("allow-ginsert-as-artifact", cl::desc("Allow G_INSERT to be considered an artifact. Hack around AMDGPU " "test infinite loops."), cl::Optional, cl::init(true))
#define DEBUG_TYPE
Definition: Legalizer.cpp:34
static bool isArtifact(const MachineInstr &MI)
Definition: Legalizer.cpp:99
Tracks DebugLocs between checkpoints and verifies that they are transferred.
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Target-Independent Code Generator Pass Configuration Options pass.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1830
The actual analysis pass wrapper.
Definition: CSEInfo.h:222
Simple wrapper that does the following.
Definition: CSEInfo.h:204
The CSE Analysis object.
Definition: CSEInfo.h:69
Abstract class that contains various methods for clients to notify about changes.
To use KnownBitsInfo analysis in a pass, KnownBitsInfo &Info = getAnalysis<GISelKnownBitsInfoAnalysis...
Simple wrapper observer that takes several observers, and calls each one for each event.
void addObserver(GISelChangeObserver *O)
void insert(MachineInstr *I)
Add the specified instruction to the worklist if it isn't already in it.
Definition: GISelWorkList.h:74
MachineInstr * pop_back_val()
unsigned size() const
Definition: GISelWorkList.h:40
void deferred_insert(MachineInstr *I)
Definition: GISelWorkList.h:50
bool empty() const
Definition: GISelWorkList.h:38
void remove(const MachineInstr *I)
Remove I from the worklist if it exists.
Definition: GISelWorkList.h:83
bool tryCombineInstruction(MachineInstr &MI, SmallVectorImpl< MachineInstr * > &DeadInsts, GISelObserverWrapper &WrapperObserver)
Try to combine away MI.
@ Legalized
Instruction has been legalized and the MachineFunction changed.
@ UnableToLegalize
Some kind of error has occurred and we could not legalize this instruction.
MachineIRBuilder & MIRBuilder
Expose MIRBuilder so clients can set their own RecordInsertInstruction functions.
LegalizeResult legalizeInstrStep(MachineInstr &MI, LostDebugLocObserver &LocObserver)
Replace MI by a sequence of legal instructions that can implement the same operation.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: Legalizer.cpp:310
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Legalizer.cpp:86
static char ID
Definition: Legalizer.h:39
static MFResult legalizeMachineFunction(MachineFunction &MF, const LegalizerInfo &LI, ArrayRef< GISelChangeObserver * > AuxObservers, LostDebugLocObserver &LocObserver, MachineIRBuilder &MIRBuilder, GISelKnownBits *KB)
Definition: Legalizer.cpp:177
void checkpoint(bool CheckDebugLocs=true)
Call this to indicate that it's a good point to assess whether locations have been lost.
unsigned getNumLostDebugLocs() const
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
bool hasProperty(Property P) const
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineFunctionProperties & getProperties() const
Get the function properties.
Helper class to build MachineInstr.
void setMF(MachineFunction &MF)
Representation of each machine instruction.
Definition: MachineInstr.h:69
Diagnostic information for missed-optimization remarks.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Class to install both of the above.
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Target-Independent Code Generator Pass Configuration Options.
virtual std::unique_ptr< CSEConfigBase > getCSEConfig() const
Returns the CSEConfig object to use for the current optimization level.
virtual bool isGISelCSEEnabled() const
Check whether continuous CSE should be enabled in GISel passes.
virtual const LegalizerInfo * getLegalizerInfo() const
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:718
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool errorToBool(Error Err)
Helper for converting an Error to a bool.
Definition: Error.h:1071
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Definition: Utils.cpp:1665
bool isPreISelGenericOpcode(unsigned Opcode)
Check whether the given Opcode is a generic opcode that is not supposed to appear after ISel.
Definition: TargetOpcodes.h:30
void reportGISelFailure(MachineFunction &MF, const TargetPassConfig &TPC, MachineOptimizationRemarkEmitter &MORE, MachineOptimizationRemarkMissed &R)
Report an ISel error as a missed optimization remark to the LLVMContext's diagnostic stream.
Definition: Utils.cpp:275
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU)
Modify analysis usage so it preserves passes required for the SelectionDAG fallback.
Definition: Utils.cpp:1155
void eraseInstr(MachineInstr &MI, MachineRegisterInfo &MRI, LostDebugLocObserver *LocObserver=nullptr)
Definition: Utils.cpp:1660
void eraseInstrs(ArrayRef< MachineInstr * > DeadInstrs, MachineRegisterInfo &MRI, LostDebugLocObserver *LocObserver=nullptr)
Definition: Utils.cpp:1645
bool isTriviallyDead(const MachineInstr &MI, const MachineRegisterInfo &MRI)
Check whether an instruction MI is dead: it only defines dead virtual registers, and doesn't have oth...
Definition: Utils.cpp:222
void reportGISelWarning(MachineFunction &MF, const TargetPassConfig &TPC, MachineOptimizationRemarkEmitter &MORE, MachineOptimizationRemarkMissed &R)
Report an ISel warning as a missed optimization remark to the LLVMContext's diagnostic stream.
Definition: Utils.cpp:269
#define MORE()
Definition: regcomp.c:252