CS 375, Compilers: Study Guide for Final Exam

Date: Saturday, May 11, 2013, 7-10 PM in WEL 2.304

Material on the Midterm Study Guide is included on the final.

Reading:

Aho, Lam, Sethi, and Ullman, Compilers: Principles, Techniques, and Tools, Chapters 7 through 9.

Material covered in class:

Topics in parsing programming language constructs: current status variable; type coercion; conversion of names with constant compile-time values to constants; intermediate code for non-arithmetic statements.
Array references: methods for storing arrays (row-major order, column-major order); effect of array order and loop order on efficiency; computation of effective address (formula); why optimization of array references is important.
Record structure declarations and references: what information is stored in symbol table from declaration; generation of intermediate code for references to records; references using pointers; records with variant parts.
Type systems, type checking. Failure of type checking due to aliasing, variant records, subroutine calls.
Intermediate representations: assembly language, machine language, reverse Polish, quadruples, triples, trees: advantages and disadvantages of each, comparisons. Be able to produce any of these forms as output of a shift-reduce parser.
Link editor: what functions does it perform
Code generation: absolute code, relocatable code, assembly language (advantages, disadvantages); generation of executable code, calls, interpreted code; how to generate code from trees; ways to improve generated code.
Runtime storage organization:
- Data area, base address, offset, location counter; representation of addresses in relocatable binary output and how the link editor handles them.
- Static allocation: program relocation.
- Storage management for Algol-like languages: stack frame, stack pointer; display; block and procedure entry and exit; local and global variables and how they correspond to symbol table organization.
- Records; dynamic storage management: heap, storage leak, garbage collection.
Formal, actual, implicit parameters; call by reference, value, pointer. Macros.
Optimization: economic considerations; constant folding, partial evaluation, peephole optimization, eliminating dead code, common subexpression removal, moving non-changing code out of loops, reduction in strength, optimization of subscript expressions, loop unrolling; basic blocks: definition; relation to program flow graph; be able to mark the blocks in a sequence of code. Bit vectors: referenced, defined, computed, killed, available, busy; graphs, transitive closure, dominators; intervals; global program analysis; graph coloring for register assignment.
OOP: representation of an object; process of message sending; efficiency issues.
Hardware support: register windows, memory prefetching, postincrement.

Vocabulary:

absolute code	activation record	actual parameter
adjacency matrix	aliasing	antisymmetric
automatic programming	available	backpatching
basic block	bit vector	Boolean matrix
BSS storage	busy	cache prefetch
call by name	call by reference	call by value
canonical form	Cartesian product	class
code motion	column-major order	computed
condition code register	constant folding	control flow analysis
dangling reference	data flow analysis	dead code
defined	definition-use chain	dereference a pointer
display	dominator	dynamic
dynamic memory	dynamic type checking	epilogue
formal parameter	forward reference	fragmentation
garbage	garbage collection	global optimization
graph	graph coloring	heap
implicit parameter	induction variable	inherit
inherited attribute	inlining	instance
instance variable	interpreted code	interval
keyword	killed	left factoring
lexical scoping	link editor	live variable
loader	local optimization	location counter
loop unrolling	macro	mark-and-sweep
materialization	memory hierarchy	memory leak
message	method	multiple inheritance
name equivalence	nonvolatile register	object
object-oriented programming	overloading
padding	partial evaluation	partial order
partition	peephole optimization	polymorphic function
postamble	postincrement	preamble
predictive parsing	prologue	quadruples
reduction in strength	referenced	reflexive transitive closure
relation	relocatable code	relocation
restore registers	return address	reverse Polish
RISC	row-major order	save registers
selector	send a message	sound type system
spill code	stack frame	stack pointer
static	static analysis	static type checking
strong typing	structural equivalence	superclass
superscalar	synthesized attribute	three-address code
three-address machine	transitive closure	triples
two-address code	two-address machine	type coercion
type hierarchy	type signature	union type
unreachable code	volatile register