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