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   CodeGenOptLevel 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   /// True if the function currently processing is in the function printing list
65   /// (i.e. `-filter-print-funcs`).
66   /// This is primarily used by ISEL_DUMP, which spans in multiple member
67   /// functions. Storing the filter result here so that we only need to do the
68   /// filtering once.
69   bool MatchFilterFuncName = false;
70 
71   explicit SelectionDAGISel(char &ID, TargetMachine &tm,
72                             CodeGenOptLevel OL = CodeGenOptLevel::Default);
73   ~SelectionDAGISel() override;
74 
75   const TargetLowering *getTargetLowering() const { return TLI; }
76 
77   void getAnalysisUsage(AnalysisUsage &AU) const override;
78 
79   bool runOnMachineFunction(MachineFunction &MF) override;
80 
81   virtual void emitFunctionEntryCode() {}
82 
83   /// PreprocessISelDAG - This hook allows targets to hack on the graph before
84   /// instruction selection starts.
85   virtual void PreprocessISelDAG() {}
86 
87   /// PostprocessISelDAG() - This hook allows the target to hack on the graph
88   /// right after selection.
89   virtual void PostprocessISelDAG() {}
90 
91   /// Main hook for targets to transform nodes into machine nodes.
92   virtual void Select(SDNode *N) = 0;
93 
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
98   /// OutOps vector.
99   virtual bool
100   SelectInlineAsmMemoryOperand(const SDValue &Op,
101                                InlineAsm::ConstraintCode ConstraintID,
102                                std::vector<SDValue> &OutOps) {
103     return true;
104   }
105 
106   /// IsProfitableToFold - Returns true if it's profitable to fold the specific
107   /// operand node N of U during instruction selection that starts at Root.
108   virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const;
109 
110   /// IsLegalToFold - Returns true if the specific operand node N of
111   /// U can be folded during instruction selection that starts at Root.
112   /// FIXME: This is a static member function because the MSP430/X86
113   /// targets, which uses it during isel.  This could become a proper member.
114   static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
115                             CodeGenOptLevel OptLevel,
116                             bool IgnoreChains = false);
117 
118   static void InvalidateNodeId(SDNode *N);
119   static int getUninvalidatedNodeId(SDNode *N);
120 
121   static void EnforceNodeIdInvariant(SDNode *N);
122 
123   // Opcodes used by the DAG state machine:
124   enum BuiltinOpcodes {
125     OPC_Scope,
126     OPC_RecordNode,
127     OPC_RecordChild0,
128     OPC_RecordChild1,
129     OPC_RecordChild2,
130     OPC_RecordChild3,
131     OPC_RecordChild4,
132     OPC_RecordChild5,
133     OPC_RecordChild6,
134     OPC_RecordChild7,
135     OPC_RecordMemRef,
136     OPC_CaptureGlueInput,
137     OPC_MoveChild,
138     OPC_MoveChild0,
139     OPC_MoveChild1,
140     OPC_MoveChild2,
141     OPC_MoveChild3,
142     OPC_MoveChild4,
143     OPC_MoveChild5,
144     OPC_MoveChild6,
145     OPC_MoveChild7,
146     OPC_MoveSibling,
147     OPC_MoveSibling0,
148     OPC_MoveSibling1,
149     OPC_MoveSibling2,
150     OPC_MoveSibling3,
151     OPC_MoveSibling4,
152     OPC_MoveSibling5,
153     OPC_MoveSibling6,
154     OPC_MoveSibling7,
155     OPC_MoveParent,
156     OPC_CheckSame,
157     OPC_CheckChild0Same,
158     OPC_CheckChild1Same,
159     OPC_CheckChild2Same,
160     OPC_CheckChild3Same,
161     OPC_CheckPatternPredicate,
162     OPC_CheckPatternPredicate2,
163     OPC_CheckPredicate,
164     OPC_CheckPredicateWithOperands,
165     OPC_CheckOpcode,
166     OPC_SwitchOpcode,
167     OPC_CheckType,
168     // Space-optimized forms that implicitly encode VT.
169     OPC_CheckTypeI32,
170     OPC_CheckTypeI64,
171     OPC_CheckTypeRes,
172     OPC_SwitchType,
173     OPC_CheckChild0Type,
174     OPC_CheckChild1Type,
175     OPC_CheckChild2Type,
176     OPC_CheckChild3Type,
177     OPC_CheckChild4Type,
178     OPC_CheckChild5Type,
179     OPC_CheckChild6Type,
180     OPC_CheckChild7Type,
181 
182     OPC_CheckChild0TypeI32,
183     OPC_CheckChild1TypeI32,
184     OPC_CheckChild2TypeI32,
185     OPC_CheckChild3TypeI32,
186     OPC_CheckChild4TypeI32,
187     OPC_CheckChild5TypeI32,
188     OPC_CheckChild6TypeI32,
189     OPC_CheckChild7TypeI32,
190 
191     OPC_CheckChild0TypeI64,
192     OPC_CheckChild1TypeI64,
193     OPC_CheckChild2TypeI64,
194     OPC_CheckChild3TypeI64,
195     OPC_CheckChild4TypeI64,
196     OPC_CheckChild5TypeI64,
197     OPC_CheckChild6TypeI64,
198     OPC_CheckChild7TypeI64,
199 
200     OPC_CheckInteger,
201     OPC_CheckChild0Integer,
202     OPC_CheckChild1Integer,
203     OPC_CheckChild2Integer,
204     OPC_CheckChild3Integer,
205     OPC_CheckChild4Integer,
206     OPC_CheckCondCode,
207     OPC_CheckChild2CondCode,
208     OPC_CheckValueType,
209     OPC_CheckComplexPat,
210     OPC_CheckAndImm,
211     OPC_CheckOrImm,
212     OPC_CheckImmAllOnesV,
213     OPC_CheckImmAllZerosV,
214     OPC_CheckFoldableChainNode,
215 
216     OPC_EmitInteger,
217     // Space-optimized forms that implicitly encode integer VT.
218     OPC_EmitInteger8,
219     OPC_EmitInteger16,
220     OPC_EmitInteger32,
221     OPC_EmitInteger64,
222     OPC_EmitStringInteger,
223     // Space-optimized forms that implicitly encode integer VT.
224     OPC_EmitStringInteger32,
225     OPC_EmitRegister,
226     OPC_EmitRegisterI32,
227     OPC_EmitRegisterI64,
228     OPC_EmitRegister2,
229     OPC_EmitConvertToTarget,
230     OPC_EmitConvertToTarget0,
231     OPC_EmitConvertToTarget1,
232     OPC_EmitConvertToTarget2,
233     OPC_EmitConvertToTarget3,
234     OPC_EmitConvertToTarget4,
235     OPC_EmitConvertToTarget5,
236     OPC_EmitConvertToTarget6,
237     OPC_EmitConvertToTarget7,
238     OPC_EmitMergeInputChains,
239     OPC_EmitMergeInputChains1_0,
240     OPC_EmitMergeInputChains1_1,
241     OPC_EmitMergeInputChains1_2,
242     OPC_EmitCopyToReg,
243     OPC_EmitCopyToReg0,
244     OPC_EmitCopyToReg1,
245     OPC_EmitCopyToReg2,
246     OPC_EmitCopyToReg3,
247     OPC_EmitCopyToReg4,
248     OPC_EmitCopyToReg5,
249     OPC_EmitCopyToReg6,
250     OPC_EmitCopyToReg7,
251     OPC_EmitCopyToRegTwoByte,
252     OPC_EmitNodeXForm,
253     OPC_EmitNode,
254     // Space-optimized forms that implicitly encode number of result VTs.
255     OPC_EmitNode0,
256     OPC_EmitNode1,
257     OPC_EmitNode2,
258     // Space-optimized forms that implicitly encode EmitNodeInfo.
259     OPC_EmitNode0None,
260     OPC_EmitNode1None,
261     OPC_EmitNode2None,
262     OPC_EmitNode0Chain,
263     OPC_EmitNode1Chain,
264     OPC_EmitNode2Chain,
265     OPC_MorphNodeTo,
266     // Space-optimized forms that implicitly encode number of result VTs.
267     OPC_MorphNodeTo0,
268     OPC_MorphNodeTo1,
269     OPC_MorphNodeTo2,
270     // Space-optimized forms that implicitly encode EmitNodeInfo.
271     OPC_MorphNodeTo0None,
272     OPC_MorphNodeTo1None,
273     OPC_MorphNodeTo2None,
274     OPC_MorphNodeTo0Chain,
275     OPC_MorphNodeTo1Chain,
276     OPC_MorphNodeTo2Chain,
277     OPC_MorphNodeTo0GlueInput,
278     OPC_MorphNodeTo1GlueInput,
279     OPC_MorphNodeTo2GlueInput,
280     OPC_MorphNodeTo0GlueOutput,
281     OPC_MorphNodeTo1GlueOutput,
282     OPC_MorphNodeTo2GlueOutput,
283     OPC_CompleteMatch,
284     // Contains offset in table for pattern being selected
285     OPC_Coverage
286   };
287 
288   enum {
289     OPFL_None       = 0,  // Node has no chain or glue input and isn't variadic.
290     OPFL_Chain      = 1,     // Node has a chain input.
291     OPFL_GlueInput  = 2,     // Node has a glue input.
292     OPFL_GlueOutput = 4,     // Node has a glue output.
293     OPFL_MemRefs    = 8,     // Node gets accumulated MemRefs.
294     OPFL_Variadic0  = 1<<4,  // Node is variadic, root has 0 fixed inputs.
295     OPFL_Variadic1  = 2<<4,  // Node is variadic, root has 1 fixed inputs.
296     OPFL_Variadic2  = 3<<4,  // Node is variadic, root has 2 fixed inputs.
297     OPFL_Variadic3  = 4<<4,  // Node is variadic, root has 3 fixed inputs.
298     OPFL_Variadic4  = 5<<4,  // Node is variadic, root has 4 fixed inputs.
299     OPFL_Variadic5  = 6<<4,  // Node is variadic, root has 5 fixed inputs.
300     OPFL_Variadic6  = 7<<4,  // Node is variadic, root has 6 fixed inputs.
301 
302     OPFL_VariadicInfo = OPFL_Variadic6
303   };
304 
305   /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
306   /// number of fixed arity values that should be skipped when copying from the
307   /// root.
308   static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
309     return ((Flags&OPFL_VariadicInfo) >> 4)-1;
310   }
311 
312 
313 protected:
314   /// DAGSize - Size of DAG being instruction selected.
315   ///
316   unsigned DAGSize = 0;
317 
318   /// ReplaceUses - replace all uses of the old node F with the use
319   /// of the new node T.
320   void ReplaceUses(SDValue F, SDValue T) {
321     CurDAG->ReplaceAllUsesOfValueWith(F, T);
322     EnforceNodeIdInvariant(T.getNode());
323   }
324 
325   /// ReplaceUses - replace all uses of the old nodes F with the use
326   /// of the new nodes T.
327   void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) {
328     CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num);
329     for (unsigned i = 0; i < Num; ++i)
330       EnforceNodeIdInvariant(T[i].getNode());
331   }
332 
333   /// ReplaceUses - replace all uses of the old node F with the use
334   /// of the new node T.
335   void ReplaceUses(SDNode *F, SDNode *T) {
336     CurDAG->ReplaceAllUsesWith(F, T);
337     EnforceNodeIdInvariant(T);
338   }
339 
340   /// Replace all uses of \c F with \c T, then remove \c F from the DAG.
341   void ReplaceNode(SDNode *F, SDNode *T) {
342     CurDAG->ReplaceAllUsesWith(F, T);
343     EnforceNodeIdInvariant(T);
344     CurDAG->RemoveDeadNode(F);
345   }
346 
347   /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
348   /// by tblgen.  Others should not call it.
349   void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
350                                      const SDLoc &DL);
351 
352   /// getPatternForIndex - Patterns selected by tablegen during ISEL
353   virtual StringRef getPatternForIndex(unsigned index) {
354     llvm_unreachable("Tblgen should generate the implementation of this!");
355   }
356 
357   /// getIncludePathForIndex - get the td source location of pattern instantiation
358   virtual StringRef getIncludePathForIndex(unsigned index) {
359     llvm_unreachable("Tblgen should generate the implementation of this!");
360   }
361 
362   bool shouldOptForSize(const MachineFunction *MF) const {
363     return CurDAG->shouldOptForSize();
364   }
365 
366 public:
367   // Calls to these predicates are generated by tblgen.
368   bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
369                     int64_t DesiredMaskS) const;
370   bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
371                     int64_t DesiredMaskS) const;
372 
373 
374   /// CheckPatternPredicate - This function is generated by tblgen in the
375   /// target.  It runs the specified pattern predicate and returns true if it
376   /// succeeds or false if it fails.  The number is a private implementation
377   /// detail to the code tblgen produces.
378   virtual bool CheckPatternPredicate(unsigned PredNo) const {
379     llvm_unreachable("Tblgen should generate the implementation of this!");
380   }
381 
382   /// CheckNodePredicate - This function is generated by tblgen in the target.
383   /// It runs node predicate number PredNo and returns true if it succeeds or
384   /// false if it fails.  The number is a private implementation
385   /// detail to the code tblgen produces.
386   virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {
387     llvm_unreachable("Tblgen should generate the implementation of this!");
388   }
389 
390   /// CheckNodePredicateWithOperands - This function is generated by tblgen in
391   /// the target.
392   /// It runs node predicate number PredNo and returns true if it succeeds or
393   /// false if it fails.  The number is a private implementation detail to the
394   /// code tblgen produces.
395   virtual bool CheckNodePredicateWithOperands(
396       SDNode *N, unsigned PredNo,
397       const SmallVectorImpl<SDValue> &Operands) const {
398     llvm_unreachable("Tblgen should generate the implementation of this!");
399   }
400 
401   virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N,
402                                    unsigned PatternNo,
403                         SmallVectorImpl<std::pair<SDValue, SDNode*> > &Result) {
404     llvm_unreachable("Tblgen should generate the implementation of this!");
405   }
406 
407   virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {
408     llvm_unreachable("Tblgen should generate this!");
409   }
410 
411   void SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
412                         unsigned TableSize);
413 
414   /// Return true if complex patterns for this target can mutate the
415   /// DAG.
416   virtual bool ComplexPatternFuncMutatesDAG() const {
417     return false;
418   }
419 
420   /// Return whether the node may raise an FP exception.
421   bool mayRaiseFPException(SDNode *Node) const;
422 
423   bool isOrEquivalentToAdd(const SDNode *N) const;
424 
425 private:
426 
427   // Calls to these functions are generated by tblgen.
428   void Select_INLINEASM(SDNode *N);
429   void Select_READ_REGISTER(SDNode *Op);
430   void Select_WRITE_REGISTER(SDNode *Op);
431   void Select_UNDEF(SDNode *N);
432   void CannotYetSelect(SDNode *N);
433 
434   void Select_FREEZE(SDNode *N);
435   void Select_ARITH_FENCE(SDNode *N);
436   void Select_MEMBARRIER(SDNode *N);
437 
438   void pushStackMapLiveVariable(SmallVectorImpl<SDValue> &Ops, SDValue Operand,
439                                 SDLoc DL);
440   void Select_STACKMAP(SDNode *N);
441   void Select_PATCHPOINT(SDNode *N);
442 
443   void Select_JUMP_TABLE_DEBUG_INFO(SDNode *N);
444 
445 private:
446   void DoInstructionSelection();
447   SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
448                     ArrayRef<SDValue> Ops, unsigned EmitNodeInfo);
449 
450   /// Prepares the landing pad to take incoming values or do other EH
451   /// personality specific tasks. Returns true if the block should be
452   /// instruction selected, false if no code should be emitted for it.
453   bool PrepareEHLandingPad();
454 
455   // Mark and Report IPToState for each Block under AsynchEH
456   void reportIPToStateForBlocks(MachineFunction *Fn);
457 
458   /// Perform instruction selection on all basic blocks in the function.
459   void SelectAllBasicBlocks(const Function &Fn);
460 
461   /// Perform instruction selection on a single basic block, for
462   /// instructions between \p Begin and \p End.  \p HadTailCall will be set
463   /// to true if a call in the block was translated as a tail call.
464   void SelectBasicBlock(BasicBlock::const_iterator Begin,
465                         BasicBlock::const_iterator End,
466                         bool &HadTailCall);
467   void FinishBasicBlock();
468 
469   void CodeGenAndEmitDAG();
470 
471   /// Generate instructions for lowering the incoming arguments of the
472   /// given function.
473   void LowerArguments(const Function &F);
474 
475   void ComputeLiveOutVRegInfo();
476 
477   /// Create the scheduler. If a specific scheduler was specified
478   /// via the SchedulerRegistry, use it, otherwise select the
479   /// one preferred by the target.
480   ///
481   ScheduleDAGSDNodes *CreateScheduler();
482 
483   /// OpcodeOffset - This is a cache used to dispatch efficiently into isel
484   /// state machines that start with a OPC_SwitchOpcode node.
485   std::vector<unsigned> OpcodeOffset;
486 
487   void UpdateChains(SDNode *NodeToMatch, SDValue InputChain,
488                     SmallVectorImpl<SDNode *> &ChainNodesMatched,
489                     bool isMorphNodeTo);
490 };
491 
492 }
493 
494 #endif /* LLVM_CODEGEN_SELECTIONDAGISEL_H */
495