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     SchedHeuristics Heuristic;            // Scheduling heuristic
 288     SelectionDAG &DAG;                    // DAG of the current basic block
 289     MachineBasicBlock *BB;                // Current basic block
 290     const TargetMachine &TM;              // Target processor
 291     const TargetInstrInfo *TII;           // Target instruction information
 292     const MRegisterInfo *MRI;             // Target processor register info
 293     SSARegMap *RegMap;                    // Virtual/real register map
 294     MachineConstantPool *ConstPool;       // Target constant pool
 295     std::map<SDNode *, NodeInfo *> Map;   // Map nodes to info
 296     unsigned NodeCount;                   // Number of nodes in DAG
 297     bool HasGroups;                       // True if there are any groups
 298     NodeInfo *Info;                       // Info for nodes being scheduled
 299     NIVector Ordering;                    // Emit ordering of nodes
 300     NodeGroup *HeadNG, *TailNG;           // Keep track of allocated NodeGroups
 301
 302     ScheduleDAG(SchedHeuristics hstc, SelectionDAG &dag, MachineBasicBlock *bb,
 303                 const TargetMachine &tm)
 304       : Heuristic(hstc), DAG(dag), BB(bb), TM(tm), NodeCount(0),
 305         HasGroups(false), Info(NULL), HeadNG(NULL), TailNG(NULL) {}
 306
 307     virtual ~ScheduleDAG() {
 308       if (Info)
 309         delete[] Info;
 310
 311       NodeGroup *NG = HeadNG;
 312       while (NG) {
 313         NodeGroup *NextSU = NG->Next;
 314         delete NG;
 315         NG = NextSU;
 316       }
 317     };
 318
 319     /// Run - perform scheduling.
 320     ///
 321     MachineBasicBlock *Run();
 322
 323     /// getNI - Returns the node info for the specified node.
 324     ///
 325     NodeInfo *getNI(SDNode *Node) { return Map[Node]; }
 326
 327     /// isPassiveNode - Return true if the node is a non-scheduled leaf.
 328     ///
 329     static bool isPassiveNode(SDNode *Node) {
 330       if (isa<ConstantSDNode>(Node))       return true;
 331       if (isa<RegisterSDNode>(Node))       return true;
 332       if (isa<GlobalAddressSDNode>(Node))  return true;
 333       if (isa<BasicBlockSDNode>(Node))     return true;
 334       if (isa<FrameIndexSDNode>(Node))     return true;
 335       if (isa<ConstantPoolSDNode>(Node))   return true;
 336       if (isa<ExternalSymbolSDNode>(Node)) return true;
 337       return false;
 338     }
 339
 340     /// EmitNode - Generate machine code for an node and needed dependencies.
 341     /// VRBaseMap contains, for each already emitted node, the first virtual
 342     /// register number for the results of the node.
 343     ///
 344     void EmitNode(NodeInfo *NI, std::map<SDNode*, unsigned> &VRBaseMap);
 345
 346     /// EmitNoop - Emit a noop instruction.
 347     ///
 348     void EmitNoop();
 349
 350     /// EmitAll - Emit all nodes in schedule sorted order.
 351     ///
 352     void EmitAll();
 353
 354     /// Schedule - Order nodes according to selected style.
 355     ///
 356     virtual void Schedule() {}
 357
 358     /// printNI - Print node info.
 359     ///
 360     void printNI(std::ostream &O, NodeInfo *NI) const;
 361
 362     /// printChanges - Hilight changes in order caused by scheduling.
 363     ///
 364     void printChanges(unsigned Index) const;
 365
 366     /// print - Print ordering to specified output stream.
 367     ///
 368     void print(std::ostream &O) const;
 369
 370     void dump(const char *tag) const;
 371
 372     virtual void dump() const;
 373
 374   private:
 375     void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum,
 376                     const TargetInstrDescriptor *II,
 377                     std::map<SDNode*, unsigned> &VRBaseMap);
 378
 379     void AddToGroup(NodeInfo *D, NodeInfo *U);
 380 protected:
 381     /// PrepareNodeInfo - Set up the basic minimum node info for scheduling.
 382     ///
 383     void PrepareNodeInfo();
 384
 385     /// IdentifyGroups - Put flagged nodes into groups.
 386     ///
 387     void IdentifyGroups();
 388   };
 389
 390   /// createSimpleDAGScheduler - This creates a simple two pass instruction
 391   /// scheduler.
 392   ScheduleDAG* createSimpleDAGScheduler(SchedHeuristics Heuristic,
 393                                         SelectionDAG &DAG,
 394                                         MachineBasicBlock *BB);
 395
 396   /// createBURRListDAGScheduler - This creates a bottom up register usage
 397   /// reduction list scheduler.
 398   ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG,
 399                                           MachineBasicBlock *BB);
 400
 401   /// createTDListDAGScheduler - This creates a top-down list scheduler with
 402   /// the specified hazard recognizer.  This takes ownership of the hazard
 403   /// recognizer and deletes it when done.
 404   ScheduleDAG* createTDListDAGScheduler(SelectionDAG &DAG,
 405                                         MachineBasicBlock *BB,
 406                                         HazardRecognizer *HR);
 407 }
 408
 409 #endif