We're out of tree codes; now what?

["Doug Gregor" <doug dot gregor at gmail dot com>]

[This is a re-send of my previous e-mail; my apologies, yet again, for
the e-mail mangling on my end. Those responsible have been sacked.]

With the introduction of the variadic templates patch, we now have
more than 255 tree codes in GCC. This causes the mainline
Objective-C++ compiler to fail to build:

 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31134

We've known for a long time that we would eventually hit the limit on
the number of tree codes in GCC, and the variadic templates patch
happened to win the 8-bit tree-code lottery. Reverting the variadic
templates patch is not a solution: we'll hit this limit again, and
next time it will be with a feature that you find crucial. Reducing
the number of tree codes we use also seems infeasible: combining two
somewhat-similar entities into a single tree code is a short-term fix
with long-term problems, including poor readability and a greater
likelihood of bugs.

We need more tree codes. With GCC's current structure, that means
increasing the number of bits allocated for tree codes in the
tree_base struct. This will increase GCC's memory footprint. It's
unfortunate, but is it avoidable? I suspect it is not, without a major
restructuring of the compiler.

The patch below makes the CODE field of the tree_base struct 16 bits,
and adds suitable padding to fill out a 32-bit word. Elsewhere, the
limit on tree codes is raised to 512. Tested i686-pc-linux-gnu; no
regressions with C, C++, Objective C, Objective-C++, or Java.

Note: I've also sent this to gcc-patches, because there is a patch in
it. However, let's keep the discussion on gcc@gcc.gnu.org.

 Cheers,
 Doug

:ADDPATCH C:

2007-03-12  Douglas Gregor  <doug.gregor@gmail.com>

       * tree.c (tree_contains_struct): Permit 512 tree codes.
       * tree.h (tree_contains_struct): Ditto.
       (MAX_TREE_CODES): Ditto.
       (struct tree_base): Make CODE 16 bits, instead of 8 bits. Add
       SPARE member to store remaining padding bits.

Index: tree.c
===================================================================
--- tree.c      (revision 122840)
+++ tree.c      (working copy)
@@ -168,7 +168,7 @@ static unsigned int attribute_hash_list
tree global_trees[TI_MAX];
tree integer_types[itk_none];

-unsigned char tree_contains_struct[256][64];
+unsigned char tree_contains_struct[512][64];

/* Number of operands for each OpenMP clause.  */
unsigned const char omp_clause_num_ops[] =
Index: tree.h
===================================================================
--- tree.h      (revision 122840)
+++ tree.h      (working copy)
@@ -41,7 +41,7 @@ enum tree_code {

#undef DEFTREECODE

-extern unsigned char tree_contains_struct[256][64];
+extern unsigned char tree_contains_struct[512][64];
#define CODE_CONTAINS_STRUCT(CODE, STRUCT)
(tree_contains_struct[(CODE)][(STRUCT)])

/* Number of language-independent tree codes.  */
@@ -80,7 +80,7 @@ extern const char *const tree_code_class
#define TREE_CODE_CLASS_STRING(CLASS)\
        tree_code_class_strings[(int) (CLASS)]

-#define MAX_TREE_CODES 256
+#define MAX_TREE_CODES 512
extern const enum tree_code_class tree_code_type[];
#define TREE_CODE_CLASS(CODE)  tree_code_type[(int) (CODE)]

@@ -363,7 +363,7 @@ union tree_ann_d;

struct tree_base GTY(())
{
-  ENUM_BITFIELD(tree_code) code : 8;
+  ENUM_BITFIELD(tree_code) code : 16;

  unsigned side_effects_flag : 1;
  unsigned constant_flag : 1;
@@ -392,6 +392,8 @@ struct tree_base GTY(())
  unsigned lang_flag_6 : 1;
  unsigned visited : 1;

+  unsigned spare : 24;
+
  /* FIXME tuples: Eventually, we need to move this somewhere external to
     the trees.  */
  union tree_ann_d *ann;