dotnet / dotnet/runtime

JIT (bug): superlinear compile time in "Redundant branch opts" from unbudgeted `optReachable` searches

Open
#133,983 2 comments 0 reactions 0 assignees View on GitHub
area-CodeGen-coreclr
Dominant language
C#
Stars
18.3k
Forks
5.6k
PR merge metrics
PR metrics pending

Description

`Compiler::optReachable` is a completely unbudgeted, uncached DFS over the reachable flow graph, and RBO issues two such queries per matching dominator plus two per predecessor in `optJumpThreadDom`. The phase therefore scales superlinearly in method size: a 121-byte-IL method that inlines to ~10,000 blocks spends 843 ms of its 1293 ms JIT time (65%) in RBO.

### Minimal Repro

```csharp
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;

public class P
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int H(int x, int s)
{
if (s > 3) s += x; else s -= 1;
if (s > 7) s += 2; else s -= 3;
if (s > 11) s ^= 3; else s += 5;
if (s > 13) s -= x; else s += 7;
return s;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int H1(int x, int s) => H(x, H(x, H(x, H(x, s))));
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int H2(int x, int s) => H1(x, H1(x, H1(x, H1(x, s))));
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int H3(int x, int s) => H2(x, H2(x, H2(x, H2(x, s))));
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int H4(int x, int s) => H3(x, H3(x, H3(x, H3(x, s))));

[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int L(int x, int s)
{
if (x > 100) s++;
if (x > 100) s += 2;
if (x > 100) s += 3;
if (x > 100) s += 4;
return s;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int L1(int x, int s) => L(x, L(x, L(x, L(x, s))));
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int L2(int x, int s) => L1(x, L1(x, L1(x, L1(x, s))));
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int L3(int x, int s) => L2(x, L2(x, L2(x, L2(x, s))));

[MethodImpl(MethodImplOptions.NoInlining | MethodImplOptions.AggressiveOptimization)]
static int Test(int x, int s)
{
if (x > 100)
{
return H4(x, s) + H4(x, s + 1) + H4(x, s + 2) + H4(x, s + 3) + H4(x, s + 4) + H4(x, s + 5);
}
return L3(x, s) + L3(x, s + 1) + L3(x, s + 2) + L3(x, s + 3) + L3(x, s + 4) + L3(x, s + 5);
}

public static void Main()
{
var sw = Stopwatch.StartNew();
int r = Test(5, 1);
Console.WriteLine($"{r} jit+run ms = {sw.ElapsedMilliseconds}");
}
}
```

Phase breakdown via `DOTNET_JitTimeLogFile` / `DOTNET_JitTimeLogCsv`.

### Expected

A 121-byte-IL method should not take ~1.3 s to compile, and RBO should not grow superlinearly with block count. The same method compiles in 3 ms with `DOTNET_JITMinOpts=1`.

### Actual

`21 jit+run ms = 1270` (Checked `main`). Phase report for the single `P:Test` compile:

```
Time: total: 5789.598 Mcycles/ 1293.128 ms
Redundant branch opts 1.00 3774.73 843.101 65.20% 842.561
Assertion prop 1.00 655.30 146.363 11.32% 145.898
```

Measured scaling (varying the number of top-level terms), mean of 3 runs:

| N | IL bytes | basic blocks | RBO (ms) | total JIT (ms) | RBO share |
|---|---------:|-------------:|---------:|---------------:|----------:|
| 1 | 21 | 2,475 | 66.3 | 166.5 | 39.8% |
| 2 | 41 | 5,547 | 259.4 | 494.9 | 52.4% |
| 3 | 61 | 8,619 | 583.9 | 927.6 | 62.9% |
| 4 | 81 | 10,215 | 842.4 | 1214.7 | 69.4% |

4.13x more blocks costs 12.7x more RBO time, i.e. RBO ~ `blocks^1.8`.

### Notes

Correctness is unaffected (result is always `21`); this is pure throughput, which hurts AOT/crossgen, R2R and tier-1 rejit latency. Also reproduces on released .NET 10.0.12 (Release JIT: 660 ms, RBO 62.8%), so it is long-standing, not a `main` regression. Checked-build milliseconds are pessimistic, but the shape is configuration-independent.

Root cause: `optReachableWithBudget` exists, but the only caller arming a budget is if-conversion; `optReachable` always passes `nullptr` (and asserts the budget is never exceeded). `matchLimit = 4` bounds the number of VN matches, not the O(blocks) traversal each one performs, and each query additionally pays an O(blocks) `BitVecOps::ClearD` of the whole-method bitmap. There is no memoization of `(from, to, excluded)`. Suggested fix: arm a `fgBBcount`-scaled budget for the RBO callers and treat `BudgetExceeded` as "decline to optimize" (both call sites already have conservative fallbacks); replace the per-query clear with an epoch counter.

Contributor guide

Open the contributing guide

Research direction

Start with Compiler::optReachable, optReachableWithBudget, and the Redundant branch opts callers named in the report. Reproduce the supplied C# program with DOTNET_JitTimeLogFile or DOTNET_JitTimeLogCsv, then trace the existing budget and bitmap handling. Done means preserving correctness while preventing RBO time from scaling superlinearly with block count.

Written by the indexing model from the issue text.

Assessment

Tech stack
csharp
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.