University of Arizona, Department of Computer Science

CSc 553: Topics Covered

Intermediate Representations
  • Trees and DAGs
  • Basic blocks and control flow graphs
  • Static single assignment (SSA) form
  • Program dependence graph
Code Generation
  • Basic ideas
  • Register allocation and assignment; graph coloring
  • Peephole optimization
Program Analysis
  • Control flow analysis: dominators and loops
  • Data flow analysis (intra-procedural); formulation and iterative solution of dataflow equations.
  • Example analyses: reaching definitions, liveness analysis, available expressions, very busy expressions, constant propagation.
  • Pointer analysis
  • Array dependence analysis
  • Inter-procedural analysis
Machine-Independent
Code Optimization
  • Copy propagation
  • Dead code elimination
  • Common subexpression elimination
  • Induction variable elimination
  • Strength reduction
Machine-dependent
Code Optimization
  • Instruction scheduling
  • Cache optimizations: profile-guided code layout
  • Speculative optimizations
Current Topics
(as time permits)
  • Just-in-time code generation
  • Dynamic code optimization

Background Assumed

Since CSc 453 and CSc 473 are prerequisites for this course, I will assume that you are familiar with the material listed below. We will review some of this quickly in class, but in general you are expected to be responsible for this material.

Textual Material (References are to the text Compilers – Principles, Techniques and Tools by Aho, Sethi and Ullman):

  1. General : Ch. 1, 2.
  2. Lexical Analysis : Ch. 3, Sec. 3.1-3.4: Background, specification and recognition of tokens. Sec. 3.5: specifying lexical analyzers. Sec. 3.6-3.7: Basic theory of finite state automata.
  3. Parsing : Ch. 4, Sec. 4.1-4.3: Background; Sec. 4.4: FIRST and FOLLOW sets.
  4. Syntax Directed Translation: Ch. 5. Sec. 5.1: inherited and synthesized attributes; Sec. 5.2: construction of syntax trees.
  5. Type Checking: Ch. 6. Sec. 6.1-6.4.
  6. Run-time Environments: Ch. 7. Sec. 7.1-7.3: Background; Sec. 7.6: symbol tables.
  7. Intermediate Code Generation: Ch. 8.
  8. Final Code Generation: Ch. 9. Sec. 9.1-9.3: Background; Sec. 9.9: peephole optimization.

Programming Skills:
  1. Proficiency with the programming language C.
  2. Familiarity with the Unix operating system, including tools such as editors, compilers, make, debuggers, etc.
  3. Acquaintance with lex/flex and yacc/bison (see Documentation and Notes for pointers to documentation and tutorials.)