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_CheckPatternPredicate0,
163     OPC_CheckPatternPredicate1,
164     OPC_CheckPatternPredicate2,
165     OPC_CheckPatternPredicate3,
166     OPC_CheckPatternPredicate4,
167     OPC_CheckPatternPredicate5,
168     OPC_CheckPatternPredicate6,
169     OPC_CheckPatternPredicate7,
170     OPC_CheckPatternPredicateTwoByte,
171     OPC_CheckPredicate,
172     OPC_CheckPredicate0,
173     OPC_CheckPredicate1,
174     OPC_CheckPredicate2,
175     OPC_CheckPredicate3,
176     OPC_CheckPredicate4,
177     OPC_CheckPredicate5,
178     OPC_CheckPredicate6,
179     OPC_CheckPredicate7,
180     OPC_CheckPredicateWithOperands,
181     OPC_CheckOpcode,
182     OPC_SwitchOpcode,
183     OPC_CheckType,
184     // Space-optimized forms that implicitly encode VT.
185     OPC_CheckTypeI32,
186     OPC_CheckTypeI64,
187     OPC_CheckTypeRes,
188     OPC_SwitchType,
189     OPC_CheckChild0Type,
190     OPC_CheckChild1Type,
191     OPC_CheckChild2Type,
192     OPC_CheckChild3Type,
193     OPC_CheckChild4Type,
194     OPC_CheckChild5Type,
195     OPC_CheckChild6Type,
196     OPC_CheckChild7Type,
197 
198     OPC_CheckChild0TypeI32,
199     OPC_CheckChild1TypeI32,
200     OPC_CheckChild2TypeI32,
201     OPC_CheckChild3TypeI32,
202     OPC_CheckChild4TypeI32,
203     OPC_CheckChild5TypeI32,
204     OPC_CheckChild6TypeI32,
205     OPC_CheckChild7TypeI32,
206 
207     OPC_CheckChild0TypeI64,
208     OPC_CheckChild1TypeI64,
209     OPC_CheckChild2TypeI64,
210     OPC_CheckChild3TypeI64,
211     OPC_CheckChild4TypeI64,
212     OPC_CheckChild5TypeI64,
213     OPC_CheckChild6TypeI64,
214     OPC_CheckChild7TypeI64,
215 
216     OPC_CheckInteger,
217     OPC_CheckChild0Integer,
218     OPC_CheckChild1Integer,
219     OPC_CheckChild2Integer,
220     OPC_CheckChild3Integer,
221     OPC_CheckChild4Integer,
222     OPC_CheckCondCode,
223     OPC_CheckChild2CondCode,
224     OPC_CheckValueType,
225     OPC_CheckComplexPat,
226     OPC_CheckComplexPat0,
227     OPC_CheckComplexPat1,
228     OPC_CheckComplexPat2,
229     OPC_CheckComplexPat3,
230     OPC_CheckComplexPat4,
231     OPC_CheckComplexPat5,
232     OPC_CheckComplexPat6,
233     OPC_CheckComplexPat7,
234     OPC_CheckAndImm,
235     OPC_CheckOrImm,
236     OPC_CheckImmAllOnesV,
237     OPC_CheckImmAllZerosV,
238     OPC_CheckFoldableChainNode,
239 
240     OPC_EmitInteger,
241     // Space-optimized forms that implicitly encode integer VT.
242     OPC_EmitInteger8,
243     OPC_EmitInteger16,
244     OPC_EmitInteger32,
245     OPC_EmitInteger64,
246     OPC_EmitStringInteger,
247     // Space-optimized forms that implicitly encode integer VT.
248     OPC_EmitStringInteger32,
249     OPC_EmitRegister,
250     OPC_EmitRegisterI32,
251     OPC_EmitRegisterI64,
252     OPC_EmitRegister2,
253     OPC_EmitConvertToTarget,
254     OPC_EmitConvertToTarget0,
255     OPC_EmitConvertToTarget1,
256     OPC_EmitConvertToTarget2,
257     OPC_EmitConvertToTarget3,
258     OPC_EmitConvertToTarget4,
259     OPC_EmitConvertToTarget5,
260     OPC_EmitConvertToTarget6,
261     OPC_EmitConvertToTarget7,
262     OPC_EmitMergeInputChains,
263     OPC_EmitMergeInputChains1_0,
264     OPC_EmitMergeInputChains1_1,
265     OPC_EmitMergeInputChains1_2,
266     OPC_EmitCopyToReg,
267     OPC_EmitCopyToReg0,
268     OPC_EmitCopyToReg1,
269     OPC_EmitCopyToReg2,
270     OPC_EmitCopyToReg3,
271     OPC_EmitCopyToReg4,
272     OPC_EmitCopyToReg5,
273     OPC_EmitCopyToReg6,
274     OPC_EmitCopyToReg7,
275     OPC_EmitCopyToRegTwoByte,
276     OPC_EmitNodeXForm,
277     OPC_EmitNode,
278     // Space-optimized forms that implicitly encode number of result VTs.
279     OPC_EmitNode0,
280     OPC_EmitNode1,
281     OPC_EmitNode2,
282     // Space-optimized forms that implicitly encode EmitNodeInfo.
283     OPC_EmitNode0None,
284     OPC_EmitNode1None,
285     OPC_EmitNode2None,
286     OPC_EmitNode0Chain,
287     OPC_EmitNode1Chain,
288     OPC_EmitNode2Chain,
289     OPC_MorphNodeTo,
290     // Space-optimized forms that implicitly encode number of result VTs.
291     OPC_MorphNodeTo0,
292     OPC_MorphNodeTo1,
293     OPC_MorphNodeTo2,
294     // Space-optimized forms that implicitly encode EmitNodeInfo.
295     OPC_MorphNodeTo0None,
296     OPC_MorphNodeTo1None,
297     OPC_MorphNodeTo2None,
298     OPC_MorphNodeTo0Chain,
299     OPC_MorphNodeTo1Chain,
300     OPC_MorphNodeTo2Chain,
301     OPC_MorphNodeTo0GlueInput,
302     OPC_MorphNodeTo1GlueInput,
303     OPC_MorphNodeTo2GlueInput,
304     OPC_MorphNodeTo0GlueOutput,
305     OPC_MorphNodeTo1GlueOutput,
306     OPC_MorphNodeTo2GlueOutput,
307     OPC_CompleteMatch,
308     // Contains offset in table for pattern being selected
309     OPC_Coverage
310   };
311 
312   enum {
313     OPFL_None       = 0,  // Node has no chain or glue input and isn't variadic.
314     OPFL_Chain      = 1,     // Node has a chain input.
315     OPFL_GlueInput  = 2,     // Node has a glue input.
316     OPFL_GlueOutput = 4,     // Node has a glue output.
317     OPFL_MemRefs    = 8,     // Node gets accumulated MemRefs.
318     OPFL_Variadic0  = 1<<4,  // Node is variadic, root has 0 fixed inputs.
319     OPFL_Variadic1  = 2<<4,  // Node is variadic, root has 1 fixed inputs.
320     OPFL_Variadic2  = 3<<4,  // Node is variadic, root has 2 fixed inputs.
321     OPFL_Variadic3  = 4<<4,  // Node is variadic, root has 3 fixed inputs.
322     OPFL_Variadic4  = 5<<4,  // Node is variadic, root has 4 fixed inputs.
323     OPFL_Variadic5  = 6<<4,  // Node is variadic, root has 5 fixed inputs.
324     OPFL_Variadic6  = 7<<4,  // Node is variadic, root has 6 fixed inputs.
325 
326     OPFL_VariadicInfo = OPFL_Variadic6
327   };
328 
329   /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
330   /// number of fixed arity values that should be skipped when copying from the
331   /// root.
332   static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
333     return ((Flags&OPFL_VariadicInfo) >> 4)-1;
334   }
335 
336 
337 protected:
338   /// DAGSize - Size of DAG being instruction selected.
339   ///
340   unsigned DAGSize = 0;
341 
342   /// ReplaceUses - replace all uses of the old node F with the use
343   /// of the new node T.
344   void ReplaceUses(SDValue F, SDValue T) {
345     CurDAG->ReplaceAllUsesOfValueWith(F, T);
346     EnforceNodeIdInvariant(T.getNode());
347   }
348 
349   /// ReplaceUses - replace all uses of the old nodes F with the use
350   /// of the new nodes T.
351   void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) {
352     CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num);
353     for (unsigned i = 0; i < Num; ++i)
354       EnforceNodeIdInvariant(T[i].getNode());
355   }
356 
357   /// ReplaceUses - replace all uses of the old node F with the use
358   /// of the new node T.
359   void ReplaceUses(SDNode *F, SDNode *T) {
360     CurDAG->ReplaceAllUsesWith(F, T);
361     EnforceNodeIdInvariant(T);
362   }
363 
364   /// Replace all uses of \c F with \c T, then remove \c F from the DAG.
365   void ReplaceNode(SDNode *F, SDNode *T) {
366     CurDAG->ReplaceAllUsesWith(F, T);
367     EnforceNodeIdInvariant(T);
368     CurDAG->RemoveDeadNode(F);
369   }
370 
371   /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
372   /// by tblgen.  Others should not call it.
373   void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
374                                      const SDLoc &DL);
375 
376   /// getPatternForIndex - Patterns selected by tablegen during ISEL
377   virtual StringRef getPatternForIndex(unsigned index) {
378     llvm_unreachable("Tblgen should generate the implementation of this!");
379   }
380 
381   /// getIncludePathForIndex - get the td source location of pattern instantiation
382   virtual StringRef getIncludePathForIndex(unsigned index) {
383     llvm_unreachable("Tblgen should generate the implementation of this!");
384   }
385 
386   bool shouldOptForSize(const MachineFunction *MF) const {
387     return CurDAG->shouldOptForSize();
388   }
389 
390 public:
391   // Calls to these predicates are generated by tblgen.
392   bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
393                     int64_t DesiredMaskS) const;
394   bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
395                     int64_t DesiredMaskS) const;
396 
397 
398   /// CheckPatternPredicate - This function is generated by tblgen in the
399   /// target.  It runs the specified pattern predicate and returns true if it
400   /// succeeds or false if it fails.  The number is a private implementation
401   /// detail to the code tblgen produces.
402   virtual bool CheckPatternPredicate(unsigned PredNo) const {
403     llvm_unreachable("Tblgen should generate the implementation of this!");
404   }
405 
406   /// CheckNodePredicate - This function is generated by tblgen in the target.
407   /// It runs node predicate number PredNo and returns true if it succeeds or
408   /// false if it fails.  The number is a private implementation
409   /// detail to the code tblgen produces.
410   virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {
411     llvm_unreachable("Tblgen should generate the implementation of this!");
412   }
413 
414   /// CheckNodePredicateWithOperands - This function is generated by tblgen in
415   /// the target.
416   /// It runs node predicate number PredNo and returns true if it succeeds or
417   /// false if it fails.  The number is a private implementation detail to the
418   /// code tblgen produces.
419   virtual bool CheckNodePredicateWithOperands(
420       SDNode *N, unsigned PredNo,
421       const SmallVectorImpl<SDValue> &Operands) const {
422     llvm_unreachable("Tblgen should generate the implementation of this!");
423   }
424 
425   virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N,
426                                    unsigned PatternNo,
427                         SmallVectorImpl<std::pair<SDValue, SDNode*> > &Result) {
428     llvm_unreachable("Tblgen should generate the implementation of this!");
429   }
430 
431   virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {
432     llvm_unreachable("Tblgen should generate this!");
433   }
434 
435   void SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
436                         unsigned TableSize);
437 
438   /// Return true if complex patterns for this target can mutate the
439   /// DAG.
440   virtual bool ComplexPatternFuncMutatesDAG() const {
441     return false;
442   }
443 
444   /// Return whether the node may raise an FP exception.
445   bool mayRaiseFPException(SDNode *Node) const;
446 
447   bool isOrEquivalentToAdd(const SDNode *N) const;
448 
449 private:
450 
451   // Calls to these functions are generated by tblgen.
452   void Select_INLINEASM(SDNode *N);
453   void Select_READ_REGISTER(SDNode *Op);
454   void Select_WRITE_REGISTER(SDNode *Op);
455   void Select_UNDEF(SDNode *N);
456   void CannotYetSelect(SDNode *N);
457 
458   void Select_FREEZE(SDNode *N);
459   void Select_ARITH_FENCE(SDNode *N);
460   void Select_MEMBARRIER(SDNode *N);
461 
462   void pushStackMapLiveVariable(SmallVectorImpl<SDValue> &Ops, SDValue Operand,
463                                 SDLoc DL);
464   void Select_STACKMAP(SDNode *N);
465   void Select_PATCHPOINT(SDNode *N);
466 
467   void Select_JUMP_TABLE_DEBUG_INFO(SDNode *N);
468 
469 private:
470   void DoInstructionSelection();
471   SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
472                     ArrayRef<SDValue> Ops, unsigned EmitNodeInfo);
473 
474   /// Prepares the landing pad to take incoming values or do other EH
475   /// personality specific tasks. Returns true if the block should be
476   /// instruction selected, false if no code should be emitted for it.
477   bool PrepareEHLandingPad();
478 
479   // Mark and Report IPToState for each Block under AsynchEH
480   void reportIPToStateForBlocks(MachineFunction *Fn);
481 
482   /// Perform instruction selection on all basic blocks in the function.
483   void SelectAllBasicBlocks(const Function &Fn);
484 
485   /// Perform instruction selection on a single basic block, for
486   /// instructions between \p Begin and \p End.  \p HadTailCall will be set
487   /// to true if a call in the block was translated as a tail call.
488   void SelectBasicBlock(BasicBlock::const_iterator Begin,
489                         BasicBlock::const_iterator End,
490                         bool &HadTailCall);
491   void FinishBasicBlock();
492 
493   void CodeGenAndEmitDAG();
494 
495   /// Generate instructions for lowering the incoming arguments of the
496   /// given function.
497   void LowerArguments(const Function &F);
498 
499   void ComputeLiveOutVRegInfo();
500 
501   /// Create the scheduler. If a specific scheduler was specified
502   /// via the SchedulerRegistry, use it, otherwise select the
503   /// one preferred by the target.
504   ///
505   ScheduleDAGSDNodes *CreateScheduler();
506 
507   /// OpcodeOffset - This is a cache used to dispatch efficiently into isel
508   /// state machines that start with a OPC_SwitchOpcode node.
509   std::vector<unsigned> OpcodeOffset;
510 
511   void UpdateChains(SDNode *NodeToMatch, SDValue InputChain,
512                     SmallVectorImpl<SDNode *> &ChainNodesMatched,
513                     bool isMorphNodeTo);
514 };
515 
516 }
517 
518 #endif /* LLVM_CODEGEN_SELECTIONDAGISEL_H */
519