LLVM API Documentation
00001 //===-- ScheduleDAGSimple.cpp - Implement a trivial DAG scheduler ---------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by James M. Laskey and is distributed under the 00006 // University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This implements a simple two pass scheduler. The first pass attempts to push 00011 // backward any lengthy instructions and critical paths. The second pass packs 00012 // instructions into semi-optimal time slots. 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #define DEBUG_TYPE "sched" 00017 #include "llvm/CodeGen/ScheduleDAG.h" 00018 #include "llvm/CodeGen/SelectionDAG.h" 00019 #include "llvm/Target/TargetData.h" 00020 #include "llvm/Target/TargetMachine.h" 00021 #include "llvm/Target/TargetInstrInfo.h" 00022 #include "llvm/Support/Debug.h" 00023 #include "llvm/Support/Visibility.h" 00024 #include <algorithm> 00025 #include <iostream> 00026 using namespace llvm; 00027 00028 namespace { 00029 class NodeInfo; 00030 typedef NodeInfo *NodeInfoPtr; 00031 typedef std::vector<NodeInfoPtr> NIVector; 00032 typedef std::vector<NodeInfoPtr>::iterator NIIterator; 00033 00034 //===--------------------------------------------------------------------===// 00035 /// 00036 /// Node group - This struct is used to manage flagged node groups. 00037 /// 00038 class NodeGroup { 00039 public: 00040 NodeGroup *Next; 00041 private: 00042 NIVector Members; // Group member nodes 00043 NodeInfo *Dominator; // Node with highest latency 00044 unsigned Latency; // Total latency of the group 00045 int Pending; // Number of visits pending before 00046 // adding to order 00047 00048 public: 00049 // Ctor. 00050 NodeGroup() : Next(NULL), Dominator(NULL), Pending(0) {} 00051 00052 // Accessors 00053 inline void setDominator(NodeInfo *D) { Dominator = D; } 00054 inline NodeInfo *getTop() { return Members.front(); } 00055 inline NodeInfo *getBottom() { return Members.back(); } 00056 inline NodeInfo *getDominator() { return Dominator; } 00057 inline void setLatency(unsigned L) { Latency = L; } 00058 inline unsigned getLatency() { return Latency; } 00059 inline int getPending() const { return Pending; } 00060 inline void setPending(int P) { Pending = P; } 00061 inline int addPending(int I) { return Pending += I; } 00062 00063 // Pass thru 00064 inline bool group_empty() { return Members.empty(); } 00065 inline NIIterator group_begin() { return Members.begin(); } 00066 inline NIIterator group_end() { return Members.end(); } 00067 inline void group_push_back(const NodeInfoPtr &NI) { 00068 Members.push_back(NI); 00069 } 00070 inline NIIterator group_insert(NIIterator Pos, const NodeInfoPtr &NI) { 00071 return Members.insert(Pos, NI); 00072 } 00073 inline void group_insert(NIIterator Pos, NIIterator First, 00074 NIIterator Last) { 00075 Members.insert(Pos, First, Last); 00076 } 00077 00078 static void Add(NodeInfo *D, NodeInfo *U); 00079 }; 00080 00081 //===--------------------------------------------------------------------===// 00082 /// 00083 /// NodeInfo - This struct tracks information used to schedule the a node. 00084 /// 00085 class NodeInfo { 00086 private: 00087 int Pending; // Number of visits pending before 00088 // adding to order 00089 public: 00090 SDNode *Node; // DAG node 00091 InstrStage *StageBegin; // First stage in itinerary 00092 InstrStage *StageEnd; // Last+1 stage in itinerary 00093 unsigned Latency; // Total cycles to complete instr 00094 bool IsCall : 1; // Is function call 00095 bool IsLoad : 1; // Is memory load 00096 bool IsStore : 1; // Is memory store 00097 unsigned Slot; // Node's time slot 00098 NodeGroup *Group; // Grouping information 00099 #ifndef NDEBUG 00100 unsigned Preorder; // Index before scheduling 00101 #endif 00102 00103 // Ctor. 00104 NodeInfo(SDNode *N = NULL) 00105 : Pending(0) 00106 , Node(N) 00107 , StageBegin(NULL) 00108 , StageEnd(NULL) 00109 , Latency(0) 00110 , IsCall(false) 00111 , Slot(0) 00112 , Group(NULL) 00113 #ifndef NDEBUG 00114 , Preorder(0) 00115 #endif 00116 {} 00117 00118 // Accessors 00119 inline bool isInGroup() const { 00120 assert(!Group || !Group->group_empty() && "Group with no members"); 00121 return Group != NULL; 00122 } 00123 inline bool isGroupDominator() const { 00124 return isInGroup() && Group->getDominator() == this; 00125 } 00126 inline int getPending() const { 00127 return Group ? Group->getPending() : Pending; 00128 } 00129 inline void setPending(int P) { 00130 if (Group) Group->setPending(P); 00131 else Pending = P; 00132 } 00133 inline int addPending(int I) { 00134 if (Group) return Group->addPending(I); 00135 else return Pending += I; 00136 } 00137 }; 00138 00139 //===--------------------------------------------------------------------===// 00140 /// 00141 /// NodeGroupIterator - Iterates over all the nodes indicated by the node 00142 /// info. If the node is in a group then iterate over the members of the 00143 /// group, otherwise just the node info. 00144 /// 00145 class NodeGroupIterator { 00146 private: 00147 NodeInfo *NI; // Node info 00148 NIIterator NGI; // Node group iterator 00149 NIIterator NGE; // Node group iterator end 00150 00151 public: 00152 // Ctor. 00153 NodeGroupIterator(NodeInfo *N) : NI(N) { 00154 // If the node is in a group then set up the group iterator. Otherwise 00155 // the group iterators will trip first time out. 00156 if (N->isInGroup()) { 00157 // get Group 00158 NodeGroup *Group = NI->Group; 00159 NGI = Group->group_begin(); 00160 NGE = Group->group_end(); 00161 // Prevent this node from being used (will be in members list 00162 NI = NULL; 00163 } 00164 } 00165 00166 /// next - Return the next node info, otherwise NULL. 00167 /// 00168 NodeInfo *next() { 00169 // If members list 00170 if (NGI != NGE) return *NGI++; 00171 // Use node as the result (may be NULL) 00172 NodeInfo *Result = NI; 00173 // Only use once 00174 NI = NULL; 00175 // Return node or NULL 00176 return Result; 00177 } 00178 }; 00179 //===--------------------------------------------------------------------===// 00180 00181 00182 //===--------------------------------------------------------------------===// 00183 /// 00184 /// NodeGroupOpIterator - Iterates over all the operands of a node. If the 00185 /// node is a member of a group, this iterates over all the operands of all 00186 /// the members of the group. 00187 /// 00188 class NodeGroupOpIterator { 00189 private: 00190 NodeInfo *NI; // Node containing operands 00191 NodeGroupIterator GI; // Node group iterator 00192 SDNode::op_iterator OI; // Operand iterator 00193 SDNode::op_iterator OE; // Operand iterator end 00194 00195 /// CheckNode - Test if node has more operands. If not get the next node 00196 /// skipping over nodes that have no operands. 00197 void CheckNode() { 00198 // Only if operands are exhausted first 00199 while (OI == OE) { 00200 // Get next node info 00201 NodeInfo *NI = GI.next(); 00202 // Exit if nodes are exhausted 00203 if (!NI) return; 00204 // Get node itself 00205 SDNode *Node = NI->Node; 00206 // Set up the operand iterators 00207 OI = Node->op_begin(); 00208 OE = Node->op_end(); 00209 } 00210 } 00211 00212 public: 00213 // Ctor. 00214 NodeGroupOpIterator(NodeInfo *N) 00215 : NI(N), GI(N), OI(SDNode::op_iterator()), OE(SDNode::op_iterator()) {} 00216 00217 /// isEnd - Returns true when not more operands are available. 00218 /// 00219 inline bool isEnd() { CheckNode(); return OI == OE; } 00220 00221 /// next - Returns the next available operand. 00222 /// 00223 inline SDOperand next() { 00224 assert(OI != OE && 00225 "Not checking for end of NodeGroupOpIterator correctly"); 00226 return *OI++; 00227 } 00228 }; 00229 00230 00231 //===----------------------------------------------------------------------===// 00232 /// 00233 /// BitsIterator - Provides iteration through individual bits in a bit vector. 00234 /// 00235 template<class T> 00236 class BitsIterator { 00237 private: 00238 T Bits; // Bits left to iterate through 00239 00240 public: 00241 /// Ctor. 00242 BitsIterator(T Initial) : Bits(Initial) {} 00243 00244 /// Next - Returns the next bit set or zero if exhausted. 00245 inline T Next() { 00246 // Get the rightmost bit set 00247 T Result = Bits & -Bits; 00248 // Remove from rest 00249 Bits &= ~Result; 00250 // Return single bit or zero 00251 return Result; 00252 } 00253 }; 00254 00255 //===----------------------------------------------------------------------===// 00256 00257 00258 //===----------------------------------------------------------------------===// 00259 /// 00260 /// ResourceTally - Manages the use of resources over time intervals. Each 00261 /// item (slot) in the tally vector represents the resources used at a given 00262 /// moment. A bit set to 1 indicates that a resource is in use, otherwise 00263 /// available. An assumption is made that the tally is large enough to schedule 00264 /// all current instructions (asserts otherwise.) 00265 /// 00266 template<class T> 00267 class ResourceTally { 00268 private: 00269 std::vector<T> Tally; // Resources used per slot 00270 typedef typename std::vector<T>::iterator Iter; 00271 // Tally iterator 00272 00273 /// SlotsAvailable - Returns true if all units are available. 00274 /// 00275 bool SlotsAvailable(Iter Begin, unsigned N, unsigned ResourceSet, 00276 unsigned &Resource) { 00277 assert(N && "Must check availability with N != 0"); 00278 // Determine end of interval 00279 Iter End = Begin + N; 00280 assert(End <= Tally.end() && "Tally is not large enough for schedule"); 00281 00282 // Iterate thru each resource 00283 BitsIterator<T> Resources(ResourceSet & ~*Begin); 00284 while (unsigned Res = Resources.Next()) { 00285 // Check if resource is available for next N slots 00286 Iter Interval = End; 00287 do { 00288 Interval--; 00289 if (*Interval & Res) break; 00290 } while (Interval != Begin); 00291 00292 // If available for N 00293 if (Interval == Begin) { 00294 // Success 00295 Resource = Res; 00296 return true; 00297 } 00298 } 00299 00300 // No luck 00301 Resource = 0; 00302 return false; 00303 } 00304 00305 /// RetrySlot - Finds a good candidate slot to retry search. 00306 Iter RetrySlot(Iter Begin, unsigned N, unsigned ResourceSet) { 00307 assert(N && "Must check availability with N != 0"); 00308 // Determine end of interval 00309 Iter End = Begin + N; 00310 assert(End <= Tally.end() && "Tally is not large enough for schedule"); 00311 00312 while (Begin != End--) { 00313 // Clear units in use 00314 ResourceSet &= ~*End; 00315 // If no units left then we should go no further 00316 if (!ResourceSet) return End + 1; 00317 } 00318 // Made it all the way through 00319 return Begin; 00320 } 00321 00322 /// FindAndReserveStages - Return true if the stages can be completed. If 00323 /// so mark as busy. 00324 bool FindAndReserveStages(Iter Begin, 00325 InstrStage *Stage, InstrStage *StageEnd) { 00326 // If at last stage then we're done 00327 if (Stage == StageEnd) return true; 00328 // Get number of cycles for current stage 00329 unsigned N = Stage->Cycles; 00330 // Check to see if N slots are available, if not fail 00331 unsigned Resource; 00332 if (!SlotsAvailable(Begin, N, Stage->Units, Resource)) return false; 00333 // Check to see if remaining stages are available, if not fail 00334 if (!FindAndReserveStages(Begin + N, Stage + 1, StageEnd)) return false; 00335 // Reserve resource 00336 Reserve(Begin, N, Resource); 00337 // Success 00338 return true; 00339 } 00340 00341 /// Reserve - Mark busy (set) the specified N slots. 00342 void Reserve(Iter Begin, unsigned N, unsigned Resource) { 00343 // Determine end of interval 00344 Iter End = Begin + N; 00345 assert(End <= Tally.end() && "Tally is not large enough for schedule"); 00346 00347 // Set resource bit in each slot 00348 for (; Begin < End; Begin++) 00349 *Begin |= Resource; 00350 } 00351 00352 /// FindSlots - Starting from Begin, locate consecutive slots where all stages 00353 /// can be completed. Returns the address of first slot. 00354 Iter FindSlots(Iter Begin, InstrStage *StageBegin, InstrStage *StageEnd) { 00355 // Track position 00356 Iter Cursor = Begin; 00357 00358 // Try all possible slots forward 00359 while (true) { 00360 // Try at cursor, if successful return position. 00361 if (FindAndReserveStages(Cursor, StageBegin, StageEnd)) return Cursor; 00362 // Locate a better position 00363 Cursor = RetrySlot(Cursor + 1, StageBegin->Cycles, StageBegin->Units); 00364 } 00365 } 00366 00367 public: 00368 /// Initialize - Resize and zero the tally to the specified number of time 00369 /// slots. 00370 inline void Initialize(unsigned N) { 00371 Tally.assign(N, 0); // Initialize tally to all zeros. 00372 } 00373 00374 // FindAndReserve - Locate an ideal slot for the specified stages and mark 00375 // as busy. 00376 unsigned FindAndReserve(unsigned Slot, InstrStage *StageBegin, 00377 InstrStage *StageEnd) { 00378 // Where to begin 00379 Iter Begin = Tally.begin() + Slot; 00380 // Find a free slot 00381 Iter Where = FindSlots(Begin, StageBegin, StageEnd); 00382 // Distance is slot number 00383 unsigned Final = Where - Tally.begin(); 00384 return Final; 00385 } 00386 00387 }; 00388 00389 //===----------------------------------------------------------------------===// 00390 /// 00391 /// ScheduleDAGSimple - Simple two pass scheduler. 00392 /// 00393 class VISIBILITY_HIDDEN ScheduleDAGSimple : public ScheduleDAG { 00394 private: 00395 bool NoSched; // Just do a BFS schedule, nothing fancy 00396 bool NoItins; // Don't use itineraries? 00397 ResourceTally<unsigned> Tally; // Resource usage tally 00398 unsigned NSlots; // Total latency 00399 static const unsigned NotFound = ~0U; // Search marker 00400 00401 unsigned NodeCount; // Number of nodes in DAG 00402 std::map<SDNode *, NodeInfo *> Map; // Map nodes to info 00403 bool HasGroups; // True if there are any groups 00404 NodeInfo *Info; // Info for nodes being scheduled 00405 NIVector Ordering; // Emit ordering of nodes 00406 NodeGroup *HeadNG, *TailNG; // Keep track of allocated NodeGroups 00407 00408 public: 00409 00410 // Ctor. 00411 ScheduleDAGSimple(bool noSched, bool noItins, SelectionDAG &dag, 00412 MachineBasicBlock *bb, const TargetMachine &tm) 00413 : ScheduleDAG(dag, bb, tm), NoSched(noSched), NoItins(noItins), NSlots(0), 00414 NodeCount(0), HasGroups(false), Info(NULL), HeadNG(NULL), TailNG(NULL) { 00415 assert(&TII && "Target doesn't provide instr info?"); 00416 assert(&MRI && "Target doesn't provide register info?"); 00417 } 00418 00419 virtual ~ScheduleDAGSimple() { 00420 if (Info) 00421 delete[] Info; 00422 00423 NodeGroup *NG = HeadNG; 00424 while (NG) { 00425 NodeGroup *NextSU = NG->Next; 00426 delete NG; 00427 NG = NextSU; 00428 } 00429 } 00430 00431 void Schedule(); 00432 00433 /// getNI - Returns the node info for the specified node. 00434 /// 00435 NodeInfo *getNI(SDNode *Node) { return Map[Node]; } 00436 00437 private: 00438 static bool isDefiner(NodeInfo *A, NodeInfo *B); 00439 void IncludeNode(NodeInfo *NI); 00440 void VisitAll(); 00441 void GatherSchedulingInfo(); 00442 void FakeGroupDominators(); 00443 bool isStrongDependency(NodeInfo *A, NodeInfo *B); 00444 bool isWeakDependency(NodeInfo *A, NodeInfo *B); 00445 void ScheduleBackward(); 00446 void ScheduleForward(); 00447 00448 void AddToGroup(NodeInfo *D, NodeInfo *U); 00449 /// PrepareNodeInfo - Set up the basic minimum node info for scheduling. 00450 /// 00451 void PrepareNodeInfo(); 00452 00453 /// IdentifyGroups - Put flagged nodes into groups. 00454 /// 00455 void IdentifyGroups(); 00456 00457 /// print - Print ordering to specified output stream. 00458 /// 00459 void print(std::ostream &O) const; 00460 00461 void dump(const char *tag) const; 00462 00463 virtual void dump() const; 00464 00465 /// EmitAll - Emit all nodes in schedule sorted order. 00466 /// 00467 void EmitAll(); 00468 00469 /// printNI - Print node info. 00470 /// 00471 void printNI(std::ostream &O, NodeInfo *NI) const; 00472 00473 /// printChanges - Hilight changes in order caused by scheduling. 00474 /// 00475 void printChanges(unsigned Index) const; 00476 }; 00477 00478 //===----------------------------------------------------------------------===// 00479 /// Special case itineraries. 00480 /// 00481 enum { 00482 CallLatency = 40, // To push calls back in time 00483 00484 RSInteger = 0xC0000000, // Two integer units 00485 RSFloat = 0x30000000, // Two float units 00486 RSLoadStore = 0x0C000000, // Two load store units 00487 RSBranch = 0x02000000 // One branch unit 00488 }; 00489 static InstrStage CallStage = { CallLatency, RSBranch }; 00490 static InstrStage LoadStage = { 5, RSLoadStore }; 00491 static InstrStage StoreStage = { 2, RSLoadStore }; 00492 static InstrStage IntStage = { 2, RSInteger }; 00493 static InstrStage FloatStage = { 3, RSFloat }; 00494 //===----------------------------------------------------------------------===// 00495 00496 } // namespace 00497 00498 //===----------------------------------------------------------------------===// 00499 00500 /// PrepareNodeInfo - Set up the basic minimum node info for scheduling. 00501 /// 00502 void ScheduleDAGSimple::PrepareNodeInfo() { 00503 // Allocate node information 00504 Info = new NodeInfo[NodeCount]; 00505 00506 unsigned i = 0; 00507 for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), 00508 E = DAG.allnodes_end(); I != E; ++I, ++i) { 00509 // Fast reference to node schedule info 00510 NodeInfo* NI = &Info[i]; 00511 // Set up map 00512 Map[I] = NI; 00513 // Set node 00514 NI->Node = I; 00515 // Set pending visit count 00516 NI->setPending(I->use_size()); 00517 } 00518 } 00519 00520 /// IdentifyGroups - Put flagged nodes into groups. 00521 /// 00522 void ScheduleDAGSimple::IdentifyGroups() { 00523 for (unsigned i = 0, N = NodeCount; i < N; i++) { 00524 NodeInfo* NI = &Info[i]; 00525 SDNode *Node = NI->Node; 00526 00527 // For each operand (in reverse to only look at flags) 00528 for (unsigned N = Node->getNumOperands(); 0 < N--;) { 00529 // Get operand 00530 SDOperand Op = Node->getOperand(N); 00531 // No more flags to walk 00532 if (Op.getValueType() != MVT::Flag) break; 00533 // Add to node group 00534 AddToGroup(getNI(Op.Val), NI); 00535 // Let everyone else know 00536 HasGroups = true; 00537 } 00538 } 00539 } 00540 00541 /// CountInternalUses - Returns the number of edges between the two nodes. 00542 /// 00543 static unsigned CountInternalUses(NodeInfo *D, NodeInfo *U) { 00544 unsigned N = 0; 00545 for (unsigned M = U->Node->getNumOperands(); 0 < M--;) { 00546 SDOperand Op = U->Node->getOperand(M); 00547 if (Op.Val == D->Node) N++; 00548 } 00549 00550 return N; 00551 } 00552 00553 //===----------------------------------------------------------------------===// 00554 /// Add - Adds a definer and user pair to a node group. 00555 /// 00556 void ScheduleDAGSimple::AddToGroup(NodeInfo *D, NodeInfo *U) { 00557 // Get current groups 00558 NodeGroup *DGroup = D->Group; 00559 NodeGroup *UGroup = U->Group; 00560 // If both are members of groups 00561 if (DGroup && UGroup) { 00562 // There may have been another edge connecting 00563 if (DGroup == UGroup) return; 00564 // Add the pending users count 00565 DGroup->addPending(UGroup->getPending()); 00566 // For each member of the users group 00567 NodeGroupIterator UNGI(U); 00568 while (NodeInfo *UNI = UNGI.next() ) { 00569 // Change the group 00570 UNI->Group = DGroup; 00571 // For each member of the definers group 00572 NodeGroupIterator DNGI(D); 00573 while (NodeInfo *DNI = DNGI.next() ) { 00574 // Remove internal edges 00575 DGroup->addPending(-CountInternalUses(DNI, UNI)); 00576 } 00577 } 00578 // Merge the two lists 00579 DGroup->group_insert(DGroup->group_end(), 00580 UGroup->group_begin(), UGroup->group_end()); 00581 } else if (DGroup) { 00582 // Make user member of definers group 00583 U->Group = DGroup; 00584 // Add users uses to definers group pending 00585 DGroup->addPending(U->Node->use_size()); 00586 // For each member of the definers group 00587 NodeGroupIterator DNGI(D); 00588 while (NodeInfo *DNI = DNGI.next() ) { 00589 // Remove internal edges 00590 DGroup->addPending(-CountInternalUses(DNI, U)); 00591 } 00592 DGroup->group_push_back(U); 00593 } else if (UGroup) { 00594 // Make definer member of users group 00595 D->Group = UGroup; 00596 // Add definers uses to users group pending 00597 UGroup->addPending(D->Node->use_size()); 00598 // For each member of the users group 00599 NodeGroupIterator UNGI(U); 00600 while (NodeInfo *UNI = UNGI.next() ) { 00601 // Remove internal edges 00602 UGroup->addPending(-CountInternalUses(D, UNI)); 00603 } 00604 UGroup->group_insert(UGroup->group_begin(), D); 00605 } else { 00606 D->Group = U->Group = DGroup = new NodeGroup(); 00607 DGroup->addPending(D->Node->use_size() + U->Node->use_size() - 00608 CountInternalUses(D, U)); 00609 DGroup->group_push_back(D); 00610 DGroup->group_push_back(U); 00611 00612 if (HeadNG == NULL) 00613 HeadNG = DGroup; 00614 if (TailNG != NULL) 00615 TailNG->Next = DGroup; 00616 TailNG = DGroup; 00617 } 00618 } 00619 00620 00621 /// print - Print ordering to specified output stream. 00622 /// 00623 void ScheduleDAGSimple::print(std::ostream &O) const { 00624 #ifndef NDEBUG 00625 O << "Ordering\n"; 00626 for (unsigned i = 0, N = Ordering.size(); i < N; i++) { 00627 NodeInfo *NI = Ordering[i]; 00628 printNI(O, NI); 00629 O << "\n"; 00630 if (NI->isGroupDominator()) { 00631 NodeGroup *Group = NI->Group; 00632 for (NIIterator NII = Group->group_begin(), E = Group->group_end(); 00633 NII != E; NII++) { 00634 O << " "; 00635 printNI(O, *NII); 00636 O << "\n"; 00637 } 00638 } 00639 } 00640 #endif 00641 } 00642 00643 void ScheduleDAGSimple::dump(const char *tag) const { 00644 std::cerr << tag; dump(); 00645 } 00646 00647 void ScheduleDAGSimple::dump() const { 00648 print(std::cerr); 00649 } 00650 00651 00652 /// EmitAll - Emit all nodes in schedule sorted order. 00653 /// 00654 void ScheduleDAGSimple::EmitAll() { 00655 std::map<SDNode*, unsigned> VRBaseMap; 00656 00657 // For each node in the ordering 00658 for (unsigned i = 0, N = Ordering.size(); i < N; i++) { 00659 // Get the scheduling info 00660 NodeInfo *NI = Ordering[i]; 00661 if (NI->isInGroup()) { 00662 NodeGroupIterator NGI(Ordering[i]); 00663 while (NodeInfo *NI = NGI.next()) EmitNode(NI->Node, VRBaseMap); 00664 } else { 00665 EmitNode(NI->Node, VRBaseMap); 00666 } 00667 } 00668 } 00669 00670 /// isFlagDefiner - Returns true if the node defines a flag result. 00671 static bool isFlagDefiner(SDNode *A) { 00672 unsigned N = A->getNumValues(); 00673 return N && A->getValueType(N - 1) == MVT::Flag; 00674 } 00675 00676 /// isFlagUser - Returns true if the node uses a flag result. 00677 /// 00678 static bool isFlagUser(SDNode *A) { 00679 unsigned N = A->getNumOperands(); 00680 return N && A->getOperand(N - 1).getValueType() == MVT::Flag; 00681 } 00682 00683 /// printNI - Print node info. 00684 /// 00685 void ScheduleDAGSimple::printNI(std::ostream &O, NodeInfo *NI) const { 00686 #ifndef NDEBUG 00687 SDNode *Node = NI->Node; 00688 O << " " 00689 << std::hex << Node << std::dec 00690 << ", Lat=" << NI->Latency 00691 << ", Slot=" << NI->Slot 00692 << ", ARITY=(" << Node->getNumOperands() << "," 00693 << Node->getNumValues() << ")" 00694 << " " << Node->getOperationName(&DAG); 00695 if (isFlagDefiner(Node)) O << "<#"; 00696 if (isFlagUser(Node)) O << ">#"; 00697 #endif 00698 } 00699 00700 /// printChanges - Hilight changes in order caused by scheduling. 00701 /// 00702 void ScheduleDAGSimple::printChanges(unsigned Index) const { 00703 #ifndef NDEBUG 00704 // Get the ordered node count 00705 unsigned N = Ordering.size(); 00706 // Determine if any changes 00707 unsigned i = 0; 00708 for (; i < N; i++) { 00709 NodeInfo *NI = Ordering[i]; 00710 if (NI->Preorder != i) break; 00711 } 00712 00713 if (i < N) { 00714 std::cerr << Index << ". New Ordering\n"; 00715 00716 for (i = 0; i < N; i++) { 00717 NodeInfo *NI = Ordering[i]; 00718 std::cerr << " " << NI->Preorder << ". "; 00719 printNI(std::cerr, NI); 00720 std::cerr << "\n"; 00721 if (NI->isGroupDominator()) { 00722 NodeGroup *Group = NI->Group; 00723 for (NIIterator NII = Group->group_begin(), E = Group->group_end(); 00724 NII != E; NII++) { 00725 std::cerr << " "; 00726 printNI(std::cerr, *NII); 00727 std::cerr << "\n"; 00728 } 00729 } 00730 } 00731 } else { 00732 std::cerr << Index << ". No Changes\n"; 00733 } 00734 #endif 00735 } 00736 00737 //===----------------------------------------------------------------------===// 00738 /// isDefiner - Return true if node A is a definer for B. 00739 /// 00740 bool ScheduleDAGSimple::isDefiner(NodeInfo *A, NodeInfo *B) { 00741 // While there are A nodes 00742 NodeGroupIterator NII(A); 00743 while (NodeInfo *NI = NII.next()) { 00744 // Extract node 00745 SDNode *Node = NI->Node; 00746 // While there operands in nodes of B 00747 NodeGroupOpIterator NGOI(B); 00748 while (!NGOI.isEnd()) { 00749 SDOperand Op = NGOI.next(); 00750 // If node from A defines a node in B 00751 if (Node == Op.Val) return true; 00752 } 00753 } 00754 return false; 00755 } 00756 00757 /// IncludeNode - Add node to NodeInfo vector. 00758 /// 00759 void ScheduleDAGSimple::IncludeNode(NodeInfo *NI) { 00760 // Get node 00761 SDNode *Node = NI->Node; 00762 // Ignore entry node 00763 if (Node->getOpcode() == ISD::EntryToken) return; 00764 // Check current count for node 00765 int Count = NI->getPending(); 00766 // If the node is already in list 00767 if (Count < 0) return; 00768 // Decrement count to indicate a visit 00769 Count--; 00770 // If count has gone to zero then add node to list 00771 if (!Count) { 00772 // Add node 00773 if (NI->isInGroup()) { 00774 Ordering.push_back(NI->Group->getDominator()); 00775 } else { 00776 Ordering.push_back(NI); 00777 } 00778 // indicate node has been added 00779 Count--; 00780 } 00781 // Mark as visited with new count 00782 NI->setPending(Count); 00783 } 00784 00785 /// GatherSchedulingInfo - Get latency and resource information about each node. 00786 /// 00787 void ScheduleDAGSimple::GatherSchedulingInfo() { 00788 // Get instruction itineraries for the target 00789 const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); 00790 00791 // For each node 00792 for (unsigned i = 0, N = NodeCount; i < N; i++) { 00793 // Get node info 00794 NodeInfo* NI = &Info[i]; 00795 SDNode *Node = NI->Node; 00796 00797 // If there are itineraries and it is a machine instruction 00798 if (InstrItins.isEmpty() || NoItins) { 00799 // If machine opcode 00800 if (Node->isTargetOpcode()) { 00801 // Get return type to guess which processing unit 00802 MVT::ValueType VT = Node->getValueType(0); 00803 // Get machine opcode 00804 MachineOpCode TOpc = Node->getTargetOpcode(); 00805 NI->IsCall = TII->isCall(TOpc); 00806 NI->IsLoad = TII->isLoad(TOpc); 00807 NI->IsStore = TII->isStore(TOpc); 00808 00809 if (TII->isLoad(TOpc)) NI->StageBegin = &LoadStage; 00810 else if (TII->isStore(TOpc)) NI->StageBegin = &StoreStage; 00811 else if (MVT::isInteger(VT)) NI->StageBegin = &IntStage; 00812 else if (MVT::isFloatingPoint(VT)) NI->StageBegin = &FloatStage; 00813 if (NI->StageBegin) NI->StageEnd = NI->StageBegin + 1; 00814 } 00815 } else if (Node->isTargetOpcode()) { 00816 // get machine opcode 00817 MachineOpCode TOpc = Node->getTargetOpcode(); 00818 // Check to see if it is a call 00819 NI->IsCall = TII->isCall(TOpc); 00820 // Get itinerary stages for instruction 00821 unsigned II = TII->getSchedClass(TOpc); 00822 NI->StageBegin = InstrItins.begin(II); 00823 NI->StageEnd = InstrItins.end(II); 00824 } 00825 00826 // One slot for the instruction itself 00827 NI->Latency = 1; 00828 00829 // Add long latency for a call to push it back in time 00830 if (NI->IsCall) NI->Latency += CallLatency; 00831 00832 // Sum up all the latencies 00833 for (InstrStage *Stage = NI->StageBegin, *E = NI->StageEnd; 00834 Stage != E; Stage++) { 00835 NI->Latency += Stage->Cycles; 00836 } 00837 00838 // Sum up all the latencies for max tally size 00839 NSlots += NI->Latency; 00840 } 00841 00842 // Unify metrics if in a group 00843 if (HasGroups) { 00844 for (unsigned i = 0, N = NodeCount; i < N; i++) { 00845 NodeInfo* NI = &Info[i]; 00846 00847 if (NI->isInGroup()) { 00848 NodeGroup *Group = NI->Group; 00849 00850 if (!Group->getDominator()) { 00851 NIIterator NGI = Group->group_begin(), NGE = Group->group_end(); 00852 NodeInfo *Dominator = *NGI; 00853 unsigned Latency = 0; 00854 00855 for (NGI++; NGI != NGE; NGI++) { 00856 NodeInfo* NGNI = *NGI; 00857 Latency += NGNI->Latency; 00858 if (Dominator->Latency < NGNI->Latency) Dominator = NGNI; 00859 } 00860 00861 Dominator->Latency = Latency; 00862 Group->setDominator(Dominator); 00863 } 00864 } 00865 } 00866 } 00867 } 00868 00869 /// VisitAll - Visit each node breadth-wise to produce an initial ordering. 00870 /// Note that the ordering in the Nodes vector is reversed. 00871 void ScheduleDAGSimple::VisitAll() { 00872 // Add first element to list 00873 NodeInfo *NI = getNI(DAG.getRoot().Val); 00874 if (NI->isInGroup()) { 00875 Ordering.push_back(NI->Group->getDominator()); 00876 } else { 00877 Ordering.push_back(NI); 00878 } 00879 00880 // Iterate through all nodes that have been added 00881 for (unsigned i = 0; i < Ordering.size(); i++) { // note: size() varies 00882 // Visit all operands 00883 NodeGroupOpIterator NGI(Ordering[i]); 00884 while (!NGI.isEnd()) { 00885 // Get next operand 00886 SDOperand Op = NGI.next(); 00887 // Get node 00888 SDNode *Node = Op.Val; 00889 // Ignore passive nodes 00890 if (isPassiveNode(Node)) continue; 00891 // Check out node 00892 IncludeNode(getNI(Node)); 00893 } 00894 } 00895 00896 // Add entry node last (IncludeNode filters entry nodes) 00897 if (DAG.getEntryNode().Val != DAG.getRoot().Val) 00898 Ordering.push_back(getNI(DAG.getEntryNode().Val)); 00899 00900 // Reverse the order 00901 std::reverse(Ordering.begin(), Ordering.end()); 00902 } 00903 00904 /// FakeGroupDominators - Set dominators for non-scheduling. 00905 /// 00906 void ScheduleDAGSimple::FakeGroupDominators() { 00907 for (unsigned i = 0, N = NodeCount; i < N; i++) { 00908 NodeInfo* NI = &Info[i]; 00909 00910 if (NI->isInGroup()) { 00911 NodeGroup *Group = NI->Group; 00912 00913 if (!Group->getDominator()) { 00914 Group->setDominator(NI); 00915 } 00916 } 00917 } 00918 } 00919 00920 /// isStrongDependency - Return true if node A has results used by node B. 00921 /// I.E., B must wait for latency of A. 00922 bool ScheduleDAGSimple::isStrongDependency(NodeInfo *A, NodeInfo *B) { 00923 // If A defines for B then it's a strong dependency or 00924 // if a load follows a store (may be dependent but why take a chance.) 00925 return isDefiner(A, B) || (A->IsStore && B->IsLoad); 00926 } 00927 00928 /// isWeakDependency Return true if node A produces a result that will 00929 /// conflict with operands of B. It is assumed that we have called 00930 /// isStrongDependency prior. 00931 bool ScheduleDAGSimple::isWeakDependency(NodeInfo *A, NodeInfo *B) { 00932 // TODO check for conflicting real registers and aliases 00933 #if 0 // FIXME - Since we are in SSA form and not checking register aliasing 00934 return A->Node->getOpcode() == ISD::EntryToken || isStrongDependency(B, A); 00935 #else 00936 return A->Node->getOpcode() == ISD::EntryToken; 00937 #endif 00938 } 00939 00940 /// ScheduleBackward - Schedule instructions so that any long latency 00941 /// instructions and the critical path get pushed back in time. Time is run in 00942 /// reverse to allow code reuse of the Tally and eliminate the overhead of 00943 /// biasing every slot indices against NSlots. 00944 void ScheduleDAGSimple::ScheduleBackward() { 00945 // Size and clear the resource tally 00946 Tally.Initialize(NSlots); 00947 // Get number of nodes to schedule 00948 unsigned N = Ordering.size(); 00949 00950 // For each node being scheduled 00951 for (unsigned i = N; 0 < i--;) { 00952 NodeInfo *NI = Ordering[i]; 00953 // Track insertion 00954 unsigned Slot = NotFound; 00955 00956 // Compare against those previously scheduled nodes 00957 unsigned j = i + 1; 00958 for (; j < N; j++) { 00959 // Get following instruction 00960 NodeInfo *Other = Ordering[j]; 00961 00962 // Check dependency against previously inserted nodes 00963 if (isStrongDependency(NI, Other)) { 00964 Slot = Other->Slot + Other->Latency; 00965 break; 00966 } else if (isWeakDependency(NI, Other)) { 00967 Slot = Other->Slot; 00968 break; 00969 } 00970 } 00971 00972 // If independent of others (or first entry) 00973 if (Slot == NotFound) Slot = 0; 00974 00975 #if 0 // FIXME - measure later 00976 // Find a slot where the needed resources are available 00977 if (NI->StageBegin != NI->StageEnd) 00978 Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd); 00979 #endif 00980 00981 // Set node slot 00982 NI->Slot = Slot; 00983 00984 // Insert sort based on slot 00985 j = i + 1; 00986 for (; j < N; j++) { 00987 // Get following instruction 00988 NodeInfo *Other = Ordering[j]; 00989 // Should we look further (remember slots are in reverse time) 00990 if (Slot >= Other->Slot) break; 00991 // Shuffle other into ordering 00992 Ordering[j - 1] = Other; 00993 } 00994 // Insert node in proper slot 00995 if (j != i + 1) Ordering[j - 1] = NI; 00996 } 00997 } 00998 00999 /// ScheduleForward - Schedule instructions to maximize packing. 01000 /// 01001 void ScheduleDAGSimple::ScheduleForward() { 01002 // Size and clear the resource tally 01003 Tally.Initialize(NSlots); 01004 // Get number of nodes to schedule 01005 unsigned N = Ordering.size(); 01006 01007 // For each node being scheduled 01008 for (unsigned i = 0; i < N; i++) { 01009 NodeInfo *NI = Ordering[i]; 01010 // Track insertion 01011 unsigned Slot = NotFound; 01012 01013 // Compare against those previously scheduled nodes 01014 unsigned j = i; 01015 for (; 0 < j--;) { 01016 // Get following instruction 01017 NodeInfo *Other = Ordering[j]; 01018 01019 // Check dependency against previously inserted nodes 01020 if (isStrongDependency(Other, NI)) { 01021 Slot = Other->Slot + Other->Latency; 01022 break; 01023 } else if (Other->IsCall || isWeakDependency(Other, NI)) { 01024 Slot = Other->Slot; 01025 break; 01026 } 01027 } 01028 01029 // If independent of others (or first entry) 01030 if (Slot == NotFound) Slot = 0; 01031 01032 // Find a slot where the needed resources are available 01033 if (NI->StageBegin != NI->StageEnd) 01034 Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd); 01035 01036 // Set node slot 01037 NI->Slot = Slot; 01038 01039 // Insert sort based on slot 01040 j = i; 01041 for (; 0 < j--;) { 01042 // Get prior instruction 01043 NodeInfo *Other = Ordering[j]; 01044 // Should we look further 01045 if (Slot >= Other->Slot) break; 01046 // Shuffle other into ordering 01047 Ordering[j + 1] = Other; 01048 } 01049 // Insert node in proper slot 01050 if (j != i) Ordering[j + 1] = NI; 01051 } 01052 } 01053 01054 /// Schedule - Order nodes according to selected style. 01055 /// 01056 void ScheduleDAGSimple::Schedule() { 01057 // Number the nodes 01058 NodeCount = std::distance(DAG.allnodes_begin(), DAG.allnodes_end()); 01059 01060 // Set up minimum info for scheduling 01061 PrepareNodeInfo(); 01062 // Construct node groups for flagged nodes 01063 IdentifyGroups(); 01064 01065 // Test to see if scheduling should occur 01066 bool ShouldSchedule = NodeCount > 3 && !NoSched; 01067 // Don't waste time if is only entry and return 01068 if (ShouldSchedule) { 01069 // Get latency and resource requirements 01070 GatherSchedulingInfo(); 01071 } else if (HasGroups) { 01072 // Make sure all the groups have dominators 01073 FakeGroupDominators(); 01074 } 01075 01076 // Breadth first walk of DAG 01077 VisitAll(); 01078 01079 #ifndef NDEBUG 01080 static unsigned Count = 0; 01081 Count++; 01082 for (unsigned i = 0, N = Ordering.size(); i < N; i++) { 01083 NodeInfo *NI = Ordering[i]; 01084 NI->Preorder = i; 01085 } 01086 #endif 01087 01088 // Don't waste time if is only entry and return 01089 if (ShouldSchedule) { 01090 // Push back long instructions and critical path 01091 ScheduleBackward(); 01092 01093 // Pack instructions to maximize resource utilization 01094 ScheduleForward(); 01095 } 01096 01097 DEBUG(printChanges(Count)); 01098 01099 // Emit in scheduled order 01100 EmitAll(); 01101 } 01102 01103 01104 /// createSimpleDAGScheduler - This creates a simple two pass instruction 01105 /// scheduler. 01106 llvm::ScheduleDAG* llvm::createSimpleDAGScheduler(bool NoItins, 01107 SelectionDAG &DAG, 01108 MachineBasicBlock *BB) { 01109 return new ScheduleDAGSimple(false, NoItins, DAG, BB, DAG.getTarget()); 01110 } 01111 01112 llvm::ScheduleDAG* llvm::createBFS_DAGScheduler(SelectionDAG &DAG, 01113 MachineBasicBlock *BB) { 01114 return new ScheduleDAGSimple(true, false, DAG, BB, DAG.getTarget()); 01115 }