include/llvm/CodeGen/ScheduleDAG.h

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