[nlewycky]

Hi! I'm a former compiler engineer who specialized on undefined behaviour.

Would you like warnings on:

   * int f(int x, int y) { return x + y; }
   * int get_x_coord(Point *p) { return p->x; }
   * void compute_and_cache(const char *key) { *get_cache_bucket_for(key) = compute_value_for(key); }

I'm curious, what would you do with a warning on every load or store through a pointer?

On the flip side, I can offer -fsanitize=undefined which will catch when you do many things that have UB at runtime. It does not change the ABI which means that there are some bugs it can't catch, but deploying it is easier since you do not need to recompile all your libraries with it (like your C++ standard library and C library, in particular). You can use this to help you build unit tests that send intentionally overflowing values into your functions and show that they do not overflow. It turns untestable problem (since you cannot check for UB after it happens) into a problem you can write deterministic tests for.

[wrs]

The problem isn’t overflow, the problem is the backwards logic of the compiler assuming there will never be any execution that leads to overflow, so the code that overflows just vanishes completely.

In other words,

    bool overflowed = (x+1)<x;

should be meaningful. It may or may not do what you want on any given architecture, but it shouldn’t just be assumed false.

[dzaima]

How about if the x+1 was from an inlined function? a macro? perhaps even just a variable defined 10 lines up?

In a 7-character sequence it may seem pretty obvious that it's probably intended to mean something, but when joining together multiple independent things doing redundant operations it's much less trivial.

    int game_logic(int prev_score, int bonus) {
      if (bonus < 0) { // check for bad argument
        return -1;
      }
      int new_score = prev_score + bonus;
      // ...
      if (new_score < prev_score) { // sanity check
        abort();
      }
      return new_score;
    }
    // in the above the abort path can (and is) already optimized out, but an invocation of game_logic(x,1) becomes exactly x+1<x

[nlewycky]

    bool overflowed = (x+1)<x;

I was convinced that some warning, probably -Wtautological-compare, already handled this and I plugged it into godbolt to see which one, but got no warnings with either gcc or clang. Frankly, I'm stunned and even a bit annoyed. Clearly this code deserves a warning, unless there's some good reason I'm just blind to right now.

Nevertheless, I don't know what to do about the suggestion "it may or may not do what you want on any given architecture, but it shouldn’t just be assumed false." The compiler needs to know what it can and can't do. The common advice of "just do what the CPU does" doesn't work, we need to know what to do when cross-compiling, when constant folding, and we need to know which instructions are valid to select. If I selected PADDSW for this add (a saturating addition operation) but then later when you use x+1 I select a non-saturating addition, would you be happy with that? Probably not. The compiler needs actual rules to follow.

I don't know how to apply the suggestion about warnings when we end up deleting dead code. The compiler deletes dead code all the time, consider a case like "vector<t> v; v.push_back(a); v.push_back(b);", each push_back begins with an if-statement on whether reallocation is required, and that becomes constant with inlining. Tracking "this code became dead because", well, because which situations exactly?

[wrs]

Cross-compiling is irrelevant, because if the behavior is processor-specific then the cross-compiler knows the behavior. Constant folding shouldn’t happen in this case because x is not constant. If you choose a saturating add consistently on this processor target, and document it, that’s fine.

Deleting dead code because the code demonstrably wouldn’t do anything (that is, it has defined behavior that is not observable) makes sense and is of course hugely useful. Deleting code that isn’t dead, it just doesn’t have a universally defined behavior, is the issue.

[nlewycky]

> Deleting code that isn’t dead, it just doesn’t have a universally defined behavior, is the issue.

Can I delete "if (x & 3 == 16)" without a warning? There is no 'x' which makes that expression true, so I can safely fold it to false without a warning?

Can I delete "if (x + 1 < x)" without a warning? There is no signed 'x' which makes that expression true, so I can safely fold it to false without a warning?

How about this:

    int x = 7;
    call_function_outside_this_file();
    if (x != 7) { /* dead */ }

Does deleting the code require a warning or no?

Or this:

    void f(int *x, float *y) {
      *x = 1;
      *y = 2;
      if (*x != 1) { /* dead */ }

A float cannot alias an int, so '*x' can not have changed. Warning or no?

The problem with UB is that you can use it to set up impossible situations, like create an 'x' where x & 3 == 16 is true or a variable whose address was never taken being modified through a pointer, and so on. If you account for UB then "code that doesn't have a universally defined behaviour" becomes all code.

Ideally I think the first two examples should have warnings, though not because we delete the code, and the last two shouldn't? The warning should be because it's a tautology so the human likely didn't mean to write that (for instance if the human wrote it indirectly through macros, then we shouldn't warn on it).

[wrs]

You’re on to something with that last example. The idea that those two pointers can’t alias is one place C has diverged from my understanding. Of course they can alias. Which is why I wouldn’t naturally write that code, I’d write:

    void f(int *px, float *py) {
        int x = *px;
        x = 1;
        *y = 2;
        if (x != 1) { /* dead */ }
        *px = x;

If I put in a dereference, I expect a dereference to happen. Not dereferencing the pointer when I wrote a dereference operator seems like going too far. If they aren’t supposed to alias, but they did anyway, the code should do the wrong thing, in a way that makes sense based on the code I wrote.

I’m obviously just a holdover from the 90s, but it does seem we’ve leaned too far into hidden assumptions that the compiler thinks I share, rather than doing what the code says, or a simplification of what the code says.

[nlewycky]

> If I put in a dereference, I expect a dereference to happen. Not dereferencing the pointer when I wrote a dereference operator seems like going too far.

Surely not? I mean, you probably didn't intend to include unevaluated contexts like "sizeof(ptr)" where putting in a memory access is forbidden, but I think nearly-all programmers fully expect the compiler to delete the dead store in "ptr = a; ptr = b;" or "ptr = x; free(ptr);" and would get annoyed if it didn't. Especially if we can't just take a scalar computation in a loop, move the memory access to register, then store it to memory only once when we're done.

I once did a cleanup of undefined behaviour dereferencing NULL pointers (-fsanitize=null) and I got a lot of pushback from people complaining about "&ptr" where the ptr is NULL, because the compiler doesn't emit any assembly for that, so their code is just fine as is.

The rule for memory is that all memory you've stored to has an effective-type -- same as the static types but for addresses at runtime -- and a pointer has to point to an object with the effective-type matching the pointer's static type. Further details aside (uninitialized pointers, pointers to data you just freed, freshly malloc'd memory which has no effective type yet, unions) when you think of it in this model, the fact you can't have an int and float* pointing to the memory feels natural.

[mjevans]

If code is dead or unreached, and therefore deleted / no instructions emitted; clearly THAT is of a level a warning should cover, if not an error.

[nlewycky]

Dead code happens all the time. Adjusting the example in my comment you're replying to:

    vector<t> v;
    v.push_back(a);
    v.push_back(b);
    v.push_back(c);
    v.push_back(d);

Let's suppose the definition of our vector here looks something like this:

    template <typename T> struct vector<t> {
      size_t len = 0;
      size_t storage_len = 0;
      T *storage = nullptr;

      void push_back(T t) {
        if (len + 1 > storage_len) {
          storage_len = storage_len ? storage_len * 2 : 1;
          storage = realloc(storage, storage_len);
        }
        storage[len] = t;
        ++len;
      }
    };

So here's what happens.

    vector<t> v;
    v.push_back(a);
    v.push_back(b);
    v.push_back(c);
    v.push_back(d);

becomes

    len = 0;
    storage_len = 0;
    storage = nullptr;

    if (len + 1 > storage_len) {
      storage_len = storage_len ? storage_len * 2 : 1;
      storage = realloc(storage, storage_len);
    }
    storage[len] = a;
    ++len;

    if (len + 1 > storage_len) {
      storage_len = storage_len ? storage_len * 2 : 1;
      storage = realloc(storage, storage_len);
    }
    storage[len] = b;
    ++len;

    if (len + 1 > storage_len) {
      storage_len = storage_len ? storage_len * 2 : 1;
      storage = realloc(storage, storage_len);
    }
    storage[len] = c;
    ++len;

    if (len + 1 > storage_len) {
      storage_len = storage_len ? storage_len * 2 : 1;
      storage = realloc(storage, storage_len);
    }
    storage[len] = d;
    ++len;

becomes

    len = 0;
    storage_len = 0;
    storage = nullptr;

    if (0 + 1 > 0) {
      storage_len = 1;
      storage = realloc(storage, 1);
    }
    storage[0] = a;
    len = 1;

    if (1 + 1 > 1) {
      storage_len = 2;
      storage = realloc(storage, 2);
    }
    storage[1] = b;
    len = 2;

    if (2 + 1 > 2) {
      storage_len = 4;
      storage = realloc(storage, 4);
    }
    storage[2] = c;
    len = 3;

    if (3 + 1 > 4) {
      storage_len = 8;
      storage = realloc(storage, 8);
    }
    storage[3] = d;
    len = 4;

In that last one, you can see that the if-expression is false and the body becomes dead code. If I understand the rule you're proposing, you want to get a warning or error for that?

[mjevans]

As a hypothetical, lets assume there's a compiler that has a deep transformation around alloc/reallocs to optimize them when they're only fed 'static' input sizes.

    // Source by nlewycky
    template <typename T> struct vector<t> {
      size_t len = 0;
      size_t storage_len = 0;
      T *storage = nullptr;

      void push_back(T t) {
        if (len + 1 > storage_len) {
          // FIXME: what if storage_len > (size_t_max >> 1) ??
          // ? Define maximum expected growth unit? 1K? 4K? 64K?
          // Assignment from trinary op visually confusing, add ( )
          storage_len = ( storage_len ? storage_len * 2 : 1 );
          storage = realloc(storage, storage_len);
        }
        storage[len] = t;
        ++len;
      }
    };
    // 
    vector<t> v;
    v.push_back(a);
    v.push_back(b);
    v.push_back(c);
    v.push_back(d);

After inlining all 4 times, the compiler might notice that in this code section vector<t> v always reaches the final size of storage = realloc(storage, 8); and optimize for that.

    // Pseudo code
    template <typename T> vector<T> v = {
      // final state at end of code section
      size_t len = 4;
      size_t storage_len = 8;
      T *storage = realloc(NULL, storage_len);
    };
    // Compiled and included, forgot template function syntax.
    void template <typename T> vector<T>.push_back(T t);
    (v[0], v[1], v[2], v[3]) = (a, b, c, d);

Even in this case, all the code the programmer wrote was evaluated and had side effects at least once at compile time. No code was eliminated as unreachable / impossible to reach. Instead it was optimized into operations that would always occur, barring realloc failure (which wasn't specified in the toy source, but would probably be a fatal error).

[mjevans]

No, because the code as it was written is still evaluated and executed. Said execution happened to become static at the time the program was compiled and 3 out of the 4 times it was executed an effect and binary output was generated.

In all the cases that the hypothetical -Wubelim would cover the written code would be evaluated by the compiler and 'as it's undefined it can't ever be true, silent elimination'. That's the case where the human that wrote the code and the compiler that's interpreting a specification to claim that code can't ever do anything. Rather than transliterate the code as it was written to the machine instructions the programmer probably expected to see were this native machine assembly they'd written, the compiler behaved differently, silently.

[zzo38computer]

I think the -fwrapv switch in GCC allows this to work properly. I don't actually know about this specific case, but -fwrapv makes signed and unsigned arithmetic to wrap around so that only the appropriate number of low bits are kept.

(I commonly use -fwrapv when writing programs in C.)

[mjevans]

Different levels of warnings might be useful.

-Wub # Warn _anytime_ there is detected potential undefined behavior, irrespective of if there is an associated optimization.

-Wubelim # Warn any time code is eliminated as a result of undefined behavior / assumptions.

-Wub... # Any other classes of UB optimizations that change the program as (incorrectly) written.

Again, the goal is to provide feedback that improves the program and possibly educates / reminds the programmer about how their meanings might be misunderstood.

[nlewycky]

> -Wub # Warn _anytime_ there is detected potential undefined behavior, irrespective of if there is an associated optimization.

Can I ask you, have you tried any existing tools? Coverity static analysis, Klocwork, PVS-Studio, clang static analysis, tis-interpreter, Frama-C? What did you think of those? If not, why not (how important is the problem to you)?

My understanding of these tools is that they start by marking every spot potential UB could happen -- every add is potentially overflowing, every pointer dereference is potentially null or freed or whatnot, and then they use solvers to prove that the UB does not occur, and print out the rest. The benefit they have is that they can examine more than one file at a time (the compiler may only look at one .c file at a time) and they have permission to take much longer than compiling.

> -Wubelim # Warn any time code is eliminated as a result of undefined behavior / assumptions.

This doesn't happen, the compiler doesn't detect your UB and use that to delete your code. Consider this:

    int x = 4;
    int y;
    int *p = &y - sizeof(int);
    *p = 7;
    printf("%d", x);

The compiler sees 'x' mentioned in two places, once where it's defined, and once where it's used (picture the compiler building up a graph of places a values is set (definitions) and places the value is used, the use-def graph) and replaces the print with "printf("%d", 4);", then since 'x' is dead it can be deleted entirely. The rest of the code with 'y' and 'p' executes exactly in the way the programmer wrote it, we keep 'y' on the stack, and make 'p' a pointer out of bounds by computing the address that is 4 below 'y' and writing sizeof(int) bytes representing the value 7 there. We don't really go out of our way to detect UB.

Another way to think about it is that the assumptions we make about your program being free of UB are completely indistinguishable from all the rest of the correct and working code. "int x = 4;" should declare a new variable, named x, with an int's worth of memory, initialized to the value 4. That is precisely as true to the compiler as any UB-performing, code. When you write "p->xcoord" you are telling the compiler that 'p' is a valid pointer to an object of its type at this moment, and it believes you. Trust the programmer, and all that.

> -Wub... # Any other classes of UB optimizations that change the program as (incorrectly) written.

"UB optimizations" isn't a thing. It just isn't. The optimizations never change the program, at least, not unless the compiler is buggy. The compiler's job is to find some assembly which meets the specification we call the program. With the optimizer enabled, we spend more time so that we can select assembly that minimizes a cost model we have for the execution time on the underlying machine (or sometimes file size).

> Again, the goal is to provide feedback that improves the program and possibly educates / reminds the programmer about how their meanings might be misunderstood.

FWIW we agree on the goal.

The model for warnings in clang at least has been to look at the code as it is typed, and focus on errors that programmers make. We have all kinds of complex rules for warnings, like "if (3 < 4)" issues a warning (-Wtautological-compare) but "if (MAX_THREADS < MAX_CORES)" with #define MAX_THREADS 3 and #define MAX_CORES 4 doesn't. We've put a ton of effort into getting this sort of thing right, and that includes warnings that code will always produce UB when run, even if it was expanded through macros or templates. It's not an exhaustive system, the warnings work was guided by actual bugs we've encountered in real systems.

There might be another way to do this. The C++ constexpr feature has the compiler evaluate some functions at compile time and detect any UB they encounter as they run. The clang implementation of this can also handle working with values that are not known at compile time, and working with dynamic allocations. One could try to run every function with the constexpr evaluator and see whether it does a better job at producing good warnings, then remove the redundant warnings (made by pattern matching on the AST) and see if the result is fast enough to use as part of regular compilation.

[SleepyMyroslav]

>int *p = &y - sizeof(int);

Funny how arguing about UB shows that even compiler writers can miss when they are juggling with lots of sharp objects :) There is no way you meant to write integer pointer value - 4 if your intent was 'next to it'. And double the fun is that some future hardware may do sizeof(int) == 1 and have it running 'just fine' :)

As gamedev engine person doing bugs all the time I wish we had some middle ground but a lot of smart people do not want to find it. I guess it is cheaper that way when we just build on the existing C code and hope for the best.

[mjevans]

I've forgotten if 'address of' ( & ) is signed or unsigned. Worse, in a quick search online I can't seem to find anyplace that mentions what the return type of address of is, just a bunch of basic working with pointers pages.

The pointer math line should still be legal, even if it would be 'unsafe' in some popular other languages. Useful for determining where to write to memory mapped files or IO. Not so useful in the above case.

The warnings/errors I'd expect would be: *p = 7; // out of known bounds write

[nlewycky]

> I've forgotten if 'address of' ( & ) is signed or unsigned.

Neither, pointers are their own types which have no sign, only integral types come in signed and unsigned. There exist intptr_t (signed) and uintptr_t (unsigned) which are integral types you can losslessly cast a pointer to. Also the difference of two pointers is a ptrdiff_t which is a signed integral type.

> The warnings/errors I'd expect would be: *p = 7; // out of known bounds write

In that regard I picked a bad example, this code always executes undefined behaviour, so this could indeed be detected by a compiler warning at the cost of doing a simulated execution of the code. Most real problems come about where the code is UB only for certain runtime inputs.

The reason I chose that example was to make a point about how the compiler doesn't realize it's doing anything to "change" the program, and isn't going out of its way to optimize based on undefined behavior. It assumes that a local variable's value can't change with it being assigned to, so how could it know whether to issue the warning?

Another way to put it is:

    void written_in_asm_in_another_file();
    void test() {
        int x = 4;
        written_in_asm_in_another_file();
        printf("%d", x);
    }

The function written in asm might go up the stack to find caller's stack frame and search for the 0x00000004 and change it to a different value. Is the compiler forbidden to replace printf("%d", x); with printf("%d", 4);? Is the compiler allowed to, but required to emit a warning? Are we required to have a 4 on the stack as opposed to keeping it only in registers?

> The pointer math line should still be legal, even if it would be 'unsafe' in some popular other languages.

I'm not sure what you mean by "should", you might be suggesting a change to C or you might be stating what you think the code currently does. Right now in C, the very creation of an invalid pointer is UB whether you use the thing or not. I'm told this is because of very old CPU designs that had distinct pointer and integer registers and loading an invalid address into the pointer register would trap.

[int_19h]

I wouldn't like warnings for these things. I'd like them all to trap in a well-defined (but non-recoverable) way if UB actually gets triggered. And I'd like this to be the default behavior, even in release builds. Safety should never be opt-in.

[nlewycky]

I can offer you -fsanitize=undefined -fsanitize-trap=undefined, which you'd need to put in your configuration for release builds, presumably you have other flags in your build system (like -O2) already.

It's possible that a program terminating based on attacker influenced values could be used as a channel to leak confidential data to the attacker, so I'd suggest that developers decide whether to use this on a case-by-case basis. (Maybe it should default to on, but we'd need user education so people who are building sensitive systems know they need to turn it off.)