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