CSE 401/M501 21au 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
  • 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 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 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