LLVM 17.0.0git
InstructionSelect.cpp
Go to the documentation of this file.
1//===- llvm/CodeGen/GlobalISel/InstructionSelect.cpp - InstructionSelect ---==//
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/// \file
9/// This file implements the InstructionSelect class.
10//===----------------------------------------------------------------------===//
11
14#include "llvm/ADT/ScopeExit.h"
27#include "llvm/Config/config.h"
28#include "llvm/IR/Function.h"
32#include "llvm/Support/Debug.h"
34
35#define DEBUG_TYPE "instruction-select"
36
37using namespace llvm;
38
39#ifdef LLVM_GISEL_COV_PREFIX
41 CoveragePrefix("gisel-coverage-prefix", cl::init(LLVM_GISEL_COV_PREFIX),
42 cl::desc("Record GlobalISel rule coverage files of this "
43 "prefix if instrumentation was generated"));
44#else
45static const std::string CoveragePrefix;
46#endif
47
50 "Select target instructions out of generic instructions",
51 false, false)
57 "Select target instructions out of generic instructions",
59
61 : MachineFunctionPass(ID), OptLevel(OL) {}
62
63// In order not to crash when calling getAnalysis during testing with -run-pass
64// we use the default opt level here instead of None, so that the addRequired()
65// calls are made in getAnalysisUsage().
67 : MachineFunctionPass(ID), OptLevel(CodeGenOpt::Default) {}
68
73
77 }
80}
81
83 // If the ISel pipeline failed, do not bother running that pass.
86 return false;
87
88 LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n');
89
90 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
92
93 CodeGenOpt::Level OldOptLevel = OptLevel;
94 auto RestoreOptLevel = make_scope_exit([=]() { OptLevel = OldOptLevel; });
96 : MF.getTarget().getOptLevel();
97
98 GISelKnownBits *KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF);
100 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
101 if (PSI && PSI->hasProfileSummary())
102 BFI = &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI();
103 }
104
105 CodeGenCoverage CoverageInfo;
106 assert(ISel && "Cannot work without InstructionSelector");
107 ISel->setupMF(MF, KB, CoverageInfo, PSI, BFI);
108
109 // An optimization remark emitter. Used to report failures.
110 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
111
112 // FIXME: There are many other MF/MFI fields we need to initialize.
113
115#ifndef NDEBUG
116 // Check that our input is fully legal: we require the function to have the
117 // Legalized property, so it should be.
118 // FIXME: This should be in the MachineVerifier, as the RegBankSelected
119 // property check already is.
121 if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
122 reportGISelFailure(MF, TPC, MORE, "gisel-select",
123 "instruction is not legal", *MI);
124 return false;
125 }
126 // FIXME: We could introduce new blocks and will need to fix the outer loop.
127 // Until then, keep track of the number of blocks to assert that we don't.
128 const size_t NumBlocks = MF.size();
129#endif
130 // Keep track of selected blocks, so we can delete unreachable ones later.
131 DenseSet<MachineBasicBlock *> SelectedBlocks;
132
133 for (MachineBasicBlock *MBB : post_order(&MF)) {
134 ISel->CurMBB = MBB;
135 SelectedBlocks.insert(MBB);
136 if (MBB->empty())
137 continue;
138
139 // Select instructions in reverse block order. We permit erasing so have
140 // to resort to manually iterating and recognizing the begin (rend) case.
141 bool ReachedBegin = false;
142 for (auto MII = std::prev(MBB->end()), Begin = MBB->begin();
143 !ReachedBegin;) {
144#ifndef NDEBUG
145 // Keep track of the insertion range for debug printing.
146 const auto AfterIt = std::next(MII);
147#endif
148 // Select this instruction.
149 MachineInstr &MI = *MII;
150
151 // And have our iterator point to the next instruction, if there is one.
152 if (MII == Begin)
153 ReachedBegin = true;
154 else
155 --MII;
156
157 LLVM_DEBUG(dbgs() << "Selecting: \n " << MI);
158
159 // We could have folded this instruction away already, making it dead.
160 // If so, erase it.
161 if (isTriviallyDead(MI, MRI)) {
162 LLVM_DEBUG(dbgs() << "Is dead; erasing.\n");
164 MI.eraseFromParent();
165 continue;
166 }
167
168 // Eliminate hints.
169 if (isPreISelGenericOptimizationHint(MI.getOpcode())) {
170 Register DstReg = MI.getOperand(0).getReg();
171 Register SrcReg = MI.getOperand(1).getReg();
172
173 // At this point, the destination register class of the hint may have
174 // been decided.
175 //
176 // Propagate that through to the source register.
177 const TargetRegisterClass *DstRC = MRI.getRegClassOrNull(DstReg);
178 if (DstRC)
179 MRI.setRegClass(SrcReg, DstRC);
180 assert(canReplaceReg(DstReg, SrcReg, MRI) &&
181 "Must be able to replace dst with src!");
182 MI.eraseFromParent();
183 MRI.replaceRegWith(DstReg, SrcReg);
184 continue;
185 }
186
187 if (MI.getOpcode() == TargetOpcode::G_INVOKE_REGION_START) {
188 MI.eraseFromParent();
189 continue;
190 }
191
192 if (!ISel->select(MI)) {
193 // FIXME: It would be nice to dump all inserted instructions. It's
194 // not obvious how, esp. considering select() can insert after MI.
195 reportGISelFailure(MF, TPC, MORE, "gisel-select", "cannot select", MI);
196 return false;
197 }
198
199 // Dump the range of instructions that MI expanded into.
200 LLVM_DEBUG({
201 auto InsertedBegin = ReachedBegin ? MBB->begin() : std::next(MII);
202 dbgs() << "Into:\n";
203 for (auto &InsertedMI : make_range(InsertedBegin, AfterIt))
204 dbgs() << " " << InsertedMI;
205 dbgs() << '\n';
206 });
207 }
208 }
209
210 for (MachineBasicBlock &MBB : MF) {
211 if (MBB.empty())
212 continue;
213
214 if (!SelectedBlocks.contains(&MBB)) {
215 // This is an unreachable block and therefore hasn't been selected, since
216 // the main selection loop above uses a postorder block traversal.
217 // We delete all the instructions in this block since it's unreachable.
218 MBB.clear();
219 // Don't delete the block in case the block has it's address taken or is
220 // still being referenced by a phi somewhere.
221 continue;
222 }
223 // Try to find redundant copies b/w vregs of the same register class.
224 bool ReachedBegin = false;
225 for (auto MII = std::prev(MBB.end()), Begin = MBB.begin(); !ReachedBegin;) {
226 // Select this instruction.
227 MachineInstr &MI = *MII;
228
229 // And have our iterator point to the next instruction, if there is one.
230 if (MII == Begin)
231 ReachedBegin = true;
232 else
233 --MII;
234 if (MI.getOpcode() != TargetOpcode::COPY)
235 continue;
236 Register SrcReg = MI.getOperand(1).getReg();
237 Register DstReg = MI.getOperand(0).getReg();
238 if (SrcReg.isVirtual() && DstReg.isVirtual()) {
239 auto SrcRC = MRI.getRegClass(SrcReg);
240 auto DstRC = MRI.getRegClass(DstReg);
241 if (SrcRC == DstRC) {
242 MRI.replaceRegWith(DstReg, SrcReg);
243 MI.eraseFromParent();
244 }
245 }
246 }
247 }
248
249#ifndef NDEBUG
251 // Now that selection is complete, there are no more generic vregs. Verify
252 // that the size of the now-constrained vreg is unchanged and that it has a
253 // register class.
254 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
256
257 MachineInstr *MI = nullptr;
258 if (!MRI.def_empty(VReg))
259 MI = &*MRI.def_instr_begin(VReg);
260 else if (!MRI.use_empty(VReg)) {
261 MI = &*MRI.use_instr_begin(VReg);
262 // Debug value instruction is permitted to use undefined vregs.
263 if (MI->isDebugValue())
264 continue;
265 }
266 if (!MI)
267 continue;
268
269 const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg);
270 if (!RC) {
271 reportGISelFailure(MF, TPC, MORE, "gisel-select",
272 "VReg has no regclass after selection", *MI);
273 return false;
274 }
275
276 const LLT Ty = MRI.getType(VReg);
277 if (Ty.isValid() && Ty.getSizeInBits() > TRI.getRegSizeInBits(*RC)) {
279 MF, TPC, MORE, "gisel-select",
280 "VReg's low-level type and register class have different sizes", *MI);
281 return false;
282 }
283 }
284
285 if (MF.size() != NumBlocks) {
286 MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure",
288 /*MBB=*/nullptr);
289 R << "inserting blocks is not supported yet";
290 reportGISelFailure(MF, TPC, MORE, R);
291 return false;
292 }
293#endif
294 // Determine if there are any calls in this machine function. Ported from
295 // SelectionDAG.
296 MachineFrameInfo &MFI = MF.getFrameInfo();
297 for (const auto &MBB : MF) {
298 if (MFI.hasCalls() && MF.hasInlineAsm())
299 break;
300
301 for (const auto &MI : MBB) {
302 if ((MI.isCall() && !MI.isReturn()) || MI.isStackAligningInlineAsm())
303 MFI.setHasCalls(true);
304 if (MI.isInlineAsm())
305 MF.setHasInlineAsm(true);
306 }
307 }
308
309 // FIXME: FinalizeISel pass calls finalizeLowering, so it's called twice.
310 auto &TLI = *MF.getSubtarget().getTargetLowering();
311 TLI.finalizeLowering(MF);
312
313 LLVM_DEBUG({
314 dbgs() << "Rules covered by selecting function: " << MF.getName() << ":";
315 for (auto RuleID : CoverageInfo.covered())
316 dbgs() << " id" << RuleID;
317 dbgs() << "\n\n";
318 });
319 CoverageInfo.emit(CoveragePrefix,
320 TLI.getTargetMachine().getTarget().getBackendName());
321
322 // If we successfully selected the function nothing is going to use the vreg
323 // types after us (otherwise MIRPrinter would need them). Make sure the types
324 // disappear.
325 MRI.clearVirtRegTypes();
326
327 // FIXME: Should we accurately track changes?
328 return true;
329}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
amdgpu AMDGPU Register Bank Select
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
@ Default
Definition: DwarfDebug.cpp:86
Provides analysis for querying information about KnownBits during GISel passes.
IRTranslator LLVM IR MI
Select target instructions out of generic instructions
#define DEBUG_TYPE
static const std::string CoveragePrefix
Interface for Targets to specify which operations they can successfully select and how the others sho...
#define I(x, y, z)
Definition: MD5.cpp:58
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file describes how to lower LLVM code to machine code.
Target-Independent Code Generator Pass Configuration Options pass.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
iterator_range< const_covered_iterator > covered() const
bool emit(StringRef FilePrefix, StringRef BackendName) const
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1725
bool hasOptNone() const
Do not optimize this function (-O0).
Definition: Function.h:639
To use KnownBitsInfo analysis in a pass, KnownBitsInfo &Info = getAnalysis<GISelKnownBitsInfoAnalysis...
This pass is responsible for selecting generic machine instructions to target-specific instructions.
CodeGenOpt::Level OptLevel
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
ProfileSummaryInfo * PSI
BlockFrequencyInfo * BFI
Provides the logic to select generic machine instructions.
virtual bool select(MachineInstr &I)=0
Select the (possibly generic) instruction I to only use target-specific opcodes.
virtual void setupMF(MachineFunction &mf, GISelKnownBits *KB, CodeGenCoverage &covinfo, ProfileSummaryInfo *psi, BlockFrequencyInfo *bfi)
Setup per-MF selector state.
constexpr bool isValid() const
Definition: LowLevelType.h:121
constexpr TypeSize getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
Definition: LowLevelType.h:159
This is an alternative analysis pass to BlockFrequencyInfoWrapperPass.
static void getLazyBFIAnalysisUsage(AnalysisUsage &AU)
Helper for client passes to set up the analysis usage on behalf of this pass.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
bool hasCalls() const
Return true if the current function has any function calls.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
bool hasProperty(Property P) const
void setHasInlineAsm(bool B)
Set a flag that indicates that the function contains inline assembly.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
bool hasInlineAsm() const
Returns true if the function contains any inline assembly.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
unsigned size() const
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
const LLVMTargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
const MachineFunctionProperties & getProperties() const
Get the function properties.
Representation of each machine instruction.
Definition: MachineInstr.h:68
Diagnostic information for missed-optimization remarks.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
bool hasProfileSummary() const
Returns true if profile summary is available.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
virtual void finalizeLowering(MachineFunction &MF) const
Execute target specific actions to finalize target lowering.
CodeGenOpt::Level getOptLevel() const
Returns the optimization level: None, Less, Default, or Aggressive.
Target-Independent Code Generator Pass Configuration Options.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual InstructionSelector * getInstructionSelector() const
virtual const TargetLowering * getTargetLowering() const
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition: DenseSet.h:185
Level
Code generation optimization level.
Definition: CodeGen.h:57
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Definition: Utils.cpp:1364
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
iterator_range< po_iterator< T > > post_order(const T &G)
bool isPreISelGenericOptimizationHint(unsigned Opcode)
Definition: TargetOpcodes.h:42
cl::opt< bool > DisableGISelLegalityCheck
bool canReplaceReg(Register DstReg, Register SrcReg, MachineRegisterInfo &MRI)
Check if DstReg can be replaced with SrcReg depending on the register constraints.
Definition: Utils.cpp:198
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:265
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
const MachineInstr * machineFunctionIsIllegal(const MachineFunction &MF)
Checks that MIR is fully legal, returns an illegal instruction if it's not, nullptr otherwise.
void getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU)
Modify analysis usage so it preserves passes required for the SelectionDAG fallback.
Definition: Utils.cpp:892
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:212
#define MORE()
Definition: regcomp.c:252