Code Generation and What an Optimiser May Change · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Rearrange, but change nothing you can see

Computing · Computer Systems · ages 21-22
Name ______________________   Date ____________

  1. What single rule decides whether a rearrangement is allowed?

    • Whether observable behaviour stays the same
    • Whether it makes the file shorter
    • Whether the programmer approves each time

  2. Which jobs belong to the back end?

    • Parsing text into a tree
    • Writing user documentation
    • Picking instructions and assigning registers

  3. An optimiser may reorder two independent sums.

    Circle one:   True   False

  4. Why is folding 2 plus 3 into 5 always allowed?

    • Constants have no observable behaviour of their own
    • Folding makes the source file prettier
    • Constants never appear in real programs

  5. Only two registers are free for a times b plus c. What must the back end do?

    • Skip the multiplication entirely
    • Spill one value to memory and reload it
    • Ask the programmer for more registers

  6. Why must the optimiser keep a read that looks unused when a device sits behind it?

    • Reads make the program run faster
    • Devices enjoy extra attention
    • Deleting it changes what the device experiences

  7. Two statements touch different variables, but the second writes to a log file. May they swap?

    • Yes, different variables always swap safely
    • Yes, logs are invisible to observers
    • No, the log write is observable and fixes the order

  8. The optimiser swaps a device write with the computation of its value to save time. Allowed?

    • Yes, computations always move freely
    • No, reordering across a visible write is forbidden
    • Yes, writes are never observable
LightMySky · lightmysky.comW1-mt__ZSPwP4hfA-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Rearrange, but change nothing you can see W1-mt__ZSPwP4hfA-s1

  1. Whether observable behaviour stays the same · Invisible changes are free; visible ones are forbidden.
  2. Picking instructions and assigning registers · Instructions, registers, and rearrangement are back-end work.
  3. True · Independent means nobody can observe the swap.
  4. Constants have no observable behaviour of their own · The value is identical, so no observer can tell.
  5. Spill one value to memory and reload it · Every temporary needs a home, so one waits in memory.
  6. Deleting it changes what the device experiences · A device read is an observable act, not dead code.
  7. No, the log write is observable and fixes the order · The log is outside behaviour, so the order must stand.
  8. No, reordering across a visible write is forbidden · The write is visible, so nothing may cross it.
Worksheet · LightMySky