CSE 401/M501 22au 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.

As with the midterm, the exam will be closed book, except that you may have two 5x8 (or smaller) index cards with whatever notes you wish written on both sides for reference. The notes must be hand-written, i.e., no computer printouts, no scanned/reduced notes, and no electronic devices or other technology. You can use the notecard you had for the midterm as one of these cards or you can have two completely new cards.

• Distribution of tasks in phases of a typical compiler (scanning, parsing, semantics, optimization, code gen, etc.)
• Static semantics and type checking, symbol tables, etc.
• x86-64 architecture - basic instruction set as used in the project
  • You should be able to read/write simple functions in assembly language
  • Don't memorize instruction set details -- summaries will be provided as needed on the exam -- but you should know the basic data manipulation and control flow instructions without having to look these up
• Runtime storage organization
  • Representation of scalars, arrays, objects
  • Address space layout: code, static data, stack, heap
• Calling conventions
  • Parameters and register usage (don't spend time memorizing 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, including the use of the first parameter register for this in MiniJava programs)
  • Function call, entry, and return conventions; function prologue and epilogue code; use of base pointer (%rbp) to link stack frames and access function local variables in simple x86-64 code
  • Stack frame layout and alignment
• Object representation
  • Data layout
  • Object creation - new
  • Inheritance and method overriding
  • Method invocation using dynamic dispatch (vtables)
• Code generation for other common 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 (def, use, in, and out sets); 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 necessary phi functions and provide variable version numbers correctly)
  • 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 key algorithms discussed in class
  • Instruction selection & tree pattern matching
  • Instruction scheduling & list scheduling
  • Register allocation & allocation by graph coloring
• Garbage collection - general ideas, not details.
  • Basic notions of liveness, reachability
  • Reasons behind strategies like compacting and generational collectors