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