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

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 Apr 30, 2008, at 10:25 PM, Chris Lattner wrote:
> 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.
Ah yes, of course.  Does LLVM do this for known & small constant n?

(I suppose it could be transformed into:

	void f(size_t n) {
	  bool __opt = n < __L;
	  char *str = (char*)(opt ? alloca(n) : malloc(n));
	  // ...
	  if (!opt) free(str);
	}

The payoff is less obvious here.)
> We do delete "free(malloc(n))" though.
Cool.

	Daveed

On Apr 30, 2008, at 8:51 PM, David Vandevoorde wrote:
>> This isn't safe in general unless you can (tightly) bound
"n".  You
>> don't want to overflow the stack.
>
> Ah yes, of course.  Does LLVM do this for known & small constant n?
We don't do this currently, primarily because I haven't seen a case  
where it is a win yet: it would be very easy to do for some cases.   
The trick with this is that you have to prove a couple of interesting  
properties of the program.  For example, you effectively have to prove  
that the malloc can only be executed once for each invocation of the  
function.  You don't want to turn something like this:

for ()
   malloc(12)  // perhaps a linked list.

Into unbounded stack allocation (even though it would work as long as  
you don't run out of stack).

There are interesting cases that could be caught like:

for () {
   p = malloc(42)
   use(p);
   free(p);
}

etc, which could also be done.  In this case, the alloca could even be  
a fixed alloca coded into the prolog of the function, not a dynamic  
alloca.


Personally to me, I have a bigger axe to grind with C++ operator new.   
AFAIK, the standard doesn't give leeway to do a number of interesting  
optimizations for new/delete because the user is explicitly allowed to  
override them and the std doesn't require them to behave "as  
expected".  Very interesting properties to me would be:

1) Safety to remove "delete (new int);" and friends.
2) Aliasing guarantees about the result of new.  There are a huge  
number of code pessimizations that happen because the optimizer has to  
assume that 'new' can return a pointer that already exists in the  
program.
3) Lifetime guarantees.  It would be really nice to be able to delete  
the store to X in:  " double *X = ...; *X = 4.0; delete X;" which is  
safe with 'free'.

etc.  A lot of nice guarantees that we have with malloc/free aren't  
available with new/delete.  Also, since new/delete can be overridden  
at any time (as late as runtime with LD_PRELOAD and friends), there is  
really no way the compiler can assume anything spiffy about new/delete  
except with some magic "standards violation is ok" compiler option,  
which is gross.

Any thoughts on how to improve this situation?

-Chris