LLVM  10.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) { }
54 
61 }
62 
63 void Legalizer::init(MachineFunction &MF) {
64 }
65 
66 static bool isArtifact(const MachineInstr &MI) {
67  switch (MI.getOpcode()) {
68  default:
69  return false;
70  case TargetOpcode::G_TRUNC:
71  case TargetOpcode::G_ZEXT:
72  case TargetOpcode::G_ANYEXT:
73  case TargetOpcode::G_SEXT:
74  case TargetOpcode::G_MERGE_VALUES:
75  case TargetOpcode::G_UNMERGE_VALUES:
76  case TargetOpcode::G_CONCAT_VECTORS:
77  case TargetOpcode::G_BUILD_VECTOR:
78  case TargetOpcode::G_EXTRACT:
79  return true;
80  }
81 }
84 
85 namespace {
86 class LegalizerWorkListManager : public GISelChangeObserver {
87  InstListTy &InstList;
88  ArtifactListTy &ArtifactList;
89 #ifndef NDEBUG
91 #endif
92 
93 public:
94  LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
95  : InstList(Insts), ArtifactList(Arts) {}
96 
97  void createdOrChangedInstr(MachineInstr &MI) {
98  // Only legalize pre-isel generic instructions.
99  // Legalization process could generate Target specific pseudo
100  // instructions with generic types. Don't record them
101  if (isPreISelGenericOpcode(MI.getOpcode())) {
102  if (isArtifact(MI))
103  ArtifactList.insert(&MI);
104  else
105  InstList.insert(&MI);
106  }
107  }
108 
109  void createdInstr(MachineInstr &MI) override {
110  LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI);
111  LLVM_DEBUG(NewMIs.push_back(&MI));
112  createdOrChangedInstr(MI);
113  }
114 
115  void printNewInstrs() {
116  LLVM_DEBUG({
117  for (const auto *MI : NewMIs)
118  dbgs() << ".. .. New MI: " << *MI;
119  NewMIs.clear();
120  });
121  }
122 
123  void erasingInstr(MachineInstr &MI) override {
124  LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
125  InstList.remove(&MI);
126  ArtifactList.remove(&MI);
127  }
128 
129  void changingInstr(MachineInstr &MI) override {
130  LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
131  }
132 
133  void changedInstr(MachineInstr &MI) override {
134  // When insts change, we want to revisit them to legalize them again.
135  // We'll consider them the same as created.
136  LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
137  createdOrChangedInstr(MI);
138  }
139 };
140 } // namespace
141 
143  // If the ISel pipeline failed, do not bother running that pass.
144  if (MF.getProperties().hasProperty(
146  return false;
147  LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
148  init(MF);
149  const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
151  getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
152  MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
153 
154  const size_t NumBlocks = MF.size();
156 
157  // Populate Insts
158  InstListTy InstList;
159  ArtifactListTy ArtifactList;
161  // Perform legalization bottom up so we can DCE as we legalize.
162  // Traverse BB in RPOT and within each basic block, add insts top down,
163  // so when we pop_back_val in the legalization process, we traverse bottom-up.
164  for (auto *MBB : RPOT) {
165  if (MBB->empty())
166  continue;
167  for (MachineInstr &MI : *MBB) {
168  // Only legalize pre-isel generic instructions: others don't have types
169  // and are assumed to be legal.
170  if (!isPreISelGenericOpcode(MI.getOpcode()))
171  continue;
172  if (isArtifact(MI))
173  ArtifactList.deferred_insert(&MI);
174  else
175  InstList.deferred_insert(&MI);
176  }
177  }
178  ArtifactList.finalize();
179  InstList.finalize();
180  std::unique_ptr<MachineIRBuilder> MIRBuilder;
181  GISelCSEInfo *CSEInfo = nullptr;
182  bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
184  : TPC.isGISelCSEEnabled();
185 
186  if (EnableCSE) {
187  MIRBuilder = std::make_unique<CSEMIRBuilder>();
188  CSEInfo = &Wrapper.get(TPC.getCSEConfig());
189  MIRBuilder->setCSEInfo(CSEInfo);
190  } else
191  MIRBuilder = std::make_unique<MachineIRBuilder>();
192  // This observer keeps the worklist updated.
193  LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
194  // We want both WorkListObserver as well as CSEInfo to observe all changes.
195  // Use the wrapper observer.
196  GISelObserverWrapper WrapperObserver(&WorkListObserver);
197  if (EnableCSE && CSEInfo)
198  WrapperObserver.addObserver(CSEInfo);
199  // Now install the observer as the delegate to MF.
200  // This will keep all the observers notified about new insertions/deletions.
201  RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
202  LegalizerHelper Helper(MF, WrapperObserver, *MIRBuilder.get());
203  const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
204  LegalizationArtifactCombiner ArtCombiner(*MIRBuilder.get(), MF.getRegInfo(),
205  LInfo);
206  auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
207  WrapperObserver.erasingInstr(*DeadMI);
208  };
209  bool Changed = false;
210  do {
211  while (!InstList.empty()) {
212  MachineInstr &MI = *InstList.pop_back_val();
213  assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
214  if (isTriviallyDead(MI, MRI)) {
215  LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
217  continue;
218  }
219 
220  // Do the legalization for this instruction.
221  auto Res = Helper.legalizeInstrStep(MI);
222  // Error out if we couldn't legalize this instruction. We may want to
223  // fall back to DAG ISel instead in the future.
225  Helper.MIRBuilder.stopObservingChanges();
226  reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
227  "unable to legalize instruction", MI);
228  return false;
229  }
230  WorkListObserver.printNewInstrs();
231  Changed |= Res == LegalizerHelper::Legalized;
232  }
233  while (!ArtifactList.empty()) {
234  MachineInstr &MI = *ArtifactList.pop_back_val();
235  assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
236  if (isTriviallyDead(MI, MRI)) {
237  LLVM_DEBUG(dbgs() << MI << "Is dead\n");
238  RemoveDeadInstFromLists(&MI);
240  continue;
241  }
242  SmallVector<MachineInstr *, 4> DeadInstructions;
243  if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
244  WrapperObserver)) {
245  WorkListObserver.printNewInstrs();
246  for (auto *DeadMI : DeadInstructions) {
247  LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
248  RemoveDeadInstFromLists(DeadMI);
249  DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
250  }
251  Changed = true;
252  continue;
253  }
254  // If this was not an artifact (that could be combined away), this might
255  // need special handling. Add it to InstList, so when it's processed
256  // there, it has to be legal or specially handled.
257  else
258  InstList.insert(&MI);
259  }
260  } while (!InstList.empty());
261 
262  // For now don't support if new blocks are inserted - we would need to fix the
263  // outerloop for that.
264  if (MF.size() != NumBlocks) {
265  MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
266  MF.getFunction().getSubprogram(),
267  /*MBB=*/nullptr);
268  R << "inserting blocks is not supported yet";
269  reportGISelFailure(MF, TPC, MORE, R);
270  return false;
271  }
272 
273  return Changed;
274 }
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
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:412
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:411
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:142
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:158
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:64
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:66
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Legalizer.cpp:55
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:178