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