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 
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 <memory>
22 
23 namespace llvm {
24 class AAResults;
25 class SelectionDAGBuilder;
26 class SDValue;
27 class MachineRegisterInfo;
28 class MachineFunction;
29 class OptimizationRemarkEmitter;
30 class TargetLowering;
31 class TargetLibraryInfo;
32 class FunctionLoweringInfo;
33 class SwiftErrorValueTracking;
34 class GCFunctionInfo;
35 class ScheduleDAGSDNodes;
36 
37 /// SelectionDAGISel - This is the common base class used for SelectionDAG-based
38 /// pattern-matching instruction selectors.
39 class SelectionDAGISel : public MachineFunctionPass {
40 public:
41   TargetMachine &TM;
42   const TargetLibraryInfo *LibInfo;
43   std::unique_ptr<FunctionLoweringInfo> FuncInfo;
44   SwiftErrorValueTracking *SwiftError;
45   MachineFunction *MF;
46   MachineRegisterInfo *RegInfo;
47   SelectionDAG *CurDAG;
48   std::unique_ptr<SelectionDAGBuilder> SDB;
49   AAResults *AA;
50   GCFunctionInfo *GFI;
51   CodeGenOpt::Level OptLevel;
52   const TargetInstrInfo *TII;
53   const TargetLowering *TLI;
54   bool FastISelFailed;
55   SmallPtrSet<const Instruction *, 4> ElidedArgCopyInstrs;
56 
57   /// Current optimization remark emitter.
58   /// Used to report things like combines and FastISel failures.
59   std::unique_ptr<OptimizationRemarkEmitter> ORE;
60 
61   static char ID;
62 
63   explicit SelectionDAGISel(TargetMachine &tm,
64                             CodeGenOpt::Level OL = CodeGenOpt::Default);
65   ~SelectionDAGISel() override;
66 
67   const TargetLowering *getTargetLowering() const { return TLI; }
68 
69   void getAnalysisUsage(AnalysisUsage &AU) const override;
70 
71   bool runOnMachineFunction(MachineFunction &MF) override;
72 
73   virtual void emitFunctionEntryCode() {}
74 
75   /// PreprocessISelDAG - This hook allows targets to hack on the graph before
76   /// instruction selection starts.
77   virtual void PreprocessISelDAG() {}
78 
79   /// PostprocessISelDAG() - This hook allows the target to hack on the graph
80   /// right after selection.
81   virtual void PostprocessISelDAG() {}
82 
83   /// Main hook for targets to transform nodes into machine nodes.
84   virtual void Select(SDNode *N) = 0;
85 
86   /// SelectInlineAsmMemoryOperand - Select the specified address as a target
87   /// addressing mode, according to the specified constraint.  If this does
88   /// not match or is not implemented, return true.  The resultant operands
89   /// (which will appear in the machine instruction) should be added to the
90   /// OutOps vector.
91   virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op,
92                                             unsigned ConstraintID,
93                                             std::vector<SDValue> &OutOps) {
94     return true;
95   }
96 
97   /// IsProfitableToFold - Returns true if it's profitable to fold the specific
98   /// operand node N of U during instruction selection that starts at Root.
99   virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const;
100 
101   /// IsLegalToFold - Returns true if the specific operand node N of
102   /// U can be folded during instruction selection that starts at Root.
103   /// FIXME: This is a static member function because the MSP430/X86
104   /// targets, which uses it during isel.  This could become a proper member.
105   static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
106                             CodeGenOpt::Level OptLevel,
107                             bool IgnoreChains = false);
108 
109   static void InvalidateNodeId(SDNode *N);
110   static int getUninvalidatedNodeId(SDNode *N);
111 
112   static void EnforceNodeIdInvariant(SDNode *N);
113 
114   // Opcodes used by the DAG state machine:
115   enum BuiltinOpcodes {
116     OPC_Scope,
117     OPC_RecordNode,
118     OPC_RecordChild0, OPC_RecordChild1, OPC_RecordChild2, OPC_RecordChild3,
119     OPC_RecordChild4, OPC_RecordChild5, OPC_RecordChild6, OPC_RecordChild7,
120     OPC_RecordMemRef,
121     OPC_CaptureGlueInput,
122     OPC_MoveChild,
123     OPC_MoveChild0, OPC_MoveChild1, OPC_MoveChild2, OPC_MoveChild3,
124     OPC_MoveChild4, OPC_MoveChild5, OPC_MoveChild6, OPC_MoveChild7,
125     OPC_MoveParent,
126     OPC_CheckSame,
127     OPC_CheckChild0Same, OPC_CheckChild1Same,
128     OPC_CheckChild2Same, OPC_CheckChild3Same,
129     OPC_CheckPatternPredicate,
130     OPC_CheckPredicate,
131     OPC_CheckPredicateWithOperands,
132     OPC_CheckOpcode,
133     OPC_SwitchOpcode,
134     OPC_CheckType,
135     OPC_CheckTypeRes,
136     OPC_SwitchType,
137     OPC_CheckChild0Type, OPC_CheckChild1Type, OPC_CheckChild2Type,
138     OPC_CheckChild3Type, OPC_CheckChild4Type, OPC_CheckChild5Type,
139     OPC_CheckChild6Type, OPC_CheckChild7Type,
140     OPC_CheckInteger,
141     OPC_CheckChild0Integer, OPC_CheckChild1Integer, OPC_CheckChild2Integer,
142     OPC_CheckChild3Integer, OPC_CheckChild4Integer,
143     OPC_CheckCondCode, OPC_CheckChild2CondCode,
144     OPC_CheckValueType,
145     OPC_CheckComplexPat,
146     OPC_CheckAndImm, OPC_CheckOrImm,
147     OPC_CheckImmAllOnesV,
148     OPC_CheckImmAllZerosV,
149     OPC_CheckFoldableChainNode,
150 
151     OPC_EmitInteger,
152     OPC_EmitRegister,
153     OPC_EmitRegister2,
154     OPC_EmitConvertToTarget,
155     OPC_EmitMergeInputChains,
156     OPC_EmitMergeInputChains1_0,
157     OPC_EmitMergeInputChains1_1,
158     OPC_EmitMergeInputChains1_2,
159     OPC_EmitCopyToReg,
160     OPC_EmitCopyToReg2,
161     OPC_EmitNodeXForm,
162     OPC_EmitNode,
163     // Space-optimized forms that implicitly encode number of result VTs.
164     OPC_EmitNode0, OPC_EmitNode1, OPC_EmitNode2,
165     OPC_MorphNodeTo,
166     // Space-optimized forms that implicitly encode number of result VTs.
167     OPC_MorphNodeTo0, OPC_MorphNodeTo1, OPC_MorphNodeTo2,
168     OPC_CompleteMatch,
169     // Contains offset in table for pattern being selected
170     OPC_Coverage
171   };
172 
173   enum {
174     OPFL_None       = 0,  // Node has no chain or glue input and isn't variadic.
175     OPFL_Chain      = 1,     // Node has a chain input.
176     OPFL_GlueInput  = 2,     // Node has a glue input.
177     OPFL_GlueOutput = 4,     // Node has a glue output.
178     OPFL_MemRefs    = 8,     // Node gets accumulated MemRefs.
179     OPFL_Variadic0  = 1<<4,  // Node is variadic, root has 0 fixed inputs.
180     OPFL_Variadic1  = 2<<4,  // Node is variadic, root has 1 fixed inputs.
181     OPFL_Variadic2  = 3<<4,  // Node is variadic, root has 2 fixed inputs.
182     OPFL_Variadic3  = 4<<4,  // Node is variadic, root has 3 fixed inputs.
183     OPFL_Variadic4  = 5<<4,  // Node is variadic, root has 4 fixed inputs.
184     OPFL_Variadic5  = 6<<4,  // Node is variadic, root has 5 fixed inputs.
185     OPFL_Variadic6  = 7<<4,  // Node is variadic, root has 6 fixed inputs.
186 
187     OPFL_VariadicInfo = OPFL_Variadic6
188   };
189 
190   /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
191   /// number of fixed arity values that should be skipped when copying from the
192   /// root.
193   static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
194     return ((Flags&OPFL_VariadicInfo) >> 4)-1;
195   }
196 
197 
198 protected:
199   /// DAGSize - Size of DAG being instruction selected.
200   ///
201   unsigned DAGSize;
202 
203   /// ReplaceUses - replace all uses of the old node F with the use
204   /// of the new node T.
205   void ReplaceUses(SDValue F, SDValue T) {
206     CurDAG->ReplaceAllUsesOfValueWith(F, T);
207     EnforceNodeIdInvariant(T.getNode());
208   }
209 
210   /// ReplaceUses - replace all uses of the old nodes F with the use
211   /// of the new nodes T.
212   void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) {
213     CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num);
214     for (unsigned i = 0; i < Num; ++i)
215       EnforceNodeIdInvariant(T[i].getNode());
216   }
217 
218   /// ReplaceUses - replace all uses of the old node F with the use
219   /// of the new node T.
220   void ReplaceUses(SDNode *F, SDNode *T) {
221     CurDAG->ReplaceAllUsesWith(F, T);
222     EnforceNodeIdInvariant(T);
223   }
224 
225   /// Replace all uses of \c F with \c T, then remove \c F from the DAG.
226   void ReplaceNode(SDNode *F, SDNode *T) {
227     CurDAG->ReplaceAllUsesWith(F, T);
228     EnforceNodeIdInvariant(T);
229     CurDAG->RemoveDeadNode(F);
230   }
231 
232   /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
233   /// by tblgen.  Others should not call it.
234   void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
235                                      const SDLoc &DL);
236 
237   /// getPatternForIndex - Patterns selected by tablegen during ISEL
238   virtual StringRef getPatternForIndex(unsigned index) {
239     llvm_unreachable("Tblgen should generate the implementation of this!");
240   }
241 
242   /// getIncludePathForIndex - get the td source location of pattern instantiation
243   virtual StringRef getIncludePathForIndex(unsigned index) {
244     llvm_unreachable("Tblgen should generate the implementation of this!");
245   }
246 
247   bool shouldOptForSize(const MachineFunction *MF) const {
248     return CurDAG->shouldOptForSize();
249   }
250 
251 public:
252   // Calls to these predicates are generated by tblgen.
253   bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
254                     int64_t DesiredMaskS) const;
255   bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
256                     int64_t DesiredMaskS) const;
257 
258 
259   /// CheckPatternPredicate - This function is generated by tblgen in the
260   /// target.  It runs the specified pattern predicate and returns true if it
261   /// succeeds or false if it fails.  The number is a private implementation
262   /// detail to the code tblgen produces.
263   virtual bool CheckPatternPredicate(unsigned PredNo) const {
264     llvm_unreachable("Tblgen should generate the implementation of this!");
265   }
266 
267   /// CheckNodePredicate - This function is generated by tblgen in the target.
268   /// It runs node predicate number PredNo and returns true if it succeeds or
269   /// false if it fails.  The number is a private implementation
270   /// detail to the code tblgen produces.
271   virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {
272     llvm_unreachable("Tblgen should generate the implementation of this!");
273   }
274 
275   /// CheckNodePredicateWithOperands - This function is generated by tblgen in
276   /// the target.
277   /// It runs node predicate number PredNo and returns true if it succeeds or
278   /// false if it fails.  The number is a private implementation detail to the
279   /// code tblgen produces.
280   virtual bool CheckNodePredicateWithOperands(
281       SDNode *N, unsigned PredNo,
282       const SmallVectorImpl<SDValue> &Operands) const {
283     llvm_unreachable("Tblgen should generate the implementation of this!");
284   }
285 
286   virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N,
287                                    unsigned PatternNo,
288                         SmallVectorImpl<std::pair<SDValue, SDNode*> > &Result) {
289     llvm_unreachable("Tblgen should generate the implementation of this!");
290   }
291 
292   virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {
293     llvm_unreachable("Tblgen should generate this!");
294   }
295 
296   void SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
297                         unsigned TableSize);
298 
299   /// Return true if complex patterns for this target can mutate the
300   /// DAG.
301   virtual bool ComplexPatternFuncMutatesDAG() const {
302     return false;
303   }
304 
305   /// Return whether the node may raise an FP exception.
306   bool mayRaiseFPException(SDNode *Node) const;
307 
308   bool isOrEquivalentToAdd(const SDNode *N) const;
309 
310 private:
311 
312   // Calls to these functions are generated by tblgen.
313   void Select_INLINEASM(SDNode *N);
314   void Select_READ_REGISTER(SDNode *Op);
315   void Select_WRITE_REGISTER(SDNode *Op);
316   void Select_UNDEF(SDNode *N);
317   void CannotYetSelect(SDNode *N);
318 
319   void Select_FREEZE(SDNode *N);
320 
321 private:
322   void DoInstructionSelection();
323   SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
324                     ArrayRef<SDValue> Ops, unsigned EmitNodeInfo);
325 
326   SDNode *MutateStrictFPToFP(SDNode *Node, unsigned NewOpc);
327 
328   /// Prepares the landing pad to take incoming values or do other EH
329   /// personality specific tasks. Returns true if the block should be
330   /// instruction selected, false if no code should be emitted for it.
331   bool PrepareEHLandingPad();
332 
333   /// Perform instruction selection on all basic blocks in the function.
334   void SelectAllBasicBlocks(const Function &Fn);
335 
336   /// Perform instruction selection on a single basic block, for
337   /// instructions between \p Begin and \p End.  \p HadTailCall will be set
338   /// to true if a call in the block was translated as a tail call.
339   void SelectBasicBlock(BasicBlock::const_iterator Begin,
340                         BasicBlock::const_iterator End,
341                         bool &HadTailCall);
342   void FinishBasicBlock();
343 
344   void CodeGenAndEmitDAG();
345 
346   /// Generate instructions for lowering the incoming arguments of the
347   /// given function.
348   void LowerArguments(const Function &F);
349 
350   void ComputeLiveOutVRegInfo();
351 
352   /// Create the scheduler. If a specific scheduler was specified
353   /// via the SchedulerRegistry, use it, otherwise select the
354   /// one preferred by the target.
355   ///
356   ScheduleDAGSDNodes *CreateScheduler();
357 
358   /// OpcodeOffset - This is a cache used to dispatch efficiently into isel
359   /// state machines that start with a OPC_SwitchOpcode node.
360   std::vector<unsigned> OpcodeOffset;
361 
362   void UpdateChains(SDNode *NodeToMatch, SDValue InputChain,
363                     SmallVectorImpl<SDNode *> &ChainNodesMatched,
364                     bool isMorphNodeTo);
365 };
366 
367 }
368 
369 #endif /* LLVM_CODEGEN_SELECTIONDAGISEL_H */
370