LLVM 20.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
20#include "llvm/IR/BasicBlock.h"
21#include <memory>
22
23namespace llvm {
24class AAResults;
25class AssumptionCache;
26class TargetInstrInfo;
27class TargetMachine;
28class SSPLayoutInfo;
29class SelectionDAGBuilder;
30class SDValue;
31class MachineRegisterInfo;
32class MachineFunction;
33class OptimizationRemarkEmitter;
34class TargetLowering;
35class TargetLibraryInfo;
36class TargetTransformInfo;
37class FunctionLoweringInfo;
38class SwiftErrorValueTracking;
39class GCFunctionInfo;
40class ScheduleDAGSDNodes;
41
42/// SelectionDAGISel - This is the common base class used for SelectionDAG-based
43/// pattern-matching instruction selectors.
45public:
48 std::unique_ptr<FunctionLoweringInfo> FuncInfo;
54 std::unique_ptr<SelectionDAGBuilder> SDB;
55 AAResults *AA = nullptr;
56 AssumptionCache *AC = nullptr;
57 GCFunctionInfo *GFI = nullptr;
58 SSPLayoutInfo *SP = nullptr;
59#if LLVM_ENABLE_ABI_BREAKING_CHECKS
60 TargetTransformInfo *TTI = nullptr;
61#endif
67
68 /// Current optimization remark emitter.
69 /// Used to report things like combines and FastISel failures.
70 std::unique_ptr<OptimizationRemarkEmitter> ORE;
71
72 /// True if the function currently processing is in the function printing list
73 /// (i.e. `-filter-print-funcs`).
74 /// This is primarily used by ISEL_DUMP, which spans in multiple member
75 /// functions. Storing the filter result here so that we only need to do the
76 /// filtering once.
77 bool MatchFilterFuncName = false;
79
82 virtual ~SelectionDAGISel();
83
84 const TargetLowering *getTargetLowering() const { return TLI; }
85
88
89 virtual bool runOnMachineFunction(MachineFunction &mf);
90
91 virtual void emitFunctionEntryCode() {}
92
93 /// PreprocessISelDAG - This hook allows targets to hack on the graph before
94 /// instruction selection starts.
95 virtual void PreprocessISelDAG() {}
96
97 /// PostprocessISelDAG() - This hook allows the target to hack on the graph
98 /// right after selection.
99 virtual void PostprocessISelDAG() {}
100
101 /// Main hook for targets to transform nodes into machine nodes.
102 virtual void Select(SDNode *N) = 0;
103
104 /// SelectInlineAsmMemoryOperand - Select the specified address as a target
105 /// addressing mode, according to the specified constraint. If this does
106 /// not match or is not implemented, return true. The resultant operands
107 /// (which will appear in the machine instruction) should be added to the
108 /// OutOps vector.
109 virtual bool
111 InlineAsm::ConstraintCode ConstraintID,
112 std::vector<SDValue> &OutOps) {
113 return true;
114 }
115
116 /// IsProfitableToFold - Returns true if it's profitable to fold the specific
117 /// operand node N of U during instruction selection that starts at Root.
118 virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const;
119
120 /// IsLegalToFold - Returns true if the specific operand node N of
121 /// U can be folded during instruction selection that starts at Root.
122 /// FIXME: This is a static member function because the MSP430/X86
123 /// targets, which uses it during isel. This could become a proper member.
124 static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
126 bool IgnoreChains = false);
127
128 static void InvalidateNodeId(SDNode *N);
129 static int getUninvalidatedNodeId(SDNode *N);
130
131 static void EnforceNodeIdInvariant(SDNode *N);
132
133 // Opcodes used by the DAG state machine:
194 // Space-optimized forms that implicitly encode VT.
207
216
225
249
251 // Space-optimized forms that implicitly encode integer VT.
257 // Space-optimized forms that implicitly encode integer VT.
288 // Space-optimized forms that implicitly encode number of result VTs.
292 // Space-optimized forms that implicitly encode EmitNodeInfo.
300 // Space-optimized forms that implicitly encode number of result VTs.
304 // Space-optimized forms that implicitly encode EmitNodeInfo.
318 // Contains offset in table for pattern being selected
320 };
321
322 enum {
323 OPFL_None = 0, // Node has no chain or glue input and isn't variadic.
324 OPFL_Chain = 1, // Node has a chain input.
325 OPFL_GlueInput = 2, // Node has a glue input.
326 OPFL_GlueOutput = 4, // Node has a glue output.
327 OPFL_MemRefs = 8, // Node gets accumulated MemRefs.
328 OPFL_Variadic0 = 1<<4, // Node is variadic, root has 0 fixed inputs.
329 OPFL_Variadic1 = 2<<4, // Node is variadic, root has 1 fixed inputs.
330 OPFL_Variadic2 = 3<<4, // Node is variadic, root has 2 fixed inputs.
331 OPFL_Variadic3 = 4<<4, // Node is variadic, root has 3 fixed inputs.
332 OPFL_Variadic4 = 5<<4, // Node is variadic, root has 4 fixed inputs.
333 OPFL_Variadic5 = 6<<4, // Node is variadic, root has 5 fixed inputs.
334 OPFL_Variadic6 = 7<<4, // Node is variadic, root has 6 fixed inputs.
335
337 };
338
339 /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
340 /// number of fixed arity values that should be skipped when copying from the
341 /// root.
342 static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
343 return ((Flags&OPFL_VariadicInfo) >> 4)-1;
344 }
345
346
347protected:
348 /// DAGSize - Size of DAG being instruction selected.
349 ///
350 unsigned DAGSize = 0;
351
352 /// ReplaceUses - replace all uses of the old node F with the use
353 /// of the new node T.
356 EnforceNodeIdInvariant(T.getNode());
357 }
358
359 /// ReplaceUses - replace all uses of the old nodes F with the use
360 /// of the new nodes T.
361 void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) {
363 for (unsigned i = 0; i < Num; ++i)
365 }
366
367 /// ReplaceUses - replace all uses of the old node F with the use
368 /// of the new node T.
372 }
373
374 /// Replace all uses of \c F with \c T, then remove \c F from the DAG.
379 }
380
381 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
382 /// by tblgen. Others should not call it.
383 void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
384 const SDLoc &DL);
385
386 /// getPatternForIndex - Patterns selected by tablegen during ISEL
387 virtual StringRef getPatternForIndex(unsigned index) {
388 llvm_unreachable("Tblgen should generate the implementation of this!");
389 }
390
391 /// getIncludePathForIndex - get the td source location of pattern instantiation
392 virtual StringRef getIncludePathForIndex(unsigned index) {
393 llvm_unreachable("Tblgen should generate the implementation of this!");
394 }
395
397 return CurDAG->shouldOptForSize();
398 }
399
400public:
401 // Calls to these predicates are generated by tblgen.
403 int64_t DesiredMaskS) const;
405 int64_t DesiredMaskS) const;
406
407
408 /// CheckPatternPredicate - This function is generated by tblgen in the
409 /// target. It runs the specified pattern predicate and returns true if it
410 /// succeeds or false if it fails. The number is a private implementation
411 /// detail to the code tblgen produces.
412 virtual bool CheckPatternPredicate(unsigned PredNo) const {
413 llvm_unreachable("Tblgen should generate the implementation of this!");
414 }
415
416 /// CheckNodePredicate - This function is generated by tblgen in the target.
417 /// It runs node predicate number PredNo and returns true if it succeeds or
418 /// false if it fails. The number is a private implementation
419 /// detail to the code tblgen produces.
420 virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {
421 llvm_unreachable("Tblgen should generate the implementation of this!");
422 }
423
424 /// CheckNodePredicateWithOperands - This function is generated by tblgen in
425 /// the target.
426 /// It runs node predicate number PredNo and returns true if it succeeds or
427 /// false if it fails. The number is a private implementation detail to the
428 /// code tblgen produces.
430 SDNode *N, unsigned PredNo,
431 const SmallVectorImpl<SDValue> &Operands) const {
432 llvm_unreachable("Tblgen should generate the implementation of this!");
433 }
434
435 virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N,
436 unsigned PatternNo,
437 SmallVectorImpl<std::pair<SDValue, SDNode*> > &Result) {
438 llvm_unreachable("Tblgen should generate the implementation of this!");
439 }
440
441 virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {
442 llvm_unreachable("Tblgen should generate this!");
443 }
444
445 void SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
446 unsigned TableSize);
447
448 /// Return true if complex patterns for this target can mutate the
449 /// DAG.
450 virtual bool ComplexPatternFuncMutatesDAG() const {
451 return false;
452 }
453
454 /// Return whether the node may raise an FP exception.
455 bool mayRaiseFPException(SDNode *Node) const;
456
457 bool isOrEquivalentToAdd(const SDNode *N) const;
458
459private:
460
461 // Calls to these functions are generated by tblgen.
462 void Select_INLINEASM(SDNode *N);
463 void Select_READ_REGISTER(SDNode *Op);
464 void Select_WRITE_REGISTER(SDNode *Op);
465 void Select_UNDEF(SDNode *N);
466 void CannotYetSelect(SDNode *N);
467
468 void Select_FREEZE(SDNode *N);
469 void Select_ARITH_FENCE(SDNode *N);
470 void Select_MEMBARRIER(SDNode *N);
471
472 void Select_CONVERGENCECTRL_ANCHOR(SDNode *N);
473 void Select_CONVERGENCECTRL_ENTRY(SDNode *N);
474 void Select_CONVERGENCECTRL_LOOP(SDNode *N);
475
476 void pushStackMapLiveVariable(SmallVectorImpl<SDValue> &Ops, SDValue Operand,
477 SDLoc DL);
478 void Select_STACKMAP(SDNode *N);
479 void Select_PATCHPOINT(SDNode *N);
480
481 void Select_JUMP_TABLE_DEBUG_INFO(SDNode *N);
482
483private:
484 void DoInstructionSelection();
485 SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
486 ArrayRef<SDValue> Ops, unsigned EmitNodeInfo);
487
488 /// Prepares the landing pad to take incoming values or do other EH
489 /// personality specific tasks. Returns true if the block should be
490 /// instruction selected, false if no code should be emitted for it.
491 bool PrepareEHLandingPad();
492
493 // Mark and Report IPToState for each Block under AsynchEH
494 void reportIPToStateForBlocks(MachineFunction *Fn);
495
496 /// Perform instruction selection on all basic blocks in the function.
497 void SelectAllBasicBlocks(const Function &Fn);
498
499 /// Perform instruction selection on a single basic block, for
500 /// instructions between \p Begin and \p End. \p HadTailCall will be set
501 /// to true if a call in the block was translated as a tail call.
502 void SelectBasicBlock(BasicBlock::const_iterator Begin,
504 bool &HadTailCall);
505 void FinishBasicBlock();
506
507 void CodeGenAndEmitDAG();
508
509 /// Generate instructions for lowering the incoming arguments of the
510 /// given function.
511 void LowerArguments(const Function &F);
512
513 void ComputeLiveOutVRegInfo();
514
515 /// Create the scheduler. If a specific scheduler was specified
516 /// via the SchedulerRegistry, use it, otherwise select the
517 /// one preferred by the target.
518 ///
519 ScheduleDAGSDNodes *CreateScheduler();
520
521 /// OpcodeOffset - This is a cache used to dispatch efficiently into isel
522 /// state machines that start with a OPC_SwitchOpcode node.
523 std::vector<unsigned> OpcodeOffset;
524
525 void UpdateChains(SDNode *NodeToMatch, SDValue InputChain,
526 SmallVectorImpl<SDNode *> &ChainNodesMatched,
527 bool isMorphNodeTo);
528};
529
531 std::unique_ptr<SelectionDAGISel> Selector;
532
533public:
534 SelectionDAGISelLegacy(char &ID, std::unique_ptr<SelectionDAGISel> S);
535
536 ~SelectionDAGISelLegacy() override = default;
537
538 void getAnalysisUsage(AnalysisUsage &AU) const override;
539
540 bool runOnMachineFunction(MachineFunction &MF) override;
541};
542
543class SelectionDAGISelPass : public PassInfoMixin<SelectionDAGISelPass> {
544 std::unique_ptr<SelectionDAGISel> Selector;
545
546protected:
547 SelectionDAGISelPass(std::unique_ptr<SelectionDAGISel> Selector)
548 : Selector(std::move(Selector)) {}
549
550public:
553};
554}
555
556#endif /* LLVM_CODEGEN_SELECTIONDAGISEL_H */
static msgpack::DocNode getNode(msgpack::DocNode DN, msgpack::Type Type, MCValue Val)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
bool End
Definition: ELF_riscv.cpp:480
#define F(x, y, z)
Definition: MD5.cpp:55
mir Rename Register Operands
Value * RHS
Value * LHS
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
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:168
This class represents an Operation in the Expression.
Garbage collection metadata for a single function.
Definition: GCMetadata.h:78
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
This class contains meta information specific to a module.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
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.
~SelectionDAGISelLegacy() override=default
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
SelectionDAGISelPass(std::unique_ptr< SelectionDAGISel > Selector)
PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
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
void initializeAnalysisResults(MachineFunctionAnalysisManager &MFAM)
MachineModuleInfo * MMI
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)
bool MatchFilterFuncName
True if the function currently processing is in the function printing list (i.e.
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.
std::unique_ptr< SelectionDAGBuilder > SDB
void ReplaceNode(SDNode *F, SDNode *T)
Replace all uses of F with T, then remove F from the DAG.
virtual bool runOnMachineFunction(MachineFunction &mf)
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:227
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:479
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
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:77
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
#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
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1849
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
#define N
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:69
This represents a list of ValueType's that has been intern'd by a SelectionDAG.