You need to put some bounds on what optimizations are allowed to do.... So, if you propose to drop that notion, you have to propose something else that still lets us be confident that the compiled program will do what we want it to do, without having to inspect its assembly code.
I agree there should be bounds on what optimizations are allowed to do. The problem is that present discussions are focused on determining the circumstances where optimization may be observably affect the behavior of a program, while failing to recognize any limits as to what may happen when such situations arise.
Returning to the endless loop example, suppose a program is subject to the following constraints:
- It should behave usefully when possible ('should' rather than 'must' to avoid having to precisely define "when possible").
- When it can't fulfill its primary purpose, it must behave in a fashion that is at worst tolerably useless.
If receipt of a certain input causes a program to get stuck in an endless loop, that might render the entire execution useless, but generally not intolerably worse than useless. If one gives a compiler carte blanche to behave in arbitrary fashion if a program's inputs would cause it to get stuck in an endless loop with no side effects, then the only way to meet requirements would be to ensure that every potentially-endless loop has side effects. If instead one allows that a compiler may defer or omit the execution of certain loops without regard for whether they terminate, without granting special permission in cases where they do not, then compilers would be able to exploit such license much more often within correct programs.
As another example, consider something like:
struct string63 { char st[64]; } x,y;
void test(unsigned number)
{
struct string63 temp;
sprintf(temp.st, "%u", number);
x = temp;
y = temp;
}
Following a call test(23), what if anything should be guaranteed about the last 60 bytes of x.st and y.st? One could interpret the Standard as saying that behavior is undefined because code copies temp before all portions thereof have been written, but requiring that a programmer assign values to every byte of temp before copying it would hardly make the code more efficient. If one didn't regard the above as invoking UB, however, the fact that an Indeterminate Value is "either an unspecified value or a trap representation" would imply that code must behave as though it stores the same 64 byte values to x and y.
Suppose instead one allowed a compiler to, at its leisure, omit actions that would copy parts of an automatic object whose value is indeterminate. The effects of such an optimization may be observable if e.g. a program were to store different values into x.st[63] and y.st[63], call test(23), and then compare x.st[63] and y.st[63]. If, however, the fact that the values are different would not prevent a program from satisfying its application requirements, then both the program and optimization should be regarded as correct despite the fact that the optimization affected program behavior.
Putting it differently: clearly a compiler that permits the three optimizations I used in my blog post is bogus. I can change program behavior in a way that the final program does not what the programmer intended it to do. How do you propose we make sure that the compiler is not bogus, if not by saying "it must not change program behavior"?
First of all, I think the integer-to-pointer casts are a needless complication. Both clang and gcc will perform the "optimization" even if all such casts are removed.
Otherwise, I'd suggest that it may be appropriate to have multiple ways of comparing pointers, which the utility generating LLVM code could select based upon its semantic requirements:
-
Most strongly specified would say that if two pointers identify the same address, they must compare equal, and if they don't they must not, but an implementation may not observably use possibly-coincidental equality to justify assumptions about the sets of objects that are reachable using the pointers. This should generally be the default.
-
Next would say that if two objects are based on different allocations but have the same address, each individual action that compares them may arbitrarily report them equal or unequal, but generated code must behave in a fashion consistent with each individual determination. If generated code decides they are never equal, and thus omits the comparison and code which would performs some action as a result of them comparing equal, it would be entitled to ignore the possibility of such action occurring; if, however, it generates code which would perform some action if the pointers compare equal, it must allow for the possibility that the action might occur.
-
Weakest would be to say that if a block of code will only be executed if pointers are compared and found to be equal, a compiler may within that block regard them as freely substitutable. This appears to be what clang and gcc actually do.
Each stage would allow some optimizations that would be precluded by the one above, but the later forms would be inadequate for some tasks.
This is called non-determinism , and it is a crucial tool to avoid overconstraining a specification.
In order to support it, however, an abstraction model needs to recognize the concept at a fundamental level. I'm not sure whether it is clearer, however, to say that if x holds Indeterminate Value and y, z1, and z2 are all automatic objects whose address has not been observed, then y = (x & 3) + (x & 9); z1=y; z2=y; would set y, z1, and z2 to the non-deterministic union of values {0,1,2,3,4,8,9,10,11,12}, or whether it would be clearer to say that a compiler may at its leisure process each assignment by either computing some value and storing it, or by causing the target to be treated as a symbolic shorthand for the right-hand expression, but with x replaced by "any value"). The two descriptions would both allow for the same behaviors, but I think it would be much easier to validate a compiler design against the latter description.
