Teaching
Courses, Spring 2006 |
|
COSC6361 And
Compilers Course Material Syllabus |
Modern
compilers are invariably optimizing compilers. In addition to implementing a basic
strategy for translating programs written in a given programming language to
object code for a target machine, optimizing compilers spend a good deal of
effort trying to improve the behavior of the resulting output. Much of the
work of compiler development, and most of the complexity, is within the
optimization process. A compiler developer must decide on the goals of
optimization and develop one or more strategies for reaching that goal. This
is an imprecise art that implies many trade-offs as the compiler attempts to
analyze source programs and use the resulting information gathered to make
structure changes to the program. In this
course we review the general strategy for building a compiler and then
introduce the structure of an optimizing compiler. These compilers use a
variety of intermediate representations analyses and program transformations
to reach their goals. The remainder of this course considers a selected
subset of such analyses, transformations and strategies for optimization, and
discusses implementation issues related to different programming languages
and target platforms. The course book is: S.S. Muchnik. Advanced Compiler Design and
Implementation, Morgan Kaufman Publishers,
We also use excerpts from: H. Zima and B. Chapman. Supercompilers for Parallel and Vector Computers,
ACM Press, Course ContentsIntroduction -
Overview of course, material etc. A short history of compiler construction. Overview of
Compilation - Lexical
Analysis, Syntax Analysis, Semantic Analysis, Code Generation, Register
Allocation and Instruction Scheduling Intermediate
Languages - Design of Intermediate Languages,
High level, Medium Level and Low Level IRs,
Representation of IRs and efficiency aspects. Symbol Tables - Design Issues. Scope,
Extent and Visibility, Efficiency Run Time
Environment - Setting up storage for
global, local, static and dynamic data objects, role of procedures and
their implementation, run time
libraries, object code, linkage and execution Introduction to
Optimization - purpose and role of
optimization in modern compilers, examples of optimizations, role of analysis and transformation,
correctness and efficiency of optimizations; optimization strategies,
examples of compilers and use of different IR levels for optimization Scalar Control Flow
Analysis - representing structure of
a procedure, basic blocks, flow graph, dominators and dominance tree,
identifying loops in IR, depth-first spanning trees, dominance frontiers,
control dependence, (ir)reducible graphs Data Flow Analysis - data flow problems, def,
use, DU-UD chains, semi-lattices and
formal data flow systems, classification of dataflow problems,
iterative algorithm, reaching definitions, useless and dead code elimination,
available expressions problem, constant propagation, SSA form of DFA,
practical aspects Alias Analysis - role of alias analysis,
must and may aliases, aliasing in different languages, gathering alias
information Data Dependence
Analysis - loop nests and execution
orders, definition of data dependence, purpose of dependence testing, linear diophantine equations, range test, GCD algorithm and GCD
test, Banerjee test. Dependence graphs, strongly
connected components - normalizing loop
nests, induction variable
substitution, scalar forward substitution; goals of loop optimization, legality
of transformations, manual optimizations, reducing loop overheads, loop
unrolling, handling branches, statement reordering, scalar expansion, loop
distribution, loop peeling Memory
Optimizations - register and cache, temporal and spatial reuse,
application of loop optimizations to support memory optimization, loop memory
footprint, loop fission, loop fusion, loop interchange, loop tiling, unroll
and jam, array padding SIMD and Vector
Optimizations - statement reordering,
scalar expansion, loop distribution,
loop peeling, vector code generation Interprocedural Analysis - call graph construction,
call chains, must and may analysis, array regions and their representation,
accuracy and efficiency of summary analyses Interprocedural Optimizations - procedure inlining, procedure cloning, specialization, tail-call
elimination |