16 May 1999 15:14:17 -0400

Related articles |
---|

ssa form without dominators muth@cs.arizona.edu (1999-05-16) |

From: | muth@cs.arizona.edu (Robert M. Muth) |

Newsgroups: | comp.compilers |

Date: | 16 May 1999 15:14:17 -0400 |

Organization: | University of Arizona, Computer Science |

Keywords: | analysis, question |

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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.