LLVM  6.0.0svn
HexagonMachineScheduler.cpp
Go to the documentation of this file.
1 //===- HexagonMachineScheduler.cpp - MI Scheduler for Hexagon -------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // MachineScheduler schedules machine instructions after phi elimination. It
11 // preserves LiveIntervals so it can be invoked before register allocation.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "HexagonInstrInfo.h"
17 #include "HexagonSubtarget.h"
18 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/IR/Function.h"
34 #include "llvm/Support/Debug.h"
36 #include <algorithm>
37 #include <cassert>
38 #include <iomanip>
39 #include <limits>
40 #include <memory>
41 #include <sstream>
42 
43 using namespace llvm;
44 
45 #define DEBUG_TYPE "machine-scheduler"
46 
47 static cl::opt<bool> IgnoreBBRegPressure("ignore-bb-reg-pressure",
49 
50 static cl::opt<unsigned> SchedDebugVerboseLevel("misched-verbose-level",
52 
53 static cl::opt<bool> TopUseShorterTie("top-use-shorter-tie",
55 
56 static cl::opt<bool> BotUseShorterTie("bot-use-shorter-tie",
58 
59 static cl::opt<bool> DisableTCTie("disable-tc-tie",
61 
62 // Check if the scheduler should penalize instructions that are available to
63 // early due to a zero-latency dependence.
64 static cl::opt<bool> CheckEarlyAvail("check-early-avail", cl::Hidden,
65  cl::ZeroOrMore, cl::init(true));
66 
67 /// Save the last formed packet
69  OldPacket = Packet;
70 }
71 
72 /// Check if scheduling of this SU is possible
73 /// in the current packet.
74 /// It is _not_ precise (statefull), it is more like
75 /// another heuristic. Many corner cases are figured
76 /// empirically.
78  if (!SU || !SU->getInstr())
79  return false;
80 
81  // First see if the pipeline could receive this instruction
82  // in the current cycle.
83  switch (SU->getInstr()->getOpcode()) {
84  default:
85  if (!ResourcesModel->canReserveResources(*SU->getInstr()))
86  return false;
87  case TargetOpcode::EXTRACT_SUBREG:
88  case TargetOpcode::INSERT_SUBREG:
89  case TargetOpcode::SUBREG_TO_REG:
90  case TargetOpcode::REG_SEQUENCE:
91  case TargetOpcode::IMPLICIT_DEF:
92  case TargetOpcode::COPY:
94  break;
95  }
96 
97  MachineFunction &MF = *SU->getInstr()->getParent()->getParent();
98  auto &QII = *MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
99 
100  // Now see if there are no other dependencies to instructions already
101  // in the packet.
102  for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
103  if (Packet[i]->Succs.size() == 0)
104  continue;
105 
106  // Enable .cur formation.
107  if (QII.mayBeCurLoad(*Packet[i]->getInstr()))
108  continue;
109 
110  for (SUnit::const_succ_iterator I = Packet[i]->Succs.begin(),
111  E = Packet[i]->Succs.end(); I != E; ++I) {
112  // Since we do not add pseudos to packets, might as well
113  // ignore order dependencies.
114  if (I->isCtrl())
115  continue;
116 
117  if (I->getSUnit() == SU)
118  return false;
119  }
120  }
121  return true;
122 }
123 
124 /// Keep track of available resources.
126  bool startNewCycle = false;
127  // Artificially reset state.
128  if (!SU) {
129  ResourcesModel->clearResources();
130  savePacket();
131  Packet.clear();
132  TotalPackets++;
133  return false;
134  }
135  // If this SU does not fit in the packet
136  // start a new one.
137  if (!isResourceAvailable(SU)) {
138  ResourcesModel->clearResources();
139  savePacket();
140  Packet.clear();
141  TotalPackets++;
142  startNewCycle = true;
143  }
144 
145  switch (SU->getInstr()->getOpcode()) {
146  default:
147  ResourcesModel->reserveResources(*SU->getInstr());
148  break;
149  case TargetOpcode::EXTRACT_SUBREG:
150  case TargetOpcode::INSERT_SUBREG:
151  case TargetOpcode::SUBREG_TO_REG:
152  case TargetOpcode::REG_SEQUENCE:
153  case TargetOpcode::IMPLICIT_DEF:
154  case TargetOpcode::KILL:
155  case TargetOpcode::CFI_INSTRUCTION:
157  case TargetOpcode::COPY:
159  break;
160  }
161  Packet.push_back(SU);
162 
163 #ifndef NDEBUG
164  DEBUG(dbgs() << "Packet[" << TotalPackets << "]:\n");
165  for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
166  DEBUG(dbgs() << "\t[" << i << "] SU(");
167  DEBUG(dbgs() << Packet[i]->NodeNum << ")\t");
168  DEBUG(Packet[i]->getInstr()->dump());
169  }
170 #endif
171 
172  // If packet is now full, reset the state so in the next cycle
173  // we start fresh.
174  if (Packet.size() >= SchedModel->getIssueWidth()) {
175  ResourcesModel->clearResources();
176  savePacket();
177  Packet.clear();
178  TotalPackets++;
179  startNewCycle = true;
180  }
181 
182  return startNewCycle;
183 }
184 
185 /// schedule - Called back from MachineScheduler::runOnMachineFunction
186 /// after setting up the current scheduling region. [RegionBegin, RegionEnd)
187 /// only includes instructions that have DAG nodes, not scheduling boundaries.
189  DEBUG(dbgs()
190  << "********** MI Converging Scheduling VLIW BB#" << BB->getNumber()
191  << " " << BB->getName()
192  << " in_func " << BB->getParent()->getFunction()->getName()
193  << " at loop depth " << MLI->getLoopDepth(BB)
194  << " \n");
195 
196  buildDAGWithRegPressure();
197 
198  SmallVector<SUnit*, 8> TopRoots, BotRoots;
199  findRootsAndBiasEdges(TopRoots, BotRoots);
200 
201  // Initialize the strategy before modifying the DAG.
202  SchedImpl->initialize(this);
203 
204  DEBUG(unsigned maxH = 0;
205  for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
206  if (SUnits[su].getHeight() > maxH)
207  maxH = SUnits[su].getHeight();
208  dbgs() << "Max Height " << maxH << "\n";);
209  DEBUG(unsigned maxD = 0;
210  for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
211  if (SUnits[su].getDepth() > maxD)
212  maxD = SUnits[su].getDepth();
213  dbgs() << "Max Depth " << maxD << "\n";);
214  DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
215  SUnits[su].dumpAll(this));
216 
217  initQueues(TopRoots, BotRoots);
218 
219  bool IsTopNode = false;
220  while (true) {
221  DEBUG(dbgs() << "** VLIWMachineScheduler::schedule picking next node\n");
222  SUnit *SU = SchedImpl->pickNode(IsTopNode);
223  if (!SU) break;
224 
225  if (!checkSchedLimit())
226  break;
227 
228  scheduleMI(SU, IsTopNode);
229 
230  updateQueues(SU, IsTopNode);
231 
232  // Notify the scheduling strategy after updating the DAG.
233  SchedImpl->schedNode(SU, IsTopNode);
234  }
235  assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
236 
237  placeDebugValues();
238 
239  DEBUG({
240  unsigned BBNum = begin()->getParent()->getNumber();
241  dbgs() << "*** Final schedule for BB#" << BBNum << " ***\n";
242  dumpSchedule();
243  dbgs() << '\n';
244  });
245 }
246 
248  DAG = static_cast<VLIWMachineScheduler*>(dag);
249  SchedModel = DAG->getSchedModel();
250 
251  Top.init(DAG, SchedModel);
252  Bot.init(DAG, SchedModel);
253 
254  // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
255  // are disabled, then these HazardRecs will be disabled.
256  const InstrItineraryData *Itin = DAG->getSchedModel()->getInstrItineraries();
257  const TargetSubtargetInfo &STI = DAG->MF.getSubtarget();
258  const TargetInstrInfo *TII = STI.getInstrInfo();
259  delete Top.HazardRec;
260  delete Bot.HazardRec;
261  Top.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
262  Bot.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
263 
264  delete Top.ResourceModel;
265  delete Bot.ResourceModel;
266  Top.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
267  Bot.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
268 
270  "-misched-topdown incompatible with -misched-bottomup");
271 }
272 
274  if (SU->isScheduled)
275  return;
276 
277  for (const SDep &PI : SU->Preds) {
278  unsigned PredReadyCycle = PI.getSUnit()->TopReadyCycle;
279  unsigned MinLatency = PI.getLatency();
280 #ifndef NDEBUG
281  Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency);
282 #endif
283  if (SU->TopReadyCycle < PredReadyCycle + MinLatency)
284  SU->TopReadyCycle = PredReadyCycle + MinLatency;
285  }
286  Top.releaseNode(SU, SU->TopReadyCycle);
287 }
288 
290  if (SU->isScheduled)
291  return;
292 
293  assert(SU->getInstr() && "Scheduled SUnit must have instr");
294 
295  for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
296  I != E; ++I) {
297  unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle;
298  unsigned MinLatency = I->getLatency();
299 #ifndef NDEBUG
300  Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency);
301 #endif
302  if (SU->BotReadyCycle < SuccReadyCycle + MinLatency)
303  SU->BotReadyCycle = SuccReadyCycle + MinLatency;
304  }
305  Bot.releaseNode(SU, SU->BotReadyCycle);
306 }
307 
308 /// Does this SU have a hazard within the current instruction group.
309 ///
310 /// The scheduler supports two modes of hazard recognition. The first is the
311 /// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
312 /// supports highly complicated in-order reservation tables
313 /// (ScoreboardHazardRecognizer) and arbitrary target-specific logic.
314 ///
315 /// The second is a streamlined mechanism that checks for hazards based on
316 /// simple counters that the scheduler itself maintains. It explicitly checks
317 /// for instruction dispatch limitations, including the number of micro-ops that
318 /// can dispatch per cycle.
319 ///
320 /// TODO: Also check whether the SU must start a new group.
321 bool ConvergingVLIWScheduler::VLIWSchedBoundary::checkHazard(SUnit *SU) {
322  if (HazardRec->isEnabled())
323  return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard;
324 
325  unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
326  if (IssueCount + uops > SchedModel->getIssueWidth())
327  return true;
328 
329  return false;
330 }
331 
332 void ConvergingVLIWScheduler::VLIWSchedBoundary::releaseNode(SUnit *SU,
333  unsigned ReadyCycle) {
334  if (ReadyCycle < MinReadyCycle)
335  MinReadyCycle = ReadyCycle;
336 
337  // Check for interlocks first. For the purpose of other heuristics, an
338  // instruction that cannot issue appears as if it's not in the ReadyQueue.
339  if (ReadyCycle > CurrCycle || checkHazard(SU))
340 
341  Pending.push(SU);
342  else
343  Available.push(SU);
344 }
345 
346 /// Move the boundary of scheduled code by one cycle.
347 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpCycle() {
348  unsigned Width = SchedModel->getIssueWidth();
349  IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width;
350 
351  assert(MinReadyCycle < std::numeric_limits<unsigned>::max() &&
352  "MinReadyCycle uninitialized");
353  unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle);
354 
355  if (!HazardRec->isEnabled()) {
356  // Bypass HazardRec virtual calls.
357  CurrCycle = NextCycle;
358  } else {
359  // Bypass getHazardType calls in case of long latency.
360  for (; CurrCycle != NextCycle; ++CurrCycle) {
361  if (isTop())
362  HazardRec->AdvanceCycle();
363  else
364  HazardRec->RecedeCycle();
365  }
366  }
367  CheckPending = true;
368 
369  DEBUG(dbgs() << "*** Next cycle " << Available.getName() << " cycle "
370  << CurrCycle << '\n');
371 }
372 
373 /// Move the boundary of scheduled code by one SUnit.
374 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpNode(SUnit *SU) {
375  bool startNewCycle = false;
376 
377  // Update the reservation table.
378  if (HazardRec->isEnabled()) {
379  if (!isTop() && SU->isCall) {
380  // Calls are scheduled with their preceding instructions. For bottom-up
381  // scheduling, clear the pipeline state before emitting.
382  HazardRec->Reset();
383  }
384  HazardRec->EmitInstruction(SU);
385  }
386 
387  // Update DFA model.
388  startNewCycle = ResourceModel->reserveResources(SU);
389 
390  // Check the instruction group dispatch limit.
391  // TODO: Check if this SU must end a dispatch group.
392  IssueCount += SchedModel->getNumMicroOps(SU->getInstr());
393  if (startNewCycle) {
394  DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n');
395  bumpCycle();
396  }
397  else
398  DEBUG(dbgs() << "*** IssueCount " << IssueCount
399  << " at cycle " << CurrCycle << '\n');
400 }
401 
402 /// Release pending ready nodes in to the available queue. This makes them
403 /// visible to heuristics.
404 void ConvergingVLIWScheduler::VLIWSchedBoundary::releasePending() {
405  // If the available queue is empty, it is safe to reset MinReadyCycle.
406  if (Available.empty())
407  MinReadyCycle = std::numeric_limits<unsigned>::max();
408 
409  // Check to see if any of the pending instructions are ready to issue. If
410  // so, add them to the available queue.
411  for (unsigned i = 0, e = Pending.size(); i != e; ++i) {
412  SUnit *SU = *(Pending.begin()+i);
413  unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
414 
415  if (ReadyCycle < MinReadyCycle)
416  MinReadyCycle = ReadyCycle;
417 
418  if (ReadyCycle > CurrCycle)
419  continue;
420 
421  if (checkHazard(SU))
422  continue;
423 
424  Available.push(SU);
425  Pending.remove(Pending.begin()+i);
426  --i; --e;
427  }
428  CheckPending = false;
429 }
430 
431 /// Remove SU from the ready set for this boundary.
432 void ConvergingVLIWScheduler::VLIWSchedBoundary::removeReady(SUnit *SU) {
433  if (Available.isInQueue(SU))
434  Available.remove(Available.find(SU));
435  else {
436  assert(Pending.isInQueue(SU) && "bad ready count");
437  Pending.remove(Pending.find(SU));
438  }
439 }
440 
441 /// If this queue only has one ready candidate, return it. As a side effect,
442 /// advance the cycle until at least one node is ready. If multiple instructions
443 /// are ready, return NULL.
444 SUnit *ConvergingVLIWScheduler::VLIWSchedBoundary::pickOnlyChoice() {
445  if (CheckPending)
446  releasePending();
447 
448  for (unsigned i = 0; Available.empty(); ++i) {
449  assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
450  "permanent hazard"); (void)i;
451  ResourceModel->reserveResources(nullptr);
452  bumpCycle();
453  releasePending();
454  }
455  if (Available.size() == 1)
456  return *Available.begin();
457  return nullptr;
458 }
459 
460 #ifndef NDEBUG
462  const ReadyQueue &Q, SUnit *SU, int Cost, PressureChange P) {
463  dbgs() << Label << " " << Q.getName() << " ";
464  if (P.isValid())
465  dbgs() << DAG->TRI->getRegPressureSetName(P.getPSet()) << ":"
466  << P.getUnitInc() << " ";
467  else
468  dbgs() << " ";
469  dbgs() << "cost(" << Cost << ")\t";
470  SU->dump(DAG);
471 }
472 
473 // Very detailed queue dump, to be used with higher verbosity levels.
475  const RegPressureTracker &RPTracker, SchedCandidate &Candidate,
476  ReadyQueue &Q) {
477  RegPressureTracker &TempTracker = const_cast<RegPressureTracker &>(RPTracker);
478 
479  dbgs() << ">>> " << Q.getName() << "\n";
480  for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
481  RegPressureDelta RPDelta;
482  TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
483  DAG->getRegionCriticalPSets(),
484  DAG->getRegPressure().MaxSetPressure);
485  std::stringstream dbgstr;
486  dbgstr << "SU(" << std::setw(3) << (*I)->NodeNum << ")";
487  dbgs() << dbgstr.str();
488  SchedulingCost(Q, *I, Candidate, RPDelta, true);
489  dbgs() << "\t";
490  (*I)->getInstr()->dump();
491  }
492  dbgs() << "\n";
493 }
494 #endif
495 
496 /// isSingleUnscheduledPred - If SU2 is the only unscheduled predecessor
497 /// of SU, return true (we may have duplicates)
498 static inline bool isSingleUnscheduledPred(SUnit *SU, SUnit *SU2) {
499  if (SU->NumPredsLeft == 0)
500  return false;
501 
502  for (auto &Pred : SU->Preds) {
503  // We found an available, but not scheduled, predecessor.
504  if (!Pred.getSUnit()->isScheduled && (Pred.getSUnit() != SU2))
505  return false;
506  }
507 
508  return true;
509 }
510 
511 /// isSingleUnscheduledSucc - If SU2 is the only unscheduled successor
512 /// of SU, return true (we may have duplicates)
513 static inline bool isSingleUnscheduledSucc(SUnit *SU, SUnit *SU2) {
514  if (SU->NumSuccsLeft == 0)
515  return false;
516 
517  for (auto &Succ : SU->Succs) {
518  // We found an available, but not scheduled, successor.
519  if (!Succ.getSUnit()->isScheduled && (Succ.getSUnit() != SU2))
520  return false;
521  }
522  return true;
523 }
524 
525 // Constants used to denote relative importance of
526 // heuristic components for cost computation.
527 static const unsigned PriorityOne = 200;
528 static const unsigned PriorityTwo = 50;
529 static const unsigned PriorityThree = 75;
530 static const unsigned ScaleTwo = 10;
531 static const unsigned FactorOne = 2;
532 
533 /// Single point to compute overall scheduling cost.
534 /// TODO: More heuristics will be used soon.
536  SchedCandidate &Candidate,
537  RegPressureDelta &Delta,
538  bool verbose) {
539  // Initial trivial priority.
540  int ResCount = 1;
541 
542  // Do not waste time on a node that is already scheduled.
543  if (!SU || SU->isScheduled)
544  return ResCount;
545 
546  MachineInstr &Instr = *SU->getInstr();
547 
548  DEBUG(if (verbose) dbgs() << ((Q.getID() == TopQID) ? "(top|" : "(bot|"));
549  // Forced priority is high.
550  if (SU->isScheduleHigh) {
551  ResCount += PriorityOne;
552  DEBUG(dbgs() << "H|");
553  }
554 
555  // Critical path first.
556  if (Q.getID() == TopQID) {
557  ResCount += (SU->getHeight() * ScaleTwo);
558 
559  DEBUG(if (verbose) {
560  std::stringstream dbgstr;
561  dbgstr << "h" << std::setw(3) << SU->getHeight() << "|";
562  dbgs() << dbgstr.str();
563  });
564 
565  // If resources are available for it, multiply the
566  // chance of scheduling.
567  if (Top.ResourceModel->isResourceAvailable(SU)) {
568  ResCount <<= FactorOne;
569  ResCount += PriorityThree;
570  DEBUG(if (verbose) dbgs() << "A|");
571  } else
572  DEBUG(if (verbose) dbgs() << " |");
573  } else {
574  ResCount += (SU->getDepth() * ScaleTwo);
575 
576  DEBUG(if (verbose) {
577  std::stringstream dbgstr;
578  dbgstr << "d" << std::setw(3) << SU->getDepth() << "|";
579  dbgs() << dbgstr.str();
580  });
581 
582  // If resources are available for it, multiply the
583  // chance of scheduling.
584  if (Bot.ResourceModel->isResourceAvailable(SU)) {
585  ResCount <<= FactorOne;
586  ResCount += PriorityThree;
587  DEBUG(if (verbose) dbgs() << "A|");
588  } else
589  DEBUG(if (verbose) dbgs() << " |");
590  }
591 
592  unsigned NumNodesBlocking = 0;
593  if (Q.getID() == TopQID) {
594  // How many SUs does it block from scheduling?
595  // Look at all of the successors of this node.
596  // Count the number of nodes that
597  // this node is the sole unscheduled node for.
598  for (const SDep &SI : SU->Succs)
599  if (isSingleUnscheduledPred(SI.getSUnit(), SU))
600  ++NumNodesBlocking;
601  } else {
602  // How many unscheduled predecessors block this node?
603  for (const SDep &PI : SU->Preds)
604  if (isSingleUnscheduledSucc(PI.getSUnit(), SU))
605  ++NumNodesBlocking;
606  }
607  ResCount += (NumNodesBlocking * ScaleTwo);
608 
609  DEBUG(if (verbose) {
610  std::stringstream dbgstr;
611  dbgstr << "blk " << std::setw(2) << NumNodesBlocking << ")|";
612  dbgs() << dbgstr.str();
613  });
614 
615  // Factor in reg pressure as a heuristic.
616  if (!IgnoreBBRegPressure) {
617  // Decrease priority by the amount that register pressure exceeds the limit.
618  ResCount -= (Delta.Excess.getUnitInc()*PriorityOne);
619  // Decrease priority if register pressure exceeds the limit.
620  ResCount -= (Delta.CriticalMax.getUnitInc()*PriorityOne);
621  // Decrease priority slightly if register pressure would increase over the
622  // current maximum.
623  ResCount -= (Delta.CurrentMax.getUnitInc()*PriorityTwo);
624  DEBUG(if (verbose) {
625  dbgs() << "RP " << Delta.Excess.getUnitInc() << "/"
626  << Delta.CriticalMax.getUnitInc() <<"/"
627  << Delta.CurrentMax.getUnitInc() << ")|";
628  });
629  }
630 
631  // Give a little extra priority to a .cur instruction if there is a resource
632  // available for it.
633  auto &QST = DAG->MF.getSubtarget<HexagonSubtarget>();
634  auto &QII = *QST.getInstrInfo();
635  if (SU->isInstr() && QII.mayBeCurLoad(*SU->getInstr())) {
636  if (Q.getID() == TopQID && Top.ResourceModel->isResourceAvailable(SU)) {
637  ResCount += PriorityTwo;
638  DEBUG(if (verbose) dbgs() << "C|");
639  } else if (Q.getID() == BotQID &&
640  Bot.ResourceModel->isResourceAvailable(SU)) {
641  ResCount += PriorityTwo;
642  DEBUG(if (verbose) dbgs() << "C|");
643  }
644  }
645 
646  // Give preference to a zero latency instruction if the dependent
647  // instruction is in the current packet.
648  if (Q.getID() == TopQID) {
649  for (const SDep &PI : SU->Preds) {
650  if (!PI.getSUnit()->getInstr()->isPseudo() && PI.isAssignedRegDep() &&
651  PI.getLatency() == 0 &&
652  Top.ResourceModel->isInPacket(PI.getSUnit())) {
653  ResCount += PriorityThree;
654  DEBUG(if (verbose) dbgs() << "Z|");
655  }
656  }
657  } else {
658  for (const SDep &SI : SU->Succs) {
659  if (!SI.getSUnit()->getInstr()->isPseudo() && SI.isAssignedRegDep() &&
660  SI.getLatency() == 0 &&
661  Bot.ResourceModel->isInPacket(SI.getSUnit())) {
662  ResCount += PriorityThree;
663  DEBUG(if (verbose) dbgs() << "Z|");
664  }
665  }
666  }
667 
668  // Give less preference to an instruction that will cause a stall with
669  // an instruction in the previous packet.
670  if (QII.isHVXVec(Instr)) {
671  // Check for stalls in the previous packet.
672  if (Q.getID() == TopQID) {
673  for (auto J : Top.ResourceModel->OldPacket)
674  if (QII.producesStall(*J->getInstr(), Instr))
675  ResCount -= PriorityOne;
676  } else {
677  for (auto J : Bot.ResourceModel->OldPacket)
678  if (QII.producesStall(Instr, *J->getInstr()))
679  ResCount -= PriorityOne;
680  }
681  }
682 
683  // If the instruction has a non-zero latency dependence with an instruction in
684  // the current packet, then it should not be scheduled yet. The case occurs
685  // when the dependent instruction is scheduled in a new packet, so the
686  // scheduler updates the current cycle and pending instructions become
687  // available.
688  if (CheckEarlyAvail) {
689  if (Q.getID() == TopQID) {
690  for (const auto &PI : SU->Preds) {
691  if (PI.getLatency() > 0 &&
692  Top.ResourceModel->isInPacket(PI.getSUnit())) {
693  ResCount -= PriorityOne;
694  DEBUG(if (verbose) dbgs() << "D|");
695  }
696  }
697  } else {
698  for (const auto &SI : SU->Succs) {
699  if (SI.getLatency() > 0 &&
700  Bot.ResourceModel->isInPacket(SI.getSUnit())) {
701  ResCount -= PriorityOne;
702  DEBUG(if (verbose) dbgs() << "D|");
703  }
704  }
705  }
706  }
707 
708  DEBUG(if (verbose) {
709  std::stringstream dbgstr;
710  dbgstr << "Total " << std::setw(4) << ResCount << ")";
711  dbgs() << dbgstr.str();
712  });
713 
714  return ResCount;
715 }
716 
717 /// Pick the best candidate from the top queue.
718 ///
719 /// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
720 /// DAG building. To adjust for the current scheduling location we need to
721 /// maintain the number of vreg uses remaining to be top-scheduled.
722 ConvergingVLIWScheduler::CandResult ConvergingVLIWScheduler::
724  SchedCandidate &Candidate) {
726  readyQueueVerboseDump(RPTracker, Candidate, Q);
727  else Q.dump(););
728 
729  // getMaxPressureDelta temporarily modifies the tracker.
730  RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
731 
732  // BestSU remains NULL if no top candidates beat the best existing candidate.
733  CandResult FoundCandidate = NoCand;
734  for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
735  RegPressureDelta RPDelta;
736  TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
737  DAG->getRegionCriticalPSets(),
738  DAG->getRegPressure().MaxSetPressure);
739 
740  int CurrentCost = SchedulingCost(Q, *I, Candidate, RPDelta, false);
741 
742  // Initialize the candidate if needed.
743  if (!Candidate.SU) {
744  DEBUG(traceCandidate("DCAND", Q, *I, CurrentCost));
745  Candidate.SU = *I;
746  Candidate.RPDelta = RPDelta;
747  Candidate.SCost = CurrentCost;
748  FoundCandidate = NodeOrder;
749  continue;
750  }
751 
752  // Best cost.
753  if (CurrentCost > Candidate.SCost) {
754  DEBUG(traceCandidate("CCAND", Q, *I, CurrentCost));
755  Candidate.SU = *I;
756  Candidate.RPDelta = RPDelta;
757  Candidate.SCost = CurrentCost;
758  FoundCandidate = BestCost;
759  continue;
760  }
761 
762  // Tie breaker using Timing Class.
763  if (!DisableTCTie) {
764  auto &QST = DAG->MF.getSubtarget<HexagonSubtarget>();
765  auto &QII = *QST.getInstrInfo();
766 
767  const MachineInstr *MI = (*I)->getInstr();
768  const MachineInstr *CandI = Candidate.SU->getInstr();
769  const InstrItineraryData *InstrItins = QST.getInstrItineraryData();
770 
771  unsigned InstrLatency = QII.getInstrTimingClassLatency(InstrItins, *MI);
772  unsigned CandLatency = QII.getInstrTimingClassLatency(InstrItins, *CandI);
773  DEBUG(dbgs() << "TC Tie Breaker Cand: "
774  << CandLatency << " Instr:" << InstrLatency << "\n"
775  << *MI << *CandI << "\n");
776  if (Q.getID() == TopQID && CurrentCost == Candidate.SCost) {
777  if (InstrLatency < CandLatency && TopUseShorterTie) {
778  Candidate.SU = *I;
779  Candidate.RPDelta = RPDelta;
780  Candidate.SCost = CurrentCost;
781  FoundCandidate = BestCost;
782  DEBUG(dbgs() << "Used top shorter tie breaker\n");
783  continue;
784  } else if (InstrLatency > CandLatency && !TopUseShorterTie) {
785  Candidate.SU = *I;
786  Candidate.RPDelta = RPDelta;
787  Candidate.SCost = CurrentCost;
788  FoundCandidate = BestCost;
789  DEBUG(dbgs() << "Used top longer tie breaker\n");
790  continue;
791  }
792  } else if (Q.getID() == BotQID && CurrentCost == Candidate.SCost) {
793  if (InstrLatency < CandLatency && BotUseShorterTie) {
794  Candidate.SU = *I;
795  Candidate.RPDelta = RPDelta;
796  Candidate.SCost = CurrentCost;
797  FoundCandidate = BestCost;
798  DEBUG(dbgs() << "Used Bot shorter tie breaker\n");
799  continue;
800  } else if (InstrLatency > CandLatency && !BotUseShorterTie) {
801  Candidate.SU = *I;
802  Candidate.RPDelta = RPDelta;
803  Candidate.SCost = CurrentCost;
804  FoundCandidate = BestCost;
805  DEBUG(dbgs() << "Used Bot longer tie breaker\n");
806  continue;
807  }
808  }
809  }
810 
811  if (CurrentCost == Candidate.SCost) {
812  if ((Q.getID() == TopQID &&
813  (*I)->Succs.size() > Candidate.SU->Succs.size()) ||
814  (Q.getID() == BotQID &&
815  (*I)->Preds.size() < Candidate.SU->Preds.size())) {
816  DEBUG(traceCandidate("SPCAND", Q, *I, CurrentCost));
817  Candidate.SU = *I;
818  Candidate.RPDelta = RPDelta;
819  Candidate.SCost = CurrentCost;
820  FoundCandidate = BestCost;
821  continue;
822  }
823  }
824 
825  // Fall through to original instruction order.
826  // Only consider node order if Candidate was chosen from this Q.
827  if (FoundCandidate == NoCand)
828  continue;
829  }
830  return FoundCandidate;
831 }
832 
833 /// Pick the best candidate node from either the top or bottom queue.
835  // Schedule as far as possible in the direction of no choice. This is most
836  // efficient, but also provides the best heuristics for CriticalPSets.
837  if (SUnit *SU = Bot.pickOnlyChoice()) {
838  DEBUG(dbgs() << "Picked only Bottom\n");
839  IsTopNode = false;
840  return SU;
841  }
842  if (SUnit *SU = Top.pickOnlyChoice()) {
843  DEBUG(dbgs() << "Picked only Top\n");
844  IsTopNode = true;
845  return SU;
846  }
847  SchedCandidate BotCand;
848  // Prefer bottom scheduling when heuristics are silent.
849  CandResult BotResult = pickNodeFromQueue(Bot.Available,
850  DAG->getBotRPTracker(), BotCand);
851  assert(BotResult != NoCand && "failed to find the first candidate");
852 
853  // If either Q has a single candidate that provides the least increase in
854  // Excess pressure, we can immediately schedule from that Q.
855  //
856  // RegionCriticalPSets summarizes the pressure within the scheduled region and
857  // affects picking from either Q. If scheduling in one direction must
858  // increase pressure for one of the excess PSets, then schedule in that
859  // direction first to provide more freedom in the other direction.
860  if (BotResult == SingleExcess || BotResult == SingleCritical) {
861  DEBUG(dbgs() << "Prefered Bottom Node\n");
862  IsTopNode = false;
863  return BotCand.SU;
864  }
865  // Check if the top Q has a better candidate.
866  SchedCandidate TopCand;
867  CandResult TopResult = pickNodeFromQueue(Top.Available,
868  DAG->getTopRPTracker(), TopCand);
869  assert(TopResult != NoCand && "failed to find the first candidate");
870 
871  if (TopResult == SingleExcess || TopResult == SingleCritical) {
872  DEBUG(dbgs() << "Prefered Top Node\n");
873  IsTopNode = true;
874  return TopCand.SU;
875  }
876  // If either Q has a single candidate that minimizes pressure above the
877  // original region's pressure pick it.
878  if (BotResult == SingleMax) {
879  DEBUG(dbgs() << "Prefered Bottom Node SingleMax\n");
880  IsTopNode = false;
881  return BotCand.SU;
882  }
883  if (TopResult == SingleMax) {
884  DEBUG(dbgs() << "Prefered Top Node SingleMax\n");
885  IsTopNode = true;
886  return TopCand.SU;
887  }
888  if (TopCand.SCost > BotCand.SCost) {
889  DEBUG(dbgs() << "Prefered Top Node Cost\n");
890  IsTopNode = true;
891  return TopCand.SU;
892  }
893  // Otherwise prefer the bottom candidate in node order.
894  DEBUG(dbgs() << "Prefered Bottom in Node order\n");
895  IsTopNode = false;
896  return BotCand.SU;
897 }
898 
899 /// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
901  if (DAG->top() == DAG->bottom()) {
902  assert(Top.Available.empty() && Top.Pending.empty() &&
903  Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
904  return nullptr;
905  }
906  SUnit *SU;
907  if (ForceTopDown) {
908  SU = Top.pickOnlyChoice();
909  if (!SU) {
910  SchedCandidate TopCand;
911  CandResult TopResult =
912  pickNodeFromQueue(Top.Available, DAG->getTopRPTracker(), TopCand);
913  assert(TopResult != NoCand && "failed to find the first candidate");
914  (void)TopResult;
915  SU = TopCand.SU;
916  }
917  IsTopNode = true;
918  } else if (ForceBottomUp) {
919  SU = Bot.pickOnlyChoice();
920  if (!SU) {
921  SchedCandidate BotCand;
922  CandResult BotResult =
923  pickNodeFromQueue(Bot.Available, DAG->getBotRPTracker(), BotCand);
924  assert(BotResult != NoCand && "failed to find the first candidate");
925  (void)BotResult;
926  SU = BotCand.SU;
927  }
928  IsTopNode = false;
929  } else {
930  SU = pickNodeBidrectional(IsTopNode);
931  }
932  if (SU->isTopReady())
933  Top.removeReady(SU);
934  if (SU->isBottomReady())
935  Bot.removeReady(SU);
936 
937  DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom")
938  << " Scheduling Instruction in cycle "
939  << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << '\n';
940  SU->dump(DAG));
941  return SU;
942 }
943 
944 /// Update the scheduler's state after scheduling a node. This is the same node
945 /// that was just returned by pickNode(). However, VLIWMachineScheduler needs
946 /// to update it's state based on the current cycle before MachineSchedStrategy
947 /// does.
948 void ConvergingVLIWScheduler::schedNode(SUnit *SU, bool IsTopNode) {
949  if (IsTopNode) {
950  SU->TopReadyCycle = Top.CurrCycle;
951  Top.bumpNode(SU);
952  } else {
953  SU->BotReadyCycle = Bot.CurrCycle;
954  Bot.bumpNode(SU);
955  }
956 }
VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM)
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
void schedule() override
Schedule - This is called back from ScheduleDAGInstrs::Run() when it&#39;s time to do some work...
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:235
static bool isSingleUnscheduledPred(SUnit *SU, SUnit *SU2)
isSingleUnscheduledPred - If SU2 is the only unscheduled predecessor of SU, return true (we may have ...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Extend the standard ScheduleDAGMI to provide more context and override the top-level schedule() drive...
static cl::opt< unsigned > SchedDebugVerboseLevel("misched-verbose-level", cl::Hidden, cl::ZeroOrMore, cl::init(1))
void readyQueueVerboseDump(const RegPressureTracker &RPTracker, SchedCandidate &Candidate, ReadyQueue &Q)
int SchedulingCost(ReadyQueue &Q, SUnit *SU, SchedCandidate &Candidate, RegPressureDelta &Delta, bool verbose)
Single point to compute overall scheduling cost.
void dump(const ScheduleDAG *G) const
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
Definition: ScheduleDAG.h:403
CandResult pickNodeFromQueue(ReadyQueue &Q, const RegPressureTracker &RPTracker, SchedCandidate &Candidate)
Pick the best candidate from the top queue.
static cl::opt< bool > TopUseShorterTie("top-use-shorter-tie", cl::Hidden, cl::ZeroOrMore, cl::init(false))
void init(const MCSchedModel &sm, const TargetSubtargetInfo *sti, const TargetInstrInfo *tii)
Initialize the machine model for instruction scheduling.
std::vector< SUnit * > OldPacket
Save the last formed packet.
void savePacket()
Save the last formed packet.
bool isBottomReady() const
Definition: ScheduleDAG.h:454
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
Definition: ScheduleDAG.h:212
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
unsigned BotReadyCycle
Cycle relative to end when node is ready.
Definition: ScheduleDAG.h:305
SmallVectorImpl< SDep >::iterator succ_iterator
Definition: ScheduleDAG.h:265
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:261
bool isScheduled
True once scheduled.
Definition: ScheduleDAG.h:289
unsigned getID() const
SUnit * pickNodeBidrectional(bool &IsTopNode)
Pick the best candidate node from either the top or bottom queue.
static const unsigned ScaleTwo
unsigned getLatency() const
Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...
Definition: ScheduleDAG.h:143
unsigned NumSuccsLeft
of succs not scheduled.
Definition: ScheduleDAG.h:274
const HexagonInstrInfo * TII
static cl::opt< bool > IgnoreBBRegPressure("ignore-bb-reg-pressure", cl::Hidden, cl::ZeroOrMore, cl::init(false))
SUnit * pickNode(bool &IsTopNode) override
Pick the best node to balance the schedule. Implements MachineSchedStrategy.
StringRef getName() const
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:290
INLINEASM - Represents an inline asm block.
Definition: ISDOpcodes.h:634
unsigned TopReadyCycle
Cycle relative to start when node is ready.
Definition: ScheduleDAG.h:304
unsigned getNumMicroOps(const MachineInstr *MI, const MCSchedClassDesc *SC=nullptr) const
Return the number of issue slots required for this MI.
static cl::opt< bool > BotUseShorterTie("bot-use-shorter-tie", cl::Hidden, cl::ZeroOrMore, cl::init(false))
void releaseTopNode(SUnit *SU) override
When all predecessor dependencies have been resolved, free this node for top-down scheduling...
Itinerary data supplied by a subtarget to be used by a target.
unsigned NumPredsLeft
of preds not scheduled.
Definition: ScheduleDAG.h:273
bool isTopReady() const
Definition: ScheduleDAG.h:451
virtual const TargetInstrInfo * getInstrInfo() const
SUnit * getSUnit() const
Definition: ScheduleDAG.h:490
std::vector< SUnit * >::iterator iterator
TargetInstrInfo - Interface to description of machine instruction set.
Scheduling dependency.
Definition: ScheduleDAG.h:50
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
bool isCall
Is a function call.
Definition: ScheduleDAG.h:280
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:378
Helpers for implementing custom MachineSchedStrategy classes.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
bool isPseudo(QueryType Type=IgnoreBundle) const
Return true if this is a pseudo instruction that doesn&#39;t correspond to a real machine instruction...
Definition: MachineInstr.h:450
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Track the current register pressure at some position in the instruction stream, and remember the high...
bool isResourceAvailable(SUnit *SU)
Check if scheduling of this SU is possible in the current packet.
static const unsigned FactorOne
EH_LABEL - Represents a label in mid basic block used to track locations needed for debug and excepti...
Definition: ISDOpcodes.h:639
static bool isSingleUnscheduledSucc(SUnit *SU, SUnit *SU2)
isSingleUnscheduledSucc - If SU2 is the only unscheduled successor of SU, return true (we may have du...
bool isScheduleHigh
True if preferable to schedule high.
Definition: ScheduleDAG.h:290
void schedNode(SUnit *SU, bool IsTopNode) override
Update the scheduler&#39;s state after scheduling a node.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
bool canReserveResources(const MCInstrDesc *MID)
void getMaxPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit)
Find the pressure set with the most change beyond its pressure limit after traversing this instructio...
void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU, int Cost, PressureChange P=PressureChange())
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
PressureChange CriticalMax
SmallVectorImpl< SDep >::const_iterator const_succ_iterator
Definition: ScheduleDAG.h:267
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:139
TargetSubtargetInfo - Generic base class for all target subtargets.
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
Definition: ScheduleDAG.h:411
Representation of each machine instruction.
Definition: MachineInstr.h:59
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
static const unsigned PriorityOne
cl::opt< bool > ForceBottomUp
#define I(x, y, z)
Definition: MD5.cpp:58
Capture a change in pressure for a single pressure set.
bool reserveResources(SUnit *SU)
Keep track of available resources.
static const unsigned PriorityThree
void releaseBottomNode(SUnit *SU) override
When all successor dependencies have been resolved, free this node for bottom-up scheduling.
Store the effects of a change in pressure on things that MI scheduler cares about.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static cl::opt< bool > CheckEarlyAvail("check-early-avail", cl::Hidden, cl::ZeroOrMore, cl::init(true))
static const unsigned PriorityTwo
const HexagonInstrInfo * getInstrInfo() const override
virtual ScheduleHazardRecognizer * CreateTargetMIHazardRecognizer(const InstrItineraryData *, const ScheduleDAG *DAG) const
Allocate and return a hazard recognizer to use for this target when scheduling the machine instructio...
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:262
static cl::opt< bool > DisableTCTie("disable-tc-tie", cl::Hidden, cl::ZeroOrMore, cl::init(false))
#define DEBUG(X)
Definition: Debug.h:118
IRTranslator LLVM IR MI
unsigned getPSet() const
unsigned getIssueWidth() const
Maximum number of micro-ops that may be scheduled per cycle.
bool isInstr() const
Returns true if this SUnit refers to a machine instruction as opposed to an SDNode.
Definition: ScheduleDAG.h:367
const MCSchedModel & getSchedModel() const
Get the machine model for this subtarget&#39;s CPU.
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:247
cl::opt< bool > ForceTopDown
void reserveResources(const MCInstrDesc *MID)
void initialize(ScheduleDAGMI *dag) override
Initialize the strategy after building the DAG for a new region.