Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Defining the Undefinedness of C (2015) [pdf]

fsl.cs.illinois.edu

Post reply on HN
Print view View original

11–20 of 91 posts

Re: Defining the Undefinedness of C (2015) [pdf]

#11

Post by iainmerrick »

xrange wrote: post #5
iainmerrick wrote: post #2

Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? It seems like problems crop up when you combine a fairly low-level language with an emphasis on performance, a specification that explicitly calls out implementation-defined and undefined semantics, and very highly optimizing compilers. None of the…

>Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? How similar is similar? Pascal? Ada? Spark Ada? Rust? Friendly C ( https://blog.regehr.org/archives/1180 )?

Yes, I'd say those are similar. Systems languages, no mandatory GC.

That Friendly C proposal is terrific, I'd dearly love to use that. Basically, use sane and conservative optimizations for most code, with the option of using aggressive optimizations for hotspots. Kind of similar to Rust -- mostly safe by default, more dangerous stuff available when you need it.

Re: Defining the Undefinedness of C (2015) [pdf]

#12

Post by simias »

iainmerrick wrote: post #7
simias wrote: post #4

Earlier quoted context omitted.

Any language which allows unprotected memory access will potentially have "undefined behaviour" if you start plowing through random addresses. Things like divisions by 0 are also commonly UB. Some CPU ABI even have instructions which, when used with certain operands, are undefined. For instance the ARM Thumb "BL" instruction is encoded as two successive "pseudo-instructions", IIRC if you break the pair the behaviour…

Yeah, it's not at all clear to me why so many things need to be undefined rather than implementation-defined.

It could let the compiler get rid of entire branches if it can statically assert than an overflow or other UB is guaranteed (assuming that it's not a coding error but that the check is done somewhere upstream and the branch would be unreachable).

That might seem a bit aggressive and risky but it's not rare to write funky macro code where you hope the compiler will be clever enough to get rid of the cruft.

One case I can come up with is if you have some code that does, say:

    int foo(int a) {
        int next = a + 1;

        return increment(a);
    }

    int increment(int a) {
        if (a == INT_MAX) {
            return 0;
        }

        return ++a;
    }
In this situation if the compiler inlines "increment" it can also get rid of the "if" because it can assume that it'll always be false. If it wasn't false then "int next = a + 1" triggers UB so the compiler can do whatever it wants.

Now, if this is an actual coding error, that's nasty. If however I wrote foo that way because I'm sure that "a" is a small integer with no risk of overflow then it's a fine optimization.

If overflow is implementation defined then the optimization is illegal, in case of overflow "next" is implementation defined but the test should run.

Note that here I put the "next = a + 1" before the call to increment, but it would still be a valid optimization if the call was done after the call to increment (with the original value of a, that is):

    int foo(int a) {
        int next, ret;

        ret = increment(a);

        next = a + 1;

        return ret;
    }
UB "travels backwards in time", so to speak. If the compiler knows for a fact that "a == INT_MAX" could cause an UB anywhere in the code, it has the right to assume that it can't happen if it allows him to optimize some more.

Re: Defining the Undefinedness of C (2015) [pdf]

#13

Post by iainmerrick »

raphlinus wrote: post #8
iainmerrick wrote: post #2

Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? It seems like problems crop up when you combine a fairly low-level language with an emphasis on performance, a specification that explicitly calls out implementation-defined and undefined semantics, and very highly optimizing compilers. None of the…

This is a really good question. Each language adopts its own philosophical stance on the matter. Java is an excellent example of a language that tries to minimize undefined behavior, as much as C maximizes it. Even in the case of data races, the range of machine behavior is quite constrained (it can't break type safety, for example). This approach has some cost in performance, but Java is still performant. We don't n…

I think Java is a terrific role model. Defining the multithreaded memory model was a long and painful process, but the end result is excellent.

It just doesn't quite fully fill the role of C for systems programming, as it uses GC rather than manual memory management.

Re: Defining the Undefinedness of C (2015) [pdf]

#14

Post by raphlinus »

iainmerrick wrote: post #11
xrange wrote: post #5

Earlier quoted context omitted.

>Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? How similar is similar? Pascal? Ada? Spark Ada? Rust? Friendly C ( https://blog.regehr.org/archives/1180 )?

Yes, I'd say those are similar. Systems languages, no mandatory GC. That Friendly C proposal is terrific, I'd dearly love to use that. Basically, use sane and conservative optimizations for most code, with the option of using aggressive optimizations for hotspots. Kind of similar to Rust -- mostly safe by default, more dangerous stuff available when you need it.

The Friendly C idea seems to be basically dead. For an update of what Regehr is pursuing now, see https://blog.regehr.org/archives/1520 (Undefined Behavior in 2017).

Re: Defining the Undefinedness of C (2015) [pdf]

#15

Post by the8472 »

iainmerrick wrote: post #2

Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? It seems like problems crop up when you combine a fairly low-level language with an emphasis on performance, a specification that explicitly calls out implementation-defined and undefined semantics, and very highly optimizing compilers. None of the…

Division by zero is UB. This lets the compiler assume it does not happen and thus it won't have to emit additional instructions to check for it.

To be eliminate the check at compile to it would have to be able to infer the range of the values of the divisor.

> and their compilers don't optimize as aggressively as GCC or Clang.

Some languages use GCC or LLVM as optimizing backends. So they can suffer from just the same UB if the language itself does not prevent it.

https://github.com/rust-lang/rust/issues/28728

Re: Defining the Undefinedness of C (2015) [pdf]

#16

Post by iainmerrick »

woodrowbarlow wrote: post #10
iainmerrick wrote: post #2

Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? It seems like problems crop up when you combine a fairly low-level language with an emphasis on performance, a specification that explicitly calls out implementation-defined and undefined semantics, and very highly optimizing compilers. None of the…

> is it something that any similar language would have to contend with? it's something any language could _potentially_ have to deal with. C's penchant for undefined behavior comes from two factors, i think: 1. it's ancient. we've learned a lot of lessons since its inception about how to design a language. it also comes from a time when CPU architectures varied wildly -- even within a given manufacturer's product lin…

by "safer C", i assume you're talking about the likes of rust et al.

I'm actually thinking of variants of C that allow existing code to be used with no or minimal modifications. The "Friendly C" proposal that another commenter linked to is a good example: https://blog.regehr.org/archives/1180

It seems like Rust is getting some traction, and that's great, but it's certainly not a drop-in replacement for C.

Re: Defining the Undefinedness of C (2015) [pdf]

#17

Post by smitherfield »

iainmerrick wrote: post #2

Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? It seems like problems crop up when you combine a fairly low-level language with an emphasis on performance, a specification that explicitly calls out implementation-defined and undefined semantics, and very highly optimizing compilers. None of the…

Yes, there are a number of optimizations that require UB, or something like it. For example, say you have this valid C or Rust code:

    if (my_signed_int + 1 > my_signed_int) {
            foo();
    }
Since signed integer overflow is UB in C, C compilers can optimize out the conditional, but since Rust specifies that overflow may wrap, the compiler can’t assume the condition is true.

Re: Defining the Undefinedness of C (2015) [pdf]

#18

Post by thesmithdynasty »

iainmerrick wrote: post #2

Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? It seems like problems crop up when you combine a fairly low-level language with an emphasis on performance, a specification that explicitly calls out implementation-defined and undefined semantics, and very highly optimizing compilers. None of the…

One word, portability. Since C is relatively low level, allows direct access to mem, primitive types correspond to actual machine types, etc. It can be crippling for a low level language that targets many many architectures to define undefined behavior. For example, it is undefined behavior to overflow a signed integer. Now, I can't think of a modern processor that doesn't use two's complement so this behavior is relatively well defined, but theoretically if there was a processor that doesn't use two's complement and signed integer overflow was well defined in C, then the compiler would have to insert a workaround which could hinder performance, have unintended side effects, or just be impossible to workaround. One of the best features of C is how portable it is, it is the defacto standard for any risc architecture, be it a tiny microcontroller or a beefy modern processor, a C compiler targets it. The cost of this portability is undefined behavior.

Re: Defining the Undefinedness of C (2015) [pdf]

#19

Post by fundabulousrIII »

iainmerrick wrote: post #2

Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? It seems like problems crop up when you combine a fairly low-level language with an emphasis on performance, a specification that explicitly calls out implementation-defined and undefined semantics, and very highly optimizing compilers. None of the…

Fortran...

Re: Defining the Undefinedness of C (2015) [pdf]

#20

Post by iainmerrick »

simias wrote: post #12
iainmerrick wrote: post #7

Earlier quoted context omitted.

Yeah, it's not at all clear to me why so many things need to be undefined rather than implementation-defined.

It could let the compiler get rid of entire branches if it can statically assert than an overflow or other UB is guaranteed (assuming that it's not a coding error but that the check is done somewhere upstream and the branch would be unreachable). That might seem a bit aggressive and risky but it's not rare to write funky macro code where you hope the compiler will be clever enough to get rid of the cruft. One case I…

So that "next = a + 1" is essentially a note to the compiler, promising that "++a" won't overflow?

To me that seems really reckless! If you need that note, make it a compiler pragma or something, rather than trying to sneak it in by repurposing some existing code.

Now if overflow were implementation-defined, the compiler would have to assume that INT_MAX + 1 wraps to INT_MIN (say). So as written, the "if (a == INT_MAX)" line would stay. That's what I would expect to happen on reading the code, and I'm confident that that's what most reasonable people would expect too.

If you want to skip the "if (a == INT_MAX)" check, just take it out.

I'm sure optimizations like this are important for squeezing a few extra percent out of the standard benchmarks. But for most ordinary programmers they're just a minefield you have to tiptoe carefully around.

Post reply on HN