1//===- ScheduleDAGRRList.cpp - Reg pressure reduction list scheduler ------===//
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 implements bottom-up and top-down register pressure reduction list
10// schedulers, using standard algorithms. The basic approach uses a priority
11// queue of available nodes to schedule. One at a time, nodes are taken from
12// the priority queue (thus in priority order), checked for legality to
13// schedule, and emitted if legal.
14//
15//===----------------------------------------------------------------------===//
16
17#include "ScheduleDAGSDNodes.h"
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/SmallSet.h"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/ADT/Statistic.h"
24#include "llvm/CodeGen/ISDOpcodes.h"
25#include "llvm/CodeGen/MachineFunction.h"
26#include "llvm/CodeGen/MachineOperand.h"
27#include "llvm/CodeGen/Register.h"
28#include "llvm/CodeGen/ScheduleDAG.h"
29#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
30#include "llvm/CodeGen/SchedulerRegistry.h"
31#include "llvm/CodeGen/SelectionDAGISel.h"
32#include "llvm/CodeGen/SelectionDAGNodes.h"
33#include "llvm/CodeGen/TargetInstrInfo.h"
34#include "llvm/CodeGen/TargetLowering.h"
35#include "llvm/CodeGen/TargetOpcodes.h"
36#include "llvm/CodeGen/TargetRegisterInfo.h"
37#include "llvm/CodeGen/TargetSubtargetInfo.h"
38#include "llvm/CodeGenTypes/MachineValueType.h"
39#include "llvm/Config/llvm-config.h"
40#include "llvm/IR/InlineAsm.h"
41#include "llvm/MC/MCInstrDesc.h"
42#include "llvm/MC/MCRegisterInfo.h"
43#include "llvm/Support/Casting.h"
44#include "llvm/Support/CodeGen.h"
45#include "llvm/Support/CommandLine.h"
46#include "llvm/Support/Compiler.h"
47#include "llvm/Support/Debug.h"
48#include "llvm/Support/ErrorHandling.h"
49#include "llvm/Support/raw_ostream.h"
50#include <algorithm>
51#include <cassert>
52#include <cstdint>
53#include <cstdlib>
54#include <iterator>
55#include <limits>
56#include <memory>
57#include <utility>
58#include <vector>
59
60using namespace llvm;
61
62#define DEBUG_TYPE "pre-RA-sched"
63
64STATISTIC(NumBacktracks, "Number of times scheduler backtracked");
65STATISTIC(NumUnfolds, "Number of nodes unfolded");
66STATISTIC(NumDups, "Number of duplicated nodes");
67STATISTIC(NumPRCopies, "Number of physical register copies");
68
69static RegisterScheduler
70 burrListDAGScheduler("list-burr",
71 "Bottom-up register reduction list scheduling",
72 createBURRListDAGScheduler);
73
74static RegisterScheduler
75 sourceListDAGScheduler("source",
76 "Similar to list-burr but schedules in source "
77 "order when possible",
78 createSourceListDAGScheduler);
79
80static RegisterScheduler
81 hybridListDAGScheduler("list-hybrid",
82 "Bottom-up register pressure aware list scheduling "
83 "which tries to balance latency and register pressure",
84 createHybridListDAGScheduler);
85
86static RegisterScheduler
87 ILPListDAGScheduler("list-ilp",
88 "Bottom-up register pressure aware list scheduling "
89 "which tries to balance ILP and register pressure",
90 createILPListDAGScheduler);
91
92static cl::opt<bool> DisableSchedCycles(
93 "disable-sched-cycles", cl::Hidden, cl::init(Val: false),
94 cl::desc("Disable cycle-level precision during preRA scheduling"));
95
96// Temporary sched=list-ilp flags until the heuristics are robust.
97// Some options are also available under sched=list-hybrid.
98static cl::opt<bool> DisableSchedRegPressure(
99 "disable-sched-reg-pressure", cl::Hidden, cl::init(Val: false),
100 cl::desc("Disable regpressure priority in sched=list-ilp"));
101static cl::opt<bool> DisableSchedLiveUses(
102 "disable-sched-live-uses", cl::Hidden, cl::init(Val: true),
103 cl::desc("Disable live use priority in sched=list-ilp"));
104static cl::opt<bool> DisableSchedVRegCycle(
105 "disable-sched-vrcycle", cl::Hidden, cl::init(Val: false),
106 cl::desc("Disable virtual register cycle interference checks"));
107static cl::opt<bool> DisableSchedPhysRegJoin(
108 "disable-sched-physreg-join", cl::Hidden, cl::init(Val: false),
109 cl::desc("Disable physreg def-use affinity"));
110static cl::opt<bool> DisableSchedStalls(
111 "disable-sched-stalls", cl::Hidden, cl::init(Val: true),
112 cl::desc("Disable no-stall priority in sched=list-ilp"));
113static cl::opt<bool> DisableSchedCriticalPath(
114 "disable-sched-critical-path", cl::Hidden, cl::init(Val: false),
115 cl::desc("Disable critical path priority in sched=list-ilp"));
116static cl::opt<bool> DisableSchedHeight(
117 "disable-sched-height", cl::Hidden, cl::init(Val: false),
118 cl::desc("Disable scheduled-height priority in sched=list-ilp"));
119static cl::opt<bool> Disable2AddrHack(
120 "disable-2addr-hack", cl::Hidden, cl::init(Val: true),
121 cl::desc("Disable scheduler's two-address hack"));
122
123static cl::opt<int> MaxReorderWindow(
124 "max-sched-reorder", cl::Hidden, cl::init(Val: 6),
125 cl::desc("Number of instructions to allow ahead of the critical path "
126 "in sched=list-ilp"));
127
128static cl::opt<unsigned>
129 AvgIPC("sched-avg-ipc", cl::Hidden, cl::init(Val: 1),
130 cl::desc("Average inst/cycle when no target itinerary exists."));
131
132namespace {
133
134//===----------------------------------------------------------------------===//
135/// ScheduleDAGRRList - The actual register reduction list scheduler
136/// implementation. This supports both top-down and bottom-up scheduling.
137///
138class ScheduleDAGRRList : public ScheduleDAGSDNodes {
139private:
140 /// NeedLatency - True if the scheduler will make use of latency information.
141 bool NeedLatency;
142
143 /// AvailableQueue - The priority queue to use for the available SUnits.
144 SchedulingPriorityQueue *AvailableQueue;
145
146 /// PendingQueue - This contains all of the instructions whose operands have
147 /// been issued, but their results are not ready yet (due to the latency of
148 /// the operation). Once the operands becomes available, the instruction is
149 /// added to the AvailableQueue.
150 std::vector<SUnit *> PendingQueue;
151
152 /// HazardRec - The hazard recognizer to use.
153 ScheduleHazardRecognizer *HazardRec;
154
155 /// CurCycle - The current scheduler state corresponds to this cycle.
156 unsigned CurCycle = 0;
157
158 /// MinAvailableCycle - Cycle of the soonest available instruction.
159 unsigned MinAvailableCycle = ~0u;
160
161 /// IssueCount - Count instructions issued in this cycle
162 /// Currently valid only for bottom-up scheduling.
163 unsigned IssueCount = 0u;
164
165 /// LiveRegDefs - A set of physical registers and their definition
166 /// that are "live". These nodes must be scheduled before any other nodes that
167 /// modifies the registers can be scheduled.
168 unsigned NumLiveRegs = 0u;
169 std::unique_ptr<SUnit*[]> LiveRegDefs;
170 std::unique_ptr<SUnit*[]> LiveRegGens;
171
172 // Collect interferences between physical register use/defs.
173 // Each interference is an SUnit and set of physical registers.
174 SmallVector<SUnit*, 4> Interferences;
175
176 using LRegsMapT = DenseMap<SUnit *, SmallVector<unsigned, 4>>;
177
178 LRegsMapT LRegsMap;
179
180 /// Topo - A topological ordering for SUnits which permits fast IsReachable
181 /// and similar queries.
182 ScheduleDAGTopologicalSort Topo;
183
184 // Hack to keep track of the inverse of FindCallSeqStart without more crazy
185 // DAG crawling.
186 SmallDenseMap<SUnit *, SUnit *, 16> CallSeqEndForStart;
187
188public:
189 ScheduleDAGRRList(MachineFunction &mf, bool needlatency,
190 SchedulingPriorityQueue *availqueue,
191 CodeGenOptLevel OptLevel)
192 : ScheduleDAGSDNodes(mf), NeedLatency(needlatency),
193 AvailableQueue(availqueue), Topo(SUnits, nullptr) {
194 const TargetSubtargetInfo &STI = mf.getSubtarget();
195 if (DisableSchedCycles || !NeedLatency)
196 HazardRec = new ScheduleHazardRecognizer();
197 else
198 HazardRec = STI.getInstrInfo()->CreateTargetHazardRecognizer(STI: &STI, DAG: this);
199 }
200
201 ~ScheduleDAGRRList() override {
202 delete HazardRec;
203 delete AvailableQueue;
204 }
205
206 void Schedule() override;
207
208 ScheduleHazardRecognizer *getHazardRec() { return HazardRec; }
209
210 /// IsReachable - Checks if SU is reachable from TargetSU.
211 bool IsReachable(const SUnit *SU, const SUnit *TargetSU) {
212 return Topo.IsReachable(SU, TargetSU);
213 }
214
215 /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will
216 /// create a cycle.
217 bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
218 return Topo.WillCreateCycle(TargetSU: SU, SU: TargetSU);
219 }
220
221 /// AddPredQueued - Queues and update to add a predecessor edge to SUnit SU.
222 /// This returns true if this is a new predecessor.
223 /// Does *NOT* update the topological ordering! It just queues an update.
224 void AddPredQueued(SUnit *SU, const SDep &D) {
225 Topo.AddPredQueued(Y: SU, X: D.getSUnit());
226 SU->addPred(D);
227 }
228
229 /// RemovePred - removes a predecessor edge from SUnit SU.
230 /// This returns true if an edge was removed.
231 /// Updates the topological ordering if required.
232 void RemovePred(SUnit *SU, const SDep &D) {
233 Topo.RemovePred(M: SU, N: D.getSUnit());
234 SU->removePred(D);
235 }
236
237private:
238 bool isReady(SUnit *SU) {
239 return DisableSchedCycles || !AvailableQueue->hasReadyFilter() ||
240 AvailableQueue->isReady(SU);
241 }
242
243 void ReleasePred(SUnit *SU, const SDep *PredEdge);
244 void ReleasePredecessors(SUnit *SU);
245 void ReleasePending();
246 void AdvanceToCycle(unsigned NextCycle);
247 void AdvancePastStalls(SUnit *SU);
248 void EmitNode(SUnit *SU);
249 void ScheduleNodeBottomUp(SUnit*);
250 void CapturePred(SDep *PredEdge);
251 void UnscheduleNodeBottomUp(SUnit*);
252 void RestoreHazardCheckerBottomUp();
253 void BacktrackBottomUp(SUnit*, SUnit*);
254 SUnit *TryUnfoldSU(SUnit *);
255 SUnit *CopyAndMoveSuccessors(SUnit*);
256 void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
257 const TargetRegisterClass*,
258 const TargetRegisterClass*,
259 SmallVectorImpl<SUnit*>&);
260 bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl<unsigned>&);
261
262 void releaseInterferences(unsigned Reg = 0);
263
264 SUnit *PickNodeToScheduleBottomUp();
265 void ListScheduleBottomUp();
266
267 /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it.
268 SUnit *CreateNewSUnit(SDNode *N) {
269 unsigned NumSUnits = SUnits.size();
270 SUnit *NewNode = newSUnit(N);
271 // Update the topological ordering.
272 if (NewNode->NodeNum >= NumSUnits)
273 Topo.AddSUnitWithoutPredecessors(SU: NewNode);
274 return NewNode;
275 }
276
277 /// CreateClone - Creates a new SUnit from an existing one.
278 SUnit *CreateClone(SUnit *N) {
279 unsigned NumSUnits = SUnits.size();
280 SUnit *NewNode = Clone(Old: N);
281 // Update the topological ordering.
282 if (NewNode->NodeNum >= NumSUnits)
283 Topo.AddSUnitWithoutPredecessors(SU: NewNode);
284 return NewNode;
285 }
286
287 /// forceUnitLatencies - Register-pressure-reducing scheduling doesn't
288 /// need actual latency information but the hybrid scheduler does.
289 bool forceUnitLatencies() const override {
290 return !NeedLatency;
291 }
292};
293
294} // end anonymous namespace
295
296static constexpr unsigned RegSequenceCost = 1;
297
298/// GetCostForDef - Looks up the register class and cost for a given definition.
299/// Typically this just means looking up the representative register class,
300/// but for untyped values (MVT::Untyped) it means inspecting the node's
301/// opcode to determine what register class is being generated.
302static void GetCostForDef(const ScheduleDAGSDNodes::RegDefIter &RegDefPos,
303 const TargetLowering *TLI,
304 const TargetInstrInfo *TII,
305 const TargetRegisterInfo *TRI,
306 unsigned &RegClass, unsigned &Cost,
307 const MachineFunction &MF) {
308 MVT VT = RegDefPos.GetValue();
309
310 // Special handling for untyped values. These values can only come from
311 // the expansion of custom DAG-to-DAG patterns.
312 if (VT == MVT::Untyped) {
313 const SDNode *Node = RegDefPos.GetNode();
314
315 // Special handling for CopyFromReg of untyped values.
316 if (!Node->isMachineOpcode() && Node->getOpcode() == ISD::CopyFromReg) {
317 Register Reg = cast<RegisterSDNode>(Val: Node->getOperand(Num: 1))->getReg();
318 const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(Reg);
319 RegClass = RC->getID();
320 Cost = 1;
321 return;
322 }
323
324 unsigned Opcode = Node->getMachineOpcode();
325 if (Opcode == TargetOpcode::REG_SEQUENCE) {
326 unsigned DstRCIdx = Node->getConstantOperandVal(Num: 0);
327 const TargetRegisterClass *RC = TRI->getRegClass(i: DstRCIdx);
328 RegClass = RC->getID();
329 Cost = RegSequenceCost;
330 return;
331 }
332
333 unsigned Idx = RegDefPos.GetIdx();
334 const MCInstrDesc &Desc = TII->get(Opcode);
335 const TargetRegisterClass *RC = TII->getRegClass(MCID: Desc, OpNum: Idx);
336 assert(RC && "Not a valid register class");
337 RegClass = RC->getID();
338 // FIXME: Cost arbitrarily set to 1 because there doesn't seem to be a
339 // better way to determine it.
340 Cost = 1;
341 } else {
342 RegClass = TLI->getRepRegClassFor(VT)->getID();
343 Cost = TLI->getRepRegClassCostFor(VT);
344 }
345}
346
347/// Schedule - Schedule the DAG using list scheduling.
348void ScheduleDAGRRList::Schedule() {
349 LLVM_DEBUG(dbgs() << "********** List Scheduling " << printMBBReference(*BB)
350 << " '" << BB->getName() << "' **********\n");
351
352 CurCycle = 0;
353 IssueCount = 0;
354 MinAvailableCycle =
355 DisableSchedCycles ? 0 : std::numeric_limits<unsigned>::max();
356 NumLiveRegs = 0;
357 // Allocate slots for each physical register, plus one for a special register
358 // to track the virtual resource of a calling sequence.
359 LiveRegDefs.reset(p: new SUnit*[TRI->getNumRegs() + 1]());
360 LiveRegGens.reset(p: new SUnit*[TRI->getNumRegs() + 1]());
361 CallSeqEndForStart.clear();
362 assert(Interferences.empty() && LRegsMap.empty() && "stale Interferences");
363
364 // Build the scheduling graph.
365 BuildSchedGraph();
366
367 LLVM_DEBUG(dump());
368 Topo.MarkDirty();
369
370 AvailableQueue->initNodes(SUnits);
371
372 HazardRec->Reset();
373
374 // Execute the actual scheduling loop.
375 ListScheduleBottomUp();
376
377 AvailableQueue->releaseState();
378
379 LLVM_DEBUG({
380 dbgs() << "*** Final schedule ***\n";
381 dumpSchedule();
382 dbgs() << '\n';
383 });
384}
385
386//===----------------------------------------------------------------------===//
387// Bottom-Up Scheduling
388//===----------------------------------------------------------------------===//
389
390/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
391/// the AvailableQueue if the count reaches zero. Also update its cycle bound.
392void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) {
393 SUnit *PredSU = PredEdge->getSUnit();
394
395#ifndef NDEBUG
396 if (PredSU->NumSuccsLeft == 0) {
397 dbgs() << "*** Scheduling failed! ***\n";
398 dumpNode(*PredSU);
399 dbgs() << " has been released too many times!\n";
400 llvm_unreachable(nullptr);
401 }
402#endif
403 --PredSU->NumSuccsLeft;
404
405 if (!forceUnitLatencies()) {
406 // Updating predecessor's height. This is now the cycle when the
407 // predecessor can be scheduled without causing a pipeline stall.
408 PredSU->setHeightToAtLeast(SU->getHeight() + PredEdge->getLatency());
409 }
410
411 // If all the node's successors are scheduled, this node is ready
412 // to be scheduled. Ignore the special EntrySU node.
413 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
414 PredSU->isAvailable = true;
415
416 unsigned Height = PredSU->getHeight();
417 if (Height < MinAvailableCycle)
418 MinAvailableCycle = Height;
419
420 if (isReady(SU: PredSU)) {
421 AvailableQueue->push(U: PredSU);
422 }
423 // CapturePred and others may have left the node in the pending queue, avoid
424 // adding it twice.
425 else if (!PredSU->isPending) {
426 PredSU->isPending = true;
427 PendingQueue.push_back(x: PredSU);
428 }
429 }
430}
431
432/// IsChainDependent - Test if Outer is reachable from Inner through
433/// chain dependencies.
434static bool IsChainDependent(SDNode *Outer, SDNode *Inner,
435 unsigned NestLevel,
436 const TargetInstrInfo *TII) {
437 SDNode *N = Outer;
438 while (true) {
439 if (N == Inner)
440 return true;
441 // For a TokenFactor, examine each operand. There may be multiple ways
442 // to get to the CALLSEQ_BEGIN, but we need to find the path with the
443 // most nesting in order to ensure that we find the corresponding match.
444 if (N->getOpcode() == ISD::TokenFactor) {
445 for (const SDValue &Op : N->op_values())
446 if (IsChainDependent(Outer: Op.getNode(), Inner, NestLevel, TII))
447 return true;
448 return false;
449 }
450 // Check for a lowered CALLSEQ_BEGIN or CALLSEQ_END.
451 if (N->isMachineOpcode()) {
452 if (N->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
453 ++NestLevel;
454 } else if (N->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {
455 if (NestLevel == 0)
456 return false;
457 --NestLevel;
458 }
459 }
460 // Otherwise, find the chain and continue climbing.
461 for (const SDValue &Op : N->op_values())
462 if (Op.getValueType() == MVT::Other) {
463 N = Op.getNode();
464 goto found_chain_operand;
465 }
466 return false;
467 found_chain_operand:;
468 if (N->getOpcode() == ISD::EntryToken)
469 return false;
470 }
471}
472
473/// FindCallSeqStart - Starting from the (lowered) CALLSEQ_END node, locate
474/// the corresponding (lowered) CALLSEQ_BEGIN node.
475///
476/// NestLevel and MaxNested are used in recursion to indcate the current level
477/// of nesting of CALLSEQ_BEGIN and CALLSEQ_END pairs, as well as the maximum
478/// level seen so far.
479///
480/// TODO: It would be better to give CALLSEQ_END an explicit operand to point
481/// to the corresponding CALLSEQ_BEGIN to avoid needing to search for it.
482static SDNode *
483FindCallSeqStart(SDNode *N, unsigned &NestLevel, unsigned &MaxNest,
484 const TargetInstrInfo *TII) {
485 while (true) {
486 // For a TokenFactor, examine each operand. There may be multiple ways
487 // to get to the CALLSEQ_BEGIN, but we need to find the path with the
488 // most nesting in order to ensure that we find the corresponding match.
489 if (N->getOpcode() == ISD::TokenFactor) {
490 SDNode *Best = nullptr;
491 unsigned BestMaxNest = MaxNest;
492 for (const SDValue &Op : N->op_values()) {
493 unsigned MyNestLevel = NestLevel;
494 unsigned MyMaxNest = MaxNest;
495 if (SDNode *New = FindCallSeqStart(N: Op.getNode(),
496 NestLevel&: MyNestLevel, MaxNest&: MyMaxNest, TII))
497 if (!Best || (MyMaxNest > BestMaxNest)) {
498 Best = New;
499 BestMaxNest = MyMaxNest;
500 }
501 }
502 assert(Best);
503 MaxNest = BestMaxNest;
504 return Best;
505 }
506 // Check for a lowered CALLSEQ_BEGIN or CALLSEQ_END.
507 if (N->isMachineOpcode()) {
508 if (N->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
509 ++NestLevel;
510 MaxNest = std::max(a: MaxNest, b: NestLevel);
511 } else if (N->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {
512 assert(NestLevel != 0);
513 --NestLevel;
514 if (NestLevel == 0)
515 return N;
516 }
517 }
518 // Otherwise, find the chain and continue climbing.
519 for (const SDValue &Op : N->op_values())
520 if (Op.getValueType() == MVT::Other) {
521 N = Op.getNode();
522 goto found_chain_operand;
523 }
524 return nullptr;
525 found_chain_operand:;
526 if (N->getOpcode() == ISD::EntryToken)
527 return nullptr;
528 }
529}
530
531/// Call ReleasePred for each predecessor, then update register live def/gen.
532/// Always update LiveRegDefs for a register dependence even if the current SU
533/// also defines the register. This effectively create one large live range
534/// across a sequence of two-address node. This is important because the
535/// entire chain must be scheduled together. Example:
536///
537/// flags = (3) add
538/// flags = (2) addc flags
539/// flags = (1) addc flags
540///
541/// results in
542///
543/// LiveRegDefs[flags] = 3
544/// LiveRegGens[flags] = 1
545///
546/// If (2) addc is unscheduled, then (1) addc must also be unscheduled to avoid
547/// interference on flags.
548void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU) {
549 // Bottom up: release predecessors
550 for (SDep &Pred : SU->Preds) {
551 ReleasePred(SU, PredEdge: &Pred);
552 if (Pred.isAssignedRegDep()) {
553 // This is a physical register dependency and it's impossible or
554 // expensive to copy the register. Make sure nothing that can
555 // clobber the register is scheduled between the predecessor and
556 // this node.
557 SUnit *RegDef = LiveRegDefs[Pred.getReg()]; (void)RegDef;
558 assert((!RegDef || RegDef == SU || RegDef == Pred.getSUnit()) &&
559 "interference on register dependence");
560 LiveRegDefs[Pred.getReg()] = Pred.getSUnit();
561 if (!LiveRegGens[Pred.getReg()]) {
562 ++NumLiveRegs;
563 LiveRegGens[Pred.getReg()] = SU;
564 }
565 }
566 }
567
568 // If we're scheduling a lowered CALLSEQ_END, find the corresponding
569 // CALLSEQ_BEGIN. Inject an artificial physical register dependence between
570 // these nodes, to prevent other calls from being interscheduled with them.
571 unsigned CallResource = TRI->getNumRegs();
572 if (!LiveRegDefs[CallResource])
573 for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode())
574 if (Node->isMachineOpcode() &&
575 Node->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
576 unsigned NestLevel = 0;
577 unsigned MaxNest = 0;
578 SDNode *N = FindCallSeqStart(N: Node, NestLevel, MaxNest, TII);
579 assert(N && "Must find call sequence start");
580
581 SUnit *Def = &SUnits[N->getNodeId()];
582 CallSeqEndForStart[Def] = SU;
583
584 ++NumLiveRegs;
585 LiveRegDefs[CallResource] = Def;
586 LiveRegGens[CallResource] = SU;
587 break;
588 }
589}
590
591/// Check to see if any of the pending instructions are ready to issue. If
592/// so, add them to the available queue.
593void ScheduleDAGRRList::ReleasePending() {
594 if (DisableSchedCycles) {
595 assert(PendingQueue.empty() && "pending instrs not allowed in this mode");
596 return;
597 }
598
599 // If the available queue is empty, it is safe to reset MinAvailableCycle.
600 if (AvailableQueue->empty())
601 MinAvailableCycle = std::numeric_limits<unsigned>::max();
602
603 // Check to see if any of the pending instructions are ready to issue. If
604 // so, add them to the available queue.
605 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
606 unsigned ReadyCycle = PendingQueue[i]->getHeight();
607 if (ReadyCycle < MinAvailableCycle)
608 MinAvailableCycle = ReadyCycle;
609
610 if (PendingQueue[i]->isAvailable) {
611 if (!isReady(SU: PendingQueue[i]))
612 continue;
613 AvailableQueue->push(U: PendingQueue[i]);
614 }
615 PendingQueue[i]->isPending = false;
616 PendingQueue[i] = PendingQueue.back();
617 PendingQueue.pop_back();
618 --i; --e;
619 }
620}
621
622/// Move the scheduler state forward by the specified number of Cycles.
623void ScheduleDAGRRList::AdvanceToCycle(unsigned NextCycle) {
624 if (NextCycle <= CurCycle)
625 return;
626
627 IssueCount = 0;
628 AvailableQueue->setCurCycle(NextCycle);
629 if (!HazardRec->isEnabled()) {
630 // Bypass lots of virtual calls in case of long latency.
631 CurCycle = NextCycle;
632 }
633 else {
634 for (; CurCycle != NextCycle; ++CurCycle) {
635 HazardRec->RecedeCycle();
636 }
637 }
638 // FIXME: Instead of visiting the pending Q each time, set a dirty flag on the
639 // available Q to release pending nodes at least once before popping.
640 ReleasePending();
641}
642
643/// Move the scheduler state forward until the specified node's dependents are
644/// ready and can be scheduled with no resource conflicts.
645void ScheduleDAGRRList::AdvancePastStalls(SUnit *SU) {
646 if (DisableSchedCycles)
647 return;
648
649 // FIXME: Nodes such as CopyFromReg probably should not advance the current
650 // cycle. Otherwise, we can wrongly mask real stalls. If the non-machine node
651 // has predecessors the cycle will be advanced when they are scheduled.
652 // But given the crude nature of modeling latency though such nodes, we
653 // currently need to treat these nodes like real instructions.
654 // if (!SU->getNode() || !SU->getNode()->isMachineOpcode()) return;
655
656 unsigned ReadyCycle = SU->getHeight();
657
658 // Bump CurCycle to account for latency. We assume the latency of other
659 // available instructions may be hidden by the stall (not a full pipe stall).
660 // This updates the hazard recognizer's cycle before reserving resources for
661 // this instruction.
662 AdvanceToCycle(NextCycle: ReadyCycle);
663
664 // Calls are scheduled in their preceding cycle, so don't conflict with
665 // hazards from instructions after the call. EmitNode will reset the
666 // scoreboard state before emitting the call.
667 if (SU->isCall)
668 return;
669
670 // FIXME: For resource conflicts in very long non-pipelined stages, we
671 // should probably skip ahead here to avoid useless scoreboard checks.
672 int Stalls = 0;
673 while (true) {
674 ScheduleHazardRecognizer::HazardType HT =
675 HazardRec->getHazardType(SU, Stalls: -Stalls);
676
677 if (HT == ScheduleHazardRecognizer::NoHazard)
678 break;
679
680 ++Stalls;
681 }
682 AdvanceToCycle(NextCycle: CurCycle + Stalls);
683}
684
685/// Record this SUnit in the HazardRecognizer.
686/// Does not update CurCycle.
687void ScheduleDAGRRList::EmitNode(SUnit *SU) {
688 if (!HazardRec->isEnabled())
689 return;
690
691 // Check for phys reg copy.
692 if (!SU->getNode())
693 return;
694
695 switch (SU->getNode()->getOpcode()) {
696 default:
697 assert(SU->getNode()->isMachineOpcode() &&
698 "This target-independent node should not be scheduled.");
699 break;
700 case ISD::MERGE_VALUES:
701 case ISD::TokenFactor:
702 case ISD::LIFETIME_START:
703 case ISD::LIFETIME_END:
704 case ISD::CopyToReg:
705 case ISD::CopyFromReg:
706 case ISD::EH_LABEL:
707 case ISD::ANNOTATION_LABEL:
708 // Noops don't affect the scoreboard state. Copies are likely to be
709 // removed.
710 return;
711 case ISD::INLINEASM:
712 case ISD::INLINEASM_BR:
713 // For inline asm, clear the pipeline state.
714 HazardRec->Reset();
715 return;
716 }
717 if (SU->isCall) {
718 // Calls are scheduled with their preceding instructions. For bottom-up
719 // scheduling, clear the pipeline state before emitting.
720 HazardRec->Reset();
721 }
722
723 HazardRec->EmitInstruction(SU);
724}
725
726static void resetVRegCycle(SUnit *SU);
727
728/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
729/// count of its predecessors. If a predecessor pending count is zero, add it to
730/// the Available queue.
731void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU) {
732 LLVM_DEBUG(dbgs() << "\n*** Scheduling [" << CurCycle << "]: ");
733 LLVM_DEBUG(dumpNode(*SU));
734
735#ifndef NDEBUG
736 if (CurCycle < SU->getHeight())
737 LLVM_DEBUG(dbgs() << " Height [" << SU->getHeight()
738 << "] pipeline stall!\n");
739#endif
740
741 // FIXME: Do not modify node height. It may interfere with
742 // backtracking. Instead add a "ready cycle" to SUnit. Before scheduling the
743 // node its ready cycle can aid heuristics, and after scheduling it can
744 // indicate the scheduled cycle.
745 SU->setHeightToAtLeast(CurCycle);
746
747 // Reserve resources for the scheduled instruction.
748 EmitNode(SU);
749
750 Sequence.push_back(x: SU);
751
752 AvailableQueue->scheduledNode(SU);
753
754 // If HazardRec is disabled, and each inst counts as one cycle, then
755 // advance CurCycle before ReleasePredecessors to avoid useless pushes to
756 // PendingQueue for schedulers that implement HasReadyFilter.
757 if (!HazardRec->isEnabled() && AvgIPC < 2)
758 AdvanceToCycle(NextCycle: CurCycle + 1);
759
760 // Update liveness of predecessors before successors to avoid treating a
761 // two-address node as a live range def.
762 ReleasePredecessors(SU);
763
764 // Release all the implicit physical register defs that are live.
765 for (SDep &Succ : SU->Succs) {
766 // LiveRegDegs[Succ.getReg()] != SU when SU is a two-address node.
767 if (Succ.isAssignedRegDep() && LiveRegDefs[Succ.getReg()] == SU) {
768 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
769 --NumLiveRegs;
770 LiveRegDefs[Succ.getReg()] = nullptr;
771 LiveRegGens[Succ.getReg()] = nullptr;
772 releaseInterferences(Reg: Succ.getReg());
773 }
774 }
775 // Release the special call resource dependence, if this is the beginning
776 // of a call.
777 unsigned CallResource = TRI->getNumRegs();
778 if (LiveRegDefs[CallResource] == SU)
779 for (const SDNode *SUNode = SU->getNode(); SUNode;
780 SUNode = SUNode->getGluedNode()) {
781 if (SUNode->isMachineOpcode() &&
782 SUNode->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {
783 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
784 --NumLiveRegs;
785 LiveRegDefs[CallResource] = nullptr;
786 LiveRegGens[CallResource] = nullptr;
787 releaseInterferences(Reg: CallResource);
788 }
789 }
790
791 resetVRegCycle(SU);
792
793 SU->isScheduled = true;
794
795 // Conditions under which the scheduler should eagerly advance the cycle:
796 // (1) No available instructions
797 // (2) All pipelines full, so available instructions must have hazards.
798 //
799 // If HazardRec is disabled, the cycle was pre-advanced before calling
800 // ReleasePredecessors. In that case, IssueCount should remain 0.
801 //
802 // Check AvailableQueue after ReleasePredecessors in case of zero latency.
803 if (HazardRec->isEnabled() || AvgIPC > 1) {
804 if (SU->getNode() && SU->getNode()->isMachineOpcode())
805 ++IssueCount;
806 if ((HazardRec->isEnabled() && HazardRec->atIssueLimit())
807 || (!HazardRec->isEnabled() && IssueCount == AvgIPC))
808 AdvanceToCycle(NextCycle: CurCycle + 1);
809 }
810}
811
812/// CapturePred - This does the opposite of ReleasePred. Since SU is being
813/// unscheduled, increase the succ left count of its predecessors. Remove
814/// them from AvailableQueue if necessary.
815void ScheduleDAGRRList::CapturePred(SDep *PredEdge) {
816 SUnit *PredSU = PredEdge->getSUnit();
817 if (PredSU->isAvailable) {
818 PredSU->isAvailable = false;
819 if (!PredSU->isPending)
820 AvailableQueue->remove(SU: PredSU);
821 }
822
823 assert(PredSU->NumSuccsLeft < std::numeric_limits<unsigned>::max() &&
824 "NumSuccsLeft will overflow!");
825 ++PredSU->NumSuccsLeft;
826}
827
828/// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and
829/// its predecessor states to reflect the change.
830void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
831 LLVM_DEBUG(dbgs() << "*** Unscheduling [" << SU->getHeight() << "]: ");
832 LLVM_DEBUG(dumpNode(*SU));
833
834 for (SDep &Pred : SU->Preds) {
835 CapturePred(PredEdge: &Pred);
836 if (Pred.isAssignedRegDep() && SU == LiveRegGens[Pred.getReg()]){
837 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
838 assert(LiveRegDefs[Pred.getReg()] == Pred.getSUnit() &&
839 "Physical register dependency violated?");
840 --NumLiveRegs;
841 LiveRegDefs[Pred.getReg()] = nullptr;
842 LiveRegGens[Pred.getReg()] = nullptr;
843 releaseInterferences(Reg: Pred.getReg());
844 }
845 }
846
847 // Reclaim the special call resource dependence, if this is the beginning
848 // of a call.
849 unsigned CallResource = TRI->getNumRegs();
850 for (const SDNode *SUNode = SU->getNode(); SUNode;
851 SUNode = SUNode->getGluedNode()) {
852 if (SUNode->isMachineOpcode() &&
853 SUNode->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {
854 SUnit *SeqEnd = CallSeqEndForStart[SU];
855 assert(SeqEnd && "Call sequence start/end must be known");
856 assert(!LiveRegDefs[CallResource]);
857 assert(!LiveRegGens[CallResource]);
858 ++NumLiveRegs;
859 LiveRegDefs[CallResource] = SU;
860 LiveRegGens[CallResource] = SeqEnd;
861 }
862 }
863
864 // Release the special call resource dependence, if this is the end
865 // of a call.
866 if (LiveRegGens[CallResource] == SU)
867 for (const SDNode *SUNode = SU->getNode(); SUNode;
868 SUNode = SUNode->getGluedNode()) {
869 if (SUNode->isMachineOpcode() &&
870 SUNode->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
871 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
872 assert(LiveRegDefs[CallResource]);
873 assert(LiveRegGens[CallResource]);
874 --NumLiveRegs;
875 LiveRegDefs[CallResource] = nullptr;
876 LiveRegGens[CallResource] = nullptr;
877 releaseInterferences(Reg: CallResource);
878 }
879 }
880
881 for (auto &Succ : SU->Succs) {
882 if (Succ.isAssignedRegDep()) {
883 auto Reg = Succ.getReg();
884 if (!LiveRegDefs[Reg])
885 ++NumLiveRegs;
886 // This becomes the nearest def. Note that an earlier def may still be
887 // pending if this is a two-address node.
888 LiveRegDefs[Reg] = SU;
889
890 // Update LiveRegGen only if was empty before this unscheduling.
891 // This is to avoid incorrect updating LiveRegGen set in previous run.
892 if (!LiveRegGens[Reg]) {
893 // Find the successor with the lowest height.
894 LiveRegGens[Reg] = Succ.getSUnit();
895 for (auto &Succ2 : SU->Succs) {
896 if (Succ2.isAssignedRegDep() && Succ2.getReg() == Reg &&
897 Succ2.getSUnit()->getHeight() < LiveRegGens[Reg]->getHeight())
898 LiveRegGens[Reg] = Succ2.getSUnit();
899 }
900 }
901 }
902 }
903 if (SU->getHeight() < MinAvailableCycle)
904 MinAvailableCycle = SU->getHeight();
905
906 SU->setHeightDirty();
907 SU->isScheduled = false;
908 SU->isAvailable = true;
909 if (!DisableSchedCycles && AvailableQueue->hasReadyFilter()) {
910 // Don't make available until backtracking is complete.
911 SU->isPending = true;
912 PendingQueue.push_back(x: SU);
913 }
914 else {
915 AvailableQueue->push(U: SU);
916 }
917 AvailableQueue->unscheduledNode(SU);
918}
919
920/// After backtracking, the hazard checker needs to be restored to a state
921/// corresponding the current cycle.
922void ScheduleDAGRRList::RestoreHazardCheckerBottomUp() {
923 HazardRec->Reset();
924
925 unsigned LookAhead = std::min(a: (unsigned)Sequence.size(),
926 b: HazardRec->getMaxLookAhead());
927 if (LookAhead == 0)
928 return;
929
930 std::vector<SUnit *>::const_iterator I = (Sequence.end() - LookAhead);
931 unsigned HazardCycle = (*I)->getHeight();
932 for (auto E = Sequence.end(); I != E; ++I) {
933 SUnit *SU = *I;
934 for (; SU->getHeight() > HazardCycle; ++HazardCycle) {
935 HazardRec->RecedeCycle();
936 }
937 EmitNode(SU);
938 }
939}
940
941/// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in
942/// BTCycle in order to schedule a specific node.
943void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, SUnit *BtSU) {
944 SUnit *OldSU = Sequence.back();
945 while (true) {
946 Sequence.pop_back();
947 // FIXME: use ready cycle instead of height
948 CurCycle = OldSU->getHeight();
949 UnscheduleNodeBottomUp(SU: OldSU);
950 AvailableQueue->setCurCycle(CurCycle);
951 if (OldSU == BtSU)
952 break;
953 OldSU = Sequence.back();
954 }
955
956 assert(!SU->isSucc(OldSU) && "Something is wrong!");
957
958 RestoreHazardCheckerBottomUp();
959
960 ReleasePending();
961
962 ++NumBacktracks;
963}
964
965static bool isOperandOf(const SUnit *SU, SDNode *N) {
966 for (const SDNode *SUNode = SU->getNode(); SUNode;
967 SUNode = SUNode->getGluedNode()) {
968 if (SUNode->isOperandOf(N))
969 return true;
970 }
971 return false;
972}
973
974/// TryUnfold - Attempt to unfold
975SUnit *ScheduleDAGRRList::TryUnfoldSU(SUnit *SU) {
976 SDNode *N = SU->getNode();
977 // Use while over if to ease fall through.
978 SmallVector<SDNode *, 2> NewNodes;
979 if (!TII->unfoldMemoryOperand(DAG&: *DAG, N, NewNodes))
980 return nullptr;
981
982 assert(NewNodes.size() == 2 && "Expected a load folding node!");
983
984 N = NewNodes[1];
985 SDNode *LoadNode = NewNodes[0];
986 unsigned NumVals = N->getNumValues();
987 unsigned OldNumVals = SU->getNode()->getNumValues();
988
989 // LoadNode may already exist. This can happen when there is another
990 // load from the same location and producing the same type of value
991 // but it has different alignment or volatileness.
992 bool isNewLoad = true;
993 SUnit *LoadSU;
994 if (LoadNode->getNodeId() != -1) {
995 LoadSU = &SUnits[LoadNode->getNodeId()];
996 // If LoadSU has already been scheduled, we should clone it but
997 // this would negate the benefit to unfolding so just return SU.
998 if (LoadSU->isScheduled)
999 return SU;
1000 isNewLoad = false;
1001 } else {
1002 LoadSU = CreateNewSUnit(N: LoadNode);
1003 LoadNode->setNodeId(LoadSU->NodeNum);
1004
1005 InitNumRegDefsLeft(SU: LoadSU);
1006 computeLatency(SU: LoadSU);
1007 }
1008
1009 bool isNewN = true;
1010 SUnit *NewSU;
1011 // This can only happen when isNewLoad is false.
1012 if (N->getNodeId() != -1) {
1013 NewSU = &SUnits[N->getNodeId()];
1014 // If NewSU has already been scheduled, we need to clone it, but this
1015 // negates the benefit to unfolding so just return SU.
1016 if (NewSU->isScheduled) {
1017 return SU;
1018 }
1019 isNewN = false;
1020 } else {
1021 NewSU = CreateNewSUnit(N);
1022 N->setNodeId(NewSU->NodeNum);
1023
1024 const MCInstrDesc &MCID = TII->get(Opcode: N->getMachineOpcode());
1025 for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
1026 if (MCID.getOperandConstraint(OpNum: i, Constraint: MCOI::TIED_TO) != -1) {
1027 NewSU->isTwoAddress = true;
1028 break;
1029 }
1030 }
1031 if (MCID.isCommutable())
1032 NewSU->isCommutable = true;
1033
1034 InitNumRegDefsLeft(SU: NewSU);
1035 computeLatency(SU: NewSU);
1036 }
1037
1038 LLVM_DEBUG(dbgs() << "Unfolding SU #" << SU->NodeNum << "\n");
1039
1040 // Now that we are committed to unfolding replace DAG Uses.
1041 for (unsigned i = 0; i != NumVals; ++i)
1042 DAG->ReplaceAllUsesOfValueWith(From: SDValue(SU->getNode(), i), To: SDValue(N, i));
1043 DAG->ReplaceAllUsesOfValueWith(From: SDValue(SU->getNode(), OldNumVals - 1),
1044 To: SDValue(LoadNode, 1));
1045
1046 // Record all the edges to and from the old SU, by category.
1047 SmallVector<SDep, 4> ChainPreds;
1048 SmallVector<SDep, 4> ChainSuccs;
1049 SmallVector<SDep, 4> LoadPreds;
1050 SmallVector<SDep, 4> NodePreds;
1051 SmallVector<SDep, 4> NodeSuccs;
1052 for (SDep &Pred : SU->Preds) {
1053 if (Pred.isCtrl())
1054 ChainPreds.push_back(Elt: Pred);
1055 else if (isOperandOf(SU: Pred.getSUnit(), N: LoadNode))
1056 LoadPreds.push_back(Elt: Pred);
1057 else
1058 NodePreds.push_back(Elt: Pred);
1059 }
1060 for (SDep &Succ : SU->Succs) {
1061 if (Succ.isCtrl())
1062 ChainSuccs.push_back(Elt: Succ);
1063 else
1064 NodeSuccs.push_back(Elt: Succ);
1065 }
1066
1067 // Now assign edges to the newly-created nodes.
1068 for (const SDep &Pred : ChainPreds) {
1069 RemovePred(SU, D: Pred);
1070 if (isNewLoad)
1071 AddPredQueued(SU: LoadSU, D: Pred);
1072 }
1073 for (const SDep &Pred : LoadPreds) {
1074 RemovePred(SU, D: Pred);
1075 if (isNewLoad)
1076 AddPredQueued(SU: LoadSU, D: Pred);
1077 }
1078 for (const SDep &Pred : NodePreds) {
1079 RemovePred(SU, D: Pred);
1080 AddPredQueued(SU: NewSU, D: Pred);
1081 }
1082 for (SDep &D : NodeSuccs) {
1083 SUnit *SuccDep = D.getSUnit();
1084 D.setSUnit(SU);
1085 RemovePred(SU: SuccDep, D);
1086 D.setSUnit(NewSU);
1087 AddPredQueued(SU: SuccDep, D);
1088 // Balance register pressure.
1089 if (AvailableQueue->tracksRegPressure() && SuccDep->isScheduled &&
1090 !D.isCtrl() && NewSU->NumRegDefsLeft > 0)
1091 --NewSU->NumRegDefsLeft;
1092 }
1093 for (SDep &D : ChainSuccs) {
1094 SUnit *SuccDep = D.getSUnit();
1095 D.setSUnit(SU);
1096 RemovePred(SU: SuccDep, D);
1097 if (isNewLoad) {
1098 D.setSUnit(LoadSU);
1099 AddPredQueued(SU: SuccDep, D);
1100 }
1101 }
1102
1103 // Add a data dependency to reflect that NewSU reads the value defined
1104 // by LoadSU.
1105 SDep D(LoadSU, SDep::Data, 0);
1106 D.setLatency(LoadSU->Latency);
1107 AddPredQueued(SU: NewSU, D);
1108
1109 if (isNewLoad)
1110 AvailableQueue->addNode(SU: LoadSU);
1111 if (isNewN)
1112 AvailableQueue->addNode(SU: NewSU);
1113
1114 ++NumUnfolds;
1115
1116 if (NewSU->NumSuccsLeft == 0)
1117 NewSU->isAvailable = true;
1118
1119 return NewSU;
1120}
1121
1122/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
1123/// successors to the newly created node.
1124SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
1125 SDNode *N = SU->getNode();
1126 if (!N)
1127 return nullptr;
1128
1129 LLVM_DEBUG(dbgs() << "Considering duplicating the SU\n");
1130 LLVM_DEBUG(dumpNode(*SU));
1131
1132 if (N->getGluedNode() &&
1133 !TII->canCopyGluedNodeDuringSchedule(N)) {
1134 LLVM_DEBUG(
1135 dbgs()
1136 << "Giving up because it has incoming glue and the target does not "
1137 "want to copy it\n");
1138 return nullptr;
1139 }
1140
1141 SUnit *NewSU;
1142 bool TryUnfold = false;
1143 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
1144 MVT VT = N->getSimpleValueType(ResNo: i);
1145 if (VT == MVT::Glue) {
1146 LLVM_DEBUG(dbgs() << "Giving up because it has outgoing glue\n");
1147 return nullptr;
1148 } else if (VT == MVT::Other)
1149 TryUnfold = true;
1150 }
1151 for (const SDValue &Op : N->op_values()) {
1152 MVT VT = Op.getNode()->getSimpleValueType(ResNo: Op.getResNo());
1153 if (VT == MVT::Glue && !TII->canCopyGluedNodeDuringSchedule(N)) {
1154 LLVM_DEBUG(
1155 dbgs() << "Giving up because it one of the operands is glue and "
1156 "the target does not want to copy it\n");
1157 return nullptr;
1158 }
1159 }
1160
1161 // If possible unfold instruction.
1162 if (TryUnfold) {
1163 SUnit *UnfoldSU = TryUnfoldSU(SU);
1164 if (!UnfoldSU)
1165 return nullptr;
1166 SU = UnfoldSU;
1167 N = SU->getNode();
1168 // If this can be scheduled don't bother duplicating and just return
1169 if (SU->NumSuccsLeft == 0)
1170 return SU;
1171 }
1172
1173 LLVM_DEBUG(dbgs() << " Duplicating SU #" << SU->NodeNum << "\n");
1174 NewSU = CreateClone(N: SU);
1175
1176 // New SUnit has the exact same predecessors.
1177 for (SDep &Pred : SU->Preds)
1178 if (!Pred.isArtificial())
1179 AddPredQueued(SU: NewSU, D: Pred);
1180
1181 // Make sure the clone comes after the original. (InstrEmitter assumes
1182 // this ordering.)
1183 AddPredQueued(SU: NewSU, D: SDep(SU, SDep::Artificial));
1184
1185 // Only copy scheduled successors. Cut them from old node's successor
1186 // list and move them over.
1187 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
1188 for (SDep &Succ : SU->Succs) {
1189 if (Succ.isArtificial())
1190 continue;
1191 SUnit *SuccSU = Succ.getSUnit();
1192 if (SuccSU->isScheduled) {
1193 SDep D = Succ;
1194 D.setSUnit(NewSU);
1195 AddPredQueued(SU: SuccSU, D);
1196 D.setSUnit(SU);
1197 DelDeps.emplace_back(Args&: SuccSU, Args&: D);
1198 }
1199 }
1200 for (const auto &[DelSU, DelD] : DelDeps)
1201 RemovePred(SU: DelSU, D: DelD);
1202
1203 AvailableQueue->updateNode(SU);
1204 AvailableQueue->addNode(SU: NewSU);
1205
1206 ++NumDups;
1207 return NewSU;
1208}
1209
1210/// InsertCopiesAndMoveSuccs - Insert register copies and move all
1211/// scheduled successors of the given SUnit to the last copy.
1212void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
1213 const TargetRegisterClass *DestRC,
1214 const TargetRegisterClass *SrcRC,
1215 SmallVectorImpl<SUnit*> &Copies) {
1216 SUnit *CopyFromSU = CreateNewSUnit(N: nullptr);
1217 CopyFromSU->CopySrcRC = SrcRC;
1218 CopyFromSU->CopyDstRC = DestRC;
1219
1220 SUnit *CopyToSU = CreateNewSUnit(N: nullptr);
1221 CopyToSU->CopySrcRC = DestRC;
1222 CopyToSU->CopyDstRC = SrcRC;
1223
1224 // Only copy scheduled successors. Cut them from old node's successor
1225 // list and move them over.
1226 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
1227 for (SDep &Succ : SU->Succs) {
1228 if (Succ.isArtificial())
1229 continue;
1230 SUnit *SuccSU = Succ.getSUnit();
1231 if (SuccSU->isScheduled) {
1232 SDep D = Succ;
1233 D.setSUnit(CopyToSU);
1234 AddPredQueued(SU: SuccSU, D);
1235 DelDeps.emplace_back(Args&: SuccSU, Args&: Succ);
1236 }
1237 else {
1238 // Avoid scheduling the def-side copy before other successors. Otherwise,
1239 // we could introduce another physreg interference on the copy and
1240 // continue inserting copies indefinitely.
1241 AddPredQueued(SU: SuccSU, D: SDep(CopyFromSU, SDep::Artificial));
1242 }
1243 }
1244 for (const auto &[DelSU, DelD] : DelDeps)
1245 RemovePred(SU: DelSU, D: DelD);
1246
1247 SDep FromDep(SU, SDep::Data, Reg);
1248 FromDep.setLatency(SU->Latency);
1249 AddPredQueued(SU: CopyFromSU, D: FromDep);
1250 SDep ToDep(CopyFromSU, SDep::Data, 0);
1251 ToDep.setLatency(CopyFromSU->Latency);
1252 AddPredQueued(SU: CopyToSU, D: ToDep);
1253
1254 AvailableQueue->updateNode(SU);
1255 AvailableQueue->addNode(SU: CopyFromSU);
1256 AvailableQueue->addNode(SU: CopyToSU);
1257 Copies.push_back(Elt: CopyFromSU);
1258 Copies.push_back(Elt: CopyToSU);
1259
1260 ++NumPRCopies;
1261}
1262
1263/// CheckForLiveRegDef - Return true and update live register vector if the
1264/// specified register def of the specified SUnit clobbers any "live" registers.
1265static void CheckForLiveRegDef(SUnit *SU, MCRegister Reg, SUnit **LiveRegDefs,
1266 SmallSet<unsigned, 4> &RegAdded,
1267 SmallVectorImpl<unsigned> &LRegs,
1268 const TargetRegisterInfo *TRI,
1269 const SDNode *Node = nullptr) {
1270 for (MCRegAliasIterator AliasI(Reg, TRI, true); AliasI.isValid(); ++AliasI) {
1271
1272 // Check if Ref is live.
1273 if (!LiveRegDefs[*AliasI]) continue;
1274
1275 // Allow multiple uses of the same def.
1276 if (LiveRegDefs[*AliasI] == SU) continue;
1277
1278 // Allow multiple uses of same def
1279 if (Node && LiveRegDefs[*AliasI]->getNode() == Node)
1280 continue;
1281
1282 // Add Reg to the set of interfering live regs.
1283 if (RegAdded.insert(V: *AliasI).second) {
1284 LRegs.push_back(Elt: *AliasI);
1285 }
1286 }
1287}
1288
1289/// CheckForLiveRegDefMasked - Check for any live physregs that are clobbered
1290/// by RegMask, and add them to LRegs.
1291static void CheckForLiveRegDefMasked(SUnit *SU, const uint32_t *RegMask,
1292 ArrayRef<SUnit*> LiveRegDefs,
1293 SmallSet<unsigned, 4> &RegAdded,
1294 SmallVectorImpl<unsigned> &LRegs) {
1295 // Look at all live registers. Skip Reg0 and the special CallResource.
1296 for (unsigned i = 1, e = LiveRegDefs.size()-1; i != e; ++i) {
1297 if (!LiveRegDefs[i]) continue;
1298 if (LiveRegDefs[i] == SU) continue;
1299 if (!MachineOperand::clobbersPhysReg(RegMask, PhysReg: i)) continue;
1300 if (RegAdded.insert(V: i).second)
1301 LRegs.push_back(Elt: i);
1302 }
1303}
1304
1305/// getNodeRegMask - Returns the register mask attached to an SDNode, if any.
1306static const uint32_t *getNodeRegMask(const SDNode *N) {
1307 for (const SDValue &Op : N->op_values())
1308 if (const auto *RegOp = dyn_cast<RegisterMaskSDNode>(Val: Op.getNode()))
1309 return RegOp->getRegMask();
1310 return nullptr;
1311}
1312
1313/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
1314/// scheduling of the given node to satisfy live physical register dependencies.
1315/// If the specific node is the last one that's available to schedule, do
1316/// whatever is necessary (i.e. backtracking or cloning) to make it possible.
1317bool ScheduleDAGRRList::
1318DelayForLiveRegsBottomUp(SUnit *SU, SmallVectorImpl<unsigned> &LRegs) {
1319 if (NumLiveRegs == 0)
1320 return false;
1321
1322 SmallSet<unsigned, 4> RegAdded;
1323 // If this node would clobber any "live" register, then it's not ready.
1324 //
1325 // If SU is the currently live definition of the same register that it uses,
1326 // then we are free to schedule it.
1327 for (SDep &Pred : SU->Preds) {
1328 if (Pred.isAssignedRegDep() && LiveRegDefs[Pred.getReg()] != SU)
1329 CheckForLiveRegDef(SU: Pred.getSUnit(), Reg: Pred.getReg(), LiveRegDefs: LiveRegDefs.get(),
1330 RegAdded, LRegs, TRI);
1331 }
1332
1333 for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode()) {
1334 if (Node->getOpcode() == ISD::INLINEASM ||
1335 Node->getOpcode() == ISD::INLINEASM_BR) {
1336 // Inline asm can clobber physical defs.
1337 unsigned NumOps = Node->getNumOperands();
1338 if (Node->getOperand(Num: NumOps-1).getValueType() == MVT::Glue)
1339 --NumOps; // Ignore the glue operand.
1340
1341 for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) {
1342 unsigned Flags = Node->getConstantOperandVal(Num: i);
1343 const InlineAsm::Flag F(Flags);
1344 unsigned NumVals = F.getNumOperandRegisters();
1345
1346 ++i; // Skip the ID value.
1347 if (F.isRegDefKind() || F.isRegDefEarlyClobberKind() ||
1348 F.isClobberKind()) {
1349 // Check for def of register or earlyclobber register.
1350 for (; NumVals; --NumVals, ++i) {
1351 Register Reg = cast<RegisterSDNode>(Val: Node->getOperand(Num: i))->getReg();
1352 if (Reg.isPhysical())
1353 CheckForLiveRegDef(SU, Reg, LiveRegDefs: LiveRegDefs.get(), RegAdded, LRegs, TRI);
1354 }
1355 } else
1356 i += NumVals;
1357 }
1358 continue;
1359 }
1360
1361 if (Node->getOpcode() == ISD::CopyToReg) {
1362 Register Reg = cast<RegisterSDNode>(Val: Node->getOperand(Num: 1))->getReg();
1363 if (Reg.isPhysical()) {
1364 SDNode *SrcNode = Node->getOperand(Num: 2).getNode();
1365 CheckForLiveRegDef(SU, Reg, LiveRegDefs: LiveRegDefs.get(), RegAdded, LRegs, TRI,
1366 Node: SrcNode);
1367 }
1368 }
1369
1370 if (!Node->isMachineOpcode())
1371 continue;
1372 // If we're in the middle of scheduling a call, don't begin scheduling
1373 // another call. Also, don't allow any physical registers to be live across
1374 // the call.
1375 if (Node->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
1376 // Check the special calling-sequence resource.
1377 unsigned CallResource = TRI->getNumRegs();
1378 if (LiveRegDefs[CallResource]) {
1379 SDNode *Gen = LiveRegGens[CallResource]->getNode();
1380 while (SDNode *Glued = Gen->getGluedNode())
1381 Gen = Glued;
1382 if (!IsChainDependent(Outer: Gen, Inner: Node, NestLevel: 0, TII) &&
1383 RegAdded.insert(V: CallResource).second)
1384 LRegs.push_back(Elt: CallResource);
1385 }
1386 }
1387 if (const uint32_t *RegMask = getNodeRegMask(N: Node))
1388 CheckForLiveRegDefMasked(SU, RegMask,
1389 LiveRegDefs: ArrayRef(LiveRegDefs.get(), TRI->getNumRegs()),
1390 RegAdded, LRegs);
1391
1392 const MCInstrDesc &MCID = TII->get(Opcode: Node->getMachineOpcode());
1393 if (MCID.hasOptionalDef()) {
1394 // Most ARM instructions have an OptionalDef for CPSR, to model the S-bit.
1395 // This operand can be either a def of CPSR, if the S bit is set; or a use
1396 // of %noreg. When the OptionalDef is set to a valid register, we need to
1397 // handle it in the same way as an ImplicitDef.
1398 for (unsigned i = 0; i < MCID.getNumDefs(); ++i)
1399 if (MCID.operands()[i].isOptionalDef()) {
1400 const SDValue &OptionalDef = Node->getOperand(Num: i - Node->getNumValues());
1401 Register Reg = cast<RegisterSDNode>(Val: OptionalDef)->getReg();
1402 CheckForLiveRegDef(SU, Reg, LiveRegDefs: LiveRegDefs.get(), RegAdded, LRegs, TRI);
1403 }
1404 }
1405 for (MCPhysReg Reg : MCID.implicit_defs())
1406 CheckForLiveRegDef(SU, Reg, LiveRegDefs: LiveRegDefs.get(), RegAdded, LRegs, TRI);
1407 }
1408
1409 return !LRegs.empty();
1410}
1411
1412void ScheduleDAGRRList::releaseInterferences(unsigned Reg) {
1413 // Add the nodes that aren't ready back onto the available list.
1414 for (unsigned i = Interferences.size(); i > 0; --i) {
1415 SUnit *SU = Interferences[i-1];
1416 LRegsMapT::iterator LRegsPos = LRegsMap.find(Val: SU);
1417 if (Reg) {
1418 SmallVectorImpl<unsigned> &LRegs = LRegsPos->second;
1419 if (!is_contained(Range&: LRegs, Element: Reg))
1420 continue;
1421 }
1422 SU->isPending = false;
1423 // The interfering node may no longer be available due to backtracking.
1424 // Furthermore, it may have been made available again, in which case it is
1425 // now already in the AvailableQueue.
1426 if (SU->isAvailable && !SU->NodeQueueId) {
1427 LLVM_DEBUG(dbgs() << " Repushing SU #" << SU->NodeNum << '\n');
1428 AvailableQueue->push(U: SU);
1429 }
1430 if (i < Interferences.size())
1431 Interferences[i-1] = Interferences.back();
1432 Interferences.pop_back();
1433 LRegsMap.erase(I: LRegsPos);
1434 }
1435}
1436
1437/// Return a node that can be scheduled in this cycle. Requirements:
1438/// (1) Ready: latency has been satisfied
1439/// (2) No Hazards: resources are available
1440/// (3) No Interferences: may unschedule to break register interferences.
1441SUnit *ScheduleDAGRRList::PickNodeToScheduleBottomUp() {
1442 SUnit *CurSU = AvailableQueue->empty() ? nullptr : AvailableQueue->pop();
1443 auto FindAvailableNode = [&]() {
1444 while (CurSU) {
1445 SmallVector<unsigned, 4> LRegs;
1446 if (!DelayForLiveRegsBottomUp(SU: CurSU, LRegs))
1447 break;
1448 LLVM_DEBUG(dbgs() << " Interfering reg ";
1449 if (LRegs[0] == TRI->getNumRegs()) dbgs() << "CallResource";
1450 else dbgs() << printReg(LRegs[0], TRI);
1451 dbgs() << " SU #" << CurSU->NodeNum << '\n');
1452 auto [LRegsIter, LRegsInserted] = LRegsMap.try_emplace(Key: CurSU, Args&: LRegs);
1453 if (LRegsInserted) {
1454 CurSU->isPending = true; // This SU is not in AvailableQueue right now.
1455 Interferences.push_back(Elt: CurSU);
1456 }
1457 else {
1458 assert(CurSU->isPending && "Interferences are pending");
1459 // Update the interference with current live regs.
1460 LRegsIter->second = LRegs;
1461 }
1462 CurSU = AvailableQueue->pop();
1463 }
1464 };
1465 FindAvailableNode();
1466 if (CurSU)
1467 return CurSU;
1468
1469 // We query the topological order in the loop body, so make sure outstanding
1470 // updates are applied before entering it (we only enter the loop if there
1471 // are some interferences). If we make changes to the ordering, we exit
1472 // the loop.
1473
1474 // All candidates are delayed due to live physical reg dependencies.
1475 // Try backtracking, code duplication, or inserting cross class copies
1476 // to resolve it.
1477 for (SUnit *TrySU : Interferences) {
1478 SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
1479
1480 // Try unscheduling up to the point where it's safe to schedule
1481 // this node.
1482 SUnit *BtSU = nullptr;
1483 unsigned LiveCycle = std::numeric_limits<unsigned>::max();
1484 for (unsigned Reg : LRegs) {
1485 if (LiveRegGens[Reg]->getHeight() < LiveCycle) {
1486 BtSU = LiveRegGens[Reg];
1487 LiveCycle = BtSU->getHeight();
1488 }
1489 }
1490 if (!WillCreateCycle(SU: TrySU, TargetSU: BtSU)) {
1491 // BacktrackBottomUp mutates Interferences!
1492 BacktrackBottomUp(SU: TrySU, BtSU);
1493
1494 // Force the current node to be scheduled before the node that
1495 // requires the physical reg dep.
1496 if (BtSU->isAvailable) {
1497 BtSU->isAvailable = false;
1498 if (!BtSU->isPending)
1499 AvailableQueue->remove(SU: BtSU);
1500 }
1501 LLVM_DEBUG(dbgs() << "ARTIFICIAL edge from SU(" << BtSU->NodeNum
1502 << ") to SU(" << TrySU->NodeNum << ")\n");
1503 AddPredQueued(SU: TrySU, D: SDep(BtSU, SDep::Artificial));
1504
1505 // If one or more successors has been unscheduled, then the current
1506 // node is no longer available.
1507 if (!TrySU->isAvailable || !TrySU->NodeQueueId) {
1508 LLVM_DEBUG(dbgs() << "TrySU not available; choosing node from queue\n");
1509 CurSU = AvailableQueue->pop();
1510 } else {
1511 LLVM_DEBUG(dbgs() << "TrySU available\n");
1512 // Available and in AvailableQueue
1513 AvailableQueue->remove(SU: TrySU);
1514 CurSU = TrySU;
1515 }
1516 FindAvailableNode();
1517 // Interferences has been mutated. We must break.
1518 break;
1519 }
1520 }
1521
1522 if (!CurSU) {
1523 // Can't backtrack. If it's too expensive to copy the value, then try
1524 // duplicate the nodes that produces these "too expensive to copy"
1525 // values to break the dependency. In case even that doesn't work,
1526 // insert cross class copies.
1527 // If it's not too expensive, i.e. cost != -1, issue copies.
1528 SUnit *TrySU = Interferences[0];
1529 SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
1530 assert(LRegs.size() == 1 && "Can't handle this yet!");
1531 unsigned Reg = LRegs[0];
1532 SUnit *LRDef = LiveRegDefs[Reg];
1533 const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
1534 const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
1535
1536 // If cross copy register class is the same as RC, then it must be possible
1537 // copy the value directly. Do not try duplicate the def.
1538 // If cross copy register class is not the same as RC, then it's possible to
1539 // copy the value but it require cross register class copies and it is
1540 // expensive.
1541 // If cross copy register class is null, then it's not possible to copy
1542 // the value at all.
1543 SUnit *NewDef = nullptr;
1544 if (DestRC != RC) {
1545 NewDef = CopyAndMoveSuccessors(SU: LRDef);
1546 if (!DestRC && !NewDef)
1547 report_fatal_error(reason: "Can't handle live physical register dependency!");
1548 }
1549 if (!NewDef) {
1550 // Issue copies, these can be expensive cross register class copies.
1551 SmallVector<SUnit*, 2> Copies;
1552 InsertCopiesAndMoveSuccs(SU: LRDef, Reg, DestRC, SrcRC: RC, Copies);
1553 LLVM_DEBUG(dbgs() << " Adding an edge from SU #" << TrySU->NodeNum
1554 << " to SU #" << Copies.front()->NodeNum << "\n");
1555 AddPredQueued(SU: TrySU, D: SDep(Copies.front(), SDep::Artificial));
1556 NewDef = Copies.back();
1557 }
1558
1559 LLVM_DEBUG(dbgs() << " Adding an edge from SU #" << NewDef->NodeNum
1560 << " to SU #" << TrySU->NodeNum << "\n");
1561 LiveRegDefs[Reg] = NewDef;
1562 AddPredQueued(SU: NewDef, D: SDep(TrySU, SDep::Artificial));
1563 TrySU->isAvailable = false;
1564 CurSU = NewDef;
1565 }
1566 assert(CurSU && "Unable to resolve live physical register dependencies!");
1567 return CurSU;
1568}
1569
1570/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
1571/// schedulers.
1572void ScheduleDAGRRList::ListScheduleBottomUp() {
1573 // Release any predecessors of the special Exit node.
1574 ReleasePredecessors(SU: &ExitSU);
1575
1576 // Add root to Available queue.
1577 if (!SUnits.empty()) {
1578 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
1579 assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
1580 RootSU->isAvailable = true;
1581 AvailableQueue->push(U: RootSU);
1582 }
1583
1584 // While Available queue is not empty, grab the node with the highest
1585 // priority. If it is not ready put it back. Schedule the node.
1586 Sequence.reserve(n: SUnits.size());
1587 while (!AvailableQueue->empty() || !Interferences.empty()) {
1588 LLVM_DEBUG(dbgs() << "\nExamining Available:\n";
1589 AvailableQueue->dump(this));
1590
1591 // Pick the best node to schedule taking all constraints into
1592 // consideration.
1593 SUnit *SU = PickNodeToScheduleBottomUp();
1594
1595 AdvancePastStalls(SU);
1596
1597 ScheduleNodeBottomUp(SU);
1598
1599 while (AvailableQueue->empty() && !PendingQueue.empty()) {
1600 // Advance the cycle to free resources. Skip ahead to the next ready SU.
1601 assert(MinAvailableCycle < std::numeric_limits<unsigned>::max() &&
1602 "MinAvailableCycle uninitialized");
1603 AdvanceToCycle(NextCycle: std::max(a: CurCycle + 1, b: MinAvailableCycle));
1604 }
1605 }
1606
1607 // Reverse the order if it is bottom up.
1608 std::reverse(first: Sequence.begin(), last: Sequence.end());
1609
1610#ifndef NDEBUG
1611 VerifyScheduledSequence(/*isBottomUp=*/true);
1612#endif
1613}
1614
1615namespace {
1616
1617class RegReductionPQBase;
1618
1619struct queue_sort {
1620 bool isReady(SUnit* SU, unsigned CurCycle) const { return true; }
1621};
1622
1623#ifndef NDEBUG
1624template<class SF>
1625struct reverse_sort : public queue_sort {
1626 SF &SortFunc;
1627
1628 reverse_sort(SF &sf) : SortFunc(sf) {}
1629
1630 bool operator()(SUnit* left, SUnit* right) const {
1631 // reverse left/right rather than simply !SortFunc(left, right)
1632 // to expose different paths in the comparison logic.
1633 return SortFunc(right, left);
1634 }
1635};
1636#endif // NDEBUG
1637
1638/// bu_ls_rr_sort - Priority function for bottom up register pressure
1639// reduction scheduler.
1640struct bu_ls_rr_sort : public queue_sort {
1641 enum {
1642 IsBottomUp = true,
1643 HasReadyFilter = false
1644 };
1645
1646 RegReductionPQBase *SPQ;
1647
1648 bu_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1649
1650 bool operator()(SUnit* left, SUnit* right) const;
1651};
1652
1653// src_ls_rr_sort - Priority function for source order scheduler.
1654struct src_ls_rr_sort : public queue_sort {
1655 enum {
1656 IsBottomUp = true,
1657 HasReadyFilter = false
1658 };
1659
1660 RegReductionPQBase *SPQ;
1661
1662 src_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1663
1664 bool operator()(SUnit* left, SUnit* right) const;
1665};
1666
1667// hybrid_ls_rr_sort - Priority function for hybrid scheduler.
1668struct hybrid_ls_rr_sort : public queue_sort {
1669 enum {
1670 IsBottomUp = true,
1671 HasReadyFilter = false
1672 };
1673
1674 RegReductionPQBase *SPQ;
1675
1676 hybrid_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1677
1678 bool isReady(SUnit *SU, unsigned CurCycle) const;
1679
1680 bool operator()(SUnit* left, SUnit* right) const;
1681};
1682
1683// ilp_ls_rr_sort - Priority function for ILP (instruction level parallelism)
1684// scheduler.
1685struct ilp_ls_rr_sort : public queue_sort {
1686 enum {
1687 IsBottomUp = true,
1688 HasReadyFilter = false
1689 };
1690
1691 RegReductionPQBase *SPQ;
1692
1693 ilp_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1694
1695 bool isReady(SUnit *SU, unsigned CurCycle) const;
1696
1697 bool operator()(SUnit* left, SUnit* right) const;
1698};
1699
1700class RegReductionPQBase : public SchedulingPriorityQueue {
1701protected:
1702 std::vector<SUnit *> Queue;
1703 unsigned CurQueueId = 0;
1704 bool TracksRegPressure;
1705 bool SrcOrder;
1706
1707 // SUnits - The SUnits for the current graph.
1708 std::vector<SUnit> *SUnits = nullptr;
1709
1710 MachineFunction &MF;
1711 const TargetInstrInfo *TII = nullptr;
1712 const TargetRegisterInfo *TRI = nullptr;
1713 const TargetLowering *TLI = nullptr;
1714 ScheduleDAGRRList *scheduleDAG = nullptr;
1715
1716 // SethiUllmanNumbers - The SethiUllman number for each node.
1717 std::vector<unsigned> SethiUllmanNumbers;
1718
1719 /// RegPressure - Tracking current reg pressure per register class.
1720 std::vector<unsigned> RegPressure;
1721
1722 /// RegLimit - Tracking the number of allocatable registers per register
1723 /// class.
1724 std::vector<unsigned> RegLimit;
1725
1726public:
1727 RegReductionPQBase(MachineFunction &mf,
1728 bool hasReadyFilter,
1729 bool tracksrp,
1730 bool srcorder,
1731 const TargetInstrInfo *tii,
1732 const TargetRegisterInfo *tri,
1733 const TargetLowering *tli)
1734 : SchedulingPriorityQueue(hasReadyFilter), TracksRegPressure(tracksrp),
1735 SrcOrder(srcorder), MF(mf), TII(tii), TRI(tri), TLI(tli) {
1736 if (TracksRegPressure) {
1737 unsigned NumRC = TRI->getNumRegClasses();
1738 RegLimit.resize(new_size: NumRC);
1739 RegPressure.resize(new_size: NumRC);
1740 llvm::fill(Range&: RegLimit, Value: 0);
1741 llvm::fill(Range&: RegPressure, Value: 0);
1742 for (const TargetRegisterClass &RC : TRI->regclasses())
1743 RegLimit[RC.getID()] = tri->getRegPressureLimit(RC: &RC, MF);
1744 }
1745 }
1746
1747 void setScheduleDAG(ScheduleDAGRRList *scheduleDag) {
1748 scheduleDAG = scheduleDag;
1749 }
1750
1751 ScheduleHazardRecognizer* getHazardRec() {
1752 return scheduleDAG->getHazardRec();
1753 }
1754
1755 void initNodes(std::vector<SUnit> &sunits) override;
1756
1757 void addNode(const SUnit *SU) override;
1758
1759 void updateNode(const SUnit *SU) override;
1760
1761 void releaseState() override {
1762 SUnits = nullptr;
1763 SethiUllmanNumbers.clear();
1764 llvm::fill(Range&: RegPressure, Value: 0);
1765 }
1766
1767 unsigned getNodePriority(const SUnit *SU) const;
1768
1769 unsigned getNodeOrdering(const SUnit *SU) const {
1770 if (!SU->getNode()) return 0;
1771
1772 return SU->getNode()->getIROrder();
1773 }
1774
1775 bool empty() const override { return Queue.empty(); }
1776
1777 void push(SUnit *U) override {
1778 assert(!U->NodeQueueId && "Node in the queue already");
1779 U->NodeQueueId = ++CurQueueId;
1780 Queue.push_back(x: U);
1781 }
1782
1783 void remove(SUnit *SU) override {
1784 assert(!Queue.empty() && "Queue is empty!");
1785 assert(SU->NodeQueueId != 0 && "Not in queue!");
1786 std::vector<SUnit *>::iterator I = llvm::find(Range&: Queue, Val: SU);
1787 if (I != std::prev(x: Queue.end()))
1788 std::swap(a&: *I, b&: Queue.back());
1789 Queue.pop_back();
1790 SU->NodeQueueId = 0;
1791 }
1792
1793 bool tracksRegPressure() const override { return TracksRegPressure; }
1794
1795 void dumpRegPressure() const;
1796
1797 bool HighRegPressure(const SUnit *SU) const;
1798
1799 bool MayReduceRegPressure(SUnit *SU) const;
1800
1801 int RegPressureDiff(SUnit *SU, unsigned &LiveUses) const;
1802
1803 void scheduledNode(SUnit *SU) override;
1804
1805 void unscheduledNode(SUnit *SU) override;
1806
1807protected:
1808 bool canClobber(const SUnit *SU, const SUnit *Op);
1809 void AddPseudoTwoAddrDeps();
1810 void PrescheduleNodesWithMultipleUses();
1811 void CalculateSethiUllmanNumbers();
1812};
1813
1814template<class SF>
1815static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, SF &Picker) {
1816 unsigned BestIdx = 0;
1817 // Only compute the cost for the first 1000 items in the queue, to avoid
1818 // excessive compile-times for very large queues.
1819 for (unsigned I = 1, E = std::min(a: Q.size(), b: (decltype(Q.size()))1000); I != E;
1820 I++)
1821 if (Picker(Q[BestIdx], Q[I]))
1822 BestIdx = I;
1823 SUnit *V = Q[BestIdx];
1824 if (BestIdx + 1 != Q.size())
1825 std::swap(a&: Q[BestIdx], b&: Q.back());
1826 Q.pop_back();
1827 return V;
1828}
1829
1830template<class SF>
1831SUnit *popFromQueue(std::vector<SUnit *> &Q, SF &Picker, ScheduleDAG *DAG) {
1832#ifndef NDEBUG
1833 if (DAG->StressSched) {
1834 reverse_sort<SF> RPicker(Picker);
1835 return popFromQueueImpl(Q, RPicker);
1836 }
1837#endif
1838 (void)DAG;
1839 return popFromQueueImpl(Q, Picker);
1840}
1841
1842//===----------------------------------------------------------------------===//
1843// RegReductionPriorityQueue Definition
1844//===----------------------------------------------------------------------===//
1845//
1846// This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
1847// to reduce register pressure.
1848//
1849template<class SF>
1850class RegReductionPriorityQueue : public RegReductionPQBase {
1851 SF Picker;
1852
1853public:
1854 RegReductionPriorityQueue(MachineFunction &mf,
1855 bool tracksrp,
1856 bool srcorder,
1857 const TargetInstrInfo *tii,
1858 const TargetRegisterInfo *tri,
1859 const TargetLowering *tli)
1860 : RegReductionPQBase(mf, SF::HasReadyFilter, tracksrp, srcorder,
1861 tii, tri, tli),
1862 Picker(this) {}
1863
1864 bool isBottomUp() const override { return SF::IsBottomUp; }
1865
1866 bool isReady(SUnit *U) const override {
1867 return Picker.HasReadyFilter && Picker.isReady(U, getCurCycle());
1868 }
1869
1870 SUnit *pop() override {
1871 if (Queue.empty()) return nullptr;
1872
1873 SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);
1874 V->NodeQueueId = 0;
1875 return V;
1876 }
1877
1878#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1879 LLVM_DUMP_METHOD void dump(ScheduleDAG *DAG) const override {
1880 // Emulate pop() without clobbering NodeQueueIds.
1881 std::vector<SUnit *> DumpQueue = Queue;
1882 SF DumpPicker = Picker;
1883 while (!DumpQueue.empty()) {
1884 SUnit *SU = popFromQueue(DumpQueue, DumpPicker, scheduleDAG);
1885 dbgs() << "Height " << SU->getHeight() << ": ";
1886 DAG->dumpNode(*SU);
1887 }
1888 }
1889#endif
1890};
1891
1892using BURegReductionPriorityQueue = RegReductionPriorityQueue<bu_ls_rr_sort>;
1893using SrcRegReductionPriorityQueue = RegReductionPriorityQueue<src_ls_rr_sort>;
1894using HybridBURRPriorityQueue = RegReductionPriorityQueue<hybrid_ls_rr_sort>;
1895using ILPBURRPriorityQueue = RegReductionPriorityQueue<ilp_ls_rr_sort>;
1896
1897} // end anonymous namespace
1898
1899//===----------------------------------------------------------------------===//
1900// Static Node Priority for Register Pressure Reduction
1901//===----------------------------------------------------------------------===//
1902
1903// Check for special nodes that bypass scheduling heuristics.
1904// Currently this pushes TokenFactor nodes down, but may be used for other
1905// pseudo-ops as well.
1906//
1907// Return -1 to schedule right above left, 1 for left above right.
1908// Return 0 if no bias exists.
1909static int checkSpecialNodes(const SUnit *left, const SUnit *right) {
1910 bool LSchedLow = left->isScheduleLow;
1911 bool RSchedLow = right->isScheduleLow;
1912 if (LSchedLow != RSchedLow)
1913 return LSchedLow < RSchedLow ? 1 : -1;
1914 return 0;
1915}
1916
1917/// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
1918/// Smaller number is the higher priority.
1919static unsigned
1920CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) {
1921 if (SUNumbers[SU->NodeNum] != 0)
1922 return SUNumbers[SU->NodeNum];
1923
1924 // Use WorkList to avoid stack overflow on excessively large IRs.
1925 struct WorkState {
1926 WorkState(const SUnit *SU) : SU(SU) {}
1927 const SUnit *SU;
1928 unsigned PredsProcessed = 0;
1929 };
1930
1931 SmallVector<WorkState, 16> WorkList;
1932 WorkList.push_back(Elt: SU);
1933 while (!WorkList.empty()) {
1934 auto &Temp = WorkList.back();
1935 auto *TempSU = Temp.SU;
1936 bool AllPredsKnown = true;
1937 // Try to find a non-evaluated pred and push it into the processing stack.
1938 for (unsigned P = Temp.PredsProcessed; P < TempSU->Preds.size(); ++P) {
1939 auto &Pred = TempSU->Preds[P];
1940 if (Pred.isCtrl()) continue; // ignore chain preds
1941 SUnit *PredSU = Pred.getSUnit();
1942 if (SUNumbers[PredSU->NodeNum] == 0) {
1943#ifndef NDEBUG
1944 // In debug mode, check that we don't have such element in the stack.
1945 for (auto It : WorkList)
1946 assert(It.SU != PredSU && "Trying to push an element twice?");
1947#endif
1948 // Next time start processing this one starting from the next pred.
1949 Temp.PredsProcessed = P + 1;
1950 WorkList.push_back(Elt: PredSU);
1951 AllPredsKnown = false;
1952 break;
1953 }
1954 }
1955
1956 if (!AllPredsKnown)
1957 continue;
1958
1959 // Once all preds are known, we can calculate the answer for this one.
1960 unsigned SethiUllmanNumber = 0;
1961 unsigned Extra = 0;
1962 for (const SDep &Pred : TempSU->Preds) {
1963 if (Pred.isCtrl()) continue; // ignore chain preds
1964 SUnit *PredSU = Pred.getSUnit();
1965 unsigned PredSethiUllman = SUNumbers[PredSU->NodeNum];
1966 assert(PredSethiUllman > 0 && "We should have evaluated this pred!");
1967 if (PredSethiUllman > SethiUllmanNumber) {
1968 SethiUllmanNumber = PredSethiUllman;
1969 Extra = 0;
1970 } else if (PredSethiUllman == SethiUllmanNumber)
1971 ++Extra;
1972 }
1973
1974 SethiUllmanNumber += Extra;
1975 if (SethiUllmanNumber == 0)
1976 SethiUllmanNumber = 1;
1977 SUNumbers[TempSU->NodeNum] = SethiUllmanNumber;
1978 WorkList.pop_back();
1979 }
1980
1981 assert(SUNumbers[SU->NodeNum] > 0 && "SethiUllman should never be zero!");
1982 return SUNumbers[SU->NodeNum];
1983}
1984
1985/// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
1986/// scheduling units.
1987void RegReductionPQBase::CalculateSethiUllmanNumbers() {
1988 SethiUllmanNumbers.assign(n: SUnits->size(), val: 0);
1989
1990 for (const SUnit &SU : *SUnits)
1991 CalcNodeSethiUllmanNumber(SU: &SU, SUNumbers&: SethiUllmanNumbers);
1992}
1993
1994void RegReductionPQBase::addNode(const SUnit *SU) {
1995 unsigned SUSize = SethiUllmanNumbers.size();
1996 if (SUnits->size() > SUSize)
1997 SethiUllmanNumbers.resize(new_size: SUSize*2, x: 0);
1998 CalcNodeSethiUllmanNumber(SU, SUNumbers&: SethiUllmanNumbers);
1999}
2000
2001void RegReductionPQBase::updateNode(const SUnit *SU) {
2002 SethiUllmanNumbers[SU->NodeNum] = 0;
2003 CalcNodeSethiUllmanNumber(SU, SUNumbers&: SethiUllmanNumbers);
2004}
2005
2006// Lower priority means schedule further down. For bottom-up scheduling, lower
2007// priority SUs are scheduled before higher priority SUs.
2008unsigned RegReductionPQBase::getNodePriority(const SUnit *SU) const {
2009 assert(SU->NodeNum < SethiUllmanNumbers.size());
2010 unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0;
2011 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
2012 // CopyToReg should be close to its uses to facilitate coalescing and
2013 // avoid spilling.
2014 return 0;
2015 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2016 Opc == TargetOpcode::SUBREG_TO_REG ||
2017 Opc == TargetOpcode::INSERT_SUBREG)
2018 // EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG nodes should be
2019 // close to their uses to facilitate coalescing.
2020 return 0;
2021 if (SU->NumSuccs == 0 && SU->NumPreds != 0)
2022 // If SU does not have a register use, i.e. it doesn't produce a value
2023 // that would be consumed (e.g. store), then it terminates a chain of
2024 // computation. Give it a large SethiUllman number so it will be
2025 // scheduled right before its predecessors that it doesn't lengthen
2026 // their live ranges.
2027 return 0xffff;
2028 if (SU->NumPreds == 0 && SU->NumSuccs != 0)
2029 // If SU does not have a register def, schedule it close to its uses
2030 // because it does not lengthen any live ranges.
2031 return 0;
2032#if 1
2033 return SethiUllmanNumbers[SU->NodeNum];
2034#else
2035 unsigned Priority = SethiUllmanNumbers[SU->NodeNum];
2036 if (SU->isCallOp) {
2037 // FIXME: This assumes all of the defs are used as call operands.
2038 int NP = (int)Priority - SU->getNode()->getNumValues();
2039 return (NP > 0) ? NP : 0;
2040 }
2041 return Priority;
2042#endif
2043}
2044
2045//===----------------------------------------------------------------------===//
2046// Register Pressure Tracking
2047//===----------------------------------------------------------------------===//
2048
2049#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2050LLVM_DUMP_METHOD void RegReductionPQBase::dumpRegPressure() const {
2051 for (const TargetRegisterClass &RC : TRI->regclasses()) {
2052 unsigned Id = RC.getID();
2053 unsigned RP = RegPressure[Id];
2054 if (!RP) continue;
2055 LLVM_DEBUG(dbgs() << TRI->getRegClassName(&RC) << ": " << RP << " / "
2056 << RegLimit[Id] << '\n');
2057 }
2058}
2059#endif
2060
2061bool RegReductionPQBase::HighRegPressure(const SUnit *SU) const {
2062 if (!TLI)
2063 return false;
2064
2065 for (const SDep &Pred : SU->Preds) {
2066 if (Pred.isCtrl())
2067 continue;
2068 SUnit *PredSU = Pred.getSUnit();
2069 // NumRegDefsLeft is zero when enough uses of this node have been scheduled
2070 // to cover the number of registers defined (they are all live).
2071 if (PredSU->NumRegDefsLeft == 0) {
2072 continue;
2073 }
2074 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);
2075 RegDefPos.IsValid(); RegDefPos.Advance()) {
2076 unsigned RCId, Cost;
2077 GetCostForDef(RegDefPos, TLI, TII, TRI, RegClass&: RCId, Cost, MF);
2078
2079 if ((RegPressure[RCId] + Cost) >= RegLimit[RCId])
2080 return true;
2081 }
2082 }
2083 return false;
2084}
2085
2086bool RegReductionPQBase::MayReduceRegPressure(SUnit *SU) const {
2087 const SDNode *N = SU->getNode();
2088
2089 if (!N->isMachineOpcode() || !SU->NumSuccs)
2090 return false;
2091
2092 unsigned NumDefs = TII->get(Opcode: N->getMachineOpcode()).getNumDefs();
2093 for (unsigned i = 0; i != NumDefs; ++i) {
2094 MVT VT = N->getSimpleValueType(ResNo: i);
2095 if (!N->hasAnyUseOfValue(Value: i))
2096 continue;
2097 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2098 if (RegPressure[RCId] >= RegLimit[RCId])
2099 return true;
2100 }
2101 return false;
2102}
2103
2104// Compute the register pressure contribution by this instruction by count up
2105// for uses that are not live and down for defs. Only count register classes
2106// that are already under high pressure. As a side effect, compute the number of
2107// uses of registers that are already live.
2108//
2109// FIXME: This encompasses the logic in HighRegPressure and MayReduceRegPressure
2110// so could probably be factored.
2111int RegReductionPQBase::RegPressureDiff(SUnit *SU, unsigned &LiveUses) const {
2112 LiveUses = 0;
2113 int PDiff = 0;
2114 for (const SDep &Pred : SU->Preds) {
2115 if (Pred.isCtrl())
2116 continue;
2117 SUnit *PredSU = Pred.getSUnit();
2118 // NumRegDefsLeft is zero when enough uses of this node have been scheduled
2119 // to cover the number of registers defined (they are all live).
2120 if (PredSU->NumRegDefsLeft == 0) {
2121 if (PredSU->getNode()->isMachineOpcode())
2122 ++LiveUses;
2123 continue;
2124 }
2125 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);
2126 RegDefPos.IsValid(); RegDefPos.Advance()) {
2127 MVT VT = RegDefPos.GetValue();
2128 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2129 if (RegPressure[RCId] >= RegLimit[RCId])
2130 ++PDiff;
2131 }
2132 }
2133 const SDNode *N = SU->getNode();
2134
2135 if (!N || !N->isMachineOpcode() || !SU->NumSuccs)
2136 return PDiff;
2137
2138 unsigned NumDefs = TII->get(Opcode: N->getMachineOpcode()).getNumDefs();
2139 for (unsigned i = 0; i != NumDefs; ++i) {
2140 MVT VT = N->getSimpleValueType(ResNo: i);
2141 if (!N->hasAnyUseOfValue(Value: i))
2142 continue;
2143 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2144 if (RegPressure[RCId] >= RegLimit[RCId])
2145 --PDiff;
2146 }
2147 return PDiff;
2148}
2149
2150void RegReductionPQBase::scheduledNode(SUnit *SU) {
2151 if (!TracksRegPressure)
2152 return;
2153
2154 if (!SU->getNode())
2155 return;
2156
2157 for (const SDep &Pred : SU->Preds) {
2158 if (Pred.isCtrl())
2159 continue;
2160 SUnit *PredSU = Pred.getSUnit();
2161 // NumRegDefsLeft is zero when enough uses of this node have been scheduled
2162 // to cover the number of registers defined (they are all live).
2163 if (PredSU->NumRegDefsLeft == 0) {
2164 continue;
2165 }
2166 // FIXME: The ScheduleDAG currently loses information about which of a
2167 // node's values is consumed by each dependence. Consequently, if the node
2168 // defines multiple register classes, we don't know which to pressurize
2169 // here. Instead the following loop consumes the register defs in an
2170 // arbitrary order. At least it handles the common case of clustered loads
2171 // to the same class. For precise liveness, each SDep needs to indicate the
2172 // result number. But that tightly couples the ScheduleDAG with the
2173 // SelectionDAG making updates tricky. A simpler hack would be to attach a
2174 // value type or register class to SDep.
2175 //
2176 // The most important aspect of register tracking is balancing the increase
2177 // here with the reduction further below. Note that this SU may use multiple
2178 // defs in PredSU. The can't be determined here, but we've already
2179 // compensated by reducing NumRegDefsLeft in PredSU during
2180 // ScheduleDAGSDNodes::AddSchedEdges.
2181 --PredSU->NumRegDefsLeft;
2182 unsigned SkipRegDefs = PredSU->NumRegDefsLeft;
2183 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);
2184 RegDefPos.IsValid(); RegDefPos.Advance(), --SkipRegDefs) {
2185 if (SkipRegDefs)
2186 continue;
2187
2188 unsigned RCId, Cost;
2189 GetCostForDef(RegDefPos, TLI, TII, TRI, RegClass&: RCId, Cost, MF);
2190 RegPressure[RCId] += Cost;
2191 break;
2192 }
2193 }
2194
2195 // We should have this assert, but there may be dead SDNodes that never
2196 // materialize as SUnits, so they don't appear to generate liveness.
2197 //assert(SU->NumRegDefsLeft == 0 && "not all regdefs have scheduled uses");
2198 int SkipRegDefs = (int)SU->NumRegDefsLeft;
2199 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(SU, scheduleDAG);
2200 RegDefPos.IsValid(); RegDefPos.Advance(), --SkipRegDefs) {
2201 if (SkipRegDefs > 0)
2202 continue;
2203 unsigned RCId, Cost;
2204 GetCostForDef(RegDefPos, TLI, TII, TRI, RegClass&: RCId, Cost, MF);
2205 if (RegPressure[RCId] < Cost) {
2206 // Register pressure tracking is imprecise. This can happen. But we try
2207 // hard not to let it happen because it likely results in poor scheduling.
2208 LLVM_DEBUG(dbgs() << " SU(" << SU->NodeNum
2209 << ") has too many regdefs\n");
2210 RegPressure[RCId] = 0;
2211 }
2212 else {
2213 RegPressure[RCId] -= Cost;
2214 }
2215 }
2216 LLVM_DEBUG(dumpRegPressure());
2217}
2218
2219void RegReductionPQBase::unscheduledNode(SUnit *SU) {
2220 if (!TracksRegPressure)
2221 return;
2222
2223 const SDNode *N = SU->getNode();
2224 if (!N) return;
2225
2226 if (!N->isMachineOpcode()) {
2227 if (N->getOpcode() != ISD::CopyToReg)
2228 return;
2229 } else {
2230 unsigned Opc = N->getMachineOpcode();
2231 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2232 Opc == TargetOpcode::INSERT_SUBREG ||
2233 Opc == TargetOpcode::SUBREG_TO_REG ||
2234 Opc == TargetOpcode::REG_SEQUENCE ||
2235 Opc == TargetOpcode::IMPLICIT_DEF)
2236 return;
2237 }
2238
2239 for (const SDep &Pred : SU->Preds) {
2240 if (Pred.isCtrl())
2241 continue;
2242 SUnit *PredSU = Pred.getSUnit();
2243 // NumSuccsLeft counts all deps. Don't compare it with NumSuccs which only
2244 // counts data deps.
2245 if (PredSU->NumSuccsLeft != PredSU->Succs.size())
2246 continue;
2247 const SDNode *PN = PredSU->getNode();
2248 if (!PN->isMachineOpcode()) {
2249 if (PN->getOpcode() == ISD::CopyFromReg) {
2250 MVT VT = PN->getSimpleValueType(ResNo: 0);
2251 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2252 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
2253 }
2254 continue;
2255 }
2256 unsigned POpc = PN->getMachineOpcode();
2257 if (POpc == TargetOpcode::IMPLICIT_DEF)
2258 continue;
2259 if (POpc == TargetOpcode::EXTRACT_SUBREG ||
2260 POpc == TargetOpcode::INSERT_SUBREG ||
2261 POpc == TargetOpcode::SUBREG_TO_REG) {
2262 MVT VT = PN->getSimpleValueType(ResNo: 0);
2263 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2264 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
2265 continue;
2266 }
2267 if (POpc == TargetOpcode::REG_SEQUENCE) {
2268 unsigned DstRCIdx = PN->getConstantOperandVal(Num: 0);
2269 const TargetRegisterClass *RC = TRI->getRegClass(i: DstRCIdx);
2270 unsigned RCId = RC->getID();
2271 // REG_SEQUENCE is untyped, so getRepRegClassCostFor could not be used
2272 // here. Instead use the same constant as in GetCostForDef.
2273 RegPressure[RCId] += RegSequenceCost;
2274 continue;
2275 }
2276 unsigned NumDefs = TII->get(Opcode: PN->getMachineOpcode()).getNumDefs();
2277 for (unsigned i = 0; i != NumDefs; ++i) {
2278 MVT VT = PN->getSimpleValueType(ResNo: i);
2279 if (!PN->hasAnyUseOfValue(Value: i))
2280 continue;
2281 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2282 if (RegPressure[RCId] < TLI->getRepRegClassCostFor(VT))
2283 // Register pressure tracking is imprecise. This can happen.
2284 RegPressure[RCId] = 0;
2285 else
2286 RegPressure[RCId] -= TLI->getRepRegClassCostFor(VT);
2287 }
2288 }
2289
2290 // Check for isMachineOpcode() as PrescheduleNodesWithMultipleUses()
2291 // may transfer data dependencies to CopyToReg.
2292 if (SU->NumSuccs && N->isMachineOpcode()) {
2293 unsigned NumDefs = TII->get(Opcode: N->getMachineOpcode()).getNumDefs();
2294 for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
2295 MVT VT = N->getSimpleValueType(ResNo: i);
2296 if (VT == MVT::Glue || VT == MVT::Other)
2297 continue;
2298 if (!N->hasAnyUseOfValue(Value: i))
2299 continue;
2300 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2301 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
2302 }
2303 }
2304
2305 LLVM_DEBUG(dumpRegPressure());
2306}
2307
2308//===----------------------------------------------------------------------===//
2309// Dynamic Node Priority for Register Pressure Reduction
2310//===----------------------------------------------------------------------===//
2311
2312/// closestSucc - Returns the scheduled cycle of the successor which is
2313/// closest to the current cycle.
2314static unsigned closestSucc(const SUnit *SU) {
2315 unsigned MaxHeight = 0;
2316 for (const SDep &Succ : SU->Succs) {
2317 if (Succ.isCtrl()) continue; // ignore chain succs
2318 unsigned Height = Succ.getSUnit()->getHeight();
2319 // If there are bunch of CopyToRegs stacked up, they should be considered
2320 // to be at the same position.
2321 if (Succ.getSUnit()->getNode() &&
2322 Succ.getSUnit()->getNode()->getOpcode() == ISD::CopyToReg)
2323 Height = closestSucc(SU: Succ.getSUnit())+1;
2324 if (Height > MaxHeight)
2325 MaxHeight = Height;
2326 }
2327 return MaxHeight;
2328}
2329
2330/// calcMaxScratches - Returns an cost estimate of the worse case requirement
2331/// for scratch registers, i.e. number of data dependencies.
2332static unsigned calcMaxScratches(const SUnit *SU) {
2333 unsigned Scratches = 0;
2334 for (const SDep &Pred : SU->Preds) {
2335 if (Pred.isCtrl()) continue; // ignore chain preds
2336 Scratches++;
2337 }
2338 return Scratches;
2339}
2340
2341/// hasOnlyLiveInOpers - Return true if SU has only value predecessors that are
2342/// CopyFromReg from a virtual register.
2343static bool hasOnlyLiveInOpers(const SUnit *SU) {
2344 bool RetVal = false;
2345 for (const SDep &Pred : SU->Preds) {
2346 if (Pred.isCtrl()) continue;
2347 const SUnit *PredSU = Pred.getSUnit();
2348 if (PredSU->getNode() &&
2349 PredSU->getNode()->getOpcode() == ISD::CopyFromReg) {
2350 Register Reg =
2351 cast<RegisterSDNode>(Val: PredSU->getNode()->getOperand(Num: 1))->getReg();
2352 if (Reg.isVirtual()) {
2353 RetVal = true;
2354 continue;
2355 }
2356 }
2357 return false;
2358 }
2359 return RetVal;
2360}
2361
2362/// hasOnlyLiveOutUses - Return true if SU has only value successors that are
2363/// CopyToReg to a virtual register. This SU def is probably a liveout and
2364/// it has no other use. It should be scheduled closer to the terminator.
2365static bool hasOnlyLiveOutUses(const SUnit *SU) {
2366 bool RetVal = false;
2367 for (const SDep &Succ : SU->Succs) {
2368 if (Succ.isCtrl()) continue;
2369 const SUnit *SuccSU = Succ.getSUnit();
2370 if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg) {
2371 Register Reg =
2372 cast<RegisterSDNode>(Val: SuccSU->getNode()->getOperand(Num: 1))->getReg();
2373 if (Reg.isVirtual()) {
2374 RetVal = true;
2375 continue;
2376 }
2377 }
2378 return false;
2379 }
2380 return RetVal;
2381}
2382
2383// Set isVRegCycle for a node with only live in opers and live out uses. Also
2384// set isVRegCycle for its CopyFromReg operands.
2385//
2386// This is only relevant for single-block loops, in which case the VRegCycle
2387// node is likely an induction variable in which the operand and target virtual
2388// registers should be coalesced (e.g. pre/post increment values). Setting the
2389// isVRegCycle flag helps the scheduler prioritize other uses of the same
2390// CopyFromReg so that this node becomes the virtual register "kill". This
2391// avoids interference between the values live in and out of the block and
2392// eliminates a copy inside the loop.
2393static void initVRegCycle(SUnit *SU) {
2394 if (DisableSchedVRegCycle)
2395 return;
2396
2397 if (!hasOnlyLiveInOpers(SU) || !hasOnlyLiveOutUses(SU))
2398 return;
2399
2400 LLVM_DEBUG(dbgs() << "VRegCycle: SU(" << SU->NodeNum << ")\n");
2401
2402 SU->isVRegCycle = true;
2403
2404 for (const SDep &Pred : SU->Preds) {
2405 if (Pred.isCtrl()) continue;
2406 Pred.getSUnit()->isVRegCycle = true;
2407 }
2408}
2409
2410// After scheduling the definition of a VRegCycle, clear the isVRegCycle flag of
2411// CopyFromReg operands. We should no longer penalize other uses of this VReg.
2412static void resetVRegCycle(SUnit *SU) {
2413 if (!SU->isVRegCycle)
2414 return;
2415
2416 for (const SDep &Pred : SU->Preds) {
2417 if (Pred.isCtrl()) continue; // ignore chain preds
2418 SUnit *PredSU = Pred.getSUnit();
2419 if (PredSU->isVRegCycle) {
2420 assert(PredSU->getNode()->getOpcode() == ISD::CopyFromReg &&
2421 "VRegCycle def must be CopyFromReg");
2422 Pred.getSUnit()->isVRegCycle = false;
2423 }
2424 }
2425}
2426
2427// Return true if this SUnit uses a CopyFromReg node marked as a VRegCycle. This
2428// means a node that defines the VRegCycle has not been scheduled yet.
2429static bool hasVRegCycleUse(const SUnit *SU) {
2430 // If this SU also defines the VReg, don't hoist it as a "use".
2431 if (SU->isVRegCycle)
2432 return false;
2433
2434 for (const SDep &Pred : SU->Preds) {
2435 if (Pred.isCtrl()) continue; // ignore chain preds
2436 if (Pred.getSUnit()->isVRegCycle &&
2437 Pred.getSUnit()->getNode()->getOpcode() == ISD::CopyFromReg) {
2438 LLVM_DEBUG(dbgs() << " VReg cycle use: SU (" << SU->NodeNum << ")\n");
2439 return true;
2440 }
2441 }
2442 return false;
2443}
2444
2445// Check for either a dependence (latency) or resource (hazard) stall.
2446//
2447// Note: The ScheduleHazardRecognizer interface requires a non-const SU.
2448static bool BUHasStall(SUnit *SU, int Height, RegReductionPQBase *SPQ) {
2449 if ((int)SPQ->getCurCycle() < Height) return true;
2450 if (SPQ->getHazardRec()->getHazardType(SU, Stalls: 0)
2451 != ScheduleHazardRecognizer::NoHazard)
2452 return true;
2453 return false;
2454}
2455
2456// Return -1 if left has higher priority, 1 if right has higher priority.
2457// Return 0 if latency-based priority is equivalent.
2458static int BUCompareLatency(SUnit *left, SUnit *right, bool checkPref,
2459 RegReductionPQBase *SPQ) {
2460 // Scheduling an instruction that uses a VReg whose postincrement has not yet
2461 // been scheduled will induce a copy. Model this as an extra cycle of latency.
2462 int LPenalty = hasVRegCycleUse(SU: left) ? 1 : 0;
2463 int RPenalty = hasVRegCycleUse(SU: right) ? 1 : 0;
2464 int LHeight = (int)left->getHeight() + LPenalty;
2465 int RHeight = (int)right->getHeight() + RPenalty;
2466
2467 bool LStall = (!checkPref || left->SchedulingPref == Sched::ILP) &&
2468 BUHasStall(SU: left, Height: LHeight, SPQ);
2469 bool RStall = (!checkPref || right->SchedulingPref == Sched::ILP) &&
2470 BUHasStall(SU: right, Height: RHeight, SPQ);
2471
2472 // If scheduling one of the node will cause a pipeline stall, delay it.
2473 // If scheduling either one of the node will cause a pipeline stall, sort
2474 // them according to their height.
2475 if (LStall) {
2476 if (!RStall)
2477 return 1;
2478 if (LHeight != RHeight)
2479 return LHeight > RHeight ? 1 : -1;
2480 } else if (RStall)
2481 return -1;
2482
2483 // If either node is scheduling for latency, sort them by height/depth
2484 // and latency.
2485 if (!checkPref || (left->SchedulingPref == Sched::ILP ||
2486 right->SchedulingPref == Sched::ILP)) {
2487 // If neither instruction stalls (!LStall && !RStall) and HazardRecognizer
2488 // is enabled, grouping instructions by cycle, then its height is already
2489 // covered so only its depth matters. We also reach this point if both stall
2490 // but have the same height.
2491 if (!SPQ->getHazardRec()->isEnabled()) {
2492 if (LHeight != RHeight)
2493 return LHeight > RHeight ? 1 : -1;
2494 }
2495 int LDepth = left->getDepth() - LPenalty;
2496 int RDepth = right->getDepth() - RPenalty;
2497 if (LDepth != RDepth) {
2498 LLVM_DEBUG(dbgs() << " Comparing latency of SU (" << left->NodeNum
2499 << ") depth " << LDepth << " vs SU (" << right->NodeNum
2500 << ") depth " << RDepth << "\n");
2501 return LDepth < RDepth ? 1 : -1;
2502 }
2503 if (left->Latency != right->Latency)
2504 return left->Latency > right->Latency ? 1 : -1;
2505 }
2506 return 0;
2507}
2508
2509static bool BURRSort(SUnit *left, SUnit *right, RegReductionPQBase *SPQ) {
2510 // Schedule physical register definitions close to their use. This is
2511 // motivated by microarchitectures that can fuse cmp+jump macro-ops. But as
2512 // long as shortening physreg live ranges is generally good, we can defer
2513 // creating a subtarget hook.
2514 if (!DisableSchedPhysRegJoin) {
2515 bool LHasPhysReg = left->hasPhysRegDefs;
2516 bool RHasPhysReg = right->hasPhysRegDefs;
2517 if (LHasPhysReg != RHasPhysReg) {
2518 #ifndef NDEBUG
2519 static const char *const PhysRegMsg[] = { " has no physreg",
2520 " defines a physreg" };
2521 #endif
2522 LLVM_DEBUG(dbgs() << " SU (" << left->NodeNum << ") "
2523 << PhysRegMsg[LHasPhysReg] << " SU(" << right->NodeNum
2524 << ") " << PhysRegMsg[RHasPhysReg] << "\n");
2525 return LHasPhysReg < RHasPhysReg;
2526 }
2527 }
2528
2529 // Prioritize by Sethi-Ulmann number and push CopyToReg nodes down.
2530 unsigned LPriority = SPQ->getNodePriority(SU: left);
2531 unsigned RPriority = SPQ->getNodePriority(SU: right);
2532
2533 // Be really careful about hoisting call operands above previous calls.
2534 // Only allows it if it would reduce register pressure.
2535 if (left->isCall && right->isCallOp) {
2536 unsigned RNumVals = right->getNode()->getNumValues();
2537 RPriority = (RPriority > RNumVals) ? (RPriority - RNumVals) : 0;
2538 }
2539 if (right->isCall && left->isCallOp) {
2540 unsigned LNumVals = left->getNode()->getNumValues();
2541 LPriority = (LPriority > LNumVals) ? (LPriority - LNumVals) : 0;
2542 }
2543
2544 if (LPriority != RPriority)
2545 return LPriority > RPriority;
2546
2547 // One or both of the nodes are calls and their sethi-ullman numbers are the
2548 // same, then keep source order.
2549 if (left->isCall || right->isCall) {
2550 unsigned LOrder = SPQ->getNodeOrdering(SU: left);
2551 unsigned ROrder = SPQ->getNodeOrdering(SU: right);
2552
2553 // Prefer an ordering where the lower the non-zero order number, the higher
2554 // the preference.
2555 if ((LOrder || ROrder) && LOrder != ROrder)
2556 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
2557 }
2558
2559 // Try schedule def + use closer when Sethi-Ullman numbers are the same.
2560 // e.g.
2561 // t1 = op t2, c1
2562 // t3 = op t4, c2
2563 //
2564 // and the following instructions are both ready.
2565 // t2 = op c3
2566 // t4 = op c4
2567 //
2568 // Then schedule t2 = op first.
2569 // i.e.
2570 // t4 = op c4
2571 // t2 = op c3
2572 // t1 = op t2, c1
2573 // t3 = op t4, c2
2574 //
2575 // This creates more short live intervals.
2576 unsigned LDist = closestSucc(SU: left);
2577 unsigned RDist = closestSucc(SU: right);
2578 if (LDist != RDist)
2579 return LDist < RDist;
2580
2581 // How many registers becomes live when the node is scheduled.
2582 unsigned LScratch = calcMaxScratches(SU: left);
2583 unsigned RScratch = calcMaxScratches(SU: right);
2584 if (LScratch != RScratch)
2585 return LScratch > RScratch;
2586
2587 // Comparing latency against a call makes little sense unless the node
2588 // is register pressure-neutral.
2589 if ((left->isCall && RPriority > 0) || (right->isCall && LPriority > 0))
2590 return (left->NodeQueueId > right->NodeQueueId);
2591
2592 // Do not compare latencies when one or both of the nodes are calls.
2593 if (!DisableSchedCycles &&
2594 !(left->isCall || right->isCall)) {
2595 int result = BUCompareLatency(left, right, checkPref: false /*checkPref*/, SPQ);
2596 if (result != 0)
2597 return result > 0;
2598 }
2599 else {
2600 if (left->getHeight() != right->getHeight())
2601 return left->getHeight() > right->getHeight();
2602
2603 if (left->getDepth() != right->getDepth())
2604 return left->getDepth() < right->getDepth();
2605 }
2606
2607 assert(left->NodeQueueId && right->NodeQueueId &&
2608 "NodeQueueId cannot be zero");
2609 return (left->NodeQueueId > right->NodeQueueId);
2610}
2611
2612// Bottom up
2613bool bu_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2614 if (int res = checkSpecialNodes(left, right))
2615 return res > 0;
2616
2617 return BURRSort(left, right, SPQ);
2618}
2619
2620// Source order, otherwise bottom up.
2621bool src_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2622 if (int res = checkSpecialNodes(left, right))
2623 return res > 0;
2624
2625 unsigned LOrder = SPQ->getNodeOrdering(SU: left);
2626 unsigned ROrder = SPQ->getNodeOrdering(SU: right);
2627
2628 // Prefer an ordering where the lower the non-zero order number, the higher
2629 // the preference.
2630 if ((LOrder || ROrder) && LOrder != ROrder)
2631 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
2632
2633 return BURRSort(left, right, SPQ);
2634}
2635
2636// If the time between now and when the instruction will be ready can cover
2637// the spill code, then avoid adding it to the ready queue. This gives long
2638// stalls highest priority and allows hoisting across calls. It should also
2639// speed up processing the available queue.
2640bool hybrid_ls_rr_sort::isReady(SUnit *SU, unsigned CurCycle) const {
2641 static const unsigned ReadyDelay = 3;
2642
2643 if (SPQ->MayReduceRegPressure(SU)) return true;
2644
2645 if (SU->getHeight() > (CurCycle + ReadyDelay)) return false;
2646
2647 if (SPQ->getHazardRec()->getHazardType(SU, Stalls: -ReadyDelay)
2648 != ScheduleHazardRecognizer::NoHazard)
2649 return false;
2650
2651 return true;
2652}
2653
2654// Return true if right should be scheduled with higher priority than left.
2655bool hybrid_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2656 if (int res = checkSpecialNodes(left, right))
2657 return res > 0;
2658
2659 if (left->isCall || right->isCall)
2660 // No way to compute latency of calls.
2661 return BURRSort(left, right, SPQ);
2662
2663 bool LHigh = SPQ->HighRegPressure(SU: left);
2664 bool RHigh = SPQ->HighRegPressure(SU: right);
2665 // Avoid causing spills. If register pressure is high, schedule for
2666 // register pressure reduction.
2667 if (LHigh && !RHigh) {
2668 LLVM_DEBUG(dbgs() << " pressure SU(" << left->NodeNum << ") > SU("
2669 << right->NodeNum << ")\n");
2670 return true;
2671 }
2672 else if (!LHigh && RHigh) {
2673 LLVM_DEBUG(dbgs() << " pressure SU(" << right->NodeNum << ") > SU("
2674 << left->NodeNum << ")\n");
2675 return false;
2676 }
2677 if (!LHigh && !RHigh) {
2678 int result = BUCompareLatency(left, right, checkPref: true /*checkPref*/, SPQ);
2679 if (result != 0)
2680 return result > 0;
2681 }
2682 return BURRSort(left, right, SPQ);
2683}
2684
2685// Schedule as many instructions in each cycle as possible. So don't make an
2686// instruction available unless it is ready in the current cycle.
2687bool ilp_ls_rr_sort::isReady(SUnit *SU, unsigned CurCycle) const {
2688 if (SU->getHeight() > CurCycle) return false;
2689
2690 if (SPQ->getHazardRec()->getHazardType(SU, Stalls: 0)
2691 != ScheduleHazardRecognizer::NoHazard)
2692 return false;
2693
2694 return true;
2695}
2696
2697static bool canEnableCoalescing(SUnit *SU) {
2698 unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0;
2699 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
2700 // CopyToReg should be close to its uses to facilitate coalescing and
2701 // avoid spilling.
2702 return true;
2703
2704 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2705 Opc == TargetOpcode::SUBREG_TO_REG ||
2706 Opc == TargetOpcode::INSERT_SUBREG)
2707 // EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG nodes should be
2708 // close to their uses to facilitate coalescing.
2709 return true;
2710
2711 if (SU->NumPreds == 0 && SU->NumSuccs != 0)
2712 // If SU does not have a register def, schedule it close to its uses
2713 // because it does not lengthen any live ranges.
2714 return true;
2715
2716 return false;
2717}
2718
2719// list-ilp is currently an experimental scheduler that allows various
2720// heuristics to be enabled prior to the normal register reduction logic.
2721bool ilp_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2722 if (int res = checkSpecialNodes(left, right))
2723 return res > 0;
2724
2725 if (left->isCall || right->isCall)
2726 // No way to compute latency of calls.
2727 return BURRSort(left, right, SPQ);
2728
2729 unsigned LLiveUses = 0, RLiveUses = 0;
2730 int LPDiff = 0, RPDiff = 0;
2731 if (!DisableSchedRegPressure || !DisableSchedLiveUses) {
2732 LPDiff = SPQ->RegPressureDiff(SU: left, LiveUses&: LLiveUses);
2733 RPDiff = SPQ->RegPressureDiff(SU: right, LiveUses&: RLiveUses);
2734 }
2735 if (!DisableSchedRegPressure && LPDiff != RPDiff) {
2736 LLVM_DEBUG(dbgs() << "RegPressureDiff SU(" << left->NodeNum
2737 << "): " << LPDiff << " != SU(" << right->NodeNum
2738 << "): " << RPDiff << "\n");
2739 return LPDiff > RPDiff;
2740 }
2741
2742 if (!DisableSchedRegPressure && (LPDiff > 0 || RPDiff > 0)) {
2743 bool LReduce = canEnableCoalescing(SU: left);
2744 bool RReduce = canEnableCoalescing(SU: right);
2745 if (LReduce && !RReduce) return false;
2746 if (RReduce && !LReduce) return true;
2747 }
2748
2749 if (!DisableSchedLiveUses && (LLiveUses != RLiveUses)) {
2750 LLVM_DEBUG(dbgs() << "Live uses SU(" << left->NodeNum << "): " << LLiveUses
2751 << " != SU(" << right->NodeNum << "): " << RLiveUses
2752 << "\n");
2753 return LLiveUses < RLiveUses;
2754 }
2755
2756 if (!DisableSchedStalls) {
2757 bool LStall = BUHasStall(SU: left, Height: left->getHeight(), SPQ);
2758 bool RStall = BUHasStall(SU: right, Height: right->getHeight(), SPQ);
2759 if (LStall != RStall)
2760 return left->getHeight() > right->getHeight();
2761 }
2762
2763 if (!DisableSchedCriticalPath) {
2764 int spread = (int)left->getDepth() - (int)right->getDepth();
2765 if (std::abs(x: spread) > MaxReorderWindow) {
2766 LLVM_DEBUG(dbgs() << "Depth of SU(" << left->NodeNum << "): "
2767 << left->getDepth() << " != SU(" << right->NodeNum
2768 << "): " << right->getDepth() << "\n");
2769 return left->getDepth() < right->getDepth();
2770 }
2771 }
2772
2773 if (!DisableSchedHeight && left->getHeight() != right->getHeight()) {
2774 int spread = (int)left->getHeight() - (int)right->getHeight();
2775 if (std::abs(x: spread) > MaxReorderWindow)
2776 return left->getHeight() > right->getHeight();
2777 }
2778
2779 return BURRSort(left, right, SPQ);
2780}
2781
2782void RegReductionPQBase::initNodes(std::vector<SUnit> &sunits) {
2783 SUnits = &sunits;
2784 // Add pseudo dependency edges for two-address nodes.
2785 if (!Disable2AddrHack)
2786 AddPseudoTwoAddrDeps();
2787 // Reroute edges to nodes with multiple uses.
2788 if (!TracksRegPressure && !SrcOrder)
2789 PrescheduleNodesWithMultipleUses();
2790 // Calculate node priorities.
2791 CalculateSethiUllmanNumbers();
2792
2793 // For single block loops, mark nodes that look like canonical IV increments.
2794 if (scheduleDAG->BB->isSuccessor(MBB: scheduleDAG->BB))
2795 for (SUnit &SU : sunits)
2796 initVRegCycle(SU: &SU);
2797}
2798
2799//===----------------------------------------------------------------------===//
2800// Preschedule for Register Pressure
2801//===----------------------------------------------------------------------===//
2802
2803bool RegReductionPQBase::canClobber(const SUnit *SU, const SUnit *Op) {
2804 if (SU->isTwoAddress) {
2805 unsigned Opc = SU->getNode()->getMachineOpcode();
2806 const MCInstrDesc &MCID = TII->get(Opcode: Opc);
2807 unsigned NumRes = MCID.getNumDefs();
2808 unsigned NumOps = MCID.getNumOperands() - NumRes;
2809 for (unsigned i = 0; i != NumOps; ++i) {
2810 if (MCID.getOperandConstraint(OpNum: i+NumRes, Constraint: MCOI::TIED_TO) != -1) {
2811 SDNode *DU = SU->getNode()->getOperand(Num: i).getNode();
2812 if (DU->getNodeId() != -1 &&
2813 Op->OrigNode == &(*SUnits)[DU->getNodeId()])
2814 return true;
2815 }
2816 }
2817 }
2818 return false;
2819}
2820
2821/// canClobberReachingPhysRegUse - True if SU would clobber one of it's
2822/// successor's explicit physregs whose definition can reach DepSU.
2823/// i.e. DepSU should not be scheduled above SU.
2824static bool canClobberReachingPhysRegUse(const SUnit *DepSU, const SUnit *SU,
2825 ScheduleDAGRRList *scheduleDAG,
2826 const TargetInstrInfo *TII,
2827 const TargetRegisterInfo *TRI) {
2828 ArrayRef<MCPhysReg> ImpDefs =
2829 TII->get(Opcode: SU->getNode()->getMachineOpcode()).implicit_defs();
2830 const uint32_t *RegMask = getNodeRegMask(N: SU->getNode());
2831 if (ImpDefs.empty() && !RegMask)
2832 return false;
2833
2834 for (const SDep &Succ : SU->Succs) {
2835 SUnit *SuccSU = Succ.getSUnit();
2836 for (const SDep &SuccPred : SuccSU->Preds) {
2837 if (!SuccPred.isAssignedRegDep())
2838 continue;
2839
2840 if (RegMask &&
2841 MachineOperand::clobbersPhysReg(RegMask, PhysReg: SuccPred.getReg()) &&
2842 scheduleDAG->IsReachable(SU: DepSU, TargetSU: SuccPred.getSUnit()))
2843 return true;
2844
2845 for (MCPhysReg ImpDef : ImpDefs) {
2846 // Return true if SU clobbers this physical register use and the
2847 // definition of the register reaches from DepSU. IsReachable queries
2848 // a topological forward sort of the DAG (following the successors).
2849 if (TRI->regsOverlap(RegA: ImpDef, RegB: SuccPred.getReg()) &&
2850 scheduleDAG->IsReachable(SU: DepSU, TargetSU: SuccPred.getSUnit()))
2851 return true;
2852 }
2853 }
2854 }
2855 return false;
2856}
2857
2858/// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's
2859/// physical register defs.
2860static bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU,
2861 const TargetInstrInfo *TII,
2862 const TargetRegisterInfo *TRI) {
2863 SDNode *N = SuccSU->getNode();
2864 unsigned NumDefs = TII->get(Opcode: N->getMachineOpcode()).getNumDefs();
2865 ArrayRef<MCPhysReg> ImpDefs = TII->get(Opcode: N->getMachineOpcode()).implicit_defs();
2866 assert(!ImpDefs.empty() && "Caller should check hasPhysRegDefs");
2867 for (const SDNode *SUNode = SU->getNode(); SUNode;
2868 SUNode = SUNode->getGluedNode()) {
2869 if (!SUNode->isMachineOpcode())
2870 continue;
2871 ArrayRef<MCPhysReg> SUImpDefs =
2872 TII->get(Opcode: SUNode->getMachineOpcode()).implicit_defs();
2873 const uint32_t *SURegMask = getNodeRegMask(N: SUNode);
2874 if (SUImpDefs.empty() && !SURegMask)
2875 continue;
2876 for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
2877 MVT VT = N->getSimpleValueType(ResNo: i);
2878 if (VT == MVT::Glue || VT == MVT::Other)
2879 continue;
2880 if (!N->hasAnyUseOfValue(Value: i))
2881 continue;
2882 MCPhysReg Reg = ImpDefs[i - NumDefs];
2883 if (SURegMask && MachineOperand::clobbersPhysReg(RegMask: SURegMask, PhysReg: Reg))
2884 return true;
2885 for (MCPhysReg SUReg : SUImpDefs) {
2886 if (TRI->regsOverlap(RegA: Reg, RegB: SUReg))
2887 return true;
2888 }
2889 }
2890 }
2891 return false;
2892}
2893
2894/// PrescheduleNodesWithMultipleUses - Nodes with multiple uses
2895/// are not handled well by the general register pressure reduction
2896/// heuristics. When presented with code like this:
2897///
2898/// N
2899/// / |
2900/// / |
2901/// U store
2902/// |
2903/// ...
2904///
2905/// the heuristics tend to push the store up, but since the
2906/// operand of the store has another use (U), this would increase
2907/// the length of that other use (the U->N edge).
2908///
2909/// This function transforms code like the above to route U's
2910/// dependence through the store when possible, like this:
2911///
2912/// N
2913/// ||
2914/// ||
2915/// store
2916/// |
2917/// U
2918/// |
2919/// ...
2920///
2921/// This results in the store being scheduled immediately
2922/// after N, which shortens the U->N live range, reducing
2923/// register pressure.
2924void RegReductionPQBase::PrescheduleNodesWithMultipleUses() {
2925 // Visit all the nodes in topological order, working top-down.
2926 for (SUnit &SU : *SUnits) {
2927 // For now, only look at nodes with no data successors, such as stores.
2928 // These are especially important, due to the heuristics in
2929 // getNodePriority for nodes with no data successors.
2930 if (SU.NumSuccs != 0)
2931 continue;
2932 // For now, only look at nodes with exactly one data predecessor.
2933 if (SU.NumPreds != 1)
2934 continue;
2935 // Avoid prescheduling copies to virtual registers, which don't behave
2936 // like other nodes from the perspective of scheduling heuristics.
2937 if (SDNode *N = SU.getNode())
2938 if (N->getOpcode() == ISD::CopyToReg &&
2939 cast<RegisterSDNode>(Val: N->getOperand(Num: 1))->getReg().isVirtual())
2940 continue;
2941
2942 SDNode *PredFrameSetup = nullptr;
2943 for (const SDep &Pred : SU.Preds)
2944 if (Pred.isCtrl() && Pred.getSUnit()) {
2945 // Find the predecessor which is not data dependence.
2946 SDNode *PredND = Pred.getSUnit()->getNode();
2947
2948 // If PredND is FrameSetup, we should not pre-scheduled the node,
2949 // or else, when bottom up scheduling, ADJCALLSTACKDOWN and
2950 // ADJCALLSTACKUP may hold CallResource too long and make other
2951 // calls can't be scheduled. If there's no other available node
2952 // to schedule, the schedular will try to rename the register by
2953 // creating copy to avoid the conflict which will fail because
2954 // CallResource is not a real physical register.
2955 if (PredND && PredND->isMachineOpcode() &&
2956 (PredND->getMachineOpcode() == TII->getCallFrameSetupOpcode())) {
2957 PredFrameSetup = PredND;
2958 break;
2959 }
2960 }
2961 // Skip the node has FrameSetup parent.
2962 if (PredFrameSetup != nullptr)
2963 continue;
2964
2965 // Locate the single data predecessor.
2966 SUnit *PredSU = nullptr;
2967 for (const SDep &Pred : SU.Preds)
2968 if (!Pred.isCtrl()) {
2969 PredSU = Pred.getSUnit();
2970 break;
2971 }
2972 assert(PredSU);
2973
2974 // Don't rewrite edges that carry physregs, because that requires additional
2975 // support infrastructure.
2976 if (PredSU->hasPhysRegDefs)
2977 continue;
2978 // Short-circuit the case where SU is PredSU's only data successor.
2979 if (PredSU->NumSuccs == 1)
2980 continue;
2981 // Avoid prescheduling to copies from virtual registers, which don't behave
2982 // like other nodes from the perspective of scheduling heuristics.
2983 if (SDNode *N = SU.getNode())
2984 if (N->getOpcode() == ISD::CopyFromReg &&
2985 cast<RegisterSDNode>(Val: N->getOperand(Num: 1))->getReg().isVirtual())
2986 continue;
2987
2988 // Perform checks on the successors of PredSU.
2989 for (const SDep &PredSucc : PredSU->Succs) {
2990 SUnit *PredSuccSU = PredSucc.getSUnit();
2991 if (PredSuccSU == &SU) continue;
2992 // If PredSU has another successor with no data successors, for
2993 // now don't attempt to choose either over the other.
2994 if (PredSuccSU->NumSuccs == 0)
2995 goto outer_loop_continue;
2996 // Don't break physical register dependencies.
2997 if (SU.hasPhysRegClobbers && PredSuccSU->hasPhysRegDefs)
2998 if (canClobberPhysRegDefs(SuccSU: PredSuccSU, SU: &SU, TII, TRI))
2999 goto outer_loop_continue;
3000 // Don't introduce graph cycles.
3001 if (scheduleDAG->IsReachable(SU: &SU, TargetSU: PredSuccSU))
3002 goto outer_loop_continue;
3003 }
3004
3005 // Ok, the transformation is safe and the heuristics suggest it is
3006 // profitable. Update the graph.
3007 LLVM_DEBUG(
3008 dbgs() << " Prescheduling SU #" << SU.NodeNum << " next to PredSU #"
3009 << PredSU->NodeNum
3010 << " to guide scheduling in the presence of multiple uses\n");
3011 for (unsigned i = 0; i != PredSU->Succs.size(); ++i) {
3012 SDep Edge = PredSU->Succs[i];
3013 assert(!Edge.isAssignedRegDep());
3014 SUnit *SuccSU = Edge.getSUnit();
3015 if (SuccSU != &SU) {
3016 Edge.setSUnit(PredSU);
3017 scheduleDAG->RemovePred(SU: SuccSU, D: Edge);
3018 scheduleDAG->AddPredQueued(SU: &SU, D: Edge);
3019 Edge.setSUnit(&SU);
3020 scheduleDAG->AddPredQueued(SU: SuccSU, D: Edge);
3021 --i;
3022 }
3023 }
3024 outer_loop_continue:;
3025 }
3026}
3027
3028/// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
3029/// it as a def&use operand. Add a pseudo control edge from it to the other
3030/// node (if it won't create a cycle) so the two-address one will be scheduled
3031/// first (lower in the schedule). If both nodes are two-address, favor the
3032/// one that has a CopyToReg use (more likely to be a loop induction update).
3033/// If both are two-address, but one is commutable while the other is not
3034/// commutable, favor the one that's not commutable.
3035void RegReductionPQBase::AddPseudoTwoAddrDeps() {
3036 for (SUnit &SU : *SUnits) {
3037 if (!SU.isTwoAddress)
3038 continue;
3039
3040 SDNode *Node = SU.getNode();
3041 if (!Node || !Node->isMachineOpcode() || SU.getNode()->getGluedNode())
3042 continue;
3043
3044 bool isLiveOut = hasOnlyLiveOutUses(SU: &SU);
3045 unsigned Opc = Node->getMachineOpcode();
3046 const MCInstrDesc &MCID = TII->get(Opcode: Opc);
3047 unsigned NumRes = MCID.getNumDefs();
3048 unsigned NumOps = MCID.getNumOperands() - NumRes;
3049 for (unsigned j = 0; j != NumOps; ++j) {
3050 if (MCID.getOperandConstraint(OpNum: j+NumRes, Constraint: MCOI::TIED_TO) == -1)
3051 continue;
3052 SDNode *DU = SU.getNode()->getOperand(Num: j).getNode();
3053 if (DU->getNodeId() == -1)
3054 continue;
3055 const SUnit *DUSU = &(*SUnits)[DU->getNodeId()];
3056 if (!DUSU)
3057 continue;
3058 for (const SDep &Succ : DUSU->Succs) {
3059 if (Succ.isCtrl())
3060 continue;
3061 SUnit *SuccSU = Succ.getSUnit();
3062 if (SuccSU == &SU)
3063 continue;
3064 // Be conservative. Ignore if nodes aren't at roughly the same
3065 // depth and height.
3066 if (SuccSU->getHeight() < SU.getHeight() &&
3067 (SU.getHeight() - SuccSU->getHeight()) > 1)
3068 continue;
3069 // Skip past COPY_TO_REGCLASS nodes, so that the pseudo edge
3070 // constrains whatever is using the copy, instead of the copy
3071 // itself. In the case that the copy is coalesced, this
3072 // preserves the intent of the pseudo two-address heurietics.
3073 while (SuccSU->Succs.size() == 1 &&
3074 SuccSU->getNode()->isMachineOpcode() &&
3075 SuccSU->getNode()->getMachineOpcode() ==
3076 TargetOpcode::COPY_TO_REGCLASS)
3077 SuccSU = SuccSU->Succs.front().getSUnit();
3078 // Don't constrain non-instruction nodes.
3079 if (!SuccSU->getNode() || !SuccSU->getNode()->isMachineOpcode())
3080 continue;
3081 // Don't constrain nodes with physical register defs if the
3082 // predecessor can clobber them.
3083 if (SuccSU->hasPhysRegDefs && SU.hasPhysRegClobbers) {
3084 if (canClobberPhysRegDefs(SuccSU, SU: &SU, TII, TRI))
3085 continue;
3086 }
3087 // Don't constrain EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG;
3088 // these may be coalesced away. We want them close to their uses.
3089 unsigned SuccOpc = SuccSU->getNode()->getMachineOpcode();
3090 if (SuccOpc == TargetOpcode::EXTRACT_SUBREG ||
3091 SuccOpc == TargetOpcode::INSERT_SUBREG ||
3092 SuccOpc == TargetOpcode::SUBREG_TO_REG)
3093 continue;
3094 if (!canClobberReachingPhysRegUse(DepSU: SuccSU, SU: &SU, scheduleDAG, TII, TRI) &&
3095 (!canClobber(SU: SuccSU, Op: DUSU) ||
3096 (isLiveOut && !hasOnlyLiveOutUses(SU: SuccSU)) ||
3097 (!SU.isCommutable && SuccSU->isCommutable)) &&
3098 !scheduleDAG->IsReachable(SU: SuccSU, TargetSU: &SU)) {
3099 LLVM_DEBUG(dbgs()
3100 << " Adding a pseudo-two-addr edge from SU #"
3101 << SU.NodeNum << " to SU #" << SuccSU->NodeNum << "\n");
3102 scheduleDAG->AddPredQueued(SU: &SU, D: SDep(SuccSU, SDep::Artificial));
3103 }
3104 }
3105 }
3106 }
3107}
3108
3109//===----------------------------------------------------------------------===//
3110// Public Constructor Functions
3111//===----------------------------------------------------------------------===//
3112
3113ScheduleDAGSDNodes *llvm::createBURRListDAGScheduler(SelectionDAGISel *IS,
3114 CodeGenOptLevel OptLevel) {
3115 const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
3116 const TargetInstrInfo *TII = STI.getInstrInfo();
3117 const TargetRegisterInfo *TRI = STI.getRegisterInfo();
3118
3119 BURegReductionPriorityQueue *PQ =
3120 new BURegReductionPriorityQueue(*IS->MF, false, false, TII, TRI, nullptr);
3121 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, PQ, OptLevel);
3122 PQ->setScheduleDAG(SD);
3123 return SD;
3124}
3125
3126ScheduleDAGSDNodes *
3127llvm::createSourceListDAGScheduler(SelectionDAGISel *IS,
3128 CodeGenOptLevel OptLevel) {
3129 const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
3130 const TargetInstrInfo *TII = STI.getInstrInfo();
3131 const TargetRegisterInfo *TRI = STI.getRegisterInfo();
3132
3133 SrcRegReductionPriorityQueue *PQ =
3134 new SrcRegReductionPriorityQueue(*IS->MF, false, true, TII, TRI, nullptr);
3135 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, PQ, OptLevel);
3136 PQ->setScheduleDAG(SD);
3137 return SD;
3138}
3139
3140ScheduleDAGSDNodes *
3141llvm::createHybridListDAGScheduler(SelectionDAGISel *IS,
3142 CodeGenOptLevel OptLevel) {
3143 const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
3144 const TargetInstrInfo *TII = STI.getInstrInfo();
3145 const TargetRegisterInfo *TRI = STI.getRegisterInfo();
3146 const TargetLowering *TLI = IS->TLI;
3147
3148 HybridBURRPriorityQueue *PQ =
3149 new HybridBURRPriorityQueue(*IS->MF, true, false, TII, TRI, TLI);
3150
3151 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, PQ, OptLevel);
3152 PQ->setScheduleDAG(SD);
3153 return SD;
3154}
3155
3156ScheduleDAGSDNodes *llvm::createILPListDAGScheduler(SelectionDAGISel *IS,
3157 CodeGenOptLevel OptLevel) {
3158 const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
3159 const TargetInstrInfo *TII = STI.getInstrInfo();
3160 const TargetRegisterInfo *TRI = STI.getRegisterInfo();
3161 const TargetLowering *TLI = IS->TLI;
3162
3163 ILPBURRPriorityQueue *PQ =
3164 new ILPBURRPriorityQueue(*IS->MF, true, false, TII, TRI, TLI);
3165 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, PQ, OptLevel);
3166 PQ->setScheduleDAG(SD);
3167 return SD;
3168}
3169