Live data from Hacker News

I Do Not Know C: Short quiz on undefined behavior (2015)

kukuruku.co

51–60 of 189 posts

Re: I Do Not Know C: Short quiz on undefined behavior (2015)

#51

Honestly, Optimizing compilers will kill C. It killed the one thing C was good at - simplicity (you know exactly what happens where, note I'm not saying speed, as C++ can be quite a bit faster than C). Now, due to language lawyering, you can't just know C and your CPU, you have to know your compiler (and every iteration of it!). And if you slip somewhere, your security checks blow up ( http://blog.regehr.org/archives…

Optimisers are what made C what it is: they convert the idealised PDP-11 assembly into something efficient on modern computers, and speed is something C programmers care about.

Re: I Do Not Know C: Short quiz on undefined behavior (2015)

#52
post #17

I'll be honest, I didn't find any of these to be particularly surprising. If you've been using C and are familiar with strict-aliasing and common UB issues I wouldn't expect any of these questions to seriously trip you up. Number 2 is probably the one most people are unlikely to guess, but that example has also been beaten to death so much since it started happening that I think lots of people (Or at least, the peopl…

I don't think #2 has been fully beaten to death yet. Assuming a platform where you don't segfault (say that 'page 0' variables are valid) and thus runtime does proceed; I still can't think of any /valid/ reason to eliminate the if that follows (focus line 2 in the comments). Under what set of logic does being able to de-reference a pointer confer that it's value is not 0 (which is what the test equates to)? In my opi…

  Under what set of logic does being able to de-reference a pointer confer that it's value is not 0 (which is what the test equates to)?
Normal deductive logic?

  * No NULL pointer can be dereferenced. 
  * x is dereferenced.
  * Therefore, x is not a NULL pointer.
Of course, the compiler is presuming that your code is correct. That's a reasonable presumption when dealing with computer programming languages. Programming languages would be rather hard to interpret and translate--not to mention impossible to optimize--if you couldn't apply basic deductive logic to their statements.

Imagine the routine had this code, instead:

  void foo (int *x) {
    if (*x != *x) {
    {
      return;
    }
    bar();
    return;
  }
wouldn't you expect the compiler to apply the same optimizations? Or would you be upset that eliding the check broke some code that depended on a race condition somewhere else in your program?

Also, pointing out that the "value is not 0 (which is what the test equates to)" is a non-sequitur. During compilation the literal 0 can behave as a NULL pointer constant. But the machine representation of a NULL pointer does not need to be all-bits 0, and such machine still exist today. And usually, as in this case, the distinction is irrelevant. It doesn't matter that the 0th page is mappable on your hardware. What matters is that the C specification says that a NULL pointer cannot be dereferenced; that dereferencing a NULL pointer is non-sense code.

There's an argument that compilers should be careful about the optimizations they make. Not all programs are correct, and taking that presumption too far can be detrimental. But it's not always trivial to implement an optimizing compiler to "do what I say, not what I mean". Optimizations depend on the soundness of being able to apply deductive logic to a program--that is, being able to string together a series of simple predicates to reach a conclusion about program behavior. You often have to add _more_ complexity to a compiler to _not_ optimize certain syntactic constructs. Recognizing the larger construct, especially only the subset that are pathological, without optimizing the ones everybody expects to actually be optimized, can be more difficult than simply applying a series of very basic deductive rules. So it's no wonder that most compiler implementations, especially high-performance compilers, tend to push back on this front.

What would be nice is for compilers to attempt to generate diagnostics when they elide code like that. An optimizer needs to be 100% correct all the time, every time. A diagnostic can be wrong some amount of time, which means it's easier to implement and the implementation of a particular check doesn't ripple through the entire code base.

GCC and clang implement many good diagnostics. But with -Wall -Wextra they also tend to generate alot of noise. Nothing is more annoying than GCC or clang complaining about perfectly compliant code for which there's no chance of it hiding a bug. For example, I used to often wrote initializer macros like:

  #define OPTIONS_INIT(...) { .foo = 1, .bar = 3, __VA_ARGS__ }
  struct options {
    int foo;
    int bar;
  };
allowing applications to have code like:

  struct options opts = OPTIONS_INIT(.bar = 0);
But with -Wall GCC and clang will complain about the second .bar definition overriding the first. (Because the macro expands to { .foo = 1, .bar = 3, .bar = 0 }). The C specification guarantees in no unambiguous terms that the last definition of .bar wins. And presumably they guarantee that precisely to make writing such macros feasible. I've never once had a problem with unintentionally redefine a struct field in an initializer list. Yet GCC and clang are adamant about complaining. It's so annoying especially because 1) there's absolutely nothing wrong with the code and 2) disabling the warning requires a different flag for clang than for GCC.

(I realize that for such option types you usually want define the semantics so that the default, most common value is 0. But it's not always desirable, and certainly not always practical, to be able to stick that mode. And that's just one example of that construct.)

Re: I Do Not Know C: Short quiz on undefined behavior (2015)

#53
post #50

Isn't this line from #3, undefined behavior not mentioned in the article (sequence point violation) zp++ = xp + *yp;

That's not a sequence point violation. The C standard makes it clear that zp gets xp + *yp prior to the increment. Quoting 6.5.2.4

> The result of the postfix ++ operator is the value of the operand. After the result is obtained, the value of the operand is incremented. (That is, the value 1 of the appropriate type is added to it.) See the discussions of additive operators and compound assignment for information on constraints, types, and conversions and the effects of operations on pointers. The side effect of updating the stored value of the operand shall occur between the previous and the next sequence point.

The last sentence is key.

Re: I Do Not Know C: Short quiz on undefined behavior (2015)

#55
post #39

Earlier quoted context omitted.

If you are going to do theorem proving, you should try to only prove true theorems.

If you want to phrase it like that, a compiler tries to prove conjectures and performs actions (usually code and data elimination) based on whether it can prove them or their negatives. Sometimes it can't do either. I don't see where you're going, though.

It's easy to see the problem in the null pointer case. The compiler deduction is that the null test is redundant, but it's not actually redundant. Therefore the compiler "proves" a false theorem. That the standards rules permit the compiler to deduce false things would be, in normal engineering analysis, considered to show a failure in the rules, but the bureaucratic mindset holds that the rules are always, by definition, correct, so the failure is the fault of the miscreant who neglected to staple cover sheet properly.

If the compiler is unable to prove a transformation preserves correctness, it should not do the transformation.

To your point below: The compiler is definitely not "forced" to assume that the pointer is not null - that is a choice made by the compiler writers. Even the ridiculous standard does not require the compiler writer to make that assumption. The compiler can simply compile the code as written - or, if it is smart enough to see the problem - it can produce a warning.

Re: I Do Not Know C: Short quiz on undefined behavior (2015)

#56

Honestly, Optimizing compilers will kill C. It killed the one thing C was good at - simplicity (you know exactly what happens where, note I'm not saying speed, as C++ can be quite a bit faster than C). Now, due to language lawyering, you can't just know C and your CPU, you have to know your compiler (and every iteration of it!). And if you slip somewhere, your security checks blow up ( http://blog.regehr.org/archives…

If you do know your compiler and your CPU (singular), you're probably not really programming C.

Conversely, if you maintain software that compiles on a bunch of compilers, operating systems and architectures (particularly little endian + big endian, 32 bit + 64 bit), then it's probably written in something rather like C. A lot of people do this.

Re: I Do Not Know C: Short quiz on undefined behavior (2015)

#57
post #39

Earlier quoted context omitted.

If you want to phrase it like that, a compiler tries to prove conjectures and performs actions (usually code and data elimination) based on whether it can prove them or their negatives. Sometimes it can't do either. I don't see where you're going, though.

It's easy to see the problem in the null pointer case. The compiler deduction is that the null test is redundant, but it's not actually redundant. Therefore the compiler "proves" a false theorem. That the standards rules permit the compiler to deduce false things would be, in normal engineering analysis, considered to show a failure in the rules, but the bureaucratic mindset holds that the rules are always, by defini…

> The compiler deduction is that the null test is redundant, but it's not actually redundant.

No. The compiler is forced to assume x isn't null, because int y = *x; has no meaning iff x IS null, so the compiler can't possibly generate any code to cover that case. There's no definition of that construct for the compiler to work off of that could possibly allow x to be null.

Blame the standard if you want, but you can't blame the compiler for not generating code to cover behaviour that you've made up in your head.

Re: I Do Not Know C: Short quiz on undefined behavior (2015)

#58
post #17

Earlier quoted context omitted.

I don't think #2 has been fully beaten to death yet. Assuming a platform where you don't segfault (say that 'page 0' variables are valid) and thus runtime does proceed; I still can't think of any /valid/ reason to eliminate the if that follows (focus line 2 in the comments). Under what set of logic does being able to de-reference a pointer confer that it's value is not 0 (which is what the test equates to)? In my opi…

C programmers expect dead code removal. Especially when the compiler also inlines functions (and, of course, inlining makes the biggest impact on short functions; and one way to get short functions is to have aggressive dead code removal). And macros can expand into very weird, but valid, code; so the statement that "nobody would ever write code like that" isn't relevant. The compiler may well have to handle unnatura…

C programmers should be able to expect that "optimizations" will not transform program meaning. And because C is so low level, certain types of optimizations may be more difficult or impossible. If the pointer was explicitly set to NULL, the compiler can justifiably deduce the branch will not be taken but the deduction "if the programmer dereferenced the pointer it must not be NULL" is not based on a sound rule. In fact, the whole concept that the compiler can make any transformation it wants in the presence of UB is wacky. Optimization should always be secondary to correctness.

Re: I Do Not Know C: Short quiz on undefined behavior (2015)

#59
post #28

My 'favourite' bit of surprising (not undefined) behaviour I've seen recently in the C11 spec is around infinite loops, where void foo() { while (1) {} } will loop forever, but void foo(int i) { while (i) {} } is permitted to terminate...even if i is 1: > An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and pe…

[deleted]
Post reply on HN