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 #include <set>
  21
  22 namespace llvm {
  23   struct InstrStage;
  24   class MachineConstantPool;
  25   class MachineDebugInfo;
  26   class MachineInstr;
  27   class MRegisterInfo;
  28   class SelectionDAG;
  29   class SelectionDAGISel;
  30   class SSARegMap;
  31   class TargetInstrInfo;
  32   class TargetInstrDescriptor;
  33   class TargetMachine;
  34
  35   /// HazardRecognizer - This determines whether or not an instruction can be
  36   /// issued this cycle, and whether or not a noop needs to be inserted to handle
  37   /// the hazard.
  38   class HazardRecognizer {
  39   public:
  40     virtual ~HazardRecognizer();
  41
  42     enum HazardType {
  43       NoHazard,      // This instruction can be emitted at this cycle.
  44       Hazard,        // This instruction can't be emitted at this cycle.
  45       NoopHazard     // This instruction can't be emitted, and needs noops.
  46     };
  47
  48     /// getHazardType - Return the hazard type of emitting this node.  There are
  49     /// three possible results.  Either:
  50     ///  * NoHazard: it is legal to issue this instruction on this cycle.
  51     ///  * Hazard: issuing this instruction would stall the machine.  If some
  52     ///     other instruction is available, issue it first.
  53     ///  * NoopHazard: issuing this instruction would break the program.  If
  54     ///     some other instruction can be issued, do so, otherwise issue a noop.
  55     virtual HazardType getHazardType(SDNode *Node) {
  56       return NoHazard;
  57     }
  58
  59     /// EmitInstruction - This callback is invoked when an instruction is
  60     /// emitted, to advance the hazard state.
  61     virtual void EmitInstruction(SDNode *Node) {
  62     }
  63
  64     /// AdvanceCycle - This callback is invoked when no instructions can be
  65     /// issued on this cycle without a hazard.  This should increment the
  66     /// internal state of the hazard recognizer so that previously "Hazard"
  67     /// instructions will now not be hazards.
  68     virtual void AdvanceCycle() {
  69     }
  70
  71     /// EmitNoop - This callback is invoked when a noop was added to the
  72     /// instruction stream.
  73     virtual void EmitNoop() {
  74     }
  75   };
  76
  77   /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
  78   /// a group of nodes flagged together.
  79   struct SUnit {
  80     SDNode *Node;                       // Representative node.
  81     SmallVector<SDNode*,4> FlaggedNodes;// All nodes flagged to Node.
  82
  83     // Preds/Succs - The SUnits before/after us in the graph.  The boolean value
  84     // is true if the edge is a token chain edge, false if it is a value edge.
  85     std::set<std::pair<SUnit*,bool> > Preds;  // All sunit predecessors.
  86     std::set<std::pair<SUnit*,bool> > Succs;  // All sunit successors.
  87
  88     short NumPreds;                     // # of preds.
  89     short NumSuccs;                     // # of sucss.
  90     short NumPredsLeft;                 // # of preds not scheduled.
  91     short NumSuccsLeft;                 // # of succs not scheduled.
  92     short NumChainPredsLeft;            // # of chain preds not scheduled.
  93     short NumChainSuccsLeft;            // # of chain succs not scheduled.
  94     bool isTwoAddress     : 1;          // Is a two-address instruction.
  95     bool isCommutable     : 1;          // Is a commutable instruction.
  96     bool isPending        : 1;          // True once pending.
  97     bool isAvailable      : 1;          // True once available.
  98     bool isScheduled      : 1;          // True once scheduled.
  99     unsigned short Latency;             // Node latency.
 100     unsigned CycleBound;                // Upper/lower cycle to be scheduled at.
 101     unsigned Cycle;                     // Once scheduled, the cycle of the op.
 102     unsigned Depth;                     // Node depth;
 103     unsigned Height;                    // Node height;
 104     unsigned NodeNum;                   // Entry # of node in the node vector.
 105
 106     SUnit(SDNode *node, unsigned nodenum)
 107       : Node(node), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
 108         NumChainPredsLeft(0), NumChainSuccsLeft(0),
 109         isTwoAddress(false), isCommutable(false),
 110         isPending(false), isAvailable(false), isScheduled(false),
 111         Latency(0), CycleBound(0), Cycle(0), Depth(0), Height(0),
 112         NodeNum(nodenum) {}
 113
 114     void dump(const SelectionDAG *G) const;
 115     void dumpAll(const SelectionDAG *G) const;
 116   };
 117
 118   //===--------------------------------------------------------------------===//
 119   /// SchedulingPriorityQueue - This interface is used to plug different
 120   /// priorities computation algorithms into the list scheduler. It implements
 121   /// the interface of a standard priority queue, where nodes are inserted in
 122   /// arbitrary order and returned in priority order.  The computation of the
 123   /// priority and the representation of the queue are totally up to the
 124   /// implementation to decide.
 125   ///
 126   class SchedulingPriorityQueue {
 127   public:
 128     virtual ~SchedulingPriorityQueue() {}
 129
 130     virtual void initNodes(const std::vector<SUnit> &SUnits) = 0;
 131     virtual void releaseState() = 0;
 132
 133     virtual bool empty() const = 0;
 134     virtual void push(SUnit *U) = 0;
 135
 136     virtual void push_all(const std::vector<SUnit *> &Nodes) = 0;
 137     virtual SUnit *pop() = 0;
 138
 139     /// ScheduledNode - As each node is scheduled, this method is invoked.  This
 140     /// allows the priority function to adjust the priority of node that have
 141     /// already been emitted.
 142     virtual void ScheduledNode(SUnit *Node) {}
 143   };
 144
 145   class ScheduleDAG {
 146   public:
 147     SelectionDAG &DAG;                    // DAG of the current basic block
 148     MachineBasicBlock *BB;                // Current basic block
 149     const TargetMachine &TM;              // Target processor
 150     const TargetInstrInfo *TII;           // Target instruction information
 151     const MRegisterInfo *MRI;             // Target processor register info
 152     SSARegMap *RegMap;                    // Virtual/real register map
 153     MachineConstantPool *ConstPool;       // Target constant pool
 154     std::vector<SUnit*> Sequence;         // The schedule. Null SUnit*'s
 155                                           // represent noop instructions.
 156     std::map<SDNode*, SUnit*> SUnitMap;   // SDNode to SUnit mapping (n -> 1).
 157     std::vector<SUnit> SUnits;            // The scheduling units.
 158     std::set<SDNode*> CommuteSet;         // Nodes the should be commuted.
 159
 160     ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb,
 161                 const TargetMachine &tm)
 162       : DAG(dag), BB(bb), TM(tm) {}
 163
 164     virtual ~ScheduleDAG() {}
 165
 166     /// Run - perform scheduling.
 167     ///
 168     MachineBasicBlock *Run();
 169
 170     /// isPassiveNode - Return true if the node is a non-scheduled leaf.
 171     ///
 172     static bool isPassiveNode(SDNode *Node) {
 173       if (isa<ConstantSDNode>(Node))       return true;
 174       if (isa<RegisterSDNode>(Node))       return true;
 175       if (isa<GlobalAddressSDNode>(Node))  return true;
 176       if (isa<BasicBlockSDNode>(Node))     return true;
 177       if (isa<FrameIndexSDNode>(Node))     return true;
 178       if (isa<ConstantPoolSDNode>(Node))   return true;
 179       if (isa<JumpTableSDNode>(Node))      return true;
 180       if (isa<ExternalSymbolSDNode>(Node)) return true;
 181       return false;
 182     }
 183
 184     /// NewSUnit - Creates a new SUnit and return a ptr to it.
 185     ///
 186     SUnit *NewSUnit(SDNode *N) {
 187       SUnits.push_back(SUnit(N, SUnits.size()));
 188       return &SUnits.back();
 189     }
 190
 191     /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
 192     /// This SUnit graph is similar to the SelectionDAG, but represents flagged
 193     /// together nodes with a single SUnit.
 194     void BuildSchedUnits();
 195
 196     /// CalculateDepths, CalculateHeights - Calculate node depth / height.
 197     ///
 198     void CalculateDepths();
 199     void CalculateHeights();
 200
 201     /// EmitNode - Generate machine code for an node and needed dependencies.
 202     /// VRBaseMap contains, for each already emitted node, the first virtual
 203     /// register number for the results of the node.
 204     ///
 205     void EmitNode(SDNode *Node, std::map<SDNode*, unsigned> &VRBaseMap);
 206
 207     /// EmitNoop - Emit a noop instruction.
 208     ///
 209     void EmitNoop();
 210
 211     void EmitSchedule();
 212
 213     void dumpSchedule() const;
 214
 215     /// Schedule - Order nodes according to selected style.
 216     ///
 217     virtual void Schedule() {}
 218
 219   private:
 220     void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum,
 221                     const TargetInstrDescriptor *II,
 222                     std::map<SDNode*, unsigned> &VRBaseMap);
 223   };
 224
 225   /// createBFS_DAGScheduler - This creates a simple breadth first instruction
 226   /// scheduler.
 227   ScheduleDAG *createBFS_DAGScheduler(SelectionDAGISel *IS,
 228                                       SelectionDAG *DAG,
 229                                       MachineBasicBlock *BB);
 230
 231   /// createSimpleDAGScheduler - This creates a simple two pass instruction
 232   /// scheduler using instruction itinerary.
 233   ScheduleDAG* createSimpleDAGScheduler(SelectionDAGISel *IS,
 234                                         SelectionDAG *DAG,
 235                                         MachineBasicBlock *BB);
 236
 237   /// createNoItinsDAGScheduler - This creates a simple two pass instruction
 238   /// scheduler without using instruction itinerary.
 239   ScheduleDAG* createNoItinsDAGScheduler(SelectionDAGISel *IS,
 240                                          SelectionDAG *DAG,
 241                                          MachineBasicBlock *BB);
 242
 243   /// createBURRListDAGScheduler - This creates a bottom up register usage
 244   /// reduction list scheduler.
 245   ScheduleDAG* createBURRListDAGScheduler(SelectionDAGISel *IS,
 246                                           SelectionDAG *DAG,
 247                                           MachineBasicBlock *BB);
 248
 249   /// createTDRRListDAGScheduler - This creates a top down register usage
 250   /// reduction list scheduler.
 251   ScheduleDAG* createTDRRListDAGScheduler(SelectionDAGISel *IS,
 252                                           SelectionDAG *DAG,
 253                                           MachineBasicBlock *BB);
 254
 255   /// createTDListDAGScheduler - This creates a top-down list scheduler with
 256   /// a hazard recognizer.
 257   ScheduleDAG* createTDListDAGScheduler(SelectionDAGISel *IS,
 258                                         SelectionDAG *DAG,
 259                                         MachineBasicBlock *BB);
 260
 261   /// createDefaultScheduler - This creates an instruction scheduler appropriate
 262   /// for the target.
 263   ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS,
 264                                       SelectionDAG *DAG,
 265                                       MachineBasicBlock *BB);
 266 }
 267
 268 #endif