Indexed text attachment
coherent-specialization-on-graalvm.tex
Source for Coherent Specialization on GraalVM
View paper · Download original file
Lines 223–322 of 803. Source text is displayed literally.
223 S\times_{[D_S,Y_S]_S}C .224\]225Mapping into this object over \(S\) gives candidates and226correctness paths over any context \(A\to S\), by exponential227adjunction and the defining property of the pullback. This228assigns a space of witnesses to each context with all higher229restriction maps induced by precomposition. It satisfies230\eqref{eq:descent} because mapping out of a \v{C}ech231colimit in the slice takes it to a limit. A relabeling between232candidate representations lifts to a comparison between233certified candidates when its execution homotopy is234compatible with their correctness paths. Higher comparisons235are given by the same homotopy pullback.236 237For a higher example take $\mathcal X=\mathcal S$, $S=S^2$, $D=*$, and $Y=K(\mathbb Z,2)$. Let $F$ represent the generator of $H^2(S^2;\mathbb Z)$ and let $R=1$ supply one candidate with constant basepoint denotation over every $A$. At a point of $S$, the certificate space is equivalent to $\Omega K(\mathbb Z,2)\simeq K(\mathbb Z,1)$ after choosing a path to the basepoint. Take $U$ to be the disjoint union of the complements of the north and south poles, mapped to $S^2$. Each complement is contractible. The map $U\to S^2$ is an effective epimorphism in spaces because it is surjective on components. Both restrictions of $F$ are nullhomotopic, so $C_F(U)$ is inhabited. A global certificate would nullhomotope a generator, which is impossible. Equation \eqref{eq:descent} identifies the obstruction as failure to complete these local certificates to a compatible \v{C}ech diagram. This example tests the semantics of higher certificates. The executable word-valued compiler uses the discrete instance.238 239\paragraph{Guarded refinement.}240For a fixed context \(A\), let \(g:A\times D\to 1\sqcup1\)241be a decidable guard. Its two pullbacks split \(A\times D\)242as \(G\sqcup\bar G\), since coproducts in an243\(\infty\)-topos are disjoint and universal. Let \(J:G\to Y\)244be the fast branch, \(s:\bar G\to Q\) a checkpoint on guard245failure, and \(j:Q\to Y\) its generic continuation.246Given paths \(J\simeq F_a|_G\) and247\(j\circ s\simeq F_a|_{\bar G}\), the dispatcher248\([J,j\circ s]\) is observationally equivalent to \(F_a\).249The mapping space out of the coproduct is the product of the250branch mapping spaces, where the two certificates form the two251components of the desired path. Both the guard decomposition and252the assembly of certificates commute with pullback.253 254An entry guard can checkpoint the original arguments. After255observable work, the checkpoint hypothesis demands a simulation256relating optimized state to an interpreter state at a valid257continuation, and preservation of any trace already produced.258For instance, restarting the call after a write can repeat the259write even when the return value agrees. A mutable speculative260assumption also needs valid synchronization through its use when261calls and invalidation can occur concurrently.262 263 264\section{From residual syntax to Truffle calls}265\label{sec:graal}266 267\paragraph{Two stages.}268The compiler takes a checked algorithm $t$ and static parameters $s$ in its declared scalar type. It substitutes the parameters, simplifies the resulting term, and lowers the residual tree to a Truffle \texttt{RootNode}. Each executable kernel holds the call target of that root. For dynamic inputs $d$, the call target executes the lowered tree through Truffle. Graal can specialize the interpreter with respect to the root and its stable structure. Schematically,269\begin{align*}270 r_s &= \operatorname{simplify}(t[s]), \\271 K_s &= \operatorname{callTarget}(\operatorname{lower}(r_s)), \\272 K_s(d) &= \operatorname{exec}_{\mathrm{Truffle}}(r_s,d).273\end{align*}274The first stage fixes source-level parameters. The second stage uses the constructed AST as static interpreter state, in the sense of Truffle's first-Futamura-projection architecture \cite{graalpe,wuerthinger}. Constructing $K_s$ yields an executable value immediately. Compilation to machine code depends on the engine, the runtime tier, the workload, and compilation heuristics \cite{graalroot}.275 276\paragraph{Lowering invariant.}277Input and local nodes read distinct logical environments. Constants and input indices are fixed at construction. For \texttt{i64}, Java \texttt{long} addition, subtraction, and multiplication compute in $W=\mathbb Z/2^{64}\mathbb Z$ and comparison uses signed order. The \texttt{f64} case decodes the stored bits, performs the corresponding Java \texttt{double} operation, and re-encodes numerical results. The representation preserves signed zero and canonicalizes NaN payloads. The internal representations of false and true are $0$ and $1$, with the type checker controlling their use. A conditional evaluates its test and only the selected branch. A \texttt{LET} first evaluates its definition and writes the result to its assigned frame slot. References in the body read the frame slot for their lexical binder. A fresh execution frame prevents previous calls from supplying local values.278 279For each subterm $u$, let $\eta$ map its free local variables to assigned slots, and let $F$ be a frame with dynamic arguments $d$ and slot values representing an environment $\rho$. The lowering invariant is280\[281 \operatorname{run}(\operatorname{lower}_{\eta}(u),F)282 = \operatorname{encode}(\operatorname{den}(u)(d,\rho)).283\]284The frame after execution agrees with $\rho$ on the slots for free variables of $u$. For a constant, input, or local, the invariant is the defining read operation. Arithmetic and comparisons follow from the inductive hypotheses for their operands and the declared scalar operations. For a conditional, the test invariant selects the same branch on both sides and that branch's invariant gives the result. For a binding, a slot distinct from the currently live slots becomes the location of the bound value. The body invariant then applies to the environment extended by that value. At the root the local environment is empty. Combined with specialization correctness, the invariant proves $K_s(d)=\operatorname{den}(t)(s,d)$ for the interpreter on well-typed inputs, assuming adequate runtime resources. This is a source-to-interpreter argument. The further claim about optimized execution depends on the Truffle and Graal implementation preserving the interpreter's behavior.285 286\paragraph{Runtime assumptions and transfer.}287Truffle treats the root of a compiling call target as a partial-evaluation constant. Stable fields reached from that root, including AST children declared with \texttt{@Child} and \texttt{@Children}, can make interpreter dispatch sites monomorphic and enable inlining. Dynamic arguments can select different paths in the same compiled kernel. In this prototype, each conditional passes its test value through a Truffle \texttt{CountingConditionProfile}. The profile records branch frequencies and returns the test value. The engine can speculate that an unobserved case remains untaken and invalidate that speculation if a later input exercises the branch \cite{graalprofile,graalpe,wuerthinger}.288 289For a simplified model of guarded optimization, let $E$ be the interpreter configurations for a given residual term with observable result $O\colon E\to W$. Let $j\colon U\hookrightarrow E$ include the states satisfying a guard, and let $M\colon U\to W$ denote the guarded machine fragment. The fragment is sound on its domain exactly when $M=O\circ j$. If the guard fails, a deoptimization path must restore an interpreter configuration with the same pending observation. Thus if reentry maps an optimized state $q$ to $\delta(q)\in E$, its semantic obligation is $O(\delta(q))=O_{\mathrm{pending}}(q)$, where $O_{\mathrm{pending}}$ is specified by the source computation at the corresponding input and continuation. Together, this obligation and the domain equality suffice for observational equivalence of guarded execution with fallback and interpretation. The observation here records the returned word. The engine must implement the state transfer, including reentry at the appropriate continuation.290 291The prototype builds a fresh tree on a miss in the module's bounded cache of static tuples and fixes the substituted constants for that kernel's lifetime. Truffle offers mechanisms for interpreters that maintain mutable speculation state. A write to a \texttt{@CompilationFinal} field on which compiled code relies must be accompanied by invalidation. The documentation describes local transfer via \texttt{transferToInterpreterAndInvalidate} and dependency tracking through a Truffle \texttt{Assumption} for externally invalidated facts \cite{graalpe}.292 293\paragraph{The polyglot boundary.}294Evaluating a \texttt{catpe} specification supplies a module with \texttt{compile}. Calling \texttt{compile} with the static tuple yields the executable $K_s$, which exports Truffle interoperability messages. A guest can hold $K_s$ and call it repeatedly with the dynamic tuple. JavaScript and Python use the same resident implementation through the executable-value protocol \cite{graalinterop}. The boundary checks the arity and uses Truffle's \texttt{asLong} or \texttt{asDouble} to convert the guest arguments to the declared scalar type. The correctness statement compares values after those lossless conversions. JavaScript \texttt{Number} rounds some integers beyond its safe-integer range, so exact tests of those words require exact foreign representations and explicit checks on the returned value.295 296The executable value supplies a concrete guarded dispatch example. Its direct-call specialization is applicable when the receiver's call target equals the call node's cached target. The generic path uses an indirect call to the receiver's target. Both paths perform the same arity and word conversions. On the equality guard they invoke the same target with the same arguments, which supplies the local agreement needed for this dispatch optimization.297 298\section{Compiling two families of algorithms}299\label{sec:workloads}300 301Let $R=\mathbb Z/2^{64}\mathbb Z$. An external signed word denotes its class in $R$.302Order comparisons use $\operatorname{sgnrep}\colon R\to[-2^{63},2^{63}-1]\cap\mathbb Z$, the signed representative, followed by the usual integer order. The two domain compilers in \texttt{Workloads.java} construct typed source terms. Static data and dynamic samples use separate input ports. Both compilers build balanced trees for sums, using $0$ for the empty sum. Associativity in $R$ ensures that the chosen grouping preserves the result even on inputs whose ordinary integer sums would overflow.303 304\subsection{A bank of finite impulse response filters}305 306A specification fixes a window of length $m\ge 2$ and a finite, nonempty ordered bank. For a bank entry $b$, the shape gives a symmetry sign $\epsilon_b\in\{1,-1\}$, while the static inputs include the bank selector, every independent pair coefficient $c_{b,i}$, and the center coefficient if needed. Put $q=\lfloor m/2\rfloor$ and $j(i)=m-1-i$. For $0\le i<q$, the coefficient vector satisfies307\[308h_{b,i}=c_{b,i},\qquad h_{b,j(i)}=\epsilon_b c_{b,i}.309\]310An odd symmetric window takes its center coefficient as a static input. An odd antisymmetric window chooses center zero as part of the specification. This choice fixes the center even though $2c=0$ also admits a nonzero class in $R$.311 312The generator emits a bank selector built from equality tests over the static bank index. Each pair is compiled to $c_{b,i}(x_i+\epsilon_b x_{j(i)})$, with addition or subtraction determined by the bank shape. A coefficient-zero conditional wraps each contribution and a static bank dispatch wraps the bank terms. Specialization therefore keeps a single bank branch and removes every pair whose coefficient is zero. The named-parameter binder validates the index. The generic source term is total, with default result zero for an index outside the bank.313 314For each valid static assignment and each dynamic sample window $x$, the convolution dot product agrees with the result of the selected residual function.315\begin{align*}316\sum_{i=0}^{m-1}h_{b,i}x_i317&= \sum_{i=0}^{q-1}\bigl(c_{b,i}x_i+318 \epsilon_b c_{b,i}x_{j(i)}\bigr)+\delta_b(x)\\319&= \sum_{i=0}^{q-1}c_{b,i}(x_i+\epsilon_b x_{j(i)})+\delta_b(x).320\end{align*}321Here $\delta_b(x)$ is the center contribution when present and zero otherwise. The first equality partitions the coordinate projections into pairs and a possible singleton. The second is distributivity in $R$. Each remaining summand uses at most one multiplication per pair. The domain compiler constructs this factored expression before CATPE specializes it.322