lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp

   1 //===-- ScheduleDAGSimple.cpp - Implement a trivial DAG scheduler ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by James M. Laskey and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements a simple two pass scheduler.  The first pass attempts to push
  11 // backward any lengthy instructions and critical paths.  The second pass packs
  12 // instructions into semi-optimal time slots.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "sched"
  17 #include "llvm/CodeGen/ScheduleDAG.h"
  18 #include "llvm/CodeGen/SelectionDAG.h"
  19 #include "llvm/Target/TargetMachine.h"
  20 #include "llvm/Target/TargetInstrInfo.h"
  21 #include "llvm/Support/Debug.h"
  22 #include <algorithm>
  23 #include <iostream>
  24 using namespace llvm;
  25
  26 namespace {
  27 class NodeInfo;
  28 typedef NodeInfo *NodeInfoPtr;
  29 typedef std::vector<NodeInfoPtr>           NIVector;
  30 typedef std::vector<NodeInfoPtr>::iterator NIIterator;
  31
  32 //===--------------------------------------------------------------------===//
  33 ///
  34 /// Node group -  This struct is used to manage flagged node groups.
  35 ///
  36 class NodeGroup {
  37 public:
  38   NodeGroup     *Next;
  39 private:
  40   NIVector      Members;                // Group member nodes
  41   NodeInfo      *Dominator;             // Node with highest latency
  42   unsigned      Latency;                // Total latency of the group
  43   int           Pending;                // Number of visits pending before
  44                                         // adding to order
  45
  46 public:
  47   // Ctor.
  48   NodeGroup() : Next(NULL), Dominator(NULL), Pending(0) {}
  49
  50   // Accessors
  51   inline void setDominator(NodeInfo *D) { Dominator = D; }
  52   inline NodeInfo *getTop() { return Members.front(); }
  53   inline NodeInfo *getBottom() { return Members.back(); }
  54   inline NodeInfo *getDominator() { return Dominator; }
  55   inline void setLatency(unsigned L) { Latency = L; }
  56   inline unsigned getLatency() { return Latency; }
  57   inline int getPending() const { return Pending; }
  58   inline void setPending(int P)  { Pending = P; }
  59   inline int addPending(int I)  { return Pending += I; }
  60
  61   // Pass thru
  62   inline bool group_empty() { return Members.empty(); }
  63   inline NIIterator group_begin() { return Members.begin(); }
  64   inline NIIterator group_end() { return Members.end(); }
  65   inline void group_push_back(const NodeInfoPtr &NI) {
  66     Members.push_back(NI);
  67   }
  68   inline NIIterator group_insert(NIIterator Pos, const NodeInfoPtr &NI) {
  69     return Members.insert(Pos, NI);
  70   }
  71   inline void group_insert(NIIterator Pos, NIIterator First,
  72                            NIIterator Last) {
  73     Members.insert(Pos, First, Last);
  74   }
  75
  76   static void Add(NodeInfo *D, NodeInfo *U);
  77 };
  78
  79 //===--------------------------------------------------------------------===//
  80 ///
  81 /// NodeInfo - This struct tracks information used to schedule the a node.
  82 ///
  83 class NodeInfo {
  84 private:
  85   int           Pending;                // Number of visits pending before
  86                                         // adding to order
  87 public:
  88   SDNode        *Node;                  // DAG node
  89   InstrStage    *StageBegin;            // First stage in itinerary
  90   InstrStage    *StageEnd;              // Last+1 stage in itinerary
  91   unsigned      Latency;                // Total cycles to complete instr
  92   bool          IsCall : 1;             // Is function call
  93   bool          IsLoad : 1;             // Is memory load
  94   bool          IsStore : 1;            // Is memory store
  95   unsigned      Slot;                   // Node's time slot
  96   NodeGroup     *Group;                 // Grouping information
  97 #ifndef NDEBUG
  98   unsigned      Preorder;               // Index before scheduling
  99 #endif
 100
 101   // Ctor.
 102   NodeInfo(SDNode *N = NULL)
 103     : Pending(0)
 104     , Node(N)
 105     , StageBegin(NULL)
 106     , StageEnd(NULL)
 107     , Latency(0)
 108     , IsCall(false)
 109     , Slot(0)
 110     , Group(NULL)
 111 #ifndef NDEBUG
 112     , Preorder(0)
 113 #endif
 114   {}
 115
 116   // Accessors
 117   inline bool isInGroup() const {
 118     assert(!Group || !Group->group_empty() && "Group with no members");
 119     return Group != NULL;
 120   }
 121   inline bool isGroupDominator() const {
 122     return isInGroup() && Group->getDominator() == this;
 123   }
 124   inline int getPending() const {
 125     return Group ? Group->getPending() : Pending;
 126   }
 127   inline void setPending(int P) {
 128     if (Group) Group->setPending(P);
 129     else       Pending = P;
 130   }
 131   inline int addPending(int I) {
 132     if (Group) return Group->addPending(I);
 133     else       return Pending += I;
 134   }
 135 };
 136
 137 //===--------------------------------------------------------------------===//
 138 ///
 139 /// NodeGroupIterator - Iterates over all the nodes indicated by the node
 140 /// info. If the node is in a group then iterate over the members of the
 141 /// group, otherwise just the node info.
 142 ///
 143 class NodeGroupIterator {
 144 private:
 145   NodeInfo   *NI;                       // Node info
 146   NIIterator NGI;                       // Node group iterator
 147   NIIterator NGE;                       // Node group iterator end
 148
 149 public:
 150   // Ctor.
 151   NodeGroupIterator(NodeInfo *N) : NI(N) {
 152     // If the node is in a group then set up the group iterator.  Otherwise
 153     // the group iterators will trip first time out.
 154     if (N->isInGroup()) {
 155       // get Group
 156       NodeGroup *Group = NI->Group;
 157       NGI = Group->group_begin();
 158       NGE = Group->group_end();
 159       // Prevent this node from being used (will be in members list
 160       NI = NULL;
 161     }
 162   }
 163
 164   /// next - Return the next node info, otherwise NULL.
 165   ///
 166   NodeInfo *next() {
 167     // If members list
 168     if (NGI != NGE) return *NGI++;
 169     // Use node as the result (may be NULL)
 170     NodeInfo *Result = NI;
 171     // Only use once
 172     NI = NULL;
 173     // Return node or NULL
 174     return Result;
 175   }
 176 };
 177 //===--------------------------------------------------------------------===//
 178
 179
 180 //===--------------------------------------------------------------------===//
 181 ///
 182 /// NodeGroupOpIterator - Iterates over all the operands of a node.  If the
 183 /// node is a member of a group, this iterates over all the operands of all
 184 /// the members of the group.
 185 ///
 186 class NodeGroupOpIterator {
 187 private:
 188   NodeInfo            *NI;              // Node containing operands
 189   NodeGroupIterator   GI;               // Node group iterator
 190   SDNode::op_iterator OI;               // Operand iterator
 191   SDNode::op_iterator OE;               // Operand iterator end
 192
 193   /// CheckNode - Test if node has more operands.  If not get the next node
 194   /// skipping over nodes that have no operands.
 195   void CheckNode() {
 196     // Only if operands are exhausted first
 197     while (OI == OE) {
 198       // Get next node info
 199       NodeInfo *NI = GI.next();
 200       // Exit if nodes are exhausted
 201       if (!NI) return;
 202       // Get node itself
 203       SDNode *Node = NI->Node;
 204       // Set up the operand iterators
 205       OI = Node->op_begin();
 206       OE = Node->op_end();
 207     }
 208   }
 209
 210 public:
 211   // Ctor.
 212   NodeGroupOpIterator(NodeInfo *N)
 213     : NI(N), GI(N), OI(SDNode::op_iterator()), OE(SDNode::op_iterator()) {}
 214
 215   /// isEnd - Returns true when not more operands are available.
 216   ///
 217   inline bool isEnd() { CheckNode(); return OI == OE; }
 218
 219   /// next - Returns the next available operand.
 220   ///
 221   inline SDOperand next() {
 222     assert(OI != OE &&
 223            "Not checking for end of NodeGroupOpIterator correctly");
 224     return *OI++;
 225   }
 226 };
 227
 228
 229 //===----------------------------------------------------------------------===//
 230 ///
 231 /// BitsIterator - Provides iteration through individual bits in a bit vector.
 232 ///
 233 template<class T>
 234 class BitsIterator {
 235 private:
 236   T Bits;                               // Bits left to iterate through
 237
 238 public:
 239   /// Ctor.
 240   BitsIterator(T Initial) : Bits(Initial) {}
 241
 242   /// Next - Returns the next bit set or zero if exhausted.
 243   inline T Next() {
 244     // Get the rightmost bit set
 245     T Result = Bits & -Bits;
 246     // Remove from rest
 247     Bits &= ~Result;
 248     // Return single bit or zero
 249     return Result;
 250   }
 251 };
 252
 253 //===----------------------------------------------------------------------===//
 254
 255
 256 //===----------------------------------------------------------------------===//
 257 ///
 258 /// ResourceTally - Manages the use of resources over time intervals.  Each
 259 /// item (slot) in the tally vector represents the resources used at a given
 260 /// moment.  A bit set to 1 indicates that a resource is in use, otherwise
 261 /// available.  An assumption is made that the tally is large enough to schedule
 262 /// all current instructions (asserts otherwise.)
 263 ///
 264 template<class T>
 265 class ResourceTally {
 266 private:
 267   std::vector<T> Tally;                 // Resources used per slot
 268   typedef typename std::vector<T>::iterator Iter;
 269                                         // Tally iterator
 270
 271   /// SlotsAvailable - Returns true if all units are available.
 272         ///
 273   bool SlotsAvailable(Iter Begin, unsigned N, unsigned ResourceSet,
 274                                               unsigned &Resource) {
 275     assert(N && "Must check availability with N != 0");
 276     // Determine end of interval
 277     Iter End = Begin + N;
 278     assert(End <= Tally.end() && "Tally is not large enough for schedule");
 279
 280     // Iterate thru each resource
 281     BitsIterator<T> Resources(ResourceSet & ~*Begin);
 282     while (unsigned Res = Resources.Next()) {
 283       // Check if resource is available for next N slots
 284       Iter Interval = End;
 285       do {
 286         Interval--;
 287         if (*Interval & Res) break;
 288       } while (Interval != Begin);
 289
 290       // If available for N
 291       if (Interval == Begin) {
 292         // Success
 293         Resource = Res;
 294         return true;
 295       }
 296     }
 297
 298     // No luck
 299     Resource = 0;
 300     return false;
 301   }
 302
 303         /// RetrySlot - Finds a good candidate slot to retry search.
 304   Iter RetrySlot(Iter Begin, unsigned N, unsigned ResourceSet) {
 305     assert(N && "Must check availability with N != 0");
 306     // Determine end of interval
 307     Iter End = Begin + N;
 308     assert(End <= Tally.end() && "Tally is not large enough for schedule");
 309
 310                 while (Begin != End--) {
 311                         // Clear units in use
 312                         ResourceSet &= ~*End;
 313                         // If no units left then we should go no further
 314                         if (!ResourceSet) return End + 1;
 315                 }
 316                 // Made it all the way through
 317                 return Begin;
 318         }
 319
 320   /// FindAndReserveStages - Return true if the stages can be completed. If
 321   /// so mark as busy.
 322   bool FindAndReserveStages(Iter Begin,
 323                             InstrStage *Stage, InstrStage *StageEnd) {
 324     // If at last stage then we're done
 325     if (Stage == StageEnd) return true;
 326     // Get number of cycles for current stage
 327     unsigned N = Stage->Cycles;
 328     // Check to see if N slots are available, if not fail
 329     unsigned Resource;
 330     if (!SlotsAvailable(Begin, N, Stage->Units, Resource)) return false;
 331     // Check to see if remaining stages are available, if not fail
 332     if (!FindAndReserveStages(Begin + N, Stage + 1, StageEnd)) return false;
 333     // Reserve resource
 334     Reserve(Begin, N, Resource);
 335     // Success
 336     return true;
 337   }
 338
 339   /// Reserve - Mark busy (set) the specified N slots.
 340   void Reserve(Iter Begin, unsigned N, unsigned Resource) {
 341     // Determine end of interval
 342     Iter End = Begin + N;
 343     assert(End <= Tally.end() && "Tally is not large enough for schedule");
 344
 345     // Set resource bit in each slot
 346     for (; Begin < End; Begin++)
 347       *Begin |= Resource;
 348   }
 349
 350   /// FindSlots - Starting from Begin, locate consecutive slots where all stages
 351   /// can be completed.  Returns the address of first slot.
 352   Iter FindSlots(Iter Begin, InstrStage *StageBegin, InstrStage *StageEnd) {
 353     // Track position
 354     Iter Cursor = Begin;
 355
 356     // Try all possible slots forward
 357     while (true) {
 358       // Try at cursor, if successful return position.
 359       if (FindAndReserveStages(Cursor, StageBegin, StageEnd)) return Cursor;
 360       // Locate a better position
 361                         Cursor = RetrySlot(Cursor + 1, StageBegin->Cycles, StageBegin->Units);
 362     }
 363   }
 364
 365 public:
 366   /// Initialize - Resize and zero the tally to the specified number of time
 367   /// slots.
 368   inline void Initialize(unsigned N) {
 369     Tally.assign(N, 0);   // Initialize tally to all zeros.
 370   }
 371
 372   // FindAndReserve - Locate an ideal slot for the specified stages and mark
 373   // as busy.
 374   unsigned FindAndReserve(unsigned Slot, InstrStage *StageBegin,
 375                                          InstrStage *StageEnd) {
 376                 // Where to begin
 377                 Iter Begin = Tally.begin() + Slot;
 378                 // Find a free slot
 379                 Iter Where = FindSlots(Begin, StageBegin, StageEnd);
 380                 // Distance is slot number
 381                 unsigned Final = Where - Tally.begin();
 382     return Final;
 383   }
 384
 385 };
 386
 387 //===----------------------------------------------------------------------===//
 388 ///
 389 /// ScheduleDAGSimple - Simple two pass scheduler.
 390 ///
 391 class ScheduleDAGSimple : public ScheduleDAG {
 392 private:
 393   bool NoSched;                         // Just do a BFS schedule, nothing fancy
 394   bool NoItins;                         // Don't use itineraries?
 395   ResourceTally<unsigned> Tally;        // Resource usage tally
 396   unsigned NSlots;                      // Total latency
 397   static const unsigned NotFound = ~0U; // Search marker
 398
 399   unsigned NodeCount;                   // Number of nodes in DAG
 400   std::map<SDNode *, NodeInfo *> Map;   // Map nodes to info
 401   bool HasGroups;                       // True if there are any groups
 402   NodeInfo *Info;                       // Info for nodes being scheduled
 403   NIVector Ordering;                    // Emit ordering of nodes
 404   NodeGroup *HeadNG, *TailNG;           // Keep track of allocated NodeGroups
 405
 406 public:
 407
 408   // Ctor.
 409   ScheduleDAGSimple(bool noSched, bool noItins, SelectionDAG &dag,
 410                     MachineBasicBlock *bb, const TargetMachine &tm)
 411     : ScheduleDAG(dag, bb, tm), NoSched(noSched), NoItins(noItins), NSlots(0),
 412     NodeCount(0), HasGroups(false), Info(NULL), HeadNG(NULL), TailNG(NULL) {
 413     assert(&TII && "Target doesn't provide instr info?");
 414     assert(&MRI && "Target doesn't provide register info?");
 415   }
 416
 417   virtual ~ScheduleDAGSimple() {
 418     if (Info)
 419       delete[] Info;
 420
 421     NodeGroup *NG = HeadNG;
 422     while (NG) {
 423       NodeGroup *NextSU = NG->Next;
 424       delete NG;
 425       NG = NextSU;
 426     }
 427   }
 428
 429   void Schedule();
 430
 431   /// getNI - Returns the node info for the specified node.
 432   ///
 433   NodeInfo *getNI(SDNode *Node) { return Map[Node]; }
 434
 435 private:
 436   static bool isDefiner(NodeInfo *A, NodeInfo *B);
 437   void IncludeNode(NodeInfo *NI);
 438   void VisitAll();
 439   void GatherSchedulingInfo();
 440   void FakeGroupDominators();
 441   bool isStrongDependency(NodeInfo *A, NodeInfo *B);
 442   bool isWeakDependency(NodeInfo *A, NodeInfo *B);
 443   void ScheduleBackward();
 444   void ScheduleForward();
 445
 446   void AddToGroup(NodeInfo *D, NodeInfo *U);
 447   /// PrepareNodeInfo - Set up the basic minimum node info for scheduling.
 448   ///
 449   void PrepareNodeInfo();
 450
 451   /// IdentifyGroups - Put flagged nodes into groups.
 452   ///
 453   void IdentifyGroups();
 454
 455   /// print - Print ordering to specified output stream.
 456   ///
 457   void print(std::ostream &O) const;
 458
 459   void dump(const char *tag) const;
 460
 461   virtual void dump() const;
 462
 463   /// EmitAll - Emit all nodes in schedule sorted order.
 464   ///
 465   void EmitAll();
 466
 467   /// printNI - Print node info.
 468   ///
 469   void printNI(std::ostream &O, NodeInfo *NI) const;
 470
 471   /// printChanges - Hilight changes in order caused by scheduling.
 472   ///
 473   void printChanges(unsigned Index) const;
 474 };
 475
 476 //===----------------------------------------------------------------------===//
 477 /// Special case itineraries.
 478 ///
 479 enum {
 480   CallLatency = 40,          // To push calls back in time
 481
 482   RSInteger   = 0xC0000000,  // Two integer units
 483   RSFloat     = 0x30000000,  // Two float units
 484   RSLoadStore = 0x0C000000,  // Two load store units
 485   RSBranch    = 0x02000000   // One branch unit
 486 };
 487 static InstrStage CallStage  = { CallLatency, RSBranch };
 488 static InstrStage LoadStage  = { 5, RSLoadStore };
 489 static InstrStage StoreStage = { 2, RSLoadStore };
 490 static InstrStage IntStage   = { 2, RSInteger };
 491 static InstrStage FloatStage = { 3, RSFloat };
 492 //===----------------------------------------------------------------------===//
 493
 494 } // namespace
 495
 496 //===----------------------------------------------------------------------===//
 497
 498 /// PrepareNodeInfo - Set up the basic minimum node info for scheduling.
 499 ///
 500 void ScheduleDAGSimple::PrepareNodeInfo() {
 501   // Allocate node information
 502   Info = new NodeInfo[NodeCount];
 503
 504   unsigned i = 0;
 505   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
 506        E = DAG.allnodes_end(); I != E; ++I, ++i) {
 507     // Fast reference to node schedule info
 508     NodeInfo* NI = &Info[i];
 509     // Set up map
 510     Map[I] = NI;
 511     // Set node
 512     NI->Node = I;
 513     // Set pending visit count
 514     NI->setPending(I->use_size());
 515   }
 516 }
 517
 518 /// IdentifyGroups - Put flagged nodes into groups.
 519 ///
 520 void ScheduleDAGSimple::IdentifyGroups() {
 521   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 522     NodeInfo* NI = &Info[i];
 523     SDNode *Node = NI->Node;
 524
 525     // For each operand (in reverse to only look at flags)
 526     for (unsigned N = Node->getNumOperands(); 0 < N--;) {
 527       // Get operand
 528       SDOperand Op = Node->getOperand(N);
 529       // No more flags to walk
 530       if (Op.getValueType() != MVT::Flag) break;
 531       // Add to node group
 532       AddToGroup(getNI(Op.Val), NI);
 533       // Let everyone else know
 534       HasGroups = true;
 535     }
 536   }
 537 }
 538
 539 /// CountInternalUses - Returns the number of edges between the two nodes.
 540 ///
 541 static unsigned CountInternalUses(NodeInfo *D, NodeInfo *U) {
 542   unsigned N = 0;
 543   for (unsigned M = U->Node->getNumOperands(); 0 < M--;) {
 544     SDOperand Op = U->Node->getOperand(M);
 545     if (Op.Val == D->Node) N++;
 546   }
 547
 548   return N;
 549 }
 550
 551 //===----------------------------------------------------------------------===//
 552 /// Add - Adds a definer and user pair to a node group.
 553 ///
 554 void ScheduleDAGSimple::AddToGroup(NodeInfo *D, NodeInfo *U) {
 555   // Get current groups
 556   NodeGroup *DGroup = D->Group;
 557   NodeGroup *UGroup = U->Group;
 558   // If both are members of groups
 559   if (DGroup && UGroup) {
 560     // There may have been another edge connecting
 561     if (DGroup == UGroup) return;
 562     // Add the pending users count
 563     DGroup->addPending(UGroup->getPending());
 564     // For each member of the users group
 565     NodeGroupIterator UNGI(U);
 566     while (NodeInfo *UNI = UNGI.next() ) {
 567       // Change the group
 568       UNI->Group = DGroup;
 569       // For each member of the definers group
 570       NodeGroupIterator DNGI(D);
 571       while (NodeInfo *DNI = DNGI.next() ) {
 572         // Remove internal edges
 573         DGroup->addPending(-CountInternalUses(DNI, UNI));
 574       }
 575     }
 576     // Merge the two lists
 577     DGroup->group_insert(DGroup->group_end(),
 578                          UGroup->group_begin(), UGroup->group_end());
 579   } else if (DGroup) {
 580     // Make user member of definers group
 581     U->Group = DGroup;
 582     // Add users uses to definers group pending
 583     DGroup->addPending(U->Node->use_size());
 584     // For each member of the definers group
 585     NodeGroupIterator DNGI(D);
 586     while (NodeInfo *DNI = DNGI.next() ) {
 587       // Remove internal edges
 588       DGroup->addPending(-CountInternalUses(DNI, U));
 589     }
 590     DGroup->group_push_back(U);
 591   } else if (UGroup) {
 592     // Make definer member of users group
 593     D->Group = UGroup;
 594     // Add definers uses to users group pending
 595     UGroup->addPending(D->Node->use_size());
 596     // For each member of the users group
 597     NodeGroupIterator UNGI(U);
 598     while (NodeInfo *UNI = UNGI.next() ) {
 599       // Remove internal edges
 600       UGroup->addPending(-CountInternalUses(D, UNI));
 601     }
 602     UGroup->group_insert(UGroup->group_begin(), D);
 603   } else {
 604     D->Group = U->Group = DGroup = new NodeGroup();
 605     DGroup->addPending(D->Node->use_size() + U->Node->use_size() -
 606                        CountInternalUses(D, U));
 607     DGroup->group_push_back(D);
 608     DGroup->group_push_back(U);
 609
 610     if (HeadNG == NULL)
 611       HeadNG = DGroup;
 612     if (TailNG != NULL)
 613       TailNG->Next = DGroup;
 614     TailNG = DGroup;
 615   }
 616 }
 617
 618
 619 /// print - Print ordering to specified output stream.
 620 ///
 621 void ScheduleDAGSimple::print(std::ostream &O) const {
 622 #ifndef NDEBUG
 623   O << "Ordering\n";
 624   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
 625     NodeInfo *NI = Ordering[i];
 626     printNI(O, NI);
 627     O << "\n";
 628     if (NI->isGroupDominator()) {
 629       NodeGroup *Group = NI->Group;
 630       for (NIIterator NII = Group->group_begin(), E = Group->group_end();
 631            NII != E; NII++) {
 632         O << "    ";
 633         printNI(O, *NII);
 634         O << "\n";
 635       }
 636     }
 637   }
 638 #endif
 639 }
 640
 641 void ScheduleDAGSimple::dump(const char *tag) const {
 642   std::cerr << tag; dump();
 643 }
 644
 645 void ScheduleDAGSimple::dump() const {
 646   print(std::cerr);
 647 }
 648
 649
 650 /// EmitAll - Emit all nodes in schedule sorted order.
 651 ///
 652 void ScheduleDAGSimple::EmitAll() {
 653   std::map<SDNode*, unsigned> VRBaseMap;
 654
 655   // For each node in the ordering
 656   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
 657     // Get the scheduling info
 658     NodeInfo *NI = Ordering[i];
 659     if (NI->isInGroup()) {
 660       NodeGroupIterator NGI(Ordering[i]);
 661       while (NodeInfo *NI = NGI.next()) EmitNode(NI->Node, VRBaseMap);
 662     } else {
 663       EmitNode(NI->Node, VRBaseMap);
 664     }
 665   }
 666 }
 667
 668 /// isFlagDefiner - Returns true if the node defines a flag result.
 669 static bool isFlagDefiner(SDNode *A) {
 670   unsigned N = A->getNumValues();
 671   return N && A->getValueType(N - 1) == MVT::Flag;
 672 }
 673
 674 /// isFlagUser - Returns true if the node uses a flag result.
 675 ///
 676 static bool isFlagUser(SDNode *A) {
 677   unsigned N = A->getNumOperands();
 678   return N && A->getOperand(N - 1).getValueType() == MVT::Flag;
 679 }
 680
 681 /// printNI - Print node info.
 682 ///
 683 void ScheduleDAGSimple::printNI(std::ostream &O, NodeInfo *NI) const {
 684 #ifndef NDEBUG
 685   SDNode *Node = NI->Node;
 686   O << " "
 687     << std::hex << Node << std::dec
 688     << ", Lat=" << NI->Latency
 689     << ", Slot=" << NI->Slot
 690     << ", ARITY=(" << Node->getNumOperands() << ","
 691     << Node->getNumValues() << ")"
 692     << " " << Node->getOperationName(&DAG);
 693   if (isFlagDefiner(Node)) O << "<#";
 694   if (isFlagUser(Node)) O << ">#";
 695 #endif
 696 }
 697
 698 /// printChanges - Hilight changes in order caused by scheduling.
 699 ///
 700 void ScheduleDAGSimple::printChanges(unsigned Index) const {
 701 #ifndef NDEBUG
 702   // Get the ordered node count
 703   unsigned N = Ordering.size();
 704   // Determine if any changes
 705   unsigned i = 0;
 706   for (; i < N; i++) {
 707     NodeInfo *NI = Ordering[i];
 708     if (NI->Preorder != i) break;
 709   }
 710
 711   if (i < N) {
 712     std::cerr << Index << ". New Ordering\n";
 713
 714     for (i = 0; i < N; i++) {
 715       NodeInfo *NI = Ordering[i];
 716       std::cerr << "  " << NI->Preorder << ". ";
 717       printNI(std::cerr, NI);
 718       std::cerr << "\n";
 719       if (NI->isGroupDominator()) {
 720         NodeGroup *Group = NI->Group;
 721         for (NIIterator NII = Group->group_begin(), E = Group->group_end();
 722              NII != E; NII++) {
 723           std::cerr << "          ";
 724           printNI(std::cerr, *NII);
 725           std::cerr << "\n";
 726         }
 727       }
 728     }
 729   } else {
 730     std::cerr << Index << ". No Changes\n";
 731   }
 732 #endif
 733 }
 734
 735 //===----------------------------------------------------------------------===//
 736 /// isDefiner - Return true if node A is a definer for B.
 737 ///
 738 bool ScheduleDAGSimple::isDefiner(NodeInfo *A, NodeInfo *B) {
 739   // While there are A nodes
 740   NodeGroupIterator NII(A);
 741   while (NodeInfo *NI = NII.next()) {
 742     // Extract node
 743     SDNode *Node = NI->Node;
 744     // While there operands in nodes of B
 745     NodeGroupOpIterator NGOI(B);
 746     while (!NGOI.isEnd()) {
 747       SDOperand Op = NGOI.next();
 748       // If node from A defines a node in B
 749       if (Node == Op.Val) return true;
 750     }
 751   }
 752   return false;
 753 }
 754
 755 /// IncludeNode - Add node to NodeInfo vector.
 756 ///
 757 void ScheduleDAGSimple::IncludeNode(NodeInfo *NI) {
 758   // Get node
 759   SDNode *Node = NI->Node;
 760   // Ignore entry node
 761   if (Node->getOpcode() == ISD::EntryToken) return;
 762   // Check current count for node
 763   int Count = NI->getPending();
 764   // If the node is already in list
 765   if (Count < 0) return;
 766   // Decrement count to indicate a visit
 767   Count--;
 768   // If count has gone to zero then add node to list
 769   if (!Count) {
 770     // Add node
 771     if (NI->isInGroup()) {
 772       Ordering.push_back(NI->Group->getDominator());
 773     } else {
 774       Ordering.push_back(NI);
 775     }
 776     // indicate node has been added
 777     Count--;
 778   }
 779   // Mark as visited with new count
 780   NI->setPending(Count);
 781 }
 782
 783 /// GatherSchedulingInfo - Get latency and resource information about each node.
 784 ///
 785 void ScheduleDAGSimple::GatherSchedulingInfo() {
 786   // Get instruction itineraries for the target
 787   const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
 788
 789   // For each node
 790   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 791     // Get node info
 792     NodeInfo* NI = &Info[i];
 793     SDNode *Node = NI->Node;
 794
 795     // If there are itineraries and it is a machine instruction
 796     if (InstrItins.isEmpty() || NoItins) {
 797       // If machine opcode
 798       if (Node->isTargetOpcode()) {
 799         // Get return type to guess which processing unit
 800         MVT::ValueType VT = Node->getValueType(0);
 801         // Get machine opcode
 802         MachineOpCode TOpc = Node->getTargetOpcode();
 803         NI->IsCall = TII->isCall(TOpc);
 804         NI->IsLoad = TII->isLoad(TOpc);
 805         NI->IsStore = TII->isStore(TOpc);
 806
 807         if (TII->isLoad(TOpc))             NI->StageBegin = &LoadStage;
 808         else if (TII->isStore(TOpc))       NI->StageBegin = &StoreStage;
 809         else if (MVT::isInteger(VT))       NI->StageBegin = &IntStage;
 810         else if (MVT::isFloatingPoint(VT)) NI->StageBegin = &FloatStage;
 811         if (NI->StageBegin) NI->StageEnd = NI->StageBegin + 1;
 812       }
 813     } else if (Node->isTargetOpcode()) {
 814       // get machine opcode
 815       MachineOpCode TOpc = Node->getTargetOpcode();
 816       // Check to see if it is a call
 817       NI->IsCall = TII->isCall(TOpc);
 818       // Get itinerary stages for instruction
 819       unsigned II = TII->getSchedClass(TOpc);
 820       NI->StageBegin = InstrItins.begin(II);
 821       NI->StageEnd = InstrItins.end(II);
 822     }
 823
 824     // One slot for the instruction itself
 825     NI->Latency = 1;
 826
 827     // Add long latency for a call to push it back in time
 828     if (NI->IsCall) NI->Latency += CallLatency;
 829
 830     // Sum up all the latencies
 831     for (InstrStage *Stage = NI->StageBegin, *E = NI->StageEnd;
 832         Stage != E; Stage++) {
 833       NI->Latency += Stage->Cycles;
 834     }
 835
 836     // Sum up all the latencies for max tally size
 837     NSlots += NI->Latency;
 838   }
 839
 840   // Unify metrics if in a group
 841   if (HasGroups) {
 842     for (unsigned i = 0, N = NodeCount; i < N; i++) {
 843       NodeInfo* NI = &Info[i];
 844
 845       if (NI->isInGroup()) {
 846         NodeGroup *Group = NI->Group;
 847
 848         if (!Group->getDominator()) {
 849           NIIterator NGI = Group->group_begin(), NGE = Group->group_end();
 850           NodeInfo *Dominator = *NGI;
 851           unsigned Latency = 0;
 852
 853           for (NGI++; NGI != NGE; NGI++) {
 854             NodeInfo* NGNI = *NGI;
 855             Latency += NGNI->Latency;
 856             if (Dominator->Latency < NGNI->Latency) Dominator = NGNI;
 857           }
 858
 859           Dominator->Latency = Latency;
 860           Group->setDominator(Dominator);
 861         }
 862       }
 863     }
 864   }
 865 }
 866
 867 /// VisitAll - Visit each node breadth-wise to produce an initial ordering.
 868 /// Note that the ordering in the Nodes vector is reversed.
 869 void ScheduleDAGSimple::VisitAll() {
 870   // Add first element to list
 871   NodeInfo *NI = getNI(DAG.getRoot().Val);
 872   if (NI->isInGroup()) {
 873     Ordering.push_back(NI->Group->getDominator());
 874   } else {
 875     Ordering.push_back(NI);
 876   }
 877
 878   // Iterate through all nodes that have been added
 879   for (unsigned i = 0; i < Ordering.size(); i++) { // note: size() varies
 880     // Visit all operands
 881     NodeGroupOpIterator NGI(Ordering[i]);
 882     while (!NGI.isEnd()) {
 883       // Get next operand
 884       SDOperand Op = NGI.next();
 885       // Get node
 886       SDNode *Node = Op.Val;
 887       // Ignore passive nodes
 888       if (isPassiveNode(Node)) continue;
 889       // Check out node
 890       IncludeNode(getNI(Node));
 891     }
 892   }
 893
 894   // Add entry node last (IncludeNode filters entry nodes)
 895   if (DAG.getEntryNode().Val != DAG.getRoot().Val)
 896     Ordering.push_back(getNI(DAG.getEntryNode().Val));
 897
 898   // Reverse the order
 899   std::reverse(Ordering.begin(), Ordering.end());
 900 }
 901
 902 /// FakeGroupDominators - Set dominators for non-scheduling.
 903 ///
 904 void ScheduleDAGSimple::FakeGroupDominators() {
 905   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 906     NodeInfo* NI = &Info[i];
 907
 908     if (NI->isInGroup()) {
 909       NodeGroup *Group = NI->Group;
 910
 911       if (!Group->getDominator()) {
 912         Group->setDominator(NI);
 913       }
 914     }
 915   }
 916 }
 917
 918 /// isStrongDependency - Return true if node A has results used by node B.
 919 /// I.E., B must wait for latency of A.
 920 bool ScheduleDAGSimple::isStrongDependency(NodeInfo *A, NodeInfo *B) {
 921   // If A defines for B then it's a strong dependency or
 922   // if a load follows a store (may be dependent but why take a chance.)
 923   return isDefiner(A, B) || (A->IsStore && B->IsLoad);
 924 }
 925
 926 /// isWeakDependency Return true if node A produces a result that will
 927 /// conflict with operands of B.  It is assumed that we have called
 928 /// isStrongDependency prior.
 929 bool ScheduleDAGSimple::isWeakDependency(NodeInfo *A, NodeInfo *B) {
 930   // TODO check for conflicting real registers and aliases
 931 #if 0 // FIXME - Since we are in SSA form and not checking register aliasing
 932   return A->Node->getOpcode() == ISD::EntryToken || isStrongDependency(B, A);
 933 #else
 934   return A->Node->getOpcode() == ISD::EntryToken;
 935 #endif
 936 }
 937
 938 /// ScheduleBackward - Schedule instructions so that any long latency
 939 /// instructions and the critical path get pushed back in time. Time is run in
 940 /// reverse to allow code reuse of the Tally and eliminate the overhead of
 941 /// biasing every slot indices against NSlots.
 942 void ScheduleDAGSimple::ScheduleBackward() {
 943   // Size and clear the resource tally
 944   Tally.Initialize(NSlots);
 945   // Get number of nodes to schedule
 946   unsigned N = Ordering.size();
 947
 948   // For each node being scheduled
 949   for (unsigned i = N; 0 < i--;) {
 950     NodeInfo *NI = Ordering[i];
 951     // Track insertion
 952     unsigned Slot = NotFound;
 953
 954     // Compare against those previously scheduled nodes
 955     unsigned j = i + 1;
 956     for (; j < N; j++) {
 957       // Get following instruction
 958       NodeInfo *Other = Ordering[j];
 959
 960       // Check dependency against previously inserted nodes
 961       if (isStrongDependency(NI, Other)) {
 962         Slot = Other->Slot + Other->Latency;
 963         break;
 964       } else if (isWeakDependency(NI, Other)) {
 965         Slot = Other->Slot;
 966         break;
 967       }
 968     }
 969
 970     // If independent of others (or first entry)
 971     if (Slot == NotFound) Slot = 0;
 972
 973 #if 0 // FIXME - measure later
 974     // Find a slot where the needed resources are available
 975     if (NI->StageBegin != NI->StageEnd)
 976       Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd);
 977 #endif
 978
 979     // Set node slot
 980     NI->Slot = Slot;
 981
 982     // Insert sort based on slot
 983     j = i + 1;
 984     for (; j < N; j++) {
 985       // Get following instruction
 986       NodeInfo *Other = Ordering[j];
 987       // Should we look further (remember slots are in reverse time)
 988       if (Slot >= Other->Slot) break;
 989       // Shuffle other into ordering
 990       Ordering[j - 1] = Other;
 991     }
 992     // Insert node in proper slot
 993     if (j != i + 1) Ordering[j - 1] = NI;
 994   }
 995 }
 996
 997 /// ScheduleForward - Schedule instructions to maximize packing.
 998 ///
 999 void ScheduleDAGSimple::ScheduleForward() {
1000   // Size and clear the resource tally
1001   Tally.Initialize(NSlots);
1002   // Get number of nodes to schedule
1003   unsigned N = Ordering.size();
1004
1005   // For each node being scheduled
1006   for (unsigned i = 0; i < N; i++) {
1007     NodeInfo *NI = Ordering[i];
1008     // Track insertion
1009     unsigned Slot = NotFound;
1010
1011     // Compare against those previously scheduled nodes
1012     unsigned j = i;
1013     for (; 0 < j--;) {
1014       // Get following instruction
1015       NodeInfo *Other = Ordering[j];
1016
1017       // Check dependency against previously inserted nodes
1018       if (isStrongDependency(Other, NI)) {
1019         Slot = Other->Slot + Other->Latency;
1020         break;
1021       } else if (Other->IsCall || isWeakDependency(Other, NI)) {
1022         Slot = Other->Slot;
1023         break;
1024       }
1025     }
1026
1027     // If independent of others (or first entry)
1028     if (Slot == NotFound) Slot = 0;
1029
1030     // Find a slot where the needed resources are available
1031     if (NI->StageBegin != NI->StageEnd)
1032       Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd);
1033
1034     // Set node slot
1035     NI->Slot = Slot;
1036
1037     // Insert sort based on slot
1038     j = i;
1039     for (; 0 < j--;) {
1040       // Get prior instruction
1041       NodeInfo *Other = Ordering[j];
1042       // Should we look further
1043       if (Slot >= Other->Slot) break;
1044       // Shuffle other into ordering
1045       Ordering[j + 1] = Other;
1046     }
1047     // Insert node in proper slot
1048     if (j != i) Ordering[j + 1] = NI;
1049   }
1050 }
1051
1052 /// Schedule - Order nodes according to selected style.
1053 ///
1054 void ScheduleDAGSimple::Schedule() {
1055   // Number the nodes
1056   NodeCount = std::distance(DAG.allnodes_begin(), DAG.allnodes_end());
1057
1058   // Set up minimum info for scheduling
1059   PrepareNodeInfo();
1060   // Construct node groups for flagged nodes
1061   IdentifyGroups();
1062
1063   // Test to see if scheduling should occur
1064   bool ShouldSchedule = NodeCount > 3 && !NoSched;
1065   // Don't waste time if is only entry and return
1066   if (ShouldSchedule) {
1067     // Get latency and resource requirements
1068     GatherSchedulingInfo();
1069   } else if (HasGroups) {
1070     // Make sure all the groups have dominators
1071     FakeGroupDominators();
1072   }
1073
1074   // Breadth first walk of DAG
1075   VisitAll();
1076
1077 #ifndef NDEBUG
1078   static unsigned Count = 0;
1079   Count++;
1080   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
1081     NodeInfo *NI = Ordering[i];
1082     NI->Preorder = i;
1083   }
1084 #endif
1085
1086   // Don't waste time if is only entry and return
1087   if (ShouldSchedule) {
1088     // Push back long instructions and critical path
1089     ScheduleBackward();
1090
1091     // Pack instructions to maximize resource utilization
1092     ScheduleForward();
1093   }
1094
1095   DEBUG(printChanges(Count));
1096
1097   // Emit in scheduled order
1098   EmitAll();
1099 }
1100
1101
1102 /// createSimpleDAGScheduler - This creates a simple two pass instruction
1103 /// scheduler.
1104 llvm::ScheduleDAG* llvm::createSimpleDAGScheduler(bool NoItins,
1105                                                   SelectionDAG &DAG,
1106                                                   MachineBasicBlock *BB) {
1107   return new ScheduleDAGSimple(false, NoItins, DAG, BB, DAG.getTarget());
1108 }
1109
1110 llvm::ScheduleDAG* llvm::createBFS_DAGScheduler(SelectionDAG &DAG,
1111                                                 MachineBasicBlock *BB) {
1112   return new ScheduleDAGSimple(true, false, DAG, BB,  DAG.getTarget());
1113 }