Code Optimization

General information

Course instructor: Asst. Prof. Miran Pobar, PhD / Vedran Miletić, PhD
Name of the course: Code Optimization
Study programme: Undergraduate University Study Programme Informatics
Status of the course: compulsory for Software Development (SD) module, elective for other modules
Year of study: 3
ECTS credits and manner of instruction:

• ECTS credits: 5
• Number of class hours (L+E+S): 30+30+0

Course description

Course objectives

The objective of this course is to introduce students to basic principles and methods of code optimization at the level of abstract syntax, program flowchart and executable (machine) code.

Course enrollment requirements

A pass mark in Algorithms and Data Structures.

Expected learning outcomes

After fulfilling all the obligations anticipated by the course, students are expected to be able to:

O1. Analyse the properties enabling code transformation and represent the code using a flowchart.
O2. Show the differences between local and global optimization and identify where each of them applies.
O3. Perform a conventional data flow analysis, register allocation by graph colouring and common subexpression elimination.
O4. Describe mode of operation of higher-level optimization and apply existing optimizations.
O5. Describe differences between higher-level optimizations and target architecture-specific optimizations.
O6. Choose instructions.
O7. Analyse the problem of optimization phase sequence.

Course content

• Overview of programming language optimizing compiler. Optimization per elements. Analysis of properties enabling transformation. Flowchart and representation of program concepts. Problem of optimization phase sequence.
• Types of optimization. Local optimization: peephole optimization, instruction scheduling. Global optimization: common subexpressions, code changes. Interprocedural optimization. Call graph.
• Conventional data flow analysis. Algorithms on graphs, sets of live and available variables. Register allocation by graph colouring. Common subexpression elimination. Spilling to memory; use of temporary expressions introduced during common subexpression elimination. Data flow anomalies. Static single assignment form.
• Overview of higher-level optimizations. Pointer analysis and pseudonym analysis.
• Target architecture-specific optimization. Choice of instruction. Instruction scheduling and related problem of optimization phase sequence.

Manner of instruction

• lectures
• seminars and workshops
• exercises
• distance learning
• fieldwork
• individual assignments
• multimedia and network
• laboratories
• mentorship
• other _______

Comments

Classes are held by combining classroom work and computer laboratory work, with the application of distance learning system. When they enrol into this course, students will be instructed to use the distance learning system. A detailed schedule with lectures and exercises will be defined in the syllabus.

Student responsibilities

Student responsibilities for this course are as follows:

• Regularly follow course activities within the distance learning system and attend classes taking place in the form of lectures, auditory and/or laboratory exercises.
• Participate in continuous assessment (theoretical and practical preliminary exams) and successfully pass them.
• Complete individual or team practical work related to a given topic.
• Score at least 50% on the final exam.

A detailed scoring system for the course and passing scores for individual activities will be specified in the course syllabus.

Monitoring¹ of student work

• Class attendance: 1
• Class participation: 0.5
• Seminar paper:
• Experimental work:
• Written exam: 1
• Oral exam:
• Essay:
• Research:
• Project:
• Continuous assessment: 1.5
• Report:
• Practical work: 1
• Portfolio:

Assessment of learning outcomes in class and at the final exam (procedure and examples)

• Practical assessment on a computer (practical preliminary exam), in which students analyse and transform the code, and use and adapt the existing optimizations (I1, I2, I3, I4, I6).
• Group or individual practical work in which students, according to the set instructions, implement a solution containing required optimizations and draw up documentation for their own implementation (I1, I2, I3, I4, I6).
• Written or online assessment in which students demonstrate their understanding of theoretical concepts related to optimization of programming code, e.g. through multiple choice questions, fill in the blank questions and essay questions (I1, I2, I4, I5, I7).

Mandatory literature (at the time of submission of study programme proposal)

1. Cooper, K. D. & Torczon, L. Engineering a compiler. (Elsevier/Morgan Kaufmann, 2011).
2. Holub, A. I. Compiler design in C. (Prentice Hall, 1990). (E-book is available for free download from the author's site holub.com/compiler/ and can be printed if necessary)
3. Scripts, presentations and other learning material available in the e-course.

Optional/additional literature (at the time of submission of the study programme proposal)

1. Fraser, C. W. & Hanson, D. R. A retargetable C compiler: design and implementation. (Benjamin-Cummings, 1995).
2. Muchnick, S. S. Advanced compiler design and implementation. (Morgan Kaufmann, 1997).
3. Nielson, F., Nielson, H. R. & Hankin, C. Principles of program analysis. (Springer, 1999).
4. Appel, A. W. Modern compiler implementation in C. (Cambridge University Press, 2004).
5. Aho, A. V., Lam, M. S., Sethi, R. & Ullman, J. D. Compilers: principles, techniques, & tools. (Pearson/Addison-Wesley, 2006).
6. Morgensen, T. Ae. Basics of Compiler Design. (Lulu, 2010).
7. Wilhelm, R. & Seidl, H. Compiler design: virtual machines. (Springer, 2011).
8. Hack, S., Wilhelm, R. & Seidl, H. Compiler design: code generation and machine-level optimization. (Springer, 2019).
9. The GNU Compiler Collection. GCC online documenatation. (GNU, 2019). (available online: gcc.gnu.org/onlinedocs/)
10. The LLVM Compiler Infrastructure. LLVM documentation. (LLVM, 2019). (available online: llvm.org/docs/)

Number of assigned reading copies in relation to the number of students currently attending the course

Quality monitoring methods that ensure the acquisition of exit knowledge, skills and competences

It is anticipated to make periodical evaluations for the purpose of ensuring and continuously improving the quality of classes and study programme (as part of the activities of the Quality Assurance Committee at the Department of Informatics). In the last week of classes, students will evaluate the quality of classes using an anonymous questionnaire. Students' achievements in the course will also be analysed (percentage of students who passed the course and their average grade).