Oracular Optimization
- GCC currently uses a number of techniques for generating optimal code, including peephole optimization, instruction scheduling, loop unrolling, and other similar techniques. All of these techniques are known to suffer from the fact that they do not always generate truly optimal code; they are just heuristics. We plan to improve GCC by generating perfectly optimal code for all input programs by taking advantag of a simple technique explained in every undergraduate automata theory course: using an oracle. By using an oracle that knows the right answer, we can generate much better code. There will be a small penalty in compilation time, since the oracle sometimes takes a long time to answer, so this optimization will only be enabled with -Ooo (Optimize with Oracular Optimization).
Personnel
- A. Turing and The Machines
- A. Church and The Lambdas
Delivery Date
- This optimization will be ready by 2006-04-01.
Benefits
- GCC will generate perfectly optimal code.
Dependencies
Recursively, on SampleProjectTemplate.
Modifications Required
- In the first phase, oracular optimization will only be used for instruction scheduling. So, we will be replacing haifa-sched.c. We will keep the same entry points, but just call the oracle from inside the scheduler. The oracular optimization code requires use of Object-Oriented Oracle Programming, so the new code will be written in the Practial OOOP language (POOOP). Therefore, we will have to update the build system to use the user's POOOP compiler to build the new scheduler file. Also, since the scheduling macros in the machine description will no longer be needed, we will remove them.