ssa form without dominators

I have been playing with SSA forms for a while and found it cumbersome
to compute dominators and dominator frontiers in order to determine
the insertion points for phi definitions.


Recently, I came up with a simple algorithm that will do without
explicitly computing dominators and dominator frontiers. It works
quite well in practice even though it might not be quite as efficient.


I am curious whether this is a new idea. If not I would appreciate
pointers to the literature.


A short description (simplified for presentation)
of the algorithm follows


Thanks,


        Robert
====================================================


STEP 1: Propagate defintions through CFG using a
                data flow analysis


The meet lattice is depicted below:


                              top
                          / | \
                  def1 def2 ...
                          \ | /
                              bot




def1, def2, ... are definitions of (assignments to) the
variable which is to be transformed into SSA form.
They can be thought of as program points inside
of basic blocks where the assignment occurs.
phi definitions are also considered to be definitions.
We assume that there is a definition in the init node
and that all node are reachable from the init node.


The fixpoint computation is initialized as follows
n denotes a node (basic block) of the CFG.


In[n] := bot
Def[n] := last definition of the variable in n or bot otherwise
Out[n] := bot


The fixpoint equations are shown below


Out[n] := IF Def[n] = bot THEN In[n] ELSE Def[n] ENDIF
In[n] := Meet { Out[p] | p is Predecessor of n}


After the fixpoint computation Out[n] != bot and In[n] != bot
for all n (with exception of the init and exit node).


STEP 2: Determine confluence points and insert new definitions


We insert new (phi) definitions at the beginning of
those nodes with In[n]=top where at least real defintion (from the middle
of the lattice) is propagated from one of the predecessor nodes:


FOREACH n WITH In[n] = top DO
        FOREACH p WITH p is predecessor of n DO
                  IF Out[p] != top THEN
                            /* n is a confluence point */
                            Add new (phi) definition at the
                            beginning of n if there is none already
                            BREAK;
                  END
        END
END




STEP 3: Repeat steps 1 and 2 until no more new definition
                  are added.


Sanity check:
Eventually all nodes with In[n] = top should have a phi definition
at the beginning, this means that from a data flow point of view "top"
is kept from reaching any "use" of the variable to be transformed
into SSA form.
To verify this assume the contrary. Ie. after termination of step 3
there is a node with In[n] = top and without a phi definition, ie.
for all its predecessor we have Out[p] = top.
Consider a path from the init node to n. WLOG we assume that n
is the first node on the path with the said property.
Now, by construction for the previous node in the path we must
have Out[p] != top a contradiction.

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