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)
 406     : NI(N), GI(N), OI(SDNode::op_iterator()), OE(SDNode::op_iterator()) {}
 407
 408   /// isEnd - Returns true when not more operands are available.
 409   ///
 410   inline bool isEnd() { CheckNode(); return OI == OE; }
 411
 412   /// next - Returns the next available operand.
 413   ///
 414   inline SDOperand next() {
 415     assert(OI != OE && "Not checking for end of NodeGroupOpIterator correctly");
 416     return *OI++;
 417   }
 418 };
 419 //===----------------------------------------------------------------------===//
 420
 421
 422 //===----------------------------------------------------------------------===//
 423 ///
 424 /// SimpleSched - Simple two pass scheduler.
 425 ///
 426 class SimpleSched {
 427 private:
 428   MachineBasicBlock *BB;                // Current basic block
 429   SelectionDAG &DAG;                    // DAG of the current basic block
 430   const TargetMachine &TM;              // Target processor
 431   const TargetInstrInfo &TII;           // Target instruction information
 432   const MRegisterInfo &MRI;             // Target processor register information
 433   SSARegMap *RegMap;                    // Virtual/real register map
 434   MachineConstantPool *ConstPool;       // Target constant pool
 435   unsigned NodeCount;                   // Number of nodes in DAG
 436   bool HasGroups;                       // True if there are any groups
 437   NodeInfo *Info;                       // Info for nodes being scheduled
 438   std::map<SDNode *, NodeInfo *> Map;   // Map nodes to info
 439   NIVector Ordering;                    // Emit ordering of nodes
 440   ResourceTally<unsigned> Tally;        // Resource usage tally
 441   unsigned NSlots;                      // Total latency
 442   static const unsigned NotFound = ~0U; // Search marker
 443
 444 public:
 445
 446   // Ctor.
 447   SimpleSched(SelectionDAG &D, MachineBasicBlock *bb)
 448     : BB(bb), DAG(D), TM(D.getTarget()), TII(*TM.getInstrInfo()),
 449       MRI(*TM.getRegisterInfo()), RegMap(BB->getParent()->getSSARegMap()),
 450       ConstPool(BB->getParent()->getConstantPool()),
 451       NodeCount(0), HasGroups(false), Info(NULL), Map(), Tally(), NSlots(0) {
 452     assert(&TII && "Target doesn't provide instr info?");
 453     assert(&MRI && "Target doesn't provide register info?");
 454   }
 455
 456   // Run - perform scheduling.
 457   MachineBasicBlock *Run() {
 458     Schedule();
 459     return BB;
 460   }
 461
 462 private:
 463   /// getNI - Returns the node info for the specified node.
 464   ///
 465   inline NodeInfo *getNI(SDNode *Node) { return Map[Node]; }
 466
 467   /// getVR - Returns the virtual register number of the node.
 468   ///
 469   inline unsigned getVR(SDOperand Op) {
 470     NodeInfo *NI = getNI(Op.Val);
 471     assert(NI->VRBase != 0 && "Node emitted out of order - late");
 472     return NI->VRBase + Op.ResNo;
 473   }
 474
 475   static bool isFlagDefiner(SDNode *A);
 476   static bool isFlagUser(SDNode *A);
 477   static bool isDefiner(NodeInfo *A, NodeInfo *B);
 478   static bool isPassiveNode(SDNode *Node);
 479   void IncludeNode(NodeInfo *NI);
 480   void VisitAll();
 481   void Schedule();
 482   void IdentifyGroups();
 483   void GatherSchedulingInfo();
 484   void FakeGroupDominators();
 485   void PrepareNodeInfo();
 486   bool isStrongDependency(NodeInfo *A, NodeInfo *B);
 487   bool isWeakDependency(NodeInfo *A, NodeInfo *B);
 488   void ScheduleBackward();
 489   void ScheduleForward();
 490   void EmitAll();
 491   void EmitNode(NodeInfo *NI);
 492   static unsigned CountResults(SDNode *Node);
 493   static unsigned CountOperands(SDNode *Node);
 494   unsigned CreateVirtualRegisters(MachineInstr *MI,
 495                                   unsigned NumResults,
 496                                   const TargetInstrDescriptor &II);
 497
 498   void printChanges(unsigned Index);
 499   void printSI(std::ostream &O, NodeInfo *NI) const;
 500   void print(std::ostream &O) const;
 501   inline void dump(const char *tag) const { std::cerr << tag; dump(); }
 502   void dump() const;
 503 };
 504
 505
 506 //===----------------------------------------------------------------------===//
 507 /// Special case itineraries.
 508 ///
 509 enum {
 510   CallLatency = 40,          // To push calls back in time
 511
 512   RSInteger   = 0xC0000000,  // Two integer units
 513   RSFloat     = 0x30000000,  // Two float units
 514   RSLoadStore = 0x0C000000,  // Two load store units
 515   RSBranch    = 0x02000000   // One branch unit
 516 };
 517 static InstrStage CallStage  = { CallLatency, RSBranch };
 518 static InstrStage LoadStage  = { 5, RSLoadStore };
 519 static InstrStage StoreStage = { 2, RSLoadStore };
 520 static InstrStage IntStage   = { 2, RSInteger };
 521 static InstrStage FloatStage = { 3, RSFloat };
 522 //===----------------------------------------------------------------------===//
 523
 524
 525 //===----------------------------------------------------------------------===//
 526
 527 } // namespace
 528
 529 //===----------------------------------------------------------------------===//
 530
 531
 532 //===----------------------------------------------------------------------===//
 533 /// Add - Adds a definer and user pair to a node group.
 534 ///
 535 void NodeGroup::Add(NodeInfo *D, NodeInfo *U) {
 536   // Get current groups
 537   NodeGroup *DGroup = D->Group;
 538   NodeGroup *UGroup = U->Group;
 539   // If both are members of groups
 540   if (DGroup && UGroup) {
 541     // There may have been another edge connecting
 542     if (DGroup == UGroup) return;
 543     // Add the pending users count
 544     DGroup->addPending(UGroup->getPending());
 545     // For each member of the users group
 546     NodeGroupIterator UNGI(U);
 547     while (NodeInfo *UNI = UNGI.next() ) {
 548       // Change the group
 549       UNI->Group = DGroup;
 550       // For each member of the definers group
 551       NodeGroupIterator DNGI(D);
 552       while (NodeInfo *DNI = DNGI.next() ) {
 553         // Remove internal edges
 554         DGroup->addPending(-CountInternalUses(DNI, UNI));
 555       }
 556     }
 557     // Merge the two lists
 558     DGroup->group_insert(DGroup->group_end(),
 559                          UGroup->group_begin(), UGroup->group_end());
 560   } else if (DGroup) {
 561     // Make user member of definers group
 562     U->Group = DGroup;
 563     // Add users uses to definers group pending
 564     DGroup->addPending(U->Node->use_size());
 565     // For each member of the definers group
 566     NodeGroupIterator DNGI(D);
 567     while (NodeInfo *DNI = DNGI.next() ) {
 568       // Remove internal edges
 569       DGroup->addPending(-CountInternalUses(DNI, U));
 570     }
 571     DGroup->group_push_back(U);
 572   } else if (UGroup) {
 573     // Make definer member of users group
 574     D->Group = UGroup;
 575     // Add definers uses to users group pending
 576     UGroup->addPending(D->Node->use_size());
 577     // For each member of the users group
 578     NodeGroupIterator UNGI(U);
 579     while (NodeInfo *UNI = UNGI.next() ) {
 580       // Remove internal edges
 581       UGroup->addPending(-CountInternalUses(D, UNI));
 582     }
 583     UGroup->group_insert(UGroup->group_begin(), D);
 584   } else {
 585     D->Group = U->Group = DGroup = new NodeGroup();
 586     DGroup->addPending(D->Node->use_size() + U->Node->use_size() -
 587                        CountInternalUses(D, U));
 588     DGroup->group_push_back(D);
 589     DGroup->group_push_back(U);
 590   }
 591 }
 592
 593 /// CountInternalUses - Returns the number of edges between the two nodes.
 594 ///
 595 unsigned NodeGroup::CountInternalUses(NodeInfo *D, NodeInfo *U) {
 596   unsigned N = 0;
 597   for (unsigned M = U->Node->getNumOperands(); 0 < M--;) {
 598     SDOperand Op = U->Node->getOperand(M);
 599     if (Op.Val == D->Node) N++;
 600   }
 601
 602   return N;
 603 }
 604 //===----------------------------------------------------------------------===//
 605
 606
 607 //===----------------------------------------------------------------------===//
 608 /// isFlagDefiner - Returns true if the node defines a flag result.
 609 bool SimpleSched::isFlagDefiner(SDNode *A) {
 610   unsigned N = A->getNumValues();
 611   return N && A->getValueType(N - 1) == MVT::Flag;
 612 }
 613
 614 /// isFlagUser - Returns true if the node uses a flag result.
 615 ///
 616 bool SimpleSched::isFlagUser(SDNode *A) {
 617   unsigned N = A->getNumOperands();
 618   return N && A->getOperand(N - 1).getValueType() == MVT::Flag;
 619 }
 620
 621 /// isDefiner - Return true if node A is a definer for B.
 622 ///
 623 bool SimpleSched::isDefiner(NodeInfo *A, NodeInfo *B) {
 624   // While there are A nodes
 625   NodeGroupIterator NII(A);
 626   while (NodeInfo *NI = NII.next()) {
 627     // Extract node
 628     SDNode *Node = NI->Node;
 629     // While there operands in nodes of B
 630     NodeGroupOpIterator NGOI(B);
 631     while (!NGOI.isEnd()) {
 632       SDOperand Op = NGOI.next();
 633       // If node from A defines a node in B
 634       if (Node == Op.Val) return true;
 635     }
 636   }
 637   return false;
 638 }
 639
 640 /// isPassiveNode - Return true if the node is a non-scheduled leaf.
 641 ///
 642 bool SimpleSched::isPassiveNode(SDNode *Node) {
 643   if (isa<ConstantSDNode>(Node))       return true;
 644   if (isa<RegisterSDNode>(Node))       return true;
 645   if (isa<GlobalAddressSDNode>(Node))  return true;
 646   if (isa<BasicBlockSDNode>(Node))     return true;
 647   if (isa<FrameIndexSDNode>(Node))     return true;
 648   if (isa<ConstantPoolSDNode>(Node))   return true;
 649   if (isa<ExternalSymbolSDNode>(Node)) return true;
 650   return false;
 651 }
 652
 653 /// IncludeNode - Add node to NodeInfo vector.
 654 ///
 655 void SimpleSched::IncludeNode(NodeInfo *NI) {
 656 // Get node
 657 SDNode *Node = NI->Node;
 658 // Ignore entry node
 659 if (Node->getOpcode() == ISD::EntryToken) return;
 660   // Check current count for node
 661   int Count = NI->getPending();
 662   // If the node is already in list
 663   if (Count < 0) return;
 664   // Decrement count to indicate a visit
 665   Count--;
 666   // If count has gone to zero then add node to list
 667   if (!Count) {
 668     // Add node
 669     if (NI->isInGroup()) {
 670       Ordering.push_back(NI->Group->getDominator());
 671     } else {
 672       Ordering.push_back(NI);
 673     }
 674     // indicate node has been added
 675     Count--;
 676   }
 677   // Mark as visited with new count
 678   NI->setPending(Count);
 679 }
 680
 681 /// VisitAll - Visit each node breadth-wise to produce an initial ordering.
 682 /// Note that the ordering in the Nodes vector is reversed.
 683 void SimpleSched::VisitAll() {
 684   // Add first element to list
 685   Ordering.push_back(getNI(DAG.getRoot().Val));
 686
 687   // Iterate through all nodes that have been added
 688   for (unsigned i = 0; i < Ordering.size(); i++) { // note: size() varies
 689     // Visit all operands
 690     NodeGroupOpIterator NGI(Ordering[i]);
 691     while (!NGI.isEnd()) {
 692       // Get next operand
 693       SDOperand Op = NGI.next();
 694       // Get node
 695       SDNode *Node = Op.Val;
 696       // Ignore passive nodes
 697       if (isPassiveNode(Node)) continue;
 698       // Check out node
 699       IncludeNode(getNI(Node));
 700     }
 701   }
 702
 703   // Add entry node last (IncludeNode filters entry nodes)
 704   if (DAG.getEntryNode().Val != DAG.getRoot().Val)
 705     Ordering.push_back(getNI(DAG.getEntryNode().Val));
 706
 707   // FIXME - Reverse the order
 708   for (unsigned i = 0, N = Ordering.size(), Half = N >> 1; i < Half; i++) {
 709     unsigned j = N - i - 1;
 710     NodeInfo *tmp = Ordering[i];
 711     Ordering[i] = Ordering[j];
 712     Ordering[j] = tmp;
 713   }
 714 }
 715
 716 /// IdentifyGroups - Put flagged nodes into groups.
 717 ///
 718 void SimpleSched::IdentifyGroups() {
 719   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 720     NodeInfo* NI = &Info[i];
 721     SDNode *Node = NI->Node;
 722
 723     // For each operand (in reverse to only look at flags)
 724     for (unsigned N = Node->getNumOperands(); 0 < N--;) {
 725       // Get operand
 726       SDOperand Op = Node->getOperand(N);
 727       // No more flags to walk
 728       if (Op.getValueType() != MVT::Flag) break;
 729       // Add to node group
 730       NodeGroup::Add(getNI(Op.Val), NI);
 731       // Let evryone else know
 732       HasGroups = true;
 733     }
 734   }
 735 }
 736
 737 /// GatherSchedulingInfo - Get latency and resource information about each node.
 738 ///
 739 void SimpleSched::GatherSchedulingInfo() {
 740   // Get instruction itineraries for the target
 741   const InstrItineraryData InstrItins = TM.getInstrItineraryData();
 742
 743   // For each node
 744   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 745     // Get node info
 746     NodeInfo* NI = &Info[i];
 747     SDNode *Node = NI->Node;
 748
 749     // If there are itineraries and it is a machine instruction
 750     if (InstrItins.isEmpty() || ScheduleStyle == simpleNoItinScheduling) {
 751       // If machine opcode
 752       if (Node->isTargetOpcode()) {
 753         // Get return type to guess which processing unit
 754         MVT::ValueType VT = Node->getValueType(0);
 755         // Get machine opcode
 756         MachineOpCode TOpc = Node->getTargetOpcode();
 757         NI->IsCall = TII.isCall(TOpc);
 758
 759         if (TII.isLoad(TOpc))              NI->StageBegin = &LoadStage;
 760         else if (TII.isStore(TOpc))        NI->StageBegin = &StoreStage;
 761         else if (MVT::isInteger(VT))       NI->StageBegin = &IntStage;
 762         else if (MVT::isFloatingPoint(VT)) NI->StageBegin = &FloatStage;
 763         if (NI->StageBegin) NI->StageEnd = NI->StageBegin + 1;
 764       }
 765     } else if (Node->isTargetOpcode()) {
 766       // get machine opcode
 767       MachineOpCode TOpc = Node->getTargetOpcode();
 768       // Check to see if it is a call
 769       NI->IsCall = TII.isCall(TOpc);
 770       // Get itinerary stages for instruction
 771       unsigned II = TII.getSchedClass(TOpc);
 772       NI->StageBegin = InstrItins.begin(II);
 773       NI->StageEnd = InstrItins.end(II);
 774     }
 775
 776     // One slot for the instruction itself
 777     NI->Latency = 1;
 778
 779     // Add long latency for a call to push it back in time
 780     if (NI->IsCall) NI->Latency += CallLatency;
 781
 782     // Sum up all the latencies
 783     for (InstrStage *Stage = NI->StageBegin, *E = NI->StageEnd;
 784         Stage != E; Stage++) {
 785       NI->Latency += Stage->Cycles;
 786     }
 787
 788     // Sum up all the latencies for max tally size
 789     NSlots += NI->Latency;
 790   }
 791
 792   // Unify metrics if in a group
 793   if (HasGroups) {
 794     for (unsigned i = 0, N = NodeCount; i < N; i++) {
 795       NodeInfo* NI = &Info[i];
 796
 797       if (NI->isInGroup()) {
 798         NodeGroup *Group = NI->Group;
 799
 800         if (!Group->getDominator()) {
 801           NIIterator NGI = Group->group_begin(), NGE = Group->group_end();
 802           NodeInfo *Dominator = *NGI;
 803           unsigned Latency = 0;
 804
 805           for (NGI++; NGI != NGE; NGI++) {
 806             NodeInfo* NGNI = *NGI;
 807             Latency += NGNI->Latency;
 808             if (Dominator->Latency < NGNI->Latency) Dominator = NGNI;
 809           }
 810
 811           Dominator->Latency = Latency;
 812           Group->setDominator(Dominator);
 813         }
 814       }
 815     }
 816   }
 817 }
 818
 819 /// FakeGroupDominators - Set dominators for non-scheduling.
 820 ///
 821 void SimpleSched::FakeGroupDominators() {
 822   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 823     NodeInfo* NI = &Info[i];
 824
 825     if (NI->isInGroup()) {
 826       NodeGroup *Group = NI->Group;
 827
 828       if (!Group->getDominator()) {
 829         Group->setDominator(NI);
 830       }
 831     }
 832   }
 833 }
 834
 835 /// PrepareNodeInfo - Set up the basic minimum node info for scheduling.
 836 ///
 837 void SimpleSched::PrepareNodeInfo() {
 838   // Allocate node information
 839   Info = new NodeInfo[NodeCount];
 840
 841   unsigned i = 0;
 842   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
 843        E = DAG.allnodes_end(); I != E; ++I, ++i) {
 844     // Fast reference to node schedule info
 845     NodeInfo* NI = &Info[i];
 846     // Set up map
 847     Map[I] = NI;
 848     // Set node
 849     NI->Node = I;
 850     // Set pending visit count
 851     NI->setPending(I->use_size());
 852   }
 853 }
 854
 855 /// isStrongDependency - Return true if node A has results used by node B.
 856 /// I.E., B must wait for latency of A.
 857 bool SimpleSched::isStrongDependency(NodeInfo *A, NodeInfo *B) {
 858   // If A defines for B then it's a strong dependency
 859   return isDefiner(A, B);
 860 }
 861
 862 /// isWeakDependency Return true if node A produces a result that will
 863 /// conflict with operands of B.  It is assumed that we have called
 864 /// isStrongDependency prior.
 865 bool SimpleSched::isWeakDependency(NodeInfo *A, NodeInfo *B) {
 866   // TODO check for conflicting real registers and aliases
 867 #if 0 // FIXME - Since we are in SSA form and not checking register aliasing
 868   return A->Node->getOpcode() == ISD::EntryToken || isStrongDependency(B, A);
 869 #else
 870   return A->Node->getOpcode() == ISD::EntryToken;
 871 #endif
 872 }
 873
 874 /// ScheduleBackward - Schedule instructions so that any long latency
 875 /// instructions and the critical path get pushed back in time. Time is run in
 876 /// reverse to allow code reuse of the Tally and eliminate the overhead of
 877 /// biasing every slot indices against NSlots.
 878 void SimpleSched::ScheduleBackward() {
 879   // Size and clear the resource tally
 880   Tally.Initialize(NSlots);
 881   // Get number of nodes to schedule
 882   unsigned N = Ordering.size();
 883
 884   // For each node being scheduled
 885   for (unsigned i = N; 0 < i--;) {
 886     NodeInfo *NI = Ordering[i];
 887     // Track insertion
 888     unsigned Slot = NotFound;
 889
 890     // Compare against those previously scheduled nodes
 891     unsigned j = i + 1;
 892     for (; j < N; j++) {
 893       // Get following instruction
 894       NodeInfo *Other = Ordering[j];
 895
 896       // Check dependency against previously inserted nodes
 897       if (isStrongDependency(NI, Other)) {
 898         Slot = Other->Slot + Other->Latency;
 899         break;
 900       } else if (isWeakDependency(NI, Other)) {
 901         Slot = Other->Slot;
 902         break;
 903       }
 904     }
 905
 906     // If independent of others (or first entry)
 907     if (Slot == NotFound) Slot = 0;
 908
 909 #if 0 // FIXME - measure later
 910     // Find a slot where the needed resources are available
 911     if (NI->StageBegin != NI->StageEnd)
 912       Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd);
 913 #endif
 914
 915     // Set node slot
 916     NI->Slot = Slot;
 917
 918     // Insert sort based on slot
 919     j = i + 1;
 920     for (; j < N; j++) {
 921       // Get following instruction
 922       NodeInfo *Other = Ordering[j];
 923       // Should we look further (remember slots are in reverse time)
 924       if (Slot >= Other->Slot) break;
 925       // Shuffle other into ordering
 926       Ordering[j - 1] = Other;
 927     }
 928     // Insert node in proper slot
 929     if (j != i + 1) Ordering[j - 1] = NI;
 930   }
 931 }
 932
 933 /// ScheduleForward - Schedule instructions to maximize packing.
 934 ///
 935 void SimpleSched::ScheduleForward() {
 936   // Size and clear the resource tally
 937   Tally.Initialize(NSlots);
 938   // Get number of nodes to schedule
 939   unsigned N = Ordering.size();
 940
 941   // For each node being scheduled
 942   for (unsigned i = 0; i < N; i++) {
 943     NodeInfo *NI = Ordering[i];
 944     // Track insertion
 945     unsigned Slot = NotFound;
 946
 947     // Compare against those previously scheduled nodes
 948     unsigned j = i;
 949     for (; 0 < j--;) {
 950       // Get following instruction
 951       NodeInfo *Other = Ordering[j];
 952
 953       // Check dependency against previously inserted nodes
 954       if (isStrongDependency(Other, NI)) {
 955         Slot = Other->Slot + Other->Latency;
 956         break;
 957       } else if (Other->IsCall || isWeakDependency(Other, NI)) {
 958         Slot = Other->Slot;
 959         break;
 960       }
 961     }
 962
 963     // If independent of others (or first entry)
 964     if (Slot == NotFound) Slot = 0;
 965
 966     // Find a slot where the needed resources are available
 967     if (NI->StageBegin != NI->StageEnd)
 968       Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd);
 969
 970     // Set node slot
 971     NI->Slot = Slot;
 972
 973     // Insert sort based on slot
 974     j = i;
 975     for (; 0 < j--;) {
 976       // Get prior instruction
 977       NodeInfo *Other = Ordering[j];
 978       // Should we look further
 979       if (Slot >= Other->Slot) break;
 980       // Shuffle other into ordering
 981       Ordering[j + 1] = Other;
 982     }
 983     // Insert node in proper slot
 984     if (j != i) Ordering[j + 1] = NI;
 985   }
 986 }
 987
 988 /// EmitAll - Emit all nodes in schedule sorted order.
 989 ///
 990 void SimpleSched::EmitAll() {
 991   // For each node in the ordering
 992   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
 993     // Get the scheduling info
 994     NodeInfo *NI = Ordering[i];
 995     // Iterate through nodes
 996     NodeGroupIterator NGI(Ordering[i]);
 997     if (NI->isInGroup()) {
 998       if (NI->isGroupDominator()) {
 999         NodeGroupIterator NGI(Ordering[i]);
1000         while (NodeInfo *NI = NGI.next()) EmitNode(NI);
1001       }
1002     } else {
1003       EmitNode(NI);
1004     }
1005   }
1006 }
1007
1008 /// CountResults - The results of target nodes have register or immediate
1009 /// operands first, then an optional chain, and optional flag operands (which do
1010 /// not go into the machine instrs.)
1011 unsigned SimpleSched::CountResults(SDNode *Node) {
1012   unsigned N = Node->getNumValues();
1013   while (N && Node->getValueType(N - 1) == MVT::Flag)
1014     --N;
1015   if (N && Node->getValueType(N - 1) == MVT::Other)
1016     --N;    // Skip over chain result.
1017   return N;
1018 }
1019
1020 /// CountOperands  The inputs to target nodes have any actual inputs first,
1021 /// followed by an optional chain operand, then flag operands.  Compute the
1022 /// number of actual operands that  will go into the machine instr.
1023 unsigned SimpleSched::CountOperands(SDNode *Node) {
1024   unsigned N = Node->getNumOperands();
1025   while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag)
1026     --N;
1027   if (N && Node->getOperand(N - 1).getValueType() == MVT::Other)
1028     --N; // Ignore chain if it exists.
1029   return N;
1030 }
1031
1032 /// CreateVirtualRegisters - Add result register values for things that are
1033 /// defined by this instruction.
1034 unsigned SimpleSched::CreateVirtualRegisters(MachineInstr *MI,
1035                                              unsigned NumResults,
1036                                              const TargetInstrDescriptor &II) {
1037   // Create the result registers for this node and add the result regs to
1038   // the machine instruction.
1039   const TargetOperandInfo *OpInfo = II.OpInfo;
1040   unsigned ResultReg = RegMap->createVirtualRegister(OpInfo[0].RegClass);
1041   MI->addRegOperand(ResultReg, MachineOperand::Def);
1042   for (unsigned i = 1; i != NumResults; ++i) {
1043     assert(OpInfo[i].RegClass && "Isn't a register operand!");
1044     MI->addRegOperand(RegMap->createVirtualRegister(OpInfo[i].RegClass),
1045                       MachineOperand::Def);
1046   }
1047   return ResultReg;
1048 }
1049
1050 /// EmitNode - Generate machine code for an node and needed dependencies.
1051 ///
1052 void SimpleSched::EmitNode(NodeInfo *NI) {
1053   unsigned VRBase = 0;                 // First virtual register for node
1054   SDNode *Node = NI->Node;
1055
1056   // If machine instruction
1057   if (Node->isTargetOpcode()) {
1058     unsigned Opc = Node->getTargetOpcode();
1059     const TargetInstrDescriptor &II = TII.get(Opc);
1060
1061     unsigned NumResults = CountResults(Node);
1062     unsigned NodeOperands = CountOperands(Node);
1063     unsigned NumMIOperands = NodeOperands + NumResults;
1064 #ifndef NDEBUG
1065     assert((unsigned(II.numOperands) == NumMIOperands || II.numOperands == -1)&&
1066            "#operands for dag node doesn't match .td file!");
1067 #endif
1068
1069     // Create the new machine instruction.
1070     MachineInstr *MI = new MachineInstr(Opc, NumMIOperands, true, true);
1071
1072     // Add result register values for things that are defined by this
1073     // instruction.
1074
1075     // If the node is only used by a CopyToReg and the dest reg is a vreg, use
1076     // the CopyToReg'd destination register instead of creating a new vreg.
1077     if (NumResults == 1) {
1078       for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
1079            UI != E; ++UI) {
1080         SDNode *Use = *UI;
1081         if (Use->getOpcode() == ISD::CopyToReg &&
1082             Use->getOperand(2).Val == Node) {
1083           unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
1084           if (MRegisterInfo::isVirtualRegister(Reg)) {
1085             VRBase = Reg;
1086             MI->addRegOperand(Reg, MachineOperand::Def);
1087             break;
1088           }
1089         }
1090       }
1091     }
1092
1093     // Otherwise, create new virtual registers.
1094     if (NumResults && VRBase == 0)
1095       VRBase = CreateVirtualRegisters(MI, NumResults, II);
1096
1097     // Emit all of the actual operands of this instruction, adding them to the
1098     // instruction as appropriate.
1099     for (unsigned i = 0; i != NodeOperands; ++i) {
1100       if (Node->getOperand(i).isTargetOpcode()) {
1101         // Note that this case is redundant with the final else block, but we
1102         // include it because it is the most common and it makes the logic
1103         // simpler here.
1104         assert(Node->getOperand(i).getValueType() != MVT::Other &&
1105                Node->getOperand(i).getValueType() != MVT::Flag &&
1106                "Chain and flag operands should occur at end of operand list!");
1107
1108         // Get/emit the operand.
1109         unsigned VReg = getVR(Node->getOperand(i));
1110         MI->addRegOperand(VReg, MachineOperand::Use);
1111
1112         // Verify that it is right.
1113         assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?");
1114         assert(II.OpInfo[i+NumResults].RegClass &&
1115                "Don't have operand info for this instruction!");
1116         assert(RegMap->getRegClass(VReg) == II.OpInfo[i+NumResults].RegClass &&
1117                "Register class of operand and regclass of use don't agree!");
1118       } else if (ConstantSDNode *C =
1119                  dyn_cast<ConstantSDNode>(Node->getOperand(i))) {
1120         MI->addZeroExtImm64Operand(C->getValue());
1121       } else if (RegisterSDNode*R =
1122                  dyn_cast<RegisterSDNode>(Node->getOperand(i))) {
1123         MI->addRegOperand(R->getReg(), MachineOperand::Use);
1124       } else if (GlobalAddressSDNode *TGA =
1125                        dyn_cast<GlobalAddressSDNode>(Node->getOperand(i))) {
1126         MI->addGlobalAddressOperand(TGA->getGlobal(), false, TGA->getOffset());
1127       } else if (BasicBlockSDNode *BB =
1128                        dyn_cast<BasicBlockSDNode>(Node->getOperand(i))) {
1129         MI->addMachineBasicBlockOperand(BB->getBasicBlock());
1130       } else if (FrameIndexSDNode *FI =
1131                        dyn_cast<FrameIndexSDNode>(Node->getOperand(i))) {
1132         MI->addFrameIndexOperand(FI->getIndex());
1133       } else if (ConstantPoolSDNode *CP =
1134                     dyn_cast<ConstantPoolSDNode>(Node->getOperand(i))) {
1135         unsigned Idx = ConstPool->getConstantPoolIndex(CP->get());
1136         MI->addConstantPoolIndexOperand(Idx);
1137       } else if (ExternalSymbolSDNode *ES =
1138                  dyn_cast<ExternalSymbolSDNode>(Node->getOperand(i))) {
1139         MI->addExternalSymbolOperand(ES->getSymbol(), false);
1140       } else {
1141         assert(Node->getOperand(i).getValueType() != MVT::Other &&
1142                Node->getOperand(i).getValueType() != MVT::Flag &&
1143                "Chain and flag operands should occur at end of operand list!");
1144         unsigned VReg = getVR(Node->getOperand(i));
1145         MI->addRegOperand(VReg, MachineOperand::Use);
1146
1147         // Verify that it is right.
1148         assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?");
1149         assert(II.OpInfo[i+NumResults].RegClass &&
1150                "Don't have operand info for this instruction!");
1151         assert(RegMap->getRegClass(VReg) == II.OpInfo[i+NumResults].RegClass &&
1152                "Register class of operand and regclass of use don't agree!");
1153       }
1154     }
1155
1156     // Now that we have emitted all operands, emit this instruction itself.
1157     if ((II.Flags & M_USES_CUSTOM_DAG_SCHED_INSERTION) == 0) {
1158       BB->insert(BB->end(), MI);
1159     } else {
1160       // Insert this instruction into the end of the basic block, potentially
1161       // taking some custom action.
1162       BB = DAG.getTargetLoweringInfo().InsertAtEndOfBasicBlock(MI, BB);
1163     }
1164   } else {
1165     switch (Node->getOpcode()) {
1166     default:
1167       Node->dump();
1168       assert(0 && "This target-independent node should have been selected!");
1169     case ISD::EntryToken: // fall thru
1170     case ISD::TokenFactor:
1171       break;
1172     case ISD::CopyToReg: {
1173       unsigned InReg = getVR(Node->getOperand(2));
1174       unsigned DestReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
1175       if (InReg != DestReg)   // Coallesced away the copy?
1176         MRI.copyRegToReg(*BB, BB->end(), DestReg, InReg,
1177                          RegMap->getRegClass(InReg));
1178       break;
1179     }
1180     case ISD::CopyFromReg: {
1181       unsigned SrcReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
1182       if (MRegisterInfo::isVirtualRegister(SrcReg)) {
1183         VRBase = SrcReg;  // Just use the input register directly!
1184         break;
1185       }
1186
1187       // If the node is only used by a CopyToReg and the dest reg is a vreg, use
1188       // the CopyToReg'd destination register instead of creating a new vreg.
1189       for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end();
1190            UI != E; ++UI) {
1191         SDNode *Use = *UI;
1192         if (Use->getOpcode() == ISD::CopyToReg &&
1193             Use->getOperand(2).Val == Node) {
1194           unsigned DestReg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
1195           if (MRegisterInfo::isVirtualRegister(DestReg)) {
1196             VRBase = DestReg;
1197             break;
1198           }
1199         }
1200       }
1201
1202       // Figure out the register class to create for the destreg.
1203       const TargetRegisterClass *TRC = 0;
1204       if (VRBase) {
1205         TRC = RegMap->getRegClass(VRBase);
1206       } else {
1207
1208         // Pick the register class of the right type that contains this physreg.
1209         for (MRegisterInfo::regclass_iterator I = MRI.regclass_begin(),
1210              E = MRI.regclass_end(); I != E; ++I)
1211           if ((*I)->hasType(Node->getValueType(0)) &&
1212               (*I)->contains(SrcReg)) {
1213             TRC = *I;
1214             break;
1215           }
1216         assert(TRC && "Couldn't find register class for reg copy!");
1217
1218         // Create the reg, emit the copy.
1219         VRBase = RegMap->createVirtualRegister(TRC);
1220       }
1221       MRI.copyRegToReg(*BB, BB->end(), VRBase, SrcReg, TRC);
1222       break;
1223     }
1224     }
1225   }
1226
1227   assert(NI->VRBase == 0 && "Node emitted out of order - early");
1228   NI->VRBase = VRBase;
1229 }
1230
1231 /// Schedule - Order nodes according to selected style.
1232 ///
1233 void SimpleSched::Schedule() {
1234   // Number the nodes
1235   NodeCount = std::distance(DAG.allnodes_begin(), DAG.allnodes_end());
1236   // Test to see if scheduling should occur
1237   bool ShouldSchedule = NodeCount > 3 && ScheduleStyle != noScheduling;
1238   // Set up minimum info for scheduling
1239   PrepareNodeInfo();
1240   // Construct node groups for flagged nodes
1241   IdentifyGroups();
1242
1243   // Don't waste time if is only entry and return
1244   if (ShouldSchedule) {
1245     // Get latency and resource requirements
1246     GatherSchedulingInfo();
1247   } else if (HasGroups) {
1248     // Make sure all the groups have dominators
1249     FakeGroupDominators();
1250   }
1251
1252   // Breadth first walk of DAG
1253   VisitAll();
1254
1255 #ifndef NDEBUG
1256   static unsigned Count = 0;
1257   Count++;
1258   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
1259     NodeInfo *NI = Ordering[i];
1260     NI->Preorder = i;
1261   }
1262 #endif
1263
1264   // Don't waste time if is only entry and return
1265   if (ShouldSchedule) {
1266     // Push back long instructions and critical path
1267     ScheduleBackward();
1268
1269     // Pack instructions to maximize resource utilization
1270     ScheduleForward();
1271   }
1272
1273   DEBUG(printChanges(Count));
1274
1275   // Emit in scheduled order
1276   EmitAll();
1277 }
1278
1279 /// printChanges - Hilight changes in order caused by scheduling.
1280 ///
1281 void SimpleSched::printChanges(unsigned Index) {
1282 #ifndef NDEBUG
1283   // Get the ordered node count
1284   unsigned N = Ordering.size();
1285   // Determine if any changes
1286   unsigned i = 0;
1287   for (; i < N; i++) {
1288     NodeInfo *NI = Ordering[i];
1289     if (NI->Preorder != i) break;
1290   }
1291
1292   if (i < N) {
1293     std::cerr << Index << ". New Ordering\n";
1294
1295     for (i = 0; i < N; i++) {
1296       NodeInfo *NI = Ordering[i];
1297       std::cerr << "  " << NI->Preorder << ". ";
1298       printSI(std::cerr, NI);
1299       std::cerr << "\n";
1300       if (NI->isGroupDominator()) {
1301         NodeGroup *Group = NI->Group;
1302         for (NIIterator NII = Group->group_begin(), E = Group->group_end();
1303              NII != E; NII++) {
1304           std::cerr << "          ";
1305           printSI(std::cerr, *NII);
1306           std::cerr << "\n";
1307         }
1308       }
1309     }
1310   } else {
1311     std::cerr << Index << ". No Changes\n";
1312   }
1313 #endif
1314 }
1315
1316 /// printSI - Print schedule info.
1317 ///
1318 void SimpleSched::printSI(std::ostream &O, NodeInfo *NI) const {
1319 #ifndef NDEBUG
1320   SDNode *Node = NI->Node;
1321   O << " "
1322     << std::hex << Node << std::dec
1323     << ", Lat=" << NI->Latency
1324     << ", Slot=" << NI->Slot
1325     << ", ARITY=(" << Node->getNumOperands() << ","
1326                    << Node->getNumValues() << ")"
1327     << " " << Node->getOperationName(&DAG);
1328   if (isFlagDefiner(Node)) O << "<#";
1329   if (isFlagUser(Node)) O << ">#";
1330 #endif
1331 }
1332
1333 /// print - Print ordering to specified output stream.
1334 ///
1335 void SimpleSched::print(std::ostream &O) const {
1336 #ifndef NDEBUG
1337   using namespace std;
1338   O << "Ordering\n";
1339   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
1340     NodeInfo *NI = Ordering[i];
1341     printSI(O, NI);
1342     O << "\n";
1343     if (NI->isGroupDominator()) {
1344       NodeGroup *Group = NI->Group;
1345       for (NIIterator NII = Group->group_begin(), E = Group->group_end();
1346            NII != E; NII++) {
1347         O << "    ";
1348         printSI(O, *NII);
1349         O << "\n";
1350       }
1351     }
1352   }
1353 #endif
1354 }
1355
1356 /// dump - Print ordering to std::cerr.
1357 ///
1358 void SimpleSched::dump() const {
1359   print(std::cerr);
1360 }
1361 //===----------------------------------------------------------------------===//
1362
1363
1364 //===----------------------------------------------------------------------===//
1365 /// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each
1366 /// target node in the graph.
1367 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &SD) {
1368   if (ViewDAGs) SD.viewGraph();
1369   BB = SimpleSched(SD, BB).Run();
1370 }