5 ms·

Should a compiler be allowed to optimize: int x = 0; int y = 42; foo(&x); bar(y); to: int x = 0; foo(&x); bar(42); without perfo

Should a compiler be allowed to optimize: int x = 0; int y = 42; foo(&x); bar(y); to: int x = 0; foo(&x); bar(42); without performing analysis on foo? If so, how can that optimization be legal without UB?

anovikov 3y ago
How is this UB? foo() won't have any access to y so won't be able to modify it, so we can be more or less certain that y is still 42 when bar() is called? What is it that i'm missing?
- remexre 3y ago
  That's it -- the optimization is legal because there's no way foo() could modify y, because any (&x)[1] = 20 shenanigans would be UB. This is how UB is used in optimizations; it's (usually) not that the compiler is finding positions where UB occurs and explicitly choosing to perform mischief, it's performing a bunch of simple and obviously-what-you-want rewrites that are only correct because of UB; otherwise, arbitrary pointer writes are too powerful.
  - deleted 3y ago
    [deleted]
  - Dylan16807 3y ago
    UB is what allows `(&x)[1]` to happen at all. If you didn't have UB, there would be no reasonable way to allow code that messes up arbitrary pointers. A typical non-UB language wouldn't allow `(&x)[1]` and it would be easy to allow the optimization. It would be difficult or obtuse to design a non-UB language that doesn't allow optimizing y away.
    - remexre 3y ago
      Standard Forth, to my knowledge, doesn't have UB and consequently doesn't allow the optimization. That'd just be : foo CELL + 20 SWAP ! ; there. Machine languages also generally don't have this kind of UB, and don't allow the optimization. It's not impossible to imagine a C without UB, it's just not a particularly desirable language.
      - Jtsummers 3y ago
        The UB permits the optimization, but is not necessary for it. If a language had a stricter definition of pointer and memory access behavior then the optimization would still be applicable if it conformed to the assumption that people are making around the UB in C. UB is not necessary for optimization, it just permits some optimizations which may or may not be valid and may or may not be consistent across compilers and platforms because people get to fill in the gaps with whatever they want.
      - Dylan16807 3y ago
        Parameters don't really work the same way in Forth. A similar C program would explicitly pass in an entire stack every time it runs a function, or have a global stack variable. And such a C program would disallow the optimization whether or not you consider UB. Machine language means you have basically no rules imposed on your code at all. So it's true that you can't optimize anything, but I think that's outside the scope of normal language talk.
        remexre 3y ago
        In my example, the variables are assumed to be addressable, only the address of x was passed via the stack. Dunno what you mean about having no rules imposed on your code -- you can define the semantics of the language formally and execute them on a machine, same as you can for C, JavaScript, or Prolog.
        Dylan16807 3y ago
        > In my example, the variables are assumed to be addressable, only the address of x was passed via the stack. Yeah but I could add 3 billion to the pointer instead. Now what happens, if we're trying to define behavior? > you can define the semantics of the language formally If the semantics aren't a direct translation into CPU opcodes, then it's not machine code. And CPU opcodes can access all memory at all times including self-inspection so you can't change anything for optimization purposes without an additional framework on top.
- stouset 3y ago
  The biggest misunderstanding people have around UB is—in my experience—the (often) subconscious assumption that UB optimization is around optimizing the performance of code that exhibits UB. It is not. You're partially correct. foo() won't have any access to y so won't be able to modify it… unless foo() is written in way that exploits undefined behavior. Compilers can (and should) assume that foo() is not written pathologically in a way that writes into the frames of functions higher in the call stack, and so can make the above optimization.
kevin_thibedeau 3y ago
Y is never visible from foo()s scope. You'd have to employ ABI specific stack manipulation to get to it. Optimization in the outside frame doesn't depend on foo().
- tyler569 3y ago
  And that ABI specific stack manipulation would be UB, so the optimizer can assume it doesn't happen. With no UB, that's not true.
  - Dylan16807 3y ago
    You assume a langue without UB would allow stack manipulation. But then it would have to be defined. How would you possibly define it fully?
    - remexre 3y ago
      There's an area of memory into which variables with automatic storage duration are allocated at implementation-defined addrs, at any point exactly those variables have addresses.
      - Dylan16807 3y ago
        > at any point exactly those variables have addresses That doesn't sound like it lets me increment any stack address I want and store into the resulting pointer. And are return values still on the same stack? I probably should have said I meant the traditional kind of C stack.
        remexre 3y ago
        > That doesn't sound like it lets me increment any stack address I want and store into the resulting pointer. Why not? > And are return values still on the same stack? Other implementation-defined things might have addresses too, those things just aren't variables. I think you might be able to still allow inlining without UB if you make it implementation-defined per call-site what other things might get addresses.

anovikov 3y ago

How is this UB? foo() won't have any access to y so won't be able to modify it, so we can be more or less certain that y is still 42 when bar() is called? What is it that i'm missing?

remexre 3y ago
That's it -- the optimization is legal because there's no way foo() could modify y, because any (&x)[1] = 20 shenanigans would be UB. This is how UB is used in optimizations; it's (usually) not that the compiler is finding positions where UB occurs and explicitly choosing to perform mischief, it's performing a bunch of simple and obviously-what-you-want rewrites that are only correct because of UB; otherwise, arbitrary pointer writes are too powerful.
- deleted 3y ago
  [deleted]
- Dylan16807 3y ago
  UB is what allows `(&x)[1]` to happen at all. If you didn't have UB, there would be no reasonable way to allow code that messes up arbitrary pointers. A typical non-UB language wouldn't allow `(&x)[1]` and it would be easy to allow the optimization. It would be difficult or obtuse to design a non-UB language that doesn't allow optimizing y away.
  - remexre 3y ago
    Standard Forth, to my knowledge, doesn't have UB and consequently doesn't allow the optimization. That'd just be : foo CELL + 20 SWAP ! ; there. Machine languages also generally don't have this kind of UB, and don't allow the optimization. It's not impossible to imagine a C without UB, it's just not a particularly desirable language.
    - Jtsummers 3y ago
      The UB permits the optimization, but is not necessary for it. If a language had a stricter definition of pointer and memory access behavior then the optimization would still be applicable if it conformed to the assumption that people are making around the UB in C. UB is not necessary for optimization, it just permits some optimizations which may or may not be valid and may or may not be consistent across compilers and platforms because people get to fill in the gaps with whatever they want.
    - Dylan16807 3y ago
      Parameters don't really work the same way in Forth. A similar C program would explicitly pass in an entire stack every time it runs a function, or have a global stack variable. And such a C program would disallow the optimization whether or not you consider UB. Machine language means you have basically no rules imposed on your code at all. So it's true that you can't optimize anything, but I think that's outside the scope of normal language talk.
      - remexre 3y ago
        In my example, the variables are assumed to be addressable, only the address of x was passed via the stack. Dunno what you mean about having no rules imposed on your code -- you can define the semantics of the language formally and execute them on a machine, same as you can for C, JavaScript, or Prolog.
        Dylan16807 3y ago
        > In my example, the variables are assumed to be addressable, only the address of x was passed via the stack. Yeah but I could add 3 billion to the pointer instead. Now what happens, if we're trying to define behavior? > you can define the semantics of the language formally If the semantics aren't a direct translation into CPU opcodes, then it's not machine code. And CPU opcodes can access all memory at all times including self-inspection so you can't change anything for optimization purposes without an additional framework on top.
stouset 3y ago
The biggest misunderstanding people have around UB is—in my experience—the (often) subconscious assumption that UB optimization is around optimizing the performance of code that exhibits UB. It is not. You're partially correct. foo() won't have any access to y so won't be able to modify it… unless foo() is written in way that exploits undefined behavior. Compilers can (and should) assume that foo() is not written pathologically in a way that writes into the frames of functions higher in the call stack, and so can make the above optimization.

kevin_thibedeau 3y ago

Y is never visible from foo()s scope. You'd have to employ ABI specific stack manipulation to get to it. Optimization in the outside frame doesn't depend on foo().

tyler569 3y ago
And that ABI specific stack manipulation would be UB, so the optimizer can assume it doesn't happen. With no UB, that's not true.
- Dylan16807 3y ago
  You assume a langue without UB would allow stack manipulation. But then it would have to be defined. How would you possibly define it fully?
  - remexre 3y ago
    There's an area of memory into which variables with automatic storage duration are allocated at implementation-defined addrs, at any point exactly those variables have addresses.
    - Dylan16807 3y ago
      > at any point exactly those variables have addresses That doesn't sound like it lets me increment any stack address I want and store into the resulting pointer. And are return values still on the same stack? I probably should have said I meant the traditional kind of C stack.
      - remexre 3y ago
        > That doesn't sound like it lets me increment any stack address I want and store into the resulting pointer. Why not? > And are return values still on the same stack? Other implementation-defined things might have addresses too, those things just aren't variables. I think you might be able to still allow inlining without UB if you make it implementation-defined per call-site what other things might get addresses.