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 #include "llvm/ADT/DenseMap.h"
  20 #include "llvm/ADT/GraphTraits.h"
  21 #include "llvm/ADT/SmallSet.h"
  22
  23 namespace llvm {
  24   struct InstrStage;
  25   struct SUnit;
  26   class MachineConstantPool;
  27   class MachineModuleInfo;
  28   class MachineInstr;
  29   class MRegisterInfo;
  30   class SelectionDAG;
  31   class SelectionDAGISel;
  32   class SSARegMap;
  33   class TargetInstrInfo;
  34   class TargetInstrDescriptor;
  35   class TargetMachine;
  36
  37   /// HazardRecognizer - This determines whether or not an instruction can be
  38   /// issued this cycle, and whether or not a noop needs to be inserted to handle
  39   /// the hazard.
  40   class HazardRecognizer {
  41   public:
  42     virtual ~HazardRecognizer();
  43
  44     enum HazardType {
  45       NoHazard,      // This instruction can be emitted at this cycle.
  46       Hazard,        // This instruction can't be emitted at this cycle.
  47       NoopHazard     // This instruction can't be emitted, and needs noops.
  48     };
  49
  50     /// getHazardType - Return the hazard type of emitting this node.  There are
  51     /// three possible results.  Either:
  52     ///  * NoHazard: it is legal to issue this instruction on this cycle.
  53     ///  * Hazard: issuing this instruction would stall the machine.  If some
  54     ///     other instruction is available, issue it first.
  55     ///  * NoopHazard: issuing this instruction would break the program.  If
  56     ///     some other instruction can be issued, do so, otherwise issue a noop.
  57     virtual HazardType getHazardType(SDNode *Node) {
  58       return NoHazard;
  59     }
  60
  61     /// EmitInstruction - This callback is invoked when an instruction is
  62     /// emitted, to advance the hazard state.
  63     virtual void EmitInstruction(SDNode *Node) {
  64     }
  65
  66     /// AdvanceCycle - This callback is invoked when no instructions can be
  67     /// issued on this cycle without a hazard.  This should increment the
  68     /// internal state of the hazard recognizer so that previously "Hazard"
  69     /// instructions will now not be hazards.
  70     virtual void AdvanceCycle() {
  71     }
  72
  73     /// EmitNoop - This callback is invoked when a noop was added to the
  74     /// instruction stream.
  75     virtual void EmitNoop() {
  76     }
  77   };
  78
  79   /// SDep - Scheduling dependency. It keeps track of dependent nodes,
  80   /// cost of the depdenency, etc.
  81   struct SDep {
  82     SUnit    *Dep;           // Dependent - either a predecessor or a successor.
  83     unsigned  Reg;           // If non-zero, this dep is a phy register dependency.
  84     int       Cost;          // Cost of the dependency.
  85     bool      isCtrl    : 1; // True iff it's a control dependency.
  86     bool      isSpecial : 1; // True iff it's a special ctrl dep added during sched.
  87     SDep(SUnit *d, unsigned r, int t, bool c, bool s)
  88       : Dep(d), Reg(r), Cost(t), isCtrl(c), isSpecial(s) {}
  89   };
  90
  91   /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
  92   /// a group of nodes flagged together.
  93   struct SUnit {
  94     SDNode *Node;                       // Representative node.
  95     SmallVector<SDNode*,4> FlaggedNodes;// All nodes flagged to Node.
  96     unsigned InstanceNo;                // Instance#. One SDNode can be multiple
  97                                         // SUnit due to cloning.
  98
  99     // Preds/Succs - The SUnits before/after us in the graph.  The boolean value
 100     // is true if the edge is a token chain edge, false if it is a value edge.
 101     SmallVector<SDep, 4> Preds;  // All sunit predecessors.
 102     SmallVector<SDep, 4> Succs;  // All sunit successors.
 103
 104     typedef SmallVector<SDep, 4>::iterator pred_iterator;
 105     typedef SmallVector<SDep, 4>::iterator succ_iterator;
 106     typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator;
 107     typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator;
 108
 109     unsigned NodeNum;                   // Entry # of node in the node vector.
 110     unsigned short Latency;             // Node latency.
 111     short NumPreds;                     // # of preds.
 112     short NumSuccs;                     // # of sucss.
 113     short NumPredsLeft;                 // # of preds not scheduled.
 114     short NumSuccsLeft;                 // # of succs not scheduled.
 115     short NumChainPredsLeft;            // # of chain preds not scheduled.
 116     short NumChainSuccsLeft;            // # of chain succs not scheduled.
 117     bool isTwoAddress     : 1;          // Is a two-address instruction.
 118     bool isCommutable     : 1;          // Is a commutable instruction.
 119     bool hasImplicitDefs  : 1;          // Has implicit physical reg defs.
 120     bool isPending        : 1;          // True once pending.
 121     bool isAvailable      : 1;          // True once available.
 122     bool isScheduled      : 1;          // True once scheduled.
 123     unsigned CycleBound;                // Upper/lower cycle to be scheduled at.
 124     unsigned Cycle;                     // Once scheduled, the cycle of the op.
 125     unsigned Depth;                     // Node depth;
 126     unsigned Height;                    // Node height;
 127
 128     SUnit(SDNode *node, unsigned nodenum)
 129       : Node(node), InstanceNo(0), NodeNum(nodenum), Latency(0),
 130         NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
 131         NumChainPredsLeft(0), NumChainSuccsLeft(0),
 132         isTwoAddress(false), isCommutable(false), hasImplicitDefs(false),
 133         isPending(false), isAvailable(false), isScheduled(false),
 134         CycleBound(0), Cycle(0), Depth(0), Height(0) {}
 135
 136     /// addPred - This adds the specified node as a pred of the current node if
 137     /// not already.  This returns true if this is a new pred.
 138     bool addPred(SUnit *N, bool isCtrl, bool isSpecial,
 139                  unsigned PhyReg = 0, int Cost = 1) {
 140       for (unsigned i = 0, e = Preds.size(); i != e; ++i)
 141         if (Preds[i].Dep == N &&
 142             Preds[i].isCtrl == isCtrl && Preds[i].isSpecial == isSpecial)
 143           return false;
 144       Preds.push_back(SDep(N, PhyReg, Cost, isCtrl, isSpecial));
 145       N->Succs.push_back(SDep(this, PhyReg, Cost, isCtrl, isSpecial));
 146       if (isCtrl) {
 147         if (!N->isScheduled)
 148           ++NumChainPredsLeft;
 149         if (!isScheduled)
 150           ++N->NumChainSuccsLeft;
 151       } else {
 152         ++NumPreds;
 153         ++N->NumSuccs;
 154         if (!N->isScheduled)
 155           ++NumPredsLeft;
 156         if (!isScheduled)
 157           ++N->NumSuccsLeft;
 158       }
 159       return true;
 160     }
 161
 162     bool removePred(SUnit *N, bool isCtrl, bool isSpecial) {
 163       for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end();
 164            I != E; ++I)
 165         if (I->Dep == N && I->isCtrl == isCtrl && I->isSpecial == isSpecial) {
 166           bool FoundSucc = false;
 167           for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(),
 168                  EE = N->Succs.end(); II != EE; ++II)
 169             if (II->Dep == this &&
 170                 II->isCtrl == isCtrl && II->isSpecial == isSpecial) {
 171               FoundSucc = true;
 172               N->Succs.erase(II);
 173               break;
 174             }
 175           assert(FoundSucc && "Mismatching preds / succs lists!");
 176           Preds.erase(I);
 177           if (isCtrl) {
 178             if (!N->isScheduled)
 179               --NumChainPredsLeft;
 180             if (!isScheduled)
 181               --NumChainSuccsLeft;
 182           } else {
 183             --NumPreds;
 184             --N->NumSuccs;
 185             if (!N->isScheduled)
 186               --NumPredsLeft;
 187             if (!isScheduled)
 188               --N->NumSuccsLeft;
 189           }
 190           return true;
 191         }
 192       return false;
 193     }
 194
 195     bool isPred(SUnit *N) {
 196       for (unsigned i = 0, e = Preds.size(); i != e; ++i)
 197         if (Preds[i].Dep == N)
 198           return true;
 199       return false;
 200     }
 201
 202     bool isSucc(SUnit *N) {
 203       for (unsigned i = 0, e = Succs.size(); i != e; ++i)
 204         if (Succs[i].Dep == N)
 205           return true;
 206       return false;
 207     }
 208
 209     void dump(const SelectionDAG *G) const;
 210     void dumpAll(const SelectionDAG *G) const;
 211   };
 212
 213   //===--------------------------------------------------------------------===//
 214   /// SchedulingPriorityQueue - This interface is used to plug different
 215   /// priorities computation algorithms into the list scheduler. It implements
 216   /// the interface of a standard priority queue, where nodes are inserted in
 217   /// arbitrary order and returned in priority order.  The computation of the
 218   /// priority and the representation of the queue are totally up to the
 219   /// implementation to decide.
 220   ///
 221   class SchedulingPriorityQueue {
 222   public:
 223     virtual ~SchedulingPriorityQueue() {}
 224
 225     virtual void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &SUMap,
 226                            std::vector<SUnit> &SUnits) = 0;
 227     virtual void addNode(const SUnit *SU) = 0;
 228     virtual void updateNode(const SUnit *SU) = 0;
 229     virtual void releaseState() = 0;
 230
 231     virtual unsigned size() const = 0;
 232     virtual bool empty() const = 0;
 233     virtual void push(SUnit *U) = 0;
 234
 235     virtual void push_all(const std::vector<SUnit *> &Nodes) = 0;
 236     virtual SUnit *pop() = 0;
 237
 238     virtual void remove(SUnit *SU) = 0;
 239
 240     /// ScheduledNode - As each node is scheduled, this method is invoked.  This
 241     /// allows the priority function to adjust the priority of node that have
 242     /// already been emitted.
 243     virtual void ScheduledNode(SUnit *Node) {}
 244
 245     virtual void UnscheduledNode(SUnit *Node) {}
 246   };
 247
 248   class ScheduleDAG {
 249   public:
 250     SelectionDAG &DAG;                    // DAG of the current basic block
 251     MachineBasicBlock *BB;                // Current basic block
 252     const TargetMachine &TM;              // Target processor
 253     const TargetInstrInfo *TII;           // Target instruction information
 254     const MRegisterInfo *MRI;             // Target processor register info
 255     SSARegMap *RegMap;                    // Virtual/real register map
 256     MachineConstantPool *ConstPool;       // Target constant pool
 257     std::vector<SUnit*> Sequence;         // The schedule. Null SUnit*'s
 258                                           // represent noop instructions.
 259     DenseMap<SDNode*, std::vector<SUnit*> > SUnitMap;
 260                                           // SDNode to SUnit mapping (n -> n).
 261     std::vector<SUnit> SUnits;            // The scheduling units.
 262     SmallSet<SDNode*, 16> CommuteSet;     // Nodes the should be commuted.
 263
 264     ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb,
 265                 const TargetMachine &tm)
 266       : DAG(dag), BB(bb), TM(tm) {}
 267
 268     virtual ~ScheduleDAG() {}
 269
 270     /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered
 271     /// using 'dot'.
 272     ///
 273     void viewGraph();
 274
 275     /// Run - perform scheduling.
 276     ///
 277     MachineBasicBlock *Run();
 278
 279     /// isPassiveNode - Return true if the node is a non-scheduled leaf.
 280     ///
 281     static bool isPassiveNode(SDNode *Node) {
 282       if (isa<ConstantSDNode>(Node))       return true;
 283       if (isa<RegisterSDNode>(Node))       return true;
 284       if (isa<GlobalAddressSDNode>(Node))  return true;
 285       if (isa<BasicBlockSDNode>(Node))     return true;
 286       if (isa<FrameIndexSDNode>(Node))     return true;
 287       if (isa<ConstantPoolSDNode>(Node))   return true;
 288       if (isa<JumpTableSDNode>(Node))      return true;
 289       if (isa<ExternalSymbolSDNode>(Node)) return true;
 290       return false;
 291     }
 292
 293     /// NewSUnit - Creates a new SUnit and return a ptr to it.
 294     ///
 295     SUnit *NewSUnit(SDNode *N) {
 296       SUnits.push_back(SUnit(N, SUnits.size()));
 297       return &SUnits.back();
 298     }
 299
 300     /// Clone - Creates a clone of the specified SUnit. It does not copy the
 301     /// predecessors / successors info nor the temporary scheduling states.
 302     SUnit *Clone(SUnit *N);
 303
 304     /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
 305     /// This SUnit graph is similar to the SelectionDAG, but represents flagged
 306     /// together nodes with a single SUnit.
 307     void BuildSchedUnits();
 308
 309     /// CalculateDepths, CalculateHeights - Calculate node depth / height.
 310     ///
 311     void CalculateDepths();
 312     void CalculateHeights();
 313
 314     /// CountResults - The results of target nodes have register or immediate
 315     /// operands first, then an optional chain, and optional flag operands
 316     /// (which do not go into the machine instrs.)
 317     static unsigned CountResults(SDNode *Node);
 318
 319     /// CountOperands  The inputs to target nodes have any actual inputs first,
 320     /// followed by an optional chain operand, then flag operands.  Compute the
 321     /// number of actual operands that  will go into the machine instr.
 322     static unsigned CountOperands(SDNode *Node);
 323
 324     /// EmitNode - Generate machine code for an node and needed dependencies.
 325     /// VRBaseMap contains, for each already emitted node, the first virtual
 326     /// register number for the results of the node.
 327     ///
 328     void EmitNode(SDNode *Node, unsigned InstNo,
 329                   DenseMap<SDOperand, unsigned> &VRBaseMap);
 330
 331     /// EmitNoop - Emit a noop instruction.
 332     ///
 333     void EmitNoop();
 334
 335     /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an
 336     /// implicit physical register output.
 337     void EmitCopyFromReg(SDNode *Node, unsigned ResNo, unsigned InstNo,
 338                          unsigned SrcReg,
 339                          DenseMap<SDOperand, unsigned> &VRBaseMap);
 340
 341     void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
 342                                 const TargetInstrDescriptor &II,
 343                                 DenseMap<SDOperand, unsigned> &VRBaseMap);
 344
 345     void EmitSchedule();
 346
 347     void dumpSchedule() const;
 348
 349     /// Schedule - Order nodes according to selected style.
 350     ///
 351     virtual void Schedule() {}
 352
 353   private:
 354     /// EmitSubregNode - Generate machine code for subreg nodes.
 355     ///
 356     void EmitSubregNode(SDNode *Node,
 357                         DenseMap<SDOperand, unsigned> &VRBaseMap);
 358
 359     void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum,
 360                     const TargetInstrDescriptor *II,
 361                     DenseMap<SDOperand, unsigned> &VRBaseMap);
 362   };
 363
 364   /// createBFS_DAGScheduler - This creates a simple breadth first instruction
 365   /// scheduler.
 366   ScheduleDAG *createBFS_DAGScheduler(SelectionDAGISel *IS,
 367                                       SelectionDAG *DAG,
 368                                       MachineBasicBlock *BB);
 369
 370   /// createSimpleDAGScheduler - This creates a simple two pass instruction
 371   /// scheduler using instruction itinerary.
 372   ScheduleDAG* createSimpleDAGScheduler(SelectionDAGISel *IS,
 373                                         SelectionDAG *DAG,
 374                                         MachineBasicBlock *BB);
 375
 376   /// createNoItinsDAGScheduler - This creates a simple two pass instruction
 377   /// scheduler without using instruction itinerary.
 378   ScheduleDAG* createNoItinsDAGScheduler(SelectionDAGISel *IS,
 379                                          SelectionDAG *DAG,
 380                                          MachineBasicBlock *BB);
 381
 382   /// createBURRListDAGScheduler - This creates a bottom up register usage
 383   /// reduction list scheduler.
 384   ScheduleDAG* createBURRListDAGScheduler(SelectionDAGISel *IS,
 385                                           SelectionDAG *DAG,
 386                                           MachineBasicBlock *BB);
 387
 388   /// createTDRRListDAGScheduler - This creates a top down register usage
 389   /// reduction list scheduler.
 390   ScheduleDAG* createTDRRListDAGScheduler(SelectionDAGISel *IS,
 391                                           SelectionDAG *DAG,
 392                                           MachineBasicBlock *BB);
 393
 394   /// createTDListDAGScheduler - This creates a top-down list scheduler with
 395   /// a hazard recognizer.
 396   ScheduleDAG* createTDListDAGScheduler(SelectionDAGISel *IS,
 397                                         SelectionDAG *DAG,
 398                                         MachineBasicBlock *BB);
 399
 400   /// createDefaultScheduler - This creates an instruction scheduler appropriate
 401   /// for the target.
 402   ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS,
 403                                       SelectionDAG *DAG,
 404                                       MachineBasicBlock *BB);
 405
 406   class SUnitIterator : public forward_iterator<SUnit, ptrdiff_t> {
 407     SUnit *Node;
 408     unsigned Operand;
 409
 410     SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
 411   public:
 412     bool operator==(const SUnitIterator& x) const {
 413       return Operand == x.Operand;
 414     }
 415     bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
 416
 417     const SUnitIterator &operator=(const SUnitIterator &I) {
 418       assert(I.Node == Node && "Cannot assign iterators to two different nodes!");
 419       Operand = I.Operand;
 420       return *this;
 421     }
 422
 423     pointer operator*() const {
 424       return Node->Preds[Operand].Dep;
 425     }
 426     pointer operator->() const { return operator*(); }
 427
 428     SUnitIterator& operator++() {                // Preincrement
 429       ++Operand;
 430       return *this;
 431     }
 432     SUnitIterator operator++(int) { // Postincrement
 433       SUnitIterator tmp = *this; ++*this; return tmp;
 434     }
 435
 436     static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
 437     static SUnitIterator end  (SUnit *N) {
 438       return SUnitIterator(N, N->Preds.size());
 439     }
 440
 441     unsigned getOperand() const { return Operand; }
 442     const SUnit *getNode() const { return Node; }
 443     bool isCtrlDep() const { return Node->Preds[Operand].isCtrl; }
 444   };
 445
 446   template <> struct GraphTraits<SUnit*> {
 447     typedef SUnit NodeType;
 448     typedef SUnitIterator ChildIteratorType;
 449     static inline NodeType *getEntryNode(SUnit *N) { return N; }
 450     static inline ChildIteratorType child_begin(NodeType *N) {
 451       return SUnitIterator::begin(N);
 452     }
 453     static inline ChildIteratorType child_end(NodeType *N) {
 454       return SUnitIterator::end(N);
 455     }
 456   };
 457
 458   template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
 459     typedef std::vector<SUnit>::iterator nodes_iterator;
 460     static nodes_iterator nodes_begin(ScheduleDAG *G) {
 461       return G->SUnits.begin();
 462     }
 463     static nodes_iterator nodes_end(ScheduleDAG *G) {
 464       return G->SUnits.end();
 465     }
 466   };
 467 }
 468
 469 #endif