LLVM 19.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"
28#include "llvm/Config/config.h"
29#include "llvm/IR/Function.h"
33#include "llvm/Support/Debug.h"
36
37#define DEBUG_TYPE "instruction-select"
38
39using namespace llvm;
40
41DEBUG_COUNTER(GlobalISelCounter, "globalisel",
42 "Controls whether to select function with GlobalISel");
43
44#ifdef LLVM_GISEL_COV_PREFIX
46 CoveragePrefix("gisel-coverage-prefix", cl::init(LLVM_GISEL_COV_PREFIX),
47 cl::desc("Record GlobalISel rule coverage files of this "
48 "prefix if instrumentation was generated"));
49#else
50static const std::string CoveragePrefix;
51#endif
52
55 "Select target instructions out of generic instructions",
56 false, false)
62 "Select target instructions out of generic instructions",
64
66 : MachineFunctionPass(ID), OptLevel(OL) {}
67
68// In order not to crash when calling getAnalysis during testing with -run-pass
69// we use the default opt level here instead of None, so that the addRequired()
70// calls are made in getAnalysisUsage().
73
78
82 }
85}
86
88 // If the ISel pipeline failed, do not bother running that pass.
91 return false;
92
93 LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n');
94
95 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
97 ISel->setTargetPassConfig(&TPC);
98
99 CodeGenOptLevel OldOptLevel = OptLevel;
100 auto RestoreOptLevel = make_scope_exit([=]() { OptLevel = OldOptLevel; });
102 : MF.getTarget().getOptLevel();
103
104 GISelKnownBits *KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF);
106 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
107 if (PSI && PSI->hasProfileSummary())
108 BFI = &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI();
109 }
110
111 CodeGenCoverage CoverageInfo;
112 assert(ISel && "Cannot work without InstructionSelector");
113 ISel->setupMF(MF, KB, &CoverageInfo, PSI, BFI);
114
115 // An optimization remark emitter. Used to report failures.
116 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
117 ISel->setRemarkEmitter(&MORE);
118
119 // FIXME: There are many other MF/MFI fields we need to initialize.
120
122#ifndef NDEBUG
123 // Check that our input is fully legal: we require the function to have the
124 // Legalized property, so it should be.
125 // FIXME: This should be in the MachineVerifier, as the RegBankSelected
126 // property check already is.
128 if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
129 reportGISelFailure(MF, TPC, MORE, "gisel-select",
130 "instruction is not legal", *MI);
131 return false;
132 }
133 // FIXME: We could introduce new blocks and will need to fix the outer loop.
134 // Until then, keep track of the number of blocks to assert that we don't.
135 const size_t NumBlocks = MF.size();
136#endif
137 // Keep track of selected blocks, so we can delete unreachable ones later.
138 DenseSet<MachineBasicBlock *> SelectedBlocks;
139
140 for (MachineBasicBlock *MBB : post_order(&MF)) {
141 ISel->CurMBB = MBB;
142 SelectedBlocks.insert(MBB);
143 if (MBB->empty())
144 continue;
145
146 // Select instructions in reverse block order. We permit erasing so have
147 // to resort to manually iterating and recognizing the begin (rend) case.
148 bool ReachedBegin = false;
149 for (auto MII = std::prev(MBB->end()), Begin = MBB->begin();
150 !ReachedBegin;) {
151#ifndef NDEBUG
152 // Keep track of the insertion range for debug printing.
153 const auto AfterIt = std::next(MII);
154#endif
155 // Select this instruction.
156 MachineInstr &MI = *MII;
157
158 // And have our iterator point to the next instruction, if there is one.
159 if (MII == Begin)
160 ReachedBegin = true;
161 else
162 --MII;
163
164 LLVM_DEBUG(dbgs() << "Selecting: \n " << MI);
165
166 // We could have folded this instruction away already, making it dead.
167 // If so, erase it.
168 if (isTriviallyDead(MI, MRI)) {
169 LLVM_DEBUG(dbgs() << "Is dead; erasing.\n");
171 MI.eraseFromParent();
172 continue;
173 }
174
175 // Eliminate hints or G_CONSTANT_FOLD_BARRIER.
176 if (isPreISelGenericOptimizationHint(MI.getOpcode()) ||
177 MI.getOpcode() == TargetOpcode::G_CONSTANT_FOLD_BARRIER) {
178 auto [DstReg, SrcReg] = MI.getFirst2Regs();
179
180 // At this point, the destination register class of the op may have
181 // been decided.
182 //
183 // Propagate that through to the source register.
184 const TargetRegisterClass *DstRC = MRI.getRegClassOrNull(DstReg);
185 if (DstRC)
186 MRI.setRegClass(SrcReg, DstRC);
187 assert(canReplaceReg(DstReg, SrcReg, MRI) &&
188 "Must be able to replace dst with src!");
189 MI.eraseFromParent();
190 MRI.replaceRegWith(DstReg, SrcReg);
191 continue;
192 }
193
194 if (MI.getOpcode() == TargetOpcode::G_INVOKE_REGION_START) {
195 MI.eraseFromParent();
196 continue;
197 }
198
199 if (!ISel->select(MI)) {
200 // FIXME: It would be nice to dump all inserted instructions. It's
201 // not obvious how, esp. considering select() can insert after MI.
202 reportGISelFailure(MF, TPC, MORE, "gisel-select", "cannot select", MI);
203 return false;
204 }
205
206 // Dump the range of instructions that MI expanded into.
207 LLVM_DEBUG({
208 auto InsertedBegin = ReachedBegin ? MBB->begin() : std::next(MII);
209 dbgs() << "Into:\n";
210 for (auto &InsertedMI : make_range(InsertedBegin, AfterIt))
211 dbgs() << " " << InsertedMI;
212 dbgs() << '\n';
213 });
214 }
215 }
216
217 for (MachineBasicBlock &MBB : MF) {
218 if (MBB.empty())
219 continue;
220
221 if (!SelectedBlocks.contains(&MBB)) {
222 // This is an unreachable block and therefore hasn't been selected, since
223 // the main selection loop above uses a postorder block traversal.
224 // We delete all the instructions in this block since it's unreachable.
225 MBB.clear();
226 // Don't delete the block in case the block has it's address taken or is
227 // still being referenced by a phi somewhere.
228 continue;
229 }
230 // Try to find redundant copies b/w vregs of the same register class.
231 bool ReachedBegin = false;
232 for (auto MII = std::prev(MBB.end()), Begin = MBB.begin(); !ReachedBegin;) {
233 // Select this instruction.
234 MachineInstr &MI = *MII;
235
236 // And have our iterator point to the next instruction, if there is one.
237 if (MII == Begin)
238 ReachedBegin = true;
239 else
240 --MII;
241 if (MI.getOpcode() != TargetOpcode::COPY)
242 continue;
243 Register SrcReg = MI.getOperand(1).getReg();
244 Register DstReg = MI.getOperand(0).getReg();
245 if (SrcReg.isVirtual() && DstReg.isVirtual()) {
246 auto SrcRC = MRI.getRegClass(SrcReg);
247 auto DstRC = MRI.getRegClass(DstReg);
248 if (SrcRC == DstRC) {
249 MRI.replaceRegWith(DstReg, SrcReg);
250 MI.eraseFromParent();
251 }
252 }
253 }
254 }
255
256#ifndef NDEBUG
258 // Now that selection is complete, there are no more generic vregs. Verify
259 // that the size of the now-constrained vreg is unchanged and that it has a
260 // register class.
261 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
263
264 MachineInstr *MI = nullptr;
265 if (!MRI.def_empty(VReg))
266 MI = &*MRI.def_instr_begin(VReg);
267 else if (!MRI.use_empty(VReg)) {
268 MI = &*MRI.use_instr_begin(VReg);
269 // Debug value instruction is permitted to use undefined vregs.
270 if (MI->isDebugValue())
271 continue;
272 }
273 if (!MI)
274 continue;
275
276 const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg);
277 if (!RC) {
278 reportGISelFailure(MF, TPC, MORE, "gisel-select",
279 "VReg has no regclass after selection", *MI);
280 return false;
281 }
282
283 const LLT Ty = MRI.getType(VReg);
284 if (Ty.isValid() &&
285 TypeSize::isKnownGT(Ty.getSizeInBits(), TRI.getRegSizeInBits(*RC))) {
287 MF, TPC, MORE, "gisel-select",
288 "VReg's low-level type and register class have different sizes", *MI);
289 return false;
290 }
291 }
292
293 if (MF.size() != NumBlocks) {
294 MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure",
296 /*MBB=*/nullptr);
297 R << "inserting blocks is not supported yet";
298 reportGISelFailure(MF, TPC, MORE, R);
299 return false;
300 }
301#endif
302
303 if (!DebugCounter::shouldExecute(GlobalISelCounter)) {
304 dbgs() << "Falling back for function " << MF.getName() << "\n";
306 return false;
307 }
308
309 // Determine if there are any calls in this machine function. Ported from
310 // SelectionDAG.
311 MachineFrameInfo &MFI = MF.getFrameInfo();
312 for (const auto &MBB : MF) {
313 if (MFI.hasCalls() && MF.hasInlineAsm())
314 break;
315
316 for (const auto &MI : MBB) {
317 if ((MI.isCall() && !MI.isReturn()) || MI.isStackAligningInlineAsm())
318 MFI.setHasCalls(true);
319 if (MI.isInlineAsm())
320 MF.setHasInlineAsm(true);
321 }
322 }
323
324 // FIXME: FinalizeISel pass calls finalizeLowering, so it's called twice.
325 auto &TLI = *MF.getSubtarget().getTargetLowering();
326 TLI.finalizeLowering(MF);
327
328 LLVM_DEBUG({
329 dbgs() << "Rules covered by selecting function: " << MF.getName() << ":";
330 for (auto RuleID : CoverageInfo.covered())
331 dbgs() << " id" << RuleID;
332 dbgs() << "\n\n";
333 });
334 CoverageInfo.emit(CoveragePrefix,
335 TLI.getTargetMachine().getTarget().getBackendName());
336
337 // If we successfully selected the function nothing is going to use the vreg
338 // types after us (otherwise MIRPrinter would need them). Make sure the types
339 // disappear.
340 MRI.clearVirtRegTypes();
341
342 // FIXME: Should we accurately track changes?
343 return true;
344}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
amdgpu AMDGPU Register Bank Select
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
Definition: DebugCounter.h:182
#define LLVM_DEBUG(X)
Definition: Debug.h:101
@ Default
Definition: DwarfDebug.cpp:87
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
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:72
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1828
bool hasOptNone() const
Do not optimize this function (-O0).
Definition: Function.h:671
virtual void setupMF(MachineFunction &mf, GISelKnownBits *kb, CodeGenCoverage *covinfo=nullptr, ProfileSummaryInfo *psi=nullptr, BlockFrequencyInfo *bfi=nullptr)
Setup per-MF executor state.
To use KnownBitsInfo analysis in a pass, KnownBitsInfo &Info = getAnalysis<GISelKnownBitsInfoAnalysis...
This pass is responsible for selecting generic machine instructions to target-specific instructions.
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
virtual bool select(MachineInstr &I)=0
Select the (possibly generic) instruction I to only use target-specific opcodes.
void setTargetPassConfig(const TargetPassConfig *T)
void setRemarkEmitter(MachineOptimizationRemarkEmitter *M)
constexpr bool isValid() const
Definition: LowLevelType.h:137
constexpr TypeSize getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
Definition: LowLevelType.h:185
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.
MachineFunctionProperties & set(Property P)
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:69
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.
CodeGenOptLevel 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
static constexpr bool isKnownGT(const FixedOrScalableQuantity &LHS, const FixedOrScalableQuantity &RHS)
Definition: TypeSize.h:210
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
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:1582
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:199
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:273
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.
CodeGenOptLevel
Code generation optimization level.
Definition: CodeGen.h:54
void getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU)
Modify analysis usage so it preserves passes required for the SelectionDAG fallback.
Definition: Utils.cpp:1072
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:220
#define MORE()
Definition: regcomp.c:252