In article <35D4B2AC.4C25@noSPAM.central.beasys.com>,
  dtribble@technologist.com wrote:
>
> markw@silicon-spice.com wrote:
> >>> ...
> >>> the linker _always_  has access to the entire program.
>
> I, David R Tribble, dtribble@technologist.com wrote:
> >> Except on Win/NT when you link against DLLs; the linker doesn't
> >> read the .DLL files, but rather uses the "export library" .LIB
> >> files, which contain stub functions to invoke the actual functions
> >> in the DLL at runtime.  So there is some information about the
> >> entire program that the linker doesn't have at link time (at least
> >> on Win/NT).

<snip>

> The point of this thread was trying to come up with ways that the
> linker can omit unused virtual member functions.  This requires
> some inter-function analysis, to know which functions call which
> other functions.  My point was that the .LIB "import" files
> probably don't contain enough information about the .DLL contents
> (function code) to do such analysis.

Yes, but nor do normal .LIB files, or even .OBJ files.

The point of this thread was whether or not a compiler system (ie compiler +
linker + possibly other programs) _could_ be made capable of dead stripping
virtual functions.

Clearly all the required information _could_ be made available in the DLL or
stub lihrary. And as I mentioned in my previous response to this thread,
general purpose DLLs are usually written with C only interfaces, because of
the fragile base class problem, and the non-uniformity of C++ ABIs accross
different compilers on the same platform. Normally, you only create a DLL
with a C++ interface when you are providing a closed system of DLLs and
applications. In which case you have all the source code anyway.

In the rare exceptions, you do need summary information about the DLLs use of
virtual functions etc.

Mark Williams

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

<AllanW@my-dejanews.com> wrote:
>> Allan:
>> > I think you're implying that the DLL might have a reference to a
>> > symbol in the .EXE. This is possible but difficult and extremely rare
>> > -- so rare that we can disallow it completely.
>>
>David:
>> Um, what if the DLL contains a base class member function that
>> invokes a virtual member function, which I provide as a part of a
>> derived class in my .OBJ file?
>
>How common is it to have a base class in a DLL, which is overridden
>by a derived class in another DLL or in the .EXE?

It doesn't matter how common it is.  It's the nature of a shared
library (or "DLL", if you insist) that it can be replaced by a
later version.  For any base class interface it has access to,
the current or some later version might use *any* member, so you
cannot discard any those virtuals.

You would need an assertion from the programmer at link time that the
shared library is in fact not C++, or depends only on certain virtual
functions, in order to get away with assuming that it will not later
depend on additional members.

But so what?  The point of the optimization was to reduce the memory
footprint in embedded systems, which typically will not be using
shared libraries.  For programmers of embedded systems which do
happen to use shared libraries, they are certainly equipped to
identify which shared libraries are "safe" in this way.

(Some of us consider Win32 an embedded system, and could hardly
imagine compiling native for it.  It has a primitive form of shared
library ("DLL"), and that's the least of the compromises one makes
trying to build programs for it.  But that's off-topic.)

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

markw65@my-dejanews.com wrote:
>
>
> Normally, you only create a DLL
> with a C++ interface when you are providing a closed system of DLLs and
> applications.

OWL and MFC users would be surprised to hear this. <g>

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

AllanW@my-dejanews.com wrote:
>
> How common is it to have a base class in a DLL, which is overridden
> by a derived class in another DLL or in the .EXE?

It's quite common. OWL and MFC, for example, ship as DLLs, and you use
them by deriving from the classes that they define.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Nathan Myers wrote:
>
> But so what?  The point of the optimization was to reduce the memory
> footprint in embedded systems, which typically will not be using
> shared libraries.

With Microsoft pushing Windows CE as the operating system for embedded
systems of the future, this is a bit optimistic. Especially since they
provide MFC, in a DLL, hosted on Windows CE. On the other hand, MS's
view of how you get a small footprint is to cripple the C library and
leave the standard C++ library out entirely. MFC for CE has its own
implementation of the operators new and delete, to make up for their
absence in the standard libraries. But it's all DLLs...

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

<AllanW@my-dejanews.com> wrote:
>> I think you're implying that the DLL might have a reference to a
>> symbol in the .EXE. This is possible but difficult and extremely rare
>> -- so rare that we can disallow it completely.

Me:
>> Um, what if the DLL contains a base class member function that
>> invokes a virtual member function, which I provide as a part of a
>> derived class in my .OBJ file?

Allan:
>> How common is it to have a base class in a DLL, which is overridden
>> by a derived class in another DLL or in the .EXE?

Nathan Myers wrote:
> It doesn't matter how common it is.  It's the nature of a shared
> library (or "DLL", if you insist) that it can be replaced by a
> later version.  For any base class interface it has access to,
> the current or some later version might use *any* member, so you
> cannot discard any those virtuals.

I guess I misunderstood the point of this thread.  I thought we
were trying to get rid of linking in unnecessary virtual member
functions in our executable (not in the libraries it links to).
I seems to me that being able do some function-dependecny analysis
between our code (object files) and the libraries we use might
help eliminate linking some of our uncalled functions into the
final executable.

But as for my original post...
> Um, what if the DLL contains a base class member function that
> invokes a virtual member function, which I provide as a part of a
> derived class in my .OBJ file?  Then the DLL has a (virtual)
> reference into my code.

I thought this would be a way that a DLL could "refer to" a function
outside of itself, but in retrospect I believe this is not the case;
a virtual table reference is merely a call to a function through a
(vtable) pointer which is supplied at runtime from outside the
(base class code in the) DLL.  The derived vtable resides somewhere
outside the DLL (base class) code, so I don't think it really
qualifies as an "external reference".

But this still doesn't change my point that having access to
(or the ability to analyze) inter-function dependencies between
your object code and third-party libraries might lead to smaller
executables by eliminating unnecessary (derived) virtual functions.
And I don't believe import LIBs give the linker this kind of
information.

-- David R. Tribble, dtribble@technologist.com --


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35D72E3B.5AB67CD2@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:
>
> AllanW@my-dejanews.com wrote:
> >
> > How common is it to have a base class in a DLL, which is overridden
> > by a derived class in another DLL or in the .EXE?

I asked this question, because if it's not very common then it would
be no big loss to skip this particular optimization in that case.

> It's quite common. OWL and MFC, for example, ship as DLLs, and you use
> them by deriving from the classes that they define.

That's true, but in these cases we don't want to optimize away any
of the overriding functions anyway.

A better version of the same question: how common is it to have a
base class in a Shared Library (to avoid OS-dependant terms), which
is overridden by a derived class in the executable image, and yet
the overridden versions of those member functions are not used (and
so should, ideally, be supressed)?

--
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35D87A91.2D43@noSPAM.central.beasys.com>,
  dtribble@technologist.com wrote:
>
> But this still doesn't change my point that having access to
> (or the ability to analyze) inter-function dependencies between
> your object code and third-party libraries might lead to smaller
> executables by eliminating unnecessary (derived) virtual functions.
> And I don't believe import LIBs give the linker this kind of
> information.

They dont. But that doesnt mean they cant. We are not talking about doing this
optimization with current compilers and linkers, we are talking about changing
them to make it possible.

Mark Williams

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35D87A91.2D43@noSPAM.central.beasys.com>,
  dtribble@technologist.com wrote:
>
> <AllanW@my-dejanews.com> wrote:
> >> I think you're implying that the DLL might have a reference to a
> >> symbol in the .EXE. This is possible but difficult and extremely rare
> >> -- so rare that we can disallow it completely.
>
David:
> >> Um, what if the DLL contains a base class member function that
> >> invokes a virtual member function, which I provide as a part of a
> >> derived class in my .OBJ file?
>
> Allan:
> >> How common is it to have a base class in a DLL, which is overridden
> >> by a derived class in another DLL or in the .EXE?
>
> Nathan Myers wrote:
> > It doesn't matter how common it is.  It's the nature of a shared
> > library (or "DLL", if you insist) that it can be replaced by a
> > later version.  For any base class interface it has access to,
> > the current or some later version might use *any* member, so you
> > cannot discard any those virtuals.
>
> I guess I misunderstood the point of this thread.  I thought we
> were trying to get rid of linking in unnecessary virtual member
> functions in our executable (not in the libraries it links to).

Yes, but I think that Nathan is saying (and if he's not, I am) that
this would be a bad idea. You've obviously realized that we can
build more .EXE's that use the same DLL, and presubably realize
that we can make changes to the .EXE without making any changes
to the .DLL. But sometimes we might want to make changes to the
.DLL without making changes to the .EXE! If these optimizations
have been performed, the .DLL may now refer to functions (through
the virtual table) that were previously optimized away.

> I seems to me that being able do some function-dependecny analysis
> between our code (object files) and the libraries we use might
> help eliminate linking some of our uncalled functions into the
> final executable.

Yes, but that isn't always -- or even usually -- what you want.
There are some cases where the DLL is deliberately replacable;
i.e. a DLL that interfaces to databases can be replaced to make
your product work with a different database. But the general
case seems safer; for instance, a library that implements the
standard C++ library and/or a collection of math classes. So
here you would ask for these optimizations. But then you (or
the vendor) find some bugs in the DLL, and so they re-release
it. Do you re-link all your .EXEs? Of course not, because you
expect the DLL to be compatible with the old one. And it is,
too, except that one of the bug fixes cause one of the functions
to refer to a virtual function that (by mistake) wasn't used
before -- and *pow* your program dies a miserable death.

> But as for my original post...
> > Um, what if the DLL contains a base class member function that
> > invokes a virtual member function, which I provide as a part of a
> > derived class in my .OBJ file?  Then the DLL has a (virtual)
> > reference into my code.
>
> I thought this would be a way that a DLL could "refer to" a function
> outside of itself, but in retrospect I believe this is not the case;
> a virtual table reference is merely a call to a function through a
> (vtable) pointer which is supplied at runtime from outside the
> (base class code in the) DLL.  The derived vtable resides somewhere
> outside the DLL (base class) code, so I don't think it really
> qualifies as an "external reference".

Right, so the big debate is how to safely optimize away functions
which have no reference except the virtual table. For the general
case this is very important, but for certain cases this turns out
to be a very bad idea.

> But this still doesn't change my point that having access to
> (or the ability to analyze) inter-function dependencies between
> your object code and third-party libraries might lead to smaller
> executables by eliminating unnecessary (derived) virtual functions.

I believe you're right. And for "object libraries" (the type where
individual modules are added to your code, based on unresolved
references), this is an important concept.

But if the third-party libraries are "shared libraries" (the type
where the whole thing is brought into memory at run-time, if any
part of it is needed), then this seems to be one of the cases where
doing this type of optimization is a bad idea, for the reasons
listed above.

> And I don't believe import LIBs give the linker this kind of
> information.

Not at present. We were, however, talking about what types of
optimization could be done in the future. If this requires a
new format of .LIB file, that certainly wouldn't automatically
make it infeasible.

--
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

AllanW@my-dejanews.com wrote:
>>> How common is it to have a base class in a DLL, which is overridden
>>> by a derived class in another DLL or in the .EXE?
>
> I asked this question, because if it's not very common then it would
> be no big loss to skip this particular optimization in that case.

Pete Becker <petebecker@acm.org> wrote:
>> It's quite common. OWL and MFC, for example, ship as DLLs, and you
>> use them by deriving from the classes that they define.

Allan:
> That's true, but in these cases we don't want to optimize away any
> of the overriding functions anyway.

Unless you can prove (by inter-function analysis) that they are never
called.

> A better version of the same question: how common is it to have a
> base class in a Shared Library (to avoid OS-dependant terms), which
> is overridden by a derived class in the executable image, and yet
> the overridden versions of those member functions are not used (and
> so should, ideally, be supressed)?

It's probably common for classes that require a lot of derived
functions to be overridden (such as by declaring them all as pure
virtuals).  In such programs, I would guess that it's unlikely
that *all* of the virtual functions ever get called.  Another way
of asking this is: how much of a class (i.e., how many of its
member functions) does a program really use?  For nontrivial
classes, it's pretty unlikely that a given program uses all of
the class's functions.

For example, consider an I/O class that provides several input and
several output functions.  If I define a derived class that
overrides all of these virtual functions, but my program only
uses the output functions, it seems plausible that the input
functions of my derived class could be excluded from the
executable, with the proper analysis.

-- David R. Tribble, dtribble@technologist.com --


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

I'm following up on my own message because I later realized (while
washing dishes) that I was not quite correct in my post:

phalpern@truffle.ma.ultranet.com (Pablo Halpern) wrote:

>
>Pete Becker <petebecker@acm.org> wrote:
>
>>AlanStokes@my-dejanews.com wrote:
>>>
>>>
>>> The polymorphic call in X::f() must call X::g() when the X base of the Y
>>> object is constructed. I suspect the various algorithms proposed might omit
>>> X::f() (but not X::g(), which really is never called!).
>>
>>Oooooh, devious! It looks like you've identified the killer case.
>
>No. All you've identified is one case among thousands where call-flow
>analysis can do better than static analysis.  My algorithm is specificly
>stated not to do flow analysis and therefore has the limitations of
>static analysis.  In real life, I doubt this "killer case" comes up
>often enough to cause real code bloat.

Actually, what you are describing does not involve dynamic call-flow
analysis. Static call-graph analysis will do. The linker already does
some of this, so it is not totally unreasonable to add this
optimization.

My rules for minimal inclusion of virtual functions expanded as follows
(for the purpose of these rules, taking the address of a function is
equivalent to calling it):

A virtual function, X::f() must be linked in to the executable IF:

  1. X::f() is called statically from another linked-in function

          OR

  2. a) An object of class X is created in the program AND
     b) f() is called polymorphically through X or a base class of X.

          OR

  3. a) A constructor for X is called through a derived-class
        constructor AND
     b) The static call graph for either the called constructor or the
        destructor for X includes this->f().

A less-effective set of rules to remove unused virtual functions
collapses conditions 2 and 3 into:

  2'. a) A constructor for X is called, directly or indirectly AND
      b) f() is called polymorphically through X or a base class of X.

This was my original rule. This simplification means that if X::f() is
called indirectly through the constructor for X, then, for derived class
Y, Y::f() will be linked in even if it is never used.

-------------------------------------------------------------
Pablo Halpern                   phalpern@truffle.ultranet.com

I am self-employed. Therefore, my opinions *do* represent
those of my employer.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35D21777.51EB@noSPAM.central.beasys.com>,
  dtribble@technologist.com wrote:
>
> markw@silicon-spice.com wrote:
> > ...
> > the linker _always_  has access to the entire program.
>
> Except on Win/NT when you link against DLLs; the linker doesn't
> read the .DLL files, but rather uses the "export library" .LIB
> files, which contain stub functions to invoke the actual functions
> in the DLL at runtime.  So there is some information about the
> entire program that the linker doesn't have at link time (at least
> on Win/NT).

Yes, but so what? The DLL has already been linked; it contains what
it contains. It might have to, to support multiple clients including
some we haven't started yet, and others from third parties...

The .LIB file tells us what functions are in the DLL. These functions
never have to be in the .EXE file, and any dependant function is
already also in the DLL (or in some other DLL). So find references
to all of these symbols and mark them satisfied, then continue.

> Hopefully, it's enough to do some function dependency
> analysis, but I don't know this for sure.

I think you're implying that the DLL might have a reference to a symbol
in the .EXE. This is possible but difficult and extremely rare -- so
rare that we can disallow it completely. Usually if the client has to
supply any information to the DLL it can pass the address to the DLL in
a start-up initialization, so this is done at run-time instead of link
time.

No other function dependency analysis is needed for the DLL.

> The situation might be the same for Unixes, except for the fact
> that (most) Unixes read the shared library (.so) file directly at
> link time.  So these systems _do_ have the benefit of access to the
> whole program at link time.

But again, they certainly aren't going to change them!

--
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

markw@silicon-spice.com wrote:
>>> ...
>>> the linker _always_  has access to the entire program.

I, David R Tribble, dtribble@technologist.com wrote:
>> Except on Win/NT when you link against DLLs; the linker doesn't
>> read the .DLL files, but rather uses the "export library" .LIB
>> files, which contain stub functions to invoke the actual functions
>> in the DLL at runtime.  So there is some information about the
>> entire program that the linker doesn't have at link time (at least
>> on Win/NT).

AllanW@my-dejanews.com wrote:
> Yes, but so what? The DLL has already been linked; it contains what
> it contains. It might have to, to support multiple clients including
> some we haven't started yet, and others from third parties...
>
> The .LIB file tells us what functions are in the DLL. These functions
> never have to be in the .EXE file, and any dependant function is
> already also in the DLL (or in some other DLL). So find references
> to all of these symbols and mark them satisfied, then continue.

Me:
>> Hopefully, it's enough to do some function dependency
>> analysis, but I don't know this for sure.

Allan:
> I think you're implying that the DLL might have a reference to a
> symbol in the .EXE. This is possible but difficult and extremely rare
> -- so rare that we can disallow it completely.

Um, what if the DLL contains a base class member function that
invokes a virtual member function, which I provide as a part of a
derived class in my .OBJ file?  Then the DLL has a (virtual)
reference into my code.  I would imagine that that sort of
situation is not rare at all, but in fact quite common.

Allan:
> No other function dependency analysis is needed for the DLL.

The point of this thread was trying to come up with ways that the
linker can omit unused virtual member functions.  This requires
some inter-function analysis, to know which functions call which
other functions.  My point was that the .LIB "import" files
probably don't contain enough information about the .DLL contents
(function code) to do such analysis.

-- David R. Tribble, dtribble@technologist.com --
-- Win95: Start me up... You make a grown man cry...


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35D4B2AC.4C25@noSPAM.central.beasys.com>,
  dtribble@technologist.com wrote:
>
> markw@silicon-spice.com wrote:
> >>> ...
> >>> the linker _always_  has access to the entire program.
>
> David R Tribble, dtribble@technologist.com wrote:
> >> Except on Win/NT when you link against DLLs; the linker doesn't
> >> read the .DLL files, but rather uses the "export library" .LIB
> >> files, which contain stub functions to invoke the actual functions
> >> in the DLL at runtime.  So there is some information about the
> >> entire program that the linker doesn't have at link time (at least
> >> on Win/NT).
>
> AllanW@my-dejanews.com wrote:
> > Yes, but so what? The DLL has already been linked; it contains what
> > it contains. It might have to, to support multiple clients including
> > some we haven't started yet, and others from third parties...
> >
> > The .LIB file tells us what functions are in the DLL. These functions
> > never have to be in the .EXE file, and any dependant function is
> > already also in the DLL (or in some other DLL). So find references
> > to all of these symbols and mark them satisfied, then continue.
>
> David:
> >> Hopefully, it's enough to do some function dependency
> >> analysis, but I don't know this for sure.
>
> Allan:
> > I think you're implying that the DLL might have a reference to a
> > symbol in the .EXE. This is possible but difficult and extremely rare
> > -- so rare that we can disallow it completely.
>
David:
> Um, what if the DLL contains a base class member function that
> invokes a virtual member function, which I provide as a part of a
> derived class in my .OBJ file?  Then the DLL has a (virtual)
> reference into my code.  I would imagine that that sort of
> situation is not rare at all, but in fact quite common.

The DLL still doesn't have a reference into the .EXE. Instead, the
.EXE constructs a virtual table, and the object contains a pointer
to this table rather than to the virtual table (in the DLL) for the
base object.

> Allan:
> > No other function dependency analysis is needed for the DLL.
>
> The point of this thread was trying to come up with ways that the
> linker can omit unused virtual member functions.  This requires
> some inter-function analysis, to know which functions call which
> other functions.  My point was that the .LIB "import" files
> probably don't contain enough information about the .DLL contents
> (function code) to do such analysis.

In the case of a .DLL that will be used by several clients, you
*don't want* these virtual functions supressed. You still want
to eliminate unused virtual functions in the .EXE, though...

Oh, I see what you're getting at. Some function complicate() in
the DLL has a reference to Base::memberfunc(), which is virtual.
And the .EXE defines class Derived:public Base, which overrides
memberfunc(). But nothing in the .EXE calls Derived::memberfunc
or even Base::memberfunc, so we can omit Derived::memberfunc
from the .EXE -- unless some function calls complicate(), even
indirectly...

Yeesh.

Okay, I see what you're saying -- if we could examine the .OBJ
files used to create the .DLL, then we could possibly recognize
that complicate() will never be called, and so there is no
reference to any version of memberfunc(). The DLL already
includes Base::memberfunc, but at least we can omit
Derived::memberfunc from the .EXE. Is that right?

...but no, even if we could do this, it wouldn't be sufficient.
Because if we supress Derived::memberfunc based on the knowledge
that the .DLL will never call it, we will break when the next
version of the .DLL is distributed, because perhaps it *will*
call Base::memberfunc. One of the many uses of DLLs allows the
programmer to replace parts of the program without re-linking
the other parts.

How common is it to have a base class in a DLL, which is overridden
by a derived class in another DLL or in the .EXE? Maybe the only
good answer to this problem is to skip this optimization in this
situation. DLL's would never supress any member functions, and
.EXE's would never supress virtual member functions in a class
with base classes in DLLs.

--
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

markw@silicon-spice.com wrote:
> ...
> the linker _always_  has access to the entire program.

Except on Win/NT when you link against DLLs; the linker doesn't
read the .DLL files, but rather uses the "export library" .LIB
files, which contain stub functions to invoke the actual functions
in the DLL at runtime.  So there is some information about the
entire program that the linker doesn't have at link time (at least
on Win/NT).  Hopefully, it's enough to do some function dependency
analysis, but I don't know this for sure.

The situation might be the same for Unixes, except for the fact
that (most) Unixes read the shared library (.so) file directly at
link time.  So these systems _do_ have the benefit of access to the
whole program at link time.

-- David R. Tribble, dtribble@technologist.com --
-- Win95: Start me up... You make a grown man cry...


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35D21777.51EB@noSPAM.central.beasys.com>,
  dtribble@technologist.com wrote:
>
> markw@silicon-spice.com wrote:
> > ...
> > the linker _always_  has access to the entire program.
>
> Except on Win/NT when you link against DLLs; the linker doesn't
> read the .DLL files, but rather uses the "export library" .LIB
> files, which contain stub functions to invoke the actual functions
> in the DLL at runtime.  So there is some information about the
> entire program that the linker doesn't have at link time (at least
> on Win/NT).  Hopefully, it's enough to do some function dependency
> analysis, but I don't know this for sure.
>

Yes. I thought this had been covered several times. i) Embedded systems are
unlikely to be using dlls (for various reasons). Of course, this optimization
is of interest in other areas too, but its not a big deal on most modern
desktop machines (although the related problem of resolving virtual calls
statically _is_ of interest here). ii) If you are creating a DLL, then you
typically dont want to dead strip (because you have no idea which functions
potential clients may use). The only case where you may want to is where you
have a fixed set of clients - in which case, you _do_ have all the code
avaialble. iii) If you are creating a program which links against a DLL, then
it is possible to store enough information in the dll, or stub library to
dead strip the client. Typically, general purpose DLLs have C only
interfaces, because of the fragile base class problem, and so can have very
little impact on which virtual functions can be stripped.

I think that just about covers it...

Mark Williams

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6qcbq6$fet$1@nnrp1.dejanews.com>,
  markw65@my-dejanews.com wrote:
> In article <6qakhd$c9e$1@nnrp1.dejanews.com>,
>   AllanW@my-dejanews.com wrote:
> > In article <6q9p8b$rnd$1@nnrp1.dejanews.com>,
> >   markw@silicon-spice.com wrote:
> <snip>
> > >
> > > struct Z: Y {
> > >    virtual void g() { }
> > > };
> > >
> > > void main(int argc, char **argv) {
> > >    Y y;
> > >    X x;
> > >    Z z;
> > >
> > >    X *p = argc > 1 ? &y : &x;
> > >    p->f();
> > > }
> > >
> > > main -> Y::Y -> X::X -> X::f -> X::g
> > >      -> X::X -> X::f -> X::g
> > >      -> Z::Z -> Y::Y -> X::X -> X::f -> X::g
> > >      -> X::f -> {X::g, Y::g}
> > >
> > > And we can strip Z::g, illustrating that the technique can still work for
> > > programs which contain virtual calls whose destination cannot be resolved
at
> > > compile time
> > >
> > > Again... Im not claiming you cant fool this algorithm... you can; but it
> > > works pretty well for a large number of common cases. In fact it does
much
> > > better than just strip unwanted virtuals, it can change virtual calls
into
> > > non-virtual calls, enabling other optimizations such as inlining etc.
> > >
> > > Mark Williams
> >
> > You've pretty well documented how a manual analysis would work. If I was
> > manually selecting which functions to include, and which to exclude, I
> > would go through exactly the same steps you did.
> >
> > Would you care to expound on an algorithm to be used by linkers and/or
> > compilers, to accomplish the same thing?  It's no good saying
> >     "Figure out if Z::g() can be called"
> > because Figuring It Out is what this whole thread is about. Instead, say
> >     "If the code calls g() on a pointer whose static type is X, then we
> >      must include X::g and Y::g because the actual type could be X or Y.
> >      But we can leave out Z::g because ..."
> > and then finish the sentance.  For instance, are you suggesting that the
> > compiler should recognize that even though a Z is constructed, we never
> > take it's address, and therefore we never have a Z pointer? Be specific.
> >
>
> Im sorry, I was deliberately not specific, because there are many different
> techniques for doing this. They are essentially well known (to compiler
> writers at any rate), and commonly implemented (take a look at the nullstone
> alias optimizations for some examples of what compilers can be expected to
> do). They range from fairly simple, and very fast (with conservative results)
> to extremely complex and time consuming (with generally much better results).

This could be; I don't pretend to be an expert on the subject. What I
do know is that optimization is in some respects like the card game
"21:" you want to get as close as possible to some ideal, but you never
want to go too far. If your algorithm ever, *ever* takes out even *one*
virtual function that really was needed, then your algorithm is in the
category of "unsafe optimizations." That means you better supply an
on/off switch, to handle cases where it does things wrong, and you also
better make the default "off" because a lot of your customers won't have
the time or the inclination to find out when it's safe and when it isn't
(no matter how good your documentation :-).

> So, a simple algorithm would notice that the only assignments ever made to p
> are pointers to objects whose underlying types are known to be X & Y
> respectively; hence the call cannot be through a Z.
>
> Now you can easily break this, by changing the code to
>
> void main(int argc, char **argv) {
>     Y y;
>     X x;
>     Z z;
>
>     X *p;
>     p = &z;
>     p = argc > 1 ? &y : &x;
>     p->f();
>  }
>
> But I hope I dont have to say that redundant store elimination is a rather
> trivial optimization...

I had assumed that all of your examples, although small, were illustrating
larger problems.  Consider:
    void f2(int&x, X*p) {
        if (x<3) p->f();
    }
    // void main() -- NO! Not legal
    int main(int argc, char **argv) {
        Y y;
        X x;
        Z z;

        X *p;
        switch (argc) {
            case 0: case 1: p = &x; break;
            case 2:         p = &y; break;
            default:        p = &z; break;
        }
        f2(argc,p);
        return 0;
    }
Would you expect the compiler to omit Z::g() in this more general case?
But this is closer to realistic (although still far away). Why play
around with pointers, unless you're passing them to some other function
dynamically? It's unrealistic to think that more than a few virtual
function calls will be from the same scope that created the dynamic
objects.

> We could also break it by saying
>
> void main(int argc, char **argv) {
>     Y y;
>     X x;
>     Z z;
>
>     X *p;
>     p = argc > 1 ? &y : &x;
>     p->f();
>     p = &z;
>     p->q();
>  }
>
> [lets just assume that the analysis of q() is trivial enough that it doesnt
> introduce any new problems]

This is my point --  you can't keep assuming everything is trivial,
because sooner or later your theory will bump into a brick wall.

> Now we are still not able to remove Z::g using the algorithm described. (In
> practice of course the optimizer would change the last call to z.q(), and then
> eliminate the store of &z to p, at which point it would be possible again...)
>
> But we _can_ solve this one, by doing flow sensitive pointer analysis; at the
> callsite to X::f, p can only point to an X or a Y.
>
> The fact is that you dont have to do any of this; in which case Nathan's
> original algorithm would probably hit a large number of the cases of interest
> in the standard library. You could use the simple algorithm above, and hit
> some more. You could use cross module, flow sensitive pointer analysis, and
> get even better results... how far do you want to go? :-)

I suppose the ultimate would be to have a special "analysis" build, in
which the run-time system identifies all virtual functions called. Then
the programmer would be responsible for executing a thorough test script,
intended to exercise every virtual function at least once. When she's
finished she would re-link using the collected run-time flow analysis,
excluding all virtual functions that were never called.

But even this extreme (you do agree it's extreme, right?) would have
some serious problems. First, programmers generally aren't as thorough
at testing as they think they are; inevitably there would be some
functions omitted that shouldn't be. And second, some functions are
intended to be called on a "rare" basis -- for example, error-handling
code might not trigger unless some hardware error occurs. Simulating
this would be difficult. So we would have to provide hooks so that a
programmer could say "include this function even if it's not hit in
a run-time flow analysis..."

--
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

| ...You cannot strip unused (non-static) functions (let alone virtual
| functions) without access to the whole program. Period.
|
| Does this actually change the problem? No. Because the linker _always_
| has access to the entire program....

That may have been true at one time, but it no longer is:  Most OS's
used today support dynamic loading.  In this case, only the dynamic
linker has access to the whole program - and even *it* can't know when
it's seen the whole program, since there's no way to know when you've
seen the *last* dynamically-loaded module.

BTW, libraries in general - dynamically loaded or not - add a new level
of "separate compilation" that is not currently dealt with well, if at
all.  Even compilers that are good about keeping only one copy of each
template instantiation will still leave you with one copy *per library*
if multiple libraries instantiate the same way.  There's plenty of work
yet to be done....
       -- Jerry


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

AllanW@my-dejanews.com wrote:
>
> In article <6q9p8b$rnd$1@nnrp1.dejanews.com>,
>   markw@silicon-spice.com wrote:
> > In article <6q7nfd$isr$1@nnrp1.dejanews.com>,
> >   AllanW@my-dejanews.com wrote:

[...]
> > > In article <6pn7br$fjg$1@nnrp1.dejanews.com>,
> > >   AlanStokes@my-dejanews.com wrote:
> > > > I don't think this is sufficient. Consider the following, where no X is
> ever
> > > > constructed, and yet one of X's functions is called polymorphically:
> > > >
> > > > struct X {
> > > >    X() { f(); }
> > > >    void f() { g(); }
> > > >    virtual void g() { }
> > > > };
> > > >
> > > > struct Y : X {
> > > >    virtual void g() { }
> > > > };
> > > >
> > > > void main() {
> > > >    Y y;
> > > > }
> > > >
> > > > The polymorphic call in X::f() must call X::g() when the X base of the Y
> > > > object is constructed. I suspect the various algorithms proposed might
> omit
> > > > X::f() (but not X::g(), which really is never called!).
> > >
> > > Let's assume that all the functions f() and g() are too big to inline.
> > > X's constructor can easily recognize that it will always call X::f(),
> > > even if some derived class overrides f.
> > >
> > > But X::f() can't make that assumption, unless you generate two
> > > versions (one to call from X's constructor, and another one to
> > > call at any other time). When X::f() is called from X's
> > > constructor, the call to g() must call X::g(). But if it was
> > > called from Y's constructor it would have to call Y::g().
> > >
> > > The first compliant compiler/linker vendor that manages to omit Y::g()
> > > from from the build without any additional clues from the user, will
> > > earn the awe and respect (and probably the dollars!) of many of us.
> >
> > OK, so I build the static call graph:
> >
> > main -> Y::Y -> X::X -> X::f -> X::g
> >
> > Now... those are the only functions that can be called, so omit everything
> > else.
> >
> > Like I said, trivial. Have I earned your awe yet? If so, start sending those
> > dollars :-)
> >
> > Since I can tell that you're going to come back and say Im cheating :-) Ill
> > show you how I would build the call graph for some other cases.
> >
> > void main() {
> >    Y y;
> >    y.f();
> > }
> >
> > now the graph looks like
> >
> > main -> Y::Y -> X::X -> X::f -> X::g
> >      -> X::f -> Y::g
> >
> > And in this case there is nothing to strip, but we still "know" where all the
> > calls go... for suitable f (and profiling info) it may be worth duplicating
> > the code to eliminate the virtual tables/dispatch altogether.
> >
> > struct Z: Y {
> >    virtual void g() { }
> > };
> >
> > void main(int argc, char **argv) {
> >    Y y;
> >    X x;
> >    Z z;
> >
> >    X *p = argc > 1 ? &y : &x;
> >    p->f();
> > }
> >
> > main -> Y::Y -> X::X -> X::f -> X::g
> >      -> X::X -> X::f -> X::g
> >      -> Z::Z -> Y::Y -> X::X -> X::f -> X::g
> >      -> X::f -> {X::g, Y::g}
> >
> > And we can strip Z::g, illustrating that the technique can still work for
> > programs which contain virtual calls whose destination cannot be resolved at
> > compile time
> >
> > Again... Im not claiming you cant fool this algorithm... you can; but it
> > works pretty well for a large number of common cases. In fact it does much
> > better than just strip unwanted virtuals, it can change virtual calls into
> > non-virtual calls, enabling other optimizations such as inlining etc.
> >
> > Mark Williams
>
> You've pretty well documented how a manual analysis would work. If I was
> manually selecting which functions to include, and which to exclude, I
> would go through exactly the same steps you did.
>
> Would you care to expound on an algorithm to be used by linkers and/or
> compilers, to accomplish the same thing?  It's no good saying
>     "Figure out if Z::g() can be called"
> because Figuring It Out is what this whole thread is about. Instead, say
>     "If the code calls g() on a pointer whose static type is X, then we
>      must include X::g and Y::g because the actual type could be X or Y.
>      But we can leave out Z::g because ..."
> and then finish the sentance.  For instance, are you suggesting that the
> compiler should recognize that even though a Z is constructed, we never
> take it's address, and therefore we never have a Z pointer? Be specific.

Well, maybe the solution would be a "type flow graph".

This would work like the following:

1. For each function, determine the "polymorphic interface".
   The "polymorphic interface" consists of the polymorphic types
   and pointers/references to those going in and out through the
   function call interface and through called functions (including
   member functions). Casts can be treated like function calls
   returning the type casted to.

   Example:

   The constructor of X would have the polymorphic interface
   passes an exact X to X::f() // as this pointer

   X::f() would have the polymorphic interface:
   receives an unconstrained X
   calls virtual g() on unconstrained X

   The function
     X* f(Y* y, X*& x) { x=y; return x; }
   would have the polymorphic interface:
   receives an unconstrained X and an unconstrained Y
   returns two unconstrained X

   (Note that still information is thrown away; the compiler
   might generate better info, but that would be more expensive;
   here the rule is: If an unconstrained X is received, assume
   all outgoing X to be unconstrained, if allowed by the type.
   If the compiler can generate better informmation, the better.
   In this case the compiler could note that all outgoing types are
   constrained to be at least an Y.)

2. Given that information, the linker builds the function call
   graph using that information. For example, on the "killer"
   it would first analyse main, and find it passes no object,
   but calls X::X(). Therefore X::X() would be analysed, which
   passes an exact X to X::f(). Now the interesting part begins.

   X::f() is known to receive a polymorphic type X. Now, we have
   one call to X::f() with a known type of X, that is, there's
   one place where we know that an X is passed. The linker would
   note that f is once passed an exact X, and would therefore
   conclude that *up to now*, only X::g() can be called, given an
   exact X too. Therefore it would link in X::g() and go on
   analysing that. If there are later calls to X::f(), the analysis
   must be done again, since this time, the type might be Y, Z,
   anything above an Y, or anything above an X. If more than one
   possibility exists, all possible g()'s must be linked in *and*
   analysed.

   This analyse would be expensive (esp. since some work will have
   to be effectively done twice), however it would throw out far
   more virtual functions than the simpler models. It would obviously
   work best with functions with few polymorphic parameters.
   Also, the better the compiler generated info (that is, the
   more local flow analysis the compiler does), the better the
   linker can throw out virtual functions.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6qakhd$c9e$1@nnrp1.dejanews.com>,
  AllanW@my-dejanews.com wrote:
> In article <6q9p8b$rnd$1@nnrp1.dejanews.com>,
>   markw@silicon-spice.com wrote:
<snip>
> >
> > struct Z: Y {
> >    virtual void g() { }
> > };
> >
> > void main(int argc, char **argv) {
> >    Y y;
> >    X x;
> >    Z z;
> >
> >    X *p = argc > 1 ? &y : &x;
> >    p->f();
> > }
> >
> > main -> Y::Y -> X::X -> X::f -> X::g
> >      -> X::X -> X::f -> X::g
> >      -> Z::Z -> Y::Y -> X::X -> X::f -> X::g
> >      -> X::f -> {X::g, Y::g}
> >
> > And we can strip Z::g, illustrating that the technique can still work for
> > programs which contain virtual calls whose destination cannot be resolved at
> > compile time
> >
> > Again... Im not claiming you cant fool this algorithm... you can; but it
> > works pretty well for a large number of common cases. In fact it does much
> > better than just strip unwanted virtuals, it can change virtual calls into
> > non-virtual calls, enabling other optimizations such as inlining etc.
> >
> > Mark Williams
>
> You've pretty well documented how a manual analysis would work. If I was
> manually selecting which functions to include, and which to exclude, I
> would go through exactly the same steps you did.
>
> Would you care to expound on an algorithm to be used by linkers and/or
> compilers, to accomplish the same thing?  It's no good saying
>     "Figure out if Z::g() can be called"
> because Figuring It Out is what this whole thread is about. Instead, say
>     "If the code calls g() on a pointer whose static type is X, then we
>      must include X::g and Y::g because the actual type could be X or Y.
>      But we can leave out Z::g because ..."
> and then finish the sentance.  For instance, are you suggesting that the
> compiler should recognize that even though a Z is constructed, we never
> take it's address, and therefore we never have a Z pointer? Be specific.
>

Im sorry, I was deliberately not specific, because there are many different
techniques for doing this. They are essentially well known (to compiler
writers at any rate), and commonly implemented (take a look at the nullstone
alias optimizations for some examples of what compilers can be expected to
do). They range from fairly simple, and very fast (with conservative results)
to extremely complex and time consuming (with generally much better results).

So, a simple algorithm would notice that the only assignments ever made to p
are pointers to objects whose underlying types are known to be X & Y
respectively; hence the call cannot be through a Z.

Now you can easily break this, by changing the code to

void main(int argc, char **argv) {
    Y y;
    X x;
    Z z;

    X *p;
    p = &z;
    p = argc > 1 ? &y : &x;
    p->f();
 }

But I hope I dont have to say that redundant store elimination is a rather
trivial optimization...

We could also break it by saying

void main(int argc, char **argv) {
    Y y;
    X x;
    Z z;

    X *p;
    p = argc > 1 ? &y : &x;
    p->f();
    p = &z;
    p->q();
 }

[lets just assume that the analysis of q() is trivial enough that it doesnt
introduce any new problems]

Now we are still not able to remove Z::g using the algorithm described. (In
practice of course the optimizer would change the last call to z.q(), and then
eliminate the store of &z to p, at which point it would be possible again...)

But we _can_ solve this one, by doing flow sensitive pointer analysis; at the
callsite to X::f, p can only point to an X or a Y.

The fact is that you dont have to do any of this; in which case Nathan's
original algorithm would probably hit a large number of the cases of interest
in the standard library. You could use the simple algorithm above, and hit
some more. You could use cross module, flow sensitive pointer analysis, and
get even better results... how far do you want to go? :-)

Hope this makes things clearer.

Mark Williams

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35C8E483.604C2EB6@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:
>
>  Fine. This needs to be stated explicitly when you say that you know how
> to solve this problem, because you are offering a constrained solution,
> not a general solution. (If I were trying to "misrepresent" the
> situation I would claim that this means you are compiling some language
> other than C++.)

This is getting ridiculous.

You cannot strip unused (non-static) functions (let alone virtual functions)
without access to the whole program. Period.

Does this actually change the problem? No. Because the linker _always_ has
access to the entire program. The optimizations described so far all involve
some degree of cooperation between compiler and linker. The fact that
traditional linkers _dont_ do "compiler-style" optimizations doesnt mean that
linkers _cant_ do them (with sufficient cooperation from the compiler).

So requiring access to all sources/objects does not make this a constrained
solution.

On the other hand, it isnt a general solution (and nobody has claimed that it
is). It will always be possible to construct programs which have unused
virtual functions that the compiler cannot strip. But its the same with any
optimization.

>
> >
> > In any case, if all of the source (or objects) are not available at compile
> > time, then they must be available at link time. So move the processing into
> > the linker. There are a number of compilers which do this. The object files
> > consist of an internal representation of the code. When the linker is
> > invoked, it effectively runs the compiler on the combined source of the
> > entire program.
>
>  I'm confused by your tenses. When you say "the object files consist of"
> do you mean that that's what they are today, or that it would be
> possible to implement a compiler that does this? If the latter, please
> tell me when that's going to ship. To the best of my knowledge, object
> files contain machine code and linking information, that is, a great
> deal less information than is contained in the source files.

You are easily confused. I will repeat what I said before with notes.

> There are a number of compilers which do this.
[note for pete: Im using the present tense because these compilers exist]

> The object files consist of an internal representation of the code.
> When the linker is invoked, it effectively runs the compiler on the
> combined source of the entire program.
[still using present tense. this is how these compilers work]

If you want examples, then SGIs MIPSPro compiler has worked like this for
maybe 2 years.

[I am not talking about removing unused functions, just about doing cross
module optimizations at link time]

The compiler I am currently working on also does this (and has done for nearly
a year), but is not commercially available.

Mark Williams

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

markw@silicon-spice.com wrote:
>
> In article <35C8E483.604C2EB6@acm.org>,
>   Pete Becker <petebecker@acm.org> wrote:
> >
> >       Fine. This needs to be stated explicitly when you say that you know how
> > to solve this problem, because you are offering a constrained solution,
> > not a general solution. (If I were trying to "misrepresent" the
> > situation I would claim that this means you are compiling some language
> > other than C++.)
>
> This is getting ridiculous.

Sorry. I've been so frustrated at seeing so much marketing hype where
there should be good technical analysis that I overreacted.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

That's not true.

There are two cases: you're writing a new dynamic library, or you're
using one from your client program (which could itself be another
dynamic library).

In the first case, the new dynamic library probably has functions that
you want to have available for the clients, even though it may not be
used by the dynamic library itself. You could, I suppose, create a list
of functions that you want to instanciate even if it appears unused.
An easier way to deal with the same problem is to turn off this
optimization. Dynamic libraries are a special case.

In the second case, the new client has references to the dynamic library.
But the OS or run-time system has to know which dynamic library to load,
so this information must be present at link time anyway. Typically
compilers make this as easy as linking in any other library; the same
type of file that contains static libraries is extended to hold
information about dynamic library contents, and you include this library
information file in your link.

A slightly harder scenario is that the dynamic library has a reference
that the client must satisfy. This is rare, but it can be handled the
same way -- with information in the library file. If the client is
the final executable, then all references must be satisfied; if the
client is still another dynamic library, then the reference goes into
this new client's library information file as well.

By the time we get to the linker, it has *ALL* the information it
needs to accomplish the link. (By definition -- because every tool
that generates input to the linker is required to record all of
the information that the linker will need!)

> BTW, libraries in general - dynamically loaded or not - add a new level
> of "separate compilation" that is not currently dealt with well, if at
> all.  Even compilers that are good about keeping only one copy of each
> template instantiation will still leave you with one copy *per library*
> if multiple libraries instantiate the same way.  There's plenty of work
> yet to be done....

Which isn't a big problem if the linker removes the duplicates. Hardly
new technology; FORTRAN compilers have been doing this since the 1960's;
it was once their only form of "global" variables (see keyword COMMON in
your nearby FORTRAN manual). Most linkers call this a "COMDEF" which is
short for "COMMON Definition."

--
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Yes, of course. But more because it will likely bump up your build time by
significant amounts, depending on the algorithm chosen, than because of
possible errors; for this particular optimization I would expect no more
errors than say in the code generator (something which cant be turned off
:-). ie implementation errors, rather than algorithmic errors.

>
> I had assumed that all of your examples, although small, were illustrating
> larger problems.

Of course.

>  Consider:
>     void f2(int&x, X*p) {
>         if (x<3) p->f();
>     }
>     // void main() -- NO! Not legal
>     int main(int argc, char **argv) {
>         Y y;
>         X x;
>         Z z;
>
>         X *p;
>         switch (argc) {
>             case 0: case 1: p = &x; break;
>             case 2:         p = &y; break;
>             default:        p = &z; break;
>         }
>         f2(argc,p);
>         return 0;
>     }
> Would you expect the compiler to omit Z::g() in this more general case?
> But this is closer to realistic (although still far away). Why play
> around with pointers, unless you're passing them to some other function
> dynamically? It's unrealistic to think that more than a few virtual
> function calls will be from the same scope that created the dynamic
> objects.

I dont think it would be particularly hard to pick up this kind of code. But
I would also argue that its _not_ typical (and therefore probably not worth
it). In fact come to that, the original class structure is not typical
either... base class constructors indirectly calling virtual functions which
are not called from anywhere else? Maybe I lead a sheltered life:-)

By the way, just so you dont think Im being too glib about saying "not that
hard"... here is an example of an optimization our compiler already does:

int main(int argc, char **argv) {
    Y y;
    X x;
    Z z;
    X *p;
    switch (argc) {
        case 0: case 1: p = &x; break;
        case 2:         p = &y; break;
        default:        p = 0; break;
    }

 if (argc == 5) {
        /*
   The entire if clause will be deleted
  */
  p->f();
 }

 if (argc == 2 && p == &x) {
  // deleted
 }

    return 0;
}

<snip>

> >
> > [lets just assume that the analysis of q() is trivial enough that it doesnt
> > introduce any new problems]
>
> This is my point --  you can't keep assuming everything is trivial,
> because sooner or later your theory will bump into a brick wall.
>

The only thing Im assuming is trivial is q. Which was introduced to make the
example slightly more complicated than the one we _were_ talking about to
demonstrate the difference in effectiveness between two techniques (which
were otherwise equivalent on the original example). I dont think its
unreasonable to ignore q for the purpose of that demonstration.

But I agree... however good a compiler is at recognising unused functions, you
will be able to come up with an example that it cannot deal with.

<snip>

> > The fact is that you dont have to do any of this; in which case Nathan's
> > original algorithm would probably hit a large number of the cases of interest
> > in the standard library. You could use the simple algorithm above, and hit
> > some more. You could use cross module, flow sensitive pointer analysis, and
> > get even better results... how far do you want to go? :-)
>
> I suppose the ultimate would be to have a special "analysis" build, in
> which the run-time system identifies all virtual functions called. Then
> the programmer would be responsible for executing a thorough test script,
> intended to exercise every virtual function at least once. When she's
> finished she would re-link using the collected run-time flow analysis,
> excluding all virtual functions that were never called.
>
> But even this extreme (you do agree it's extreme, right?) would have
> some serious problems.

Yes. It would be completely useless. No, make that almost completely... You
could use it to get an upper bound for what was achievable, and then rate the
compiler's performance (using the earlier techniques) by how close it came.
But for production code? You must be joking.

> First, programmers generally aren't as thorough
> at testing as they think they are; inevitably there would be some
> functions omitted that shouldn't be. And second, some functions are
> intended to be called on a "rare" basis -- for example, error-handling
> code might not trigger unless some hardware error occurs. Simulating
> this would be difficult. So we would have to provide hooks so that a
> programmer could say "include this function even if it's not hit in
> a run-time flow analysis..."

Mark Williams

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker <petebecker@acm.org> wrote:

>AlanStokes@my-dejanews.com wrote:
>>
>>
>> The polymorphic call in X::f() must call X::g() when the X base of the Y
>> object is constructed. I suspect the various algorithms proposed might omit
>> X::f() (but not X::g(), which really is never called!).
>
>Oooooh, devious! It looks like you've identified the killer case.

No. All you've identified is one case among thousands where call-flow
analysis can do better than static analysis.  My algorithm is specificly
stated not to do flow analysis and therefore has the limitations of
static analysis.  In real life, I doubt this "killer case" comes up
often enough to cause real code bloat.

-------------------------------------------------------------
Pablo Halpern                   phalpern@truffle.ultranet.com

I am self-employed. Therefore, my opinions *do* represent
those of my employer.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker <petebecker@acm.org> wrote:

>Nathan Myers wrote:
>>
>> No, it doesn't.  Referring to his description of the linker
>> algorithm, when the program contains a call to a Y constructor,
>> that creates the vtbl which contains the "vtbl" reference to X::f().
>> His summary can be refined:
>>
>> >>   a. At least one object of class X [or class Y that inherits
>> >>      X::f] is constructed AND [...]
>
>OK, that's not how I read it, but it's reasonable. It's much weaker than
>I thought it was intended to be. This means that, for example, in a
>single inheritance hierarchy, every version of f from the base down to
>the most derived class that is actually instantiated must be linked in.

I don't think that's quite right.  Let me restate my principles with the
corrrections noted:

The minimal condition for requiring the inclusion of a virtual function,
X::f() that is not called statically is:

  a. The constructor for X is called (directly or indirectly) AND
  b. f() is called polymorphically through a pointer or reference
     to X or one of its base classes.

Thus X::f() is overriden by Y::f() and X::X() does not directly or
indirectly call f(), then there is no polymorphic call to X::f() in the
program and X::f() and Y::f() can be optimized away by my algorithm.
If, on the other hand, X::X() calls a function q() that calls r() that
calls z() which calls f(), then a polymorphic (or static) call to X::f()
would exist and it would be linked in, as it should be. Y::f() would
also be linked in, as you indicated, but I don't see how static analysis
can do better than that in the general case. (In specific cases, such as
direct calls in the constructor, it can generate a static instead of
polymorphic call to X::f() and thus avoid bringing in Y::f().)

>Roughly speaking, it provides the greatest benefit in shallow
>inheritance hierarchies, and less in deep hierarchies.

That is too general a statement, I think.  If any virtual function is
not called at all (e.g. f() is not called through X or any derived
class), then a large number of virtual functions can be eliminated in
both deep and broad hierachies.

-------------------------------------------------------------
Pablo Halpern                   phalpern@truffle.ultranet.com

I am self-employed. Therefore, my opinions *do* represent
those of my employer.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6q4h2a$1vo$1@nnrp1.dejanews.com>,
  markw65@my-dejanews.com wrote:
> In article <35C220B5.D60630AC@ix.netcom.com>,
>   "Paul D. DeRocco" <pderocco@ix.netcom.com> wrote:
> > markw65@my-dejanews.com wrote:
> > >
> > > Not really. A good compiler will often be able to remove the reference
> > > to the base class's virtual table (and its the reference to the
> > > virtual table which matters, not whether or not a class's constructor
> > > was called).
> >
> > How can the compiler or linker know that a particular virtual function
> > won't be invoked during construction or destruction, while a derived
> > object's type is technically still the base class? Such a call may occur
> > indirectly, and therefore be invisible.
>
> By analysing the code :-)
>
> Note the word "often"... not "always"
>
> eg the so called "killer" example which "proved" the ineffectiveness of this
> technique is a particularly easy target...
>
> Dont forget that any virtual functions called directly by the constructor do
> not (need to) go through the virtual table at all.

Which is exactly the point of that "killer" example!  Reposted here
for your convenience:

In article <6pn7br$fjg$1@nnrp1.dejanews.com>,
  AlanStokes@my-dejanews.com wrote:
> I don't think this is sufficient. Consider the following, where no X is ever
> constructed, and yet one of X's functions is called polymorphically:
>
> struct X {
>    X() { f(); }
>    void f() { g(); }
>    virtual void g() { }
> };
>
> struct Y : X {
>    virtual void g() { }
> };
>
> void main() {
>    Y y;
> }
>
> The polymorphic call in X::f() must call X::g() when the X base of the Y
> object is constructed. I suspect the various algorithms proposed might omit
> X::f() (but not X::g(), which really is never called!).

Let's assume that all the functions f() and g() are too big to inline.
X's constructor can easily recognize that it will always call X::f(),
even if some derived class overrides f.

But X::f() can't make that assumption, unless you generate two
versions (one to call from X's constructor, and another one to
call at any other time). When X::f() is called from X's
constructor, the call to g() must call X::g(). But if it was
called from Y's constructor it would have to call Y::g().

The first compliant compiler/linker vendor that manages to omit Y::g()
from from the build without any additional clues from the user, will
earn the awe and respect (and probably the dollars!) of many of us.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

markw65@my-dejanews.com wrote:
>
> In article <35C70005.A20AB915@acm.org>,
>   Pete Becker <petebecker@acm.org> wrote:
> > markw65@my-dejanews.com wrote:
> > >
> > > eg the so called "killer" example which "proved" the ineffectiveness of this
> > > technique is a particularly easy target...
> >
> > But the obvious extension of that example, defining the functions in
> > separate translation units, is nowhere near as easy. So you've fixed a
> > trivial case, not the general problem.
>
> This optimization cant be implemented on a one translation unit at a time
> basis anyway (which is why most of the solutions are described in terms of
> the linker). Solving the slightly more general problem of removing the
> references by doing a little cross module analysis at compile time is really
> not hard.

I have no idea what it means to say that it "can't be implemented" but
that it "is really not hard". C++ does not require that source code or
object code for other translation units be present when code is being
compiled. That's a significant obstacle to "cross module analysis". I
stand by what I said.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6q7nfd$isr$1@nnrp1.dejanews.com>,
  AllanW@my-dejanews.com wrote:
> In article <6q4h2a$1vo$1@nnrp1.dejanews.com>,
>   markw65@my-dejanews.com wrote:
> > In article <35C220B5.D60630AC@ix.netcom.com>,
> >   "Paul D. DeRocco" <pderocco@ix.netcom.com> wrote:
> > > markw65@my-dejanews.com wrote:
> > > >
> > > > Not really. A good compiler will often be able to remove the reference
> > > > to the base class's virtual table (and its the reference to the
> > > > virtual table which matters, not whether or not a class's constructor
> > > > was called).
> > >
> > > How can the compiler or linker know that a particular virtual function
> > > won't be invoked during construction or destruction, while a derived
> > > object's type is technically still the base class? Such a call may occur
> > > indirectly, and therefore be invisible.
> >
> > By analysing the code :-)
> >
> > Note the word "often"... not "always"
> >
> > eg the so called "killer" example which "proved" the ineffectiveness of this
> > technique is a particularly easy target...
> >
> > Dont forget that any virtual functions called directly by the constructor do
> > not (need to) go through the virtual table at all.
>
> Which is exactly the point of that "killer" example!  Reposted here
> for your convenience:
>
> In article <6pn7br$fjg$1@nnrp1.dejanews.com>,
>   AlanStokes@my-dejanews.com wrote:
> > I don't think this is sufficient. Consider the following, where no X is ever
> > constructed, and yet one of X's functions is called polymorphically:
> >
> > struct X {
> >    X() { f(); }
> >    void f() { g(); }
> >    virtual void g() { }
> > };
> >
> > struct Y : X {
> >    virtual void g() { }
> > };
> >
> > void main() {
> >    Y y;
> > }
> >
> > The polymorphic call in X::f() must call X::g() when the X base of the Y
> > object is constructed. I suspect the various algorithms proposed might omit
> > X::f() (but not X::g(), which really is never called!).
>
> Let's assume that all the functions f() and g() are too big to inline.
> X's constructor can easily recognize that it will always call X::f(),
> even if some derived class overrides f.
>
> But X::f() can't make that assumption, unless you generate two
> versions (one to call from X's constructor, and another one to
> call at any other time). When X::f() is called from X's
> constructor, the call to g() must call X::g(). But if it was
> called from Y's constructor it would have to call Y::g().
>
> The first compliant compiler/linker vendor that manages to omit Y::g()
> from from the build without any additional clues from the user, will
> earn the awe and respect (and probably the dollars!) of many of us.

OK, so I build the static call graph:

main -> Y::Y -> X::X -> X::f -> X::g

Now... those are the only functions that can be called, so omit everything
else.

Like I said, trivial. Have I earned your awe yet? If so, start sending those
dollars :-)

Since I can tell that you're going to come back and say Im cheating :-) Ill
show you how I would build the call graph for some other cases.

void main() {
   Y y;
   y.f();
}

now the graph looks like

main -> Y::Y -> X::X -> X::f -> X::g
     -> X::f -> Y::g

And in this case there is nothing to strip, but we still "know" where all the
calls go... for suitable f (and profiling info) it may be worth duplicating
the code to eliminate the virtual tables/dispatch altogether.

struct Z: Y {
   virtual void g() { }
};

void main(int argc, char **argv) {
   Y y;
   X x;
   Z z;

   X *p = argc > 1 ? &y : &x;
   p->f();
}

main -> Y::Y -> X::X -> X::f -> X::g
     -> X::X -> X::f -> X::g
     -> Z::Z -> Y::Y -> X::X -> X::f -> X::g
     -> X::f -> {X::g, Y::g}

And we can strip Z::g, illustrating that the technique can still work for
programs which contain virtual calls whose destination cannot be resolved at
compile time

Again... Im not claiming you cant fool this algorithm... you can; but it
works pretty well for a large number of common cases. In fact it does much
better than just strip unwanted virtuals, it can change virtual calls into
non-virtual calls, enabling other optimizations such as inlining etc.

Mark Williams

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35C7CDF6.D47BE042@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:
> markw65@my-dejanews.com wrote:
> >
> > In article <35C70005.A20AB915@acm.org>,
> >   Pete Becker <petebecker@acm.org> wrote:
> > > markw65@my-dejanews.com wrote:
> > > >
> > > > eg the so called "killer" example which "proved" the ineffectiveness of
this
> > > > technique is a particularly easy target...
> > >
> > > But the obvious extension of that example, defining the functions in
> > > separate translation units, is nowhere near as easy. So you've fixed a
> > > trivial case, not the general problem.
> >
> > This optimization cant be implemented on a one translation unit at a time
> > basis anyway (which is why most of the solutions are described in terms of
> > the linker). Solving the slightly more general problem of removing the
> > references by doing a little cross module analysis at compile time is really
> > not hard.
>
> I have no idea what it means to say that it "can't be implemented" but
> that it "is really not hard".

Pete, I really dont understand your determination to make this sound hard.
Especially by misrepresenting other peoples posts...

Removing unused virtuals _is_ impossible one translation unit at a time.
Removing a large number of virtual functions _is_ relatively trivial if you do
some cross module analysis.

> C++ does not require that source code or
> object code for other translation units be present when code is being
> compiled.

True. But so what? If you want this optimization to be possible you _make_ the
sources or objects available.

In any case, if all of the source (or objects) are not available at compile
time, then they must be available at link time. So move the processing into
the linker. There are a number of compilers which do this. The object files
consist of an internal representation of the code. When the linker is
invoked, it effectively runs the compiler on the combined source of the
entire program.

If you are referring to dll's, then the problem becomes harder. I doubt if
dlls are that common in embedded systems where memory is tight... But in
anycase, you could apply the same basic method, "linking" the dll against all
of its clients, then removing the intersection of the dead functions.

> That's a significant obstacle to "cross module analysis".

I dont think so.

> I stand by what I said.

Evidently.

Mark Williams

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35C7CDF6.D47BE042@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:
> markw65@my-dejanews.com wrote:
> > This optimization cant be implemented on a one translation unit at a time
> > basis anyway (which is why most of the solutions are described in terms of
> > the linker). Solving the slightly more general problem of removing the
> > references by doing a little cross module analysis at compile time is really
> > not hard.
>
> I have no idea what it means to say that it "can't be implemented" but
> that it "is really not hard".

He meant that it's not possible if you can analyze only one translation
unit at a time, but it is not hard to do if you can analyze all of the
translation units. (I'm not certain that the last part is true, though.)

> C++ does not require that source code or
> object code for other translation units be present when code is being
> compiled. That's a significant obstacle to "cross module analysis".

But it doesn't require optimization, either. And it doesn't require the
linker to be totally independant of the compiler; in fact, every C++
compiler I know of includes a linker, and there's no reason why the
linker can't do the last few steps of optimization. Obviously, the
linker *does* require that all the object code for every translation
unit is present.

--
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6q9p8b$rnd$1@nnrp1.dejanews.com>,
  markw@silicon-spice.com wrote:
> In article <6q7nfd$isr$1@nnrp1.dejanews.com>,
>   AllanW@my-dejanews.com wrote:
> > In article <6q4h2a$1vo$1@nnrp1.dejanews.com>,
> >   markw65@my-dejanews.com wrote:
> > > In article <35C220B5.D60630AC@ix.netcom.com>,
> > >   "Paul D. DeRocco" <pderocco@ix.netcom.com> wrote:
> > > > markw65@my-dejanews.com wrote:
> > > > >
> > > > > Not really. A good compiler will often be able to remove the
reference
> > > > > to the base class's virtual table (and its the reference to the
> > > > > virtual table which matters, not whether or not a class's constructor
> > > > > was called).
> > > >
> > > > How can the compiler or linker know that a particular virtual function
> > > > won't be invoked during construction or destruction, while a derived
> > > > object's type is technically still the base class? Such a call may
occur
> > > > indirectly, and therefore be invisible.
> > >
> > > By analysing the code :-)
> > >
> > > Note the word "often"... not "always"
> > >
> > > eg the so called "killer" example which "proved" the ineffectiveness of
this
> > > technique is a particularly easy target...
> > >
> > > Dont forget that any virtual functions called directly by the constructor
do
> > > not (need to) go through the virtual table at all.
> >
> > Which is exactly the point of that "killer" example!  Reposted here
> > for your convenience:
> >
> > In article <6pn7br$fjg$1@nnrp1.dejanews.com>,
> >   AlanStokes@my-dejanews.com wrote:
> > > I don't think this is sufficient. Consider the following, where no X is
ever
> > > constructed, and yet one of X's functions is called polymorphically:
> > >
> > > struct X {
> > >    X() { f(); }
> > >    void f() { g(); }
> > >    virtual void g() { }
> > > };
> > >
> > > struct Y : X {
> > >    virtual void g() { }
> > > };
> > >
> > > void main() {
> > >    Y y;
> > > }
> > >
> > > The polymorphic call in X::f() must call X::g() when the X base of the Y
> > > object is constructed. I suspect the various algorithms proposed might
omit
> > > X::f() (but not X::g(), which really is never called!).
> >
> > Let's assume that all the functions f() and g() are too big to inline.
> > X's constructor can easily recognize that it will always call X::f(),
> > even if some derived class overrides f.
> >
> > But X::f() can't make that assumption, unless you generate two
> > versions (one to call from X's constructor, and another one to
> > call at any other time). When X::f() is called from X's
> > constructor, the call to g() must call X::g(). But if it was
> > called from Y's constructor it would have to call Y::g().
> >
> > The first compliant compiler/linker vendor that manages to omit Y::g()
> > from from the build without any additional clues from the user, will
> > earn the awe and respect (and probably the dollars!) of many of us.
>
> OK, so I build the static call graph:
>
> main -> Y::Y -> X::X -> X::f -> X::g
>
> Now... those are the only functions that can be called, so omit everything
> else.
>
> Like I said, trivial. Have I earned your awe yet? If so, start sending those
> dollars :-)
>
> Since I can tell that you're going to come back and say Im cheating :-) Ill
> show you how I would build the call graph for some other cases.
>
> void main() {
>    Y y;
>    y.f();
> }
>
> now the graph looks like
>
> main -> Y::Y -> X::X -> X::f -> X::g
>      -> X::f -> Y::g
>
> And in this case there is nothing to strip, but we still "know" where all the
> calls go... for suitable f (and profiling info) it may be worth duplicating
> the code to eliminate the virtual tables/dispatch altogether.
>
> struct Z: Y {
>    virtual void g() { }
> };
>
> void main(int argc, char **argv) {
>    Y y;
>    X x;
>    Z z;
>
>    X *p = argc > 1 ? &y : &x;
>    p->f();
> }
>
> main -> Y::Y -> X::X -> X::f -> X::g
>      -> X::X -> X::f -> X::g
>      -> Z::Z -> Y::Y -> X::X -> X::f -> X::g
>      -> X::f -> {X::g, Y::g}
>
> And we can strip Z::g, illustrating that the technique can still work for
> programs which contain virtual calls whose destination cannot be resolved at
> compile time
>
> Again... Im not claiming you cant fool this algorithm... you can; but it
> works pretty well for a large number of common cases. In fact it does much
> better than just strip unwanted virtuals, it can change virtual calls into
> non-virtual calls, enabling other optimizations such as inlining etc.
>
> Mark Williams

You've pretty well documented how a manual analysis would work. If I was
manually selecting which functions to include, and which to exclude, I
would go through exactly the same steps you did.

Would you care to expound on an algorithm to be used by linkers and/or
compilers, to accomplish the same thing?  It's no good saying
    "Figure out if Z::g() can be called"
because Figuring It Out is what this whole thread is about. Instead, say
    "If the code calls g() on a pointer whose static type is X, then we
     must include X::g and Y::g because the actual type could be X or Y.
     But we can leave out Z::g because ..."
and then finish the sentance.  For instance, are you suggesting that the
compiler should recognize that even though a Z is constructed, we never
take it's address, and therefore we never have a Z pointer? Be specific.

--
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

markw@silicon-spice.com wrote:
>
 > In article <35C7CDF6.D47BE042@acm.org>,
 >   Pete Becker <petebecker@acm.org> wrote:
 > > markw65@my-dejanews.com wrote:
> > >
> > > This optimization cant be implemented on a one translation unit at a time
> > > basis anyway (which is why most of the solutions are described in terms of
> > > the linker). Solving the slightly more general problem of removing the
> > > references by doing a little cross module analysis at compile time is really
> > > not hard.
> >
> > I have no idea what it means to say that it "can't be implemented" but
> > that it "is really not hard".
>
> Pete, I really dont understand your determination to make this sound hard.
> Especially by misrepresenting other peoples posts...

 In what way did I misrepresent anyone's post? Note that the original
message is quoted exactly. People can draw their own conclusions. I
found those statements contradictory without further explanation.
 My insistence on not oversimplifying the issues is exactly that. It has
been far too common in this thread for folks to announce without
qualification that they know how to solve some problem, only to agree
later on that they solve some simpler version of the problem.

>
> Removing unused virtuals _is_ impossible one translation unit at a time.
> Removing a large number of virtual functions _is_ relatively trivial if you do
> some cross module analysis.
>
> > C++ does not require that source code or
> > object code for other translation units be present when code is being
> > compiled.
>
> True. But so what? If you want this optimization to be possible you _make_ the
> sources or objects available.

 Fine. This needs to be stated explicitly when you say that you know how
to solve this problem, because you are offering a constrained solution,
not a general solution. (If I were trying to "misrepresent" the
situation I would claim that this means you are compiling some language
other than C++.)

>
> In any case, if all of the source (or objects) are not available at compile
> time, then they must be available at link time. So move the processing into
> the linker. There are a number of compilers which do this. The object files
> consist of an internal representation of the code. When the linker is
> invoked, it effectively runs the compiler on the combined source of the
> entire program.

 I'm confused by your tenses. When you say "the object files consist of"
do you mean that that's what they are today, or that it would be
possible to implement a compiler that does this? If the latter, please
tell me when that's going to ship. To the best of my knowledge, object
files contain machine code and linking information, that is, a great
deal less information than is contained in the source files.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

markw65@my-dejanews.com wrote:
>
> eg the so called "killer" example which "proved" the ineffectiveness of this
> technique is a particularly easy target...

But the obvious extension of that example, defining the functions in
separate translation units, is nowhere near as easy. So you've fixed a
trivial case, not the general problem.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35C70005.A20AB915@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:
> markw65@my-dejanews.com wrote:
> >
> > eg the so called "killer" example which "proved" the ineffectiveness of this
> > technique is a particularly easy target...
>
> But the obvious extension of that example, defining the functions in
> separate translation units, is nowhere near as easy. So you've fixed a
> trivial case, not the general problem.

This optimization cant be implemented on a one translation unit at a time
basis anyway (which is why most of the solutions are described in terms of
the linker). Solving the slightly more general problem of removing the
references by doing a little cross module analysis at compile time is really
not hard.

Agreed, the _general_ problem cannot be solved. That doesnt mean you cant hit
most of the common cases.

Mark Williams

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Nathan Myers wrote:
>
> Pete Becker <petebecker@acm.org> wrote:
> >AlanStokes@my-dejanews.com wrote:
> >>
> >>
> >> The polymorphic call in X::f() must call X::g() when the X base of the Y
> >> object is constructed. I suspect the various algorithms proposed might
> >> omit X::f() (but not X::g(), which really is never called!).
> >
> >Oooooh, devious! It looks like you've identified the killer case.
>
> Wishful thinking.

Not at all. As I said in my other message, a differing interpretation of
an ambiguous description of the technique. Now that you've described
more specifically what you meant, this case is covered.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Nathan Myers wrote:
>
> Pete Becker <petebecker@acm.org> wrote:
> >OK, that's not how I read it, but it's reasonable. It's much weaker than
> >I thought it was intended to be. This means that, for example, in a
> >single inheritance hierarchy, every version of f from the base down to
> >the most derived class that is actually instantiated must be linked in.
> >Roughly speaking, it provides the greatest benefit in shallow
> >inheritance hierarchies, and less in deep hierarchies.
>
> More precisely, it provides the greatest benefit in broad
> hierarchies, regardless of their depth.

More precise, yes. But less accurate. See below.

> The more virtual
> function slots a class defines, the more likely it is that
> some go unused.  For any f that goes unused, all the f's
> from the base down to the most derived may be omitted.

This is an oversimplification. Take locales as an example: if someone
wants to provide custom capabilities they can derive a class from one of
the library facets and override one or more virtual functions. They'll
use their overridden functions, and the unused base versions will be
linked in. For this case, this means that the technique under discussion
provides the least benefit in exactly the area where the hierarchy is
deepest.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

 Pete Becker <petebecker@acm.org> wrote:
>Nathan Myers wrote:
>>
>> Pete Becker <petebecker@acm.org> wrote:
>> >Roughly speaking, it provides the greatest benefit in shallow
>> >inheritance hierarchies, and less in deep hierarchies.
>>
>> More precisely, it provides the greatest benefit in broad
>> hierarchies, regardless of their depth.
>
>This is an oversimplification. Take locales as an example: if someone
>wants to provide custom capabilities they can derive a class from one of
>the library facets and override one or more virtual functions. They'll
>use their overridden functions, and the unused base versions will be
>linked in. For this case, this means that the technique under discussion
>provides the least benefit in exactly the area where the hierarchy is
>deepest.

Yes, let us take locales as an example.  The overwhelmingly most
common case of using locales overrides no members; then none of
those functions unused are retained.  Of the remaining cases, most
override only one or a few facets -- most likely one member of one
facet; again, most functions are not retained.  The most useful
members to override are in the "punctuation" facets, and are very,
very short, so that it doesn't much matter whether they are kept
or not.  Where the implementation is not short, the most likely
thing to do in an overriding function is to apply a small adjustment
and call the base class version.

Of course a conscientious implementer would arrange that those
larger functions that are used by both base class and the derived
"byname" facets share their implementation, rather than duplicating
it, so the overridden code itself is actually very small.

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6pqpe4$p8v$1@shell7.ba.best.com>,
  ncm@nospam.cantrip.org (Nathan Myers) wrote:
[Heavy snippage]
> The goal (for those who have forgotten) was to reduce the size of
> executables, not to eliminate every conceivable twisted case of
> dead code.  The posted algorithms accomplish this handily.  Find
> some function called but not linked, and the algorithm will need
> adjustment.

Exactly.

Which is why I think that it's sufficient to look for virtual
functions whose names are never used anywhere in the program.
That is, a call
    c->f();
(assuming c is a pointer to C) would probably link in X::f(),
where X is some class anywhere on the heirarchy of C (it could
be C, or some base class, or something derived from C). But
we could expect to avoid linking X::g(), unless something
called or took the address of g() somewhere in the heirarchy.

For instance, in programs that don't call locale or it's facets
(the original complaint that started this thread's ancestor),
this would avoid bringing this static data into memory, thus
lowering the program's footprint.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35C220B5.D60630AC@ix.netcom.com>,
  "Paul D. DeRocco" <pderocco@ix.netcom.com> wrote:
> markw65@my-dejanews.com wrote:
> >
> > Not really. A good compiler will often be able to remove the reference
> > to the base class's virtual table (and its the reference to the
> > virtual table which matters, not whether or not a class's constructor
> > was called).
>
> How can the compiler or linker know that a particular virtual function
> won't be invoked during construction or destruction, while a derived
> object's type is technically still the base class? Such a call may occur
> indirectly, and therefore be invisible.

By analysing the code :-)

Note the word "often"... not "always"

eg the so called "killer" example which "proved" the ineffectiveness of this
technique is a particularly easy target...

Dont forget that any virtual functions called directly by the constructor do
not (need to) go through the virtual table at all.

Mark Williams

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hyman Rosen wrote:
>
> Pete Becker wrote:
> > It's easily fixed, but the problem arises with pointers to
> > member functions, which must generate the same records as virtual calls.
>
> Those records are generated at the point where the address of an actual
> (virtual) function is taken, just as if that functionhad been called.

Yes, as I said, it's easily fixed. The problem is that it wasn't in the
original specification, which was, therefore, incomplete.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Nathan Myers wrote:
>
> No, it doesn't.  Referring to his description of the linker
> algorithm, when the program contains a call to a Y constructor,
> that creates the vtbl which contains the "vtbl" reference to X::f().
> His summary can be refined:
>
> >>   a. At least one object of class X [or class Y that inherits
> >>      X::f] is constructed AND [...]

OK, that's not how I read it, but it's reasonable. It's much weaker than
I thought it was intended to be. This means that, for example, in a
single inheritance hierarchy, every version of f from the base down to
the most derived class that is actually instantiated must be linked in.
Roughly speaking, it provides the greatest benefit in shallow
inheritance hierarchies, and less in deep hierarchies.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35C07198.350BF18D@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:
> Nathan Myers wrote:
> >
> > No, it doesn't.  Referring to his description of the linker
> > algorithm, when the program contains a call to a Y constructor,
> > that creates the vtbl which contains the "vtbl" reference to X::f().
> > His summary can be refined:
> >
> > >>   a. At least one object of class X [or class Y that inherits
> > >>      X::f] is constructed AND [...]
>
> OK, that's not how I read it, but it's reasonable. It's much weaker than
> I thought it was intended to be. This means that, for example, in a
> single inheritance hierarchy, every version of f from the base down to
> the most derived class that is actually instantiated must be linked in.
> Roughly speaking, it provides the greatest benefit in shallow
> inheritance hierarchies, and less in deep hierarchies.

Not really. A good compiler will often be able to remove the reference to the
base class's virtual table (and its the reference to the virtual table which
matters, not whether or not a class's constructor was called).

Mark Williams

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

AlanStokes@my-dejanews.com wrote:
> And I stand by the statement that this makes things nastier. Unless the
> compiler/linker is willing to try to work out what functions are reachable
> from the constructor of base classes, we must include virtual functions of
> bases whenever we include the overriding virtual functions of descendants,
> even though they are unlikely to be needed.

This is true, but is avoidable through optimization. Your example is

struct X { X() { f(); } void f() { g(); } virtual void g(); };
struct Y : X { void g(); };

In a straightforward compilation, the polymorphic call of X::g in X::f
would cause both X::g and Y::g to be linked in, because the program
contains vtables for X and Y. But suppose the compiler inlines the call to
X::f in X::X. Then X::X looks like X() { g(); }, and this is *not* a
polymorphic call, because within X::X the dynamic type of *this is X. So
the compiler simply issues a normal call to X::g, which will not force in
Y::g.

These optimizations will always occur at the call site. If the compiler can
infer more strict type information about the calling object than its given
declaration, it is free to generate references based on its inferences and
thereby cause fewer functions to be linked in.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker wrote:
> OK, that's not how I read it, but it's reasonable. It's much weaker than
> I thought it was intended to be. This means that, for example, in a
> single inheritance hierarchy, every version of f from the base down to
> the most derived class that is actually instantiated must be linked in.
> Roughly speaking, it provides the greatest benefit in shallow
> inheritance hierarchies, and less in deep hierarchies.

Just as you say, given a standalone call of BasePtr->VirtFunc(), all the
versions of VirtFunc in derived classes instantiated within the program
must be linked in. In the absence of other information, the compiler must
assume that the call can be polymorphic across any derived type of Base.
Fortunately, other information is not always absent. Given inlining, and
other interprocedural analysis, the compiler can often determine that the
BasePtr has a particular static type, or perhaps that it is at least
guaranteed to be derived from a particular descendant class. Then it can
generate more restrictive references and avoid linking in the unused base
versions.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker <petebecker@acm.org> wrote:
>AlanStokes@my-dejanews.com wrote:
>>
>>
>> The polymorphic call in X::f() must call X::g() when the X base of the Y
>> object is constructed. I suspect the various algorithms proposed might
>> omit X::f() (but not X::g(), which really is never called!).
>
>Oooooh, devious! It looks like you've identified the killer case.

Wishful thinking.   Here's the example again.

> struct X
> {
>    virtual void g() { }
>    void f() { g(); }
>    X() { f(); }
> };
>
> struct Y : X { virtual void g() { } };
> void main() { Y y; }

First, the calls to X::X and to X::f() are not polymorphic, so they
produce ordinary references -- or just expand inline.  If either is
expanded inline, then the call to this->g() can also be converted to
a regular call to X::g().  Then Y::g() is not linked, because there
are no uses of its vtbl slot.

In the general case where these function are not inline, X::g()
and Y::g() must both be linked.  However, compilers already identify
cases where the vtbl for a base class is not needed, because the
constructor is compiler-generated, so overridden occupants of used
vtbl slots certainly need not always be linked.

Of course (as has been stated many times) all linkers "drag in" some
functions that are not actually called.  Proving that is shooting
fish in a barrel:

  int main(int argc, char** argv) { if (argc < 0) f(); }

The goal (for those who have forgotten) was to reduce the size of
executables, not to eliminate every conceivable twisted case of
dead code.  The posted algorithms accomplish this handily.  Find
some function called but not linked, and the algorithm will need
adjustment.

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35BF5782.2C54C08B@prolifics.com>,
  Hyman Rosen <hymie@prolifics.com> wrote:
> AlanStokes@my-dejanews.com wrote:

BTW, I love that name.

> > I don't think this is sufficient. Consider the following, where no X is ever
> > constructed, and yet one of X's functions is called polymorphically:
> >
> > struct X
> > {
> >    X() { f(); }
> >    void f() { g(); }
> >    virtual void g() { }
> > };
> >
> > struct Y : X
> > {
> >    virtual void g() { }
> > };
> >
> > void main()
> > {
> >    Y y;
       y.g(); // Needed to make this example complete -- AllanW
> > }
>
> You have several errors here. First, an X most certainly is constructed, as
> part of the construction of Y.

This is true, and may be an answer to Alan's objection.  If we're
careful to consider the X-subobject to be an X object, then yes,
X objects are created and X member functions need to be instanciated
even if they are overridden in Y.

> Furthermore, the call to g() from X::f()
> from X::X() will go to X::g() and not to Y::g(), because during the
> construction of the X part of y, y is in every respect an X.

This was exactly Alan's point. If we keep Y::f (which is needed by the
line I added), but "optimize away" X::f in the mistaken belief that no
X's are ever constructed, then the program cannot run correctly.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker <petebecker@acm.org> wrote:
>Nathan Myers wrote:
>>
>> No, it doesn't.  Referring to his description of the linker
>> algorithm, when the program contains a call to a Y constructor,
>> that creates the vtbl which contains the "vtbl" reference to X::f().
>> His summary can be refined:
>>
>> >>   a. At least one object of class X [or class Y that inherits
>> >>      X::f] is constructed AND [...]
>
>OK, that's not how I read it, but it's reasonable. It's much weaker than
>I thought it was intended to be. This means that, for example, in a
>single inheritance hierarchy, every version of f from the base down to
>the most derived class that is actually instantiated must be linked in.
>Roughly speaking, it provides the greatest benefit in shallow
>inheritance hierarchies, and less in deep hierarchies.

More precisely, it provides the greatest benefit in broad
hierarchies, regardless of their depth.  The more virtual
function slots a class defines, the more likely it is that
some go unused.  For any f that goes unused, all the f's
from the base down to the most derived may be omitted.

In addition, for slots f that _are_ used, base members f for
classes with vacuous (compiler-generated) constructors may
frequently be omitted as well.

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6pplpc$i6t$1@nnrp1.dejanews.com>,
  AlanStokes@my-dejanews.com wrote:
> And I stand by the statement that this makes things nastier. Unless the
> compiler/linker is willing to try to work out what functions are reachable
> from the constructor of base classes, we must include virtual functions of
> bases whenever we include the overriding virtual functions of descendants,
> even though they are unlikely to be needed.

The local problem is that this case is easily overlooked until it
bites somebody.  However, once identified, it seems to me that the
solution is the least-complicated part of the bigger problem
(identifying which virtual functions can or cannot be omitted.)
For this phase of the solution, simply pretend that the word
"virtual" did not apply, and analyze what happens in X's
constructor.

FWIW, the problem that started this thread (lots of facet code
being included even if facets aren't used explicitly) would be
considerably reduced even without this level of analysis.  Except
for embedded systems (which perhaps needs a way to turn off
facets completely), it would probably be sufficient to omit all
occurences of f() when there are no references to f() except
from various virtual tables.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

markw65@my-dejanews.com wrote:
>
> Not really. A good compiler will often be able to remove the reference
> to the base class's virtual table (and its the reference to the
> virtual table which matters, not whether or not a class's constructor
> was called).

How can the compiler or linker know that a particular virtual function
won't be invoked during construction or destruction, while a derived
object's type is technically still the base class? Such a call may occur
indirectly, and therefore be invisible.

--

Ciao,
Paul
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker wrote:
> It's easily fixed, but the problem arises with pointers to
> member functions, which must generate the same records as virtual calls.

Those records are generated at the point where the address of an actual
(virtual) function is taken, just as if that functionhad been called.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

AlanStokes@my-dejanews.com wrote:
> I don't think this is sufficient. Consider the following, where no X is ever
> constructed, and yet one of X's functions is called polymorphically:
>
> struct X
> {
>    X() { f(); }
>    void f() { g(); }
>    virtual void g() { }
> };
>
> struct Y : X
> {
>    virtual void g() { }
> };
>
> void main()
> {
>    Y y;
> }

You have several errors here. First, an X most certainly is constructed, as
part of the construction of Y. Furthermore, the call to g() from X::f()
from X::X() will go to X::g() and not to Y::g(), because during the
construction of the X part of y, y is in every respect an X.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

<AlanStokes@my-dejanews.com> wrote:
>phalpern@truffle.ma.ultranet.com (Pablo Halpern) wrote:
>> The minimal condition for requiring the inclusion of a virtual function,
>> X::f() that is not called statically is:
>>
>>   a. At least one object of class X is constructed AND
>>   b. f() is called polymorphically through a pointer or reference
>>      to X or one of its base classes.
>
>I don't think this is sufficient. Consider the following, where no X is ever
>constructed, and yet one of X's functions is called polymorphically:
> ...
>I think this makes the whole problem much nastier.

No, it doesn't.  Referring to his description of the linker
algorithm, when the program contains a call to a Y constructor,
that creates the vtbl which contains the "vtbl" reference to X::f().
His summary can be refined:

>>   a. At least one object of class X [or class Y that inherits
>>      X::f] is constructed AND [...]

but his algorithm already handled this.  My summary did as well:

> 1. When you call a constructor, that class's virtual functions
>    (and any it fails to override) "might be" needed.

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

AlanStokes@my-dejanews.com wrote:
>
>
> The polymorphic call in X::f() must call X::g() when the X base of the Y
> object is constructed. I suspect the various algorithms proposed might omit
> X::f() (but not X::g(), which really is never called!).

Oooooh, devious! It looks like you've identified the killer case.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35BF5782.2C54C08B@prolifics.com>,
  Hyman Rosen <hymie@prolifics.com> wrote:
> You have several errors here. First, an X most certainly is constructed, as
> part of the construction of Y.

Yes, but it's neccessarily that obvious. It wasn't clear to me from the
various stated algorithms whether the rule about "an object of type X is
constructed" was intended, and was understood, to include this case. As I
said, more explicit phrasing would help.

And I stand by the statement that this makes things nastier. Unless the
compiler/linker is willing to try to work out what functions are reachable
from the constructor of base classes, we must include virtual functions of
bases whenever we include the overriding virtual functions of descendants,
even though they are unlikely to be needed.

> Furthermore, the call to g() from X::f()
> from X::X() will go to X::g() and not to Y::g(), because during the
> construction of the X part of y, y is in every respect an X.

That was the whole point of the example, and what I meant when I said "The
polymorphic call in X::f() must call X::g() when the X base of the Y
object is constructed."

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <199807231426.KAA25205@calumny.jyacc.com>,
  Hyman Rosen <hymie@prolifics.com> wrote:
> It was bbrunswick@my-dejanews.com who first posted the suggestion that
> led me to this train of thought.
>
> First, some definitions of linker terms:
>
> Reference A use of an undefined symbol. The linker searches its
>   available object files and libraries, trying to find
>   one which defines the symbol. The reference is then
>   replaced with the value of the symbol.
>
> Weak Reference Just like a Reference, but the linker will not pull in
>   a module just to satisfy this type of reference. If a
>   module defining the symbol is pulled in for another
>   reason, the reference is replaced with the value of the
>   symbol, but otherwise the reference is replaced with zero.
>
> Transparent Symbol
>   I just made this one up. This is what needs to be added to
>   linkers to enable the elimination of unused virtuals. A
>   Transparent Symbol causes a module to be pulled in by the
>   linker
>   if the linker has unresolved references to the symbol, but
>   this does not cause the symbol to become defined; the linker
>   will continue to pull in other modules that define the same
>   transparent symbol.
>
> So here's the scheme. We assign a symbol for each slot in the vtable
> of each class which first declares a virtual function. The vtable
> itself contains weak references to the virtual functions. Whenever a
> polymorphic call is made to a virtual function, we generate a
> reference to the appropriate slot symbol. In every module which
> contains an implementation of a virtual function, we generate a transparent
> symbol for that function's slot. And that's it.
>
> Because the vtable references are weak, the vtable itself does not
> cause any module to be forcibly linked. Whenever a polymorphic call to
> a virtual function is made, the resulting reference to the transparent
> symbol will cause the linker to pull in all modules which define that
> symbol, so virtual functions from derived classes will get properly
> linked.

You have the right idea, but it wouldn't work exactly as written.
>  Transparent Symbol causes a module to be pulled in
>  by the linker if the linker has unresolved
>  references to the symbol, ...
The problem is that the Strong Reference might have already been
resolved.  Indeed, the Strong Reference might have even been made
in the same module that defined the symbol.

    // CountBase.H
    struct CountBase {
        int m_count;
        CountBase(int i=0);
        virtual int Count(int i);
    };

    // CountBase.Cpp
    #include <CountBase.H>
    CountBase::CountBase(int i) : m_count(i) {}
    int CountBase::Count(int i) { return (m_count += i); }
    int MyFunc(CountBase *b) { return b->Count(5); }

    //CountDer.H
    #include <CountBase.H>
    struct CountDerived : public CountBase {
        CountDerived(int i=10);
        virtual int Count(int i);
    }

    // CountDer1.Cpp
    #include <CountDer.H>
    CountDerived::CountDerived(int i) : m_count(i+50) {}

    // CountDer2.Cpp
    #include <CountDer.H>
    int CountDerived::Count(int i) { return (m_count += i*100); }

    // Main.Cpp
    #include <iostream>
    #include <CountDer.H>
    int main(int, char**) {
        CountDer d(25);
        std::cout << MyFunc(&d) << std::endl;
    }

CountBase.Obj contains:
    * Definition for CountBase's Virtual Table, which contains
      --> Weak reference to CountBase::Count
    * Definition for CountBase's constructor, which contains
      --> Strong reference to CountBase's Virtual Table
    * Definition for CountBase::Count(int)
    * Definition for MyFunc(Base*), which contains
      --> Strong reference to CountBase::Count(int)

CountDer1.Obj contains:
    * Definition for CountDerived's Virtual Table, which contains
      --> Weak reference to CountDerived::Count
    * Definition for CountDerived's constructor, which contains
      --> Strong reference to CountBase's constructor
      --> Strong reference to CountDerived's Virtual Table

CountDer2.Obj contains:
    * Definition for CountDerived::Count(int), which contains
      --> "Transparent Definition" for CountBase::Count(int)

Main.Obj contains:
    * Definition for int main(int,char**), which contains
      --> (references to standard library, ignored for this discussion)
      --> Strong reference to CountDerived's constructor

According to your description, Main.Obj causes CountDer1.Obj
to be included, which in turn causes CountBase.Obj to be
included.  There are no remaining unresolved references, so
the link is done -- even though CountDer2.Obj wasn't included!

No, what we need is something very similar:
    If there is a Strong Reference to X anywhere in the
    executable, then consider all references to Y to be
    Strong References.
I would call this a Magnet, because it causes Y to "stick"
to X if X is included.  Now, consider the same descriptions
above except change
      --> "Transparent Definition" for CountBase::Count(int)
into
      --> "Magnet" sticking CountDerived::Count(int)
          to CountBase::Count(int)

Since there is a Strong Reference to CountBase::Count(int) (in
CountBase.Obj), we must also include the module that defines
CountDerived::Count(int).  Everything is included, so everything
works.

Note that this is a more-or-less radical change from most
linkers that I am familiar with.  These linkers include
all the object files, and then examine the library files
until there are no more unresolved references.  But this
wouldn't work if the Magnet was in a library file.
Instead, the linker would have to examine every library
file that even potentially had any Magnets in it.
Furthermore, once a Magnet is found and the linker pulls
in a new module, this will probably include other Strong
References -- which may be Magnet targets themselves --
so the linker must start reading the library files all
over again.

I saw more or less this same idea posted quite some time ago,
although it was in far less detail and it didn't have a short
name.  But Magnet is probably a good name for this concept,
isn't it?  (You see, even though the Strong Reference was to
CountBase::Count, and we didn't directly touch
CountDerived::Count, the latter was "pulled" in anyway --
much like a magnet might make one paper clip "stick" to
another...)

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Nathan Myers wrote:
>
> How to link only needed virtual functions can be described more simply
> than anything I have seen posted yet.
>
> 1. When you call a constructor, that class's virtual functions
>    (and any it fails to override) "might be" needed.
>
> 2. When you call through a vtable slot, only functions that "might be"
>    needed which occupy that slot actually are needed.   A further
>    optimization is possible: of these, only the function that
>    corresponds to the static type of the reference and any that
>    override it are strictly needed.
>
> This process is iterative; as you discover a need for each additional
> virtual function, it may create a need for more yet.  You stop when no
> more are needed.

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

class Derived1 : public Base
{
public:
 void f();
 void g();
};

class Derived2 : public Base
{
public:
 void f();
 void g();
};

int main()
{
Base *b1 = new Derived1;
Base *b2 = new Derived2;
b1->f();
b2->g();
}

The algorithm described above links in Derived1::g, even though it's
never used. It also links in Derived2::f, even though it's never used.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35ba00c6.33474425@news.ma.ultranet.com>,
  phalpern@truffle.ma.ultranet.com (Pablo Halpern) wrote:
[...]
> The minimal condition for requiring the inclusion of a virtual function,
> X::f() that is not called statically is:
>
>   a. At least one object of class X is constructed AND
>   b. f() is called polymorphically through a pointer or reference
>      to X or one of its base classes.

This makes sense.

> Now, lets look at an example:
>
> struct A            { virtual void f(); };
> struct B : public A { virtual void f(); };
> struct C : public B { virtual void f(); virtual void h(); };
> struct D : public C { virtual void f(); };
>
> void g(B& b) { b.f(); /* polymophic call */ }
> int main() { A a; B b; C c; g(c); }
[...]

A good reference example, because it plenty of optimizations that
are easy to see, but difficult to implement.  The only virtual
function that is actually needed is C::f(), so the more functions
that a compiler/linker pair can remove while still keeping this
one, the better.

> It seems our linker would have to be quite a bit smarter. Perhaps,
> instead of a transparent symbol, we could have a compound symbol that
> represents a boolean condition. Each portion of a boolean expression
> would be represented by a simple symbol. That portion of the expression
> would evaulate true if a reference to that symbol exists in the program.
> Only if the whole expression evaluates true is the compound symbol
> linked in.  So, for our example we would have the following compound
> symbols:
>
>       A::f = compound(A::f_vtbl && A::f_call)
>  B::f = compound(B::f_vtbl && (B::f_call || A::f_call))
>  C::f = compound(C::f_vtbl && (C::f_call || B::f_call ||
>                                       A::f_call))
>  D::f = compound(D::f_vtbl && (D::f_call || C::f_call ||
>                                       B::f_call || A::f_call))
>
> C::f_vtbl is referenced by C's vtbl.  B::f_call is referenced by the
> call to b.f().  Thus C::f() is linked in. B::f() would also by linked in
> using this logic. However, A::f() would not be linked in (because there
> is no reference to A::f_call), nor would D::f() be linked in (because
> there is no reference to D::f_vtbl).

Why stop there?  Why not require the linker to do a full run-time
simulation and synthesize which virtual functions can actually be
reached at run-time?  [See my earlier post on the Ronko C++ Compiler
with psychic ability]

This isn't merely complicated, it's draconian.

> The object format and linker logic could be simplified by assigning each
> simple symbol a bit pattern and causing a compound symbol to be linked
> only if all of its bits were set by ORing the references to its
> component simple symbols together. Thus, all of the f_vtbl symbols could
> be associated with the bit pattern, 0x1 and all of the f_call symbols
> could be associated with 0xfffffffe.  Only if at least one of the
> required f_call and the required f_vtbl reference exist would the result
> be 0xffffffff, and the function would be linked:
>
>  B::f = compound(B::f_vtbl | B::f_call | A::f_call)
>
> A traditional strong reference would just be a reference associated with
> the bit pattern 0xffffffff and a traditional weak reference would just
> be a reference associated with the bit pattern 0.

This is simplified?

I think that most of the people calling for unused-virtual-function
elimination -- except the Embedded C++ users -- would be satisfied with
the removal of D::f() (because there is no D object) and C::g() (because
function g is never called).  In the case of the standard library, this
would remove almost all of the unrequired virtual functions.

The Embedded C++ users might still be unsatisfied, because they have a
limited amount of ROM.  But I noticed something interesting the other day
in the 1997 C++ Public Review Document:

[[[begin quote]]]

  1.3  Implementation compliance                      [intro.compliance]

  [...]

4 Two kinds of implementations are  defined:  hosted  and  freestanding.
  For  a  hosted implementation, this International Standard defines the
  set of available libraries.  A freestanding implementation is  one  in
  which  execution  may  take  place without the benefit of an operating
  system, and  has  an  implementation-defined  set  of  libraries  that
  includes certain language-support libraries (_lib.compliance_).

  [...]

  17.3.1.3  Freestanding implementations                [lib.compliance]

1 Two  kinds  of  implementations  are  defined: hosted and freestanding
  (_intro.compliance_).  For a hosted implementation, this International
  Standard describes the set of available headers.

2 A freestanding implementation has has an implementation-defined set of
  headers.  This set shall include at least the  following  headers,  as
  shown in Table 4:

          Table 4--C++ Headers for Freestanding Implementations

     +--------------------------------------------------------------+
     |                   Subclause                       Header(s)  |
     +--------------------------------------------------------------+
     |_lib.support.types_ Types                         <cstddef>   |
     +--------------------------------------------------------------+
     |_lib.support.limits_ Implementation properties    <limits>    |
     +--------------------------------------------------------------+
     |_lib.support.start.term_ Start and termination    <cstdlib>   |
     +--------------------------------------------------------------+
     |_lib.support.dynamic_ Dynamic memory management   <new>       |
     +--------------------------------------------------------------+
     |_lib.support.rtti_ Type identification            <typeinfo>  |
     +--------------------------------------------------------------+
     |_lib.support.exception_ Exception handling        <exception> |
     +--------------------------------------------------------------+
     |_lib.support.runtime_ Other runtime support       <cstdarg>   |
     +--------------------------------------------------------------+

3 The  supplied  version  of the header <cstdlib> shall declare at least
  the   functions   abort(),    atexit(),    and    exit()    (_lib.sup-
  port.start.term_).

[[[end quote]]]

Thus, unless this section has drastically changed in the FDIS, a
C++ compiler for standalone programs can be compliant without
including *ANY* of the standard I/O functionality in <iostream>.
If it chooses to include a subset of this, that would also be
compliant.  In particular, it can remove some or all of the
facets, or provide explicit methods for enabling them, thus
saving space in the executables where they were not enabled...

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35B91800.D65811FA@acm.org>, petebecker@acm.org says...
>
> The algorithm described above links in Derived1::g, even though it's
> never used. It also links in Derived2::f, even though it's never used.
>

I suppose "never used" means "never called".

It is impossible to find an algorithm which will eliminate all
never called virtual functions, as this would solve the halting
problem.

So, the only possible positive output of this thread is an
algorithm which will remove a big subset of the never called
virtual functions in a reasonable amount of time, together with
a definition of big and reasonable.

Nathan's algorithm is a move in that direction. Your remark
above shows that - as expected - it does not remove some never
called virtual functions. Do you have some suggestion on how to
improve it ?

--- Raoul

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker <petebecker@acm.org> wrote:
>Nathan Myers wrote:
>>
>> How to link only needed virtual functions can be described more simply
>> than anything I have seen posted yet.
>>
>> 1. When you call a constructor, that class's virtual functions
>>    (and any that it fails to override) "might be" needed.
>>
>> 2. When you call through a vtable slot, only functions that "might be"
>>    needed which occupy that slot actually are needed.   A further
>>    optimization is possible: of these, only the function that
>>    corresponds to the static type of the reference and any that
>>    override it are strictly needed.
>>
>> This process is iterative; as you discover a need for each additional
>> virtual function, it may create a need for more yet.  You stop when no
>> more are needed.
>
>The algorithm described above links in Derived1::g, even though it's
>never used. It also links in Derived2::f, even though it's never used.

The purpose of the optimization is to omit the f's when there are
no calls to f in the program.  To be specific, in a program with no
calls to (e.g.) money_put<wchar_t>::put, no versions of that function
would be linked.  That was the goal, and that is achieved by the
algorithm above.

To omit all functions that happen not to be called though they could
be is of course impossible, and was (as Pete well knows) never the goal.
Does it really advance the discussion to cobble up artificial examples
where an optimization does no better than the status quo, when it is
perfectly clear that it does solve the problem as encountered in real
programs?

The algorithm is simple, and it works.  Its utility is unimpeachable.
Its implementability has been demonstrated.  Next topic.

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Nathan Myers wrote:
>
> Pete Becker <petebecker@acm.org> wrote:
> >Nathan Myers wrote:
> >>
> >> How to link only needed virtual functions can be described more simply
> >> than anything I have seen posted yet.
>
> To omit all functions that happen not to be called though they could
> be is of course impossible, and was (as Pete well knows) never the goal.

There you go again, making assertions about what I think or know. I do
not know what your goal was in posting this algorithm, but I can make
reasonable inferences from what you say about it. What you said is quite
clear: it's purpose is "to link only needed virtual functions". I
demonstrated that it does not meet this goal. If you intended it to meet
some other goal you need so say so.

> Does it really advance the discussion to cobble up artificial examples
> where an optimization does no better than the status quo,

Now you're conceding too much. It in fact does better than the status
quo, because it only links in four of the six virtual functions.
Nevertheless, the point that this example makes is valid: it links in
the "product" of classes that are used and virtual functions that are
used.

> when it is
> perfectly clear that it does solve the problem as encountered in real
> programs?

It is not at all clear that it "does solve the problem as encountered in
real programs", at least, not until programmers have actual experience
applying it to real programs. This idea isn't particularly new. We
discussed it four years ago at Borland, and decided that the benefits
were minimal for the kind of code that we were writing at the time. It
might be useful for certain kinds of coding, but it is by no means a
general solution to this problem.

>
> The algorithm is simple, and it works.  Its utility is unimpeachable.
> Its implementability has been demonstrated.  Next topic.

Unimpeachable? It does more than it ought to do, namely, eliminates some
virtual functions that ARE used. That's definitely not a good thing. Try
again.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker wrote:
>
> Hyman Rosen wrote:
> >
> > So here's the scheme. We assign a symbol for each slot in the vtable
> > of each class which first declares a virtual function. The vtable
> > itself contains weak references to the virtual functions. Whenever a
> > polymorphic call is made to a virtual function, we generate a
> > reference to the appropriate slot symbol. In every module which
> > contains an implementation of a virtual function, we generate a transparent
> > symbol for that function's slot. And that's it.
>
>         I think this goes too far. Consider a library that contains a class
> derived from Base, overriding Base::f(). Any virtual call in the program
> to Base::f will force the overriding version to be linked in, even if
> the derived class is never actually used.
>         Thanks, though: I thought I had a technique that worked, but it turns
> out that it has exactly the same problem. I hadn't seen it until I read
> your example.

However, let me add my thoughts:

I would add a new type of link, which I'll name "hardener".
A hardener for a symbol by itself doesn't cause any code to be pulled
in.
However, a hardener to a symbol, if linked in, causes all weak links
to that symbol act like hard links - that is, if you have a weak link
*and* a hardener to a symbol, the module gets linked in.
In addition, one would need links which don't correspond to code
where the address of a symbol is put in (I'll call them "free links").
(I'm not shure if free links do already exist, maybe under a different
name). Hardeners are considered to be free in the following (although
one might find uses for non-free hardeners as well).

Now the mechanism would be as follows:

The virtual tables contain weak links to the virtual functions.
For all virtual functions which get into a given vtbl slot in a
hierarchy), there's an entry to a corresponding "slot module"
which contains no code, but a normal symbol identifying that slot
for that class, free hard links to the corresponing slot modules of
all derived classes, and a hardener for each of the virtual function.
Now, each call of a virtual function gets a hard link to the
corresponding slot module (this doesn't pull in additional code,
since the slot module doesn't contain anything than a symbol, some
links and hardeners; none of them cause code to be generated).

To illustrate how this would work, a simple example:

// def.h

struct A
{
  virtual ~A();
  virtual void f();
};

struct B: A
{
  virtual ~B();
  virtual void f();
};

struct C: A
{
  virtual ~C();
  virtual void f();
};

A::~A() {}
void A::f() {}

B::~B() {}
void B::f() {}

C::~C() {}
void C::f() {}

int main() // needs A::~A() and B::~B()
{
  A* a=new A;
  delete a;
  a=new B;
  delete a;
}

Now imagine each of the functions is compiled into a separate module.
Now, the following happens:

Slot modules are generated, looking like:

// module for A::f():
symbol (slot for void A::f())
hardener (void A::f())
free hard link to (slot for void B::f());

// module for B::f()
symbol (slot for void B::f())
hardener (void B::f())

// module for C::f()
symbol (slot for void C::f())
hardener (void C::f())


// module for destructor of A
symbol (slot for destructor of A)
hardener (void A::~A())
free hard link to (slot for destructor of B)
free hard link to (slot for destructor of C)

// module for destructor of B
symbol (slot for destructor of B)
hardener (void B::~B())

// module for destructor of C
symbol (slot for destructor of C)
hardener (void C::~C())

Now, generating an A object pulls in the vtbl for A, containing
(non-free)
weak links to A::~A() and void A::f(). Then delete a pulls in the slot
module (slot for destructor of A), which in turn pulls in
(slot for destructor of B) and (slot for destructor of C).
Now generating a B pulls in the
vtbl for B, containing weak links to B::~B() and void B::~f().
The slot module contains hardeners for A::~A(), B::~B() and C::~C(),
so those weak links to those symbols are hardened. Now, there's no
weak link for C::~C() which could be hardened, thus we get hardened
links for A::~A() and B::~B() only. Thus only those two virtual
functions we actually use are linked in. And the (non-free)
weak links in the vtbl cause the address to be written there.

Now to be fair, it won't get that fine result in any case (I don't
think that would be possible in general, though), but it pulls
the code of a virtual function in exactly if
- a vtbl for the object is pulled in (that is, an object of that
  type is actually generated; thus code for functions of never
  instantiated objects is not generated) *and*
- the virtual function in question is called anywhere in the
  hierarchy through a pointer to the object or one of its bases.


Now what would the implementation need to support this?

Well, first the linker would have to support weak links, free links
and hardeners. Weak links are AFAIK quite standard in modern
linkers, and free links might exist already (and would be easy to
implement if not; just make the address to change a null pointer
and check for that before writing the symbol address to a link).
Hardeners are nothing I've heared from until now; but that doesn't
mean much.
The whole hierarchy could be implemented in a new link format quite
straightforward: Make the "weak link" flag a whole unsigned char
instead of a simple flag, and demand that oring together all the
encountered flags has to result in UINT_MAX to link a module in.
That is, assuming f.ex. 8 bit chars, the link types could f.ex.
be defined as following:

                  link type (binary)        link address

hard link:        11111111                  (the address of the link)
free hard link:   11111111                  null pointer
weak link:        00001111                  (the address of the link)
free weak link:   00001111                  null pointer
hardener:         11110000                  null pointer

This would make a lot of flexibility; for example, there could be
non-hardenable weak links (type 00000000), three-component links
(f. ex. 10000000, 01000000, 00111111), or even more complex
link types if one finds them convenient for a given goal. The
hardener would just be a special type of free link.


The second thing the implementation would need to support would
be to combine modules from different translation units. This
would most easily be achieved, if the identity object file==module
would be dropped, allowing one module to spread over different
objects, and one object contain several complete and/or partial
modules. The linker would have to combine those modules, and then
decide if they should be linked in (well, it would have to unite
the symbols only, to decide; code combination can be done after
the decition, if needed).
Note that the linker modules would not have a 1:1 correspondence to
compilation units (however, for "code modules" this correspondence
might be preserved).

Another way would be to allow the compiler "edit" corresponding
object files instead of just replacing them (however, I don't like
that second option; IMHO the combination of modules should be the
linker's job).
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Nathan Myers wrote:
>
>
> Somebody claimed that this omits functions that might be called, but
> offered no examples.  I don't think it's true.

I've had mysterious newsreader glitches, so I don't know if you
responded to my posting in which I said that it omits functions that can
be called. It's easily fixed, but the problem arises with pointers to
member functions, which must generate the same records as virtual calls.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pablo Halpern wrote in message <35bcbe0a.8190800@news.ma.ultranet.com>...
>>>  a. At least one object of class X is constructed AND
>>>  b. f() is called polymorphically through a pointer or reference
>>>     to X or one of its base classes.

I'm sure you intended this as part of (b), but to make it explicit:

"or f() is called polymorphically through a pointer or reference to a class
derived from X which doesn't override X::f"
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <35ba00c6.33474425@news.ma.ultranet.com>,
  phalpern@truffle.ma.ultranet.com (Pablo Halpern) wrote:
> The minimal condition for requiring the inclusion of a virtual function,
> X::f() that is not called statically is:
>
>   a. At least one object of class X is constructed AND
>   b. f() is called polymorphically through a pointer or reference
>      to X or one of its base classes.

I don't think this is sufficient. Consider the following, where no X is ever
constructed, and yet one of X's functions is called polymorphically:

struct X
{
   X() { f(); }
   void f() { g(); }
   virtual void g() { }
};

struct Y : X
{
   virtual void g() { }
};

void main()
{
   Y y;
}

The polymorphic call in X::f() must call X::g() when the X base of the Y
object is constructed. I suspect the various algorithms proposed might omit
X::f() (but not X::g(), which really is never called!).

(Of course your clause a. may have been intended to include this case, but if
so more explicit phrasing would be helpful.)

I think this makes the whole problem much nastier.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Christopher Eltschka wrote:
[good proposal snipped]

I propose a mechanism that can accommodate C++
as well as every other language, past and future,
once and for all.  The proposal fits nicely into one
sentence:  "Add scripting language to linker".
There is a whole lot of good, free, embeddable,
extensible, ready-to-use scripting languages around.
Just pick one and go.

Interested parties can easily work out the
necessary additional primitives the language
should have, and probably even put together
some kind of standard <g>.

Any seconds?
--
Regards
Anatoli (anatoli at ptc dot com) -- opinions aren't
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

I Wrote:
>>
>>  a. At least one object of class X is constructed AND
>>  b. f() is called polymorphically through a pointer or reference
>>     to X or one of its base classes.

ncm@nospam.cantrip.org (Nathan Myers) wrote:

>How to link only needed virtual functions can be described more simply
>than anything I have seen posted yet.
>
>1. When you call a constructor, that class's virtual functions
>   (and any it fails to override) "might be" needed.
>
>2. When you call through a vtable slot, only functions that "might be"
>   needed which occupy that slot actually are needed.   A further
>   optimization is possible: of these, only the function that
>   corresponds to the static type of the reference and any that
>   override it are strictly needed.

This doesn't seem simpler that what I wrote. And it seems less precise.
However, if effectively says exactly the same thing, so its just a
matter of judgement which is easier to understand.

>
>This process is iterative; as you discover a need for each additional
>virtual function, it may create a need for more yet.  You stop when no
>more are needed.
>
>This process can be done in the "prelinker", zeroing out references
>to unneeded virtuals, so it doesn't depend on having control of the
>probably-brain-dead native linker.

Agreed.

-------------------------------------------------------------
Pablo Halpern                   phalpern@truffle.ultranet.com

I am self-employed. Therefore, my opinions *do* represent
those of my employer.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

AllanW@my-dejanews.com wrote:

>>
>>       A::f = compound(A::f_vtbl && A::f_call)
>>  B::f = compound(B::f_vtbl && (B::f_call || A::f_call))
>>  C::f = compound(C::f_vtbl && (C::f_call || B::f_call ||
>>                                       A::f_call))
>>  D::f = compound(D::f_vtbl && (D::f_call || C::f_call ||
>>                                       B::f_call || A::f_call))
>>
>> C::f_vtbl is referenced by C's vtbl.  B::f_call is referenced by the
>> call to b.f().  Thus C::f() is linked in. B::f() would also by linked in
>> using this logic. However, A::f() would not be linked in (because there
>> is no reference to A::f_call), nor would D::f() be linked in (because
>> there is no reference to D::f_vtbl).
>
>Why stop there?  Why not require the linker to do a full run-time
>simulation and synthesize which virtual functions can actually be
>reached at run-time?  [See my earlier post on the Ronko C++ Compiler
>with psychic ability]
>
>This isn't merely complicated, it's draconian.

My algorithm may be complicated in expression because I was putting so
much theory out. I think it could be implemented simply enough. It is
certainly deterministic and not "psychic." It does not require flow
analysis of any kind.

>> The object format and linker logic could be simplified by assigning each
>> simple symbol a bit pattern and causing a compound symbol to be linked
>> only if all of its bits were set by ORing the references to its
>> component simple symbols together. Thus, all of the f_vtbl symbols could
>> be associated with the bit pattern, 0x1 and all of the f_call symbols
>> could be associated with 0xfffffffe.  Only if at least one of the
>> required f_call and the required f_vtbl reference exist would the result
>> be 0xffffffff, and the function would be linked:
>>
>>  B::f = compound(B::f_vtbl | B::f_call | A::f_call)
>>
>> A traditional strong reference would just be a reference associated with
>> the bit pattern 0xffffffff and a traditional weak reference would just
>> be a reference associated with the bit pattern 0.
>
>This is simplified?

Okay, I'll concede that I didn't make it sound too simple. I was also
being too general-purpose for the specific problem.
Let me try again:

1. Besides weak references and strong references, we have "vtbl"
references, which reference special vtbl symbols, and "polymorphic"
references, which reference polymorphic symbols.  Each vtbl symbol can
appear at most once in a linked executable. Each polymorphic symbol can
appear many times.

2. A given virtual function, X::f() defines exactly one vtbl symbol,
X::f and a set of polymorphic symbols, Y::f() for each Y where Y is X or
any base class of X that defines f().  The function is linked in only if
its vtbl symbol AND at least one of its polymorphic symbols are linked
in.

5. The vtbl for class X contains a vtbl reference to X::f.

6. Every polymorphic call to X::f() generates a polymorphic reference to
X::f.

That's it. The bit-field technique is just one way to implement the
condition of requiring two different kinds of references.  Note that
this technique avoids having to create special modules for each class
which are written into by the derived classes.  I don't think this would
be hard to implement.

>I think that most of the people calling for unused-virtual-function
>elimination -- except the Embedded C++ users -- would be satisfied with
>the removal of D::f() (because there is no D object) and C::g() (because
>function g is never called).  In the case of the standard library, this
>would remove almost all of the unrequired virtual functions.

Perhaps. I won't argue with you, since I don't have any data to go by.
Would this assumption make it any easier to implement the optimization?

-------------------------------------------------------------
Pablo Halpern                   phalpern@truffle.ultranet.com

I am self-employed. Therefore, my opinions *do* represent
those of my employer.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pablo Halpern<phalpern@truffle.ma.ultranet.com> wrote:
>Pablo Wrote:
>>>
>>>  a. At least one object of class X is constructed AND
>>>  b. f() is called polymorphically through a pointer or reference
>>>     to X or one of its base classes.
>
>ncm@nospam.cantrip.org (Nathan Myers) wrote:
>
>>1. When you call a constructor, that class's virtual functions
>>   (and any it fails to override) "might be" needed.
>>
>>2. When you call through a vtable slot, only functions that "might be"
>>   needed which occupy that slot actually are needed.   A further
>>   optimization is possible: of these, only the function that
>>   corresponds to the static type of the reference and any that
>>   override it are strictly needed.
>
Pablo wrote:
>This doesn't seem simpler that what I wrote. And it seems less precise.
>However, if effectively says exactly the same thing, so its just a
>matter of judgement which is easier to understand.

I'm sorry.  Your posting was long and I didn't recognize the
points as a summary.

Somebody claimed that this omits functions that might be called, but
offered no examples.  I don't think it's true.

>>This process is iterative; as you discover a need for each additional
>>virtual function, it may create a need for more yet.  You stop when no
>>more are needed.
>>
>>This process can be done in the "prelinker", zeroing out references
>>to unneeded virtuals, so it doesn't depend on having control of the
>>probably-brain-dead native linker.
>
> Agreed.

A different, somewhat less effective approach is much easier to
implement in the pre-linker.  Instead of omitting all virtuals
and then adopting them as needed, you keep them all except the
ones not evidently used.  This is less effective because it keeps
some functions that are called only by other virtuals which might
not be needed themselves.  However, it can be done a lot quicker.
E.g. in


   struct X {
     virtual void f() { g(); }
     virtual void g() { f(); }
   };
   int main() { X* x = new X; }

it would keep f and g unnecessarily.  Still, it might be entirely
sufficient as an optimization.

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pablo Halpern<phalpern@truffle.ma.ultranet.com> wrote:
>
>1. Besides weak references and strong references, we have "vtbl"
>references, which reference special vtbl symbols, and "polymorphic"
>references, which reference polymorphic symbols.  Each vtbl symbol can
>appear at most once in a linked executable. Each polymorphic symbol can
>appear many times.
>
>2. A given virtual function, X::f() defines exactly one vtbl symbol,
>X::f and a set of polymorphic symbols, Y::f() for each Y where Y is X or
>any base class of X that defines f().  The function is linked in only if
>its vtbl symbol AND at least one of its polymorphic symbols are linked
>in.
>
>5. The vtbl for class X contains a vtbl reference to X::f.
>
>6. Every polymorphic call to X::f() generates a polymorphic reference to
>X::f.
>
>That's it.  ...  Note that
>this technique avoids having to create special modules for each class
>which are written into by the derived classes.  I don't think this would
>be hard to implement.

This is precisely the algorithm I had in mind, as well.

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

It was bbrunswick@my-dejanews.com who first posted the suggestion that
led me to this train of thought.

First, some definitions of linker terms:

Reference A use of an undefined symbol. The linker searches its
  available object files and libraries, trying to find
  one which defines the symbol. The reference is then
  replaced with the value of the symbol.

Weak Reference Just like a Reference, but the linker will not pull in
  a module just to satisfy this type of reference. If a
  module defining the symbol is pulled in for another
  reason, the reference is replaced with the value of the
  symbol, but otherwise the reference is replaced with zero.

Transparent Symbol
  I just made this one up. This is what needs to be added to
  linkers to enable the elimination of unused virtuals. A
  Transparent Symbol causes a module to be pulled in by the linker
  if the linker has unresolved references to the symbol, but
  this does not cause the symbol to become defined; the linker
  will continue to pull in other modules that define the same
  transparent symbol.

So here's the scheme. We assign a symbol for each slot in the vtable
of each class which first declares a virtual function. The vtable
itself contains weak references to the virtual functions. Whenever a
polymorphic call is made to a virtual function, we generate a
reference to the appropriate slot symbol. In every module which
contains an implementation of a virtual function, we generate a transparent
symbol for that function's slot. And that's it.

Because the vtable references are weak, the vtable itself does not
cause any module to be forcibly linked. Whenever a polymorphic call to
a virtual function is made, the resulting reference to the transparent
symbol will cause the linker to pull in all modules which define that
symbol, so virtual functions from derived classes will get properly
linked.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hyman Rosen wrote:
>
> So here's the scheme. We assign a symbol for each slot in the vtable
> of each class which first declares a virtual function. The vtable
> itself contains weak references to the virtual functions. Whenever a
> polymorphic call is made to a virtual function, we generate a
> reference to the appropriate slot symbol. In every module which
> contains an implementation of a virtual function, we generate a transparent
> symbol for that function's slot. And that's it.

 I think this goes too far. Consider a library that contains a class
derived from Base, overriding Base::f(). Any virtual call in the program
to Base::f will force the overriding version to be linked in, even if
the derived class is never actually used.
 Thanks, though: I thought I had a technique that worked, but it turns
out that it has exactly the same problem. I hadn't seen it until I read
your example.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.com


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hyman Rosen <hymie@prolifics.com> wrote:

>First, some definitions of linker terms:

[ Defines "Reference," "Weak Reference," and "Transparent Symbol" ]

>So here's the scheme. We assign a symbol for each slot in the vtable
>of each class which first declares a virtual function. The vtable
>itself contains weak references to the virtual functions. Whenever a
>polymorphic call is made to a virtual function, we generate a
>reference to the appropriate slot symbol. In every module which
>contains an implementation of a virtual function, we generate a transparent
>symbol for that function's slot. And that's it.
>
>Because the vtable references are weak, the vtable itself does not
>cause any module to be forcibly linked. Whenever a polymorphic call to
>a virtual function is made, the resulting reference to the transparent
>symbol will cause the linker to pull in all modules which define that
>symbol, so virtual functions from derived classes will get properly
>linked.

Since you started a new thread, I will repeat part of my response to
your post in the thread titled, "Re: Weak refs suffice for virtual
pruning - was C++ as PL/1". I have adjusted the language to your new
definitions.

Your idea is a start, but it is not enough.

The minimal condition for requiring the inclusion of a virtual function,
X::f() that is not called statically is:

  a. At least one object of class X is constructed AND
  b. f() is called polymorphically through a pointer or reference
     to X or one of its base classes.

Now, lets look at an example:

struct A            { virtual void f(); };
struct B : public A { virtual void f(); };
struct C : public B { virtual void f(); virtual void h(); };
struct D : public C { virtual void f(); };

void g(B& b) { b.f(); /* polymophic call */ }
int main() { A a; B b; C c; g(c); }

Your solution would generate symbol for A::f() that we'll call
A::f_call. The implementations of A::f(), B::f(), C::f() and D::f()
would all define the transparent symbol A::f_call. The call to b.f()
would generate a reference to A::f_call, causing A::f(), B::f(), C::f()
and D::f() all to be linked in.

This would prevent C::h() from being liked in, thus saving some code
bloat. Depending on the program, it might save a lot of code bloat.
However, the minimal rules I proposed above say you can do better.  Our
program does not construct an object of type D, so it clearly doesn't
need D::f().  Also, we don't call f() through A or a base class of A, so
we don't need A::f(), either.

It seems our linker would have to be quite a bit smarter. Perhaps,
instead of a transparent symbol, we could have a compound symbol that
represents a boolean condition. Each portion of a boolean expression
would be represented by a simple symbol. That portion of the expression
would evaulate true if a reference to that symbol exists in the program.
Only if the whole expression evaluates true is the compound symbol
linked in.  So, for our example we would have the following compound
symbols:

        A::f = compound(A::f_vtbl && A::f_call)
 B::f = compound(B::f_vtbl && (B::f_call || A::f_call))
 C::f = compound(C::f_vtbl && (C::f_call || B::f_call ||
                                      A::f_call))
 D::f = compound(D::f_vtbl && (D::f_call || C::f_call ||
                                      B::f_call || A::f_call))

C::f_vtbl is referenced by C's vtbl.  B::f_call is referenced by the
call to b.f().  Thus C::f() is linked in. B::f() would also by linked in
using this logic. However, A::f() would not be linked in (because there
is no reference to A::f_call), nor would D::f() be linked in (because
there is no reference to D::f_vtbl).

The object format and linker logic could be simplified by assigning each
simple symbol a bit pattern and causing a compound symbol to be linked
only if all of its bits were set by ORing the references to its
component simple symbols together. Thus, all of the f_vtbl symbols could
be associated with the bit pattern, 0x1 and all of the f_call symbols
could be associated with 0xfffffffe.  Only if at least one of the
required f_call and the required f_vtbl reference exist would the result
be 0xffffffff, and the function would be linked:

 B::f = compound(B::f_vtbl | B::f_call | A::f_call)

A traditional strong reference would just be a reference associated with
the bit pattern 0xffffffff and a traditional weak reference would just
be a reference associated with the bit pattern 0.

Finally, it should be noted that my algorithm would cause B::f() to be
linked in, even though it is not really needed. However, determining
that B::f() is not needed would require global flow analysis, and not
just a static set of rules. In a non-trivial program, the amount of
code-bloat saved by doing the global analysis is not likely to be
significant. IMHO, there are certainly better places to put your
optimization dollars.

-------------------------------------------------------------
Pablo Halpern                   phalpern@truffle.ultranet.com

I am self-employed. Therefore, my opinions *do* represent
those of my employer.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

How to link only needed virtual functions can be described more simply
than anything I have seen posted yet.

1. When you call a constructor, that class's virtual functions
   (and any it fails to override) "might be" needed.

2. When you call through a vtable slot, only functions that "might be"
   needed which occupy that slot actually are needed.   A further
   optimization is possible: of these, only the function that
   corresponds to the static type of the reference and any that
   override it are strictly needed.

This process is iterative; as you discover a need for each additional
virtual function, it may create a need for more yet.  You stop when no
more are needed.

This process can be done in the "prelinker", zeroing out references
to unneeded virtuals, so it doesn't depend on having control of the
probably-brain-dead native linker.

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pablo Halpern wrote:
> Your idea is a start, but it is not enough.
>
> The minimal condition for requiring the inclusion of a virtual function,
> X::f() that is not called statically is:
>
>   a. At least one object of class X is constructed AND
>   b. f() is called polymorphically through a pointer or reference
>      to X or one of its base classes.
>
> Now, lets look at an example:
>
> struct A            { virtual void f(); };
> struct B : public A { virtual void f(); };
> struct C : public B { virtual void f(); virtual void h(); };
> struct D : public C { virtual void f(); };
>
> void g(B& b) { b.f(); /* polymophic call */ }
> int main() { A a; B b; C c; g(c); }
>
> Your solution would generate symbol for A::f() that we'll call
> A::f_call. The implementations of A::f(), B::f(), C::f() and D::f()
> would all define the transparent symbol A::f_call. The call to b.f()
> would generate a reference to A::f_call, causing A::f(), B::f(), C::f()
> and D::f() all to be linked in.
>
> This would prevent C::h() from being liked in, thus saving some code
> bloat. Depending on the program, it might save a lot of code bloat.
> However, the minimal rules I proposed above say you can do better.  Our
> program does not construct an object of type D, so it clearly doesn't
> need D::f().  Also, we don't call f() through A or a base class of A, so
> we don't need A::f(), either.

Hmm... Suppose we modify the linker's behavior on transparent symbols, such
that a module defining a transparent symbol is linked in only if there
exists a (weak or normal) reference to a non-transparent symbol within that
module. This prevents the module from being linked in if there isn't a
vtable asking for its functions.

Furthermore, when the compiler sees a polymorphic call to a function f, it
generates a reference to the final overrider of f_call within the static
type of the pointer or reference used in the call.

When the compiler generates the out-of-line code for the f of a class, it
generates transparent symbols for each of the base classes in which f is a
final overrider.

So, given your example, let's have the following files:

Af.C: void A::f() { }
Bf.C: void B::f() { }
Cf.c: void C::f() { }
Ch.c: void C::h() { }
Df.c: void D::f() { }
main.C: void g(B& b) { b.f(); } int main() { A a; B b; C c; g(c); }

Then

Af.C: S A::f TS A::f_call
Bf.C: S B::f TS B::f_call, A::f_call
Cf.C: S C::f TS C::f_call, B::f_call, A::f_call
Ch.c: S C::h TS C::h_call
Df.c: S D::f TS D::f_call, C::f_call, B::f_call, A::f_call
main.c: WR A::f, B::f, C::f, C::h
  R B::f_call

The reference to B::f_call will cause Bf.c and Cf.c to be linked in because
there are references to B::f and C::f from the vtables in main.C. Af.c does
not get linked in because there is only a weak reference to A::f. Df.c does
not get linked in because there is no reference to D::f, despite the
presence of B::f_call. Ch.c does not linked in because there is only a weak
reference to C::h.

I think this gives us what we wanted.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]