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