LLVM API Documentation
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