[LLVMdev] optimization assumes malloc return is non-null

[Jonathan S. Shapiro]

On Thu, 2008-05-01 at 09:57 -0400, David Vandevoorde wrote:
> > 1. There is an observably linear chain of calls to malloc() in the
> > example, and because of the structure of the example, the compiler can
> > see that there are no *unobserved* calls to malloc() in the program.
> 
> (You meant "no *observed*", right?)

I think I mean "unobserved". The requirement here seems to be that the
compiler has to know that no call to malloc() exists someplace else in
the overall program that might rely on the side effects of a malloc()
call performed in the current compilation unit. Unless the compiler can
determine this, or can show that no such side effects exist, then the
internal side effects are not provably unwitnessed.

If I am reading the standard correctly, merely having an unused result
is insufficient to permit deleting the call. Any side effects of the
call that are witnessed must still be performed. It is clearly legal to
perform them directly rather than by calling malloc() if the malloc()
result is unused, but the side effects of the malloc() call cannot
simply disappear if later code may exist that observes those effects.

But see below, because I think your "malloc from alternate heap"
argument is also relevant.

> > Just to cement my understanding, I suspect that *either* of the
> > following two changes to the sample code would make this optimization
> > invalid:
> >
> >  1. Rename main() to f()
> >
> >  2. Introduce a call to some external procedure anywhere in main().
> >
> > In either case, the compiler can no longer witness all reachable calls
> > to malloc(), and must assume conservatively that the internally  
> > produced
> > side effect results of malloc() may be sourced by other units of
> > compilation, and therefore cannot be elided.
> >
> > Is this correct?
> 
> 
> I'm of the opinion that even with such changes the optimization is  
> valid.  Let me rename main to f (and drop the unused parameters) and  
> add calls to a function g.  The original example is then:
> 
> 	#include <stdlib.h>
> 
> 	int f() {
> 	  g();
> 	  if (malloc(sizeof(int)) == NULL) { return 0; } else { return 1; }
> 	  g();
> 	}
> 
> The malloc value cannot escape and the allocated storage isn't used  
> (in other words, it can be "garbage collected" right away).  So it can  
> be replaced by a unique address (though the same address can be used  
> for each invocation, IMO).
> 
> Note that within the confines of the C (or C++) standard, g has no way  
> of observing the result of the call to malloc. (We might "know" that  
> there is a static-lifetime variable somewhere that changed, but that  
> variable isn't required by the standard, and a compiler may instead  
> posit that for this very call to malloc, a separate heap is used.)

I agree that g() cannot observe the malloc return value, but g() *can*
observe the side effect on the heap bound pointer. It is not sufficient
under the standard for the compiler to assume that g() **might not** do
so. It is required that the compiler demonstrate that g() **does not in
fact** do so.

Or are you arguing that since malloc() is a built-in procedure, the
compiler is entitled to substitute an alternate implementation of
malloc() when it observes that the return pointer is not captured (and
therefore cannot be handed back to free() or realloc()?) and that once
it does this, it is entitled to reason about this call to malloc()
without regard to any other call to malloc()? This would effectively
constitute built-in knowledge of a two-heap implementation, and I concur
that that would be within bounds according to the standard.

> My view is that the storage only becomes  
> an object when the pointer returned is bound to a typed pointer  
> (7.20.3/1).

I see where you are going, but I might be careful about this one.
Binding to a void* pointer is sufficient to be able to observe pointer
non-uniqueness, because it is legal to compare void * values for
equality. In light of which, I am inclined to think that the returned
value has to be unique if it is captured, without regard to the type of
the capturing pointer.

> See above.  If the allocation is small enough that it can be modelled  
> by a "reserved heap", I think it can.

Both small enough and partially evaluable at compile time, I should
think. This would preclude certain non-freed return results from
malloc() within loops, for example.

But basically I agree.

> > Daveed: Thanks for being patient on this. I appreciate your  
> > willingness
> > to help me see this one.
> 
> No problem at all.  I should probably worry that I find ISO exegesis  
> mildly fun :-P

Not to worry. If the bottom falls out of the software market you have a
promising second career opportunity as an orthodox rabbi. :-)

Thanks again.


shap