RFC - Alternatives to gengtype

[Diego Novillo <dnovillo at google dot com>]

As we continue adding new C++ features in the compiler, gengtype
is becoming an increasing source of pain.  In this proposal, we
want to explore different approaches to GC that we could
implement.

At this point, we are trying to reach consensus on the general
direction that we should take.  Given how intertwined GC and PCH
are, the choices we make for one affect the other.

We don't have a strong preference at the moment, but we are
leaning in these directions:

Diego:
	Get rid of GC completely.  Move into pool allocation.
	If we continue to use GC, then either use boehm-gc or
	continue use the precise allocator, but with user
	generated  marking.

Lawrence:
	Get rid of GC completely.  Move into pool allocation.
	If we continue to use GC, either move to user-generated
	marking or implement the GTY attributes in cc1plus (read
	below).  For PCH, used a fixed address where all the
	PCH-able data would go, as this would represent less work
	than implementing streamable types.



Gengtype is a poor C parser. It is a long way from handling all
of the C++ constructs what are used by the C++ standard library.
We have a few potential solutions. Solution: Stick with Gengtype


As gengtype currently does not handle what we need, something
must change.


=== Approach: Limit the Language Used

We could avoid the problem by limiting the language we use to
near that which gengtype currently understands.  This approach
has significant consequences. It will make the standard library
incompatible with GTY.  It will prevent the use of common idioms,
such as iterators, within GTY types.  These limitations are
significant and not desirable. Approach: Upgrade Gengtype


Full C++ support would essentially require building a new C++
parser.


=== Approach: Both Limit and Upgrade

We can try upgrading gengtype to handle a more extensive subset
of C++, without trying to handle the full language. See Thoughts
on Gengtype and Single Inheritance. Taking this approach would
likely mean we would be unable to use the C++ standard library
within GCC.


=== Approach: Move GTY to cc1plus.

Instead of a separate weak parser, we would make cc1plus
understand GTY attributes.  The compiler would emit IL in the
object files instead of generating source.

This solution would require a first boot stage that did not
support PCH, because we cannot rely on the seed compiler
supporting GTY.  We would probably need to use the Boehm
collector during the first stage as well.

Because the first stage would be fundamentally different from the
second stage, we may need to add an additional pass for correct
object file comparisons.


=== Approach: Do GTY manually

In this approach we would be converting GTY from a declarative
form into a procedural one using the C++ type system and
manually-implemented structure field handlers.  At the highest
level, this roughly means that all the structures using GTY(())
markers will start using GTY((user)).

The marking code dealing with the semantics of the marked data
structure is co-located with the data structure.  When GC
problems occur, this simplifies debugging.  The user is no longer
faced with a mass of auto generated code that is unfamiliar and
hard to trace. The code to implement is straightforward.  For
every pointer field in the given instance pointer, a single
"mark" function needs to be called.

Common facilities to mark arrays will be provided via a base GC
class. No generated header files to #include at the end of the
source file. No new dependencies to add to the Makefile. No need
to parse C++.

The problem with this approach is that the declarative approach
puts the field additions and the GTY annotations in the same
place, as opposed to in separate code. While it is possible to
use standard library containers with GC pointers in them, we
would not be able to write these containers to PCH images.


=== Approach: Get rid of GTY

This approach engenders more choices.  The pre-compiled header
implementation uses gengtype, so this approach is not viable
unless we have an alternate implementation for PCH. We will also
need another approach to memory management. 


=== Approach: Permanent Addresses for PCH

Create an alternate implementation of PCH using mmap and a region
allocator. The essential difference is that we need to allocate
the data structures in their final location, rather than the
current approach of allocating someplace and then walking the
trees to move them to the desired and fixed mmap address. Because
this implementation would not do a final copy, it may leave
allocation holes in the memory region.  To reduce this cost, we
can zero all unallocated memory in the region and then compress
it before writing the PCH file.  Compressing the file has already
proven effective on existing PCH files, and so the compression
work would not be a problem.

We still need to indicate which objects go into PCH memory.  For
compiler-specific types that always go into PCH memory, we can
create a base class that provides class-member operators new and
delete. These would allocate from the region allocator.  For C++
standard library structures parameterized by allocators, we could
provide an allocator that does the same thing.  For other types,
we would require more explicit allocation and deallocation.


=== Approach: Manual PCH using streamable types

Every type knows how to build a bytecode vector for its contents.
A stream manager asks all the instances to build their bytecode
vectors and writes them to disk. This build on the streaming
support implemented for LTO.


=== Approach: Use the Boehm collector.

The general approach is to define allocation and deallocation
functions to the Boehm collector that handle memory within the
PCH range.  We would also provide a class to register global
roots at the point of declaration of those roots. We would likely
configure the collector to collect only on command, not
automatically.  Laurynas says previous efforts showed
that the peak memory usage was slightly higher that with the
existing collectors due to Boehm's conservativeness. The run time
was comparable.


=== Approach: Move RTL back to obstacks.

Laurynas started this in 2011.  I'm not sure what the status of
this is.  Laurynas?


=== Approach: Replace GC with smart pointers.

We need to identify all pointers that result in circular
structures and not use smart pointers for them.  We would
probably still have some circular structures resulting from the
compilation of mutually referencing structs.


So, the options seem numerous.  Before we start running in any
particular direction, we'd like to get a sense of what folks
think would be the best approach long term.

In this, we want to stress that we would rather shoot for
long-term viability/maintainability, even if it means
short/medium term pain.  We are thinking of targetting 4.9 or
even 5.0.

In the meantime, we will need to apply some more duct tape and
string to keep gengtype puttering along.


Thanks.