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

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

Sorry, for j
On Thu, May 1, 2008 at 1:16 PM, David Vandevoorde
<daveed at vandevoorde.com> wrote:
>
>  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.)
But this reduction depends on knowledge of the malloc implementation,
which no one has confirmed is actually the case here.

On Wed, Apr 30, 2008 at 10:21 PM, Chris Lattner <sabre at nondot.org>
wrote:
>  LLVM should not (and does not, afaik) assume the malloc succeeds in
>  general.
>
>  If LLVM is able to eliminate all users of the malloc assuming the
>  malloc succeeded (as in this case), then it is safe to assume the malloc
>  returned success.
I don't see how this could be true in general, without either
knowledge of the malloc implementation, which would be fine, or
presuming knowledge of the target, which would not be fine. If
"malloc(sizeof(int))" were changed to "malloc(3245677423)",
would it
still be eliminated?

Sandro

On May 1, 2008, at 3:30 PM, Sandro Magi wrote:
> Sorry, for j
> On Thu, May 1, 2008 at 1:16 PM, David Vandevoorde
> <daveed at vandevoorde.com> wrote:
>>
>> 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.)
>
> But this reduction depends on knowledge of the malloc implementation,
> which no one has confirmed is actually the case here.
Not really, because the implementation doesn't get called.  Another  
way of thinking about it is as follows: Let __general_malloc be the  
"normal implementation of malloc".  Then the compiler replaces that  
implementation by

	inline void *malloc(size_t n) {
	  if (this_one_special_call_site()) {
	    static byte buf[n] __attribute((most_aligned));
	    return (void*)buf;
	  } else {
	    return __general_malloc(n);
	  }
	}


> On Wed, Apr 30, 2008 at 10:21 PM, Chris Lattner <sabre at nondot.org>
> wrote:
>> LLVM should not (and does not, afaik) assume the malloc succeeds in
>> general.
>>
>> If LLVM is able to eliminate all users of the malloc assuming the
>> malloc succeeded (as in this case), then it is safe to assume the  
>> malloc
>> returned success.
>
> I don't see how this could be true in general, without either
> knowledge of the malloc implementation, which would be fine, or
> presuming knowledge of the target, which would not be fine. If
> "malloc(sizeof(int))" were changed to
"malloc(3245677423)", would it
> still be eliminated?

That's a good question.  More specifically, does the _language_ allow  
the optimization if I ask for so much storage that the address space  
could not possibly accommodate an object of the given size "disjoint  
from any other object" (words of 7.20.3/1)?  My view is that yes this  
is allowed, because the words in 7.20.3/1 only require that for an  
_object_ associated with that storage, which doesn't exist here  
because the address is never used to create a non-opaque pointer.

Here is 7.20.3 for reference:

"The order and contiguity of storage allocated by successive calls to  
the calloc, malloc, and realloc functions is unspecified. The pointer  
returned if the allocation succeeds is suitably aligned so that it may  
be assigned to a pointer to any type of object and then used to access  
such an object or an array of such objects in the space allocated  
(until the space is explicitly deallocated). The lifetime of an  
allocated object extends from the allocation until the deallocation.  
Each such allocation shall yield a pointer to an object disjoint from  
anyother object. The pointer returned points to the start (lowest byte  
address) of the allocated space. If the space cannot be allocated, a  
null pointer is returned. If the size of the space requested is zero,  
the behavior is implementation-defined: either a null pointer is  
returned, or the behavior is as if the size were some nonzero value,  
except that the returned pointer shall not be used to access an object."

Admittedly, that argument is weaker than for small bounded allocations  
where hypothetical addresses can just be stolen from non-data pages.

	Daveed

On Thu, 1 May 2008, Sandro Magi wrote:
>>  If LLVM is able to eliminate all users of the malloc assuming the
>>  malloc succeeded (as in this case), then it is safe to assume the
malloc
>>  returned success.
>
> I don't see how this could be true in general, without either
> knowledge of the malloc implementation, which would be fine, or
> presuming knowledge of the target, which would not be fine. If
> "malloc(sizeof(int))" were changed to
"malloc(3245677423)", would it
> still be eliminated?
Would it cause your head to explode if you knew that llvm optimizes this:

static char* G;
void foo() {
   G = malloc(sizeof(char));
}
char get() { return *G; }
void set(char x) { *G = x; }

into this (note the lack of malloc):

@G.body = internal global i8 undef		; <i8*> [#uses=2]
define i8 @get() signext nounwind  {
entry:
 	%tmp2 = load i8* @G.body, align 1		; <i8> [#uses=1]
 	ret i8 %tmp2
}
define void @set(i8 signext  %x) nounwind  {
entry:
 	store i8 %x, i8* @G.body, align 1
 	ret void
}
define void @foo() nounwind  {
entry:
 	ret void
}

?

This is safe even without "whole program" information.  I love the
as-if
rule ;-)

-Chris

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