Re: SSA without phi

Nicolas.Capens@gmail.com writes:


> I'm wondering whether it is possible to get (part of) the benefits of
> SSA by using it only per basic block. This way I could avoid all the
> complexity of phi functions.


Welcome to optimizer construction circa 1978. This technique if I
recall the terminology correctly, was called (local) value numbering
or local common sub-expression elimination. It "falls out" if you
implement "triples" (opertator + operands) as your intermediate form.
Each triple has a unique value number (address) and is in SSA form
within the basic block. I believe it can be shown to be "optimal"
under certain conditions.




> The problem with phi functions is that they're not executable. I would
> prefer keeping my intermediate code executable at all time.


I'm not sure why you "fear" phi functions, though. They don't need to
be executable. If you generate assignments at the places where the
operands to the phi functions are created, you can treat them (the phi
functions) as a no-op, when you are executing your internediate form.
A phi function simply records which values can get to a variable on
the paths that lead to the point in question. You don't need to do
anything at the point where you insert a phi function. The
"assignments" leading up to the phi function will have stored the
correct values in the phi function target. (At least this is the
model of how I've seen them used.)


Now, if you have phi functions, you can turn them into C-style
ternary-operators (?: gates) and eliminate the preceding assignments
where that is advantageous. If it isn't advantageous, leave the
assignments in place and disregard the phi functions. The purpose of a
phi function is to record information. You use that information if it
helps you generate more optimal code. You discard that information if
it does not.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

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