LLVM  9.0.0svn
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"
29 #include "llvm/Support/Debug.h"
31 
32 #include <iterator>
33 
34 #define DEBUG_TYPE "legalizer"
35 
36 using namespace llvm;
37 
38 static 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 char Legalizer::ID = 0;
45  "Legalize the Machine IR a function's Machine IR", false,
46  false)
50  "Legalize the Machine IR a function's Machine IR", false,
51  false)
52 
53 Legalizer::Legalizer() : MachineFunctionPass(ID) {
55 }
56 
63 }
64 
65 void Legalizer::init(MachineFunction &MF) {
66 }
67 
68 static bool isArtifact(const MachineInstr &MI) {
69  switch (MI.getOpcode()) {
70  default:
71  return false;
72  case TargetOpcode::G_TRUNC:
73  case TargetOpcode::G_ZEXT:
74  case TargetOpcode::G_ANYEXT:
75  case TargetOpcode::G_SEXT:
76  case TargetOpcode::G_MERGE_VALUES:
77  case TargetOpcode::G_UNMERGE_VALUES:
78  case TargetOpcode::G_CONCAT_VECTORS:
79  case TargetOpcode::G_BUILD_VECTOR:
80  case TargetOpcode::G_EXTRACT:
81  return true;
82  }
83 }
86 
87 namespace {
88 class LegalizerWorkListManager : public GISelChangeObserver {
89  InstListTy &InstList;
90  ArtifactListTy &ArtifactList;
91 #ifndef NDEBUG
93 #endif
94 
95 public:
96  LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
97  : InstList(Insts), ArtifactList(Arts) {}
98 
99  void createdOrChangedInstr(MachineInstr &MI) {
100  // Only legalize pre-isel generic instructions.
101  // Legalization process could generate Target specific pseudo
102  // instructions with generic types. Don't record them
103  if (isPreISelGenericOpcode(MI.getOpcode())) {
104  if (isArtifact(MI))
105  ArtifactList.insert(&MI);
106  else
107  InstList.insert(&MI);
108  }
109  }
110 
111  void createdInstr(MachineInstr &MI) override {
112  LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI);
113  LLVM_DEBUG(NewMIs.push_back(&MI));
114  createdOrChangedInstr(MI);
115  }
116 
117  void printNewInstrs() {
118  LLVM_DEBUG({
119  for (const auto *MI : NewMIs)
120  dbgs() << ".. .. New MI: " << *MI;
121  NewMIs.clear();
122  });
123  }
124 
125  void erasingInstr(MachineInstr &MI) override {
126  LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
127  InstList.remove(&MI);
128  ArtifactList.remove(&MI);
129  }
130 
131  void changingInstr(MachineInstr &MI) override {
132  LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
133  }
134 
135  void changedInstr(MachineInstr &MI) override {
136  // When insts change, we want to revisit them to legalize them again.
137  // We'll consider them the same as created.
138  LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
139  createdOrChangedInstr(MI);
140  }
141 };
142 } // namespace
143 
145  // If the ISel pipeline failed, do not bother running that pass.
146  if (MF.getProperties().hasProperty(
148  return false;
149  LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
150  init(MF);
151  const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
153  getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
154  MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
155 
156  const size_t NumBlocks = MF.size();
158 
159  // Populate Insts
160  InstListTy InstList;
161  ArtifactListTy ArtifactList;
163  // Perform legalization bottom up so we can DCE as we legalize.
164  // Traverse BB in RPOT and within each basic block, add insts top down,
165  // so when we pop_back_val in the legalization process, we traverse bottom-up.
166  for (auto *MBB : RPOT) {
167  if (MBB->empty())
168  continue;
169  for (MachineInstr &MI : *MBB) {
170  // Only legalize pre-isel generic instructions: others don't have types
171  // and are assumed to be legal.
172  if (!isPreISelGenericOpcode(MI.getOpcode()))
173  continue;
174  if (isArtifact(MI))
175  ArtifactList.deferred_insert(&MI);
176  else
177  InstList.deferred_insert(&MI);
178  }
179  }
180  ArtifactList.finalize();
181  InstList.finalize();
182  std::unique_ptr<MachineIRBuilder> MIRBuilder;
183  GISelCSEInfo *CSEInfo = nullptr;
184  bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
186  : TPC.isGISelCSEEnabled();
187 
188  if (EnableCSE) {
189  MIRBuilder = make_unique<CSEMIRBuilder>();
190  CSEInfo = &Wrapper.get(TPC.getCSEConfig());
191  MIRBuilder->setCSEInfo(CSEInfo);
192  } else
193  MIRBuilder = make_unique<MachineIRBuilder>();
194  // This observer keeps the worklist updated.
195  LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
196  // We want both WorkListObserver as well as CSEInfo to observe all changes.
197  // Use the wrapper observer.
198  GISelObserverWrapper WrapperObserver(&WorkListObserver);
199  if (EnableCSE && CSEInfo)
200  WrapperObserver.addObserver(CSEInfo);
201  // Now install the observer as the delegate to MF.
202  // This will keep all the observers notified about new insertions/deletions.
203  RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
204  LegalizerHelper Helper(MF, WrapperObserver, *MIRBuilder.get());
205  const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
206  LegalizationArtifactCombiner ArtCombiner(*MIRBuilder.get(), MF.getRegInfo(),
207  LInfo);
208  auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
209  WrapperObserver.erasingInstr(*DeadMI);
210  };
211  bool Changed = false;
212  do {
213  while (!InstList.empty()) {
214  MachineInstr &MI = *InstList.pop_back_val();
215  assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
216  if (isTriviallyDead(MI, MRI)) {
217  LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
219  continue;
220  }
221 
222  // Do the legalization for this instruction.
223  auto Res = Helper.legalizeInstrStep(MI);
224  // Error out if we couldn't legalize this instruction. We may want to
225  // fall back to DAG ISel instead in the future.
227  Helper.MIRBuilder.stopObservingChanges();
228  reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
229  "unable to legalize instruction", MI);
230  return false;
231  }
232  WorkListObserver.printNewInstrs();
233  Changed |= Res == LegalizerHelper::Legalized;
234  }
235  while (!ArtifactList.empty()) {
236  MachineInstr &MI = *ArtifactList.pop_back_val();
237  assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
238  if (isTriviallyDead(MI, MRI)) {
239  LLVM_DEBUG(dbgs() << MI << "Is dead\n");
240  RemoveDeadInstFromLists(&MI);
242  continue;
243  }
244  SmallVector<MachineInstr *, 4> DeadInstructions;
245  if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
246  WrapperObserver)) {
247  WorkListObserver.printNewInstrs();
248  for (auto *DeadMI : DeadInstructions) {
249  LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
250  RemoveDeadInstFromLists(DeadMI);
251  DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
252  }
253  Changed = true;
254  continue;
255  }
256  // If this was not an artifact (that could be combined away), this might
257  // need special handling. Add it to InstList, so when it's processed
258  // there, it has to be legal or specially handled.
259  else
260  InstList.insert(&MI);
261  }
262  } while (!InstList.empty());
263 
264  // For now don't support if new blocks are inserted - we would need to fix the
265  // outerloop for that.
266  if (MF.size() != NumBlocks) {
267  MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
268  MF.getFunction().getSubprogram(),
269  /*MBB=*/nullptr);
270  R << "inserting blocks is not supported yet";
271  reportGISelFailure(MF, TPC, MORE, R);
272  return false;
273  }
274 
275  return Changed;
276 }
A simple RAII based CSEInfo installer.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
The CSE Analysis object.
Definition: CSEInfo.h:71
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
void deferred_insert(MachineInstr *I)
Definition: GISelWorkList.h:54
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:364
const MachineFunctionProperties & getProperties() const
Get the function properties.
unsigned size() const
void push_back(const T &Elt)
Definition: SmallVector.h:211
bool empty() const
Definition: GISelWorkList.h:42
virtual bool isGISelCSEEnabled() const
Check whether continuous CSE should be enabled in GISel passes.
The actual analysis pass wrapper.
Definition: CSEInfo.h:218
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:85
virtual std::unique_ptr< CSEConfigBase > getCSEConfig() const
Returns the CSEConfig object to use for the current optimization level.
void erasingInstr(MachineInstr &MI) override
An instruction is about to be erased.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
amdgpu aa AMDGPU Address space based Alias Analysis Wrapper
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:410
Target-Independent Code Generator Pass Configuration Options.
void eraseFromParentAndMarkDBGValuesForRemoval()
Unlink &#39;this&#39; from the containing basic block and delete it.
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:365
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
Abstract class that contains various methods for clients to notify about changes. ...
unsigned const MachineRegisterInfo * MRI
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1504
This file implements a version of MachineIRBuilder which CSEs insts within a MachineBasicBlock.
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:144
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:49
Simple wrapper that does the following.
Definition: CSEInfo.h:200
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
The optimization diagnostic interface.
#define MORE()
Definition: regcomp.c:251
MachineInstr * pop_back_val()
void insert(MachineInstr *I)
Add the specified instruction to the worklist if it isn&#39;t already in it.
Definition: GISelWorkList.h:78
const Function & getFunction() const
Return the LLVM function that this machine code represents.
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:32
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
bool isTriviallyDead(const MachineInstr &MI, const MachineRegisterInfo &MRI)
Check whether an instruction MI is dead: it only defines dead virtual registers, and doesn&#39;t have oth...
Definition: Utils.cpp:160
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:63
Instruction has been legalized and the MachineFunction changed.
void addObserver(GISelChangeObserver *O)
#define DEBUG_TYPE
Definition: Legalizer.cpp:34
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
static bool isArtifact(const MachineInstr &MI)
Definition: Legalizer.cpp:68
void initializeLegalizerPass(PassRegistry &)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Legalizer.cpp:57
Diagnostic information for missed-optimization remarks.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool hasProperty(Property P) const
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
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
void reportGISelFailure(MachineFunction &MF, const TargetPassConfig &TPC, MachineOptimizationRemarkEmitter &MORE, MachineOptimizationRemarkMissed &R)
Report an ISel error as a missed optimization remark to the LLVMContext&#39;s diagnostic stream...
Definition: Utils.cpp:181