PostRASchedulerList.cpp revision 57796906e96fa68af19262323496e4b9c038a516
1//===----- SchedulePostRAList.cpp - list scheduler ------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 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. 14// 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. 18// 19//===----------------------------------------------------------------------===// 20 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" 45#include <map> 46#include <set> 47using namespace llvm; 48 49STATISTIC(NumNoops, "Number of noops inserted"); 50STATISTIC(NumStalls, "Number of pipeline stalls"); 51 52// Post-RA scheduling is enabled with 53// TargetSubtarget.enablePostRAScheduler(). This flag can be used to 54// override the target. 55static cl::opt<bool> 56EnablePostRAScheduler("post-RA-scheduler", 57 cl::desc("Enable scheduling after register allocation"), 58 cl::init(false), cl::Hidden); 59static cl::opt<bool> 60EnableAntiDepBreaking("break-anti-dependencies", 61 cl::desc("Break post-RA scheduling anti-dependencies"), 62 cl::init(true), cl::Hidden); 63static cl::opt<bool> 64EnablePostRAHazardAvoidance("avoid-hazards", 65 cl::desc("Enable exact hazard avoidance"), 66 cl::init(true), cl::Hidden); 67 68// If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod 69static cl::opt<int> 70DebugDiv("postra-sched-debugdiv", 71 cl::desc("Debug control MBBs that are scheduled"), 72 cl::init(0), cl::Hidden); 73static cl::opt<int> 74DebugMod("postra-sched-debugmod", 75 cl::desc("Debug control MBBs that are scheduled"), 76 cl::init(0), cl::Hidden); 77 78namespace { 79 class VISIBILITY_HIDDEN PostRAScheduler : public MachineFunctionPass { 80 AliasAnalysis *AA; 81 82 public: 83 static char ID; 84 PostRAScheduler() : MachineFunctionPass(&ID) {} 85 86 void getAnalysisUsage(AnalysisUsage &AU) const { 87 AU.setPreservesCFG(); 88 AU.addRequired<AliasAnalysis>(); 89 AU.addRequired<MachineDominatorTree>(); 90 AU.addPreserved<MachineDominatorTree>(); 91 AU.addRequired<MachineLoopInfo>(); 92 AU.addPreserved<MachineLoopInfo>(); 93 MachineFunctionPass::getAnalysisUsage(AU); 94 } 95 96 const char *getPassName() const { 97 return "Post RA top-down list latency scheduler"; 98 } 99 100 bool runOnMachineFunction(MachineFunction &Fn); 101 }; 102 char PostRAScheduler::ID = 0; 103 104 class VISIBILITY_HIDDEN SchedulePostRATDList : public ScheduleDAGInstrs { 105 /// AvailableQueue - The priority queue to use for the available SUnits. 106 /// 107 LatencyPriorityQueue AvailableQueue; 108 109 /// PendingQueue - This contains all of the instructions whose operands have 110 /// been issued, but their results are not ready yet (due to the latency of 111 /// the operation). Once the operands becomes available, the instruction is 112 /// added to the AvailableQueue. 113 std::vector<SUnit*> PendingQueue; 114 115 /// Topo - A topological ordering for SUnits. 116 ScheduleDAGTopologicalSort Topo; 117 118 /// AllocatableSet - The set of allocatable registers. 119 /// We'll be ignoring anti-dependencies on non-allocatable registers, 120 /// because they may not be safe to break. 121 const BitVector AllocatableSet; 122 123 /// HazardRec - The hazard recognizer to use. 124 ScheduleHazardRecognizer *HazardRec; 125 126 /// AA - AliasAnalysis for making memory reference queries. 127 AliasAnalysis *AA; 128 129 /// Classes - For live regs that are only used in one register class in a 130 /// live range, the register class. If the register is not live, the 131 /// corresponding value is null. If the register is live but used in 132 /// multiple register classes, the corresponding value is -1 casted to a 133 /// pointer. 134 const TargetRegisterClass * 135 Classes[TargetRegisterInfo::FirstVirtualRegister]; 136 137 /// RegRegs - Map registers to all their references within a live range. 138 std::multimap<unsigned, MachineOperand *> RegRefs; 139 140 /// KillIndices - The index of the most recent kill (proceding bottom-up), 141 /// or ~0u if the register is not live. 142 unsigned KillIndices[TargetRegisterInfo::FirstVirtualRegister]; 143 144 /// DefIndices - The index of the most recent complete def (proceding bottom 145 /// up), or ~0u if the register is live. 146 unsigned DefIndices[TargetRegisterInfo::FirstVirtualRegister]; 147 148 /// KeepRegs - A set of registers which are live and cannot be changed to 149 /// break anti-dependencies. 150 SmallSet<unsigned, 4> KeepRegs; 151 152 public: 153 SchedulePostRATDList(MachineFunction &MF, 154 const MachineLoopInfo &MLI, 155 const MachineDominatorTree &MDT, 156 ScheduleHazardRecognizer *HR, 157 AliasAnalysis *aa) 158 : ScheduleDAGInstrs(MF, MLI, MDT), Topo(SUnits), 159 AllocatableSet(TRI->getAllocatableSet(MF)), 160 HazardRec(HR), AA(aa) {} 161 162 ~SchedulePostRATDList() { 163 delete HazardRec; 164 } 165 166 /// StartBlock - Initialize register live-range state for scheduling in 167 /// this block. 168 /// 169 void StartBlock(MachineBasicBlock *BB); 170 171 /// Schedule - Schedule the instruction range using list scheduling. 172 /// 173 void Schedule(); 174 175 /// FixupKills - Fix register kill flags that have been made 176 /// invalid due to scheduling 177 /// 178 void FixupKills(MachineBasicBlock *MBB); 179 180 /// Observe - Update liveness information to account for the current 181 /// instruction, which will not be scheduled. 182 /// 183 void Observe(MachineInstr *MI, unsigned Count); 184 185 /// FinishBlock - Clean up register live-range state. 186 /// 187 void FinishBlock(); 188 189 private: 190 void PrescanInstruction(MachineInstr *MI); 191 void ScanInstruction(MachineInstr *MI, unsigned Count); 192 void ReleaseSucc(SUnit *SU, SDep *SuccEdge); 193 void ReleaseSuccessors(SUnit *SU); 194 void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 195 void ListScheduleTopDown(); 196 bool BreakAntiDependencies(); 197 unsigned findSuitableFreeRegister(unsigned AntiDepReg, 198 unsigned LastNewReg, 199 const TargetRegisterClass *); 200 void StartBlockForKills(MachineBasicBlock *BB); 201 202 // ToggleKillFlag - Toggle a register operand kill flag. Other 203 // adjustments may be made to the instruction if necessary. Return 204 // true if the operand has been deleted, false if not. 205 bool ToggleKillFlag(MachineInstr *MI, MachineOperand &MO); 206 }; 207} 208 209/// isSchedulingBoundary - Test if the given instruction should be 210/// considered a scheduling boundary. This primarily includes labels 211/// and terminators. 212/// 213static bool isSchedulingBoundary(const MachineInstr *MI, 214 const MachineFunction &MF) { 215 // Terminators and labels can't be scheduled around. 216 if (MI->getDesc().isTerminator() || MI->isLabel()) 217 return true; 218 219 // Don't attempt to schedule around any instruction that modifies 220 // a stack-oriented pointer, as it's unlikely to be profitable. This 221 // saves compile time, because it doesn't require every single 222 // stack slot reference to depend on the instruction that does the 223 // modification. 224 const TargetLowering &TLI = *MF.getTarget().getTargetLowering(); 225 if (MI->modifiesRegister(TLI.getStackPointerRegisterToSaveRestore())) 226 return true; 227 228 return false; 229} 230 231bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { 232 AA = &getAnalysis<AliasAnalysis>(); 233 234 // Check for explicit enable/disable of post-ra scheduling. 235 if (EnablePostRAScheduler.getPosition() > 0) { 236 if (!EnablePostRAScheduler) 237 return false; 238 } else { 239 // Check that post-RA scheduling is enabled for this target. 240 const TargetSubtarget &ST = Fn.getTarget().getSubtarget<TargetSubtarget>(); 241 if (!ST.enablePostRAScheduler()) 242 return false; 243 } 244 245 DEBUG(errs() << "PostRAScheduler\n"); 246 247 const MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>(); 248 const MachineDominatorTree &MDT = getAnalysis<MachineDominatorTree>(); 249 const InstrItineraryData &InstrItins = Fn.getTarget().getInstrItineraryData(); 250 ScheduleHazardRecognizer *HR = EnablePostRAHazardAvoidance ? 251 (ScheduleHazardRecognizer *)new ExactHazardRecognizer(InstrItins) : 252 (ScheduleHazardRecognizer *)new SimpleHazardRecognizer(); 253 254 SchedulePostRATDList Scheduler(Fn, MLI, MDT, HR, AA); 255 256 // Loop over all of the basic blocks 257 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 258 MBB != MBBe; ++MBB) { 259#ifndef NDEBUG 260 // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod 261 if (DebugDiv > 0) { 262 static int bbcnt = 0; 263 if (bbcnt++ % DebugDiv != DebugMod) 264 continue; 265 errs() << "*** DEBUG scheduling " << Fn.getFunction()->getNameStr() << 266 ":MBB ID#" << MBB->getNumber() << " ***\n"; 267 } 268#endif 269 270 // Initialize register live-range state for scheduling in this block. 271 Scheduler.StartBlock(MBB); 272 273 // Schedule each sequence of instructions not interrupted by a label 274 // or anything else that effectively needs to shut down scheduling. 275 MachineBasicBlock::iterator Current = MBB->end(); 276 unsigned Count = MBB->size(), CurrentCount = Count; 277 for (MachineBasicBlock::iterator I = Current; I != MBB->begin(); ) { 278 MachineInstr *MI = prior(I); 279 if (isSchedulingBoundary(MI, Fn)) { 280 Scheduler.Run(MBB, I, Current, CurrentCount); 281 Scheduler.EmitSchedule(0); 282 Current = MI; 283 CurrentCount = Count - 1; 284 Scheduler.Observe(MI, CurrentCount); 285 } 286 I = MI; 287 --Count; 288 } 289 assert(Count == 0 && "Instruction count mismatch!"); 290 assert((MBB->begin() == Current || CurrentCount != 0) && 291 "Instruction count mismatch!"); 292 Scheduler.Run(MBB, MBB->begin(), Current, CurrentCount); 293 Scheduler.EmitSchedule(0); 294 295 // Clean up register live-range state. 296 Scheduler.FinishBlock(); 297 298 // Update register kills 299 Scheduler.FixupKills(MBB); 300 } 301 302 return true; 303} 304 305/// StartBlock - Initialize register live-range state for scheduling in 306/// this block. 307/// 308void SchedulePostRATDList::StartBlock(MachineBasicBlock *BB) { 309 // Call the superclass. 310 ScheduleDAGInstrs::StartBlock(BB); 311 312 // Reset the hazard recognizer. 313 HazardRec->Reset(); 314 315 // Clear out the register class data. 316 std::fill(Classes, array_endof(Classes), 317 static_cast<const TargetRegisterClass *>(0)); 318 319 // Initialize the indices to indicate that no registers are live. 320 std::fill(KillIndices, array_endof(KillIndices), ~0u); 321 std::fill(DefIndices, array_endof(DefIndices), BB->size()); 322 323 // Clear "do not change" set. 324 KeepRegs.clear(); 325 326 bool IsReturnBlock = (!BB->empty() && BB->back().getDesc().isReturn()); 327 328 // Determine the live-out physregs for this block. 329 if (IsReturnBlock) { 330 // In a return block, examine the function live-out regs. 331 for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(), 332 E = MRI.liveout_end(); I != E; ++I) { 333 unsigned Reg = *I; 334 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 335 KillIndices[Reg] = BB->size(); 336 DefIndices[Reg] = ~0u; 337 // Repeat, for all aliases. 338 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 339 unsigned AliasReg = *Alias; 340 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 341 KillIndices[AliasReg] = BB->size(); 342 DefIndices[AliasReg] = ~0u; 343 } 344 } 345 } else { 346 // In a non-return block, examine the live-in regs of all successors. 347 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 348 SE = BB->succ_end(); SI != SE; ++SI) 349 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), 350 E = (*SI)->livein_end(); I != E; ++I) { 351 unsigned Reg = *I; 352 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 353 KillIndices[Reg] = BB->size(); 354 DefIndices[Reg] = ~0u; 355 // Repeat, for all aliases. 356 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 357 unsigned AliasReg = *Alias; 358 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 359 KillIndices[AliasReg] = BB->size(); 360 DefIndices[AliasReg] = ~0u; 361 } 362 } 363 } 364 365 // Mark live-out callee-saved registers. In a return block this is 366 // all callee-saved registers. In non-return this is any 367 // callee-saved register that is not saved in the prolog. 368 const MachineFrameInfo *MFI = MF.getFrameInfo(); 369 BitVector Pristine = MFI->getPristineRegs(BB); 370 for (const unsigned *I = TRI->getCalleeSavedRegs(); *I; ++I) { 371 unsigned Reg = *I; 372 if (!IsReturnBlock && !Pristine.test(Reg)) continue; 373 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 374 KillIndices[Reg] = BB->size(); 375 DefIndices[Reg] = ~0u; 376 // Repeat, for all aliases. 377 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 378 unsigned AliasReg = *Alias; 379 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 380 KillIndices[AliasReg] = BB->size(); 381 DefIndices[AliasReg] = ~0u; 382 } 383 } 384} 385 386/// Schedule - Schedule the instruction range using list scheduling. 387/// 388void SchedulePostRATDList::Schedule() { 389 DEBUG(errs() << "********** List Scheduling **********\n"); 390 391 // Build the scheduling graph. 392 BuildSchedGraph(AA); 393 394 if (EnableAntiDepBreaking) { 395 if (BreakAntiDependencies()) { 396 // We made changes. Update the dependency graph. 397 // Theoretically we could update the graph in place: 398 // When a live range is changed to use a different register, remove 399 // the def's anti-dependence *and* output-dependence edges due to 400 // that register, and add new anti-dependence and output-dependence 401 // edges based on the next live range of the register. 402 SUnits.clear(); 403 EntrySU = SUnit(); 404 ExitSU = SUnit(); 405 BuildSchedGraph(AA); 406 } 407 } 408 409 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 410 SUnits[su].dumpAll(this)); 411 412 AvailableQueue.initNodes(SUnits); 413 414 ListScheduleTopDown(); 415 416 AvailableQueue.releaseState(); 417} 418 419/// Observe - Update liveness information to account for the current 420/// instruction, which will not be scheduled. 421/// 422void SchedulePostRATDList::Observe(MachineInstr *MI, unsigned Count) { 423 assert(Count < InsertPosIndex && "Instruction index out of expected range!"); 424 425 // Any register which was defined within the previous scheduling region 426 // may have been rescheduled and its lifetime may overlap with registers 427 // in ways not reflected in our current liveness state. For each such 428 // register, adjust the liveness state to be conservatively correct. 429 for (unsigned Reg = 0; Reg != TargetRegisterInfo::FirstVirtualRegister; ++Reg) 430 if (DefIndices[Reg] < InsertPosIndex && DefIndices[Reg] >= Count) { 431 assert(KillIndices[Reg] == ~0u && "Clobbered register is live!"); 432 // Mark this register to be non-renamable. 433 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 434 // Move the def index to the end of the previous region, to reflect 435 // that the def could theoretically have been scheduled at the end. 436 DefIndices[Reg] = InsertPosIndex; 437 } 438 439 PrescanInstruction(MI); 440 ScanInstruction(MI, Count); 441} 442 443/// FinishBlock - Clean up register live-range state. 444/// 445void SchedulePostRATDList::FinishBlock() { 446 RegRefs.clear(); 447 448 // Call the superclass. 449 ScheduleDAGInstrs::FinishBlock(); 450} 451 452/// CriticalPathStep - Return the next SUnit after SU on the bottom-up 453/// critical path. 454static SDep *CriticalPathStep(SUnit *SU) { 455 SDep *Next = 0; 456 unsigned NextDepth = 0; 457 // Find the predecessor edge with the greatest depth. 458 for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); 459 P != PE; ++P) { 460 SUnit *PredSU = P->getSUnit(); 461 unsigned PredLatency = P->getLatency(); 462 unsigned PredTotalLatency = PredSU->getDepth() + PredLatency; 463 // In the case of a latency tie, prefer an anti-dependency edge over 464 // other types of edges. 465 if (NextDepth < PredTotalLatency || 466 (NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) { 467 NextDepth = PredTotalLatency; 468 Next = &*P; 469 } 470 } 471 return Next; 472} 473 474void SchedulePostRATDList::PrescanInstruction(MachineInstr *MI) { 475 // Scan the register operands for this instruction and update 476 // Classes and RegRefs. 477 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 478 MachineOperand &MO = MI->getOperand(i); 479 if (!MO.isReg()) continue; 480 unsigned Reg = MO.getReg(); 481 if (Reg == 0) continue; 482 const TargetRegisterClass *NewRC = 0; 483 484 if (i < MI->getDesc().getNumOperands()) 485 NewRC = MI->getDesc().OpInfo[i].getRegClass(TRI); 486 487 // For now, only allow the register to be changed if its register 488 // class is consistent across all uses. 489 if (!Classes[Reg] && NewRC) 490 Classes[Reg] = NewRC; 491 else if (!NewRC || Classes[Reg] != NewRC) 492 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 493 494 // Now check for aliases. 495 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 496 // If an alias of the reg is used during the live range, give up. 497 // Note that this allows us to skip checking if AntiDepReg 498 // overlaps with any of the aliases, among other things. 499 unsigned AliasReg = *Alias; 500 if (Classes[AliasReg]) { 501 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 502 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 503 } 504 } 505 506 // If we're still willing to consider this register, note the reference. 507 if (Classes[Reg] != reinterpret_cast<TargetRegisterClass *>(-1)) 508 RegRefs.insert(std::make_pair(Reg, &MO)); 509 510 // It's not safe to change register allocation for source operands of 511 // that have special allocation requirements. 512 if (MO.isUse() && MI->getDesc().hasExtraSrcRegAllocReq()) { 513 if (KeepRegs.insert(Reg)) { 514 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 515 *Subreg; ++Subreg) 516 KeepRegs.insert(*Subreg); 517 } 518 } 519 } 520} 521 522void SchedulePostRATDList::ScanInstruction(MachineInstr *MI, 523 unsigned Count) { 524 // Update liveness. 525 // Proceding upwards, registers that are defed but not used in this 526 // instruction are now dead. 527 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 528 MachineOperand &MO = MI->getOperand(i); 529 if (!MO.isReg()) continue; 530 unsigned Reg = MO.getReg(); 531 if (Reg == 0) continue; 532 if (!MO.isDef()) continue; 533 // Ignore two-addr defs. 534 if (MI->isRegTiedToUseOperand(i)) continue; 535 536 DefIndices[Reg] = Count; 537 KillIndices[Reg] = ~0u; 538 assert(((KillIndices[Reg] == ~0u) != 539 (DefIndices[Reg] == ~0u)) && 540 "Kill and Def maps aren't consistent for Reg!"); 541 KeepRegs.erase(Reg); 542 Classes[Reg] = 0; 543 RegRefs.erase(Reg); 544 // Repeat, for all subregs. 545 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 546 *Subreg; ++Subreg) { 547 unsigned SubregReg = *Subreg; 548 DefIndices[SubregReg] = Count; 549 KillIndices[SubregReg] = ~0u; 550 KeepRegs.erase(SubregReg); 551 Classes[SubregReg] = 0; 552 RegRefs.erase(SubregReg); 553 } 554 // Conservatively mark super-registers as unusable. 555 for (const unsigned *Super = TRI->getSuperRegisters(Reg); 556 *Super; ++Super) { 557 unsigned SuperReg = *Super; 558 Classes[SuperReg] = reinterpret_cast<TargetRegisterClass *>(-1); 559 } 560 } 561 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 562 MachineOperand &MO = MI->getOperand(i); 563 if (!MO.isReg()) continue; 564 unsigned Reg = MO.getReg(); 565 if (Reg == 0) continue; 566 if (!MO.isUse()) continue; 567 568 const TargetRegisterClass *NewRC = 0; 569 if (i < MI->getDesc().getNumOperands()) 570 NewRC = MI->getDesc().OpInfo[i].getRegClass(TRI); 571 572 // For now, only allow the register to be changed if its register 573 // class is consistent across all uses. 574 if (!Classes[Reg] && NewRC) 575 Classes[Reg] = NewRC; 576 else if (!NewRC || Classes[Reg] != NewRC) 577 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 578 579 RegRefs.insert(std::make_pair(Reg, &MO)); 580 581 // It wasn't previously live but now it is, this is a kill. 582 if (KillIndices[Reg] == ~0u) { 583 KillIndices[Reg] = Count; 584 DefIndices[Reg] = ~0u; 585 assert(((KillIndices[Reg] == ~0u) != 586 (DefIndices[Reg] == ~0u)) && 587 "Kill and Def maps aren't consistent for Reg!"); 588 } 589 // Repeat, for all aliases. 590 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 591 unsigned AliasReg = *Alias; 592 if (KillIndices[AliasReg] == ~0u) { 593 KillIndices[AliasReg] = Count; 594 DefIndices[AliasReg] = ~0u; 595 } 596 } 597 } 598} 599 600unsigned 601SchedulePostRATDList::findSuitableFreeRegister(unsigned AntiDepReg, 602 unsigned LastNewReg, 603 const TargetRegisterClass *RC) { 604 for (TargetRegisterClass::iterator R = RC->allocation_order_begin(MF), 605 RE = RC->allocation_order_end(MF); R != RE; ++R) { 606 unsigned NewReg = *R; 607 // Don't replace a register with itself. 608 if (NewReg == AntiDepReg) continue; 609 // Don't replace a register with one that was recently used to repair 610 // an anti-dependence with this AntiDepReg, because that would 611 // re-introduce that anti-dependence. 612 if (NewReg == LastNewReg) continue; 613 // If NewReg is dead and NewReg's most recent def is not before 614 // AntiDepReg's kill, it's safe to replace AntiDepReg with NewReg. 615 assert(((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u)) && 616 "Kill and Def maps aren't consistent for AntiDepReg!"); 617 assert(((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u)) && 618 "Kill and Def maps aren't consistent for NewReg!"); 619 if (KillIndices[NewReg] != ~0u || 620 Classes[NewReg] == reinterpret_cast<TargetRegisterClass *>(-1) || 621 KillIndices[AntiDepReg] > DefIndices[NewReg]) 622 continue; 623 return NewReg; 624 } 625 626 // No registers are free and available! 627 return 0; 628} 629 630/// BreakAntiDependencies - Identifiy anti-dependencies along the critical path 631/// of the ScheduleDAG and break them by renaming registers. 632/// 633bool SchedulePostRATDList::BreakAntiDependencies() { 634 // The code below assumes that there is at least one instruction, 635 // so just duck out immediately if the block is empty. 636 if (SUnits.empty()) return false; 637 638 // Find the node at the bottom of the critical path. 639 SUnit *Max = 0; 640 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 641 SUnit *SU = &SUnits[i]; 642 if (!Max || SU->getDepth() + SU->Latency > Max->getDepth() + Max->Latency) 643 Max = SU; 644 } 645 646#ifndef NDEBUG 647 { 648 DEBUG(errs() << "Critical path has total latency " 649 << (Max->getDepth() + Max->Latency) << "\n"); 650 DEBUG(errs() << "Available regs:"); 651 for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) { 652 if (KillIndices[Reg] == ~0u) 653 DEBUG(errs() << " " << TRI->getName(Reg)); 654 } 655 DEBUG(errs() << '\n'); 656 } 657#endif 658 659 // Track progress along the critical path through the SUnit graph as we walk 660 // the instructions. 661 SUnit *CriticalPathSU = Max; 662 MachineInstr *CriticalPathMI = CriticalPathSU->getInstr(); 663 664 // Consider this pattern: 665 // A = ... 666 // ... = A 667 // A = ... 668 // ... = A 669 // A = ... 670 // ... = A 671 // A = ... 672 // ... = A 673 // There are three anti-dependencies here, and without special care, 674 // we'd break all of them using the same register: 675 // A = ... 676 // ... = A 677 // B = ... 678 // ... = B 679 // B = ... 680 // ... = B 681 // B = ... 682 // ... = B 683 // because at each anti-dependence, B is the first register that 684 // isn't A which is free. This re-introduces anti-dependencies 685 // at all but one of the original anti-dependencies that we were 686 // trying to break. To avoid this, keep track of the most recent 687 // register that each register was replaced with, avoid 688 // using it to repair an anti-dependence on the same register. 689 // This lets us produce this: 690 // A = ... 691 // ... = A 692 // B = ... 693 // ... = B 694 // C = ... 695 // ... = C 696 // B = ... 697 // ... = B 698 // This still has an anti-dependence on B, but at least it isn't on the 699 // original critical path. 700 // 701 // TODO: If we tracked more than one register here, we could potentially 702 // fix that remaining critical edge too. This is a little more involved, 703 // because unlike the most recent register, less recent registers should 704 // still be considered, though only if no other registers are available. 705 unsigned LastNewReg[TargetRegisterInfo::FirstVirtualRegister] = {}; 706 707 // Attempt to break anti-dependence edges on the critical path. Walk the 708 // instructions from the bottom up, tracking information about liveness 709 // as we go to help determine which registers are available. 710 bool Changed = false; 711 unsigned Count = InsertPosIndex - 1; 712 for (MachineBasicBlock::iterator I = InsertPos, E = Begin; 713 I != E; --Count) { 714 MachineInstr *MI = --I; 715 716 // Check if this instruction has a dependence on the critical path that 717 // is an anti-dependence that we may be able to break. If it is, set 718 // AntiDepReg to the non-zero register associated with the anti-dependence. 719 // 720 // We limit our attention to the critical path as a heuristic to avoid 721 // breaking anti-dependence edges that aren't going to significantly 722 // impact the overall schedule. There are a limited number of registers 723 // and we want to save them for the important edges. 724 // 725 // TODO: Instructions with multiple defs could have multiple 726 // anti-dependencies. The current code here only knows how to break one 727 // edge per instruction. Note that we'd have to be able to break all of 728 // the anti-dependencies in an instruction in order to be effective. 729 unsigned AntiDepReg = 0; 730 if (MI == CriticalPathMI) { 731 if (SDep *Edge = CriticalPathStep(CriticalPathSU)) { 732 SUnit *NextSU = Edge->getSUnit(); 733 734 // Only consider anti-dependence edges. 735 if (Edge->getKind() == SDep::Anti) { 736 AntiDepReg = Edge->getReg(); 737 assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); 738 if (!AllocatableSet.test(AntiDepReg)) 739 // Don't break anti-dependencies on non-allocatable registers. 740 AntiDepReg = 0; 741 else if (KeepRegs.count(AntiDepReg)) 742 // Don't break anti-dependencies if an use down below requires 743 // this exact register. 744 AntiDepReg = 0; 745 else { 746 // If the SUnit has other dependencies on the SUnit that it 747 // anti-depends on, don't bother breaking the anti-dependency 748 // since those edges would prevent such units from being 749 // scheduled past each other regardless. 750 // 751 // Also, if there are dependencies on other SUnits with the 752 // same register as the anti-dependency, don't attempt to 753 // break it. 754 for (SUnit::pred_iterator P = CriticalPathSU->Preds.begin(), 755 PE = CriticalPathSU->Preds.end(); P != PE; ++P) 756 if (P->getSUnit() == NextSU ? 757 (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) : 758 (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) { 759 AntiDepReg = 0; 760 break; 761 } 762 } 763 } 764 CriticalPathSU = NextSU; 765 CriticalPathMI = CriticalPathSU->getInstr(); 766 } else { 767 // We've reached the end of the critical path. 768 CriticalPathSU = 0; 769 CriticalPathMI = 0; 770 } 771 } 772 773 PrescanInstruction(MI); 774 775 if (MI->getDesc().hasExtraDefRegAllocReq()) 776 // If this instruction's defs have special allocation requirement, don't 777 // break this anti-dependency. 778 AntiDepReg = 0; 779 else if (AntiDepReg) { 780 // If this instruction has a use of AntiDepReg, breaking it 781 // is invalid. 782 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 783 MachineOperand &MO = MI->getOperand(i); 784 if (!MO.isReg()) continue; 785 unsigned Reg = MO.getReg(); 786 if (Reg == 0) continue; 787 if (MO.isUse() && AntiDepReg == Reg) { 788 AntiDepReg = 0; 789 break; 790 } 791 } 792 } 793 794 // Determine AntiDepReg's register class, if it is live and is 795 // consistently used within a single class. 796 const TargetRegisterClass *RC = AntiDepReg != 0 ? Classes[AntiDepReg] : 0; 797 assert((AntiDepReg == 0 || RC != NULL) && 798 "Register should be live if it's causing an anti-dependence!"); 799 if (RC == reinterpret_cast<TargetRegisterClass *>(-1)) 800 AntiDepReg = 0; 801 802 // Look for a suitable register to use to break the anti-depenence. 803 // 804 // TODO: Instead of picking the first free register, consider which might 805 // be the best. 806 if (AntiDepReg != 0) { 807 if (unsigned NewReg = findSuitableFreeRegister(AntiDepReg, 808 LastNewReg[AntiDepReg], 809 RC)) { 810 DEBUG(errs() << "Breaking anti-dependence edge on " 811 << TRI->getName(AntiDepReg) 812 << " with " << RegRefs.count(AntiDepReg) << " references" 813 << " using " << TRI->getName(NewReg) << "!\n"); 814 815 // Update the references to the old register to refer to the new 816 // register. 817 std::pair<std::multimap<unsigned, MachineOperand *>::iterator, 818 std::multimap<unsigned, MachineOperand *>::iterator> 819 Range = RegRefs.equal_range(AntiDepReg); 820 for (std::multimap<unsigned, MachineOperand *>::iterator 821 Q = Range.first, QE = Range.second; Q != QE; ++Q) 822 Q->second->setReg(NewReg); 823 824 // We just went back in time and modified history; the 825 // liveness information for the anti-depenence reg is now 826 // inconsistent. Set the state as if it were dead. 827 Classes[NewReg] = Classes[AntiDepReg]; 828 DefIndices[NewReg] = DefIndices[AntiDepReg]; 829 KillIndices[NewReg] = KillIndices[AntiDepReg]; 830 assert(((KillIndices[NewReg] == ~0u) != 831 (DefIndices[NewReg] == ~0u)) && 832 "Kill and Def maps aren't consistent for NewReg!"); 833 834 Classes[AntiDepReg] = 0; 835 DefIndices[AntiDepReg] = KillIndices[AntiDepReg]; 836 KillIndices[AntiDepReg] = ~0u; 837 assert(((KillIndices[AntiDepReg] == ~0u) != 838 (DefIndices[AntiDepReg] == ~0u)) && 839 "Kill and Def maps aren't consistent for AntiDepReg!"); 840 841 RegRefs.erase(AntiDepReg); 842 Changed = true; 843 LastNewReg[AntiDepReg] = NewReg; 844 } 845 } 846 847 ScanInstruction(MI, Count); 848 } 849 850 return Changed; 851} 852 853/// StartBlockForKills - Initialize register live-range state for updating kills 854/// 855void SchedulePostRATDList::StartBlockForKills(MachineBasicBlock *BB) { 856 // Initialize the indices to indicate that no registers are live. 857 std::fill(KillIndices, array_endof(KillIndices), ~0u); 858 859 // Determine the live-out physregs for this block. 860 if (!BB->empty() && BB->back().getDesc().isReturn()) { 861 // In a return block, examine the function live-out regs. 862 for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(), 863 E = MRI.liveout_end(); I != E; ++I) { 864 unsigned Reg = *I; 865 KillIndices[Reg] = BB->size(); 866 // Repeat, for all subregs. 867 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 868 *Subreg; ++Subreg) { 869 KillIndices[*Subreg] = BB->size(); 870 } 871 } 872 } 873 else { 874 // In a non-return block, examine the live-in regs of all successors. 875 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 876 SE = BB->succ_end(); SI != SE; ++SI) { 877 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), 878 E = (*SI)->livein_end(); I != E; ++I) { 879 unsigned Reg = *I; 880 KillIndices[Reg] = BB->size(); 881 // Repeat, for all subregs. 882 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 883 *Subreg; ++Subreg) { 884 KillIndices[*Subreg] = BB->size(); 885 } 886 } 887 } 888 } 889} 890 891bool SchedulePostRATDList::ToggleKillFlag(MachineInstr *MI, 892 MachineOperand &MO) { 893 // Setting kill flag... 894 if (!MO.isKill()) { 895 MO.setIsKill(true); 896 return false; 897 } 898 899 // If MO itself is live, clear the kill flag... 900 if (KillIndices[MO.getReg()] != ~0u) { 901 MO.setIsKill(false); 902 return false; 903 } 904 905 // If any subreg of MO is live, then create an imp-def for that 906 // subreg and keep MO marked as killed. 907 MO.setIsKill(false); 908 bool AllDead = true; 909 const unsigned SuperReg = MO.getReg(); 910 for (const unsigned *Subreg = TRI->getSubRegisters(SuperReg); 911 *Subreg; ++Subreg) { 912 if (KillIndices[*Subreg] != ~0u) { 913 MI->addOperand(MachineOperand::CreateReg(*Subreg, 914 true /*IsDef*/, 915 true /*IsImp*/, 916 false /*IsKill*/, 917 false /*IsDead*/)); 918 AllDead = false; 919 } 920 } 921 922 if(AllDead) 923 MO.setIsKill(true); 924 return false; 925} 926 927/// FixupKills - Fix the register kill flags, they may have been made 928/// incorrect by instruction reordering. 929/// 930void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { 931 DEBUG(errs() << "Fixup kills for BB ID#" << MBB->getNumber() << '\n'); 932 933 std::set<unsigned> killedRegs; 934 BitVector ReservedRegs = TRI->getReservedRegs(MF); 935 936 StartBlockForKills(MBB); 937 938 // Examine block from end to start... 939 unsigned Count = MBB->size(); 940 for (MachineBasicBlock::iterator I = MBB->end(), E = MBB->begin(); 941 I != E; --Count) { 942 MachineInstr *MI = --I; 943 944 // Update liveness. Registers that are defed but not used in this 945 // instruction are now dead. Mark register and all subregs as they 946 // are completely defined. 947 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 948 MachineOperand &MO = MI->getOperand(i); 949 if (!MO.isReg()) continue; 950 unsigned Reg = MO.getReg(); 951 if (Reg == 0) continue; 952 if (!MO.isDef()) continue; 953 // Ignore two-addr defs. 954 if (MI->isRegTiedToUseOperand(i)) continue; 955 956 KillIndices[Reg] = ~0u; 957 958 // Repeat for all subregs. 959 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 960 *Subreg; ++Subreg) { 961 KillIndices[*Subreg] = ~0u; 962 } 963 } 964 965 // Examine all used registers and set/clear kill flag. When a 966 // register is used multiple times we only set the kill flag on 967 // the first use. 968 killedRegs.clear(); 969 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 970 MachineOperand &MO = MI->getOperand(i); 971 if (!MO.isReg() || !MO.isUse()) continue; 972 unsigned Reg = MO.getReg(); 973 if ((Reg == 0) || ReservedRegs.test(Reg)) continue; 974 975 bool kill = false; 976 if (killedRegs.find(Reg) == killedRegs.end()) { 977 kill = true; 978 // A register is not killed if any subregs are live... 979 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 980 *Subreg; ++Subreg) { 981 if (KillIndices[*Subreg] != ~0u) { 982 kill = false; 983 break; 984 } 985 } 986 987 // If subreg is not live, then register is killed if it became 988 // live in this instruction 989 if (kill) 990 kill = (KillIndices[Reg] == ~0u); 991 } 992 993 if (MO.isKill() != kill) { 994 bool removed = ToggleKillFlag(MI, MO); 995 if (removed) { 996 DEBUG(errs() << "Fixed <removed> in "); 997 } else { 998 DEBUG(errs() << "Fixed " << MO << " in "); 999 } 1000 DEBUG(MI->dump()); 1001 } 1002 1003 killedRegs.insert(Reg); 1004 } 1005 1006 // Mark any used register (that is not using undef) and subregs as 1007 // now live... 1008 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1009 MachineOperand &MO = MI->getOperand(i); 1010 if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue; 1011 unsigned Reg = MO.getReg(); 1012 if ((Reg == 0) || ReservedRegs.test(Reg)) continue; 1013 1014 KillIndices[Reg] = Count; 1015 1016 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 1017 *Subreg; ++Subreg) { 1018 KillIndices[*Subreg] = Count; 1019 } 1020 } 1021 } 1022} 1023 1024//===----------------------------------------------------------------------===// 1025// Top-Down Scheduling 1026//===----------------------------------------------------------------------===// 1027 1028/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 1029/// the PendingQueue if the count reaches zero. Also update its cycle bound. 1030void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) { 1031 SUnit *SuccSU = SuccEdge->getSUnit(); 1032 1033#ifndef NDEBUG 1034 if (SuccSU->NumPredsLeft == 0) { 1035 errs() << "*** Scheduling failed! ***\n"; 1036 SuccSU->dump(this); 1037 errs() << " has been released too many times!\n"; 1038 llvm_unreachable(0); 1039 } 1040#endif 1041 --SuccSU->NumPredsLeft; 1042 1043 // Compute how many cycles it will be before this actually becomes 1044 // available. This is the max of the start time of all predecessors plus 1045 // their latencies. 1046 SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency()); 1047 1048 // If all the node's predecessors are scheduled, this node is ready 1049 // to be scheduled. Ignore the special ExitSU node. 1050 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 1051 PendingQueue.push_back(SuccSU); 1052} 1053 1054/// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors. 1055void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) { 1056 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1057 I != E; ++I) 1058 ReleaseSucc(SU, &*I); 1059} 1060 1061/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 1062/// count of its successors. If a successor pending count is zero, add it to 1063/// the Available queue. 1064void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 1065 DEBUG(errs() << "*** Scheduling [" << CurCycle << "]: "); 1066 DEBUG(SU->dump(this)); 1067 1068 Sequence.push_back(SU); 1069 assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); 1070 SU->setDepthToAtLeast(CurCycle); 1071 1072 ReleaseSuccessors(SU); 1073 SU->isScheduled = true; 1074 AvailableQueue.ScheduledNode(SU); 1075} 1076 1077/// ListScheduleTopDown - The main loop of list scheduling for top-down 1078/// schedulers. 1079void SchedulePostRATDList::ListScheduleTopDown() { 1080 unsigned CurCycle = 0; 1081 1082 // Release any successors of the special Entry node. 1083 ReleaseSuccessors(&EntrySU); 1084 1085 // All leaves to Available queue. 1086 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 1087 // It is available if it has no predecessors. 1088 if (SUnits[i].Preds.empty()) { 1089 AvailableQueue.push(&SUnits[i]); 1090 SUnits[i].isAvailable = true; 1091 } 1092 } 1093 1094 // In any cycle where we can't schedule any instructions, we must 1095 // stall or emit a noop, depending on the target. 1096 bool CycleHasInsts = false; 1097 1098 // While Available queue is not empty, grab the node with the highest 1099 // priority. If it is not ready put it back. Schedule the node. 1100 std::vector<SUnit*> NotReady; 1101 Sequence.reserve(SUnits.size()); 1102 while (!AvailableQueue.empty() || !PendingQueue.empty()) { 1103 // Check to see if any of the pending instructions are ready to issue. If 1104 // so, add them to the available queue. 1105 unsigned MinDepth = ~0u; 1106 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { 1107 if (PendingQueue[i]->getDepth() <= CurCycle) { 1108 AvailableQueue.push(PendingQueue[i]); 1109 PendingQueue[i]->isAvailable = true; 1110 PendingQueue[i] = PendingQueue.back(); 1111 PendingQueue.pop_back(); 1112 --i; --e; 1113 } else if (PendingQueue[i]->getDepth() < MinDepth) 1114 MinDepth = PendingQueue[i]->getDepth(); 1115 } 1116 1117 DEBUG(errs() << "\n*** Examining Available\n"; 1118 LatencyPriorityQueue q = AvailableQueue; 1119 while (!q.empty()) { 1120 SUnit *su = q.pop(); 1121 errs() << "Height " << su->getHeight() << ": "; 1122 su->dump(this); 1123 }); 1124 1125 SUnit *FoundSUnit = 0; 1126 1127 bool HasNoopHazards = false; 1128 while (!AvailableQueue.empty()) { 1129 SUnit *CurSUnit = AvailableQueue.pop(); 1130 1131 ScheduleHazardRecognizer::HazardType HT = 1132 HazardRec->getHazardType(CurSUnit); 1133 if (HT == ScheduleHazardRecognizer::NoHazard) { 1134 FoundSUnit = CurSUnit; 1135 break; 1136 } 1137 1138 // Remember if this is a noop hazard. 1139 HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard; 1140 1141 NotReady.push_back(CurSUnit); 1142 } 1143 1144 // Add the nodes that aren't ready back onto the available list. 1145 if (!NotReady.empty()) { 1146 AvailableQueue.push_all(NotReady); 1147 NotReady.clear(); 1148 } 1149 1150 // If we found a node to schedule, do it now. 1151 if (FoundSUnit) { 1152 ScheduleNodeTopDown(FoundSUnit, CurCycle); 1153 HazardRec->EmitInstruction(FoundSUnit); 1154 CycleHasInsts = true; 1155 1156 // If we are using the target-specific hazards, then don't 1157 // advance the cycle time just because we schedule a node. If 1158 // the target allows it we can schedule multiple nodes in the 1159 // same cycle. 1160 if (!EnablePostRAHazardAvoidance) { 1161 if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops! 1162 ++CurCycle; 1163 } 1164 } else { 1165 if (CycleHasInsts) { 1166 DEBUG(errs() << "*** Finished cycle " << CurCycle << '\n'); 1167 HazardRec->AdvanceCycle(); 1168 } else if (!HasNoopHazards) { 1169 // Otherwise, we have a pipeline stall, but no other problem, 1170 // just advance the current cycle and try again. 1171 DEBUG(errs() << "*** Stall in cycle " << CurCycle << '\n'); 1172 HazardRec->AdvanceCycle(); 1173 ++NumStalls; 1174 } else { 1175 // Otherwise, we have no instructions to issue and we have instructions 1176 // that will fault if we don't do this right. This is the case for 1177 // processors without pipeline interlocks and other cases. 1178 DEBUG(errs() << "*** Emitting noop in cycle " << CurCycle << '\n'); 1179 HazardRec->EmitNoop(); 1180 Sequence.push_back(0); // NULL here means noop 1181 ++NumNoops; 1182 } 1183 1184 ++CurCycle; 1185 CycleHasInsts = false; 1186 } 1187 } 1188 1189#ifndef NDEBUG 1190 VerifySchedule(/*isBottomUp=*/false); 1191#endif 1192} 1193 1194//===----------------------------------------------------------------------===// 1195// Public Constructor Functions 1196//===----------------------------------------------------------------------===// 1197 1198FunctionPass *llvm::createPostRAScheduler() { 1199 return new PostRAScheduler(); 1200} 1201