LLVM  12.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 
17 #include "llvm/ADT/SetVector.h"
30 #include "llvm/InitializePasses.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/Error.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,
50 };
51 #ifndef NDEBUG
53  "verify-legalizer-debug-locs",
54  cl::desc("Verify that debug locations are handled"),
55  cl::values(
56  clEnumValN(DebugLocVerifyLevel::None, "none", "No verification"),
58  "Verify legalizations"),
60  "legalizations+artifactcombiners",
61  "Verify legalizations and artifact combines")),
63 #else
64 // Always disable it for release builds by preventing the observer from being
65 // installed.
67 #endif
68 
69 char Legalizer::ID = 0;
71  "Legalize the Machine IR a function's Machine IR", false,
72  false)
76  "Legalize the Machine IR a function's Machine IR", false,
77  false)
78 
80 
87 }
88 
89 void Legalizer::init(MachineFunction &MF) {
90 }
91 
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 }
110 
111 namespace {
112 class LegalizerWorkListManager : public GISelChangeObserver {
113  InstListTy &InstList;
114  ArtifactListTy &ArtifactList;
115 #ifndef NDEBUG
117 #endif
118 
119 public:
120  LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
121  : InstList(Insts), ArtifactList(Arts) {}
122 
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 
135  void createdInstr(MachineInstr &MI) override {
136  LLVM_DEBUG(NewMIs.push_back(&MI));
137  createdOrChangedInstr(MI);
138  }
139 
140  void printNewInstrs() {
141  LLVM_DEBUG({
142  for (const auto *MI : NewMIs)
143  dbgs() << ".. .. New MI: " << *MI;
144  NewMIs.clear();
145  });
146  }
147 
148  void erasingInstr(MachineInstr &MI) override {
149  LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
150  InstList.remove(&MI);
151  ArtifactList.remove(&MI);
152  }
153 
154  void changingInstr(MachineInstr &MI) override {
155  LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
156  }
157 
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 
169  ArrayRef<GISelChangeObserver *> AuxObservers,
170  LostDebugLocObserver &LocObserver,
171  MachineIRBuilder &MIRBuilder) {
172  MIRBuilder.setMF(MF);
174 
175  // Populate worklists.
176  InstListTy InstList;
177  ArtifactListTy ArtifactList;
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;
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.
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  }
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");
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 ==
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  const size_t NumBlocks = MF.size();
323 
324  std::unique_ptr<MachineIRBuilder> MIRBuilder;
325  GISelCSEInfo *CSEInfo = nullptr;
326  bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
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 
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);
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 }
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
The CSE Analysis object.
Definition: CSEInfo.h:69
void deferred_insert(MachineInstr *I)
Definition: GISelWorkList.h:51
DiagnosticInfoOptimizationBase::Argument NV
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU)
Modify analysis usage so it preserves passes required for the SelectionDAG fallback.
Definition: Utils.cpp:607
void checkpoint(bool CheckDebugLocs=true)
Call this to indicate that it's a good point to assess whether locations have been lost.
const MachineFunctionProperties & getProperties() const
Get the function properties.
unsigned size() const
void push_back(const T &Elt)
Definition: SmallVector.h:379
bool empty() const
Definition: GISelWorkList.h:39
virtual bool isGISelCSEEnabled() const
Check whether continuous CSE should be enabled in GISel passes.
The actual analysis pass wrapper.
Definition: CSEInfo.h:220
INITIALIZE_PASS_BEGIN(Legalizer, DEBUG_TYPE, "Legalize the Machine IR a function's Machine IR", false, false) INITIALIZE_PASS_END(Legalizer
void remove(const MachineInstr *I)
Remove I from the worklist if it exists.
Definition: GISelWorkList.h:82
virtual std::unique_ptr< CSEConfigBase > getCSEConfig() const
Returns the CSEConfig object to use for the current optimization level.
Function & getFunction()
Return the LLVM function that this machine code represents.
void erasingInstr(MachineInstr &MI) override
An instruction is about to be erased.
MachineBasicBlock & MBB
void setMF(MachineFunction &MF)
AnalysisUsage & addRequired()
amdgpu aa AMDGPU Address space based Alias Analysis Wrapper
MachineIRBuilder & MIRBuilder
Expose MIRBuilder so clients can set their own RecordInsertInstruction functions.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
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))
Target-Independent Code Generator Pass Configuration Options.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:365
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
virtual const LegalizerInfo * getLegalizerInfo() const
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:427
Abstract class that contains various methods for clients to notify about changes.
unsigned const MachineRegisterInfo * MRI
LegalizeResult legalizeInstrStep(MachineInstr &MI)
Replace MI by a sequence of legal instructions that can implement the same operation.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1513
bool errorToBool(Error Err)
Helper for converting an Error to a bool.
Definition: Error.h:1029
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:683
This file implements a version of MachineIRBuilder which CSEs insts within a MachineBasicBlock.
Helper class to build MachineInstr.
int getNumOccurrences() const
Definition: CommandLine.h:388
Represent the analysis usage information of a pass.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: Legalizer.cpp:310
Some kind of error has occurred and we could not legalize this instruction.
Legalize the Machine IR a function s Machine IR
Definition: Legalizer.cpp:75
Simple wrapper that does the following.
Definition: CSEInfo.h:202
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
unsigned size() const
Definition: GISelWorkList.h:41
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:595
#define MORE()
Definition: regcomp.c:252
MachineInstr * pop_back_val()
Definition: GISelWorkList.h:99
void insert(MachineInstr *I)
Add the specified instruction to the worklist if it isn't already in it.
Definition: GISelWorkList.h:75
unsigned getNumLostDebugLocs() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static char ID
Definition: Legalizer.h:33
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:658
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
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:187
static cl::opt< bool > EnableCSEInLegalizer("enable-cse-in-legalizer", cl::desc("Should enable CSE in Legalizer"), cl::Optional, cl::init(false))
Representation of each machine instruction.
Definition: MachineInstr.h:62
Instruction has been legalized and the MachineFunction changed.
void addObserver(GISelChangeObserver *O)
#define DEBUG_TYPE
Definition: Legalizer.cpp:37
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
static bool isArtifact(const MachineInstr &MI)
Definition: Legalizer.cpp:92
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Legalizer.cpp:81
bool tryCombineInstruction(MachineInstr &MI, SmallVectorImpl< MachineInstr * > &DeadInsts, GISelObserverWrapper &WrapperObserver)
Try to combine away MI.
Diagnostic information for missed-optimization remarks.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool hasProperty(Property P) const
static MFResult legalizeMachineFunction(MachineFunction &MF, const LegalizerInfo &LI, ArrayRef< GISelChangeObserver * > AuxObservers, LostDebugLocObserver &LocObserver, MachineIRBuilder &MIRBuilder)
Definition: Legalizer.cpp:168
Class to install both of the above.
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 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:233
print Print MemDeps of function
IRTranslator LLVM IR MI
Simple wrapper observer that takes several observers, and calls each one for each event.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
DebugLocVerifyLevel
Definition: Legalizer.cpp:46
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:239
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)