Rearrange, but change nothing you can see

Computing · Computer Systems · ages 21-22

Name ______________________ Date ____________

What decides whether an optimiser's proposed change is valid?
- It preserves behaviour required by the language and platform
- It reduces instruction count even if required output values change
- It reduces register use even if required device effects disappear
Which tasks belong to the compiler back end?
- Recognising source tokens and building their grammatical tree
- Resolving source declarations and checking function argument counts
- Selecting target instructions and assigning values to registers
Two local integer sums may swap if they are independent, cannot overflow or trap, and have no observable effects.
Circle one: True False
In the exact-integer model, 9 + 3 has no side effects or traps. Why may the compiler replace it with 12?
- The replacement has the same value and required effects
- Every shorter expression is valid even if its computed value changes
- Every constant expression is ignored whenever the program executes
LOAD R,[x] loads x into R; MUL R,S and ADD R,S overwrite R with R*S and R+S. To compute a*b+c, run LOAD R1,[a]; LOAD R2,[b]; MUL R1,R2. b is no longer needed. Which continuation leaves a*b+c in R1 without spilling?
- LOAD R1,[c]; ADD R1,R2, leaving the result in R1
- LOAD R2,[c]; ADD R1,R2, leaving the result in R1
- ADD R1,R2; LOAD R2,[c], leaving the result in R1
A platform requires a device read that clears a set event flag. Its returned value is unused. Why must the optimiser retain it?
- Unused return values make all memory reads permanent requirements
- Every device read produces a value needed by the next instruction
- Removing this read would leave the required event flag uncleared
Single-threaded code sets local t = a+b, then logs fixed text. Neither statement can fail or transfer control; the sum cannot overflow and has no effects. The log does not use t. No shared-state or timing observation is allowed. May they swap?
- No; every log write prevents all earlier local computation from moving across it
- No; using different variables automatically creates a required data dependency
- Yes; t's value and the required log effect stay the same
value starts at 0. The program computes value = 4*3, then writes value to a device. An optimiser swaps these statements without changing either. Is that valid?
- Yes; retaining the same two statements means their order cannot change device behaviour
- No; the swapped program writes 0 instead of the required computed value 12
- Yes; the later multiplication changes the value the device already received

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

It preserves behaviour required by the language and platform · Less work does not justify changing a required value or observable effect.
Selecting target instructions and assigning values to registers · The back end translates the intermediate form using target instructions and registers.
True · Under these conditions, neither the computed values nor required effects depend on their order.
The replacement has the same value and required effects · 9 + 3 equals 12 under the stated rules, with no additional effects to preserve.
LOAD R2,[c]; ADD R1,R2, leaving the result in R1 · R1 holds a*b. Reuse R2 for c, then add it to R1 without overwriting the product.
Removing this read would leave the required event flag uncleared · Clearing the flag is a required effect, separate from using the returned value.
Yes; t's value and the required log effect stay the same · Neither statement depends on the other. Both complete normally, and swapping them preserves t's value and the fixed log effect.
No; the swapped program writes 0 instead of the required computed value 12 · The original writes 12. The swapped program writes 0, then computes 12 too late for that write.