We're out of tree codes; now what?

[Doug Gregor]

On 3/21/07, Mark Mitchell <mark@codesourcery.com> wrote:
> Yes, that's true.  Here, however, we have two paths in front of us:
> 9-bit tree codes, or some language-dependent subcodes.  The benefit of
> 9-bit tree codes is that they're easy to understand; the benefit of
> subcodes is that they might be faster, but, then again, they might use
> more memory.  I'd be interested in understanding the tradeoff.

I have now implemented subcodes for all of the C++ type nodes. The
patch is attached. It bootstraps and passes C++ compiler and
libstdc++-v3 test suites. A small amount of work remains before we
would be able to build other front ends, because I had to change some
common bits.

The basic approach:

  I've used the LANG_TYPE tree code to identify the subcoded types
within the C++ front end. When TREE_CODE (T) = LANG_TYPE, the C++
front end will look into TYPE_LANG_SPECIFIC to dig out a subcode. All
of the "tcc_type" nodes that were in cp-tree.def are now subcoded
types.

  To keep the same switches and tests in the C++ front end, I added
LANG_TREE_CODE, which maps normal trees and subcoded trees into the
same code space (subcoded trees get codes > 256). Relying heavily on
warnings about case values being out of range and comparisons that
always produce false, I tweaked those TREE_CODE accesses in the front
end to instead use LANG_TREE_CODE.

The results, memory usage:

Memory usage rose a constant, negligible amount. I was able to fit the
subcode into padding in the existing lang_tree struct for the two
lang_tree kinds that are dynamically allocated (lang_tree_class,
lang_tree_ptrmem). For the new lang_tree kinds, we allocate only
lang_tree_headers, and I've used Daniel's trick of keeping constant
lang_tree_header pointers as statics. So, aside from a compile new
one-time allocations, --enable-gather-detailed-mem-stats doesn't show
any differences in memory usage. Good.

The results, compile time:

For a bootstrapped, --disable-checking compiler:

8-bit tree code (baseline):

real    0m51.987s
user    0m41.283s
sys     0m0.420s

subcodes (this patch):

real    0m53.168s
user    0m41.297s
sys     0m0.432s

9-bit tree code (alternative):

real    0m56.409s
user    0m43.942s
sys     0m0.429s

So, performance of subcodes is comparable to baseline with
--disable-checking. Good.

With --enable-checking, the results are quite frightening:

8-bit tree codes (baseline, --enable-checking):

real    1m56.776s
user    1m54.995s
sys     0m0.541s

subcodes (--enable-checking):

real    3m32.030s
user    2m53.606s
sys     0m0.486s

50% slower. Ouch! I only decided to check --enable-checking
performance after I noticed that the libstdc++-v3 tests were taking
way too long to run.

So without looking at the patch itself, we can get about the same
performance with no change in memory usage, but that horrific slowdown
in --enable-checking is going to seriously hurt the C++ front end
development process.

The patch itself is really big, so I'll try to point out the highlights:

cp_types.def:

All of the tcc_type nodes from cp-tree.def have moved into
cp-types.def, because they are subcoded. All of these subcoded types
share the same, top-level "LANG_TYPE".

cp-tree.h:

enum cplus_tree_code contains all of the common, C, and C++ tree
codes, followed by a separator with the value 256, then the subcoded
types. So subcoded types always have values > 256. LANG_TREE_CODE
extracts the "extended" tree code from a tree, by adding the type
subcode to 256 when we see a LANG_TYPE node.

struct lang_type_header has the new 8-bit subcode. TYPE_LANG_SPECIFIC
always points to at least a struct lang_type_header, possibly
something larger (for RECORD_TYPE nodes).

You'll see lots of TREE_CODE -> LANG_TREE_CODE changes; I'll get back
to those later.

cp/cp-lang.c:

I ended up making the tree_code_type, tree_code_length, and
tree_code_name structures larger, to accommodate the new tree codes. I
also had to make them non-const, because there is no good way to
initialize the first N elements in an array, fill the elements from N
to 256, then initialize everything beyond 256.

cp/lex.c:

cxx_make_type has been updated to check the (extended) tree code it is
given. If that tree code > 256, it builds a LANG_TYPE with the
appropriate subcode (note how we don't allocate anything for most
subcoded types; only the ones that allocated a TYPE_LANG_SPECIFIC
before).

everywhere:

The TREE_CODE -> LANG_TREE_CODE fixes took most of the development
effort for this patch. I ended up doing a lot of grep'ing, watching
GCC's warnings carefully, and debugging ICEs to get everything up and
running. It wasn't pretty, and I'm not convinced I got them all. GCC's
warning about comparisons always being false or case values that are
too large (both due to limited range of data types) were somewhat
useful, but they miss two important kinds of cases:

(a)
  enum tree_code code = TREE_CODE (t);
  switch (code)
    {
    case TYPENAME_TYPE:
      // oops, we'll never get here, because TYPENAME_TYPE is
subtyped. GCC does *not* warn about this
    break;
    }

(b)
  if (TREE_CODE (t1) != TREE_CODE (t2)) // all LANG_TYPEs are created
equal; uh-oh
    return false;

Grep found most of the latter, gdb found most of the former. Not pretty.

On significant problem remains, and it will get uglier if we don't
address it. The middle-end doesn't know anything about subcodes, so it
treats LANG_TYPE like any other type. That almost works, because all
type nodes are the same size (100 bytes!), but if one tries to
"debug_tree" the tree node name is always "lang_type." If we tried to
subcode expressions and declarations, we may run into problems where
tree_code_length is wrong.

So, while I was trying to keep my changes in the C++ front end, I
think the only way to make subcodes work is to teach the middle-end
that LANG_TYPE (and future LANG_DECL and LANG_EXPR) are subcoded. That
probably means creating hooks for tree_code_name and tree_code_length,
possibly others.

Take a skim through the patch. There might be some cleanups that one
could do, and perhaps things might be a little nicer if subcodes were
in the middle-end as described above. However, I find this solution to
be rather unwieldy, and the process that makes it possible (grepping,
watching warnings) to be problematic for future development. The 50%
slowdown in the C++ front end with --enable-checking is also a great
concern to me.

Comments always welcome, and generally appreciated :)

  Cheers,
  Doug
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cp-subcodes.patch
Type: text/x-patch
Size: 95245 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20070322/7026e7fc/attachment.bin>