1 //===-- llvm/CodeGen/SelectionDAGISel.h - Common Base Class------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements the SelectionDAGISel class, which is used as the common
10 // base class for SelectionDAG-based instruction selectors.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CODEGEN_SELECTIONDAGISEL_H
15 #define LLVM_CODEGEN_SELECTIONDAGISEL_H
17 #include "llvm/CodeGen/MachineFunctionPass.h"
18 #include "llvm/CodeGen/SelectionDAG.h"
19 #include "llvm/CodeGen/TargetSubtargetInfo.h"
20 #include "llvm/IR/BasicBlock.h"
21 #include "llvm/Pass.h"
27 class SelectionDAGBuilder;
29 class MachineRegisterInfo;
30 class MachineBasicBlock;
31 class MachineFunction;
33 class OptimizationRemarkEmitter;
35 class TargetLibraryInfo;
36 class FunctionLoweringInfo;
37 class ScheduleHazardRecognizer;
38 class SwiftErrorValueTracking;
40 class ScheduleDAGSDNodes;
42 class ProfileSummaryInfo;
43 class BlockFrequencyInfo;
45 /// SelectionDAGISel - This is the common base class used for SelectionDAG-based
46 /// pattern-matching instruction selectors.
47 class SelectionDAGISel : public MachineFunctionPass {
50 const TargetLibraryInfo *LibInfo;
51 std::unique_ptr<FunctionLoweringInfo> FuncInfo;
52 SwiftErrorValueTracking *SwiftError;
54 MachineRegisterInfo *RegInfo;
56 std::unique_ptr<SelectionDAGBuilder> SDB;
59 CodeGenOpt::Level OptLevel;
60 const TargetInstrInfo *TII;
61 const TargetLowering *TLI;
63 SmallPtrSet<const Instruction *, 4> ElidedArgCopyInstrs;
65 /// Current optimization remark emitter.
66 /// Used to report things like combines and FastISel failures.
67 std::unique_ptr<OptimizationRemarkEmitter> ORE;
71 explicit SelectionDAGISel(TargetMachine &tm,
72 CodeGenOpt::Level OL = CodeGenOpt::Default);
73 ~SelectionDAGISel() override;
75 const TargetLowering *getTargetLowering() const { return TLI; }
77 void getAnalysisUsage(AnalysisUsage &AU) const override;
79 bool runOnMachineFunction(MachineFunction &MF) override;
81 virtual void EmitFunctionEntryCode() {}
83 /// PreprocessISelDAG - This hook allows targets to hack on the graph before
84 /// instruction selection starts.
85 virtual void PreprocessISelDAG() {}
87 /// PostprocessISelDAG() - This hook allows the target to hack on the graph
88 /// right after selection.
89 virtual void PostprocessISelDAG() {}
91 /// Main hook for targets to transform nodes into machine nodes.
92 virtual void Select(SDNode *N) = 0;
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
99 virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op,
100 unsigned ConstraintID,
101 std::vector<SDValue> &OutOps) {
105 /// IsProfitableToFold - Returns true if it's profitable to fold the specific
106 /// operand node N of U during instruction selection that starts at Root.
107 virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const;
109 /// IsLegalToFold - Returns true if the specific operand node N of
110 /// U can be folded during instruction selection that starts at Root.
111 /// FIXME: This is a static member function because the MSP430/X86
112 /// targets, which uses it during isel. This could become a proper member.
113 static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
114 CodeGenOpt::Level OptLevel,
115 bool IgnoreChains = false);
117 static void InvalidateNodeId(SDNode *N);
118 static int getUninvalidatedNodeId(SDNode *N);
120 static void EnforceNodeIdInvariant(SDNode *N);
122 // Opcodes used by the DAG state machine:
123 enum BuiltinOpcodes {
126 OPC_RecordChild0, OPC_RecordChild1, OPC_RecordChild2, OPC_RecordChild3,
127 OPC_RecordChild4, OPC_RecordChild5, OPC_RecordChild6, OPC_RecordChild7,
129 OPC_CaptureGlueInput,
131 OPC_MoveChild0, OPC_MoveChild1, OPC_MoveChild2, OPC_MoveChild3,
132 OPC_MoveChild4, OPC_MoveChild5, OPC_MoveChild6, OPC_MoveChild7,
135 OPC_CheckChild0Same, OPC_CheckChild1Same,
136 OPC_CheckChild2Same, OPC_CheckChild3Same,
137 OPC_CheckPatternPredicate,
139 OPC_CheckPredicateWithOperands,
145 OPC_CheckChild0Type, OPC_CheckChild1Type, OPC_CheckChild2Type,
146 OPC_CheckChild3Type, OPC_CheckChild4Type, OPC_CheckChild5Type,
147 OPC_CheckChild6Type, OPC_CheckChild7Type,
149 OPC_CheckChild0Integer, OPC_CheckChild1Integer, OPC_CheckChild2Integer,
150 OPC_CheckChild3Integer, OPC_CheckChild4Integer,
151 OPC_CheckCondCode, OPC_CheckChild2CondCode,
154 OPC_CheckAndImm, OPC_CheckOrImm,
155 OPC_CheckImmAllOnesV,
156 OPC_CheckImmAllZerosV,
157 OPC_CheckFoldableChainNode,
162 OPC_EmitConvertToTarget,
163 OPC_EmitMergeInputChains,
164 OPC_EmitMergeInputChains1_0,
165 OPC_EmitMergeInputChains1_1,
166 OPC_EmitMergeInputChains1_2,
171 // Space-optimized forms that implicitly encode number of result VTs.
172 OPC_EmitNode0, OPC_EmitNode1, OPC_EmitNode2,
174 // Space-optimized forms that implicitly encode number of result VTs.
175 OPC_MorphNodeTo0, OPC_MorphNodeTo1, OPC_MorphNodeTo2,
177 // Contains offset in table for pattern being selected
182 OPFL_None = 0, // Node has no chain or glue input and isn't variadic.
183 OPFL_Chain = 1, // Node has a chain input.
184 OPFL_GlueInput = 2, // Node has a glue input.
185 OPFL_GlueOutput = 4, // Node has a glue output.
186 OPFL_MemRefs = 8, // Node gets accumulated MemRefs.
187 OPFL_Variadic0 = 1<<4, // Node is variadic, root has 0 fixed inputs.
188 OPFL_Variadic1 = 2<<4, // Node is variadic, root has 1 fixed inputs.
189 OPFL_Variadic2 = 3<<4, // Node is variadic, root has 2 fixed inputs.
190 OPFL_Variadic3 = 4<<4, // Node is variadic, root has 3 fixed inputs.
191 OPFL_Variadic4 = 5<<4, // Node is variadic, root has 4 fixed inputs.
192 OPFL_Variadic5 = 6<<4, // Node is variadic, root has 5 fixed inputs.
193 OPFL_Variadic6 = 7<<4, // Node is variadic, root has 6 fixed inputs.
195 OPFL_VariadicInfo = OPFL_Variadic6
198 /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
199 /// number of fixed arity values that should be skipped when copying from the
201 static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
202 return ((Flags&OPFL_VariadicInfo) >> 4)-1;
207 /// DAGSize - Size of DAG being instruction selected.
211 /// ReplaceUses - replace all uses of the old node F with the use
212 /// of the new node T.
213 void ReplaceUses(SDValue F, SDValue T) {
214 CurDAG->ReplaceAllUsesOfValueWith(F, T);
215 EnforceNodeIdInvariant(T.getNode());
218 /// ReplaceUses - replace all uses of the old nodes F with the use
219 /// of the new nodes T.
220 void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) {
221 CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num);
222 for (unsigned i = 0; i < Num; ++i)
223 EnforceNodeIdInvariant(T[i].getNode());
226 /// ReplaceUses - replace all uses of the old node F with the use
227 /// of the new node T.
228 void ReplaceUses(SDNode *F, SDNode *T) {
229 CurDAG->ReplaceAllUsesWith(F, T);
230 EnforceNodeIdInvariant(T);
233 /// Replace all uses of \c F with \c T, then remove \c F from the DAG.
234 void ReplaceNode(SDNode *F, SDNode *T) {
235 CurDAG->ReplaceAllUsesWith(F, T);
236 EnforceNodeIdInvariant(T);
237 CurDAG->RemoveDeadNode(F);
240 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
241 /// by tblgen. Others should not call it.
242 void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
245 /// getPatternForIndex - Patterns selected by tablegen during ISEL
246 virtual StringRef getPatternForIndex(unsigned index) {
247 llvm_unreachable("Tblgen should generate the implementation of this!");
250 /// getIncludePathForIndex - get the td source location of pattern instantiation
251 virtual StringRef getIncludePathForIndex(unsigned index) {
252 llvm_unreachable("Tblgen should generate the implementation of this!");
255 bool shouldOptForSize(const MachineFunction *MF) const {
256 return CurDAG->shouldOptForSize();
260 // Calls to these predicates are generated by tblgen.
261 bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
262 int64_t DesiredMaskS) const;
263 bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
264 int64_t DesiredMaskS) const;
267 /// CheckPatternPredicate - This function is generated by tblgen in the
268 /// target. It runs the specified pattern predicate and returns true if it
269 /// succeeds or false if it fails. The number is a private implementation
270 /// detail to the code tblgen produces.
271 virtual bool CheckPatternPredicate(unsigned PredNo) const {
272 llvm_unreachable("Tblgen should generate the implementation of this!");
275 /// CheckNodePredicate - This function is generated by tblgen in the target.
276 /// It runs node predicate number PredNo and returns true if it succeeds or
277 /// false if it fails. The number is a private implementation
278 /// detail to the code tblgen produces.
279 virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {
280 llvm_unreachable("Tblgen should generate the implementation of this!");
283 /// CheckNodePredicateWithOperands - This function is generated by tblgen in
285 /// It runs node predicate number PredNo and returns true if it succeeds or
286 /// false if it fails. The number is a private implementation detail to the
287 /// code tblgen produces.
288 virtual bool CheckNodePredicateWithOperands(
289 SDNode *N, unsigned PredNo,
290 const SmallVectorImpl<SDValue> &Operands) const {
291 llvm_unreachable("Tblgen should generate the implementation of this!");
294 virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N,
296 SmallVectorImpl<std::pair<SDValue, SDNode*> > &Result) {
297 llvm_unreachable("Tblgen should generate the implementation of this!");
300 virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {
301 llvm_unreachable("Tblgen should generate this!");
304 void SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
307 /// Return true if complex patterns for this target can mutate the
309 virtual bool ComplexPatternFuncMutatesDAG() const {
313 /// Return whether the node may raise an FP exception.
314 bool mayRaiseFPException(SDNode *Node) const;
316 bool isOrEquivalentToAdd(const SDNode *N) const;
320 // Calls to these functions are generated by tblgen.
321 void Select_INLINEASM(SDNode *N, bool Branch);
322 void Select_READ_REGISTER(SDNode *Op);
323 void Select_WRITE_REGISTER(SDNode *Op);
324 void Select_UNDEF(SDNode *N);
325 void CannotYetSelect(SDNode *N);
328 void DoInstructionSelection();
329 SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
330 ArrayRef<SDValue> Ops, unsigned EmitNodeInfo);
332 SDNode *MutateStrictFPToFP(SDNode *Node, unsigned NewOpc);
334 /// Prepares the landing pad to take incoming values or do other EH
335 /// personality specific tasks. Returns true if the block should be
336 /// instruction selected, false if no code should be emitted for it.
337 bool PrepareEHLandingPad();
339 /// Perform instruction selection on all basic blocks in the function.
340 void SelectAllBasicBlocks(const Function &Fn);
342 /// Perform instruction selection on a single basic block, for
343 /// instructions between \p Begin and \p End. \p HadTailCall will be set
344 /// to true if a call in the block was translated as a tail call.
345 void SelectBasicBlock(BasicBlock::const_iterator Begin,
346 BasicBlock::const_iterator End,
348 void FinishBasicBlock();
350 void CodeGenAndEmitDAG();
352 /// Generate instructions for lowering the incoming arguments of the
354 void LowerArguments(const Function &F);
356 void ComputeLiveOutVRegInfo();
358 /// Create the scheduler. If a specific scheduler was specified
359 /// via the SchedulerRegistry, use it, otherwise select the
360 /// one preferred by the target.
362 ScheduleDAGSDNodes *CreateScheduler();
364 /// OpcodeOffset - This is a cache used to dispatch efficiently into isel
365 /// state machines that start with a OPC_SwitchOpcode node.
366 std::vector<unsigned> OpcodeOffset;
368 void UpdateChains(SDNode *NodeToMatch, SDValue InputChain,
369 SmallVectorImpl<SDNode *> &ChainNodesMatched,
375 #endif /* LLVM_CODEGEN_SELECTIONDAGISEL_H */