LLVM  15.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 
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 (SUnit &SU : *SUnits) {
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 (const SUnit *S : Packet)
267  for (const SDep &Succ : S->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  case ISD::INLINEASM_BR:
450  ResCount += PriorityThree;
451  break;
452  }
453  }
454  return ResCount;
455 }
456 
457 
458 /// Main resource tracking point.
460  // Use NULL entry as an event marker to reset
461  // the DFA state.
462  if (!SU) {
463  ResourcesModel->clearResources();
464  Packet.clear();
465  return;
466  }
467 
468  const SDNode *ScegN = SU->getNode();
469  // Update reg pressure tracking.
470  // First update current node.
471  if (ScegN->isMachineOpcode()) {
472  // Estimate generated regs.
473  for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) {
474  MVT VT = ScegN->getSimpleValueType(i);
475 
476  if (TLI->isTypeLegal(VT)) {
477  const TargetRegisterClass *RC = TLI->getRegClassFor(VT);
478  if (RC)
479  RegPressure[RC->getID()] += numberRCValSuccInSU(SU, RC->getID());
480  }
481  }
482  // Estimate killed regs.
483  for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) {
484  const SDValue &Op = ScegN->getOperand(i);
485  MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
486 
487  if (TLI->isTypeLegal(VT)) {
488  const TargetRegisterClass *RC = TLI->getRegClassFor(VT);
489  if (RC) {
490  if (RegPressure[RC->getID()] >
491  (numberRCValPredInSU(SU, RC->getID())))
492  RegPressure[RC->getID()] -= numberRCValPredInSU(SU, RC->getID());
493  else RegPressure[RC->getID()] = 0;
494  }
495  }
496  }
497  for (SDep &Pred : SU->Preds) {
498  if (Pred.isCtrl() || (Pred.getSUnit()->NumRegDefsLeft == 0))
499  continue;
500  --Pred.getSUnit()->NumRegDefsLeft;
501  }
502  }
503 
504  // Reserve resources for this SU.
505  reserveResources(SU);
506 
507  // Adjust number of parallel live ranges.
508  // Heuristic is simple - node with no data successors reduces
509  // number of live ranges. All others, increase it.
510  unsigned NumberNonControlDeps = 0;
511 
512  for (const SDep &Succ : SU->Succs) {
513  adjustPriorityOfUnscheduledPreds(Succ.getSUnit());
514  if (!Succ.isCtrl())
515  NumberNonControlDeps++;
516  }
517 
518  if (!NumberNonControlDeps) {
519  if (ParallelLiveRanges >= SU->NumPreds)
520  ParallelLiveRanges -= SU->NumPreds;
521  else
522  ParallelLiveRanges = 0;
523 
524  }
525  else
526  ParallelLiveRanges += SU->NumRegDefsLeft;
527 
528  // Track parallel live chains.
529  HorizontalVerticalBalance += (SU->Succs.size() - numberCtrlDepsInSU(SU));
530  HorizontalVerticalBalance -= (SU->Preds.size() - numberCtrlPredInSU(SU));
531 }
532 
534  unsigned NodeNumDefs = 0;
535  for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
536  if (N->isMachineOpcode()) {
537  const MCInstrDesc &TID = TII->get(N->getMachineOpcode());
538  // No register need be allocated for this.
539  if (N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF) {
540  NodeNumDefs = 0;
541  break;
542  }
543  NodeNumDefs = std::min(N->getNumValues(), TID.getNumDefs());
544  }
545  else
546  switch(N->getOpcode()) {
547  default: break;
548  case ISD::CopyFromReg:
549  NodeNumDefs++;
550  break;
551  case ISD::INLINEASM:
552  case ISD::INLINEASM_BR:
553  NodeNumDefs++;
554  break;
555  }
556 
557  SU->NumRegDefsLeft = NodeNumDefs;
558 }
559 
560 /// adjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just
561 /// scheduled. If SU is not itself available, then there is at least one
562 /// predecessor node that has not been scheduled yet. If SU has exactly ONE
563 /// unscheduled predecessor, we want to increase its priority: it getting
564 /// scheduled will make this node available, so it is better than some other
565 /// node of the same priority that will not make a node available.
566 void ResourcePriorityQueue::adjustPriorityOfUnscheduledPreds(SUnit *SU) {
567  if (SU->isAvailable) return; // All preds scheduled.
568 
569  SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);
570  if (!OnlyAvailablePred || !OnlyAvailablePred->isAvailable)
571  return;
572 
573  // Okay, we found a single predecessor that is available, but not scheduled.
574  // Since it is available, it must be in the priority queue. First remove it.
575  remove(OnlyAvailablePred);
576 
577  // Reinsert the node into the priority queue, which recomputes its
578  // NumNodesSolelyBlocking value.
579  push(OnlyAvailablePred);
580 }
581 
582 
583 /// Main access point - returns next instructions
584 /// to be placed in scheduling sequence.
586  if (empty())
587  return nullptr;
588 
589  std::vector<SUnit *>::iterator Best = Queue.begin();
590  if (!DisableDFASched) {
591  int BestCost = SUSchedulingCost(*Best);
592  for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E; ++I) {
593 
594  if (SUSchedulingCost(*I) > BestCost) {
595  BestCost = SUSchedulingCost(*I);
596  Best = I;
597  }
598  }
599  }
600  // Use default TD scheduling mechanism.
601  else {
602  for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E; ++I)
603  if (Picker(*Best, *I))
604  Best = I;
605  }
606 
607  SUnit *V = *Best;
608  if (Best != std::prev(Queue.end()))
609  std::swap(*Best, Queue.back());
610 
611  Queue.pop_back();
612 
613  return V;
614 }
615 
616 
618  assert(!Queue.empty() && "Queue is empty!");
619  std::vector<SUnit *>::iterator I = find(Queue, SU);
620  if (I != std::prev(Queue.end()))
621  std::swap(*I, Queue.back());
622 
623  Queue.pop_back();
624 }
i
i
Definition: README.txt:29
llvm::MCInstrDesc::getNumDefs
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:245
llvm::SelectionDAGISel::TLI
const TargetLowering * TLI
Definition: SelectionDAGISel.h:54
llvm::TargetRegisterClass::getID
unsigned getID() const
Return the register class ID number.
Definition: TargetRegisterInfo.h:72
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::ResourcePriorityQueue::initNumRegDefsLeft
void initNumRegDefsLeft(SUnit *SU)
InitNumRegDefsLeft - Determine the # of regs defined by this node.
Definition: ResourcePriorityQueue.cpp:533
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:388
numberCtrlPredInSU
static unsigned numberCtrlPredInSU(SUnit *SU)
Definition: ResourcePriorityQueue.cpp:151
llvm::SUnit::isAvailable
bool isAvailable
True once available.
Definition: ScheduleDAG.h:283
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:93
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:125
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
PriorityOne
static const unsigned PriorityOne
Definition: ResourcePriorityQueue.cpp:377
TargetInstrInfo.h
llvm::TargetInstrInfo::CreateTargetScheduleState
virtual DFAPacketizer * CreateTargetScheduleState(const TargetSubtargetInfo &) const
Create machine specific model for scheduling.
Definition: TargetInstrInfo.h:1790
llvm::ResourcePriorityQueue::pop
SUnit * pop() override
Main access point - returns next instructions to be placed in scheduling sequence.
Definition: ResourcePriorityQueue.cpp:585
llvm::SUnit::Succs
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:257
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::ISD::INLINEASM
@ INLINEASM
INLINEASM - Represents an inline asm block.
Definition: ISDOpcodes.h:1018
CommandLine.h
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
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:175
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:632
ScaleThree
static const unsigned ScaleThree
Definition: ResourcePriorityQueue.cpp:383
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:45
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:197
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:740
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:116
llvm::ResourcePriorityQueue::rawRegPressureDelta
int rawRegPressureDelta(SUnit *SU, unsigned RCId)
Definition: ResourcePriorityQueue.cpp:318
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:640
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:352
llvm::TargetLoweringBase::isTypeLegal
bool isTypeLegal(EVT VT) const
Return true if the target has native support for the specified value type.
Definition: TargetLowering.h:932
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:285
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:1625
numberCtrlDepsInSU
static unsigned numberCtrlDepsInSU(SUnit *SU)
Definition: ResourcePriorityQueue.cpp:142
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:908
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:432
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:853
llvm::ResourcePriorityQueue::isResourceAvailable
bool isResourceAvailable(SUnit *SU)
Check if scheduling of this SU is possible in the current packet.
Definition: ResourcePriorityQueue.cpp:238
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:976
llvm::SDNode::isMachineOpcode
bool isMachineOpcode() const
Test if this node has a post-isel opcode, directly corresponding to a MachineInstr opcode.
Definition: SelectionDAGNodes.h:687
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:43
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:60
llvm::SDep
Scheduling dependency.
Definition: ScheduleDAG.h:49
PriorityThree
static const unsigned PriorityThree
Definition: ResourcePriorityQueue.cpp:379
PriorityTwo
static const unsigned PriorityTwo
Definition: ResourcePriorityQueue.cpp:378
llvm::SelectionDAGISel::MF
MachineFunction * MF
Definition: SelectionDAGISel.h:46
ScaleOne
static const unsigned ScaleOne
Definition: ResourcePriorityQueue.cpp:381
llvm::ResourcePriorityQueue::push
void push(SUnit *U) override
Definition: ResourcePriorityQueue.cpp:224
llvm::SDNode::getNumOperands
unsigned getNumOperands() const
Return the number of values used by this operation.
Definition: SelectionDAGNodes.h:895
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:341
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:1021
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:967
llvm::TargetRegisterInfo::getNumRegClasses
unsigned getNumRegClasses() const
Definition: TargetRegisterInfo.h:744
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:692
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:40
llvm::ResourcePriorityQueue::scheduledNode
void scheduledNode(SUnit *SU) override
scheduledNode - Main resource tracking point.
Definition: ResourcePriorityQueue.cpp:459
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:617
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:889
FactorOne
static const unsigned FactorOne
Definition: ResourcePriorityQueue.cpp:384
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:163
llvm::MCInstrInfo::get
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
Definition: MCInstrInfo.h:63
llvm::cl::desc
Definition: CommandLine.h:405
PriorityFour
static const unsigned PriorityFour
Definition: ResourcePriorityQueue.cpp:380
llvm::SDep::isCtrl
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
Definition: ScheduleDAG.h:161
TargetRegisterInfo.h
ScaleTwo
static const unsigned ScaleTwo
Definition: ResourcePriorityQueue.cpp:382
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:801
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:943
llvm::ResourcePriorityQueue::reserveResources
void reserveResources(SUnit *SU)
Keep track of available resources.
Definition: ResourcePriorityQueue.cpp:281