LLVM API Documentation
00001 //===----- SchedulePostRAList.cpp - list scheduler ------------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This implements a top-down list scheduler, using standard algorithms. 00011 // The basic approach uses a priority queue of available nodes to schedule. 00012 // One at a time, nodes are taken from the priority queue (thus in priority 00013 // order), checked for legality to schedule, and emitted if legal. 00014 // 00015 // Nodes may not be legal to schedule either due to structural hazards (e.g. 00016 // pipeline or resource constraints) or because an input to the instruction has 00017 // not completed execution. 00018 // 00019 //===----------------------------------------------------------------------===// 00020 00021 #define DEBUG_TYPE "post-RA-sched" 00022 #include "ExactHazardRecognizer.h" 00023 #include "SimpleHazardRecognizer.h" 00024 #include "ScheduleDAGInstrs.h" 00025 #include "llvm/CodeGen/Passes.h" 00026 #include "llvm/CodeGen/LatencyPriorityQueue.h" 00027 #include "llvm/CodeGen/SchedulerRegistry.h" 00028 #include "llvm/CodeGen/MachineDominators.h" 00029 #include "llvm/CodeGen/MachineFunctionPass.h" 00030 #include "llvm/CodeGen/MachineLoopInfo.h" 00031 #include "llvm/CodeGen/MachineRegisterInfo.h" 00032 #include "llvm/CodeGen/ScheduleHazardRecognizer.h" 00033 #include "llvm/Target/TargetLowering.h" 00034 #include "llvm/Target/TargetMachine.h" 00035 #include "llvm/Target/TargetInstrInfo.h" 00036 #include "llvm/Target/TargetRegisterInfo.h" 00037 #include "llvm/Support/Compiler.h" 00038 #include "llvm/Support/Debug.h" 00039 #include "llvm/Support/ErrorHandling.h" 00040 #include "llvm/Support/raw_ostream.h" 00041 #include "llvm/ADT/Statistic.h" 00042 #include <map> 00043 using namespace llvm; 00044 00045 STATISTIC(NumNoops, "Number of noops inserted"); 00046 STATISTIC(NumStalls, "Number of pipeline stalls"); 00047 00048 static cl::opt<bool> 00049 EnableAntiDepBreaking("break-anti-dependencies", 00050 cl::desc("Break post-RA scheduling anti-dependencies"), 00051 cl::init(true), cl::Hidden); 00052 00053 static cl::opt<bool> 00054 EnablePostRAHazardAvoidance("avoid-hazards", 00055 cl::desc("Enable exact hazard avoidance"), 00056 cl::init(false), cl::Hidden); 00057 00058 namespace { 00059 class VISIBILITY_HIDDEN PostRAScheduler : public MachineFunctionPass { 00060 public: 00061 static char ID; 00062 PostRAScheduler() : MachineFunctionPass(&ID) {} 00063 00064 void getAnalysisUsage(AnalysisUsage &AU) const { 00065 AU.setPreservesCFG(); 00066 AU.addRequired<MachineDominatorTree>(); 00067 AU.addPreserved<MachineDominatorTree>(); 00068 AU.addRequired<MachineLoopInfo>(); 00069 AU.addPreserved<MachineLoopInfo>(); 00070 MachineFunctionPass::getAnalysisUsage(AU); 00071 } 00072 00073 const char *getPassName() const { 00074 return "Post RA top-down list latency scheduler"; 00075 } 00076 00077 bool runOnMachineFunction(MachineFunction &Fn); 00078 }; 00079 char PostRAScheduler::ID = 0; 00080 00081 class VISIBILITY_HIDDEN SchedulePostRATDList : public ScheduleDAGInstrs { 00082 /// AvailableQueue - The priority queue to use for the available SUnits. 00083 /// 00084 LatencyPriorityQueue AvailableQueue; 00085 00086 /// PendingQueue - This contains all of the instructions whose operands have 00087 /// been issued, but their results are not ready yet (due to the latency of 00088 /// the operation). Once the operands becomes available, the instruction is 00089 /// added to the AvailableQueue. 00090 std::vector<SUnit*> PendingQueue; 00091 00092 /// Topo - A topological ordering for SUnits. 00093 ScheduleDAGTopologicalSort Topo; 00094 00095 /// AllocatableSet - The set of allocatable registers. 00096 /// We'll be ignoring anti-dependencies on non-allocatable registers, 00097 /// because they may not be safe to break. 00098 const BitVector AllocatableSet; 00099 00100 /// HazardRec - The hazard recognizer to use. 00101 ScheduleHazardRecognizer *HazardRec; 00102 00103 /// Classes - For live regs that are only used in one register class in a 00104 /// live range, the register class. If the register is not live, the 00105 /// corresponding value is null. If the register is live but used in 00106 /// multiple register classes, the corresponding value is -1 casted to a 00107 /// pointer. 00108 const TargetRegisterClass * 00109 Classes[TargetRegisterInfo::FirstVirtualRegister]; 00110 00111 /// RegRegs - Map registers to all their references within a live range. 00112 std::multimap<unsigned, MachineOperand *> RegRefs; 00113 00114 /// The index of the most recent kill (proceding bottom-up), or ~0u if 00115 /// the register is not live. 00116 unsigned KillIndices[TargetRegisterInfo::FirstVirtualRegister]; 00117 00118 /// The index of the most recent complete def (proceding bottom up), or ~0u 00119 /// if the register is live. 00120 unsigned DefIndices[TargetRegisterInfo::FirstVirtualRegister]; 00121 00122 public: 00123 SchedulePostRATDList(MachineFunction &MF, 00124 const MachineLoopInfo &MLI, 00125 const MachineDominatorTree &MDT, 00126 ScheduleHazardRecognizer *HR) 00127 : ScheduleDAGInstrs(MF, MLI, MDT), Topo(SUnits), 00128 AllocatableSet(TRI->getAllocatableSet(MF)), 00129 HazardRec(HR) {} 00130 00131 ~SchedulePostRATDList() { 00132 delete HazardRec; 00133 } 00134 00135 /// StartBlock - Initialize register live-range state for scheduling in 00136 /// this block. 00137 /// 00138 void StartBlock(MachineBasicBlock *BB); 00139 00140 /// Schedule - Schedule the instruction range using list scheduling. 00141 /// 00142 void Schedule(); 00143 00144 /// Observe - Update liveness information to account for the current 00145 /// instruction, which will not be scheduled. 00146 /// 00147 void Observe(MachineInstr *MI, unsigned Count); 00148 00149 /// FinishBlock - Clean up register live-range state. 00150 /// 00151 void FinishBlock(); 00152 00153 private: 00154 void PrescanInstruction(MachineInstr *MI); 00155 void ScanInstruction(MachineInstr *MI, unsigned Count); 00156 void ReleaseSucc(SUnit *SU, SDep *SuccEdge); 00157 void ReleaseSuccessors(SUnit *SU); 00158 void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 00159 void ListScheduleTopDown(); 00160 bool BreakAntiDependencies(); 00161 unsigned findSuitableFreeRegister(unsigned AntiDepReg, 00162 unsigned LastNewReg, 00163 const TargetRegisterClass *); 00164 }; 00165 } 00166 00167 /// isSchedulingBoundary - Test if the given instruction should be 00168 /// considered a scheduling boundary. This primarily includes labels 00169 /// and terminators. 00170 /// 00171 static bool isSchedulingBoundary(const MachineInstr *MI, 00172 const MachineFunction &MF) { 00173 // Terminators and labels can't be scheduled around. 00174 if (MI->getDesc().isTerminator() || MI->isLabel()) 00175 return true; 00176 00177 // Don't attempt to schedule around any instruction that modifies 00178 // a stack-oriented pointer, as it's unlikely to be profitable. This 00179 // saves compile time, because it doesn't require every single 00180 // stack slot reference to depend on the instruction that does the 00181 // modification. 00182 const TargetLowering &TLI = *MF.getTarget().getTargetLowering(); 00183 if (MI->modifiesRegister(TLI.getStackPointerRegisterToSaveRestore())) 00184 return true; 00185 00186 return false; 00187 } 00188 00189 bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { 00190 DEBUG(errs() << "PostRAScheduler\n"); 00191 00192 const MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>(); 00193 const MachineDominatorTree &MDT = getAnalysis<MachineDominatorTree>(); 00194 const InstrItineraryData &InstrItins = Fn.getTarget().getInstrItineraryData(); 00195 ScheduleHazardRecognizer *HR = EnablePostRAHazardAvoidance ? 00196 (ScheduleHazardRecognizer *)new ExactHazardRecognizer(InstrItins) : 00197 (ScheduleHazardRecognizer *)new SimpleHazardRecognizer(); 00198 00199 SchedulePostRATDList Scheduler(Fn, MLI, MDT, HR); 00200 00201 // Loop over all of the basic blocks 00202 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 00203 MBB != MBBe; ++MBB) { 00204 // Initialize register live-range state for scheduling in this block. 00205 Scheduler.StartBlock(MBB); 00206 00207 // Schedule each sequence of instructions not interrupted by a label 00208 // or anything else that effectively needs to shut down scheduling. 00209 MachineBasicBlock::iterator Current = MBB->end(); 00210 unsigned Count = MBB->size(), CurrentCount = Count; 00211 for (MachineBasicBlock::iterator I = Current; I != MBB->begin(); ) { 00212 MachineInstr *MI = prior(I); 00213 if (isSchedulingBoundary(MI, Fn)) { 00214 Scheduler.Run(MBB, I, Current, CurrentCount); 00215 Scheduler.EmitSchedule(); 00216 Current = MI; 00217 CurrentCount = Count - 1; 00218 Scheduler.Observe(MI, CurrentCount); 00219 } 00220 I = MI; 00221 --Count; 00222 } 00223 assert(Count == 0 && "Instruction count mismatch!"); 00224 assert((MBB->begin() == Current || CurrentCount != 0) && 00225 "Instruction count mismatch!"); 00226 Scheduler.Run(MBB, MBB->begin(), Current, CurrentCount); 00227 Scheduler.EmitSchedule(); 00228 00229 // Clean up register live-range state. 00230 Scheduler.FinishBlock(); 00231 } 00232 00233 return true; 00234 } 00235 00236 /// StartBlock - Initialize register live-range state for scheduling in 00237 /// this block. 00238 /// 00239 void SchedulePostRATDList::StartBlock(MachineBasicBlock *BB) { 00240 // Call the superclass. 00241 ScheduleDAGInstrs::StartBlock(BB); 00242 00243 // Reset the hazard recognizer. 00244 HazardRec->Reset(); 00245 00246 // Clear out the register class data. 00247 std::fill(Classes, array_endof(Classes), 00248 static_cast<const TargetRegisterClass *>(0)); 00249 00250 // Initialize the indices to indicate that no registers are live. 00251 std::fill(KillIndices, array_endof(KillIndices), ~0u); 00252 std::fill(DefIndices, array_endof(DefIndices), BB->size()); 00253 00254 // Determine the live-out physregs for this block. 00255 if (!BB->empty() && BB->back().getDesc().isReturn()) 00256 // In a return block, examine the function live-out regs. 00257 for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(), 00258 E = MRI.liveout_end(); I != E; ++I) { 00259 unsigned Reg = *I; 00260 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 00261 KillIndices[Reg] = BB->size(); 00262 DefIndices[Reg] = ~0u; 00263 // Repeat, for all aliases. 00264 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 00265 unsigned AliasReg = *Alias; 00266 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 00267 KillIndices[AliasReg] = BB->size(); 00268 DefIndices[AliasReg] = ~0u; 00269 } 00270 } 00271 else 00272 // In a non-return block, examine the live-in regs of all successors. 00273 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 00274 SE = BB->succ_end(); SI != SE; ++SI) 00275 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), 00276 E = (*SI)->livein_end(); I != E; ++I) { 00277 unsigned Reg = *I; 00278 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 00279 KillIndices[Reg] = BB->size(); 00280 DefIndices[Reg] = ~0u; 00281 // Repeat, for all aliases. 00282 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 00283 unsigned AliasReg = *Alias; 00284 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 00285 KillIndices[AliasReg] = BB->size(); 00286 DefIndices[AliasReg] = ~0u; 00287 } 00288 } 00289 00290 // Consider callee-saved registers as live-out, since we're running after 00291 // prologue/epilogue insertion so there's no way to add additional 00292 // saved registers. 00293 // 00294 // TODO: If the callee saves and restores these, then we can potentially 00295 // use them between the save and the restore. To do that, we could scan 00296 // the exit blocks to see which of these registers are defined. 00297 // Alternatively, callee-saved registers that aren't saved and restored 00298 // could be marked live-in in every block. 00299 for (const unsigned *I = TRI->getCalleeSavedRegs(); *I; ++I) { 00300 unsigned Reg = *I; 00301 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 00302 KillIndices[Reg] = BB->size(); 00303 DefIndices[Reg] = ~0u; 00304 // Repeat, for all aliases. 00305 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 00306 unsigned AliasReg = *Alias; 00307 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 00308 KillIndices[AliasReg] = BB->size(); 00309 DefIndices[AliasReg] = ~0u; 00310 } 00311 } 00312 } 00313 00314 /// Schedule - Schedule the instruction range using list scheduling. 00315 /// 00316 void SchedulePostRATDList::Schedule() { 00317 DEBUG(errs() << "********** List Scheduling **********\n"); 00318 00319 // Build the scheduling graph. 00320 BuildSchedGraph(); 00321 00322 if (EnableAntiDepBreaking) { 00323 if (BreakAntiDependencies()) { 00324 // We made changes. Update the dependency graph. 00325 // Theoretically we could update the graph in place: 00326 // When a live range is changed to use a different register, remove 00327 // the def's anti-dependence *and* output-dependence edges due to 00328 // that register, and add new anti-dependence and output-dependence 00329 // edges based on the next live range of the register. 00330 SUnits.clear(); 00331 EntrySU = SUnit(); 00332 ExitSU = SUnit(); 00333 BuildSchedGraph(); 00334 } 00335 } 00336 00337 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 00338 SUnits[su].dumpAll(this)); 00339 00340 AvailableQueue.initNodes(SUnits); 00341 00342 ListScheduleTopDown(); 00343 00344 AvailableQueue.releaseState(); 00345 } 00346 00347 /// Observe - Update liveness information to account for the current 00348 /// instruction, which will not be scheduled. 00349 /// 00350 void SchedulePostRATDList::Observe(MachineInstr *MI, unsigned Count) { 00351 assert(Count < InsertPosIndex && "Instruction index out of expected range!"); 00352 00353 // Any register which was defined within the previous scheduling region 00354 // may have been rescheduled and its lifetime may overlap with registers 00355 // in ways not reflected in our current liveness state. For each such 00356 // register, adjust the liveness state to be conservatively correct. 00357 for (unsigned Reg = 0; Reg != TargetRegisterInfo::FirstVirtualRegister; ++Reg) 00358 if (DefIndices[Reg] < InsertPosIndex && DefIndices[Reg] >= Count) { 00359 assert(KillIndices[Reg] == ~0u && "Clobbered register is live!"); 00360 // Mark this register to be non-renamable. 00361 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 00362 // Move the def index to the end of the previous region, to reflect 00363 // that the def could theoretically have been scheduled at the end. 00364 DefIndices[Reg] = InsertPosIndex; 00365 } 00366 00367 PrescanInstruction(MI); 00368 ScanInstruction(MI, Count); 00369 } 00370 00371 /// FinishBlock - Clean up register live-range state. 00372 /// 00373 void SchedulePostRATDList::FinishBlock() { 00374 RegRefs.clear(); 00375 00376 // Call the superclass. 00377 ScheduleDAGInstrs::FinishBlock(); 00378 } 00379 00380 /// CriticalPathStep - Return the next SUnit after SU on the bottom-up 00381 /// critical path. 00382 static SDep *CriticalPathStep(SUnit *SU) { 00383 SDep *Next = 0; 00384 unsigned NextDepth = 0; 00385 // Find the predecessor edge with the greatest depth. 00386 for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); 00387 P != PE; ++P) { 00388 SUnit *PredSU = P->getSUnit(); 00389 unsigned PredLatency = P->getLatency(); 00390 unsigned PredTotalLatency = PredSU->getDepth() + PredLatency; 00391 // In the case of a latency tie, prefer an anti-dependency edge over 00392 // other types of edges. 00393 if (NextDepth < PredTotalLatency || 00394 (NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) { 00395 NextDepth = PredTotalLatency; 00396 Next = &*P; 00397 } 00398 } 00399 return Next; 00400 } 00401 00402 void SchedulePostRATDList::PrescanInstruction(MachineInstr *MI) { 00403 // Scan the register operands for this instruction and update 00404 // Classes and RegRefs. 00405 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00406 MachineOperand &MO = MI->getOperand(i); 00407 if (!MO.isReg()) continue; 00408 unsigned Reg = MO.getReg(); 00409 if (Reg == 0) continue; 00410 const TargetRegisterClass *NewRC = 0; 00411 00412 if (i < MI->getDesc().getNumOperands()) 00413 NewRC = MI->getDesc().OpInfo[i].getRegClass(TRI); 00414 00415 // For now, only allow the register to be changed if its register 00416 // class is consistent across all uses. 00417 if (!Classes[Reg] && NewRC) 00418 Classes[Reg] = NewRC; 00419 else if (!NewRC || Classes[Reg] != NewRC) 00420 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 00421 00422 // Now check for aliases. 00423 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 00424 // If an alias of the reg is used during the live range, give up. 00425 // Note that this allows us to skip checking if AntiDepReg 00426 // overlaps with any of the aliases, among other things. 00427 unsigned AliasReg = *Alias; 00428 if (Classes[AliasReg]) { 00429 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 00430 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 00431 } 00432 } 00433 00434 // If we're still willing to consider this register, note the reference. 00435 if (Classes[Reg] != reinterpret_cast<TargetRegisterClass *>(-1)) 00436 RegRefs.insert(std::make_pair(Reg, &MO)); 00437 } 00438 } 00439 00440 void SchedulePostRATDList::ScanInstruction(MachineInstr *MI, 00441 unsigned Count) { 00442 // Update liveness. 00443 // Proceding upwards, registers that are defed but not used in this 00444 // instruction are now dead. 00445 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00446 MachineOperand &MO = MI->getOperand(i); 00447 if (!MO.isReg()) continue; 00448 unsigned Reg = MO.getReg(); 00449 if (Reg == 0) continue; 00450 if (!MO.isDef()) continue; 00451 // Ignore two-addr defs. 00452 if (MI->isRegTiedToUseOperand(i)) continue; 00453 00454 DefIndices[Reg] = Count; 00455 KillIndices[Reg] = ~0u; 00456 assert(((KillIndices[Reg] == ~0u) != 00457 (DefIndices[Reg] == ~0u)) && 00458 "Kill and Def maps aren't consistent for Reg!"); 00459 Classes[Reg] = 0; 00460 RegRefs.erase(Reg); 00461 // Repeat, for all subregs. 00462 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 00463 *Subreg; ++Subreg) { 00464 unsigned SubregReg = *Subreg; 00465 DefIndices[SubregReg] = Count; 00466 KillIndices[SubregReg] = ~0u; 00467 Classes[SubregReg] = 0; 00468 RegRefs.erase(SubregReg); 00469 } 00470 // Conservatively mark super-registers as unusable. 00471 for (const unsigned *Super = TRI->getSuperRegisters(Reg); 00472 *Super; ++Super) { 00473 unsigned SuperReg = *Super; 00474 Classes[SuperReg] = reinterpret_cast<TargetRegisterClass *>(-1); 00475 } 00476 } 00477 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00478 MachineOperand &MO = MI->getOperand(i); 00479 if (!MO.isReg()) continue; 00480 unsigned Reg = MO.getReg(); 00481 if (Reg == 0) continue; 00482 if (!MO.isUse()) continue; 00483 00484 const TargetRegisterClass *NewRC = 0; 00485 if (i < MI->getDesc().getNumOperands()) 00486 NewRC = MI->getDesc().OpInfo[i].getRegClass(TRI); 00487 00488 // For now, only allow the register to be changed if its register 00489 // class is consistent across all uses. 00490 if (!Classes[Reg] && NewRC) 00491 Classes[Reg] = NewRC; 00492 else if (!NewRC || Classes[Reg] != NewRC) 00493 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 00494 00495 RegRefs.insert(std::make_pair(Reg, &MO)); 00496 00497 // It wasn't previously live but now it is, this is a kill. 00498 if (KillIndices[Reg] == ~0u) { 00499 KillIndices[Reg] = Count; 00500 DefIndices[Reg] = ~0u; 00501 assert(((KillIndices[Reg] == ~0u) != 00502 (DefIndices[Reg] == ~0u)) && 00503 "Kill and Def maps aren't consistent for Reg!"); 00504 } 00505 // Repeat, for all aliases. 00506 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 00507 unsigned AliasReg = *Alias; 00508 if (KillIndices[AliasReg] == ~0u) { 00509 KillIndices[AliasReg] = Count; 00510 DefIndices[AliasReg] = ~0u; 00511 } 00512 } 00513 } 00514 } 00515 00516 unsigned 00517 SchedulePostRATDList::findSuitableFreeRegister(unsigned AntiDepReg, 00518 unsigned LastNewReg, 00519 const TargetRegisterClass *RC) { 00520 for (TargetRegisterClass::iterator R = RC->allocation_order_begin(MF), 00521 RE = RC->allocation_order_end(MF); R != RE; ++R) { 00522 unsigned NewReg = *R; 00523 // Don't replace a register with itself. 00524 if (NewReg == AntiDepReg) continue; 00525 // Don't replace a register with one that was recently used to repair 00526 // an anti-dependence with this AntiDepReg, because that would 00527 // re-introduce that anti-dependence. 00528 if (NewReg == LastNewReg) continue; 00529 // If NewReg is dead and NewReg's most recent def is not before 00530 // AntiDepReg's kill, it's safe to replace AntiDepReg with NewReg. 00531 assert(((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u)) && 00532 "Kill and Def maps aren't consistent for AntiDepReg!"); 00533 assert(((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u)) && 00534 "Kill and Def maps aren't consistent for NewReg!"); 00535 if (KillIndices[NewReg] != ~0u || 00536 Classes[NewReg] == reinterpret_cast<TargetRegisterClass *>(-1) || 00537 KillIndices[AntiDepReg] > DefIndices[NewReg]) 00538 continue; 00539 return NewReg; 00540 } 00541 00542 // No registers are free and available! 00543 return 0; 00544 } 00545 00546 /// BreakAntiDependencies - Identifiy anti-dependencies along the critical path 00547 /// of the ScheduleDAG and break them by renaming registers. 00548 /// 00549 bool SchedulePostRATDList::BreakAntiDependencies() { 00550 // The code below assumes that there is at least one instruction, 00551 // so just duck out immediately if the block is empty. 00552 if (SUnits.empty()) return false; 00553 00554 // Find the node at the bottom of the critical path. 00555 SUnit *Max = 0; 00556 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 00557 SUnit *SU = &SUnits[i]; 00558 if (!Max || SU->getDepth() + SU->Latency > Max->getDepth() + Max->Latency) 00559 Max = SU; 00560 } 00561 00562 DEBUG(errs() << "Critical path has total latency " 00563 << (Max->getDepth() + Max->Latency) << "\n"); 00564 00565 // Track progress along the critical path through the SUnit graph as we walk 00566 // the instructions. 00567 SUnit *CriticalPathSU = Max; 00568 MachineInstr *CriticalPathMI = CriticalPathSU->getInstr(); 00569 00570 // Consider this pattern: 00571 // A = ... 00572 // ... = A 00573 // A = ... 00574 // ... = A 00575 // A = ... 00576 // ... = A 00577 // A = ... 00578 // ... = A 00579 // There are three anti-dependencies here, and without special care, 00580 // we'd break all of them using the same register: 00581 // A = ... 00582 // ... = A 00583 // B = ... 00584 // ... = B 00585 // B = ... 00586 // ... = B 00587 // B = ... 00588 // ... = B 00589 // because at each anti-dependence, B is the first register that 00590 // isn't A which is free. This re-introduces anti-dependencies 00591 // at all but one of the original anti-dependencies that we were 00592 // trying to break. To avoid this, keep track of the most recent 00593 // register that each register was replaced with, avoid 00594 // using it to repair an anti-dependence on the same register. 00595 // This lets us produce this: 00596 // A = ... 00597 // ... = A 00598 // B = ... 00599 // ... = B 00600 // C = ... 00601 // ... = C 00602 // B = ... 00603 // ... = B 00604 // This still has an anti-dependence on B, but at least it isn't on the 00605 // original critical path. 00606 // 00607 // TODO: If we tracked more than one register here, we could potentially 00608 // fix that remaining critical edge too. This is a little more involved, 00609 // because unlike the most recent register, less recent registers should 00610 // still be considered, though only if no other registers are available. 00611 unsigned LastNewReg[TargetRegisterInfo::FirstVirtualRegister] = {}; 00612 00613 // Attempt to break anti-dependence edges on the critical path. Walk the 00614 // instructions from the bottom up, tracking information about liveness 00615 // as we go to help determine which registers are available. 00616 bool Changed = false; 00617 unsigned Count = InsertPosIndex - 1; 00618 for (MachineBasicBlock::iterator I = InsertPos, E = Begin; 00619 I != E; --Count) { 00620 MachineInstr *MI = --I; 00621 00622 // After regalloc, IMPLICIT_DEF instructions aren't safe to treat as 00623 // dependence-breaking. In the case of an INSERT_SUBREG, the IMPLICIT_DEF 00624 // is left behind appearing to clobber the super-register, while the 00625 // subregister needs to remain live. So we just ignore them. 00626 if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 00627 continue; 00628 00629 // Check if this instruction has a dependence on the critical path that 00630 // is an anti-dependence that we may be able to break. If it is, set 00631 // AntiDepReg to the non-zero register associated with the anti-dependence. 00632 // 00633 // We limit our attention to the critical path as a heuristic to avoid 00634 // breaking anti-dependence edges that aren't going to significantly 00635 // impact the overall schedule. There are a limited number of registers 00636 // and we want to save them for the important edges. 00637 // 00638 // TODO: Instructions with multiple defs could have multiple 00639 // anti-dependencies. The current code here only knows how to break one 00640 // edge per instruction. Note that we'd have to be able to break all of 00641 // the anti-dependencies in an instruction in order to be effective. 00642 unsigned AntiDepReg = 0; 00643 if (MI == CriticalPathMI) { 00644 if (SDep *Edge = CriticalPathStep(CriticalPathSU)) { 00645 SUnit *NextSU = Edge->getSUnit(); 00646 00647 // Only consider anti-dependence edges. 00648 if (Edge->getKind() == SDep::Anti) { 00649 AntiDepReg = Edge->getReg(); 00650 assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); 00651 // Don't break anti-dependencies on non-allocatable registers. 00652 if (!AllocatableSet.test(AntiDepReg)) 00653 AntiDepReg = 0; 00654 else { 00655 // If the SUnit has other dependencies on the SUnit that it 00656 // anti-depends on, don't bother breaking the anti-dependency 00657 // since those edges would prevent such units from being 00658 // scheduled past each other regardless. 00659 // 00660 // Also, if there are dependencies on other SUnits with the 00661 // same register as the anti-dependency, don't attempt to 00662 // break it. 00663 for (SUnit::pred_iterator P = CriticalPathSU->Preds.begin(), 00664 PE = CriticalPathSU->Preds.end(); P != PE; ++P) 00665 if (P->getSUnit() == NextSU ? 00666 (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) : 00667 (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) { 00668 AntiDepReg = 0; 00669 break; 00670 } 00671 } 00672 } 00673 CriticalPathSU = NextSU; 00674 CriticalPathMI = CriticalPathSU->getInstr(); 00675 } else { 00676 // We've reached the end of the critical path. 00677 CriticalPathSU = 0; 00678 CriticalPathMI = 0; 00679 } 00680 } 00681 00682 PrescanInstruction(MI); 00683 00684 // If this instruction has a use of AntiDepReg, breaking it 00685 // is invalid. 00686 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00687 MachineOperand &MO = MI->getOperand(i); 00688 if (!MO.isReg()) continue; 00689 unsigned Reg = MO.getReg(); 00690 if (Reg == 0) continue; 00691 if (MO.isUse() && AntiDepReg == Reg) { 00692 AntiDepReg = 0; 00693 break; 00694 } 00695 } 00696 00697 // Determine AntiDepReg's register class, if it is live and is 00698 // consistently used within a single class. 00699 const TargetRegisterClass *RC = AntiDepReg != 0 ? Classes[AntiDepReg] : 0; 00700 assert((AntiDepReg == 0 || RC != NULL) && 00701 "Register should be live if it's causing an anti-dependence!"); 00702 if (RC == reinterpret_cast<TargetRegisterClass *>(-1)) 00703 AntiDepReg = 0; 00704 00705 // Look for a suitable register to use to break the anti-depenence. 00706 // 00707 // TODO: Instead of picking the first free register, consider which might 00708 // be the best. 00709 if (AntiDepReg != 0) { 00710 if (unsigned NewReg = findSuitableFreeRegister(AntiDepReg, 00711 LastNewReg[AntiDepReg], 00712 RC)) { 00713 DEBUG(errs() << "Breaking anti-dependence edge on " 00714 << TRI->getName(AntiDepReg) 00715 << " with " << RegRefs.count(AntiDepReg) << " references" 00716 << " using " << TRI->getName(NewReg) << "!\n"); 00717 00718 // Update the references to the old register to refer to the new 00719 // register. 00720 std::pair<std::multimap<unsigned, MachineOperand *>::iterator, 00721 std::multimap<unsigned, MachineOperand *>::iterator> 00722 Range = RegRefs.equal_range(AntiDepReg); 00723 for (std::multimap<unsigned, MachineOperand *>::iterator 00724 Q = Range.first, QE = Range.second; Q != QE; ++Q) 00725 Q->second->setReg(NewReg); 00726 00727 // We just went back in time and modified history; the 00728 // liveness information for the anti-depenence reg is now 00729 // inconsistent. Set the state as if it were dead. 00730 Classes[NewReg] = Classes[AntiDepReg]; 00731 DefIndices[NewReg] = DefIndices[AntiDepReg]; 00732 KillIndices[NewReg] = KillIndices[AntiDepReg]; 00733 assert(((KillIndices[NewReg] == ~0u) != 00734 (DefIndices[NewReg] == ~0u)) && 00735 "Kill and Def maps aren't consistent for NewReg!"); 00736 00737 Classes[AntiDepReg] = 0; 00738 DefIndices[AntiDepReg] = KillIndices[AntiDepReg]; 00739 KillIndices[AntiDepReg] = ~0u; 00740 assert(((KillIndices[AntiDepReg] == ~0u) != 00741 (DefIndices[AntiDepReg] == ~0u)) && 00742 "Kill and Def maps aren't consistent for AntiDepReg!"); 00743 00744 RegRefs.erase(AntiDepReg); 00745 Changed = true; 00746 LastNewReg[AntiDepReg] = NewReg; 00747 } 00748 } 00749 00750 ScanInstruction(MI, Count); 00751 } 00752 00753 return Changed; 00754 } 00755 00756 //===----------------------------------------------------------------------===// 00757 // Top-Down Scheduling 00758 //===----------------------------------------------------------------------===// 00759 00760 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 00761 /// the PendingQueue if the count reaches zero. Also update its cycle bound. 00762 void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) { 00763 SUnit *SuccSU = SuccEdge->getSUnit(); 00764 --SuccSU->NumPredsLeft; 00765 00766 #ifndef NDEBUG 00767 if (SuccSU->NumPredsLeft < 0) { 00768 cerr << "*** Scheduling failed! ***\n"; 00769 SuccSU->dump(this); 00770 cerr << " has been released too many times!\n"; 00771 llvm_unreachable(0); 00772 } 00773 #endif 00774 00775 // Compute how many cycles it will be before this actually becomes 00776 // available. This is the max of the start time of all predecessors plus 00777 // their latencies. 00778 SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency()); 00779 00780 // If all the node's predecessors are scheduled, this node is ready 00781 // to be scheduled. Ignore the special ExitSU node. 00782 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 00783 PendingQueue.push_back(SuccSU); 00784 } 00785 00786 /// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors. 00787 void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) { 00788 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 00789 I != E; ++I) 00790 ReleaseSucc(SU, &*I); 00791 } 00792 00793 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 00794 /// count of its successors. If a successor pending count is zero, add it to 00795 /// the Available queue. 00796 void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 00797 DEBUG(errs() << "*** Scheduling [" << CurCycle << "]: "); 00798 DEBUG(SU->dump(this)); 00799 00800 Sequence.push_back(SU); 00801 assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); 00802 SU->setDepthToAtLeast(CurCycle); 00803 00804 ReleaseSuccessors(SU); 00805 SU->isScheduled = true; 00806 AvailableQueue.ScheduledNode(SU); 00807 } 00808 00809 /// ListScheduleTopDown - The main loop of list scheduling for top-down 00810 /// schedulers. 00811 void SchedulePostRATDList::ListScheduleTopDown() { 00812 unsigned CurCycle = 0; 00813 00814 // Release any successors of the special Entry node. 00815 ReleaseSuccessors(&EntrySU); 00816 00817 // All leaves to Available queue. 00818 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 00819 // It is available if it has no predecessors. 00820 if (SUnits[i].Preds.empty()) { 00821 AvailableQueue.push(&SUnits[i]); 00822 SUnits[i].isAvailable = true; 00823 } 00824 } 00825 00826 // In any cycle where we can't schedule any instructions, we must 00827 // stall or emit a noop, depending on the target. 00828 bool CycleInstCnt = 0; 00829 00830 // While Available queue is not empty, grab the node with the highest 00831 // priority. If it is not ready put it back. Schedule the node. 00832 std::vector<SUnit*> NotReady; 00833 Sequence.reserve(SUnits.size()); 00834 while (!AvailableQueue.empty() || !PendingQueue.empty()) { 00835 // Check to see if any of the pending instructions are ready to issue. If 00836 // so, add them to the available queue. 00837 unsigned MinDepth = ~0u; 00838 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { 00839 if (PendingQueue[i]->getDepth() <= CurCycle) { 00840 AvailableQueue.push(PendingQueue[i]); 00841 PendingQueue[i]->isAvailable = true; 00842 PendingQueue[i] = PendingQueue.back(); 00843 PendingQueue.pop_back(); 00844 --i; --e; 00845 } else if (PendingQueue[i]->getDepth() < MinDepth) 00846 MinDepth = PendingQueue[i]->getDepth(); 00847 } 00848 00849 DEBUG(errs() << "\n*** Examining Available\n"; 00850 LatencyPriorityQueue q = AvailableQueue; 00851 while (!q.empty()) { 00852 SUnit *su = q.pop(); 00853 errs() << "Height " << su->getHeight() << ": "; 00854 su->dump(this); 00855 }); 00856 00857 SUnit *FoundSUnit = 0; 00858 00859 bool HasNoopHazards = false; 00860 while (!AvailableQueue.empty()) { 00861 SUnit *CurSUnit = AvailableQueue.pop(); 00862 00863 ScheduleHazardRecognizer::HazardType HT = 00864 HazardRec->getHazardType(CurSUnit); 00865 if (HT == ScheduleHazardRecognizer::NoHazard) { 00866 FoundSUnit = CurSUnit; 00867 break; 00868 } 00869 00870 // Remember if this is a noop hazard. 00871 HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard; 00872 00873 NotReady.push_back(CurSUnit); 00874 } 00875 00876 // Add the nodes that aren't ready back onto the available list. 00877 if (!NotReady.empty()) { 00878 AvailableQueue.push_all(NotReady); 00879 NotReady.clear(); 00880 } 00881 00882 // If we found a node to schedule, do it now. 00883 if (FoundSUnit) { 00884 ScheduleNodeTopDown(FoundSUnit, CurCycle); 00885 HazardRec->EmitInstruction(FoundSUnit); 00886 CycleInstCnt++; 00887 00888 // If we are using the target-specific hazards, then don't 00889 // advance the cycle time just because we schedule a node. If 00890 // the target allows it we can schedule multiple nodes in the 00891 // same cycle. 00892 if (!EnablePostRAHazardAvoidance) { 00893 if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops! 00894 ++CurCycle; 00895 } 00896 } else { 00897 if (CycleInstCnt > 0) { 00898 DEBUG(errs() << "*** Finished cycle " << CurCycle << '\n'); 00899 HazardRec->AdvanceCycle(); 00900 } else if (!HasNoopHazards) { 00901 // Otherwise, we have a pipeline stall, but no other problem, 00902 // just advance the current cycle and try again. 00903 DEBUG(errs() << "*** Stall in cycle " << CurCycle << '\n'); 00904 HazardRec->AdvanceCycle(); 00905 ++NumStalls; 00906 } else { 00907 // Otherwise, we have no instructions to issue and we have instructions 00908 // that will fault if we don't do this right. This is the case for 00909 // processors without pipeline interlocks and other cases. 00910 DEBUG(errs() << "*** Emitting noop in cycle " << CurCycle << '\n'); 00911 HazardRec->EmitNoop(); 00912 Sequence.push_back(0); // NULL here means noop 00913 ++NumNoops; 00914 } 00915 00916 ++CurCycle; 00917 CycleInstCnt = 0; 00918 } 00919 } 00920 00921 #ifndef NDEBUG 00922 VerifySchedule(/*isBottomUp=*/false); 00923 #endif 00924 } 00925 00926 //===----------------------------------------------------------------------===// 00927 // Public Constructor Functions 00928 //===----------------------------------------------------------------------===// 00929 00930 FunctionPass *llvm::createPostRAScheduler() { 00931 return new PostRAScheduler(); 00932 }