Code Generation and What an Optimiser May Change
The back end translates an intermediate representation into target instructions and assigns registers. Optimisations preserve behaviour required by the language and platform. Data dependencies, arithmetic rules and required device effects constrain which changes are valid.
What a learner can do afterwards
- Hand-generate instructions for a small expression and assign registers to the temporaries
- Name two transformations an optimiser is allowed to make and say what justifies each
- Explain why an apparently unused device read must remain when the language and platform require its observable effect
1 · Read
You studied how a front end produces an intermediate representation. The back end selects target instructions and assigns registers to values. Optimisation can remove or rearrange work only while preserving behaviour required by the language and platform. The ISA supplies instruction meanings, which determine whether a register assignment and instruction sequence work.
Use valid ordinary-memory loads in this teaching ISA. LOAD R,[x] loads x; MUL R,S and ADD R,S overwrite R with R*S and R+S. For p*q+r, load p into R1 and q into R2, then multiply into R1. Reuse R2 for r and add. Two registers suffice because q is no longer needed after multiplication. A spill temporarily stores a value in memory when it cannot remain in an available register.
Observable behaviour includes required outputs, return values and device effects. Constant folding replaces a constant expression with its result when the value and required effects stay the same. In our exact-integer examples, 5 + 6 can become 11. This does not permit changing floating-point rounding, overflow behaviour or exceptions.
Check dependencies and effects before swapping statements. Independent local integer sums may swap if they cannot overflow or trap and have no effects. In a single-threaded model with no observable timing, an unrelated sum may cross a fixed log write if neither can fail or transfer control and the log does not use the sum. Preserve both values and the required log effect. A visible write alone does not forbid the move.
Some device reads have effects even when their returned value is unused. Suppose the language and platform require a read that clears a currently set event flag. Removing it leaves the flag set, changing device behaviour. Preserve the required read and its required ordering. An ordinary unused read without such effects follows different rules.
A write must receive its required value. For value = 6 + 2 followed by a device write of value, writing an earlier value before doing the addition changes what reaches the device. Preserve that dependency, or use another sequence sending the same required value. Judge transformations by their values and effects.
Reuse registers when earlier values are no longer needed. Preserve required values, effects and ordering when folding constants or moving computations.
Lesson, questions and flashcards on code generation and optimisation written for this dataset.
2 · Watch
به انگلیسیTake it off screen
Where it sits
Learn first
Optional connections
This opens up
Nothing builds on it yet.
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.