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