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