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
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 /// True if the function currently processing is in the function printing list
65 /// (i.e. `-filter-print-funcs`).
66 /// This is primarily used by ISEL_DUMP, which spans in multiple member
67 /// functions. Storing the filter result here so that we only need to do the
68 /// filtering once.
69 bool MatchFilterFuncName = false;
70
71 explicit SelectionDAGISel(char &ID, TargetMachine &tm,
73 ~SelectionDAGISel() override;
74
75 const TargetLowering *getTargetLowering() const { return TLI; }
76
77 void getAnalysisUsage(AnalysisUsage &AU) const override;
78
80
81 virtual void emitFunctionEntryCode() {}
82
83 /// PreprocessISelDAG - This hook allows targets to hack on the graph before
84 /// instruction selection starts.
85 virtual void PreprocessISelDAG() {}
86
87 /// PostprocessISelDAG() - This hook allows the target to hack on the graph
88 /// right after selection.
89 virtual void PostprocessISelDAG() {}
90
91 /// Main hook for targets to transform nodes into machine nodes.
92 virtual void Select(SDNode *N) = 0;
93
94 /// SelectInlineAsmMemoryOperand - Select the specified address as a target
95 /// addressing mode, according to the specified constraint. If this does
96 /// not match or is not implemented, return true. The resultant operands
97 /// (which will appear in the machine instruction) should be added to the
98 /// OutOps vector.
99 virtual bool
101 InlineAsm::ConstraintCode ConstraintID,
102 std::vector<SDValue> &OutOps) {
103 return true;
104 }
105
106 /// IsProfitableToFold - Returns true if it's profitable to fold the specific
107 /// operand node N of U during instruction selection that starts at Root.
108 virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const;
109
110 /// IsLegalToFold - Returns true if the specific operand node N of
111 /// U can be folded during instruction selection that starts at Root.
112 /// FIXME: This is a static member function because the MSP430/X86
113 /// targets, which uses it during isel. This could become a proper member.
114 static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
116 bool IgnoreChains = false);
117
118 static void InvalidateNodeId(SDNode *N);
119 static int getUninvalidatedNodeId(SDNode *N);
120
121 static void EnforceNodeIdInvariant(SDNode *N);
122
123 // Opcodes used by the DAG state machine:
184 // Space-optimized forms that implicitly encode VT.
197
206
215
239
241 // Space-optimized forms that implicitly encode integer VT.
247 // Space-optimized forms that implicitly encode integer VT.
278 // Space-optimized forms that implicitly encode number of result VTs.
282 // Space-optimized forms that implicitly encode EmitNodeInfo.
290 // Space-optimized forms that implicitly encode number of result VTs.
294 // Space-optimized forms that implicitly encode EmitNodeInfo.
308 // Contains offset in table for pattern being selected
310 };
311
312 enum {
313 OPFL_None = 0, // Node has no chain or glue input and isn't variadic.
314 OPFL_Chain = 1, // Node has a chain input.
315 OPFL_GlueInput = 2, // Node has a glue input.
316 OPFL_GlueOutput = 4, // Node has a glue output.
317 OPFL_MemRefs = 8, // Node gets accumulated MemRefs.
318 OPFL_Variadic0 = 1<<4, // Node is variadic, root has 0 fixed inputs.
319 OPFL_Variadic1 = 2<<4, // Node is variadic, root has 1 fixed inputs.
320 OPFL_Variadic2 = 3<<4, // Node is variadic, root has 2 fixed inputs.
321 OPFL_Variadic3 = 4<<4, // Node is variadic, root has 3 fixed inputs.
322 OPFL_Variadic4 = 5<<4, // Node is variadic, root has 4 fixed inputs.
323 OPFL_Variadic5 = 6<<4, // Node is variadic, root has 5 fixed inputs.
324 OPFL_Variadic6 = 7<<4, // Node is variadic, root has 6 fixed inputs.
325
327 };
328
329 /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
330 /// number of fixed arity values that should be skipped when copying from the
331 /// root.
332 static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
333 return ((Flags&OPFL_VariadicInfo) >> 4)-1;
334 }
335
336
337protected:
338 /// DAGSize - Size of DAG being instruction selected.
339 ///
340 unsigned DAGSize = 0;
341
342 /// ReplaceUses - replace all uses of the old node F with the use
343 /// of the new node T.
346 EnforceNodeIdInvariant(T.getNode());
347 }
348
349 /// ReplaceUses - replace all uses of the old nodes F with the use
350 /// of the new nodes T.
351 void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) {
353 for (unsigned i = 0; i < Num; ++i)
354 EnforceNodeIdInvariant(T[i].getNode());
355 }
356
357 /// ReplaceUses - replace all uses of the old node F with the use
358 /// of the new node T.
362 }
363
364 /// Replace all uses of \c F with \c T, then remove \c F from the DAG.
369 }
370
371 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
372 /// by tblgen. Others should not call it.
373 void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
374 const SDLoc &DL);
375
376 /// getPatternForIndex - Patterns selected by tablegen during ISEL
377 virtual StringRef getPatternForIndex(unsigned index) {
378 llvm_unreachable("Tblgen should generate the implementation of this!");
379 }
380
381 /// getIncludePathForIndex - get the td source location of pattern instantiation
382 virtual StringRef getIncludePathForIndex(unsigned index) {
383 llvm_unreachable("Tblgen should generate the implementation of this!");
384 }
385
387 return CurDAG->shouldOptForSize();
388 }
389
390public:
391 // Calls to these predicates are generated by tblgen.
393 int64_t DesiredMaskS) const;
395 int64_t DesiredMaskS) const;
396
397
398 /// CheckPatternPredicate - This function is generated by tblgen in the
399 /// target. It runs the specified pattern predicate and returns true if it
400 /// succeeds or false if it fails. The number is a private implementation
401 /// detail to the code tblgen produces.
402 virtual bool CheckPatternPredicate(unsigned PredNo) const {
403 llvm_unreachable("Tblgen should generate the implementation of this!");
404 }
405
406 /// CheckNodePredicate - This function is generated by tblgen in the target.
407 /// It runs node predicate number PredNo and returns true if it succeeds or
408 /// false if it fails. The number is a private implementation
409 /// detail to the code tblgen produces.
410 virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {
411 llvm_unreachable("Tblgen should generate the implementation of this!");
412 }
413
414 /// CheckNodePredicateWithOperands - This function is generated by tblgen in
415 /// 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 detail to the
418 /// code tblgen produces.
420 SDNode *N, unsigned PredNo,
421 const SmallVectorImpl<SDValue> &Operands) const {
422 llvm_unreachable("Tblgen should generate the implementation of this!");
423 }
424
425 virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N,
426 unsigned PatternNo,
427 SmallVectorImpl<std::pair<SDValue, SDNode*> > &Result) {
428 llvm_unreachable("Tblgen should generate the implementation of this!");
429 }
430
431 virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {
432 llvm_unreachable("Tblgen should generate this!");
433 }
434
435 void SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
436 unsigned TableSize);
437
438 /// Return true if complex patterns for this target can mutate the
439 /// DAG.
440 virtual bool ComplexPatternFuncMutatesDAG() const {
441 return false;
442 }
443
444 /// Return whether the node may raise an FP exception.
445 bool mayRaiseFPException(SDNode *Node) const;
446
447 bool isOrEquivalentToAdd(const SDNode *N) const;
448
449private:
450
451 // Calls to these functions are generated by tblgen.
452 void Select_INLINEASM(SDNode *N);
453 void Select_READ_REGISTER(SDNode *Op);
454 void Select_WRITE_REGISTER(SDNode *Op);
455 void Select_UNDEF(SDNode *N);
456 void CannotYetSelect(SDNode *N);
457
458 void Select_FREEZE(SDNode *N);
459 void Select_ARITH_FENCE(SDNode *N);
460 void Select_MEMBARRIER(SDNode *N);
461
462 void Select_CONVERGENCECTRL_ANCHOR(SDNode *N);
463 void Select_CONVERGENCECTRL_ENTRY(SDNode *N);
464 void Select_CONVERGENCECTRL_LOOP(SDNode *N);
465
466 void pushStackMapLiveVariable(SmallVectorImpl<SDValue> &Ops, SDValue Operand,
467 SDLoc DL);
468 void Select_STACKMAP(SDNode *N);
469 void Select_PATCHPOINT(SDNode *N);
470
471 void Select_JUMP_TABLE_DEBUG_INFO(SDNode *N);
472
473private:
474 void DoInstructionSelection();
475 SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
476 ArrayRef<SDValue> Ops, unsigned EmitNodeInfo);
477
478 /// Prepares the landing pad to take incoming values or do other EH
479 /// personality specific tasks. Returns true if the block should be
480 /// instruction selected, false if no code should be emitted for it.
481 bool PrepareEHLandingPad();
482
483 // Mark and Report IPToState for each Block under AsynchEH
484 void reportIPToStateForBlocks(MachineFunction *Fn);
485
486 /// Perform instruction selection on all basic blocks in the function.
487 void SelectAllBasicBlocks(const Function &Fn);
488
489 /// Perform instruction selection on a single basic block, for
490 /// instructions between \p Begin and \p End. \p HadTailCall will be set
491 /// to true if a call in the block was translated as a tail call.
492 void SelectBasicBlock(BasicBlock::const_iterator Begin,
494 bool &HadTailCall);
495 void FinishBasicBlock();
496
497 void CodeGenAndEmitDAG();
498
499 /// Generate instructions for lowering the incoming arguments of the
500 /// given function.
501 void LowerArguments(const Function &F);
502
503 void ComputeLiveOutVRegInfo();
504
505 /// Create the scheduler. If a specific scheduler was specified
506 /// via the SchedulerRegistry, use it, otherwise select the
507 /// one preferred by the target.
508 ///
509 ScheduleDAGSDNodes *CreateScheduler();
510
511 /// OpcodeOffset - This is a cache used to dispatch efficiently into isel
512 /// state machines that start with a OPC_SwitchOpcode node.
513 std::vector<unsigned> OpcodeOffset;
514
515 void UpdateChains(SDNode *NodeToMatch, SDValue InputChain,
516 SmallVectorImpl<SDNode *> &ChainNodesMatched,
517 bool isMorphNodeTo);
518};
519
520}
521
522#endif /* LLVM_CODEGEN_SELECTIONDAGISEL_H */
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
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:165
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,...
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)
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.
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: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:76
#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.