Hacker News Reader

Comment by afdbcreid | Hacker News Reader

It is quite hard to come with a reliable example, but (https://c.godbolt.org/z/56bfYszEb):

    int* p = malloc(sizeof(int));
    int v = *p;
    if (!(v < 0 || v == 0 || v > 0)) {
        exit(1);
    }

This compiles into `exit(1)` in Clang under -O3.

View on HN

How? That doesn’t seem like it should be possible. Why is that?

Because it invokes UB.

Well, yes, but as a C decidedly-not-an-expert, I didn't understand what kind of UB it was invoking that could make all three of those expressions simultaneously false.

That is your mistake, right here. UB can cause everything, there does not need to be a "reason" or "kind of UB".

(If you are looking for an explanation how it happens in practice, see the other comment).

As I understand it, the compiler "knows" the range of valid values for a variable (for instance, if an int was promoted from an unsigned char, it knows it doesn't need to bother with testing for negative values). If the value came from uninitialised malloc'ed memory, the compiler knows that there are no valid values less than zero, no valid values directly equal to zero, and no valid values greater than zero - thus all three tests fail, and the overall negated test always succeeds!

The reasoning is roughly correct but range checking isn't what const-folding the comparisons into `false` (rather it's a special rule for LLVM's `undef`).

Because uninitialized memory isn't "it could be any possible value." Uninitialized memory is semantically an indeterminate value whose value is not guaranteed to be consistent between different reads of the value. Optimizations generally "choose" a value that is most convenient for eliminating code; for example, when comparing an indeterminate value to another value, it's easiest to "choose" one that makes the comparison just outright false. But these choices are not necessarily consistent between different uses of the value, since there's nothing to force the compiler to remember the value it chose.

(Note that it's not just the compiler that plays the game--a memory allocator might choose to use MADV_FREE for freed pages of memory, which means that at any point until its next write, the OS may replace the contents of the page with a zero page. So if a subsequent call to malloc reuses a MADV_FREE'd page, then reads of that data before anything it has been written to it may suddenly switch to a different value depending on the whims of the kernel.)

Ohhh, so it'd be kind of like the SQL

  (NULL < 0 || NULL == 0 || NULL > 0)

where even though it seems like one of those would have to be true, yet all 3 are individually unknown? Got it. Thanks for the explanation!

My knowledge of SQL NULL is rusty, but I think NULL is just plain unordered with respect to other values, more akin to a NaN value in floating-point than an indeterminate value.

Yeah, the details are a little different, but I think the concept's similar. Is null < 0? Uh, not sure. Is it equal to zero? No clue. Is it greater than 0? Can't tell. So, are any of those true? No way of knowing.

  SQLite-3.54 in-memory-> select NULL < 0 or NULL == 0 or NULL > 0;
  ╭──────────────────────╮
  │ NULL < 0 or NULL ... │
  ╞══════════════════════╡
  │ NULL                 │
  ╰──────────────────────╯

It's not the same. Maybe `NaN != NaN` (I don't know SQL enough to tell if `NULL != NULL`), but it can't be true that you observe `NaN == NaN` and then `!(NaN == NaN)`. With LLVM's `undef` this is entirely possible.

Though all of this explanation is only in LLVM IR level. In C, this is just UB and it is also possible that this will erase your hard drive.

Reply on news.ycombinator.com