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