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     unsigned      VRBase;                 // Virtual register base
 155 #ifndef NDEBUG
 156     unsigned      Preorder;               // Index before scheduling
 157 #endif
 158
 159     // Ctor.
 160     NodeInfo(SDNode *N = NULL)
 161       : Pending(0)
 162       , Node(N)
 163       , StageBegin(NULL)
 164       , StageEnd(NULL)
 165       , Latency(0)
 166       , IsCall(false)
 167       , Slot(0)
 168       , Group(NULL)
 169       , VRBase(0)
 170 #ifndef NDEBUG
 171       , Preorder(0)
 172 #endif
 173     {}
 174
 175     // Accessors
 176     inline bool isInGroup() const {
 177       assert(!Group || !Group->group_empty() && "Group with no members");
 178       return Group != NULL;
 179     }
 180     inline bool isGroupDominator() const {
 181       return isInGroup() && Group->getDominator() == this;
 182     }
 183     inline int getPending() const {
 184       return Group ? Group->getPending() : Pending;
 185     }
 186     inline void setPending(int P) {
 187       if (Group) Group->setPending(P);
 188       else       Pending = P;
 189     }
 190     inline int addPending(int I) {
 191       if (Group) return Group->addPending(I);
 192       else       return Pending += I;
 193     }
 194   };
 195
 196   //===--------------------------------------------------------------------===//
 197   ///
 198   /// NodeGroupIterator - Iterates over all the nodes indicated by the node
 199   /// info. If the node is in a group then iterate over the members of the
 200   /// group, otherwise just the node info.
 201   ///
 202   class NodeGroupIterator {
 203   private:
 204     NodeInfo   *NI;                       // Node info
 205     NIIterator NGI;                       // Node group iterator
 206     NIIterator NGE;                       // Node group iterator end
 207
 208   public:
 209     // Ctor.
 210     NodeGroupIterator(NodeInfo *N) : NI(N) {
 211       // If the node is in a group then set up the group iterator.  Otherwise
 212       // the group iterators will trip first time out.
 213       if (N->isInGroup()) {
 214         // get Group
 215         NodeGroup *Group = NI->Group;
 216         NGI = Group->group_begin();
 217         NGE = Group->group_end();
 218         // Prevent this node from being used (will be in members list
 219         NI = NULL;
 220       }
 221     }
 222
 223     /// next - Return the next node info, otherwise NULL.
 224     ///
 225     NodeInfo *next() {
 226       // If members list
 227       if (NGI != NGE) return *NGI++;
 228       // Use node as the result (may be NULL)
 229       NodeInfo *Result = NI;
 230       // Only use once
 231       NI = NULL;
 232       // Return node or NULL
 233       return Result;
 234     }
 235   };
 236   //===--------------------------------------------------------------------===//
 237
 238
 239   //===--------------------------------------------------------------------===//
 240   ///
 241   /// NodeGroupOpIterator - Iterates over all the operands of a node.  If the
 242   /// node is a member of a group, this iterates over all the operands of all
 243   /// the members of the group.
 244   ///
 245   class NodeGroupOpIterator {
 246   private:
 247     NodeInfo            *NI;              // Node containing operands
 248     NodeGroupIterator   GI;               // Node group iterator
 249     SDNode::op_iterator OI;               // Operand iterator
 250     SDNode::op_iterator OE;               // Operand iterator end
 251
 252     /// CheckNode - Test if node has more operands.  If not get the next node
 253     /// skipping over nodes that have no operands.
 254     void CheckNode() {
 255       // Only if operands are exhausted first
 256       while (OI == OE) {
 257         // Get next node info
 258         NodeInfo *NI = GI.next();
 259         // Exit if nodes are exhausted
 260         if (!NI) return;
 261         // Get node itself
 262         SDNode *Node = NI->Node;
 263         // Set up the operand iterators
 264         OI = Node->op_begin();
 265         OE = Node->op_end();
 266       }
 267     }
 268
 269   public:
 270     // Ctor.
 271     NodeGroupOpIterator(NodeInfo *N)
 272       : NI(N), GI(N), OI(SDNode::op_iterator()), OE(SDNode::op_iterator()) {}
 273
 274     /// isEnd - Returns true when not more operands are available.
 275     ///
 276     inline bool isEnd() { CheckNode(); return OI == OE; }
 277
 278     /// next - Returns the next available operand.
 279     ///
 280     inline SDOperand next() {
 281       assert(OI != OE &&
 282              "Not checking for end of NodeGroupOpIterator correctly");
 283       return *OI++;
 284     }
 285   };
 286
 287   class ScheduleDAG {
 288   public:
 289     SchedHeuristics Heuristic;            // Scheduling heuristic
 290     SelectionDAG &DAG;                    // DAG of the current basic block
 291     MachineBasicBlock *BB;                // Current basic block
 292     const TargetMachine &TM;              // Target processor
 293     const TargetInstrInfo *TII;           // Target instruction information
 294     const MRegisterInfo *MRI;             // Target processor register info
 295     SSARegMap *RegMap;                    // Virtual/real register map
 296     MachineConstantPool *ConstPool;       // Target constant pool
 297     std::map<SDNode *, NodeInfo *> Map;   // Map nodes to info
 298     unsigned NodeCount;                   // Number of nodes in DAG
 299     bool HasGroups;                       // True if there are any groups
 300     NodeInfo *Info;                       // Info for nodes being scheduled
 301     NIVector Ordering;                    // Emit ordering of nodes
 302     NodeGroup *HeadNG, *TailNG;           // Keep track of allocated NodeGroups
 303
 304     ScheduleDAG(SchedHeuristics hstc, SelectionDAG &dag, MachineBasicBlock *bb,
 305                 const TargetMachine &tm)
 306       : Heuristic(hstc), DAG(dag), BB(bb), TM(tm), NodeCount(0),
 307         HasGroups(false), Info(NULL), HeadNG(NULL), TailNG(NULL) {}
 308
 309     virtual ~ScheduleDAG() {
 310       if (Info)
 311         delete[] Info;
 312
 313       NodeGroup *NG = HeadNG;
 314       while (NG) {
 315         NodeGroup *NextSU = NG->Next;
 316         delete NG;
 317         NG = NextSU;
 318       }
 319     };
 320
 321     /// Run - perform scheduling.
 322     ///
 323     MachineBasicBlock *Run();
 324
 325     /// getNI - Returns the node info for the specified node.
 326     ///
 327     NodeInfo *getNI(SDNode *Node) { return Map[Node]; }
 328
 329     /// getVR - Returns the virtual register number of the node.
 330     ///
 331     unsigned getVR(SDOperand Op) {
 332       NodeInfo *NI = getNI(Op.Val);
 333       assert(NI->VRBase != 0 && "Node emitted out of order - late");
 334       return NI->VRBase + Op.ResNo;
 335     }
 336
 337     /// isPassiveNode - Return true if the node is a non-scheduled leaf.
 338     ///
 339     static bool isPassiveNode(SDNode *Node) {
 340       if (isa<ConstantSDNode>(Node))       return true;
 341       if (isa<RegisterSDNode>(Node))       return true;
 342       if (isa<GlobalAddressSDNode>(Node))  return true;
 343       if (isa<BasicBlockSDNode>(Node))     return true;
 344       if (isa<FrameIndexSDNode>(Node))     return true;
 345       if (isa<ConstantPoolSDNode>(Node))   return true;
 346       if (isa<ExternalSymbolSDNode>(Node)) return true;
 347       return false;
 348     }
 349
 350     /// EmitNode - Generate machine code for an node and needed dependencies.
 351     ///
 352     void EmitNode(NodeInfo *NI);
 353
 354     /// EmitNoop - Emit a noop instruction.
 355     ///
 356     void EmitNoop();
 357
 358     /// EmitAll - Emit all nodes in schedule sorted order.
 359     ///
 360     void EmitAll();
 361
 362     /// Schedule - Order nodes according to selected style.
 363     ///
 364     virtual void Schedule() {}
 365
 366     /// printNI - Print node info.
 367     ///
 368     void printNI(std::ostream &O, NodeInfo *NI) const;
 369
 370     /// printChanges - Hilight changes in order caused by scheduling.
 371     ///
 372     void printChanges(unsigned Index) const;
 373
 374     /// print - Print ordering to specified output stream.
 375     ///
 376     void print(std::ostream &O) const;
 377
 378     void dump(const char *tag) const;
 379
 380     virtual void dump() const;
 381
 382   private:
 383     void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum,
 384                     const TargetInstrDescriptor *II);
 385
 386     /// PrepareNodeInfo - Set up the basic minimum node info for scheduling.
 387     ///
 388     void PrepareNodeInfo();
 389
 390     /// IdentifyGroups - Put flagged nodes into groups.
 391     ///
 392     void IdentifyGroups();
 393
 394     void AddToGroup(NodeInfo *D, NodeInfo *U);
 395   };
 396
 397   /// createSimpleDAGScheduler - This creates a simple two pass instruction
 398   /// scheduler.
 399   ScheduleDAG* createSimpleDAGScheduler(SchedHeuristics Heuristic,
 400                                         SelectionDAG &DAG,
 401                                         MachineBasicBlock *BB);
 402
 403   /// createBURRListDAGScheduler - This creates a bottom up register usage
 404   /// reduction list scheduler.
 405   ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG,
 406                                           MachineBasicBlock *BB);
 407
 408   /// createTDListDAGScheduler - This creates a top-down list scheduler with
 409   /// the specified hazard recognizer.  This takes ownership of the hazard
 410   /// recognizer and deletes it when done.
 411   ScheduleDAG* createTDListDAGScheduler(SelectionDAG &DAG,
 412                                         MachineBasicBlock *BB,
 413                                         HazardRecognizer *HR);
 414 }
 415
 416 #endif