ScheduleDAG.h revision e24f8f1ec9277dc80ebf38f0d914053f8c31caf1
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#include "llvm/ADT/DenseMap.h" 20#include "llvm/ADT/SmallSet.h" 21 22namespace llvm { 23 struct InstrStage; 24 class MachineConstantPool; 25 class MachineModuleInfo; 26 class MachineInstr; 27 class MRegisterInfo; 28 class SelectionDAG; 29 class SelectionDAGISel; 30 class SSARegMap; 31 class TargetInstrInfo; 32 class TargetInstrDescriptor; 33 class TargetMachine; 34 35 /// HazardRecognizer - This determines whether or not an instruction can be 36 /// issued this cycle, and whether or not a noop needs to be inserted to handle 37 /// the hazard. 38 class HazardRecognizer { 39 public: 40 virtual ~HazardRecognizer(); 41 42 enum HazardType { 43 NoHazard, // This instruction can be emitted at this cycle. 44 Hazard, // This instruction can't be emitted at this cycle. 45 NoopHazard // This instruction can't be emitted, and needs noops. 46 }; 47 48 /// getHazardType - Return the hazard type of emitting this node. There are 49 /// three possible results. Either: 50 /// * NoHazard: it is legal to issue this instruction on this cycle. 51 /// * Hazard: issuing this instruction would stall the machine. If some 52 /// other instruction is available, issue it first. 53 /// * NoopHazard: issuing this instruction would break the program. If 54 /// some other instruction can be issued, do so, otherwise issue a noop. 55 virtual HazardType getHazardType(SDNode *Node) { 56 return NoHazard; 57 } 58 59 /// EmitInstruction - This callback is invoked when an instruction is 60 /// emitted, to advance the hazard state. 61 virtual void EmitInstruction(SDNode *Node) { 62 } 63 64 /// AdvanceCycle - This callback is invoked when no instructions can be 65 /// issued on this cycle without a hazard. This should increment the 66 /// internal state of the hazard recognizer so that previously "Hazard" 67 /// instructions will now not be hazards. 68 virtual void AdvanceCycle() { 69 } 70 71 /// EmitNoop - This callback is invoked when a noop was added to the 72 /// instruction stream. 73 virtual void EmitNoop() { 74 } 75 }; 76 77 /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or 78 /// a group of nodes flagged together. 79 struct SUnit { 80 SDNode *Node; // Representative node. 81 SmallVector<SDNode*,4> FlaggedNodes;// All nodes flagged to Node. 82 83 // Preds/Succs - The SUnits before/after us in the graph. The boolean value 84 // is true if the edge is a token chain edge, false if it is a value edge. 85 SmallVector<std::pair<SUnit*,bool>, 4> Preds; // All sunit predecessors. 86 SmallVector<std::pair<SUnit*,bool>, 4> Succs; // All sunit successors. 87 88 typedef SmallVector<std::pair<SUnit*,bool>, 4>::iterator pred_iterator; 89 typedef SmallVector<std::pair<SUnit*,bool>, 4>::iterator succ_iterator; 90 typedef SmallVector<std::pair<SUnit*,bool>, 4>::const_iterator 91 const_pred_iterator; 92 typedef SmallVector<std::pair<SUnit*,bool>, 4>::const_iterator 93 const_succ_iterator; 94 95 short NumPreds; // # of preds. 96 short NumSuccs; // # of sucss. 97 short NumPredsLeft; // # of preds not scheduled. 98 short NumSuccsLeft; // # of succs not scheduled. 99 short NumChainPredsLeft; // # of chain preds not scheduled. 100 short NumChainSuccsLeft; // # of chain succs not scheduled. 101 bool isTwoAddress : 1; // Is a two-address instruction. 102 bool isCommutable : 1; // Is a commutable instruction. 103 bool isPending : 1; // True once pending. 104 bool isAvailable : 1; // True once available. 105 bool isScheduled : 1; // True once scheduled. 106 unsigned short Latency; // Node latency. 107 unsigned CycleBound; // Upper/lower cycle to be scheduled at. 108 unsigned Cycle; // Once scheduled, the cycle of the op. 109 unsigned Depth; // Node depth; 110 unsigned Height; // Node height; 111 unsigned NodeNum; // Entry # of node in the node vector. 112 113 SUnit(SDNode *node, unsigned nodenum) 114 : Node(node), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), 115 NumChainPredsLeft(0), NumChainSuccsLeft(0), 116 isTwoAddress(false), isCommutable(false), 117 isPending(false), isAvailable(false), isScheduled(false), 118 Latency(0), CycleBound(0), Cycle(0), Depth(0), Height(0), 119 NodeNum(nodenum) {} 120 121 /// addPred - This adds the specified node as a pred of the current node if 122 /// not already. This returns true if this is a new pred. 123 bool addPred(SUnit *N, bool isChain) { 124 for (unsigned i = 0, e = Preds.size(); i != e; ++i) 125 if (Preds[i].first == N && Preds[i].second == isChain) 126 return false; 127 Preds.push_back(std::make_pair(N, isChain)); 128 return true; 129 } 130 131 /// addSucc - This adds the specified node as a succ of the current node if 132 /// not already. This returns true if this is a new succ. 133 bool addSucc(SUnit *N, bool isChain) { 134 for (unsigned i = 0, e = Succs.size(); i != e; ++i) 135 if (Succs[i].first == N && Succs[i].second == isChain) 136 return false; 137 Succs.push_back(std::make_pair(N, isChain)); 138 return true; 139 } 140 141 void dump(const SelectionDAG *G) const; 142 void dumpAll(const SelectionDAG *G) const; 143 }; 144 145 //===--------------------------------------------------------------------===// 146 /// SchedulingPriorityQueue - This interface is used to plug different 147 /// priorities computation algorithms into the list scheduler. It implements 148 /// the interface of a standard priority queue, where nodes are inserted in 149 /// arbitrary order and returned in priority order. The computation of the 150 /// priority and the representation of the queue are totally up to the 151 /// implementation to decide. 152 /// 153 class SchedulingPriorityQueue { 154 public: 155 virtual ~SchedulingPriorityQueue() {} 156 157 virtual void initNodes(DenseMap<SDNode*, SUnit*> &SUMap, 158 std::vector<SUnit> &SUnits) = 0; 159 virtual void releaseState() = 0; 160 161 virtual bool empty() const = 0; 162 virtual void push(SUnit *U) = 0; 163 164 virtual void push_all(const std::vector<SUnit *> &Nodes) = 0; 165 virtual SUnit *pop() = 0; 166 167 /// ScheduledNode - As each node is scheduled, this method is invoked. This 168 /// allows the priority function to adjust the priority of node that have 169 /// already been emitted. 170 virtual void ScheduledNode(SUnit *Node) {} 171 }; 172 173 class ScheduleDAG { 174 public: 175 SelectionDAG &DAG; // DAG of the current basic block 176 MachineBasicBlock *BB; // Current basic block 177 const TargetMachine &TM; // Target processor 178 const TargetInstrInfo *TII; // Target instruction information 179 const MRegisterInfo *MRI; // Target processor register info 180 SSARegMap *RegMap; // Virtual/real register map 181 MachineConstantPool *ConstPool; // Target constant pool 182 std::vector<SUnit*> Sequence; // The schedule. Null SUnit*'s 183 // represent noop instructions. 184 DenseMap<SDNode*, SUnit*> SUnitMap; // SDNode to SUnit mapping (n -> 1). 185 std::vector<SUnit> SUnits; // The scheduling units. 186 SmallSet<SDNode*, 16> CommuteSet; // Nodes the should be commuted. 187 188 ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb, 189 const TargetMachine &tm) 190 : DAG(dag), BB(bb), TM(tm) {} 191 192 virtual ~ScheduleDAG() {} 193 194 /// Run - perform scheduling. 195 /// 196 MachineBasicBlock *Run(); 197 198 /// isPassiveNode - Return true if the node is a non-scheduled leaf. 199 /// 200 static bool isPassiveNode(SDNode *Node) { 201 if (isa<ConstantSDNode>(Node)) return true; 202 if (isa<RegisterSDNode>(Node)) return true; 203 if (isa<GlobalAddressSDNode>(Node)) return true; 204 if (isa<BasicBlockSDNode>(Node)) return true; 205 if (isa<FrameIndexSDNode>(Node)) return true; 206 if (isa<ConstantPoolSDNode>(Node)) return true; 207 if (isa<JumpTableSDNode>(Node)) return true; 208 if (isa<ExternalSymbolSDNode>(Node)) return true; 209 return false; 210 } 211 212 /// NewSUnit - Creates a new SUnit and return a ptr to it. 213 /// 214 SUnit *NewSUnit(SDNode *N) { 215 SUnits.push_back(SUnit(N, SUnits.size())); 216 return &SUnits.back(); 217 } 218 219 /// BuildSchedUnits - Build SUnits from the selection dag that we are input. 220 /// This SUnit graph is similar to the SelectionDAG, but represents flagged 221 /// together nodes with a single SUnit. 222 void BuildSchedUnits(); 223 224 /// CalculateDepths, CalculateHeights - Calculate node depth / height. 225 /// 226 void CalculateDepths(); 227 void CalculateHeights(); 228 229 /// CountResults - The results of target nodes have register or immediate 230 /// operands first, then an optional chain, and optional flag operands 231 /// (which do not go into the machine instrs.) 232 static unsigned CountResults(SDNode *Node); 233 234 /// CountOperands The inputs to target nodes have any actual inputs first, 235 /// followed by an optional chain operand, then flag operands. Compute the 236 /// number of actual operands that will go into the machine instr. 237 static unsigned CountOperands(SDNode *Node); 238 239 /// EmitNode - Generate machine code for an node and needed dependencies. 240 /// VRBaseMap contains, for each already emitted node, the first virtual 241 /// register number for the results of the node. 242 /// 243 void EmitNode(SDNode *Node, DenseMap<SDOperand, unsigned> &VRBaseMap); 244 245 /// EmitNoop - Emit a noop instruction. 246 /// 247 void EmitNoop(); 248 249 void EmitSchedule(); 250 251 void dumpSchedule() const; 252 253 /// Schedule - Order nodes according to selected style. 254 /// 255 virtual void Schedule() {} 256 257 private: 258 /// EmitSubregNode - Generate machine code for subreg nodes. 259 /// 260 void EmitSubregNode(SDNode *Node, 261 DenseMap<SDOperand, unsigned> &VRBaseMap); 262 263 void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum, 264 const TargetInstrDescriptor *II, 265 DenseMap<SDOperand, unsigned> &VRBaseMap); 266 }; 267 268 /// createBFS_DAGScheduler - This creates a simple breadth first instruction 269 /// scheduler. 270 ScheduleDAG *createBFS_DAGScheduler(SelectionDAGISel *IS, 271 SelectionDAG *DAG, 272 MachineBasicBlock *BB); 273 274 /// createSimpleDAGScheduler - This creates a simple two pass instruction 275 /// scheduler using instruction itinerary. 276 ScheduleDAG* createSimpleDAGScheduler(SelectionDAGISel *IS, 277 SelectionDAG *DAG, 278 MachineBasicBlock *BB); 279 280 /// createNoItinsDAGScheduler - This creates a simple two pass instruction 281 /// scheduler without using instruction itinerary. 282 ScheduleDAG* createNoItinsDAGScheduler(SelectionDAGISel *IS, 283 SelectionDAG *DAG, 284 MachineBasicBlock *BB); 285 286 /// createBURRListDAGScheduler - This creates a bottom up register usage 287 /// reduction list scheduler. 288 ScheduleDAG* createBURRListDAGScheduler(SelectionDAGISel *IS, 289 SelectionDAG *DAG, 290 MachineBasicBlock *BB); 291 292 /// createTDRRListDAGScheduler - This creates a top down register usage 293 /// reduction list scheduler. 294 ScheduleDAG* createTDRRListDAGScheduler(SelectionDAGISel *IS, 295 SelectionDAG *DAG, 296 MachineBasicBlock *BB); 297 298 /// createTDListDAGScheduler - This creates a top-down list scheduler with 299 /// a hazard recognizer. 300 ScheduleDAG* createTDListDAGScheduler(SelectionDAGISel *IS, 301 SelectionDAG *DAG, 302 MachineBasicBlock *BB); 303 304 /// createDefaultScheduler - This creates an instruction scheduler appropriate 305 /// for the target. 306 ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS, 307 SelectionDAG *DAG, 308 MachineBasicBlock *BB); 309} 310 311#endif 312