Independent scholarship · Open accessThe monthly digest

Indexed text attachment

coherent-specialization-on-graalvm.tex

Source for Coherent Specialization on GraalVM

View paper · Download original file

Lines 261–360 of 803. Source text is displayed literally.

261calls 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 323\subsection{An ensemble of decision trees}324 325A forest specification fixes the number of sample ports, an ordered set $F$ of features, and a list of finite binary tree shapes. Each feature $i\in F$ specifies two input projections $\pi_{a_i}$ and $\pi_{b_i}$. Static scale $s_i$ and bias $d_i$ give the affine feature326\[327\alpha_i(x)=\pi_{a_i}(x)+s_i\pi_{b_i}(x)+d_i\in R.328\]329The shapes are the initial algebra of $X\mapsto 1+F\times X\times X$ in sets. An occurrence of a leaf receives a static output word. An occurrence of a split receives a static cut word and compares the indicated feature to it. Each tree also has a static inclusion flag, with zero meaning disabled. The source uses a nested chain of \texttt{let} bindings for feature values. The branches refer to the bound features, so a surviving feature is shared by every split citing it.330 331For a fixed assignment to all settings, define the score of each tree recursively. A leaf yields its assigned word. A split with feature $i$, cut $\tau$, and children $L,H$ yields $L$'s score when $\operatorname{sgnrep}(\alpha_i(x))<\operatorname{sgnrep}(\tau)$ and $H$'s score otherwise. The ensemble score is the sum of all enabled scores. This semantics factors through the product map $x\mapsto(\alpha_i(x))_{i\in F}$. The lowering of a leaf is its parameter projection. The lowering of a split composes the relevant feature projection, the signed comparison, and source conditional selection. Induction on the initial-algebra constructors proves equality with the recursive score for every tree. Applying the flag tests and summing then proves equality for the forest. Static specialization removes disabled subtrees. If a feature is unused throughout the residual forest, purity and totality justify removing its binding.332 333The two examples require different categorical structure in the lowering. The filter expresses a ring polynomial using paired coordinate projections. The forest folds a branching inductive shape into a family of morphisms and factors the result through a common product of derived features. Each construction lands in the same typed source fragment, and each residual uses the same Truffle invocation interface.334 335 336\section{Compiling finite-dimensional quantum evolution}337\label{sec:quantum}338 339Let $H$ be a finite-dimensional Hermitian matrix and fix units with340$\hbar=1$. A time interval $t$ specifies341$U(t)=\exp(-itH)\colon\mathcal H\to\mathcal H$.342By the spectral theorem, $U(t)^*U(t)=I$ and343$U(t+s)=U(t)U(s)$. Hamiltonians with different spectra induce different344families of specialization constants. The state is dynamic, so an345individual compiled evolution can be applied to any state of the required346dimension or repeatedly reused in a time-stepping loop.347 348The functor of restriction of scalars from complex to real vector spaces349sends $U=A+iB$ to350\[351  \mathcal R(U)=352  \begin{pmatrix} A&-B\\ B&A\end{pmatrix}.353\]354The ordered basis used by the code interleaves the real and imaginary355coordinates. The displayed block order and the stored order differ by a356permutation of coordinates. For $z=x+iy$,357$U z=(Ax-By)+i(Ay+Bx)$. This identity follows by bilinearity and358$i^2=-1$. It implies359$\mathcal R(UV)=\mathcal R(U)\mathcal R(V)$ and360$\mathcal R(U^*)=\mathcal R(U)^\top$. In particular realification