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