lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp

   1 //===---- ScheduleDAGList.cpp - Implement a list scheduler for isel DAG ---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Evan Cheng 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 <climits>
  23 #include <iostream>
  24 #include <queue>
  25 #include <set>
  26 #include <vector>
  27 using namespace llvm;
  28
  29 namespace {
  30
  31 /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or a
  32 /// group of nodes flagged together.
  33 struct SUnit {
  34   SDNode *Node;                       // Representative node.
  35   std::vector<SDNode*> FlaggedNodes;  // All nodes flagged to Node.
  36   std::set<SUnit*> Preds;             // All real predecessors.
  37   std::set<SUnit*> ChainPreds;        // All chain predecessors.
  38   std::set<SUnit*> Succs;             // All real successors.
  39   std::set<SUnit*> ChainSuccs;        // All chain successors.
  40   int NumPredsLeft;                   // # of preds not scheduled.
  41   int NumSuccsLeft;                   // # of succs not scheduled.
  42   int NumChainPredsLeft;              // # of chain preds not scheduled.
  43   int NumChainSuccsLeft;              // # of chain succs not scheduled.
  44   int Priority1;                      // Scheduling priority 1.
  45   int Priority2;                      // Scheduling priority 2.
  46   bool isTwoAddress;                  // Is a two-address instruction.
  47   bool isDefNUseOperand;              // Is a def&use operand.
  48   unsigned Latency;                   // Node latency.
  49   unsigned CycleBound;                // Upper/lower cycle to be scheduled at.
  50   unsigned Slot;                      // Cycle node is scheduled at.
  51   SUnit *Next;
  52
  53   SUnit(SDNode *node)
  54     : Node(node), NumPredsLeft(0), NumSuccsLeft(0),
  55       NumChainPredsLeft(0), NumChainSuccsLeft(0),
  56       Priority1(INT_MIN), Priority2(INT_MIN),
  57       isTwoAddress(false), isDefNUseOperand(false),
  58       Latency(0), CycleBound(0), Slot(0), Next(NULL) {}
  59
  60   void dump(const SelectionDAG *G, bool All=true) const;
  61 };
  62
  63 void SUnit::dump(const SelectionDAG *G, bool All) const {
  64   std::cerr << "SU: ";
  65   Node->dump(G);
  66   std::cerr << "\n";
  67   if (FlaggedNodes.size() != 0) {
  68     for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) {
  69       std::cerr << "    ";
  70       FlaggedNodes[i]->dump(G);
  71       std::cerr << "\n";
  72     }
  73   }
  74
  75   if (All) {
  76     std::cerr << "# preds left       : " << NumPredsLeft << "\n";
  77     std::cerr << "# succs left       : " << NumSuccsLeft << "\n";
  78     std::cerr << "# chain preds left : " << NumChainPredsLeft << "\n";
  79     std::cerr << "# chain succs left : " << NumChainSuccsLeft << "\n";
  80     std::cerr << "Latency            : " << Latency << "\n";
  81     std::cerr << "Priority           : " << Priority1 << " , " << Priority2 << "\n";
  82
  83     if (Preds.size() != 0) {
  84       std::cerr << "Predecessors  :\n";
  85       for (std::set<SUnit*>::const_iterator I = Preds.begin(),
  86              E = Preds.end(); I != E; ++I) {
  87         std::cerr << "    ";
  88         (*I)->dump(G, false);
  89       }
  90     }
  91     if (ChainPreds.size() != 0) {
  92       std::cerr << "Chained Preds :\n";
  93       for (std::set<SUnit*>::const_iterator I = ChainPreds.begin(),
  94              E = ChainPreds.end(); I != E; ++I) {
  95         std::cerr << "    ";
  96         (*I)->dump(G, false);
  97       }
  98     }
  99     if (Succs.size() != 0) {
 100       std::cerr << "Successors    :\n";
 101       for (std::set<SUnit*>::const_iterator I = Succs.begin(),
 102              E = Succs.end(); I != E; ++I) {
 103         std::cerr << "    ";
 104         (*I)->dump(G, false);
 105       }
 106     }
 107     if (ChainSuccs.size() != 0) {
 108       std::cerr << "Chained succs :\n";
 109       for (std::set<SUnit*>::const_iterator I = ChainSuccs.begin(),
 110              E = ChainSuccs.end(); I != E; ++I) {
 111         std::cerr << "    ";
 112         (*I)->dump(G, false);
 113       }
 114     }
 115   }
 116 }
 117
 118 /// Sorting functions for the Available queue.
 119 struct ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
 120   bool operator()(const SUnit* left, const SUnit* right) const {
 121     bool LFloater = (left ->Preds.size() == 0);
 122     bool RFloater = (right->Preds.size() == 0);
 123     int LBonus = (int)left ->isDefNUseOperand;
 124     int RBonus = (int)right->isDefNUseOperand;
 125
 126     // Special tie breaker: if two nodes share a operand, the one that
 127     // use it as a def&use operand is preferred.
 128     if (left->isTwoAddress && !right->isTwoAddress) {
 129       SDNode *DUNode = left->Node->getOperand(0).Val;
 130       if (DUNode->isOperand(right->Node))
 131         LBonus++;
 132     }
 133     if (!left->isTwoAddress && right->isTwoAddress) {
 134       SDNode *DUNode = right->Node->getOperand(0).Val;
 135       if (DUNode->isOperand(left->Node))
 136         RBonus++;
 137     }
 138
 139     int LPriority1 = left ->Priority1 - LBonus;
 140     int RPriority1 = right->Priority1 - RBonus;
 141     int LPriority2 = left ->Priority2 + LBonus;
 142     int RPriority2 = right->Priority2 + RBonus;
 143
 144     // Favor floaters (i.e. node with no non-passive predecessors):
 145     // e.g. MOV32ri.
 146     if (!LFloater && RFloater)
 147       return true;
 148     else if (LFloater == RFloater)
 149       if (LPriority1 > RPriority1)
 150         return true;
 151       else if (LPriority1 == RPriority1)
 152         if (LPriority2 < RPriority2)
 153           return true;
 154         else if (LPriority1 == RPriority1)
 155           if (left->CycleBound > right->CycleBound)
 156             return true;
 157
 158     return false;
 159   }
 160 };
 161
 162 /// ScheduleDAGList - List scheduler.
 163 class ScheduleDAGList : public ScheduleDAG {
 164 private:
 165   // SDNode to SUnit mapping (many to one).
 166   std::map<SDNode*, SUnit*> SUnitMap;
 167   // Available queue.
 168   std::priority_queue<SUnit*, std::vector<SUnit*>, ls_rr_sort> Available;
 169   // The schedule.
 170   std::vector<SUnit*> Sequence;
 171   // Current scheduling cycle.
 172   unsigned CurrCycle;
 173   // First and last SUnit created.
 174   SUnit *HeadSUnit, *TailSUnit;
 175
 176 public:
 177   ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb,
 178                   const TargetMachine &tm)
 179     : ScheduleDAG(listSchedulingBURR, dag, bb, tm),
 180       CurrCycle(0), HeadSUnit(NULL), TailSUnit(NULL) {};
 181
 182   ~ScheduleDAGList() {
 183     SUnit *SU = HeadSUnit;
 184     while (SU) {
 185       SUnit *NextSU = SU->Next;
 186       delete SU;
 187       SU = NextSU;
 188     }
 189   }
 190
 191   void Schedule();
 192
 193   void dump() const;
 194
 195 private:
 196   SUnit *NewSUnit(SDNode *N);
 197   void ReleasePred(SUnit *PredSU, bool isChain = false);
 198   void ScheduleNode(SUnit *SU);
 199   int  CalcNodePriority(SUnit *SU);
 200   void CalculatePriorities();
 201   void ListSchedule();
 202   void BuildSchedUnits();
 203   void EmitSchedule();
 204 };
 205 }  // end namespace
 206
 207
 208 /// NewSUnit - Creates a new SUnit and return a ptr to it.
 209 SUnit *ScheduleDAGList::NewSUnit(SDNode *N) {
 210   SUnit *CurrSUnit = new SUnit(N);
 211
 212   if (HeadSUnit == NULL)
 213     HeadSUnit = CurrSUnit;
 214   if (TailSUnit != NULL)
 215     TailSUnit->Next = CurrSUnit;
 216   TailSUnit = CurrSUnit;
 217
 218   return CurrSUnit;
 219 }
 220
 221 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
 222 /// the Available queue is the count reaches zero. Also update its cycle bound.
 223 void ScheduleDAGList::ReleasePred(SUnit *PredSU, bool isChain) {
 224   SDNode *PredNode = PredSU->Node;
 225
 226   // FIXME: the distance between two nodes is not always == the predecessor's
 227   // latency. For example, the reader can very well read the register written
 228   // by the predecessor later than the issue cycle. It also depends on the
 229   // interrupt model (drain vs. freeze).
 230   PredSU->CycleBound = std::max(PredSU->CycleBound, CurrCycle + PredSU->Latency);
 231
 232   if (!isChain) {
 233     PredSU->NumSuccsLeft--;
 234     PredSU->Priority1++;
 235   } else
 236     PredSU->NumChainSuccsLeft--;
 237   if (PredSU->NumSuccsLeft == 0 && PredSU->NumChainSuccsLeft == 0) {
 238     // EntryToken has to go last!
 239     if (PredNode->getOpcode() != ISD::EntryToken)
 240       Available.push(PredSU);
 241   } else if (PredSU->NumSuccsLeft < 0) {
 242 #ifndef NDEBUG
 243     std::cerr << "*** List scheduling failed! ***\n";
 244     PredSU->dump(&DAG);
 245     std::cerr << " has been released too many times!\n";
 246     assert(0);
 247 #endif
 248   }
 249 }
 250
 251 /// ScheduleNode - Add the node to the schedule. Decrement the pending count of
 252 /// its predecessors. If a predecessor pending count is zero, add it to the
 253 /// Available queue.
 254 void ScheduleDAGList::ScheduleNode(SUnit *SU) {
 255   DEBUG(std::cerr << "*** Scheduling: ");
 256   DEBUG(SU->dump(&DAG, false));
 257
 258   Sequence.push_back(SU);
 259   SU->Slot = CurrCycle;
 260
 261   // Bottom up: release predecessors
 262   for (std::set<SUnit*>::iterator I1 = SU->Preds.begin(),
 263          E1 = SU->Preds.end(); I1 != E1; ++I1) {
 264     ReleasePred(*I1);
 265     SU->NumPredsLeft--;
 266     SU->Priority1--;
 267   }
 268   for (std::set<SUnit*>::iterator I2 = SU->ChainPreds.begin(),
 269          E2 = SU->ChainPreds.end(); I2 != E2; ++I2)
 270     ReleasePred(*I2, true);
 271
 272   CurrCycle++;
 273 }
 274
 275 /// isReady - True if node's lower cycle bound is less or equal to the current
 276 /// scheduling cycle. Always true if all nodes have uniform latency 1.
 277 static inline bool isReady(SUnit *SU, unsigned CurrCycle) {
 278   return SU->CycleBound <= CurrCycle;
 279 }
 280
 281 /// ListSchedule - The main loop of list scheduling.
 282 void ScheduleDAGList::ListSchedule() {
 283   // Add root to Available queue
 284   SUnit *Root = SUnitMap[DAG.getRoot().Val];
 285   Available.push(Root);
 286
 287   // While Available queue is not empty, grab the node with the highest
 288   // priority. If it is not ready put it back. Schedule the node.
 289   std::vector<SUnit*> NotReady;
 290   while (!Available.empty()) {
 291     SUnit *CurrNode = Available.top();
 292     Available.pop();
 293
 294     NotReady.clear();
 295     while (!isReady(CurrNode, CurrCycle)) {
 296       NotReady.push_back(CurrNode);
 297       CurrNode = Available.top();
 298       Available.pop();
 299     }
 300     for (unsigned i = 0, e = NotReady.size(); i != e; ++i)
 301       Available.push(NotReady[i]);
 302
 303     ScheduleNode(CurrNode);
 304   }
 305
 306   // Add entry node last
 307   if (DAG.getEntryNode().Val != DAG.getRoot().Val) {
 308     SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
 309     Entry->Slot = CurrCycle;
 310     Sequence.push_back(Entry);
 311   }
 312
 313 #ifndef NDEBUG
 314   bool AnyNotSched = false;
 315   for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
 316     if (SU->NumSuccsLeft != 0 || SU->NumChainSuccsLeft != 0) {
 317       if (!AnyNotSched)
 318         std::cerr << "*** List scheduling failed! ***\n";
 319       SU->dump(&DAG);
 320       std::cerr << "has not been scheduled!\n";
 321       AnyNotSched = true;
 322     }
 323   }
 324   assert(!AnyNotSched);
 325 #endif
 326
 327
 328   // Reverse the order if it is bottom up.
 329   std::reverse(Sequence.begin(), Sequence.end());
 330
 331   DEBUG(std::cerr << "*** Final schedule ***\n");
 332   DEBUG(dump());
 333   DEBUG(std::cerr << "\n");
 334 }
 335
 336 /// CalcNodePriority - Priority1 is just the number of live range genned -
 337 /// number of live range killed. Priority2 is the Sethi Ullman number. It
 338 /// returns Priority2 since it is calculated recursively.
 339 /// Smaller number is the higher priority for Priority2. Reverse is true for
 340 /// Priority1.
 341 int ScheduleDAGList::CalcNodePriority(SUnit *SU) {
 342   if (SU->Priority2 != INT_MIN)
 343     return SU->Priority2;
 344
 345   SU->Priority1 = SU->NumPredsLeft - SU->NumSuccsLeft;
 346
 347   if (SU->Preds.size() == 0) {
 348     SU->Priority2 = 1;
 349   } else {
 350     int Extra = 0;
 351     for (std::set<SUnit*>::iterator I = SU->Preds.begin(),
 352            E = SU->Preds.end(); I != E; ++I) {
 353       SUnit *PredSU = *I;
 354       int PredPriority = CalcNodePriority(PredSU);
 355       if (PredPriority > SU->Priority2) {
 356         SU->Priority2 = PredPriority;
 357         Extra = 0;
 358       } else if (PredPriority == SU->Priority2)
 359         Extra++;
 360     }
 361
 362     if (SU->Node->getOpcode() != ISD::TokenFactor)
 363       SU->Priority2 += Extra;
 364     else
 365       SU->Priority2 = (Extra == 1) ? 0 : Extra-1;
 366   }
 367
 368   return SU->Priority2;
 369 }
 370
 371 /// CalculatePriorities - Calculate priorities of all scheduling units.
 372 void ScheduleDAGList::CalculatePriorities() {
 373   for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
 374     // FIXME: assumes uniform latency for now.
 375     SU->Latency = 1;
 376     (void)CalcNodePriority(SU);
 377     DEBUG(SU->dump(&DAG));
 378     DEBUG(std::cerr << "\n");
 379   }
 380 }
 381
 382 void ScheduleDAGList::BuildSchedUnits() {
 383   // Pass 1: create the SUnit's.
 384   for (unsigned i = 0, NC = NodeCount; i < NC; i++) {
 385     NodeInfo *NI = &Info[i];
 386     SDNode *N = NI->Node;
 387     if (isPassiveNode(N))
 388       continue;
 389
 390     SUnit *SU;
 391     if (NI->isInGroup()) {
 392       if (NI != NI->Group->getBottom())  // Bottom up, so only look at bottom
 393         continue;                        // node of the NodeGroup
 394
 395       SU = NewSUnit(N);
 396       // Find the flagged nodes.
 397       SDOperand  FlagOp = N->getOperand(N->getNumOperands() - 1);
 398       SDNode    *Flag   = FlagOp.Val;
 399       unsigned   ResNo  = FlagOp.ResNo;
 400       while (Flag->getValueType(ResNo) == MVT::Flag) {
 401         NodeInfo *FNI = getNI(Flag);
 402         assert(FNI->Group == NI->Group);
 403         SU->FlaggedNodes.insert(SU->FlaggedNodes.begin(), Flag);
 404         SUnitMap[Flag] = SU;
 405
 406         FlagOp = Flag->getOperand(Flag->getNumOperands() - 1);
 407         Flag   = FlagOp.Val;
 408         ResNo  = FlagOp.ResNo;
 409       }
 410     } else {
 411       SU = NewSUnit(N);
 412     }
 413     SUnitMap[N] = SU;
 414   }
 415
 416   // Pass 2: add the preds, succs, etc.
 417   for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
 418     SDNode   *N  = SU->Node;
 419     NodeInfo *NI = getNI(N);
 420
 421     if (N->isTargetOpcode() && TII->isTwoAddrInstr(N->getTargetOpcode()))
 422       SU->isTwoAddress = true;
 423
 424     if (NI->isInGroup()) {
 425       // Find all predecessors (of the group).
 426       NodeGroupOpIterator NGOI(NI);
 427       while (!NGOI.isEnd()) {
 428         SDOperand Op  = NGOI.next();
 429         SDNode   *OpN = Op.Val;
 430         MVT::ValueType VT = OpN->getValueType(Op.ResNo);
 431         NodeInfo *OpNI = getNI(OpN);
 432         if (OpNI->Group != NI->Group && !isPassiveNode(OpN)) {
 433           assert(VT != MVT::Flag);
 434           SUnit *OpSU = SUnitMap[OpN];
 435           if (VT == MVT::Other) {
 436             if (SU->ChainPreds.insert(OpSU).second)
 437               SU->NumChainPredsLeft++;
 438             if (OpSU->ChainSuccs.insert(SU).second)
 439               OpSU->NumChainSuccsLeft++;
 440           } else {
 441             if (SU->Preds.insert(OpSU).second)
 442               SU->NumPredsLeft++;
 443             if (OpSU->Succs.insert(SU).second)
 444               OpSU->NumSuccsLeft++;
 445           }
 446         }
 447       }
 448     } else {
 449       // Find node predecessors.
 450       for (unsigned j = 0, e = N->getNumOperands(); j != e; j++) {
 451         SDOperand Op  = N->getOperand(j);
 452         SDNode   *OpN = Op.Val;
 453         MVT::ValueType VT = OpN->getValueType(Op.ResNo);
 454         if (!isPassiveNode(OpN)) {
 455           assert(VT != MVT::Flag);
 456           SUnit *OpSU = SUnitMap[OpN];
 457           if (VT == MVT::Other) {
 458             if (SU->ChainPreds.insert(OpSU).second)
 459               SU->NumChainPredsLeft++;
 460             if (OpSU->ChainSuccs.insert(SU).second)
 461               OpSU->NumChainSuccsLeft++;
 462           } else {
 463             if (SU->Preds.insert(OpSU).second)
 464               SU->NumPredsLeft++;
 465             if (OpSU->Succs.insert(SU).second)
 466               OpSU->NumSuccsLeft++;
 467             if (j == 0 && SU->isTwoAddress)
 468               OpSU->isDefNUseOperand = true;
 469           }
 470         }
 471       }
 472     }
 473   }
 474 }
 475
 476 /// EmitSchedule - Emit the machine code in scheduled order.
 477 void ScheduleDAGList::EmitSchedule() {
 478   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
 479     SDNode *N;
 480     SUnit *SU = Sequence[i];
 481     for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; j++) {
 482       N = SU->FlaggedNodes[j];
 483       EmitNode(getNI(N));
 484     }
 485     EmitNode(getNI(SU->Node));
 486   }
 487 }
 488
 489 /// dump - dump the schedule.
 490 void ScheduleDAGList::dump() const {
 491   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
 492     SUnit *SU = Sequence[i];
 493     SU->dump(&DAG, false);
 494   }
 495 }
 496
 497 /// Schedule - Schedule the DAG using list scheduling.
 498 /// FIXME: Right now it only supports the burr (bottom up register reducing)
 499 /// heuristic.
 500 void ScheduleDAGList::Schedule() {
 501   DEBUG(std::cerr << "********** List Scheduling **********\n");
 502
 503   // Build scheduling units.
 504   BuildSchedUnits();
 505
 506   // Calculate node prirorities.
 507   CalculatePriorities();
 508
 509   // Execute the actual scheduling loop.
 510   ListSchedule();
 511
 512   // Emit in scheduled order
 513   EmitSchedule();
 514 }
 515
 516 llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAG &DAG,
 517                                                     MachineBasicBlock *BB) {
 518   return new ScheduleDAGList(DAG, BB, DAG.getTarget());
 519 }