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