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 instruction schedulers.
  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/ADT/DenseMap.h"
  20 #include "llvm/ADT/GraphTraits.h"
  21 #include "llvm/ADT/SmallVector.h"
  22
  23 namespace llvm {
  24   struct SUnit;
  25   class MachineConstantPool;
  26   class MachineFunction;
  27   class MachineModuleInfo;
  28   class MachineRegisterInfo;
  29   class MachineInstr;
  30   class TargetRegisterInfo;
  31   class ScheduleDAG;
  32   class SelectionDAG;
  33   class SDNode;
  34   class TargetInstrInfo;
  35   class TargetInstrDesc;
  36   class TargetLowering;
  37   class TargetMachine;
  38   class TargetRegisterClass;
  39   template<class Graph> class GraphWriter;
  40
  41   /// SDep - Scheduling dependency. It keeps track of dependent nodes,
  42   /// cost of the depdenency, etc.
  43   struct SDep {
  44     SUnit    *Dep;           // Dependent - either a predecessor or a successor.
  45     unsigned  Reg;           // If non-zero, this dep is a physreg dependency.
  46     int       Cost;          // Cost of the dependency.
  47     bool      isCtrl    : 1; // True iff it's a control dependency.
  48     bool      isArtificial : 1; // True iff it's an artificial ctrl dep added
  49                                 // during sched that may be safely deleted if
  50                                 // necessary.
  51     bool      isAntiDep : 1; // True iff it's an anti-dependency (on a physical
  52                              // register.
  53     SDep(SUnit *d, unsigned r, int t, bool c, bool a, bool anti)
  54       : Dep(d), Reg(r), Cost(t), isCtrl(c), isArtificial(a), isAntiDep(anti) {}
  55   };
  56
  57   /// SUnit - Scheduling unit. This is a node in the scheduling DAG.
  58   struct SUnit {
  59   private:
  60     SDNode *Node;                       // Representative node.
  61     MachineInstr *Instr;                // Alternatively, a MachineInstr.
  62   public:
  63     SUnit *OrigNode;                    // If not this, the node from which
  64                                         // this node was cloned.
  65
  66     // Preds/Succs - The SUnits before/after us in the graph.  The boolean value
  67     // is true if the edge is a token chain edge, false if it is a value edge.
  68     SmallVector<SDep, 4> Preds;  // All sunit predecessors.
  69     SmallVector<SDep, 4> Succs;  // All sunit successors.
  70
  71     typedef SmallVector<SDep, 4>::iterator pred_iterator;
  72     typedef SmallVector<SDep, 4>::iterator succ_iterator;
  73     typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator;
  74     typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator;
  75
  76     unsigned NodeNum;                   // Entry # of node in the node vector.
  77     unsigned NodeQueueId;               // Queue id of node.
  78     unsigned short Latency;             // Node latency.
  79     short NumPreds;                     // # of non-control preds.
  80     short NumSuccs;                     // # of non-control sucss.
  81     short NumPredsLeft;                 // # of preds not scheduled.
  82     short NumSuccsLeft;                 // # of succs not scheduled.
  83     bool isTwoAddress     : 1;          // Is a two-address instruction.
  84     bool isCommutable     : 1;          // Is a commutable instruction.
  85     bool hasPhysRegDefs   : 1;          // Has physreg defs that are being used.
  86     bool isPending        : 1;          // True once pending.
  87     bool isAvailable      : 1;          // True once available.
  88     bool isScheduled      : 1;          // True once scheduled.
  89     unsigned CycleBound;                // Upper/lower cycle to be scheduled at.
  90     unsigned Cycle;                     // Once scheduled, the cycle of the op.
  91     unsigned Depth;                     // Node depth;
  92     unsigned Height;                    // Node height;
  93     const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null.
  94     const TargetRegisterClass *CopySrcRC;
  95
  96     /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent
  97     /// an SDNode and any nodes flagged to it.
  98     SUnit(SDNode *node, unsigned nodenum)
  99       : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), NodeQueueId(0),
 100         Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
 101         isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
 102         isPending(false), isAvailable(false), isScheduled(false),
 103         CycleBound(0), Cycle(~0u), Depth(0), Height(0),
 104         CopyDstRC(NULL), CopySrcRC(NULL) {}
 105
 106     /// SUnit - Construct an SUnit for post-regalloc scheduling to represent
 107     /// a MachineInstr.
 108     SUnit(MachineInstr *instr, unsigned nodenum)
 109       : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum), NodeQueueId(0),
 110         Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
 111         isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false),
 112         isPending(false), isAvailable(false), isScheduled(false),
 113         CycleBound(0), Cycle(~0u), Depth(0), Height(0),
 114         CopyDstRC(NULL), CopySrcRC(NULL) {}
 115
 116     /// setNode - Assign the representative SDNode for this SUnit.
 117     /// This may be used during pre-regalloc scheduling.
 118     void setNode(SDNode *N) {
 119       assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
 120       Node = N;
 121     }
 122
 123     /// getNode - Return the representative SDNode for this SUnit.
 124     /// This may be used during pre-regalloc scheduling.
 125     SDNode *getNode() const {
 126       assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
 127       return Node;
 128     }
 129
 130     /// setInstr - Assign the instruction for the SUnit.
 131     /// This may be used during post-regalloc scheduling.
 132     void setInstr(MachineInstr *MI) {
 133       assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
 134       Instr = MI;
 135     }
 136
 137     /// getInstr - Return the representative MachineInstr for this SUnit.
 138     /// This may be used during post-regalloc scheduling.
 139     MachineInstr *getInstr() const {
 140       assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
 141       return Instr;
 142     }
 143
 144     /// addPred - This adds the specified node as a pred of the current node if
 145     /// not already.  It also adds the current node as a successor of the
 146     /// specified node.  This returns true if this is a new pred.
 147     bool addPred(SUnit *N, bool isCtrl, bool isArtificial,
 148                  unsigned PhyReg = 0, int Cost = 1, bool isAntiDep = false) {
 149       for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
 150         if (Preds[i].Dep == N &&
 151             Preds[i].isCtrl == isCtrl && Preds[i].isArtificial == isArtificial)
 152           return false;
 153       Preds.push_back(SDep(N, PhyReg, Cost, isCtrl, isArtificial, isAntiDep));
 154       N->Succs.push_back(SDep(this, PhyReg, Cost, isCtrl,
 155                               isArtificial, isAntiDep));
 156       if (!isCtrl) {
 157         ++NumPreds;
 158         ++N->NumSuccs;
 159       }
 160       if (!N->isScheduled)
 161         ++NumPredsLeft;
 162       if (!isScheduled)
 163         ++N->NumSuccsLeft;
 164       return true;
 165     }
 166
 167     bool removePred(SUnit *N, bool isCtrl, bool isArtificial, bool isAntiDep) {
 168       for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end();
 169            I != E; ++I)
 170         if (I->Dep == N && I->isCtrl == isCtrl && I->isArtificial == isArtificial) {
 171           bool FoundSucc = false;
 172           for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(),
 173                  EE = N->Succs.end(); II != EE; ++II)
 174             if (II->Dep == this &&
 175                 II->isCtrl == isCtrl && II->isArtificial == isArtificial &&
 176                 II->isAntiDep == isAntiDep) {
 177               FoundSucc = true;
 178               N->Succs.erase(II);
 179               break;
 180             }
 181           assert(FoundSucc && "Mismatching preds / succs lists!");
 182           Preds.erase(I);
 183           if (!isCtrl) {
 184             --NumPreds;
 185             --N->NumSuccs;
 186           }
 187           if (!N->isScheduled)
 188             --NumPredsLeft;
 189           if (!isScheduled)
 190             --N->NumSuccsLeft;
 191           return true;
 192         }
 193       return false;
 194     }
 195
 196     bool isPred(SUnit *N) {
 197       for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
 198         if (Preds[i].Dep == N)
 199           return true;
 200       return false;
 201     }
 202
 203     bool isSucc(SUnit *N) {
 204       for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i)
 205         if (Succs[i].Dep == N)
 206           return true;
 207       return false;
 208     }
 209
 210     void dump(const ScheduleDAG *G) const;
 211     void dumpAll(const ScheduleDAG *G) const;
 212     void print(raw_ostream &O, const ScheduleDAG *G) const;
 213   };
 214
 215   //===--------------------------------------------------------------------===//
 216   /// SchedulingPriorityQueue - This interface is used to plug different
 217   /// priorities computation algorithms into the list scheduler. It implements
 218   /// the interface of a standard priority queue, where nodes are inserted in
 219   /// arbitrary order and returned in priority order.  The computation of the
 220   /// priority and the representation of the queue are totally up to the
 221   /// implementation to decide.
 222   ///
 223   class SchedulingPriorityQueue {
 224   public:
 225     virtual ~SchedulingPriorityQueue() {}
 226
 227     virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
 228     virtual void addNode(const SUnit *SU) = 0;
 229     virtual void updateNode(const SUnit *SU) = 0;
 230     virtual void releaseState() = 0;
 231
 232     virtual unsigned size() const = 0;
 233     virtual bool empty() const = 0;
 234     virtual void push(SUnit *U) = 0;
 235
 236     virtual void push_all(const std::vector<SUnit *> &Nodes) = 0;
 237     virtual SUnit *pop() = 0;
 238
 239     virtual void remove(SUnit *SU) = 0;
 240
 241     /// ScheduledNode - As each node is scheduled, this method is invoked.  This
 242     /// allows the priority function to adjust the priority of related
 243     /// unscheduled nodes, for example.
 244     ///
 245     virtual void ScheduledNode(SUnit *) {}
 246
 247     virtual void UnscheduledNode(SUnit *) {}
 248   };
 249
 250   class ScheduleDAG {
 251   public:
 252     SelectionDAG *DAG;                    // DAG of the current basic block
 253     MachineBasicBlock *BB;                // Current basic block
 254     const TargetMachine &TM;              // Target processor
 255     const TargetInstrInfo *TII;           // Target instruction information
 256     const TargetRegisterInfo *TRI;        // Target processor register info
 257     TargetLowering *TLI;                  // Target lowering info
 258     MachineFunction *MF;                  // Machine function
 259     MachineRegisterInfo &MRI;             // Virtual/real register map
 260     MachineConstantPool *ConstPool;       // Target constant pool
 261     std::vector<SUnit*> Sequence;         // The schedule. Null SUnit*'s
 262                                           // represent noop instructions.
 263     std::vector<SUnit> SUnits;            // The scheduling units.
 264
 265     ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb,
 266                 const TargetMachine &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     void Run();
 278
 279     /// BuildSchedUnits - Build SUnits and set up their Preds and Succs
 280     /// to form the scheduling dependency graph.
 281     ///
 282     virtual void BuildSchedUnits() = 0;
 283
 284     /// ComputeLatency - Compute node latency.
 285     ///
 286     virtual void ComputeLatency(SUnit *SU) { SU->Latency = 1; }
 287
 288     /// CalculateDepths, CalculateHeights - Calculate node depth / height.
 289     ///
 290     void CalculateDepths();
 291     void CalculateHeights();
 292
 293   protected:
 294     /// EmitNoop - Emit a noop instruction.
 295     ///
 296     void EmitNoop();
 297
 298   public:
 299     virtual MachineBasicBlock *EmitSchedule() = 0;
 300
 301     void dumpSchedule() const;
 302
 303     /// Schedule - Order nodes according to selected style, filling
 304     /// in the Sequence member.
 305     ///
 306     virtual void Schedule() = 0;
 307
 308     virtual void dumpNode(const SUnit *SU) const = 0;
 309
 310     /// getGraphNodeLabel - Return a label for an SUnit node in a visualization
 311     /// of the ScheduleDAG.
 312     virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
 313
 314     /// addCustomGraphFeatures - Add custom features for a visualization of
 315     /// the ScheduleDAG.
 316     virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {}
 317
 318 #ifndef NDEBUG
 319     /// VerifySchedule - Verify that all SUnits were scheduled and that
 320     /// their state is consistent.
 321     void VerifySchedule(bool isBottomUp);
 322 #endif
 323
 324   protected:
 325     void AddMemOperand(MachineInstr *MI, const MachineMemOperand &MO);
 326
 327     void EmitCrossRCCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap);
 328
 329   private:
 330     /// EmitLiveInCopy - Emit a copy for a live in physical register. If the
 331     /// physical register has only a single copy use, then coalesced the copy
 332     /// if possible.
 333     void EmitLiveInCopy(MachineBasicBlock *MBB,
 334                         MachineBasicBlock::iterator &InsertPos,
 335                         unsigned VirtReg, unsigned PhysReg,
 336                         const TargetRegisterClass *RC,
 337                         DenseMap<MachineInstr*, unsigned> &CopyRegMap);
 338
 339     /// EmitLiveInCopies - If this is the first basic block in the function,
 340     /// and if it has live ins that need to be copied into vregs, emit the
 341     /// copies into the top of the block.
 342     void EmitLiveInCopies(MachineBasicBlock *MBB);
 343   };
 344
 345   class SUnitIterator : public forward_iterator<SUnit, ptrdiff_t> {
 346     SUnit *Node;
 347     unsigned Operand;
 348
 349     SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
 350   public:
 351     bool operator==(const SUnitIterator& x) const {
 352       return Operand == x.Operand;
 353     }
 354     bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
 355
 356     const SUnitIterator &operator=(const SUnitIterator &I) {
 357       assert(I.Node == Node && "Cannot assign iterators to two different nodes!");
 358       Operand = I.Operand;
 359       return *this;
 360     }
 361
 362     pointer operator*() const {
 363       return Node->Preds[Operand].Dep;
 364     }
 365     pointer operator->() const { return operator*(); }
 366
 367     SUnitIterator& operator++() {                // Preincrement
 368       ++Operand;
 369       return *this;
 370     }
 371     SUnitIterator operator++(int) { // Postincrement
 372       SUnitIterator tmp = *this; ++*this; return tmp;
 373     }
 374
 375     static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
 376     static SUnitIterator end  (SUnit *N) {
 377       return SUnitIterator(N, (unsigned)N->Preds.size());
 378     }
 379
 380     unsigned getOperand() const { return Operand; }
 381     const SUnit *getNode() const { return Node; }
 382     bool isCtrlDep() const { return Node->Preds[Operand].isCtrl; }
 383     bool isArtificialDep() const { return Node->Preds[Operand].isArtificial; }
 384   };
 385
 386   template <> struct GraphTraits<SUnit*> {
 387     typedef SUnit NodeType;
 388     typedef SUnitIterator ChildIteratorType;
 389     static inline NodeType *getEntryNode(SUnit *N) { return N; }
 390     static inline ChildIteratorType child_begin(NodeType *N) {
 391       return SUnitIterator::begin(N);
 392     }
 393     static inline ChildIteratorType child_end(NodeType *N) {
 394       return SUnitIterator::end(N);
 395     }
 396   };
 397
 398   template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
 399     typedef std::vector<SUnit>::iterator nodes_iterator;
 400     static nodes_iterator nodes_begin(ScheduleDAG *G) {
 401       return G->SUnits.begin();
 402     }
 403     static nodes_iterator nodes_end(ScheduleDAG *G) {
 404       return G->SUnits.end();
 405     }
 406   };
 407 }
 408
 409 #endif