◄ WORLD V · SONNY 5DART 232 · a helldive at the net

THE DEF-USE CHAIN every value: where it is born, everywhere it is read

A def-use chain links each definition of a variable to every place its value is read before being overwritten. It is the wiring diagram of data: follow it and you know exactly which assignment feeds which use. Almost every optimization needs it — dead-code elimination asks “does this def have any uses?”, constant propagation asks “do all defs reaching this use agree?” When a variable is assigned exactly once (static single assignment, SSA), the chains are unambiguous: one def, a clean fan-out of uses, no question about which assignment you mean.

THE TECHNIQUE link each definition to every downstream read

A short instruction stream reads operands by id. Pick a variable; the demo finds every use of that definition — its def-use fan-out: live demo







  
HISTORY & CREDIT Allen & Cocke, 1970s

  
“The compiler reads variables like you do, by name.” — it reads them by definition. Two assignments to the same name are two different values; a use belongs to whichever def reaches it. The chain, not the name, is the truth of the dataflow. cited

  
1970s · Frances Allen & John Cocke — use-definition and def-use chains as the data-side companion to the control-flow graph.
1988 · Rosen, Wegman & Zadeck — introduce static single assignment (SSA) form (“Global value numbers and redundant computations”, POPL): every variable a single definition, so each chain has exactly one source.
1991 · Cytron, Ferrante, Rosen, Wegman & Zadeck — the efficient construction of SSA via dominance frontiers (TOPLAS) — what made it the modern default IR.
now · LLVM, GCC, V8 all build on single-assignment def-use.

  
Single assignment is the clean case: one def, a fan of uses, no ambiguity about which value a use reads. A language whose bindings are written once is already halfway to SSA. Rosen-Wegman-Zadeck 1988






  
RECOMMEND FOR I-13 uses of a single-assigned variable, computed

  
On the canonical compiler, variable v1 in a six-instruction stream is read at three sites — a clean three-use chain from one definition:

  
$ i13 run defuse.i13   # count uses of v1 in the stream
n_uses = 3          -- v1 is defined once and read at ops 0, 2, 4

  
Recommend: def-use is near-free in I-13 — its globals are single-assignment (a global re-assign is rejected, E0302) and its I x <- e bindings name one value, so i13 is already close to SSA: every definition has one source and a clean fan of uses. The hardest precondition of the classical optimizer — unambiguous chains — i13 gets by construction, the same way it got honest verification: by writing values once.