LLVM  8.0.0svn
InstructionSelect.cpp
Go to the documentation of this file.
1 //===- llvm/CodeGen/GlobalISel/InstructionSelect.cpp - InstructionSelect ---==//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 /// This file implements the InstructionSelect class.
11 //===----------------------------------------------------------------------===//
12 
15 #include "llvm/ADT/Twine.h"
24 #include "llvm/Config/config.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/Function.h"
28 #include "llvm/Support/Debug.h"
30 
31 #define DEBUG_TYPE "instruction-select"
32 
33 using namespace llvm;
34 
35 #ifdef LLVM_GISEL_COV_PREFIX
37  CoveragePrefix("gisel-coverage-prefix", cl::init(LLVM_GISEL_COV_PREFIX),
38  cl::desc("Record GlobalISel rule coverage files of this "
39  "prefix if instrumentation was generated"));
40 #else
41 static const std::string CoveragePrefix = "";
42 #endif
43 
44 char InstructionSelect::ID = 0;
46  "Select target instructions out of generic instructions",
47  false, false)
50  "Select target instructions out of generic instructions",
51  false, false)
52 
53 InstructionSelect::InstructionSelect() : MachineFunctionPass(ID) {
55 }
56 
61 }
62 
64  // If the ISel pipeline failed, do not bother running that pass.
65  if (MF.getProperties().hasProperty(
67  return false;
68 
69  LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n');
70 
71  const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
73  CodeGenCoverage CoverageInfo;
74  assert(ISel && "Cannot work without InstructionSelector");
75 
76  // An optimization remark emitter. Used to report failures.
77  MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
78 
79  // FIXME: There are many other MF/MFI fields we need to initialize.
80 
82 #ifndef NDEBUG
83  // Check that our input is fully legal: we require the function to have the
84  // Legalized property, so it should be.
85  // FIXME: This should be in the MachineVerifier, as the RegBankSelected
86  // property check already is.
88  if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
89  reportGISelFailure(MF, TPC, MORE, "gisel-select",
90  "instruction is not legal", *MI);
91  return false;
92  }
93 #endif
94  // FIXME: We could introduce new blocks and will need to fix the outer loop.
95  // Until then, keep track of the number of blocks to assert that we don't.
96  const size_t NumBlocks = MF.size();
97 
98  for (MachineBasicBlock *MBB : post_order(&MF)) {
99  if (MBB->empty())
100  continue;
101 
102  // Select instructions in reverse block order. We permit erasing so have
103  // to resort to manually iterating and recognizing the begin (rend) case.
104  bool ReachedBegin = false;
105  for (auto MII = std::prev(MBB->end()), Begin = MBB->begin();
106  !ReachedBegin;) {
107 #ifndef NDEBUG
108  // Keep track of the insertion range for debug printing.
109  const auto AfterIt = std::next(MII);
110 #endif
111  // Select this instruction.
112  MachineInstr &MI = *MII;
113 
114  // And have our iterator point to the next instruction, if there is one.
115  if (MII == Begin)
116  ReachedBegin = true;
117  else
118  --MII;
119 
120  LLVM_DEBUG(dbgs() << "Selecting: \n " << MI);
121 
122  // We could have folded this instruction away already, making it dead.
123  // If so, erase it.
124  if (isTriviallyDead(MI, MRI)) {
125  LLVM_DEBUG(dbgs() << "Is dead; erasing.\n");
127  continue;
128  }
129 
130  if (!ISel->select(MI, CoverageInfo)) {
131  // FIXME: It would be nice to dump all inserted instructions. It's
132  // not obvious how, esp. considering select() can insert after MI.
133  reportGISelFailure(MF, TPC, MORE, "gisel-select", "cannot select", MI);
134  return false;
135  }
136 
137  // Dump the range of instructions that MI expanded into.
138  LLVM_DEBUG({
139  auto InsertedBegin = ReachedBegin ? MBB->begin() : std::next(MII);
140  dbgs() << "Into:\n";
141  for (auto &InsertedMI : make_range(InsertedBegin, AfterIt))
142  dbgs() << " " << InsertedMI;
143  dbgs() << '\n';
144  });
145  }
146  }
147 
149 
150  for (MachineBasicBlock &MBB : MF) {
151  if (MBB.empty())
152  continue;
153 
154  // Try to find redundant copies b/w vregs of the same register class.
155  bool ReachedBegin = false;
156  for (auto MII = std::prev(MBB.end()), Begin = MBB.begin(); !ReachedBegin;) {
157  // Select this instruction.
158  MachineInstr &MI = *MII;
159 
160  // And have our iterator point to the next instruction, if there is one.
161  if (MII == Begin)
162  ReachedBegin = true;
163  else
164  --MII;
165  if (MI.getOpcode() != TargetOpcode::COPY)
166  continue;
167  unsigned SrcReg = MI.getOperand(1).getReg();
168  unsigned DstReg = MI.getOperand(0).getReg();
171  auto SrcRC = MRI.getRegClass(SrcReg);
172  auto DstRC = MRI.getRegClass(DstReg);
173  if (SrcRC == DstRC) {
174  MRI.replaceRegWith(DstReg, SrcReg);
176  }
177  }
178  }
179  }
180 
181  // Now that selection is complete, there are no more generic vregs. Verify
182  // that the size of the now-constrained vreg is unchanged and that it has a
183  // register class.
184  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
185  unsigned VReg = TargetRegisterInfo::index2VirtReg(I);
186 
187  MachineInstr *MI = nullptr;
188  if (!MRI.def_empty(VReg))
189  MI = &*MRI.def_instr_begin(VReg);
190  else if (!MRI.use_empty(VReg))
191  MI = &*MRI.use_instr_begin(VReg);
192  if (!MI)
193  continue;
194 
195  const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg);
196  if (!RC) {
197  reportGISelFailure(MF, TPC, MORE, "gisel-select",
198  "VReg has no regclass after selection", *MI);
199  return false;
200  }
201 
202  const LLT Ty = MRI.getType(VReg);
203  if (Ty.isValid() && Ty.getSizeInBits() > TRI.getRegSizeInBits(*RC)) {
205  MF, TPC, MORE, "gisel-select",
206  "VReg's low-level type and register class have different sizes", *MI);
207  return false;
208  }
209  }
210 
211  if (MF.size() != NumBlocks) {
212  MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure",
213  MF.getFunction().getSubprogram(),
214  /*MBB=*/nullptr);
215  R << "inserting blocks is not supported yet";
216  reportGISelFailure(MF, TPC, MORE, R);
217  return false;
218  }
219 
220  auto &TLI = *MF.getSubtarget().getTargetLowering();
221  TLI.finalizeLowering(MF);
222 
223  LLVM_DEBUG({
224  dbgs() << "Rules covered by selecting function: " << MF.getName() << ":";
225  for (auto RuleID : CoverageInfo.covered())
226  dbgs() << " id" << RuleID;
227  dbgs() << "\n\n";
228  });
229  CoverageInfo.emit(CoveragePrefix,
230  MF.getSubtarget()
231  .getTargetLowering()
232  ->getTargetMachine()
233  .getTarget()
234  .getBackendName());
235 
236  // If we successfully selected the function nothing is going to use the vreg
237  // types after us (otherwise MIRPrinter would need them). Make sure the types
238  // disappear.
239  MRI.clearVirtRegTypes();
240 
241  // FIXME: Should we accurately track changes?
242  return true;
243 }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
void clearVirtRegTypes()
Remove all types associated to virtual registers (after instruction selection and constraining of all...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU)
Modify analysis usage so it preserves passes required for the SelectionDAG fallback.
Definition: Utils.cpp:238
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
void initializeInstructionSelectPass(PassRegistry &)
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
const MachineFunctionProperties & getProperties() const
Get the function properties.
unsigned size() const
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
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
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
bool emit(StringRef FilePrefix, StringRef BackendName) const
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:409
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...
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
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
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:251
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:133
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:135
Representation of each machine instruction.
Definition: MachineInstr.h:64
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
virtual const InstructionSelector * getInstructionSelector() const
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
IRTranslator LLVM IR MI
inst_range instructions(Function *F)
Definition: InstIterator.h:134
#define LLVM_DEBUG(X)
Definition: Debug.h:123
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414
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:156
This file describes how to lower LLVM code to machine code.