LLVM  10.0.0svn
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/Twine.h"
26 #include "llvm/Config/config.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/Function.h"
30 #include "llvm/Support/Debug.h"
32 
33 #define DEBUG_TYPE "instruction-select"
34 
35 using namespace llvm;
36 
37 #ifdef LLVM_GISEL_COV_PREFIX
39  CoveragePrefix("gisel-coverage-prefix", cl::init(LLVM_GISEL_COV_PREFIX),
40  cl::desc("Record GlobalISel rule coverage files of this "
41  "prefix if instrumentation was generated"));
42 #else
43 static const std::string CoveragePrefix = "";
44 #endif
45 
46 char InstructionSelect::ID = 0;
48  "Select target instructions out of generic instructions",
49  false, false)
53  "Select target instructions out of generic instructions",
54  false, false)
55 
56 InstructionSelect::InstructionSelect() : MachineFunctionPass(ID) { }
57 
64 }
65 
67  // If the ISel pipeline failed, do not bother running that pass.
68  if (MF.getProperties().hasProperty(
70  return false;
71 
72  LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n');
73  GISelKnownBits &KB = getAnalysis<GISelKnownBitsAnalysis>().get(MF);
74 
75  const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
77  CodeGenCoverage CoverageInfo;
78  assert(ISel && "Cannot work without InstructionSelector");
79  ISel->setupMF(MF, KB, CoverageInfo);
80 
81  // An optimization remark emitter. Used to report failures.
82  MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
83 
84  // FIXME: There are many other MF/MFI fields we need to initialize.
85 
87 #ifndef NDEBUG
88  // Check that our input is fully legal: we require the function to have the
89  // Legalized property, so it should be.
90  // FIXME: This should be in the MachineVerifier, as the RegBankSelected
91  // property check already is.
93  if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
94  reportGISelFailure(MF, TPC, MORE, "gisel-select",
95  "instruction is not legal", *MI);
96  return false;
97  }
98  // FIXME: We could introduce new blocks and will need to fix the outer loop.
99  // Until then, keep track of the number of blocks to assert that we don't.
100  const size_t NumBlocks = MF.size();
101 #endif
102 
103  for (MachineBasicBlock *MBB : post_order(&MF)) {
104  if (MBB->empty())
105  continue;
106 
107  // Select instructions in reverse block order. We permit erasing so have
108  // to resort to manually iterating and recognizing the begin (rend) case.
109  bool ReachedBegin = false;
110  for (auto MII = std::prev(MBB->end()), Begin = MBB->begin();
111  !ReachedBegin;) {
112 #ifndef NDEBUG
113  // Keep track of the insertion range for debug printing.
114  const auto AfterIt = std::next(MII);
115 #endif
116  // Select this instruction.
117  MachineInstr &MI = *MII;
118 
119  // And have our iterator point to the next instruction, if there is one.
120  if (MII == Begin)
121  ReachedBegin = true;
122  else
123  --MII;
124 
125  LLVM_DEBUG(dbgs() << "Selecting: \n " << MI);
126 
127  // We could have folded this instruction away already, making it dead.
128  // If so, erase it.
129  if (isTriviallyDead(MI, MRI)) {
130  LLVM_DEBUG(dbgs() << "Is dead; erasing.\n");
132  continue;
133  }
134 
135  if (!ISel->select(MI)) {
136  // FIXME: It would be nice to dump all inserted instructions. It's
137  // not obvious how, esp. considering select() can insert after MI.
138  reportGISelFailure(MF, TPC, MORE, "gisel-select", "cannot select", MI);
139  return false;
140  }
141 
142  // Dump the range of instructions that MI expanded into.
143  LLVM_DEBUG({
144  auto InsertedBegin = ReachedBegin ? MBB->begin() : std::next(MII);
145  dbgs() << "Into:\n";
146  for (auto &InsertedMI : make_range(InsertedBegin, AfterIt))
147  dbgs() << " " << InsertedMI;
148  dbgs() << '\n';
149  });
150  }
151  }
152 
153  for (MachineBasicBlock &MBB : MF) {
154  if (MBB.empty())
155  continue;
156 
157  // Try to find redundant copies b/w vregs of the same register class.
158  bool ReachedBegin = false;
159  for (auto MII = std::prev(MBB.end()), Begin = MBB.begin(); !ReachedBegin;) {
160  // Select this instruction.
161  MachineInstr &MI = *MII;
162 
163  // And have our iterator point to the next instruction, if there is one.
164  if (MII == Begin)
165  ReachedBegin = true;
166  else
167  --MII;
168  if (MI.getOpcode() != TargetOpcode::COPY)
169  continue;
170  Register SrcReg = MI.getOperand(1).getReg();
171  Register DstReg = MI.getOperand(0).getReg();
172  if (Register::isVirtualRegister(SrcReg) &&
173  Register::isVirtualRegister(DstReg)) {
174  auto SrcRC = MRI.getRegClass(SrcReg);
175  auto DstRC = MRI.getRegClass(DstReg);
176  if (SrcRC == DstRC) {
177  MRI.replaceRegWith(DstReg, SrcReg);
179  }
180  }
181  }
182  }
183 
184 #ifndef NDEBUG
185  const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
186  // Now that selection is complete, there are no more generic vregs. Verify
187  // that the size of the now-constrained vreg is unchanged and that it has a
188  // register class.
189  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
190  unsigned VReg = Register::index2VirtReg(I);
191 
192  MachineInstr *MI = nullptr;
193  if (!MRI.def_empty(VReg))
194  MI = &*MRI.def_instr_begin(VReg);
195  else if (!MRI.use_empty(VReg))
196  MI = &*MRI.use_instr_begin(VReg);
197  if (!MI)
198  continue;
199 
200  const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg);
201  if (!RC) {
202  reportGISelFailure(MF, TPC, MORE, "gisel-select",
203  "VReg has no regclass after selection", *MI);
204  return false;
205  }
206 
207  const LLT Ty = MRI.getType(VReg);
208  if (Ty.isValid() && Ty.getSizeInBits() > TRI.getRegSizeInBits(*RC)) {
210  MF, TPC, MORE, "gisel-select",
211  "VReg's low-level type and register class have different sizes", *MI);
212  return false;
213  }
214  }
215 
216  if (MF.size() != NumBlocks) {
217  MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure",
218  MF.getFunction().getSubprogram(),
219  /*MBB=*/nullptr);
220  R << "inserting blocks is not supported yet";
221  reportGISelFailure(MF, TPC, MORE, R);
222  return false;
223  }
224 #endif
225  auto &TLI = *MF.getSubtarget().getTargetLowering();
226  TLI.finalizeLowering(MF);
227 
228  // Determine if there are any calls in this machine function. Ported from
229  // SelectionDAG.
230  MachineFrameInfo &MFI = MF.getFrameInfo();
231  for (const auto &MBB : MF) {
232  if (MFI.hasCalls() && MF.hasInlineAsm())
233  break;
234 
235  for (const auto &MI : MBB) {
236  if ((MI.isCall() && !MI.isReturn()) || MI.isStackAligningInlineAsm())
237  MFI.setHasCalls(true);
238  if (MI.isInlineAsm())
239  MF.setHasInlineAsm(true);
240  }
241  }
242 
243 
244  LLVM_DEBUG({
245  dbgs() << "Rules covered by selecting function: " << MF.getName() << ":";
246  for (auto RuleID : CoverageInfo.covered())
247  dbgs() << " id" << RuleID;
248  dbgs() << "\n\n";
249  });
250  CoverageInfo.emit(CoveragePrefix,
251  MF.getSubtarget()
252  .getTargetLowering()
253  ->getTargetMachine()
254  .getTarget()
255  .getBackendName());
256 
257  // If we successfully selected the function nothing is going to use the vreg
258  // types after us (otherwise MIRPrinter would need them). Make sure the types
259  // disappear.
260  MRI.clearVirtRegTypes();
261 
262  // FIXME: Should we accurately track changes?
263  return true;
264 }
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void clearVirtRegTypes()
Remove all types associated to virtual registers (after instruction selection and constraining of all...
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:431
const MachineFunctionProperties & getProperties() const
Get the function properties.
unsigned size() const
LLT getType(unsigned Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register...
unsigned const TargetRegisterInfo * TRI
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:83
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
bool emit(StringRef FilePrefix, StringRef BackendName) const
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:410
Target-Independent Code Generator Pass Configuration Options.
INITIALIZE_PASS_BEGIN(InstructionSelect, DEBUG_TYPE, "Select target instructions out of generic instructions", false, false) INITIALIZE_PASS_END(InstructionSelect
void eraseFromParentAndMarkDBGValuesForRemoval()
Unlink &#39;this&#39; from the containing basic block and delete it.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
To use KnownBitsInfo analysis in a pass, KnownBitsInfo &Info = getAnalysis<GISelKnownBitsInfoAnalysis...
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
unsigned const MachineRegisterInfo * MRI
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Represent the analysis usage information of a pass.
use_instr_iterator use_instr_begin(unsigned RegNo) const
bool isValid() const
virtual InstructionSelector * getInstructionSelector() const
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
bool def_empty(unsigned RegNo) const
def_empty - Return true if there are no instructions defining the specified register (it may be live-...
iterator_range< po_iterator< T > > post_order(const T &G)
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
static const std::string CoveragePrefix
cl::opt< bool > DisableGISelLegalityCheck
#define DEBUG_TYPE
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
const MachineInstr * machineFunctionIsIllegal(const MachineFunction &MF)
Checks that MIR is fully legal, returns an illegal instruction if it&#39;s not, nullptr otherwise...
The optimization diagnostic interface.
unsigned getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
#define MORE()
Definition: regcomp.c:252
This pass is responsible for selecting generic machine instructions to target-specific instructions...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool use_empty(unsigned RegNo) const
use_empty - Return true if there are no instructions using the specified register.
def_instr_iterator def_instr_begin(unsigned RegNo) const
void replaceRegWith(unsigned FromReg, unsigned ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Provides the logic to select generic machine instructions.
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
Representation of each machine instruction.
Definition: MachineInstr.h:63
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
iterator_range< const_covered_iterator > covered() const
#define I(x, y, z)
Definition: MD5.cpp:58
Diagnostic information for missed-optimization remarks.
const TargetRegisterClass * getRegClassOrNull(unsigned Reg) const
Return the register class of Reg, or null if Reg has not been assigned a register class yet...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool hasProperty(Property P) const
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:69
IRTranslator LLVM IR MI
inst_range instructions(Function *F)
Definition: InstIterator.h:133
unsigned getRegSizeInBits(const TargetRegisterClass &RC) const
Return the size in bits of a register from class RC.
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
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
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
This file describes how to lower LLVM code to machine code.
bool hasCalls() const
Return true if the current function has any function calls.