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   // The schedule.
 168   std::vector<SUnit*> Sequence;
 169   // Current scheduling cycle.
 170   unsigned CurrCycle;
 171   // First and last SUnit created.
 172   SUnit *HeadSUnit, *TailSUnit;
 173
 174   typedef std::priority_queue<SUnit*, std::vector<SUnit*>, ls_rr_sort>
 175     AvailableQueueTy;
 176
 177 public:
 178   ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb,
 179                   const TargetMachine &tm)
 180     : ScheduleDAG(listSchedulingBURR, dag, bb, tm),
 181       CurrCycle(0), HeadSUnit(NULL), TailSUnit(NULL) {};
 182
 183   ~ScheduleDAGList() {
 184     SUnit *SU = HeadSUnit;
 185     while (SU) {
 186       SUnit *NextSU = SU->Next;
 187       delete SU;
 188       SU = NextSU;
 189     }
 190   }
 191
 192   void Schedule();
 193
 194   void dump() const;
 195
 196 private:
 197   SUnit *NewSUnit(SDNode *N);
 198   void ReleasePred(AvailableQueueTy &Avail,SUnit *PredSU, bool isChain = false);
 199   void ScheduleNode(AvailableQueueTy &Avail, SUnit *SU);
 200   int  CalcNodePriority(SUnit *SU);
 201   void CalculatePriorities();
 202   void ListSchedule();
 203   void BuildSchedUnits();
 204   void EmitSchedule();
 205 };
 206 }  // end namespace
 207
 208
 209 /// NewSUnit - Creates a new SUnit and return a ptr to it.
 210 SUnit *ScheduleDAGList::NewSUnit(SDNode *N) {
 211   SUnit *CurrSUnit = new SUnit(N);
 212
 213   if (HeadSUnit == NULL)
 214     HeadSUnit = CurrSUnit;
 215   if (TailSUnit != NULL)
 216     TailSUnit->Next = CurrSUnit;
 217   TailSUnit = CurrSUnit;
 218
 219   return CurrSUnit;
 220 }
 221
 222 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
 223 /// the Available queue is the count reaches zero. Also update its cycle bound.
 224 void ScheduleDAGList::ReleasePred(AvailableQueueTy &Available,
 225                                   SUnit *PredSU, bool isChain) {
 226   SDNode *PredNode = PredSU->Node;
 227
 228   // FIXME: the distance between two nodes is not always == the predecessor's
 229   // latency. For example, the reader can very well read the register written
 230   // by the predecessor later than the issue cycle. It also depends on the
 231   // interrupt model (drain vs. freeze).
 232   PredSU->CycleBound = std::max(PredSU->CycleBound, CurrCycle + PredSU->Latency);
 233
 234   if (!isChain) {
 235     PredSU->NumSuccsLeft--;
 236     PredSU->Priority1++;
 237   } else
 238     PredSU->NumChainSuccsLeft--;
 239   if (PredSU->NumSuccsLeft == 0 && PredSU->NumChainSuccsLeft == 0) {
 240     // EntryToken has to go last!
 241     if (PredNode->getOpcode() != ISD::EntryToken)
 242       Available.push(PredSU);
 243   } else if (PredSU->NumSuccsLeft < 0) {
 244 #ifndef NDEBUG
 245     std::cerr << "*** List scheduling failed! ***\n";
 246     PredSU->dump(&DAG);
 247     std::cerr << " has been released too many times!\n";
 248     assert(0);
 249 #endif
 250   }
 251 }
 252
 253 /// ScheduleNode - Add the node to the schedule. Decrement the pending count of
 254 /// its predecessors. If a predecessor pending count is zero, add it to the
 255 /// Available queue.
 256 void ScheduleDAGList::ScheduleNode(AvailableQueueTy &Available, SUnit *SU) {
 257   DEBUG(std::cerr << "*** Scheduling: ");
 258   DEBUG(SU->dump(&DAG, false));
 259
 260   Sequence.push_back(SU);
 261   SU->Slot = CurrCycle;
 262
 263   // Bottom up: release predecessors
 264   for (std::set<SUnit*>::iterator I1 = SU->Preds.begin(),
 265          E1 = SU->Preds.end(); I1 != E1; ++I1) {
 266     ReleasePred(Available, *I1);
 267     SU->NumPredsLeft--;
 268     SU->Priority1--;
 269   }
 270   for (std::set<SUnit*>::iterator I2 = SU->ChainPreds.begin(),
 271          E2 = SU->ChainPreds.end(); I2 != E2; ++I2)
 272     ReleasePred(Available, *I2, true);
 273
 274   CurrCycle++;
 275 }
 276
 277 /// isReady - True if node's lower cycle bound is less or equal to the current
 278 /// scheduling cycle. Always true if all nodes have uniform latency 1.
 279 static inline bool isReady(SUnit *SU, unsigned CurrCycle) {
 280   return SU->CycleBound <= CurrCycle;
 281 }
 282
 283 /// ListSchedule - The main loop of list scheduling.
 284 void ScheduleDAGList::ListSchedule() {
 285   // Available queue.
 286   AvailableQueueTy Available;
 287
 288   // Add root to Available queue.
 289   SUnit *Root = SUnitMap[DAG.getRoot().Val];
 290   Available.push(Root);
 291
 292   // While Available queue is not empty, grab the node with the highest
 293   // priority. If it is not ready put it back. Schedule the node.
 294   std::vector<SUnit*> NotReady;
 295   while (!Available.empty()) {
 296     SUnit *CurrNode = Available.top();
 297     Available.pop();
 298
 299     NotReady.clear();
 300     while (!isReady(CurrNode, CurrCycle)) {
 301       NotReady.push_back(CurrNode);
 302       CurrNode = Available.top();
 303       Available.pop();
 304     }
 305     for (unsigned i = 0, e = NotReady.size(); i != e; ++i)
 306       Available.push(NotReady[i]);
 307
 308     ScheduleNode(Available, CurrNode);
 309   }
 310
 311   // Add entry node last
 312   if (DAG.getEntryNode().Val != DAG.getRoot().Val) {
 313     SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
 314     Entry->Slot = CurrCycle;
 315     Sequence.push_back(Entry);
 316   }
 317
 318 #ifndef NDEBUG
 319   bool AnyNotSched = false;
 320   for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
 321     if (SU->NumSuccsLeft != 0 || SU->NumChainSuccsLeft != 0) {
 322       if (!AnyNotSched)
 323         std::cerr << "*** List scheduling failed! ***\n";
 324       SU->dump(&DAG);
 325       std::cerr << "has not been scheduled!\n";
 326       AnyNotSched = true;
 327     }
 328   }
 329   assert(!AnyNotSched);
 330 #endif
 331
 332
 333   // Reverse the order if it is bottom up.
 334   std::reverse(Sequence.begin(), Sequence.end());
 335
 336   DEBUG(std::cerr << "*** Final schedule ***\n");
 337   DEBUG(dump());
 338   DEBUG(std::cerr << "\n");
 339 }
 340
 341 /// CalcNodePriority - Priority1 is just the number of live range genned -
 342 /// number of live range killed. Priority2 is the Sethi Ullman number. It
 343 /// returns Priority2 since it is calculated recursively.
 344 /// Smaller number is the higher priority for Priority2. Reverse is true for
 345 /// Priority1.
 346 int ScheduleDAGList::CalcNodePriority(SUnit *SU) {
 347   if (SU->Priority2 != INT_MIN)
 348     return SU->Priority2;
 349
 350   SU->Priority1 = SU->NumPredsLeft - SU->NumSuccsLeft;
 351
 352   if (SU->Preds.size() == 0) {
 353     SU->Priority2 = 1;
 354   } else {
 355     int Extra = 0;
 356     for (std::set<SUnit*>::iterator I = SU->Preds.begin(),
 357            E = SU->Preds.end(); I != E; ++I) {
 358       SUnit *PredSU = *I;
 359       int PredPriority = CalcNodePriority(PredSU);
 360       if (PredPriority > SU->Priority2) {
 361         SU->Priority2 = PredPriority;
 362         Extra = 0;
 363       } else if (PredPriority == SU->Priority2)
 364         Extra++;
 365     }
 366
 367     if (SU->Node->getOpcode() != ISD::TokenFactor)
 368       SU->Priority2 += Extra;
 369     else
 370       SU->Priority2 = (Extra == 1) ? 0 : Extra-1;
 371   }
 372
 373   return SU->Priority2;
 374 }
 375
 376 /// CalculatePriorities - Calculate priorities of all scheduling units.
 377 void ScheduleDAGList::CalculatePriorities() {
 378   for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
 379     // FIXME: assumes uniform latency for now.
 380     SU->Latency = 1;
 381     (void)CalcNodePriority(SU);
 382     DEBUG(SU->dump(&DAG));
 383     DEBUG(std::cerr << "\n");
 384   }
 385 }
 386
 387 void ScheduleDAGList::BuildSchedUnits() {
 388   // Pass 1: create the SUnit's.
 389   for (unsigned i = 0, NC = NodeCount; i < NC; i++) {
 390     NodeInfo *NI = &Info[i];
 391     SDNode *N = NI->Node;
 392     if (isPassiveNode(N))
 393       continue;
 394
 395     SUnit *SU;
 396     if (NI->isInGroup()) {
 397       if (NI != NI->Group->getBottom())  // Bottom up, so only look at bottom
 398         continue;                        // node of the NodeGroup
 399
 400       SU = NewSUnit(N);
 401       // Find the flagged nodes.
 402       SDOperand  FlagOp = N->getOperand(N->getNumOperands() - 1);
 403       SDNode    *Flag   = FlagOp.Val;
 404       unsigned   ResNo  = FlagOp.ResNo;
 405       while (Flag->getValueType(ResNo) == MVT::Flag) {
 406         NodeInfo *FNI = getNI(Flag);
 407         assert(FNI->Group == NI->Group);
 408         SU->FlaggedNodes.insert(SU->FlaggedNodes.begin(), Flag);
 409         SUnitMap[Flag] = SU;
 410
 411         FlagOp = Flag->getOperand(Flag->getNumOperands() - 1);
 412         Flag   = FlagOp.Val;
 413         ResNo  = FlagOp.ResNo;
 414       }
 415     } else {
 416       SU = NewSUnit(N);
 417     }
 418     SUnitMap[N] = SU;
 419   }
 420
 421   // Pass 2: add the preds, succs, etc.
 422   for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
 423     SDNode   *N  = SU->Node;
 424     NodeInfo *NI = getNI(N);
 425
 426     if (N->isTargetOpcode() && TII->isTwoAddrInstr(N->getTargetOpcode()))
 427       SU->isTwoAddress = true;
 428
 429     if (NI->isInGroup()) {
 430       // Find all predecessors (of the group).
 431       NodeGroupOpIterator NGOI(NI);
 432       while (!NGOI.isEnd()) {
 433         SDOperand Op  = NGOI.next();
 434         SDNode   *OpN = Op.Val;
 435         MVT::ValueType VT = OpN->getValueType(Op.ResNo);
 436         NodeInfo *OpNI = getNI(OpN);
 437         if (OpNI->Group != NI->Group && !isPassiveNode(OpN)) {
 438           assert(VT != MVT::Flag);
 439           SUnit *OpSU = SUnitMap[OpN];
 440           if (VT == MVT::Other) {
 441             if (SU->ChainPreds.insert(OpSU).second)
 442               SU->NumChainPredsLeft++;
 443             if (OpSU->ChainSuccs.insert(SU).second)
 444               OpSU->NumChainSuccsLeft++;
 445           } else {
 446             if (SU->Preds.insert(OpSU).second)
 447               SU->NumPredsLeft++;
 448             if (OpSU->Succs.insert(SU).second)
 449               OpSU->NumSuccsLeft++;
 450           }
 451         }
 452       }
 453     } else {
 454       // Find node predecessors.
 455       for (unsigned j = 0, e = N->getNumOperands(); j != e; j++) {
 456         SDOperand Op  = N->getOperand(j);
 457         SDNode   *OpN = Op.Val;
 458         MVT::ValueType VT = OpN->getValueType(Op.ResNo);
 459         if (!isPassiveNode(OpN)) {
 460           assert(VT != MVT::Flag);
 461           SUnit *OpSU = SUnitMap[OpN];
 462           if (VT == MVT::Other) {
 463             if (SU->ChainPreds.insert(OpSU).second)
 464               SU->NumChainPredsLeft++;
 465             if (OpSU->ChainSuccs.insert(SU).second)
 466               OpSU->NumChainSuccsLeft++;
 467           } else {
 468             if (SU->Preds.insert(OpSU).second)
 469               SU->NumPredsLeft++;
 470             if (OpSU->Succs.insert(SU).second)
 471               OpSU->NumSuccsLeft++;
 472             if (j == 0 && SU->isTwoAddress)
 473               OpSU->isDefNUseOperand = true;
 474           }
 475         }
 476       }
 477     }
 478   }
 479 }
 480
 481 /// EmitSchedule - Emit the machine code in scheduled order.
 482 void ScheduleDAGList::EmitSchedule() {
 483   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
 484     SDNode *N;
 485     SUnit *SU = Sequence[i];
 486     for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; j++) {
 487       N = SU->FlaggedNodes[j];
 488       EmitNode(getNI(N));
 489     }
 490     EmitNode(getNI(SU->Node));
 491   }
 492 }
 493
 494 /// dump - dump the schedule.
 495 void ScheduleDAGList::dump() const {
 496   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
 497     SUnit *SU = Sequence[i];
 498     SU->dump(&DAG, false);
 499   }
 500 }
 501
 502 /// Schedule - Schedule the DAG using list scheduling.
 503 /// FIXME: Right now it only supports the burr (bottom up register reducing)
 504 /// heuristic.
 505 void ScheduleDAGList::Schedule() {
 506   DEBUG(std::cerr << "********** List Scheduling **********\n");
 507
 508   // Build scheduling units.
 509   BuildSchedUnits();
 510
 511   // Calculate node prirorities.
 512   CalculatePriorities();
 513
 514   // Execute the actual scheduling loop.
 515   ListSchedule();
 516
 517   // Emit in scheduled order
 518   EmitSchedule();
 519 }
 520
 521 llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAG &DAG,
 522                                                     MachineBasicBlock *BB) {
 523   return new ScheduleDAGList(DAG, BB, DAG.getTarget());
 524 }