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


This topic: Main > CS255Part3
Topic revision: r1 - 2008-02-17 - XiaomingGu
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback