LLVM  10.0.0svn
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 "llvm/Pass.h"
22 #include <memory>
23 
24 namespace llvm {
25 class AAResults;
26 class FastISel;
27 class SelectionDAGBuilder;
28 class SDValue;
29 class MachineRegisterInfo;
30 class MachineBasicBlock;
31 class MachineFunction;
32 class MachineInstr;
33 class OptimizationRemarkEmitter;
34 class TargetLowering;
35 class TargetLibraryInfo;
36 class FunctionLoweringInfo;
37 class ScheduleHazardRecognizer;
38 class SwiftErrorValueTracking;
39 class GCFunctionInfo;
40 class ScheduleDAGSDNodes;
41 class LoadInst;
42 
43 /// SelectionDAGISel - This is the common base class used for SelectionDAG-based
44 /// pattern-matching instruction selectors.
46 public:
62 
63  /// Current optimization remark emitter.
64  /// Used to report things like combines and FastISel failures.
65  std::unique_ptr<OptimizationRemarkEmitter> ORE;
66 
67  static char ID;
68 
69  explicit SelectionDAGISel(TargetMachine &tm,
71  ~SelectionDAGISel() override;
72 
73  const TargetLowering *getTargetLowering() const { return TLI; }
74 
75  void getAnalysisUsage(AnalysisUsage &AU) const override;
76 
77  bool runOnMachineFunction(MachineFunction &MF) override;
78 
79  virtual void EmitFunctionEntryCode() {}
80 
81  /// PreprocessISelDAG - This hook allows targets to hack on the graph before
82  /// instruction selection starts.
83  virtual void PreprocessISelDAG() {}
84 
85  /// PostprocessISelDAG() - This hook allows the target to hack on the graph
86  /// right after selection.
87  virtual void PostprocessISelDAG() {}
88 
89  /// Main hook for targets to transform nodes into machine nodes.
90  virtual void Select(SDNode *N) = 0;
91 
92  /// SelectInlineAsmMemoryOperand - Select the specified address as a target
93  /// addressing mode, according to the specified constraint. If this does
94  /// not match or is not implemented, return true. The resultant operands
95  /// (which will appear in the machine instruction) should be added to the
96  /// OutOps vector.
98  unsigned ConstraintID,
99  std::vector<SDValue> &OutOps) {
100  return true;
101  }
102 
103  /// IsProfitableToFold - Returns true if it's profitable to fold the specific
104  /// operand node N of U during instruction selection that starts at Root.
105  virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const;
106 
107  /// IsLegalToFold - Returns true if the specific operand node N of
108  /// U can be folded during instruction selection that starts at Root.
109  /// FIXME: This is a static member function because the MSP430/X86
110  /// targets, which uses it during isel. This could become a proper member.
111  static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
112  CodeGenOpt::Level OptLevel,
113  bool IgnoreChains = false);
114 
115  static void InvalidateNodeId(SDNode *N);
116  static int getUninvalidatedNodeId(SDNode *N);
117 
118  static void EnforceNodeIdInvariant(SDNode *N);
119 
120  // Opcodes used by the DAG state machine:
156 
169  // Space-optimized forms that implicitly encode number of result VTs.
172  // Space-optimized forms that implicitly encode number of result VTs.
175  // Contains offset in table for pattern being selected
177  };
178 
179  enum {
180  OPFL_None = 0, // Node has no chain or glue input and isn't variadic.
181  OPFL_Chain = 1, // Node has a chain input.
182  OPFL_GlueInput = 2, // Node has a glue input.
183  OPFL_GlueOutput = 4, // Node has a glue output.
184  OPFL_MemRefs = 8, // Node gets accumulated MemRefs.
185  OPFL_Variadic0 = 1<<4, // Node is variadic, root has 0 fixed inputs.
186  OPFL_Variadic1 = 2<<4, // Node is variadic, root has 1 fixed inputs.
187  OPFL_Variadic2 = 3<<4, // Node is variadic, root has 2 fixed inputs.
188  OPFL_Variadic3 = 4<<4, // Node is variadic, root has 3 fixed inputs.
189  OPFL_Variadic4 = 5<<4, // Node is variadic, root has 4 fixed inputs.
190  OPFL_Variadic5 = 6<<4, // Node is variadic, root has 5 fixed inputs.
191  OPFL_Variadic6 = 7<<4, // Node is variadic, root has 6 fixed inputs.
192 
194  };
195 
196  /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
197  /// number of fixed arity values that should be skipped when copying from the
198  /// root.
199  static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
200  return ((Flags&OPFL_VariadicInfo) >> 4)-1;
201  }
202 
203 
204 protected:
205  /// DAGSize - Size of DAG being instruction selected.
206  ///
207  unsigned DAGSize;
208 
209  /// ReplaceUses - replace all uses of the old node F with the use
210  /// of the new node T.
212  CurDAG->ReplaceAllUsesOfValueWith(F, T);
214  }
215 
216  /// ReplaceUses - replace all uses of the old nodes F with the use
217  /// of the new nodes T.
218  void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) {
219  CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num);
220  for (unsigned i = 0; i < Num; ++i)
221  EnforceNodeIdInvariant(T[i].getNode());
222  }
223 
224  /// ReplaceUses - replace all uses of the old node F with the use
225  /// of the new node T.
227  CurDAG->ReplaceAllUsesWith(F, T);
229  }
230 
231  /// Replace all uses of \c F with \c T, then remove \c F from the DAG.
233  CurDAG->ReplaceAllUsesWith(F, T);
235  CurDAG->RemoveDeadNode(F);
236  }
237 
238  /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
239  /// by tblgen. Others should not call it.
240  void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
241  const SDLoc &DL);
242 
243  /// getPatternForIndex - Patterns selected by tablegen during ISEL
244  virtual StringRef getPatternForIndex(unsigned index) {
245  llvm_unreachable("Tblgen should generate the implementation of this!");
246  }
247 
248  /// getIncludePathForIndex - get the td source location of pattern instantiation
249  virtual StringRef getIncludePathForIndex(unsigned index) {
250  llvm_unreachable("Tblgen should generate the implementation of this!");
251  }
252 public:
253  // Calls to these predicates are generated by tblgen.
254  bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
255  int64_t DesiredMaskS) const;
256  bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
257  int64_t DesiredMaskS) const;
258 
259 
260  /// CheckPatternPredicate - This function is generated by tblgen in the
261  /// target. It runs the specified pattern predicate and returns true if it
262  /// succeeds or false if it fails. The number is a private implementation
263  /// detail to the code tblgen produces.
264  virtual bool CheckPatternPredicate(unsigned PredNo) const {
265  llvm_unreachable("Tblgen should generate the implementation of this!");
266  }
267 
268  /// CheckNodePredicate - This function is generated by tblgen in the target.
269  /// It runs node predicate number PredNo and returns true if it succeeds or
270  /// false if it fails. The number is a private implementation
271  /// detail to the code tblgen produces.
272  virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {
273  llvm_unreachable("Tblgen should generate the implementation of this!");
274  }
275 
276  /// CheckNodePredicateWithOperands - This function is generated by tblgen in
277  /// the target.
278  /// It runs node predicate number PredNo and returns true if it succeeds or
279  /// false if it fails. The number is a private implementation detail to the
280  /// code tblgen produces.
282  SDNode *N, unsigned PredNo,
283  const SmallVectorImpl<SDValue> &Operands) const {
284  llvm_unreachable("Tblgen should generate the implementation of this!");
285  }
286 
287  virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N,
288  unsigned PatternNo,
289  SmallVectorImpl<std::pair<SDValue, SDNode*> > &Result) {
290  llvm_unreachable("Tblgen should generate the implementation of this!");
291  }
292 
293  virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {
294  llvm_unreachable("Tblgen should generate this!");
295  }
296 
297  void SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
298  unsigned TableSize);
299 
300  /// Return true if complex patterns for this target can mutate the
301  /// DAG.
302  virtual bool ComplexPatternFuncMutatesDAG() const {
303  return false;
304  }
305 
306  bool isOrEquivalentToAdd(const SDNode *N) const;
307 
308 private:
309 
310  // Calls to these functions are generated by tblgen.
311  void Select_INLINEASM(SDNode *N, bool Branch);
312  void Select_READ_REGISTER(SDNode *Op);
313  void Select_WRITE_REGISTER(SDNode *Op);
314  void Select_UNDEF(SDNode *N);
315  void CannotYetSelect(SDNode *N);
316 
317 private:
318  void DoInstructionSelection();
319  SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
320  ArrayRef<SDValue> Ops, unsigned EmitNodeInfo);
321 
322  SDNode *MutateStrictFPToFP(SDNode *Node, unsigned NewOpc);
323 
324  /// Prepares the landing pad to take incoming values or do other EH
325  /// personality specific tasks. Returns true if the block should be
326  /// instruction selected, false if no code should be emitted for it.
327  bool PrepareEHLandingPad();
328 
329  /// Perform instruction selection on all basic blocks in the function.
330  void SelectAllBasicBlocks(const Function &Fn);
331 
332  /// Perform instruction selection on a single basic block, for
333  /// instructions between \p Begin and \p End. \p HadTailCall will be set
334  /// to true if a call in the block was translated as a tail call.
335  void SelectBasicBlock(BasicBlock::const_iterator Begin,
337  bool &HadTailCall);
338  void FinishBasicBlock();
339 
340  void CodeGenAndEmitDAG();
341 
342  /// Generate instructions for lowering the incoming arguments of the
343  /// given function.
344  void LowerArguments(const Function &F);
345 
346  void ComputeLiveOutVRegInfo();
347 
348  /// Create the scheduler. If a specific scheduler was specified
349  /// via the SchedulerRegistry, use it, otherwise select the
350  /// one preferred by the target.
351  ///
352  ScheduleDAGSDNodes *CreateScheduler();
353 
354  /// OpcodeOffset - This is a cache used to dispatch efficiently into isel
355  /// state machines that start with a OPC_SwitchOpcode node.
356  std::vector<unsigned> OpcodeOffset;
357 
358  void UpdateChains(SDNode *NodeToMatch, SDValue InputChain,
359  SmallVectorImpl<SDNode *> &ChainNodesMatched,
360  bool isMorphNodeTo);
361 };
362 
363 }
364 
365 #endif /* LLVM_CODEGEN_SELECTIONDAGISEL_H */
void ReplaceUses(SDNode *F, SDNode *T)
ReplaceUses - replace all uses of the old node F with the use of the new node T.
SelectionDAGBuilder * SDB
static int getNumFixedFromVariadicInfo(unsigned Flags)
getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the number of fixed arity values ...
GCFunctionInfo * GFI
virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const
IsProfitableToFold - Returns true if it&#39;s profitable to fold the specific operand node N of U during ...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void ReplaceUses(SDValue F, SDValue T)
ReplaceUses - replace all uses of the old node F with the use of the new node T.
bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS, int64_t DesiredMaskS) const
CheckAndMask - The isel is trying to match something like (and X, 255).
SelectionDAGBuilder - This is the common target-independent lowering implementation that is parameter...
virtual bool CheckNodePredicateWithOperands(SDNode *N, unsigned PredNo, const SmallVectorImpl< SDValue > &Operands) const
CheckNodePredicateWithOperands - This function is generated by tblgen in the target.
F(f)
SDNode * getNode() const
get the SDNode which holds the desired result
MachineFunction * MF
void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To, unsigned Num)
Like ReplaceAllUsesOfValueWith, but for multiple values at once.
const TargetLibraryInfo * LibInfo
InstListType::const_iterator const_iterator
Definition: BasicBlock.h:90
SwiftErrorValueTracking * SwiftError
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
virtual bool ComplexPatternFuncMutatesDAG() const
Return true if complex patterns for this target can mutate the DAG.
static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root, CodeGenOpt::Level OptLevel, bool IgnoreChains=false)
IsLegalToFold - Returns true if the specific operand node N of U can be folded during instruction sel...
const TargetLowering * TLI
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
virtual void Select(SDNode *N)=0
Main hook for targets to transform nodes into machine nodes.
static void EnforceNodeIdInvariant(SDNode *N)
mir Rename Register Operands
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
This represents a list of ValueType&#39;s that has been intern&#39;d by a SelectionDAG.
unsigned DAGSize
DAGSize - Size of DAG being instruction selected.
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.
virtual StringRef getPatternForIndex(unsigned index)
getPatternForIndex - Patterns selected by tablegen during ISEL
static void InvalidateNodeId(SDNode *N)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
TargetInstrInfo - Interface to description of machine instruction set.
MachineRegisterInfo * RegInfo
virtual bool CheckPatternPredicate(unsigned PredNo) const
CheckPatternPredicate - This function is generated by tblgen in the target.
SmallPtrSet< const Instruction *, 4 > ElidedArgCopyInstrs
CodeGenOpt::Level OptLevel
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
Represent the analysis usage information of a pass.
virtual void EmitFunctionEntryCode()
void ReplaceAllUsesWith(SDValue From, SDValue To)
Modify anything using &#39;From&#39; to use &#39;To&#39; instead.
virtual void PostprocessISelDAG()
PostprocessISelDAG() - This hook allows the target to hack on the graph right after selection...
void RemoveDeadNode(SDNode *N)
Remove the specified node from the system.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool isOrEquivalentToAdd(const SDNode *N) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N, unsigned PatternNo, SmallVectorImpl< std::pair< SDValue, SDNode *> > &Result)
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Definition: SelectionDAG.h:221
Provides information about what library functions are available for the current target.
SelectionDAGISel(TargetMachine &tm, CodeGenOpt::Level OL=CodeGenOpt::Default)
Wrapper class for IR location info (IR ordering and DebugLoc) to be passed into SDNode creation funct...
Represents one node in the SelectionDAG.
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
#define N
FunctionLoweringInfo - This contains information that is global to a function that is used when lower...
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.
const TargetLowering * getTargetLowering() const
virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned 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).
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.
void SelectInlineAsmMemoryOperands(std::vector< SDValue > &Ops, const SDLoc &DL)
SelectInlineAsmMemoryOperands - Calls to this are automatically generated by tblgen.
void ReplaceAllUsesOfValueWith(SDValue From, SDValue To)
Replace any uses of From with To, leaving uses of other values produced by From.getNode() alone...
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:65
void ReplaceNode(SDNode *F, SDNode *T)
Replace all uses of F with T, then remove F from the DAG.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
Garbage collection metadata for a single function.
Definition: GCMetadata.h:77
virtual void PreprocessISelDAG()
PreprocessISelDAG - This hook allows targets to hack on the graph before instruction selection starts...
virtual StringRef getIncludePathForIndex(unsigned index)
getIncludePathForIndex - get the td source location of pattern instantiation
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation...
const TargetInstrInfo * TII
FunctionLoweringInfo * FuncInfo
virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo)
void SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable, unsigned TableSize)
static int getUninvalidatedNodeId(SDNode *N)