LLVM API Documentation

ScheduleDAGSimple.cpp

Go to the documentation of this file.
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 }