diff options
author | Ryotaro KASUGA <kasuga.ryotaro@fujitsu.com> | 2024-07-01 09:07:32 +0900 |
---|---|---|
committer | GitHub <noreply@github.com> | 2024-07-01 09:07:32 +0900 |
commit | e19ac0dcfd7357161210f157ed0559836e88155f (patch) | |
tree | 2d1b3a147a12281cdb84f47bba7225a85ddd14cb /llvm/lib/CodeGen/MachinePipeliner.cpp | |
parent | 6c1c451b867f250f1c2fab709f0c8657ffd21116 (diff) | |
download | llvm-e19ac0dcfd7357161210f157ed0559836e88155f.zip llvm-e19ac0dcfd7357161210f157ed0559836e88155f.tar.gz llvm-e19ac0dcfd7357161210f157ed0559836e88155f.tar.bz2 |
[MachinePipeliner] Fix constraints aren't considered in certain cases (#95356)
when scheduling
When scheduling an instruction, if both any predecessors and any
successors of the instruction are already scheduled, `SchedStart` isn't
taken into account. It may result generating incorrect code. This patch
fixes the problem. Also, this patch merges `SchedStart` into
`EarlyStart` (same for `SchedEnd`).
Fixes https://github.com/llvm/llvm-project/issues/93936
Diffstat (limited to 'llvm/lib/CodeGen/MachinePipeliner.cpp')
-rw-r--r-- | llvm/lib/CodeGen/MachinePipeliner.cpp | 70 |
1 files changed, 39 insertions, 31 deletions
diff --git a/llvm/lib/CodeGen/MachinePipeliner.cpp b/llvm/lib/CodeGen/MachinePipeliner.cpp index 7ff14a6..515c7f8 100644 --- a/llvm/lib/CodeGen/MachinePipeliner.cpp +++ b/llvm/lib/CodeGen/MachinePipeliner.cpp @@ -2461,47 +2461,43 @@ bool SwingSchedulerDAG::schedulePipeline(SMSchedule &Schedule) { // upon the scheduled time for any predecessors/successors. int EarlyStart = INT_MIN; int LateStart = INT_MAX; - // These values are set when the size of the schedule window is limited - // due to chain dependences. - int SchedEnd = INT_MAX; - int SchedStart = INT_MIN; - Schedule.computeStart(SU, &EarlyStart, &LateStart, &SchedEnd, &SchedStart, - II, this); + Schedule.computeStart(SU, &EarlyStart, &LateStart, II, this); LLVM_DEBUG({ dbgs() << "\n"; dbgs() << "Inst (" << SU->NodeNum << ") "; SU->getInstr()->dump(); dbgs() << "\n"; }); - LLVM_DEBUG({ - dbgs() << format("\tes: %8x ls: %8x me: %8x ms: %8x\n", EarlyStart, - LateStart, SchedEnd, SchedStart); - }); + LLVM_DEBUG( + dbgs() << format("\tes: %8x ls: %8x\n", EarlyStart, LateStart)); - if (EarlyStart > LateStart || SchedEnd < EarlyStart || - SchedStart > LateStart) + if (EarlyStart > LateStart) scheduleFound = false; - else if (EarlyStart != INT_MIN && LateStart == INT_MAX) { - SchedEnd = std::min(SchedEnd, EarlyStart + (int)II - 1); - scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II); - } else if (EarlyStart == INT_MIN && LateStart != INT_MAX) { - SchedStart = std::max(SchedStart, LateStart - (int)II + 1); - scheduleFound = Schedule.insert(SU, LateStart, SchedStart, II); - } else if (EarlyStart != INT_MIN && LateStart != INT_MAX) { - SchedEnd = - std::min(SchedEnd, std::min(LateStart, EarlyStart + (int)II - 1)); - // When scheduling a Phi it is better to start at the late cycle and go - // backwards. The default order may insert the Phi too far away from - // its first dependence. - if (SU->getInstr()->isPHI()) - scheduleFound = Schedule.insert(SU, SchedEnd, EarlyStart, II); + else if (EarlyStart != INT_MIN && LateStart == INT_MAX) + scheduleFound = + Schedule.insert(SU, EarlyStart, EarlyStart + (int)II - 1, II); + else if (EarlyStart == INT_MIN && LateStart != INT_MAX) + scheduleFound = + Schedule.insert(SU, LateStart, LateStart - (int)II + 1, II); + else if (EarlyStart != INT_MIN && LateStart != INT_MAX) { + LateStart = std::min(LateStart, EarlyStart + (int)II - 1); + // When scheduling a Phi it is better to start at the late cycle and + // go backwards. The default order may insert the Phi too far away + // from its first dependence. + // Also, do backward search when all scheduled predecessors are + // loop-carried output/order dependencies. Empirically, there are also + // cases where scheduling becomes possible with backward search. + if (SU->getInstr()->isPHI() || + Schedule.onlyHasLoopCarriedOutputOrOrderPreds(SU, this)) + scheduleFound = Schedule.insert(SU, LateStart, EarlyStart, II); else - scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II); + scheduleFound = Schedule.insert(SU, EarlyStart, LateStart, II); } else { int FirstCycle = Schedule.getFirstCycle(); scheduleFound = Schedule.insert(SU, FirstCycle + getASAP(SU), FirstCycle + getASAP(SU) + II - 1, II); } + // Even if we find a schedule, make sure the schedule doesn't exceed the // allowable number of stages. We keep trying if this happens. if (scheduleFound) @@ -2909,8 +2905,7 @@ static SUnit *multipleIterations(SUnit *SU, SwingSchedulerDAG *DAG) { /// Compute the scheduling start slot for the instruction. The start slot /// depends on any predecessor or successor nodes scheduled already. void SMSchedule::computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart, - int *MinEnd, int *MaxStart, int II, - SwingSchedulerDAG *DAG) { + int II, SwingSchedulerDAG *DAG) { // Iterate over each instruction that has been scheduled already. The start // slot computation depends on whether the previously scheduled instruction // is a predecessor or successor of the specified instruction. @@ -2929,7 +2924,7 @@ void SMSchedule::computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart, *MaxEarlyStart = std::max(*MaxEarlyStart, EarlyStart); if (DAG->isLoopCarriedDep(SU, Dep, false)) { int End = earliestCycleInChain(Dep) + (II - 1); - *MinEnd = std::min(*MinEnd, End); + *MinLateStart = std::min(*MinLateStart, End); } } else { int LateStart = cycle - Dep.getLatency() + @@ -2953,7 +2948,7 @@ void SMSchedule::computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart, *MinLateStart = std::min(*MinLateStart, LateStart); if (DAG->isLoopCarriedDep(SU, Dep)) { int Start = latestCycleInChain(Dep) + 1 - II; - *MaxStart = std::max(*MaxStart, Start); + *MaxEarlyStart = std::max(*MaxEarlyStart, Start); } } else { int EarlyStart = cycle + Dep.getLatency() - @@ -3146,6 +3141,19 @@ bool SMSchedule::isLoopCarriedDefOfUse(const SwingSchedulerDAG *SSD, return false; } +/// Return true if all scheduled predecessors are loop-carried output/order +/// dependencies. +bool SMSchedule::onlyHasLoopCarriedOutputOrOrderPreds( + SUnit *SU, SwingSchedulerDAG *DAG) const { + for (const SDep &Pred : SU->Preds) + if (InstrToCycle.count(Pred.getSUnit()) && !DAG->isBackedge(SU, Pred)) + return false; + for (const SDep &Succ : SU->Succs) + if (InstrToCycle.count(Succ.getSUnit()) && DAG->isBackedge(SU, Succ)) + return false; + return true; +} + /// Determine transitive dependences of unpipelineable instructions SmallSet<SUnit *, 8> SMSchedule::computeUnpipelineableNodes( SwingSchedulerDAG *SSD, TargetInstrInfo::PipelinerLoopInfo *PLI) { |