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