>>>>> On Mon, 1 Oct 2012 19:40:58 -0700, Nick Lewycky <nlewycky at google.com> said:> On 1 October 2012 18:34, reed kotler <rkotler at mips.com> wrote: > This code is essentially from an LTP test ( > http://ltp.sourceforge.net/ ). > #include <stdlib.h> > int main() { void *curr; > do { curr = malloc(1); } while (curr); > return 0; > } > If you compile it with no optimization, it will keep the > malloc calls. > If you compile it with -O2, it will create an infinite > loop, i.e. assuming that malloc always returns a non zero > result and the result is not used. Nick> As far as I know, this optimization is legal. Well, indeed the result is used by the while and we have a control dependence on the future execution. The termination or not of the program is a side effect from the user perspective. [...] Nick> Oh how people don't appreciate the luxury of having an Nick> infinite memory machine! You have also a potentially infinite loop, which is another kind of luxury. More boring, especially on the end. :-) Even if you have a lazy allocation as with the default libC on Linux that allocates the memory pages only on demand, the memory will blow up just because the malloc() library itself has to track the allocations for a potential future free(). Of course, if you have an infinite memory, you can avoid implementing free() or your interprocedural analysis may prove you do not call free() in your program. :-) This makes me feel uncomfortable to have this kind of optimizations with too many hypothesis on the run-time, even if it addresses domains not well captured by the norm... How to know about the real target? It may be another allocation library, some LD_PRELOAD hack to insert memory verification code or at the end the code is to be run inside a tool like valgrind to track this very malloc() bug that would be hidden by this optimization... :-( Just to give an example from another compiler, in the PIPS source-to-source compiler the side effect of malloc() is taken into account by registering a write effect on an abstract location which is tested later by some optimization phases to avoid too much liberal optimizations, like the one above. Anyway, this is an interesting limit case to discuss tonight at the LLVM Bay-area Social. :-) -- Ronan KERYELL |\/ Phone: +1 408 658 9453 SILKAN Wild Systems |/) 4962 El Camino Real #201 K Ronan.Keryell at silkan.com Los Altos, CA 94022 |\ skype:keryell USA | \ http://silkan.com
They have been discussing this for a solid two days on the C committee list with many pro and con opinions, all supported by various parts of the standard or other sources. My personal opinion is that it's only a bug if some real program can be made to fail because of this. If I were writing this test case for LPT, I would call an external function and pass the value curr to it. If I was really paranoid about compiling it with an -O4 compiler, I would write an assembly language program. Back in the day, in the ACVS (Ada compiler validation suite), they used to call functions that were noops but that had some complex recursion that no compiler could unwind and realise that it was a noop. So that is probably the safest. I can't remember anymore the exact form of these recursive functions in the suite as it was 28 years ago that I worked with that suite. On 10/04/2012 04:21 PM, Ronan Keryell wrote:>>>>>> On Mon, 1 Oct 2012 19:40:58 -0700, Nick Lewycky <nlewycky at google.com> said: > > On 1 October 2012 18:34, reed kotler <rkotler at mips.com> wrote: > > This code is essentially from an LTP test ( > > http://ltp.sourceforge.net/ ). > > > #include <stdlib.h> > > int main() { void *curr; > > do { curr = malloc(1); } while (curr); > > return 0; > > } > > > If you compile it with no optimization, it will keep the > > malloc calls. > > > If you compile it with -O2, it will create an infinite > > loop, i.e. assuming that malloc always returns a non zero > > result and the result is not used. > > Nick> As far as I know, this optimization is legal. > > Well, indeed the result is used by the while and we have a control > dependence on the future execution. The termination or not of the > program is a side effect from the user perspective. > > [...] > > Nick> Oh how people don't appreciate the luxury of having an > Nick> infinite memory machine! > > You have also a potentially infinite loop, which is another kind of > luxury. More boring, especially on the end. :-) > > Even if you have a lazy allocation as with the default libC on Linux > that allocates the memory pages only on demand, the memory will blow > up just because the malloc() library itself has to track the allocations > for a potential future free(). Of course, if you have an infinite > memory, you can avoid implementing free() or your interprocedural > analysis may prove you do not call free() in your program. :-) > > This makes me feel uncomfortable to have this kind of optimizations with > too many hypothesis on the run-time, even if it addresses domains not > well captured by the norm... > > How to know about the real target? It may be another allocation library, > some LD_PRELOAD hack to insert memory verification code or at the end > the code is to be run inside a tool like valgrind to track this very > malloc() bug that would be hidden by this optimization... :-( > > Just to give an example from another compiler, in the PIPS > source-to-source compiler the side effect of malloc() is taken into > account by registering a write effect on an abstract location which is > tested later by some optimization phases to avoid too much liberal > optimizations, like the one above. > > Anyway, this is an interesting limit case to discuss tonight at the LLVM > Bay-area Social. :-)
For what it's worth, I will be at the social tonight, and am happy to discuss this paper. I'm a co-author and the instigator the work here to clarify the spec and allow a large number of exciting optimizations on code that have previously not be employed merely because of the use of malloc rather than (for example) alloca. On Thu, Oct 4, 2012 at 4:40 PM, reed kotler <rkotler at mips.com> wrote:> They have been discussing this for a solid two days on the C committee > list with many pro and con opinions, all supported by various parts of the > standard or other sources. > > My personal opinion is that it's only a bug if some real program can be > made to fail because of this. > > If I were writing this test case for LPT, I would call an external > function and pass the value curr to it. > > If I was really paranoid about compiling it with an -O4 compiler, I would > write an assembly language program. > > Back in the day, in the ACVS (Ada compiler validation suite), they used to > call functions that were noops but that had some complex recursion that no > compiler could unwind and realise that it was a noop. So that is probably > the safest. I can't remember anymore the exact form of these recursive > functions in the suite as it was 28 years ago that I worked with that suite. > > On 10/04/2012 04:21 PM, Ronan Keryell wrote: > >> On Mon, 1 Oct 2012 19:40:58 -0700, Nick Lewycky <nlewycky at google.com> >>>>>>> said: >>>>>>> >>>>>> > On 1 October 2012 18:34, reed kotler <rkotler at mips.com> wrote: >> > This code is essentially from an LTP test ( >> > http://ltp.sourceforge.net/ ). >> >> > #include <stdlib.h> >> > int main() { void *curr; >> > do { curr = malloc(1); } while (curr); >> > return 0; >> > } >> >> > If you compile it with no optimization, it will keep the >> > malloc calls. >> >> > If you compile it with -O2, it will create an infinite >> > loop, i.e. assuming that malloc always returns a non zero >> > result and the result is not used. >> >> Nick> As far as I know, this optimization is legal. >> >> Well, indeed the result is used by the while and we have a control >> dependence on the future execution. The termination or not of the >> program is a side effect from the user perspective. >> >> [...] >> >> Nick> Oh how people don't appreciate the luxury of having an >> Nick> infinite memory machine! >> >> You have also a potentially infinite loop, which is another kind of >> luxury. More boring, especially on the end. :-) >> >> Even if you have a lazy allocation as with the default libC on Linux >> that allocates the memory pages only on demand, the memory will blow >> up just because the malloc() library itself has to track the allocations >> for a potential future free(). Of course, if you have an infinite >> memory, you can avoid implementing free() or your interprocedural >> analysis may prove you do not call free() in your program. :-) >> >> This makes me feel uncomfortable to have this kind of optimizations with >> too many hypothesis on the run-time, even if it addresses domains not >> well captured by the norm... >> >> How to know about the real target? It may be another allocation library, >> some LD_PRELOAD hack to insert memory verification code or at the end >> the code is to be run inside a tool like valgrind to track this very >> malloc() bug that would be hidden by this optimization... :-( >> >> Just to give an example from another compiler, in the PIPS >> source-to-source compiler the side effect of malloc() is taken into >> account by registering a write effect on an abstract location which is >> tested later by some optimization phases to avoid too much liberal >> optimizations, like the one above. >> >> Anyway, this is an interesting limit case to discuss tonight at the LLVM >> Bay-area Social. :-) >> > > ______________________________**_________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/**mailman/listinfo/llvmdev<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121004/bb1e3189/attachment.html>