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