Compilation fails with backend ran out of registers

[rlyerly]

For some benchmarks, inserting stackmaps into the code causes the following error message:

fatal error: error in backend: ran out of registers during register allocation
clang-3.7: error: clang frontend command failed with exit code 70 (use -v to see invocation)
clang version 3.7.1 (tags/RELEASE_371/final 320332)
Target: x86_64-unknown-linux-gnu
Thread model: posix
clang-3.7: note: diagnostic msg: PLEASE submit a bug report to http://llvm.org/bugs/ and include the crash backtrace, preprocessed source, and associated run script.
clang-3.7: note: diagnostic msg:

---

PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT:
Preprocessed source(s) and associated run script(s) are located at:
clang-3.7: note: diagnostic msg: /tmp/adapt-89f13a.c
clang-3.7: note: diagnostic msg: /tmp/adapt-89f13a.sh
clang-3.7: note: diagnostic msg:

---

This is caused by the backend pathologically rematerializing lots of values before a stackmap (in InlineSpiller::reMaterializeAll()). Rematerialized values cannot be spilled (to prevent infinite loops in the register allocator), but these values fill up all available registers, especially on x86. This eventually causes the register allocator to choke in the select or split implementation, e.g., RAGreedy::selectOrSplitImpl().

One solution would be to prevent rematerializing values before stackmaps and instead forcing them to be spilled to the stack. Spilled values will fold into the stackmap, cleanly preventing usage of physical registers (which really aren't using the values but are simply recording their location). However, this causes the creation of a large number of new spill slots which are not currently handled in the StackTransformMetadata pass.

The attached files reproduce this behavior.

adapt.tar.gz

[rlyerly]

More background

The rematerializing code is built to cheaply reproduce a small number of values for a single instruction. Since almost all machine instructions only use a handful of values, reproducing this small set of values right before the instruction doesn't normally cause issues. The rematerialization code creates small live ranges containing the remat instruction and its use, and prevents if from being evicted or spilled again.

The stackmap intrinsic violates the assumption of a few small values and can have a large number of live values that are rematerialized just for inclusion in the stackmap. This depletes the pool of available registers, causing this error. Note that this issue isn't encountered for call instructions which take a large number of values -- they are custom lowered so that all argument registers are filled and any remaining arguments are spilled to the stack appropriately.

See [1] for more information.

Quick and dirty workaround

The root cause of this issue is a large number of live values across stackmaps. Optimizations exacerbate this problem (as they often trade time for space or increased code size); in particular, inlining seems to cause this in some instances. Compiling with -fno-inline may work around the issue. If not, turning the optimization level to -O0 may also eliminate the issue.

[1] "LLVM Register Allocation" https://www.slideshare.net/chimerawang/llvm-register-allocation-59885569