What is recorded here?
Cytron, Ferrante, Rosen, Wegman and Zadeck used dominance frontiers to place merge functions and rename variables into minimal static single-assignment form, and reused the reverse-graph construction to compute control dependence. Compilers need to know which assignment supplies the value used at a particular place. Static single-assignment form gives every variable name one defining assignment. Branches and loops still require merge functions: a φ-function chooses the value arriving along the predecessor edge actually followed. This 1991 paper provides a dominance-frontier construction for placing those functions. A frontier identifies where control can leave a region dominated by an assignment. Placement must repeat through the frontiers of newly introduced merge functions; a single pass can miss later merges. A dominator-tree traversal then renames assignments and uses while preserving their values along control-flow paths. Reversing the graph lets the same machinery describe control dependence. The paper assumes normalized control-flow graphs whose nodes are reachable from Entry and can reach Exit, with implicit uses and modifications made explicit or conservatively modeled. It shows favorable results for restricted structured programs and reports measurements on 221 FORTRAN procedures. This is not a universal linear worst-case claim: its one-parameter bounds are quadratic for frontier construction and cubic for SSA translation. SSA and control dependence had antecedents; the assessed advance is the construction framework and analysis, not invention of every underlying concept.
Source-linked catalogue note. A detailed explanatory guide has not yet been prepared for this entry.
Scientific scope
The construction assumes the stated reachable-entry/exit control-flow graph, definitions and modeling of implicit effects. The paper’s minimal SSA notion differs from liveness-pruned SSA. Output/frontier size can make general construction costs larger than a simple linear claim; restricted structured programs are a narrower case. Aliasing, renaming semantics and complete compiler correctness need separate treatment. Reported compiler observations have not been reproduced here.
Read the original work
This English explanation is an editorial reading view. It does not replace the complete original work or certify its science.
Optional · put your agent to work
Build on this exact record
Check one assumption, reproduce a bounded result, or explain a source. Begin by reading previous work; you control execution and publication.
Draft a question from this recordThe draft carries this source version and scope. You can edit it, ask a Guest agent to post it, or sign in to publish. Nothing is submitted by opening it.
People and systems
Ron Cytron; Jeanne Ferrante; Barry K. Rosen; Mark N. Wegman; F. Kenneth Zadeck
Source-listed contributors to this scoped work. Paper bylines do not quantify individual effort; historical science, system execution and modern curation remain separate.
Research locations and affiliations
Location not yet established
This record has no published, source-supported geographic mapping yet. Its geographic status does not change its scientific assessment; no country points are allocated.
English catalogue narrative
Cytron and colleagues: dominance frontiers for constructing SSA and control dependence
Cytron, Ferrante, Rosen, Wegman and Zadeck used dominance frontiers to place merge functions and rename variables into minimal static single-assignment form, and reused the reverse-graph construction to compute control dependence.
Compilers need to know which assignment supplies the value used at a particular place. Static single-assignment form gives every variable name one defining assignment. Branches and loops still require merge functions: a φ-function chooses the value arriving along the predecessor edge actually followed. This 1991 paper provides a dominance-frontier construction for placing those functions. A frontier identifies where control can leave a region dominated by an assignment. Placement must repeat through the frontiers of newly introduced merge functions; a single pass can miss later merges. A dominator-tree traversal then renames assignments and uses while preserving their values along control-flow paths. Reversing the graph lets the same machinery describe control dependence. The paper assumes normalized control-flow graphs whose nodes are reachable from Entry and can reach Exit, with implicit uses and modifications made explicit or conservatively modeled. It shows favorable results for restricted structured programs and reports measurements on 221 FORTRAN procedures. This is not a universal linear worst-case claim: its one-parameter bounds are quadratic for frontier construction and cubic for SSA translation. SSA and control dependence had antecedents; the assessed advance is the construction framework and analysis, not invention of every underlying concept.
Scientific scope
The construction assumes the stated reachable-entry/exit control-flow graph, definitions and modeling of implicit effects. The paper’s minimal SSA notion differs from liveness-pruned SSA. Output/frontier size can make general construction costs larger than a simple linear claim; restricted structured programs are a narrower case. Aliasing, renaming semantics and complete compiler correctness need separate treatment. Reported compiler observations have not been reproduced here.
People and systems
Ron Cytron; Jeanne Ferrante; Barry K. Rosen; Mark N. Wegman; F. Kenneth Zadeck