llvm / llvm/llvm-project

[llvm-mca] Non-termination when a write consumes several partially overlapping ProcResGroups

Open
#224,248 1 comment 0 reactions 0 assignees View on GitHub
hang tools:llvm-mca
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

`llvm-mca` does not terminate on a single instruction, on an otherwise empty machine, when that instruction's `SchedWriteRes` consumes several partially overlapping `ProcResGroup`s — groups that share units where none contains the other.

The instruction never becomes issuable, so the pipeline never drains and `Pipeline::run()` keeps advancing cycles forever. It is not a crash and not a tight spin: `llvm-mca` sits at 100% CPU indefinitely and produces no output.

A valid assignment of units to groups exists in the failing case, and `llc` finds one — the machine scheduler handles the same model and emits identical assembly. The failure is specific to the llvm-mca resource manager.

## Reproducer

This needs no new resource groups. `X86ScheduleZnver4.td` already defines these four over the same four `Zn4FPFMisc` units:

```
def Zn4FPFMisc0123 : ProcResGroup<[Zn4FPFMisc0, Zn4FPFMisc1, Zn4FPFMisc2, Zn4FPFMisc3]>;
def Zn4FPFMisc01 : ProcResGroup<[Zn4FPFMisc0, Zn4FPFMisc1]>;
def Zn4FPFMisc12 : ProcResGroup<[Zn4FPFMisc1, Zn4FPFMisc2]>;
def Zn4FPFMisc23 : ProcResGroup<[Zn4FPFMisc2, Zn4FPFMisc3]>;
def Zn4FPFMisc123 : ProcResGroup<[Zn4FPFMisc1,Zn4FPFMisc2, Zn4FPFMisc3]>;
```

Add one write that uses four of them, one cycle each, and bind it to any instruction:

```diff
def Zn4FPFMisc123 : ProcResGroup<[Zn4FPFMisc1,Zn4FPFMisc2, Zn4FPFMisc3]>;
+
+def Zn4WriteMCALivelock : SchedWriteRes<[Zn4FPFMisc01, Zn4FPFMisc12,
+ Zn4FPFMisc123, Zn4FPFMisc23]> {
+ let Latency = 10;
+ let ReleaseAtCycles = [1, 1, 1, 1];
+ let NumMicroOps = 22;
+}
+def : InstRW<[Zn4WriteMCALivelock], (instrs VPADDBrr)>;
```

Then:

```
$ cat repro.s
vpaddb %xmm0, %xmm1, %xmm2

$ llvm-mca -mtriple=x86_64-unknown-unknown -mcpu=znver4 -iterations=1 repro.s

```

Interrupting it gives:

```
Program received signal SIGINT, Interrupt.
#0 llvm::mca::RetireStage::cycleEnd ()
#1 llvm::mca::Pipeline::runCycle ()
#2 llvm::mca::Pipeline::run ()
#3 runPipeline(llvm::mca::Pipeline&)
#4 main
```

A satisfying assignment exists, so this is a false rejection rather than a genuinely unschedulable write:

| group | units | assign |
| --- | --- | --- |
| `Zn4FPFMisc01` | M0, M1 | M0 |
| `Zn4FPFMisc12` | M1, M2 | M1 |
| `Zn4FPFMisc123` | M1, M2, M3 | M3 |
| `Zn4FPFMisc23` | M2, M3 | M2 |

Dropping any one of the four groups makes it terminate, so three overlapping groups are not enough to trigger it.

## Diagnosis

An instruction using partially overlapping groups is flagged `HasPartiallyOverlappingGroups` in `InstrBuilder.cpp`, which sends `ResourceManager::checkAvailability` down a second pass that verifies at least one unit can be selected per group:

```cpp
// llvm/lib/MCA/HardwareUnits/ResourceManager.cpp
// If this instruction has overlapping groups, make sure that we can
// select at least one unit per group.
for (const std::pair &E : Desc.Resources) {
const ResourceState &RS = *Resources[getResourceStateIndex(E.first)];
if (!E.second.isReserved() && RS.isAResourceGroup()) {
uint64_t ReadyMask = RS.getReadyMask() & ~ConsumedResourceMask;
...
uint64_t ResourceMask = llvm::bit_floor(ReadyMask);
```

That pass is a single greedy sweep with no backtracking: for each group it takes the highest-numbered ready unit via `bit_floor`, decrements that unit's count, and marks it consumed at zero.

Deciding whether every group can be given a distinct unit simultaneously is a bipartite matching problem, and one greedy pass does not solve it. An earlier group can take the only unit still available to a later group even when a different assignment would have satisfied both. `checkAvailability` then reports a busy resource on a completely idle machine, the instruction is never issued, and the simulation never makes progress.

## Expected behaviour

`llvm-mca` should either simulate the instruction — a valid assignment exists, and `llc` finds one — or fail with a diagnostic. It should not run forever.

Replacing the greedy sweep with a real matching (augmenting paths, or a Hall-condition check across the groups the instruction uses) would fix it. Failing that, bounding the number of cycles with no retirement would at least turn the hang into an error rather than an unbounded run.

## Impact

This makes accurate port-eligibility modelling unrepresentable for Zen 4 gather/scatter. uops.info reports `VGATHERDPS (ZMM, K, VSIB_ZMM)` on Zen 4 as `1*FP01+8*FP0123+3*FP12+8*FP123+2*FP23+18*FP45`, but writing that `FP12` term down alongside the `FP01` one makes `llvm-mca` hang. #212997 therefore has to widen those micro-ops into `FP1-3`, modelling an eligibility the hardware does not have.

That workaround leaves every modelled throughput unchanged, and `llc` emits byte-identical assembly with and without it, under default scheduling and under `-enable-post-misched -misched=converge`. But it stands in place of a measurement, and it can only be removed once llvm-mca can allocate these groups.

Contributor guide

Open the contributing guide

Research direction

Start in llvm/lib/MCA/HardwareUnits/ResourceManager.cpp at ResourceManager::checkAvailability and compare the HasPartiallyOverlappingGroups path identified in InstrBuilder.cpp. Run the supplied llvm-mca znver4 repro, then add regression coverage showing that the instruction terminates with a valid assignment or a diagnostic rather than looping indefinitely.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers, tooling
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
58/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.