So consider the following code with corresponding assembly:
int i = 0;
loop:
int j = i;
j *= 123456789;
print(j)
i += 1;
if (i < 100)
goto loop;
mov r1 0
loop:
mov ra r1
mul ra 123456789
call printf
add r1 1
cmp r1 100
jle loop
Multiplications are quite slow, so this code will be slow. Can we make it faster?
Well, we're actually only using i for one thing, namely to calculate j. We can clearly see that j == i * 123456789, so why not iterate over j instead?
int j = 0;
loop:
print(j);
j += 123456789;
if (j < 12345678900)
goto loop;
mov ra 0
loop:
call print
add ra 123456789
cmp ra 12345678900
jle loop
We got rid of the multiplication, and shaved off a few instructions as well.
But we also know that 12345678900 is larger than any 32 bit integer that fits inside the ra register, so j < 12345678900 will always return true:
int j = 0;
loop:
print(j);
j += 123456789;
goto loop;
mov ra 0
loop:
call print
add ra 123456789
jmp loop
Which gives us an infinite loop.
Both transformations (induction variable analysis and dead code elimination) are allowed to be performed by the compiler, because it assumes that overflows will not happen.
Both transformations (induction variable analysis and dead code elimination) are allowed to be performed by the compiler, because it assumes that overflows will not happen.
That's why your code is now 4x faster than C++.
[deleted] ยท 52 points ยท Posted at 21:43:23 on December 2, 2018 ยท (Permalink)
[removed]
bxct ยท 9 points ยท Posted at 02:46:01 on December 3, 2018 ยท (Permalink)*
Wait so, I wanted to try this out, I can get the following with gcc -O1 test.c:
Which makes sense, because INT_MAX = 2147483647, 123456789 * 17 = 2098765413 and 123456789 * 18 = 2222222202, so the 18th iteration results in signed integer overflow. But the undefined behavior isn't an infinite loop! Since it's using jne and (123456789 * 100) & 0xffffffff == (...(...(123456789 & 0xffffffff) + 123456789) & 0xffffffff)... it actually works (prints out 100 lines and exits).
Edit: Oh I guess I'm late to the party, I didn't see OctagonClock's comment
mqduck ยท 1 points ยท Posted at 05:32:11 on December 3, 2018 ยท (Permalink)
I feel like I'm missing the point here. No compiler would assume that overflows can't happen when optimizing code. Is your point just that compilers aren't explicitly forbidden from ignoring overflows when optimizing code or something?
scatters ยท 15 points ยท Posted at 08:17:21 on December 3, 2018 ยท (Permalink)
No compiler would assume that overflows can't happen when optimizing code
You're funny. I like you.
zenolijo ยท 1 points ยท Posted at 14:40:00 on December 3, 2018 ยท (Permalink)
He's probably been running some downstream patch on GCC with a -O4 option which includes the -fplease-overflow option.
polprog ยท 3 points ยท Posted at 00:39:06 on December 10, 2018 ยท (Permalink)
jonnywoh ยท 5 points ยท Posted at 01:03:27 on December 3, 2018 ยท (Permalink)
I don't know what it looks like on your end, but for me on your link it's not optimized out:
.LC0:
.string "%i\n"
main:
push rbx
xor ebx, ebx
.L2:
mov esi, ebx
mov edi, OFFSET FLAT:.LC0
xor eax, eax
add ebx, 123456789
call printf
cmp ebx, -539222988
jne .L2
xor eax, eax
pop rbx
ret
It's still got a jne, not a jmp
heckerle ยท 2 points ยท Posted at 08:15:42 on December 3, 2018 ยท (Permalink)
You're right!
I was only looking for the comment about how the multiplication is optimized away and didn't notice that the conditional jump is still in there.
heckerle ยท 1 points ยท Posted at 08:24:47 on December 3, 2018 ยท (Permalink)*
A standard compliant compiler is still perfectly allowed to generate an infinite loop for this code. Actually, if it does, you should be thankful that it didn't generate code that deletes your home directory and orders a nuclear strike on your neighborhood, because that wouldn't have been any less standard compliant.
I don't think it is invoking undefined behavior, and I think that any compiler that generates an infinite loop from this has a bug.
Dentosal ยท 1 points ยท Posted at 12:57:32 on December 3, 2018 ยท (Permalink)
Not always, I think. int can also be int64_t, if platform defines it like that.
err_pell ยท 1 points ยท Posted at 13:17:32 on December 3, 2018 ยท (Permalink)
That's a compiler bug, not undefined behaviour.
one_zer ยท 24 points ยท Posted at 21:13:00 on December 2, 2018 ยท (Permalink)*
One day, our descendants are going to look back at this age, and wonder why it took so long for civilization to acknowledge the intellectual power house that HN had become. Undoubtedly, they'll have only one conclusion to come to. HN was just too far ahead of its time, just like the Antikythera mechanism.
Saved comment
G3Kappa ยท 76 points ยท Posted at 19:01:22 on December 2, 2018 ยท (Permalink)
I'm not retarded, I was merely pretending
hedgehog1024 ยท 3 points ยท Posted at 09:10:12 on December 4, 2018 ยท (Permalink)
mods new flair pls
SelfDistinction ยท 56 points ยท Posted at 20:18:55 on December 2, 2018 ยท (Permalink)
They didn't even include my favourite:
This one is an infinite loop.
allKnowingHagrid ยท 30 points ยท Posted at 20:36:39 on December 2, 2018 ยท (Permalink)
Why?
SelfDistinction ยท 72 points ยท Posted at 21:03:17 on December 2, 2018 ยท (Permalink)
Glad you asked.
So consider the following code with corresponding assembly:
Multiplications are quite slow, so this code will be slow. Can we make it faster?
Well, we're actually only using i for one thing, namely to calculate j. We can clearly see that j == i * 123456789, so why not iterate over j instead?
We got rid of the multiplication, and shaved off a few instructions as well. But we also know that 12345678900 is larger than any 32 bit integer that fits inside the ra register, so
j < 12345678900will always return true:Which gives us an infinite loop.
Both transformations (induction variable analysis and dead code elimination) are allowed to be performed by the compiler, because it assumes that overflows will not happen.
defunkydrummer ยท 20 points ยท Posted at 01:26:15 on December 3, 2018 ยท (Permalink)
That's why your code is now 4x faster than C++.
[deleted] ยท 52 points ยท Posted at 21:43:23 on December 2, 2018 ยท (Permalink)
[removed]
bxct ยท 9 points ยท Posted at 02:46:01 on December 3, 2018 ยท (Permalink)*
Wait so, I wanted to try this out, I can get the following with
gcc -O1 test.c:And gcc warns that it's triggering undefined behavior:
Which makes sense, because
INT_MAX = 2147483647,123456789 * 17 = 2098765413and123456789 * 18 = 2222222202, so the 18th iteration results in signed integer overflow. But the undefined behavior isn't an infinite loop! Since it's usingjneand(123456789 * 100) & 0xffffffff == (...(...(123456789 & 0xffffffff) + 123456789) & 0xffffffff)...it actually works (prints out 100 lines and exits).Edit: Oh I guess I'm late to the party, I didn't see OctagonClock's comment
mqduck ยท 1 points ยท Posted at 05:32:11 on December 3, 2018 ยท (Permalink)
I feel like I'm missing the point here. No compiler would assume that overflows can't happen when optimizing code. Is your point just that compilers aren't explicitly forbidden from ignoring overflows when optimizing code or something?
scatters ยท 15 points ยท Posted at 08:17:21 on December 3, 2018 ยท (Permalink)
You're funny. I like you.
zenolijo ยท 1 points ยท Posted at 14:40:00 on December 3, 2018 ยท (Permalink)
He's probably been running some downstream patch on GCC with a -O4 option which includes the -fplease-overflow option.
polprog ยท 3 points ยท Posted at 00:39:06 on December 10, 2018 ยท (Permalink)
-fhurt-me-plenty
OctagonClock ยท 30 points ยท Posted at 20:44:44 on December 2, 2018 ยท (Permalink)
Terminates fine on gcc 8.2.1.
SelfDistinction ยท 59 points ยท Posted at 21:31:19 on December 2, 2018 ยท (Permalink)
Did they fucking patch it?!
There goes my jerking material.
Akira1364 ยท 18 points ยท Posted at 22:47:08 on December 2, 2018 ยท (Permalink)
Works normally with Clang 8 also. I feel like it's probably been ok in all compilers for a long time TBH.
hedgehog1024 ยท 1 points ยท Posted at 09:12:46 on December 4, 2018 ยท (Permalink)
Yeah, we all know that Pascal is superi... What? Clang 8? Not Pascal?!
heckerle ยท 6 points ยท Posted at 00:29:08 on December 3, 2018 ยท (Permalink)
According to godbolt itโs still optimized away: https://godbolt.org/z/mA0jca
jonnywoh ยท 5 points ยท Posted at 01:03:27 on December 3, 2018 ยท (Permalink)
I don't know what it looks like on your end, but for me on your link it's not optimized out:
It's still got a
jne, not ajmpheckerle ยท 2 points ยท Posted at 08:15:42 on December 3, 2018 ยท (Permalink)
You're right!
I was only looking for the comment about how the multiplication is optimized away and didn't notice that the conditional jump is still in there.
heckerle ยท 1 points ยท Posted at 08:24:47 on December 3, 2018 ยท (Permalink)*
Although if we're trying to achieve infinite loops this is probably the answer: https://godbolt.org/z/vFN0MB
Source
MaltersWandler ยท 25 points ยท Posted at 00:12:31 on December 3, 2018 ยท (Permalink)
A standard compliant compiler is still perfectly allowed to generate an infinite loop for this code. Actually, if it does, you should be thankful that it didn't generate code that deletes your home directory and orders a nuclear strike on your neighborhood, because that wouldn't have been any less standard compliant.
loopsdeer ยท 6 points ยท Posted at 01:27:33 on December 3, 2018 ยท (Permalink)
but the jerk after that would be sooo
no_more_kulaks ยท 1 points ยท Posted at 23:47:41 on December 2, 2018 ยท (Permalink)
Did you enable all optimizations?
MaltersWandler ยท 1 points ยท Posted at 00:13:34 on December 3, 2018 ยท (Permalink)
just use unsigned int and stop complaining
iloveportalz0r ยท 5 points ยท Posted at 05:55:08 on December 3, 2018 ยท (Permalink)
lol no stdint.h
irqlnotdispatchlevel ยท 1 points ยท Posted at 09:14:34 on December 3, 2018 ยท (Permalink)
I don't think it is invoking undefined behavior, and I think that any compiler that generates an infinite loop from this has a bug.
Dentosal ยท 1 points ยท Posted at 12:57:32 on December 3, 2018 ยท (Permalink)
Not always, I think.
intcan also beint64_t, if platform defines it like that.err_pell ยท 1 points ยท Posted at 13:17:32 on December 3, 2018 ยท (Permalink)
That's a compiler bug, not undefined behaviour.
one_zer ยท 24 points ยท Posted at 21:13:00 on December 2, 2018 ยท (Permalink)*
One day, our descendants are going to look back at this age, and wonder why it took so long for civilization to acknowledge the intellectual power house that HN had become. Undoubtedly, they'll have only one conclusion to come to. HN was just too far ahead of its time, just like the Antikythera mechanism.
Macrobian ยท 18 points ยท Posted at 20:54:18 on December 2, 2018 ยท (Permalink)
War is peace / freedom is slavery / ignorance is strength
AprilSpektra ยท 8 points ยท Posted at 00:17:20 on December 3, 2018 ยท (Permalink)*
Actually undefined is defined. It's defined as
not a function.bmarkovic ยท 11 points ยท Posted at 07:37:43 on December 3, 2018 ยท (Permalink)
Akira1364 ยท 6 points ยท Posted at 21:23:16 on December 2, 2018 ยท (Permalink)
lol no definition
thejuror8 ยท 6 points ยท Posted at 01:13:22 on December 3, 2018 ยท (Permalink)
Checkmate atheists
[deleted] ยท 3 points ยท Posted at 20:41:49 on December 2, 2018 ยท (Permalink)
It is defined as undefined by the standard.
[deleted] ยท 2 points ยท Posted at 06:16:05 on December 3, 2018 ยท (Permalink)
This is a koan. I am now enlightened.