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