1 //===----- SchedulePostRAList.cpp - list scheduler ------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements a top-down list scheduler, using standard algorithms.
11 // The basic approach uses a priority queue of available nodes to schedule.
12 // One at a time, nodes are taken from the priority queue (thus in priority
13 // order), checked for legality to schedule, and emitted if legal.
15 // Nodes may not be legal to schedule either due to structural hazards (e.g.
16 // pipeline or resource constraints) or because an input to the instruction has
17 // not completed execution.
19 //===----------------------------------------------------------------------===//
21 #define DEBUG_TYPE "post-RA-sched"
22 #include "ExactHazardRecognizer.h"
23 #include "SimpleHazardRecognizer.h"
24 #include "ScheduleDAGInstrs.h"
25 #include "llvm/CodeGen/Passes.h"
26 #include "llvm/CodeGen/LatencyPriorityQueue.h"
27 #include "llvm/CodeGen/SchedulerRegistry.h"
28 #include "llvm/CodeGen/MachineDominators.h"
29 #include "llvm/CodeGen/MachineFrameInfo.h"
30 #include "llvm/CodeGen/MachineFunctionPass.h"
31 #include "llvm/CodeGen/MachineLoopInfo.h"
32 #include "llvm/CodeGen/MachineRegisterInfo.h"
33 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
34 #include "llvm/Analysis/AliasAnalysis.h"
35 #include "llvm/Target/TargetLowering.h"
36 #include "llvm/Target/TargetMachine.h"
37 #include "llvm/Target/TargetInstrInfo.h"
38 #include "llvm/Target/TargetRegisterInfo.h"
39 #include "llvm/Target/TargetSubtarget.h"
40 #include "llvm/Support/Compiler.h"
41 #include "llvm/Support/Debug.h"
42 #include "llvm/Support/ErrorHandling.h"
43 #include "llvm/Support/raw_ostream.h"
44 #include "llvm/ADT/Statistic.h"
49 STATISTIC(NumNoops, "Number of noops inserted");
50 STATISTIC(NumStalls, "Number of pipeline stalls");
51 STATISTIC(NumFixedAnti, "Number of fixed anti-dependencies");
53 // Post-RA scheduling is enabled with
54 // TargetSubtarget.enablePostRAScheduler(). This flag can be used to
55 // override the target.
57 EnablePostRAScheduler("post-RA-scheduler",
58 cl::desc("Enable scheduling after register allocation"),
59 cl::init(false), cl::Hidden);
60 static cl::opt<std::string>
61 EnableAntiDepBreaking("break-anti-dependencies",
62 cl::desc("Break post-RA scheduling anti-dependencies: "
63 "\"critical\", \"all\", or \"none\""),
64 cl::init("critical"), cl::Hidden);
66 EnablePostRAHazardAvoidance("avoid-hazards",
67 cl::desc("Enable exact hazard avoidance"),
68 cl::init(true), cl::Hidden);
70 // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod
72 DebugDiv("postra-sched-debugdiv",
73 cl::desc("Debug control MBBs that are scheduled"),
74 cl::init(0), cl::Hidden);
76 DebugMod("postra-sched-debugmod",
77 cl::desc("Debug control MBBs that are scheduled"),
78 cl::init(0), cl::Hidden);
81 class VISIBILITY_HIDDEN PostRAScheduler : public MachineFunctionPass {
83 CodeGenOpt::Level OptLevel;
87 PostRAScheduler(CodeGenOpt::Level ol) :
88 MachineFunctionPass(&ID), OptLevel(ol) {}
90 void getAnalysisUsage(AnalysisUsage &AU) const {
92 AU.addRequired<AliasAnalysis>();
93 AU.addRequired<MachineDominatorTree>();
94 AU.addPreserved<MachineDominatorTree>();
95 AU.addRequired<MachineLoopInfo>();
96 AU.addPreserved<MachineLoopInfo>();
97 MachineFunctionPass::getAnalysisUsage(AU);
100 const char *getPassName() const {
101 return "Post RA top-down list latency scheduler";
104 bool runOnMachineFunction(MachineFunction &Fn);
106 char PostRAScheduler::ID = 0;
108 class VISIBILITY_HIDDEN SchedulePostRATDList : public ScheduleDAGInstrs {
109 /// RegisterReference - Information about a register reference
110 /// within a liverange
112 /// Operand - The registers operand
113 MachineOperand *Operand;
114 /// RC - The register class
115 const TargetRegisterClass *RC;
118 /// AvailableQueue - The priority queue to use for the available SUnits.
119 LatencyPriorityQueue AvailableQueue;
121 /// PendingQueue - This contains all of the instructions whose operands have
122 /// been issued, but their results are not ready yet (due to the latency of
123 /// the operation). Once the operands becomes available, the instruction is
124 /// added to the AvailableQueue.
125 std::vector<SUnit*> PendingQueue;
127 /// Topo - A topological ordering for SUnits.
128 ScheduleDAGTopologicalSort Topo;
130 /// HazardRec - The hazard recognizer to use.
131 ScheduleHazardRecognizer *HazardRec;
133 /// AA - AliasAnalysis for making memory reference queries.
136 /// AllocatableSet - The set of allocatable registers.
137 /// We'll be ignoring anti-dependencies on non-allocatable registers,
138 /// because they may not be safe to break.
139 const BitVector AllocatableSet;
141 /// GroupNodes - Implements a disjoint-union data structure to
142 /// form register groups. A node is represented by an index into
143 /// the vector. A node can "point to" itself to indicate that it
144 /// is the parent of a group, or point to another node to indicate
145 /// that it is a member of the same group as that node.
146 std::vector<unsigned> GroupNodes;
148 /// GroupNodeIndices - For each register, the index of the GroupNode
149 /// currently representing the group that the register belongs to.
150 /// Register 0 is always represented by the 0 group, a group
151 /// composed of registers that are not eligible for anti-aliasing.
152 unsigned GroupNodeIndices[TargetRegisterInfo::FirstVirtualRegister];
154 /// RegRegs - Map registers to all their references within a live range.
155 std::multimap<unsigned, RegisterReference> RegRefs;
157 /// KillIndices - The index of the most recent kill (proceding
158 /// bottom-up), or ~0u if no kill of the register has been
159 /// seen. The register is live if this index != ~0u and DefIndices
161 unsigned KillIndices[TargetRegisterInfo::FirstVirtualRegister];
163 /// DefIndices - The index of the most recent complete def (proceding bottom
164 /// up), or ~0u if the register is live.
165 unsigned DefIndices[TargetRegisterInfo::FirstVirtualRegister];
168 SchedulePostRATDList(MachineFunction &MF,
169 const MachineLoopInfo &MLI,
170 const MachineDominatorTree &MDT,
171 ScheduleHazardRecognizer *HR,
173 : ScheduleDAGInstrs(MF, MLI, MDT), Topo(SUnits),
174 HazardRec(HR), AA(aa),
175 AllocatableSet(TRI->getAllocatableSet(MF)),
176 GroupNodes(TargetRegisterInfo::FirstVirtualRegister, 0) {}
178 ~SchedulePostRATDList() {
182 /// StartBlock - Initialize register live-range state for scheduling in
185 void StartBlock(MachineBasicBlock *BB);
187 /// FinishBlock - Clean up register live-range state.
191 /// Observe - Update liveness information to account for the current
192 /// instruction, which will not be scheduled.
194 void Observe(MachineInstr *MI, unsigned Count);
196 /// Schedule - Schedule the instruction range using list scheduling.
200 /// FixupKills - Fix register kill flags that have been made
201 /// invalid due to scheduling
203 void FixupKills(MachineBasicBlock *MBB);
206 /// IsLive - Return true if Reg is live
207 bool IsLive(unsigned Reg);
209 void PrescanInstruction(MachineInstr *MI, unsigned Count);
210 void ScanInstruction(MachineInstr *MI, unsigned Count);
211 bool BreakAntiDependencies(bool CriticalPathOnly);
212 unsigned FindSuitableFreeRegister(unsigned AntiDepReg);
214 void ReleaseSucc(SUnit *SU, SDep *SuccEdge);
215 void ReleaseSuccessors(SUnit *SU);
216 void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
217 void ListScheduleTopDown();
219 void StartBlockForKills(MachineBasicBlock *BB);
221 // ToggleKillFlag - Toggle a register operand kill flag. Other
222 // adjustments may be made to the instruction if necessary. Return
223 // true if the operand has been deleted, false if not.
224 bool ToggleKillFlag(MachineInstr *MI, MachineOperand &MO);
226 // GetGroup - Get the group for a register. The returned value is
227 // the index of the GroupNode representing the group.
228 unsigned GetGroup(unsigned Reg);
230 // GetGroupRegs - Return a vector of the registers belonging to a
232 void GetGroupRegs(unsigned Group, std::vector<unsigned> &Regs);
234 // UnionGroups - Union Reg1's and Reg2's groups to form a new
235 // group. Return the index of the GroupNode representing the
237 unsigned UnionGroups(unsigned Reg1, unsigned Reg2);
239 // LeaveGroup - Remove a register from its current group and place
240 // it alone in its own group. Return the index of the GroupNode
241 // representing the registers new group.
242 unsigned LeaveGroup(unsigned Reg);
246 /// isSchedulingBoundary - Test if the given instruction should be
247 /// considered a scheduling boundary. This primarily includes labels
250 static bool isSchedulingBoundary(const MachineInstr *MI,
251 const MachineFunction &MF) {
252 // Terminators and labels can't be scheduled around.
253 if (MI->getDesc().isTerminator() || MI->isLabel())
256 // Don't attempt to schedule around any instruction that modifies
257 // a stack-oriented pointer, as it's unlikely to be profitable. This
258 // saves compile time, because it doesn't require every single
259 // stack slot reference to depend on the instruction that does the
261 const TargetLowering &TLI = *MF.getTarget().getTargetLowering();
262 if (MI->modifiesRegister(TLI.getStackPointerRegisterToSaveRestore()))
268 bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) {
269 AA = &getAnalysis<AliasAnalysis>();
271 // Check for explicit enable/disable of post-ra scheduling.
272 if (EnablePostRAScheduler.getPosition() > 0) {
273 if (!EnablePostRAScheduler)
276 // Check that post-RA scheduling is enabled for this target.
277 const TargetSubtarget &ST = Fn.getTarget().getSubtarget<TargetSubtarget>();
278 if (!ST.enablePostRAScheduler(OptLevel))
282 DEBUG(errs() << "PostRAScheduler\n");
284 const MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
285 const MachineDominatorTree &MDT = getAnalysis<MachineDominatorTree>();
286 const InstrItineraryData &InstrItins = Fn.getTarget().getInstrItineraryData();
287 ScheduleHazardRecognizer *HR = EnablePostRAHazardAvoidance ?
288 (ScheduleHazardRecognizer *)new ExactHazardRecognizer(InstrItins) :
289 (ScheduleHazardRecognizer *)new SimpleHazardRecognizer();
291 SchedulePostRATDList Scheduler(Fn, MLI, MDT, HR, AA);
293 // Loop over all of the basic blocks
294 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
295 MBB != MBBe; ++MBB) {
297 // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod
299 static int bbcnt = 0;
300 if (bbcnt++ % DebugDiv != DebugMod)
302 errs() << "*** DEBUG scheduling " << Fn.getFunction()->getNameStr() <<
303 ":MBB ID#" << MBB->getNumber() << " ***\n";
307 // Initialize register live-range state for scheduling in this block.
308 Scheduler.StartBlock(MBB);
310 // Schedule each sequence of instructions not interrupted by a label
311 // or anything else that effectively needs to shut down scheduling.
312 MachineBasicBlock::iterator Current = MBB->end();
313 unsigned Count = MBB->size(), CurrentCount = Count;
314 for (MachineBasicBlock::iterator I = Current; I != MBB->begin(); ) {
315 MachineInstr *MI = prior(I);
316 if (isSchedulingBoundary(MI, Fn)) {
317 Scheduler.Run(MBB, I, Current, CurrentCount);
318 Scheduler.EmitSchedule(0);
320 CurrentCount = Count - 1;
321 Scheduler.Observe(MI, CurrentCount);
326 assert(Count == 0 && "Instruction count mismatch!");
327 assert((MBB->begin() == Current || CurrentCount != 0) &&
328 "Instruction count mismatch!");
329 Scheduler.Run(MBB, MBB->begin(), Current, CurrentCount);
330 Scheduler.EmitSchedule(0);
332 // Clean up register live-range state.
333 Scheduler.FinishBlock();
335 // Update register kills
336 Scheduler.FixupKills(MBB);
342 unsigned SchedulePostRATDList::GetGroup(unsigned Reg)
344 unsigned Node = GroupNodeIndices[Reg];
345 while (GroupNodes[Node] != Node)
346 Node = GroupNodes[Node];
351 void SchedulePostRATDList::GetGroupRegs(unsigned Group, std::vector<unsigned> &Regs)
353 for (unsigned Reg = 0; Reg != TargetRegisterInfo::FirstVirtualRegister; ++Reg) {
354 if (GetGroup(Reg) == Group)
359 unsigned SchedulePostRATDList::UnionGroups(unsigned Reg1, unsigned Reg2)
361 assert(GroupNodes[0] == 0 && "GroupNode 0 not parent!");
362 assert(GroupNodeIndices[0] == 0 && "Reg 0 not in Group 0!");
364 // find group for each register
365 unsigned Group1 = GetGroup(Reg1);
366 unsigned Group2 = GetGroup(Reg2);
368 // if either group is 0, then that must become the parent
369 unsigned Parent = (Group1 == 0) ? Group1 : Group2;
370 unsigned Other = (Parent == Group1) ? Group2 : Group1;
371 GroupNodes.at(Other) = Parent;
375 unsigned SchedulePostRATDList::LeaveGroup(unsigned Reg)
377 // Create a new GroupNode for Reg. Reg's existing GroupNode must
378 // stay as is because there could be other GroupNodes referring to
380 unsigned idx = GroupNodes.size();
381 GroupNodes.push_back(idx);
382 GroupNodeIndices[Reg] = idx;
386 bool SchedulePostRATDList::IsLive(unsigned Reg)
388 // KillIndex must be defined and DefIndex not defined for a register
390 return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u));
393 /// StartBlock - Initialize register live-range state for scheduling in
396 void SchedulePostRATDList::StartBlock(MachineBasicBlock *BB) {
397 // Call the superclass.
398 ScheduleDAGInstrs::StartBlock(BB);
400 // Reset the hazard recognizer.
403 // Initialize all registers to be in their own group. Initially we
404 // assign the register to the same-indexed GroupNode.
405 for (unsigned i = 0; i < TargetRegisterInfo::FirstVirtualRegister; ++i)
406 GroupNodeIndices[i] = i;
408 // Initialize the indices to indicate that no registers are live.
409 std::fill(KillIndices, array_endof(KillIndices), ~0u);
410 std::fill(DefIndices, array_endof(DefIndices), BB->size());
412 bool IsReturnBlock = (!BB->empty() && BB->back().getDesc().isReturn());
414 // Determine the live-out physregs for this block.
416 // In a return block, examine the function live-out regs.
417 for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(),
418 E = MRI.liveout_end(); I != E; ++I) {
421 KillIndices[Reg] = BB->size();
422 DefIndices[Reg] = ~0u;
423 // Repeat, for all aliases.
424 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
425 unsigned AliasReg = *Alias;
426 UnionGroups(AliasReg, 0);
427 KillIndices[AliasReg] = BB->size();
428 DefIndices[AliasReg] = ~0u;
432 // In a non-return block, examine the live-in regs of all successors.
433 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
434 SE = BB->succ_end(); SI != SE; ++SI)
435 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
436 E = (*SI)->livein_end(); I != E; ++I) {
439 KillIndices[Reg] = BB->size();
440 DefIndices[Reg] = ~0u;
441 // Repeat, for all aliases.
442 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
443 unsigned AliasReg = *Alias;
444 UnionGroups(AliasReg, 0);
445 KillIndices[AliasReg] = BB->size();
446 DefIndices[AliasReg] = ~0u;
451 // Mark live-out callee-saved registers. In a return block this is
452 // all callee-saved registers. In non-return this is any
453 // callee-saved register that is not saved in the prolog.
454 const MachineFrameInfo *MFI = MF.getFrameInfo();
455 BitVector Pristine = MFI->getPristineRegs(BB);
456 for (const unsigned *I = TRI->getCalleeSavedRegs(); *I; ++I) {
458 if (!IsReturnBlock && !Pristine.test(Reg)) continue;
460 KillIndices[Reg] = BB->size();
461 DefIndices[Reg] = ~0u;
462 // Repeat, for all aliases.
463 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
464 unsigned AliasReg = *Alias;
465 UnionGroups(AliasReg, 0);
466 KillIndices[AliasReg] = BB->size();
467 DefIndices[AliasReg] = ~0u;
472 /// Schedule - Schedule the instruction range using list scheduling.
474 void SchedulePostRATDList::Schedule() {
475 DEBUG(errs() << "********** List Scheduling **********\n");
477 // Build the scheduling graph.
480 if (EnableAntiDepBreaking != "none") {
481 if (BreakAntiDependencies((EnableAntiDepBreaking == "all") ? false : true)) {
482 // We made changes. Update the dependency graph.
483 // Theoretically we could update the graph in place:
484 // When a live range is changed to use a different register, remove
485 // the def's anti-dependence *and* output-dependence edges due to
486 // that register, and add new anti-dependence and output-dependence
487 // edges based on the next live range of the register.
495 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
496 SUnits[su].dumpAll(this));
498 AvailableQueue.initNodes(SUnits);
500 ListScheduleTopDown();
502 AvailableQueue.releaseState();
505 /// Observe - Update liveness information to account for the current
506 /// instruction, which will not be scheduled.
508 void SchedulePostRATDList::Observe(MachineInstr *MI, unsigned Count) {
509 assert(Count < InsertPosIndex && "Instruction index out of expected range!");
511 DEBUG(errs() << "Observe: ");
514 for (unsigned Reg = 0; Reg != TargetRegisterInfo::FirstVirtualRegister; ++Reg) {
515 // If Reg is current live, then mark that it can't be renamed as
516 // we don't know the extent of its live-range anymore (now that it
517 // has been scheduled). If it is not live but was defined in the
518 // previous schedule region, then set its def index to the most
519 // conservative location (i.e. the beginning of the previous
522 DEBUG(if (GetGroup(Reg) != 0)
523 errs() << " " << TRI->getName(Reg) << "=g" <<
524 GetGroup(Reg) << "->g0(region live-out)");
526 } else if ((DefIndices[Reg] < InsertPosIndex) && (DefIndices[Reg] >= Count)) {
527 DefIndices[Reg] = Count;
531 PrescanInstruction(MI, Count);
532 ScanInstruction(MI, Count);
535 /// FinishBlock - Clean up register live-range state.
537 void SchedulePostRATDList::FinishBlock() {
540 // Call the superclass.
541 ScheduleDAGInstrs::FinishBlock();
544 /// CriticalPathStep - Return the next SUnit after SU on the bottom-up
546 static SDep *CriticalPathStep(SUnit *SU) {
548 unsigned NextDepth = 0;
549 // Find the predecessor edge with the greatest depth.
550 for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
552 SUnit *PredSU = P->getSUnit();
553 unsigned PredLatency = P->getLatency();
554 unsigned PredTotalLatency = PredSU->getDepth() + PredLatency;
555 // In the case of a latency tie, prefer an anti-dependency edge over
556 // other types of edges.
557 if (NextDepth < PredTotalLatency ||
558 (NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) {
559 NextDepth = PredTotalLatency;
566 /// AntiDepPathStep - Return SUnit that SU has an anti-dependence on.
567 static SDep *AntiDepPathStep(SUnit *SU) {
568 for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end();
570 if (P->getKind() == SDep::Anti) {
577 void SchedulePostRATDList::PrescanInstruction(MachineInstr *MI, unsigned Count) {
578 // Scan the register defs for this instruction and update
579 // live-ranges, groups and RegRefs.
580 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
581 MachineOperand &MO = MI->getOperand(i);
582 if (!MO.isReg() || !MO.isDef()) continue;
583 unsigned Reg = MO.getReg();
584 if (Reg == 0) continue;
585 // Ignore two-addr defs for liveness...
586 if (MI->isRegTiedToUseOperand(i)) continue;
588 // Update Def for Reg and subregs.
589 DefIndices[Reg] = Count;
590 for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
592 unsigned SubregReg = *Subreg;
593 DefIndices[SubregReg] = Count;
597 DEBUG(errs() << "\tDef Groups:");
598 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
599 MachineOperand &MO = MI->getOperand(i);
600 if (!MO.isReg() || !MO.isDef()) continue;
601 unsigned Reg = MO.getReg();
602 if (Reg == 0) continue;
604 DEBUG(errs() << " " << TRI->getName(Reg) << "=g" << GetGroup(Reg));
606 // If MI's defs have special allocation requirement, don't allow
607 // any def registers to be changed. Also assume all registers
608 // defined in a call must not be changed (ABI).
609 if (MI->getDesc().isCall() || MI->getDesc().hasExtraDefRegAllocReq()) {
610 DEBUG(if (GetGroup(Reg) != 0) errs() << "->g0(alloc-req)");
614 // Any subregisters that are live at this point are defined here,
615 // so group those subregisters with Reg.
616 for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
618 unsigned SubregReg = *Subreg;
619 if (IsLive(SubregReg)) {
620 UnionGroups(Reg, SubregReg);
621 DEBUG(errs() << "->g" << GetGroup(Reg) << "(via " <<
622 TRI->getName(SubregReg) << ")");
626 // Note register reference...
627 const TargetRegisterClass *RC = NULL;
628 if (i < MI->getDesc().getNumOperands())
629 RC = MI->getDesc().OpInfo[i].getRegClass(TRI);
630 RegisterReference RR = { &MO, RC };
631 RegRefs.insert(std::make_pair(Reg, RR));
634 DEBUG(errs() << '\n');
637 void SchedulePostRATDList::ScanInstruction(MachineInstr *MI,
639 DEBUG(errs() << "\tUse Groups:");
641 // Scan the register uses for this instruction and update
642 // live-ranges, groups and RegRefs.
643 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
644 MachineOperand &MO = MI->getOperand(i);
645 if (!MO.isReg() || !MO.isUse()) continue;
646 unsigned Reg = MO.getReg();
647 if (Reg == 0) continue;
649 DEBUG(errs() << " " << TRI->getName(Reg) << "=g" << GetGroup(Reg));
651 // It wasn't previously live but now it is, this is a kill. Forget
652 // the previous live-range information and start a new live-range
655 KillIndices[Reg] = Count;
656 DefIndices[Reg] = ~0u;
659 DEBUG(errs() << "->g" << GetGroup(Reg) << "(last-use)");
661 // Repeat, for subregisters.
662 for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
664 unsigned SubregReg = *Subreg;
665 if (!IsLive(SubregReg)) {
666 KillIndices[SubregReg] = Count;
667 DefIndices[SubregReg] = ~0u;
668 RegRefs.erase(SubregReg);
669 LeaveGroup(SubregReg);
670 DEBUG(errs() << "->g" << GetGroup(SubregReg) << "(last-use)");
674 // If MI's uses have special allocation requirement, don't allow
675 // any use registers to be changed. Also assume all registers
676 // used in a call must not be changed (ABI).
677 if (MI->getDesc().isCall() || MI->getDesc().hasExtraSrcRegAllocReq()) {
678 DEBUG(if (GetGroup(Reg) != 0) errs() << "->g0(alloc-req)");
682 // Note register reference...
683 const TargetRegisterClass *RC = NULL;
684 if (i < MI->getDesc().getNumOperands())
685 RC = MI->getDesc().OpInfo[i].getRegClass(TRI);
686 RegisterReference RR = { &MO, RC };
687 RegRefs.insert(std::make_pair(Reg, RR));
690 DEBUG(errs() << '\n');
692 // Form a group of all defs and uses of a KILL instruction to ensure
693 // that all registers are renamed as a group.
694 if (MI->getOpcode() == TargetInstrInfo::KILL) {
695 unsigned FirstReg = 0;
696 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
697 MachineOperand &MO = MI->getOperand(i);
698 if (!MO.isReg()) continue;
699 unsigned Reg = MO.getReg();
700 if (Reg == 0) continue;
703 UnionGroups(FirstReg, Reg);
707 DEBUG(if (FirstReg != 0) errs() << "\tKill Group: g" <<
708 GetGroup(FirstReg) << '\n');
712 unsigned SchedulePostRATDList::FindSuitableFreeRegister(unsigned AntiDepReg) {
713 // Collect all registers in the same group as AntiDepReg. These all
714 // need to be renamed together if we are to break the
716 std::vector<unsigned> Regs;
717 GetGroupRegs(GetGroup(AntiDepReg), Regs);
719 DEBUG(errs() << "\tRename Register Group:");
720 DEBUG(for (unsigned i = 0, e = Regs.size(); i != e; ++i)
721 DEBUG(errs() << " " << TRI->getName(Regs[i])));
722 DEBUG(errs() << "\n");
724 // If there is a single register that needs to be renamed then we
725 // can do it ourselves.
726 if (Regs.size() == 1) {
727 assert(Regs[0] == AntiDepReg && "Register group does not contain register!");
729 // Check all references that need rewriting. Gather up all the
730 // register classes for the register references.
731 const TargetRegisterClass *FirstRC = NULL;
732 std::set<const TargetRegisterClass *> RCs;
733 std::pair<std::multimap<unsigned, RegisterReference>::iterator,
734 std::multimap<unsigned, RegisterReference>::iterator>
735 Range = RegRefs.equal_range(AntiDepReg);
736 for (std::multimap<unsigned, RegisterReference>::iterator
737 Q = Range.first, QE = Range.second; Q != QE; ++Q) {
738 const TargetRegisterClass *RC = Q->second.RC;
739 if (RC == NULL) continue;
742 else if (FirstRC != RC)
749 DEBUG(errs() << "\tChecking Regclasses: " << FirstRC->getName());
750 DEBUG(for (std::set<const TargetRegisterClass *>::iterator S =
751 RCs.begin(), E = RCs.end(); S != E; ++S)
752 errs() << " " << (*S)->getName());
753 DEBUG(errs() << '\n');
755 // Using the allocation order for one of the register classes,
756 // find the first register that belongs to all the register
757 // classes that is available over the liverange of the register.
758 DEBUG(errs() << "\tFind Register:");
759 for (TargetRegisterClass::iterator R = FirstRC->allocation_order_begin(MF),
760 RE = FirstRC->allocation_order_end(MF); R != RE; ++R) {
761 unsigned NewReg = *R;
763 // Don't replace a register with itself.
764 if (NewReg == AntiDepReg) continue;
766 DEBUG(errs() << " " << TRI->getName(NewReg));
768 // Make sure NewReg is in all required register classes.
769 for (std::set<const TargetRegisterClass *>::iterator S =
770 RCs.begin(), E = RCs.end(); S != E; ++S) {
771 const TargetRegisterClass *RC = *S;
772 if (!RC->contains(NewReg)) {
773 DEBUG(errs() << "(not in " << RC->getName() << ")");
779 // If NewReg is dead and NewReg's most recent def is not before
780 // AntiDepReg's kill, it's safe to replace AntiDepReg with
781 // NewReg. We must also check all subregisters of NewReg.
782 if (IsLive(NewReg) || (KillIndices[AntiDepReg] > DefIndices[NewReg])) {
783 DEBUG(errs() << "(live)");
788 for (const unsigned *Subreg = TRI->getSubRegisters(NewReg);
790 unsigned SubregReg = *Subreg;
791 if (IsLive(SubregReg) || (KillIndices[AntiDepReg] > DefIndices[SubregReg])) {
792 DEBUG(errs() << "(subreg " << TRI->getName(SubregReg) << " live)");
801 DEBUG(errs() << '\n');
806 DEBUG(errs() << '\n');
809 // No registers are free and available!
813 /// BreakAntiDependencies - Identifiy anti-dependencies along the critical path
814 /// of the ScheduleDAG and break them by renaming registers.
816 bool SchedulePostRATDList::BreakAntiDependencies(bool CriticalPathOnly) {
817 // The code below assumes that there is at least one instruction,
818 // so just duck out immediately if the block is empty.
819 if (SUnits.empty()) return false;
821 // If breaking anti-dependencies only along the critical path, track
822 // progress along the critical path through the SUnit graph as we
823 // walk the instructions.
824 SUnit *CriticalPathSU = 0;
825 MachineInstr *CriticalPathMI = 0;
827 // If breaking all anti-dependencies need a map from MI to SUnit.
828 std::map<MachineInstr *, SUnit *> MISUnitMap;
830 // Find the node at the bottom of the critical path.
831 if (CriticalPathOnly) {
833 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
834 SUnit *SU = &SUnits[i];
835 if (!Max || SU->getDepth() + SU->Latency > Max->getDepth() + Max->Latency)
839 DEBUG(errs() << "Critical path has total latency "
840 << (Max->getDepth() + Max->Latency) << "\n");
841 CriticalPathSU = Max;
842 CriticalPathMI = CriticalPathSU->getInstr();
844 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
845 SUnit *SU = &SUnits[i];
846 MISUnitMap.insert(std::pair<MachineInstr *, SUnit *>(SU->getInstr(), SU));
848 DEBUG(errs() << "Breaking all anti-dependencies\n");
853 DEBUG(errs() << "Available regs:");
854 for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) {
856 DEBUG(errs() << " " << TRI->getName(Reg));
858 DEBUG(errs() << '\n');
863 // Attempt to break anti-dependence edges. Walk the instructions
864 // from the bottom up, tracking information about liveness as we go
865 // to help determine which registers are available.
866 bool Changed = false;
867 unsigned Count = InsertPosIndex - 1;
868 for (MachineBasicBlock::iterator I = InsertPos, E = Begin;
870 MachineInstr *MI = --I;
872 DEBUG(errs() << "Anti: ");
875 // Process the defs in MI...
876 PrescanInstruction(MI, Count);
878 // Check if this instruction has an anti-dependence that we may be
879 // able to break. If it is, set AntiDepReg to the non-zero
880 // register associated with the anti-dependence.
882 unsigned AntiDepReg = 0;
884 // Limiting our attention to the critical path is a heuristic to avoid
885 // breaking anti-dependence edges that aren't going to significantly
886 // impact the overall schedule. There are a limited number of registers
887 // and we want to save them for the important edges.
889 // We can also break all anti-dependencies because they can
890 // occur along the non-critical path but are still detrimental for
893 // TODO: Instructions with multiple defs could have multiple
894 // anti-dependencies. The current code here only knows how to break one
895 // edge per instruction. Note that we'd have to be able to break all of
896 // the anti-dependencies in an instruction in order to be effective.
897 if (!CriticalPathOnly || (MI == CriticalPathMI)) {
898 DEBUG(dbgStr.clear());
902 if (CriticalPathOnly) {
903 PathSU = CriticalPathSU;
904 Edge = CriticalPathStep(PathSU);
906 PathSU = MISUnitMap[MI];
907 Edge = (PathSU) ? AntiDepPathStep(PathSU) : 0;
911 SUnit *NextSU = Edge->getSUnit();
913 // Only consider anti-dependence edges, and ignore KILL
914 // instructions (they form a group in ScanInstruction but
915 // don't cause any anti-dependence breaking themselves)
916 if ((Edge->getKind() == SDep::Anti) &&
917 (MI->getOpcode() != TargetInstrInfo::KILL)) {
918 AntiDepReg = Edge->getReg();
919 DEBUG(dbgStr += "\tAntidep reg: ");
920 DEBUG(dbgStr += TRI->getName(AntiDepReg));
921 assert(AntiDepReg != 0 && "Anti-dependence on reg0?");
922 if (!AllocatableSet.test(AntiDepReg)) {
923 // Don't break anti-dependencies on non-allocatable registers.
924 DEBUG(dbgStr += " (non-allocatable)");
927 int OpIdx = MI->findRegisterDefOperandIdx(AntiDepReg);
928 assert(OpIdx != -1 && "Can't find index for defined register operand");
929 if (MI->isRegTiedToUseOperand(OpIdx)) {
930 // If the anti-dep register is tied to a use, then don't try to
931 // change it. It will be changed along with the use if required
932 // to break an earlier antidep.
933 DEBUG(dbgStr += " (tied-to-use)");
936 // If the SUnit has other dependencies on the SUnit that
937 // it anti-depends on, don't bother breaking the
938 // anti-dependency since those edges would prevent such
939 // units from being scheduled past each other
942 // Also, if there are dependencies on other SUnits with
943 // the same register as the anti-dependency, don't
944 // attempt to break it.
945 for (SUnit::pred_iterator P = PathSU->Preds.begin(),
946 PE = PathSU->Preds.end(); P != PE; ++P) {
947 if (P->getSUnit() == NextSU ?
948 (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) :
949 (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) {
950 DEBUG(dbgStr += " (real dependency)");
959 if (CriticalPathOnly) {
960 CriticalPathSU = NextSU;
961 CriticalPathMI = CriticalPathSU->getInstr();
964 // We've reached the end of the critical path.
970 // Determine AntiDepReg's register group.
971 const unsigned GroupIndex = AntiDepReg != 0 ? GetGroup(AntiDepReg) : 0;
972 if (GroupIndex == 0) {
973 DEBUG(if (AntiDepReg != 0) dbgStr += " (zero group)");
977 DEBUG(if (!dbgStr.empty()) errs() << dbgStr << '\n');
979 // Look for a suitable register to use to break the anti-dependence.
980 if (AntiDepReg != 0) {
981 if (unsigned NewReg = FindSuitableFreeRegister(AntiDepReg)) {
982 DEBUG(errs() << "\tBreaking anti-dependence edge on "
983 << TRI->getName(AntiDepReg)
984 << " with " << RegRefs.count(AntiDepReg) << " references"
985 << " using " << TRI->getName(NewReg) << "!\n");
987 // Update the references to the old register to refer to the new
989 std::pair<std::multimap<unsigned, RegisterReference>::iterator,
990 std::multimap<unsigned, RegisterReference>::iterator>
991 Range = RegRefs.equal_range(AntiDepReg);
992 for (std::multimap<unsigned, RegisterReference>::iterator
993 Q = Range.first, QE = Range.second; Q != QE; ++Q)
994 Q->second.Operand->setReg(NewReg);
996 // We just went back in time and modified history; the
997 // liveness information for the anti-dependence reg is now
998 // inconsistent. Set the state as if it were dead.
999 // FIXME forall in group
1000 UnionGroups(NewReg, 0);
1001 RegRefs.erase(NewReg);
1002 DefIndices[NewReg] = DefIndices[AntiDepReg];
1003 KillIndices[NewReg] = KillIndices[AntiDepReg];
1005 // FIXME forall in group
1006 UnionGroups(AntiDepReg, 0);
1007 RegRefs.erase(AntiDepReg);
1008 DefIndices[AntiDepReg] = KillIndices[AntiDepReg];
1009 KillIndices[AntiDepReg] = ~0u;
1010 assert(((KillIndices[AntiDepReg] == ~0u) !=
1011 (DefIndices[AntiDepReg] == ~0u)) &&
1012 "Kill and Def maps aren't consistent for AntiDepReg!");
1019 ScanInstruction(MI, Count);
1025 /// StartBlockForKills - Initialize register live-range state for updating kills
1027 void SchedulePostRATDList::StartBlockForKills(MachineBasicBlock *BB) {
1028 // Initialize the indices to indicate that no registers are live.
1029 std::fill(KillIndices, array_endof(KillIndices), ~0u);
1031 // Determine the live-out physregs for this block.
1032 if (!BB->empty() && BB->back().getDesc().isReturn()) {
1033 // In a return block, examine the function live-out regs.
1034 for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(),
1035 E = MRI.liveout_end(); I != E; ++I) {
1037 KillIndices[Reg] = BB->size();
1038 // Repeat, for all subregs.
1039 for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
1040 *Subreg; ++Subreg) {
1041 KillIndices[*Subreg] = BB->size();
1046 // In a non-return block, examine the live-in regs of all successors.
1047 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
1048 SE = BB->succ_end(); SI != SE; ++SI) {
1049 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
1050 E = (*SI)->livein_end(); I != E; ++I) {
1052 KillIndices[Reg] = BB->size();
1053 // Repeat, for all subregs.
1054 for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
1055 *Subreg; ++Subreg) {
1056 KillIndices[*Subreg] = BB->size();
1063 bool SchedulePostRATDList::ToggleKillFlag(MachineInstr *MI,
1064 MachineOperand &MO) {
1065 // Setting kill flag...
1071 // If MO itself is live, clear the kill flag...
1072 if (KillIndices[MO.getReg()] != ~0u) {
1073 MO.setIsKill(false);
1077 // If any subreg of MO is live, then create an imp-def for that
1078 // subreg and keep MO marked as killed.
1079 MO.setIsKill(false);
1080 bool AllDead = true;
1081 const unsigned SuperReg = MO.getReg();
1082 for (const unsigned *Subreg = TRI->getSubRegisters(SuperReg);
1083 *Subreg; ++Subreg) {
1084 if (KillIndices[*Subreg] != ~0u) {
1085 MI->addOperand(MachineOperand::CreateReg(*Subreg,
1099 /// FixupKills - Fix the register kill flags, they may have been made
1100 /// incorrect by instruction reordering.
1102 void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) {
1103 DEBUG(errs() << "Fixup kills for BB ID#" << MBB->getNumber() << '\n');
1105 std::set<unsigned> killedRegs;
1106 BitVector ReservedRegs = TRI->getReservedRegs(MF);
1108 StartBlockForKills(MBB);
1110 // Examine block from end to start...
1111 unsigned Count = MBB->size();
1112 for (MachineBasicBlock::iterator I = MBB->end(), E = MBB->begin();
1114 MachineInstr *MI = --I;
1116 // Update liveness. Registers that are defed but not used in this
1117 // instruction are now dead. Mark register and all subregs as they
1118 // are completely defined.
1119 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1120 MachineOperand &MO = MI->getOperand(i);
1121 if (!MO.isReg()) continue;
1122 unsigned Reg = MO.getReg();
1123 if (Reg == 0) continue;
1124 if (!MO.isDef()) continue;
1125 // Ignore two-addr defs.
1126 if (MI->isRegTiedToUseOperand(i)) continue;
1128 KillIndices[Reg] = ~0u;
1130 // Repeat for all subregs.
1131 for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
1132 *Subreg; ++Subreg) {
1133 KillIndices[*Subreg] = ~0u;
1137 // Examine all used registers and set/clear kill flag. When a
1138 // register is used multiple times we only set the kill flag on
1141 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1142 MachineOperand &MO = MI->getOperand(i);
1143 if (!MO.isReg() || !MO.isUse()) continue;
1144 unsigned Reg = MO.getReg();
1145 if ((Reg == 0) || ReservedRegs.test(Reg)) continue;
1148 if (killedRegs.find(Reg) == killedRegs.end()) {
1150 // A register is not killed if any subregs are live...
1151 for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
1152 *Subreg; ++Subreg) {
1153 if (KillIndices[*Subreg] != ~0u) {
1159 // If subreg is not live, then register is killed if it became
1160 // live in this instruction
1162 kill = (KillIndices[Reg] == ~0u);
1165 if (MO.isKill() != kill) {
1166 bool removed = ToggleKillFlag(MI, MO);
1168 DEBUG(errs() << "Fixed <removed> in ");
1170 DEBUG(errs() << "Fixed " << MO << " in ");
1175 killedRegs.insert(Reg);
1178 // Mark any used register (that is not using undef) and subregs as
1180 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1181 MachineOperand &MO = MI->getOperand(i);
1182 if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue;
1183 unsigned Reg = MO.getReg();
1184 if ((Reg == 0) || ReservedRegs.test(Reg)) continue;
1186 KillIndices[Reg] = Count;
1188 for (const unsigned *Subreg = TRI->getSubRegisters(Reg);
1189 *Subreg; ++Subreg) {
1190 KillIndices[*Subreg] = Count;
1196 //===----------------------------------------------------------------------===//
1197 // Top-Down Scheduling
1198 //===----------------------------------------------------------------------===//
1200 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
1201 /// the PendingQueue if the count reaches zero. Also update its cycle bound.
1202 void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
1203 SUnit *SuccSU = SuccEdge->getSUnit();
1206 if (SuccSU->NumPredsLeft == 0) {
1207 errs() << "*** Scheduling failed! ***\n";
1209 errs() << " has been released too many times!\n";
1210 llvm_unreachable(0);
1213 --SuccSU->NumPredsLeft;
1215 // Compute how many cycles it will be before this actually becomes
1216 // available. This is the max of the start time of all predecessors plus
1218 SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency());
1220 // If all the node's predecessors are scheduled, this node is ready
1221 // to be scheduled. Ignore the special ExitSU node.
1222 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
1223 PendingQueue.push_back(SuccSU);
1226 /// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors.
1227 void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) {
1228 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1230 ReleaseSucc(SU, &*I);
1233 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
1234 /// count of its successors. If a successor pending count is zero, add it to
1235 /// the Available queue.
1236 void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
1237 DEBUG(errs() << "*** Scheduling [" << CurCycle << "]: ");
1238 DEBUG(SU->dump(this));
1240 Sequence.push_back(SU);
1241 assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!");
1242 SU->setDepthToAtLeast(CurCycle);
1244 ReleaseSuccessors(SU);
1245 SU->isScheduled = true;
1246 AvailableQueue.ScheduledNode(SU);
1249 /// ListScheduleTopDown - The main loop of list scheduling for top-down
1251 void SchedulePostRATDList::ListScheduleTopDown() {
1252 unsigned CurCycle = 0;
1254 // Release any successors of the special Entry node.
1255 ReleaseSuccessors(&EntrySU);
1257 // All leaves to Available queue.
1258 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
1259 // It is available if it has no predecessors.
1260 if (SUnits[i].Preds.empty()) {
1261 AvailableQueue.push(&SUnits[i]);
1262 SUnits[i].isAvailable = true;
1266 // In any cycle where we can't schedule any instructions, we must
1267 // stall or emit a noop, depending on the target.
1268 bool CycleHasInsts = false;
1270 // While Available queue is not empty, grab the node with the highest
1271 // priority. If it is not ready put it back. Schedule the node.
1272 std::vector<SUnit*> NotReady;
1273 Sequence.reserve(SUnits.size());
1274 while (!AvailableQueue.empty() || !PendingQueue.empty()) {
1275 // Check to see if any of the pending instructions are ready to issue. If
1276 // so, add them to the available queue.
1277 unsigned MinDepth = ~0u;
1278 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
1279 if (PendingQueue[i]->getDepth() <= CurCycle) {
1280 AvailableQueue.push(PendingQueue[i]);
1281 PendingQueue[i]->isAvailable = true;
1282 PendingQueue[i] = PendingQueue.back();
1283 PendingQueue.pop_back();
1285 } else if (PendingQueue[i]->getDepth() < MinDepth)
1286 MinDepth = PendingQueue[i]->getDepth();
1289 DEBUG(errs() << "\n*** Examining Available\n";
1290 LatencyPriorityQueue q = AvailableQueue;
1291 while (!q.empty()) {
1292 SUnit *su = q.pop();
1293 errs() << "Height " << su->getHeight() << ": ";
1297 SUnit *FoundSUnit = 0;
1299 bool HasNoopHazards = false;
1300 while (!AvailableQueue.empty()) {
1301 SUnit *CurSUnit = AvailableQueue.pop();
1303 ScheduleHazardRecognizer::HazardType HT =
1304 HazardRec->getHazardType(CurSUnit);
1305 if (HT == ScheduleHazardRecognizer::NoHazard) {
1306 FoundSUnit = CurSUnit;
1310 // Remember if this is a noop hazard.
1311 HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard;
1313 NotReady.push_back(CurSUnit);
1316 // Add the nodes that aren't ready back onto the available list.
1317 if (!NotReady.empty()) {
1318 AvailableQueue.push_all(NotReady);
1322 // If we found a node to schedule, do it now.
1324 ScheduleNodeTopDown(FoundSUnit, CurCycle);
1325 HazardRec->EmitInstruction(FoundSUnit);
1326 CycleHasInsts = true;
1328 // If we are using the target-specific hazards, then don't
1329 // advance the cycle time just because we schedule a node. If
1330 // the target allows it we can schedule multiple nodes in the
1332 if (!EnablePostRAHazardAvoidance) {
1333 if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops!
1337 if (CycleHasInsts) {
1338 DEBUG(errs() << "*** Finished cycle " << CurCycle << '\n');
1339 HazardRec->AdvanceCycle();
1340 } else if (!HasNoopHazards) {
1341 // Otherwise, we have a pipeline stall, but no other problem,
1342 // just advance the current cycle and try again.
1343 DEBUG(errs() << "*** Stall in cycle " << CurCycle << '\n');
1344 HazardRec->AdvanceCycle();
1347 // Otherwise, we have no instructions to issue and we have instructions
1348 // that will fault if we don't do this right. This is the case for
1349 // processors without pipeline interlocks and other cases.
1350 DEBUG(errs() << "*** Emitting noop in cycle " << CurCycle << '\n');
1351 HazardRec->EmitNoop();
1352 Sequence.push_back(0); // NULL here means noop
1357 CycleHasInsts = false;
1362 VerifySchedule(/*isBottomUp=*/false);
1366 //===----------------------------------------------------------------------===//
1367 // Public Constructor Functions
1368 //===----------------------------------------------------------------------===//
1370 FunctionPass *llvm::createPostRAScheduler(CodeGenOpt::Level OptLevel) {
1371 return new PostRAScheduler(OptLevel);