4 ms·

The presence of UB is not statically detectable. Global analysis may help, but it's probably reducible to the halting problem. (of course, you can detect some c

The presence of UB is not statically detectable. Global analysis may help, but it's probably reducible to the halting problem. (of course, you can detect some common mistakes, which is what many analysis tools do) UB is not a property of the local code. It's a property of the code and the values you feed to it. Without explicit annotations of contracts you won't be able to statically detect this for C/C++. At runtime UBSan exists to detect this.

kbenson 10y ago
This isn't about statically detecting undefined behavior in general, it's about using detected undefined behavior to make assumptions that don't play well with later stages in the optimization pipeline. Deciding that a statement must be true because otherwise it would contain undefined behavior (which is assuming the developer won't cause undefined behavior), and then using it's truthiness to elide the check the developer included to attempt to make sure they weren't causing undefined behavior is some contorted reasoning that I'm confident isn't something that compiler authors decided specifically should be included, but instead is an unfortunate interaction between two separate aspects of compilation.
- Manishearth 10y ago
  I don't think it's that clear cut. It's not "an unfortunate interaction between two separate aspects of compilation", it's how it's supposed to work -- the optimizer gathers invariants about the control flow and then makes optimizations based on it. The problem here is that the intent of the code is not something the optimizer can pick up on. Regular bounds check elimination works pretty much exactly the same way.
  - kbenson 10y ago
    There is a difference between whether something is an invariant based entirely on mathematical properties and rules that the compiler ensures, and one that also includes expected programmer behavior. In this case, the optimizer made an assumption that required the programmer to have ensured than an addition could not overflow, otherwise it would be undefined behavior. The compiler assuming that holds as true when it isn't necessarily so (and in this case was not so), is a problem. Optimizations that assume a programmer was diligent enough to follow those rules should not be attempted, period, if they result in the removal of some code (or possibly ever, just to be safe). That's not to say those optimization are forever lost to us. It just requires the programmer be more careful about the actions they take such that no assumptions need be made. For example, if you are adding two types which could cause an overflow, and overflows are undefined, you can cast and use larger types, or rely on compiler knowledge. Examples of that might be casting in the comparison or casting to larger types earlier on and not modifying it prior to comparison, in which case a sufficiently smart compiler might infer that since it was an unsigned char originally and you haven't modified it since you casted it to an unsigned int, while its type is actually an unsigned int, for comparisons of overflow detection for optimization you can treat it as an unsigned char.
    - Manishearth 10y ago
      I still don't think it's that clear cut, most optimizations are based on these assumptions, it's just that some assumptions are more reasonable than others. A lot of compilers do this to some extent already, avoiding using certain kinds of information for optimization even if they could.
      - kbenson 10y ago
        Sure, I'm specifically talking about assumptions that rest on programmers having followed some constraint purposefully. Humans are fallible, and if the compiler can't actually prove it, it shouldn't be taking any action that might remove statements. That's not to say programmers can't take steps to make it provable for the compiler.
        Manishearth 10y ago
        Right, my point is that most of the assumptions made are like that. Some are more obvious than others. Yes, this could help construct a "warn on assumption made" mode, but you'd likely be inundiated with a lot of mundane assumptions as well. You could filter by kind of assumption, but scary-ub-triggering assumptions like the one in the post happen all the time too, and they usually depend on the runtime properties of the program, which are hard to statically figure out. Basically, this is a very nontrivial problem, and quite likely intractable to solve in a way that doesn't produce a deluge of unnecessary info. (In the presence of annotations to help the compiler -- like the ISOC++ core guidelines -- the problem becomes significantly easier because you have local information on the runtime properties)
        kbenson 10y ago
        > Right, my point is that most of the assumptions made are like that. Some are more obvious than others. My argument is that any optimization that requires the compiler to infer intent rather than make concrete decisions based on known facts and this results in a change in the output of the program, then that is an optimization that is irresponsible to apply. The only part hard to know about this is how it affects execution, as the rest is already done currently. If that's too hard to determine, the correct stance is to disallow the optimization in that instance. It is not irresponsible to have undefined behavior that the programmer can leverage. It is not irresponsible to optimize out instructions that do not affect the result. It is irresponsible to allow undefined behavior, and then change the output based on how that undefined behavior is interpreted but only if a specific optimization is applied. Optimizations should never change deterministic output. Code that is non-deterministic purely because of undefined behavior needs to noted. That people have gotten used to some speed improvements at the expense of consistency, but not necessarily to their knowledge, is no excuse not to fix it. In many cases the code could be changed to once again take advantage of the same optimizations which are more strict, or to avoid undefined behavior. In this case, that would mean either casting to a type with defined overflow prior to addition or using a large data type to accumulate the values and test if it's too large. Neither of those allows the optimization, because that optimization is actually wrong in this case. In the cases where the optimization would be correct, correct use of types and casting should yield the same result. I would love to see a specific counter-example where this would be unworkable. I do not consider code having to be changed from what was previously a possible undefined behavior to definitively not undefined behavior as unworkable. I don't see how C could be considered a systems language without this. I understand how this is an unpopular stance with C programmers, but without it, there's actually a bunch of non-deterministic source code in the wile that's an allowed compiler tweak away from changing how it functions, not just what instructions it uses to achieve that function.

kbenson 10y ago

This isn't about statically detecting undefined behavior in general, it's about using detected undefined behavior to make assumptions that don't play well with later stages in the optimization pipeline. Deciding that a statement must be true because otherwise it would contain undefined behavior (which is assuming the developer won't cause undefined behavior), and then using it's truthiness to elide the check the developer included to attempt to make sure they weren't causing undefined behavior is some contorted reasoning that I'm confident isn't something that compiler authors decided specifically should be included, but instead is an unfortunate interaction between two separate aspects of compilation.

Manishearth 10y ago
I don't think it's that clear cut. It's not "an unfortunate interaction between two separate aspects of compilation", it's how it's supposed to work -- the optimizer gathers invariants about the control flow and then makes optimizations based on it. The problem here is that the intent of the code is not something the optimizer can pick up on. Regular bounds check elimination works pretty much exactly the same way.
- kbenson 10y ago
  There is a difference between whether something is an invariant based entirely on mathematical properties and rules that the compiler ensures, and one that also includes expected programmer behavior. In this case, the optimizer made an assumption that required the programmer to have ensured than an addition could not overflow, otherwise it would be undefined behavior. The compiler assuming that holds as true when it isn't necessarily so (and in this case was not so), is a problem. Optimizations that assume a programmer was diligent enough to follow those rules should not be attempted, period, if they result in the removal of some code (or possibly ever, just to be safe). That's not to say those optimization are forever lost to us. It just requires the programmer be more careful about the actions they take such that no assumptions need be made. For example, if you are adding two types which could cause an overflow, and overflows are undefined, you can cast and use larger types, or rely on compiler knowledge. Examples of that might be casting in the comparison or casting to larger types earlier on and not modifying it prior to comparison, in which case a sufficiently smart compiler might infer that since it was an unsigned char originally and you haven't modified it since you casted it to an unsigned int, while its type is actually an unsigned int, for comparisons of overflow detection for optimization you can treat it as an unsigned char.
  - Manishearth 10y ago
    I still don't think it's that clear cut, most optimizations are based on these assumptions, it's just that some assumptions are more reasonable than others. A lot of compilers do this to some extent already, avoiding using certain kinds of information for optimization even if they could.
    - kbenson 10y ago
      Sure, I'm specifically talking about assumptions that rest on programmers having followed some constraint purposefully. Humans are fallible, and if the compiler can't actually prove it, it shouldn't be taking any action that might remove statements. That's not to say programmers can't take steps to make it provable for the compiler.
      - Manishearth 10y ago
        Right, my point is that most of the assumptions made are like that. Some are more obvious than others. Yes, this could help construct a "warn on assumption made" mode, but you'd likely be inundiated with a lot of mundane assumptions as well. You could filter by kind of assumption, but scary-ub-triggering assumptions like the one in the post happen all the time too, and they usually depend on the runtime properties of the program, which are hard to statically figure out. Basically, this is a very nontrivial problem, and quite likely intractable to solve in a way that doesn't produce a deluge of unnecessary info. (In the presence of annotations to help the compiler -- like the ISOC++ core guidelines -- the problem becomes significantly easier because you have local information on the runtime properties)
        kbenson 10y ago
        > Right, my point is that most of the assumptions made are like that. Some are more obvious than others. My argument is that any optimization that requires the compiler to infer intent rather than make concrete decisions based on known facts and this results in a change in the output of the program, then that is an optimization that is irresponsible to apply. The only part hard to know about this is how it affects execution, as the rest is already done currently. If that's too hard to determine, the correct stance is to disallow the optimization in that instance. It is not irresponsible to have undefined behavior that the programmer can leverage. It is not irresponsible to optimize out instructions that do not affect the result. It is irresponsible to allow undefined behavior, and then change the output based on how that undefined behavior is interpreted but only if a specific optimization is applied. Optimizations should never change deterministic output. Code that is non-deterministic purely because of undefined behavior needs to noted. That people have gotten used to some speed improvements at the expense of consistency, but not necessarily to their knowledge, is no excuse not to fix it. In many cases the code could be changed to once again take advantage of the same optimizations which are more strict, or to avoid undefined behavior. In this case, that would mean either casting to a type with defined overflow prior to addition or using a large data type to accumulate the values and test if it's too large. Neither of those allows the optimization, because that optimization is actually wrong in this case. In the cases where the optimization would be correct, correct use of types and casting should yield the same result. I would love to see a specific counter-example where this would be unworkable. I do not consider code having to be changed from what was previously a possible undefined behavior to definitively not undefined behavior as unworkable. I don't see how C could be considered a systems language without this. I understand how this is an unpopular stance with C programmers, but without it, there's actually a bunch of non-deterministic source code in the wile that's an allowed compiler tweak away from changing how it functions, not just what instructions it uses to achieve that function.