The internal data structures used to represent GIMPLE are not well suited for performing link-time or run-time optimizations. The representation takes up quite a bit of memory, it depends on global and static internal state built at random phases from the parser down, and it requires front-end involvement to disambiguate some language-dependent information and rules.
This makes it almost impossible to combine several compilation units in memory, re-create a compilation unit from a stream and generally perform many of the transformations required for link-time and/or run-time optimizations. The goal of this cleanup project is to prepare the internal data structures used by GIMPLE so that we can later implement link-time optimizations as proposed in http://gcc.gnu.org/ml/gcc/2005-11/msg00735.html. Additionally, this would also allow GCC to integrate a dynamic compilation system such as LLVM to provide JIT capabilities for all languages.
The common thread to these cleanups is going to be memory savings, and to a certain extent compile time improvements. New optimization opportunities and improved analysis are outside the scope of this project. This task list is by no means complete. I have added a few items from other TODO lists in other areas of this Wiki so that we can keep related work in the same place. The work will likely encompass more than one development branch.
Some of the projects listed in the speedup areas page are relevant for this plan. In particular, the 'Trees' section.
The virtual SSA representation is very bloated, particularly in the presence of imprecise alias information. This work attempts to compact that information without risking precision. This is currently underway and expected to be integrated by the next stage 1, to be included in GCC 4.3. More details at http://gcc.gnu.org/ml/gcc/2006-02/msg00620.html
New data structures for representing GIMPLE statements. The current IL uses a central data structure called 'tree'. Every IL node has this type, which results in nodes with unused fields. The basic idea is to analyze the tree codes used in GIMPLE and create smaller data structures to represent them.
This will require some exploratory work and details are a bit vague, but some early discussion and implementation strategies were discussed in http://gcc.gnu.org/ml/gcc/2006-02/msg00622.html.
Introduce the notion of GIMPLE statements and GIMPLE expressions
- Personnel: Aldy Hernandez
- Create a basic 1 or 2 word structure that's basically a code and some bitfields. GIMPLE statements and expressions inherit from this structure.
- Introduce the notion of GIMPLE statements and GIMPLE expressions. Each has attributes that the other does not need. A statement will have location information and no type, while an expression will have type and no location information.
- GIMPLE statements have an array of operands, location info (including basic block) and an ID. Each operand will be a GIMPLE expression.
- GIMPLE expressions have 0 or more operands and a type. SSA names are GIMPLE expressions with 0 operands.
Shrink compiler temporaries
Convert compiler temporaries into smaller DECLs and/or emit them directly as SSA names or just indices into a temporary table. http://gcc.gnu.org/ml/gcc/2005-12/msg00632.html, http://gcc.gnu.org/ml/gcc/2006-01/msg00510.html
Move annotations to hash tables or make them part of the IL structures.
Remove on-the-side data structures
A key property of a streamable IL is to be able to recover full compilation state from an isolated file. This means that the IL must have all the information required to create final code out of it. We currently keep some on-the-side data structures and/or global variables that are created at various points starting at the parser.
A litmus test for this would be a pass that can read a program in GIMPLE form from a file and compile it to completion. This will force us to commit to a completely explicit representation: variables, types, exception handling, wrap-around semantics for arithmetic, etc.
It's not clear yet whether we will want to make GIMPLE itself streamable for the purposes of optimization. Perhaps we will end up using some other variant like the GVM bytecodes proposed in LTO or convert into the bytecodes used by LLVM. But I think it should be useful if we could read/write GIMPLE for developing test cases and general debugging of the compiler itself.
A possibly complicating factor is that existing ports can use on the side data structures for things like constant pool handling (ARM) and pic code generation (Darwin). These might be generated late enough to not be a problem specifically, but other ports might squirrel away data ealier and cause problems. For PCH, for example, there was a bug once about alias sets that the rs6000 backend defines early on, which were not written to the PCH. There may be other, similar issues that we will have to deal with for LTO...
Separate the frontends from the middle-end
To be able to stream the IL, maybe even in a language independent form, the dependency on frontend provided information in the middle-end has to be removed. Tasks in this area include:
- Removing language hooks.
- Defining a proper middle-end type system.
- A middle-end symbol table.
- A cleanup/integration with the cgraph infrastructure.
- Removing some global operation modes and making them flags on operations instead. E.g., -fwrapv.