LLVM 18.0.0git
SelectionDAGISel.h
Go to the documentation of this file.
1//===-- llvm/CodeGen/SelectionDAGISel.h - Common Base Class------*- C++ -*-===//
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// This file implements the SelectionDAGISel class, which is used as the common
10// base class for SelectionDAG-based instruction selectors.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_CODEGEN_SELECTIONDAGISEL_H
15#define LLVM_CODEGEN_SELECTIONDAGISEL_H
16
19#include "llvm/IR/BasicBlock.h"
20#include <memory>
21
22namespace llvm {
23class AAResults;
24class AssumptionCache;
25class TargetInstrInfo;
26class TargetMachine;
27class SelectionDAGBuilder;
28class SDValue;
29class MachineRegisterInfo;
30class MachineFunction;
31class OptimizationRemarkEmitter;
32class TargetLowering;
33class TargetLibraryInfo;
34class FunctionLoweringInfo;
35class SwiftErrorValueTracking;
36class GCFunctionInfo;
37class ScheduleDAGSDNodes;
38
39/// SelectionDAGISel - This is the common base class used for SelectionDAG-based
40/// pattern-matching instruction selectors.
42public:
45 std::unique_ptr<FunctionLoweringInfo> FuncInfo;
50 std::unique_ptr<SelectionDAGBuilder> SDB;
51 AAResults *AA = nullptr;
52 AssumptionCache *AC = nullptr;
53 GCFunctionInfo *GFI = nullptr;
59
60 /// Current optimization remark emitter.
61 /// Used to report things like combines and FastISel failures.
62 std::unique_ptr<OptimizationRemarkEmitter> ORE;
63
64 explicit SelectionDAGISel(char &ID, TargetMachine &tm,
66 ~SelectionDAGISel() override;
67
68 const TargetLowering *getTargetLowering() const { return TLI; }
69
70 void getAnalysisUsage(AnalysisUsage &AU) const override;
71
73
74 virtual void emitFunctionEntryCode() {}
75
76 /// PreprocessISelDAG - This hook allows targets to hack on the graph before
77 /// instruction selection starts.
78 virtual void PreprocessISelDAG() {}
79
80 /// PostprocessISelDAG() - This hook allows the target to hack on the graph
81 /// right after selection.
82 virtual void PostprocessISelDAG() {}
83
84 /// Main hook for targets to transform nodes into machine nodes.
85 virtual void Select(SDNode *N) = 0;
86
87 /// SelectInlineAsmMemoryOperand - Select the specified address as a target
88 /// addressing mode, according to the specified constraint. If this does
89 /// not match or is not implemented, return true. The resultant operands
90 /// (which will appear in the machine instruction) should be added to the
91 /// OutOps vector.
92 virtual bool
94 InlineAsm::ConstraintCode ConstraintID,
95 std::vector<SDValue> &OutOps) {
96 return true;
97 }
98
99 /// IsProfitableToFold - Returns true if it's profitable to fold the specific
100 /// operand node N of U during instruction selection that starts at Root.
101 virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const;
102
103 /// IsLegalToFold - Returns true if the specific operand node N of
104 /// U can be folded during instruction selection that starts at Root.
105 /// FIXME: This is a static member function because the MSP430/X86
106 /// targets, which uses it during isel. This could become a proper member.
107 static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
109 bool IgnoreChains = false);
110
111 static void InvalidateNodeId(SDNode *N);
112 static int getUninvalidatedNodeId(SDNode *N);
113
114 static void EnforceNodeIdInvariant(SDNode *N);
115
116 // Opcodes used by the DAG state machine:
153
167 // Space-optimized forms that implicitly encode number of result VTs.
170 // Space-optimized forms that implicitly encode number of result VTs.
173 // Contains offset in table for pattern being selected
175 };
176
177 enum {
178 OPFL_None = 0, // Node has no chain or glue input and isn't variadic.
179 OPFL_Chain = 1, // Node has a chain input.
180 OPFL_GlueInput = 2, // Node has a glue input.
181 OPFL_GlueOutput = 4, // Node has a glue output.
182 OPFL_MemRefs = 8, // Node gets accumulated MemRefs.
183 OPFL_Variadic0 = 1<<4, // Node is variadic, root has 0 fixed inputs.
184 OPFL_Variadic1 = 2<<4, // Node is variadic, root has 1 fixed inputs.
185 OPFL_Variadic2 = 3<<4, // Node is variadic, root has 2 fixed inputs.
186 OPFL_Variadic3 = 4<<4, // Node is variadic, root has 3 fixed inputs.
187 OPFL_Variadic4 = 5<<4, // Node is variadic, root has 4 fixed inputs.
188 OPFL_Variadic5 = 6<<4, // Node is variadic, root has 5 fixed inputs.
189 OPFL_Variadic6 = 7<<4, // Node is variadic, root has 6 fixed inputs.
190
192 };
193
194 /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
195 /// number of fixed arity values that should be skipped when copying from the
196 /// root.
197 static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
198 return ((Flags&OPFL_VariadicInfo) >> 4)-1;
199 }
200
201
202protected:
203 /// DAGSize - Size of DAG being instruction selected.
204 ///
205 unsigned DAGSize = 0;
206
207 /// ReplaceUses - replace all uses of the old node F with the use
208 /// of the new node T.
211 EnforceNodeIdInvariant(T.getNode());
212 }
213
214 /// ReplaceUses - replace all uses of the old nodes F with the use
215 /// of the new nodes T.
216 void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) {
218 for (unsigned i = 0; i < Num; ++i)
219 EnforceNodeIdInvariant(T[i].getNode());
220 }
221
222 /// ReplaceUses - replace all uses of the old node F with the use
223 /// of the new node T.
227 }
228
229 /// Replace all uses of \c F with \c T, then remove \c F from the DAG.
234 }
235
236 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
237 /// by tblgen. Others should not call it.
238 void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
239 const SDLoc &DL);
240
241 /// getPatternForIndex - Patterns selected by tablegen during ISEL
242 virtual StringRef getPatternForIndex(unsigned index) {
243 llvm_unreachable("Tblgen should generate the implementation of this!");
244 }
245
246 /// getIncludePathForIndex - get the td source location of pattern instantiation
247 virtual StringRef getIncludePathForIndex(unsigned index) {
248 llvm_unreachable("Tblgen should generate the implementation of this!");
249 }
250
252 return CurDAG->shouldOptForSize();
253 }
254
255public:
256 // Calls to these predicates are generated by tblgen.
258 int64_t DesiredMaskS) const;
260 int64_t DesiredMaskS) const;
261
262
263 /// CheckPatternPredicate - This function is generated by tblgen in the
264 /// target. It runs the specified pattern predicate and returns true if it
265 /// succeeds or false if it fails. The number is a private implementation
266 /// detail to the code tblgen produces.
267 virtual bool CheckPatternPredicate(unsigned PredNo) const {
268 llvm_unreachable("Tblgen should generate the implementation of this!");
269 }
270
271 /// CheckNodePredicate - This function is generated by tblgen in the target.
272 /// It runs node predicate number PredNo and returns true if it succeeds or
273 /// false if it fails. The number is a private implementation
274 /// detail to the code tblgen produces.
275 virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {
276 llvm_unreachable("Tblgen should generate the implementation of this!");
277 }
278
279 /// CheckNodePredicateWithOperands - This function is generated by tblgen in
280 /// the target.
281 /// It runs node predicate number PredNo and returns true if it succeeds or
282 /// false if it fails. The number is a private implementation detail to the
283 /// code tblgen produces.
285 SDNode *N, unsigned PredNo,
286 const SmallVectorImpl<SDValue> &Operands) const {
287 llvm_unreachable("Tblgen should generate the implementation of this!");
288 }
289
290 virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N,
291 unsigned PatternNo,
292 SmallVectorImpl<std::pair<SDValue, SDNode*> > &Result) {
293 llvm_unreachable("Tblgen should generate the implementation of this!");
294 }
295
296 virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {
297 llvm_unreachable("Tblgen should generate this!");
298 }
299
300 void SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
301 unsigned TableSize);
302
303 /// Return true if complex patterns for this target can mutate the
304 /// DAG.
305 virtual bool ComplexPatternFuncMutatesDAG() const {
306 return false;
307 }
308
309 /// Return whether the node may raise an FP exception.
310 bool mayRaiseFPException(SDNode *Node) const;
311
312 bool isOrEquivalentToAdd(const SDNode *N) const;
313
314private:
315
316 // Calls to these functions are generated by tblgen.
317 void Select_INLINEASM(SDNode *N);
318 void Select_READ_REGISTER(SDNode *Op);
319 void Select_WRITE_REGISTER(SDNode *Op);
320 void Select_UNDEF(SDNode *N);
321 void CannotYetSelect(SDNode *N);
322
323 void Select_FREEZE(SDNode *N);
324 void Select_ARITH_FENCE(SDNode *N);
325 void Select_MEMBARRIER(SDNode *N);
326
327 void pushStackMapLiveVariable(SmallVectorImpl<SDValue> &Ops, SDValue Operand,
328 SDLoc DL);
329 void Select_STACKMAP(SDNode *N);
330 void Select_PATCHPOINT(SDNode *N);
331
332 void Select_JUMP_TABLE_DEBUG_INFO(SDNode *N);
333
334private:
335 void DoInstructionSelection();
336 SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
337 ArrayRef<SDValue> Ops, unsigned EmitNodeInfo);
338
339 /// Prepares the landing pad to take incoming values or do other EH
340 /// personality specific tasks. Returns true if the block should be
341 /// instruction selected, false if no code should be emitted for it.
342 bool PrepareEHLandingPad();
343
344 // Mark and Report IPToState for each Block under AsynchEH
345 void reportIPToStateForBlocks(MachineFunction *Fn);
346
347 /// Perform instruction selection on all basic blocks in the function.
348 void SelectAllBasicBlocks(const Function &Fn);
349
350 /// Perform instruction selection on a single basic block, for
351 /// instructions between \p Begin and \p End. \p HadTailCall will be set
352 /// to true if a call in the block was translated as a tail call.
353 void SelectBasicBlock(BasicBlock::const_iterator Begin,
355 bool &HadTailCall);
356 void FinishBasicBlock();
357
358 void CodeGenAndEmitDAG();
359
360 /// Generate instructions for lowering the incoming arguments of the
361 /// given function.
362 void LowerArguments(const Function &F);
363
364 void ComputeLiveOutVRegInfo();
365
366 /// Create the scheduler. If a specific scheduler was specified
367 /// via the SchedulerRegistry, use it, otherwise select the
368 /// one preferred by the target.
369 ///
370 ScheduleDAGSDNodes *CreateScheduler();
371
372 /// OpcodeOffset - This is a cache used to dispatch efficiently into isel
373 /// state machines that start with a OPC_SwitchOpcode node.
374 std::vector<unsigned> OpcodeOffset;
375
376 void UpdateChains(SDNode *NodeToMatch, SDValue InputChain,
377 SmallVectorImpl<SDNode *> &ChainNodesMatched,
378 bool isMorphNodeTo);
379};
380
381}
382
383#endif /* LLVM_CODEGEN_SELECTIONDAGISEL_H */
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
bool End
Definition: ELF_riscv.cpp:469
#define F(x, y, z)
Definition: MD5.cpp:55
mir Rename Register Operands
Value * RHS
Value * LHS
Represent the analysis usage information of a pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A cache of @llvm.assume calls within a function.
InstListType::const_iterator const_iterator
Definition: BasicBlock.h:88
This class represents an Operation in the Expression.
Garbage collection metadata for a single function.
Definition: GCMetadata.h:77
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Wrapper class for IR location info (IR ordering and DebugLoc) to be passed into SDNode creation funct...
Represents one node in the SelectionDAG.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
std::unique_ptr< FunctionLoweringInfo > FuncInfo
SmallPtrSet< const Instruction *, 4 > ElidedArgCopyInstrs
virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op, InlineAsm::ConstraintCode ConstraintID, std::vector< SDValue > &OutOps)
SelectInlineAsmMemoryOperand - Select the specified address as a target addressing mode,...
bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS, int64_t DesiredMaskS) const
CheckOrMask - The isel is trying to match something like (or X, 255).
AssumptionCache * AC
const TargetLowering * TLI
virtual void PostprocessISelDAG()
PostprocessISelDAG() - This hook allows the target to hack on the graph right after selection.
MachineFunction * MF
virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const
CheckNodePredicate - This function is generated by tblgen in the target.
std::unique_ptr< OptimizationRemarkEmitter > ORE
Current optimization remark emitter.
MachineRegisterInfo * RegInfo
unsigned DAGSize
DAGSize - Size of DAG being instruction selected.
bool isOrEquivalentToAdd(const SDNode *N) const
virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N, unsigned PatternNo, SmallVectorImpl< std::pair< SDValue, SDNode * > > &Result)
virtual bool CheckPatternPredicate(unsigned PredNo) const
CheckPatternPredicate - This function is generated by tblgen in the target.
static int getNumFixedFromVariadicInfo(unsigned Flags)
getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the number of fixed arity values ...
const TargetLibraryInfo * LibInfo
static int getUninvalidatedNodeId(SDNode *N)
const TargetInstrInfo * TII
CodeGenOptLevel OptLevel
virtual bool CheckNodePredicateWithOperands(SDNode *N, unsigned PredNo, const SmallVectorImpl< SDValue > &Operands) const
CheckNodePredicateWithOperands - This function is generated by tblgen in the target.
GCFunctionInfo * GFI
void SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable, unsigned TableSize)
virtual void Select(SDNode *N)=0
Main hook for targets to transform nodes into machine nodes.
void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num)
ReplaceUses - replace all uses of the old nodes F with the use of the new nodes T.
static void EnforceNodeIdInvariant(SDNode *N)
virtual void emitFunctionEntryCode()
void ReplaceUses(SDValue F, SDValue T)
ReplaceUses - replace all uses of the old node F with the use of the new node T.
virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const
IsProfitableToFold - Returns true if it's profitable to fold the specific operand node N of U during ...
virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo)
void SelectInlineAsmMemoryOperands(std::vector< SDValue > &Ops, const SDLoc &DL)
SelectInlineAsmMemoryOperands - Calls to this are automatically generated by tblgen.
static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root, CodeGenOptLevel OptLevel, bool IgnoreChains=false)
IsLegalToFold - Returns true if the specific operand node N of U can be folded during instruction sel...
virtual bool ComplexPatternFuncMutatesDAG() const
Return true if complex patterns for this target can mutate the DAG.
void ReplaceUses(SDNode *F, SDNode *T)
ReplaceUses - replace all uses of the old node F with the use of the new node T.
virtual void PreprocessISelDAG()
PreprocessISelDAG - This hook allows targets to hack on the graph before instruction selection starts...
bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS, int64_t DesiredMaskS) const
CheckAndMask - The isel is trying to match something like (and X, 255).
SwiftErrorValueTracking * SwiftError
virtual StringRef getPatternForIndex(unsigned index)
getPatternForIndex - Patterns selected by tablegen during ISEL
bool mayRaiseFPException(SDNode *Node) const
Return whether the node may raise an FP exception.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
std::unique_ptr< SelectionDAGBuilder > SDB
void ReplaceNode(SDNode *F, SDNode *T)
Replace all uses of F with T, then remove F from the DAG.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static void InvalidateNodeId(SDNode *N)
const TargetLowering * getTargetLowering() const
bool shouldOptForSize(const MachineFunction *MF) const
virtual StringRef getIncludePathForIndex(unsigned index)
getIncludePathForIndex - get the td source location of pattern instantiation
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Definition: SelectionDAG.h:225
void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To, unsigned Num)
Like ReplaceAllUsesOfValueWith, but for multiple values at once.
bool shouldOptForSize() const
void ReplaceAllUsesWith(SDValue From, SDValue To)
Modify anything using 'From' to use 'To' instead.
void RemoveDeadNode(SDNode *N)
Remove the specified node from the system.
void ReplaceAllUsesOfValueWith(SDValue From, SDValue To)
Replace any uses of From with To, leaving uses of other values produced by From.getNode() alone.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
TargetInstrInfo - Interface to description of machine instruction set.
Provides information about what library functions are available for the current target.
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:78
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
CodeGenOptLevel
Code generation optimization level.
Definition: CodeGen.h:54
#define N
This represents a list of ValueType's that has been intern'd by a SelectionDAG.