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