CMSI 3802: Quiz 7 Preparation

When

Last 10 minutes of class on Wednesday, April 29, 2026.

Everyone takes the exam at the same time.

Scope

Static Analysis, Intermediate Representations, Code Generation, Code Optimization.

Ground Rules

You will take the exam on Brightspace. There is 10 minute time limit, or 15 minutes for those with time-and-a-half accommodations.

Preparation Checklist

Do each of the following to maximize your preparation:

Review the recordings for class periods you missed, and for portions of the class sessions that you attended but feel you need to review.
Work through the course notes on Static Analysis, Intermediate Representations, Code Generation, and Code Optimization.
Watch the embedded videos in the course notes above.
Follow some of the links within the course notes to outside articles and videos. This gives you access to new material as well as additional takes on the course content.
Practice with the recall questions on the notes above.
Skim Chapters 6–8 of [Mogensen].
Skim (but with interest) Chapters 11–12 of [Mogensen].
Continue studying the Ohm Documentation (as much as you can).
Skim the Wikipedia articles on Transpilers, Intermediate Language, Virtual Machine, LLVM, Java Virtual Machine, C--, WebAssembly, Single Static Assignment
Skim The Wikipedia page on Static Program Analysis
Skim the OWASP brief article on Static Code Analysis (from a security perspective)
Browse the Wikipedia article on Program Optimization
Study this “Optimization Killers” article. You’ll be glad you did. There are so many good things in here you can impress your friends (and future interviewers) with!
Browse this great presentation by Graydon Hoare. You don’t have to understand every slide, but jot down notes from some of the big ideas. If it gets too technical, don’t worry, just move on.
Read Frances Allen’s classic A Catalogue of Optimizing Transformations. This work followed two of her previous papers where she created new frameworks and algorithms and structures for performing and implementing static program analysis. You may also wish to read this remembrance from IBM (where she was a fellow), or any number of bibliographies on her life and work.

Were you able to check off every box?

Outline of Course Content

The fact that active recall is better for acquiring long-term knowledge does not mean that outlines and concept maps are not useful. Learners should use multiple techniques—think “both and” rather than “either or.”

Static Analysis
    Difference between syntax errors and static semantic errors
    Many examples of contextual constraints
    Formal specification of contextual rules
        Attribute grammars
            Semantic rules
            Action routines
        Static semantic definitions
    Implementing a static analyzer
        Name analysis
        Type analysis
            Type inference
            Type checking
        Control flow analysis
        Data flow analysis
    Security analysis
Intermediate Representations
    Why have them?
        Analysis/Synthesis is inherent to translation
        Break down complex problem
        Retargetability
        For machine independent optimizations
    Tuple vs. Stack-based IRs
    Entities
    Big list of possible tuples
    Examples
    Control flow graphs
    SSA
    Some well-known IRs
        JVM
        CLR
        LLVM
        SIL
        CIL
        WebAssembly
        MLIR
Code Generation
        Goals
        Translation to JavaScript
        Translation to Assembly Language
            Naïve
            Interpretive
            Code generator generators
        Generation of real assembly language
            Address assignment
            Instruction selection
            Register allocation
            Low-level optimization
        Understanding the runtime system for block-structured languages
            Stack frames
            Dynamic links
            Static links
            Register save area
            Register spilling
Code Optimization
    Things we can optimize for:
        Speed
        Size
        Power consumption
        Memory usage
    Why "code improvement" is a better name than "code optimization"
    Degrees of optimization
        None
        Basic / Peephole
        Within Basic Blocks
        Intraprocedural
        Interprocedural
        Whole Program
    Criteria
        Safety
        Profitability
    When optimizations can be done
    General strategies
        Use more efficient instructions
        Reuse results rather than recomputing
        Reduce the amount of code
        Reduce conditional jumps
        Use hardware resources efficiently
    Common optimization techniques
        Constant Folding
        Algebraic Simplification
        Operation Reordering
        Strength Reduction
        Assignment Simplification
        Unreachable Code Elimination
        Dead Code Elimination
        Copy Propagation
        Common Subexpression Elimination
        Conditional Jump Compression
        Loop Unrolling
        Loop Fusion
        Loop Fission
        Loop Inversion
        Loop Interchange
        Loop Invariant Code Motion
        Jump Threading
        Special Instructions
            e.g., muladd, range, ...
        Induction Variable Simplification
        Tail Recursion Elimination
        Function Inlining

About the Problems

This is a mini-quiz which tests for immediate understanding of topics and not your ability to work out problems over an extended duration of time. There is a strict time limit so that your immediate fluency is tested rather than your ability to search the web (or worse, ask a chatbot), since these things take time. There will be 5–10 questions, some will be multiple choice, some multi-select, and some matching. There are no free-form answers, so the exam will be autograded and you will see your score immediately after it is submitted.

All content on the assigned readings is fair game for questions, so do not neglect the readings, and by all means do the recall questions!