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   class NodeInfo;
  33   typedef NodeInfo *NodeInfoPtr;
  34   typedef std::vector<NodeInfoPtr>           NIVector;
  35   typedef std::vector<NodeInfoPtr>::iterator NIIterator;
  36
  37   /// HazardRecognizer - This determines whether or not an instruction can be
  38   /// issued this cycle, and whether or not a noop needs to be inserted to handle
  39   /// the hazard.
  40   class HazardRecognizer {
  41   public:
  42     virtual ~HazardRecognizer();
  43
  44     enum HazardType {
  45       NoHazard,      // This instruction can be emitted at this cycle.
  46       Hazard,        // This instruction can't be emitted at this cycle.
  47       NoopHazard,    // This instruction can't be emitted, and needs noops.
  48     };
  49
  50     /// getHazardType - Return the hazard type of emitting this node.  There are
  51     /// three possible results.  Either:
  52     ///  * NoHazard: it is legal to issue this instruction on this cycle.
  53     ///  * Hazard: issuing this instruction would stall the machine.  If some
  54     ///     other instruction is available, issue it first.
  55     ///  * NoopHazard: issuing this instruction would break the program.  If
  56     ///     some other instruction can be issued, do so, otherwise issue a noop.
  57     virtual HazardType getHazardType(SDNode *Node) {
  58       return NoHazard;
  59     }
  60
  61     /// EmitInstruction - This callback is invoked when an instruction is
  62     /// emitted, to advance the hazard state.
  63     virtual void EmitInstruction(SDNode *Node) {
  64     }
  65
  66     /// AdvanceCycle - This callback is invoked when no instructions can be
  67     /// issued on this cycle without a hazard.  This should increment the
  68     /// internal state of the hazard recognizer so that previously "Hazard"
  69     /// instructions will now not be hazards.
  70     virtual void AdvanceCycle() {
  71     }
  72
  73     /// EmitNoop - This callback is invoked when a noop was added to the
  74     /// instruction stream.
  75     virtual void EmitNoop() {
  76     }
  77   };
  78
  79   //===--------------------------------------------------------------------===//
  80   ///
  81   /// Node group -  This struct is used to manage flagged node groups.
  82   ///
  83   class NodeGroup {
  84   public:
  85     NodeGroup     *Next;
  86   private:
  87     NIVector      Members;                // Group member nodes
  88     NodeInfo      *Dominator;             // Node with highest latency
  89     unsigned      Latency;                // Total latency of the group
  90     int           Pending;                // Number of visits pending before
  91                                           // adding to order
  92
  93   public:
  94     // Ctor.
  95     NodeGroup() : Next(NULL), Dominator(NULL), Pending(0) {}
  96
  97     // Accessors
  98     inline void setDominator(NodeInfo *D) { Dominator = D; }
  99     inline NodeInfo *getTop() { return Members.front(); }
 100     inline NodeInfo *getBottom() { return Members.back(); }
 101     inline NodeInfo *getDominator() { return Dominator; }
 102     inline void setLatency(unsigned L) { Latency = L; }
 103     inline unsigned getLatency() { return Latency; }
 104     inline int getPending() const { return Pending; }
 105     inline void setPending(int P)  { Pending = P; }
 106     inline int addPending(int I)  { return Pending += I; }
 107
 108     // Pass thru
 109     inline bool group_empty() { return Members.empty(); }
 110     inline NIIterator group_begin() { return Members.begin(); }
 111     inline NIIterator group_end() { return Members.end(); }
 112     inline void group_push_back(const NodeInfoPtr &NI) {
 113       Members.push_back(NI);
 114     }
 115     inline NIIterator group_insert(NIIterator Pos, const NodeInfoPtr &NI) {
 116       return Members.insert(Pos, NI);
 117     }
 118     inline void group_insert(NIIterator Pos, NIIterator First,
 119                              NIIterator Last) {
 120       Members.insert(Pos, First, Last);
 121     }
 122
 123     static void Add(NodeInfo *D, NodeInfo *U);
 124   };
 125
 126   //===--------------------------------------------------------------------===//
 127   ///
 128   /// NodeInfo - This struct tracks information used to schedule the a node.
 129   ///
 130   class NodeInfo {
 131   private:
 132     int           Pending;                // Number of visits pending before
 133                                           // adding to order
 134   public:
 135     SDNode        *Node;                  // DAG node
 136     InstrStage    *StageBegin;            // First stage in itinerary
 137     InstrStage    *StageEnd;              // Last+1 stage in itinerary
 138     unsigned      Latency;                // Total cycles to complete instr
 139     bool          IsCall : 1;             // Is function call
 140     bool          IsLoad : 1;             // Is memory load
 141     bool          IsStore : 1;            // Is memory store
 142     unsigned      Slot;                   // Node's time slot
 143     NodeGroup     *Group;                 // Grouping information
 144 #ifndef NDEBUG
 145     unsigned      Preorder;               // Index before scheduling
 146 #endif
 147
 148     // Ctor.
 149     NodeInfo(SDNode *N = NULL)
 150       : Pending(0)
 151       , Node(N)
 152       , StageBegin(NULL)
 153       , StageEnd(NULL)
 154       , Latency(0)
 155       , IsCall(false)
 156       , Slot(0)
 157       , Group(NULL)
 158 #ifndef NDEBUG
 159       , Preorder(0)
 160 #endif
 161     {}
 162
 163     // Accessors
 164     inline bool isInGroup() const {
 165       assert(!Group || !Group->group_empty() && "Group with no members");
 166       return Group != NULL;
 167     }
 168     inline bool isGroupDominator() const {
 169       return isInGroup() && Group->getDominator() == this;
 170     }
 171     inline int getPending() const {
 172       return Group ? Group->getPending() : Pending;
 173     }
 174     inline void setPending(int P) {
 175       if (Group) Group->setPending(P);
 176       else       Pending = P;
 177     }
 178     inline int addPending(int I) {
 179       if (Group) return Group->addPending(I);
 180       else       return Pending += I;
 181     }
 182   };
 183
 184   //===--------------------------------------------------------------------===//
 185   ///
 186   /// NodeGroupIterator - Iterates over all the nodes indicated by the node
 187   /// info. If the node is in a group then iterate over the members of the
 188   /// group, otherwise just the node info.
 189   ///
 190   class NodeGroupIterator {
 191   private:
 192     NodeInfo   *NI;                       // Node info
 193     NIIterator NGI;                       // Node group iterator
 194     NIIterator NGE;                       // Node group iterator end
 195
 196   public:
 197     // Ctor.
 198     NodeGroupIterator(NodeInfo *N) : NI(N) {
 199       // If the node is in a group then set up the group iterator.  Otherwise
 200       // the group iterators will trip first time out.
 201       if (N->isInGroup()) {
 202         // get Group
 203         NodeGroup *Group = NI->Group;
 204         NGI = Group->group_begin();
 205         NGE = Group->group_end();
 206         // Prevent this node from being used (will be in members list
 207         NI = NULL;
 208       }
 209     }
 210
 211     /// next - Return the next node info, otherwise NULL.
 212     ///
 213     NodeInfo *next() {
 214       // If members list
 215       if (NGI != NGE) return *NGI++;
 216       // Use node as the result (may be NULL)
 217       NodeInfo *Result = NI;
 218       // Only use once
 219       NI = NULL;
 220       // Return node or NULL
 221       return Result;
 222     }
 223   };
 224   //===--------------------------------------------------------------------===//
 225
 226
 227   //===--------------------------------------------------------------------===//
 228   ///
 229   /// NodeGroupOpIterator - Iterates over all the operands of a node.  If the
 230   /// node is a member of a group, this iterates over all the operands of all
 231   /// the members of the group.
 232   ///
 233   class NodeGroupOpIterator {
 234   private:
 235     NodeInfo            *NI;              // Node containing operands
 236     NodeGroupIterator   GI;               // Node group iterator
 237     SDNode::op_iterator OI;               // Operand iterator
 238     SDNode::op_iterator OE;               // Operand iterator end
 239
 240     /// CheckNode - Test if node has more operands.  If not get the next node
 241     /// skipping over nodes that have no operands.
 242     void CheckNode() {
 243       // Only if operands are exhausted first
 244       while (OI == OE) {
 245         // Get next node info
 246         NodeInfo *NI = GI.next();
 247         // Exit if nodes are exhausted
 248         if (!NI) return;
 249         // Get node itself
 250         SDNode *Node = NI->Node;
 251         // Set up the operand iterators
 252         OI = Node->op_begin();
 253         OE = Node->op_end();
 254       }
 255     }
 256
 257   public:
 258     // Ctor.
 259     NodeGroupOpIterator(NodeInfo *N)
 260       : NI(N), GI(N), OI(SDNode::op_iterator()), OE(SDNode::op_iterator()) {}
 261
 262     /// isEnd - Returns true when not more operands are available.
 263     ///
 264     inline bool isEnd() { CheckNode(); return OI == OE; }
 265
 266     /// next - Returns the next available operand.
 267     ///
 268     inline SDOperand next() {
 269       assert(OI != OE &&
 270              "Not checking for end of NodeGroupOpIterator correctly");
 271       return *OI++;
 272     }
 273   };
 274
 275   class ScheduleDAG {
 276   public:
 277     SelectionDAG &DAG;                    // DAG of the current basic block
 278     MachineBasicBlock *BB;                // Current basic block
 279     const TargetMachine &TM;              // Target processor
 280     const TargetInstrInfo *TII;           // Target instruction information
 281     const MRegisterInfo *MRI;             // Target processor register info
 282     SSARegMap *RegMap;                    // Virtual/real register map
 283     MachineConstantPool *ConstPool;       // Target constant pool
 284
 285     ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb,
 286                 const TargetMachine &tm)
 287       : DAG(dag), BB(bb), TM(tm) {}
 288
 289     virtual ~ScheduleDAG() {}
 290
 291     /// Run - perform scheduling.
 292     ///
 293     MachineBasicBlock *Run();
 294
 295     /// isPassiveNode - Return true if the node is a non-scheduled leaf.
 296     ///
 297     static bool isPassiveNode(SDNode *Node) {
 298       if (isa<ConstantSDNode>(Node))       return true;
 299       if (isa<RegisterSDNode>(Node))       return true;
 300       if (isa<GlobalAddressSDNode>(Node))  return true;
 301       if (isa<BasicBlockSDNode>(Node))     return true;
 302       if (isa<FrameIndexSDNode>(Node))     return true;
 303       if (isa<ConstantPoolSDNode>(Node))   return true;
 304       if (isa<ExternalSymbolSDNode>(Node)) return true;
 305       return false;
 306     }
 307
 308     /// EmitNode - Generate machine code for an node and needed dependencies.
 309     /// VRBaseMap contains, for each already emitted node, the first virtual
 310     /// register number for the results of the node.
 311     ///
 312     void EmitNode(SDNode *Node, std::map<SDNode*, unsigned> &VRBaseMap);
 313
 314     /// EmitNoop - Emit a noop instruction.
 315     ///
 316     void EmitNoop();
 317
 318
 319     /// Schedule - Order nodes according to selected style.
 320     ///
 321     virtual void Schedule() {}
 322
 323   private:
 324     void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum,
 325                     const TargetInstrDescriptor *II,
 326                     std::map<SDNode*, unsigned> &VRBaseMap);
 327   };
 328
 329   ScheduleDAG *createBFS_DAGScheduler(SelectionDAG &DAG, MachineBasicBlock *BB);
 330
 331   /// createSimpleDAGScheduler - This creates a simple two pass instruction
 332   /// scheduler.
 333   ScheduleDAG* createSimpleDAGScheduler(bool NoItins, SelectionDAG &DAG,
 334                                         MachineBasicBlock *BB);
 335
 336   /// createBURRListDAGScheduler - This creates a bottom up register usage
 337   /// reduction list scheduler.
 338   ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG,
 339                                           MachineBasicBlock *BB);
 340
 341   /// createTDListDAGScheduler - This creates a top-down list scheduler with
 342   /// the specified hazard recognizer.  This takes ownership of the hazard
 343   /// recognizer and deletes it when done.
 344   ScheduleDAG* createTDListDAGScheduler(SelectionDAG &DAG,
 345                                         MachineBasicBlock *BB,
 346                                         HazardRecognizer *HR);
 347 }
 348
 349 #endif