ScheduleDAG.h revision ee00a1d12c631eb7360ddd4809bdde72331b2736
1//===------- llvm/CodeGen/ScheduleDAG.h - Common Base Class------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Evan Cheng and is distributed under 6// the University of Illinois Open Source 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/SelectionDAG.h" 19 20#include <set> 21 22namespace llvm { 23 struct InstrStage; 24 class MachineConstantPool; 25 class MachineDebugInfo; 26 class MachineInstr; 27 class MRegisterInfo; 28 class SelectionDAG; 29 class SSARegMap; 30 class TargetInstrInfo; 31 class TargetInstrDescriptor; 32 class TargetMachine; 33 34 /// HazardRecognizer - This determines whether or not an instruction can be 35 /// issued this cycle, and whether or not a noop needs to be inserted to handle 36 /// the hazard. 37 class HazardRecognizer { 38 public: 39 virtual ~HazardRecognizer(); 40 41 enum HazardType { 42 NoHazard, // This instruction can be emitted at this cycle. 43 Hazard, // This instruction can't be emitted at this cycle. 44 NoopHazard, // This instruction can't be emitted, and needs noops. 45 }; 46 47 /// getHazardType - Return the hazard type of emitting this node. There are 48 /// three possible results. Either: 49 /// * NoHazard: it is legal to issue this instruction on this cycle. 50 /// * Hazard: issuing this instruction would stall the machine. If some 51 /// other instruction is available, issue it first. 52 /// * NoopHazard: issuing this instruction would break the program. If 53 /// some other instruction can be issued, do so, otherwise issue a noop. 54 virtual HazardType getHazardType(SDNode *Node) { 55 return NoHazard; 56 } 57 58 /// EmitInstruction - This callback is invoked when an instruction is 59 /// emitted, to advance the hazard state. 60 virtual void EmitInstruction(SDNode *Node) { 61 } 62 63 /// AdvanceCycle - This callback is invoked when no instructions can be 64 /// issued on this cycle without a hazard. This should increment the 65 /// internal state of the hazard recognizer so that previously "Hazard" 66 /// instructions will now not be hazards. 67 virtual void AdvanceCycle() { 68 } 69 70 /// EmitNoop - This callback is invoked when a noop was added to the 71 /// instruction stream. 72 virtual void EmitNoop() { 73 } 74 }; 75 76 /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or 77 /// a group of nodes flagged together. 78 struct SUnit { 79 SDNode *Node; // Representative node. 80 std::vector<SDNode*> FlaggedNodes; // All nodes flagged to Node. 81 82 // Preds/Succs - The SUnits before/after us in the graph. The boolean value 83 // is true if the edge is a token chain edge, false if it is a value edge. 84 std::set<std::pair<SUnit*,bool> > Preds; // All sunit predecessors. 85 std::set<std::pair<SUnit*,bool> > Succs; // All sunit successors. 86 87 short NumPreds; // # of preds. 88 short NumSuccs; // # of sucss. 89 short NumPredsLeft; // # of preds not scheduled. 90 short NumSuccsLeft; // # of succs not scheduled. 91 short NumChainPredsLeft; // # of chain preds not scheduled. 92 short NumChainSuccsLeft; // # of chain succs not scheduled. 93 bool isTwoAddress : 1; // Is a two-address instruction. 94 bool isCommutable : 1; // Is a commutable instruction. 95 bool isPending : 1; // True once pending. 96 bool isAvailable : 1; // True once available. 97 bool isScheduled : 1; // True once scheduled. 98 unsigned short Latency; // Node latency. 99 unsigned CycleBound; // Upper/lower cycle to be scheduled at. 100 unsigned Cycle; // Once scheduled, the cycle of the op. 101 unsigned Depth; // Node depth; 102 unsigned Height; // Node height; 103 unsigned NodeNum; // Entry # of node in the node vector. 104 105 SUnit(SDNode *node, unsigned nodenum) 106 : Node(node), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), 107 NumChainPredsLeft(0), NumChainSuccsLeft(0), 108 isTwoAddress(false), isCommutable(false), 109 isPending(false), isAvailable(false), isScheduled(false), 110 Latency(0), CycleBound(0), Cycle(0), Depth(0), Height(0), 111 NodeNum(nodenum) {} 112 113 void dump(const SelectionDAG *G) const; 114 void dumpAll(const SelectionDAG *G) const; 115 }; 116 117 //===--------------------------------------------------------------------===// 118 /// SchedulingPriorityQueue - This interface is used to plug different 119 /// priorities computation algorithms into the list scheduler. It implements 120 /// the interface of a standard priority queue, where nodes are inserted in 121 /// arbitrary order and returned in priority order. The computation of the 122 /// priority and the representation of the queue are totally up to the 123 /// implementation to decide. 124 /// 125 class SchedulingPriorityQueue { 126 public: 127 virtual ~SchedulingPriorityQueue() {} 128 129 virtual void initNodes(const std::vector<SUnit> &SUnits) = 0; 130 virtual void releaseState() = 0; 131 132 virtual bool empty() const = 0; 133 virtual void push(SUnit *U) = 0; 134 135 virtual void push_all(const std::vector<SUnit *> &Nodes) = 0; 136 virtual SUnit *pop() = 0; 137 138 /// ScheduledNode - As each node is scheduled, this method is invoked. This 139 /// allows the priority function to adjust the priority of node that have 140 /// already been emitted. 141 virtual void ScheduledNode(SUnit *Node) {} 142 }; 143 144 class ScheduleDAG { 145 public: 146 SelectionDAG &DAG; // DAG of the current basic block 147 MachineBasicBlock *BB; // Current basic block 148 const TargetMachine &TM; // Target processor 149 const TargetInstrInfo *TII; // Target instruction information 150 const MRegisterInfo *MRI; // Target processor register info 151 SSARegMap *RegMap; // Virtual/real register map 152 MachineConstantPool *ConstPool; // Target constant pool 153 std::vector<SUnit*> Sequence; // The schedule. Null SUnit*'s 154 // represent noop instructions. 155 std::map<SDNode*, SUnit*> SUnitMap; // SDNode to SUnit mapping (n -> 1). 156 std::vector<SUnit> SUnits; // The scheduling units. 157 std::set<SDNode*> CommuteSet; // Nodes the should be commuted. 158 159 ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb, 160 const TargetMachine &tm) 161 : DAG(dag), BB(bb), TM(tm) {} 162 163 virtual ~ScheduleDAG() {} 164 165 /// Run - perform scheduling. 166 /// 167 MachineBasicBlock *Run(); 168 169 /// isPassiveNode - Return true if the node is a non-scheduled leaf. 170 /// 171 static bool isPassiveNode(SDNode *Node) { 172 if (isa<ConstantSDNode>(Node)) return true; 173 if (isa<RegisterSDNode>(Node)) return true; 174 if (isa<GlobalAddressSDNode>(Node)) return true; 175 if (isa<BasicBlockSDNode>(Node)) return true; 176 if (isa<FrameIndexSDNode>(Node)) return true; 177 if (isa<ConstantPoolSDNode>(Node)) return true; 178 if (isa<JumpTableSDNode>(Node)) return true; 179 if (isa<ExternalSymbolSDNode>(Node)) return true; 180 return false; 181 } 182 183 /// NewSUnit - Creates a new SUnit and return a ptr to it. 184 /// 185 SUnit *NewSUnit(SDNode *N) { 186 SUnits.push_back(SUnit(N, SUnits.size())); 187 return &SUnits.back(); 188 } 189 190 /// BuildSchedUnits - Build SUnits from the selection dag that we are input. 191 /// This SUnit graph is similar to the SelectionDAG, but represents flagged 192 /// together nodes with a single SUnit. 193 void BuildSchedUnits(); 194 195 /// CalculateDepths, CalculateHeights - Calculate node depth / height. 196 /// 197 void CalculateDepths(); 198 void CalculateHeights(); 199 200 /// EmitNode - Generate machine code for an node and needed dependencies. 201 /// VRBaseMap contains, for each already emitted node, the first virtual 202 /// register number for the results of the node. 203 /// 204 void EmitNode(SDNode *Node, std::map<SDNode*, unsigned> &VRBaseMap); 205 206 /// EmitNoop - Emit a noop instruction. 207 /// 208 void EmitNoop(); 209 210 void EmitSchedule(); 211 212 void dumpSchedule() const; 213 214 /// Schedule - Order nodes according to selected style. 215 /// 216 virtual void Schedule() {} 217 218 private: 219 void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum, 220 const TargetInstrDescriptor *II, 221 std::map<SDNode*, unsigned> &VRBaseMap); 222 }; 223 224 ScheduleDAG *createBFS_DAGScheduler(SelectionDAG &DAG, MachineBasicBlock *BB); 225 226 /// createSimpleDAGScheduler - This creates a simple two pass instruction 227 /// scheduler. 228 ScheduleDAG* createSimpleDAGScheduler(bool NoItins, SelectionDAG &DAG, 229 MachineBasicBlock *BB); 230 231 /// createBURRListDAGScheduler - This creates a bottom up register usage 232 /// reduction list scheduler. 233 ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG, 234 MachineBasicBlock *BB); 235 236 /// createTDRRListDAGScheduler - This creates a top down register usage 237 /// reduction list scheduler. 238 ScheduleDAG* createTDRRListDAGScheduler(SelectionDAG &DAG, 239 MachineBasicBlock *BB); 240 241 /// createTDListDAGScheduler - This creates a top-down list scheduler with 242 /// the specified hazard recognizer. This takes ownership of the hazard 243 /// recognizer and deletes it when done. 244 ScheduleDAG* createTDListDAGScheduler(SelectionDAG &DAG, 245 MachineBasicBlock *BB, 246 HazardRecognizer *HR); 247} 248 249#endif 250