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