CSE 401 / M501 18wi Final Exam Topic List

This is a quick reminder of topics covered since the midterm. Any topic related to compiling is reasonable on the final (i.e, what would you need to do to implement some feature, from the front to the back end of the compiler?). We won't have detailed questions on regular expressions, LR parser tables, and other front-end issues that were covered in depth on the midterm, but you should be generally familiar with those ideas, including everything on the midterm exam topic list.

• Distribution of tasks in phases of a typical compiler (scanning, parsing, semantics, optimization, code gen, etc.)
• Static semantics and type checking
• x86-64 architecture - basic instruction set as used in the project, including floating-point arithmetic
  • You should be able to read/write simple functions in assembly language
  • Don't memorize instruction set details -- summaries will be provided if needed on the exam -- but you should know the basic data manipulation and control flow instructions
• Runtime storage organization
  • Representation of scalars, arrays, objects
  • Address space layout: code, static data, stack, heap
• Calling conventions
  • Parameters and register usage (you don't need to memorize the register list -- that will be provided if needed -- but you do need to understand parameter and result register conventions and saving/restoring registers as needed across function calls)
  • Function call, entry, and return conventions; function prologue and epilogue code; use of base pointer (%rbp) to link stack frames in simple x86-64 code
  • Stack frame layout and alignment
• Object representation
  • Data layout
  • Object creation - new
  • Inheritance
  • Method invocation using dynamic dispatch (vtables)
• Code generation for other language constructs
  • if-then-else
  • Loops
  • Arrays - new, length, subscripting
• Optimization
  • Scope of optimizations: peephole, local, global, interprocedural; tradeoffs between very local vs more global analysis/optimization
  • Basics of dataflow analysis; be able to solve simple problems
  • Dominators and dominance frontiers; be able to figure these out in a flowgraph.
  • SSA: be able to translate a simple flowgraph into SSA form (informally; you don't need to exactly implement any particular algorithm, but you should be able to place all necessary phi functions appropriately)
  • Examples of some common optimizations and how dataflow or SSA analysis reveals when these are possible (e.g., common subexpressions, live variables, constant folding).
• Major backend issues - not in detail, but know the major ideas and algorithms
  • Instruction selection & tree pattern matching
  • Instruction scheduling & list scheduling
  • Register allocation & allocation by graph coloring