Port the post-RA anti-dependency breaker lifecycle to ScheduleDAGMI so
PostMachineScheduler can rename physical registers across scheduling
regions. Drive the StartBlock/Observe/BreakAntiDependencies/FinishBlock
sequence from the DAG, selecting the aggressive or critical breaker from
the subtarget's anti-dependency mode.
Add the -misched-postra-antidep override so the machinery can be tested
with llc, and cover a within-region WAR hazard with a RISC-V test that
contrasts the ANTIDEP and NO-ANTIDEP results.
Preserve MachineRegisterClassInfo across late AArch64 passes and the
RISC-V load/store optimizer, which only rewrite machine instructions,
so PostMachineScheduler can reuse the existing analysis result.
Assisted-by: TRAE CLI (GPT-5.6)
Reviewers:
tlinthic, lenary, tomershafir, mshockwave, lukel97, topperc, optimisan, MatzeB, cofibrant
Pull Request: https://github.com/llvm/llvm-project/pull/231790
`GenericScheduler::reschedulePhysReg` can leave stale `read-undef` flags
when moving an already-scheduled COPY. This can be exposed most commonly
if a user introduces a large inline assembly section that can otherwise
limit the registers that are available to the compiler.
This addresses this bug in 2 steps:
1) Check for backends that can produce `read-undef` on subregisters in a
way that can meaningful move (e.g. has lane mask).
2) After a move regenerate the `read-undef` flags for just the region of
"movement" between the old/new location in the code.
You can find the motivating example here:
https://gist.github.com/njriasan/73a4b080e98cdb54bd0b59138bc5ad9c
The test case would crash before this patch because in that context the
SUnit can be an ExitSU thus it would assert inside the new SUnit
operator<<. Should use `dumpNodeName()`.
I plan to fix other callers in a followup - though those callers are not
crashing but merely print a "random" number.
Continue with cleanups enabled by #158224.. TRI can now always directly
be referenced from TargetInstrInfo
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>
Allow targets to add an MachineScheduler before PHI elimination, i.e. in
SSA mode.
Add initial support in AMDGPU backend for using SSA Machine Scheduler
instead of normal Machine Scheduler.
(This behaviour is disabled by default.)
Also add basic "kick the tyres" demonstrator tests.
This change is intended to support the introduction of a pre-RA spilling
pass which runs prior to PHI elimination. Machine scheduler has a
significant impact on register pressure and as such is best run before
this new spilling pass.
Co-authored-by: Konstantina Mitropoulou <KonstantinaMitropoulou@amd.com>
AMDGPU reads -misched-prera-direction and -verify-misched, every
target's TTI reads -partial-unrolling-threshold through BasicTTIImpl.h,
and AsmPrinter reads -emit-bb-hash through extern declarations. Add
getters for them, move inline code that reads options (LiveIntervals,
MachinePipeliner, MIR2Vec) out of line, and let unittests use default
weights, so that the options can be file-local.
Aided by Opus 5.5
Add missing tracePick calls. Now GenericScheduler and
PostGenericScheduler tracing coverage is complete. Add a stable only1
test for pre-RA scheduling.
## Summary
- sort fixed frame-index memory operands by their explicit stack offsets
- preserve the existing frame-index ordering for ordinary stack objects
and as a tie-breaker
- add an AArch64 MIR regression with fixed objects created out of offset
order
## Background
`BaseMemOpClusterMutation` currently orders frame-index bases by
frame-index number, adjusted for the stack growth direction. Fixed frame
objects are different from ordinary stack objects: they carry explicit
offsets, and their creation order is not required to match address
order.
As a result, a target clustering hook can receive two fixed objects in
reverse address order. AArch64's `shouldClusterFI` expects the incoming
fixed-object offsets to be ordered and aborts with `Object offsets are
not ordered` in an assertions-enabled build.
When both operands refer to fixed frame objects, compare their
`MachineFrameInfo` object offsets first. The existing frame-index
comparison remains the fallback, so the ordering of ordinary stack
objects is unchanged.
Make the ordering between fixed and non-fixed frame-index bases
explicit: non-fixed bases precede fixed bases for downward-growing
stacks, while fixed bases precede non-fixed bases for upward-growing
stacks. This preserves the existing cross-category ordering without
relying on non-fixed object offsets before frame layout.
The regression deliberately creates two fixed objects in an order that
disagrees with their explicit offsets. It covers both the legacy and new
machine-scheduler pass forms.
## AI assistance
OpenAI Codex was used to assist with the investigation, patch
preparation, testing, and drafting this PR description.
Print picked SU node number inline in `tracePick` for convenience.
Otherwise its may be a bit more confusing, for example if we have 2 best
candidates with a similar reason under a single direction.
Printing node number directly as it cannot be an ExitSU (and EntrySU is
effectively unused in-tree).
Apply the `misched-only-func` and `misched-only-block` filters before
calling `startBlock`. This avoids entering a target scheduling strategy
for a filtered block without a matching `finishBlock`/`leaveMBB` call.
Add a SystemZ post-RA scheduler regression that checks a filtered block
does not contribute hazard-recognizer state.
Split from #221984 in response to review.
Despite what the documentation of `adjustLaneLiveness` states, the
method never sets dead flags on dead def operands, even when missing
dead flags can later lead to machine verifier errors.
This makes the method identify dead definitions from definitions that
are initially thought to be alive, and makes it add a dead flag on the
last definition of a virtual register, matching the behavior expected by
the machine verifier (ref. "Instruction ending live segment on dead slot
has no dead flag").
`adjustLaneLiveness` and `detectDeadDefs` now also use the same
mechanism to identify dead definitions. It relies on comparing the
defined lanes of a definition with those that stay alive after it.
When providing a non-null `AddFlagsMI` it makes no sense to pass a `Pos`
that is not `AddFlagsMI`'s own position. In such cases the position can
be queried from the MI directly, avoiding possible inconsistencies.
This splits `RegisterOperands::adjustLaneLiveness` into two overloads
whose behavior only differ in whether an MI's operand flags are updated
in the process.
To simplify testing and do not require a secondary output flag like
`-debug` or `-print-before=machine-scheduler` just to FileCheck against
function name boundaries. Motivating example:
https://github.com/llvm/llvm-project/pull/213950
WMMA instructions in gfx1250 exposes an execution window during which
only certain other instruction classes may co-execute. Teach the hazard
recognizer about those windows so the scheduler can fill co-execution
slots and account for the resulting stalls. This adds a preRA hazard
recognizer mode.
Add AMDGPUCoExecInfo.h, a shared model of a co-execution window: the
per-stage capability bitmask, the stage types (CoExecStageType), and
CoExecInfo, which maps a multi-cycle instruction to its per-cycle slot
pattern via getCoExecInfo(). InstructionFlavor and its helpers move here
from AMDGPUCoExecSchedStrategy.h with no functional change so they can
be shared by the scheduler and the hazard recognizer.
Legacy PM: setPreservesCFG() adds every pass registered as CFG-only
(dominator/post-dominator trees, loop/cycle info, block frequency,
register class info, BasicAA, ...) to the preserved set, so a separate
addPreserved<X> for such X is a no-op, as is
addPreservedID(MachineDominatorsID) / addPreservedID(MachineLoopInfoID).
New PM: preserveSet<CFGAnalyses>() keeps every result whose invalidate()
accepts the CFGAnalyses set, making an explicit preserve<X>() on the
same PreservedAnalyses redundant. SLPVectorizer, AggressiveInstCombine
and SROA keep their explicit preserves, which are load-bearing on paths
that change the CFG.
Suggested by jmmartinez in
https://github.com/llvm/llvm-project/pull/212430#discussion_r3664131067
Aided by Claude Fable 5
Remove analysis requirements whose pass never calls getAnalysis for
them, and MachineSchedContext::MDT, which no scheduler reads. Also remove
addPreserved calls subsumed by setPreservesCFG (MachineDominatorTree and
MachineLoopInfo are CFG-only analyses) and a now-unpaired INITIALIZE_PASS_DEPENDENCY.
The PowerPC, Hexagon and R600 pipelines each drop a MachineDominatorTree
construction.
Aided by Claude Opus 5
This patch adds a new CLI option to the MC layer called
`-sched-model-reservation-station-scale-factor` that enables to scale
the buffer size of all reservation stations (RS) for resources in the
scheduling model by a positive `float` factor. It is limited to scaling
OOO resources, and not special buffer sizes (-1,0,1), and similarly it
is only allowed to produce OOO resources.
This can be used for example to try find headroom in post-RA instruction
scheduling for OOO cores - e.g. scale RS size by 2 and observe IPC
gains, if so the code may be senetitive to the schedule and we may do
better.
Note: Currently, BufferSize for LSU resources defines the reservation
station (RS), but if present also the ld/st queue size, which just
points to the provided LSU resource. Thus, we currently scale them both
in lockstep, until we have an independent ld/st queue model.
The implementation adds a new method
`MCSchedule::getResourceBufferSize()` that calculates the buffer size
and exits early by default. It is wrapped on `TargetSchedule` for
CodeGen, or other users call it directly. For `ResourceState` we add a
scheduling model context to the constructor. `LSUnit` still uses
`BufferSize` directly, as it has inline logic for load/store queues
handling. So is `llvm/lib/Target/SystemZ/SystemZHazardRecognizer.cpp`
which is target specific. Testing through `llvm-mca` debug output. We
could syntesize a BB that is sensitive to the schedule and check an IPC
improvement, but it would be more compilated.
This only impacts llvm-mca at the moment. However, I think it should
logically belong to the MC layer, which owns the scheduling model
infrastructure, as the option is coupled to the model and not MCA. Thus,
this patch adds it speculatively to the MC layer, e.g. so that we can
easily observe how a RS-based scheduler performs for next-generation
larger-RS target without re-coding and re-building LLVM. Following up,
we may even move other such options to from the `llvm-mca` tool to the
MC library like dispatch width etc.
Factor out the handling of coalesced preg COPYs from SystemZMachineScheduler.cpp into MachineScheduler.cpp.
This extends the handling to other types of instructions than COPYs or immediate
loads, such as Load Address and takes care of maintaining the original input
order if both SUs are biased the same way in the same zone.
Another target that uses GenericScheduler can enable this by setting the new
MachineSchedPolicy member BiasPRegsExtra to true (default false). In a derived
scheduling strategy, this could be used either by passing /*BiasPRegsExtra=*/true
to biasPhysReg() (extra instruction detection), or by calling tryBiasPhysRegs()
instead which also preserves the original order if biased the same way.
This is a relatively simple strategy as it is omitting any heuristics for
liveness and register pressure reduction. This works well as the SystemZ ISel
scheduler is using Sched::RegPressure which gives a good input order to begin
with.
It is trying harder with biasing phys regs than GenericScheduler as it also
considers other instructions such as immediate loads directly into phys-regs
produced by the register coalescer. This can hopefully be refactored into
MachineScheduler.cpp.
It has a latency heuristic that is slightly different from the one in
GenericScheduler: It is activated for a specific type of region that have
many "data sequences" consisting of SUs connected only with a single
data-edge that are next to each other in the input order. This is only 3% of
all the scheduling regions, but when activated it is applied on all the
candidates (not just once per cycle). At the same time it is a bit more
careful by checking not only the SU Height against the scheduled latency but
also its Depth against the remaining latency.
It reuses the GenericScheduler handling of weak edges to help copy
coalescing.
It also helps with compare zero elimination as it tries to put a CC-defining
instruction that produces the compare source value above the compare before
any other instruction clobbering CC or the value.
This work was started after observing heavy spilling in Cactus, which was
actually *caused* by GenericScheduler - disabling it (no pre-RA scheduling)
remedied it and gave a 7% improvement in performance on that benchmark. Many
different versions have been tried which has evolved into this initial
simplistic MachineSchedStrategy that does relatively little and yet achieves
double-digit improvements on Cactus and Imagick compared to GenericSched
(which is OTOH 3% better on Blender). There will hopefully be more
improvements added later on as there seems to be potential for it.
It would be very interesting to have other OOO targets try this as well and
perhaps make this available in MachineScheduler.cpp
(A first attempt with improving the pre-RA scheduling was made with #90181,
which however did not materialize in anything actually useful.)
There are three calls to bumpCycle in bumpNode. Prior to the first call,
we calculate NextCycle as the next cycle in which all of a given
instruction's required hardware resources (as defined by the SchedModel)
are available. Any gap between this calculated NextCycle and CurrCycle
measures stalls that must occur before we can schedule the given
instruction.
The second and third call handle adjustments that occur during or after
issuing of the instruction (e.g. if the number of microops exceeds the
issue width).
According to the documentation of HazardRec->EmitInstruction, we should
call this method when an instruction is emitted: "This callback is
invoked when an instruction is emitted, to advance the hazard state."
In the context of bumpNode, this implies that it should be called after
we bumpCycle for stalls that must occur before issue of the
instructions, but before those that occur during or after. This PR moves
the placement to do that.
In practice, this affects schedulers that use both the SchedModel and
HazardRec. Suppose we have instructions A, B and C, and partial schedule
AB. Also, suppose instruction A exclusively holds ProcResource X for 2
cycles, and B uses ProcResource X, and there is a HazardRec hazard
between B and C which requires 1 cycle stall.
Currently, we call HazardRec->EmitInstruction on B before we call
HazardRec->AdvanceCycle for the stall between A->B. Then, when deciding
whether to schedule C, HazardRec sees that a cycle has already occurred
after B, so we do not need to stall.
After this change, we HazardRec->EmitInstruction on B after we call
HazardRec->AdvanceCycle for the stall between A->B. So, HazardRec
accurately places the stall cycle between A and B. Then, when deciding
whether to schedule C, HazardRec accurately sees that no cycles have
occurred after B, so we do need to stall for 1 cycle.
- Remove pass initialization calls from pass constructors.
- For some passes, add the initialization to `initializeCodeGen` or
`initializeGlobalISel`.
- Remove redundant initializations from llc and X86 target for some
passes.
This is needed to support functionality in the AMDGPU scheduler. Various
passes have been modified to preserve MBFI to ensure that this change
does not introduce new invocations of MBFI. Some targets have passes
reordered, but there are no new runs of MBFI.
Use it in `printVRegOrUnit()`, `getPressureSets()`/`PSetIterator`,
and in functions/classes dealing with register pressure.
Static type checking revealed several bugs, mainly in MachinePipeliner.
I'm not very familiar with this pass, so I left a bunch of FIXMEs.
There is one bug in `findUseBetween()` in RegisterPressure.cpp, also
annotated with a FIXME.
In both ScheduleDAGInstrs and MachineScheduler, we call `BufferSize = 0`
as _reserved_ and `BufferSize = 1` as _unbuffered_. This convention is
stem from the fact that we set `SUnit::hasReservedResource` to true when
any of the SUnit's consumed resources has BufferSize equal to zero; set
`SUnit::isUnbuffered` to true when any of its consumed resources has
BufferSize equal to one.
However, `SchedBoundary::isUnbufferedGroup` doesn't really follow this
convention: it returns true when the resource in question is a
`ProcResGroup` and its BufferSize equals to **zero** rather than one.
This could be really confusing for the reader. This patch renames this
function to `isReservedGroup` in aligned with the convention mentioned
above.
NFC.
It is unnecessary and confusing to have a do/while loop that checks
SU->isScheduled as this should never be true.
ScheduleDAGMI::updateQueues() is always called after pickNode() and it
sets isScheduled on the SU. Turn this into an assertion instead.
This patch updates `overrideSchedPolicy` and `overridePostRASchedPolicy`
to take a
`SchedRegion` parameter instead of just `NumRegionInstrs`. This provides
access to both the
instruction range and the parent `MachineBasicBlock`, which enables
looking up function-level
attributes.
With this change, targets can select post-RA scheduling direction per
function using a function
attribute. For example:
```cpp
void overridePostRASchedPolicy(MachineSchedPolicy &Policy,
const SchedRegion &Region) const {
const Function &F = Region.RegionBegin->getMF()->getFunction();
Attribute Attr = F.getFnAttribute("amdgpu-post-ra-direction");
...
}
The existing way of managing clustered nodes was done through adding
weak edges between the neighbouring cluster nodes, which is a sort of
ordered queue. And this will be later recorded as `NextClusterPred` or
`NextClusterSucc` in `ScheduleDAGMI`.
But actually the instruction may be picked not in the exact order of the
queue. For example, we have a queue of cluster nodes A B C. But during
scheduling, node B might be picked first, then it will be very likely
that we only cluster B and C for Top-Down scheduling (leaving A alone).
Another issue is:
```
if (!ReorderWhileClustering && SUa->NodeNum > SUb->NodeNum)
std::swap(SUa, SUb);
if (!DAG->addEdge(SUb, SDep(SUa, SDep::Cluster)))
```
may break the cluster queue.
For example, we want to cluster nodes (order as in `MemOpRecords`): 1 3
2. 1(SUa) will be pred of 3(SUb) normally. But when it comes to (3, 2),
As 3(SUa) > 2(SUb), we would reorder the two nodes, which makes 2 be
pred of 3. This makes both 1 and 2 become preds of 3, but there is no
edge between 1 and 2. Thus we get a broken cluster chain.
To fix both issues, we introduce an unordered set in the change. This
could help improve clustering in some hard case.
One key reason the change causes so many test check changes is: As the
cluster candidates are not ordered now, the candidates might be picked
in different order from before.
The most affected targets are: AMDGPU, AArch64, RISCV.
For RISCV, it seems to me most are just minor instruction reorder, don't
see obvious regression.
For AArch64, there were some combining of ldr into ldp being affected.
With two cases being regressed and two being improved. This has more
deeper reason that machine scheduler cannot cluster them well both
before and after the change, and the load combine algorithm later is
also not smart enough.
For AMDGPU, some cases have more v_dual instructions used while some are
regressed. It seems less critical. Seems like test `v_vselect_v32bf16`
gets more buffer_load being claused.
We rename `createGenericSchedLive` and `createGenericSchedPostRA`
to `createSchedLive` and `createSchedPostRA`, and add a template
parameter `Strategy` which is the generic implementation by default.
This can simplify some code for targets that have custom scheduler
strategy.
When diagnosing scheduling issues it can be useful to know which
heuristics are driving the scheduler. This adds pre-RA and post-RA
statistics for all heuristics.
When diagnosing scheduler issues it can be useful to know how scheduling
changes the order of instructions, particularly for large functions when
it's not trivial to figure out from the debug output by looking at the
scheduling unit (SU) IDs.
This adds pre-RA and post-RA statistics to track 1) the number of
instructions that remain in source order after scheduling and 2) the
total number of instructions scheduled, to compare 1) against.
This flag instructs the scheduler to stop scheduling after N
instructions, but
in the debug output it appears as if it's scheduling N+1 instructions,
e.g.
$ llc -misched-cutoff=10 -debug-only=machine-scheduler
example.ll 2>&1 | grep "^Scheduling SU" | wc -l
11
as it calls pickNode before calling checkSchedLimit.
This change removes the uint64_t constructor on LocationSize
preventing implicit conversion, and fixes up the using APIs to adapt to
the change. Note that I'm adding a couple of explicit conversion points
on routines where passing in a fixed offset as an integer seems likely
to have well understood semantics.
We had an unfortunate case which arose if you tried to pass a TypeSize
value to a parameter of LocationSize type. We'd find the implicit
conversion path through TypeSize -> uint64_t -> LocationSize which works
just fine for fixed values, but looses information and fails assertions
if the TypeSize was scalable. This change breaks the first link in that
implicit conversion chain since that seemed to be the easier one.
While we already have some detailed debug messages on the candidate
selection process -- which selects a SUnit from the Available queue, we
didn't say much about why a SUnit was _not_ moved from Pending queue to
Available queue in the first place, which is just as important as why we
scheduled a node IMHO. Therefore, I added some debug prints for this
very purpose.
I decide to print these extra messages by default (instead of being
guarded by command line like `-misched-detail-resource-booking`) because
we have been printing some of the hazard remarks, so I thought we might
as well print these new messages -- which are mostly about hazard -- by
default.
Pengcheng Wang