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