lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp

   1 //===-- ScheduleDAGSimple.cpp - Implement a trivial DAG scheduler ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by James M. Laskey and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements a simple two pass scheduler.  The first pass attempts to push
  11 // backward any lengthy instructions and critical paths.  The second pass packs
  12 // instructions into semi-optimal time slots.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "sched"
  17 #include "llvm/CodeGen/ScheduleDAG.h"
  18 #include "llvm/CodeGen/SelectionDAG.h"
  19 #include "llvm/Target/TargetMachine.h"
  20 #include "llvm/Target/TargetInstrInfo.h"
  21 #include "llvm/Support/Debug.h"
  22 using namespace llvm;
  23
  24 namespace {
  25 //===----------------------------------------------------------------------===//
  26 ///
  27 /// BitsIterator - Provides iteration through individual bits in a bit vector.
  28 ///
  29 template<class T>
  30 class BitsIterator {
  31 private:
  32   T Bits;                               // Bits left to iterate through
  33
  34 public:
  35   /// Ctor.
  36   BitsIterator(T Initial) : Bits(Initial) {}
  37
  38   /// Next - Returns the next bit set or zero if exhausted.
  39   inline T Next() {
  40     // Get the rightmost bit set
  41     T Result = Bits & -Bits;
  42     // Remove from rest
  43     Bits &= ~Result;
  44     // Return single bit or zero
  45     return Result;
  46   }
  47 };
  48
  49 //===----------------------------------------------------------------------===//
  50
  51
  52 //===----------------------------------------------------------------------===//
  53 ///
  54 /// ResourceTally - Manages the use of resources over time intervals.  Each
  55 /// item (slot) in the tally vector represents the resources used at a given
  56 /// moment.  A bit set to 1 indicates that a resource is in use, otherwise
  57 /// available.  An assumption is made that the tally is large enough to schedule
  58 /// all current instructions (asserts otherwise.)
  59 ///
  60 template<class T>
  61 class ResourceTally {
  62 private:
  63   std::vector<T> Tally;                 // Resources used per slot
  64   typedef typename std::vector<T>::iterator Iter;
  65                                         // Tally iterator
  66
  67   /// SlotsAvailable - Returns true if all units are available.
  68         ///
  69   bool SlotsAvailable(Iter Begin, unsigned N, unsigned ResourceSet,
  70                                               unsigned &Resource) {
  71     assert(N && "Must check availability with N != 0");
  72     // Determine end of interval
  73     Iter End = Begin + N;
  74     assert(End <= Tally.end() && "Tally is not large enough for schedule");
  75
  76     // Iterate thru each resource
  77     BitsIterator<T> Resources(ResourceSet & ~*Begin);
  78     while (unsigned Res = Resources.Next()) {
  79       // Check if resource is available for next N slots
  80       Iter Interval = End;
  81       do {
  82         Interval--;
  83         if (*Interval & Res) break;
  84       } while (Interval != Begin);
  85
  86       // If available for N
  87       if (Interval == Begin) {
  88         // Success
  89         Resource = Res;
  90         return true;
  91       }
  92     }
  93
  94     // No luck
  95     Resource = 0;
  96     return false;
  97   }
  98
  99         /// RetrySlot - Finds a good candidate slot to retry search.
 100   Iter RetrySlot(Iter Begin, unsigned N, unsigned ResourceSet) {
 101     assert(N && "Must check availability with N != 0");
 102     // Determine end of interval
 103     Iter End = Begin + N;
 104     assert(End <= Tally.end() && "Tally is not large enough for schedule");
 105
 106                 while (Begin != End--) {
 107                         // Clear units in use
 108                         ResourceSet &= ~*End;
 109                         // If no units left then we should go no further
 110                         if (!ResourceSet) return End + 1;
 111                 }
 112                 // Made it all the way through
 113                 return Begin;
 114         }
 115
 116   /// FindAndReserveStages - Return true if the stages can be completed. If
 117   /// so mark as busy.
 118   bool FindAndReserveStages(Iter Begin,
 119                             InstrStage *Stage, InstrStage *StageEnd) {
 120     // If at last stage then we're done
 121     if (Stage == StageEnd) return true;
 122     // Get number of cycles for current stage
 123     unsigned N = Stage->Cycles;
 124     // Check to see if N slots are available, if not fail
 125     unsigned Resource;
 126     if (!SlotsAvailable(Begin, N, Stage->Units, Resource)) return false;
 127     // Check to see if remaining stages are available, if not fail
 128     if (!FindAndReserveStages(Begin + N, Stage + 1, StageEnd)) return false;
 129     // Reserve resource
 130     Reserve(Begin, N, Resource);
 131     // Success
 132     return true;
 133   }
 134
 135   /// Reserve - Mark busy (set) the specified N slots.
 136   void Reserve(Iter Begin, unsigned N, unsigned Resource) {
 137     // Determine end of interval
 138     Iter End = Begin + N;
 139     assert(End <= Tally.end() && "Tally is not large enough for schedule");
 140
 141     // Set resource bit in each slot
 142     for (; Begin < End; Begin++)
 143       *Begin |= Resource;
 144   }
 145
 146   /// FindSlots - Starting from Begin, locate consecutive slots where all stages
 147   /// can be completed.  Returns the address of first slot.
 148   Iter FindSlots(Iter Begin, InstrStage *StageBegin, InstrStage *StageEnd) {
 149     // Track position
 150     Iter Cursor = Begin;
 151
 152     // Try all possible slots forward
 153     while (true) {
 154       // Try at cursor, if successful return position.
 155       if (FindAndReserveStages(Cursor, StageBegin, StageEnd)) return Cursor;
 156       // Locate a better position
 157                         Cursor = RetrySlot(Cursor + 1, StageBegin->Cycles, StageBegin->Units);
 158     }
 159   }
 160
 161 public:
 162   /// Initialize - Resize and zero the tally to the specified number of time
 163   /// slots.
 164   inline void Initialize(unsigned N) {
 165     Tally.assign(N, 0);   // Initialize tally to all zeros.
 166   }
 167
 168   // FindAndReserve - Locate an ideal slot for the specified stages and mark
 169   // as busy.
 170   unsigned FindAndReserve(unsigned Slot, InstrStage *StageBegin,
 171                                          InstrStage *StageEnd) {
 172                 // Where to begin
 173                 Iter Begin = Tally.begin() + Slot;
 174                 // Find a free slot
 175                 Iter Where = FindSlots(Begin, StageBegin, StageEnd);
 176                 // Distance is slot number
 177                 unsigned Final = Where - Tally.begin();
 178     return Final;
 179   }
 180
 181 };
 182
 183 //===----------------------------------------------------------------------===//
 184 ///
 185 /// ScheduleDAGSimple - Simple two pass scheduler.
 186 ///
 187 class ScheduleDAGSimple : public ScheduleDAG {
 188 private:
 189   ResourceTally<unsigned> Tally;        // Resource usage tally
 190   unsigned NSlots;                      // Total latency
 191   static const unsigned NotFound = ~0U; // Search marker
 192
 193 public:
 194
 195   // Ctor.
 196   ScheduleDAGSimple(SchedHeuristics hstc, SelectionDAG &dag,
 197                     MachineBasicBlock *bb, const TargetMachine &tm)
 198     : ScheduleDAG(hstc, dag, bb, tm), Tally(), NSlots(0) {
 199     assert(&TII && "Target doesn't provide instr info?");
 200     assert(&MRI && "Target doesn't provide register info?");
 201   }
 202
 203   virtual ~ScheduleDAGSimple() {};
 204
 205   void Schedule();
 206
 207 private:
 208   static bool isDefiner(NodeInfo *A, NodeInfo *B);
 209   void IncludeNode(NodeInfo *NI);
 210   void VisitAll();
 211   void GatherSchedulingInfo();
 212   void FakeGroupDominators();
 213   bool isStrongDependency(NodeInfo *A, NodeInfo *B);
 214   bool isWeakDependency(NodeInfo *A, NodeInfo *B);
 215   void ScheduleBackward();
 216   void ScheduleForward();
 217 };
 218
 219 //===----------------------------------------------------------------------===//
 220 /// Special case itineraries.
 221 ///
 222 enum {
 223   CallLatency = 40,          // To push calls back in time
 224
 225   RSInteger   = 0xC0000000,  // Two integer units
 226   RSFloat     = 0x30000000,  // Two float units
 227   RSLoadStore = 0x0C000000,  // Two load store units
 228   RSBranch    = 0x02000000   // One branch unit
 229 };
 230 static InstrStage CallStage  = { CallLatency, RSBranch };
 231 static InstrStage LoadStage  = { 5, RSLoadStore };
 232 static InstrStage StoreStage = { 2, RSLoadStore };
 233 static InstrStage IntStage   = { 2, RSInteger };
 234 static InstrStage FloatStage = { 3, RSFloat };
 235 //===----------------------------------------------------------------------===//
 236
 237 } // namespace
 238
 239 //===----------------------------------------------------------------------===//
 240
 241
 242 //===----------------------------------------------------------------------===//
 243 /// isDefiner - Return true if node A is a definer for B.
 244 ///
 245 bool ScheduleDAGSimple::isDefiner(NodeInfo *A, NodeInfo *B) {
 246   // While there are A nodes
 247   NodeGroupIterator NII(A);
 248   while (NodeInfo *NI = NII.next()) {
 249     // Extract node
 250     SDNode *Node = NI->Node;
 251     // While there operands in nodes of B
 252     NodeGroupOpIterator NGOI(B);
 253     while (!NGOI.isEnd()) {
 254       SDOperand Op = NGOI.next();
 255       // If node from A defines a node in B
 256       if (Node == Op.Val) return true;
 257     }
 258   }
 259   return false;
 260 }
 261
 262 /// IncludeNode - Add node to NodeInfo vector.
 263 ///
 264 void ScheduleDAGSimple::IncludeNode(NodeInfo *NI) {
 265   // Get node
 266   SDNode *Node = NI->Node;
 267   // Ignore entry node
 268   if (Node->getOpcode() == ISD::EntryToken) return;
 269   // Check current count for node
 270   int Count = NI->getPending();
 271   // If the node is already in list
 272   if (Count < 0) return;
 273   // Decrement count to indicate a visit
 274   Count--;
 275   // If count has gone to zero then add node to list
 276   if (!Count) {
 277     // Add node
 278     if (NI->isInGroup()) {
 279       Ordering.push_back(NI->Group->getDominator());
 280     } else {
 281       Ordering.push_back(NI);
 282     }
 283     // indicate node has been added
 284     Count--;
 285   }
 286   // Mark as visited with new count
 287   NI->setPending(Count);
 288 }
 289
 290 /// GatherSchedulingInfo - Get latency and resource information about each node.
 291 ///
 292 void ScheduleDAGSimple::GatherSchedulingInfo() {
 293   // Get instruction itineraries for the target
 294   const InstrItineraryData InstrItins = TM.getInstrItineraryData();
 295
 296   // For each node
 297   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 298     // Get node info
 299     NodeInfo* NI = &Info[i];
 300     SDNode *Node = NI->Node;
 301
 302     // If there are itineraries and it is a machine instruction
 303     if (InstrItins.isEmpty() || Heuristic == simpleNoItinScheduling) {
 304       // If machine opcode
 305       if (Node->isTargetOpcode()) {
 306         // Get return type to guess which processing unit
 307         MVT::ValueType VT = Node->getValueType(0);
 308         // Get machine opcode
 309         MachineOpCode TOpc = Node->getTargetOpcode();
 310         NI->IsCall = TII->isCall(TOpc);
 311         NI->IsLoad = TII->isLoad(TOpc);
 312         NI->IsStore = TII->isStore(TOpc);
 313
 314         if (TII->isLoad(TOpc))             NI->StageBegin = &LoadStage;
 315         else if (TII->isStore(TOpc))       NI->StageBegin = &StoreStage;
 316         else if (MVT::isInteger(VT))       NI->StageBegin = &IntStage;
 317         else if (MVT::isFloatingPoint(VT)) NI->StageBegin = &FloatStage;
 318         if (NI->StageBegin) NI->StageEnd = NI->StageBegin + 1;
 319       }
 320     } else if (Node->isTargetOpcode()) {
 321       // get machine opcode
 322       MachineOpCode TOpc = Node->getTargetOpcode();
 323       // Check to see if it is a call
 324       NI->IsCall = TII->isCall(TOpc);
 325       // Get itinerary stages for instruction
 326       unsigned II = TII->getSchedClass(TOpc);
 327       NI->StageBegin = InstrItins.begin(II);
 328       NI->StageEnd = InstrItins.end(II);
 329     }
 330
 331     // One slot for the instruction itself
 332     NI->Latency = 1;
 333
 334     // Add long latency for a call to push it back in time
 335     if (NI->IsCall) NI->Latency += CallLatency;
 336
 337     // Sum up all the latencies
 338     for (InstrStage *Stage = NI->StageBegin, *E = NI->StageEnd;
 339         Stage != E; Stage++) {
 340       NI->Latency += Stage->Cycles;
 341     }
 342
 343     // Sum up all the latencies for max tally size
 344     NSlots += NI->Latency;
 345   }
 346
 347   // Unify metrics if in a group
 348   if (HasGroups) {
 349     for (unsigned i = 0, N = NodeCount; i < N; i++) {
 350       NodeInfo* NI = &Info[i];
 351
 352       if (NI->isInGroup()) {
 353         NodeGroup *Group = NI->Group;
 354
 355         if (!Group->getDominator()) {
 356           NIIterator NGI = Group->group_begin(), NGE = Group->group_end();
 357           NodeInfo *Dominator = *NGI;
 358           unsigned Latency = 0;
 359
 360           for (NGI++; NGI != NGE; NGI++) {
 361             NodeInfo* NGNI = *NGI;
 362             Latency += NGNI->Latency;
 363             if (Dominator->Latency < NGNI->Latency) Dominator = NGNI;
 364           }
 365
 366           Dominator->Latency = Latency;
 367           Group->setDominator(Dominator);
 368         }
 369       }
 370     }
 371   }
 372 }
 373
 374 /// VisitAll - Visit each node breadth-wise to produce an initial ordering.
 375 /// Note that the ordering in the Nodes vector is reversed.
 376 void ScheduleDAGSimple::VisitAll() {
 377   // Add first element to list
 378   NodeInfo *NI = getNI(DAG.getRoot().Val);
 379   if (NI->isInGroup()) {
 380     Ordering.push_back(NI->Group->getDominator());
 381   } else {
 382     Ordering.push_back(NI);
 383   }
 384
 385   // Iterate through all nodes that have been added
 386   for (unsigned i = 0; i < Ordering.size(); i++) { // note: size() varies
 387     // Visit all operands
 388     NodeGroupOpIterator NGI(Ordering[i]);
 389     while (!NGI.isEnd()) {
 390       // Get next operand
 391       SDOperand Op = NGI.next();
 392       // Get node
 393       SDNode *Node = Op.Val;
 394       // Ignore passive nodes
 395       if (isPassiveNode(Node)) continue;
 396       // Check out node
 397       IncludeNode(getNI(Node));
 398     }
 399   }
 400
 401   // Add entry node last (IncludeNode filters entry nodes)
 402   if (DAG.getEntryNode().Val != DAG.getRoot().Val)
 403     Ordering.push_back(getNI(DAG.getEntryNode().Val));
 404
 405   // Reverse the order
 406   std::reverse(Ordering.begin(), Ordering.end());
 407 }
 408
 409 /// FakeGroupDominators - Set dominators for non-scheduling.
 410 ///
 411 void ScheduleDAGSimple::FakeGroupDominators() {
 412   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 413     NodeInfo* NI = &Info[i];
 414
 415     if (NI->isInGroup()) {
 416       NodeGroup *Group = NI->Group;
 417
 418       if (!Group->getDominator()) {
 419         Group->setDominator(NI);
 420       }
 421     }
 422   }
 423 }
 424
 425 /// isStrongDependency - Return true if node A has results used by node B.
 426 /// I.E., B must wait for latency of A.
 427 bool ScheduleDAGSimple::isStrongDependency(NodeInfo *A, NodeInfo *B) {
 428   // If A defines for B then it's a strong dependency or
 429   // if a load follows a store (may be dependent but why take a chance.)
 430   return isDefiner(A, B) || (A->IsStore && B->IsLoad);
 431 }
 432
 433 /// isWeakDependency Return true if node A produces a result that will
 434 /// conflict with operands of B.  It is assumed that we have called
 435 /// isStrongDependency prior.
 436 bool ScheduleDAGSimple::isWeakDependency(NodeInfo *A, NodeInfo *B) {
 437   // TODO check for conflicting real registers and aliases
 438 #if 0 // FIXME - Since we are in SSA form and not checking register aliasing
 439   return A->Node->getOpcode() == ISD::EntryToken || isStrongDependency(B, A);
 440 #else
 441   return A->Node->getOpcode() == ISD::EntryToken;
 442 #endif
 443 }
 444
 445 /// ScheduleBackward - Schedule instructions so that any long latency
 446 /// instructions and the critical path get pushed back in time. Time is run in
 447 /// reverse to allow code reuse of the Tally and eliminate the overhead of
 448 /// biasing every slot indices against NSlots.
 449 void ScheduleDAGSimple::ScheduleBackward() {
 450   // Size and clear the resource tally
 451   Tally.Initialize(NSlots);
 452   // Get number of nodes to schedule
 453   unsigned N = Ordering.size();
 454
 455   // For each node being scheduled
 456   for (unsigned i = N; 0 < i--;) {
 457     NodeInfo *NI = Ordering[i];
 458     // Track insertion
 459     unsigned Slot = NotFound;
 460
 461     // Compare against those previously scheduled nodes
 462     unsigned j = i + 1;
 463     for (; j < N; j++) {
 464       // Get following instruction
 465       NodeInfo *Other = Ordering[j];
 466
 467       // Check dependency against previously inserted nodes
 468       if (isStrongDependency(NI, Other)) {
 469         Slot = Other->Slot + Other->Latency;
 470         break;
 471       } else if (isWeakDependency(NI, Other)) {
 472         Slot = Other->Slot;
 473         break;
 474       }
 475     }
 476
 477     // If independent of others (or first entry)
 478     if (Slot == NotFound) Slot = 0;
 479
 480 #if 0 // FIXME - measure later
 481     // Find a slot where the needed resources are available
 482     if (NI->StageBegin != NI->StageEnd)
 483       Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd);
 484 #endif
 485
 486     // Set node slot
 487     NI->Slot = Slot;
 488
 489     // Insert sort based on slot
 490     j = i + 1;
 491     for (; j < N; j++) {
 492       // Get following instruction
 493       NodeInfo *Other = Ordering[j];
 494       // Should we look further (remember slots are in reverse time)
 495       if (Slot >= Other->Slot) break;
 496       // Shuffle other into ordering
 497       Ordering[j - 1] = Other;
 498     }
 499     // Insert node in proper slot
 500     if (j != i + 1) Ordering[j - 1] = NI;
 501   }
 502 }
 503
 504 /// ScheduleForward - Schedule instructions to maximize packing.
 505 ///
 506 void ScheduleDAGSimple::ScheduleForward() {
 507   // Size and clear the resource tally
 508   Tally.Initialize(NSlots);
 509   // Get number of nodes to schedule
 510   unsigned N = Ordering.size();
 511
 512   // For each node being scheduled
 513   for (unsigned i = 0; i < N; i++) {
 514     NodeInfo *NI = Ordering[i];
 515     // Track insertion
 516     unsigned Slot = NotFound;
 517
 518     // Compare against those previously scheduled nodes
 519     unsigned j = i;
 520     for (; 0 < j--;) {
 521       // Get following instruction
 522       NodeInfo *Other = Ordering[j];
 523
 524       // Check dependency against previously inserted nodes
 525       if (isStrongDependency(Other, NI)) {
 526         Slot = Other->Slot + Other->Latency;
 527         break;
 528       } else if (Other->IsCall || isWeakDependency(Other, NI)) {
 529         Slot = Other->Slot;
 530         break;
 531       }
 532     }
 533
 534     // If independent of others (or first entry)
 535     if (Slot == NotFound) Slot = 0;
 536
 537     // Find a slot where the needed resources are available
 538     if (NI->StageBegin != NI->StageEnd)
 539       Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd);
 540
 541     // Set node slot
 542     NI->Slot = Slot;
 543
 544     // Insert sort based on slot
 545     j = i;
 546     for (; 0 < j--;) {
 547       // Get prior instruction
 548       NodeInfo *Other = Ordering[j];
 549       // Should we look further
 550       if (Slot >= Other->Slot) break;
 551       // Shuffle other into ordering
 552       Ordering[j + 1] = Other;
 553     }
 554     // Insert node in proper slot
 555     if (j != i) Ordering[j + 1] = NI;
 556   }
 557 }
 558
 559 /// Schedule - Order nodes according to selected style.
 560 ///
 561 void ScheduleDAGSimple::Schedule() {
 562   // Test to see if scheduling should occur
 563   bool ShouldSchedule = NodeCount > 3 && Heuristic != noScheduling;
 564   // Don't waste time if is only entry and return
 565   if (ShouldSchedule) {
 566     // Get latency and resource requirements
 567     GatherSchedulingInfo();
 568   } else if (HasGroups) {
 569     // Make sure all the groups have dominators
 570     FakeGroupDominators();
 571   }
 572
 573   // Breadth first walk of DAG
 574   VisitAll();
 575
 576 #ifndef NDEBUG
 577   static unsigned Count = 0;
 578   Count++;
 579   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
 580     NodeInfo *NI = Ordering[i];
 581     NI->Preorder = i;
 582   }
 583 #endif
 584
 585   // Don't waste time if is only entry and return
 586   if (ShouldSchedule) {
 587     // Push back long instructions and critical path
 588     ScheduleBackward();
 589
 590     // Pack instructions to maximize resource utilization
 591     ScheduleForward();
 592   }
 593
 594   DEBUG(printChanges(Count));
 595
 596   // Emit in scheduled order
 597   EmitAll();
 598 }
 599
 600
 601 /// createSimpleDAGScheduler - This creates a simple two pass instruction
 602 /// scheduler.
 603 llvm::ScheduleDAG* llvm::createSimpleDAGScheduler(SchedHeuristics Heuristic,
 604                                                   SelectionDAG &DAG,
 605                                                   MachineBasicBlock *BB) {
 606   return new ScheduleDAGSimple(Heuristic, DAG, BB,  DAG.getTarget());
 607 }