Re: C++ PATCH: throw (T *)NULL and dynamic_cast

[Nathan Sidwell <nathan at acm dot org>]

Jason Merrill wrote:
> 
> An idea for accelerating dynamic_cast came up in the ABI group:

Here's a replacement for the runtime behaviour of dynamic cast and catch
matching. It's pretty much a complete replacement for tinfo.cc. The
existing behaviour is broken, as the attached testcases show. I've
split the handling of catching (upcast towards a base class, possibly
with a NULL pointer), and dynamic casting (downcast or crosscast with
non-NULL objects). It's probably easiest to just read the source -- I've
heavily commented it, as the algorithm can get rather hairy when dealing
with multiple virtual inheritance via various access paths. Here's the
highlights.

I've removed any WANT_PUBLIC parameter, as we always want this.

The upcast behaviour is fairly straight forward, the trickiness is
coping with a NULL object and spotting ambiguous bases. I do this by
tracking the most derrived virtual base containing the target. When
multiple target bases are found, the most derrived virtual base must be
the same, otherwise it is ambiguous. I also early-out whenever an
ambiguity is found or private base is found. You have to search the
private bases to check for ambiguity.

The dynamic cast behaviour is more complicated. Jason suggested an
improved algorithm, which I've augmented further. The basic idea in a
dynamic cast from static type V to target type T of some object with
dynamic type X is to give some indication of how T derrives from V via
a parameter BOFF. Here is my augmented algorithm.
BOFF >= 0, The only public V base of T is non-virtual. The
offset from T to V is BOFF.
BOFF = -1, The public V bases of T are all non-virtual.
BOFF = -2, The public V bases of T are both vitual and non-virtual. This
is the safe `don't know' value, used for backwards compatibility.
BOFF = -3, There are no public V bases of T.
Note, in all cases there might be private V bases of T.

The search proceeds with the most derrived type, doing a depth-first
search for a T base. When a T base is found we do a quick check when BOFF
>= 0 to see if the subobject we started from is at that offset (this is
just a pointer comparison). If it is, this is a downcast and we're
done. Otherwise we continue searching. If we have found a previous T
base, we have a possible ambiguity. We search for the V subobject we
started from inside both choices, and if it is in one of them
non-virtually, then it's a downcast and we're done. If it is in only one of
them virtually, it's possibly a downcast, so we remember that and
continue searching. If it is in both it's ambiguous and we're done.
Otherwise it's ambiguous but we continue searching. In looking for the
subobject we take advantage of BOFF to prune the tree walk. Though this
walk will skip private bases, that doesn't matter as a downcast can
only succeed with a public V base. During the search, if we find the V
subobject we started from, then it can only be a cross cast. We take
note of where the subobject was. Once we've done the search, and it
still looks valid, we have to check if the access path is OK.
It might be that we already know sufficient
information (cross cast and some down casts). When we don't, we search
inside the located target object for the V subobject and if, that is
found publicly it's a downcast.

For both downcast and upcast, we don't know the ratio of failures to
successes. It is therefore not possible to slant the algorithm in
favour of either. I've either filled things in lazily, when it is known
the information is required, or opportunisticly note fortuitous
information. I also take early outs when I can determine unequivically
what the result will be part way thought the tree walk. For instance
during a dyncast tree walk, if the V subobject is located via private
non-virtual access from the most derrived object, it must fail (cross
cast will fail, and it cannot be a downcast as in that case we'd have
met the target object first).

In build_dynamic_cast_1 (rtti.c), we determine the BOFF parameter using
get_base_distance. That unfortunately cannot be instructed to ignore
the non-public bases. And when ambiguity is found, cannot indicate
whether they were all non-virtual. So we currently cannot use all the
BOFF values above. Anyway the hook's there. The new dynamic cast
runtime function is __dynamic_cast_2, which passes through the BOFF
parameter. The existing function __dynamic_cast remains, and provides a
BOFF of -2.

Hope this makes sufficient sense.

I've attached the patch and testcases as a tar gzip -- that ok?

nathan
-- 
Dr Nathan Sidwell :: Computer Science Department :: Bristol University
        I have seen the death of PhotoShop -- it is called GIMP
nathan@acm.org  http://www.cs.bris.ac.uk/~nathan/  nathan@cs.bris.ac.uk

rtti.tar.gz