This was excluded by mistake in #1; without a configuration, cargo-deny
runs with a default one, and rejects a lot of things (largely due to
open-source-but-not-allowlisted licenses).
This `deny.toml` comes from the regalloc.rs repo. It results in one
warning currently that will be resolved once #7 is.
From feedback from @julian-seward1. I had used "list" in a more generic
sense, meaning ordered sequence of elements, while in a Rust context it
can sometimes be confused with "linked list" specifically. These
alternative terms are more precise.
In wasmtime's `gc::many_live_refs` unit-test, approximately ~1K vregs
are live over ~1K safepoints (actually, each vreg is live over half the
safepoints on average, in a LIFO sort of arrangement).
This causes a huge slowdown with the current heuristics. Basically, each
vreg had a `Conflict` requirement because it had both stack uses
(safepoints) and register uses (the actual def and normal use). The
action in this case when processing the vreg's bundle is to split off
the first use -- a conservative-but-correct approach that will always
eventually split bundles far enough to get non-conflicting-requirement
pieces.
However, because each vreg had N stack uses followed by one register
use, this meant that each had to be split N times (!) -- so we had
O(n^2) splits and O(n^2) bundles by the end of the allocation.
This instead implements another simple heuristic that is much better:
when the requirements are conflicting, scan forward and find the exact
point at which the requirements become conflicting, such that the prefix
(first half prior to the split) still has no conflict, and split there.
This turns the above test-case into an O(n)-bundle / O(n)-split
situation.
This feature needs more thought; for now we will of course continue to
support pinned vregs, but perhaps we can do better for
"pass-through-and-forget" operands that are given non-allocatable
registers.
This reverts commit 736f636c36.
