Virtual function call stuff, again

[Mark Mitchell]

>>>>> "Christophe" == Christophe de Dinechin <ddd at cup.hp.com> writes:

Thanks for helping me with this.

    Christophe> Mark, I did not find anything containing "Virtual
    Christophe> Function Calling Convention" in the
    Christophe> documentation. Could you specify an URL and quote the
    Christophe> original text, it would help me locating it...

http://reality.sgi.com/dehnert_engr/cxx/abi-layout.html#vtable

There doesn't appear to be a tag for the "VFCC" section, but it's down
just a bit from the URL I gave.

    >> Here's an attempted rewrite.  Let's see if it's what y'all
    >> meant.

    >>  o Suppose a class `A' defines a virtual function `A::f'.  The
    >> primary vtable for `A' contains a pointer to an entry point
    >> that performs no adjustment.
    >> 
    >> o Suppose that a class `A' declares a virtual function `A::f',
    >> and suppose that `A' is a base class in a hierarchy dominated
    >> by another class `B'.  Suppose that the unique final overrider
    >> for `A::f' in `B' is `C::f'.  We must determine what entry
    >> point is used for `f' in the `A-in-B' secondary vtable.  Here
    >> is the algorithm:
    >> 
    >> - Find any path from `B' to `C' in the inheritance graph for
    >> `B'.
    >> 
    >> - If there is no virtual base along the path, then create an
    >> entry point which adjusts the `this' pointer from `A' to `C'.
    >> This value can be computed statically when the `A-in-B' vtable
    >> is created.  Then transfer control to the non-adjusting entry
    >> point for `C::f'.

    Christophe> Yes. What's more, in that case, the offset is stored
    Christophe> in the vtable at a (possibly large) constant negative
    Christophe> offset from the vptr. We called this offset
    Christophe> 'convert_to_C', and it is used only when the final
    Christophe> overrider is a C. The A-in-B vtable contains a
    Christophe> 'convert_to_C' value that converts from an A* to a
    Christophe> C*. The benefits are explained in
    Christophe> http://reality.sgi.com/dehnert_engr/cxx/cxx-closed.html,
    Christophe> section B-1.

I understand the high-level points of that discussion: what I don't
understand is exactly what goes where, when.  I'm not really trying to
reopen any issue -- I'm trying to force the committe to write down
what it decided.  At this point, the decision is not, quite frankly,
written in a form that anyone not on the committee is likely to
decipher.  (Well, at least I've tried hard, I'm not an idiot, I know
about this application domain, and I still can't figure it out.)

    >> - If there is a virtual base along this path, let `V' be the
    >> virtual base nearest to `C' along the path.  (In fact, `V' will
    >> be `C' itself if `C' is a virtual base.)

    Christophe> You are considering a path between B and C, so V would
    Christophe> be the closest between B and C. In which case I do not
    Christophe> understand the adjustment below ("Adjustment from 'A'
    Christophe> to 'V'"). Either you are considering that V is between
    Christophe> A and C, in which case you need to adjust from A to V,
    Christophe> or you are considering that V is between C and B, in
    Christophe> which case if you see it at call site, you would have
    Christophe> to adjust from B to V. Did I misunderstand?

You won't in general see `V' at the call site, if it's between C and
B, because you might have `A*' when you're making the call.  (If you
had a `B*', or a `C*', then `C::f' would be the unique final overrider
-- by hypothesis -- so you would have converted your pointer to a
`C*', and you be looking at the C-in-B vtable, rather than the A-in-B
vtable, which is what my discussion was talking about.)

I'm not sure where you're supposed to adjust `A' to.  That's what I'm
trying to find out.  It may not be the V that I suggested -- I'm not
sure.  I'm hoping that my words could serve as the model for whatever
the right answer is.  They're in the form of an algorithm that
explains exactly what to put in the vtable, in the general case, and
that's a good thing, since that's what an implementor needs to know.

    Christophe> So, starting with your example again. Sorry for the
    Christophe> verbiage...

    Christophe> Case 1 is: V is between A and C.

THere's no discussion of these two different cases in the current
writeup.  So, I'm already lost.  What you write below seems reasonably
logical -- but I'm not sure it's the same thing as in the document.

In general, "between A and C" doesn't make sense; they may be
unrelated. The picture I had in mind was:

              B
             / \
            A   C

In other words, B is the most derived class, C contains the final
overrider, we're looking at the vtable for A.  That's the general case
-- all other cases are special instances of this one.  But, I guess
for case 1, we're assuming C is derived from A?

    Christophe> - If you call through an A*, you call through the A
    Christophe> vtable, which points to a virtual-base-adjustment
    Christophe> thunk. That thunk reads the C-to-A virtual base
    Christophe> offset, and adds that to get a C*, and then jumps to

Where is this offset?  There's a vbase offset in C for converting to
A, if A is a virtual base of C.  But, there's no virtual base offset
in A, for converting to a C.  Where's V in all this?

    Christophe> the non-adjusting C::f. Of course, the C-to-A virtual
    Christophe> base offset is not necessarily constant along the
    Christophe> class hierarchy, so for instance the C-to-A virtual
    Christophe> base offset in a C is not the same as the C-to-A
    Christophe> virtual base offset in a B.

I don't understand this.

    Christophe> - If you call through a C*, you call through the C
    Christophe> vtable. In that case, you don't care if A is a virtual
    Christophe> base, since C::f expects a C*. Virtual-base adjustment
    Christophe> to A, if necessary, would be done inside C::f. So the
    Christophe> C vtable points to the non-adjusting entry point.

That one makes sense.

    Christophe> - If you call through a B*, you call through the C
    Christophe> vtable (the final overrider for f), and you adjust to
    Christophe> a C* statically.

That too.

    Christophe> Case 2: V is between C and B:

    Christophe> - If you call through an A*, you call through the A
    Christophe> vtable. The offset from A to C is constant in the
    Christophe> class hierarchy, but there may be multiple bases A1,
    Christophe> A2, A3, with different offsets. The "classical"

Are all these bases of type A?  Or are these just different bases, all
of which declare the same `f' overridden by `C::f'?

    Christophe> approach is to use multiple thunks that convert from
    Christophe> A1 to C, from A2 to C, from A3 to C. Because of the
    Christophe> high cache muss and branch misprediction penalty, I
    Christophe> proposed that we rather have all vtables A1-in-C,
    Christophe> A2-in-C, ... contain an offset, call it
    Christophe> 'Convert_to_C', that adjusts from A1 to C, A2 to C,
    Christophe> etc. This way, there can be a single adjusting entry
    Christophe> point that does this adjustment (although you can
    Christophe> still emit thunks)

Right -- I get that.  And the point is that you can store the
'convert_to_C' offset at some fixed negative index from the vptr from
each *unadjusted* `this' pointer? 

    Christophe> - If you call through a C*, you call through the C
    Christophe> vtable, which points to the non-adjusting entry point
    Christophe> C::f.

Yes.

    Christophe> - If you call through a B*, you need at call-site to
    Christophe> convert from B* to C*, which involves a dynamic
    Christophe> adjustment using the B-to-V virtual base offsets in
    Christophe> B's vtable, followed by a static adjustment from V to
    Christophe> C (which is known at compile-time).

Yes.  Note that in my attempted writeup, I wasn't trying to specify
how to call the function: I was trying to specify what you put in the
vtable for A.

    Christophe> I'm not sure I clarified anything ;-)

Somewhat. :-)

    Christophe> First, note that the scheme is believed to be
    Christophe> advantageous whenever there is no virtual inheritance,
    Christophe> which I think is a frequent case. Cache locality plays
    Christophe> a big role here.

OK.  It would really help if the ABI document contained some
non-normative notes explaining some of this, and giving some examples.
Unfortunately, I can't write these, because I don't know the answers.

    Christophe> Second, in the virtual base case, there is no
    Christophe> guarantee that the thunk will be right before the
    Christophe> non-adjusting entry point: as Jason pointed out, you
    Christophe> cannot find a single offset to use to perform the
    Christophe> adjustment.

    Christophe> Third, I do not understand in this statement whether
    Christophe> you are calling through an A*, B* or C*.

An A*: that's the point of figuring out what to put in the A-in-B
vtable.  (In general, we might be calling through something derived
from `A' but where `A::f' is the unique final overrider in that
objects static type.  So, we first convert to `A*' -- then use the
A-in-B vtable to get to `C::f'.)

    >>  I still can't see why it is a win to use vcall offsets in the
    >> case where `A' and `V' are not the same class.  You already
    >> have to do one static adjustment in the entry point -- why not
    >> just adjust all the way to `B' directly, without bothering to
    >> look up the vcall offset?

    Christophe> I did not understand this question :-( If you feel a

It seems to me, from:

   For each secondary vtable from a base 'D' which is a non-virtual
   base of a virtual base 'E', an additional entry point is generated
   in the secondary vtable for 'E' which first performs the constant
   adjustment from D* to E*, then the adjustment from E* to A* by
   adding the vcall offset for f stored in the secondary vtable for E.

(which I admittedly do not understand -- hence this email!) that there
are some situations where we have an entry point which *both* performs
a constant adjustment *and* adjustes via a vcall offset.  In other
words, it does two adjustments.  So the code for that entry point will
look like:

  entry:
    adjust by constant to a virtual base
    jump to vcall-adjusting-entry-point

(Then, elsewhere, we have:

  vcall-adjusting-entry-point:
    adjust by vcall offset
  f:
    /* here's where user code starts */)

Note that `entry' needs a jump at the end -- it can't just
fall-through (in general) because there may be lots of different such
double-adjusting things.  So, I'm asking why this is a win over just:

  entry:
    adjust by constant all the way to the destination
    jump to f

The point is that if we're going to adjust by a constant and then
jump, we might as well adjust all the way.
  
    Christophe> static thunk is better than a dynamic lookup, then you
    Christophe> can emit that thunk and point to it through the
    Christophe> vtable, as Jason pointed out. The ABI allows you to do
    Christophe> that.

That's unclear.  That may have been the intent, but there's no
discussion of what's normative and what's not in the ABI.

The ABI says:

    For each secondary vtable from a virtual base class 'C' which
    defines f, an additional entry point is generated which performs
    the adjustment from A* to C* by adding the vcall offset for f
    stored in the secondary vtable for A. 

It doesn't say that you can adjust in some other way, for instance.
It also says that the caller adjusts to the class containing the
unique final overrider.  It should just say that the caller locates
any class containing a virtual function table entry for the function,
converts `this' to that class, and calls the corresponding entry.
*Which* class is chosen isn't an ABI issue.  Then, there should be a
non-normative note that says (Note: it is probably most efficient to
convert to the class containing the unique final overrider.)

    >> Furthermore, the actual algorithm used to perform the
    >> adjustments does not seem necessarily to be part of the ABI.
    >> The layout of the vtables is certainly part of the ABI.  But,
    >> if one compiler wants to completely ignore the vcall offset
    >> entries in the vtables, and compute the entire adjustment
    >> statically, shouldn't that be permitted by the ABI, even though
    >> it might require one extra branch?  Surely that's just a
    >> quality-of-implementation issue?

    Christophe> Correct. Again, that seems clear to me from Jason's
    Christophe> writeup:

    Christophe> Note that the ABI only specifies the multiple entry
    Christophe> points; how those entry points are provided is
    Christophe> unspecified. An existing compiler which uses thunks
    Christophe> could be converted to use this ABI by only adding
    Christophe> support for the vcall offsets. A more efficient

That's the sentence that's unclear.  It should say something more
like:

    An existing compiler which uses thunks could be converted to use
    this ABI by adding vcall offsets in the vtable (as required by the
    ABI).  (The thunks generated need not be modified.)

I'm not trying to split hairs, or polish prose.  These are places
where I'm legitimately unsure as to the intent of the words written.

--
Mark Mitchell                   mark at codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com