include/llvm/CodeGen/ScheduleDAG.h

   1 //===------- llvm/CodeGen/ScheduleDAG.h - Common Base Class------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Evan Cheng and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the ScheduleDAG class, which is used as the common
  11 // base class for SelectionDAG-based instruction scheduler.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CODEGEN_SCHEDULEDAG_H
  16 #define LLVM_CODEGEN_SCHEDULEDAG_H
  17
  18 #include "llvm/CodeGen/SelectionDAG.h"
  19
  20 namespace llvm {
  21   struct InstrStage;
  22   class MachineConstantPool;
  23   class MachineDebugInfo;
  24   class MachineInstr;
  25   class MRegisterInfo;
  26   class SelectionDAG;
  27   class SSARegMap;
  28   class TargetInstrInfo;
  29   class TargetInstrDescriptor;
  30   class TargetMachine;
  31
  32   /// HazardRecognizer - This determines whether or not an instruction can be
  33   /// issued this cycle, and whether or not a noop needs to be inserted to handle
  34   /// the hazard.
  35   class HazardRecognizer {
  36   public:
  37     virtual ~HazardRecognizer();
  38
  39     enum HazardType {
  40       NoHazard,      // This instruction can be emitted at this cycle.
  41       Hazard,        // This instruction can't be emitted at this cycle.
  42       NoopHazard,    // This instruction can't be emitted, and needs noops.
  43     };
  44
  45     /// getHazardType - Return the hazard type of emitting this node.  There are
  46     /// three possible results.  Either:
  47     ///  * NoHazard: it is legal to issue this instruction on this cycle.
  48     ///  * Hazard: issuing this instruction would stall the machine.  If some
  49     ///     other instruction is available, issue it first.
  50     ///  * NoopHazard: issuing this instruction would break the program.  If
  51     ///     some other instruction can be issued, do so, otherwise issue a noop.
  52     virtual HazardType getHazardType(SDNode *Node) {
  53       return NoHazard;
  54     }
  55
  56     /// EmitInstruction - This callback is invoked when an instruction is
  57     /// emitted, to advance the hazard state.
  58     virtual void EmitInstruction(SDNode *Node) {
  59     }
  60
  61     /// AdvanceCycle - This callback is invoked when no instructions can be
  62     /// issued on this cycle without a hazard.  This should increment the
  63     /// internal state of the hazard recognizer so that previously "Hazard"
  64     /// instructions will now not be hazards.
  65     virtual void AdvanceCycle() {
  66     }
  67
  68     /// EmitNoop - This callback is invoked when a noop was added to the
  69     /// instruction stream.
  70     virtual void EmitNoop() {
  71     }
  72   };
  73
  74   class ScheduleDAG {
  75   public:
  76     SelectionDAG &DAG;                    // DAG of the current basic block
  77     MachineBasicBlock *BB;                // Current basic block
  78     const TargetMachine &TM;              // Target processor
  79     const TargetInstrInfo *TII;           // Target instruction information
  80     const MRegisterInfo *MRI;             // Target processor register info
  81     SSARegMap *RegMap;                    // Virtual/real register map
  82     MachineConstantPool *ConstPool;       // Target constant pool
  83
  84     ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb,
  85                 const TargetMachine &tm)
  86       : DAG(dag), BB(bb), TM(tm) {}
  87
  88     virtual ~ScheduleDAG() {}
  89
  90     /// Run - perform scheduling.
  91     ///
  92     MachineBasicBlock *Run();
  93
  94     /// isPassiveNode - Return true if the node is a non-scheduled leaf.
  95     ///
  96     static bool isPassiveNode(SDNode *Node) {
  97       if (isa<ConstantSDNode>(Node))       return true;
  98       if (isa<RegisterSDNode>(Node))       return true;
  99       if (isa<GlobalAddressSDNode>(Node))  return true;
 100       if (isa<BasicBlockSDNode>(Node))     return true;
 101       if (isa<FrameIndexSDNode>(Node))     return true;
 102       if (isa<ConstantPoolSDNode>(Node))   return true;
 103       if (isa<ExternalSymbolSDNode>(Node)) return true;
 104       return false;
 105     }
 106
 107     /// EmitNode - Generate machine code for an node and needed dependencies.
 108     /// VRBaseMap contains, for each already emitted node, the first virtual
 109     /// register number for the results of the node.
 110     ///
 111     void EmitNode(SDNode *Node, std::map<SDNode*, unsigned> &VRBaseMap);
 112
 113     /// EmitNoop - Emit a noop instruction.
 114     ///
 115     void EmitNoop();
 116
 117
 118     /// Schedule - Order nodes according to selected style.
 119     ///
 120     virtual void Schedule() {}
 121
 122   private:
 123     void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum,
 124                     const TargetInstrDescriptor *II,
 125                     std::map<SDNode*, unsigned> &VRBaseMap);
 126   };
 127
 128   ScheduleDAG *createBFS_DAGScheduler(SelectionDAG &DAG, MachineBasicBlock *BB);
 129
 130   /// createSimpleDAGScheduler - This creates a simple two pass instruction
 131   /// scheduler.
 132   ScheduleDAG* createSimpleDAGScheduler(bool NoItins, SelectionDAG &DAG,
 133                                         MachineBasicBlock *BB);
 134
 135   /// createBURRListDAGScheduler - This creates a bottom up register usage
 136   /// reduction list scheduler.
 137   ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG,
 138                                           MachineBasicBlock *BB);
 139
 140   /// createTDListDAGScheduler - This creates a top-down list scheduler with
 141   /// the specified hazard recognizer.  This takes ownership of the hazard
 142   /// recognizer and deletes it when done.
 143   ScheduleDAG* createTDListDAGScheduler(SelectionDAG &DAG,
 144                                         MachineBasicBlock *BB,
 145                                         HazardRecognizer *HR);
 146 }
 147
 148 #endif