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