In this part you need to implement value numbering in your compiler. As you know, value
numbering can be carried out in different scopes: basic block, extended basic block, or
dominator block. In this assignment, you are required to implement basic-block value
numbering. However, optimizing at a larger scope may help you in your final competition. It
is up to you to decide which algorithm you implement.
The public test programs use only basic arithmetic and logical operations. Your compiler is
required only to correctly optimize these programs. It does not need to support pointer
operations except to allow the taking-address operation in scanf. The absence of dynamic
data allocation and pointer dereference removes most of the aliasing concerns and gives you
more room for optimization. In addition, if you are taking CS255 instead of CS455, your
compiler does not need to support or optimize array operations.
Your compiler may fail if a program contains operations it does not support. It should fail
gracefully: it should check for cases it does not support, and when it finds such cases,
output a descriptive error and exit. Under no circumstances it may generate incorrect code
(except in Part 2). Your compiler will be evaluated in hidden test cases, and an
incorrectly optimized program would count against you more so than a failure in compilation.
In this and later projects, instrumentation should always be the last pass. Do not optimize
on the instrumented program.
In this and later projects, do not use any Gcc optimization passes and make sure you have
the
update posted earlier. You can use Gcc routines for inspecting and
changing gimple statements and their control flow, as you did in the first two projects.
You need to write your own algorithm iterating through program statements, maintaining value
tables, and removing redundant operations, as well as checking for unsupported operations.
You may use vector, hash table, search tree, and other generic data structures in Gcc. You
may also use the analysis in Gcc including the dominator information. For this project you
may not use the SSA information.
You do not have to use Gcc code. If you do, you should document precisely the functions you
use and the purpose of using them. Talk to the TA or the instructor if you are not sure.
If you find useful Gcc routines, please post them to the class discussion page. The
project is a collaborative contest. You collaborate to understand and make the best use of
existing code. You compete in the design and implementation of the optimization algorithms
you add to the compiler.
--
XiaomingGu - 17 Feb 2008