Lines Matching +full:cycle +full:- +full:3
1 //======----------- WindowScheduler.cpp - window scheduler -------------======//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
30 // target-specific logic can be added in initialize(), preProcess(), and
37 //===----------------------------------------------------------------------===//
64 WindowSearchNum("window-search-num",
70 "window-search-ratio",
77 "window-ii-coeff",
83 "window-region-limit",
86 cl::Hidden, cl::init(3));
89 "window-diff-limit",
99 WindowIILimit("window-ii-limit",
104 : Context(C), MF(C->MF), MBB(ML.getHeader()), Loop(ML), in WindowScheduler()
105 Subtarget(&MF->getSubtarget()), TII(Subtarget->getInstrInfo()), in WindowScheduler()
106 TRI(Subtarget->getRegisterInfo()), MRI(&MF->getRegInfo()) { in WindowScheduler()
116 // The window algorithm is time-consuming, and its compilation time should be in run()
128 // The scheduling starts with non-phi instruction, so SchedPhiNum needs to in run()
132 SchedDAG->startBlock(MBB); in run()
133 SchedDAG->enterRegion(MBB, Range.begin(), Range.end(), SchedInstrNum); in run()
134 SchedDAG->schedule(); in run()
135 LLVM_DEBUG(SchedDAG->dump()); in run()
170 : Context->PassConfig->createMachineScheduler(Context); in createMachineScheduler()
174 if (!Subtarget->enableWindowScheduler()) { in initialize()
190 if (!Context->LIS) { in initialize()
211 auto PLI = TII->analyzeLoopForPipelining(MBB); in initialize()
224 if (TII->isSchedulingBoundary(MI, MBB, *MF)) { in initialize()
229 if (PLI->shouldIgnoreForPipelining(&MI)) { in initialize()
253 TripleDAG->startBlock(MBB); in preProcess()
254 TripleDAG->enterRegion( in preProcess()
255 MBB, MBB->begin(), MBB->getFirstTerminator(), in preProcess()
256 std::distance(MBB->begin(), MBB->getFirstTerminator())); in preProcess()
257 TripleDAG->buildSchedGraph(Context->AA); in preProcess()
263 TripleDAG->exitRegion(); in postProcess()
264 TripleDAG->finishBlock(); in postProcess()
269 for (auto &MI : MBB->instrs()) in backupMBB()
273 Context->LIS->getSlotIndexes()->removeMachineInstrFromMaps(MI, true); in backupMBB()
274 MBB->remove(&MI); in backupMBB()
281 Context->LIS->getSlotIndexes()->removeMachineInstrFromMaps(MI, true); in restoreMBB()
286 MBB->push_back(MI); in restoreMBB()
291 const unsigned DuplicateNum = 3; in generateTripleMBB()
296 // terminators. At the same time, we back up the anti-register of phis. in generateTripleMBB()
300 if (MI->isMetaInstruction() || MI->isTerminator()) in generateTripleMBB()
302 if (MI->isPHI()) in generateTripleMBB()
304 DefPairs[MI->getOperand(0).getReg()] = AntiReg; in generateTripleMBB()
305 auto *NewMI = MF->CloneMachineInstr(MI); in generateTripleMBB()
306 MBB->push_back(NewMI); in generateTripleMBB()
315 if (MI->isPHI() || MI->isMetaInstruction() || in generateTripleMBB()
316 (MI->isTerminator() && Cnt < DuplicateNum - 1)) in generateTripleMBB()
318 auto *NewMI = MF->CloneMachineInstr(MI); in generateTripleMBB()
321 for (auto MO : NewMI->all_defs()) in generateTripleMBB()
324 MRI->createVirtualRegister(MRI->getRegClass(MO.getReg())); in generateTripleMBB()
325 NewMI->substituteRegister(MO.getReg(), NewDef, 0, *TRI); in generateTripleMBB()
330 if (NewMI->readsRegister(DefRegPair.first, TRI)) { in generateTripleMBB()
332 // Note the update process for '%1 -> %9' in '%10 = sub i32 %9, %3': in generateTripleMBB()
334 // BB.3: DefPairs in generateTripleMBB()
336 // %1 = phi i32 [%2, %BB.1], [%7, %BB.3] (%1,%7) in generateTripleMBB()
340 // %4 = sub i32 %1, %3 in generateTripleMBB()
344 // ---------------------------------- in generateTripleMBB()
346 // %8 = sub i32 %7, %3 (%1,%7),(%4,%8) in generateTripleMBB()
350 // ---------------------------------- in generateTripleMBB()
352 // %10 = sub i32 %9, %3 (%1,%7),(%4,%10),(%7,%9) in generateTripleMBB()
361 NewMI->substituteRegister(DefRegPair.first, NewUse, 0, *TRI); in generateTripleMBB()
366 MBB->push_back(NewMI); in generateTripleMBB()
371 // Step 3: The registers used by phis are updated, and they are generated in in generateTripleMBB()
374 // %1 = phi i32 [%2, %BB.1], [%7, %BB.3] in generateTripleMBB()
376 // %1 = phi i32 [%2, %BB.1], [%11, %BB.3] in generateTripleMBB()
377 for (auto &Phi : MBB->phis()) { in generateTripleMBB()
389 auto OldPos = MBB->begin(); in restoreTripleMBB()
391 auto CurPos = MI->getIterator(); in restoreTripleMBB()
393 MBB->splice(OldPos, MBB, CurPos); in restoreTripleMBB()
394 Context->LIS->handleMove(*MI, /*UpdateFlags=*/false); in restoreTripleMBB()
427 // ResourceManager and DAG are used to calculate the maximum cycle for the in calculateMaxCycle()
435 // The predecessors of current MI determine its earliest issue cycle. in calculateMaxCycle()
436 for (auto &Pred : SU->Preds) { in calculateMaxCycle()
439 auto *PredMI = Pred.getSUnit()->getInstr(); in calculateMaxCycle()
444 if (!TII->isZeroCost(MI.getOpcode())) { in calculateMaxCycle()
463 // Based on the MaxCycle and the issue cycle of A and B, we can determine
464 // whether it is necessary to add a stall cycle. This is because, without
465 // inserting the stall cycle, the latency constraint between A and B cannot be
475 // ~~~~~~~~~~~~~~~~~~~|~~~~~~~~~~~~~~~~~~~~ ----schedule window-----
481 // ~~~~~~~~~~~~~~~~~~~:~~~~~~~~~~~~~~~~~~~~ ------------------------
484 // MBB copy 3 < MI B'>
497 auto *SU = TripleDAG->getSUnit(&MI); in calculateStallCycle()
499 for (auto &Succ : SU->Succs) { in calculateStallCycle()
500 if (Succ.isWeak() || Succ.getSUnit() == &TripleDAG->ExitSU) in calculateStallCycle()
502 // If the expected cycle does not exceed CurrentII, no check is needed. in calculateStallCycle()
505 // If the cycle of the scheduled MI A is less than that of the scheduled in calculateStallCycle()
508 auto *SuccMI = Succ.getSUnit()->getInstr(); in calculateStallCycle()
512 // Get the stall cycle introduced by the register between two trips. in calculateStallCycle()
513 int StallCycle = DefCycle + (int)Succ.getLatency() - CurrentII - UseCycle; in calculateStallCycle()
529 // The value of II is equal to the maximum execution cycle plus 1. in analyseII()
535 for (auto &Phi : MBB->phis()) { in schedulePhi()
537 auto *SU = TripleDAG->getSUnit(&Phi); in schedulePhi()
538 for (auto &Succ : SU->Succs) { in schedulePhi()
542 // Phi is scheduled before the successor of stage 0. The issue cycle of in schedulePhi()
543 // phi is the latest cycle in this interval. in schedulePhi()
544 auto *SuccMI = Succ.getSUnit()->getInstr(); in schedulePhi()
545 int Cycle = getOriCycle(SuccMI); in schedulePhi() local
547 LateCycle = std::min(LateCycle, Cycle); in schedulePhi()
549 // The anti-dependency of phi need to be handled separately in the same way. in schedulePhi()
551 auto *AntiMI = MRI->getVRegDef(AntiReg); in schedulePhi()
553 if (AntiMI->getParent() == MBB) { in schedulePhi()
559 // If there is no limit to the late cycle, a default value is given. in schedulePhi()
561 LateCycle = (int)(II - 1); in schedulePhi()
563 // The issue cycle of phi is set to the latest cycle in the interval. in schedulePhi()
571 // At each issue cycle, phi is placed before MIs in stage 0. So the simplest in getIssueOrder()
572 // way is to put phi at the beginning of the current cycle. in getIssueOrder()
575 for (auto &Phi : MBB->phis()) in getIssueOrder()
583 for (int Cycle = 0; Cycle < (int)II; ++Cycle) { in getIssueOrder() local
584 if (!CycleToMIs.count(Cycle)) in getIssueOrder()
586 for (auto *MI : CycleToMIs[Cycle]) in getIssueOrder()
624 return std::get<3>(A) < std::get<3>(B); in expand()
640 ModuloScheduleExpander MSE(*MF, MS, *Context->LIS, in expand()
656 Context->LIS->repairIntervalsInRange(MBB, MBB->begin(), MBB->end(), UsedRegs); in updateLiveIntervals()
661 auto RegionBegin = MBB->begin(); in getScheduleRange()
671 assert(OriToCycle.count(OriMI) && "Cannot find schedule cycle!"); in getOriCycle()
690 if (MI->isMetaInstruction()) in getOriStage()
700 assert(Phi->isPHI() && "Expecting PHI!"); in getAntiRegister()
702 for (auto MO : Phi->uses()) { in getAntiRegister()