🚀 go-pugleaf

In article 816557310@cadlab, martelli@cadlab.it (Alex Martelli) writes:
>
>In a debate over on comp.compilers, there was some discussion of
>whether it would be legal for a compiler to optimize the following
>snippet of code...:

>class P {
>public: virtual void f();
>    // etc
>};

>// with a P* p
>    for(i=0;i<1000;i++)
>	p->f();

>by hoisting out of the loop the virtual lookup for f()'s address.

> ...

>Here's the counterexample I have in mind:
>
>#include <iostream>
>
>class Base {
>public: virtual void f() {cout<<"Base ";}
>};
>class Derived: public Base {
>    int countdown;
>public: Derived(int n=2):countdown(n) {}
>    virtual void f();
>};
>int main()
>{
>    Base *p=new Derived;
>    for(int i=0;i<4;i++)
>      p->f();
>    cout<<endl;
>    return 0;
>}
>
>and, separately compiled perhaps,
>
>#include <iostream>
>#include <new>
>// above-seen declarations of Base and Derived, then:
>    virtual void Derived::f() {
>	cout<<"Derived ";
>	if(--n==0) {
>	    this->~Derived();
>	    new(this) Base;
>	}
>    }
>
>Isn't this a strictly conformant, well-defined program, ...


I am not at all convinced that constructing a new object on top of "this"
is well-defined. Recent changes in the DWP assure us that you can
construct a new object of the SAME type on top of an existing object if
you destroy the old one first, but even this case is not discussed in
terms of doing it from inside a member function.

Here is a different example which is well-defined. (I haven't compiled
it, so please excuse any typos.)

class Base { public: virtual void f(); };
class Derived : public Base { public: virtual void f(); };

extern Base* array[4] = { new Base, new Derived, new Base, new Derived };
Base* p = 0;

int main()
{
	p = Base[0];
	for(int i=0; i<4; i++)
		p->f();
}

void X::f() // X is Base or Derived
{
	static int i = 0;
	... do something unique for each class, then
	i = (i+1)%4;
	p = array[i]; // change the value of p
}

The difference here is that p is global, not local, so its value cannot
be assumed to be unchanged. You didn't say whether that was an assumption
in the original case. Similarly, you could make p a local variable, but
pass it by reference to f. Again, it cannot be assumed to be unchanged,
which may not fit the original problem definition.

If we assume that the VALUE of p does not change, the question is whether
the object it points to can change type (except during construction and
destruction). I think the answer is no, in which case the optimization is valid.
---
Steve Clamage, stephen.clamage@eng.sun.com



---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

Alex Martelli (martelli@cadlab.it) wrote:

|> In a debate over on comp.compilers, there was some discussion of
|> whether it would be legal for a compiler to optimize the following
|> snippet of code...:

|> class P {
|> public: virtual void f();
|>     // etc
|> };

|> // with a P* p
|>     for(i=0;i<1000;i++)
|> 	p->f();

|> by hoisting out of the loop the virtual lookup for f()'s address.

|> I was astonished to see normally knowledgeable folks claim that
|> the optimization is legal, and the only counterexamples posted
|> involve illegal stuff such as F() memcpy()'ing all over "*this".

|> I tried to post what I believe is the correct way to show that
|> the optimization would be illegal, except basically when the
|> compiler knows enough about P and p that the virtual lookup
|> is not in fact needed, or when it knows everything about f()
|> and whatever it is that f() calls, etc -- but the c.c moderator
|> is apparently sick & tired of the issue, so I'm turning to here
|> for authoritative opinions... I think that if it is the committe's
|> desire to permit that optimization, then something presently
|> legal would be outlawed.

|> Here's the counterexample I have in mind:

   [I've added line numbers for convenience in the discussion which
   follows...]

|>   1 #include <iostream>

|>   3 class Base {
|>   4 public: virtual void f() {cout<<"Base ";}
|>   5 };
|>   6 class Derived: public Base {
|>   7     int countdown;
|>   8 public: Derived(int n=2):countdown(n) {}
|>   9     virtual void f();
|>  10 };
|>  11 int main()
|>  12 {
|>  13     Base *p=new Derived;
|>  14     for(int i=0;i<4;i++)
|>  15       p->f();
|>  16     cout<<endl;
|>  17     return 0;
|>  18 }

|> and, separately compiled perhaps,

|>  20 #include <iostream>
|>  21 #include <new>
|>  22 // above-seen declarations of Base and Derived, then:
|>  23     virtual void Derived::f() {
|>  24 	cout<<"Derived ";
|>  25 	if(--n==0) {
|>  26 	    this->~Derived();
|>  27 	    new(this) Base;
|>  28 	}
|>  29     }

|> Isn't this a strictly conformant, well-defined program, and the
|> ONLY legal output it can give under a conformant compiler:

|> Derived Derived Base Base

|> ???

There's one obvious problem.  The address of Base in Derived is not
guaranteed to be the same as the address of Derived.  Thus, in line 13,
the actual address assigned to p will be that of the Base in Derived,
and *not* the address of the complete object.  Calling throught the
virtual call mechanism will cause the address seen in functions of
Derived (including f) do be different that that in p.

Consider a trivial example: suppose an implementation puts the
additional data members of the derived class in front of the base class
at each derivation.  In this case, the compiler will add the size of
these data members to the address returned by the new expression in line
13.  The virtual function call mechanism will also arrange to subtract
this value from this address each time a virtual function resolves
dynamically to a function in Derived (typically by means of an offset in
the vtbl or a trampoline).  The placement new in line 27 thus constructs
the Base lower in memory than it was previously, and lower in memory
than the address in p.  *Any* use of p after this is undefined
(including further calls to f).

A general hint: when attempting to analyse such things, always use
multiple inheritance, with non-empty classes, and use the second base
specified.  In this case, I think you would immediately see that it
cannot work; that there is no possible implementation for which it would
work, and thus, if it is guaranteed by the standard, the standard is in
error.  Now note that there is *no* additional guarantee in the standard
concerning layout (or anything else) in the case of single inheritance;
if it doesn't work in some form of multiple inheritance (without virtual
base classes), it isn't guaranteed to work in single inheritance either.

I think it would be nice if language were added to the standard to
expressedly forbid this (rather than counting on the somewhat circuitous
argument above).  However, such language must be thought out very
carefully in order not to break other things that should work.  (I'm
thinking, in particular, of the assignment operator idiom that uses
explicit destruction and placement new.  This works because the new type
is the same as the old.)  So unless someone has the time to work out the
exact wording, I think we can live with having it implicitly illegal by
the above argument.
-- 
James Kanze           (+33) 88 14 49 00          email: kanze@gabi-soft.fr
GABI Software, Sarl., 8 rue des Francs Bourgeois, 67000 Strasbourg, France
Conseils, études et réalisations en logiciel orienté objet --
              -- A la recherche d'une activité dans une region francophone

[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <martelli.816557310@cadlab>,
Alex Martelli <martelli@cadlab.it> wrote:
>
>In a debate over on comp.compilers, there was some discussion of
>whether it would be legal for a compiler to optimize the following
>snippet of code...:
>
>class P {
>public: virtual void f();
>    // etc
>};
>
>// with a P* p
>    for(i=0;i<1000;i++)
>	p->f();
>
>by hoisting out of the loop the virtual lookup for f()'s address.

I'll admit it, I was the one who got this entire debate started :-)
I originally posted to comp.compilers because I was convinced of the
legality, but wondering about the feasibility and whether real
compilers actually did this yet.  comp.std.c++ is probably a better
forum to debate the legality of the optimization.

>Here's the counterexample I have in mind:
>
>#include <iostream>
>
>class Base {
>public: virtual void f() {cout<<"Base ";}
>};
>class Derived: public Base {
>    int countdown;
>public: Derived(int n=2):countdown(n) {}
>    virtual void f();
>};
>int main()
>{
>    Base *p=new Derived;
>    for(int i=0;i<4;i++)
>      p->f();
>    cout<<endl;
>    return 0;
>}
>
>and, separately compiled perhaps,
>
>#include <iostream>
>#include <new>
>// above-seen declarations of Base and Derived, then:
>    virtual void Derived::f() {
>	cout<<"Derived ";
>	if(--n==0) {
>	    this->~Derived();
>	    new(this) Base;
>	}
>    }
>
>Isn't this a strictly conformant, well-defined program ...

I think it's pretty clear the answer is no:

[class.dtor] #11:

"...  Once a destructor is invoked for an object, the object no longer
 exists; ..."

Now, it is legal to use a (T*) as a (void*) even after the T's life
has ended, however:

[basic.life] #7:

"If, after the lifetime of an object has ended and while the storage
which the object occupied still exists, a new object is created at the
storage location which the original object occupied, a pointer that
pointed to the original object will automatically refer to the new
object and, once the lifetime of the new object has started, can be
used to manipulate the new object, if:

[...]

... the new object is of THE SAME TYPE as the original object ...

[...]

The conditions are not met, so the pointer 'p' DOES NOT refer to the
new object you have created.  It still refers to the old object whose
life has ended, and hence it can only be used in very restricted ways.
Specifically, dereferencing it or using it as on object of type T
invokes undefined behavior.

So you program is not strictly conforming.  Based on the careful
wording of [basic.life], it does indeed seem that the comittee was
very careful to make sure the type of an object cannot be changed
arbitrarily.

-Tim
-- 
Tim Hollebeek      | Everything above is a true statement, for sufficiently
PChem Grad Student | false values of true.
Princeton Univ.    | C++ == OOP--
-------------------| tim@handel.princeton.edu  http://wagner.princeton.edu/~tim

[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <martelli.816557310@cadlab> martelli@cadlab.it (Alex Martelli) writes:

>     virtual void Derived::f() {
> 	cout<<"Derived ";
> 	if(--n==0) {
> 	    this->~Derived();
> 	    new(this) Base;
> 	}
>     }

> Isn't this a strictly conformant, well-defined program

The work on the object model is not quite complete, but the
direction it is going is towards a `no' answer here.
One reason is this:

	class Foo {
	public:
		virtual void f();
	// ...
	};

	void g() {
		Foo foo;

		foo.f();	// virtual?
		foo.f();	// virtual?
	}

It would be nice if each call to foo.f could avoid the run-time
dispatch overhead, because object foo is known to be of type Foo.
But one could imagine that Foo::f, compiled separately, changes
the type of its object to Bar (derived from Foo and known to be
the same size) and Bar::f changes it back to Foo (so the destructor
will do the right thing).  The people I've talked to on the committee
agree that such programs should be taken out and shot; therefore
they will not bless such behavior.
-- 
				--Andrew Koenig
				  ark@research.att.com


---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

martelli@cadlab.it (Alex Martelli) writes:

>In a debate over on comp.compilers, there was some discussion of
>whether it would be legal for a compiler to optimize the following
>snippet of code...:
>
>class P {
>public: virtual void f();
>    // etc
>};
>
>// with a P* p
>    for(i=0;i<1000;i++)
>	p->f();
>
>by hoisting out of the loop the virtual lookup for f()'s address.

Yes, I saw that debate.  I believe that the optimization is legal
according to the current draft standard.  See section 3.8 [basic.life],
"Object Lifetime".  The committee was quite deliberate in its intent to
make sure that this optimizations and other similar optimizations were
legal.

>#include <iostream>
>
>class Base {
>public: virtual void f() {cout<<"Base ";}
>};
>class Derived: public Base {
>    int countdown;
>public: Derived(int n=2):countdown(n) {}
>    virtual void f();
>};
>int main()
>{
>    Base *p=new Derived;
>    for(int i=0;i<4;i++)
>      p->f();
>    cout<<endl;
>    return 0;
>}
>
>and, separately compiled perhaps,
>
>#include <iostream>
>#include <new>
>// above-seen declarations of Base and Derived, then:
>    virtual void Derived::f() {
>	cout<<"Derived ";
>	if(--n==0) {
>	    this->~Derived();
>	    new(this) Base;
>	}
>    }
>
>Isn't this a strictly conformant, well-defined program,

No.  According to 3.8, it has undefined behaviour.  It violates 3.8/6.
The pointer `p' is dereferenced after the lifetime of the object
it points to has ended (since the storage has been reused).

|   3.8  Object Lifetime                                      [basic.life]
| 5 A  program  may  end the lifetime of any object by reusing the storage
|   which the object occupies or by explicitly calling the destructor  for
|   an  object  of  a  class  type  with a non-trivial destructor.
[...]
| 6 After the lifetime of an object has ended and while the storage  which
|   the  object  occupied still exists, any pointer to the original object
|   can be used but only in limited ways.  Such a pointer still points  to
|   valid  storage and using the pointer as a pointer to the storage where
|   the object was located, as if the pointer were of type void*, is well-
|   defined.   However,  using the pointer to refer to the original object
|   is no longer valid.  In particular, such a pointer cannot be  derefer-
|   enced; for a non-POD class type T, a pointer of type T* that points to
|   the  original  object  cannot  be  the  operand   of   a   static_cast
|   (_expr.static.cast_) (except when the conversion is to void* or char*)
|   and cannot be the operand of a dynamic_cast (_expr.dynamic.cast_);  if
|   T  is  a class with a non-trivial destructor, such a pointer cannot be
|   used as the operand of a delete-expression.  [Example:
|           struct B {
|                   virtual void f();
|                   void mutate();
|                   virtual ~B();
|           };
| 
|           struct D1 : B { void f(); };
|           struct D2 : B { void f(); };
|           void B::mutate() {
|                   new (this) D2;  // reuses storage - ends the lifetime of '*th
| is'
|                   f();            // undefined behavior
|                   ... = this;     // ok, 'this' points to valid memory
|           }
| 
|           void g() {
|                   void* p = malloc(sizeof(D1) + sizeof(D2));
|                   B* pb = new (p) D1;
|                   pb->mutate();
|                   &pb;            // ok: pb points to valid memory
|                   void* q = pb;   // ok: pb points to valid memory
|                   pb->f();        // undefined behavior, lifetime of *pb has en
| ded
|           }
|    --end example]

--
Fergus Henderson             	WWW: http://www.cs.mu.oz.au/~fjh
fjh@cs.mu.oz.au              	PGP: finger fjh@128.250.37.3

[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

Fergus Henderson (fjh@munta.cs.mu.OZ.AU) wrote:
: 
<snip>
: |   3.8  Object Lifetime                                      [basic.life]
: | 5 A  program  may  end the lifetime of any object by reusing the storage
: |   which the object occupies or by explicitly calling the destructor  for
: |   an  object  of  a  class  type  with a non-trivial destructor.
: [...]
: | 6 After the lifetime of an object has ended and while the storage  which
: |   the  object  occupied still exists, any pointer to the original object
: |   can be used but only in limited ways.  Such a pointer still points  to
: |   valid  storage and using the pointer as a pointer to the storage where
: |   the object was located, as if the pointer were of type void*, is well-
: |   defined.   However,  using the pointer to refer to the original object
: |   is no longer valid.  In particular, such a pointer cannot be  derefer-
: |   enced; ...
<snip>

This seems to conflict with two (mis)impressions that I had about
pointers to deleted objects:

  1) If the expression denoting the object in a delete expression is
     a modifiable lvalue, its value is undefined after the deletion.
     (ARM p.63)

  2) The result of merely reading (not dereferencing) a pointer object
     holding an invalid value (e.g. the address of a deleted object)
     is defined to be undefined.
     
I understood from a thread three or four months ago (possible in
comp.lang.c++) that (2) came about as a result of the need to allow
pointers to be stored in special registers whose hardware did a
validity check on every access, a point which seems related to the 
strange 486 behavior mentioned by John Skaller in the current thread.

Tom Payne (thp@cs.ucr.edu)

[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]