Backend dataflow
- GCC's current backend dataflow, including live registers, is computed using an algorithm and in a fashion that is incredibly conservative. This causes pessimization of things like the global register allocator, and makes writing passes that change liveness not do what they should. An example of this is prespilling. In the current compiler, if you spill a register, it still ends up being marked live over the region in which it is spilled, because of how liveness is calculated. This project replaces the current dataflow in [gccsource:flow.c] that calculates live registers with the algorithm used in [gccsource:df.c] (which is the standard liveness algorithm). As a side effect, it replaces all users of global_live_at_start and global_live_at_end with the approriate df.c bitmaps, and has a df instance that lives over the entire backend. This produces a faster compiler, faster code, and enables passes like prespilling to work properly.
The GCC SC has approved a flag-day, wholesale replacement of dataflow, when the feature is ready. The requirements are:
- Bootstrapped and tested C, C++, Fortran and Java
- Regression tests showing no regressions with respect to mainline before the merge
- Bootstrapped and tested on: i686-pc-linux-gnu, x86_64-unknown-linux-gnu, powerpc-unknown-linux-gnu, ia64-unknown-linux-gnu
- Built and tested on arm-elf
- Tested with recent glibc, recent linux kernel, POOMA.
- SPECint and SPECfp performance within 3% of mainline.
- Compile time and memory consumption within 5% of mainline.
Personnel
- Kenneth Zadeck
- Daniel Berlin
- David Edelsohn
Delivery Date
- This optimization will be ready by 2006-12-31
Benefits
- GCC will generate better code and run faster, benefitting if-conversion, dce, dse, and auto-increment/decrement detection. This will also enable better optimization passes to be written, including better scheduling and register allocation.
Dependencies
- Renumbering of entry and exit blocks.
Modifications Required
- Global replacement of global_live_at_start and global_live_at_end with new bitmaps. Modification of df.c to calculate liveness properly in all cases.