Optimizing of explicit temporary storage

Optimizing of explicit temporary storage

[Richard Guenther]

Is it legal for a conforming C++ compiler to optimize away storage 
allocation / deallocation?  Like in

#include <new>

void foo(void)
{
         int *x = new(std::nothrow) int;
         delete x;
}

is it allowed to kill the new and delete statements?  Would it be 
allowed to do this for the throwing version of new, too?

Thanks,
Richard.

Re: Optimizing of explicit temporary storage

[Mike Stump]

On Sunday, October 10, 2004, at 07:48  AM, Richard Guenther wrote:
> Is it legal for a conforming C++ compiler to optimize away storage 
> allocation / deallocation?  Like in
>
> #include <new>
>
> void foo(void)
> {
>         int *x = new(std::nothrow) int;
>         delete x;
> }
>
> is it allowed to kill the new and delete statements?  Would it be 
> allowed to do this for the throwing version of new, too?

The as if rule is fairly powerful...  If the resulting program behaves 
as if it had it, then the optimization is allowed.  I don't think 
memory consumption is an externally visible effect.  Now, we might need 
to do full program analysis to know which new is run, and to know its 
semantics; I don't recall if the user is prohibited from adding 
semantics to a new replacement function.

Re: Optimizing of explicit temporary storage

[Richard Guenther]

Mike Stump wrote:
> On Sunday, October 10, 2004, at 07:48  AM, Richard Guenther wrote:
> 
>> Is it legal for a conforming C++ compiler to optimize away storage 
>> allocation / deallocation?  Like in
>>
>> #include <new>
>>
>> void foo(void)
>> {
>>         int *x = new(std::nothrow) int;
>>         delete x;
>> }
>>
>> is it allowed to kill the new and delete statements?  Would it be 
>> allowed to do this for the throwing version of new, too?
> 
> The as if rule is fairly powerful...  If the resulting program behaves 
> as if it had it, then the optimization is allowed.  I don't think memory 
> consumption is an externally visible effect.  Now, we might need to do 
> full program analysis to know which new is run, and to know its 
> semantics; I don't recall if the user is prohibited from adding 
> semantics to a new replacement function.

Well, I was thinking of the traditional

struct Vector {
    Vector(int size);
    Vector operator*(const Vector&);
    Vector& operator=(const Vector&);
    double *storage;
};

and doing expressions like

Vector a,b,c;
a = b*c;

where one usually considers using expression templates because of the 
temporaries.  With loop fusion one could get the speed of the expression 
template code, but are you allowed to get rid of the temporaries (and 
their allocated memory), too?

Richard.

Re: Optimizing of explicit temporary storage

[Mark Mitchell]

Richard Guenther wrote:

> Mike Stump wrote:
>
>> On Sunday, October 10, 2004, at 07:48  AM, Richard Guenther wrote:
>>
>>> Is it legal for a conforming C++ compiler to optimize away storage 
>>> allocation / deallocation?  Like in
>>>
>>> #include <new>
>>>
>>> void foo(void)
>>> {
>>>         int *x = new(std::nothrow) int;
>>>         delete x;
>>> }
>>>
>>> is it allowed to kill the new and delete statements?  Would it be 
>>> allowed to do this for the throwing version of new, too?
>>
>>
>> The as if rule is fairly powerful...  If the resulting program 
>> behaves as if it had it, then the optimization is allowed.  I don't 
>> think memory consumption is an externally visible effect.  Now, we 
>> might need to do full program analysis to know which new is run, and 
>> to know its semantics; I don't recall if the user is prohibited from 
>> adding semantics to a new replacement function.
>
>
> Well, I was thinking of the traditional
>
> struct Vector {
>    Vector(int size);
>    Vector operator*(const Vector&);
>    Vector& operator=(const Vector&);
>    double *storage;
> };
>
> and doing expressions like
>
> Vector a,b,c;
> a = b*c;
>
> where one usually considers using expression templates because of the 
> temporaries.  With loop fusion one could get the speed of the 
> expression template code, but are you allowed to get rid of the 
> temporaries (and their allocated memory), too?

As Mike says, if you can prove that there are no side-effects, then, 
yes, you can.  But, that's in general impossible; even with 
whole-program analysis, you see that "::operator new" calls 
"std::malloc" and "std::malloc" eventually makes a syscall.  I don't 
think any compiler has ever attempted to turn:

  free (malloc (16));

into a no-op, which would be a simpler case.

So, I think that for practical purposes, you're not going to find that 
compilers get rid of these kinds of calls.

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com

Re: Optimizing of explicit temporary storage

[Florian Weimer]

* Mark Mitchell:

> I don't think any compiler has ever attempted to turn:
>
>  free (malloc (16));
>
> into a no-op, which would be a simpler case.

There are scheme compilers that turn heap allocation into stack
allocation if they can prove that the object does not escape.
Java code would benefit from this optimization, too.

Re: Optimizing of explicit temporary storage

[Mark Mitchell]

Florian Weimer wrote:

>* Mark Mitchell:
>
>  
>
>>I don't think any compiler has ever attempted to turn:
>>
>> free (malloc (16));
>>
>>into a no-op, which would be a simpler case.
>>    
>>
>
>There are scheme compilers that turn heap allocation into stack
>allocation if they can prove that the object does not escape.
>Java code would benefit from this optimization, too.
>  
>
Yes, but that's rather a different situation due to the nature of Scheme.

In C, even given just:

  (void) malloc(16);

it would be surprising to most programmers to optimize away the call 
because malloc *does* have side-effects on real systems.  For example, 
on UNIX, it is likely to call sbrk, which result in observable changes 
in the process state.

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com

Re: Optimizing of explicit temporary storage

[Robert Dewar]

Mark Mitchell wrote:

> In C, even given just:
> 
>  (void) malloc(16);
> 
> it would be surprising to most programmers to optimize away the call 
> because malloc *does* have side-effects on real systems.  For example, 
> on UNIX, it is likely to call sbrk, which result in observable changes 
> in the process state.

Yes, but the condition of not surprising programmers is different from
the condition of conforming to the standard. Strictly from a standards
conformance point of view, these kinds of optimization seem perfectly
valid, but of course the criterion of not surprising programmers is
indeed a reasonable one!

Re: Optimizing of explicit temporary storage

[Mark Mitchell]

Robert Dewar wrote:

> Mark Mitchell wrote:
>
>> In C, even given just:
>>
>>  (void) malloc(16);
>>
>> it would be surprising to most programmers to optimize away the call 
>> because malloc *does* have side-effects on real systems.  For 
>> example, on UNIX, it is likely to call sbrk, which result in 
>> observable changes in the process state.
>
>
> Yes, but the condition of not surprising programmers is different from
> the condition of conforming to the standard. Strictly from a standards
> conformance point of view, these kinds of optimization seem perfectly
> valid, but of course the criterion of not surprising programmers is
> indeed a reasonable one!

I'm not sure stanadards are all that relevant here, since most real C 
programs go beyond the set of library functions standardized by ISO, or 
even POSIX.

The as-if rule says that the compiler can perform the optimization only 
if the program can't tell the difference.  I don't think it means "can't 
tell the difference using functions from the ISO C standard library;" 
instead, I think it means "can't tell the difference in the current 
environment."  Certainly, calling malloc has observable side effects on 
most UNIX systems; I can see whether or not processes are calling malloc 
by running "top".

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com

Re: Optimizing of explicit temporary storage

[Robert Dewar]

Mark Mitchell wrote:

> The as-if rule says that the compiler can perform the optimization only 
> if the program can't tell the difference.  I don't think it means "can't 
> tell the difference using functions from the ISO C standard library;" 
> instead, I think it means "can't tell the difference in the current 
> environment."  Certainly, calling malloc has observable side effects on 
> most UNIX systems; I can see whether or not processes are calling malloc 
> by running "top".

Anything has observable effects in this respect, because it changes the
code generated, which changes the cache usage, size of external object
files etc etc. Indeed it is perfectly easy to observe all kinds of things
using tools like gdb, objdump etc.

When we are talking about standards conformance, we restrict our attention
strictly to the standard, and what we mean by the as-if rule is that we
cannot write a C program whose meaning is defined by the standard that
can tell the difference at the semantic level of description in the
standard.

That is why you often have to go beyond the standard in deciding when
it is appropriate to do transformations that may violate programmer
expectations, even if these expectations are not derivable from the
standard.

Re: Optimizing of explicit temporary storage

[Mike Stump]

On Oct 12, 2004, at 12:00 AM, Mark Mitchell wrote:
> In C, even given just:
>
>  (void) malloc(16);
>
> it would be surprising to most programmers to optimize away the call 
> because malloc *does* have side-effects on real systems.  For example, 
> on UNIX, it is likely to call sbrk, which result in observable changes 
> in the process state.

There are details (side-effects as you call them) that can be observed 
with gdb, that are not to be interpreted having any relationship with 
the term side-effect or observable behavior in the language standard; 
by this I mean are to be allowed by the optimizer.  In the more general 
standard of a real system, we have to decide which details are 
important (side-effects or observable behaviors) and which aren't, 
that's our job.  As we do higher level optimizations, we have to 
consider exactly which details we want to be side-effects, and which we 
don't want to be, and why.  We can debate just how much information is 
to be required for a particular optimization, that's part of the 
language design.  I'd argue that exactly when sbrk is called under 
malloc isn't an observable side-effect, even on a UNIX system.  I'd 
argue that the value of malloc, likewise, isn't important.

For some languages, this type of optimization is going to be more 
beneficial than for other languages, for C is might not make any 
sense.  For objc or java, I think it might make more sense.  For C, we 
might want to define our language as not permitting it, but for objc, 
to allow it.

Anyway, we can postpone further discussions on this topic until such 
time as someone seriously wants to consider adding it...

Re: Optimizing of explicit temporary storage

[Geoffrey Keating]

Mark Mitchell <mark@codesourcery.com> writes:

> Florian Weimer wrote:
> 
> >* Mark Mitchell:
> >
> >
> >>I don't think any compiler has ever attempted to turn:
> >>
> >> free (malloc (16));
> >>
> >>into a no-op, which would be a simpler case.
> >>
> >
> >There are scheme compilers that turn heap allocation into stack
> >allocation if they can prove that the object does not escape.
> >Java code would benefit from this optimization, too.
> >
> Yes, but that's rather a different situation due to the nature of Scheme.
> 
> In C, even given just:
> 
>   (void) malloc(16);
> 
> it would be surprising to most programmers to optimize away the call
> because malloc *does* have side-effects on real systems.  For example,
> on UNIX, it is likely to call sbrk, which result in observable changes
> in the process state.

Well, yes, but

        int x[65536];

also results in observable changes in the process state, and we don't
hesitate to optimise it away.

Re: Optimizing of explicit temporary storage

[Daniel Berlin]

>>>
>> Yes, but that's rather a different situation due to the nature of Scheme.
>>
>> In C, even given just:
>>
>>   (void) malloc(16);
>>
>> it would be surprising to most programmers to optimize away the call
>> because malloc *does* have side-effects on real systems.  For example,
>> on UNIX, it is likely to call sbrk, which result in observable changes
>> in the process state.
>
> Well, yes, but
>
>        int x[65536];
>
> also results in observable changes in the process state, and we don't
> hesitate to optimise it away.

I believe LLVM actually does all kinds of promotion that ends up removing 
malloc calls.   Maybe i'm just misremembering.
Chris, am i on crack?

--Dan

Re: Optimizing of explicit temporary storage

[Chris Lattner]

On Tue, 12 Oct 2004, Daniel Berlin wrote:

> >> Yes, but that's rather a different situation due to the nature of Scheme.
> >>
> >> In C, even given just:
> >>
> >>   (void) malloc(16);
> >>
> >> it would be surprising to most programmers to optimize away the call
> >> because malloc *does* have side-effects on real systems.  For example,
> >> on UNIX, it is likely to call sbrk, which result in observable changes
> >> in the process state.
> >
> > Well, yes, but
> >
> >        int x[65536];
> >
> > also results in observable changes in the process state, and we don't
> > hesitate to optimise it away.
>
> I believe LLVM actually does all kinds of promotion that ends up removing
> malloc calls.   Maybe i'm just misremembering.

Yes, LLVM deletes dead malloc calls and does other things as well.  The C
spec defines the behavior of malloc/free, and from this description I
believe that it is safe to do this (e.g. C99 second 7.20.3).  Note,
however, that Mark's point above about calling sbrk is beyond the
standard: conformant programs can't know anything about sbrk.

Assuming standards compliant programs, this can still cause changes in
observable behavior.  In particular, something like this:

malloc(HEAPSIZE-100);   // dead
P = malloc(1000);       // not dead
*P = x;

Would cause *P to trap for a suitable value of HEAPSIZE (the second malloc
would return null) in an unmodified program.  In the optimized program the
second call would not return zero.   However again, portable program's
can't really know the size of the heap (malloc can fail at any time (e.g.
due to fragmentation issues) so the program can't even portably probe) so
this is not an issue.

If we are talking about being a C compiler, I think that's as far as it
goes.  However, almost no programs *only* use features from the standard,
so as a QOI feature, adding an argument to disable this kind of thing
might be useful: -fno-builtins seems reasonable to me.  Note that most
programmers would be very happy to have their memory usage optimized, so
IMHO it should be the default.  Obviously you guys have to choose what you
think is right for GCC.

Also note that the comments above only apply to malloc/free.  We don't do
anything special with operator new/delete, though in the future we might
at link-time (we need to detect that a version with known behavior is
linked to, that a new_handler has not been installed, and potentially
other things).

To me, I consider it a defect in the language that the C++ std (as far as
I can tell) does not explicitly allow optimization of operator new/delete,
just like we can optimize out copy ctors.  In particular, the restrictions
placed on allocation functions (3.7.3.1 in C++2003) specify restrictions
that callers must obey, but does not say anything about side effects or
optimizability or restrictions that implementations and new_handlers must
respect.

> Chris, am i on crack?

I don't know Dan, it's hard for me to say, are you?  :-)

-Chris

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

Re: Optimizing of explicit temporary storage

[Kai Henningsen]

sabre@nondot.org (Chris Lattner)  wrote on 12.10.04 in <Pine.LNX.4.44.0410122302530.31127-100000@nondot.org>:

> On Tue, 12 Oct 2004, Daniel Berlin wrote:
>
> > >> Yes, but that's rather a different situation due to the nature of
> > >> Scheme.
> > >>
> > >> In C, even given just:
> > >>
> > >>   (void) malloc(16);
> > >>
> > >> it would be surprising to most programmers to optimize away the call
> > >> because malloc *does* have side-effects on real systems.  For example,
> > >> on UNIX, it is likely to call sbrk, which result in observable changes
> > >> in the process state.
> > >
> > > Well, yes, but
> > >
> > >        int x[65536];
> > >
> > > also results in observable changes in the process state, and we don't
> > > hesitate to optimise it away.
> >
> > I believe LLVM actually does all kinds of promotion that ends up removing
> > malloc calls.   Maybe i'm just misremembering.
>
> Yes, LLVM deletes dead malloc calls and does other things as well.  The C
> spec defines the behavior of malloc/free, and from this description I
> believe that it is safe to do this (e.g. C99 second 7.20.3).  Note,
> however, that Mark's point above about calling sbrk is beyond the
> standard: conformant programs can't know anything about sbrk.

Especially as that is strictly an internal library design decision: there  
are certainly implementations that, say, use mmap() instead, and leave  
sbrk() alone.

MfG Kai

Re: Optimizing of explicit temporary storage

[Daniel Berlin]

>>
>> I believe LLVM actually does all kinds of promotion that ends up removing
>> malloc calls.   Maybe i'm just misremembering.
>
> Yes, LLVM deletes dead malloc calls and does other things as well.  The C
> spec defines the behavior of malloc/free, and from this description I
> believe that it is safe to do this (e.g. C99 second 7.20.3).  Note,
> however, that Mark's point above about calling sbrk is beyond the
> standard: conformant programs can't know anything about sbrk.
>
> Assuming standards compliant programs, this can still cause changes in
> observable behavior.  In particular, something like this:
>
> malloc(HEAPSIZE-100);   // dead
> P = malloc(1000);       // not dead
> *P = x;

>> Chris, am i on crack?
>
> I don't know Dan, it's hard for me to say, are you?  :-)

:)

Also, isn't your thesis on automatic conversion of programs to use pool 
allocation?

Won't that change malloc->pool_alloc?

Or is this something you didn't plan on making the default in LLVM?

Re: Optimizing of explicit temporary storage

[Chris Lattner]

On Wed, 13 Oct 2004, Daniel Berlin wrote:

> > Yes, LLVM deletes dead malloc calls and does other things as well.  The C
> > spec defines the behavior of malloc/free, and from this description I
> > believe that it is safe to do this (e.g. C99 second 7.20.3).  Note,
> > however, that Mark's point above about calling sbrk is beyond the
> > standard: conformant programs can't know anything about sbrk.
> >
> > Assuming standards compliant programs, this can still cause changes in
> > observable behavior.  In particular, something like this:
> >
> > malloc(HEAPSIZE-100);   // dead
> > P = malloc(1000);       // not dead
> > *P = x;
>
> >> Chris, am i on crack?
> >
> > I don't know Dan, it's hard for me to say, are you?  :-)
>
> :)
>
> Also, isn't your thesis on automatic conversion of programs to use pool
> allocation?
>
> Won't that change malloc->pool_alloc?

Yes, that's the first chunk of my thesis work, and falls into the "other
stuff as well" catagory.  :)  Note, however, that the generated code is
substantially different than the libstdc++ style of pools.  From my
understanding, libstdc++'s pool allocator is basically a malloc
replacement by now that allows multiple heaps.  The code generated by my
pool allocation xform ends up using short lived pools as much as possible,
perhaps most similar in spirit to the GCC zone collector.  For example, if
you have two std::sets with elements of the same types, the LLVM pool
allocator would put the nodes into different pools.

> Or is this something you didn't plan on making the default in LLVM?

It's not something that will be default for a long time (perhaps ever?).
First of all it's not robust enough or predictable enough yet.  Second, I
think that automatic pool allocation is an aggressive enough
transformation that it should be enabled explicitly by the user.  OTOH,
the underlying heap analysis may become the default AA in the future,
we'll just have to see.  Currently LLVM uses a pretty trivial alias
analysis by default.

-Chris

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

Re: Optimizing of explicit temporary storage

[Nick Ing-Simmons]

Mark Mitchell <mark@codesourcery.com> writes:
>>
>Yes, but that's rather a different situation due to the nature of Scheme.
>
>In C, even given just:
>
>  (void) malloc(16);
>
>it would be surprising to most programmers to optimize away the call 
>because malloc *does* have side-effects on real systems.  For example, 
>on UNIX, it is likely to call sbrk, which result in observable changes 
>in the process state.

Indeed! - I have actually written 

free(malloc(estimated_total_need));

To get expensive sbrk() call out of the way with one big one
rather than many smaller ones.

Re: Optimizing of explicit temporary storage

[Giovanni Bajo]

Nick Ing-Simmons wrote:

>> it would be surprising to most programmers to optimize away the call
>> because malloc *does* have side-effects on real systems.  For
>> example, on UNIX, it is likely to call sbrk, which result in
>> observable changes in the process state.
> 
> Indeed! - I have actually written
> 
> free(malloc(estimated_total_need));
> 
> To get expensive sbrk() call out of the way with one big one
> rather than many smaller ones.

So why not calling sbrk() directly?

Giovanni Bajo

Re: Optimizing of explicit temporary storage

[Nick Ing-Simmons]

Giovanni Bajo <giovannibajo@libero.it> writes:
>Nick Ing-Simmons wrote:
>
>>> it would be surprising to most programmers to optimize away the call
>>> because malloc *does* have side-effects on real systems.  For
>>> example, on UNIX, it is likely to call sbrk, which result in
>>> observable changes in the process state.
>> 
>> Indeed! - I have actually written
>> 
>> free(malloc(estimated_total_need));
>> 
>> To get expensive sbrk() call out of the way with one big one
>> rather than many smaller ones.
>
>So why not calling sbrk() directly?

Getting off-topic but:

Because calling sbrk() gives me once one big chunk of memory
not lots of little ones. So I would still have to "chip off" bits 
for each "object". 

In my case the malloc()s were in a library which was not to be 
re-coded, and were intermixed with free()s so simplistic slab 
allocator replacement didn't work well.

Emprically (on the Solaris 2.6 machine I was using at the time)
adding this:

  free(malloc(100000*sizeof(Foo));

Before code that had similar effect to:

  for (i=0; i < 100000; i++)
   {
    p = (Foo *) malloc(sizeof(Foo));  // really a library call as result of parse
   }

made it faster. Without the free(malloc()) it made a syscall 
to do the sbrk() for every "page or so" worth of heap it wanted.

Re: Optimizing of explicit temporary storage

[Mike Stump]

On Oct 13, 2004, at 2:19 AM, Nick Ing-Simmons wrote:
> Indeed! - I have actually written 
>
> free(malloc(estimated_total_need));
>
> To get expensive sbrk() call out of the way with one big one
> rather than many smaller ones.

This code might already be broken the the malloc optimization that uses 
mmap for larger regions, and unmaps the large regions on free.  :-)

But, this is exactly the type of thing people can think about...   very 
relevant and obscure.

Re: Optimizing of explicit temporary storage

[Kai Henningsen]

mark@codesourcery.com (Mark Mitchell)  wrote on 11.10.04 in <416B47AA.3010106@codesourcery.com>:

> Richard Guenther wrote:
>
> > Mike Stump wrote:
> >
> >> On Sunday, October 10, 2004, at 07:48  AM, Richard Guenther wrote:
> >>
> >>> Is it legal for a conforming C++ compiler to optimize away storage
> >>> allocation / deallocation?  Like in
> >>>
> >>> #include <new>
> >>>
> >>> void foo(void)
> >>> {
> >>>         int *x = new(std::nothrow) int;
> >>>         delete x;
> >>> }
> >>>
> >>> is it allowed to kill the new and delete statements?  Would it be
> >>> allowed to do this for the throwing version of new, too?
> >>
> >>
> >> The as if rule is fairly powerful...  If the resulting program
> >> behaves as if it had it, then the optimization is allowed.  I don't
> >> think memory consumption is an externally visible effect.  Now, we
> >> might need to do full program analysis to know which new is run, and
> >> to know its semantics; I don't recall if the user is prohibited from
> >> adding semantics to a new replacement function.
> >
> >
> > Well, I was thinking of the traditional
> >
> > struct Vector {
> >    Vector(int size);
> >    Vector operator*(const Vector&);
> >    Vector& operator=(const Vector&);
> >    double *storage;
> > };
> >
> > and doing expressions like
> >
> > Vector a,b,c;
> > a = b*c;
> >
> > where one usually considers using expression templates because of the
> > temporaries.  With loop fusion one could get the speed of the
> > expression template code, but are you allowed to get rid of the
> > temporaries (and their allocated memory), too?
>
> As Mike says, if you can prove that there are no side-effects, then,
> yes, you can.  But, that's in general impossible; even with
> whole-program analysis, you see that "::operator new" calls
> "std::malloc" and "std::malloc" eventually makes a syscall.  I don't
> think any compiler has ever attempted to turn:
>
>   free (malloc (16));
>
> into a no-op, which would be a simpler case.

Any of these cases can, it seems to me, not really be handled well with  
any kind of whole-program analysis.

Instead, what you'd need is to use some sort of language guarantees about  
the behaviour of the allocation functions themselves (new, delete, malloc,  
free) so the decision becomes local.

This is not really different from optimizing, say, the strXXX() functions.  
You don't look at how they are implemented, you look at what the standard  
tells you about what they do.

Assume you had a strange OS where strlen() was a syscall. You could still  
optimize strlen("foo") to 3, as long as you do *not* try to look at how it  
is actually implemented.

MfG Kai

Re: Optimizing of explicit temporary storage

[Mike Stump]

On Oct 11, 2004, at 11:44 PM, Kai Henningsen wrote:
> Instead, what you'd need is to use some sort of language guarantees 
> about  
> the behaviour of the allocation functions themselves (new, delete, 
> malloc,  
> free) so the decision becomes local.

Or a simple statement in the language definition that pairs can be 
optimized away in the right situation, even if there are side 
effects...  For example, a user defined new/delete that does a printf 
could be considered ok, and that the compiler can get rid of pairs 
output lines.

Making this a local decision would be a good language direction for C++.