151–160 of 193 posts
Earlier quoted context omitted.
No, the compiler may assume that the behavior of standard library functions is standards-conformant.
> No, the compiler may assume that the behavior of standard library functions is standards-conformant. Why? What happens if it isn't?
§6.4.2.1: "If the program defines a reserved identifier [...] the behavior is undefined."
Earlier quoted context omitted.
Mhm, this is one of these cases I'd prefer a benchmark to be sure. Checking %2 is very performant and actually just a single bit check. I can also imagine some cpu's having a special code path for %3. In practice I would not be surprised that the double operand is actually faster than the %6. I am mobile at this moment, so not able to verify.
But if % 2 && % 3 is better, then isn't there still a missed optimization in this example?
is_divisible_by_6(int):
test dil, 1
jne .LBB0_1
imul eax, edi, -1431655765
add eax, 715827882
cmp eax, 1431655765
setb al
ret
.LBB0_1:
xor eax, eax
ret
is_divisible_by_6_optimal(int):
imul eax, edi, -1431655765
add eax, 715827882
ror eax
cmp eax, 715827883
setb al
ret
But note the branch in the first function! The original code uses the && operator, which is short-circuiting -- so from the compiler's perspective, perhaps the programmer expects that x % 2 will usually be false, and so we can skip the expensive 3 most of the time. The "suboptimal" version is potentially quite a bit faster in the best case, but also potentially quite a bit slower in the worst case (since that branch could be mispredicted). There's not really a way for the compiler to know which version is "better" without more context, so deferring to "what the programmer wrote" makes sense.
That being said, I don't know that this is really a case of "the compiler knows best" rather than just not having that kind of optimization implemented. If we write 'x % 6 && x % 3', the compiler pointlessly generates both operations. And GCC generates branchless code for 'is_divisible_by_6', which is just worse than 'is_divisible_by_6_optimal' in all cases.
Earlier quoted context omitted.
Since I had to think about it: unsigned add(unsigned x, unsigned y) { unsigned a, b; do { a = x & y; /* every position where addition will generate a carry */ b = x ^ y; /* the addition, with no carries */ x = a It's easy to show that this algorithm is correct in the sense that, when b is returned, it must be equal to x + y . x + y summing to a constant is a loop invariant, and at termination x is 0 and y is b . It's…
In C, I'm pretty confident the loop is defined by the standard to terminate. Also I did take the excuse to plug it (the optimized llvm ir) into Alive: https://alive2.llvm.org/ce/#g:!((g:!((g:!((h:codeEditor,i:(f...
Huh? What's that supposed to mean?
Earlier quoted context omitted.
I understand that, but I don't agree that such optimizer behavior is worth it and I won't put it in my compilers.
I appreciate that greatly.
If I program it to cause a null pointer seg fault, I expect a null pointer seg fault. If I program it to cause a twos complement overflow, I want a twos complement overflow.
Earlier quoted context omitted.
I appreciate that greatly.
The notion that because it is undefined behavior means that the compiler is free to replace it with anything up to and including "launch nuclear missiles". This is just nuts. If I program it to cause a null pointer seg fault, I expect a null pointer seg fault. If I program it to cause a twos complement overflow, I want a twos complement overflow.
Earlier quoted context omitted.
> int bar(int num) { return num / 2; } > > Doesn't get optimized to a single shift right, because the that won't work if num is negative. Nit: some might think the reason this doesn't work is because the shift would "move" the sign bit, but actually arithmetic shifting instructions exist for this exact purpose. The reason they are not enough is because shifting provides the wrong kind of division rounding for negativ…
Will shift, shift, and add be slower or faster than a divide instruction on machines with a divide instruction?
Earlier quoted context omitted.
`s` may be null, and so the strlen may seg fault.
But that's undefined behavior, so the compiler is free to ignore that possibility.
And that's what is wrong. This is the most unfriendly behavior towards the programmer.
Earlier quoted context omitted.
`s[0] == 'h'` isn't sufficient to guarantee that `s[3]` can be access without a segfault, so the compiler is not allowed to perform this optimization. If you use `&` instead of `&&` (so that all array elements are accessed unconditionally), the optimization will happen: https://godbolt.org/z/KjdT16Kfb (also note you got the endianness wrong in your hand-optimized version)
> If you use `&` instead of `&&` (so that all array elements are accessed unconditionally), the optimization will happen But then you're accessing four elements of a string that could have a strlen of less than 3. If the strlen is 1 then the short circuit case saves you because s[1] will be '\0' instead of 'e' and then you don't access elements past the end of the string. The "optimized" version is UB for short strin…
Earlier quoted context omitted.
But if % 2 && % 3 is better, then isn't there still a missed optimization in this example?
Let's throw this into godbolt: https://clang.godbolt.org/z/qW3qx13qT is_divisible_by_6(int): test dil, 1 jne .LBB0_1 imul eax, edi, -1431655765 add eax, 715827882 cmp eax, 1431655765 setb al ret .LBB0_1: xor eax, eax ret is_divisible_by_6_optimal(int): imul eax, edi, -1431655765 add eax, 715827882 ror eax cmp eax, 715827883 setb al ret By themselves, the mod 6 and mod 3 operations are almost identical -- in both case…
bool is_divisible_by_15(int x) {
return x % 3 == 0 && x % 5 == 0;
}
bool is_divisible_by_15_optimal(int x) {
return x % 15 == 0;
}
is_divisible_by_15(int):
imul eax, edi, -1431655765
add eax, 715827882
cmp eax, 1431655764
jbe .LBB0_2
xor eax, eax
ret
.LBB0_2:
imul eax, edi, -858993459
add eax, 429496729
cmp eax, 858993459
setb al
ret
is_divisible_by_15_optimal(int):
imul eax, edi, -286331153
add eax, 143165576
cmp eax, 286331153
setb al
ret