One field of Computer Science is Optimizing Compilers. Starting with the first high-level programming language Fortran in 1954, the field has a long history, and understandably, its terminology has become overloaded (no longer the Fortran Franca days). Compiler students and even established researchers today often use the same terms for different meanings. Part of the confusion is that the original wording, while appropriate in the past, becomes misleading in modern compilers. This post gives the traditional definitions for common terms and their sources, intermixed with background context based on my teaching of an advanced compiler course at URCS.

In Engineering a Compiler by Keith Cooper and Linda Torczon, a standard compiler textbook, the section (§8.3) on Scope of Optimization gives the following definitions:

• Local methods “operate over a single-basic block.” In a basic block, “statements are executed sequentially” and “if any statement executes, the entire block executes.”
• Global methods “use an entire procedure as context.” A typical representation of a procedure is a Control Flow Graph (CFG). In between local and global are regions based on particular properties, e.g., a loop nest, an Extended Basic Block (cycle-free), or a dominator tree. Global methods are also called intraprocedural.
• Interprocedural methods “consider scopes larger than a single procedure.” They are sometimes called whole-program methods.

I used the Cooper-Torczon book when I created the advanced compiler course at URCS in the early 2000s, right when the first edition was published, and taught it for years. The first technique to teach students was local value numbering, with the original example from the 1971 paper by John Cocke (’87 Turing awardee) and Frances Allen (’06 Turing awardee, first woman to receive the award) titled “A Catalogue of Optimizing Transformations” and used the example from the EAC book to progress from local value numbering to regional methods based on EBBs and dominators. Students liked the material. Chris Stewart, now a professor at OSU, conceived a new idea during a lecture; students in later years came to know it as the Stewart extension

A compiler finds properties of program code, i.e., properties that hold on all its executions. This is known as the meet-over-all-path solution. When we consider a cyclic CFG, the number of possible paths becomes infinite. This is the course transition to data flow analysis.

• Data flow analysis was pioneered by Kam and Ullman (2020 Turing awardee). It is the foundation of iterative analysis used by almost all compilers. An analogy is solving a recursive equation in math. Think of an iterative solution as the way to find a fixed-point solution. The key questions are convergence, speed of convergence, and the uniqueness of the solution. Their 1977 paper was titled “Monotone Data Flow Analysis Frameworks” and gave the monotone and distributive conditions for iterative analysis. Their earlier paper named the technique “Global Data Flow Analysis.”
• Def-use chains are what some people think when they say “data flow”. Def-use analysis may be local or global. The resulting graph was called def-use chains in compiler papers.

Modern compilers, starting with LLVM, have converged on the intermediate representation called static-single assignment (SSA). Cytron, Ferrante, Rosen, Wegman, and Zadeck published the breakthrough technique in POPL’89 and TOPLAS’91. SSA was a direct improvement of def-use chains. Def-use chains may be quadratic in size in the worst case, SSA is linear. More useful is that SSA’s phi-functions more directly encode control flow information and makes data flow analysis simpler and more effective.

The SSA paper authors did not implement the technique. Keith Cooper, Ken Kennedy and their students were the first to test it out in the Rice compiler (SSA co-inventor F. Kenneth Zadeck was a student of Ken’s, graduated in 1983). EAC, first edition in 2003, is the first compiler textbook that teaches SSA and SSA-based compiler optimization. At the time, people questioned whether it was too advanced for undergraduate students. Chris Lattner, then a graduate student, created LLVM IR based on SSA. I don’t think it is coincidence that his advisor, Vikram Adve, was a researcher scientist at Rice at the time when SSA was first implemented. LLVM is now the most widely used compiler in the world.

My favorite data flow analysis in the Cooper-Torczon book is partial redundancy elimination (PRE). The classic formulation uses four coupled data flow equations. One year when taking my course, Linxiang Xiang implemented SSA-based PRE in Ruby. It was a most impressive compiler project.

In early days of CS, a PhD thesis might be just a new data flow analysis technique. In those days, everyone knew data flow to be the iterative compiler analysis. Now, people may use the term for its literal meaning but create confusion because it conflicts with the usage in the past. This triggered a lively discussion at Friday systems meeting and an email followup. I agree with my colleague Michael Scott (I have his Programming Language Pragmatics book right next to EAC on my shelf) who said “Yes, it’s kinda confusing. But if you try to redefine the terms it’s going to be even more confusing.“

Evolution of the Compiler Course

A motto in compiler teaching is learning a compiler by building one. As an undergrad at PKU, I took the compiler course taught by Sun Jiasu (孙家驯，北大70本) in sophomore year and then compiler practice by Professor Ding the next semester, which had no lecture and just one assignment: implement a compiler for a Pascal-like language (nested procedures, static scoping). As an MS student at Michigan, I took Steve Carr’s course and wrote an optimizer using Rice’s compiler base code. This was why as a PhD student at Rice, I sat in on Keith Cooper’s course but did not take it officially. My buddy Vijay Pai (later a tenured professor at Purdue ECE) took the course with me, vowing to beat the CS compiler wizard in the compiler project — but he couldn’t.

At the turn of the millennium, Rochester and Rice were the two smallest (with about 12 faculty members each) in the top 20 CS programs in the National Academy rankings. Rice was a compiler powerhouse, with many courses in computer systems but maybe one in AI (which I didn’t take). Rochester was an AI department with courses in computer vision, natural-language processing, robotics etc but mainly just two in systems: computer systems and programming systems. The latter teaches both compilers and programming languages, forming the basis of Michael’s popular PLP book, still the most adopted textbook on the subject among top 30 CS departments. After joining Rochester in July 2000, I taught the programming systems course for several years and then created the advanced compiler course as the follow-up course. When I teach either one, I require students to implement a compiler.

For teaching, I wrote a compiler IR in a handful of Java classes and asked students to write compiler passes on this compact IR. A kindred soul was Chris Lattner, then a PhD student attending the first ACM SIGPLAN MSP workshop Trishul Chilimbi and I co-organized with PLDI in Berlin in 2002. He told me that he was implementing an object-oriented compact IR, too, in C++.

Early students and TAs included my first two students, Yutao Zhong (who has taught at George Mason in DC for many years) and Xipeng Shen (now directing the intelligent software center at Purdue). Bill Scherer (later research faculty at Rice) wrote a test suite for the teaching compiler. One program files a tax return (the 1040 form), and another draws the Mandelbrot set. The Scherer tests were used for many years to score student compilers by how much they reduce program instructions. When Ben Van Durme (now faculty at Johns Hopkins and research manager at Microsoft) took the course, he told me every day that he knew the exact way to remove two more instructions from one test program but it was too much pain for too little gain. The morning after the deadline, he ran into me, full of joy and pride, saying “I worked overnight and did it!”

Starting in the 1980s, GCC has been the foundation of open-source software. It was a real compiler but too complex for classroom use. In 2005, GCC 4.0 adopted a compact IR called GIMPLE. I invited its API designer, Diego Novillo, to visit Rochester (from Toronto) to give a guest lecture. Shortly after, I gave students the option and preparation to complete the compiler project in GCC, which at the time meant adding their code and compiling it alongside the other two million lines of source code. Tongxin Bai, then a PhD student, wrote GCC passes and Linux kernel modules (after taking the OS course from Sandhya Dwarkadas) as routine, had so much fun, and made money from his Google internship, he didn’t think about publishing and graduating. John Pershing (featured in the 2025 newsletter) was part of a group of undergrads who chose the GCC option for the compiler project and made the compiler work. As LLVM became widely adopted, it also became an option for the compiler project. Here is a project assignment from Rahman Lavaee in 2016. One year later, Dong Chen changed the two options to LLVM and Rust.

Xipeng Shen came to Rochester in 2001 as an AI student and switched to become my student after taking the compiler course. When he graduated in 2006, he knew more about computer systems than all AI professors and more about machine learning than all systems professors. His first job was at William and Mary where he taught two courses: compilers and AI. Many of his students have become professors. When I taught CS 258 in 2023, a student showed me the compiler course slides he found online by Yufei Ding, then a professor at UC Santa Barbara and now at UCSD. Some of the material had come full circle, after starting its life years ago right here in Rochester.