Spring 2021 EE599-201/EE699-202: Optimizing Compilers
TR 11:00-12:15 live via Zoom

This is the official home page for both the undregrad (EE599-201) and grad (EE699-202) Optimizing Compilers course, which will be taught together and treated as one course, but with somewhat different project requirements. There is only one section, which be meeting live online via Zoom TR 11:00-12:15. At this time, no in-person meetings are scheduled because of the pandemic; however, there may be opportunities for optional in-person activities, especially later in the semester. The Zoom meeting address and password is announced on Canvas and sent to all students via the email address officially on record with UK. The course Canvas site will be used in combination with this website for course materials and announcements, and you are expected to use both.

Although a recording of each lecture will be posted shortly after each class, students are strongly encouraged to actively participate in the online lectures live. Interaction via chat and questions is strongly encouraged. We will often seek live student feedback during a lecture using the yes/no voting mechanism, polls, or even brief online quizes or questionaires. Professor Dietz will have virtual office hours, and you should feel free to email with any suggestions and/or questions, but please put "OC" in the Subject line.

You know how to write programs in C and specify hardware in Verilog? This course is about how to build software tools -- Optimizing Compilers -- that can shape the mud of assembly language instructions and configurable hardware into useful software/hardware structures that efficiently implement your high-level designs. Optimizing compilers rarely generate truly optimal implementations; understanding what they can and cannot do enables you to be a much more effective engineer, focusing effort where it will pay off and avoiding unpleasant surprises late in the product development cycle.

Useful Links

Links will be posted here incrementally as the course progresses.

• The preliminary syllabus (still subject to change)
• Introductory slides (PDF) for the first class meeting
• Reference materials
• Introduction To Compilers And Translation Engineering, the undergrad compiler course notes to get us started
• Various things will be in the WORK directory here: dfa.c, BB.tgz
• The Basic Block Optimizer assignment has you modifying the BB.tgz code to implement a variety of peephole, constant folding, and forward-flow basic block optimizations. Don't try to do everything at once. Start with the peephole mods (local special-case optimizations) to binop. After testing those, add the constant folding. Finally, add the common subexpression elimination (CSE) support, which includes the value propagation and availability checks.
• The Basic Block Death assignment is now posted. This is the basic backward flow problem.
• The Basic Block Parallelizer assignment is now posted. It includes a sample solution to the dead code elimination assignment.
• The Control Flow Optimization assignment is now posted. Don't worry; it's just a minimal implementation of Code Straightening.
• The Hardly Software is now posted. It's due before the final exam timeslot -- which will not have an exam, but will be more like a final regular class meeting including review of a project solution.

What's in this course?

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 langauges like C into assembly language code. However, optimizing compilers perform sophisticated analysis and a wide range of complex transformations to generate an efficient implementation of a program. The program may be written in a language like C, or it may be what the author considered to be a hardware design expressed in a language like Verilog. The implementation created by the compiler might be code for a computer supporting various types of parallel execution, gate-level circuits or FPGA configurations, or even a co-designed combination of sopafter and hardware accelerators.

This course presents the concepts needed to understand, design, and implement optimizing compiler "back-ends" that target a variety of computer architectures and digital logic circuitry. You'll not only learn how these things work, but you'll actually extend a simple compiler (provided to you as full C source code) to perform some of the analysis methods and transformations discussed. Topics covered include:

1. Introduction
2. Basic code generation and optimization
   • Target model issues, superoptimizers
   • A simple assembler with forward reference resolution
   • A simple compiler
   • Peephole optimizations, constant folding, commutativity and Sethi-Ullman numbering
3. Analysis and transformation
   • Value number analysis, linear nested regions, iterative set-based analysis, and Static Single Assignment (SSA)
   • Classical optimizations including Common Subexpression Elimination (CSE) with value forwarding
   • Parallelization transformations including parallel and pipelined code scheduling
   • Loop analysis and transformations
   • Interprocedural analysis and recursion transformations
4. Silicon compilation and high-level logic synthesis
   • Transformation from word-level to bit-level
   • Bit-level optimization and transformation
   • Binary Decision Diagrams (BDDs) and normal form transformations
   • State machine transformations
5. Hardware acceleration and hardware/software codesign

Who should take this course?

This course is intended for undergraduate (EE599-201) and graduate (EE699-201) students in computer engineering, EE, or CS. The course is particularly well suited for students who have taken EE/CS/CPE480 and a conventional (parsing theory emphasis) compilers course, but only EE/CS/CPE380 and some exposure to programming in C/C++ are required.

Course administrivia

If there is sufficient enrollment, the course will meet 3 hours/week in a mostly conventional lecture format via zoom; if enrollment is smaller, the class will be run in a partially flipped structure with hands-on coding during meeting periods. There is no scheduled lab meeting, and students are encouraged to use their own computers for the projects, but students also will be given access to appropriate computers on campus. Your grade will be determined by performance on the midterm exam (20%), the final exam (30%), and several projects (50%). Each of the projects will involve enhancing a compiler, written in C, to perform specific analysis and transformations... and thus will require some C programming. Each project must be accompanied by a short Implementor's Notes document. The only difference between EE599 and EE699 will be that the graduate (EE699) projects will incorporate a few more advanced requirements. Some projects may be done in teams, depending on course enrollment.

Course Staff

Professor Hank Dietz would normally be in the Davis Marksbury Building; see his home page for complete contact info. He has an "open-door" policy that whenever his door is open and he's not busy with someone else, he's available -- and yup, there really is a slow-update live camera in his office so you can check. However, during the pandemic, he doesn't expect to be there much. The best method to contact him is to email hankd@engr.uky.edu using "OC" in the subject line for anything related to this course. If appropriate, individual Zoom meetings also can be scheduled via email.