lib/CodeGen/SelectionDAG/ScheduleDAG.cpp

   1 //===-- ScheduleDAG.cpp - Implement a trivial DAG scheduler ---------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Chris Lattner and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements a simple two pass scheduler.  The first pass attempts to push
  11 // backward any lengthy instructions and critical paths.  The second pass packs
  12 // instructions into semi-optimal time slots.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #define DEBUG_TYPE "sched"
  17 #include "llvm/CodeGen/MachineConstantPool.h"
  18 #include "llvm/CodeGen/MachineFunction.h"
  19 #include "llvm/CodeGen/SelectionDAGISel.h"
  20 #include "llvm/CodeGen/SelectionDAG.h"
  21 #include "llvm/CodeGen/SSARegMap.h"
  22 #include "llvm/Target/TargetMachine.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetLowering.h"
  25 #include "llvm/Support/CommandLine.h"
  26 #include "llvm/Support/Debug.h"
  27 #include <iostream>
  28 using namespace llvm;
  29
  30 namespace {
  31   // Style of scheduling to use.
  32   enum ScheduleChoices {
  33     noScheduling,
  34     simpleScheduling,
  35   };
  36 } // namespace
  37
  38 cl::opt<ScheduleChoices> ScheduleStyle("sched",
  39   cl::desc("Choose scheduling style"),
  40   cl::init(noScheduling),
  41   cl::values(
  42     clEnumValN(noScheduling, "none",
  43               "Trivial emission with no analysis"),
  44     clEnumValN(simpleScheduling, "simple",
  45               "Minimize critical path and maximize processor utilization"),
  46    clEnumValEnd));
  47
  48
  49 #ifndef NDEBUG
  50 static cl::opt<bool>
  51 ViewDAGs("view-sched-dags", cl::Hidden,
  52          cl::desc("Pop up a window to show sched dags as they are processed"));
  53 #else
  54 static const bool ViewDAGs = 0;
  55 #endif
  56
  57 namespace {
  58 //===----------------------------------------------------------------------===//
  59 ///
  60 /// BitsIterator - Provides iteration through individual bits in a bit vector.
  61 ///
  62 template<class T>
  63 class BitsIterator {
  64 private:
  65   T Bits;                               // Bits left to iterate through
  66
  67 public:
  68   /// Ctor.
  69   BitsIterator(T Initial) : Bits(Initial) {}
  70
  71   /// Next - Returns the next bit set or zero if exhausted.
  72   inline T Next() {
  73     // Get the rightmost bit set
  74     T Result = Bits & -Bits;
  75     // Remove from rest
  76     Bits &= ~Result;
  77     // Return single bit or zero
  78     return Result;
  79   }
  80 };
  81
  82 //===----------------------------------------------------------------------===//
  83
  84
  85 //===----------------------------------------------------------------------===//
  86 ///
  87 /// ResourceTally - Manages the use of resources over time intervals.  Each
  88 /// item (slot) in the tally vector represents the resources used at a given
  89 /// moment.  A bit set to 1 indicates that a resource is in use, otherwise
  90 /// available.  An assumption is made that the tally is large enough to schedule
  91 /// all current instructions (asserts otherwise.)
  92 ///
  93 template<class T>
  94 class ResourceTally {
  95 private:
  96   std::vector<T> Tally;                 // Resources used per slot
  97   typedef typename std::vector<T>::iterator Iter;
  98                                         // Tally iterator
  99
 100   /// AllInUse - Test to see if all of the resources in the slot are busy (set.)
 101   inline bool AllInUse(Iter Cursor, unsigned ResourceSet) {
 102     return (*Cursor & ResourceSet) == ResourceSet;
 103   }
 104
 105   /// Skip - Skip over slots that use all of the specified resource (all are
 106   /// set.)
 107   Iter Skip(Iter Cursor, unsigned ResourceSet) {
 108     assert(ResourceSet && "At least one resource bit needs to bet set");
 109
 110     // Continue to the end
 111     while (true) {
 112       // Break out if one of the resource bits is not set
 113       if (!AllInUse(Cursor, ResourceSet)) return Cursor;
 114       // Try next slot
 115       Cursor++;
 116       assert(Cursor < Tally.end() && "Tally is not large enough for schedule");
 117     }
 118   }
 119
 120   /// FindSlots - Starting from Begin, locate N consecutive slots where at least
 121   /// one of the resource bits is available.  Returns the address of first slot.
 122   Iter FindSlots(Iter Begin, unsigned N, unsigned ResourceSet,
 123                                          unsigned &Resource) {
 124     // Track position
 125     Iter Cursor = Begin;
 126
 127     // Try all possible slots forward
 128     while (true) {
 129       // Skip full slots
 130       Cursor = Skip(Cursor, ResourceSet);
 131       // Determine end of interval
 132       Iter End = Cursor + N;
 133       assert(End <= Tally.end() && "Tally is not large enough for schedule");
 134
 135       // Iterate thru each resource
 136       BitsIterator<T> Resources(ResourceSet & ~*Cursor);
 137       while (unsigned Res = Resources.Next()) {
 138         // Check if resource is available for next N slots
 139         // Break out if resource is busy
 140         Iter Interval = Cursor;
 141         for (; Interval < End && !(*Interval & Res); Interval++) {}
 142
 143         // If available for interval, return where and which resource
 144         if (Interval == End) {
 145           Resource = Res;
 146           return Cursor;
 147         }
 148         // Otherwise, check if worth checking other resources
 149         if (AllInUse(Interval, ResourceSet)) {
 150           // Start looking beyond interval
 151           Cursor = Interval;
 152           break;
 153         }
 154       }
 155       Cursor++;
 156     }
 157   }
 158
 159   /// Reserve - Mark busy (set) the specified N slots.
 160   void Reserve(Iter Begin, unsigned N, unsigned Resource) {
 161     // Determine end of interval
 162     Iter End = Begin + N;
 163     assert(End <= Tally.end() && "Tally is not large enough for schedule");
 164
 165     // Set resource bit in each slot
 166     for (; Begin < End; Begin++)
 167       *Begin |= Resource;
 168   }
 169
 170 public:
 171   /// Initialize - Resize and zero the tally to the specified number of time
 172   /// slots.
 173   inline void Initialize(unsigned N) {
 174     Tally.assign(N, 0);   // Initialize tally to all zeros.
 175   }
 176
 177   // FindAndReserve - Locate and mark busy (set) N bits started at slot I, using
 178   // ResourceSet for choices.
 179   unsigned FindAndReserve(unsigned I, unsigned N, unsigned ResourceSet) {
 180     // Which resource used
 181     unsigned Resource;
 182     // Find slots for instruction.
 183     Iter Where = FindSlots(Tally.begin() + I, N, ResourceSet, Resource);
 184     // Reserve the slots
 185     Reserve(Where, N, Resource);
 186     // Return time slot (index)
 187     return Where - Tally.begin();
 188   }
 189
 190 };
 191 //===----------------------------------------------------------------------===//
 192
 193
 194 //===----------------------------------------------------------------------===//
 195 // This struct tracks information used to schedule the a node.
 196 struct ScheduleInfo {
 197   SDOperand     Op;                     // Operand information
 198   unsigned      Latency;                // Cycles to complete instruction
 199   unsigned      ResourceSet;            // Bit vector of usable resources
 200   unsigned      Slot;                   // Operand's time slot
 201
 202   // Ctor.
 203   ScheduleInfo(SDOperand op)
 204   : Op(op)
 205   , Latency(0)
 206   , ResourceSet(0)
 207   , Slot(0)
 208   {}
 209 };
 210 //===----------------------------------------------------------------------===//
 211
 212
 213 //===----------------------------------------------------------------------===//
 214 class SimpleSched {
 215 private:
 216   // TODO - get ResourceSet from TII
 217   enum {
 218     RSInteger = 0x3,                    // Two integer units
 219     RSFloat = 0xC,                      // Two float units
 220     RSLoadStore = 0x30,                 // Two load store units
 221     RSOther = 0                         // Processing unit independent
 222   };
 223
 224   MachineBasicBlock *BB;                // Current basic block
 225   SelectionDAG &DAG;                    // DAG of the current basic block
 226   const TargetMachine &TM;              // Target processor
 227   const TargetInstrInfo &TII;           // Target instruction information
 228   const MRegisterInfo &MRI;             // Target processor register information
 229   SSARegMap *RegMap;                    // Virtual/real register map
 230   MachineConstantPool *ConstPool;       // Target constant pool
 231   std::vector<ScheduleInfo> Operands;   // All operands to be scheduled
 232   std::vector<ScheduleInfo*> Ordering;  // Emit ordering of operands
 233   std::map<SDNode *, int> Visited;      // Operands that have been visited
 234   ResourceTally<unsigned> Tally;        // Resource usage tally
 235   unsigned NSlots;                      // Total latency
 236   std::map<SDNode *, unsigned>VRMap;    // Operand to VR map
 237   static const unsigned NotFound = ~0U; // Search marker
 238
 239 public:
 240
 241   // Ctor.
 242   SimpleSched(SelectionDAG &D, MachineBasicBlock *bb)
 243     : BB(bb), DAG(D), TM(D.getTarget()), TII(*TM.getInstrInfo()),
 244       MRI(*TM.getRegisterInfo()), RegMap(BB->getParent()->getSSARegMap()),
 245       ConstPool(BB->getParent()->getConstantPool()),
 246       NSlots(0) {
 247     assert(&TII && "Target doesn't provide instr info?");
 248     assert(&MRI && "Target doesn't provide register info?");
 249   }
 250
 251   // Run - perform scheduling.
 252   MachineBasicBlock *Run() {
 253     Schedule();
 254     return BB;
 255   }
 256
 257 private:
 258   static bool isFlagDefiner(SDOperand Op) { return isFlagDefiner(Op.Val); }
 259   static bool isFlagUser(SDOperand Op) { return isFlagUser(Op.Val); }
 260   static bool isFlagDefiner(SDNode *A);
 261   static bool isFlagUser(SDNode *A);
 262   static bool isDefiner(SDNode *A, SDNode *B);
 263   static bool isPassiveOperand(SDOperand Op);
 264   void IncludeOperand(SDOperand Op);
 265   void VisitAll();
 266   void Schedule();
 267   void GatherOperandInfo();
 268   bool isStrongDependency(SDOperand A, SDOperand B) {
 269     return isStrongDependency(A.Val, B.Val);
 270   }
 271   bool isWeakDependency(SDOperand A, SDOperand B) {
 272     return isWeakDependency(A.Val, B.Val);
 273   }
 274   static bool isStrongDependency(SDNode *A, SDNode *B);
 275   static bool isWeakDependency(SDNode *A, SDNode *B);
 276   void ScheduleBackward();
 277   void ScheduleForward();
 278   void EmitAll();
 279   void EmitFlagUsers(SDOperand Op);
 280   static unsigned CountResults(SDOperand Op);
 281   static unsigned CountOperands(SDOperand Op);
 282   unsigned CreateVirtualRegisters(SDOperand Op, MachineInstr *MI,
 283                                   unsigned NumResults,
 284                                   const TargetInstrDescriptor &II);
 285   unsigned Emit(SDOperand A);
 286
 287   void printSI(std::ostream &O, ScheduleInfo *SI) const ;
 288   void print(std::ostream &O) const ;
 289   inline void dump(const char *tag) const { std::cerr << tag; dump(); }
 290   void dump() const;
 291 };
 292 //===----------------------------------------------------------------------===//
 293
 294
 295 //===----------------------------------------------------------------------===//
 296 class FlagUserIterator {
 297 private:
 298   SDNode               *Definer;        // Node defining flag
 299   SDNode::use_iterator UI;              // User node iterator
 300   SDNode::use_iterator E;               // End of user nodes
 301   unsigned             MinRes;          // Minimum flag result
 302
 303 public:
 304   // Ctor.
 305   FlagUserIterator(SDNode *D)
 306   : Definer(D)
 307   , UI(D->use_begin())
 308   , E(D->use_end())
 309   , MinRes(D->getNumValues()) {
 310     // Find minimum flag result.
 311     while (MinRes && D->getValueType(MinRes - 1) == MVT::Flag) --MinRes;
 312   }
 313
 314   /// isFlagUser - Return true if  node uses definer's flag.
 315   bool isFlagUser(SDNode *U) {
 316     // For each operand (in reverse to only look at flags)
 317     for (unsigned N = U->getNumOperands(); 0 < N--;) {
 318       // Get operand
 319       SDOperand Op = U->getOperand(N);
 320       // Not user if there are no flags
 321       if (Op.getValueType() != MVT::Flag) return false;
 322       // Return true if it is one of the flag results
 323       if (Op.Val == Definer && Op.ResNo >= MinRes) return true;
 324     }
 325     // Not a flag user
 326     return false;
 327   }
 328
 329   SDNode *next() {
 330     // Continue to next user
 331     while (UI != E) {
 332       // Next user node
 333       SDNode *User = *UI++;
 334       // Return true if is a flag user
 335       if (isFlagUser(User)) return User;
 336     }
 337
 338     // No more user nodes
 339     return NULL;
 340   }
 341 };
 342
 343 } // namespace
 344
 345
 346 //===----------------------------------------------------------------------===//
 347 /// isFlagDefiner - Returns true if the operand defines a flag result.
 348 bool SimpleSched::isFlagDefiner(SDNode *A) {
 349   unsigned N = A->getNumValues();
 350   return N && A->getValueType(N - 1) == MVT::Flag;
 351 }
 352
 353 /// isFlagUser - Returns true if the operand uses a flag result.
 354 ///
 355 bool SimpleSched::isFlagUser(SDNode *A) {
 356   unsigned N = A->getNumOperands();
 357   return N && A->getOperand(N - 1).getValueType() == MVT::Flag;
 358 }
 359
 360 /// isDefiner - Return true if Node A is a definder for B.
 361 ///
 362 bool SimpleSched::isDefiner(SDNode *A, SDNode *B) {
 363   for (unsigned i = 0, N = B->getNumOperands(); i < N; i++) {
 364     if (B->getOperand(i).Val == A) return true;
 365   }
 366   return false;
 367 }
 368
 369 /// isPassiveOperand - Return true if the operand is a non-scheduled leaf
 370 /// operand.
 371 bool SimpleSched::isPassiveOperand(SDOperand Op) {
 372   if (isa<ConstantSDNode>(Op))       return true;
 373   if (isa<RegisterSDNode>(Op))       return true;
 374   if (isa<GlobalAddressSDNode>(Op))  return true;
 375   if (isa<BasicBlockSDNode>(Op))     return true;
 376   if (isa<FrameIndexSDNode>(Op))     return true;
 377   if (isa<ConstantPoolSDNode>(Op))   return true;
 378   if (isa<ExternalSymbolSDNode>(Op)) return true;
 379   return false;
 380 }
 381
 382 /// IncludeOperand - Add operand to ScheduleInfo vector.
 383 ///
 384 void SimpleSched::IncludeOperand(SDOperand Op) {
 385   // Ignore entry node
 386   if (Op.getOpcode() == ISD::EntryToken) return;
 387   // Check current count for operand
 388   int Count = Visited[Op.Val];
 389   // If the operand is already in list
 390   if (Count < 0) return;
 391   // If this the first time then get count
 392   if (!Count) Count = Op.Val->use_size();
 393   // Decrement count to indicate a visit
 394   Count--;
 395   // If count has gone to zero then add operand to list
 396   if (!Count) {
 397     // Add operand
 398     Operands.push_back(ScheduleInfo(Op));
 399     // indicate operand has been added
 400     Count--;
 401   }
 402   // Mark as visited with new count
 403   Visited[Op.Val] = Count;
 404 }
 405
 406 /// VisitAll - Visit each operand breadth-wise to produce an initial ordering.
 407 /// Note that the ordering in the Operands vector is reversed.
 408 void SimpleSched::VisitAll() {
 409   // Add first element to list
 410   Operands.push_back(DAG.getRoot());
 411   for (unsigned i = 0; i < Operands.size(); i++) { // note: size() varies
 412     // Get next operand. Need copy because Operands vector is growing and
 413     // addresses can be ScheduleInfo changing.
 414     SDOperand Op = Operands[i].Op;
 415     // Get the number of real operands
 416     unsigned NodeOperands = CountOperands(Op);
 417     // Get the total number of operands
 418     unsigned NumOperands = Op.getNumOperands();
 419
 420     // Visit all operands skipping the Other operand if present
 421     for (unsigned i = NumOperands; 0 < i--;) {
 422       SDOperand OpI = Op.getOperand(i);
 423       // Ignore passive operands
 424       if (isPassiveOperand(OpI)) continue;
 425       // Check out operand
 426       IncludeOperand(OpI);
 427     }
 428   }
 429
 430   // Add entry node last (IncludeOperand filters entry nodes)
 431   if (DAG.getEntryNode().Val != DAG.getRoot().Val)
 432     Operands.push_back(DAG.getEntryNode());
 433 }
 434
 435 /// GatherOperandInfo - Get latency and resource information about each operand.
 436 ///
 437 void SimpleSched::GatherOperandInfo() {
 438   // Add addresses of operand info to ordering vector
 439   // Get number of operands
 440   unsigned N = Operands.size();
 441   // FIXME: This is an ugly (but temporary!) hack to test the scheduler before
 442   // we have real target info.
 443
 444   // For each operand being scheduled
 445   for (unsigned i = 0; i < N; i++) {
 446     ScheduleInfo* SI = &Operands[N - i - 1];
 447     SDOperand Op = SI->Op;
 448     MVT::ValueType VT = Op.Val->getValueType(0);
 449     if (Op.isTargetOpcode()) {
 450       MachineOpCode TOpc = Op.getTargetOpcode();
 451       // FIXME SI->Latency = std::max(1, TII.maxLatency(TOpc));
 452       // FIXME SI->ResourceSet = TII.resources(TOpc);
 453       if (TII.isCall(TOpc)) {
 454         SI->ResourceSet = RSInteger;
 455         SI->Latency = 40;
 456       } else if (TII.isLoad(TOpc)) {
 457         SI->ResourceSet = RSLoadStore;
 458         SI->Latency = 5;
 459       } else if (TII.isStore(TOpc)) {
 460         SI->ResourceSet = RSLoadStore;
 461         SI->Latency = 2;
 462       } else if (MVT::isInteger(VT)) {
 463         SI->ResourceSet = RSInteger;
 464         SI->Latency = 2;
 465       } else if (MVT::isFloatingPoint(VT)) {
 466         SI->ResourceSet = RSFloat;
 467         SI->Latency = 3;
 468       } else {
 469         SI->ResourceSet = RSOther;
 470         SI->Latency = 0;
 471       }
 472     } else {
 473       if (MVT::isInteger(VT)) {
 474         SI->ResourceSet = RSInteger;
 475         SI->Latency = 2;
 476       } else if (MVT::isFloatingPoint(VT)) {
 477         SI->ResourceSet = RSFloat;
 478         SI->Latency = 3;
 479       } else {
 480         SI->ResourceSet = RSOther;
 481         SI->Latency = 0;
 482       }
 483     }
 484
 485     // Add one slot for the instruction itself
 486     SI->Latency++;
 487
 488     // Sum up all the latencies for max tally size
 489     NSlots += SI->Latency;
 490
 491     // Place in initial sorted order
 492     // FIXME - PUNT - ignore flag users
 493     if (!isFlagUser(Op)) Ordering.push_back(SI);
 494   }
 495 }
 496
 497 /// isStrongDependency - Return true if operand A has results used by operand B.
 498 /// I.E., B must wait for latency of A.
 499 bool SimpleSched::isStrongDependency(SDNode *A, SDNode *B) {
 500   // If A defines for B then it's a strong dependency
 501   if (isDefiner(A, B)) return true;
 502   // If A defines a flag then it's users are part of the dependency
 503   if (isFlagDefiner(A)) {
 504     // Check each flag user
 505     FlagUserIterator FI(A);
 506     while (SDNode *User = FI.next()) {
 507       // If flag user has strong dependency so does B
 508       if (isStrongDependency(User, B)) return true;
 509     }
 510   }
 511   // If B defines a flag then it's users are part of the dependency
 512   if (isFlagDefiner(B)) {
 513     // Check each flag user
 514     FlagUserIterator FI(B);
 515     while (SDNode *User = FI.next()) {
 516       // If flag user has strong dependency so does B
 517       if (isStrongDependency(A, User)) return true;
 518     }
 519   }
 520   return false;
 521 }
 522
 523 /// isWeakDependency Return true if operand A produces a result that will
 524 /// conflict with operands of B.
 525 bool SimpleSched::isWeakDependency(SDNode *A, SDNode *B) {
 526   // TODO check for conflicting real registers and aliases
 527 #if 0 // Since we are in SSA form and not checking register aliasing
 528   return A->getOpcode() == ISD::EntryToken || isStrongDependency(B, A);
 529 #else
 530   return A->getOpcode() == ISD::EntryToken;
 531 #endif
 532 }
 533
 534 /// ScheduleBackward - Schedule instructions so that any long latency
 535 /// instructions and the critical path get pushed back in time. Time is run in
 536 /// reverse to allow code reuse of the Tally and eliminate the overhead of
 537 /// biasing every slot indices against NSlots.
 538 void SimpleSched::ScheduleBackward() {
 539   // Size and clear the resource tally
 540   Tally.Initialize(NSlots);
 541   // Get number of operands to schedule
 542   unsigned N = Ordering.size();
 543
 544   // For each operand being scheduled
 545   for (unsigned i = N; 0 < i--;) {
 546     ScheduleInfo *SI = Ordering[i];
 547     // Track insertion
 548     unsigned Slot = NotFound;
 549
 550     // Compare against those previously scheduled operands
 551     for (unsigned j = i + 1; j < N; j++) {
 552       // Get following instruction
 553       ScheduleInfo *Other = Ordering[j];
 554
 555       // Check dependency against previously inserted operands
 556       if (isStrongDependency(SI->Op, Other->Op)) {
 557         Slot = Other->Slot + Other->Latency;
 558         break;
 559       } else if (isWeakDependency(SI->Op, Other->Op)) {
 560         Slot = Other->Slot;
 561         break;
 562       }
 563     }
 564
 565     // If independent of others (or first entry)
 566     if (Slot == NotFound) Slot = 0;
 567
 568     // Find a slot where the needed resources are available
 569     if (SI->ResourceSet)
 570       Slot = Tally.FindAndReserve(Slot, SI->Latency, SI->ResourceSet);
 571
 572     // Set operand slot
 573     SI->Slot = Slot;
 574
 575     // Insert sort based on slot
 576     unsigned j = i + 1;
 577     for (; j < N; j++) {
 578       // Get following instruction
 579       ScheduleInfo *Other = Ordering[j];
 580       // Should we look further
 581       if (Slot >= Other->Slot) break;
 582       // Shuffle other into ordering
 583       Ordering[j - 1] = Other;
 584     }
 585     // Insert operand in proper slot
 586     if (j != i + 1) Ordering[j - 1] = SI;
 587   }
 588 }
 589
 590 /// ScheduleForward - Schedule instructions to maximize packing.
 591 ///
 592 void SimpleSched::ScheduleForward() {
 593   // Size and clear the resource tally
 594   Tally.Initialize(NSlots);
 595   // Get number of operands to schedule
 596   unsigned N = Ordering.size();
 597
 598   // For each operand being scheduled
 599   for (unsigned i = 0; i < N; i++) {
 600     ScheduleInfo *SI = Ordering[i];
 601     // Track insertion
 602     unsigned Slot = NotFound;
 603
 604     // Compare against those previously scheduled operands
 605     for (unsigned j = i; 0 < j--;) {
 606       // Get following instruction
 607       ScheduleInfo *Other = Ordering[j];
 608
 609       // Check dependency against previously inserted operands
 610       if (isStrongDependency(Other->Op, SI->Op)) {
 611         Slot = Other->Slot + Other->Latency;
 612         break;
 613       } else if (isWeakDependency(Other->Op, SI->Op)) {
 614         Slot = Other->Slot;
 615         break;
 616       }
 617     }
 618
 619     // If independent of others (or first entry)
 620     if (Slot == NotFound) Slot = 0;
 621
 622     // Find a slot where the needed resources are available
 623     if (SI->ResourceSet)
 624       Slot = Tally.FindAndReserve(Slot, SI->Latency, SI->ResourceSet);
 625
 626     // Set operand slot
 627     SI->Slot = Slot;
 628
 629     // Insert sort based on slot
 630     unsigned j = i;
 631     for (; 0 < j--;) {
 632       // Get following instruction
 633       ScheduleInfo *Other = Ordering[j];
 634       // Should we look further
 635       if (Slot >= Other->Slot) break;
 636       // Shuffle other into ordering
 637       Ordering[j + 1] = Other;
 638     }
 639     // Insert operand in proper slot
 640     if (j != i) Ordering[j + 1] = SI;
 641   }
 642 }
 643
 644 /// EmitAll - Emit all operands in schedule sorted order.
 645 ///
 646 void SimpleSched::EmitAll() {
 647   // For each operand in the ordering
 648   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
 649     // Get the scheduling info
 650     ScheduleInfo *SI = Ordering[i];
 651     // Get the operand
 652     SDOperand Op = SI->Op;
 653     // Emit the operand
 654     Emit(Op);
 655     // FIXME - PUNT - If Op defines a flag then it's users need to be emitted now
 656     if (isFlagDefiner(Op)) EmitFlagUsers(Op);
 657   }
 658 }
 659
 660 /// EmitFlagUsers - Emit users of operands flag.
 661 ///
 662 void SimpleSched::EmitFlagUsers(SDOperand Op) {
 663   // Check each flag user
 664   FlagUserIterator FI(Op.Val);
 665   while (SDNode *User = FI.next()) {
 666     // Construct user node as operand
 667     SDOperand OpU(User, 0);
 668     // Emit  user node
 669     Emit(OpU);
 670     // If user defines a flag then it's users need to be emitted now
 671     if (isFlagDefiner(User)) EmitFlagUsers(OpU);
 672   }
 673 }
 674
 675 /// CountResults - The results of target nodes have register or immediate
 676 /// operands first, then an optional chain, and optional flag operands (which do
 677 /// not go into the machine instrs.)
 678 unsigned SimpleSched::CountResults(SDOperand Op) {
 679   unsigned N = Op.Val->getNumValues();
 680   while (N && Op.Val->getValueType(N - 1) == MVT::Flag)
 681     --N;
 682   if (N && Op.Val->getValueType(N - 1) == MVT::Other)
 683     --N;    // Skip over chain result.
 684   return N;
 685 }
 686
 687 /// CountOperands  The inputs to target nodes have any actual inputs first,
 688 /// followed by an optional chain operand, then flag operands.  Compute the
 689 /// number of actual operands that  will go into the machine instr.
 690 unsigned SimpleSched::CountOperands(SDOperand Op) {
 691   unsigned N = Op.getNumOperands();
 692   while (N && Op.getOperand(N - 1).getValueType() == MVT::Flag)
 693     --N;
 694   if (N && Op.getOperand(N - 1).getValueType() == MVT::Other)
 695     --N; // Ignore chain if it exists.
 696   return N;
 697 }
 698
 699 /// CreateVirtualRegisters - Add result register values for things that are
 700 /// defined by this instruction.
 701 unsigned SimpleSched::CreateVirtualRegisters(SDOperand Op, MachineInstr *MI,
 702                                              unsigned NumResults,
 703                                              const TargetInstrDescriptor &II) {
 704   // Create the result registers for this node and add the result regs to
 705   // the machine instruction.
 706   const TargetOperandInfo *OpInfo = II.OpInfo;
 707   unsigned ResultReg = RegMap->createVirtualRegister(OpInfo[0].RegClass);
 708   MI->addRegOperand(ResultReg, MachineOperand::Def);
 709   for (unsigned i = 1; i != NumResults; ++i) {
 710     assert(OpInfo[i].RegClass && "Isn't a register operand!");
 711     MI->addRegOperand(RegMap->createVirtualRegister(OpInfo[0].RegClass),
 712                       MachineOperand::Def);
 713   }
 714   return ResultReg;
 715 }
 716
 717 /// Emit - Generate machine code for an operand and needed dependencies.
 718 ///
 719 unsigned SimpleSched::Emit(SDOperand Op) {
 720   std::map<SDNode *, unsigned>::iterator OpI = VRMap.lower_bound(Op.Val);
 721   if (OpI != VRMap.end() && OpI->first == Op.Val)
 722     return OpI->second + Op.ResNo;
 723   unsigned &OpSlot = VRMap.insert(OpI, std::make_pair(Op.Val, 0))->second;
 724
 725   unsigned ResultReg = 0;
 726   if (Op.isTargetOpcode()) {
 727     unsigned Opc = Op.getTargetOpcode();
 728     const TargetInstrDescriptor &II = TII.get(Opc);
 729
 730     unsigned NumResults = CountResults(Op);
 731     unsigned NodeOperands = CountOperands(Op);
 732     unsigned NumMIOperands = NodeOperands + NumResults;
 733 #ifndef NDEBUG
 734     assert((unsigned(II.numOperands) == NumMIOperands || II.numOperands == -1)&&
 735            "#operands for dag node doesn't match .td file!");
 736 #endif
 737
 738     // Create the new machine instruction.
 739     MachineInstr *MI = new MachineInstr(Opc, NumMIOperands, true, true);
 740
 741     // Add result register values for things that are defined by this
 742     // instruction.
 743     if (NumResults) ResultReg = CreateVirtualRegisters(Op, MI, NumResults, II);
 744
 745     // If there is a token chain operand, emit it first, as a hack to get avoid
 746     // really bad cases.
 747     if (Op.getNumOperands() > NodeOperands &&
 748         Op.getOperand(NodeOperands).getValueType() == MVT::Other) {
 749       Emit(Op.getOperand(NodeOperands));
 750     }
 751
 752     // Emit all of the actual operands of this instruction, adding them to the
 753     // instruction as appropriate.
 754     for (unsigned i = 0; i != NodeOperands; ++i) {
 755       if (Op.getOperand(i).isTargetOpcode()) {
 756         // Note that this case is redundant with the final else block, but we
 757         // include it because it is the most common and it makes the logic
 758         // simpler here.
 759         assert(Op.getOperand(i).getValueType() != MVT::Other &&
 760                Op.getOperand(i).getValueType() != MVT::Flag &&
 761                "Chain and flag operands should occur at end of operand list!");
 762
 763         MI->addRegOperand(Emit(Op.getOperand(i)), MachineOperand::Use);
 764       } else if (ConstantSDNode *C =
 765                                    dyn_cast<ConstantSDNode>(Op.getOperand(i))) {
 766         MI->addZeroExtImm64Operand(C->getValue());
 767       } else if (RegisterSDNode*R =dyn_cast<RegisterSDNode>(Op.getOperand(i))) {
 768         MI->addRegOperand(R->getReg(), MachineOperand::Use);
 769       } else if (GlobalAddressSDNode *TGA =
 770                        dyn_cast<GlobalAddressSDNode>(Op.getOperand(i))) {
 771         MI->addGlobalAddressOperand(TGA->getGlobal(), false, 0);
 772       } else if (BasicBlockSDNode *BB =
 773                        dyn_cast<BasicBlockSDNode>(Op.getOperand(i))) {
 774         MI->addMachineBasicBlockOperand(BB->getBasicBlock());
 775       } else if (FrameIndexSDNode *FI =
 776                        dyn_cast<FrameIndexSDNode>(Op.getOperand(i))) {
 777         MI->addFrameIndexOperand(FI->getIndex());
 778       } else if (ConstantPoolSDNode *CP =
 779                     dyn_cast<ConstantPoolSDNode>(Op.getOperand(i))) {
 780         unsigned Idx = ConstPool->getConstantPoolIndex(CP->get());
 781         MI->addConstantPoolIndexOperand(Idx);
 782       } else if (ExternalSymbolSDNode *ES =
 783                  dyn_cast<ExternalSymbolSDNode>(Op.getOperand(i))) {
 784         MI->addExternalSymbolOperand(ES->getSymbol(), false);
 785       } else {
 786         assert(Op.getOperand(i).getValueType() != MVT::Other &&
 787                Op.getOperand(i).getValueType() != MVT::Flag &&
 788                "Chain and flag operands should occur at end of operand list!");
 789         MI->addRegOperand(Emit(Op.getOperand(i)), MachineOperand::Use);
 790       }
 791     }
 792
 793     // Finally, if this node has any flag operands, we *must* emit them last, to
 794     // avoid emitting operations that might clobber the flags.
 795     if (Op.getNumOperands() > NodeOperands) {
 796       unsigned i = NodeOperands;
 797       if (Op.getOperand(i).getValueType() == MVT::Other)
 798         ++i;  // the chain is already selected.
 799       for (unsigned N = Op.getNumOperands(); i < N; i++) {
 800         assert(Op.getOperand(i).getValueType() == MVT::Flag &&
 801                "Must be flag operands!");
 802         Emit(Op.getOperand(i));
 803       }
 804     }
 805
 806     // Now that we have emitted all operands, emit this instruction itself.
 807     if ((II.Flags & M_USES_CUSTOM_DAG_SCHED_INSERTION) == 0) {
 808       BB->insert(BB->end(), MI);
 809     } else {
 810       // Insert this instruction into the end of the basic block, potentially
 811       // taking some custom action.
 812       BB = DAG.getTargetLoweringInfo().InsertAtEndOfBasicBlock(MI, BB);
 813     }
 814   } else {
 815     switch (Op.getOpcode()) {
 816     default:
 817       Op.Val->dump();
 818       assert(0 && "This target-independent node should have been selected!");
 819     case ISD::EntryToken: break;
 820     case ISD::TokenFactor:
 821       for (unsigned i = 0, N = Op.getNumOperands(); i < N; i++) {
 822         Emit(Op.getOperand(i));
 823       }
 824       break;
 825     case ISD::CopyToReg: {
 826       SDOperand FlagOp;
 827       if (Op.getNumOperands() == 4) {
 828         FlagOp = Op.getOperand(3);
 829       }
 830       if (Op.getOperand(0).Val != FlagOp.Val) {
 831         Emit(Op.getOperand(0));   // Emit the chain.
 832       }
 833       unsigned Val = Emit(Op.getOperand(2));
 834       if (FlagOp.Val) {
 835         Emit(FlagOp);
 836       }
 837       MRI.copyRegToReg(*BB, BB->end(),
 838                        cast<RegisterSDNode>(Op.getOperand(1))->getReg(), Val,
 839                        RegMap->getRegClass(Val));
 840       break;
 841     }
 842     case ISD::CopyFromReg: {
 843       Emit(Op.getOperand(0));   // Emit the chain.
 844       unsigned SrcReg = cast<RegisterSDNode>(Op.getOperand(1))->getReg();
 845
 846       // Figure out the register class to create for the destreg.
 847       const TargetRegisterClass *TRC = 0;
 848       if (MRegisterInfo::isVirtualRegister(SrcReg)) {
 849         TRC = RegMap->getRegClass(SrcReg);
 850       } else {
 851         // FIXME: we don't know what register class to generate this for.  Do
 852         // a brute force search and pick the first match. :(
 853         for (MRegisterInfo::regclass_iterator I = MRI.regclass_begin(),
 854                E = MRI.regclass_end(); I != E; ++I)
 855           if ((*I)->contains(SrcReg)) {
 856             TRC = *I;
 857             break;
 858           }
 859         assert(TRC && "Couldn't find register class for reg copy!");
 860       }
 861
 862       // Create the reg, emit the copy.
 863       ResultReg = RegMap->createVirtualRegister(TRC);
 864       MRI.copyRegToReg(*BB, BB->end(), ResultReg, SrcReg, TRC);
 865       break;
 866     }
 867     }
 868   }
 869
 870   OpSlot = ResultReg;
 871   return ResultReg+Op.ResNo;
 872 }
 873
 874 /// Schedule - Order operands according to selected style.
 875 ///
 876 void SimpleSched::Schedule() {
 877   switch (ScheduleStyle) {
 878   case simpleScheduling:
 879     // Breadth first walk of DAG
 880     VisitAll();
 881     // Get latency and resource requirements
 882     GatherOperandInfo();
 883     // Don't waste time if is only entry and return
 884     if (Operands.size() > 2) {
 885       DEBUG(dump("Pre-"));
 886       // Push back long instructions and critical path
 887       ScheduleBackward();
 888       DEBUG(dump("Mid-"));
 889       // Pack instructions to maximize resource utilization
 890       ScheduleForward();
 891       DEBUG(dump("Post-"));
 892       // Emit in scheduled order
 893       EmitAll();
 894       break;
 895     } // fall thru
 896   case noScheduling:
 897     // Emit instructions in using a DFS from the exit root
 898     Emit(DAG.getRoot());
 899     break;
 900   }
 901 }
 902
 903 /// printSI - Print schedule info.
 904 ///
 905 void SimpleSched::printSI(std::ostream &O, ScheduleInfo *SI) const {
 906 #ifndef NDEBUG
 907   using namespace std;
 908   SDOperand Op = SI->Op;
 909   O << " "
 910     << hex << Op.Val
 911     << ", RS=" << SI->ResourceSet
 912     << ", Lat=" << SI->Latency
 913     << ", Slot=" << SI->Slot
 914     << ", ARITY=(" << Op.getNumOperands() << ","
 915                    << Op.Val->getNumValues() << ")"
 916     << " " << Op.Val->getOperationName(&DAG);
 917   if (isFlagDefiner(Op)) O << "<#";
 918   if (isFlagUser(Op)) O << ">#";
 919 #endif
 920 }
 921
 922 /// print - Print ordering to specified output stream.
 923 ///
 924 void SimpleSched::print(std::ostream &O) const {
 925 #ifndef NDEBUG
 926   using namespace std;
 927   O << "Ordering\n";
 928   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
 929     printSI(O, Ordering[i]);
 930     O << "\n";
 931   }
 932 #endif
 933 }
 934
 935 /// dump - Print ordering to std::cerr.
 936 ///
 937 void SimpleSched::dump() const {
 938   print(std::cerr);
 939 }
 940 //===----------------------------------------------------------------------===//
 941
 942
 943 //===----------------------------------------------------------------------===//
 944 /// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each
 945 /// target node in the graph.
 946 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &SD) {
 947   if (ViewDAGs) SD.viewGraph();
 948   BB = SimpleSched(SD, BB).Run();
 949 }