Author: Asher Wolfstein
Published under the auspices of the University of Neo-Transylvania Experimental Research
This is Part 6 of a proposed 18-part series titled Failed Abstractions: Interfaces Gone Wild.
An Intermediate Representation (IR) is a carefully selected description of a program, being designed in such a way that a certain set of questions can more easily be posed and answered. A typed tree makes the declarations, the applications, and the properties that are inferred explicit; a control-flow graph makes the various transfers of execution available for use in data-flow analysis; in Static Single Assignment (SSA) form each value definition is given a separate name and the merging of values is carried out using explicit functions; a target-oriented representation shows the registers, the addressing modes, and the instruction constraints. Since compilers have reached a mature stage, they usually use more than one of these forms because no single representation can simultaneously provide an efficient description of syntax, types, control, data dependence, exceptions, memory, and target legality.
Bottom-Driven Semantic Monotonicity is the proposed framework concerned with the construction of a layered machine state (a Machine Tower) such that Dominant (higher) artifacts (Dominances) maintain explicit support for Submissive (lower) artifacts (Submissions), Project consistently into the Submachine state, keep the behavior that has been inherited, and define new actions by means of the Submissive accounts (Submissions) by way of the Dominance Condition. If this method is used for Intermediate Representations (IR), it is not required that each compiler pass use a single universal tree, but it is not ruled out either. On the contrary, the proposed framework seeks to determine whether the subsequent representations constitute replacement identities for the program using metadata, or whether they are views and plans with valid interrelationships within a single machine account.
As I elaborate on the proposed framework, the ultimate revelatory goal is to show that these interrelationships can be implicitly embedded within the abstractive framework, demonstrating the resultant Machine Tower as this unified account.
The Engineering Rationale Behind More Than One Form
Though the surface-syntax parse tree (or Abstract Syntax Tree, AST) is a tree that keeps information relevant to diagnosis as well as to the structure intended by the author, it often obstructs analysis that demands canonical control or explicit effects. A statement with a while-loop, a conditional expression, a premature return, an exception handler, and a short-circuit boolean operator are all indicative of control transfer in different syntactical forms.
However, the implications can be represented as simply edges in a control flow graph. A mutable variable may be assigned values at more than one point; the Static Single Assignment (SSA) form renames each definition and shows how values converge via a merge operation, thus making the define-use relationships direct. Finally, a target representation incorporates physical constraints that would make high-level analysis difficult if they were present from the start.
There’s nothing ‘wrong’ with these representative forms within the proposed framework. The issue isn’t that there are multiple forms per se. Each form is an artistic achievement, technically, in defining relevancy constraints so that useful information can be extracted most efficiently.
These representations grant modularity, reuse, and tractability through their translation-based abstraction and have traditionally delivered the end product with sufficient efficiency that their asymmetry remains, in the general commercial sense, unexamined. A frontend can translate many source languages into a common form; the different optimization passes can function independently of the surface grammar; a backend can support several frontends; and local invariants can be set up, for instance, the rule that every SSA use must be dominated by its definition.
Hence the argument put forward in this series should not be interpreted as asserting that the use of multiple IRs shows a lack of care in the design. The danger comes from the fact that local utility can easily become local ontology. Each representation determines what counts as a program object, and the compiler allows previous identities to vanish when the next stage no longer requires them.
A Single Expression Across Four Intermediate Representations
Consider this hypothetical function, with left-to-right evaluation and a source-level division exception:
choose(x):
if x != 0 then
return 100 / x
else
return fallback()
Code language: JavaScript (javascript)A syntax-based representation could include the if statement, the two return statements, the ranges of the literal and the identifier, and the information that / represents checked integer division. The reduced typed tree could be expressed as:
Function choose(x: Int) -> Int
If NotEqual(Ref(x), Int(0))
Return DivideChecked(Int(100), Ref(x))
Return Call(Ref(fallback), [])
Code language: PHP (php)Control-flow representation organizes the same story into executable segments, showing how execution proceeds in each:
entry:
t0 = compare_ne x, 0
branch t0, nonzero, zero
nonzero:
t1 = div_checked 100, x, on_error=division_error
jump exit(t1)
zero:
t2 = call fallback
jump exit(t2)
exit(result):
return result
Code language: PHP (php)An SSA-oriented representation may replace the parameterized exit with explicit value merging:
exit:
result = phi [t1, nonzero], [t2, zero]
return result
Code language: PHP (php)Target-oriented representation may include condition codes, information on register classes and call-clobbering registers, an exception table, and target division-instruction trap behavior that should be compatible with source exception-trap behavior:
machine_function choose:
argument x: RDI ; register class: general-purpose 64-bit
return value: RAX ; register class: general-purpose 64-bit
calling_convention: SystemV_AMD64
entry:
sub rsp, 8 ; align stack for a possible call
test rdi, rdi ; defines condition flags; ZF := (x == 0)
jz zero ; consumes ZF
; otherwise fall through to nonzero
nonzero:
mov eax, 100 ; sets RAX to 100, including upper bits
cqo ; sign-extend RAX into RDX:RAX
division_site:
idiv rdi ; signed RDX:RAX / RDI
; quotient -> RAX; remainder -> RDX
; condition flags become undefined
; may raise hardware divide error (#DE)
jmp exit
zero:
call fallback ; result -> RAX
; clobbers ABI caller-saved registers
; x is no longer needed after this call
; fall through to exit
exit:
add rsp, 8
ret ; returns the value already in RAX
There may also be duplication or splitting of blocks following scheduling. At this point, there is no one-to-one relationship between target and source objects: the source conditional is realized through machine branches and block layout; the merged result is realized through register placement; and exception semantics are enforced through instructions, compiler proofs, and runtime metadata.
Each form presents a “truth” that is coherent within its local context. The typed tree identifies the source construct and selected numeric operation. The control-flow graph shows the possible paths. SSA shows the dependencies between values. The target form shows the constraints that must be met for executability.
A fracture occurs when the sequence is treated as if each truth consumes the one that comes before it and then becomes the complete program for its own domain.
After the exit merge, the source return nodes may have no corresponding element; the SSA phi function did not appear in the source code and may disappear during later lowering; the target exception edge may not be present in the normal instruction stream. Although debug metadata tries to establish relationships between these objects, if those relationships are not included in the validity conditions of the various passes, they may be only approximate, discarded, or repaired, since the causal transformations’ main responsibility was to ensure executable correctness. Once again, reconstruction is unnecessarily opaque by design, a choice I argue need not, and should not, be made.
Semantic Preservation And Explanatory Gaps
A typical IR transition establishes a relationship that goes beyond mere syntactic resemblance. The typed tree and the control-flow graph should include corresponding paths and effects; the construction of the SSA form should retain the possible values linked to mutable variables; and the process of target legalization should preserve the Dominant operation under the semantics of the Submachine. Formally, it is possible to define a simulation or observational equivalence among the various stages, demonstrating that every behavior of a later stage corresponds to an allowed behavior of an earlier stage. Such a definition can be rigorous yet remain intentionally selective.
The selection is the key differentiator so far. An intermediate control-flow representation can normalize the order in which the source is evaluated while omitting lexical scopes irrelevant to execution and user-defined statement boundaries. The SSA process can preserve value semantics while changing both the number and the identity of the apparent variables. A target form can maintain the externally visible results even though it changes the location of faults, the internal calling structure, and the timing.
For each pass that uses a given view, such omissions can be justified. The problem manifests, as viewed through the proposed framework, when the later artifact inherits authority over questions whose relevant distinctions were omitted upstream, or when an explanation traverses several locally sound relations whose composition was never made explicit.
By way of example, the optimizer could decide that x is non-zero in the non-zero block and then use an unchecked divide operation, relying on the presence of control-flow dominance and target trap rules. When a diligent programmer queries the debugger about a failed division, its investigation must establish a connection among the physical trap, the unchecked instruction, the range proof, the branch fact, the source condition, and the commitment to a checked exception at the source level. Should these facts be stored in different archives, an explanation of the problem would span several realms, and in some cases where earlier versions have been deleted, pieces of information would only be in the logs.
Four Stage-Relative Consequences
The astute reader might’ve noticed by now, the author hopes, that in the series so far, all four consequences are present, and it’s looking like that may be the template. For more information on these consequences, see Translation As A Transfer Of Semantic Authority.
Semantic Drift happens when the properties of a representation gradually change the criteria for what should be preserved. For example, a Dominant IR might model exceptions as explicit edges, whereas a Submissive IR would represent only selected traps; the memory model may be weakened during the process of lowering (see Compilation And Lowering); and a target legalization pass might introduce calls that have effects which were not present in the previous operation. Even though each stage can still be internally well-formed, the overall composition causes the observations under which the original construct was understood to change.
Unclear responsibilities stem from the modularity IRs typically offer, and we recognize these as an example of Opaque Responsibility. If an incorrect result occurs, the IR producer can say that its output met the declared invariant, the transformation pass can state that it preserved its local relationships, and the backend can claim that the result is legal for the target. However, the error might be due to an unstated assumption common to both representations, while no single artifact can make the end-to-end assertion that the resulting execution implements the source program in a given context.
The Epistemic Discontinuity arises from stage-relative identity, since node numbers, value identifiers, blocks, virtual registers, and instructions come into being and cease to exist depending on the current form. Provenance tables can be used to link these elements, but the many-to-many nature of the transformations soon makes a simple line map insufficient. And what person in their right mind would even want to look at that, let alone draw it? But, beyond that, after a form has been destroyed or its identities recycled, any explanation must rely on the correspondence that a particular pass had at the time.
Conceptual Dishonesty arises when the expression “the same program” is used without identifying the particular relation that has been chosen. The forms need not include the same objects, need not allow the same observations, and need not support the same explanations. Although sameness might be justified based on a semantic contract, it is still a conclusion that is drawn from the relations between the different views rather than a property that automatically follows because the compiler has produced each output in turn.
The Objectivist Diagnostic
The analogy offered by Ayn Rand’s Objectivist epistemology (as outlined in Translation As A Transfer Of Semantic Authority: The Epistemology Of Abstraction) describes abstraction from abstractions as involving the use of earlier concepts as units inside broader integrations, together with the maintenance of a hierarchy among those constituent concepts that links the higher integration to its referents.
A system of integrated routines provides a computational analogy in this regard, since a sequence of specialized units replaces a single program view. A failure happens when each stage regards its local units as primary and allows the earlier identities to become floating ancestry rather than constitutive support. Although the phi value can be fully understood within SSA, it no longer has a usable path to the source bindings and the control alternatives whose integration it represents.
A set of integrated procedures provides a computational metaphor in this case, where the sequence of specialist components replaces a single program view. Failure occurs when every step treats local components as primary, while earlier identities become a floating ancestry rather than providing basic support. While the phi measure is completely explainable by SSA, it no longer provides access to the source bindings and the control alternatives whose integration it represents.
This diagnosis does not imply that every Dominant distinction must appear in every Submission. Measurement-omission allows a representation to suppress particulars outside its purpose-scope, and specialized IRs owe much of their value to precisely such suppression. What is required for monotonic extension is contextual honesty: the compiler must know which distinctions a given view omits, which earlier artifacts underwrite its units, and which claims remain valid as a result of the omission. A view used for register allocation need not include comments, but cannot by itself be relied upon to answer questions about authorship or the exact source.
Coexisting Supported Views
A compiler oriented towards Bottom-Driven Semantic Monotonicity might represent intermediate structures either as views over a common Substrate or as enriched state in which the nodes retain explicit records of their support and predecessor relationships. In the case of the choose example, the identity graph might include:
source-if:choose.7
├─ typed-condition:choose.7.c
│ └─ cfg-branch:choose.b0.term
├─ source-return:choose.8
│ ├─ cfg-value:t1
│ └─ ssa-input:result.from.nonzero
├─ source-return:choose.10
│ ├─ cfg-value:t2
│ └─ ssa-input:result.from.zero
└─ semantic-result:choose.result
└─ ssa-phi:result
Code language: CSS (css)Different points of view don’t need to use the same node type or share the same data layout. The Abstract Syntax Tree (AST) can stay tree-shaped, the control-flow view can be graph-shaped, and the target instructions can be presented as linear blocks. Stable identities and typed relationships indicate which artifacts support, elaborate on, supersede, split, merge, or realize those of others. A pass that constructs SSA would add new artifacts, along with a proof or validation record showing that the new define-use (def-use; I just dislike abbreviations of this nature) relations correspond to the control-flow view; it may render an earlier analysis inactive without destroying the view that made the analysis meaningful. Indexes would allow each pass to work efficiently within the chosen representation.
It is important to define Projection carefully, since a Dominant view does not always permit reconstruction of every Submachine-bound detail. When an SSA state is Projected onto the control-flow layer, it should recover the Submachine program state and the declared relation, not invent discarded stylistics or state that a phi node existed in the source code. A Projection may be many-to-one and can include an explicit statement about the losses involved. To preserve transitions, the inherited Submachine actions must retain their original behavior even when new annotations and views are available. New pass actions meet the requirement of interpretive closure by referring to their input artifacts, rules or resolvers, their outputs, and any external analyses on which they depend.
The system would also be able to attach equivalence contracts to boundaries and to the way in which they are composed. If typed-to-CFG (control-flow graph) validation maintains source-visible values and exceptions, while CFG-to-target validation retains only the returned values based on a no-exception assumption, the system must not conclude that exception preservation takes place end-to-end without qualification. The authority of the composed entity is constrained by its weakest relevant relationship. As a result of reorientation, semantic drift can be detected by examining mismatches between contracts rather than by analyzing the pass documentation after a failure has occurred.
Compilation Workflow Under The Redesign
Traditional builds can still be done in stages with performance-related factors in mind. Coexistence means identity and accountability, not the simultaneous execution of computations for all the views. In this way, the compiler can build a typed AST, compute and save the summary of the control flow graph, build the SSA form, and later discard most of the typed data to cold storage while leaving intact content-addressed identities and assurances about reproduction. If the debugger needs to rebuild a view, the view from a high-assurance build can be left unchanged. In a production build, only the relationships necessary to create the system- or user-requested diagnostics would be saved.
All corrections and optimizations would be stored as incremental versions. In the event of omitting an exceptional edge during a control-flow pass, the compiler would note that the particular version is invalid and create a new one; artifacts built from the previous invalid view would be found in history and in the deployed binaries. While this type of history is harder than just overwriting the cache, it helps with security and reliability analysis by identifying which executions were based on the wrong transformation, rather than assuming that the compiler’s current state was always correct.
Costs And Limits
As always, and a fact of life, such possibly vast persisted views can consume a lot of storage space, and stable cross-view identities introduce indirection, complicating in-place algorithms. It is costly to build many-to-many provenance, and it is hard to keep it up to date through block duplication, inlining, vectorization, and scheduling. The need to validate each pass results in even more compilation latency. For reproducibility, it is necessary to identify the compiler versions, the target descriptions, the environment inputs, and the nondeterministic choices, which, in turn, makes the support graph not merely technically, but also organizationally large.
Furthermore, access requires even more attention due to the fact that IRs may reveal secrets of the source, the proprietary algorithms used by the hired programmers (oh no, the dividends, think of the dividends!), or any other low-level security information. There may be a contradiction between the content-addressed retention and the need to delete data. Compact commitments may prove that an artifact existed without enabling the explanatory inspection that the architecture promises. And so, the practical system must include retention hierarchies, authorized projections, redaction semantics, and a clear procedure for weakening claims after evidence has been reclaimed.
There is also a conceptual limit: one shared artifact graph does not eliminate legitimate disagreement among views. A source-oriented debugger asks different questions about sources than a target-oriented performance analyzer asks about targets; their answers may remain irreducible into a convenient form. The concept of Bottom-Driven Semantic Monotonicity does not necessarily offer a special, universal perspective on its own. On the contrary, it assumes that the connection between perspectives is the essential part of the warranted state of the Machine Tower, thereby allowing specialization without creating a lineage of coherent realities for local subjects that can be united through belief in the compiler.
Such connections haven’t been fully or specifically covered in this series, and won’t be, only alluded to or implied by the stated shortcomings. I firmly believe that, at this juncture, it is important to distinguish what exists, and the existing potential failures or shortcomings, as well as what the proposed “solution” is not trying to do in regard to them before establishing a specific framework, my specific instantiation, that fulfills the requirements of Bottom-Driven Semantic Monotonicity. Remember that this is an introductory series.
A Personal Note
Really? Need I say more today?
Pretty pathetically self-evident.