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