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