llvm dev - May 2008 - [LLVMdev] optimization assumes malloc return is non-null

On Wednesday 30 April 2008 17:26, David Vandevoorde wrote:
> >> ...malloc() is not specified to access a volatile
> >> object, modify an object, or modifying a file (directly or
> >> indirectly); i.e., it has no side effect from the language point
of
> >> view.
> >
> > Daveed:
> >
> > Good to know that I was looking at the correct section. I do not agree
> > that your interpretation follows the as-if rule, because I do not
> > agree
> > with your interpretation of the C library specification of malloc().
>
> Before I go on, let me state that this is not a contentious issue
> among WG14: There is no doubt that the intent of the standard is that
> this be a valid optimization.
Maybe I missed something, but aren't we all talking about the wrong thing 
here?  It seems to me that this isn't about side effects, it's about the
return value of malloc.  Why can LLVM assume malloc will always return 
non-zero?

                                                -Dave

On Wed, 2008-04-30 at 18:17 -0500, David A. Greene
wrote:
> On Wednesday 30 April 2008 17:26, David Vandevoorde wrote:
> 
> > >> ...malloc() is not specified to access a volatile
> > >> object, modify an object, or modifying a file (directly or
> > >> indirectly); i.e., it has no side effect from the language
point of
> > >> view.
> > >
> > > Daveed:
> > >
> > > Good to know that I was looking at the correct section. I do not
agree
> > > that your interpretation follows the as-if rule, because I do not
> > > agree
> > > with your interpretation of the C library specification of
malloc().
> >
> > Before I go on, let me state that this is not a contentious issue
> > among WG14: There is no doubt that the intent of the standard is that
> > this be a valid optimization.
> 
> Maybe I missed something, but aren't we all talking about the wrong
thing
> here?  It seems to me that this isn't about side effects, it's
about the
> return value of malloc.  Why can LLVM assume malloc will always return 
> non-zero?
I hope that Daveed will correct me on this, but I think that the theory
is as follows:

  Since the effect of malloc is not captured, the entire malloc can be
  discarded. Any call to malloc that is discarded can be presumed
  (arbitrarily) to succeed, and therefore to return non-null.

shap

On Apr 30, 2008, at 7:17 PM, David A. Greene wrote:
> On Wednesday 30 April 2008 17:26, David Vandevoorde wrote:
>
>>>> ...malloc() is not specified to access a volatile
>>>> object, modify an object, or modifying a file (directly or
>>>> indirectly); i.e., it has no side effect from the language
point of
>>>> view.
>>>
>>> Daveed:
>>>
>>> Good to know that I was looking at the correct section. I do not  
>>> agree
>>> that your interpretation follows the as-if rule, because I do not
>>> agree
>>> with your interpretation of the C library specification of
malloc().
>>
>> Before I go on, let me state that this is not a contentious issue
>> among WG14: There is no doubt that the intent of the standard is that
>> this be a valid optimization.
>
> Maybe I missed something, but aren't we all talking about the wrong  
> thing
> here?  It seems to me that this isn't about side effects, it's
about
> the
> return value of malloc.  Why can LLVM assume malloc will always return
> non-zero?
It cannot assume that in the general case.  It can do so here because  
the return value is not used further on.  The side effects issue comes  
about because the compiler needs to know that the call to malloc was  
not observable other than through the return value.  To re-quote a  
part of 5.1.2.3/3: "An actual implementation need not evaluate part of  
an expression if it can deduce that its value is not used and that no  
needed side effects are produced".  So there are two conditions to  
optimize this: Track the return value to make sure nothing interesting  
(i.e., unknown) happens to it, and be sure that there are no  
observable side effects from the call itself (in this case, take  
advantage of the fact that "malloc" is part of the language  
implementation).

Note that more interesting optimizations are possible.  E.g., it's  
perfectly valid to transform:

	void f(size_t n) {
	  char *str = (char*)malloc(n);
	  // use str[0 .. 99 ]
	  free(str);
	}

into

	void f(size_t n) {
	  char *str = (char*)alloca(n);
	  // use str[0 .. 99 ]
	}

(Can LLVM do that?  Is that maybe why the optimization happens?)

	Daveed

Never mind -- this argument is okay as far as it goes, but I don't think
Daveed is relying on this.

On Wed, 2008-04-30 at 20:47 -0400, Jonathan S. Shapiro
wrote:
> I hope that Daveed will correct me on this, but I think that the theory
> is as follows:
> 
>   Since the effect of malloc is not captured, the entire malloc can be
>   discarded. Any call to malloc that is discarded can be presumed
>   (arbitrarily) to succeed, and therefore to return non-null.
> 
> shap
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Apr 30, 2008, at 8:47 PM, Jonathan S. Shapiro wrote:
> On Wed, 2008-04-30 at 18:17 -0500, David A. Greene wrote:
>> On Wednesday 30 April 2008 17:26, David Vandevoorde wrote:
>>
>>>>> ...malloc() is not specified to access a volatile
>>>>> object, modify an object, or modifying a file (directly or
>>>>> indirectly); i.e., it has no side effect from the language
point
>>>>> of
>>>>> view.
>>>>
>>>> Daveed:
>>>>
>>>> Good to know that I was looking at the correct section. I do
not
>>>> agree
>>>> that your interpretation follows the as-if rule, because I do
not
>>>> agree
>>>> with your interpretation of the C library specification of  
>>>> malloc().
>>>
>>> Before I go on, let me state that this is not a contentious issue
>>> among WG14: There is no doubt that the intent of the standard is  
>>> that
>>> this be a valid optimization.
>>
>> Maybe I missed something, but aren't we all talking about the wrong
>> thing
>> here?  It seems to me that this isn't about side effects, it's
>> about the
>> return value of malloc.  Why can LLVM assume malloc will always  
>> return
>> non-zero?
>
> I hope that Daveed will correct me on this, but I think that the  
> theory
> is as follows:
>
>  Since the effect of malloc is not captured, the entire malloc can be
>  discarded. Any call to malloc that is discarded can be presumed
>  (arbitrarily) to succeed, and therefore to return non-null.

Correct.  It's an extreme form of garbage collection, I suppose ;-)

(In theory, it can also be assumed to fail -- because an  
implementation is allowed to make any call to malloc fail -- though  
that's probably not useful.)

	Daveed

On Wed, 30 Apr 2008, David Vandevoorde wrote:
> Note that more interesting optimizations are possible.  E.g., it's
> perfectly valid to transform:
>
> 	void f(size_t n) {
> 	  char *str = (char*)malloc(n);
> 	  // use str[0 .. 99 ]
> 	  free(str);
> 	}
>
> into
>
> 	void f(size_t n) {
> 	  char *str = (char*)alloca(n);
> 	  // use str[0 .. 99 ]
> 	}
>
> (Can LLVM do that?  Is that maybe why the optimization happens?)
This isn't safe in general unless you can (tightly) bound "n". 
You don't
want to overflow the stack.

We do delete "free(malloc(n))" though.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/

On Thursday 01 May 2008 02:57, David Vandevoorde wrote:
> > Maybe I missed something, but aren't we all talking about the
wrong
> > thing
> > here?  It seems to me that this isn't about side effects, it's
about
> > the
> > return value of malloc.  Why can LLVM assume malloc will always return
> > non-zero?
> 
> It cannot assume that in the general case.  It can do so here because  
> the return value is not used further on.
But it _is_ used to decide what value to return, right?
And this return value sure as hell can affect what will happen
in callers. By assuming arbitrary malloc implementation
you basically can return 0 or 1 value, arbitrarily, here!
This sounds very wrong.
--
vda