Google Summer of Code 2010 Idea List
1. Advanced dead function elimination
Owner: Robert Hundt <robert.hundt@gmail.com>
Tentative Mentors: Robert Hundt <robert.hundt@gmail.com>
Description: Open64 DFE suffers from the fact that all virtual functions are address exposed via virtual tables. In this project, class hierarchy analysis and determination of the possible set of overrider functions for a class hierarchy needs to be performed. Based on this analysis, DFE can be made much sharper than it is today.
2. Implement inline heuristics to find out most profitable inline decisions
Owner: John Cavazos <cavazos@cis.udel.edu>
Tentative Mentors:John Cavazos <cavazos@cis.udel.edu>
Description: Description: Inlining can expand the optimization scope for many
optimizations and can also eliminate call overhead. However,
inlining decisions that are too aggressive can introduce register
pressure and can increase I-Cache pressure. This project seeks to
investigate the use of supervised machine learning techniques to
automatically construct good inlining heuristics.
3. Implement software transaction memory support for Open64
Owner: Wenguang Chen <cwg@tsinghua.edu.cn>
Tentative Mentors: Wenguang Chen <cwg@tsinghua.edu.cn>
Description: Transactional memory(TM) is an emerging paradigm for parallel computing. Software transactional memory(STM) can execute transactional memory applications on existing machines without hardware TM support. In this project, we will implement STM support based on current TM libraries such as TL2.
4. Enable debugging on IA-64 (or IA-32)
Owner: Handong Ye <yehandong@gmail.com>
Tentative Mentors: Handong Ye <yehandong@gmail.com>
Description: As far as I know, open64 doesn't support debugging very well. Maybe Pathscale already supported it for x86, but IA64 isn't supported yet. This project is good for a student since the framework of supporting debugging in open64 is already finished, and the student only needs to add extra support for the specific architecture and make it work. The major work for a new students consists of understanding the debugging support mechanism inside a compiler, understanding how gdb works, and how to debug gdb, and the biggest part of fixing bugs. Also the students needs to learn a lot about ABIs and DWARF. As a student project, the final target may be only supporting debugging for C language, and it should be able to debug all the C programs in SPEC2k and SPEC2k06.
5. Implement a practical unified data structure optimization framework for memory systems.
Owner: Wenguang Chen <cwg@tsinghua.edu.cn>
Tentative Mentors: Wenguang Chen <cwg@tsinghua.edu.cn>
Description: Hiding the latency of memory system is critical to achieving high performance on modern machines. In the past, lots of work have been done to improve locality of matrix accessing in loops, as well as prefetching of regular stride memory access. But completed data structures, for example, array of structures, pointer chasing structures etc, are not well handled. Recently, there are several researches addressing this issue. Sacral optimizations are proposed, such as field reordering, dead field removing, structure peeling, structure splitting etc. Preliminary results of those optimizations are promising. However, the work of those researches are either not practical, for example the target language is a tailored type-safe C. Or not easy to use, for example need huge memory trace. Or not well integrated. The work proposed here unifies all the optimizations above as well as readdressing and prefetching for complicated data structures with the help of auto memory pooling. The framework will be implemented on Open64 and has no pre-diction on its target language.
6. Implement a static program analysis tool based on Open64 compiler
Owner: Wenguang Chen <cwg@tsinghua.edu.cn>
Tentative Mentors: Wenguang Chen <cwg@tsinghua.edu.cn>
Description: Static program analysis became one of most powerful tools to identify the bugs in type-unsafe languages, such as c. Open64 compiler provide a very good infra-structure for inter-procedural analysis. in this work, we need to implement a static program analysis tool based on Open64's facilities.
7. A Documentation Project
Owner: Robert Hundt <robert.hundt@gmail.com>
Tentative Mentors: Robert Hundt <robert.hundt@gmail.com>
Description: Document phase ordering, illustrate optimization effects for each major phase with a running example, and perhaps specialized examples to make certain points. Show the IR before and after optimizations, and explain exactly what happened in the tranformations, or what didn't happen, which can be more interesting. This project is meant as a wonderful learning experience, and will benefit the greater community, as it finally documents the actual phase ordering in this compiler.
8. Improving the Open64 backend for GPUs
Owner: John Cavazos <cavazos@cis.udel.edu>
Tentative Mentors: John Cavazos <cavazos@cis.udel.edu>
Description: Nvidia is using an open64 port of its backend to generate code for several of their GPU cards. This port probably could be improved in several ways, for example in its register allocation or instruction scheduling. Also, several backend optimizations could be added that might significantly improve the performance of GPU code generated by the open64 backend.
9. Function/Loop specific-optimizations using machine learning
Owner: John Cavazos <cavazos@cis.udel.edu>
Tentative Mentors: John Cavazos <cavazos@cis.udel.edu>
Description: Selecting the best set of optimizations for a function or loop has been the focus of optimizing compiler research for decades. Determining the best optimization decisions, however is notoriously difficult. The project will drive the Open64 optimizing compiler to perform the best set of optimizations for functions and/or loops using machine learning based on the underlying target architecture.
10. Improve Dead Store Elimination
Owner: Fred Chow <fchow@pathscale.com>
Tentative Mentors: Fred Chow <fchow@pathscale.com>
Description: Improve the Dead Store Elimination in WOPT so it does effective optimization in the presence of aliasing. Potentially, extend the implementation to cover indirect stores.
11. Rewrite WHIRL simplifier using template
Owner: Fred Chow <fchow@pathscale.com>
Tentative Mentors: Fred Chow <fchow@pathscale.com>
Description: Rewrite the WHIRL simplifier using templates. Look for more peephole optimization opportunities and add them to the WHIRL simplifier.
12. Run-time versioning for pointers
Owner: Fred Chow <fchow@pathscale.com>
Tentative Mentors: Fred Chow <fchow@pathscale.com>
Description: Implement run-time versioning for pointers that cannot be de-aliased at compile time. When two pointers are determined at run-time to point to non-overlapping memory, then branch to the more optimized version of code.
13. A Flexible Compilation Driver for Open64 using Plugins
Owner:John Cavazos <cavazos@cis.udel.edu>
Tentative Mentors: John Cavazos <cavazos@cis.udel.edu>
Description: We seek to make the optimization driver more flexible by
integrating a plugin system similar to one currently being developed in
GCC. (http://libplugin.sourceforge.net) This will allow optimization
driver in Open64 to be more extensible allowing optimizations to be
performed in any order and allowing different optimization heuristics to
be easily integrated into the compiler.
14. Automatic dtrace probe insertion for fortran
Owner: Christopher Bergström <codestr0m@osunix.org>
Tentative mentors: Christopher Bergström <codestr0m@osunix.org>
Description: With even the simplest of example the conventions of Fortran can cause quite complex code to be generated. With so many varying runtime conditions it can be much more difficult to profile than c or c++ code. Sun studio recently introduce a feature that wraps subroutines in a module. The project will duplicate that feature by adding a -dtrace option to Open64 and take advantage of platforms where dtrace probes are available. (Mac OSX, FreeBSD and OpenSolaris) http://developers.sun.com/sunstudio/documentation/techart/fortran_dtrace.html
15. Better pragma support
Owner: Christopher Bergström <codestr0m@osunix.org>
Tentative mentors: Christopher Bergström <codestr0m@osunix.org>
Description: This project will extend the existing pragma support to add a fine grained compiler hint. Some of the goals will be to define explicit instructions such as : unroll this loop, this variable is only unsigned and or this value never exceeds N. With this arbitrary information and an additional cflag you should be able to force certain behaviors.
16. Clean up all makefiles
Owner: Christopher Bergström <codestr0m@osunix.org>
Tentative mentors: Christopher Bergström <codestr0m@osunix.org>
Description: The current makefile system and macros in the code make a lot of
assumptions that are highly linux specific. This assumption significantly increases the amount of code and number of files changed to port to a new OS. The current progress of the OpenSolaris port requires over 340 files to be changed. In addition these changes further complicate the macros and will increasingly become more difficult to maintain.
17. Out of bound check for array and pointer accesses
Owner: Xiaohua Zhang <xiaohua.zhang@hp.com>
Tentative mentors: Xiaohua Zhang <xiaohua.zhang@hp.com>
Description:
The +check=bounds option has sub-options to check array access, or dereference a pointer which may point to any heap object, local object, global object, or a non-bitfield member of a struct. It can check out of bounds error through common used libc string functions such as strcpy, strcat, memset… .
For instance, the check is able to find the OOB after the pointer arithmetic :
char buf[128];
char *s = buf +20;
for (int i=0; i< 110; i++) s[i] = 0;
It can also check structure field OOB access through a pointer:
struct A { int I; char buf[6]; int j; } a;
char *ptr = &a.buf[0];
strcpy(ptr, “abc”);
ptr = ptr + strlen(ptr);
strcat(ptr, “edfgh”);
Here is the description of the +check=bounds option:
+check=bounds[:array|pointer|<wbr>all|none]
The +check=bounds option enables checks for out-of-bounds references to array variables or to buffers through pointer access. The check is performed for each reference to an array element or pointer access. If a check fails, an error message is emitted and the program is aborted.
The +check=bounds option applies only to local and global array variables. It also applies to references to array fields of structs. It does not apply to arrays allocated dynamically using malloc or alloca.
You can specify one of the following +check=bounds suboptions:
· array - Enables check for out-of-bounds references to array variables.
· pointer - Enables check for out-of-bounds references to buffers through pointer access. The buffer could be a heap object, global variable, or local variable. This suboption also checks out-of-bounds access through common libc function calls such as strcpy, strcat, memset, and so on. The check can create significant run-time performance overhead. See +check=uninit and +check=malloc for their interaction with this option.
· all - Enables out-of-bounds checks for both arrays and pointers. This is equal to +check=bounds:array +check=bounds:pointer.
· none - Disables out-of-bounds checks.
· +check=bounds (with no suboption) - Is equal to +check=bounds:array. This may change in the future to also include +check=bounds:pointer.
When +check=all is specified, it enables +check=bounds:array only. To enable the pointer out-of-bounds check, +check=bounds:pointer must be specified explicitly.
You can combine +check=bounds:[pointer|all] with all other +check options, except for +check=globals (which would be ignored in this case).
Also see the +check=malloc and the +check=stack options for related runtime checks for heap and stack objects.
18. Uninitialized memory read check
Owner: Xiaohua Zhang <xiaohua.zhang@hp.com>
Tentative mentors: Xiaohua Zhang <xiaohua.zhang@hp.com>
Description:
There are two kind of uninit check, the first one check can check uninitialized local variable read; the second one can check uninitialized heap object, shared memory object read through a pointer, which requires +check=bounds:pointer is turned on.
For example,
int *p = (int *)malloc(4*sizeof(int));
int I = p[2];
The +check=uninit option checks for a use of a stack variable before it is defined. If such a use is detected, an error message is emitted and the program is aborted. The check is done by adding an internal flag variable to track the definition and use of user variables.
If the +check=bounds:pointer is on, +check=uninit will check pointer access for uninitialized memory read (UMR). To enable checking, the runtime system will initialize the heap objects and stack variables with a special pattern. If the pointer accesses an area containing the specified pattern for the specified length, then it assumes the read is UMR. To minimize UMR false positives, the user may change the special pattern and number of bytes to check by using RTC_UMR environment variable:
RTC_UMR=[INIT=0xnn][:CHECK_<wbr>SIZE=sz]
where:
· INIT specifies the char type value used to initialize heap/local objects. The default pattern is 0xDE.
· CHECK_SIZE specifies the minimum number of bytes used to check for UMR. The default number is 2.
19. Implement code size reduction techniques
Owner: Kannan Narayanan <narayanan.kannan@gmail.com>
Tentative mentors: Kannan Narayanan <narayanan.kannan@gmail.com>
Description: For embedded processors, application size is critical. Open64 has traditionally been a highly optimizing compiler with some support for code size optimizations (-Os option). This project will attempt to improve this aspect of Open64 compiler infrastructure and support more optimizations. Examples include Whole Function Abstraction, Duplicate Code Elimination, Loop recognition from straight line code, better unrolling and inlining heuristics through Whole Program Analysis. Further, in embedded applications, there is usually a target code size beyond which further optimizations are useless. The optimization to be implemented has to be cognizant of the impact on the global code size and hence the need for intra and inter-procedural analysis. Impact of reduction in code size on performance may be studied.
20. Implement support for debugging optimized code
Owner: Kannan Narayanan <narayanan.kannan@gmail.com>
Tentative mentors: Kannan Narayanan <narayanan.kannan@gmail.com>
Description: A pre-requisite for this project is the improvement of Open64's support for de-optimized code debugging (-O0 -g) : assuming this can be improved to the level of GCC. For embedded applications, debugging optimized code support is vital for the following reason. Typically, users develop application in 2 steps: a) develop functionality b) optimize and possibly iterate this process. In step 1), functionality is verified against a MATLAB or similar model. During this step, users also have to translate the program written for a general purpose simulation environment to the target processor with strict performance, size, power considerations. Sometimes, these objectives *cannot* be reached with de-optimized code. Many times, problems show up only with optimized code. The normal compiler bug triaging process breaks down because the code does not fit any more or the application fails to meet its performance deadlines. This project will attempt to upgrade the Open64 compiler infrastructure to state of the art (example GCC) by using extensions provided in DWARF. The challenges include tracking current value of variables, source line after inlining. Given the rich set of optimizations in Open64, the problem should be solved in small steps.
21. Windows port of Open64
Owner: Rayson Ho <raysonlogin(at)yahoo.com>
Tentative Mentors: Rayson Ho <raysonlogin(at)yahoo.com>
Description: Nvidia did a windows port of the pieces that it uses (cfront end, inliner, wopt, cg). They uses mingw to build on windows, so not a native windows. STM and Tensilica have also done some work on a windows port. Getting everything to build well on windows would be a nice project for GSoC, it
can be broken into multiple stages:
1) Fix compilation errors so that Open64 can be built on Windows (with gcc or Visual Studio).
2) ABI part -- the calling convention is different, so there will be some work needed here.
3) IPA part -- Inter Procedure Analysis.
4) Debug -- MS has its own debug data format, and it can be quite a lot of work for Open64 to support that. As we now know that some work has been done before to build Open64 on Windows, we should at least get "hello world" working in the middle of the summer...
22. OpenMP3.0 test suite for Open64
Owner: wenguang chen <cwg(at)tsinghua.edu.cn>
Tentative Mentors:wenguang chen <cwg(at)tsinghua.edu.cn>
Description:
23.
Owner: Coakley, David <david.coakley(at)amd.com>
Tentative Mentors: Coakley, David <david.coakley(at)amd.com>
Description: 1. Make Open64 code generation and IPA portable to non-ELF object file formats and non-Linux systems. 2. Introduce a portable build system and host system library (similar to “16. Clean up all makefiles” proposed in 2009).