Functional Elimination of Phi-Instructions
Lennart Beringer
LMU Munich, Germany
We present a functional analogue of the elimination of
Phi-instructions from Static Single Assignment (SSA) code. Extending
earlier work on the relationship between SSA and functional languages
we show that transformations from A-normal form (ANF) into a more
restrictive form called GNF require the same compensating instructions
to be inserted as are commonly inserted during the translation from SSA
to machine code. Lifting the translation from the syntactic level to
the type level, we introduce type systems that mediate the transition
from ANF code into correctly register-allocated machine code and allow
code optimisations and transformations to be performed in a typed
functional setting.