LLVM  9.0.0svn
ResourcePriorityQueue.cpp
Go to the documentation of this file.
1 //===- ResourcePriorityQueue.cpp - A DFA-oriented priority queue -*- C++ -*-==//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the ResourcePriorityQueue class, which is a
10 // SchedulingPriorityQueue that prioritizes instructions using DFA state to
11 // reduce the length of the critical path through the basic block
12 // on VLIW platforms.
13 // The scheduler is basically a top-down adaptable list scheduler with DFA
14 // resource tracking added to the cost function.
15 // DFA is queried as a state machine to model "packets/bundles" during
16 // schedule. Currently packets/bundles are discarded at the end of
17 // scheduling, affecting only order of instructions.
18 //
19 //===----------------------------------------------------------------------===//
20 
27 #include "llvm/Support/Debug.h"
30 
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "scheduler"
34 
35 static cl::opt<bool> DisableDFASched("disable-dfa-sched", cl::Hidden,
36  cl::ZeroOrMore, cl::init(false),
37  cl::desc("Disable use of DFA during scheduling"));
38 
40  "dfa-sched-reg-pressure-threshold", cl::Hidden, cl::ZeroOrMore, cl::init(5),
41  cl::desc("Track reg pressure and switch priority to in-depth"));
42 
44  : Picker(this), InstrItins(IS->MF->getSubtarget().getInstrItineraryData()) {
45  const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
46  TRI = STI.getRegisterInfo();
47  TLI = IS->TLI;
48  TII = STI.getInstrInfo();
49  ResourcesModel.reset(TII->CreateTargetScheduleState(STI));
50  // This hard requirement could be relaxed, but for now
51  // do not let it proceed.
52  assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
53 
54  unsigned NumRC = TRI->getNumRegClasses();
55  RegLimit.resize(NumRC);
56  RegPressure.resize(NumRC);
57  std::fill(RegLimit.begin(), RegLimit.end(), 0);
58  std::fill(RegPressure.begin(), RegPressure.end(), 0);
59  for (const TargetRegisterClass *RC : TRI->regclasses())
60  RegLimit[RC->getID()] = TRI->getRegPressureLimit(RC, *IS->MF);
61 
62  ParallelLiveRanges = 0;
63  HorizontalVerticalBalance = 0;
64 }
65 
66 unsigned
67 ResourcePriorityQueue::numberRCValPredInSU(SUnit *SU, unsigned RCId) {
68  unsigned NumberDeps = 0;
69  for (SDep &Pred : SU->Preds) {
70  if (Pred.isCtrl())
71  continue;
72 
73  SUnit *PredSU = Pred.getSUnit();
74  const SDNode *ScegN = PredSU->getNode();
75 
76  if (!ScegN)
77  continue;
78 
79  // If value is passed to CopyToReg, it is probably
80  // live outside BB.
81  switch (ScegN->getOpcode()) {
82  default: break;
83  case ISD::TokenFactor: break;
84  case ISD::CopyFromReg: NumberDeps++; break;
85  case ISD::CopyToReg: break;
86  case ISD::INLINEASM: break;
87  case ISD::INLINEASM_BR: break;
88  }
89  if (!ScegN->isMachineOpcode())
90  continue;
91 
92  for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) {
93  MVT VT = ScegN->getSimpleValueType(i);
94  if (TLI->isTypeLegal(VT)
95  && (TLI->getRegClassFor(VT)->getID() == RCId)) {
96  NumberDeps++;
97  break;
98  }
99  }
100  }
101  return NumberDeps;
102 }
103 
104 unsigned ResourcePriorityQueue::numberRCValSuccInSU(SUnit *SU,
105  unsigned RCId) {
106  unsigned NumberDeps = 0;
107  for (const SDep &Succ : SU->Succs) {
108  if (Succ.isCtrl())
109  continue;
110 
111  SUnit *SuccSU = Succ.getSUnit();
112  const SDNode *ScegN = SuccSU->getNode();
113  if (!ScegN)
114  continue;
115 
116  // If value is passed to CopyToReg, it is probably
117  // live outside BB.
118  switch (ScegN->getOpcode()) {
119  default: break;
120  case ISD::TokenFactor: break;
121  case ISD::CopyFromReg: break;
122  case ISD::CopyToReg: NumberDeps++; break;
123  case ISD::INLINEASM: break;
124  case ISD::INLINEASM_BR: break;
125  }
126  if (!ScegN->isMachineOpcode())
127  continue;
128 
129  for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) {
130  const SDValue &Op = ScegN->getOperand(i);
131  MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
132  if (TLI->isTypeLegal(VT)
133  && (TLI->getRegClassFor(VT)->getID() == RCId)) {
134  NumberDeps++;
135  break;
136  }
137  }
138  }
139  return NumberDeps;
140 }
141 
142 static unsigned numberCtrlDepsInSU(SUnit *SU) {
143  unsigned NumberDeps = 0;
144  for (const SDep &Succ : SU->Succs)
145  if (Succ.isCtrl())
146  NumberDeps++;
147 
148  return NumberDeps;
149 }
150 
151 static unsigned numberCtrlPredInSU(SUnit *SU) {
152  unsigned NumberDeps = 0;
153  for (SDep &Pred : SU->Preds)
154  if (Pred.isCtrl())
155  NumberDeps++;
156 
157  return NumberDeps;
158 }
159 
160 ///
161 /// Initialize nodes.
162 ///
163 void ResourcePriorityQueue::initNodes(std::vector<SUnit> &sunits) {
164  SUnits = &sunits;
165  NumNodesSolelyBlocking.resize(SUnits->size(), 0);
166 
167  for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
168  SUnit *SU = &(*SUnits)[i];
169  initNumRegDefsLeft(SU);
170  SU->NodeQueueId = 0;
171  }
172 }
173 
174 /// This heuristic is used if DFA scheduling is not desired
175 /// for some VLIW platform.
176 bool resource_sort::operator()(const SUnit *LHS, const SUnit *RHS) const {
177  // The isScheduleHigh flag allows nodes with wraparound dependencies that
178  // cannot easily be modeled as edges with latencies to be scheduled as
179  // soon as possible in a top-down schedule.
180  if (LHS->isScheduleHigh && !RHS->isScheduleHigh)
181  return false;
182 
183  if (!LHS->isScheduleHigh && RHS->isScheduleHigh)
184  return true;
185 
186  unsigned LHSNum = LHS->NodeNum;
187  unsigned RHSNum = RHS->NodeNum;
188 
189  // The most important heuristic is scheduling the critical path.
190  unsigned LHSLatency = PQ->getLatency(LHSNum);
191  unsigned RHSLatency = PQ->getLatency(RHSNum);
192  if (LHSLatency < RHSLatency) return true;
193  if (LHSLatency > RHSLatency) return false;
194 
195  // After that, if two nodes have identical latencies, look to see if one will
196  // unblock more other nodes than the other.
197  unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum);
198  unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum);
199  if (LHSBlocked < RHSBlocked) return true;
200  if (LHSBlocked > RHSBlocked) return false;
201 
202  // Finally, just to provide a stable ordering, use the node number as a
203  // deciding factor.
204  return LHSNum < RHSNum;
205 }
206 
207 
208 /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
209 /// of SU, return it, otherwise return null.
210 SUnit *ResourcePriorityQueue::getSingleUnscheduledPred(SUnit *SU) {
211  SUnit *OnlyAvailablePred = nullptr;
212  for (const SDep &Pred : SU->Preds) {
213  SUnit &PredSU = *Pred.getSUnit();
214  if (!PredSU.isScheduled) {
215  // We found an available, but not scheduled, predecessor. If it's the
216  // only one we have found, keep track of it... otherwise give up.
217  if (OnlyAvailablePred && OnlyAvailablePred != &PredSU)
218  return nullptr;
219  OnlyAvailablePred = &PredSU;
220  }
221  }
222  return OnlyAvailablePred;
223 }
224 
226  // Look at all of the successors of this node. Count the number of nodes that
227  // this node is the sole unscheduled node for.
228  unsigned NumNodesBlocking = 0;
229  for (const SDep &Succ : SU->Succs)
230  if (getSingleUnscheduledPred(Succ.getSUnit()) == SU)
231  ++NumNodesBlocking;
232 
233  NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;
234  Queue.push_back(SU);
235 }
236 
237 /// Check if scheduling of this SU is possible
238 /// in the current packet.
240  if (!SU || !SU->getNode())
241  return false;
242 
243  // If this is a compound instruction,
244  // it is likely to be a call. Do not delay it.
245  if (SU->getNode()->getGluedNode())
246  return true;
247 
248  // First see if the pipeline could receive this instruction
249  // in the current cycle.
250  if (SU->getNode()->isMachineOpcode())
251  switch (SU->getNode()->getMachineOpcode()) {
252  default:
253  if (!ResourcesModel->canReserveResources(&TII->get(
254  SU->getNode()->getMachineOpcode())))
255  return false;
256  break;
257  case TargetOpcode::EXTRACT_SUBREG:
258  case TargetOpcode::INSERT_SUBREG:
259  case TargetOpcode::SUBREG_TO_REG:
260  case TargetOpcode::REG_SEQUENCE:
261  case TargetOpcode::IMPLICIT_DEF:
262  break;
263  }
264 
265  // Now see if there are no other dependencies
266  // to instructions already in the packet.
267  for (unsigned i = 0, e = Packet.size(); i != e; ++i)
268  for (const SDep &Succ : Packet[i]->Succs) {
269  // Since we do not add pseudos to packets, might as well
270  // ignore order deps.
271  if (Succ.isCtrl())
272  continue;
273 
274  if (Succ.getSUnit() == SU)
275  return false;
276  }
277 
278  return true;
279 }
280 
281 /// Keep track of available resources.
283  // If this SU does not fit in the packet
284  // start a new one.
285  if (!isResourceAvailable(SU) || SU->getNode()->getGluedNode()) {
286  ResourcesModel->clearResources();
287  Packet.clear();
288  }
289 
290  if (SU->getNode() && SU->getNode()->isMachineOpcode()) {
291  switch (SU->getNode()->getMachineOpcode()) {
292  default:
293  ResourcesModel->reserveResources(&TII->get(
294  SU->getNode()->getMachineOpcode()));
295  break;
296  case TargetOpcode::EXTRACT_SUBREG:
297  case TargetOpcode::INSERT_SUBREG:
298  case TargetOpcode::SUBREG_TO_REG:
299  case TargetOpcode::REG_SEQUENCE:
300  case TargetOpcode::IMPLICIT_DEF:
301  break;
302  }
303  Packet.push_back(SU);
304  }
305  // Forcefully end packet for PseudoOps.
306  else {
307  ResourcesModel->clearResources();
308  Packet.clear();
309  }
310 
311  // If packet is now full, reset the state so in the next cycle
312  // we start fresh.
313  if (Packet.size() >= InstrItins->SchedModel.IssueWidth) {
314  ResourcesModel->clearResources();
315  Packet.clear();
316  }
317 }
318 
320  int RegBalance = 0;
321 
322  if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode())
323  return RegBalance;
324 
325  // Gen estimate.
326  for (unsigned i = 0, e = SU->getNode()->getNumValues(); i != e; ++i) {
327  MVT VT = SU->getNode()->getSimpleValueType(i);
328  if (TLI->isTypeLegal(VT)
329  && TLI->getRegClassFor(VT)
330  && TLI->getRegClassFor(VT)->getID() == RCId)
331  RegBalance += numberRCValSuccInSU(SU, RCId);
332  }
333  // Kill estimate.
334  for (unsigned i = 0, e = SU->getNode()->getNumOperands(); i != e; ++i) {
335  const SDValue &Op = SU->getNode()->getOperand(i);
336  MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
337  if (isa<ConstantSDNode>(Op.getNode()))
338  continue;
339 
340  if (TLI->isTypeLegal(VT) && TLI->getRegClassFor(VT)
341  && TLI->getRegClassFor(VT)->getID() == RCId)
342  RegBalance -= numberRCValPredInSU(SU, RCId);
343  }
344  return RegBalance;
345 }
346 
347 /// Estimates change in reg pressure from this SU.
348 /// It is achieved by trivial tracking of defined
349 /// and used vregs in dependent instructions.
350 /// The RawPressure flag makes this function to ignore
351 /// existing reg file sizes, and report raw def/use
352 /// balance.
353 int ResourcePriorityQueue::regPressureDelta(SUnit *SU, bool RawPressure) {
354  int RegBalance = 0;
355 
356  if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode())
357  return RegBalance;
358 
359  if (RawPressure) {
360  for (const TargetRegisterClass *RC : TRI->regclasses())
361  RegBalance += rawRegPressureDelta(SU, RC->getID());
362  }
363  else {
364  for (const TargetRegisterClass *RC : TRI->regclasses()) {
365  if ((RegPressure[RC->getID()] +
366  rawRegPressureDelta(SU, RC->getID()) > 0) &&
367  (RegPressure[RC->getID()] +
368  rawRegPressureDelta(SU, RC->getID()) >= RegLimit[RC->getID()]))
369  RegBalance += rawRegPressureDelta(SU, RC->getID());
370  }
371  }
372 
373  return RegBalance;
374 }
375 
376 // Constants used to denote relative importance of
377 // heuristic components for cost computation.
378 static const unsigned PriorityOne = 200;
379 static const unsigned PriorityTwo = 50;
380 static const unsigned PriorityThree = 15;
381 static const unsigned PriorityFour = 5;
382 static const unsigned ScaleOne = 20;
383 static const unsigned ScaleTwo = 10;
384 static const unsigned ScaleThree = 5;
385 static const unsigned FactorOne = 2;
386 
387 /// Returns single number reflecting benefit of scheduling SU
388 /// in the current cycle.
390  // Initial trivial priority.
391  int ResCount = 1;
392 
393  // Do not waste time on a node that is already scheduled.
394  if (SU->isScheduled)
395  return ResCount;
396 
397  // Forced priority is high.
398  if (SU->isScheduleHigh)
399  ResCount += PriorityOne;
400 
401  // Adaptable scheduling
402  // A small, but very parallel
403  // region, where reg pressure is an issue.
404  if (HorizontalVerticalBalance > RegPressureThreshold) {
405  // Critical path first
406  ResCount += (SU->getHeight() * ScaleTwo);
407  // If resources are available for it, multiply the
408  // chance of scheduling.
409  if (isResourceAvailable(SU))
410  ResCount <<= FactorOne;
411 
412  // Consider change to reg pressure from scheduling
413  // this SU.
414  ResCount -= (regPressureDelta(SU,true) * ScaleOne);
415  }
416  // Default heuristic, greeady and
417  // critical path driven.
418  else {
419  // Critical path first.
420  ResCount += (SU->getHeight() * ScaleTwo);
421  // Now see how many instructions is blocked by this SU.
422  ResCount += (NumNodesSolelyBlocking[SU->NodeNum] * ScaleTwo);
423  // If resources are available for it, multiply the
424  // chance of scheduling.
425  if (isResourceAvailable(SU))
426  ResCount <<= FactorOne;
427 
428  ResCount -= (regPressureDelta(SU) * ScaleTwo);
429  }
430 
431  // These are platform-specific things.
432  // Will need to go into the back end
433  // and accessed from here via a hook.
434  for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) {
435  if (N->isMachineOpcode()) {
436  const MCInstrDesc &TID = TII->get(N->getMachineOpcode());
437  if (TID.isCall())
438  ResCount += (PriorityTwo + (ScaleThree*N->getNumValues()));
439  }
440  else
441  switch (N->getOpcode()) {
442  default: break;
443  case ISD::TokenFactor:
444  case ISD::CopyFromReg:
445  case ISD::CopyToReg:
446  ResCount += PriorityFour;
447  break;
448 
449  case ISD::INLINEASM:
450  case ISD::INLINEASM_BR:
451  ResCount += PriorityThree;
452  break;
453  }
454  }
455  return ResCount;
456 }
457 
458 
459 /// Main resource tracking point.
461  // Use NULL entry as an event marker to reset
462  // the DFA state.
463  if (!SU) {
464  ResourcesModel->clearResources();
465  Packet.clear();
466  return;
467  }
468 
469  const SDNode *ScegN = SU->getNode();
470  // Update reg pressure tracking.
471  // First update current node.
472  if (ScegN->isMachineOpcode()) {
473  // Estimate generated regs.
474  for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) {
475  MVT VT = ScegN->getSimpleValueType(i);
476 
477  if (TLI->isTypeLegal(VT)) {
478  const TargetRegisterClass *RC = TLI->getRegClassFor(VT);
479  if (RC)
480  RegPressure[RC->getID()] += numberRCValSuccInSU(SU, RC->getID());
481  }
482  }
483  // Estimate killed regs.
484  for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) {
485  const SDValue &Op = ScegN->getOperand(i);
486  MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
487 
488  if (TLI->isTypeLegal(VT)) {
489  const TargetRegisterClass *RC = TLI->getRegClassFor(VT);
490  if (RC) {
491  if (RegPressure[RC->getID()] >
492  (numberRCValPredInSU(SU, RC->getID())))
493  RegPressure[RC->getID()] -= numberRCValPredInSU(SU, RC->getID());
494  else RegPressure[RC->getID()] = 0;
495  }
496  }
497  }
498  for (SDep &Pred : SU->Preds) {
499  if (Pred.isCtrl() || (Pred.getSUnit()->NumRegDefsLeft == 0))
500  continue;
501  --Pred.getSUnit()->NumRegDefsLeft;
502  }
503  }
504 
505  // Reserve resources for this SU.
506  reserveResources(SU);
507 
508  // Adjust number of parallel live ranges.
509  // Heuristic is simple - node with no data successors reduces
510  // number of live ranges. All others, increase it.
511  unsigned NumberNonControlDeps = 0;
512 
513  for (const SDep &Succ : SU->Succs) {
514  adjustPriorityOfUnscheduledPreds(Succ.getSUnit());
515  if (!Succ.isCtrl())
516  NumberNonControlDeps++;
517  }
518 
519  if (!NumberNonControlDeps) {
520  if (ParallelLiveRanges >= SU->NumPreds)
521  ParallelLiveRanges -= SU->NumPreds;
522  else
523  ParallelLiveRanges = 0;
524 
525  }
526  else
527  ParallelLiveRanges += SU->NumRegDefsLeft;
528 
529  // Track parallel live chains.
530  HorizontalVerticalBalance += (SU->Succs.size() - numberCtrlDepsInSU(SU));
531  HorizontalVerticalBalance -= (SU->Preds.size() - numberCtrlPredInSU(SU));
532 }
533 
535  unsigned NodeNumDefs = 0;
536  for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
537  if (N->isMachineOpcode()) {
538  const MCInstrDesc &TID = TII->get(N->getMachineOpcode());
539  // No register need be allocated for this.
540  if (N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF) {
541  NodeNumDefs = 0;
542  break;
543  }
544  NodeNumDefs = std::min(N->getNumValues(), TID.getNumDefs());
545  }
546  else
547  switch(N->getOpcode()) {
548  default: break;
549  case ISD::CopyFromReg:
550  NodeNumDefs++;
551  break;
552  case ISD::INLINEASM:
553  case ISD::INLINEASM_BR:
554  NodeNumDefs++;
555  break;
556  }
557 
558  SU->NumRegDefsLeft = NodeNumDefs;
559 }
560 
561 /// adjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just
562 /// scheduled. If SU is not itself available, then there is at least one
563 /// predecessor node that has not been scheduled yet. If SU has exactly ONE
564 /// unscheduled predecessor, we want to increase its priority: it getting
565 /// scheduled will make this node available, so it is better than some other
566 /// node of the same priority that will not make a node available.
567 void ResourcePriorityQueue::adjustPriorityOfUnscheduledPreds(SUnit *SU) {
568  if (SU->isAvailable) return; // All preds scheduled.
569 
570  SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);
571  if (!OnlyAvailablePred || !OnlyAvailablePred->isAvailable)
572  return;
573 
574  // Okay, we found a single predecessor that is available, but not scheduled.
575  // Since it is available, it must be in the priority queue. First remove it.
576  remove(OnlyAvailablePred);
577 
578  // Reinsert the node into the priority queue, which recomputes its
579  // NumNodesSolelyBlocking value.
580  push(OnlyAvailablePred);
581 }
582 
583 
584 /// Main access point - returns next instructions
585 /// to be placed in scheduling sequence.
587  if (empty())
588  return nullptr;
589 
590  std::vector<SUnit *>::iterator Best = Queue.begin();
591  if (!DisableDFASched) {
592  int BestCost = SUSchedulingCost(*Best);
593  for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E; ++I) {
594 
595  if (SUSchedulingCost(*I) > BestCost) {
596  BestCost = SUSchedulingCost(*I);
597  Best = I;
598  }
599  }
600  }
601  // Use default TD scheduling mechanism.
602  else {
603  for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E; ++I)
604  if (Picker(*Best, *I))
605  Best = I;
606  }
607 
608  SUnit *V = *Best;
609  if (Best != std::prev(Queue.end()))
610  std::swap(*Best, Queue.back());
611 
612  Queue.pop_back();
613 
614  return V;
615 }
616 
617 
619  assert(!Queue.empty() && "Queue is empty!");
620  std::vector<SUnit *>::iterator I = find(Queue, SU);
621  if (I != std::prev(Queue.end()))
622  std::swap(*I, Queue.back());
623 
624  Queue.pop_back();
625 }
static const unsigned PriorityTwo
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
static const unsigned PriorityFour
unsigned NumPreds
of SDep::Data preds.
Definition: ScheduleDAG.h:266
This class represents lattice values for constants.
Definition: AllocatorList.h:23
unsigned IssueWidth
Definition: MCSchedule.h:256
SDNode * getNode() const
Returns the representative SDNode for this SUnit.
Definition: ScheduleDAG.h:355
static const unsigned ScaleTwo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:163
virtual const TargetRegisterClass * getRegClassFor(MVT VT) const
Return the register class that should be used for the specified value type.
MVT getSimpleValueType(unsigned ResNo) const
Return the type of a specified result as a simple type.
static cl::opt< int > RegPressureThreshold("dfa-sched-reg-pressure-threshold", cl::Hidden, cl::ZeroOrMore, cl::init(5), cl::desc("Track reg pressure and switch priority to in-depth"))
SDNode * getNode() const
get the SDNode which holds the desired result
virtual unsigned getRegPressureLimit(const TargetRegisterClass *RC, MachineFunction &MF) const
Return the register pressure "high water mark" for the specific register class.
void reserveResources(SUnit *SU)
Keep track of available resources.
MachineFunction * MF
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:256
static unsigned numberCtrlDepsInSU(SUnit *SU)
bool isScheduled
True once scheduled.
Definition: ScheduleDAG.h:284
virtual DFAPacketizer * CreateTargetScheduleState(const TargetSubtargetInfo &) const
Create machine specific model for scheduling.
const TargetLowering * TLI
CopyToReg - This node has three operands: a chain, a register number to set to this value...
Definition: ISDOpcodes.h:169
iterator_range< regclass_iterator > regclasses() const
void initNumRegDefsLeft(SUnit *SU)
InitNumRegDefsLeft - Determine the # of regs defined by this node.
unsigned getID() const
Return the register class ID number.
INLINEASM - Represents an inline asm block.
Definition: ISDOpcodes.h:668
ResourcePriorityQueue(SelectionDAGISel *IS)
unsigned getNumRegClasses() const
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
Definition: ScheduleDAG.h:161
virtual const TargetInstrInfo * getInstrInfo() const
SUnit * getSUnit() const
Definition: ScheduleDAG.h:480
static const unsigned ScaleThree
Scheduling dependency.
Definition: ScheduleDAG.h:49
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:423
int rawRegPressureDelta(SUnit *SU, unsigned RCId)
Machine Value Type.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const SDValue & getOperand(unsigned Num) const
bool operator()(const SUnit *LHS, const SUnit *RHS) const
This heuristic is used if DFA scheduling is not desired for some VLIW platform.
int SUSchedulingCost(SUnit *SU)
Single cost function reflecting benefit of scheduling SU in the current cycle.
SDNode * getGluedNode() const
If this node has a glue operand, return the node to which the glue operand points.
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1206
bool isMachineOpcode() const
Test if this node has a post-isel opcode, directly corresponding to a MachineInstr opcode...
unsigned getNumOperands() const
Return the number of values used by this operation.
void remove(SUnit *SU) override
TokenFactor - This node takes multiple tokens as input and produces a single token result...
Definition: ISDOpcodes.h:49
bool isScheduleHigh
True if preferable to schedule high.
Definition: ScheduleDAG.h:285
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:225
Represents one node in the SelectionDAG.
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
bool isTypeLegal(EVT VT) const
Return true if the target has native support for the specified value type.
TargetSubtargetInfo - Generic base class for all target subtargets.
bool isAvailable
True once available.
Definition: ScheduleDAG.h:283
unsigned NodeQueueId
Queue id of node.
Definition: ScheduleDAG.h:265
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:406
static const unsigned FactorOne
void scheduledNode(SUnit *SU) override
scheduledNode - Main resource tracking point.
MCSchedModel SchedModel
Basic machine properties.
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:44
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
unsigned short NumRegDefsLeft
of reg defs with no scheduled use.
Definition: ScheduleDAG.h:272
bool isCall() const
Return true if the instruction is a call.
Definition: MCInstrDesc.h:257
static const unsigned PriorityThree
CopyFromReg - This node indicates that the input value is a virtual or physical register that is defi...
Definition: ISDOpcodes.h:174
bool isResourceAvailable(SUnit *SU)
Check if scheduling of this SU is possible in the current packet.
static const unsigned PriorityOne
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
static const unsigned ScaleOne
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
INLINEASM_BR - Terminator version of inline asm. Used by asm-goto.
Definition: ISDOpcodes.h:671
unsigned getResNo() const
get the index which selects a specific result in the SDNode
unsigned getMachineOpcode() const
This may only be called if isMachineOpcode returns true.
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:257
SUnit * pop() override
Main access point - returns next instructions to be placed in scheduling sequence.
static unsigned numberCtrlPredInSU(SUnit *SU)
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation...
int regPressureDelta(SUnit *SU, bool RawPressure=false)
Estimates change in reg pressure from this SU.
void initNodes(std::vector< SUnit > &sunits) override
Initialize nodes.
static cl::opt< bool > DisableDFASched("disable-dfa-sched", cl::Hidden, cl::ZeroOrMore, cl::init(false), cl::desc("Disable use of DFA during scheduling"))
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
This file describes how to lower LLVM code to machine code.