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

Jeremy Singer <jsinger@cs.man.ac.uk>5 Aug 2005 18:12:52 -0400

From comp.compilers

Related articles
SSA Versus DU-chains: Is the worst case size really different? bageshri@cse.iitb.ac.in (Bageshri Sathe) (2005-07-26)
Re: SSA Versus DU-chains: Is the worst case size really different? mmoudgill@sandbridgetech.com (Mayan Moudgill) (2005-07-28)
Re: SSA Versus DU-chains: Is the worst case size really different? jsinger@cs.man.ac.uk (Jeremy Singer) (2005-08-05)
| List of all articles for this month |

 From: Jeremy Singer Newsgroups: comp.compilers Date: 5 Aug 2005 18:12:52 -0400 Organization: Compilers Central References: 05-07-097 Keywords: analysis Posted-Date: 05 Aug 2005 18:12:52 EDT

> 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

Post a followup to this message