Home | History | Annotate | Download | only in CodeGen
      1 //===-- llvm/CodeGen/SelectionDAGISel.h - Common Base Class------*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file implements the SelectionDAGISel class, which is used as the common
     11 // base class for SelectionDAG-based instruction selectors.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #ifndef LLVM_CODEGEN_SELECTIONDAGISEL_H
     16 #define LLVM_CODEGEN_SELECTIONDAGISEL_H
     17 
     18 #include "llvm/CodeGen/MachineFunctionPass.h"
     19 #include "llvm/CodeGen/SelectionDAG.h"
     20 #include "llvm/IR/BasicBlock.h"
     21 #include "llvm/Pass.h"
     22 #include "llvm/Target/TargetSubtargetInfo.h"
     23 
     24 namespace llvm {
     25   class FastISel;
     26   class SelectionDAGBuilder;
     27   class SDValue;
     28   class MachineRegisterInfo;
     29   class MachineBasicBlock;
     30   class MachineFunction;
     31   class MachineInstr;
     32   class TargetLowering;
     33   class TargetLibraryInfo;
     34   class FunctionLoweringInfo;
     35   class ScheduleHazardRecognizer;
     36   class GCFunctionInfo;
     37   class ScheduleDAGSDNodes;
     38   class LoadInst;
     39 
     40 /// SelectionDAGISel - This is the common base class used for SelectionDAG-based
     41 /// pattern-matching instruction selectors.
     42 class SelectionDAGISel : public MachineFunctionPass {
     43 public:
     44   TargetMachine &TM;
     45   const TargetLibraryInfo *LibInfo;
     46   FunctionLoweringInfo *FuncInfo;
     47   MachineFunction *MF;
     48   MachineRegisterInfo *RegInfo;
     49   SelectionDAG *CurDAG;
     50   SelectionDAGBuilder *SDB;
     51   AliasAnalysis *AA;
     52   GCFunctionInfo *GFI;
     53   CodeGenOpt::Level OptLevel;
     54   const TargetInstrInfo *TII;
     55   const TargetLowering *TLI;
     56 
     57   static char ID;
     58 
     59   explicit SelectionDAGISel(TargetMachine &tm,
     60                             CodeGenOpt::Level OL = CodeGenOpt::Default);
     61   ~SelectionDAGISel() override;
     62 
     63   const TargetLowering *getTargetLowering() const { return TLI; }
     64 
     65   void getAnalysisUsage(AnalysisUsage &AU) const override;
     66 
     67   bool runOnMachineFunction(MachineFunction &MF) override;
     68 
     69   virtual void EmitFunctionEntryCode() {}
     70 
     71   /// PreprocessISelDAG - This hook allows targets to hack on the graph before
     72   /// instruction selection starts.
     73   virtual void PreprocessISelDAG() {}
     74 
     75   /// PostprocessISelDAG() - This hook allows the target to hack on the graph
     76   /// right after selection.
     77   virtual void PostprocessISelDAG() {}
     78 
     79   /// Select - Main hook targets implement to select a node.
     80   virtual SDNode *Select(SDNode *N) = 0;
     81 
     82   /// SelectInlineAsmMemoryOperand - Select the specified address as a target
     83   /// addressing mode, according to the specified constraint.  If this does
     84   /// not match or is not implemented, return true.  The resultant operands
     85   /// (which will appear in the machine instruction) should be added to the
     86   /// OutOps vector.
     87   virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op,
     88                                             unsigned ConstraintID,
     89                                             std::vector<SDValue> &OutOps) {
     90     return true;
     91   }
     92 
     93   /// IsProfitableToFold - Returns true if it's profitable to fold the specific
     94   /// operand node N of U during instruction selection that starts at Root.
     95   virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const;
     96 
     97   /// IsLegalToFold - Returns true if the specific operand node N of
     98   /// U can be folded during instruction selection that starts at Root.
     99   /// FIXME: This is a static member function because the MSP430/X86
    100   /// targets, which uses it during isel.  This could become a proper member.
    101   static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
    102                             CodeGenOpt::Level OptLevel,
    103                             bool IgnoreChains = false);
    104 
    105   // Opcodes used by the DAG state machine:
    106   enum BuiltinOpcodes {
    107     OPC_Scope,
    108     OPC_RecordNode,
    109     OPC_RecordChild0, OPC_RecordChild1, OPC_RecordChild2, OPC_RecordChild3,
    110     OPC_RecordChild4, OPC_RecordChild5, OPC_RecordChild6, OPC_RecordChild7,
    111     OPC_RecordMemRef,
    112     OPC_CaptureGlueInput,
    113     OPC_MoveChild,
    114     OPC_MoveParent,
    115     OPC_CheckSame,
    116     OPC_CheckChild0Same, OPC_CheckChild1Same,
    117     OPC_CheckChild2Same, OPC_CheckChild3Same,
    118     OPC_CheckPatternPredicate,
    119     OPC_CheckPredicate,
    120     OPC_CheckOpcode,
    121     OPC_SwitchOpcode,
    122     OPC_CheckType,
    123     OPC_SwitchType,
    124     OPC_CheckChild0Type, OPC_CheckChild1Type, OPC_CheckChild2Type,
    125     OPC_CheckChild3Type, OPC_CheckChild4Type, OPC_CheckChild5Type,
    126     OPC_CheckChild6Type, OPC_CheckChild7Type,
    127     OPC_CheckInteger,
    128     OPC_CheckChild0Integer, OPC_CheckChild1Integer, OPC_CheckChild2Integer,
    129     OPC_CheckChild3Integer, OPC_CheckChild4Integer,
    130     OPC_CheckCondCode,
    131     OPC_CheckValueType,
    132     OPC_CheckComplexPat,
    133     OPC_CheckAndImm, OPC_CheckOrImm,
    134     OPC_CheckFoldableChainNode,
    135 
    136     OPC_EmitInteger,
    137     OPC_EmitRegister,
    138     OPC_EmitRegister2,
    139     OPC_EmitConvertToTarget,
    140     OPC_EmitMergeInputChains,
    141     OPC_EmitMergeInputChains1_0,
    142     OPC_EmitMergeInputChains1_1,
    143     OPC_EmitCopyToReg,
    144     OPC_EmitNodeXForm,
    145     OPC_EmitNode,
    146     OPC_MorphNodeTo,
    147     OPC_MarkGlueResults,
    148     OPC_CompleteMatch
    149   };
    150 
    151   enum {
    152     OPFL_None       = 0,  // Node has no chain or glue input and isn't variadic.
    153     OPFL_Chain      = 1,     // Node has a chain input.
    154     OPFL_GlueInput  = 2,     // Node has a glue input.
    155     OPFL_GlueOutput = 4,     // Node has a glue output.
    156     OPFL_MemRefs    = 8,     // Node gets accumulated MemRefs.
    157     OPFL_Variadic0  = 1<<4,  // Node is variadic, root has 0 fixed inputs.
    158     OPFL_Variadic1  = 2<<4,  // Node is variadic, root has 1 fixed inputs.
    159     OPFL_Variadic2  = 3<<4,  // Node is variadic, root has 2 fixed inputs.
    160     OPFL_Variadic3  = 4<<4,  // Node is variadic, root has 3 fixed inputs.
    161     OPFL_Variadic4  = 5<<4,  // Node is variadic, root has 4 fixed inputs.
    162     OPFL_Variadic5  = 6<<4,  // Node is variadic, root has 5 fixed inputs.
    163     OPFL_Variadic6  = 7<<4,  // Node is variadic, root has 6 fixed inputs.
    164 
    165     OPFL_VariadicInfo = OPFL_Variadic6
    166   };
    167 
    168   /// getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the
    169   /// number of fixed arity values that should be skipped when copying from the
    170   /// root.
    171   static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
    172     return ((Flags&OPFL_VariadicInfo) >> 4)-1;
    173   }
    174 
    175 
    176 protected:
    177   /// DAGSize - Size of DAG being instruction selected.
    178   ///
    179   unsigned DAGSize;
    180 
    181   /// ReplaceUses - replace all uses of the old node F with the use
    182   /// of the new node T.
    183   void ReplaceUses(SDValue F, SDValue T) {
    184     CurDAG->ReplaceAllUsesOfValueWith(F, T);
    185   }
    186 
    187   /// ReplaceUses - replace all uses of the old nodes F with the use
    188   /// of the new nodes T.
    189   void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) {
    190     CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num);
    191   }
    192 
    193   /// ReplaceUses - replace all uses of the old node F with the use
    194   /// of the new node T.
    195   void ReplaceUses(SDNode *F, SDNode *T) {
    196     CurDAG->ReplaceAllUsesWith(F, T);
    197   }
    198 
    199 
    200   /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
    201   /// by tblgen.  Others should not call it.
    202   void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops, SDLoc DL);
    203 
    204 
    205 public:
    206   // Calls to these predicates are generated by tblgen.
    207   bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
    208                     int64_t DesiredMaskS) const;
    209   bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
    210                     int64_t DesiredMaskS) const;
    211 
    212 
    213   /// CheckPatternPredicate - This function is generated by tblgen in the
    214   /// target.  It runs the specified pattern predicate and returns true if it
    215   /// succeeds or false if it fails.  The number is a private implementation
    216   /// detail to the code tblgen produces.
    217   virtual bool CheckPatternPredicate(unsigned PredNo) const {
    218     llvm_unreachable("Tblgen should generate the implementation of this!");
    219   }
    220 
    221   /// CheckNodePredicate - This function is generated by tblgen in the target.
    222   /// It runs node predicate number PredNo and returns true if it succeeds or
    223   /// false if it fails.  The number is a private implementation
    224   /// detail to the code tblgen produces.
    225   virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {
    226     llvm_unreachable("Tblgen should generate the implementation of this!");
    227   }
    228 
    229   virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N,
    230                                    unsigned PatternNo,
    231                         SmallVectorImpl<std::pair<SDValue, SDNode*> > &Result) {
    232     llvm_unreachable("Tblgen should generate the implementation of this!");
    233   }
    234 
    235   virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {
    236     llvm_unreachable("Tblgen should generate this!");
    237   }
    238 
    239   SDNode *SelectCodeCommon(SDNode *NodeToMatch,
    240                            const unsigned char *MatcherTable,
    241                            unsigned TableSize);
    242 
    243   /// \brief Return true if complex patterns for this target can mutate the
    244   /// DAG.
    245   virtual bool ComplexPatternFuncMutatesDAG() const {
    246     return false;
    247   }
    248 
    249 private:
    250 
    251   // Calls to these functions are generated by tblgen.
    252   SDNode *Select_INLINEASM(SDNode *N);
    253   SDNode *Select_READ_REGISTER(SDNode *N);
    254   SDNode *Select_WRITE_REGISTER(SDNode *N);
    255   SDNode *Select_UNDEF(SDNode *N);
    256   void CannotYetSelect(SDNode *N);
    257 
    258 private:
    259   void DoInstructionSelection();
    260   SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTs,
    261                     ArrayRef<SDValue> Ops, unsigned EmitNodeInfo);
    262 
    263   /// Prepares the landing pad to take incoming values or do other EH
    264   /// personality specific tasks. Returns true if the block should be
    265   /// instruction selected, false if no code should be emitted for it.
    266   bool PrepareEHLandingPad();
    267 
    268   /// \brief Perform instruction selection on all basic blocks in the function.
    269   void SelectAllBasicBlocks(const Function &Fn);
    270 
    271   /// \brief Perform instruction selection on a single basic block, for
    272   /// instructions between \p Begin and \p End.  \p HadTailCall will be set
    273   /// to true if a call in the block was translated as a tail call.
    274   void SelectBasicBlock(BasicBlock::const_iterator Begin,
    275                         BasicBlock::const_iterator End,
    276                         bool &HadTailCall);
    277   void FinishBasicBlock();
    278 
    279   void CodeGenAndEmitDAG();
    280 
    281   /// \brief Generate instructions for lowering the incoming arguments of the
    282   /// given function.
    283   void LowerArguments(const Function &F);
    284 
    285   void ComputeLiveOutVRegInfo();
    286 
    287   /// Create the scheduler. If a specific scheduler was specified
    288   /// via the SchedulerRegistry, use it, otherwise select the
    289   /// one preferred by the target.
    290   ///
    291   ScheduleDAGSDNodes *CreateScheduler();
    292 
    293   /// OpcodeOffset - This is a cache used to dispatch efficiently into isel
    294   /// state machines that start with a OPC_SwitchOpcode node.
    295   std::vector<unsigned> OpcodeOffset;
    296 
    297   void UpdateChainsAndGlue(SDNode *NodeToMatch, SDValue InputChain,
    298                            const SmallVectorImpl<SDNode*> &ChainNodesMatched,
    299                            SDValue InputGlue, const SmallVectorImpl<SDNode*> &F,
    300                            bool isMorphNodeTo);
    301 
    302 };
    303 
    304 }
    305 
    306 #endif /* LLVM_CODEGEN_SELECTIONDAGISEL_H */
    307