LLVM API Documentation

ScheduleDAG.h

Go to the documentation of this file.
00001 //===------- llvm/CodeGen/ScheduleDAG.h - Common Base Class------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by Evan Cheng and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the ScheduleDAG class, which is used as the common
00011 // base class for SelectionDAG-based instruction scheduler.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #ifndef LLVM_CODEGEN_SCHEDULEDAG_H
00016 #define LLVM_CODEGEN_SCHEDULEDAG_H
00017 
00018 #include "llvm/CodeGen/SelectionDAG.h"
00019 
00020 #include <set>
00021 
00022 namespace llvm {
00023   struct InstrStage;
00024   class MachineConstantPool;
00025   class MachineDebugInfo;
00026   class MachineInstr;
00027   class MRegisterInfo;
00028   class SelectionDAG;
00029   class SSARegMap;
00030   class TargetInstrInfo;
00031   class TargetInstrDescriptor;
00032   class TargetMachine;
00033 
00034   /// HazardRecognizer - This determines whether or not an instruction can be
00035   /// issued this cycle, and whether or not a noop needs to be inserted to handle
00036   /// the hazard.
00037   class HazardRecognizer {
00038   public:
00039     virtual ~HazardRecognizer();
00040     
00041     enum HazardType {
00042       NoHazard,      // This instruction can be emitted at this cycle.
00043       Hazard,        // This instruction can't be emitted at this cycle.
00044       NoopHazard     // This instruction can't be emitted, and needs noops.
00045     };
00046     
00047     /// getHazardType - Return the hazard type of emitting this node.  There are
00048     /// three possible results.  Either:
00049     ///  * NoHazard: it is legal to issue this instruction on this cycle.
00050     ///  * Hazard: issuing this instruction would stall the machine.  If some
00051     ///     other instruction is available, issue it first.
00052     ///  * NoopHazard: issuing this instruction would break the program.  If
00053     ///     some other instruction can be issued, do so, otherwise issue a noop.
00054     virtual HazardType getHazardType(SDNode *Node) {
00055       return NoHazard;
00056     }
00057     
00058     /// EmitInstruction - This callback is invoked when an instruction is
00059     /// emitted, to advance the hazard state.
00060     virtual void EmitInstruction(SDNode *Node) {
00061     }
00062     
00063     /// AdvanceCycle - This callback is invoked when no instructions can be
00064     /// issued on this cycle without a hazard.  This should increment the
00065     /// internal state of the hazard recognizer so that previously "Hazard"
00066     /// instructions will now not be hazards.
00067     virtual void AdvanceCycle() {
00068     }
00069     
00070     /// EmitNoop - This callback is invoked when a noop was added to the
00071     /// instruction stream.
00072     virtual void EmitNoop() {
00073     }
00074   };
00075   
00076   /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
00077   /// a group of nodes flagged together.
00078   struct SUnit {
00079     SDNode *Node;                       // Representative node.
00080     std::vector<SDNode*> FlaggedNodes;  // All nodes flagged to Node.
00081     
00082     // Preds/Succs - The SUnits before/after us in the graph.  The boolean value
00083     // is true if the edge is a token chain edge, false if it is a value edge. 
00084     std::set<std::pair<SUnit*,bool> > Preds;  // All sunit predecessors.
00085     std::set<std::pair<SUnit*,bool> > Succs;  // All sunit successors.
00086 
00087     short NumPreds;                     // # of preds.
00088     short NumSuccs;                     // # of sucss.
00089     short NumPredsLeft;                 // # of preds not scheduled.
00090     short NumSuccsLeft;                 // # of succs not scheduled.
00091     short NumChainPredsLeft;            // # of chain preds not scheduled.
00092     short NumChainSuccsLeft;            // # of chain succs not scheduled.
00093     bool isTwoAddress     : 1;          // Is a two-address instruction.
00094     bool isCommutable     : 1;          // Is a commutable instruction.
00095     bool isPending        : 1;          // True once pending.
00096     bool isAvailable      : 1;          // True once available.
00097     bool isScheduled      : 1;          // True once scheduled.
00098     unsigned short Latency;             // Node latency.
00099     unsigned CycleBound;                // Upper/lower cycle to be scheduled at.
00100     unsigned Cycle;                     // Once scheduled, the cycle of the op.
00101     unsigned Depth;                     // Node depth;
00102     unsigned Height;                    // Node height;
00103     unsigned NodeNum;                   // Entry # of node in the node vector.
00104     
00105     SUnit(SDNode *node, unsigned nodenum)
00106       : Node(node), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0),
00107         NumChainPredsLeft(0), NumChainSuccsLeft(0),
00108         isTwoAddress(false), isCommutable(false),
00109         isPending(false), isAvailable(false), isScheduled(false),
00110         Latency(0), CycleBound(0), Cycle(0), Depth(0), Height(0),
00111         NodeNum(nodenum) {}
00112     
00113     void dump(const SelectionDAG *G) const;
00114     void dumpAll(const SelectionDAG *G) const;
00115   };
00116 
00117   //===--------------------------------------------------------------------===//
00118   /// SchedulingPriorityQueue - This interface is used to plug different
00119   /// priorities computation algorithms into the list scheduler. It implements
00120   /// the interface of a standard priority queue, where nodes are inserted in 
00121   /// arbitrary order and returned in priority order.  The computation of the
00122   /// priority and the representation of the queue are totally up to the
00123   /// implementation to decide.
00124   /// 
00125   class SchedulingPriorityQueue {
00126   public:
00127     virtual ~SchedulingPriorityQueue() {}
00128   
00129     virtual void initNodes(const std::vector<SUnit> &SUnits) = 0;
00130     virtual void releaseState() = 0;
00131   
00132     virtual bool empty() const = 0;
00133     virtual void push(SUnit *U) = 0;
00134   
00135     virtual void push_all(const std::vector<SUnit *> &Nodes) = 0;
00136     virtual SUnit *pop() = 0;
00137 
00138     /// ScheduledNode - As each node is scheduled, this method is invoked.  This
00139     /// allows the priority function to adjust the priority of node that have
00140     /// already been emitted.
00141     virtual void ScheduledNode(SUnit *Node) {}
00142   };
00143 
00144   class ScheduleDAG {
00145   public:
00146     SelectionDAG &DAG;                    // DAG of the current basic block
00147     MachineBasicBlock *BB;                // Current basic block
00148     const TargetMachine &TM;              // Target processor
00149     const TargetInstrInfo *TII;           // Target instruction information
00150     const MRegisterInfo *MRI;             // Target processor register info
00151     SSARegMap *RegMap;                    // Virtual/real register map
00152     MachineConstantPool *ConstPool;       // Target constant pool
00153     std::vector<SUnit*> Sequence;         // The schedule. Null SUnit*'s
00154                                           // represent noop instructions.
00155     std::map<SDNode*, SUnit*> SUnitMap;   // SDNode to SUnit mapping (n -> 1).
00156     std::vector<SUnit> SUnits;            // The scheduling units.
00157     std::set<SDNode*> CommuteSet;         // Nodes the should be commuted.
00158 
00159     ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb,
00160                 const TargetMachine &tm)
00161       : DAG(dag), BB(bb), TM(tm) {}
00162 
00163     virtual ~ScheduleDAG() {}
00164 
00165     /// Run - perform scheduling.
00166     ///
00167     MachineBasicBlock *Run();
00168 
00169     /// isPassiveNode - Return true if the node is a non-scheduled leaf.
00170     ///
00171     static bool isPassiveNode(SDNode *Node) {
00172       if (isa<ConstantSDNode>(Node))       return true;
00173       if (isa<RegisterSDNode>(Node))       return true;
00174       if (isa<GlobalAddressSDNode>(Node))  return true;
00175       if (isa<BasicBlockSDNode>(Node))     return true;
00176       if (isa<FrameIndexSDNode>(Node))     return true;
00177       if (isa<ConstantPoolSDNode>(Node))   return true;
00178       if (isa<JumpTableSDNode>(Node))      return true;
00179       if (isa<ExternalSymbolSDNode>(Node)) return true;
00180       return false;
00181     }
00182 
00183     /// NewSUnit - Creates a new SUnit and return a ptr to it.
00184     ///
00185     SUnit *NewSUnit(SDNode *N) {
00186       SUnits.push_back(SUnit(N, SUnits.size()));
00187       return &SUnits.back();
00188     }
00189 
00190     /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
00191     /// This SUnit graph is similar to the SelectionDAG, but represents flagged
00192     /// together nodes with a single SUnit.
00193     void BuildSchedUnits();
00194 
00195     /// CalculateDepths, CalculateHeights - Calculate node depth / height.
00196     ///
00197     void CalculateDepths();
00198     void CalculateHeights();
00199 
00200     /// EmitNode - Generate machine code for an node and needed dependencies.
00201     /// VRBaseMap contains, for each already emitted node, the first virtual
00202     /// register number for the results of the node.
00203     ///
00204     void EmitNode(SDNode *Node, std::map<SDNode*, unsigned> &VRBaseMap);
00205     
00206     /// EmitNoop - Emit a noop instruction.
00207     ///
00208     void EmitNoop();
00209     
00210     void EmitSchedule();
00211 
00212     void dumpSchedule() const;
00213 
00214     /// Schedule - Order nodes according to selected style.
00215     ///
00216     virtual void Schedule() {}
00217 
00218   private:
00219     void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum,
00220                     const TargetInstrDescriptor *II,
00221                     std::map<SDNode*, unsigned> &VRBaseMap);
00222   };
00223 
00224   ScheduleDAG *createBFS_DAGScheduler(SelectionDAG &DAG, MachineBasicBlock *BB);
00225   
00226   /// createSimpleDAGScheduler - This creates a simple two pass instruction
00227   /// scheduler.
00228   ScheduleDAG* createSimpleDAGScheduler(bool NoItins, SelectionDAG &DAG,
00229                                         MachineBasicBlock *BB);
00230 
00231   /// createBURRListDAGScheduler - This creates a bottom up register usage
00232   /// reduction list scheduler.
00233   ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG,
00234                                           MachineBasicBlock *BB);
00235   
00236   /// createTDRRListDAGScheduler - This creates a top down register usage
00237   /// reduction list scheduler.
00238   ScheduleDAG* createTDRRListDAGScheduler(SelectionDAG &DAG,
00239                                           MachineBasicBlock *BB);
00240   
00241   /// createTDListDAGScheduler - This creates a top-down list scheduler with
00242   /// the specified hazard recognizer.  This takes ownership of the hazard
00243   /// recognizer and deletes it when done.
00244   ScheduleDAG* createTDListDAGScheduler(SelectionDAG &DAG,
00245                                         MachineBasicBlock *BB,
00246                                         HazardRecognizer *HR);
00247 }
00248 
00249 #endif