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

(Hi Mike!)

On May 1, 2008, at 6:11 PM, Mike Stump wrote:
> On Apr 30, 2008, at 9:26 PM, Chris Lattner wrote:
>> 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".
>
> Yes it does:
>
>   Replaceable:
>     a  C++  program  may  define a function with this function
> signature
>     that displaces the default  version  defined  by  the  C++
> Standard
>     library.
>   Required behavior:
>     Return    a   non-null   pointer   to   suitably   aligned
> storage
>     (_basic.stc.dynamic_), or else throw a  bad_alloc  exception.
> This
>     requirement is binding on a replacement version of this function.
>
> These _are_ the defined semantics.  You cannot imagine any other
> semantic and substitute it.  Any program that does, is outside the
> scope of the standard and has _no_ constraint upon it.  Meaning, the
> compiler free to do anything, technically.

Not quite.  Although there is a requirement there (and more precise  
ones in Clause 3), there is no prohibition against doing additional,  
observable stuff (e.g., log the calls) and hence allocations cannot be  
elided.

(I'll repeat some of my notes to Chris earlier today.)
> The latitude exists to do exactly what you want to do as in
> intelligent optimization person.
>
> You can see that this is what the standard mandates by imagining what
> would happen if you had the allocator return the same pointer to the
> same memory all the time that was maximally aligned.  What does cout
> << "Hi" << "there" do, or some other
complex program that underneath
> wanted to use the allocator?  Either, they _have_ to work, which is
> impossible and nonsensical, or there has to be enough latitude in the
> standard to allow the code to not work.  The requirements on the
> replacement versions of the allocators is the constraint that provides
> the mechanism to decide wether your program is going to work.  If you
> behaves exactly as if you allocated suitably aligned storage and
> return it or throw bad_alloc, then, the execution of the program is as
> constrained by the abstract semantics.  If not then _all_ requirements
> of the standard are vacated.  In particular, printf("Hi") in the
> allocator means the standard places no requirements on the program.
> You can print Hi, not print it, print it twice, whatever you want.
>
>> Very interesting properties to me would be:
>>
>> 1) Safety to remove "delete (new int);" and friends.
>
> You are free to do that.

No, because both "delete" and "new" may have side effects. 
The
standard does not currenty prohibit those, and does not give latitude  
(as e.g. it does for call to construct copies of temporaries) to elide  
those effects.
>> 2) Aliasing guarantees about the result of new.
>
> The replacements have their behavior required (you can also read this
> as constrained).  They are required to allocate new memory, and
> aliasing falls out from that.

It's not equivalent.  Here are the words:

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

The problem is that with a user-written operator new, there may be  
other valid ways (besides operator new) to get at the storage  
returned.  The object lifetime rules don't always give such programs  
undefined behavior.

(I personally consider this a defect in the standard, but I don't  
think that's unarguable.)

>
>> 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.
>
> This one is safe.  It has to behaves as if it allocates storage.  If
> you can detect it didn't, there are no requirements placed upon the
> semantics of the code.

Which part of the standard would I be missing that implies so?

>> 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'.
>
> Again, you can't inspect the value as there is no way to have those
> semantics without also then violating the required semantics of the
> deallocator and if you did that, then that standard places no
> requirements on the program, so net result you are free to omit the
> store.
I don't think it's the deallocator that makes this work; it may be the  
object lifetime rules.  I'm pretty sure it would work if instead of  
"double", a type with a destructor was used.  Worth investigating?

>> 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),
>
> 3 The program's definitions are used instead  of  the  default   
> versions
>   supplied  by  the  implementation  (_dcl.fct.def_).   Such
> replacement
>   occurs prior to program startup (_basic.def.odr_, _basic.start_).
>
> So, the replacement is done before start, if later, there are no
> requirements.  And, the replacement has known semantics.

But isn't that still too late?  The optimizer often must make  
decisions way before that.  (Plus, even though the standard currently  
fails to address dynamic libraries, in practice implementations must  
keep things working right.)

	Daveed

On May 1, 2008, at 3:39 PM, David Vandevoorde wrote:
>
> Not quite.  Although there is a requirement there (and more precise  
> ones in Clause 3), there is no prohibition against doing additional,  
> observable stuff (e.g., log the calls) and hence allocations cannot  
> be elided.

That's correct, there is no prohibition, but, if one does, there are  
no requirements placed upon the semantics of the program, none:

   --If  a program contains a violation of a rule for which no  
diagnostic
     is required, this International Standard places  no  requirement   
on
     implementations with respect to that program.

   1.4.12  undefined behavior                            
[defns.undefined]
   behavior, such as might arise upon use of an  erroneous  program   
con-
   struct  or  of  erroneous  data,  for  which  the  Standard imposes  
no
   requirements.

You may also want to read these which cover the basic idea:

   17.1.6  default behavior                       
[defns.default.behavior]
   a  description of replacement function and handler function  
semantics.
   Any specific behavior provided by the implementation, within the  
scope
   of the required behavior.

   17.1.14  replacement function                       
[defns.replacement]
   a reserved function whose definition is provided  by  a  C++   
program.
   Only  one definition for such a function is in effect for the  
duration
   of the program's execution, as the  result  of  creating  the   
program
   (_lex.phases_)  and resolving the definitions of all translation  
units
   (_basic.link_).

   17.1.15  required behavior                    
[defns.required.behavior]
   a description of replacement function and handler function   
semantics,
   applicable to both the behavior provided by the implementation and  
the
   behavior that shall be provided by any function definition in the  
pro-
   gram.   If  a  function  defined  in  a  C++ program fails to meet  
the
   required behavior when it executes, the behavior is undefined.

4 For non-reserved replacement and handler functions,  Clause  _lib.lan-
   guage.support_  specifies two behaviors for the functions in  
question:
   their required and default behavior.  The default behavior  
describes a
   function  definition  provided  by  the  implementation.  The  
required
   behavior describes the semantics of a function definition provided   
by
   either  the  implementation or a C++ program.  Where no distinction  
is
   explicitly made in the description,  the  behavior  described  is   
the
   required behavior.

1 Clauses _lib.language.support_ through _lib.input.output_ describe the
   behavior  of  numerous  functions defined by the C++ Standard  
Library.
   Under some circumstances, however, certain of these function   
descrip-
   tions  also  apply  to  replacement  functions  defined in the  
program
   (_lib.definitions_).

   17.4.3.6  Other functions                        
[lib.res.on.functions]

1 In certain cases (replacement functions, handler functions, operations
   on types used to instantiate standard  library  template   
components),
   the  C++ Standard Library depends on components supplied by a C++  
pro-
   gram.  If these components do not meet their requirements,  the   
Stan-
   dard places no requirements on the implementation.

2 In particular, the effects are undefined in the following cases:

   --for  replacement  functions  (_lib.new.delete_),  if  the   
installed
     replacement function does not implement the semantics of the   
appli-
     cable Required behavior paragraph.

   --for  handler  functions (_lib.new.handler_,  
_lib.terminate.handler_,
     _lib.unexpected.handler_), if the installed  handler  function   
does
     not  implement  the  semantics  of  the applicable Required  
behavior
     paragraph


These are meant to constrain the replacements as I've described.
> No, because both "delete" and "new" may have side
effects.
No, please read the above paragraphs again.
> The problem is that with a user-written operator new, there may be
> other valid ways (besides operator new) to get at the storage
> returned.  The object lifetime rules don't always give such programs
> undefined behavior.
The reason why all that wording was included was to ensure the  
semantics of the implementation when the standard library uses the  
user's new/delete operator.  If the user does something funny and  
causes the library to not work, the standard places the responsibility  
squarely in the users lap.  We do that through the wording above.  If  
the user meets the requirements, then:

   a = new stack<int>;

produces no observable semantics.  If there were no such constraint,  
then that same line could produce:

   new allocated 24 bytes at 0xfe4238

on the standard output device (cout/stdout).  The only thing that  
ensures that line doesn't produce that output is the _hard_  
requirement on the users program.  Now, we knew that some users would  
want to put a print in new/delete implementations and do exactly as  
above.  We didn't have a good way to describe that we wanted to happen  
and we didn't spend the effort to describe it well, so, we choose the  
cheap way out and described exactly what they had to do, no more, no  
less for the standard to place any requirement on the semantics.

There would be little point in insuring the semantics of programs when  
replacements are used if the replacements could foster the reuse of in  
use memory.  At best, I think you either run into unspecified behavior  
(for reads) or undefined behavior (for writes) for allocations by the  
system routines.  Though, I do agree, the standard could be made more  
clear exactly what we meant.
> (I personally consider this a defect in the standard, but I don't   
> think that's unarguable.)
> Which part of the standard would I be missing that implies so?
   A C++ implementation pro-
   vides access to, and management of, dynamic  storage  via  the   
global
   allocation  functions  operator  new and operator new[] and the  
global
   deallocation functions operator delete and operator delete[].

The standard is not meant to be read outside the scope of english nor  
the usual and customary terms used by computer science.  It that were  
meant to be the case, we'd have a formal definition for C++.  The  
standard isn't a formal definition.

That says that new is an allocation function and that delete is a  
deallocation function.  These are the usual and customary CS terms.
> it may be the object lifetime rules.  I'm pretty sure it would work  
> if instead of
> "double", a type with a destructor was used.  Worth
investigating?
Yes, there are various bits in the lifetime rules that also constrain:

5 Before the lifetime of an object has started  but  after  the  storage
   which the object will occupy has been allocated34) or, after the  
life-
   time  of  an  object has ended and before the storage which the  
object
   occupied is reused or released, any pointer that refers to the  
storage
   location  where the object will be or was located may be used but  
only
   in  limited  ways.   Such  a  pointer  refers  to  allocated    
storage
   (_basic.stc.dynamic.deallocation_),  and  using  the pointer as if  
the
   pointer were of type void*, is well-defined.  Such a  pointer  may   
be
   dereferenced  but  the  resulting  lvalue  may only be used in  
limited
   ways, as described below.

[ see the rest of the standard for all the gory details. ]
>>> 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),
>>
>> 3 The program's definitions are used instead  of  the  default
>> versions
>>  supplied  by  the  implementation  (_dcl.fct.def_).   Such
>> replacement
>>  occurs prior to program startup (_basic.def.odr_, _basic.start_).
>>
>> So, the replacement is done before start, if later, there are no
>> requirements.  And, the replacement has known semantics.
>
>
> But isn't that still too late?
Too late?  What could that possibly mean?  There is by definition  
nothing before the start.  Talking about something that happens first  
as being too late is non-sensical (by this, we merely mean outside the  
bounds of the standard and by that, we mean, the standard places no  
requirements on such a program).
> The optimizer often must make decisions way before that.
There is no optimizer in the standard, so there is no way to even talk  
about it.  All there is, are the abstract semantics when the program  
is run and the constraint on the actual implementation semantics that  
derive from the abstract semantics.
> (Plus, even though the standard currently fails to address dynamic  
> libraries, in practice implementations must keep things working  
> right.)
The standard places no requirements in the face of shared libraries, I  
know, it kinda sucks, but there it is.  The implementation is free to  
map onto the standard as it sees fit however.  The quality can be  
judged by the user however.

On May 4, 2008, at 10:29 PM, Mike Stump wrote:
> On May 1, 2008, at 3:39 PM, David Vandevoorde wrote:
>>
>> Not quite.  Although there is a requirement there (and more precise
>> ones in Clause 3), there is no prohibition against doing additional,
>> observable stuff (e.g., log the calls) and hence allocations cannot
>> be elided.
>
>
> That's correct, there is no prohibition, but, if one does, there are
> no requirements placed upon the semantics of the program, none:
I don't read it that way.  I.e., I read it as saying that you can  
"add" to the "Required behavior".  But now I'm not sure
-- so I'll ask
the committee.

	Daveed

One more question on this.

The substitution of malloc() is predicated on the assumption that the
compiler knows the implementation of malloc(), and the argument for that
seems to rest in part on the specification of the Standard C Library.

But I am not aware of any requirement that compliant C code must be
linked with the Standard C Library. If this requirement does not exist,
then no portion of the C library specification can be used to justify a
compile-time optimization unless we have some sort of compilation model
information that tells us the C library can be assumed.

Is there a requirement somewhere in the C *Language* Specification that
ties all of this together in the required way?


shap