lib/CodeGen/SelectionDAG/ScheduleDAG.cpp

   1 //===-- ScheduleDAG.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/MachineConstantPool.h"
  18 #include "llvm/CodeGen/MachineFunction.h"
  19 #include "llvm/CodeGen/SelectionDAGISel.h"
  20 #include "llvm/CodeGen/SelectionDAG.h"
  21 #include "llvm/CodeGen/SSARegMap.h"
  22 #include "llvm/Target/TargetMachine.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetInstrItineraries.h"
  25 #include "llvm/Target/TargetLowering.h"
  26 #include "llvm/Support/CommandLine.h"
  27 #include "llvm/Support/Debug.h"
  28 #include <iostream>
  29 #include <algorithm>
  30 using namespace llvm;
  31
  32 namespace {
  33   // Style of scheduling to use.
  34   enum ScheduleChoices {
  35     noScheduling,
  36     simpleScheduling,
  37     simpleNoItinScheduling
  38   };
  39 } // namespace
  40
  41 cl::opt<ScheduleChoices> ScheduleStyle("sched",
  42   cl::desc("Choose scheduling style"),
  43   cl::init(noScheduling),
  44   cl::values(
  45     clEnumValN(noScheduling, "none",
  46               "Trivial emission with no analysis"),
  47     clEnumValN(simpleScheduling, "simple",
  48               "Minimize critical path and maximize processor utilization"),
  49     clEnumValN(simpleNoItinScheduling, "simple-noitin",
  50               "Same as simple except using generic latency"),
  51    clEnumValEnd));
  52
  53
  54 #ifndef NDEBUG
  55 static cl::opt<bool>
  56 ViewDAGs("view-sched-dags", cl::Hidden,
  57          cl::desc("Pop up a window to show sched dags as they are processed"));
  58 #else
  59 static const bool ViewDAGs = 0;
  60 #endif
  61
  62 namespace {
  63 //===----------------------------------------------------------------------===//
  64 ///
  65 /// BitsIterator - Provides iteration through individual bits in a bit vector.
  66 ///
  67 template<class T>
  68 class BitsIterator {
  69 private:
  70   T Bits;                               // Bits left to iterate through
  71
  72 public:
  73   /// Ctor.
  74   BitsIterator(T Initial) : Bits(Initial) {}
  75
  76   /// Next - Returns the next bit set or zero if exhausted.
  77   inline T Next() {
  78     // Get the rightmost bit set
  79     T Result = Bits & -Bits;
  80     // Remove from rest
  81     Bits &= ~Result;
  82     // Return single bit or zero
  83     return Result;
  84   }
  85 };
  86
  87 //===----------------------------------------------------------------------===//
  88
  89
  90 //===----------------------------------------------------------------------===//
  91 ///
  92 /// ResourceTally - Manages the use of resources over time intervals.  Each
  93 /// item (slot) in the tally vector represents the resources used at a given
  94 /// moment.  A bit set to 1 indicates that a resource is in use, otherwise
  95 /// available.  An assumption is made that the tally is large enough to schedule
  96 /// all current instructions (asserts otherwise.)
  97 ///
  98 template<class T>
  99 class ResourceTally {
 100 private:
 101   std::vector<T> Tally;                 // Resources used per slot
 102   typedef typename std::vector<T>::iterator Iter;
 103                                         // Tally iterator
 104
 105   /// SlotsAvailable - Returns true if all units are available.
 106         ///
 107   bool SlotsAvailable(Iter Begin, unsigned N, unsigned ResourceSet,
 108                                               unsigned &Resource) {
 109     assert(N && "Must check availability with N != 0");
 110     // Determine end of interval
 111     Iter End = Begin + N;
 112     assert(End <= Tally.end() && "Tally is not large enough for schedule");
 113
 114     // Iterate thru each resource
 115     BitsIterator<T> Resources(ResourceSet & ~*Begin);
 116     while (unsigned Res = Resources.Next()) {
 117       // Check if resource is available for next N slots
 118       Iter Interval = End;
 119       do {
 120         Interval--;
 121         if (*Interval & Res) break;
 122       } while (Interval != Begin);
 123
 124       // If available for N
 125       if (Interval == Begin) {
 126         // Success
 127         Resource = Res;
 128         return true;
 129       }
 130     }
 131
 132     // No luck
 133     Resource = 0;
 134     return false;
 135   }
 136
 137         /// RetrySlot - Finds a good candidate slot to retry search.
 138   Iter RetrySlot(Iter Begin, unsigned N, unsigned ResourceSet) {
 139     assert(N && "Must check availability with N != 0");
 140     // Determine end of interval
 141     Iter End = Begin + N;
 142     assert(End <= Tally.end() && "Tally is not large enough for schedule");
 143
 144                 while (Begin != End--) {
 145                         // Clear units in use
 146                         ResourceSet &= ~*End;
 147                         // If no units left then we should go no further
 148                         if (!ResourceSet) return End + 1;
 149                 }
 150                 // Made it all the way through
 151                 return Begin;
 152         }
 153
 154   /// FindAndReserveStages - Return true if the stages can be completed. If
 155   /// so mark as busy.
 156   bool FindAndReserveStages(Iter Begin,
 157                             InstrStage *Stage, InstrStage *StageEnd) {
 158     // If at last stage then we're done
 159     if (Stage == StageEnd) return true;
 160     // Get number of cycles for current stage
 161     unsigned N = Stage->Cycles;
 162     // Check to see if N slots are available, if not fail
 163     unsigned Resource;
 164     if (!SlotsAvailable(Begin, N, Stage->Units, Resource)) return false;
 165     // Check to see if remaining stages are available, if not fail
 166     if (!FindAndReserveStages(Begin + N, Stage + 1, StageEnd)) return false;
 167     // Reserve resource
 168     Reserve(Begin, N, Resource);
 169     // Success
 170     return true;
 171   }
 172
 173   /// Reserve - Mark busy (set) the specified N slots.
 174   void Reserve(Iter Begin, unsigned N, unsigned Resource) {
 175     // Determine end of interval
 176     Iter End = Begin + N;
 177     assert(End <= Tally.end() && "Tally is not large enough for schedule");
 178
 179     // Set resource bit in each slot
 180     for (; Begin < End; Begin++)
 181       *Begin |= Resource;
 182   }
 183
 184   /// FindSlots - Starting from Begin, locate consecutive slots where all stages
 185   /// can be completed.  Returns the address of first slot.
 186   Iter FindSlots(Iter Begin, InstrStage *StageBegin, InstrStage *StageEnd) {
 187     // Track position
 188     Iter Cursor = Begin;
 189
 190     // Try all possible slots forward
 191     while (true) {
 192       // Try at cursor, if successful return position.
 193       if (FindAndReserveStages(Cursor, StageBegin, StageEnd)) return Cursor;
 194       // Locate a better position
 195                         Cursor = RetrySlot(Cursor + 1, StageBegin->Cycles, StageBegin->Units);
 196     }
 197   }
 198
 199 public:
 200   /// Initialize - Resize and zero the tally to the specified number of time
 201   /// slots.
 202   inline void Initialize(unsigned N) {
 203     Tally.assign(N, 0);   // Initialize tally to all zeros.
 204   }
 205
 206   // FindAndReserve - Locate an ideal slot for the specified stages and mark
 207   // as busy.
 208   unsigned FindAndReserve(unsigned Slot, InstrStage *StageBegin,
 209                                          InstrStage *StageEnd) {
 210                 // Where to begin
 211                 Iter Begin = Tally.begin() + Slot;
 212                 // Find a free slot
 213                 Iter Where = FindSlots(Begin, StageBegin, StageEnd);
 214                 // Distance is slot number
 215                 unsigned Final = Where - Tally.begin();
 216     return Final;
 217   }
 218
 219 };
 220 //===----------------------------------------------------------------------===//
 221
 222 // Forward
 223 class NodeInfo;
 224 typedef NodeInfo *NodeInfoPtr;
 225 typedef std::vector<NodeInfoPtr>           NIVector;
 226 typedef std::vector<NodeInfoPtr>::iterator NIIterator;
 227
 228 //===----------------------------------------------------------------------===//
 229 ///
 230 /// Node group -  This struct is used to manage flagged node groups.
 231 ///
 232 class NodeGroup {
 233 private:
 234   NIVector      Members;                // Group member nodes
 235   NodeInfo      *Dominator;             // Node with highest latency
 236   unsigned      Latency;                // Total latency of the group
 237   int           Pending;                // Number of visits pending before
 238                                         //    adding to order
 239
 240 public:
 241   // Ctor.
 242   NodeGroup() : Dominator(NULL), Pending(0) {}
 243
 244   // Accessors
 245   inline void setDominator(NodeInfo *D) { Dominator = D; }
 246   inline NodeInfo *getDominator() { return Dominator; }
 247   inline void setLatency(unsigned L) { Latency = L; }
 248   inline unsigned getLatency() { return Latency; }
 249   inline int getPending() const { return Pending; }
 250   inline void setPending(int P)  { Pending = P; }
 251   inline int addPending(int I)  { return Pending += I; }
 252
 253   // Pass thru
 254   inline bool group_empty() { return Members.empty(); }
 255   inline NIIterator group_begin() { return Members.begin(); }
 256   inline NIIterator group_end() { return Members.end(); }
 257   inline void group_push_back(const NodeInfoPtr &NI) { Members.push_back(NI); }
 258   inline NIIterator group_insert(NIIterator Pos, const NodeInfoPtr &NI) {
 259     return Members.insert(Pos, NI);
 260   }
 261   inline void group_insert(NIIterator Pos, NIIterator First, NIIterator Last) {
 262     Members.insert(Pos, First, Last);
 263   }
 264
 265   static void Add(NodeInfo *D, NodeInfo *U);
 266   static unsigned CountInternalUses(NodeInfo *D, NodeInfo *U);
 267 };
 268 //===----------------------------------------------------------------------===//
 269
 270
 271 //===----------------------------------------------------------------------===//
 272 ///
 273 /// NodeInfo - This struct tracks information used to schedule the a node.
 274 ///
 275 class NodeInfo {
 276 private:
 277   int           Pending;                // Number of visits pending before
 278                                         //    adding to order
 279 public:
 280   SDNode        *Node;                  // DAG node
 281   InstrStage    *StageBegin;            // First stage in itinerary
 282   InstrStage    *StageEnd;              // Last+1 stage in itinerary
 283   unsigned      Latency;                // Total cycles to complete instruction
 284   bool          IsCall : 1;             // Is function call
 285   bool          IsLoad : 1;             // Is memory load
 286   bool          IsStore : 1;            // Is memory store
 287   unsigned      Slot;                   // Node's time slot
 288   NodeGroup     *Group;                 // Grouping information
 289   unsigned      VRBase;                 // Virtual register base
 290 #ifndef NDEBUG
 291   unsigned      Preorder;               // Index before scheduling
 292 #endif
 293
 294   // Ctor.
 295   NodeInfo(SDNode *N = NULL)
 296   : Pending(0)
 297   , Node(N)
 298   , StageBegin(NULL)
 299   , StageEnd(NULL)
 300   , Latency(0)
 301   , IsCall(false)
 302   , Slot(0)
 303   , Group(NULL)
 304   , VRBase(0)
 305 #ifndef NDEBUG
 306   , Preorder(0)
 307 #endif
 308   {}
 309
 310   // Accessors
 311   inline bool isInGroup() const {
 312     assert(!Group || !Group->group_empty() && "Group with no members");
 313     return Group != NULL;
 314   }
 315   inline bool isGroupDominator() const {
 316      return isInGroup() && Group->getDominator() == this;
 317   }
 318   inline int getPending() const {
 319     return Group ? Group->getPending() : Pending;
 320   }
 321   inline void setPending(int P) {
 322     if (Group) Group->setPending(P);
 323     else       Pending = P;
 324   }
 325   inline int addPending(int I) {
 326     if (Group) return Group->addPending(I);
 327     else       return Pending += I;
 328   }
 329 };
 330 //===----------------------------------------------------------------------===//
 331
 332
 333 //===----------------------------------------------------------------------===//
 334 ///
 335 /// NodeGroupIterator - Iterates over all the nodes indicated by the node info.
 336 /// If the node is in a group then iterate over the members of the group,
 337 /// otherwise just the node info.
 338 ///
 339 class NodeGroupIterator {
 340 private:
 341   NodeInfo   *NI;                       // Node info
 342   NIIterator NGI;                       // Node group iterator
 343   NIIterator NGE;                       // Node group iterator end
 344
 345 public:
 346   // Ctor.
 347   NodeGroupIterator(NodeInfo *N) : NI(N) {
 348     // If the node is in a group then set up the group iterator.  Otherwise
 349     // the group iterators will trip first time out.
 350     if (N->isInGroup()) {
 351       // get Group
 352       NodeGroup *Group = NI->Group;
 353       NGI = Group->group_begin();
 354       NGE = Group->group_end();
 355       // Prevent this node from being used (will be in members list
 356       NI = NULL;
 357     }
 358   }
 359
 360   /// next - Return the next node info, otherwise NULL.
 361   ///
 362   NodeInfo *next() {
 363     // If members list
 364     if (NGI != NGE) return *NGI++;
 365     // Use node as the result (may be NULL)
 366     NodeInfo *Result = NI;
 367     // Only use once
 368     NI = NULL;
 369     // Return node or NULL
 370     return Result;
 371   }
 372 };
 373 //===----------------------------------------------------------------------===//
 374
 375
 376 //===----------------------------------------------------------------------===//
 377 ///
 378 /// NodeGroupOpIterator - Iterates over all the operands of a node.  If the node
 379 /// is a member of a group, this iterates over all the operands of all the
 380 /// members of the group.
 381 ///
 382 class NodeGroupOpIterator {
 383 private:
 384   NodeInfo            *NI;              // Node containing operands
 385   NodeGroupIterator   GI;               // Node group iterator
 386   SDNode::op_iterator OI;               // Operand iterator
 387   SDNode::op_iterator OE;               // Operand iterator end
 388
 389   /// CheckNode - Test if node has more operands.  If not get the next node
 390   /// skipping over nodes that have no operands.
 391   void CheckNode() {
 392     // Only if operands are exhausted first
 393     while (OI == OE) {
 394       // Get next node info
 395       NodeInfo *NI = GI.next();
 396       // Exit if nodes are exhausted
 397       if (!NI) return;
 398       // Get node itself
 399       SDNode *Node = NI->Node;
 400       // Set up the operand iterators
 401       OI = Node->op_begin();
 402       OE = Node->op_end();
 403     }
 404   }
 405
 406 public:
 407   // Ctor.
 408   NodeGroupOpIterator(NodeInfo *N)
 409     : NI(N), GI(N), OI(SDNode::op_iterator()), OE(SDNode::op_iterator()) {}
 410
 411   /// isEnd - Returns true when not more operands are available.
 412   ///
 413   inline bool isEnd() { CheckNode(); return OI == OE; }
 414
 415   /// next - Returns the next available operand.
 416   ///
 417   inline SDOperand next() {
 418     assert(OI != OE && "Not checking for end of NodeGroupOpIterator correctly");
 419     return *OI++;
 420   }
 421 };
 422 //===----------------------------------------------------------------------===//
 423
 424
 425 //===----------------------------------------------------------------------===//
 426 ///
 427 /// SimpleSched - Simple two pass scheduler.
 428 ///
 429 class SimpleSched {
 430 private:
 431   MachineBasicBlock *BB;                // Current basic block
 432   SelectionDAG &DAG;                    // DAG of the current basic block
 433   const TargetMachine &TM;              // Target processor
 434   const TargetInstrInfo &TII;           // Target instruction information
 435   const MRegisterInfo &MRI;             // Target processor register information
 436   SSARegMap *RegMap;                    // Virtual/real register map
 437   MachineConstantPool *ConstPool;       // Target constant pool
 438   unsigned NodeCount;                   // Number of nodes in DAG
 439   bool HasGroups;                       // True if there are any groups
 440   NodeInfo *Info;                       // Info for nodes being scheduled
 441   std::map<SDNode *, NodeInfo *> Map;   // Map nodes to info
 442   NIVector Ordering;                    // Emit ordering of nodes
 443   ResourceTally<unsigned> Tally;        // Resource usage tally
 444   unsigned NSlots;                      // Total latency
 445   static const unsigned NotFound = ~0U; // Search marker
 446
 447 public:
 448
 449   // Ctor.
 450   SimpleSched(SelectionDAG &D, MachineBasicBlock *bb)
 451     : BB(bb), DAG(D), TM(D.getTarget()), TII(*TM.getInstrInfo()),
 452       MRI(*TM.getRegisterInfo()), RegMap(BB->getParent()->getSSARegMap()),
 453       ConstPool(BB->getParent()->getConstantPool()),
 454       NodeCount(0), HasGroups(false), Info(NULL), Map(), Tally(), NSlots(0) {
 455     assert(&TII && "Target doesn't provide instr info?");
 456     assert(&MRI && "Target doesn't provide register info?");
 457   }
 458
 459   // Run - perform scheduling.
 460   MachineBasicBlock *Run() {
 461     Schedule();
 462     return BB;
 463   }
 464
 465 private:
 466   /// getNI - Returns the node info for the specified node.
 467   ///
 468   inline NodeInfo *getNI(SDNode *Node) { return Map[Node]; }
 469
 470   /// getVR - Returns the virtual register number of the node.
 471   ///
 472   inline unsigned getVR(SDOperand Op) {
 473     NodeInfo *NI = getNI(Op.Val);
 474     assert(NI->VRBase != 0 && "Node emitted out of order - late");
 475     return NI->VRBase + Op.ResNo;
 476   }
 477
 478   static bool isFlagDefiner(SDNode *A);
 479   static bool isFlagUser(SDNode *A);
 480   static bool isDefiner(NodeInfo *A, NodeInfo *B);
 481   static bool isPassiveNode(SDNode *Node);
 482   void IncludeNode(NodeInfo *NI);
 483   void VisitAll();
 484   void Schedule();
 485   void IdentifyGroups();
 486   void GatherSchedulingInfo();
 487   void FakeGroupDominators();
 488   void PrepareNodeInfo();
 489   bool isStrongDependency(NodeInfo *A, NodeInfo *B);
 490   bool isWeakDependency(NodeInfo *A, NodeInfo *B);
 491   void ScheduleBackward();
 492   void ScheduleForward();
 493   void EmitAll();
 494   void EmitNode(NodeInfo *NI);
 495   static unsigned CountResults(SDNode *Node);
 496   static unsigned CountOperands(SDNode *Node);
 497   unsigned CreateVirtualRegisters(MachineInstr *MI,
 498                                   unsigned NumResults,
 499                                   const TargetInstrDescriptor &II);
 500
 501   void printChanges(unsigned Index);
 502   void printSI(std::ostream &O, NodeInfo *NI) const;
 503   void print(std::ostream &O) const;
 504   inline void dump(const char *tag) const { std::cerr << tag; dump(); }
 505   void dump() const;
 506 };
 507
 508
 509 //===----------------------------------------------------------------------===//
 510 /// Special case itineraries.
 511 ///
 512 enum {
 513   CallLatency = 40,          // To push calls back in time
 514
 515   RSInteger   = 0xC0000000,  // Two integer units
 516   RSFloat     = 0x30000000,  // Two float units
 517   RSLoadStore = 0x0C000000,  // Two load store units
 518   RSBranch    = 0x02000000   // One branch unit
 519 };
 520 static InstrStage CallStage  = { CallLatency, RSBranch };
 521 static InstrStage LoadStage  = { 5, RSLoadStore };
 522 static InstrStage StoreStage = { 2, RSLoadStore };
 523 static InstrStage IntStage   = { 2, RSInteger };
 524 static InstrStage FloatStage = { 3, RSFloat };
 525 //===----------------------------------------------------------------------===//
 526
 527
 528 //===----------------------------------------------------------------------===//
 529
 530 } // namespace
 531
 532 //===----------------------------------------------------------------------===//
 533
 534
 535 //===----------------------------------------------------------------------===//
 536 /// Add - Adds a definer and user pair to a node group.
 537 ///
 538 void NodeGroup::Add(NodeInfo *D, NodeInfo *U) {
 539   // Get current groups
 540   NodeGroup *DGroup = D->Group;
 541   NodeGroup *UGroup = U->Group;
 542   // If both are members of groups
 543   if (DGroup && UGroup) {
 544     // There may have been another edge connecting
 545     if (DGroup == UGroup) return;
 546     // Add the pending users count
 547     DGroup->addPending(UGroup->getPending());
 548     // For each member of the users group
 549     NodeGroupIterator UNGI(U);
 550     while (NodeInfo *UNI = UNGI.next() ) {
 551       // Change the group
 552       UNI->Group = DGroup;
 553       // For each member of the definers group
 554       NodeGroupIterator DNGI(D);
 555       while (NodeInfo *DNI = DNGI.next() ) {
 556         // Remove internal edges
 557         DGroup->addPending(-CountInternalUses(DNI, UNI));
 558       }
 559     }
 560     // Merge the two lists
 561     DGroup->group_insert(DGroup->group_end(),
 562                          UGroup->group_begin(), UGroup->group_end());
 563   } else if (DGroup) {
 564     // Make user member of definers group
 565     U->Group = DGroup;
 566     // Add users uses to definers group pending
 567     DGroup->addPending(U->Node->use_size());
 568     // For each member of the definers group
 569     NodeGroupIterator DNGI(D);
 570     while (NodeInfo *DNI = DNGI.next() ) {
 571       // Remove internal edges
 572       DGroup->addPending(-CountInternalUses(DNI, U));
 573     }
 574     DGroup->group_push_back(U);
 575   } else if (UGroup) {
 576     // Make definer member of users group
 577     D->Group = UGroup;
 578     // Add definers uses to users group pending
 579     UGroup->addPending(D->Node->use_size());
 580     // For each member of the users group
 581     NodeGroupIterator UNGI(U);
 582     while (NodeInfo *UNI = UNGI.next() ) {
 583       // Remove internal edges
 584       UGroup->addPending(-CountInternalUses(D, UNI));
 585     }
 586     UGroup->group_insert(UGroup->group_begin(), D);
 587   } else {
 588     D->Group = U->Group = DGroup = new NodeGroup();
 589     DGroup->addPending(D->Node->use_size() + U->Node->use_size() -
 590                        CountInternalUses(D, U));
 591     DGroup->group_push_back(D);
 592     DGroup->group_push_back(U);
 593   }
 594 }
 595
 596 /// CountInternalUses - Returns the number of edges between the two nodes.
 597 ///
 598 unsigned NodeGroup::CountInternalUses(NodeInfo *D, NodeInfo *U) {
 599   unsigned N = 0;
 600   for (unsigned M = U->Node->getNumOperands(); 0 < M--;) {
 601     SDOperand Op = U->Node->getOperand(M);
 602     if (Op.Val == D->Node) N++;
 603   }
 604
 605   return N;
 606 }
 607 //===----------------------------------------------------------------------===//
 608
 609
 610 //===----------------------------------------------------------------------===//
 611 /// isFlagDefiner - Returns true if the node defines a flag result.
 612 bool SimpleSched::isFlagDefiner(SDNode *A) {
 613   unsigned N = A->getNumValues();
 614   return N && A->getValueType(N - 1) == MVT::Flag;
 615 }
 616
 617 /// isFlagUser - Returns true if the node uses a flag result.
 618 ///
 619 bool SimpleSched::isFlagUser(SDNode *A) {
 620   unsigned N = A->getNumOperands();
 621   return N && A->getOperand(N - 1).getValueType() == MVT::Flag;
 622 }
 623
 624 /// isDefiner - Return true if node A is a definer for B.
 625 ///
 626 bool SimpleSched::isDefiner(NodeInfo *A, NodeInfo *B) {
 627   // While there are A nodes
 628   NodeGroupIterator NII(A);
 629   while (NodeInfo *NI = NII.next()) {
 630     // Extract node
 631     SDNode *Node = NI->Node;
 632     // While there operands in nodes of B
 633     NodeGroupOpIterator NGOI(B);
 634     while (!NGOI.isEnd()) {
 635       SDOperand Op = NGOI.next();
 636       // If node from A defines a node in B
 637       if (Node == Op.Val) return true;
 638     }
 639   }
 640   return false;
 641 }
 642
 643 /// isPassiveNode - Return true if the node is a non-scheduled leaf.
 644 ///
 645 bool SimpleSched::isPassiveNode(SDNode *Node) {
 646   if (isa<ConstantSDNode>(Node))       return true;
 647   if (isa<RegisterSDNode>(Node))       return true;
 648   if (isa<GlobalAddressSDNode>(Node))  return true;
 649   if (isa<BasicBlockSDNode>(Node))     return true;
 650   if (isa<FrameIndexSDNode>(Node))     return true;
 651   if (isa<ConstantPoolSDNode>(Node))   return true;
 652   if (isa<ExternalSymbolSDNode>(Node)) return true;
 653   return false;
 654 }
 655
 656 /// IncludeNode - Add node to NodeInfo vector.
 657 ///
 658 void SimpleSched::IncludeNode(NodeInfo *NI) {
 659   // Get node
 660   SDNode *Node = NI->Node;
 661   // Ignore entry node
 662   if (Node->getOpcode() == ISD::EntryToken) return;
 663   // Check current count for node
 664   int Count = NI->getPending();
 665   // If the node is already in list
 666   if (Count < 0) return;
 667   // Decrement count to indicate a visit
 668   Count--;
 669   // If count has gone to zero then add node to list
 670   if (!Count) {
 671     // Add node
 672     if (NI->isInGroup()) {
 673       Ordering.push_back(NI->Group->getDominator());
 674     } else {
 675       Ordering.push_back(NI);
 676     }
 677     // indicate node has been added
 678     Count--;
 679   }
 680   // Mark as visited with new count
 681   NI->setPending(Count);
 682 }
 683
 684 /// VisitAll - Visit each node breadth-wise to produce an initial ordering.
 685 /// Note that the ordering in the Nodes vector is reversed.
 686 void SimpleSched::VisitAll() {
 687   // Add first element to list
 688   NodeInfo *NI = getNI(DAG.getRoot().Val);
 689   if (NI->isInGroup()) {
 690     Ordering.push_back(NI->Group->getDominator());
 691   } else {
 692     Ordering.push_back(NI);
 693   }
 694
 695   // Iterate through all nodes that have been added
 696   for (unsigned i = 0; i < Ordering.size(); i++) { // note: size() varies
 697     // Visit all operands
 698     NodeGroupOpIterator NGI(Ordering[i]);
 699     while (!NGI.isEnd()) {
 700       // Get next operand
 701       SDOperand Op = NGI.next();
 702       // Get node
 703       SDNode *Node = Op.Val;
 704       // Ignore passive nodes
 705       if (isPassiveNode(Node)) continue;
 706       // Check out node
 707       IncludeNode(getNI(Node));
 708     }
 709   }
 710
 711   // Add entry node last (IncludeNode filters entry nodes)
 712   if (DAG.getEntryNode().Val != DAG.getRoot().Val)
 713     Ordering.push_back(getNI(DAG.getEntryNode().Val));
 714
 715   // Reverse the order
 716   std::reverse(Ordering.begin(), Ordering.end());
 717 }
 718
 719 /// IdentifyGroups - Put flagged nodes into groups.
 720 ///
 721 void SimpleSched::IdentifyGroups() {
 722   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 723     NodeInfo* NI = &Info[i];
 724     SDNode *Node = NI->Node;
 725
 726     // For each operand (in reverse to only look at flags)
 727     for (unsigned N = Node->getNumOperands(); 0 < N--;) {
 728       // Get operand
 729       SDOperand Op = Node->getOperand(N);
 730       // No more flags to walk
 731       if (Op.getValueType() != MVT::Flag) break;
 732       // Add to node group
 733       NodeGroup::Add(getNI(Op.Val), NI);
 734       // Let evryone else know
 735       HasGroups = true;
 736     }
 737   }
 738 }
 739
 740 /// GatherSchedulingInfo - Get latency and resource information about each node.
 741 ///
 742 void SimpleSched::GatherSchedulingInfo() {
 743   // Get instruction itineraries for the target
 744   const InstrItineraryData InstrItins = TM.getInstrItineraryData();
 745
 746   // For each node
 747   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 748     // Get node info
 749     NodeInfo* NI = &Info[i];
 750     SDNode *Node = NI->Node;
 751
 752     // If there are itineraries and it is a machine instruction
 753     if (InstrItins.isEmpty() || ScheduleStyle == simpleNoItinScheduling) {
 754       // If machine opcode
 755       if (Node->isTargetOpcode()) {
 756         // Get return type to guess which processing unit
 757         MVT::ValueType VT = Node->getValueType(0);
 758         // Get machine opcode
 759         MachineOpCode TOpc = Node->getTargetOpcode();
 760         NI->IsCall = TII.isCall(TOpc);
 761         NI->IsLoad = TII.isLoad(TOpc);
 762         NI->IsStore = TII.isStore(TOpc);
 763
 764         if (TII.isLoad(TOpc))              NI->StageBegin = &LoadStage;
 765         else if (TII.isStore(TOpc))        NI->StageBegin = &StoreStage;
 766         else if (MVT::isInteger(VT))       NI->StageBegin = &IntStage;
 767         else if (MVT::isFloatingPoint(VT)) NI->StageBegin = &FloatStage;
 768         if (NI->StageBegin) NI->StageEnd = NI->StageBegin + 1;
 769       }
 770     } else if (Node->isTargetOpcode()) {
 771       // get machine opcode
 772       MachineOpCode TOpc = Node->getTargetOpcode();
 773       // Check to see if it is a call
 774       NI->IsCall = TII.isCall(TOpc);
 775       // Get itinerary stages for instruction
 776       unsigned II = TII.getSchedClass(TOpc);
 777       NI->StageBegin = InstrItins.begin(II);
 778       NI->StageEnd = InstrItins.end(II);
 779     }
 780
 781     // One slot for the instruction itself
 782     NI->Latency = 1;
 783
 784     // Add long latency for a call to push it back in time
 785     if (NI->IsCall) NI->Latency += CallLatency;
 786
 787     // Sum up all the latencies
 788     for (InstrStage *Stage = NI->StageBegin, *E = NI->StageEnd;
 789         Stage != E; Stage++) {
 790       NI->Latency += Stage->Cycles;
 791     }
 792
 793     // Sum up all the latencies for max tally size
 794     NSlots += NI->Latency;
 795   }
 796
 797   // Unify metrics if in a group
 798   if (HasGroups) {
 799     for (unsigned i = 0, N = NodeCount; i < N; i++) {
 800       NodeInfo* NI = &Info[i];
 801
 802       if (NI->isInGroup()) {
 803         NodeGroup *Group = NI->Group;
 804
 805         if (!Group->getDominator()) {
 806           NIIterator NGI = Group->group_begin(), NGE = Group->group_end();
 807           NodeInfo *Dominator = *NGI;
 808           unsigned Latency = 0;
 809
 810           for (NGI++; NGI != NGE; NGI++) {
 811             NodeInfo* NGNI = *NGI;
 812             Latency += NGNI->Latency;
 813             if (Dominator->Latency < NGNI->Latency) Dominator = NGNI;
 814           }
 815
 816           Dominator->Latency = Latency;
 817           Group->setDominator(Dominator);
 818         }
 819       }
 820     }
 821   }
 822 }
 823
 824 /// FakeGroupDominators - Set dominators for non-scheduling.
 825 ///
 826 void SimpleSched::FakeGroupDominators() {
 827   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 828     NodeInfo* NI = &Info[i];
 829
 830     if (NI->isInGroup()) {
 831       NodeGroup *Group = NI->Group;
 832
 833       if (!Group->getDominator()) {
 834         Group->setDominator(NI);
 835       }
 836     }
 837   }
 838 }
 839
 840 /// PrepareNodeInfo - Set up the basic minimum node info for scheduling.
 841 ///
 842 void SimpleSched::PrepareNodeInfo() {
 843   // Allocate node information
 844   Info = new NodeInfo[NodeCount];
 845
 846   unsigned i = 0;
 847   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
 848        E = DAG.allnodes_end(); I != E; ++I, ++i) {
 849     // Fast reference to node schedule info
 850     NodeInfo* NI = &Info[i];
 851     // Set up map
 852     Map[I] = NI;
 853     // Set node
 854     NI->Node = I;
 855     // Set pending visit count
 856     NI->setPending(I->use_size());
 857   }
 858 }
 859
 860 /// isStrongDependency - Return true if node A has results used by node B.
 861 /// I.E., B must wait for latency of A.
 862 bool SimpleSched::isStrongDependency(NodeInfo *A, NodeInfo *B) {
 863   // If A defines for B then it's a strong dependency or
 864   // if a load follows a store (may be dependent but why take a chance.)
 865   return isDefiner(A, B) || (A->IsStore && B->IsLoad);
 866 }
 867
 868 /// isWeakDependency Return true if node A produces a result that will
 869 /// conflict with operands of B.  It is assumed that we have called
 870 /// isStrongDependency prior.
 871 bool SimpleSched::isWeakDependency(NodeInfo *A, NodeInfo *B) {
 872   // TODO check for conflicting real registers and aliases
 873 #if 0 // FIXME - Since we are in SSA form and not checking register aliasing
 874   return A->Node->getOpcode() == ISD::EntryToken || isStrongDependency(B, A);
 875 #else
 876   return A->Node->getOpcode() == ISD::EntryToken;
 877 #endif
 878 }
 879
 880 /// ScheduleBackward - Schedule instructions so that any long latency
 881 /// instructions and the critical path get pushed back in time. Time is run in
 882 /// reverse to allow code reuse of the Tally and eliminate the overhead of
 883 /// biasing every slot indices against NSlots.
 884 void SimpleSched::ScheduleBackward() {
 885   // Size and clear the resource tally
 886   Tally.Initialize(NSlots);
 887   // Get number of nodes to schedule
 888   unsigned N = Ordering.size();
 889
 890   // For each node being scheduled
 891   for (unsigned i = N; 0 < i--;) {
 892     NodeInfo *NI = Ordering[i];
 893     // Track insertion
 894     unsigned Slot = NotFound;
 895
 896     // Compare against those previously scheduled nodes
 897     unsigned j = i + 1;
 898     for (; j < N; j++) {
 899       // Get following instruction
 900       NodeInfo *Other = Ordering[j];
 901
 902       // Check dependency against previously inserted nodes
 903       if (isStrongDependency(NI, Other)) {
 904         Slot = Other->Slot + Other->Latency;
 905         break;
 906       } else if (isWeakDependency(NI, Other)) {
 907         Slot = Other->Slot;
 908         break;
 909       }
 910     }
 911
 912     // If independent of others (or first entry)
 913     if (Slot == NotFound) Slot = 0;
 914
 915 #if 0 // FIXME - measure later
 916     // Find a slot where the needed resources are available
 917     if (NI->StageBegin != NI->StageEnd)
 918       Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd);
 919 #endif
 920
 921     // Set node slot
 922     NI->Slot = Slot;
 923
 924     // Insert sort based on slot
 925     j = i + 1;
 926     for (; j < N; j++) {
 927       // Get following instruction
 928       NodeInfo *Other = Ordering[j];
 929       // Should we look further (remember slots are in reverse time)
 930       if (Slot >= Other->Slot) break;
 931       // Shuffle other into ordering
 932       Ordering[j - 1] = Other;
 933     }
 934     // Insert node in proper slot
 935     if (j != i + 1) Ordering[j - 1] = NI;
 936   }
 937 }
 938
 939 /// ScheduleForward - Schedule instructions to maximize packing.
 940 ///
 941 void SimpleSched::ScheduleForward() {
 942   // Size and clear the resource tally
 943   Tally.Initialize(NSlots);
 944   // Get number of nodes to schedule
 945   unsigned N = Ordering.size();
 946
 947   // For each node being scheduled
 948   for (unsigned i = 0; i < N; i++) {
 949     NodeInfo *NI = Ordering[i];
 950     // Track insertion
 951     unsigned Slot = NotFound;
 952
 953     // Compare against those previously scheduled nodes
 954     unsigned j = i;
 955     for (; 0 < j--;) {
 956       // Get following instruction
 957       NodeInfo *Other = Ordering[j];
 958
 959       // Check dependency against previously inserted nodes
 960       if (isStrongDependency(Other, NI)) {
 961         Slot = Other->Slot + Other->Latency;
 962         break;
 963       } else if (Other->IsCall || isWeakDependency(Other, NI)) {
 964         Slot = Other->Slot;
 965         break;
 966       }
 967     }
 968
 969     // If independent of others (or first entry)
 970     if (Slot == NotFound) Slot = 0;
 971
 972     // Find a slot where the needed resources are available
 973     if (NI->StageBegin != NI->StageEnd)
 974       Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd);
 975
 976     // Set node slot
 977     NI->Slot = Slot;
 978
 979     // Insert sort based on slot
 980     j = i;
 981     for (; 0 < j--;) {
 982       // Get prior instruction
 983       NodeInfo *Other = Ordering[j];
 984       // Should we look further
 985       if (Slot >= Other->Slot) break;
 986       // Shuffle other into ordering
 987       Ordering[j + 1] = Other;
 988     }
 989     // Insert node in proper slot
 990     if (j != i) Ordering[j + 1] = NI;
 991   }
 992 }
 993
 994 /// EmitAll - Emit all nodes in schedule sorted order.
 995 ///
 996 void SimpleSched::EmitAll() {
 997   // For each node in the ordering
 998   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
 999     // Get the scheduling info
1000     NodeInfo *NI = Ordering[i];
1001     if (NI->isInGroup()) {
1002       NodeGroupIterator NGI(Ordering[i]);
1003       while (NodeInfo *NI = NGI.next()) EmitNode(NI);
1004     } else {
1005       EmitNode(NI);
1006     }
1007   }
1008 }
1009
1010 /// CountResults - The results of target nodes have register or immediate
1011 /// operands first, then an optional chain, and optional flag operands (which do
1012 /// not go into the machine instrs.)
1013 unsigned SimpleSched::CountResults(SDNode *Node) {
1014   unsigned N = Node->getNumValues();
1015   while (N && Node->getValueType(N - 1) == MVT::Flag)
1016     --N;
1017   if (N && Node->getValueType(N - 1) == MVT::Other)
1018     --N;    // Skip over chain result.
1019   return N;
1020 }
1021
1022 /// CountOperands  The inputs to target nodes have any actual inputs first,
1023 /// followed by an optional chain operand, then flag operands.  Compute the
1024 /// number of actual operands that  will go into the machine instr.
1025 unsigned SimpleSched::CountOperands(SDNode *Node) {
1026   unsigned N = Node->getNumOperands();
1027   while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag)
1028     --N;
1029   if (N && Node->getOperand(N - 1).getValueType() == MVT::Other)
1030     --N; // Ignore chain if it exists.
1031   return N;
1032 }
1033
1034 /// CreateVirtualRegisters - Add result register values for things that are
1035 /// defined by this instruction.
1036 unsigned SimpleSched::CreateVirtualRegisters(MachineInstr *MI,
1037                                              unsigned NumResults,
1038                                              const TargetInstrDescriptor &II) {
1039   // Create the result registers for this node and add the result regs to
1040   // the machine instruction.
1041   const TargetOperandInfo *OpInfo = II.OpInfo;
1042   unsigned ResultReg = RegMap->createVirtualRegister(OpInfo[0].RegClass);
1043   MI->addRegOperand(ResultReg, MachineOperand::Def);
1044   for (unsigned i = 1; i != NumResults; ++i) {
1045     assert(OpInfo[i].RegClass && "Isn't a register operand!");
1046     MI->addRegOperand(RegMap->createVirtualRegister(OpInfo[i].RegClass),
1047                       MachineOperand::Def);
1048   }
1049   return ResultReg;
1050 }
1051
1052 /// EmitNode - Generate machine code for an node and needed dependencies.
1053 ///
1054 void SimpleSched::EmitNode(NodeInfo *NI) {
1055   unsigned VRBase = 0;                 // First virtual register for node
1056   SDNode *Node = NI->Node;
1057
1058   // If machine instruction
1059   if (Node->isTargetOpcode()) {
1060     unsigned Opc = Node->getTargetOpcode();
1061     const TargetInstrDescriptor &II = TII.get(Opc);
1062
1063     unsigned NumResults = CountResults(Node);
1064     unsigned NodeOperands = CountOperands(Node);
1065     unsigned NumMIOperands = NodeOperands + NumResults;
1066 #ifndef NDEBUG
1067     assert((unsigned(II.numOperands) == NumMIOperands || II.numOperands == -1)&&
1068            "#operands for dag node doesn't match .td file!");
1069 #endif
1070
1071     // Create the new machine instruction.
1072     MachineInstr *MI = new MachineInstr(Opc, NumMIOperands, true, true);
1073
1074     // Add result register values for things that are defined by this
1075     // instruction.
1076
1077     // If the node is only used by a CopyToReg and the dest reg is a vreg, use
1078     // the CopyToReg'd destination register instead of creating a new vreg.
1079     if (NumResults == 1) {
1080       for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
1081            UI != E; ++UI) {
1082         SDNode *Use = *UI;
1083         if (Use->getOpcode() == ISD::CopyToReg &&
1084             Use->getOperand(2).Val == Node) {
1085           unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
1086           if (MRegisterInfo::isVirtualRegister(Reg)) {
1087             VRBase = Reg;
1088             MI->addRegOperand(Reg, MachineOperand::Def);
1089             break;
1090           }
1091         }
1092       }
1093     }
1094
1095     // Otherwise, create new virtual registers.
1096     if (NumResults && VRBase == 0)
1097       VRBase = CreateVirtualRegisters(MI, NumResults, II);
1098
1099     // Emit all of the actual operands of this instruction, adding them to the
1100     // instruction as appropriate.
1101     for (unsigned i = 0; i != NodeOperands; ++i) {
1102       if (Node->getOperand(i).isTargetOpcode()) {
1103         // Note that this case is redundant with the final else block, but we
1104         // include it because it is the most common and it makes the logic
1105         // simpler here.
1106         assert(Node->getOperand(i).getValueType() != MVT::Other &&
1107                Node->getOperand(i).getValueType() != MVT::Flag &&
1108                "Chain and flag operands should occur at end of operand list!");
1109
1110         // Get/emit the operand.
1111         unsigned VReg = getVR(Node->getOperand(i));
1112         MI->addRegOperand(VReg, MachineOperand::Use);
1113
1114         // Verify that it is right.
1115         assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?");
1116         assert(II.OpInfo[i+NumResults].RegClass &&
1117                "Don't have operand info for this instruction!");
1118         assert(RegMap->getRegClass(VReg) == II.OpInfo[i+NumResults].RegClass &&
1119                "Register class of operand and regclass of use don't agree!");
1120       } else if (ConstantSDNode *C =
1121                  dyn_cast<ConstantSDNode>(Node->getOperand(i))) {
1122         MI->addZeroExtImm64Operand(C->getValue());
1123       } else if (RegisterSDNode*R =
1124                  dyn_cast<RegisterSDNode>(Node->getOperand(i))) {
1125         MI->addRegOperand(R->getReg(), MachineOperand::Use);
1126       } else if (GlobalAddressSDNode *TGA =
1127                        dyn_cast<GlobalAddressSDNode>(Node->getOperand(i))) {
1128         MI->addGlobalAddressOperand(TGA->getGlobal(), false, TGA->getOffset());
1129       } else if (BasicBlockSDNode *BB =
1130                        dyn_cast<BasicBlockSDNode>(Node->getOperand(i))) {
1131         MI->addMachineBasicBlockOperand(BB->getBasicBlock());
1132       } else if (FrameIndexSDNode *FI =
1133                        dyn_cast<FrameIndexSDNode>(Node->getOperand(i))) {
1134         MI->addFrameIndexOperand(FI->getIndex());
1135       } else if (ConstantPoolSDNode *CP =
1136                     dyn_cast<ConstantPoolSDNode>(Node->getOperand(i))) {
1137         unsigned Idx = ConstPool->getConstantPoolIndex(CP->get());
1138         MI->addConstantPoolIndexOperand(Idx);
1139       } else if (ExternalSymbolSDNode *ES =
1140                  dyn_cast<ExternalSymbolSDNode>(Node->getOperand(i))) {
1141         MI->addExternalSymbolOperand(ES->getSymbol(), false);
1142       } else {
1143         assert(Node->getOperand(i).getValueType() != MVT::Other &&
1144                Node->getOperand(i).getValueType() != MVT::Flag &&
1145                "Chain and flag operands should occur at end of operand list!");
1146         unsigned VReg = getVR(Node->getOperand(i));
1147         MI->addRegOperand(VReg, MachineOperand::Use);
1148
1149         // Verify that it is right.
1150         assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?");
1151         assert(II.OpInfo[i+NumResults].RegClass &&
1152                "Don't have operand info for this instruction!");
1153         assert(RegMap->getRegClass(VReg) == II.OpInfo[i+NumResults].RegClass &&
1154                "Register class of operand and regclass of use don't agree!");
1155       }
1156     }
1157
1158     // Now that we have emitted all operands, emit this instruction itself.
1159     if ((II.Flags & M_USES_CUSTOM_DAG_SCHED_INSERTION) == 0) {
1160       BB->insert(BB->end(), MI);
1161     } else {
1162       // Insert this instruction into the end of the basic block, potentially
1163       // taking some custom action.
1164       BB = DAG.getTargetLoweringInfo().InsertAtEndOfBasicBlock(MI, BB);
1165     }
1166   } else {
1167     switch (Node->getOpcode()) {
1168     default:
1169       Node->dump();
1170       assert(0 && "This target-independent node should have been selected!");
1171     case ISD::EntryToken: // fall thru
1172     case ISD::TokenFactor:
1173       break;
1174     case ISD::CopyToReg: {
1175       unsigned InReg = getVR(Node->getOperand(2));
1176       unsigned DestReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
1177       if (InReg != DestReg)   // Coallesced away the copy?
1178         MRI.copyRegToReg(*BB, BB->end(), DestReg, InReg,
1179                          RegMap->getRegClass(InReg));
1180       break;
1181     }
1182     case ISD::CopyFromReg: {
1183       unsigned SrcReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
1184       if (MRegisterInfo::isVirtualRegister(SrcReg)) {
1185         VRBase = SrcReg;  // Just use the input register directly!
1186         break;
1187       }
1188
1189       // If the node is only used by a CopyToReg and the dest reg is a vreg, use
1190       // the CopyToReg'd destination register instead of creating a new vreg.
1191       for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
1192            UI != E; ++UI) {
1193         SDNode *Use = *UI;
1194         if (Use->getOpcode() == ISD::CopyToReg &&
1195             Use->getOperand(2).Val == Node) {
1196           unsigned DestReg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
1197           if (MRegisterInfo::isVirtualRegister(DestReg)) {
1198             VRBase = DestReg;
1199             break;
1200           }
1201         }
1202       }
1203
1204       // Figure out the register class to create for the destreg.
1205       const TargetRegisterClass *TRC = 0;
1206       if (VRBase) {
1207         TRC = RegMap->getRegClass(VRBase);
1208       } else {
1209
1210         // Pick the register class of the right type that contains this physreg.
1211         for (MRegisterInfo::regclass_iterator I = MRI.regclass_begin(),
1212              E = MRI.regclass_end(); I != E; ++I)
1213           if ((*I)->hasType(Node->getValueType(0)) &&
1214               (*I)->contains(SrcReg)) {
1215             TRC = *I;
1216             break;
1217           }
1218         assert(TRC && "Couldn't find register class for reg copy!");
1219
1220         // Create the reg, emit the copy.
1221         VRBase = RegMap->createVirtualRegister(TRC);
1222       }
1223       MRI.copyRegToReg(*BB, BB->end(), VRBase, SrcReg, TRC);
1224       break;
1225     }
1226     }
1227   }
1228
1229   assert(NI->VRBase == 0 && "Node emitted out of order - early");
1230   NI->VRBase = VRBase;
1231 }
1232
1233 /// Schedule - Order nodes according to selected style.
1234 ///
1235 void SimpleSched::Schedule() {
1236   // Number the nodes
1237   NodeCount = std::distance(DAG.allnodes_begin(), DAG.allnodes_end());
1238   // Test to see if scheduling should occur
1239   bool ShouldSchedule = NodeCount > 3 && ScheduleStyle != noScheduling;
1240   // Set up minimum info for scheduling
1241   PrepareNodeInfo();
1242   // Construct node groups for flagged nodes
1243   IdentifyGroups();
1244
1245   // Don't waste time if is only entry and return
1246   if (ShouldSchedule) {
1247     // Get latency and resource requirements
1248     GatherSchedulingInfo();
1249   } else if (HasGroups) {
1250     // Make sure all the groups have dominators
1251     FakeGroupDominators();
1252   }
1253
1254   // Breadth first walk of DAG
1255   VisitAll();
1256
1257 #ifndef NDEBUG
1258   static unsigned Count = 0;
1259   Count++;
1260   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
1261     NodeInfo *NI = Ordering[i];
1262     NI->Preorder = i;
1263   }
1264 #endif
1265
1266   // Don't waste time if is only entry and return
1267   if (ShouldSchedule) {
1268     // Push back long instructions and critical path
1269     ScheduleBackward();
1270
1271     // Pack instructions to maximize resource utilization
1272     ScheduleForward();
1273   }
1274
1275   DEBUG(printChanges(Count));
1276
1277   // Emit in scheduled order
1278   EmitAll();
1279 }
1280
1281 /// printChanges - Hilight changes in order caused by scheduling.
1282 ///
1283 void SimpleSched::printChanges(unsigned Index) {
1284 #ifndef NDEBUG
1285   // Get the ordered node count
1286   unsigned N = Ordering.size();
1287   // Determine if any changes
1288   unsigned i = 0;
1289   for (; i < N; i++) {
1290     NodeInfo *NI = Ordering[i];
1291     if (NI->Preorder != i) break;
1292   }
1293
1294   if (i < N) {
1295     std::cerr << Index << ". New Ordering\n";
1296
1297     for (i = 0; i < N; i++) {
1298       NodeInfo *NI = Ordering[i];
1299       std::cerr << "  " << NI->Preorder << ". ";
1300       printSI(std::cerr, NI);
1301       std::cerr << "\n";
1302       if (NI->isGroupDominator()) {
1303         NodeGroup *Group = NI->Group;
1304         for (NIIterator NII = Group->group_begin(), E = Group->group_end();
1305              NII != E; NII++) {
1306           std::cerr << "          ";
1307           printSI(std::cerr, *NII);
1308           std::cerr << "\n";
1309         }
1310       }
1311     }
1312   } else {
1313     std::cerr << Index << ". No Changes\n";
1314   }
1315 #endif
1316 }
1317
1318 /// printSI - Print schedule info.
1319 ///
1320 void SimpleSched::printSI(std::ostream &O, NodeInfo *NI) const {
1321 #ifndef NDEBUG
1322   SDNode *Node = NI->Node;
1323   O << " "
1324     << std::hex << Node << std::dec
1325     << ", Lat=" << NI->Latency
1326     << ", Slot=" << NI->Slot
1327     << ", ARITY=(" << Node->getNumOperands() << ","
1328                    << Node->getNumValues() << ")"
1329     << " " << Node->getOperationName(&DAG);
1330   if (isFlagDefiner(Node)) O << "<#";
1331   if (isFlagUser(Node)) O << ">#";
1332 #endif
1333 }
1334
1335 /// print - Print ordering to specified output stream.
1336 ///
1337 void SimpleSched::print(std::ostream &O) const {
1338 #ifndef NDEBUG
1339   using namespace std;
1340   O << "Ordering\n";
1341   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
1342     NodeInfo *NI = Ordering[i];
1343     printSI(O, NI);
1344     O << "\n";
1345     if (NI->isGroupDominator()) {
1346       NodeGroup *Group = NI->Group;
1347       for (NIIterator NII = Group->group_begin(), E = Group->group_end();
1348            NII != E; NII++) {
1349         O << "    ";
1350         printSI(O, *NII);
1351         O << "\n";
1352       }
1353     }
1354   }
1355 #endif
1356 }
1357
1358 /// dump - Print ordering to std::cerr.
1359 ///
1360 void SimpleSched::dump() const {
1361   print(std::cerr);
1362 }
1363 //===----------------------------------------------------------------------===//
1364
1365
1366 //===----------------------------------------------------------------------===//
1367 /// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each
1368 /// target node in the graph.
1369 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &SD) {
1370   if (ViewDAGs) SD.viewGraph();
1371   BB = SimpleSched(SD, BB).Run();
1372 }