The short answer
A transformation can make code shorter and still make it wrong. These original examples show why a compiler needs evidence about paths, definitions and observable behaviour before it changes a program.
Original teaching comparison
Which fact is still missing?
The same textual expression does not always denote the same usable value.
| Country | Proposed change | Required evidence |
|---|---|---|
| Unchanged a and b | Reuse t for the second a + b. | Inputs and stored t retain their values; evaluation has no effects. |
| a changes between uses | Reuse the earlier t. | Not justified in the worked example: the final result changes from 6 to 5. |
| Two branches define x | Replace the output by a fixed constant. | The chosen constant must be valid on every reaching path. |
| A loop may execute zero times | Compute a division before the loop. | Added evaluation must not introduce an error or other changed behaviour. |
Chronology
A timeline of the turning points
Control-flow analysis
Allen published graph methods with explicit credit to prior work and Cocke’s intervals.
Data-flow procedure
Allen and Cocke described definitions reaching uses and remaining live.
Parallel translation research
Allen later led the PTRAN research group.
Start with a representation of possible execution
Allen’s 1970 Control Flow Analysis described a directed graph of basic blocks and transfers of control. A basic block has one entry and one exit, although the block may have several possible predecessors or successors. The paper used graph relationships to organise global analysis and credited John Cocke with its interval construct. This was part of a wider field with earlier matrix and dominance methods. A graph matters because the next instruction written on a page is not necessarily the next instruction executed after a branch or loop.
Sources for this section: [1]
A definition is an assignment whose value may reach a use
Allen and Cocke’s 1976 paper asked which definitions could supply values at later program points and which remained live because later uses could need them. Its opening page credited Kenneth Kennedy with live analysis and Richard Stasko with implementation data-structure ideas. IBM’s abstract confirms that the procedure handled reducible and irreducible flow graphs. Those are historical claims about an analysis procedure, not a promise that it would find a uniquely fastest version of every program.
Original example: reusing a calculation with unchanged inputs
For the teaching examples here, assume ordinary variables, exact unbounded integer arithmetic, no concurrent writes and no hidden effects from reading a variable. Start with a = 2, b = 3. Execute t = a + b, followed immediately by u = a + b. Replacing the second assignment with u = t preserves u = 5 under these rules. The previously computed value remains valid because neither input changed and t was not overwritten. This is a small illustration of a proof obligation, not a transcription of Allen and Cocke’s implementation.
A small intervening assignment invalidates that reuse
Now execute t = a + b; a = a + 1; u = a + b. With the same initial values, t becomes 5 but the final u becomes 6. Replacing the final expression with t produces 5 and changes the result. Seeing the same expression twice is insufficient: the relevant definitions of a differ. A branch adds another question. In x = 1; if flag then x = 2; output x, both assignments can reach the output along different paths. Substituting 2 at the output fails when flag is false.
An invariant expression can still be unsafe to move
Consider a language in which division by zero raises an error. A loop says: for each item in items, compute q = 10 / d and use q with the item. Suppose items is empty and d is zero. The original loop performs no division and finishes. Moving q = 10 / d before the loop introduces an error. The operands being unchanged inside the loop is therefore insufficient to justify motion: the transformed program also evaluates the expression on an execution where it previously did not run. A proof must address that added evaluation or preserve the original guard.
Sources for this section: [1]
A short reading exercise and answer
Exercise: a reviewer proposes replacing every repeated expression by its earliest computed value. Name two questions the compiler must answer, and explain why a speed measurement cannot answer them alone. Use the examples above rather than guessing how a current compiler behaves.
Sources for this section: [1]
What a correct justification must show
Suggested answer: the compiler must establish whether the inputs still have the same relevant values on every path reaching the later use, and whether moving or removing the computation changes observable behaviour. The zero-iteration loop shows why evaluation and errors matter alongside numerical values. A benchmark might run only a non-empty loop with a nonzero divisor, missing that case entirely. It can help measure a permitted transformation’s cost on tested inputs; it cannot prove equivalence for all allowed executions. These exercises deliberately fix arithmetic and effect rules. Floating-point rounding, overflow, aliases, calls and concurrency would add further obligations.
Keep the analysis, transformation and measurement distinct
Allen’s later PTRAN account describes an experimental compiler used to assess interacting analysis and parallelisation techniques. That practical setting illustrates three questions a reader should keep separate: what information is established about the program, which changes that information permits, and whether the permitted version performs better under a specified cost measure. An optimisation need not produce the mathematical optimum. The historical papers and the examples here explain the reasons for analysis; this guide does not validate a contemporary compiler or reproduce the full 1976 algorithm.
Sources for this section: [4]
Connected biographies
People and research
1932–2020
Frances Allen
Computer scientist, compiler researcher and technical mentorFrances Allen developed ways to analyse programs so compilers could improve their execution. Her work with John Cocke and research teams at IBM connected mathematical descriptions of programs with working systems and parallel computing.Read biography1925–2002
John Cocke
Computer scientist and computer-architecture researcherJohn Cocke linked compiler design with computer architecture at IBM. His collaborations helped establish program-analysis methods and the IBM 801 design, showing why hardware instructions and the software generating them should be considered together.Read biographyQuick answers
Common questions
- Does optimisation mean a compiler has found the fastest possible program?
- No. A compiler may improve a chosen cost under particular conditions without proving a global optimum.
- Is a repeated expression always safe to replace with an earlier result?
- No. Its inputs, execution paths and relevant effects must support the replacement.
Primary and institutional sources
How this history was checked
Original records and institutional histories support the historical account. Worked exercises are newly written teaching examples, not historical programs, measurements or experimental results. This article was reviewed on 27 October 2026.
- Frances E. Allen; Columbia-hosted originalControl Flow Analysis (1970), introduction and basic concepts
- F. E. Allen and J. Cocke; ACMA Program Data Flow Analysis Procedure (1976), original opening page
- IBM Research1976 paper abstract and bibliographic record
- Computer History MuseumOral History of Fran Allen (2008): PTRAN account