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 private:
 206   static bool isDefiner(NodeInfo *A, NodeInfo *B);
 207   void IncludeNode(NodeInfo *NI);
 208   void VisitAll();
 209   void Schedule();
 210   void GatherSchedulingInfo();
 211   void FakeGroupDominators();
 212   bool isStrongDependency(NodeInfo *A, NodeInfo *B);
 213   bool isWeakDependency(NodeInfo *A, NodeInfo *B);
 214   void ScheduleBackward();
 215   void ScheduleForward();
 216 };
 217
 218 //===----------------------------------------------------------------------===//
 219 /// Special case itineraries.
 220 ///
 221 enum {
 222   CallLatency = 40,          // To push calls back in time
 223
 224   RSInteger   = 0xC0000000,  // Two integer units
 225   RSFloat     = 0x30000000,  // Two float units
 226   RSLoadStore = 0x0C000000,  // Two load store units
 227   RSBranch    = 0x02000000   // One branch unit
 228 };
 229 static InstrStage CallStage  = { CallLatency, RSBranch };
 230 static InstrStage LoadStage  = { 5, RSLoadStore };
 231 static InstrStage StoreStage = { 2, RSLoadStore };
 232 static InstrStage IntStage   = { 2, RSInteger };
 233 static InstrStage FloatStage = { 3, RSFloat };
 234 //===----------------------------------------------------------------------===//
 235
 236 } // namespace
 237
 238 //===----------------------------------------------------------------------===//
 239
 240
 241 //===----------------------------------------------------------------------===//
 242 /// isDefiner - Return true if node A is a definer for B.
 243 ///
 244 bool ScheduleDAGSimple::isDefiner(NodeInfo *A, NodeInfo *B) {
 245   // While there are A nodes
 246   NodeGroupIterator NII(A);
 247   while (NodeInfo *NI = NII.next()) {
 248     // Extract node
 249     SDNode *Node = NI->Node;
 250     // While there operands in nodes of B
 251     NodeGroupOpIterator NGOI(B);
 252     while (!NGOI.isEnd()) {
 253       SDOperand Op = NGOI.next();
 254       // If node from A defines a node in B
 255       if (Node == Op.Val) return true;
 256     }
 257   }
 258   return false;
 259 }
 260
 261 /// IncludeNode - Add node to NodeInfo vector.
 262 ///
 263 void ScheduleDAGSimple::IncludeNode(NodeInfo *NI) {
 264   // Get node
 265   SDNode *Node = NI->Node;
 266   // Ignore entry node
 267   if (Node->getOpcode() == ISD::EntryToken) return;
 268   // Check current count for node
 269   int Count = NI->getPending();
 270   // If the node is already in list
 271   if (Count < 0) return;
 272   // Decrement count to indicate a visit
 273   Count--;
 274   // If count has gone to zero then add node to list
 275   if (!Count) {
 276     // Add node
 277     if (NI->isInGroup()) {
 278       Ordering.push_back(NI->Group->getDominator());
 279     } else {
 280       Ordering.push_back(NI);
 281     }
 282     // indicate node has been added
 283     Count--;
 284   }
 285   // Mark as visited with new count
 286   NI->setPending(Count);
 287 }
 288
 289 /// GatherSchedulingInfo - Get latency and resource information about each node.
 290 ///
 291 void ScheduleDAGSimple::GatherSchedulingInfo() {
 292   // Get instruction itineraries for the target
 293   const InstrItineraryData InstrItins = TM.getInstrItineraryData();
 294
 295   // For each node
 296   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 297     // Get node info
 298     NodeInfo* NI = &Info[i];
 299     SDNode *Node = NI->Node;
 300
 301     // If there are itineraries and it is a machine instruction
 302     if (InstrItins.isEmpty() || Heuristic == simpleNoItinScheduling) {
 303       // If machine opcode
 304       if (Node->isTargetOpcode()) {
 305         // Get return type to guess which processing unit
 306         MVT::ValueType VT = Node->getValueType(0);
 307         // Get machine opcode
 308         MachineOpCode TOpc = Node->getTargetOpcode();
 309         NI->IsCall = TII->isCall(TOpc);
 310         NI->IsLoad = TII->isLoad(TOpc);
 311         NI->IsStore = TII->isStore(TOpc);
 312
 313         if (TII->isLoad(TOpc))             NI->StageBegin = &LoadStage;
 314         else if (TII->isStore(TOpc))       NI->StageBegin = &StoreStage;
 315         else if (MVT::isInteger(VT))       NI->StageBegin = &IntStage;
 316         else if (MVT::isFloatingPoint(VT)) NI->StageBegin = &FloatStage;
 317         if (NI->StageBegin) NI->StageEnd = NI->StageBegin + 1;
 318       }
 319     } else if (Node->isTargetOpcode()) {
 320       // get machine opcode
 321       MachineOpCode TOpc = Node->getTargetOpcode();
 322       // Check to see if it is a call
 323       NI->IsCall = TII->isCall(TOpc);
 324       // Get itinerary stages for instruction
 325       unsigned II = TII->getSchedClass(TOpc);
 326       NI->StageBegin = InstrItins.begin(II);
 327       NI->StageEnd = InstrItins.end(II);
 328     }
 329
 330     // One slot for the instruction itself
 331     NI->Latency = 1;
 332
 333     // Add long latency for a call to push it back in time
 334     if (NI->IsCall) NI->Latency += CallLatency;
 335
 336     // Sum up all the latencies
 337     for (InstrStage *Stage = NI->StageBegin, *E = NI->StageEnd;
 338         Stage != E; Stage++) {
 339       NI->Latency += Stage->Cycles;
 340     }
 341
 342     // Sum up all the latencies for max tally size
 343     NSlots += NI->Latency;
 344   }
 345
 346   // Unify metrics if in a group
 347   if (HasGroups) {
 348     for (unsigned i = 0, N = NodeCount; i < N; i++) {
 349       NodeInfo* NI = &Info[i];
 350
 351       if (NI->isInGroup()) {
 352         NodeGroup *Group = NI->Group;
 353
 354         if (!Group->getDominator()) {
 355           NIIterator NGI = Group->group_begin(), NGE = Group->group_end();
 356           NodeInfo *Dominator = *NGI;
 357           unsigned Latency = 0;
 358
 359           for (NGI++; NGI != NGE; NGI++) {
 360             NodeInfo* NGNI = *NGI;
 361             Latency += NGNI->Latency;
 362             if (Dominator->Latency < NGNI->Latency) Dominator = NGNI;
 363           }
 364
 365           Dominator->Latency = Latency;
 366           Group->setDominator(Dominator);
 367         }
 368       }
 369     }
 370   }
 371 }
 372
 373 /// VisitAll - Visit each node breadth-wise to produce an initial ordering.
 374 /// Note that the ordering in the Nodes vector is reversed.
 375 void ScheduleDAGSimple::VisitAll() {
 376   // Add first element to list
 377   NodeInfo *NI = getNI(DAG.getRoot().Val);
 378   if (NI->isInGroup()) {
 379     Ordering.push_back(NI->Group->getDominator());
 380   } else {
 381     Ordering.push_back(NI);
 382   }
 383
 384   // Iterate through all nodes that have been added
 385   for (unsigned i = 0; i < Ordering.size(); i++) { // note: size() varies
 386     // Visit all operands
 387     NodeGroupOpIterator NGI(Ordering[i]);
 388     while (!NGI.isEnd()) {
 389       // Get next operand
 390       SDOperand Op = NGI.next();
 391       // Get node
 392       SDNode *Node = Op.Val;
 393       // Ignore passive nodes
 394       if (isPassiveNode(Node)) continue;
 395       // Check out node
 396       IncludeNode(getNI(Node));
 397     }
 398   }
 399
 400   // Add entry node last (IncludeNode filters entry nodes)
 401   if (DAG.getEntryNode().Val != DAG.getRoot().Val)
 402     Ordering.push_back(getNI(DAG.getEntryNode().Val));
 403
 404   // Reverse the order
 405   std::reverse(Ordering.begin(), Ordering.end());
 406 }
 407
 408 /// FakeGroupDominators - Set dominators for non-scheduling.
 409 ///
 410 void ScheduleDAGSimple::FakeGroupDominators() {
 411   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 412     NodeInfo* NI = &Info[i];
 413
 414     if (NI->isInGroup()) {
 415       NodeGroup *Group = NI->Group;
 416
 417       if (!Group->getDominator()) {
 418         Group->setDominator(NI);
 419       }
 420     }
 421   }
 422 }
 423
 424 /// isStrongDependency - Return true if node A has results used by node B.
 425 /// I.E., B must wait for latency of A.
 426 bool ScheduleDAGSimple::isStrongDependency(NodeInfo *A, NodeInfo *B) {
 427   // If A defines for B then it's a strong dependency or
 428   // if a load follows a store (may be dependent but why take a chance.)
 429   return isDefiner(A, B) || (A->IsStore && B->IsLoad);
 430 }
 431
 432 /// isWeakDependency Return true if node A produces a result that will
 433 /// conflict with operands of B.  It is assumed that we have called
 434 /// isStrongDependency prior.
 435 bool ScheduleDAGSimple::isWeakDependency(NodeInfo *A, NodeInfo *B) {
 436   // TODO check for conflicting real registers and aliases
 437 #if 0 // FIXME - Since we are in SSA form and not checking register aliasing
 438   return A->Node->getOpcode() == ISD::EntryToken || isStrongDependency(B, A);
 439 #else
 440   return A->Node->getOpcode() == ISD::EntryToken;
 441 #endif
 442 }
 443
 444 /// ScheduleBackward - Schedule instructions so that any long latency
 445 /// instructions and the critical path get pushed back in time. Time is run in
 446 /// reverse to allow code reuse of the Tally and eliminate the overhead of
 447 /// biasing every slot indices against NSlots.
 448 void ScheduleDAGSimple::ScheduleBackward() {
 449   // Size and clear the resource tally
 450   Tally.Initialize(NSlots);
 451   // Get number of nodes to schedule
 452   unsigned N = Ordering.size();
 453
 454   // For each node being scheduled
 455   for (unsigned i = N; 0 < i--;) {
 456     NodeInfo *NI = Ordering[i];
 457     // Track insertion
 458     unsigned Slot = NotFound;
 459
 460     // Compare against those previously scheduled nodes
 461     unsigned j = i + 1;
 462     for (; j < N; j++) {
 463       // Get following instruction
 464       NodeInfo *Other = Ordering[j];
 465
 466       // Check dependency against previously inserted nodes
 467       if (isStrongDependency(NI, Other)) {
 468         Slot = Other->Slot + Other->Latency;
 469         break;
 470       } else if (isWeakDependency(NI, Other)) {
 471         Slot = Other->Slot;
 472         break;
 473       }
 474     }
 475
 476     // If independent of others (or first entry)
 477     if (Slot == NotFound) Slot = 0;
 478
 479 #if 0 // FIXME - measure later
 480     // Find a slot where the needed resources are available
 481     if (NI->StageBegin != NI->StageEnd)
 482       Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd);
 483 #endif
 484
 485     // Set node slot
 486     NI->Slot = Slot;
 487
 488     // Insert sort based on slot
 489     j = i + 1;
 490     for (; j < N; j++) {
 491       // Get following instruction
 492       NodeInfo *Other = Ordering[j];
 493       // Should we look further (remember slots are in reverse time)
 494       if (Slot >= Other->Slot) break;
 495       // Shuffle other into ordering
 496       Ordering[j - 1] = Other;
 497     }
 498     // Insert node in proper slot
 499     if (j != i + 1) Ordering[j - 1] = NI;
 500   }
 501 }
 502
 503 /// ScheduleForward - Schedule instructions to maximize packing.
 504 ///
 505 void ScheduleDAGSimple::ScheduleForward() {
 506   // Size and clear the resource tally
 507   Tally.Initialize(NSlots);
 508   // Get number of nodes to schedule
 509   unsigned N = Ordering.size();
 510
 511   // For each node being scheduled
 512   for (unsigned i = 0; i < N; i++) {
 513     NodeInfo *NI = Ordering[i];
 514     // Track insertion
 515     unsigned Slot = NotFound;
 516
 517     // Compare against those previously scheduled nodes
 518     unsigned j = i;
 519     for (; 0 < j--;) {
 520       // Get following instruction
 521       NodeInfo *Other = Ordering[j];
 522
 523       // Check dependency against previously inserted nodes
 524       if (isStrongDependency(Other, NI)) {
 525         Slot = Other->Slot + Other->Latency;
 526         break;
 527       } else if (Other->IsCall || isWeakDependency(Other, NI)) {
 528         Slot = Other->Slot;
 529         break;
 530       }
 531     }
 532
 533     // If independent of others (or first entry)
 534     if (Slot == NotFound) Slot = 0;
 535
 536     // Find a slot where the needed resources are available
 537     if (NI->StageBegin != NI->StageEnd)
 538       Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd);
 539
 540     // Set node slot
 541     NI->Slot = Slot;
 542
 543     // Insert sort based on slot
 544     j = i;
 545     for (; 0 < j--;) {
 546       // Get prior instruction
 547       NodeInfo *Other = Ordering[j];
 548       // Should we look further
 549       if (Slot >= Other->Slot) break;
 550       // Shuffle other into ordering
 551       Ordering[j + 1] = Other;
 552     }
 553     // Insert node in proper slot
 554     if (j != i) Ordering[j + 1] = NI;
 555   }
 556 }
 557
 558 /// Schedule - Order nodes according to selected style.
 559 ///
 560 void ScheduleDAGSimple::Schedule() {
 561   // Test to see if scheduling should occur
 562   bool ShouldSchedule = NodeCount > 3 && Heuristic != noScheduling;
 563   // Don't waste time if is only entry and return
 564   if (ShouldSchedule) {
 565     // Get latency and resource requirements
 566     GatherSchedulingInfo();
 567   } else if (HasGroups) {
 568     // Make sure all the groups have dominators
 569     FakeGroupDominators();
 570   }
 571
 572   // Breadth first walk of DAG
 573   VisitAll();
 574
 575 #ifndef NDEBUG
 576   static unsigned Count = 0;
 577   Count++;
 578   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
 579     NodeInfo *NI = Ordering[i];
 580     NI->Preorder = i;
 581   }
 582 #endif
 583
 584   // Don't waste time if is only entry and return
 585   if (ShouldSchedule) {
 586     // Push back long instructions and critical path
 587     ScheduleBackward();
 588
 589     // Pack instructions to maximize resource utilization
 590     ScheduleForward();
 591   }
 592
 593   DEBUG(printChanges(Count));
 594
 595   // Emit in scheduled order
 596   EmitAll();
 597 }
 598
 599
 600 /// createSimpleDAGScheduler - This creates a simple two pass instruction
 601 /// scheduler.
 602 llvm::ScheduleDAG* llvm::createSimpleDAGScheduler(SchedHeuristics Heuristic,
 603                                                   SelectionDAG &DAG,
 604                                                   MachineBasicBlock *BB) {
 605   return new ScheduleDAGSimple(Heuristic, DAG, BB,  DAG.getTarget());
 606 }