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
21#include "llvm/CodeGen/ResourcePriorityQueue.h"
22#include "llvm/CodeGen/DFAPacketizer.h"
23#include "llvm/CodeGen/SelectionDAGISel.h"
24#include "llvm/CodeGen/SelectionDAGNodes.h"
25#include "llvm/CodeGen/TargetInstrInfo.h"
26#include "llvm/CodeGen/TargetLowering.h"
27#include "llvm/CodeGen/TargetRegisterInfo.h"
28#include "llvm/CodeGen/TargetSubtargetInfo.h"
29#include "llvm/Support/CommandLine.h"
30
31using namespace llvm;
32
33#define DEBUG_TYPE "scheduler"
34
35static cl::opt<bool>
36 DisableDFASched("disable-dfa-sched", cl::Hidden,
37 cl::desc("Disable use of DFA during scheduling"));
38
39static cl::opt<int> RegPressureThreshold(
40 "dfa-sched-reg-pressure-threshold", cl::Hidden, cl::init(Val: 5),
41 cl::desc("Track reg pressure and switch priority to in-depth"));
42
43ResourcePriorityQueue::ResourcePriorityQueue(SelectionDAGISel *IS)
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(p: 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(new_size: NumRC);
56 RegPressure.resize(new_size: NumRC);
57 llvm::fill(Range&: RegLimit, Value: 0);
58 llvm::fill(Range&: RegPressure, Value: 0);
59 for (const TargetRegisterClass &RC : TRI->regclasses())
60 RegLimit[RC.getID()] = TRI->getRegPressureLimit(RC: &RC, MF&: *IS->MF);
61
62 ParallelLiveRanges = 0;
63 HorizontalVerticalBalance = 0;
64}
65
66ResourcePriorityQueue::~ResourcePriorityQueue() = default;
67
68unsigned
69ResourcePriorityQueue::numberRCValPredInSU(SUnit *SU, unsigned RCId) {
70 unsigned NumberDeps = 0;
71 for (SDep &Pred : SU->Preds) {
72 if (Pred.isCtrl())
73 continue;
74
75 SUnit *PredSU = Pred.getSUnit();
76 const SDNode *ScegN = PredSU->getNode();
77
78 if (!ScegN)
79 continue;
80
81 // If value is passed to CopyToReg, it is probably
82 // live outside BB.
83 switch (ScegN->getOpcode()) {
84 default: break;
85 case ISD::TokenFactor: break;
86 case ISD::CopyFromReg: NumberDeps++; break;
87 case ISD::CopyToReg: break;
88 case ISD::INLINEASM: break;
89 case ISD::INLINEASM_BR: break;
90 }
91 if (!ScegN->isMachineOpcode())
92 continue;
93
94 for (unsigned i = 0, e = ScegN->getNumValues(); i != e; ++i) {
95 MVT VT = ScegN->getSimpleValueType(ResNo: i);
96 if (TLI->isTypeLegal(VT)
97 && (TLI->getRegClassFor(VT)->getID() == RCId)) {
98 NumberDeps++;
99 break;
100 }
101 }
102 }
103 return NumberDeps;
104}
105
106unsigned ResourcePriorityQueue::numberRCValSuccInSU(SUnit *SU,
107 unsigned RCId) {
108 unsigned NumberDeps = 0;
109 for (const SDep &Succ : SU->Succs) {
110 if (Succ.isCtrl())
111 continue;
112
113 SUnit *SuccSU = Succ.getSUnit();
114 const SDNode *ScegN = SuccSU->getNode();
115 if (!ScegN)
116 continue;
117
118 // If value is passed to CopyToReg, it is probably
119 // live outside BB.
120 switch (ScegN->getOpcode()) {
121 default: break;
122 case ISD::TokenFactor: break;
123 case ISD::CopyFromReg: break;
124 case ISD::CopyToReg: NumberDeps++; break;
125 case ISD::INLINEASM: break;
126 case ISD::INLINEASM_BR: break;
127 }
128 if (!ScegN->isMachineOpcode())
129 continue;
130
131 for (unsigned i = 0, e = ScegN->getNumOperands(); i != e; ++i) {
132 const SDValue &Op = ScegN->getOperand(Num: i);
133 MVT VT = Op.getNode()->getSimpleValueType(ResNo: Op.getResNo());
134 if (TLI->isTypeLegal(VT)
135 && (TLI->getRegClassFor(VT)->getID() == RCId)) {
136 NumberDeps++;
137 break;
138 }
139 }
140 }
141 return NumberDeps;
142}
143
144static unsigned numberCtrlDepsInSU(SUnit *SU) {
145 unsigned NumberDeps = 0;
146 for (const SDep &Succ : SU->Succs)
147 if (Succ.isCtrl())
148 NumberDeps++;
149
150 return NumberDeps;
151}
152
153static unsigned numberCtrlPredInSU(SUnit *SU) {
154 unsigned NumberDeps = 0;
155 for (SDep &Pred : SU->Preds)
156 if (Pred.isCtrl())
157 NumberDeps++;
158
159 return NumberDeps;
160}
161
162///
163/// Initialize nodes.
164///
165void ResourcePriorityQueue::initNodes(std::vector<SUnit> &sunits) {
166 SUnits = &sunits;
167 NumNodesSolelyBlocking.resize(new_size: SUnits->size(), x: 0);
168
169 for (SUnit &SU : *SUnits) {
170 initNumRegDefsLeft(SU: &SU);
171 SU.NodeQueueId = 0;
172 }
173}
174
175/// This heuristic is used if DFA scheduling is not desired
176/// for some VLIW platform.
177bool resource_sort::operator()(const SUnit *LHS, const SUnit *RHS) const {
178 // The isScheduleHigh flag allows nodes with wraparound dependencies that
179 // cannot easily be modeled as edges with latencies to be scheduled as
180 // soon as possible in a top-down schedule.
181 if (LHS->isScheduleHigh && !RHS->isScheduleHigh)
182 return false;
183
184 if (!LHS->isScheduleHigh && RHS->isScheduleHigh)
185 return true;
186
187 unsigned LHSNum = LHS->NodeNum;
188 unsigned RHSNum = RHS->NodeNum;
189
190 // The most important heuristic is scheduling the critical path.
191 unsigned LHSLatency = PQ->getLatency(NodeNum: LHSNum);
192 unsigned RHSLatency = PQ->getLatency(NodeNum: RHSNum);
193 if (LHSLatency < RHSLatency) return true;
194 if (LHSLatency > RHSLatency) return false;
195
196 // After that, if two nodes have identical latencies, look to see if one will
197 // unblock more other nodes than the other.
198 unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(NodeNum: LHSNum);
199 unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(NodeNum: RHSNum);
200 if (LHSBlocked < RHSBlocked) return true;
201 if (LHSBlocked > RHSBlocked) return false;
202
203 // Finally, just to provide a stable ordering, use the node number as a
204 // deciding factor.
205 return LHSNum < RHSNum;
206}
207
208
209/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
210/// of SU, return it, otherwise return null.
211SUnit *ResourcePriorityQueue::getSingleUnscheduledPred(SUnit *SU) {
212 SUnit *OnlyAvailablePred = nullptr;
213 for (const SDep &Pred : SU->Preds) {
214 SUnit &PredSU = *Pred.getSUnit();
215 if (!PredSU.isScheduled) {
216 // We found an available, but not scheduled, predecessor. If it's the
217 // only one we have found, keep track of it... otherwise give up.
218 if (OnlyAvailablePred && OnlyAvailablePred != &PredSU)
219 return nullptr;
220 OnlyAvailablePred = &PredSU;
221 }
222 }
223 return OnlyAvailablePred;
224}
225
226void ResourcePriorityQueue::push(SUnit *SU) {
227 // Look at all of the successors of this node. Count the number of nodes that
228 // this node is the sole unscheduled node for.
229 unsigned NumNodesBlocking = 0;
230 for (const SDep &Succ : SU->Succs)
231 if (getSingleUnscheduledPred(SU: Succ.getSUnit()) == SU)
232 ++NumNodesBlocking;
233
234 NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;
235 Queue.push_back(x: SU);
236}
237
238/// Check if scheduling of this SU is possible
239/// in the current packet.
240bool ResourcePriorityQueue::isResourceAvailable(SUnit *SU) {
241 if (!SU || !SU->getNode())
242 return false;
243
244 // If this is a compound instruction,
245 // it is likely to be a call. Do not delay it.
246 if (SU->getNode()->getGluedNode())
247 return true;
248
249 // First see if the pipeline could receive this instruction
250 // in the current cycle.
251 if (SU->getNode()->isMachineOpcode())
252 switch (SU->getNode()->getMachineOpcode()) {
253 default:
254 if (!ResourcesModel->canReserveResources(MID: &TII->get(
255 Opcode: SU->getNode()->getMachineOpcode())))
256 return false;
257 break;
258 case TargetOpcode::EXTRACT_SUBREG:
259 case TargetOpcode::INSERT_SUBREG:
260 case TargetOpcode::SUBREG_TO_REG:
261 case TargetOpcode::REG_SEQUENCE:
262 case TargetOpcode::IMPLICIT_DEF:
263 break;
264 }
265
266 // Now see if there are no other dependencies
267 // to instructions already in the packet.
268 for (const SUnit *S : Packet)
269 for (const SDep &Succ : S->Succs) {
270 // Since we do not add pseudos to packets, might as well
271 // ignore order deps.
272 if (Succ.isCtrl())
273 continue;
274
275 if (Succ.getSUnit() == SU)
276 return false;
277 }
278
279 return true;
280}
281
282/// Keep track of available resources.
283void ResourcePriorityQueue::reserveResources(SUnit *SU) {
284 // If this SU does not fit in the packet
285 // start a new one.
286 if (!isResourceAvailable(SU) || SU->getNode()->getGluedNode()) {
287 ResourcesModel->clearResources();
288 Packet.clear();
289 }
290
291 if (SU->getNode() && SU->getNode()->isMachineOpcode()) {
292 switch (SU->getNode()->getMachineOpcode()) {
293 default:
294 ResourcesModel->reserveResources(MID: &TII->get(
295 Opcode: SU->getNode()->getMachineOpcode()));
296 break;
297 case TargetOpcode::EXTRACT_SUBREG:
298 case TargetOpcode::INSERT_SUBREG:
299 case TargetOpcode::SUBREG_TO_REG:
300 case TargetOpcode::REG_SEQUENCE:
301 case TargetOpcode::IMPLICIT_DEF:
302 break;
303 }
304 Packet.push_back(x: SU);
305 }
306 // Forcefully end packet for PseudoOps.
307 else {
308 ResourcesModel->clearResources();
309 Packet.clear();
310 }
311
312 // If packet is now full, reset the state so in the next cycle
313 // we start fresh.
314 if (Packet.size() >= InstrItins->SchedModel.IssueWidth) {
315 ResourcesModel->clearResources();
316 Packet.clear();
317 }
318}
319
320int ResourcePriorityQueue::rawRegPressureDelta(SUnit *SU, unsigned RCId) {
321 int RegBalance = 0;
322
323 if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode())
324 return RegBalance;
325
326 // Gen estimate.
327 for (unsigned i = 0, e = SU->getNode()->getNumValues(); i != e; ++i) {
328 MVT VT = SU->getNode()->getSimpleValueType(ResNo: i);
329 if (TLI->isTypeLegal(VT)
330 && TLI->getRegClassFor(VT)
331 && TLI->getRegClassFor(VT)->getID() == RCId)
332 RegBalance += numberRCValSuccInSU(SU, RCId);
333 }
334 // Kill estimate.
335 for (unsigned i = 0, e = SU->getNode()->getNumOperands(); i != e; ++i) {
336 const SDValue &Op = SU->getNode()->getOperand(Num: i);
337 MVT VT = Op.getNode()->getSimpleValueType(ResNo: Op.getResNo());
338 if (isa<ConstantSDNode>(Val: Op.getNode()))
339 continue;
340
341 if (TLI->isTypeLegal(VT) && TLI->getRegClassFor(VT)
342 && TLI->getRegClassFor(VT)->getID() == RCId)
343 RegBalance -= numberRCValPredInSU(SU, RCId);
344 }
345 return RegBalance;
346}
347
348/// Estimates change in reg pressure from this SU.
349/// It is achieved by trivial tracking of defined
350/// and used vregs in dependent instructions.
351/// The RawPressure flag makes this function to ignore
352/// existing reg file sizes, and report raw def/use
353/// balance.
354int ResourcePriorityQueue::regPressureDelta(SUnit *SU, bool RawPressure) {
355 int RegBalance = 0;
356
357 if (!SU || !SU->getNode() || !SU->getNode()->isMachineOpcode())
358 return RegBalance;
359
360 if (RawPressure) {
361 for (const TargetRegisterClass &RC : TRI->regclasses())
362 RegBalance += rawRegPressureDelta(SU, RCId: RC.getID());
363 }
364 else {
365 for (const TargetRegisterClass &RC : TRI->regclasses()) {
366 if ((RegPressure[RC.getID()] + rawRegPressureDelta(SU, RCId: RC.getID()) > 0) &&
367 (RegPressure[RC.getID()] + rawRegPressureDelta(SU, RCId: RC.getID()) >=
368 RegLimit[RC.getID()]))
369 RegBalance += rawRegPressureDelta(SU, RCId: RC.getID());
370 }
371 }
372
373 return RegBalance;
374}
375
376// Constants used to denote relative importance of
377// heuristic components for cost computation.
378static const unsigned PriorityOne = 200;
379static const unsigned PriorityTwo = 50;
380static const unsigned PriorityThree = 15;
381static const unsigned PriorityFour = 5;
382static const unsigned ScaleOne = 20;
383static const unsigned ScaleTwo = 10;
384static const unsigned ScaleThree = 5;
385static const unsigned FactorOne = 2;
386
387/// Returns single number reflecting benefit of scheduling SU
388/// in the current cycle.
389int ResourcePriorityQueue::SUSchedulingCost(SUnit *SU) {
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,RawPressure: 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(Opcode: 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.
460void ResourcePriorityQueue::scheduledNode(SUnit *SU) {
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(ResNo: i);
476
477 if (TLI->isTypeLegal(VT)) {
478 const TargetRegisterClass *RC = TLI->getRegClassFor(VT);
479 if (RC)
480 RegPressure[RC->getID()] += numberRCValSuccInSU(SU, RCId: 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(Num: i);
486 MVT VT = Op.getNode()->getSimpleValueType(ResNo: 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, RCId: RC->getID())))
493 RegPressure[RC->getID()] -= numberRCValPredInSU(SU, RCId: 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(SU: 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
534void ResourcePriorityQueue::initNumRegDefsLeft(SUnit *SU) {
535 unsigned NodeNumDefs = 0;
536 for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
537 if (N->isMachineOpcode()) {
538 const MCInstrDesc &TID = TII->get(Opcode: 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(a: N->getNumValues(), b: 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.
567void 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(SU: OnlyAvailablePred);
577
578 // Reinsert the node into the priority queue, which recomputes its
579 // NumNodesSolelyBlocking value.
580 push(SU: OnlyAvailablePred);
581}
582
583
584/// Main access point - returns next instructions
585/// to be placed in scheduling sequence.
586SUnit *ResourcePriorityQueue::pop() {
587 if (empty())
588 return nullptr;
589
590 std::vector<SUnit *>::iterator Best = Queue.begin();
591 if (!DisableDFASched) {
592 int BestCost = SUSchedulingCost(SU: *Best);
593 for (auto I = std::next(x: Queue.begin()), E = Queue.end(); I != E; ++I) {
594
595 if (SUSchedulingCost(SU: *I) > BestCost) {
596 BestCost = SUSchedulingCost(SU: *I);
597 Best = I;
598 }
599 }
600 }
601 // Use default TD scheduling mechanism.
602 else {
603 for (auto I = std::next(x: 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(x: Queue.end()))
610 std::swap(a&: *Best, b&: Queue.back());
611
612 Queue.pop_back();
613
614 return V;
615}
616
617
618void ResourcePriorityQueue::remove(SUnit *SU) {
619 assert(!Queue.empty() && "Queue is empty!");
620 std::vector<SUnit *>::iterator I = find(Range&: Queue, Val: SU);
621 if (I != std::prev(x: Queue.end()))
622 std::swap(a&: *I, b&: Queue.back());
623
624 Queue.pop_back();
625}
626