JIT: (bug) exponential compile time and arena growth in `optAssertionVNIsSubtype` PHI walk
- Dominant language
- C#
- Stars
- 18.3k
- Forks
- 5.6k
- PR merge metrics
- PR metrics pending
Description
A 34-line method with a single type test takes ~5 s (Release JIT) / ~17 s (Checked JIT) to compile and grows the peak working set to ~600 MB. .NET 10 compiles the same method in ~0 ms / 25 MB, so this is a `main`-only regression.
### Minimal Repro
```csharp
using System;
using System.Diagnostics;
using System.Runtime.CompilerServices;
class A { public int X; }
public class Program
{
[MethodImpl(MethodImplOptions.NoInlining | MethodImplOptions.AggressiveOptimization)]
static int Test(int x)
{
object o = new A();
int acc = 0;
switch ((x >> 0) & 7) { case 0: o = new A(); break; case 1: acc += 1; break; case 2: acc += 2; break; case 3: acc += 3; break; case 4: acc += 4; break; case 5: acc += 5; break; case 6: acc += 6; break; case 7: acc += 7; break; }
switch ((x >> 3) & 7) { case 0: o = new A(); break; case 1: acc += 2; break; case 2: acc += 3; break; case 3: acc += 4; break; case 4: acc += 5; break; case 5: acc += 6; break; case 6: acc += 7; break; case 7: acc += 8; break; }
switch ((x >> 6) & 7) { case 0: o = new A(); break; case 1: acc += 3; break; case 2: acc += 4; break; case 3: acc += 5; break; case 4: acc += 6; break; case 5: acc += 7; break; case 6: acc += 8; break; case 7: acc += 9; break; }
switch ((x >> 9) & 7) { case 0: o = new A(); break; case 1: acc += 4; break; case 2: acc += 5; break; case 3: acc += 6; break; case 4: acc += 7; break; case 5: acc += 8; break; case 6: acc += 9; break; case 7: acc += 10; break; }
switch ((x >> 12) & 7) { case 0: o = new A(); break; case 1: acc += 5; break; case 2: acc += 6; break; case 3: acc += 7; break; case 4: acc += 8; break; case 5: acc += 9; break; case 6: acc += 10; break; case 7: acc += 11; break; }
switch ((x >> 15) & 7) { case 0: o = new A(); break; case 1: acc += 6; break; case 2: acc += 7; break; case 3: acc += 8; break; case 4: acc += 9; break; case 5: acc += 10; break; case 6: acc += 11; break; case 7: acc += 12; break; }
switch ((x >> 18) & 7) { case 0: o = new A(); break; case 1: acc += 7; break; case 2: acc += 8; break; case 3: acc += 9; break; case 4: acc += 10; break; case 5: acc += 11; break; case 6: acc += 12; break; case 7: acc += 13; break; }
switch ((x >> 21) & 7) { case 0: o = new A(); break; case 1: acc += 8; break; case 2: acc += 9; break; case 3: acc += 10; break; case 4: acc += 11; break; case 5: acc += 12; break; case 6: acc += 13; break; case 7: acc += 14; break; }
switch ((x >> 24) & 7) { case 0: o = new A(); break; case 1: acc += 9; break; case 2: acc += 10; break; case 3: acc += 11; break; case 4: acc += 12; break; case 5: acc += 13; break; case 6: acc += 14; break; case 7: acc += 15; break; }
if (o is A a) acc += a.X;
return acc;
}
static int Main()
{
var sw = Stopwatch.StartNew();
int r = Test(1);
sw.Stop();
Console.WriteLine($"result={r} jit+run={sw.ElapsedMilliseconds}ms");
Console.WriteLine($"peakWorkingSet={Process.GetCurrentProcess().PeakWorkingSet64 / (1024 * 1024)}MB");
return 100;
}
}
```
Measured with `DOTNET_TieredCompilation=0` and `DOTNET_TieredPGO=0`.
### Expected
```
result=1 jit+run=0ms
peakWorkingSet=25MB
```
(what .NET 10.0.12 prints)
### Actual
```
# Release JIT
result=1 jit+run=5043ms
peakWorkingSet=607MB
# Checked JIT
result=1 jit+run=17447ms
peakWorkingSet=629MB
```
`DOTNET_JitTimeLogFile` attributes 99.87% of the time to the `Assertion prop` phase. Time and memory scale by ~8x (the switch fan-in) per added merge point: 6 stages = 7 ms/25 MB, 7 = 67 ms/33 MB, 8 = 530 ms/96 MB, 9 = 4373 ms/608 MB. Replacing `if (o is A a)` with `if (o != null)` makes it instant.
### Notes
- `optAssertionVNIsSubtype` (`assertionprop.cpp`) passes `budget - 1` to *every* incoming PHI edge via `optVisitReachingAssertions`, so `budget` (10) bounds recursion depth, not total work; with no memoization of `(objVN, castToVN)` a depth-`d`, fan-in-`b` PHI graph costs `O(b^d)`.
- Each of those calls allocates two `fgBBNumMax + 1` `BitVec`s out of the compiler arena (`compiler.hpp`), which is never reclaimed until end of compilation, hence the memory growth.
- Fix direction: thread a shared work counter instead of a per-path depth, memoize `(objVN, castToVN)`, and/or reuse a scratch `BitVec` pair.
- `optAssertionVNIsNonNull` has the identical `budget - 1`-per-edge pattern (tracked separately).
- Likely introduced by #128500 ("JIT: fold isinst using reaching VNs and compareTypesForCast").
Contributor guide
Research direction
Start with optAssertionVNIsSubtype and optVisitReachingAssertions in assertionprop.cpp, then inspect the BitVec allocations in compiler.hpp. Run the minimal C# repro with tiering and PGO disabled, and compare the JIT time, peak working set, and scaling across added merge points. Done means the regression is removed without the exponential time or arena growth, while the type-test behavior remains correct.
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
- Clearly specified
- Newbie friendliness
- 45/100