[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: MIT discovered issue with gcc



On 28/11/13 10:02, Bernhard R. Link wrote:

In brief: Debian should call for compilation with -O0 for all packages compiled with GCC where maintainers won't take responsibility for the program not falling into UB ever.

See below for the full comments.

* Octavio Alvarez <alvarezp@alvarezp.ods.org> [131127 21:28]:
On 26/11/13 11:37, Mark Haase wrote:
Compiler developers, for better or worse, reserve the right to do
whatever they want with undefined behavior, and it's up to the person
writing the C code to not include undefined behavior in their own program.

That's a fallacy. The fact that a compiler does not violate the
standard does not imply it is behaving sane. Thus, not violating the
standard does not imply not having a bug.

"Not violating the standard means no bug" would indeed be a fallacy.
But that is a different statement that what you replied to.

The first part, "compiler developers, for better or worse, reserve the right to do whatever they want with undefined behavior", implies that the compiler takes no responsibility for code that falls under UB and should feel free to do either sane or insane things because it is not violating the standard.

This is reinforced with the second part, "it's up to the person writing the C code to not include undefined behavior in their own program", which lets developers just push bug reports back to the reporters.

So, in overall, the phrase is implying that it is valid to make unsafe assumptions and, when reported as bugs, just push the problem back to the developers. Not only that, but it promotes this practice. This is the relevance of noting the fallacy.

And this is a bad, bad problem.

Considering a programmer would not ever *ever* want to fall into
undefined behavior, the compiler should just issue warnings before
making any kind of assumptions based after undefined behavior. Those
warnings could be silenced with flags. This is a way of "yes, I'm
sure of what I'm doing".

The whole point of undefined behaviour is this type of warnings are not
possible. And if such warnings would be possible, that kind of code
would better produce an error than making that behaviour undefined.

You are mixing two things. Yes, it's the developer responsibility to make correct programs, but no, the compiler should not make the mistakes worse.

Consider this case:

$ cat zero.c
int main(void) {
	int a = 4;
	int b = a + 7;
	int c = a - b + 7;
	if (3/c > 4)
		return 5;
	return 10;
}

What is the *expected* outcome of this program? From the point of view of the C standard there is no expected outcome. The developer clearly made a mistake because c == 0 by line 5, but the coder is expecting the CPU to execute the instruction 3/c.

However, GCC takes this away even with just -O1:

$ gcc -O0 -std=c99 -Wall -Wextra -pedantic-errors -ggdb -o zero zero.c
$ ./zero; echo $?
Floating point exception (core dumped)
136

$ gcc -O1 -std=c99 -Wall -Wextra -pedantic-errors -ggdb -o zero zero.c
$ ./zero; echo $?
10

On -O1, the compiler is optimizing everything away to "return 10".

$ objdump -D zero | grep -A 5 '<main>'
00000000004004ec <main>:
  4004ec:	b8 0a 00 00 00       	mov    $0xa,%eax
  4004f1:	c3                   	retq
  4004f2:	66 2e 0f 1f 84 00 00 	nopw   %cs:0x0(%rax,%rax,1)
  4004f9:	00 00 00
  4004fc:	0f 1f 40 00          	nopl   0x0(%rax)

This is incorrect. Why? The compiler is taking the assumption that the comparison 3/x > 4 (with x being integer) always evaluate to false.

But "3/x > 4, with x being integer" does not always evaluate to false. There is the case, x == 0, where 3/x is undefined. This proves the compiler is optimizing based on blind assumptions. This should be a bug, but developers will say it's not because x/0 is UB. Saying so is the fallacy I'm talking about.

IOW, there should be an optimization option, say, -O or -O1, where at least we as programmers could rely on the compiler making optimizations ONLY within the confines of defined behavior. Make that the default and let -OU as an option to add those UB-based crazy assumptions for fast-as-light-but-wrong code.

In this other case (I changed "a" to be != 4):

$ cat zero2.c
int main(void) {
	int a = 5;
	int b = a + 7;
	int c = a - b + 7;
	if (3/c > 4)
		return 5;
	return 10;
}

$ gcc -O0 -std=c99 -Wall -Wextra -pedantic-errors -ggdb -o zero2 zero2.c
$ ./zero; echo $?
10

$ gcc -O1 -std=c99 -Wall -Wextra -pedantic-errors -ggdb -o zero2 zero2.c
$ ./zero; echo $?
10

$ objdump -D zero2 | grep -A 5 '<main>'
00000000004004ec <main>:
  4004ec:	b8 0a 00 00 00       	mov    $0xa,%eax
  4004f1:	c3                   	retq
  4004f2:	66 2e 0f 1f 84 00 00 	nopw   %cs:0x0(%rax,%rax,1)
  4004f9:	00 00 00
  4004fc:	0f 1f 40 00          	nopl   0x0(%rax)

The optimizer is still making a wrong assumption. The result being 10 is just a coincidence.

If, and only if, the compiler works through this deduction:

C must be != 0
a is 4
4 - b + 7 != 0
4 - b != -7
a != 4
In this code a == 5, so c != 0

Only then the optimizer can feel free to optimize the "if" section away.

In this function (where I changed "a" to be a parameter):

int f(int a) {
	int b = a + 7;
	int c = a - b + 7;
	if (3/c > 4)
		return 5;
	return 10;
}

The optimizer should NOT take the division away, but here:

int f(int a) {
	if (a == 4)
		return 0;
	int b = a + 7;
	int c = a - b + 7;
	if (3/c > 4)
		return 5;
	return 10;
}

... then the compiler can take the division away.

As an idea, and just thinking out loud, it could be a bad idea, how about this:

#undef NDEBUG
int f(int a) {
	assert(a == 4);
	int b = a + 7;
	int c = a - b + 7;
	if (3/c > 4)
		return 5;
	return 10;
}

Note that NDEBUG is undefined, effectively not resulting in any actual code, but the compiler could take it as an optimization hint.

Undefined behaviour is especially reserved for anything where the
compiler can on all forseeable platforms, produce fast code in the
usual case, but strange things can happen in the undefined case.

If this were optional (like -OU) I'd be fine with it. I would at least have an option to have safe compilation. I will show an example below.

Let's take the example of signed overflow:

Almost every operation with numbers has some chance for overflow,
depending on the numbers. While for unsigned numbers the result
is quite easy to define (just calculate and go module 2^wordsize)
and processors come with instructions doing that efficiently
(or it is easy and fast to emulate them). But with signed numbers,
just defining some specific behaviour means severly limiting the
compiler what processor instructions to use. It might even mean
that a compiler would have to generate a conditional for every
operation with signed numbers to just test first if it would
overflow.

I'm not saying that. The compiler defining a safe behavior is just as bad. That is also a fallacy.

It just means that the compiler should not optimize away. It is still the developer's responsibility to not fall into UB.

So this little trick of making the behaviour undefined
can speed up the programs a compiler generates a significant
amount of time.

So allowing some operations that are valid or invalid depending
on what input it is given is already needed if you want fast
programs.

I don't want fast programs. I want programs that do exactly what I said. Once that premise is fulfilled, *then* I want fast programs (or small, if I'm on embedded).

Next the compiler has to decide what to do with things like

void foo(int s, int e) {
         int i;
         for (i = s ; i != e ; i++) {
                 something();
         }
}

Given that writing programs that have signed integers overflow
is already forbidden (by making them undefined), the compiler
can translate this to:

DO e-s TIMES
         CALL something

I see your point, let me say that. But no, the compiler shouldn't do that because it does not have enough information. It would just be a wrong compiler decision.

I would, though, find it valid in the following code:

void foo(int s, int e) {
         if (s >= e))
	 	 return;
         int i;
         for (i = s ; i != e ; i++) {
                 something();
         }
}

but if you want to take away the conditional:

void foo(int s, int e) {
         assert(s < e);
         int i;
         for (i = s ; i != e ; i++) {
                 something();
         }
}

Even if NDEBUG is not defined. Or something similar, like a conditional comment:

void foo(int s, int e) {
         /* GCC_ASSERT(s < e) */
         int i;
         for (i = s ; i != e ; i++) {
                 something();
         }
}

... or whatever hint is included.

Without using the information about undefined behaviour, it would
have to translate it to:

IF s < e
         DO e-s TIMES
                 CALL something
ELSE
         DO range(int)-(s-e) TIMES
                 CALL something

or if e was a long:

IF s < e
         DO e-s TIMES
                 CALL something
ELSE IF e <= MAXINT
         DO range(int)-(s-e) TIMES
                 CALL something
ELSE
         ENDLESS LOOP
                 CALL something

Both of which are wrong. It should map to whatever gcc -O0 gives:

00000000004004f7 <foo>:
  4004f7:       55                      push   %rbp
  4004f8:       48 89 e5                mov    %rsp,%rbp
  4004fb:       48 83 ec 18             sub    $0x18,%rsp
  4004ff:       89 7d ec                mov    %edi,-0x14(%rbp)
  400502:       89 75 e8                mov    %esi,-0x18(%rbp)
  400505:       8b 45 ec                mov    -0x14(%rbp),%eax
  400508:       89 45 f8                mov    %eax,-0x8(%rbp)
  40050b:       eb 11                   jmp    40051e <foo+0x27>
  40050d:       b8 00 00 00 00          mov    $0x0,%eax
  400512:       e8 d5 ff ff ff          callq  4004ec <something>
  400517:       89 45 fc                mov    %eax,-0x4(%rbp)
  40051a:       83 45 f8 01             addl   $0x1,-0x8(%rbp)
  40051e:       8b 45 f8                mov    -0x8(%rbp),%eax
  400521:       3b 45 e8                cmp    -0x18(%rbp),%eax
  400524:       75 e7                   jne    40050d <foo+0x16>
  400526:       c9                      leaveq
  400527:       c3                      retq

You can see actual call to increment i in "addl $0x1,-0x8(%rbp)" the test for equality and the jump back to continue the loop. If the hardware fails, then so be it! It was the coder fault for falling into UB. Leave it to the CPU to make the program fail.

As people want fast programs it makes sense in my eyes to say here:

This is an incorrect assumption. Coders want fast programs *as long as they exactly map whatever the coded said* (not with what the coder intended). Otherwise the compiler is failing to do what the coder asked for.

In conclusion, the current state of this GCC optimization is not trustable. Considering the div/0 optimization begins on -O1, then -O1 and higer levels are not trustable.

Therefore, Debian should call for compilation with -O0 for all packages compiled with GCC where maintainers won't take responsibility for the program not falling into UB ever.


Reply to: