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