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

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, 2008-04-30 at 21:01 -0400, David Vandevoorde
wrote:
> On Apr 30, 2008, at 8:47 PM, Jonathan S. Shapiro wrote:
> >  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.)
I think it cannot in general assume that in this case, for reasons
outlined in my other note.

On Wednesday 30 April 2008 20:01, David Vandevoorde wrote:
> 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.)
You just contradicted yourself.  If an implementation can return zero/null,
then the optimizer can't assume the direction of the branch in this case. 
It
has to allow the call to proceed and get the return value, unless it knows
about the specific implementation of malloc, which shouldn't be the case
for LLVM.

                                            -Dave

On May 1, 2008, at 12:47 PM, David Greene wrote:
> On Wednesday 30 April 2008 20:01, David Vandevoorde wrote:
>
>> 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.)
>
> You just contradicted yourself.  If an implementation can return  
> zero/null,
> then the optimizer can't assume the direction of the branch in this  
> case.  It
> has to allow the call to proceed and get the return value, unless it  
> knows
> about the specific implementation of malloc, which shouldn't be the  
> case
> for LLVM.


I don't see the contradiction.  Note that I'm only reasoning about the  
language; not specific implementations.

A valid implementation of malloc is "return 0;".  Therefore, a valid  
reduction of the original program is "int main() { return 0; }".   
However that is a reduction that posits an essentially useless malloc;  
so I'd be upset with my vendor if its C implementation behaved like  
that.  It's only a bit of trivia for language geeks.

(Much like a few years ago I frequently was told variations of "It  
isn't hard to write a 100% ISO-conforming C++ front end... in BASIC:
	10 PRINT "Out of resources"
	20 END
".)

Another valid implementation of malloc is one that actually returns a  
non-null pointer in this case, and for such an implementation, a valid  
reduction is "int main() { return 1; }".  That reduction is IMO not  
only valid, but also defensible and maybe desirable.  (And LLVM  
apparently does so.)

	Daveed