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     /// StartBasicBlock - This is called when a new basic block is started.
  61     ///
  62     virtual void StartBasicBlock() {}
  63
  64     /// getHazardType - Return the hazard type of emitting this node.  There are
  65     /// three possible results.  Either:
  66     ///  * NoHazard: it is legal to issue this instruction on this cycle.
  67     ///  * Hazard: issuing this instruction would stall the machine.  If some
  68     ///     other instruction is available, issue it first.
  69     ///  * NoopHazard: issuing this instruction would break the program.  If
  70     ///     some other instruction can be issued, do so, otherwise issue a noop.
  71     virtual HazardType getHazardType(SDNode *Node) {
  72       return NoHazard;
  73     }
  74
  75     /// EmitInstruction - This callback is invoked when an instruction is
  76     /// emitted, to advance the hazard state.
  77     virtual void EmitInstruction(SDNode *Node) {
  78     }
  79
  80     /// AdvanceCycle - This callback is invoked when no instructions can be
  81     /// issued on this cycle without a hazard.  This should increment the
  82     /// internal state of the hazard recognizer so that previously "Hazard"
  83     /// instructions will now not be hazards.
  84     virtual void AdvanceCycle() {
  85     }
  86
  87     /// EmitNoop - This callback is invoked when a noop was added to the
  88     /// instruction stream.
  89     virtual void EmitNoop() {
  90     }
  91   };
  92
  93   //===--------------------------------------------------------------------===//
  94   ///
  95   /// Node group -  This struct is used to manage flagged node groups.
  96   ///
  97   class NodeGroup {
  98   public:
  99     NodeGroup     *Next;
 100   private:
 101     NIVector      Members;                // Group member nodes
 102     NodeInfo      *Dominator;             // Node with highest latency
 103     unsigned      Latency;                // Total latency of the group
 104     int           Pending;                // Number of visits pending before
 105                                           // adding to order
 106
 107   public:
 108     // Ctor.
 109     NodeGroup() : Next(NULL), Dominator(NULL), Pending(0) {}
 110
 111     // Accessors
 112     inline void setDominator(NodeInfo *D) { Dominator = D; }
 113     inline NodeInfo *getTop() { return Members.front(); }
 114     inline NodeInfo *getBottom() { return Members.back(); }
 115     inline NodeInfo *getDominator() { return Dominator; }
 116     inline void setLatency(unsigned L) { Latency = L; }
 117     inline unsigned getLatency() { return Latency; }
 118     inline int getPending() const { return Pending; }
 119     inline void setPending(int P)  { Pending = P; }
 120     inline int addPending(int I)  { return Pending += I; }
 121
 122     // Pass thru
 123     inline bool group_empty() { return Members.empty(); }
 124     inline NIIterator group_begin() { return Members.begin(); }
 125     inline NIIterator group_end() { return Members.end(); }
 126     inline void group_push_back(const NodeInfoPtr &NI) {
 127       Members.push_back(NI);
 128     }
 129     inline NIIterator group_insert(NIIterator Pos, const NodeInfoPtr &NI) {
 130       return Members.insert(Pos, NI);
 131     }
 132     inline void group_insert(NIIterator Pos, NIIterator First,
 133                              NIIterator Last) {
 134       Members.insert(Pos, First, Last);
 135     }
 136
 137     static void Add(NodeInfo *D, NodeInfo *U);
 138   };
 139
 140   //===--------------------------------------------------------------------===//
 141   ///
 142   /// NodeInfo - This struct tracks information used to schedule the a node.
 143   ///
 144   class NodeInfo {
 145   private:
 146     int           Pending;                // Number of visits pending before
 147                                           // adding to order
 148   public:
 149     SDNode        *Node;                  // DAG node
 150     InstrStage    *StageBegin;            // First stage in itinerary
 151     InstrStage    *StageEnd;              // Last+1 stage in itinerary
 152     unsigned      Latency;                // Total cycles to complete instr
 153     bool          IsCall : 1;             // Is function call
 154     bool          IsLoad : 1;             // Is memory load
 155     bool          IsStore : 1;            // Is memory store
 156     unsigned      Slot;                   // Node's time slot
 157     NodeGroup     *Group;                 // Grouping information
 158     unsigned      VRBase;                 // Virtual register base
 159 #ifndef NDEBUG
 160     unsigned      Preorder;               // Index before scheduling
 161 #endif
 162
 163     // Ctor.
 164     NodeInfo(SDNode *N = NULL)
 165       : Pending(0)
 166       , Node(N)
 167       , StageBegin(NULL)
 168       , StageEnd(NULL)
 169       , Latency(0)
 170       , IsCall(false)
 171       , Slot(0)
 172       , Group(NULL)
 173       , VRBase(0)
 174 #ifndef NDEBUG
 175       , Preorder(0)
 176 #endif
 177     {}
 178
 179     // Accessors
 180     inline bool isInGroup() const {
 181       assert(!Group || !Group->group_empty() && "Group with no members");
 182       return Group != NULL;
 183     }
 184     inline bool isGroupDominator() const {
 185       return isInGroup() && Group->getDominator() == this;
 186     }
 187     inline int getPending() const {
 188       return Group ? Group->getPending() : Pending;
 189     }
 190     inline void setPending(int P) {
 191       if (Group) Group->setPending(P);
 192       else       Pending = P;
 193     }
 194     inline int addPending(int I) {
 195       if (Group) return Group->addPending(I);
 196       else       return Pending += I;
 197     }
 198   };
 199
 200   //===--------------------------------------------------------------------===//
 201   ///
 202   /// NodeGroupIterator - Iterates over all the nodes indicated by the node
 203   /// info. If the node is in a group then iterate over the members of the
 204   /// group, otherwise just the node info.
 205   ///
 206   class NodeGroupIterator {
 207   private:
 208     NodeInfo   *NI;                       // Node info
 209     NIIterator NGI;                       // Node group iterator
 210     NIIterator NGE;                       // Node group iterator end
 211
 212   public:
 213     // Ctor.
 214     NodeGroupIterator(NodeInfo *N) : NI(N) {
 215       // If the node is in a group then set up the group iterator.  Otherwise
 216       // the group iterators will trip first time out.
 217       if (N->isInGroup()) {
 218         // get Group
 219         NodeGroup *Group = NI->Group;
 220         NGI = Group->group_begin();
 221         NGE = Group->group_end();
 222         // Prevent this node from being used (will be in members list
 223         NI = NULL;
 224       }
 225     }
 226
 227     /// next - Return the next node info, otherwise NULL.
 228     ///
 229     NodeInfo *next() {
 230       // If members list
 231       if (NGI != NGE) return *NGI++;
 232       // Use node as the result (may be NULL)
 233       NodeInfo *Result = NI;
 234       // Only use once
 235       NI = NULL;
 236       // Return node or NULL
 237       return Result;
 238     }
 239   };
 240   //===--------------------------------------------------------------------===//
 241
 242
 243   //===--------------------------------------------------------------------===//
 244   ///
 245   /// NodeGroupOpIterator - Iterates over all the operands of a node.  If the
 246   /// node is a member of a group, this iterates over all the operands of all
 247   /// the members of the group.
 248   ///
 249   class NodeGroupOpIterator {
 250   private:
 251     NodeInfo            *NI;              // Node containing operands
 252     NodeGroupIterator   GI;               // Node group iterator
 253     SDNode::op_iterator OI;               // Operand iterator
 254     SDNode::op_iterator OE;               // Operand iterator end
 255
 256     /// CheckNode - Test if node has more operands.  If not get the next node
 257     /// skipping over nodes that have no operands.
 258     void CheckNode() {
 259       // Only if operands are exhausted first
 260       while (OI == OE) {
 261         // Get next node info
 262         NodeInfo *NI = GI.next();
 263         // Exit if nodes are exhausted
 264         if (!NI) return;
 265         // Get node itself
 266         SDNode *Node = NI->Node;
 267         // Set up the operand iterators
 268         OI = Node->op_begin();
 269         OE = Node->op_end();
 270       }
 271     }
 272
 273   public:
 274     // Ctor.
 275     NodeGroupOpIterator(NodeInfo *N)
 276       : NI(N), GI(N), OI(SDNode::op_iterator()), OE(SDNode::op_iterator()) {}
 277
 278     /// isEnd - Returns true when not more operands are available.
 279     ///
 280     inline bool isEnd() { CheckNode(); return OI == OE; }
 281
 282     /// next - Returns the next available operand.
 283     ///
 284     inline SDOperand next() {
 285       assert(OI != OE &&
 286              "Not checking for end of NodeGroupOpIterator correctly");
 287       return *OI++;
 288     }
 289   };
 290
 291   class ScheduleDAG {
 292   public:
 293     SchedHeuristics Heuristic;            // Scheduling heuristic
 294     SelectionDAG &DAG;                    // DAG of the current basic block
 295     MachineBasicBlock *BB;                // Current basic block
 296     const TargetMachine &TM;              // Target processor
 297     const TargetInstrInfo *TII;           // Target instruction information
 298     const MRegisterInfo *MRI;             // Target processor register info
 299     SSARegMap *RegMap;                    // Virtual/real register map
 300     MachineConstantPool *ConstPool;       // Target constant pool
 301     std::map<SDNode *, NodeInfo *> Map;   // Map nodes to info
 302     unsigned NodeCount;                   // Number of nodes in DAG
 303     bool HasGroups;                       // True if there are any groups
 304     NodeInfo *Info;                       // Info for nodes being scheduled
 305     NIVector Ordering;                    // Emit ordering of nodes
 306     NodeGroup *HeadNG, *TailNG;           // Keep track of allocated NodeGroups
 307
 308     ScheduleDAG(SchedHeuristics hstc, SelectionDAG &dag, MachineBasicBlock *bb,
 309                 const TargetMachine &tm)
 310       : Heuristic(hstc), DAG(dag), BB(bb), TM(tm), NodeCount(0),
 311         HasGroups(false), Info(NULL), HeadNG(NULL), TailNG(NULL) {}
 312
 313     virtual ~ScheduleDAG() {
 314       if (Info)
 315         delete[] Info;
 316
 317       NodeGroup *NG = HeadNG;
 318       while (NG) {
 319         NodeGroup *NextSU = NG->Next;
 320         delete NG;
 321         NG = NextSU;
 322       }
 323     };
 324
 325     /// Run - perform scheduling.
 326     ///
 327     MachineBasicBlock *Run();
 328
 329     /// getNI - Returns the node info for the specified node.
 330     ///
 331     NodeInfo *getNI(SDNode *Node) { return Map[Node]; }
 332
 333     /// getVR - Returns the virtual register number of the node.
 334     ///
 335     unsigned getVR(SDOperand Op) {
 336       NodeInfo *NI = getNI(Op.Val);
 337       assert(NI->VRBase != 0 && "Node emitted out of order - late");
 338       return NI->VRBase + Op.ResNo;
 339     }
 340
 341     /// isPassiveNode - Return true if the node is a non-scheduled leaf.
 342     ///
 343     static bool isPassiveNode(SDNode *Node) {
 344       if (isa<ConstantSDNode>(Node))       return true;
 345       if (isa<RegisterSDNode>(Node))       return true;
 346       if (isa<GlobalAddressSDNode>(Node))  return true;
 347       if (isa<BasicBlockSDNode>(Node))     return true;
 348       if (isa<FrameIndexSDNode>(Node))     return true;
 349       if (isa<ConstantPoolSDNode>(Node))   return true;
 350       if (isa<ExternalSymbolSDNode>(Node)) return true;
 351       return false;
 352     }
 353
 354     /// EmitNode - Generate machine code for an node and needed dependencies.
 355     ///
 356     void EmitNode(NodeInfo *NI);
 357
 358     /// EmitNoop - Emit a noop instruction.
 359     ///
 360     void EmitNoop();
 361
 362     /// EmitAll - Emit all nodes in schedule sorted order.
 363     ///
 364     void EmitAll();
 365
 366     /// Schedule - Order nodes according to selected style.
 367     ///
 368     virtual void Schedule() {}
 369
 370     /// printNI - Print node info.
 371     ///
 372     void printNI(std::ostream &O, NodeInfo *NI) const;
 373
 374     /// printChanges - Hilight changes in order caused by scheduling.
 375     ///
 376     void printChanges(unsigned Index) const;
 377
 378     /// print - Print ordering to specified output stream.
 379     ///
 380     void print(std::ostream &O) const;
 381
 382     void dump(const char *tag) const;
 383
 384     virtual void dump() const;
 385
 386   private:
 387     void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum,
 388                     const TargetInstrDescriptor *II);
 389
 390     /// PrepareNodeInfo - Set up the basic minimum node info for scheduling.
 391     ///
 392     void PrepareNodeInfo();
 393
 394     /// IdentifyGroups - Put flagged nodes into groups.
 395     ///
 396     void IdentifyGroups();
 397
 398     void AddToGroup(NodeInfo *D, NodeInfo *U);
 399   };
 400
 401   /// createSimpleDAGScheduler - This creates a simple two pass instruction
 402   /// scheduler.
 403   ScheduleDAG* createSimpleDAGScheduler(SchedHeuristics Heuristic,
 404                                         SelectionDAG &DAG,
 405                                         MachineBasicBlock *BB);
 406
 407   /// createBURRListDAGScheduler - This creates a bottom up register usage
 408   /// reduction list scheduler.
 409   ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG,
 410                                           MachineBasicBlock *BB);
 411
 412   /// createTDListDAGScheduler - This creates a top-down list scheduler with
 413   /// the specified hazard recognizer.
 414   ScheduleDAG* createTDListDAGScheduler(SelectionDAG &DAG,
 415                                         MachineBasicBlock *BB,
 416                                         HazardRecognizer &HR);
 417 }
 418
 419 #endif