LLVM 24.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
21#include "llvm/IR/BasicBlock.h"
22#include <memory>
23
24namespace llvm {
25class AAResults;
26class AssumptionCache;
27class TargetInstrInfo;
28class TargetMachine;
29class SSPLayoutInfo;
31class SDValue;
33class MachineFunction;
35class TargetLowering;
40class GCFunctionInfo;
42
43/// SelectionDAGISel - This is the common base class used for SelectionDAG-based
44/// pattern-matching instruction selectors.
46public:
50
51 std::unique_ptr<FunctionLoweringInfo> FuncInfo;
52 std::unique_ptr<SwiftErrorValueTracking> SwiftError;
56 std::unique_ptr<SelectionDAGBuilder> SDB;
57 mutable std::optional<BatchAAResults> BatchAA;
58 AssumptionCache *AC = nullptr;
59 GCFunctionInfo *GFI = nullptr;
60 SSPLayoutInfo *SP = nullptr;
61 const TargetTransformInfo *TTI = nullptr;
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
80 // HwMode to be used by getValueTypeForHwMode. This will be initialized
81 // based on the subtarget used by the MachineFunction.
82 unsigned HwMode;
83
86 virtual ~SelectionDAGISel();
87
88 /// Returns a (possibly null) pointer to the current BatchAAResults.
90 if (BatchAA.has_value())
91 return &BatchAA.value();
92 return nullptr;
93 }
94
95 const TargetLowering *getTargetLowering() const { return TLI; }
96
97 void initializeAnalysisResults(MachineFunctionAnalysisManager &MFAM);
98 void initializeAnalysisResults(MachineFunctionPass &MFP);
99
100 virtual bool runOnMachineFunction(MachineFunction &mf);
101
102 virtual void emitFunctionEntryCode() {}
103
104 /// PreprocessISelDAG - This hook allows targets to hack on the graph before
105 /// instruction selection starts.
106 virtual void PreprocessISelDAG() {}
107
108 /// PostprocessISelDAG() - This hook allows the target to hack on the graph
109 /// right after selection.
110 virtual void PostprocessISelDAG() {}
111
112 /// Main hook for targets to transform nodes into machine nodes.
113 virtual void Select(SDNode *N) = 0;
114
115 /// SelectInlineAsmMemoryOperand - Select the specified address as a target
116 /// addressing mode, according to the specified constraint. If this does
117 /// not match or is not implemented, return true. The resultant operands
118 /// (which will appear in the machine instruction) should be added to the
119 /// OutOps vector.
120 virtual bool
122 InlineAsm::ConstraintCode ConstraintID,
123 std::vector<SDValue> &OutOps) {
124 return true;
125 }
126
127 /// IsProfitableToFold - Returns true if it's profitable to fold the specific
128 /// operand node N of U during instruction selection that starts at Root.
129 virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const;
130
131 /// IsLegalToFold - Returns true if the specific operand node N of
132 /// U can be folded during instruction selection that starts at Root.
133 /// FIXME: This is a static member function because the MSP430/X86
134 /// targets, which uses it during isel. This could become a proper member.
135 static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
136 CodeGenOptLevel OptLevel,
137 bool IgnoreChains = false);
138
139 static void InvalidateNodeId(SDNode *N);
140 static int getUninvalidatedNodeId(SDNode *N);
141
142 static void EnforceNodeIdInvariant(SDNode *N);
143
144 // Opcodes used by the DAG state machine:
206 // Space-optimized forms that implicitly encode VT.
210 // Space-optimized form that implicitly encodes index 0.
223
232
241
250
259
285
287 // Space-optimized forms that implicitly encode integer VT.
326 // Space-optimized forms that implicitly encode number of result VTs.
330 // Space-optimized forms that implicitly encode EmitNodeInfo.
338 // Space-optimized forms that implicitly encode number of result VTs.
342 // Space-optimized forms that implicitly encode EmitNodeInfo.
353 // Contains 32-bit offset in table for pattern being selected
355 };
356
357 enum {
358 OPFL_None = 0, // Node has no chain or glue input and isn't variadic.
359 OPFL_Chain = 1, // Node has a chain input.
360 OPFL_GlueInput = 2, // Node has a glue input.
361 OPFL_GlueOutput = 4, // Node has a glue output.
362 OPFL_MemRefs = 8, // Node gets accumulated MemRefs.
363 OPFL_Variadic0 = 1 << 4, // Node is variadic, root has 0 fixed inputs.
364 OPFL_Variadic1 = 2 << 4, // Node is variadic, root has 1 fixed inputs.
365 OPFL_Variadic2 = 3 << 4, // Node is variadic, root has 2 fixed inputs.
366 OPFL_Variadic3 = 4 << 4, // Node is variadic, root has 3 fixed inputs.
367 OPFL_Variadic4 = 5 << 4, // Node is variadic, root has 4 fixed inputs.
368 OPFL_Variadic5 = 6 << 4, // Node is variadic, root has 5 fixed inputs.
369 OPFL_Variadic6 = 7 << 4, // Node is variadic, root has 6 fixed inputs.
370 OPFL_Variadic7 = 8 << 4, // Node is variadic, root has 7 fixed inputs.
371
372 OPFL_VariadicInfo = 15 << 4 // Mask for extracting the OPFL_VariadicN bits.
373 };
374
375 /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
376 /// number of fixed arity values that should be skipped when copying from the
377 /// root.
378 static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
379 return ((Flags&OPFL_VariadicInfo) >> 4)-1;
380 }
381
382
383protected:
384 /// DAGSize - Size of DAG being instruction selected.
385 ///
386 unsigned DAGSize = 0;
387
388 /// ReplaceUses - replace all uses of the old node F with the use
389 /// of the new node T.
391 CurDAG->ReplaceAllUsesOfValueWith(F, T);
392 EnforceNodeIdInvariant(T.getNode());
393 }
394
395 /// ReplaceUses - replace all uses of the old nodes F with the use
396 /// of the new nodes T.
397 void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) {
398 CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num);
399 for (unsigned i = 0; i < Num; ++i)
401 }
402
403 /// ReplaceUses - replace all uses of the old node F with the use
404 /// of the new node T.
406 CurDAG->ReplaceAllUsesWith(F, T);
408 }
409
410 /// Replace all uses of \c F with \c T, then remove \c F from the DAG.
412 CurDAG->ReplaceAllUsesWith(F, T);
414 CurDAG->RemoveDeadNode(F);
415 }
416
417 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
418 /// by tblgen. Others should not call it.
419 void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
420 const SDLoc &DL);
421
422 /// getPatternForIndex - Patterns selected by tablegen during ISEL
423 virtual StringRef getPatternForIndex(unsigned index) {
424 llvm_unreachable("Tblgen should generate the implementation of this!");
425 }
426
427 /// getIncludePathForIndex - get the td source location of pattern instantiation
428 virtual StringRef getIncludePathForIndex(unsigned index) {
429 llvm_unreachable("Tblgen should generate the implementation of this!");
430 }
431
433 return CurDAG->shouldOptForSize();
434 }
435
436public:
437 // Calls to these predicates are generated by tblgen.
438 bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
439 int64_t DesiredMaskS) const;
440 bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
441 int64_t DesiredMaskS) const;
442
443
444 /// CheckPatternPredicate - This function is generated by tblgen in the
445 /// target. It runs the specified pattern predicate and returns true if it
446 /// succeeds or false if it fails. The number is a private implementation
447 /// detail to the code tblgen produces.
448 virtual bool CheckPatternPredicate(unsigned PredNo) const {
449 llvm_unreachable("Tblgen should generate the implementation of this!");
450 }
451
452 /// CheckNodePredicate - This function is generated by tblgen in the target.
453 /// It runs node predicate number PredNo and returns true if it succeeds or
454 /// false if it fails. The number is a private implementation
455 /// detail to the code tblgen produces.
456 virtual bool CheckNodePredicate(SDValue Op, unsigned PredNo) const {
457 llvm_unreachable("Tblgen should generate the implementation of this!");
458 }
459
460 /// CheckNodePredicateWithOperands - This function is generated by tblgen in
461 /// the target.
462 /// It runs node predicate number PredNo and returns true if it succeeds or
463 /// false if it fails. The number is a private implementation detail to the
464 /// code tblgen produces.
465 virtual bool
468 llvm_unreachable("Tblgen should generate the implementation of this!");
469 }
470
471 virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N,
472 unsigned PatternNo,
473 SmallVectorImpl<std::pair<SDValue, SDNode*> > &Result) {
474 llvm_unreachable("Tblgen should generate the implementation of this!");
475 }
476
477 virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {
478 llvm_unreachable("Tblgen should generate this!");
479 }
480
481 virtual MVT getValueTypeForHwMode(unsigned Index) const {
482 llvm_unreachable("Tblgen should generate the implementation of this!");
483 }
484
485 void SelectCodeCommon(SDNode *NodeToMatch, const uint8_t *MatcherTable,
486 unsigned TableSize, const uint8_t *OperandLists);
487
488 /// Return true if complex patterns for this target can mutate the
489 /// DAG.
490 virtual bool ComplexPatternFuncMutatesDAG() const {
491 return false;
492 }
493
494 /// Return whether the node may raise an FP exception.
495 bool mayRaiseFPException(SDNode *Node) const;
496
497 bool isOrEquivalentToAdd(const SDNode *N) const;
498
499 /// Look through a mask on the amount \p N of a shift that reads only the low
500 /// Log2(\p ShiftWidth) bits of its amount, as many shift instructions do.
501 ///
502 /// Looks through one TRUNCATE that keeps those bits. If the
503 /// result is (and X, C) and C keeps all the bits the shift reads, possibly
504 /// after adding bits known to be zero in X, sets \p ShAmt to X and returns
505 /// true. Otherwise returns false and leaves \p ShAmt unchanged.
506 ///
507 /// This does not look at other users of the AND. Dropping an AND that
508 /// stays live for other users keeps both X and the masked value live, so a
509 /// target that cares about register pressure must check that itself.
510 bool selectShiftAmountMask(SDValue N, unsigned ShiftWidth,
511 SDValue &ShAmt) const;
512
513private:
514
515 // Calls to these functions are generated by tblgen.
516 void Select_INLINEASM(SDNode *N);
517 void Select_READ_REGISTER(SDNode *Op);
518 void Select_WRITE_REGISTER(SDNode *Op);
519 void Select_UNDEF(SDNode *N);
520 void Select_FAKE_USE(SDNode *N);
521 void Select_RELOC_NONE(SDNode *N);
522 void CannotYetSelect(SDNode *N);
523
524 void Select_FREEZE(SDNode *N);
525 void Select_ARITH_FENCE(SDNode *N);
526 void Select_MEMBARRIER(SDNode *N);
527
528 void Select_CONVERGENCECTRL_ANCHOR(SDNode *N);
529 void Select_CONVERGENCECTRL_ENTRY(SDNode *N);
530 void Select_CONVERGENCECTRL_LOOP(SDNode *N);
531
532 void pushStackMapLiveVariable(SmallVectorImpl<SDValue> &Ops, SDValue Operand,
533 SDLoc DL);
534 void Select_STACKMAP(SDNode *N);
535 void Select_PATCHPOINT(SDNode *N);
536
537 void Select_JUMP_TABLE_DEBUG_INFO(SDNode *N);
538
539private:
540 void DoInstructionSelection();
541 SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
542 ArrayRef<SDValue> Ops, unsigned EmitNodeInfo);
543
544 /// Prepares the landing pad to take incoming values or do other EH
545 /// personality specific tasks. Returns true if the block should be
546 /// instruction selected, false if no code should be emitted for it.
547 bool PrepareEHLandingPad();
548
549 // Mark and Report IPToState for each Block under AsynchEH
550 void reportIPToStateForBlocks(MachineFunction *Fn);
551
552 /// Perform instruction selection on all basic blocks in the function.
553 void SelectAllBasicBlocks(const Function &Fn);
554
555 /// Perform instruction selection on a single basic block, for
556 /// instructions between \p Begin and \p End. \p HadTailCall will be set
557 /// to true if a call in the block was translated as a tail call.
558 void SelectBasicBlock(BasicBlock::const_iterator Begin,
560 bool &HadTailCall);
561 void FinishBasicBlock();
562
563 void CodeGenAndEmitDAG();
564
565 /// Generate instructions for lowering the incoming arguments of the
566 /// given function. \p FastISel is true if fast-isel may select other
567 /// instructions in the function.
568 void LowerArguments(const Function &F, bool FastISel);
569
570 void ComputeLiveOutVRegInfo();
571
572 /// Create the scheduler. If a specific scheduler was specified
573 /// via the SchedulerRegistry, use it, otherwise select the
574 /// one preferred by the target.
575 ///
576 ScheduleDAGSDNodes *CreateScheduler();
577
578 /// OpcodeOffset - This is a cache used to dispatch efficiently into isel
579 /// state machines that start with a OPC_SwitchOpcode node.
580 std::vector<unsigned> OpcodeOffset;
581
582 void UpdateChains(SDNode *NodeToMatch, SDValue InputChain,
583 SmallVectorImpl<SDNode *> &ChainNodesMatched,
584 bool isMorphNodeTo);
585};
586
588 std::unique_ptr<SelectionDAGISel> Selector;
589
590public:
591 SelectionDAGISelLegacy(char &ID, std::unique_ptr<SelectionDAGISel> S);
592
593 ~SelectionDAGISelLegacy() override = default;
594
595 void getAnalysisUsage(AnalysisUsage &AU) const override;
596
597 bool runOnMachineFunction(MachineFunction &MF) override;
598};
599
601 : public RequiredPassInfoMixin<SelectionDAGISelPass> {
602 std::unique_ptr<SelectionDAGISel> Selector;
603
604protected:
605 SelectionDAGISelPass(std::unique_ptr<SelectionDAGISel> Selector)
606 : Selector(std::move(Selector)) {}
607
608public:
611};
612}
613
614#endif /* LLVM_CODEGEN_SELECTIONDAGISEL_H */
static msgpack::DocNode getNode(msgpack::DocNode DN, msgpack::Type Type, MCValue Val)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define LLVM_ABI
Definition Compiler.h:211
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
#define F(x, y, z)
Definition MD5.cpp:54
#define T
SI Fold Operands
Value * RHS
Value * LHS
Represent the analysis usage information of a pass.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
A cache of @llvm.assume calls within a function.
InstListType::const_iterator const_iterator
Definition BasicBlock.h:171
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
This is a fast-path instruction selection class that generates poor code and doesn't support illegal ...
Definition FastISel.h:67
FunctionLoweringInfo - This contains information that is global to a function that is used when lower...
Garbage collection metadata for a single function.
Definition GCMetadata.h:80
Tracks which library functions to use for a particular subtarget or function.
Machine Value Type.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
The optimization diagnostic interface.
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
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.
SelectionDAGBuilder - This is the common target-independent lowering implementation that is parameter...
~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.
SelectionDAGISelLegacy(char &ID, std::unique_ptr< SelectionDAGISel > S)
SelectionDAGISelPass(std::unique_ptr< SelectionDAGISel > Selector)
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
std::optional< BatchAAResults > BatchAA
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,...
const TargetTransformInfo * TTI
virtual bool CheckNodePredicate(SDValue Op, unsigned PredNo) const
CheckNodePredicate - This function is generated by tblgen in the target.
virtual bool CheckNodePredicateWithOperands(SDValue Op, unsigned PredNo, ArrayRef< SDValue > Operands) const
CheckNodePredicateWithOperands - This function is generated by tblgen in the target.
const TargetLowering * TLI
virtual void PostprocessISelDAG()
PostprocessISelDAG() - This hook allows the target to hack on the graph right after selection.
std::unique_ptr< OptimizationRemarkEmitter > ORE
Current optimization remark emitter.
MachineRegisterInfo * RegInfo
unsigned DAGSize
DAGSize - Size of DAG being instruction selected.
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
const TargetInstrInfo * TII
std::unique_ptr< SwiftErrorValueTracking > SwiftError
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 SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo)
virtual MVT getValueTypeForHwMode(unsigned Index) const
bool MatchFilterFuncName
True if the function currently processing is in the function printing list (i.e.
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...
BatchAAResults * getBatchAA() const
Returns a (possibly null) pointer to the current BatchAAResults.
virtual StringRef getPatternForIndex(unsigned index)
getPatternForIndex - Patterns selected by tablegen during ISEL
std::unique_ptr< SelectionDAGBuilder > SDB
void ReplaceNode(SDNode *F, SDNode *T)
Replace all uses of F with T, then remove F from the DAG.
const LibcallLoweringInfo * LibcallLowering
SelectionDAGISel(TargetMachine &tm, CodeGenOptLevel OL=CodeGenOptLevel::Default)
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...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
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.
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.
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
CodeGenOptLevel
Code generation optimization level.
Definition CodeGen.h:280
@ Default
-O2, -Os, -Oz
Definition CodeGen.h:283
DWARFExpression::Operation Op
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:1933
@ End
Run the machine verifier once, at the end of the pipeline.
Definition CodeGen.h:320
Implement std::hash so that hash_code can be used in STL containers.
Definition BitVector.h:879
#define N
A CRTP mix-in for passes that should not be skipped.
This represents a list of ValueType's that has been intern'd by a SelectionDAG.