lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp

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