Re: Phi nodes?

Hi there,
> Can somebody please explain me, what Phi nodes are, and what's their
> use in the .NET IL?


The intention for the .NET IL seems to be to embed an SSA graph within
the bytecode stream. Presumably to provide information to the
install/run-time compilers to help optimize the code. Interestingly,
there seems to be no associated mechanism for checking that the SSA
graph corresponds to the bytecode stream in which it is embedded. I
wonder what would happen if someone constructs a suitably devious
example of a mismatching SSA graph and program..


A shameless plug for a paper on SafeTSA, an SSA based secure mobile
code format to facilitate optimizing compilation on the client side:


SafeTSA: A Type Safe and Referentially Secure Mobile-Code
Representation Based on Static Single Assignment Form;
W. Amme, N. Dalton, J. v. Ronne, and M. Franz;
accepted for the 2001 ACM Sigplan Conference on
Programming Language Design and Implementation (PLDI 2001),
Snowbird, Utah; June 2001.


Available from:
http://qetesh.ics.uci.edu/pubs.html


To begin to answer your question..
SSA form is an intermediate representation commonly used in optimizing
compilers. In it each variable (value) has only as single definition
point. It is "static single assignment" because dynamically, at
runtime, a variable may take on multiple values. If the definition is
in a loop for instance.


Anyway, to construct SSA for straight line code is easy, each
assignment to a variable is given a new name, and each use renamed to
use the appropriate definition point. The fun starts when you have
control flow splits. At each control flow join, say after an if/else,
you insert phi functions to preserve the single assignment aspect.
The phi for the if/else for a variable v will be of the form: v_0 <-
PHI(v_1,v_2) where v_1 is the value assigned on one side of the
control flow, and v_2 on the other. You can think of the phi function
as performing an assignment depending on the path the control flow
reaches that point. I'm ignoring lots of things here, but there are
plenty of papers which explain in detail various ways to construct SSA
and its variants. Some recent compiler books also cover it, including
Appel's 'Modern Compiler Implementation in' set, Morgan's 'Building an
Optimizing Compiler' and Muchnick's 'Advanced Compiler Design and
Implementation'.


Regards,
Niall


--
----------------------------------------------------------------------
Niall Dalton ndalton@ics.uci.edu
University of California, Irvine http://www.ics.uci.edu/~ndalton

Return to the comp.compilers page.
Search the comp.compilers archives again.