Courses

  /  

Descriptions

EECS 323: Code Analysis and Transformation

Quarter Offered

Spring : 2-3:20 TuTh ; Campanoni

Description

Fast, highly sophisticated code analysis and code transformation tools are essential for modern software development. Before releasing its mobile apps, Facebook submits them to a tool called Infer that finds bugs by static analysis, i.e., without even having to run the code, and guides developers in fixing them. Google Chrome and Mozilla Firefox analyze and optimize JavaScript code to make browsers acceptably responsive. Performance-critical systems and application software would be impossible to build and evolve without compilers that derive highly optimized machine code from high-level source code that humans can understand and reason about efficiently. Understanding what modern code analysis and transformation techniques can and can't do is a prerequisite for research on both software engineering and computer architecture, since hardware relies on software to realize its potential. In this class, you will learn the fundamentals of code analysis and transformation, and you will apply them by extending LLVM, a compiler framework now in production use by Apple, Adobe, Intel and other industrial and academic enterprises.

INSTRUCTOR: Simone Campanoni (simonec@eecs.northwestern.edu)

COURSE SYLLABUS

ASSIGNMENTS:
In this class, you will learn how to design code analysis and optimization passes in a production compiler (LLVM). You will have 7 assignments; the f rst is a raw implementation of a trivial code analysis and related optimization. Subsequent assignments will involve incremental improvement of your original work. The end result of these assignments will comprise yourfinal project that must include:

• a state-of-the-art code analysis and optimization implemented in LLVM
• a paper that describes your work, including experimental results obtained in a real system (e.g., your laptop)
• slides that you will use during your presentation at the end of the quarter where you will describe your work to the rest of the class

TENTATIVE SCHEDULE:

PAPERS:

• P1   LLVM website, LLVM documentation
• P2   Sections 6.1, 6.2, 6.3, 6.4 of Compiler transformations for high-performance computing
• P3   The program dependence graph and its use in optimization
• P4   The superblock: an effective technique for VLIW and superscalar compilation
• P5   Profile Guided Compiler Optimizations, Google-Wide Profiling: A Continuous Profiling Infrastructure for Data Centers

HOMEWORKS:

• H1 Delete useless single instructions
• H2 Delete useless instruction-pairs
• H3 Hoist instruction pairs outside loops whenever possible
• H4 Move paired-instructions as close as possible
• H5 Implement a profiler and guide your transformations

MATERIALS:
Recommended Book:

1. “Modern Compiler Implementation in C” Andrew W. Appel, 1st Edition; ISBN: 978-0521607650

Reference Book:

1. “Advanced Compiler Design and Implementation” Steven Muchnick, 1st Edition; ISBN: 978-1558603202

Selected papers for topics not covered by the mentioned books

GRADING POLICY:
Homework assignments: 70% This is cumulative to all homeworks assigned during the class
Final project: 20% Quality of the end-result of yourfinal project
Final presentation: 10% Your presentation during the last week of the class

PRE-REQS:
COMP_SCI/EECS 213: Introduction to Computer Systems (or equivalent)

CLOSELY LINKED CLASSES:
COMP_SCI/EECS 322: Compiler Construction
COMP_ENG/EECS 361: Computer Architecture 1