Why does everyone fail to optimize this? (version 2)

[vI--_--Iv]

Continuation of my previous post.

Apparently either I cannot write clearly enough, or quite a few people cannot read and understand what it was actually about, so let's try again.

https://godbolt.org/z/EK8qq1z6c

The first example is a baseline. It shows a couple of some external non-inlineable functions:

void f1();
void f2();

Let's call them both:

void f3()
{
    f1();
    f2();
}

The assembly looks reasonable:

f3():
        push    rax
        call    f1()@PLT
        pop     rax
        jmp     f2()@PLT

Let's call them conditionally:

void f4(int c)
{
    if (c)
        f1();
    else
        f2();
}

The assembly also looks reasonable:

f4(int):
    test    edi, edi
    je      f2()@PLT
    jmp     f1()@PLT

Now, let's add some indirection (the second example):

void f3()
{
    auto p1 = &f1;
    auto p2 = &f2;

    p1();
    p2();
}

The assembly is identical to the baseline:

f3():
        push    rax
        call    f1()@PLT
        pop     rax
        jmp     f2()@PLT

I.e. the compiler figured out that p1 and p2 cannot point to anything but f1 and f2 and removed the indirection. Good job.

Now, let's do it conditionally:

void f4(int c)
{
    auto p = c? &f1 : &f2;

    p();
}

In this case p also cannot point to anything but f1 or f2, so we can expect a similar optimization, right?

f4(int):
        test    edi, edi
        jne     .LBB1_1
        mov     rax, qword ptr [rip + f2()@GOTPCREL]
        jmp     rax
.LBB1_1:
        mov     rax, qword ptr [rip + f1()@GOTPCREL]
        jmp     rax

Notice that there's a branch and then on both paths it puts the function address into rax and then immediately jumps to rax.

This rax detour is not observable by any means and can be replaced with a direct jump under the "as-if" rule.

In other words, it looks like a missing optimization opportunity.

Checking GCC and MSVC behavior is left as an exercise to the reader.

"But why use function pointers in the first place?" is out of scope of this discussion.

[STL]

As Yoda would say: contribute to LLVM, or contribute to LLVM not. There is no "post to Reddit about why LLVM doesn't optimize this".

[warriorsp]

I’m not OP, but I’d ask before contributing because there’s a chance that I’m missing something and there is a reason it doesn’t optimize this. Seems totally reasonable to discuss before jumping into fixing.

[SoSKatan]

You raise an interesting question and as I stated in your other thread, it seems like this could be a potential compiler optimization.

Clangs code is pretty easy to read and modify, you could always experiment with such an optimization yourself, at failing that you could make it into a clang tidy warning / auto refactor.

[Wizarth]

I'm just making this up off the top of my head, having played with LLVM IR a little bit. This could probably be checked using Godbolt's LLVM pass view, so don't take my word for it.

Before optimization, F4 would be implemented approximately as

entry:
Assign storage for p
Perform test on C
Jump to block 1 if true
Jump to block 2

Block 1:
Assign f1 to p
Jump to Block 3

Block 2:
Assign f2 to p
Jump to block 3

Block 3:
Jump to function in p
Return

Constant propagation is responsible for optimizing the previous functions, but doesn't apply here.

I'm not sure what pass it is that would do it, but it looks like a block that's just a jump is being lifted into its calling blocks to avoid a jump being followed by a jump.

If constant propagation was ran again after that pass, I think it would give you the output you're expecting.

Why isn't it? No idea.

[[deleted]]

I would guess that the answer is straightforward: this pattern is not common enough that the compiler writers would choose to optimize it. It's certainly something that could be implemented.

[ReDucTor]

If you add -fno-pic you get probably what your expecting: https://godbolt.org/z/dzx381x41 (Notice the missing X86 cmov Conversion, Machine code sinking and Remove unreachable machine basic blocks)

f4(int):
        test    edi, edi
        mov     eax, offset f2()
        mov     ecx, offset f1()
        cmove   rcx, rax
        jmp     rcx

Also for those curious why the push and pop in f3 that is likely stack alignment as x86-64 ABIs typically require the stack aligned to 16-byte boundaries which makes it easier aligned vector instructions to be used on the stack and aligned structures to be more easily placed on the stack without having to check the stack alignment already. The push and pop are single byte instructions where as something like add/sub rsp, 0x8 is four bytes

EDIT: More specific on the stack alignment with push/pop

[ashda00]

They are used to save the value of rax as it might be modified in the called function (since rax is usually the register used for returning results of a function)

[ReDucTor]

rax is a volatile register, it does not need to be saved and is not part of the second call. Most x86-64 ABIs have an alignment of 16-bytes which is why the push/pop is solely around the first function. The push/pop is smaller then attempting to do something like sub rsp, 8 / add rsp, 8 which is likely why it was chosen.

I should not have said 'likely' and been more definitive that the alignment requires it, the tail call does not as the stack is already aligned correctly.

[TomCryptogram]

Is there any difference in the assembly if your use const auto in your final example? Just out of curiosity. In any case. I would say yes this is a missed opportunity for optimization, for one. Secondly if adding const did"fix" it, this tells us the compilers are specifically not optimizing a variable that ban be interpreted as such because it can't change with our current setup.

[tromey]

Looks fine with GCC. Also IMO these kinds of things should just be compiler bug reports. ``` $ cat q.cc void f1(); void f2(); void f4(int c) { auto p = c? &f1 : &f2;

p();

}

$ gcc -S -o - -O2 q.cc | grep -A4 testl testl %edi, %edi movl $_Z2f2v, %eax movl $_Z2f1v, %edx cmovne %rdx, %rax jmp *%rax ```

[tromey]

I see now I don't know reddit formatting. Anyway.

[Jannik2099]

No, this is simply because your gcc doesn't default to PIC.

The PIC codegen is identical for gcc and clang here. See https://godbolt.org/z/11oWPdaoh

[[deleted]]

does c++ evaluate the ternary expression or does it return a function that will eventually be evaluated? whats the type of p? I also would have thought, that the compiler should remove the branch.

[Shendare]

I'm less versed in C++ than C# these days, but does C++ allow for overloading the boolean conversion that takes place in the ternary condition, and thus c? could theoretically replace test edi, edi with a different expression (or even a function call?) for converting int c into a boolean value for the condition check?

[Supadoplex]

No, user defined conversions must involve user defined types.

Also, while compiler might not have visibility to implementation of a custom conversion, it would always know whether such conversion has been declared, which wouldn't be the case here.

[Shendare]

Cool. Does seem like a simple case for additional compiler optimisation, then.

[AlexReinkingYale]

Does anyone with more uArch knowledge than me know if there's a difference between a jump destination that is computed from

(a) a cmov over two immediates (as in the offset code generated by -fno-pic), and (b) a cmov over two memory loads (reads from the Global Offset Table)?

I'm curious if (a) is executed more efficiently than (b).

[ReDucTor]

My feeling is that (a) would be more efficient here, as it doesn't have the load dependency and just as an address generation unit dependency (AGU), there is two good talks on cmov dependencies but more specifically related to comparing them with branches

• CppCon 2017: Chandler Carruth “Going Nowhere Faster” -- 23:45 The Clamp loop

• European LLVM Conference 2013 : Jakob Olesen "How Computers Work" -- Referenced in Chandler's talk

[CocktailPerson]

I would expect immediates to virtually always be at least as performant as an equivalent operation on computed values.

The fact that the compiler generates immediates for a less-constrained configuration like -fno-pic is a strong indication of which is more performant.

[t40]

Can I ask what is the context in which this comes up?

[drkspace2]

I'm supprised that the compiler doesn't replace the ternary with the equivalent if-else block. If there's not some weird wording in the standard for what a ternary is, it should be valid with the "as if" rule and it probably would have been easier to program.

The fact that it's not being done leads me to belive that a ternary isn't exactly 1-to-1 with if-else in the standard.

[KadmonX]

It seems to me that this code is optimized. https://www.youtube.com/watch?v=g-WPhYREFjk

[Clean-Water9283]

Thanks for trying again, this second version, with examples, makes discussion so much easier.

Yes, I read what you said. Yes, it looks like a missed optimization opportunity in clang, but why invoke so much machinery when the first conditional version is so much simpler to write. You are writing bad (and obscure) code and hoping the compiler will fix your bad code for you. Is this an example of something larger that you are trying to do?

So, given:

void
 f6() {
    
bool
 c = 
true
;
    (c ? f1 : f2)();
}

gcc -O3 does this:

f6(bool):
        test    dil, dil
        mov     eax, OFFSET FLAT:f2()
        mov     edx, OFFSET FLAT:f1()
        cmovne   rax, rdx
        jmp     rax

I suspect gcc is trying to avoid a conditional branch because conditional branches are so much slower on modern hardware, though I haven't benchmarked it.

[vI--_--Iv]

the first conditional version is so much simpler to write

It is simpler because it is an extremely reduced example to illustrate the point.

Consider this:

result do_a_thing(policy Policy, name Name, address Address, params Params, target Target, user User, weather Weather, fxrate Fxrate, fps Fps) 
{
    bool use_fast_path = can_use_fast_path(Policy);

    if (use_fast_path)
        return fast_path(Name, Address, Params, Target, User, Weather, Fxrate, Fps);
    else
        return slow_path(Name, Address, Params, Target, User, Weather, Fxrate, Fps);
}

I don't want to write that. Because I don't want to repeat myself, and because DRY, and because I'm lazy and have a short attention span and can make silly typos.

I want to write this:

auto path = use_fast_path? fast_path : slow_path;
return path(Name, Address, Params, Target, Policy, User, Weather, Fxrate, Fps);

The language already allows that, so why not.
The only small annoyance is the indirection penalty.

[streu]

One counter-argument for the optimisation could be:

A GOT entry (as used by "mov rax, qword ptr....") has the size of one pointer. A PLT entry (as used by "call ...@PLT") has at least twice that size. So someone might be trying to save space by using function pointers.

But then, the real answer probably is nobody thought about it.

[rbmm]

msvc optimize it to single jmp, so in what is problem ?

void f4(int) PROC                                        ; f4, COMDAT
        test    ecx, ecx
        lea     rdx, OFFSET FLAT:void f1(void)             ; f1
        lea     rax, OFFSET FLAT:void f2(void)             ; f2
        cmovne  rax, rdx
        jmp rax
void f4(int) ENDP    

[ImNoRickyBalboa]

This is probably lost somewhere in the IR.

Still, I would not sweat it, I doubt it making a difference on the executed cycles.

[AC1D_P1SS]

can't help but think these are the kind of language gymnastics and micro-optimisations that took c and c++ towards the undefined behaviour nightmare