LLVM 19.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;
53 std::unique_ptr<SelectionDAGBuilder> SDB;
54 AAResults *AA = nullptr;
55 AssumptionCache *AC = nullptr;
56 GCFunctionInfo *GFI = nullptr;
57 SSPLayoutInfo *SP = nullptr;
58#if LLVM_ENABLE_ABI_BREAKING_CHECKS
59 TargetTransformInfo *TTI = nullptr;
60#endif
66
67 /// Current optimization remark emitter.
68 /// Used to report things like combines and FastISel failures.
69 std::unique_ptr<OptimizationRemarkEmitter> ORE;
70
71 /// True if the function currently processing is in the function printing list
72 /// (i.e. `-filter-print-funcs`).
73 /// This is primarily used by ISEL_DUMP, which spans in multiple member
74 /// functions. Storing the filter result here so that we only need to do the
75 /// filtering once.
76 bool MatchFilterFuncName = false;
78
81 virtual ~SelectionDAGISel();
82
83 const TargetLowering *getTargetLowering() const { return TLI; }
84
87
88 virtual bool runOnMachineFunction(MachineFunction &mf);
89
90 virtual void emitFunctionEntryCode() {}
91
92 /// PreprocessISelDAG - This hook allows targets to hack on the graph before
93 /// instruction selection starts.
94 virtual void PreprocessISelDAG() {}
95
96 /// PostprocessISelDAG() - This hook allows the target to hack on the graph
97 /// right after selection.
98 virtual void PostprocessISelDAG() {}
99
100 /// Main hook for targets to transform nodes into machine nodes.
101 virtual void Select(SDNode *N) = 0;
102
103 /// SelectInlineAsmMemoryOperand - Select the specified address as a target
104 /// addressing mode, according to the specified constraint. If this does
105 /// not match or is not implemented, return true. The resultant operands
106 /// (which will appear in the machine instruction) should be added to the
107 /// OutOps vector.
108 virtual bool
110 InlineAsm::ConstraintCode ConstraintID,
111 std::vector<SDValue> &OutOps) {
112 return true;
113 }
114
115 /// IsProfitableToFold - Returns true if it's profitable to fold the specific
116 /// operand node N of U during instruction selection that starts at Root.
117 virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const;
118
119 /// IsLegalToFold - Returns true if the specific operand node N of
120 /// U can be folded during instruction selection that starts at Root.
121 /// FIXME: This is a static member function because the MSP430/X86
122 /// targets, which uses it during isel. This could become a proper member.
123 static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
125 bool IgnoreChains = false);
126
127 static void InvalidateNodeId(SDNode *N);
128 static int getUninvalidatedNodeId(SDNode *N);
129
130 static void EnforceNodeIdInvariant(SDNode *N);
131
132 // Opcodes used by the DAG state machine:
193 // Space-optimized forms that implicitly encode VT.
206
215
224
248
250 // Space-optimized forms that implicitly encode integer VT.
256 // Space-optimized forms that implicitly encode integer VT.
287 // Space-optimized forms that implicitly encode number of result VTs.
291 // Space-optimized forms that implicitly encode EmitNodeInfo.
299 // Space-optimized forms that implicitly encode number of result VTs.
303 // Space-optimized forms that implicitly encode EmitNodeInfo.
317 // Contains offset in table for pattern being selected
319 };
320
321 enum {
322 OPFL_None = 0, // Node has no chain or glue input and isn't variadic.
323 OPFL_Chain = 1, // Node has a chain input.
324 OPFL_GlueInput = 2, // Node has a glue input.
325 OPFL_GlueOutput = 4, // Node has a glue output.
326 OPFL_MemRefs = 8, // Node gets accumulated MemRefs.
327 OPFL_Variadic0 = 1<<4, // Node is variadic, root has 0 fixed inputs.
328 OPFL_Variadic1 = 2<<4, // Node is variadic, root has 1 fixed inputs.
329 OPFL_Variadic2 = 3<<4, // Node is variadic, root has 2 fixed inputs.
330 OPFL_Variadic3 = 4<<4, // Node is variadic, root has 3 fixed inputs.
331 OPFL_Variadic4 = 5<<4, // Node is variadic, root has 4 fixed inputs.
332 OPFL_Variadic5 = 6<<4, // Node is variadic, root has 5 fixed inputs.
333 OPFL_Variadic6 = 7<<4, // Node is variadic, root has 6 fixed inputs.
334
336 };
337
338 /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
339 /// number of fixed arity values that should be skipped when copying from the
340 /// root.
341 static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
342 return ((Flags&OPFL_VariadicInfo) >> 4)-1;
343 }
344
345
346protected:
347 /// DAGSize - Size of DAG being instruction selected.
348 ///
349 unsigned DAGSize = 0;
350
351 /// ReplaceUses - replace all uses of the old node F with the use
352 /// of the new node T.
355 EnforceNodeIdInvariant(T.getNode());
356 }
357
358 /// ReplaceUses - replace all uses of the old nodes F with the use
359 /// of the new nodes T.
360 void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) {
362 for (unsigned i = 0; i < Num; ++i)
364 }
365
366 /// ReplaceUses - replace all uses of the old node F with the use
367 /// of the new node T.
371 }
372
373 /// Replace all uses of \c F with \c T, then remove \c F from the DAG.
378 }
379
380 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
381 /// by tblgen. Others should not call it.
382 void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
383 const SDLoc &DL);
384
385 /// getPatternForIndex - Patterns selected by tablegen during ISEL
386 virtual StringRef getPatternForIndex(unsigned index) {
387 llvm_unreachable("Tblgen should generate the implementation of this!");
388 }
389
390 /// getIncludePathForIndex - get the td source location of pattern instantiation
391 virtual StringRef getIncludePathForIndex(unsigned index) {
392 llvm_unreachable("Tblgen should generate the implementation of this!");
393 }
394
396 return CurDAG->shouldOptForSize();
397 }
398
399public:
400 // Calls to these predicates are generated by tblgen.
402 int64_t DesiredMaskS) const;
404 int64_t DesiredMaskS) const;
405
406
407 /// CheckPatternPredicate - This function is generated by tblgen in the
408 /// target. It runs the specified pattern predicate and returns true if it
409 /// succeeds or false if it fails. The number is a private implementation
410 /// detail to the code tblgen produces.
411 virtual bool CheckPatternPredicate(unsigned PredNo) const {
412 llvm_unreachable("Tblgen should generate the implementation of this!");
413 }
414
415 /// CheckNodePredicate - This function is generated by tblgen in the target.
416 /// It runs node predicate number PredNo and returns true if it succeeds or
417 /// false if it fails. The number is a private implementation
418 /// detail to the code tblgen produces.
419 virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {
420 llvm_unreachable("Tblgen should generate the implementation of this!");
421 }
422
423 /// CheckNodePredicateWithOperands - This function is generated by tblgen in
424 /// the target.
425 /// It runs node predicate number PredNo and returns true if it succeeds or
426 /// false if it fails. The number is a private implementation detail to the
427 /// code tblgen produces.
429 SDNode *N, unsigned PredNo,
430 const SmallVectorImpl<SDValue> &Operands) const {
431 llvm_unreachable("Tblgen should generate the implementation of this!");
432 }
433
434 virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N,
435 unsigned PatternNo,
436 SmallVectorImpl<std::pair<SDValue, SDNode*> > &Result) {
437 llvm_unreachable("Tblgen should generate the implementation of this!");
438 }
439
440 virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {
441 llvm_unreachable("Tblgen should generate this!");
442 }
443
444 void SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
445 unsigned TableSize);
446
447 /// Return true if complex patterns for this target can mutate the
448 /// DAG.
449 virtual bool ComplexPatternFuncMutatesDAG() const {
450 return false;
451 }
452
453 /// Return whether the node may raise an FP exception.
454 bool mayRaiseFPException(SDNode *Node) const;
455
456 bool isOrEquivalentToAdd(const SDNode *N) const;
457
458private:
459
460 // Calls to these functions are generated by tblgen.
461 void Select_INLINEASM(SDNode *N);
462 void Select_READ_REGISTER(SDNode *Op);
463 void Select_WRITE_REGISTER(SDNode *Op);
464 void Select_UNDEF(SDNode *N);
465 void CannotYetSelect(SDNode *N);
466
467 void Select_FREEZE(SDNode *N);
468 void Select_ARITH_FENCE(SDNode *N);
469 void Select_MEMBARRIER(SDNode *N);
470
471 void Select_CONVERGENCECTRL_ANCHOR(SDNode *N);
472 void Select_CONVERGENCECTRL_ENTRY(SDNode *N);
473 void Select_CONVERGENCECTRL_LOOP(SDNode *N);
474
475 void pushStackMapLiveVariable(SmallVectorImpl<SDValue> &Ops, SDValue Operand,
476 SDLoc DL);
477 void Select_STACKMAP(SDNode *N);
478 void Select_PATCHPOINT(SDNode *N);
479
480 void Select_JUMP_TABLE_DEBUG_INFO(SDNode *N);
481
482private:
483 void DoInstructionSelection();
484 SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
485 ArrayRef<SDValue> Ops, unsigned EmitNodeInfo);
486
487 /// Prepares the landing pad to take incoming values or do other EH
488 /// personality specific tasks. Returns true if the block should be
489 /// instruction selected, false if no code should be emitted for it.
490 bool PrepareEHLandingPad();
491
492 // Mark and Report IPToState for each Block under AsynchEH
493 void reportIPToStateForBlocks(MachineFunction *Fn);
494
495 /// Perform instruction selection on all basic blocks in the function.
496 void SelectAllBasicBlocks(const Function &Fn);
497
498 /// Perform instruction selection on a single basic block, for
499 /// instructions between \p Begin and \p End. \p HadTailCall will be set
500 /// to true if a call in the block was translated as a tail call.
501 void SelectBasicBlock(BasicBlock::const_iterator Begin,
503 bool &HadTailCall);
504 void FinishBasicBlock();
505
506 void CodeGenAndEmitDAG();
507
508 /// Generate instructions for lowering the incoming arguments of the
509 /// given function.
510 void LowerArguments(const Function &F);
511
512 void ComputeLiveOutVRegInfo();
513
514 /// Create the scheduler. If a specific scheduler was specified
515 /// via the SchedulerRegistry, use it, otherwise select the
516 /// one preferred by the target.
517 ///
518 ScheduleDAGSDNodes *CreateScheduler();
519
520 /// OpcodeOffset - This is a cache used to dispatch efficiently into isel
521 /// state machines that start with a OPC_SwitchOpcode node.
522 std::vector<unsigned> OpcodeOffset;
523
524 void UpdateChains(SDNode *NodeToMatch, SDValue InputChain,
525 SmallVectorImpl<SDNode *> &ChainNodesMatched,
526 bool isMorphNodeTo);
527};
528
530 std::unique_ptr<SelectionDAGISel> Selector;
531
532public:
533 SelectionDAGISelLegacy(char &ID, std::unique_ptr<SelectionDAGISel> S);
534
535 ~SelectionDAGISelLegacy() override = default;
536
537 void getAnalysisUsage(AnalysisUsage &AU) const override;
538
539 bool runOnMachineFunction(MachineFunction &MF) override;
540};
541
542class SelectionDAGISelPass : public PassInfoMixin<SelectionDAGISelPass> {
543 std::unique_ptr<SelectionDAGISel> Selector;
544
545protected:
546 SelectionDAGISelPass(std::unique_ptr<SelectionDAGISel> Selector)
547 : Selector(std::move(Selector)) {}
548
549public:
552};
553}
554
555#endif /* LLVM_CODEGEN_SELECTIONDAGISEL_H */
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static msgpack::DocNode getNode(msgpack::DocNode DN, msgpack::Type Type, MCValue Val)
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:242
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:167
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...
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:109
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)
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:427
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:68
This represents a list of ValueType's that has been intern'd by a SelectionDAG.