[RFC] Reducing process creation overhead in LLVM regression tests

On Windows, process creation incurs a significant overhead, especially when antivirus software is installed. I estimate the overhead per process on my work PC to be around 0.027 seconds, and Lit spawned 246200 processes during check-llvm, i.e. around 10 minutes of CPU time spent just creating and destroying processes. This RFC demonstrates that we can reduce the time taken by check-llvm by at least 20% on Windows by merging processes.

Inspired by @rgal’s observation that process creation is a significant overhead for Lit tests, I have been trying some ideas to reduce the number of process invocations during check-llvm, to hopefully reduce testing times and CI workload (examining the CI logs on GitHub, running the regression tests on Windows seems to take about 8 minutes - example from a random pull request I found). The main approach I have explored is introducing new frontends for opt/llc that operate on multiple modules in one process, and mechanically “merging” a group of tests just before testing by replacing them with one test that invokes the new multi-module tool.

I drafted a very rough prototype of this idea here and the results are promising, with a reduction in testing runtime on my Windows PC from 950 to 775 seconds, or 236 to 61 seconds if only tests identified as mergeable are considered. Surprisingly, a noticeable difference on Linux (WSL) was also observed, though not as dramatic as the one observed on Windows.

Prototype implementation

Merged tests consist of a single run directive invoking the multi-module version of the tool (these are optmany and llcmany in my proof-of-concept and reside in the llvm/tools directory), the result of which is piped into FileCheck with the test file as the check file as usual. Following this are a series of INPUT_FILE directives specifying the paths to the original test modules, which are interpreted by the multi-module tool. Finally, the FileCheck directives from the original tests are extracted and appended to the merged tests, interspersed by checks for special boundary labels outputted by the multi-module tool.

An example of a merged test is as follows:

RUN: optmany -o - -hide-filename < %s -O2 -S | FileCheck %s
INPUT_FILE: llvm\test\Transforms\InstCombine\no-unwind-inline-asm.ll
INPUT_FILE: llvm\test\Transforms\InstCombine\unwind-inline-asm.ll
CHECK: TEST_BEGIN
CHECK-LABEL: INPUT_FILE llvm\test\Transforms\InstCombine\no-unwind-inline-asm.ll
CHECK: define dso_local void @test()
CHECK-NEXT: entry:
CHECK-NEXT: tail call void asm sideeffect
CHECK-NEXT: ret void
CHECK: TEST_END
CHECK: TEST_BEGIN
CHECK-LABEL: INPUT_FILE llvm\test\Transforms\InstCombine\unwind-inline-asm.ll
CHECK: define dso_local void @test()
CHECK-NEXT: entry:
CHECK-NEXT: invoke void asm sideeffect unwind
CHECK: %0 = landingpad { ptr, i32 }
CHECK: resume { ptr, i32 } %0
CHECK: TEST_END

These are created and run by a Python program called test_consolidator in llvm/utils. To try it, first update the information in test_consolidator.json in the project root and then invoke test_consolidator/main.py from the LLVM clone directory and, once it’s set up and prompts for a command, run all-merged to run all regression tests with as many merged as possible - note that some TableGen tests fail when ran this way; this is because they rely on relative paths but the prototype implementation copies all tests to a temporary directory.

As for deciding which tests can be merged, the prototype implementation just sees tests with the exact same run directive (tests with multiple run directives are treated as multiple tests with one each) and the same REQUIRES/UNSUPPORTED directives and lit.local.cfg as mergeable. This results in 17832 regression tests (42% of all .ll tests) being identified as mergeable; these are converted into 5272 merged tests, reducing the total number of processes invoked from 248091 to 197581.

I also experimented with parallelising optmany but this did not result in a meaningful speed improvement during actual test runs, as Lit is already running tests in parallel.

Prototype limitations

Swathes of code are copied from llc.cpp and optdriver.cpp into llcmany and optmany. This doesn’t just violate the DRY principle but also has the major flaw that changes made to this code will not be tested by the merged tests. If this idea is to be viable then this code must be extracted into library functions (e.g. optInit and optProcessModule) which are called by opt and optmany (this follows the iniative already started by the extraction of optMain to a static library). This refactoring would be the main cost of implementing this solution.

The prototype test consolidator is quite slow to create the merged tests, taking 20 seconds to identify mergeable tests and 1 minute 50 seconds to create the merged tests on my PC. It is written in Python and relies on lots of regexes for parsing out FileCheck directives reliably(ish) and more - I am quite new to writing regexes so this is definitely a major area for optimisation. It should be possible to make this process very fast, so that it can be run just before testing. Also, it is certain that you can invent a Lit test which confuses it (I only made sure all mergeable tests that are normally invoked by check-llvm still pass after merging).

Another issue is that when a merged test fails, it requires some work to work out which test it was. A potential solution could be automatically re-running the individual tests from the merged tests that were reported as failures - this could be implemented by parsing Lit’s output or by integrating with Lit.

Other approaches

A few other approaches I considered are:

  1. Mechanically merging as many opt/llc tests as possible by concatenating them into one module before testing.
    • I decided that this approach, while the least invasive (it would only require the introduction of one “merge tests” script that is ran before testing), would be too fragile as merging modules would invalidate the existing FileCheck directives, especially if identifiers, metadata IDs, etc. have to be uniquified.
  2. Compiling the tools to be tested as shared libraries and invoking them within the Lit process.
    • This is the most powerful approach in that it could theoretically eliminate the process creation overhead entirely, and is also the most resilient to being upset by unusually structured Lit tests. However, it poses the extremely invasive restriction on all the tools for which the idea is applied that the main function must be idempotent and should never call exit or similar, as this would exit from the Lit worker itself - unless some hackery is done like linking with a fake exit function, but this is too evil.

Is reducing process invocations to speed up regression testing a useful pursuit? Do you think the trade-off of maintenance and increased testing complexity and fragility is worth it for the potential reduction in testing times? Does anyone have other ideas to achieve the same goal in a better way?

CC @jmorse

8 Likes

I do think that the general direction here is worth pursuing – this is most problematic on Windows, but increased process startup overhead is also one of the big downsides of enabling LLVM_LINK_LLVM_DYLIB builds on Linux, because dynamic relocations add significant overhead to short-running test processes.

However, I’m not really a fan of the specific approach you are using. This kind of pre- and post-processing of tests looks very fragile to me.

The broad alternative I’d consider is to support a daemonized running mode for tools like opt, and corresponding support in lit to send certain “commands” to the corresponding daemon instead, keeping a pool of such processes live. This should be mostly transparent from the perspective of the test.

10 Likes

Also want to point out both merging and daemon approach also needs to work great when tests are failing, especially the tool just crashes. It needs to ping point exactly which tests are failing, hopefully without re-executing (since it can be non-deterministic).

I guess another competing idea will be just going fully distributable so you can run it as wide as possible. Usually one lit test has a very small dependency, and you can distribute that very well, but we don’t encode fine-grain dependencies in CMake to allow that.

2 Likes

I agree with Nikita that adding new binaries that can support running multiple files at the same time and using lit to merge the test lines isn’t the best option. The patch you have looks like it duplicates a bunch of code and will end up having a pretty high maintenance overhead.

However, I do think this work is quite valuable. I have recently spent a bunch of time working on eliminating process start overhead for testing across the monorepo by working towards enabling lit’s internal shell by default on Linux. That eliminates bash invocations and has resulted in a 10-15% speedup in a couple of the big test suites. We’ve been focusing on this primarily for premerge. Most of the time spent running premerge is spent running lit tests, and we’re trying to drive down test latency that way. We’ve mostly been focused on the low hanging fruit (like finishing up the enablement of the internal shell), but the next step on that front would probably be some sort of daemon mode.

There is prior art for a daemon mode in LLVM ( ⚙ D86351 WIP: llvm-buildozer and https://www.youtube.com/watch?v=usPL_DROn4k). I don’t think anyone has made it work specifically for testing, but I would certainly be interested in seeing it. If someone ends up putting in the work to do this, it would also be great if in addition to the LLVM tools, we could also get it working with clang. That would probably have similar impact on the clang test suite and might have some impact on other test suites like libc++. However, the libc++ test suite doesn’t spend much time in process startup compared to the other test suites last I checked (and disabling PIE doesn’t have a large impact on the test suite time). I think a daemon mode would have appropriate maintenance/test speedup tradeoffs, assuming the work is done to make sure it reports crashes correctly.

1 Like

Based purely on what you’ve described, my biggest concern would be that merging processes would not mean these processes would then share memory, rather than each one having a completely clean state to work with, which could theoretically mean tests pass when merged, but fail when separate (or indeed vice versa). I acknowledge that this class of bugs is likely to be rare. Perhaps it would be sufficient to make this configurable at cmake time, with developers having it enabled and build bots having it disabled or similar.

1 Like

FWIW, Carbon uses a single process to run tests ( carbon-lang/testing/file_test at trunk · carbon-language/carbon-lang · GitHub carbon-lang/toolchain/testing/file_test.cpp at trunk · carbon-language/carbon-lang · GitHub ) that might be worth some inspiration. Combined with an LLVM busybox perhaps it could work for most of LLVM’s test suite - though the current implementation’s probably closer to clang, so maybe trying it with in-process clang might be an easier prototype/increment.

5 Likes

Thanks everyone for the kind and constructive feedback. I agree the test merging approach isn’t ideal. I’m currently prototyping the daemon-based approach.

Thanks for looking into this, it’s something I’ve talked about often over lunch, but I have no action to show for it.

There is further prior art here to look at in the Chromium test launcher (2013 announcement, implementation). One of the innovations here was to re-run failing tests in isolation at the end of the test run to distinguish between failures caused by state carried over from prior test execution, vs true positive failures of the test when run by itself.

With a more centrally-controlled corporate project like Chromium, you can imagine that there is some dedicated cleanup crew that pulls data on test re-runs and tries to continuously keep them under control.

4 Likes

Hi everyone, I’ve been experimenting with a prototype for the daemonized test running idea which can be found here.

So far, I’ve just been applying the idea to opt and FileCheck and comparing performance in the llvm/Transforms folder. Lit collects the stdout and stderr from the daemon, as well as the return code, and displays them as normal. If the daemon exits unexpectedly during a test, Lit takes the exit code as the exit code for the test and restarts the daemon, so crashing is taken care of. To try the daemonized testing, invoke Lit with --use-daemon-tools.

On Windows, running all the llvm/Transforms tests with regular Lit takes 137 seconds on my PC. With my prototype for running opt and FileCheck as daemons, it takes just 32 seconds, although 0.97% of tests in the Transforms directory fail incorrectly.

The biggest problem for the approach is static state in LLVM. Static variables are not reset between daemon tasks, so any static variable that may affect the output can break tests - for example, NumDevirtCalls in WholeProgramDevirt.cpp wasn’t being reset between runs, causing the Transforms/WholeProgramDevirt/import.ll test to fail unexpectedly - I think the causes for the remaining failures are similar. The daemonization approach could only be applied universally if all state which is shared between modules and may change the output is removed and forbidden. Another idea I had is, for tests that fail when run using the daemon, to try re-running them without it - this would cover cases where the daemonization causes incorrect failures, but doesn’t solve the issue pointed out by jh7370 that shared state could cause tests to pass incorrectly.

The daemonization is transparent from the perspective of the Lit test, although it may be sensible to make a way for a test to opt out of running tools in daemon mode in case the test relies on state that can’t be properly reset, or even to make it opt-in on a per-invocation basis (e.g. RUN: %opt_daemon rather than RUN: opt).

5 Likes

An almost 80% decrease in test times is quite nice! Trying to figure out what to do with the command line options is probably one of the biggest obstacles to landing this. It would be really nice to fix this for good and scope cl::opt values to a LLVMContext or similar. That would be a really nice improvement in general. It would also open up the possibility of doing daemon mode in threads instead of processes, but I think there would be some problems with that around handling crashes and I/O. I’m not sure if anyone has done a design of how that would look though.

I’m wondering if for prototyping purposes, it would be possible to hack up cl:: so that you can reset the command line options that are set to their default values. I don’t think that would be difficult to implement and it would allow for getting full results (eg running the entirety of check-llvm and similar). I would even be fine landing this with that approach, assuming there aren’t other issues with global state, and we have a plan to do the proper thing in the future, ideally with resourcing to finish it.

3 Likes

Is cl::opt really the issue here? As long as we’re using multiple processes and not threads, we should already have the facilities to parse command line options multiple times (see ResetAllOptionOccurrences etc).

The example @BStott mentioned is global state in WPD which does not use any of our standard facilities: llvm-project/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp at 8462cff40daf40e58d705f5d86d4e91ef6e6294c · llvm/llvm-project · GitHub This is a plain bug in the pass, and should be fixed. Passes should never use global state in this matter.

For this particular case, WholeProgramDevirtCutoff should probably be replaced with a DebugCounter, as the option exists only for debugging.

3 Likes

When I was looking through the API documentation I did not see ResetAllOptionOccurrences. This was never a major blocker, but that makes it pretty trivial.

I misunderstood what the actual problem was (probably should have actually looked at the code..). Thanks for pointing that out.

1 Like

I’ve posted [WPD] Change Devirt Cutoff to use DebugCounter by boomanaiden154 · Pull Request #170009 · llvm/llvm-project · GitHub to fix the issue in WPD.

1 Like

As the author of original WPD change, I’m obliged to mention that debug counters requires -DLLVM_ENABLE_ASSERTIONS=ON but a release compiler typically don’t enable this. And technically using a debug counter isn’t a drop-in replacement; it requires users to seek for work arounds and takes additional work, especially for large real-world programs where debug assertions might fail the compilation at irrelevant places (which is observed and not very uncommon).

That said, I’m onboard with the direction to reduce process creating overhead in regression tests, so approved [WPD] Change Devirt Cutoff to use DebugCounter by boomanaiden154 · Pull Request #170009 · llvm/llvm-project · GitHub to not block this effort.

I haven’t looked into the details of the prototype PR linked in the RFC and might missed something pretty obvious, but how this work handles debug counter when multiple modules repeatedly uses the same debug counter? Would the same per-process global counter caveat apply?

I don’t think the API for it exists right now, but debug counters provide a unified mechanism which can be globally reset, similar to what is possible with cl::opt and LLVM statistic counters.

1 Like

While I’m very interested in improving test time, I’m generically nervous about the idea of not re-executing the primary utilities-under-tests.

One question that occurs to me is whether we could either daemonize, or simply integrate into some part of the test runner, things like not or even FileCheck itself, which would reduce process spawns with almost not loss of test coverage.

1 Like

For some tests this is probably true in that we really are trying to test the tools themselves. But for the vast majority of the tests I would argue we’re not actually trying to test the tools as tools, we’re just using the tools as a means to test specific parts of their behaviour. For example, everything in llvm/test/CodeGen doesn’t actually care one bit about llc, llc is just a low-level frontend. What it cares about is what assembly gets produced for a given IR input for a given target configuration, and llc is just the means to perform that. Especially given that llc itself isn’t even involved in a normal compilation process, normally we’re using the IR-to-assembly pipeline constructed by Clang itself (or another language frontend), so if testing the tools themselves were important then we’d invest in a bunch of tests for producing assembly via Clang. However, for something like llvm-objdump, we really are testing the end-to-end functionality of the tool as used in the real world. Or at least for the llvm-objdump tests themselves; contrast with all the tests, e.g. in lld/test, that use llvm-objdump as a means to evaluate the result rather than testing the tool itself.

Also, what is the concern for things going wrong? If there’s leakage due to a lack of resetting/reinitialisation from one test to the next, that’s likely to show up in the form of non-determinism when running the tests, due to changes in test scheduling, especially once you factor in running with different amounts of parallelism across a variety of machines. Famous last words, but I’d expect it to be quite hard to have a bug in this area that consistently doesn’t show up across all buildbots, let alone end developers’ machines. As for deterministic errors like “this option no longer works”, if we have test coverage for it then that’ll show up as the test consistently failing the moment this approach gets used, so it’ll be found, and if we don’t have test coverage for it then whether we use this approach or not makes no difference to the behaviour of any test so it doesn’t matter (and if someone starts to write a test that depends on it then they should find that the test doesn’t give what they expect, so hunt down why and fix it).

2 Likes

Assuming we’re going to still to do single-thread per process execution of tests… then I’d suggest that failures (especially those that only reproduce in this multi-invocation-in-a-single-process mode, if we’re going to do the work to run them in isolation on failure to differentiate the failure mode) should print a command that reproduces the entire execution - the specific set of tests and order that the failed in.

(based on past experience - had a test framework that did just this, parallel execution, but in separate processes (though without the test reordering that LLVM tests do (where they’re run longest-to-shortest, the framework I was in always ran tests in command line/source order) which probably produces more interesting cases), each process being single threaded - and certain orderings would produce failures where others wouldn’t - I added logging to list which tests were ran in each process and was only then able to stably reproduce the problem, isolate and fix it - I can still remember that bug 15+ years later because it was frustrating but really interesting to isolate and solve… )

1 Like

This would be good to have regardless of whether or not we daemonize tests. I don’t think it would be hard or expensive to add per-worker logging to lit, and would help debug issues that are already occurring today, although mostly within lit itself (e.g., [lit] Ensure ulimit does not persist across tests by boomanaiden154 · Pull Request #164485 · llvm/llvm-project · GitHub).

1 Like

Hi everyone,

After the holidays I’ll have some time to focus on landing this, so I think it would be good to consolidate the final design first. There are a few implementation details I would appreciate feedback on.

The work to land this consists of:

  • Adding the “daemon mode” functionality to the LLVM tools being tested.
  • Adding support for the daemonized tools in Lit.
  • Incrementally updating existing tests to use the new daemonized tools.
  • Incrementally reducing cases of static state in LLVM that break the daemonized testing approach.

Lit

It seems that Lit’s core is supposed to be detached from LLVM itself, with LLVM-specific functionality (for example command substitutions) added by the local configuration. It seems like embedding support for the specific way that the LLVM daemonized tools end up working within Lit would contradict this goal. I propose introducing a SpecialCommand abstract class in Lit, representing any command that isn’t an executable invocation, and updating _executeShCmd to support these commands, including within command chains. These shall be provided through the Lit configuration. Additionally, the existing in-process commands in Lit can be refactored to use this system, meaning that they will also be able to be used in command chains. I implemented the daemon tools in Lit in a similar fashion in the prototype implementation, although the daemon tools are hardcoded in TestRunner.py.

For chained process invocations, Lit starts all the processes at the same time, so the startup overhead of the second process in a chain can be overshadowed (thus alleviated) by the processing time of the first. For simplicity, in the prototype implementation I decided the special commands would be run synchronously and act as barriers between the regular commands. Lit waits for the last “real” command to finish to collect its output and then runs the special command, before providing its output to the next command. Do you think it would be worth trying to support this asynchronous behaviour for special commands too, i.e. allowing to start up the next command before the daemonized one finishes? I think it would introduce a lot of complexity.

As running the special commands is a feature of Lit’s internal shell, the daemon testing will only be usable when Lit’s internal shell is enabled.

In the prototype, I had Lit replace all invocations of opt and FileCheck with daemon invocations. For landing this, I think it would be better to have the daemonization be opt-in for each test, by providing a separate command (e.g. “%daemon-opt” that Lit tests which work with daemonization can call). This way, the removal of persistent state that breaks the daemon testing idea can be incremental, and tests can be updated to use the daemon proceses gradually. I agree with @jrtc27 that tests intended to test user-facing tools end-to-end should still invoke the tool as a separate process. What do you think?

Daemon interface/IPC

Handling stdin/stdout/stderr for the daemonized processes, as well as collecting the return code, is tricky. In the prototype, I used the following interface:

  • Input:
    • If Lit wants to provide a file to use as stdin, it sends “in.file {path}” to the daemon via stdin. This is used when the standard input of the command is a file.
    • If Lit wants to provide a string directly as input to the daemon, it sends "in.bytes {len} {bytes}" to the daemon’s stdin. This is used when the standard input of the command is the output of the last, to avoid having to write it to a temporary file.
      • As an exception, if the output of the last command is binary rather than text, it is sent via a file, as I couldn’t find a cross-platform way to pass binary data to a subprocess from the Python side.
  • Output/error:
    • The daemon tool’s output is sent via stdout as normal, followed by a special message to indicate that the daemon is finished - this also communicates the return code. Likewise, the error log is sent via stderr. Lit sits collecting the stdout and stderr from the daemon until it receives the “Task finished” message.
  • Program arguments:
    • Once the input is specified, the daemon is sent a "run {args}" command. The arguments are split up and passed as argc and argv.
  • Crash handling:
    • If the daemon tool exits unexpectedly, its return code is taken as the return code for the command.

The way input was handled in the prototype was especially complicated. The reason I didn’t just have the input to the daemon tool be the daemon’s stdin is that LLVM’s input file reading waits until the input stream is closed, and the daemon’s stdin never closes, leading to a deadlock. One solution would be to change LLVM’s input file reading to stop when it finds a End-of-Transmission character (character code 4, a.k.a. ^D) - this way, the standard input for the tool could be sent directly through the stdin pipe of the daemon, without requiring the complicated solution used in the prototype. However this would only be viable for text files, as binary files may contain ^D characters that aren’t meant to signal EOT. Do you think this change would be a good idea?

LLVM tools

We want a way to run the LLVM tools (FileCheck, opt, llc, clang, etc) in “daemon mode” with as little code repetition as possible. Each tool has initialization that should be performed once (InitLLVM, initializing passes, etc.), as well as the code to run the tool with a given set of arguments and input, which will be called many times by the daemon.

In the prototype, I decided to integrate the daemon running functionality into the normal versions of the tools, for example opt is started as a daemon by running opt --daemon. The majority of main is extracted into a run function which is called repeatedly by a shared runDaemonMode function implementing the daemon interface. The advantages of this approach are that no code has to be repeated and no changes to the build system are made - however, it may be undesirable for this functionality to be built into the tools themselves.

Another idea would be to change the core implementation of each tool to be a static library exposing a function to initialize the tool (called once) and one to invoke it with a given set of arguments (called once per daemon invocation). Both the regular version of the tool and the daemon version will call into this library.

Which of these approaches do you find preferable? Does anyone know of a better way to structure this?

Thanks for all the discussion and feedback so far.