Study Guide

• Register Alloation. K-Coloring. Why it is NP-Complete. Coloring by Simplification algorithm. Be able to trace through the algorithm given an interference graph. (Stack and assignment of registers).
• Liveness Analysis. How to build CFG from code. Know use, def, live, live range. Live in, live out, Data flow equations. Algorithm to do liveness analysis. Be able to show the iterations and trace through the algorithm. Know the complexity of the algorithm. Interference Graph. How to build interference graph. 
• Instruction Selection. Tiling. Optimum Tiling, Optimal Tiling. Maximul Munch.
• 0Canonical Tree. Basic Blocks. 
• Translation to IR tree. Know what an IR tree is. Know what kind of nodes are there. Given a set of trees you should be able to identify the IR tree.
• Activation Record and Frames. Why frames are used. What things are stored in stack. What things are stored in heap. Be able to draw a stack from a piece of code.
• Type checking and symbol table. Know the basic implementation of symbol table. Find environments and bindings.
• Abstract Syntax tree. Convert a parse tree to Abstract Syntax Tree.
• Regular Expression RE. First Follow and nullable. Predictive parsing table.