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