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