[PATCH] Canonical types (1/3)

[Doug Gregor]

This patch introduces canonical types into GCC, which allow us to
compare two types very efficiently and results in an overall
compile-time performance improvement. I have been seeing 3-5%
improvements in compile time on the G++ and libstdc++ test suites,
5-10% on template-heavy (but realistic) code in Boost, and up to 85%
improvement for extremely template-heavy metaprogramming.

Canonical types also make the GCC type system more regular.  In GCC,
we often create many different variants of the same type that are all
considered equivalent (e.g., comptypes returns true for both). For
instance, "int" and a typedef of "int" will have separate INTEGER_TYPE
nodes, but these will compare equal when we're performing type
checking. Unfortunately, we need to perform a deep comparison,
checking cv-qualifiers, attributes, precision, alignment,
etc. Canonical types add a new field to every type which points to a
representative of the equivalent class of types: all types in GCC that
are equivalent will point to the same canonical type, so we can use
the canonical types to quickly check type equivalence. Canonical types
were discussed in this thread:

  http://gcc.gnu.org/ml/gcc/2006-11/msg00192.html

This patch adds two new fields to every _TYPE, and maintains those
fields throughout the C, C++, Objective-C and Objective-C++ front
ends. The first field is TYPE_CANONICAL, which is the canonical type
of each type. The second field is TYPE_STRUCTURAL_EQUALITY: when this
bit is set, it means that TYPE_CANONICAL cannot be used reliably for
type equality checking, so we must perform structural tests. We use
TYPE_STRUCTURAL_EQUALITY when we create a new type node for which we
can't find the canonical type. Over time, we should work to eliminate
TYPE_STRUCTURAL_EQUALITY, because each case that requires it also
means that we're wasting memory for duplicated type nodes and wasting
cycles performing deep comparisons.

There is some danger in introducing canonical types: if we fail to
canonicalize properly, types won't compare equal when they should, and
we'll break code. To mitigate this problem, I have added a flags
-f(no-)check-canonical-types. When enabled, GCC will check the
canonical types against the structural types; where they differ, it
will print a warning and use the structural information. When
disabled, we only use canonical types... and get better compile-time
performance. Canonical type checking is disabled by default for normal
builds, enabled by default when --enable-checking is present. Note,
however, that this flag is temporary: after a major release or two,
when we're sure that we have our canonical type system, we can
eliminate it.

Bootstrapped C, C++, Objective-C, Objective-C++, Java on
i686-pc-linux-gnu. Tested C, C++, Objective-C, Objective-C++, and
libstdc++ test suites; no new regressions. I've spot-checked some
template-heavy Boost libraries; no regressions there, either.

This is part one of three, containing changes to the parts of the
compiler that are shared amount the C family of languages.

Okay for mainline?

  Cheers,
  Doug Gregor
  Open Systems Lab @ Indiana University

2006-11-28  Douglas Gregor  <doug.gregor@gmail.com>

	* builtins.c (std_gimplify_va_arg_expr): Keep track of the
	canonical type when building a variant with a different alignment.
	* c-common.c (flag_check_canonical_types): New.
	(c_common_nodes_and_builtins): Since variants of void_type_node
	get built before it is given a name, we need to give those
	variants the name, too.
	(handle_packed_attribute): When building the type variant, set the
	canonical type appropriately.
	(handle_unused_attribute): When building the type variant, set the
	canonical type appropriately.
	(handle_aligned_attribute): Ditto.
	(handle_deprecated_attribute): Ditto.
	(complete_array_type): We need to work with the canonical main
	type of the array, from which we will build the qualified version.
	* c-common.h (flag_check_canonical_types): New.
	* c.opt (fcheck-canonical-types): New.
	* c-opts.c (c_common_handle_option): Handle
	-f(no-)check-canonical-types.
	* print-tree.c (print_node): Display canonical type information
	for each type.
	* stor-layout.c (layout_type): When we don't know the
	alignment of a type for which we're building an array, we end up
	guessing wrong, so make the type require structural equality.
	* tree.c (make_node_stat): When we build a new type, it is its
	own canonical type.
	(build_type_attribute_qual_variant): When building an attribute
	variant, its canonical type is the non-attribute variant. However,
	if the attributes are target-dependent and they differ, we need to
	use structural equality checks for this type.
	(build_qualified_type): Ditto.
	(build_distinct_type_copy): When building a distinct type from
	another type, the new type is its own canonical type.
	(build_pointer_type_for_mode): When building a pointer type, also
	build a canonical type pointer.
	(build_reference_type_for_mode): When building a reference type,
	also build a canonical type reference.
	(build_index_type): When we can't hash an index type (e.g.,
	because its maximum value is negative), the index type requires
	structural equality tests.
	(build_array_type): Build the canonical form of an array type.
	(build_function_type): Function types require structural equality,
	because they contain default arguments, attributes, etc.
	(build_method_type_directly): Ditto for method types.
	(build_offset_type): Build the canonical offset type.
	(build_complex_type): Build the canonical vector type.
	(make_vector_type): Build the canonical vector type.
	(build_common_tree_nodes_2): Set the canonical type of
	va_list_type_node appropriately.
	* tree.h (TYPE_CANONICAL): New.
	(TYPE_STRUCTURAL_EQUALITY): New.
	(struct tree_type): Added structural_equality, unused_bits,
	canonical fields.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: canonical-types-gcc.patch
Type: text/x-patch
Size: 15390 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20061128/8c55fa4d/attachment.bin>