ScheduleDAG.h revision 46c01cfe9f1c6900ea63df9c79094d0826fd9ecc
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 20namespace llvm { 21 struct InstrStage; 22 class MachineConstantPool; 23 class MachineDebugInfo; 24 class MachineInstr; 25 class MRegisterInfo; 26 class SelectionDAG; 27 class SSARegMap; 28 class TargetInstrInfo; 29 class TargetInstrDescriptor; 30 class TargetMachine; 31 32 class NodeInfo; 33 typedef NodeInfo *NodeInfoPtr; 34 typedef std::vector<NodeInfoPtr> NIVector; 35 typedef std::vector<NodeInfoPtr>::iterator NIIterator; 36 37 38 // Scheduling heuristics 39 enum SchedHeuristics { 40 defaultScheduling, // Let the target specify its preference. 41 noScheduling, // No scheduling, emit breath first sequence. 42 simpleScheduling, // Two pass, min. critical path, max. utilization. 43 simpleNoItinScheduling, // Same as above exact using generic latency. 44 listSchedulingBURR, // Bottom up reg reduction list scheduling. 45 }; 46 47 48 //===--------------------------------------------------------------------===// 49 /// 50 /// Node group - This struct is used to manage flagged node groups. 51 /// 52 class NodeGroup { 53 private: 54 NIVector Members; // Group member nodes 55 NodeInfo *Dominator; // Node with highest latency 56 unsigned Latency; // Total latency of the group 57 int Pending; // Number of visits pending before 58 // adding to order 59 60 public: 61 // Ctor. 62 NodeGroup() : Dominator(NULL), Pending(0) {} 63 64 // Accessors 65 inline void setDominator(NodeInfo *D) { Dominator = D; } 66 inline NodeInfo *getTop() { return Members[0]; } 67 inline NodeInfo *getBottom() { return Members[Members.size()-1]; } 68 inline NodeInfo *getDominator() { return Dominator; } 69 inline void setLatency(unsigned L) { Latency = L; } 70 inline unsigned getLatency() { return Latency; } 71 inline int getPending() const { return Pending; } 72 inline void setPending(int P) { Pending = P; } 73 inline int addPending(int I) { return Pending += I; } 74 75 // Pass thru 76 inline bool group_empty() { return Members.empty(); } 77 inline NIIterator group_begin() { return Members.begin(); } 78 inline NIIterator group_end() { return Members.end(); } 79 inline void group_push_back(const NodeInfoPtr &NI) { 80 Members.push_back(NI); 81 } 82 inline NIIterator group_insert(NIIterator Pos, const NodeInfoPtr &NI) { 83 return Members.insert(Pos, NI); 84 } 85 inline void group_insert(NIIterator Pos, NIIterator First, 86 NIIterator Last) { 87 Members.insert(Pos, First, Last); 88 } 89 90 static void Add(NodeInfo *D, NodeInfo *U); 91 }; 92 93 //===--------------------------------------------------------------------===// 94 /// 95 /// NodeInfo - This struct tracks information used to schedule the a node. 96 /// 97 class NodeInfo { 98 private: 99 int Pending; // Number of visits pending before 100 // adding to order 101 public: 102 SDNode *Node; // DAG node 103 InstrStage *StageBegin; // First stage in itinerary 104 InstrStage *StageEnd; // Last+1 stage in itinerary 105 unsigned Latency; // Total cycles to complete instr 106 bool IsCall : 1; // Is function call 107 bool IsLoad : 1; // Is memory load 108 bool IsStore : 1; // Is memory store 109 unsigned Slot; // Node's time slot 110 NodeGroup *Group; // Grouping information 111 unsigned VRBase; // Virtual register base 112#ifndef NDEBUG 113 unsigned Preorder; // Index before scheduling 114#endif 115 116 // Ctor. 117 NodeInfo(SDNode *N = NULL) 118 : Pending(0) 119 , Node(N) 120 , StageBegin(NULL) 121 , StageEnd(NULL) 122 , Latency(0) 123 , IsCall(false) 124 , Slot(0) 125 , Group(NULL) 126 , VRBase(0) 127#ifndef NDEBUG 128 , Preorder(0) 129#endif 130 {} 131 132 // Accessors 133 inline bool isInGroup() const { 134 assert(!Group || !Group->group_empty() && "Group with no members"); 135 return Group != NULL; 136 } 137 inline bool isGroupDominator() const { 138 return isInGroup() && Group->getDominator() == this; 139 } 140 inline int getPending() const { 141 return Group ? Group->getPending() : Pending; 142 } 143 inline void setPending(int P) { 144 if (Group) Group->setPending(P); 145 else Pending = P; 146 } 147 inline int addPending(int I) { 148 if (Group) return Group->addPending(I); 149 else return Pending += I; 150 } 151 }; 152 153 //===--------------------------------------------------------------------===// 154 /// 155 /// NodeGroupIterator - Iterates over all the nodes indicated by the node 156 /// info. If the node is in a group then iterate over the members of the 157 /// group, otherwise just the node info. 158 /// 159 class NodeGroupIterator { 160 private: 161 NodeInfo *NI; // Node info 162 NIIterator NGI; // Node group iterator 163 NIIterator NGE; // Node group iterator end 164 165 public: 166 // Ctor. 167 NodeGroupIterator(NodeInfo *N) : NI(N) { 168 // If the node is in a group then set up the group iterator. Otherwise 169 // the group iterators will trip first time out. 170 if (N->isInGroup()) { 171 // get Group 172 NodeGroup *Group = NI->Group; 173 NGI = Group->group_begin(); 174 NGE = Group->group_end(); 175 // Prevent this node from being used (will be in members list 176 NI = NULL; 177 } 178 } 179 180 /// next - Return the next node info, otherwise NULL. 181 /// 182 NodeInfo *next() { 183 // If members list 184 if (NGI != NGE) return *NGI++; 185 // Use node as the result (may be NULL) 186 NodeInfo *Result = NI; 187 // Only use once 188 NI = NULL; 189 // Return node or NULL 190 return Result; 191 } 192 }; 193 //===--------------------------------------------------------------------===// 194 195 196 //===--------------------------------------------------------------------===// 197 /// 198 /// NodeGroupOpIterator - Iterates over all the operands of a node. If the 199 /// node is a member of a group, this iterates over all the operands of all 200 /// the members of the group. 201 /// 202 class NodeGroupOpIterator { 203 private: 204 NodeInfo *NI; // Node containing operands 205 NodeGroupIterator GI; // Node group iterator 206 SDNode::op_iterator OI; // Operand iterator 207 SDNode::op_iterator OE; // Operand iterator end 208 209 /// CheckNode - Test if node has more operands. If not get the next node 210 /// skipping over nodes that have no operands. 211 void CheckNode() { 212 // Only if operands are exhausted first 213 while (OI == OE) { 214 // Get next node info 215 NodeInfo *NI = GI.next(); 216 // Exit if nodes are exhausted 217 if (!NI) return; 218 // Get node itself 219 SDNode *Node = NI->Node; 220 // Set up the operand iterators 221 OI = Node->op_begin(); 222 OE = Node->op_end(); 223 } 224 } 225 226 public: 227 // Ctor. 228 NodeGroupOpIterator(NodeInfo *N) 229 : NI(N), GI(N), OI(SDNode::op_iterator()), OE(SDNode::op_iterator()) {} 230 231 /// isEnd - Returns true when not more operands are available. 232 /// 233 inline bool isEnd() { CheckNode(); return OI == OE; } 234 235 /// next - Returns the next available operand. 236 /// 237 inline SDOperand next() { 238 assert(OI != OE && 239 "Not checking for end of NodeGroupOpIterator correctly"); 240 return *OI++; 241 } 242 }; 243 244 class ScheduleDAG { 245 public: 246 SchedHeuristics Heuristic; // Scheduling heuristic 247 SelectionDAG &DAG; // DAG of the current basic block 248 MachineBasicBlock *BB; // Current basic block 249 const TargetMachine &TM; // Target processor 250 const TargetInstrInfo *TII; // Target instruction information 251 const MRegisterInfo *MRI; // Target processor register info 252 SSARegMap *RegMap; // Virtual/real register map 253 MachineConstantPool *ConstPool; // Target constant pool 254 std::map<SDNode *, NodeInfo *> Map; // Map nodes to info 255 unsigned NodeCount; // Number of nodes in DAG 256 bool HasGroups; // True if there are any groups 257 NodeInfo *Info; // Info for nodes being scheduled 258 NIVector Ordering; // Emit ordering of nodes 259 260 ScheduleDAG(SchedHeuristics hstc, SelectionDAG &dag, MachineBasicBlock *bb, 261 const TargetMachine &tm) 262 : Heuristic(hstc), DAG(dag), BB(bb), TM(tm), 263 NodeCount(0), HasGroups(false), Info(NULL) {} 264 265 virtual ~ScheduleDAG() {}; 266 267 /// Run - perform scheduling. 268 /// 269 MachineBasicBlock *Run(); 270 271 /// getNI - Returns the node info for the specified node. 272 /// 273 NodeInfo *getNI(SDNode *Node) { return Map[Node]; } 274 275 /// getVR - Returns the virtual register number of the node. 276 /// 277 unsigned getVR(SDOperand Op) { 278 NodeInfo *NI = getNI(Op.Val); 279 assert(NI->VRBase != 0 && "Node emitted out of order - late"); 280 return NI->VRBase + Op.ResNo; 281 } 282 283 /// isPassiveNode - Return true if the node is a non-scheduled leaf. 284 /// 285 static bool isPassiveNode(SDNode *Node) { 286 if (isa<ConstantSDNode>(Node)) return true; 287 if (isa<RegisterSDNode>(Node)) return true; 288 if (isa<GlobalAddressSDNode>(Node)) return true; 289 if (isa<BasicBlockSDNode>(Node)) return true; 290 if (isa<FrameIndexSDNode>(Node)) return true; 291 if (isa<ConstantPoolSDNode>(Node)) return true; 292 if (isa<ExternalSymbolSDNode>(Node)) return true; 293 return false; 294 } 295 296 /// EmitNode - Generate machine code for an node and needed dependencies. 297 /// 298 void EmitNode(NodeInfo *NI); 299 300 /// EmitAll - Emit all nodes in schedule sorted order. 301 /// 302 void EmitAll(); 303 304 /// Schedule - Order nodes according to selected style. 305 /// 306 virtual void Schedule() {}; 307 308 /// printNI - Print node info. 309 /// 310 void printNI(std::ostream &O, NodeInfo *NI) const; 311 312 /// printChanges - Hilight changes in order caused by scheduling. 313 /// 314 void printChanges(unsigned Index) const; 315 316 /// print - Print ordering to specified output stream. 317 /// 318 void print(std::ostream &O) const; 319 320 void dump(const char *tag) const; 321 322 virtual void dump() const; 323 324 private: 325 /// PrepareNodeInfo - Set up the basic minimum node info for scheduling. 326 /// 327 void PrepareNodeInfo(); 328 329 /// IdentifyGroups - Put flagged nodes into groups. 330 /// 331 void IdentifyGroups(); 332 }; 333 334 /// createSimpleDAGScheduler - This creates a simple two pass instruction 335 /// scheduler. 336 ScheduleDAG* createSimpleDAGScheduler(SchedHeuristics Heuristic, 337 SelectionDAG &DAG, 338 MachineBasicBlock *BB); 339 340 /// createBURRListDAGScheduler - This creates a bottom up register usage 341 /// reduction list scheduler. 342 ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG, 343 MachineBasicBlock *BB); 344} 345 346#endif 347