Syllabus for Comp 613, Fall 1999
Prerequisites
Comp 311 and Comp 412.
Useful Background
Mathematical Logic
first order languages, theories, models, and definitions
as presented in
Operational Semantics
reduction to normal form, standard reduction strategies
as described in
H.P. Barendregt, The
Lambda Calculus, Elsevier Science Ltd, ISBN 0444875085
Dataflow Models of Computation
demand-driven and supply driven forms of dataflow execution
as described in
Arthur H. Veen: Dataflow Machine Architecture. ACM Computing Surveys, Volume
18, Number 4, December 1986, 365-396.
Resources
Primary reference books
Reference books
The following books are useful. I will try to place them on reserve
in the library. If you are thinking about going into this research area,
you should probably buy a copy.
-
Steven Muchnick, Advanced
Compiler Design and Implementation, Morgan Kaufman publishers, ISBN
1-55860-320-4 (Varsitybooks.com
and Buy.com
web pages) [Varsitybooks.com is offering a $10
student discount on purchases over $100.]
-
Now in the third printing; the first and second printing had significant
bugs, try to get the third printing
-
Richard Jones and Rafael Lins, Garbage
Collection: Algorithms for Automatic Dynamic Memory Management, John
Wiley and Sons, ISBN 0-471-0941 48-4
-
Tim Lindholm and Frank Yellin The
Java Virtual Machine Specification (Second Edition), Addison-Wesley,
ISBN 0-201-63452-X
-
Full text is available on-line,
but sometimes you want cold, hard paper in your hands
Outline
-
Java Implementation Framework and Philosophy
-
Quick overview of Java Language
-
Java VM
-
classfile format
-
bytecodes
-
verification
-
Intermediate representations
-
stack machine
-
register-transfer language
-
control-flow graph, basic blocks
-
depth first search
-
Dominators
-
finding loops - interval analysis
-
data flow analysis
-
kinds of analysis
-
methods of performing data flow analysis
-
static single assignment form
-
conventional code optimization
-
local optimization
-
global optimization
-
partial redundancy elimination
-
verification
-
threads
-
implementing synchronization
-
Java's weak consistency model
-
impact of multithreading and consistency model on optimization
-
exceptions
-
dynamic memory management and garbage collection
-
optimizing object-oriented languages
-
encoding of native code and executable IR as Java byte code
-
run-time code generation (JIT compilers) including register allocation
-
aggressive optimization for safe languages
-
set-based-analysis
-
method inlining
-
bounds check elimination
Reading Assignments
Chapters 35
and 36
of QUE
Special Edition Java Tutorial (JVM Overview)
Programming Assignments
- Due in class Thursday, September 16:
write Jasmin
assembly language code for a class named ArrayUtil
containing one method
public static float add(float[] a)
that adds the elements in a and returns the result. To test
your program write a Java class Test that includes a main
method that defines a sample float array and applies the add
method to it. You can download the Jasmin assembler from the
Jasmin web page.
This page also contains links to a
sample Jasmin
program and a summary of the
JVM instruction set
in Jasmin notation.
Grading
Grading will be based on three equally weighted components: class presentations, class participation and homework, and class projects.
Projects
Each class project will consist either of writing a short papers
or developing a code module written in Java to provide
infrastructure for building an optimizing Java compiler.
During the early part of the course, we will identify
what Java compilation tools are already available and how well they
support our implementation strategy.