Re: SSA Versus DU-chains: Is the worst case size really different?

> Can someone please give some clues to clarify my confusion? Is there
> any reference material that particularly addresses this issue? I would
> greatly appreciate any help in this regard.


Hi Bageshri,


here is a very simple example program for which there are fewer def-use
edges after SSA conversion.


BB_start:
    if ... goto BB_1 else goto BB_2


BB_1:
    def(x)
    goto BB_3


BB_2:
    def(x)
    goto BB_3


BB_3:
    use(x)
    if ... goto BB_4 else goto BB_5


BB_4:
    use(x)
    goto BB_end


BB_5:
    use(x)
    goto BB_end


BB_end:




In this program, all the uses of variable x are reached by all the
definitions of x. So, here are the def-use edges for x:
1-3, 1-4, 1-5, 2-3, 2-4, 2-5.
Note that there are 6 separate def-use edges here.


Now, let's convert this program to SSA form:


BB_start:
    if ... goto BB_1 else goto BB_2


BB_1:
    def(x1)
    goto BB_3


BB_2:
    def(x2)
    goto BB_3


BB_3:
    x3 := \phi(x1,x2)
    use(x3)
    if ... goto BB_4 else goto BB_5


BB_4:
    use(x3)
    goto BB_end


BB_5:
    use(x3)
    goto BB_end


BB_end:


Note that the definitions of x1 and x2 have been factored into a new
variable x3, by the inserted \phi-function at the head of basic block
BB_3. SSA form factors def-use chains (and use-def chains - Michael
Wolfe did a lot of work on this - read his books and papers for details)!!


So, the SSA def-use edges are


(x1) 1-3
(x2) 2-3
(x3) 3-3, 3-4, 3-5


There are only five separate def-use edges here, one less than in the
non-SSA version. Of course, the \phi-function has introduced some extra
overhead. So there is a trade-off to consider. The important property of
SSA (guaranteed by correct \phi-function insertion) is that each use is
only reached by a single definition. So there should only be one def-use
chain for each use.


It should be possible to prove, certainly for pruned SSA form if not for
minimal SSA form, that the SSA transformed version of the program has
"at most as many" def-use edges as the original version of the program,
i.e. pruned SSA form generally reduces the number of def-use edges, and
certainly does not increase it.




HTH,
Jeremy

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