Bug 23857 – backend inliner takes too long on recursive function call

The following program takes too long to compile with `dmd -O -inline -release`: int f(int[] a, int u) { return (a[u] < 0) ? u : (a[u] = f(a, a[u])); } void main() { enum N = 10; auto a = new int[N << 1]; a[] = -1; foreach (i; 0 .. N) { f(a, i << 1); f(a, i << 1 | 1); } } Measurements: - It takes ~26 seconds on my PC (WSL2, DMD64 D Compiler v2.103.0). - Removing any of -O, -inline, and -release reduces the compilation time to <1 second. - Removing the line with "f(a, i << 1 | 1);" reduces the compilation time to ~6 seconds. Note: - The recursive function can appear naturally when implementing Union-Find data structure. - I found this issue when solving problems at https://yukicoder.me/; CentOS Stream release 8, DMD64 2.102.2.

This is a problem with the dmd's backend inliner recursively trying to inline f. `-release` is needed to remove bounds checks, otherwise it doesn't inline it. By using .ptr on a, the -release switch is not needed. Reduced a bit further: ```D int f(int[] a, int u) { return (a.ptr[u] < 0) ? u : (a.ptr[u] = f(a, a.ptr[u])); } void main() { f([], 0); f([], 0); } ```

@WalterBright created dlang/dmd pull request #15172 "fix Issue 23857 and fix Issue 23880" fixing this issue: - fix Issue 23857 and fix Issue 23880 https://github.com/dlang/dmd/pull/15172

@dkorpel created dlang/dmd pull request #15437 "Fix 23857 - backend inliner takes too long on recursive function call" fixing this issue: - Fix 23857 - backend inliner takes too long on recursive function call https://github.com/dlang/dmd/pull/15437

> It takes ~26 seconds on my PC (WSL2, DMD64 D Compiler v2.103.0). Notice "30" in this line in backend/go.d: if (!(go.changes && go.mfoptim & MFloop && (clock() - starttime) < 30 * CLOCKS_PER_SEC)) It's there to prevent infinite loop if the optimizer cannot find a stable state.

The inliner itself prevents recursive inlining by setting the Finlinenest flag. But that flag is turned off when scanForInlines() returns. And then the optimizer calls scanForInlines() again, it inlines again, opening up more opportunities for other optimizations, and then the optimizer calls it again. The easy way to fix this is to only call scanForInlines() once per function.

@WalterBright created dlang/dmd pull request #15447 "fix Issue 23857 - backend inliner takes too long on recursive functio…" fixing this issue: - fix Issue 23857 - backend inliner takes too long on recursive function call https://github.com/dlang/dmd/pull/15447

dlang/dmd pull request #15447 "fix Issue 23857 - backend inliner takes too long on recursive functio…" was merged into stable: - cead34eb03273dd4b9a00856a08a598f93b86fdb by Walter Bright: fix Issue 23857 - backend inliner takes too long on recursive function call https://github.com/dlang/dmd/pull/15447

dlang/dmd pull request #15492 "merge stable" was merged into master: - f8cd3f44ef8c86e3f56318896e8d2eb765db72c4 by Walter Bright: fix Issue 23857 - backend inliner takes too long on recursive function call (#15447) https://github.com/dlang/dmd/pull/15492