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