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 // Forward
 194 class NodeInfo;
 195 typedef std::vector<NodeInfo *>           NIVector;
 196 typedef std::vector<NodeInfo *>::iterator NIIterator;
 197
 198 //===----------------------------------------------------------------------===//
 199 ///
 200 /// Node group -  This struct is used to manage flagged node groups.
 201 ///
 202 class NodeGroup : public NIVector {
 203 private:
 204   int           Pending;                // Number of visits pending before
 205                                         //    adding to order
 206
 207 public:
 208   // Ctor.
 209   NodeGroup() : Pending(0) {}
 210
 211   // Accessors
 212   inline NodeInfo *getLeader() { return empty() ? NULL : front(); }
 213   inline int getPending() const { return Pending; }
 214   inline void setPending(int P)  { Pending = P; }
 215   inline int addPending(int I)  { return Pending += I; }
 216
 217   static void Add(NodeInfo *D, NodeInfo *U);
 218   static unsigned CountInternalUses(NodeInfo *D, NodeInfo *U);
 219 };
 220 //===----------------------------------------------------------------------===//
 221
 222
 223 //===----------------------------------------------------------------------===//
 224 ///
 225 /// NodeInfo - This struct tracks information used to schedule the a node.
 226 ///
 227 class NodeInfo {
 228 private:
 229   int           Pending;                // Number of visits pending before
 230                                         //    adding to order
 231 public:
 232   SDNode        *Node;                  // DAG node
 233   unsigned      Latency;                // Cycles to complete instruction
 234   unsigned      ResourceSet;            // Bit vector of usable resources
 235   unsigned      Slot;                   // Node's time slot
 236   NodeGroup     *Group;                 // Grouping information
 237   unsigned      VRBase;                 // Virtual register base
 238 #ifndef NDEBUG
 239   unsigned      Preorder;               // Index before scheduling
 240 #endif
 241
 242   // Ctor.
 243   NodeInfo(SDNode *N = NULL)
 244   : Pending(0)
 245   , Node(N)
 246   , Latency(0)
 247   , ResourceSet(0)
 248   , Slot(0)
 249   , Group(NULL)
 250   , VRBase(0)
 251   {}
 252
 253   // Accessors
 254   inline bool isInGroup() const {
 255     assert(!Group || !Group->empty() && "Group with no members");
 256     return Group != NULL;
 257   }
 258   inline bool isGroupLeader() const {
 259      return isInGroup() && Group->getLeader() == this;
 260   }
 261   inline int getPending() const {
 262     return Group ? Group->getPending() : Pending;
 263   }
 264   inline void setPending(int P) {
 265     if (Group) Group->setPending(P);
 266     else       Pending = P;
 267   }
 268   inline int addPending(int I) {
 269     if (Group) return Group->addPending(I);
 270     else       return Pending += I;
 271   }
 272 };
 273 //===----------------------------------------------------------------------===//
 274
 275
 276 //===----------------------------------------------------------------------===//
 277 ///
 278 /// NodeGroupIterator - Iterates over all the nodes indicated by the node info.
 279 /// If the node is in a group then iterate over the members of the group,
 280 /// otherwise just the node info.
 281 ///
 282 class NodeGroupIterator {
 283 private:
 284   NodeInfo   *NI;                       // Node info
 285   NIIterator NGI;                       // Node group iterator
 286   NIIterator NGE;                       // Node group iterator end
 287
 288 public:
 289   // Ctor.
 290   NodeGroupIterator(NodeInfo *N) : NI(N) {
 291     // If the node is in a group then set up the group iterator.  Otherwise
 292     // the group iterators will trip first time out.
 293     if (N->isInGroup()) {
 294       // get Group
 295       NodeGroup *Group = NI->Group;
 296       NGI = Group->begin();
 297       NGE = Group->end();
 298       // Prevent this node from being used (will be in members list
 299       NI = NULL;
 300     }
 301   }
 302
 303   /// next - Return the next node info, otherwise NULL.
 304   ///
 305   NodeInfo *next() {
 306     // If members list
 307     if (NGI != NGE) return *NGI++;
 308     // Use node as the result (may be NULL)
 309     NodeInfo *Result = NI;
 310     // Only use once
 311     NI = NULL;
 312     // Return node or NULL
 313     return Result;
 314   }
 315 };
 316 //===----------------------------------------------------------------------===//
 317
 318
 319 //===----------------------------------------------------------------------===//
 320 ///
 321 /// NodeGroupOpIterator - Iterates over all the operands of a node.  If the node
 322 /// is a member of a group, this iterates over all the operands of all the
 323 /// members of the group.
 324 ///
 325 class NodeGroupOpIterator {
 326 private:
 327   NodeInfo            *NI;              // Node containing operands
 328   NodeGroupIterator   GI;               // Node group iterator
 329   SDNode::op_iterator OI;               // Operand iterator
 330   SDNode::op_iterator OE;               // Operand iterator end
 331
 332   /// CheckNode - Test if node has more operands.  If not get the next node
 333   /// skipping over nodes that have no operands.
 334   void CheckNode() {
 335     // Only if operands are exhausted first
 336     while (OI == OE) {
 337       // Get next node info
 338       NodeInfo *NI = GI.next();
 339       // Exit if nodes are exhausted
 340       if (!NI) return;
 341       // Get node itself
 342       SDNode *Node = NI->Node;
 343       // Set up the operand iterators
 344       OI = Node->op_begin();
 345       OE = Node->op_end();
 346     }
 347   }
 348
 349 public:
 350   // Ctor.
 351   NodeGroupOpIterator(NodeInfo *N) : NI(N), GI(N) {}
 352
 353   /// isEnd - Returns true when not more operands are available.
 354   ///
 355   inline bool isEnd() { CheckNode(); return OI == OE; }
 356
 357   /// next - Returns the next available operand.
 358   ///
 359   inline SDOperand next() {
 360     assert(OI != OE && "Not checking for end of NodeGroupOpIterator correctly");
 361     return *OI++;
 362   }
 363 };
 364 //===----------------------------------------------------------------------===//
 365
 366
 367 //===----------------------------------------------------------------------===//
 368 ///
 369 /// SimpleSched - Simple two pass scheduler.
 370 ///
 371 class SimpleSched {
 372 private:
 373   // TODO - get ResourceSet from TII
 374   enum {
 375     RSInteger = 0x3,                    // Two integer units
 376     RSFloat = 0xC,                      // Two float units
 377     RSLoadStore = 0x30,                 // Two load store units
 378     RSOther = 0                         // Processing unit independent
 379   };
 380
 381   MachineBasicBlock *BB;                // Current basic block
 382   SelectionDAG &DAG;                    // DAG of the current basic block
 383   const TargetMachine &TM;              // Target processor
 384   const TargetInstrInfo &TII;           // Target instruction information
 385   const MRegisterInfo &MRI;             // Target processor register information
 386   SSARegMap *RegMap;                    // Virtual/real register map
 387   MachineConstantPool *ConstPool;       // Target constant pool
 388   unsigned NodeCount;                   // Number of nodes in DAG
 389   NodeInfo *Info;                       // Info for nodes being scheduled
 390   std::map<SDNode *, NodeInfo *> Map;   // Map nodes to info
 391   NIVector Ordering;                    // Emit ordering of nodes
 392   ResourceTally<unsigned> Tally;        // Resource usage tally
 393   unsigned NSlots;                      // Total latency
 394   static const unsigned NotFound = ~0U; // Search marker
 395
 396 public:
 397
 398   // Ctor.
 399   SimpleSched(SelectionDAG &D, MachineBasicBlock *bb)
 400     : BB(bb), DAG(D), TM(D.getTarget()), TII(*TM.getInstrInfo()),
 401       MRI(*TM.getRegisterInfo()), RegMap(BB->getParent()->getSSARegMap()),
 402       ConstPool(BB->getParent()->getConstantPool()),
 403       NodeCount(0), Info(NULL), Map(), Tally(), NSlots(0) {
 404     assert(&TII && "Target doesn't provide instr info?");
 405     assert(&MRI && "Target doesn't provide register info?");
 406   }
 407
 408   // Run - perform scheduling.
 409   MachineBasicBlock *Run() {
 410     Schedule();
 411     return BB;
 412   }
 413
 414 private:
 415   /// getNI - Returns the node info for the specified node.
 416   ///
 417   inline NodeInfo *getNI(SDNode *Node) { return Map[Node]; }
 418
 419   /// getVR - Returns the virtual register number of the node.
 420   ///
 421   inline unsigned getVR(SDOperand Op) {
 422     NodeInfo *NI = getNI(Op.Val);
 423     assert(NI->VRBase != 0 && "Node emitted out of order - late");
 424     return NI->VRBase + Op.ResNo;
 425   }
 426
 427   static bool isFlagDefiner(SDNode *A);
 428   static bool isFlagUser(SDNode *A);
 429   static bool isDefiner(NodeInfo *A, NodeInfo *B);
 430   static bool isPassiveNode(SDNode *Node);
 431   void IncludeNode(NodeInfo *NI);
 432   void VisitAll();
 433   void Schedule();
 434   void IdentifyGroups();
 435   void GatherSchedulingInfo();
 436   void PrepareNodeInfo();
 437   bool isStrongDependency(NodeInfo *A, NodeInfo *B);
 438   bool isWeakDependency(NodeInfo *A, NodeInfo *B);
 439   void ScheduleBackward();
 440   void ScheduleForward();
 441   void EmitAll();
 442   void EmitNode(NodeInfo *NI);
 443   static unsigned CountResults(SDNode *Node);
 444   static unsigned CountOperands(SDNode *Node);
 445   unsigned CreateVirtualRegisters(MachineInstr *MI,
 446                                   unsigned NumResults,
 447                                   const TargetInstrDescriptor &II);
 448
 449   void printChanges(unsigned Index);
 450   void printSI(std::ostream &O, NodeInfo *NI) const;
 451   void print(std::ostream &O) const;
 452   inline void dump(const char *tag) const { std::cerr << tag; dump(); }
 453   void dump() const;
 454 };
 455 //===----------------------------------------------------------------------===//
 456
 457 } // namespace
 458
 459 //===----------------------------------------------------------------------===//
 460
 461
 462 //===----------------------------------------------------------------------===//
 463 /// Add - Adds a definer and user pair to a node group.
 464 ///
 465 void NodeGroup::Add(NodeInfo *D, NodeInfo *U) {
 466   // Get current groups
 467   NodeGroup *DGroup = D->Group;
 468   NodeGroup *UGroup = U->Group;
 469   // If both are members of groups
 470   if (DGroup && UGroup) {
 471     // There may have been another edge connecting
 472     if (DGroup == UGroup) return;
 473     // Add the pending users count
 474     DGroup->addPending(UGroup->getPending());
 475     // For each member of the users group
 476     NodeGroupIterator UNGI(U);
 477     while (NodeInfo *UNI = UNGI.next() ) {
 478       // Change the group
 479       UNI->Group = DGroup;
 480       // For each member of the definers group
 481       NodeGroupIterator DNGI(D);
 482       while (NodeInfo *DNI = DNGI.next() ) {
 483         // Remove internal edges
 484         DGroup->addPending(-CountInternalUses(DNI, UNI));
 485       }
 486     }
 487     // Merge the two lists
 488     DGroup->insert(DGroup->end(), UGroup->begin(), UGroup->end());
 489   } else if (DGroup) {
 490     // Make user member of definers group
 491     U->Group = DGroup;
 492     // Add users uses to definers group pending
 493     DGroup->addPending(U->Node->use_size());
 494     // For each member of the definers group
 495     NodeGroupIterator DNGI(D);
 496     while (NodeInfo *DNI = DNGI.next() ) {
 497       // Remove internal edges
 498       DGroup->addPending(-CountInternalUses(DNI, U));
 499     }
 500     DGroup->push_back(U);
 501   } else if (UGroup) {
 502     // Make definer member of users group
 503     D->Group = UGroup;
 504     // Add definers uses to users group pending
 505     UGroup->addPending(D->Node->use_size());
 506     // For each member of the users group
 507     NodeGroupIterator UNGI(U);
 508     while (NodeInfo *UNI = UNGI.next() ) {
 509       // Remove internal edges
 510       UGroup->addPending(-CountInternalUses(D, UNI));
 511     }
 512     UGroup->insert(UGroup->begin(), D);
 513   } else {
 514     D->Group = U->Group = DGroup = new NodeGroup();
 515     DGroup->addPending(D->Node->use_size() + U->Node->use_size() -
 516                        CountInternalUses(D, U));
 517     DGroup->push_back(D);
 518     DGroup->push_back(U);
 519   }
 520 }
 521
 522 /// CountInternalUses - Returns the number of edges between the two nodes.
 523 ///
 524 unsigned NodeGroup::CountInternalUses(NodeInfo *D, NodeInfo *U) {
 525   unsigned N = 0;
 526   for (SDNode:: use_iterator UI = D->Node->use_begin(),
 527                              E = D->Node->use_end(); UI != E; UI++) {
 528     if (*UI == U->Node) N++;
 529   }
 530   return N;
 531 }
 532 //===----------------------------------------------------------------------===//
 533
 534
 535 //===----------------------------------------------------------------------===//
 536 /// isFlagDefiner - Returns true if the node defines a flag result.
 537 bool SimpleSched::isFlagDefiner(SDNode *A) {
 538   unsigned N = A->getNumValues();
 539   return N && A->getValueType(N - 1) == MVT::Flag;
 540 }
 541
 542 /// isFlagUser - Returns true if the node uses a flag result.
 543 ///
 544 bool SimpleSched::isFlagUser(SDNode *A) {
 545   unsigned N = A->getNumOperands();
 546   return N && A->getOperand(N - 1).getValueType() == MVT::Flag;
 547 }
 548
 549 /// isDefiner - Return true if node A is a definer for B.
 550 ///
 551 bool SimpleSched::isDefiner(NodeInfo *A, NodeInfo *B) {
 552   // While there are A nodes
 553   NodeGroupIterator NII(A);
 554   while (NodeInfo *NI = NII.next()) {
 555     // Extract node
 556     SDNode *Node = NI->Node;
 557     // While there operands in nodes of B
 558     NodeGroupOpIterator NGOI(B);
 559     while (!NGOI.isEnd()) {
 560       SDOperand Op = NGOI.next();
 561       // If node from A defines a node in B
 562       if (Node == Op.Val) return true;
 563     }
 564   }
 565   return false;
 566 }
 567
 568 /// isPassiveNode - Return true if the node is a non-scheduled leaf.
 569 ///
 570 bool SimpleSched::isPassiveNode(SDNode *Node) {
 571   if (isa<ConstantSDNode>(Node))       return true;
 572   if (isa<RegisterSDNode>(Node))       return true;
 573   if (isa<GlobalAddressSDNode>(Node))  return true;
 574   if (isa<BasicBlockSDNode>(Node))     return true;
 575   if (isa<FrameIndexSDNode>(Node))     return true;
 576   if (isa<ConstantPoolSDNode>(Node))   return true;
 577   if (isa<ExternalSymbolSDNode>(Node)) return true;
 578   return false;
 579 }
 580
 581 /// IncludeNode - Add node to NodeInfo vector.
 582 ///
 583 void SimpleSched::IncludeNode(NodeInfo *NI) {
 584   // Get node
 585   SDNode *Node = NI->Node;
 586   // Ignore entry node
 587 if (Node->getOpcode() == ISD::EntryToken) return;
 588   // Check current count for node
 589   int Count = NI->getPending();
 590   // If the node is already in list
 591   if (Count < 0) return;
 592   // Decrement count to indicate a visit
 593   Count--;
 594   // If count has gone to zero then add node to list
 595   if (!Count) {
 596     // Add node
 597     if (NI->isInGroup()) {
 598       Ordering.push_back(NI->Group->getLeader());
 599     } else {
 600       Ordering.push_back(NI);
 601     }
 602     // indicate node has been added
 603     Count--;
 604   }
 605   // Mark as visited with new count
 606   NI->setPending(Count);
 607 }
 608
 609 /// VisitAll - Visit each node breadth-wise to produce an initial ordering.
 610 /// Note that the ordering in the Nodes vector is reversed.
 611 void SimpleSched::VisitAll() {
 612   // Add first element to list
 613   Ordering.push_back(getNI(DAG.getRoot().Val));
 614
 615   // Iterate through all nodes that have been added
 616   for (unsigned i = 0; i < Ordering.size(); i++) { // note: size() varies
 617     // Visit all operands
 618     NodeGroupOpIterator NGI(Ordering[i]);
 619     while (!NGI.isEnd()) {
 620       // Get next operand
 621       SDOperand Op = NGI.next();
 622       // Get node
 623       SDNode *Node = Op.Val;
 624       // Ignore passive nodes
 625       if (isPassiveNode(Node)) continue;
 626       // Check out node
 627       IncludeNode(getNI(Node));
 628     }
 629   }
 630
 631   // Add entry node last (IncludeNode filters entry nodes)
 632   if (DAG.getEntryNode().Val != DAG.getRoot().Val)
 633     Ordering.push_back(getNI(DAG.getEntryNode().Val));
 634
 635   // FIXME - Reverse the order
 636   for (unsigned i = 0, N = Ordering.size(), Half = N >> 1; i < Half; i++) {
 637     unsigned j = N - i - 1;
 638     NodeInfo *tmp = Ordering[i];
 639     Ordering[i] = Ordering[j];
 640     Ordering[j] = tmp;
 641   }
 642 }
 643
 644 /// IdentifyGroups - Put flagged nodes into groups.
 645 ///
 646 void SimpleSched::IdentifyGroups() {
 647   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 648     NodeInfo* NI = &Info[i];
 649     SDNode *Node = NI->Node;
 650
 651     // For each operand (in reverse to only look at flags)
 652     for (unsigned N = Node->getNumOperands(); 0 < N--;) {
 653       // Get operand
 654       SDOperand Op = Node->getOperand(N);
 655       // No more flags to walk
 656       if (Op.getValueType() != MVT::Flag) break;
 657       // Add to node group
 658       NodeGroup::Add(getNI(Op.Val), NI);
 659     }
 660   }
 661 }
 662
 663 /// GatherSchedulingInfo - Get latency and resource information about each node.
 664 ///
 665 void SimpleSched::GatherSchedulingInfo() {
 666   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 667     NodeInfo* NI = &Info[i];
 668     SDNode *Node = NI->Node;
 669
 670     MVT::ValueType VT = Node->getValueType(0);
 671
 672     if (Node->isTargetOpcode()) {
 673       MachineOpCode TOpc = Node->getTargetOpcode();
 674       // FIXME: This is an ugly (but temporary!) hack to test the scheduler
 675       // before we have real target info.
 676       // FIXME NI->Latency = std::max(1, TII.maxLatency(TOpc));
 677       // FIXME NI->ResourceSet = TII.resources(TOpc);
 678       if (TII.isCall(TOpc)) {
 679         NI->ResourceSet = RSInteger;
 680         NI->Latency = 40;
 681       } else if (TII.isLoad(TOpc)) {
 682         NI->ResourceSet = RSLoadStore;
 683         NI->Latency = 5;
 684       } else if (TII.isStore(TOpc)) {
 685         NI->ResourceSet = RSLoadStore;
 686         NI->Latency = 2;
 687       } else if (MVT::isInteger(VT)) {
 688         NI->ResourceSet = RSInteger;
 689         NI->Latency = 2;
 690       } else if (MVT::isFloatingPoint(VT)) {
 691         NI->ResourceSet = RSFloat;
 692         NI->Latency = 3;
 693       } else {
 694         NI->ResourceSet = RSOther;
 695         NI->Latency = 0;
 696       }
 697     } else {
 698       if (MVT::isInteger(VT)) {
 699         NI->ResourceSet = RSInteger;
 700         NI->Latency = 2;
 701       } else if (MVT::isFloatingPoint(VT)) {
 702         NI->ResourceSet = RSFloat;
 703         NI->Latency = 3;
 704       } else {
 705         NI->ResourceSet = RSOther;
 706         NI->Latency = 0;
 707       }
 708     }
 709
 710     // Add one slot for the instruction itself
 711     NI->Latency++;
 712
 713     // Sum up all the latencies for max tally size
 714     NSlots += NI->Latency;
 715   }
 716 }
 717
 718 /// PrepareNodeInfo - Set up the basic minimum node info for scheduling.
 719 ///
 720 void SimpleSched::PrepareNodeInfo() {
 721   // Allocate node information
 722   Info = new NodeInfo[NodeCount];
 723   // Get base of all nodes table
 724   SelectionDAG::allnodes_iterator AllNodes = DAG.allnodes_begin();
 725
 726   // For each node being scheduled
 727   for (unsigned i = 0, N = NodeCount; i < N; i++) {
 728     // Get next node from DAG all nodes table
 729     SDNode *Node = AllNodes[i];
 730     // Fast reference to node schedule info
 731     NodeInfo* NI = &Info[i];
 732     // Set up map
 733     Map[Node] = NI;
 734     // Set node
 735     NI->Node = Node;
 736     // Set pending visit count
 737     NI->setPending(Node->use_size());
 738   }
 739 }
 740
 741 /// isStrongDependency - Return true if node A has results used by node B.
 742 /// I.E., B must wait for latency of A.
 743 bool SimpleSched::isStrongDependency(NodeInfo *A, NodeInfo *B) {
 744   // If A defines for B then it's a strong dependency
 745   return isDefiner(A, B);
 746 }
 747
 748 /// isWeakDependency Return true if node A produces a result that will
 749 /// conflict with operands of B.
 750 bool SimpleSched::isWeakDependency(NodeInfo *A, NodeInfo *B) {
 751   // TODO check for conflicting real registers and aliases
 752 #if 0 // FIXME - Since we are in SSA form and not checking register aliasing
 753   return A->Node->getOpcode() == ISD::EntryToken || isStrongDependency(B, A);
 754 #else
 755   return A->Node->getOpcode() == ISD::EntryToken;
 756 #endif
 757 }
 758
 759 /// ScheduleBackward - Schedule instructions so that any long latency
 760 /// instructions and the critical path get pushed back in time. Time is run in
 761 /// reverse to allow code reuse of the Tally and eliminate the overhead of
 762 /// biasing every slot indices against NSlots.
 763 void SimpleSched::ScheduleBackward() {
 764   // Size and clear the resource tally
 765   Tally.Initialize(NSlots);
 766   // Get number of nodes to schedule
 767   unsigned N = Ordering.size();
 768
 769   // For each node being scheduled
 770   for (unsigned i = N; 0 < i--;) {
 771     NodeInfo *NI = Ordering[i];
 772     // Track insertion
 773     unsigned Slot = NotFound;
 774
 775     // Compare against those previously scheduled nodes
 776     unsigned j = i + 1;
 777     for (; j < N; j++) {
 778       // Get following instruction
 779       NodeInfo *Other = Ordering[j];
 780
 781       // Check dependency against previously inserted nodes
 782       if (isStrongDependency(NI, Other)) {
 783         Slot = Other->Slot + Other->Latency;
 784         break;
 785       } else if (isWeakDependency(NI, Other)) {
 786         Slot = Other->Slot;
 787         break;
 788       }
 789     }
 790
 791     // If independent of others (or first entry)
 792     if (Slot == NotFound) Slot = 0;
 793
 794     // Find a slot where the needed resources are available
 795     if (NI->ResourceSet)
 796       Slot = Tally.FindAndReserve(Slot, NI->Latency, NI->ResourceSet);
 797
 798     // Set node slot
 799     NI->Slot = Slot;
 800
 801     // Insert sort based on slot
 802     j = i + 1;
 803     for (; j < N; j++) {
 804       // Get following instruction
 805       NodeInfo *Other = Ordering[j];
 806       // Should we look further (remember slots are in reverse time)
 807       if (Slot >= Other->Slot) break;
 808       // Shuffle other into ordering
 809       Ordering[j - 1] = Other;
 810     }
 811     // Insert node in proper slot
 812     if (j != i + 1) Ordering[j - 1] = NI;
 813   }
 814 }
 815
 816 /// ScheduleForward - Schedule instructions to maximize packing.
 817 ///
 818 void SimpleSched::ScheduleForward() {
 819   // Size and clear the resource tally
 820   Tally.Initialize(NSlots);
 821   // Get number of nodes to schedule
 822   unsigned N = Ordering.size();
 823
 824   // For each node being scheduled
 825   for (unsigned i = 0; i < N; i++) {
 826     NodeInfo *NI = Ordering[i];
 827     // Track insertion
 828     unsigned Slot = NotFound;
 829
 830     // Compare against those previously scheduled nodes
 831     unsigned j = i;
 832     for (; 0 < j--;) {
 833       // Get following instruction
 834       NodeInfo *Other = Ordering[j];
 835
 836       // Check dependency against previously inserted nodes
 837       if (isStrongDependency(Other, NI)) {
 838         Slot = Other->Slot + Other->Latency;
 839         break;
 840       } else if (isWeakDependency(Other, NI)) {
 841         Slot = Other->Slot;
 842         break;
 843       }
 844     }
 845
 846     // If independent of others (or first entry)
 847     if (Slot == NotFound) Slot = 0;
 848
 849     // Find a slot where the needed resources are available
 850     if (NI->ResourceSet)
 851       Slot = Tally.FindAndReserve(Slot, NI->Latency, NI->ResourceSet);
 852
 853     // Set node slot
 854     NI->Slot = Slot;
 855
 856     // Insert sort based on slot
 857     j = i;
 858     for (; 0 < j--;) {
 859       // Get prior instruction
 860       NodeInfo *Other = Ordering[j];
 861       // Should we look further
 862       if (Slot >= Other->Slot) break;
 863       // Shuffle other into ordering
 864       Ordering[j + 1] = Other;
 865     }
 866     // Insert node in proper slot
 867     if (j != i) Ordering[j + 1] = NI;
 868   }
 869 }
 870
 871 /// EmitAll - Emit all nodes in schedule sorted order.
 872 ///
 873 void SimpleSched::EmitAll() {
 874   // For each node in the ordering
 875   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
 876     // Get the scheduling info
 877     NodeInfo *NI = Ordering[i];
 878     // Iterate through nodes
 879     NodeGroupIterator NGI(Ordering[i]);
 880     if (NI->isInGroup()) {
 881       if (NI->isGroupLeader()) {
 882         NodeGroupIterator NGI(Ordering[i]);
 883         while (NodeInfo *NI = NGI.next()) EmitNode(NI);
 884       }
 885     } else {
 886       EmitNode(NI);
 887     }
 888   }
 889 }
 890
 891 /// CountResults - The results of target nodes have register or immediate
 892 /// operands first, then an optional chain, and optional flag operands (which do
 893 /// not go into the machine instrs.)
 894 unsigned SimpleSched::CountResults(SDNode *Node) {
 895   unsigned N = Node->getNumValues();
 896   while (N && Node->getValueType(N - 1) == MVT::Flag)
 897     --N;
 898   if (N && Node->getValueType(N - 1) == MVT::Other)
 899     --N;    // Skip over chain result.
 900   return N;
 901 }
 902
 903 /// CountOperands  The inputs to target nodes have any actual inputs first,
 904 /// followed by an optional chain operand, then flag operands.  Compute the
 905 /// number of actual operands that  will go into the machine instr.
 906 unsigned SimpleSched::CountOperands(SDNode *Node) {
 907   unsigned N = Node->getNumOperands();
 908   while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag)
 909     --N;
 910   if (N && Node->getOperand(N - 1).getValueType() == MVT::Other)
 911     --N; // Ignore chain if it exists.
 912   return N;
 913 }
 914
 915 /// CreateVirtualRegisters - Add result register values for things that are
 916 /// defined by this instruction.
 917 unsigned SimpleSched::CreateVirtualRegisters(MachineInstr *MI,
 918                                              unsigned NumResults,
 919                                              const TargetInstrDescriptor &II) {
 920   // Create the result registers for this node and add the result regs to
 921   // the machine instruction.
 922   const TargetOperandInfo *OpInfo = II.OpInfo;
 923   unsigned ResultReg = RegMap->createVirtualRegister(OpInfo[0].RegClass);
 924   MI->addRegOperand(ResultReg, MachineOperand::Def);
 925   for (unsigned i = 1; i != NumResults; ++i) {
 926     assert(OpInfo[i].RegClass && "Isn't a register operand!");
 927     MI->addRegOperand(RegMap->createVirtualRegister(OpInfo[i].RegClass),
 928                       MachineOperand::Def);
 929   }
 930   return ResultReg;
 931 }
 932
 933 /// EmitNode - Generate machine code for an node and needed dependencies.
 934 ///
 935 void SimpleSched::EmitNode(NodeInfo *NI) {
 936   unsigned VRBase = 0;                 // First virtual register for node
 937   SDNode *Node = NI->Node;
 938
 939   // If machine instruction
 940   if (Node->isTargetOpcode()) {
 941     unsigned Opc = Node->getTargetOpcode();
 942     const TargetInstrDescriptor &II = TII.get(Opc);
 943
 944     unsigned NumResults = CountResults(Node);
 945     unsigned NodeOperands = CountOperands(Node);
 946     unsigned NumMIOperands = NodeOperands + NumResults;
 947 #ifndef NDEBUG
 948     assert((unsigned(II.numOperands) == NumMIOperands || II.numOperands == -1)&&
 949            "#operands for dag node doesn't match .td file!");
 950 #endif
 951
 952     // Create the new machine instruction.
 953     MachineInstr *MI = new MachineInstr(Opc, NumMIOperands, true, true);
 954
 955     // Add result register values for things that are defined by this
 956     // instruction.
 957     if (NumResults) VRBase = CreateVirtualRegisters(MI, NumResults, II);
 958
 959     // Emit all of the actual operands of this instruction, adding them to the
 960     // instruction as appropriate.
 961     for (unsigned i = 0; i != NodeOperands; ++i) {
 962       if (Node->getOperand(i).isTargetOpcode()) {
 963         // Note that this case is redundant with the final else block, but we
 964         // include it because it is the most common and it makes the logic
 965         // simpler here.
 966         assert(Node->getOperand(i).getValueType() != MVT::Other &&
 967                Node->getOperand(i).getValueType() != MVT::Flag &&
 968                "Chain and flag operands should occur at end of operand list!");
 969
 970         // Get/emit the operand.
 971         unsigned VReg = getVR(Node->getOperand(i));
 972         MI->addRegOperand(VReg, MachineOperand::Use);
 973
 974         // Verify that it is right.
 975         assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?");
 976         assert(II.OpInfo[i+NumResults].RegClass &&
 977                "Don't have operand info for this instruction!");
 978         assert(RegMap->getRegClass(VReg) == II.OpInfo[i+NumResults].RegClass &&
 979                "Register class of operand and regclass of use don't agree!");
 980       } else if (ConstantSDNode *C =
 981                  dyn_cast<ConstantSDNode>(Node->getOperand(i))) {
 982         MI->addZeroExtImm64Operand(C->getValue());
 983       } else if (RegisterSDNode*R =
 984                  dyn_cast<RegisterSDNode>(Node->getOperand(i))) {
 985         MI->addRegOperand(R->getReg(), MachineOperand::Use);
 986       } else if (GlobalAddressSDNode *TGA =
 987                        dyn_cast<GlobalAddressSDNode>(Node->getOperand(i))) {
 988         MI->addGlobalAddressOperand(TGA->getGlobal(), false, 0);
 989       } else if (BasicBlockSDNode *BB =
 990                        dyn_cast<BasicBlockSDNode>(Node->getOperand(i))) {
 991         MI->addMachineBasicBlockOperand(BB->getBasicBlock());
 992       } else if (FrameIndexSDNode *FI =
 993                        dyn_cast<FrameIndexSDNode>(Node->getOperand(i))) {
 994         MI->addFrameIndexOperand(FI->getIndex());
 995       } else if (ConstantPoolSDNode *CP =
 996                     dyn_cast<ConstantPoolSDNode>(Node->getOperand(i))) {
 997         unsigned Idx = ConstPool->getConstantPoolIndex(CP->get());
 998         MI->addConstantPoolIndexOperand(Idx);
 999       } else if (ExternalSymbolSDNode *ES =
1000                  dyn_cast<ExternalSymbolSDNode>(Node->getOperand(i))) {
1001         MI->addExternalSymbolOperand(ES->getSymbol(), false);
1002       } else {
1003         assert(Node->getOperand(i).getValueType() != MVT::Other &&
1004                Node->getOperand(i).getValueType() != MVT::Flag &&
1005                "Chain and flag operands should occur at end of operand list!");
1006         unsigned VReg = getVR(Node->getOperand(i));
1007         MI->addRegOperand(VReg, MachineOperand::Use);
1008
1009         // Verify that it is right.
1010         assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?");
1011         assert(II.OpInfo[i+NumResults].RegClass &&
1012                "Don't have operand info for this instruction!");
1013         assert(RegMap->getRegClass(VReg) == II.OpInfo[i+NumResults].RegClass &&
1014                "Register class of operand and regclass of use don't agree!");
1015       }
1016     }
1017
1018     // Now that we have emitted all operands, emit this instruction itself.
1019     if ((II.Flags & M_USES_CUSTOM_DAG_SCHED_INSERTION) == 0) {
1020       BB->insert(BB->end(), MI);
1021     } else {
1022       // Insert this instruction into the end of the basic block, potentially
1023       // taking some custom action.
1024       BB = DAG.getTargetLoweringInfo().InsertAtEndOfBasicBlock(MI, BB);
1025     }
1026   } else {
1027     switch (Node->getOpcode()) {
1028     default:
1029       Node->dump();
1030       assert(0 && "This target-independent node should have been selected!");
1031     case ISD::EntryToken: // fall thru
1032     case ISD::TokenFactor:
1033       break;
1034     case ISD::CopyToReg: {
1035       unsigned Val = getVR(Node->getOperand(2));
1036       MRI.copyRegToReg(*BB, BB->end(),
1037                        cast<RegisterSDNode>(Node->getOperand(1))->getReg(), Val,
1038                        RegMap->getRegClass(Val));
1039       break;
1040     }
1041     case ISD::CopyFromReg: {
1042       unsigned SrcReg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
1043       if (MRegisterInfo::isVirtualRegister(SrcReg)) {
1044         VRBase = SrcReg;  // Just use the input register directly!
1045         break;
1046       }
1047
1048       // Figure out the register class to create for the destreg.
1049       const TargetRegisterClass *TRC = 0;
1050
1051       // Pick the register class of the right type that contains this physreg.
1052       for (MRegisterInfo::regclass_iterator I = MRI.regclass_begin(),
1053            E = MRI.regclass_end(); I != E; ++I)
1054         if ((*I)->getType() == Node->getValueType(0) &&
1055             (*I)->contains(SrcReg)) {
1056           TRC = *I;
1057           break;
1058         }
1059       assert(TRC && "Couldn't find register class for reg copy!");
1060
1061       // Create the reg, emit the copy.
1062       VRBase = RegMap->createVirtualRegister(TRC);
1063       MRI.copyRegToReg(*BB, BB->end(), VRBase, SrcReg, TRC);
1064       break;
1065     }
1066     }
1067   }
1068
1069   assert(NI->VRBase == 0 && "Node emitted out of order - early");
1070   NI->VRBase = VRBase;
1071 }
1072
1073 /// Schedule - Order nodes according to selected style.
1074 ///
1075 void SimpleSched::Schedule() {
1076   // Number the nodes
1077   NodeCount = DAG.allnodes_size();
1078   // Set up minimum info for scheduling.
1079   PrepareNodeInfo();
1080   // Construct node groups for flagged nodes
1081   IdentifyGroups();
1082   // Breadth first walk of DAG
1083   VisitAll();
1084
1085 #ifndef NDEBUG
1086   static unsigned Count = 0;
1087   Count++;
1088   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
1089     NodeInfo *NI = Ordering[i];
1090     NI->Preorder = i;
1091   }
1092 #endif
1093
1094   // Don't waste time if is only entry and return
1095   if (NodeCount > 3 && ScheduleStyle != noScheduling) {
1096     // Get latency and resource requirements
1097     GatherSchedulingInfo();
1098
1099     // Push back long instructions and critical path
1100     ScheduleBackward();
1101
1102     // Pack instructions to maximize resource utilization
1103     ScheduleForward();
1104   }
1105
1106   DEBUG(printChanges(Count));
1107
1108   // Emit in scheduled order
1109   EmitAll();
1110 }
1111
1112 /// printChanges - Hilight changes in order caused by scheduling.
1113 ///
1114 void SimpleSched::printChanges(unsigned Index) {
1115 #ifndef NDEBUG
1116   // Get the ordered node count
1117   unsigned N = Ordering.size();
1118   // Determine if any changes
1119   unsigned i = 0;
1120   for (; i < N; i++) {
1121     NodeInfo *NI = Ordering[i];
1122     if (NI->Preorder != i) break;
1123   }
1124
1125   if (i < N) {
1126     std::cerr << Index << ". New Ordering\n";
1127
1128     for (i = 0; i < N; i++) {
1129       NodeInfo *NI = Ordering[i];
1130       std::cerr << "  " << NI->Preorder << ". ";
1131       printSI(std::cerr, NI);
1132       std::cerr << "\n";
1133       if (NI->isGroupLeader()) {
1134         NodeGroup *Group = NI->Group;
1135         for (NIIterator NII = Group->begin(), E = Group->end();
1136              NII != E; NII++) {
1137           std::cerr << "      ";
1138           printSI(std::cerr, *NII);
1139           std::cerr << "\n";
1140         }
1141       }
1142     }
1143   } else {
1144     std::cerr << Index << ". No Changes\n";
1145   }
1146 #endif
1147 }
1148
1149 /// printSI - Print schedule info.
1150 ///
1151 void SimpleSched::printSI(std::ostream &O, NodeInfo *NI) const {
1152 #ifndef NDEBUG
1153   SDNode *Node = NI->Node;
1154   O << " "
1155     << std::hex << Node << std::dec
1156     << ", RS=" << NI->ResourceSet
1157     << ", Lat=" << NI->Latency
1158     << ", Slot=" << NI->Slot
1159     << ", ARITY=(" << Node->getNumOperands() << ","
1160                    << Node->getNumValues() << ")"
1161     << " " << Node->getOperationName(&DAG);
1162   if (isFlagDefiner(Node)) O << "<#";
1163   if (isFlagUser(Node)) O << ">#";
1164 #endif
1165 }
1166
1167 /// print - Print ordering to specified output stream.
1168 ///
1169 void SimpleSched::print(std::ostream &O) const {
1170 #ifndef NDEBUG
1171   using namespace std;
1172   O << "Ordering\n";
1173   for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
1174     NodeInfo *NI = Ordering[i];
1175     printSI(O, NI);
1176     O << "\n";
1177     if (NI->isGroupLeader()) {
1178       NodeGroup *Group = NI->Group;
1179       for (NIIterator NII = Group->begin(), E = Group->end();
1180            NII != E; NII++) {
1181         O << "    ";
1182         printSI(O, *NII);
1183         O << "\n";
1184       }
1185     }
1186   }
1187 #endif
1188 }
1189
1190 /// dump - Print ordering to std::cerr.
1191 ///
1192 void SimpleSched::dump() const {
1193   print(std::cerr);
1194 }
1195 //===----------------------------------------------------------------------===//
1196
1197
1198 //===----------------------------------------------------------------------===//
1199 /// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each
1200 /// target node in the graph.
1201 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &SD) {
1202   if (ViewDAGs) SD.viewGraph();
1203   BB = SimpleSched(SD, BB).Run();
1204 }