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