C# strange behavior with branching

Viewed 86

I was playing with C# and stumbled upon this case:

static int F(int n) 
{
    if (n == 1)
        return 1;
    
    return 1;
}

this generates what you would expect:

<Program>$.<<Main>$>g__F|0_0(Int32)
    L0000: mov eax, 1
    L0005: ret

as you can see the compiler understood that the if is pretty much useless and "removed" that.

now, let's try adding more ifs:

static int G(int n) 
{
    if (n == 1)
        return 1;
    
    if (n == 1)
        return 1;
    
    return 1;
}

now this generates the following ASM:

<Program>$.<<Main>$>g__G|0_1(Int32)
    L0000: cmp ecx, 1        ; do we need this?
    L0003: jne short L000b   ; do we need this?
    L0005: mov eax, 1
    L000a: ret
    L000b: mov eax, 1
    L0010: ret

The weird thing is: when you add >= 5 branches then it again understands that they are not needed.

static int H(int n) 
{
    if (n == 1)
        return 1;
    
    if (n == 1)
        return 1;
    
    if (n == 1)
        return 1;
    
    if (n == 1)
        return 1;
    
    if (n == 1)
        return 1;
    
    return 1;
}

output:

<Program>$.<<Main>$>g__H|0_2(Int32)
    L0000: mov eax, 1
    L0005: ret

Question

  • Is there a reason why it generates extra instructions in the second case?

Notes

  • SharpLab link if you want to play with it.
  • This is what GCC (-O2) generates using C:
int 
f(int n) {
    if (n == 1)
        return 1;
    
    return 1;
}

int 
g(int n) {
    if (n == 1)
        return 1;
    
    if (n == 1)
        return 1;
    
    return 1;
}

int
h(int n) {
    if (n == 1)
        return 1;
    
    if (n == 1)
        return 1;
    
    if (n == 1)
        return 1;
    
    if (n == 1)
        return 1;
    
    if (n == 1)
        return 1;
    
    return 1;
}

which generates:

f:
   mov     eax, 1
    ret
g:
    mov     eax, 1
    ret
h:
    mov     eax, 1
    ret

and here is the Godbolt link.

  • IL Code of the functions:
.method assembly hidebysig static 
        int32 '<<Main>$>g__F|0_0' (
            int32 n
        ) cil managed 
    {
        // Method begins at RVA 0x2052
        // Code size 6 (0x6)
        .maxstack 8

        IL_0000: ldarg.0
        IL_0001: ldc.i4.1
        IL_0002: pop
        IL_0003: pop
        IL_0004: ldc.i4.1
        IL_0005: ret
    } // end of method '<Program>$'::'<<Main>$>g__F|0_0'

    .method assembly hidebysig static 
        int32 '<<Main>$>g__G|0_1' (
            int32 n
        ) cil managed 
    {
        // Method begins at RVA 0x2059
        // Code size 12 (0xc)
        .maxstack 8

        IL_0000: ldarg.0
        IL_0001: ldc.i4.1
        IL_0002: bne.un.s IL_0006

        IL_0004: ldc.i4.1
        IL_0005: ret

        IL_0006: ldarg.0
        IL_0007: ldc.i4.1
        IL_0008: pop
        IL_0009: pop
        IL_000a: ldc.i4.1
        IL_000b: ret
    } // end of method '<Program>$'::'<<Main>$>g__G|0_1'

    .method assembly hidebysig static 
        int32 '<<Main>$>g__H|0_2' (
            int32 n
        ) cil managed 
    {
        // Method begins at RVA 0x2066
        // Code size 30 (0x1e)
        .maxstack 8

        IL_0000: ldarg.0
        IL_0001: ldc.i4.1
        IL_0002: bne.un.s IL_0006

        IL_0004: ldc.i4.1
        IL_0005: ret

        IL_0006: ldarg.0
        IL_0007: ldc.i4.1
        IL_0008: bne.un.s IL_000c

        IL_000a: ldc.i4.1
        IL_000b: ret

        IL_000c: ldarg.0
        IL_000d: ldc.i4.1
        IL_000e: bne.un.s IL_0012

        IL_0010: ldc.i4.1
        IL_0011: ret

        IL_0012: ldarg.0
        IL_0013: ldc.i4.1
        IL_0014: bne.un.s IL_0018

        IL_0016: ldc.i4.1
        IL_0017: ret

        IL_0018: ldarg.0
        IL_0019: ldc.i4.1
        IL_001a: pop
        IL_001b: pop
        IL_001c: ldc.i4.1
        IL_001d: ret
    } // end of method '<Program>$'::'<<Main>$>g__H|0_2'
2 Answers

As usual, yet another missed optimization in the JIT. Report it to the developers of whichever JIT you're using (presumably Microsoft), especially if it comes up in real use-cases. But probably they tuned their JIT this way on purpose, presumably because it's not super common for real code to have such useless if statements. Certainly happens, but most ifs aren't useless.

The general answer to this and your previous questions (about optimizations that C compilers find but C# doesn't) is that JITs have to compile fast, and don't have the time to search for as many optimizations, so you should expect crap like this.

Why 5? Compilers frequently use heuristics on code-size or maybe number of branches to make decisions, perhaps in this case whether to try looking for some commonality between branch paths. In your case, 5 if statements was enough to push past some threshold for some heuristic. If you were investigating an open-source JIT, you could if you wanted dig in and find out specifically where in the source code it made the decision.

Especially for a JIT where compile-time more directly trades off against quality of optimization, skipping a pass that checks for that could make sense. But it doesn't for ahead-of-time C compilers; if you tell them to optimize, they will.

So anything that MSVC can optimize but C# doesn't is likely just a heuristic choice made to keep the JIT fast. IDK if MSVC is a good benchmark, but it's not the most aggressive or good optimizing compiler, compared to GCC and clang.


As @PMF mentioned in comments, this is actually an optimization the C# compiler proper could have made in the IL, instead of leaving it for the JIT. But probably most cases where it happens in real programs (that aren't on purpose written redundantly), it's only visible after things like inlining.

Still, this would be one way for MS to implement an optimization (that works for this intentionally-redundant case) without hurting the JIT-time vs. asm-speed tradeoff.

Going into a bit more detail here as to why the optimization does/doesn't happen depending on the number of ifs:

The optimization that occurs with the 1-if version actually seems to occur at compile time, since the IL produced in this case didn't contain any conditionals (it does contain some redundant loads of values that are simply popped later, but clearly the JIT is able to eliminate these from the generated code). In fact, all of the IL dumps you've given show that the compiler is optimizing away the last if, so the number of conditionals/returns in the IL is one fewer than the number in the C# source (this is relevant later). As others mention, the compiler should probably be optimizing away all the redundant conditionals, not just the last one, but let's try and work out why the JIT is doing what it's doing here.

The question therefore is: what's different in the JIT at 5 ifs that causes it to be optimized where fewer than 5 ifs aren't? Determining this pretty much requires building the .NET runtime from source in debug mode, then using the JIT-dumping functionality to see into exactly what the JIT is doing as it compiles the method. Having done this, the first obvious difference between the 2 and 5 if versions is that in the latter case, an early JIT phase kicks in which merges returns from the method, and since all the returns are the same, they are all merged into a single return block. Later phases of the JIT are then able to determine that the conditional jumps are redundant and so eliminates all of them as well, and the resulting native code is the simple mov eax,1/ret that we expect.

Now that we suspect it's return-merging that is the key to triggering the full optimization, we need to determine why 5 ifs is the magic number. This turns out to be relatively easy - there's a hard limit of 4 returns in a JITted method (see: flowgraph.cpp#L2127). While the 5 if version actually has 6 returns in the C# source, recall that the compiler optimizes away the last if, leaving just 5 returns in the IL, so it's only the 5 (or more) if version that exceeds this limit and causes the return-merging to kick in.

Finally we can test the hypothesis by rebuilding the JIT with the limit on the number of returns reduced, and see whether it optimizes the 2-4 ifs cases properly. Unfortunately it's not quite as simple as just changing the JIT's maximum number of returns to 1, because this triggers slightly different return-merging behaviour, so we'll try setting the maximum number of returns to 2, and I can confirm that it does then correctly optimize the 3 and 4 if versions as we expected.

Related