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"
30 
31 #include <iterator>
32 
33 #define DEBUG_TYPE "legalizer"
34 
35 using namespace llvm;
36 
37 static cl::opt<bool>
38  EnableCSEInLegalizer("enable-cse-in-legalizer",
39  cl::desc("Should enable CSE in Legalizer"),
40  cl::Optional, cl::init(false));
41 
42 char Legalizer::ID = 0;
44  "Legalize the Machine IR a function's Machine IR", false,
45  false)
49  "Legalize the Machine IR a function's Machine IR", false,
50  false)
51 
52 Legalizer::Legalizer() : MachineFunctionPass(ID) {
54 }
55 
62 }
63 
64 void Legalizer::init(MachineFunction &MF) {
65 }
66 
67 static bool isArtifact(const MachineInstr &MI) {
68  switch (MI.getOpcode()) {
69  default:
70  return false;
71  case TargetOpcode::G_TRUNC:
72  case TargetOpcode::G_ZEXT:
73  case TargetOpcode::G_ANYEXT:
74  case TargetOpcode::G_SEXT:
75  case TargetOpcode::G_MERGE_VALUES:
76  case TargetOpcode::G_UNMERGE_VALUES:
77  case TargetOpcode::G_CONCAT_VECTORS:
78  case TargetOpcode::G_BUILD_VECTOR:
79  case TargetOpcode::G_EXTRACT:
80  return true;
81  }
82 }
85 
86 namespace {
87 class LegalizerWorkListManager : public GISelChangeObserver {
88  InstListTy &InstList;
89  ArtifactListTy &ArtifactList;
90 
91 public:
92  LegalizerWorkListManager(InstListTy &Insts, ArtifactListTy &Arts)
93  : InstList(Insts), ArtifactList(Arts) {}
94 
95  void createdInstr(MachineInstr &MI) override {
96  // Only legalize pre-isel generic instructions.
97  // Legalization process could generate Target specific pseudo
98  // instructions with generic types. Don't record them
100  if (isArtifact(MI))
101  ArtifactList.insert(&MI);
102  else
103  InstList.insert(&MI);
104  }
105  LLVM_DEBUG(dbgs() << ".. .. New MI: " << MI);
106  }
107 
108  void erasingInstr(MachineInstr &MI) override {
109  LLVM_DEBUG(dbgs() << ".. .. Erasing: " << MI);
110  InstList.remove(&MI);
111  ArtifactList.remove(&MI);
112  }
113 
114  void changingInstr(MachineInstr &MI) override {
115  LLVM_DEBUG(dbgs() << ".. .. Changing MI: " << MI);
116  }
117 
118  void changedInstr(MachineInstr &MI) override {
119  // When insts change, we want to revisit them to legalize them again.
120  // We'll consider them the same as created.
121  LLVM_DEBUG(dbgs() << ".. .. Changed MI: " << MI);
122  createdInstr(MI);
123  }
124 };
125 } // namespace
126 
128  // If the ISel pipeline failed, do not bother running that pass.
129  if (MF.getProperties().hasProperty(
131  return false;
132  LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
133  init(MF);
134  const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
136  getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
137  MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
138 
139  const size_t NumBlocks = MF.size();
141 
142  // Populate Insts
143  InstListTy InstList;
144  ArtifactListTy ArtifactList;
146  // Perform legalization bottom up so we can DCE as we legalize.
147  // Traverse BB in RPOT and within each basic block, add insts top down,
148  // so when we pop_back_val in the legalization process, we traverse bottom-up.
149  for (auto *MBB : RPOT) {
150  if (MBB->empty())
151  continue;
152  for (MachineInstr &MI : *MBB) {
153  // Only legalize pre-isel generic instructions: others don't have types
154  // and are assumed to be legal.
155  if (!isPreISelGenericOpcode(MI.getOpcode()))
156  continue;
157  if (isArtifact(MI))
158  ArtifactList.deferred_insert(&MI);
159  else
160  InstList.deferred_insert(&MI);
161  }
162  }
163  ArtifactList.finalize();
164  InstList.finalize();
165  std::unique_ptr<MachineIRBuilder> MIRBuilder;
166  GISelCSEInfo *CSEInfo = nullptr;
167  bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
169  : TPC.isGISelCSEEnabled();
170 
171  if (EnableCSE) {
172  MIRBuilder = make_unique<CSEMIRBuilder>();
173  std::unique_ptr<CSEConfig> Config = make_unique<CSEConfig>();
174  CSEInfo = &Wrapper.get(std::move(Config));
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  for (auto *DeadMI : DeadInstructions) {
230  LLVM_DEBUG(dbgs() << *DeadMI << "Is dead\n");
231  RemoveDeadInstFromLists(DeadMI);
232  DeadMI->eraseFromParentAndMarkDBGValuesForRemoval();
233  }
234  Changed = true;
235  continue;
236  }
237  // If this was not an artifact (that could be combined away), this might
238  // need special handling. Add it to InstList, so when it's processed
239  // there, it has to be legal or specially handled.
240  else
241  InstList.insert(&MI);
242  }
243  } while (!InstList.empty());
244 
245  // For now don't support if new blocks are inserted - we would need to fix the
246  // outerloop for that.
247  if (MF.size() != NumBlocks) {
248  MachineOptimizationRemarkMissed R("gisel-legalize", "GISelFailure",
249  MF.getFunction().getSubprogram(),
250  /*MBB=*/nullptr);
251  R << "inserting blocks is not supported yet";
252  reportGISelFailure(MF, TPC, MORE, R);
253  return false;
254  }
255 
256  return Changed;
257 }
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:68
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:288
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:212
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
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:422
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:127
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:48
Simple wrapper that does the following.
Definition: CSEInfo.h:195
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:33
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
static bool isArtifact(const MachineInstr &MI)
Definition: Legalizer.cpp:67
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:56
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