Why doesn't the C99 compiler optimize “!a && b” as “a < b” for booleans?
I saw this really interesting tweet:
resisting my code golf instinct to turn
if(!bool1 && bool2)intoif(bool1<bool2)
I had never seen that before, so I wanted to see if compilers would also use this optimization. I started a repo with a README and a test C program: https://github.com/ndbroadbent/gcc_experiments
Here is the test program:
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
int main(int argc, const char* argv) {
if(argc != 3) {
printf("Usage: %s <a> <b>n", argv[0]);
exit(1);
}
bool a = strtol(argv[1], NULL, 10) != 0;
bool b = strtol(argv[2], NULL, 10) != 0;
if (!a && b) {
printf("!a && b == true (a: %d, b: %d)n", a, b);
} else {
printf("!a && b == false (a: %d, b: %d)n", a, b);
}
}
I tried compiling this program with both the gnu90 and C99 standards. I know C99 has a bool type, but is that still treated like an integer, so the compiler can't make any optimizations based on boolean logic?
I might be reading the assembly wrong, but it looks like C99 with -O3 is also including jne and je instructions, instead of just using one "less than" operation and a single jump instruction. It looks like C++ doesn't make this optimization either.
c boolean compiler-optimization boolean-logic
asked Nov 21 '18 at 17:47
ndbroadbentndbroadbent
10.4k34664
|
show 6 more comments
I saw this really interesting tweet:
resisting my code golf instinct to turn
if(!bool1 && bool2)intoif(bool1<bool2)
I had never seen that before, so I wanted to see if compilers would also use this optimization. I started a repo with a README and a test C program: https://github.com/ndbroadbent/gcc_experiments
Here is the test program:
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
int main(int argc, const char* argv) {
if(argc != 3) {
printf("Usage: %s <a> <b>n", argv[0]);
exit(1);
}
bool a = strtol(argv[1], NULL, 10) != 0;
bool b = strtol(argv[2], NULL, 10) != 0;
if (!a && b) {
printf("!a && b == true (a: %d, b: %d)n", a, b);
} else {
printf("!a && b == false (a: %d, b: %d)n", a, b);
}
}
I tried compiling this program with both the gnu90 and C99 standards. I know C99 has a bool type, but is that still treated like an integer, so the compiler can't make any optimizations based on boolean logic?
I might be reading the assembly wrong, but it looks like C99 with -O3 is also including jne and je instructions, instead of just using one "less than" operation and a single jump instruction. It looks like C++ doesn't make this optimization either.
c boolean compiler-optimization boolean-logic
asked Nov 21 '18 at 17:47
ndbroadbentndbroadbent
10.4k34664
5
"I tried compiling this program with both GCC and C99." - What do you mean? GCC is a compiler and C99 is a standard.
– Broman
Nov 21 '18 at 17:51
Sorry I just mean I used bothgccandc99on the command line. So the default forgccis apparently-std=gnu90, and calling/usr/bin/c99sets-std=c99. I updated my question to refer to the standards instead of the command-line tools I was running.
– ndbroadbent
Nov 21 '18 at 17:58
What is the assembly output then?
– Kamil Cuk
Nov 21 '18 at 18:03
4
ifbool1is true, you're comparing to another value when you could just bail out with a single test. I guess it depends on the stats of the outcome of the booleans.
– Jean-François Fabre
Nov 21 '18 at 18:03
@DavidSchwartz I tried all of the different optimization options (from -O0 to -O3). I have added the output fromobjdumpto my GitHub repo: github.com/ndbroadbent/gcc_experiments
– ndbroadbent
Nov 21 '18 at 18:05
|
show 6 more comments
I saw this really interesting tweet:
resisting my code golf instinct to turn
if(!bool1 && bool2)intoif(bool1<bool2)
I had never seen that before, so I wanted to see if compilers would also use this optimization. I started a repo with a README and a test C program: https://github.com/ndbroadbent/gcc_experiments
Here is the test program:
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
int main(int argc, const char* argv) {
if(argc != 3) {
printf("Usage: %s <a> <b>n", argv[0]);
exit(1);
}
bool a = strtol(argv[1], NULL, 10) != 0;
bool b = strtol(argv[2], NULL, 10) != 0;
if (!a && b) {
printf("!a && b == true (a: %d, b: %d)n", a, b);
} else {
printf("!a && b == false (a: %d, b: %d)n", a, b);
}
}
I tried compiling this program with both the gnu90 and C99 standards. I know C99 has a bool type, but is that still treated like an integer, so the compiler can't make any optimizations based on boolean logic?
I might be reading the assembly wrong, but it looks like C99 with -O3 is also including jne and je instructions, instead of just using one "less than" operation and a single jump instruction. It looks like C++ doesn't make this optimization either.
c boolean compiler-optimization boolean-logic
asked Nov 21 '18 at 17:47
ndbroadbentndbroadbent
10.4k34664
I saw this really interesting tweet:
resisting my code golf instinct to turn
if(!bool1 && bool2)intoif(bool1<bool2)
I had never seen that before, so I wanted to see if compilers would also use this optimization. I started a repo with a README and a test C program: https://github.com/ndbroadbent/gcc_experiments
Here is the test program:
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
int main(int argc, const char* argv) {
if(argc != 3) {
printf("Usage: %s <a> <b>n", argv[0]);
exit(1);
}
bool a = strtol(argv[1], NULL, 10) != 0;
bool b = strtol(argv[2], NULL, 10) != 0;
if (!a && b) {
printf("!a && b == true (a: %d, b: %d)n", a, b);
} else {
printf("!a && b == false (a: %d, b: %d)n", a, b);
}
}
I tried compiling this program with both the gnu90 and C99 standards. I know C99 has a bool type, but is that still treated like an integer, so the compiler can't make any optimizations based on boolean logic?
I might be reading the assembly wrong, but it looks like C99 with -O3 is also including jne and je instructions, instead of just using one "less than" operation and a single jump instruction. It looks like C++ doesn't make this optimization either.
c boolean compiler-optimization boolean-logic
c boolean compiler-optimization boolean-logic
asked Nov 21 '18 at 17:47
ndbroadbentndbroadbent
10.4k34664
asked Nov 21 '18 at 17:47
ndbroadbentndbroadbent
10.4k34664
edited Nov 21 '18 at 18:50
ndbroadbent
asked Nov 21 '18 at 17:47
ndbroadbentndbroadbent
10.4k34664
asked Nov 21 '18 at 17:47
ndbroadbentndbroadbent
10.4k34664
asked Nov 21 '18 at 17:47
ndbroadbentndbroadbent
10.4k34664
10.4k34664
5
"I tried compiling this program with both GCC and C99." - What do you mean? GCC is a compiler and C99 is a standard.
– Broman
Nov 21 '18 at 17:51
Sorry I just mean I used bothgccandc99on the command line. So the default forgccis apparently-std=gnu90, and calling/usr/bin/c99sets-std=c99. I updated my question to refer to the standards instead of the command-line tools I was running.
– ndbroadbent
Nov 21 '18 at 17:58
What is the assembly output then?
– Kamil Cuk
Nov 21 '18 at 18:03
4
ifbool1is true, you're comparing to another value when you could just bail out with a single test. I guess it depends on the stats of the outcome of the booleans.
– Jean-François Fabre
Nov 21 '18 at 18:03
@DavidSchwartz I tried all of the different optimization options (from -O0 to -O3). I have added the output fromobjdumpto my GitHub repo: github.com/ndbroadbent/gcc_experiments
– ndbroadbent
Nov 21 '18 at 18:05
|
show 6 more comments
5
"I tried compiling this program with both GCC and C99." - What do you mean? GCC is a compiler and C99 is a standard.
– Broman
Nov 21 '18 at 17:51
Sorry I just mean I used bothgccandc99on the command line. So the default forgccis apparently-std=gnu90, and calling/usr/bin/c99sets-std=c99. I updated my question to refer to the standards instead of the command-line tools I was running.
– ndbroadbent
Nov 21 '18 at 17:58
What is the assembly output then?
– Kamil Cuk
Nov 21 '18 at 18:03
4
ifbool1is true, you're comparing to another value when you could just bail out with a single test. I guess it depends on the stats of the outcome of the booleans.
– Jean-François Fabre
Nov 21 '18 at 18:03
@DavidSchwartz I tried all of the different optimization options (from -O0 to -O3). I have added the output fromobjdumpto my GitHub repo: github.com/ndbroadbent/gcc_experiments
– ndbroadbent
Nov 21 '18 at 18:05
5
5
"I tried compiling this program with both GCC and C99." - What do you mean? GCC is a compiler and C99 is a standard.
– Broman
Nov 21 '18 at 17:51
"I tried compiling this program with both GCC and C99." - What do you mean? GCC is a compiler and C99 is a standard.
– Broman
Nov 21 '18 at 17:51
Sorry I just mean I used both
gcc and c99 on the command line. So the default for gcc is apparently -std=gnu90, and calling /usr/bin/c99 sets -std=c99. I updated my question to refer to the standards instead of the command-line tools I was running.– ndbroadbent
Nov 21 '18 at 17:58
Sorry I just mean I used both
gcc and c99 on the command line. So the default for gcc is apparently -std=gnu90, and calling /usr/bin/c99 sets -std=c99. I updated my question to refer to the standards instead of the command-line tools I was running.– ndbroadbent
Nov 21 '18 at 17:58
What is the assembly output then?
– Kamil Cuk
Nov 21 '18 at 18:03
What is the assembly output then?
– Kamil Cuk
Nov 21 '18 at 18:03
4
4
if
bool1 is true, you're comparing to another value when you could just bail out with a single test. I guess it depends on the stats of the outcome of the booleans.– Jean-François Fabre
Nov 21 '18 at 18:03
if
bool1 is true, you're comparing to another value when you could just bail out with a single test. I guess it depends on the stats of the outcome of the booleans.– Jean-François Fabre
Nov 21 '18 at 18:03
@DavidSchwartz I tried all of the different optimization options (from -O0 to -O3). I have added the output from
objdump to my GitHub repo: github.com/ndbroadbent/gcc_experiments– ndbroadbent
Nov 21 '18 at 18:05
@DavidSchwartz I tried all of the different optimization options (from -O0 to -O3). I have added the output from
objdump to my GitHub repo: github.com/ndbroadbent/gcc_experiments– ndbroadbent
Nov 21 '18 at 18:05
|
show 6 more comments
1 Answer
1
active
oldest
votes
Compilers are well aware of the eqivalence and are able to optimise based on it. Their idea of what should be optimised to what might be opposite from yours though.
For sake of completeness, here's the clang-produced assembly output of a function that does !a && b and also of a function that does “a < b”. It's the same assembly output in both cases.
mov eax, edi
not al
and al, sil
ret
answered Nov 21 '18 at 18:35
n.m.n.m.
71.4k882167
Haha awesome, that was a great way to show that the compiler knows they are equivalent. Thanks!
– ndbroadbent
Nov 21 '18 at 18:40
I should also point out that GCC 8.2 doesn't make this optimization, but clang/llvm seems to be smarter and knows that they are equivalent.
– ndbroadbent
Nov 21 '18 at 19:03
1
Linking to an off-site resource without explaining it in the answer is not good for Stack Overflow.
– Eric Postpischil
Nov 21 '18 at 19:05
Really interesting that it still uses thejneandjeinstructions for my original code, even if I change it toa < b: godbolt.org/z/bUfgEd On my CPU that's actually a little bit slower than the singlecmpinstruction.
– ndbroadbent
Nov 21 '18 at 19:06
1
@ndbroadbent And MSVC is really funny.
– n.m.
Nov 21 '18 at 19:10
|
show 1 more comment
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53417868%2fwhy-doesnt-the-c99-compiler-optimize-a-b-as-a-b-for-booleans%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Compilers are well aware of the eqivalence and are able to optimise based on it. Their idea of what should be optimised to what might be opposite from yours though.
For sake of completeness, here's the clang-produced assembly output of a function that does !a && b and also of a function that does “a < b”. It's the same assembly output in both cases.
mov eax, edi
not al
and al, sil
ret
answered Nov 21 '18 at 18:35
n.m.n.m.
71.4k882167
Haha awesome, that was a great way to show that the compiler knows they are equivalent. Thanks!
– ndbroadbent
Nov 21 '18 at 18:40
I should also point out that GCC 8.2 doesn't make this optimization, but clang/llvm seems to be smarter and knows that they are equivalent.
– ndbroadbent
Nov 21 '18 at 19:03
1
Linking to an off-site resource without explaining it in the answer is not good for Stack Overflow.
– Eric Postpischil
Nov 21 '18 at 19:05
Really interesting that it still uses thejneandjeinstructions for my original code, even if I change it toa < b: godbolt.org/z/bUfgEd On my CPU that's actually a little bit slower than the singlecmpinstruction.
– ndbroadbent
Nov 21 '18 at 19:06
1
@ndbroadbent And MSVC is really funny.
– n.m.
Nov 21 '18 at 19:10
|
show 1 more comment
Compilers are well aware of the eqivalence and are able to optimise based on it. Their idea of what should be optimised to what might be opposite from yours though.
For sake of completeness, here's the clang-produced assembly output of a function that does !a && b and also of a function that does “a < b”. It's the same assembly output in both cases.
mov eax, edi
not al
and al, sil
ret
answered Nov 21 '18 at 18:35
n.m.n.m.
71.4k882167
Haha awesome, that was a great way to show that the compiler knows they are equivalent. Thanks!
– ndbroadbent
Nov 21 '18 at 18:40
I should also point out that GCC 8.2 doesn't make this optimization, but clang/llvm seems to be smarter and knows that they are equivalent.
– ndbroadbent
Nov 21 '18 at 19:03
1
Linking to an off-site resource without explaining it in the answer is not good for Stack Overflow.
– Eric Postpischil
Nov 21 '18 at 19:05
Really interesting that it still uses thejneandjeinstructions for my original code, even if I change it toa < b: godbolt.org/z/bUfgEd On my CPU that's actually a little bit slower than the singlecmpinstruction.
– ndbroadbent
Nov 21 '18 at 19:06
1
@ndbroadbent And MSVC is really funny.
– n.m.
Nov 21 '18 at 19:10
|
show 1 more comment
Compilers are well aware of the eqivalence and are able to optimise based on it. Their idea of what should be optimised to what might be opposite from yours though.
For sake of completeness, here's the clang-produced assembly output of a function that does !a && b and also of a function that does “a < b”. It's the same assembly output in both cases.
mov eax, edi
not al
and al, sil
ret
answered Nov 21 '18 at 18:35
n.m.n.m.
71.4k882167
Compilers are well aware of the eqivalence and are able to optimise based on it. Their idea of what should be optimised to what might be opposite from yours though.
For sake of completeness, here's the clang-produced assembly output of a function that does !a && b and also of a function that does “a < b”. It's the same assembly output in both cases.
mov eax, edi
not al
and al, sil
ret
answered Nov 21 '18 at 18:35
n.m.n.m.
71.4k882167
edited Nov 22 '18 at 8:10
answered Nov 21 '18 at 18:35
n.m.n.m.
71.4k882167
answered Nov 21 '18 at 18:35
n.m.n.m.
71.4k882167
answered Nov 21 '18 at 18:35
n.m.n.m.
71.4k882167
71.4k882167
Haha awesome, that was a great way to show that the compiler knows they are equivalent. Thanks!
– ndbroadbent
Nov 21 '18 at 18:40
I should also point out that GCC 8.2 doesn't make this optimization, but clang/llvm seems to be smarter and knows that they are equivalent.
– ndbroadbent
Nov 21 '18 at 19:03
1
Linking to an off-site resource without explaining it in the answer is not good for Stack Overflow.
– Eric Postpischil
Nov 21 '18 at 19:05
Really interesting that it still uses thejneandjeinstructions for my original code, even if I change it toa < b: godbolt.org/z/bUfgEd On my CPU that's actually a little bit slower than the singlecmpinstruction.
– ndbroadbent
Nov 21 '18 at 19:06
1
@ndbroadbent And MSVC is really funny.
– n.m.
Nov 21 '18 at 19:10
|
show 1 more comment
Haha awesome, that was a great way to show that the compiler knows they are equivalent. Thanks!
– ndbroadbent
Nov 21 '18 at 18:40
I should also point out that GCC 8.2 doesn't make this optimization, but clang/llvm seems to be smarter and knows that they are equivalent.
– ndbroadbent
Nov 21 '18 at 19:03
1
Linking to an off-site resource without explaining it in the answer is not good for Stack Overflow.
– Eric Postpischil
Nov 21 '18 at 19:05
Really interesting that it still uses thejneandjeinstructions for my original code, even if I change it toa < b: godbolt.org/z/bUfgEd On my CPU that's actually a little bit slower than the singlecmpinstruction.
– ndbroadbent
Nov 21 '18 at 19:06
1
@ndbroadbent And MSVC is really funny.
– n.m.
Nov 21 '18 at 19:10
Haha awesome, that was a great way to show that the compiler knows they are equivalent. Thanks!
– ndbroadbent
Nov 21 '18 at 18:40
Haha awesome, that was a great way to show that the compiler knows they are equivalent. Thanks!
– ndbroadbent
Nov 21 '18 at 18:40
I should also point out that GCC 8.2 doesn't make this optimization, but clang/llvm seems to be smarter and knows that they are equivalent.
– ndbroadbent
Nov 21 '18 at 19:03
I should also point out that GCC 8.2 doesn't make this optimization, but clang/llvm seems to be smarter and knows that they are equivalent.
– ndbroadbent
Nov 21 '18 at 19:03
1
1
Linking to an off-site resource without explaining it in the answer is not good for Stack Overflow.
– Eric Postpischil
Nov 21 '18 at 19:05
Linking to an off-site resource without explaining it in the answer is not good for Stack Overflow.
– Eric Postpischil
Nov 21 '18 at 19:05
Really interesting that it still uses the
jne and je instructions for my original code, even if I change it to a < b: godbolt.org/z/bUfgEd On my CPU that's actually a little bit slower than the single cmp instruction.– ndbroadbent
Nov 21 '18 at 19:06
Really interesting that it still uses the
jne and je instructions for my original code, even if I change it to a < b: godbolt.org/z/bUfgEd On my CPU that's actually a little bit slower than the single cmp instruction.– ndbroadbent
Nov 21 '18 at 19:06
1
1
@ndbroadbent And MSVC is really funny.
– n.m.
Nov 21 '18 at 19:10
@ndbroadbent And MSVC is really funny.
– n.m.
Nov 21 '18 at 19:10
|
show 1 more comment
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53417868%2fwhy-doesnt-the-c99-compiler-optimize-a-b-as-a-b-for-booleans%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
5
"I tried compiling this program with both GCC and C99." - What do you mean? GCC is a compiler and C99 is a standard.
– Broman
Nov 21 '18 at 17:51
Sorry I just mean I used both
gccandc99on the command line. So the default forgccis apparently-std=gnu90, and calling/usr/bin/c99sets-std=c99. I updated my question to refer to the standards instead of the command-line tools I was running.– ndbroadbent
Nov 21 '18 at 17:58
What is the assembly output then?
– Kamil Cuk
Nov 21 '18 at 18:03
4
if
bool1is true, you're comparing to another value when you could just bail out with a single test. I guess it depends on the stats of the outcome of the booleans.– Jean-François Fabre
Nov 21 '18 at 18:03
@DavidSchwartz I tried all of the different optimization options (from -O0 to -O3). I have added the output from
objdumpto my GitHub repo: github.com/ndbroadbent/gcc_experiments– ndbroadbent
Nov 21 '18 at 18:05