Why a Compiler Is a Mathematical System
Why is mathematics important in compiler optimisation? A compiler translates a program into another representation while trying to preserve its intended meaning. To improve the result, it builds control-flow graphs, computes sets of facts, finds fixed points, reasons about dominance and aliasing, estimates costs and proves when one expression can replace another. Graph theory, logic, algebra and discrete optimisation are everyday tools inside the translation.
The importance of mathematics appears when an unused calculation disappears, a loop becomes faster, two variables cannot safely be assumed independent, or a transformation is rejected because exceptional behaviour would change. “Optimise” does not mean “make every line shorter.” It means apply justified transformations under a model of language semantics and target hardware.
This article uses LLVM's official documentation as one open implementation reference. Languages, compiler versions and optimisation levels differ. Examples are deliberately small and separate a teaching model from production behaviour. An optimised program is not automatically correct; correctness begins with the source, specification and tests.
Quick Reading Routes
- Students: begin with expressions, basic blocks, graphs and sets.
- Parents: read the learning steps, limits, safety and career guidance.
- Teachers: use the constant-folding, liveness, dominance and loop investigations.
- Career explorers: connect this topic to programming languages, operating systems, processor design, AI accelerators, cybersecurity and high-performance computing.
Experiment only with code you own or are authorised to compile. Never run untrusted generated binaries outside a suitable sandbox, and do not assume an optimisation flag makes unsafe code safe.
Translation Must Preserve Meaning
Source and target are different representations
A compiler may transform source text into tokens, syntax trees, an intermediate representation and finally machine code. Each stage exposes different structure. A source loop becomes branches and basic blocks; a complex expression becomes smaller operations with explicit dependencies.
The translation is acceptable when observable behaviour matches the language's rules for the relevant program. Performance, code size and energy are secondary objectives constrained by semantics.
Equivalence needs a defined observation
Two programs can print the same value for one input yet differ on overflow, exceptions, input/output order or nontermination. “Same result” must specify which behaviours count.
For pure integer expressions without overflow, x + 0 = x is safe algebra. In a language with overloaded operators or observable evaluation, even apparently simple rewrites require semantic conditions.
Undefined behaviour changes the proof domain
Some languages declare certain operations undefined, allowing compilers to assume valid programs do not perform them. Programmers cannot use one accidental machine outcome as the language guarantee.
Optimisation debates should therefore cite the language model and compiler mode. Mathematics works on stated axioms; changing the axioms changes valid conclusions.
Lexing and Parsing Use Formal Structure
Tokens reduce a character stream
A lexer groups characters into tokens such as identifiers, numbers and operators. Regular-language ideas and finite automata help recognise many token patterns. State represents the relevant prefix history.
For a decimal integer, a simple automaton moves from a start state to a digit state when it sees 0–9 and remains there for more digits. A non-digit ends the token under the surrounding rules.
Grammars describe valid nesting
Programming languages need nested parentheses, blocks and expressions. Context-free grammars describe productions such as expression → expression + term or term. Parsers construct syntax trees that reflect precedence and association.
The string `2 + 3 * 4` should normally produce addition whose right child is multiplication, yielding 14 rather than 20. The tree captures structure that spacing alone cannot.
Ambiguity is a mathematical property
A grammar is ambiguous if one string has more than one parse tree. Language design or parsing rules resolve ambiguity through precedence, associativity or grammar refactoring.
Clear syntax reduces the number of possible meanings before optimisation begins. Representation is the first optimisation of human reasoning.
Intermediate Representation Makes Data Explicit
Instructions define values
An intermediate representation, or IR, breaks operations into a form suitable for analysis. A high-level expression `a*(b+c)` may become `%1 = add b,c` followed by `%2 = mul a,%1`.
Naming intermediate results creates a graph of definitions and uses. Edges express which value each instruction needs.
Static single assignment
In static single assignment form, each value name is defined once. When control-flow paths join, a phi-like operation selects the value corresponding to the predecessor path.
For `if condition then x=1 else x=2; use x`, SSA creates distinct x1 and x2, then x3 = phi(x1,x2). This makes reaching definitions explicit.
Def-use chains guide transformations
If a value has no uses and computing it has no required side effect, its defining instruction may be dead. If one definition reaches many uses, replacing it propagates along edges.
The graph avoids repeatedly scanning unrelated text. It also exposes when a value crosses branches or loops.
Basic Blocks Form a Control-Flow Graph
Straight-line regions become vertices
A basic block is a sequence entered at the beginning and exited at the end without internal branches. Branches connect blocks. The control-flow graph, or CFG, has blocks as vertices and possible transfers as directed edges.
LLVM's analysis and transform-pass documentation includes tools that print a function's CFG, call graph and dominator tree. These visualisations expose the structures analyses use.
Paths represent possible executions
An `if` creates two outgoing edges; a loop creates a back edge; return ends a path. A path through the graph is a possible control sequence under some conditions.
Not every syntactic path is feasible. Conditions can contradict each other. Proving infeasibility may enable stronger optimisation but requires more analysis.
Reachability removes dead blocks
Starting at the entry block, graph traversal marks reachable vertices. Unmarked blocks cannot execute under the CFG and can be removed if the representation is correct.
With V vertices and E edges, depth-first search runs in O(V+E). The complexity says work grows with graph size, not with every possible path, which can be exponentially many.
Dominance Captures “Must Pass Through”
The definition
Block A dominates block B if every path from the function entry to B passes through A. The entry dominates every reachable block. A block dominates itself under the usual definition.
If a value is defined in A and used in B, dominance helps determine whether the definition is available on every path to the use.
Immediate dominators form a tree
Each reachable non-entry block has an immediate dominator: its closest strict dominator. These relationships form a dominator tree. The CFG can have cycles; the dominator relation still forms a tree over reachable blocks.
This tree supports SSA construction, loop analysis and code motion. A compact structural summary answers many “always before” questions.
A diamond example
Entry E branches to L and R, which join at J. E dominates L, R and J. Neither L nor R dominates J because a path reaches J through the other side. J cannot use a value defined only in L without a merge mechanism or proof that R is impossible.
Graph drawing makes this obvious. Text order can be misleading because a block written earlier may not execute earlier.
Data-Flow Analysis Computes Sets
Facts move along edges
Data-flow analysis associates each block with facts entering and leaving it. Examples include variables live at a point, definitions that may reach a use, expressions already available, and values known constant.
A transfer function maps input facts to output facts. A meet operator combines facts from predecessors or successors. Union and intersection are common, depending on whether the analysis asks “may” or “must.”
Liveness runs backward
A variable is live if its current value may be used before being overwritten. For a block,
live_in = use ∪ (live_out − def).
Live-out is commonly the union of live-in sets of successors. The equations are solved across the CFG.
A small liveness example
Block B defines x and y, then uses x. At exit, successor C uses y. C makes y live into itself; therefore y is live out of B. Inside B, x is used after definition, while an earlier value of x may not be live in.
The exact instruction order matters. Sets alone at block granularity are expanded or interpreted carefully within blocks.
May and must differ
Reaching definitions is often a may analysis: a definition is included if it can reach along any path. Available expressions is commonly a must analysis: an expression is available only if computed and unmodified along every path.
Union models possibility; intersection models certainty. Choosing the wrong meet operator produces unsafe conclusions.
Fixed Points Make Loops Solvable
Cycles prevent one-pass answers
In an acyclic graph, facts can often be propagated in topological order. A loop feeds information back. The analysis starts with an initial approximation and repeatedly applies transfer functions until sets stop changing.
That stable solution is a fixed point: F(x) = x for the combined analysis function.
Monotonicity supports convergence
If facts come from a finite set and each iteration only adds facts under a monotone may analysis, the process must eventually stop. It cannot add new elements forever.
For a must analysis, iteration may start from a universal set and remove facts. The lattice and boundary conditions determine direction.
A reaching-definition iteration
Suppose a loop body defines d2 for x while entry supplies d1. Initially the loop header may know only d1. After one pass, d2 reaches the back edge; the next header set becomes {d1,d2}. A further pass changes nothing, so the solution stabilises.
The number of executions at runtime could be millions, but the analysis converges over a finite fact space.
Constant Folding Uses Algebra with Conditions
Compile-time values collapse
If operands are known constants, the compiler can compute the result once. `3*7 + 1` becomes 22 under ordinary integer semantics. The runtime avoids repeated work.
Folding must respect type width, overflow rules, floating-point modes and exceptions. A host compiler cannot casually use a different arithmetic model from its target.
Constant propagation uses data flow
If x is assigned 5 on every path reaching a use, replace x with 5 there. If one path assigns 6, the value is not a single constant without additional condition information.
A lattice might represent unknown, a specific constant, or overdefined. Meet rules combine predecessor facts conservatively.
Branch simplification follows
If a condition becomes certainly true, the false edge is unreachable. Removing it can expose more constants and dead code. Optimisations reinforce each other.
Pass order matters because one transformation creates opportunities for another. Repeating a pipeline has costs, so compilers organise analyses and passes deliberately.
Common Subexpressions and Value Numbering
Equivalent expressions can share work
If `a+b` is computed twice and neither operand changes, the second computation can reuse the first result. Textual equality is a clue; semantic equality requires side-effect and type conditions.
Loads are harder: two reads from memory may differ if an intervening store can affect the address.
Value numbers represent equivalence classes
Value numbering assigns the same abstract number to expressions proven equivalent. If a and b have value numbers 4 and 7, a commutative addition can be keyed by ordered pair (4,7) regardless of operand order.
Hash tables make lookup efficient, while dominance ensures a reused definition is available on the path.
Algebraic identities need caution
`x*0 = 0` is safe for many integers, but floating-point x might be infinity or NaN, and language rules may preserve signed zero or exceptions. Fast-math options change permitted assumptions.
Compiler mathematics is applied mathematics: identities live inside a semantics, not on a blackboard detached from representation.
Dead-Code Elimination Depends on Effects
Unused pure values can disappear
If an instruction's result is unused and it has no observable side effect, removing it preserves behaviour. This is a graph operation: begin from required roots and retain dependencies.
A multiplication whose result is discarded may be dead. A function call whose result is discarded may still write a file, change memory or throw an exception.
Side effects define roots
Returns, volatile operations, required stores and externally visible calls anchor the useful graph under the language and IR model. Mark-and-sweep reasoning traces operands backward.
An analysis that misclassifies an effect can miscompile the program. Conservative uncertainty keeps code that might be needed.
Debug information and observability
Optimised code can move or remove source variables, making step-by-step debugging surprising. Debug metadata attempts to connect transformed instructions back to source, but some values no longer exist at a particular point.
Optimisation changes implementation structure even when program semantics remain. Tools must communicate that loss.
Alias Analysis Protects Memory Correctness
Two names may reference one location
If pointers p and q can refer to the same memory, a store through p may change a later load through q. Reordering them without proof is unsafe.
Alias analysis answers relationships such as no alias, may alias or must alias under its model. “May” forces conservative treatment.
Mod/ref summarises effects
An analysis may report whether a function modifies or references memory reachable through a location. LLVM's pass documentation describes mod/ref analyses for particular cases.
Purity and no-alias facts enable code motion and elimination. Incorrect annotations from a programmer can make transformations unsound.
Precision has a cost
More context-sensitive or path-sensitive analysis can prove more independence but consumes compilation time and memory. A compiler chooses an engineering point between precision and cost.
The optimal analysis differs for a quick interactive build and a long production build.
Loops Offer Repeated Savings
Invariants can move out
If an expression inside a loop has the same value every iteration and moving it preserves exceptions and effects, compute it before the loop. Saving one operation repeated n times can matter more than saving one outside.
For `for i: y = a*b + i`, `a*b` is invariant if a and b do not change and the operation is safe to move.
Strength reduction changes operations
An address `base + i*8` can be maintained by adding 8 each iteration instead of multiplying anew. Modern hardware costs and instruction selection determine whether this is beneficial.
The transformation introduces an induction variable with a recurrence. Algebra proves equivalence over the loop domain.
Unrolling trades size for fewer branches
Unrolling by four duplicates the body to process four iterations per branch. It can expose instruction-level parallelism but increases code size and needs a remainder path when n is not divisible by four.
For n = 18, four full unrolled groups cover 16 iterations and two remain. Ceiling and modulo arithmetic manage the boundary.
Vectorisation packs operations
Single-instruction multiple-data hardware can add several numbers at once. Dependence analysis must prove that iterations can run in groups without violating order.
A recurrence such as `a[i]=a[i-1]+1` has a loop-carried dependence. A simple elementwise `c[i]=a[i]+b[i]` does not, assuming non-aliasing arrays.
Cost Models Decide Whether Legal Is Useful
A valid transformation can be slower
Inlining removes a call boundary and exposes optimisation, but duplicates code. Larger code can harm instruction-cache behaviour. Vectorisation can require shuffles and remainder handling that outweigh benefits for short arrays.
Legality asks “may we?” Profitability asks “should we?” They are different proofs.
Weighted cost estimates
A simple model might estimate cycles, code bytes, memory operations and branch penalties:
cost = aC + bB + cM + dP.
Weights depend on target processor and optimisation goal. Optimising for size uses different weights from optimising throughput.
Profiles provide probabilities
Profile-guided optimisation measures which paths and functions are frequent. If branch A occurs 99% of the time, layout can favour it. The profile is a sample; future workloads may differ.
Stale or unrepresentative profiles can make decisions worse. Record input and date, and validate the deployed workload.
Pass Managers Track Invalidated Knowledge
Analyses are cached results
Computing a dominator tree or alias summary costs time. A pass manager can cache the result and reuse it until a transformation invalidates its assumptions.
LLVM's New Pass Manager documentation explains preserved analyses: a pass reports which analysis results remain valid after its changes.
Mutation creates dependencies
If a pass changes control flow, the old dominator tree may be wrong. If it changes only arithmetic inside a block, CFG analyses may remain valid. Correct invalidation is like cache coherence: stale derived data is dangerous.
The mathematics of dependency tracking prevents an optimisation framework from using proofs about an earlier graph as though the graph had not changed.
Pipeline order is a planning problem
Pass A may expose an opportunity for B, while B may destroy information useful to C. Some passes repeat. Compile time places a budget on the search.
There is no simple universal order for every language and target. Compiler teams test pipelines across benchmark suites and real workloads.
Register Allocation Is Graph Colouring
Live ranges interfere
Two values whose live ranges overlap cannot occupy the same register. Build an interference graph with values as vertices and edges between simultaneously live values.
Assigning k physical registers becomes a graph-colouring problem: adjacent vertices need different colours. General graph colouring is computationally difficult, so allocators use heuristics, splitting and spilling.
Spilling moves values to memory
If not all live values fit, some are stored in memory and reloaded. Spilling reduces register pressure but adds instructions and traffic.
Choosing a spill candidate considers use frequency, loop depth, rematerialisation cost and interference. The vertex with most edges is not always the best victim.
Calling conventions add pre-colours
Some values must use particular registers for calls or instructions. These vertices are pre-coloured, constraining neighbours. The problem combines fixed rules and flexible assignments.
This is a rich example of school graph colouring becoming a practical resource-allocation tool.
Instruction Scheduling Is a Dependency Problem
Operations have latencies
If multiplication result M feeds addition A, A cannot use the value before it is ready. Independent instructions can fill the delay. A dependency DAG and resource model guide scheduling.
The critical path—the longest weighted dependency path—sets a lower bound on completion even with unlimited parallel resources.
Hardware resources are limited
A processor may issue only certain combinations per cycle. Scheduling must respect both data dependencies and functional-unit capacity.
This resembles classroom timetable planning with prerequisites and limited rooms. Moving one task can create a conflict elsewhere.
Static and dynamic scheduling coexist
Compilers arrange instructions statically, while processors may schedule dynamically at runtime. The compiler's model is an approximation of the target.
Good code generation cooperates with hardware rather than assuming it can predict every cache miss or branch outcome.
Numerical Optimisation Needs Error Analysis
Floating-point rearrangement changes rounding
Real-number algebra says a+b+c is associative; floating-point addition may not be. Reordering a reduction or fusing operations can change the last bits.
Strict modes preserve defined behaviour; relaxed modes permit more transformations. Users must choose based on application tolerance.
Fast is not scientifically valid by default
A simulation should compare optimised results with a trusted reference and domain-specific acceptance criteria. Absolute error, relative error and conservation laws provide different evidence.
One passing example is insufficient. Test extreme magnitudes, cancellation and special values.
Integer overflow also matters
Signed overflow semantics differ among languages and modes. Replacing `(x+y)-y` with x assumes the intermediate operation has permitted behaviour.
The optimisation proof must include the type domain, not only symbolic algebra.
Security and Side Channels
Constant-time intent can be disrupted
Cryptographic code may avoid data-dependent branches and memory accesses. An optimiser that does not know this security requirement could transform code in ways that reintroduce timing variation.
Projects use specialised primitives, compiler support and verification. Ordinary source appearance is not enough to prove constant-time machine behaviour.
Removing checks can be correct under assumptions
If prior analysis proves an array index is in bounds, a redundant check may be removed. If the proof relies on undefined behaviour or an incorrect annotation, the result becomes dangerous.
Security review follows the whole chain: source, compiler flags, target, generated code and runtime environment.
Supply-chain trust includes the compiler
A compiler is powerful software processing other programs. Reproducible builds, signed releases and diverse verification can reduce some risks.
Version control history alone does not prove the binary corresponds to reviewed source. The build process is part of the trust model.
A Complete Worked Example: Optimising a Loop
The source model
Consider a loop over n elements computing `out[i] = scale*(a[i]+b[i])`, while also recomputing `limit = width*height` inside every iteration even though width and height do not change.
The compiler identifies the loop CFG, induction variable i and invariant expression width*height. If multiplication has no changing operand or required repeated effect, it can move before the loop.
Prove memory independence
To vectorise, the compiler needs confidence that writing `out[i]` does not change later reads from a or b. If pointers may alias, it might generate a runtime overlap check or keep a scalar version.
The proof is about address sets. For each iteration, write set W_i should not intersect future read sets under the chosen ordering.
Choose a vector width
Suppose hardware handles eight floating-point lanes. For n = 1,003, 125 full vectors cover 1,000 elements and a remainder handles three. The vector path performs 125 grouped additions and multiplications at the IR level, though machine instruction counts depend on target details.
Alignment, loads and stores affect profitability. A cost model compares vector setup and tail cost with scalar work.
Check numerical behaviour
The transformation preserves element order within each formula, but fused multiply-add could round once instead of twice if enabled. Tests use a tolerance based on application needs and include infinities, NaNs and large values where relevant.
The team inspects generated IR and measures end-to-end runtime on representative data. A faster microkernel is useful only if input/output and surrounding work do not dominate.
Record the result
They report compiler version, target CPU, flags, n distribution, number of trials and validation criteria. They avoid claiming a universal speed-up from one machine.
This completes the optimisation loop: model, prove legality, estimate profitability, transform, validate and measure.
Common Misconceptions to Correct
“A compiler just translates one line at a time”
Modern compilers analyse whole functions, graphs and sometimes multiple modules. Meaning depends on control and data relationships.
“Optimisation always makes code faster”
Cost models are predictions. A legal transformation can hurt a different workload or target. Measure representative results.
“Algebraic identities are always safe”
Types, overflow, floating-point rules, exceptions and side effects constrain identities.
“More optimisation levels mean more correctness”
Optimisation should preserve defined semantics, but it does not repair source bugs. Higher levels may expose undefined behaviour that appeared harmless before.
“No source variable means the debugger is broken”
Optimisation can remove or merge values. Debug information approximates a mapping from transformed code back to source.
“Machine code proves the source was safe”
Safety depends on specifications, inputs, compiler assumptions, libraries and runtime. Generated code is one layer.
How Students Can Build Transferable Skill
Draw a CFG
Take a short program with one `if` and one loop. Divide it into basic blocks and draw possible transfers. Mark entry, exit and back edge.
List reachable blocks and identify which blocks dominate the join. Compare the graph with textual order.
Solve liveness by hand
For each block, list `use` and `def` sets. Start live-out sets empty and iterate the equations until no set changes. Record each round.
This makes fixed points and backward reasoning concrete.
Test algebra under finite arithmetic
Use a tiny four-bit signed number model. Check identities near overflow. Then compare floating-point addition orders with large and small magnitudes.
The exercise shows why domains belong in proofs.
Inspect an authorised compiler
Compile a disposable program at different optimisation levels and view its IR or assembly using official tools. Predict which expressions disappear or loops change.
Do not equate shorter output with better code. Measure and validate behaviour.
Guidance for Parents and Teachers
Use flowcharts before jargon
Students understand branches, loops and prerequisites from daily life. Turn a decision process into a graph, then introduce compiler terms.
Ask “What must be true on every path?” and “What may be true on at least one path?” to distinguish must and may analyses.
Reward proof obligations
A strong optimisation report states the original semantics, preconditions, transformed form and counterexamples outside the conditions. Speed measurements come after legality.
This encourages careful reasoning rather than magic-flag experimentation.
Include uncertainty
Cost models and profiles can be wrong for future inputs. Students should separate a proven equivalence from an empirical performance claim.
Mathematics Learning in Singapore
The MOE secondary mathematics syllabuses emphasise problem solving, algebraic reasoning, algorithms and communication. Compiler analysis applies these habits through graphs, sets, recurrences, inequalities and proof.
The official MOE Computing teaching and learning syllabus discusses decomposition and algorithmic thinking. Students can explore compiler ideas through flowcharts and set tables before advanced coding.
SEAB states that the Singapore-Cambridge Secondary Education Certificate begins in 2027 with G1, G2 and G3 subjects; use the SEC information page for current cohort terminology. This is enrichment, not an examination promise.
Did You Know?
A compiler can analyse a loop that may run a billion times by finding a fixed point over a small finite set of facts, rather than simulating every iteration.
Register allocation resembles colouring a graph: values alive at the same time need different colours, and spilling occurs when the available palette is insufficient.
An optimisation can be mathematically legal yet slower because code size, caches and input distribution change the real cost.
Frequently Asked Questions
What mathematics do compiler engineers use?
Graphs, sets, logic, algebra and algorithms are fundamental. Probability, optimisation, automata and numerical analysis become important in specialised areas.
What is a control-flow graph?
It is a directed graph whose vertices are basic blocks and edges are possible transfers of control.
What is a fixed point?
It is a state unchanged by another application of the analysis function. Iteration reaches it when data-flow facts stabilise.
Why can optimised debugging look strange?
Instructions and variables may be moved, combined or removed while defined program behaviour is preserved.
Is generated assembly always faster when shorter?
No. Instruction latency, parallelism, memory behaviour and target hardware matter. Measure representative workloads.
Can a compiler prove every program correct?
No. Compilers verify some structural and type properties and preserve semantics under assumptions. General program correctness needs specifications, tests and sometimes formal verification.
Does compiler knowledge guarantee a job?
No. It can support study and specialised careers, alongside programming, architecture, operating systems, communication and experience.
Useful Next Reading
- Read LLVM's analysis and transform passes, New Pass Manager and Writing an LLVM Pass.
- Connect dependency scheduling to CPU scheduling, clock cycles, run queues and response time.
- Compare data locality with computer memory, addresses, cache hits, latency and bandwidth.
- Extend graph reasoning through version control, commit graphs, hashes and merging.
- Review the MOE secondary mathematics syllabuses for curriculum context.
Final Perspective
Compiler optimisation shows why mathematics matters between human ideas and machine execution. Graphs represent possible paths, sets carry facts, fixed points solve cycles, algebra justifies rewrites and cost models choose among legal alternatives.
The essential question is not “Can this line be removed?” It is “Under what semantics, on every relevant path, with which effects and numerical rules, is the transformed program equivalent—and is the change profitable on the target?”
That question combines rigour with engineering judgement. It teaches students that faster software is not produced by guessing, but by building a model, proving what is safe, measuring what is useful and communicating the limits honestly.