[lto] Change the low-level representation of TYPE_ARG_TYPES.

[Kazu Hirata <kazu at codesourcery dot com>]

Hi,

Attached is a patch to change the low-level representation of
TYPE_ARG_TYPES.

Specifically, without this patch, TYPE_ARG_TYPES points to a linked
list made up with TREE_LIST with each TREE_LIST node pointing to a
type node.  With this patch, TYPE_ARG_TYPES points to a TREE_VEC
object with each of its elements pointing to a type node.

Notes
=====

void_vec_node
-------------

This patch adds void_vec_node, which is a TREE_VEC object containing
exactly one void_type_node.  This is the successor of void_list_node.

gcc_asserts
-----------

I've left a lot of gcc_asserts that I used during debugging.  I don't
know if it's a good idea to leave them.  Depending on feedback, I can
either eliminate or reduce them.

Language support
----------------

This patch has been tested with C, C++, and
Fortran.  It is known to break Java.  I don't know about Ada or
treelang.  The problem with Java is that it uses a flag bit in
TREE_LIST nodes that make up TYPE_ARG_TYPES.  We don't have a good way
of moving those bits to a TREE_VEC object.  Good news is that the Java
people are working to eliminate the bit.  See the following thread:

  http://gcc.gnu.org/ml/gcc/2006-07/msg00637.html

Backend support
---------------

This patch is known to break several backends that assume the internal
representation of TYPE_ARG_TYPES.  This patch does not affect the i386
port.


Future work
-----------

- Remove mentions of void_list_node.

- Fix Java once ARG_FINAL_P is gone.

- Fix non-i386 backends.

- Merge from mainline.  Currently, the ARM port doesn't build even
  without this patch.

Tested on x86_64-pc-linux-gnu with all default languages except Java.
OK to apply to the LTO branch?

Kazu Hirata

2006-08-15  Kazu Hirata  <kazu@codesourcery.com>

	Change the internal representation of TYPE_ARG_TYPES to use
	TREE_VEC.
	* c-common.c (c_common_nodes_and_builtins): Call
	build_void_vec_node.
	* c-common.h: Add a prototype for build_void_vec_node.
	* c-decl.c (diagnose_mismatched_decls): Assert that OLDTYPE is
	tcc_type.
	(grokdeclarator): Assert that declarator->u.arg_info->types is
	NULL_TREE, error_mark_node, or a TREE_VEC object.
	(get_parm_info): Use void_vec_node instead of void_list_node.
	(build_void_vec_node): New.
	* c-parser.c (c_parser_direct_declarator_inner): Assert that
	declarator->u.arg_info->types is NULL_TREE, error_mark_node,
	or a TREE_VEC object.
	* tree.c (num_parm_types, nth_parm_type, nth_parm_type_ptr,
	alloc_parm_types): Update to use TREE_VEC.
	(build_type_attribute_variant): Call type_hash_vec instead of
	type_hash_list.
	(type_hash_list): Rename to type_hash_vec.
	(type_hash_eq): Expect TREE_VEC instead of TREE_LIST.  Call
	type_vec_equal instead of type_list_equal.
	(type_vec_equal): New.
	(build_function_type): Assert that ARG_TYPES is either
	NULL_TREE or a TREE_VEC object.  Call type_hash_vec instead of
	type_hash_list.
	(build_method_type_directly): Construct a new parameter list
	with PTYPE at the beginning.  Use type_hash_vec instead of
	type_hash_list.
	* tree.h (tree_index): Add TI_VOID_VEC_NODE.
	(void_vec_node): New.
	Add a prototype for type_vec_equal.

2006-08-15  Kazu Hirata  <kazu@codesourcery.com>

	* call.c (build_op_delete_call): Use void_vec_node instead of
	void_list_node.
	* class.c (build_clone): Assert that SKIP is no greater than
	num_parm_types (PARM_TYPES).
	* decl.c (grokdeclarator): Use void_vec_node instaed of
	void_list_node.
	(build_void_vec_node): New.
	* except.c (do_end_catch): Use void_vec_node instaed of
	void_list_node.
	* pt.c (type_unification_real): Assert that XPARMS is either
	NULL_TREE or a TREE_VEC object.

Index: c-common.c
===================================================================
--- c-common.c	(revision 116159)
+++ c-common.c	(working copy)
@@ -3269,6 +3269,7 @@ c_common_nodes_and_builtins (void)
   TREE_TYPE (void_zero_node) = void_type_node;
 
   void_list_node = build_void_list_node ();
+  void_vec_node = build_void_vec_node ();
 
   /* Make a type to be the domain of a few array types
      whose domains don't really matter.
Index: c-common.h
===================================================================
--- c-common.h	(revision 116159)
+++ c-common.h	(working copy)
@@ -620,6 +620,7 @@ extern tree (*make_fname_decl) (tree, in
 extern tree identifier_global_value (tree);
 extern void record_builtin_type (enum rid, const char *, tree);
 extern tree build_void_list_node (void);
+extern tree build_void_vec_node (void);
 extern void start_fname_decls (void);
 extern void finish_fname_decls (void);
 extern const char *fname_as_string (int);
Index: c-decl.c
===================================================================
--- c-decl.c	(revision 116159)
+++ c-decl.c	(working copy)
@@ -1175,6 +1175,8 @@ diagnose_mismatched_decls (tree newdecl,
   if (oldtype == error_mark_node || newtype == error_mark_node)
     return false;
 
+  gcc_assert (TREE_CODE_CLASS (TREE_CODE (oldtype)) == tcc_type);
+
   /* Two different categories of symbol altogether.  This is an error
      unless OLDDECL is a builtin.  OLDDECL will be discarded in any case.  */
   if (TREE_CODE (olddecl) != TREE_CODE (newdecl))
@@ -4373,6 +4375,9 @@ grokdeclarator (const struct c_declarato
 
 	    /* Construct the function type and go to the next
 	       inner layer of declarator.  */
+	    gcc_assert (declarator->u.arg_info->types == NULL_TREE
+			|| declarator->u.arg_info->types == error_mark_node
+			|| TREE_CODE (declarator->u.arg_info->types) == TREE_VEC);
 	    arg_info = declarator->u.arg_info;
 	    arg_types = grokparms (arg_info, really_funcdef);
 
@@ -4991,7 +4996,7 @@ get_parm_info (bool ellipsis)
       if (ellipsis)
 	error ("%<void%> must be the only parameter");
 
-      arg_info->types = void_list_node;
+      arg_info->types = void_vec_node;
       return arg_info;
     }
 
@@ -6973,6 +6978,15 @@ build_void_list_node (void)
   return t;
 }
 
+/* Build the void_vec_node (void_type_node having been created).  */
+tree
+build_void_vec_node (void)
+{
+  tree t = make_tree_vec (1);
+  TREE_VEC_ELT (t, 0) = void_type_node;
+  return t;
+}
+
 /* Return a c_parm structure with the given SPECS, ATTRS and DECLARATOR.  */
 
 struct c_parm *
Index: c-parser.c
===================================================================
--- c-parser.c	(revision 116159)
+++ c-parser.c	(working copy)
@@ -2470,6 +2470,9 @@ c_parser_direct_declarator_inner (c_pars
       c_parser_consume_token (parser);
       attrs = c_parser_attributes (parser);
       args = c_parser_parms_declarator (parser, id_present, attrs);
+      gcc_assert (args->types == NULL_TREE
+		  || args->types == error_mark_node
+		  || TREE_CODE (args->types) == TREE_VEC);
       if (args == NULL)
 	return NULL;
       else
Index: cp/call.c
===================================================================
--- cp/call.c	(revision 116161)
+++ cp/call.c	(working copy)
@@ -4026,7 +4026,7 @@ build_op_delete_call (enum tree_code cod
   else
     {
       /* First try it without the size argument.  */
-      argtypes = void_list_node;
+      argtypes = void_vec_node;
       args = NULL_TREE;
     }
 
Index: cp/class.c
===================================================================
--- cp/class.c	(revision 116161)
+++ cp/class.c	(working copy)
@@ -3767,6 +3767,7 @@ build_clone (tree fn, tree name)
       if (DECL_HAS_VTT_PARM_P (fn)
 	  && ! DECL_NEEDS_VTT_PARM_P (clone))
 	skip++;
+      gcc_assert (skip <= num_parm_types (parmtypes));
       parmtypes = copy_type_arg_types_skip (parmtypes, skip);
        /* If this is subobject constructor or destructor, add the vtt
 	 parameter.  */
Index: cp/decl.c
===================================================================
--- cp/decl.c	(revision 116159)
+++ cp/decl.c	(working copy)
@@ -7612,7 +7612,7 @@ grokdeclarator (const cp_declarator *dec
 		     && nth_parm_type (arg_types, 0) == void_type_node))
 	      {
 		error ("destructors may not have parameters");
-		arg_types = void_list_node;
+		arg_types = void_vec_node;
 		parms = NULL_TREE;
 	      }
 
@@ -11539,6 +11539,15 @@ build_void_list_node (void)
   return t;
 }
 
+/* Build the void_list_node (void_type_node having been created).  */
+tree
+build_void_vec_node (void)
+{
+  tree t = make_tree_vec (1);
+  TREE_VEC_ELT (t, 0) = void_type_node;
+  return t;
+}
+
 bool
 cp_missing_noreturn_ok_p (tree decl)
 {
Index: cp/except.c
===================================================================
--- cp/except.c	(revision 116159)
+++ cp/except.c	(working copy)
@@ -228,7 +228,7 @@ do_end_catch (tree type)
   if (!get_global_value_if_present (fn, &fn))
     {
       /* Declare void __cxa_end_catch ().  */
-      fn = push_void_library_fn (fn, void_list_node);
+      fn = push_void_library_fn (fn, void_vec_node);
       /* This can throw if the destructor for the exception throws.  */
       TREE_NOTHROW (fn) = 0;
     }
Index: cp/pt.c
===================================================================
--- cp/pt.c	(revision 116161)
+++ cp/pt.c	(working copy)
@@ -9489,7 +9489,7 @@ type_unification_real (tree fn,
   int parms_len, args_len, arity;
 
   gcc_assert (TREE_CODE (tparms) == TREE_VEC);
-  gcc_assert (xparms == NULL_TREE || TREE_CODE (xparms) == TREE_LIST);
+  gcc_assert (xparms == NULL_TREE || TREE_CODE (xparms) == TREE_VEC);
   gcc_assert (ntparms > 0);
 
   if (fn)
Index: tree.c
===================================================================
--- tree.c	(revision 116159)
+++ tree.c	(working copy)
@@ -167,7 +167,7 @@ static void print_debug_expr_statistics 
 static void print_value_expr_statistics (void);
 static tree make_vector_type (tree, int, enum machine_mode);
 static int type_hash_marked_p (const void *);
-static unsigned int type_hash_list (tree, hashval_t);
+static unsigned int type_hash_vec (tree, hashval_t);
 static unsigned int attribute_hash_list (tree, hashval_t);
 
 tree global_trees[TI_MAX];
@@ -1588,7 +1588,9 @@ list_length (tree t)
 int
 num_parm_types (tree parmtypes)
 {
-  return list_length (parmtypes);
+  gcc_assert (parmtypes == NULL_TREE
+	      || TREE_CODE (parmtypes) == TREE_VEC);
+  return parmtypes ? TREE_VEC_LENGTH (parmtypes) : 0;
 }
 
 /* Return the Nth element of PARMTYPES, a list of parameter types.  */
@@ -1596,14 +1598,8 @@ num_parm_types (tree parmtypes)
 tree
 nth_parm_type (tree parmtypes, int n)
 {
-  while (n--)
-    {
-      gcc_assert (parmtypes);
-      parmtypes = TREE_CHAIN (parmtypes);
-    }
-
-  gcc_assert (parmtypes);
-  return TREE_VALUE (parmtypes);
+  gcc_assert (TREE_CODE (parmtypes) == TREE_VEC);
+  return TREE_VEC_ELT (parmtypes, n);
 }
 
 /* Return the pointer to the Nth element of PARMTYPES, a list of
@@ -1612,14 +1608,8 @@ nth_parm_type (tree parmtypes, int n)
 tree *
 nth_parm_type_ptr (tree parmtypes, int n)
 {
-  while (n--)
-    {
-      gcc_assert (parmtypes);
-      parmtypes = TREE_CHAIN (parmtypes);
-    }
-
-  gcc_assert (parmtypes);
-  return &(TREE_VALUE (parmtypes));
+  gcc_assert (TREE_CODE (parmtypes) == TREE_VEC);
+  return &TREE_VEC_ELT (parmtypes, n);
 }
 
 /* Allocate parameter types of length LEN.  */
@@ -1627,12 +1617,7 @@ nth_parm_type_ptr (tree parmtypes, int n
 tree
 alloc_parm_types (int len)
 {
-  tree t = NULL;
-
-  while (len--)
-    t = tree_cons (NULL, NULL, t);
-
-  return t;
+  return len ? make_tree_vec (len) : NULL_TREE;
 }
 
 /* Make a parameter list containing types given in V.  Return NULL if
@@ -3468,7 +3453,7 @@ build_type_attribute_variant (tree ttype
       switch (TREE_CODE (ntype))
 	{
 	case FUNCTION_TYPE:
-	  hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
+	  hashcode = type_hash_vec (TYPE_ARG_TYPES (ntype), hashcode);
 	  break;
 	case ARRAY_TYPE:
 	  hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
@@ -4149,14 +4134,18 @@ decl_value_expr_insert (tree from, tree 
    of the individual types.  */
 
 unsigned int
-type_hash_list (tree list, hashval_t hashcode)
+type_hash_vec (tree list, hashval_t hashcode)
 {
-  tree tail;
+  int len = num_parm_types (list);
+  int i;
 
-  for (tail = list; tail; tail = TREE_CHAIN (tail))
-    if (TREE_VALUE (tail) != error_mark_node)
-      hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
-					hashcode);
+  for (i = 0; i < len; i++)
+    {
+      tree type = nth_parm_type (list, i);
+      if (type != error_mark_node)
+	hashcode = iterative_hash_object (TYPE_HASH (type),
+					  hashcode);
+    }
 
   return hashcode;
 }
@@ -4243,11 +4232,11 @@ type_hash_eq (const void *va, const void
     case FUNCTION_TYPE:
       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
 	      || (TYPE_ARG_TYPES (a->type)
-		  && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
+		  && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_VEC
 		  && TYPE_ARG_TYPES (b->type)
-		  && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
-		  && type_list_equal (TYPE_ARG_TYPES (a->type),
-				      TYPE_ARG_TYPES (b->type))));
+		  && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_VEC
+		  && type_vec_equal (TYPE_ARG_TYPES (a->type),
+				     TYPE_ARG_TYPES (b->type))));
 
     default:
       return 0;
@@ -4458,6 +4447,30 @@ type_list_equal (tree l1, tree l2)
   return t1 == t2;
 }
 
+/* Given two vectors of types
+   (TREE_VEC with types in the TREE_VEC_ELT slots)
+   return 1 if the vectors contain the same types in the same order.  */
+
+int
+type_vec_equal (tree l1, tree l2)
+{
+  if (l1 == 0 && l2 == 0)
+    return 1;
+
+  if (l1 == 0 || l2 == 0)
+    return 0;
+
+  gcc_assert (TREE_CODE (l1) == TREE_VEC);
+  gcc_assert (TREE_CODE (l2) == TREE_VEC);
+
+  if (TREE_VEC_LENGTH (l1) != TREE_VEC_LENGTH (l2))
+    return 0;
+
+  return (0 == memcmp (&TREE_VEC_ELT (l1, 0),
+		       &TREE_VEC_ELT (l2, 0),
+		       sizeof (tree) * TREE_VEC_LENGTH (l1)));
+}
+
 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
    given by TYPE.  If the argument list accepts variable arguments,
    then this function counts only the ordinary arguments.  */
@@ -5271,11 +5284,13 @@ build_function_type (tree value_type, tr
   /* Make a node of the sort we want.  */
   t = make_node (FUNCTION_TYPE);
   TREE_TYPE (t) = value_type;
+  gcc_assert (arg_types == NULL_TREE
+	      || TREE_CODE (arg_types) == TREE_VEC);
   TYPE_ARG_TYPES (t) = arg_types;
 
   /* If we already have such a type, use the old one.  */
   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
-  hashcode = type_hash_list (arg_types, hashcode);
+  hashcode = type_hash_vec (arg_types, hashcode);
   t = type_hash_canon (hashcode, t);
 
   if (!COMPLETE_TYPE_P (t))
@@ -5337,13 +5352,25 @@ build_method_type_directly (tree basetyp
 
   /* The actual arglist for this function includes a "hidden" argument
      which is "this".  Put it into the list of argument types.  */
-  argtypes = tree_cons (NULL_TREE, ptype, argtypes);
+  gcc_assert (argtypes == NULL_TREE
+	      || TREE_CODE (argtypes) == TREE_VEC);
+  {
+    int len = num_parm_types (argtypes);
+    tree new_parm_types = alloc_parm_types (1 + len);
+    int i;
+
+    *(nth_parm_type_ptr (new_parm_types, 0)) = ptype;
+    for (i = 0; i < len; i++)
+      *(nth_parm_type_ptr (new_parm_types, 1 + i)) =
+	nth_parm_type (argtypes, i);
+    argtypes = new_parm_types;
+  }
   TYPE_ARG_TYPES (t) = argtypes;
 
   /* If we already have such a type, use the old one.  */
   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
   hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
-  hashcode = type_hash_list (argtypes, hashcode);
+  hashcode = type_hash_vec (argtypes, hashcode);
   t = type_hash_canon (hashcode, t);
 
   if (!COMPLETE_TYPE_P (t))
Index: tree.h
===================================================================
--- tree.h	(revision 116159)
+++ tree.h	(working copy)
@@ -3288,6 +3288,7 @@ enum tree_index
   TI_DFLOAT128_PTR_TYPE,
 
   TI_VOID_LIST_NODE,
+  TI_VOID_VEC_NODE,
 
   TI_MAIN_IDENTIFIER,
 
@@ -3373,6 +3374,7 @@ extern GTY(()) tree global_trees[TI_MAX]
    no TREE_CHAIN.  Language-independent code should not assume
    anything else about this node.  */
 #define void_list_node                  global_trees[TI_VOID_LIST_NODE]
+#define void_vec_node                   global_trees[TI_VOID_VEC_NODE]
 
 #define main_identifier_node		global_trees[TI_MAIN_IDENTIFIER]
 #define MAIN_NAME_P(NODE) (IDENTIFIER_NODE_CHECK (NODE) == main_identifier_node)
@@ -4340,6 +4342,7 @@ extern int simple_cst_equal (tree, tree)
 extern hashval_t iterative_hash_expr (tree, hashval_t);
 extern int compare_tree_int (tree, unsigned HOST_WIDE_INT);
 extern int type_list_equal (tree, tree);
+extern int type_vec_equal (tree, tree);
 extern int chain_member (tree, tree);
 extern tree type_hash_lookup (unsigned int, tree);
 extern void type_hash_add (unsigned int, tree);