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