On 2 Oct 2012, at 03:40, Nick Lewycky wrote:> As far as I know, this optimization is legal. Fix the test with a volatile pointer:Why would that be required? malloc() is defined by the standard to return a pointer that is distinct from any other valid pointer, or NULL. Any optimisation that makes any assumptions about its next value is invalid.> int main() { > volatile char *curr; > > do { > curr = malloc(1); > int i = *curr;This, in particular, looks very wrong. If curr is void, then you are dereferencing an invalid pointer, and so you are doing something undefined. In fact, this version of the code is completely free to elide the conditional loop, because by dereferencing the pointer you are asserting that it is not NULL (or, at least, that if it is then after this point the program is in an undefined state and so any behaviour is legal) and so it is completely free to generate the code that it in fact does generate without this test. So here we have another bug, because the testq in your output is redundant after the movb. David
David Chisnall wrote:> On 2 Oct 2012, at 03:40, Nick Lewycky wrote: > >> As far as I know, this optimization is legal. Fix the test with a volatile pointer: > > Why would that be required?It isn't. My suggestion for fixing the test is to make use of the returned pointer in a fashion that the compiler is forbidden to elide it: make it an observable side-effect using volatile. Another way would be to take the pointer and print it to file or stdout. Perhaps you can think of others. malloc() is defined by the standard to return a pointer that is distinct from any other valid pointer, or NULL. Any optimisation that makes any assumptions about its next value is invalid. Nowhere do we make assumptions about malloc's next value. This is a straight-forward application of the as-if rule. The malloc call behaves as-if it allocated memory. Because we prove that the code doesn't use that memory, we can get away with allocating no memory at all and not change the behaviour of the program. But we did change the behaviour of the program, didn't we? Well, we haven't changed the behaviour of the program in any way that is observable through a well-defined mechanism. Crashes, running out of memory, or asking the kernel for your processes' memory usage isn't behaviour you get to rely on. The first two really aren't defined in the language, and the last one goes through I/O which is permitted to do its own thing. (For instance, we don't forbid constant-folding "1+1" because a program may fopen and disassemble itself to look for the "add 1, 1" instruction.)>> int main() { >> volatile char *curr; >> >> do { >> curr = malloc(1); >> int i = *curr; > > This, in particular, looks very wrong. If curr is void, then you are dereferencing an invalid pointer, and so you are doing something undefined.Do you mean, if curr is NULL? It's a char*, not void*. In fact, this version of the code is completely free to elide the conditional loop, because by dereferencing the pointer you are asserting that it is not NULL (or, at least, that if it is then after this point the program is in an undefined state and so any behaviour is legal) and so it is completely free to generate the code that it in fact does generate without this test. So here we have another bug, because the testq in your output is redundant after the movb. Yes, good point, I totally missed the NULL dereference. I haven't checked what happens if you write: curr = malloc(1); if (curr) int i = *curr; but I expect that would work. Nick
I've sent this issue to some friends on the C++ committee. The first response I received indicates that the person thinks the optimizer is within it's rights to optimize away the call to malloc. Here are some points, extracted from the response: "There is no observable behavior (a technical term in the standard) that violates requirements of the standard. In particular, malloc in the abstract machine defined by the standard need not ever fail." "On linux in particular, malloc (almost) never fails, because Linux does not actually make malloc'd memory available until it is used. Here the allocated memory is never used, so if the compiler recognizes malloc as a standard library function with well-defined semantics, it can eliminate the actual call and pretend it succeeded. Since variable curr is not visible outside main and is not declared volatile, it can be optimized away." On 10/02/2012 02:12 AM, Nick Lewycky wrote:> David Chisnall wrote: >> On 2 Oct 2012, at 03:40, Nick Lewycky wrote: >> >>> As far as I know, this optimization is legal. Fix the test with a >>> volatile pointer: >> >> Why would that be required? > > It isn't. My suggestion for fixing the test is to make use of the > returned pointer in a fashion that the compiler is forbidden to elide > it: make it an observable side-effect using volatile. Another way would > be to take the pointer and print it to file or stdout. Perhaps you can > think of others. > > malloc() is defined by the standard to return a pointer that is > distinct from any other valid pointer, or NULL. Any optimisation that > makes any assumptions about its next value is invalid. > > Nowhere do we make assumptions about malloc's next value. > > This is a straight-forward application of the as-if rule. The malloc > call behaves as-if it allocated memory. Because we prove that the code > doesn't use that memory, we can get away with allocating no memory at > all and not change the behaviour of the program. > > But we did change the behaviour of the program, didn't we? Well, we > haven't changed the behaviour of the program in any way that is > observable through a well-defined mechanism. Crashes, running out of > memory, or asking the kernel for your processes' memory usage isn't > behaviour you get to rely on. The first two really aren't defined in the > language, and the last one goes through I/O which is permitted to do its > own thing. (For instance, we don't forbid constant-folding "1+1" because > a program may fopen and disassemble itself to look for the "add 1, 1" > instruction.) > >>> int main() { >>> volatile char *curr; >>> >>> do { >>> curr = malloc(1); >>> int i = *curr; >> >> This, in particular, looks very wrong. If curr is void, then you are >> dereferencing an invalid pointer, and so you are doing something >> undefined. > > Do you mean, if curr is NULL? It's a char*, not void*. > > In fact, this version of the code is completely free to elide the > conditional loop, because by dereferencing the pointer you are asserting > that it is not NULL (or, at least, that if it is then after this point > the program is in an undefined state and so any behaviour is legal) and > so it is completely free to generate the code that it in fact does > generate without this test. So here we have another bug, because the > testq in your output is redundant after the movb. > > Yes, good point, I totally missed the NULL dereference. I haven't > checked what happens if you write: > > curr = malloc(1); > if (curr) > int i = *curr; > > but I expect that would work. > > Nick
On 10/2/2012 4:12 AM, Nick Lewycky wrote:> > This is a straight-forward application of the as-if rule. The malloc > call behaves as-if it allocated memory. Because we prove that the code > doesn't use that memory, we can get away with allocating no memory at > all and not change the behaviour of the program.Are you saying that we do this kind of an analysis at -O2? This could only work if the entire program was contained in a single source file, and even then it would require interprocedural analysis to get it right. -K -- Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation