EE 599 - Compiler Code Generation And Optimization

Preliminary ABET-style Syllabus

EE 599 003 - Compiler Code Generation and Optimization: 3 Credits

Compilers are the software tools that translate high-level language constructs into something that can execute the desired operations. Normally, one thinks of compilers as straightforwardly translating programs written in C or Fortran into assembly language code for something like a single simple processor. However, state-of-the-art compilers perform a wide range of optimizations, including various transformations that support parallel computer hardware ranging from simple pipleined processors to massively-parallel supercomputers. These same basic technologies also are used to create hardware, most often by translating hardware description language constructs into optimized digital circuits implemented using programmable logic.

This course presents the concepts needed to understand, design, and implement production quality compiler "back-ends" that target a wide range of computer architectures and various forms of programmable logic. Flow analysis and concurrency detection, as well as optimizations and loop and irregular code parallelizations, are covered in detail.

Grading will be based on two in-class exams and a semester-long project involving construction of an optimizing, parallelizing, back-end for a simple compiler which will be suppiled to the students as full C source code. Modifying the compiler for the project will require some C programming. The project will be submitted online as source code and a short write-up; each student also will orally present their project in class and as a poster at ECE Day (unless exempted by the instructor).

The project and exam grades will be combined for your course grade such that (1) the project grade counts about as much as your exam grade and (2) your course grade is not more than one step above the lower of your project and exam grades.

TEXTBOOK:

None required - Course notes

COORDINATOR:

Dr. Henry G. Dietz, Professor

GOALS:

To give students a better understanding of the intimate relationship between compiler techniques and computer architecture.

PREREQUISITE:

Undergraduate standing and fluency in C or a similar programming language

TOPICS:

1. Introduction
   • An overview of compilation
   • An overview of parallel architectures
2. Basic code generation and optimization
   • Forward reference resolution
   • Evaluation modes
   • Library/target model tradeoffs
   • Peephole optimizations
   • Constant folding
   • Commutativity, Sethi-Ullman numbering
3. "Basic Block" techniques
   • Value number analysis
   • Optimization/parallelization transformations
4. "Global" techniques
   • Linear Nested Regions, structured language simplifications
   • Iterative set-based analysis
   • The cost of blocks, classical optimizations
   • Loop analysis and transformations
   • Transformations of irregular code, interprocedural analysis
5. Project specifics and presentations

OUTCOMES:

1. Understand the basic principles and techniques of compiler code generation for a wide range of computer architectures and programmable logic devices.
2. Understand and be able to implement a variety of simple optimizations (e.g., peephole transformations) that do not require flow analysis.
3. Understand and be able to implement Basic Block flow analysis, especially value numbering.
4. Understand and be able to implement flow analysis based Basic Block optimizations including common subexpression elimination with value propagation and code scheduling.
5. Understand and be able to implement at least one type of Global flow analysis.
6. Understand and be able to implement flow analysis based Global optimizations including various types of loop transformations.

COMPUTER USAGE:

Students will perform open-ended experiments implementing analysis and optimization extensions to a simple compiler.

UNDERGRADUATE VS GRADUATE CONTENT:

Graduate students taking this course will be expected to include more, and more sophisticated, analysis and optimizations in their project than will be required for undergraduates. There are no other significant differences in workload or grading.

DESIGN CONTENT:

Students will design, implement, and test Basic Block and Global analysis and optimization transformations. There are many choices as to which analysis methods should be used, which transformations implemented, and how these abilities should be implemented. The target architecture will be a simple parallel system incorporating at least two different types of parallelism that the project compiler must target.

CLASS SCHEDULE:

Lecture 3 hours per week.

Engineering Science: 1 Credit (33%)

Engineering Design: 2 Credits (67%)

• An ability to apply knowledge of mathematics, science, and engineering.
• An ability to design and conduct experiments, as well as to analyze and interpret data.
• An ability to design a system, component, or process to meet desired needs.
• An ability to identify, formulate, and solve engineering problems.
• An ability to use the techniques, skills, and modern engineering tools necessary for engineering practice.

PREPARED BY: Henry G. Dietz DATE: January 14, 2005