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 
92 public:
93  LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
94  : InstList(Insts), ArtifactList(Arts) {}
95 
96  void createdInstr(MachineInstr &MI) override {
97  // Only legalize pre-isel generic instructions.
98  // Legalization process could generate Target specific pseudo
99  // instructions with generic types. Don't record them
100  if (isPreISelGenericOpcode(MI.getOpcode())) {
101  if (isArtifact(MI))
102  ArtifactList.insert(&MI);
103  else
104  InstList.insert(&MI);
105  }
106  LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI);
107  }
108 
109  void erasingInstr(MachineInstr &MI) override {
110  LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
111  InstList.remove(&MI);
112  ArtifactList.remove(&MI);
113  }
114 
115  void changingInstr(MachineInstr &MI) override {
116  LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
117  }
118 
119  void changedInstr(MachineInstr &MI) override {
120  // When insts change, we want to revisit them to legalize them again.
121  // We'll consider them the same as created.
122  LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
123  createdInstr(MI);
124  }
125 };
126 } // namespace
127 
129  // If the ISel pipeline failed, do not bother running that pass.
130  if (MF.getProperties().hasProperty(
132  return false;
133  LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
134  init(MF);
135  const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
137  getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
138  MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
139 
140  const size_t NumBlocks = MF.size();
142 
143  // Populate Insts
144  InstListTy InstList;
145  ArtifactListTy ArtifactList;
147  // Perform legalization bottom up so we can DCE as we legalize.
148  // Traverse BB in RPOT and within each basic block, add insts top down,
149  // so when we pop_back_val in the legalization process, we traverse bottom-up.
150  for (auto *MBB : RPOT) {
151  if (MBB->empty())
152  continue;
153  for (MachineInstr &MI : *MBB) {
154  // Only legalize pre-isel generic instructions: others don't have types
155  // and are assumed to be legal.
156  if (!isPreISelGenericOpcode(MI.getOpcode()))
157  continue;
158  if (isArtifact(MI))
159  ArtifactList.deferred_insert(&MI);
160  else
161  InstList.deferred_insert(&MI);
162  }
163  }
164  ArtifactList.finalize();
165  InstList.finalize();
166  std::unique_ptr<MachineIRBuilder> MIRBuilder;
167  GISelCSEInfo *CSEInfo = nullptr;
168  bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
170  : TPC.isGISelCSEEnabled();
171 
172  if (EnableCSE) {
173  MIRBuilder = make_unique<CSEMIRBuilder>();
174  CSEInfo = &Wrapper.get(TPC.getCSEConfig());
175  MIRBuilder->setCSEInfo(CSEInfo);
176  } else
177  MIRBuilder = make_unique<MachineIRBuilder>();
178  // This observer keeps the worklist updated.
179  LegalizerWorkListManager WorkListObserver(InstList, ArtifactList);
180  // We want both WorkListObserver as well as CSEInfo to observe all changes.
181  // Use the wrapper observer.
182  GISelObserverWrapper WrapperObserver(&WorkListObserver);
183  if (EnableCSE && CSEInfo)
184  WrapperObserver.addObserver(CSEInfo);
185  // Now install the observer as the delegate to MF.
186  // This will keep all the observers notified about new insertions/deletions.
187  RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
188  LegalizerHelper Helper(MF, WrapperObserver, *MIRBuilder.get());
189  const LegalizerInfo &LInfo(Helper.getLegalizerInfo());
190  LegalizationArtifactCombiner ArtCombiner(*MIRBuilder.get(), MF.getRegInfo(),
191  LInfo);
192  auto RemoveDeadInstFromLists = [&WrapperObserver](MachineInstr *DeadMI) {
193  WrapperObserver.erasingInstr(*DeadMI);
194  };
195  bool Changed = false;
196  do {
197  while (!InstList.empty()) {
198  MachineInstr &MI = *InstList.pop_back_val();
199  assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
200  if (isTriviallyDead(MI, MRI)) {
201  LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
203  continue;
204  }
205 
206  // Do the legalization for this instruction.
207  auto Res = Helper.legalizeInstrStep(MI);
208  // Error out if we couldn't legalize this instruction. We may want to
209  // fall back to DAG ISel instead in the future.
211  Helper.MIRBuilder.stopObservingChanges();
212  reportGISelFailure(MF, TPC, MORE, "gisel-legalize",
213  "unable to legalize instruction", MI);
214  return false;
215  }
216  Changed |= Res == LegalizerHelper::Legalized;
217  }
218  while (!ArtifactList.empty()) {
219  MachineInstr &MI = *ArtifactList.pop_back_val();
220  assert(isPreISelGenericOpcode(MI.getOpcode()) && "Expecting generic opcode");
221  if (isTriviallyDead(MI, MRI)) {
222  LLVM_DEBUG(dbgs() << MI << "Is dead\n");
223  RemoveDeadInstFromLists(&MI);
225  continue;
226  }
227  SmallVector<MachineInstr *, 4> DeadInstructions;
228  if (ArtCombiner.tryCombineInstruction(MI, DeadInstructions,
229  WrapperObserver)) {
230  for (auto *DeadMI : DeadInstructions) {
231  LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
232  RemoveDeadInstFromLists(DeadMI);
233  DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
234  }
235  Changed = true;
236  continue;
237  }
238  // If this was not an artifact (that could be combined away), this might
239  // need special handling. Add it to InstList, so when it's processed
240  // there, it has to be legal or specially handled.
241  else
242  InstList.insert(&MI);
243  }
244  } while (!InstList.empty());
245 
246  // For now don't support if new blocks are inserted - we would need to fix the
247  // outerloop for that.
248  if (MF.size() != NumBlocks) {
249  MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
250  MF.getFunction().getSubprogram(),
251  /*MBB=*/nullptr);
252  R << "inserting blocks is not supported yet";
253  reportGISelFailure(MF, TPC, MORE, R);
254  return false;
255  }
256 
257  return Changed;
258 }
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:338
const MachineFunctionProperties & getProperties() const
Get the function properties.
unsigned size() const
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:408
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:427
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:1507
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:128
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:134
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:155