Subject Introduction
COMP4133: Advanced Compiler Construction
Semester 1, 2004
|
1. Objectives
This course examines a variety of topics in the design and implementation of
an optimising compilers on uniprocessor architectures. The emphasis
is on code optimisations rather than on code generation. The topics
fall into two broad categories:
- classic code optimisation techniques used in the compiler back end, and
- some topics of current research interest.
This course will be accomplished by programming projects to help you gain
experience with implementation issues and learn to evaluate the impact of each
compiler technique. You are particularly encouraged to improve and extend
existing techniques and develop new ones.
2. Pre-requisites
COMP3131/9102
with a minimum 65% or consent of lecturer.
3. Web Page
The subject web pages will provide links to all material related to this
subject. The pages can be accessed via:
http://www.cse.unsw.edu.au/~cs4133/
You should become familiar with the structure and content of the subject
web pages early on, and consult them frequently.
In particular, all important announcements will be posted to the Subject
Noticeboard on the opening page. Urgent information will also be sent to
you by email via the class mailing-lists:
comp4133-list
You should check your school e-mail frequently in case of announcements
relating to this course. If it is not convenient for you to read your
e-mail on a CSE machine, e.g. perhaps if you work during the day,
you can create a "mail alias" that forwards
your mail to an e-mail account elsewhere by logging in on a CSE machine
and doing the Unix command
mlalias -C <yourlogin> -a <your-other-email-address>
For example, if your CSE login is abc and your other e-mail
address is xyz@compiler.com.au, then you would type
mlalias -C abc -a xyz@compiler.com.au
We assume that you read e-mail sent to your CSE account by the next
working day during teaching sessions.
4. Staff
5. Syllabus
The following is a (non-exclusive and subject to change) list of topics
that may be covered:
- Classical Optimisation Techniques
- Static single assignment (SSA) form
- Control flow analysis
- Data flow optimisations and data flow frameworks
- Value flow optimisations
- Redundancy elimination techniques ([G]VN, [G]CSE, LCM, PRE, MC-PRE).
- Alias and type analysis
- Interprocedural analysis and optimisations
- Topics of Current Research Interests
- Profile-guided compiler optimisations
- Compiler techniques for VLIW and IA-64 architectures
- Compiler techniques for improving memory hierarchy performance
- Compiler techniques for low-power
6. Lecture Timetable
6pm -- 9pm Tuesday at EE222.
7. Programming Assignments
- Projects will be available after the semester starts.
- Topics are broad, covering compiler analysis and optimisations.
For detail, follow the Assignments link on the left.
8. Assessment
Your final mark will be the sum of the following two components:
- Programming project 1: 10
- Programming project 2: 50
- Presentation in weeks 13 and 14: 5
- Report: 10
- Design and implementation: 35
- Final exam (2 hours): 40
9. Course Policies
9.1 Lateness
Late programming assignments will be penalised unless you have legitimate
reasons to convince me otherwise. For details, see the assignment pages.
However, serious personal problems will be
dealt with individually.
9.2 Plagiarism
As you should be aware, the School of Computer Science and Engineering has a
commitment to detecting plagiarism in assignments. We run a special program
that detects similarity between assignment submissions of different students,
and then manually inspect those with high similarity to guarantee that the
suspected plagiarism is apparent.
We will send an email to these students individually asking for explanations
for this suspected plagiarism. While those students can collect their
assignment, their marks will only be finalised after reviewing the explanation
regarding their suspected plagiarism. Please send us an email to justify your
plagiarism if you received an email relating to this matter.
Please refer to the School's policies.
10. Reading Materials
10.1 Text
Steven S. Muchnick, Advanced Compiler Design and Implementation, Morgan Kaufmann Publishers, 1997. Try to get the latest
printing which has the fewest errors. See Errata for details.
10.2 References
- Robert Morgan, Building an Optimizing Compiler, Digital Press, 1998.
- Reinhard Wilhelm and Dieter Maurer, Compiler Design, Addison-Wesley, 1995.
- Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman, Compilers: Principles,
Techniques and Tools, Addison-Wesley, 1986.
- Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs and Koen G. Langendoen,
Modern Compiler Design, John Wiley & Sons, Ltd., 2000.
- Randy Allen and Ken Kennedy, Optimizing Compilers for Modern
Architectures: A Dependence-based Approach,
Morgan Kaufmann Publishers, 2001.
10.3 Papers
- Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. ACM Transactions on Programming Languages and Systems, vol. 13, no. 4, October, 1991, pp. 451-490.
- Partial Redundancy Elimination in SSA Form, Robert Kennedy and Sun Chan and Shin-Ming Liu and Raymond Lo and Peng Tu and Fred Chow, ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 21, no. 3, 1999, pp. 627--676.
- Lazy Code Motion: Theory and Practice, J. Knoop, O. R\"{u}thing, and B. Steffen, Proc. ACM Symposium on Programming Language Design and Implementation, 16(4), 1994.
- Optimal and Efficient Speculation-based Partial Redundancy
Elimination, Q. Cai and J. Xue, Proc. 1st IEEE/ACM International Symposium
on Code Generation and Optimization, 2003.
- Fast Copy Coalescing and Live-Range
Identification, Zoran Budimli{\'c}, Keith Cooper, Yimothy Harvey, Ken
Kennedy, Timothy Oberg and Steven Reeves, Proc. ACM Symposium on Programming Language Design and Implementation, 2002.
- Partial online cycle elimination in inclusion constraint graphs, Manuel Fähndrich, Jeffrey S. Foster,
Zhendong Su and Alexander Aiken,
Proc. ACM Symposium on Programming Language Design and Implementation, 1998.
-
Off-line variable substitution for scaling points-to analysis,
Atanas Rountev and Satish Chandra,
Proc. ACM Symposium on Programming Language Design and Implementation, 2000.
- ABCD: Eliminating Array-Bounds Checks
on Demand, Rastislav Bodik, Rajiv Gupta and Vivek Sarkar,
Proc. ACM Symposium on Programming Language Design and Implementation, 2002.
- Operator Strength Reduction , Keith Cooper, L. Taylor Simpson and Christopher Vick, ACM Transactions on Programming Languages and Systems, 23(5), Sept. 2001.
- On the Importance of Points-To Analysis and Other Memory Disambiguation Methods For C Programs, Rakesh Ghiya, Daniel Lavery and David Sehr, Proc. ACM Symposium on Programming Language Design and Implementation, 2001.
- Which Pointer Analysis Should I Use?, Michael Hind and Anthony Pioli, Int'l Symposium on Software Testing and Analysis, Aug. 2000.
- SCC-based Value Numbering, Keith Cooper and L. Taylor Simpson, Technical Report #CRPC-TR95636-S, Rice University. Oct. 1995.
- Constant Propagation with Conditional Branches, Mark N. Wegman and Kenneth Zadeck, ACM Transactions on Programming Languages and Systems, 13(2), pp. 181-210, April 1991.
Jingling Xue