[LLVMdev] optimization assumes malloc return is non-null

[David Vandevoorde]

On May 1, 2008, at 12:26 AM, Chris Lattner wrote:
> 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.

Yes, that's what I was thinking.  In particular, I had hoped this  
could happen as the result of inlining certain constructor/destructor  
pairs; e.g.:

	... {
	  std::string s...
	}

(You'd also have to be able to limit the string length, but I think  
there are quite a few cases where that is doable.)

Unfortunately, I'd forgotten that the default allocator must use  
storage returned by ::operator new(std::size_t).


>  In this case, the alloca could even be
> a fixed alloca coded into the prolog of the function, not a dynamic
> alloca.

Right.

> 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.


That is indeed a real problem: Replacement "new" can have observable  
side-effects (such as writing to the console), and currently there is  
no latitude to elide those.

> 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.


Since TC1 (i.e., the 2003 standard) the following constraint exists  
(3.7.3.1/3):

	If the request succeeds, the value returned shall be a non-null  
pointer value (4.10) different from any previously returned value p1,  
unless that value p1 was since passed to an operator delete.

That's clearly not enough, but maybe one could argue that the missing  
bit is an oversight?  Have you talked to Howard Hinnant about this by  
any chance?  (Howard is Apple's J16 rep, and he is the library  
subgroup chair; this constraint was added at the request of the  
library subgroup)

>
> 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'.


The object lifetime rules (3.8 in the 2003 standard) enable that one I  
think.

> 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?


Well, the spec has to change ;-)  If we had talked about this two  
years ago, we'd be in much better shape to get that done for C++0x.   
Now, the committee is in wrap-up mode, and new proposals aren't very  
welcome.  The aliasing guarantees issue above (2) could conceivably be  
smuggled in as a defect report resolution ("it's not a new feature;  
it's a fix for a wording bug").

Item (1) (and (3), if needed) could gain some traction if a strong  
case could be made that this is a weakness vs. C in practice.  I.e.,  
you'd want to show a realistic C example and the corresponding C++  
example, and demonstrate that an existing "typical" optimizer (LLVM  
presumably) working on both versions delivers significantly better  
performance on the C version.

I think I've seen you post to the WG21+J16 reflector before?  If you  
have access to it, you could put out a feeler for this issue,  
including asking whether the lifetime optimization example (3 above)  
is valid in C++03 and/or C++0x (I believe there have been some changes  
in this area since C++03).

	Daveed