Re: Static Single Assignment (TOPLAS Oct '91 paper questions)

One of the problems with this dead-code-elimination algorithm is that it
does'nt preserve "strong equivalence" (in the sense of Horwitz, Prins, and
Reps[1]). In Horwitz et.al.'s definition of strong equivalence two
programs are strongly equivalent if either both diverge, or produce
identical results.


Consider the following program:


          x = 1
          while (true) {
            dead code here
          }
          print x;




Cytron et. al's algorithm will eliminate the while loop, resulting in a
program that will always terminate, while the original program does not.


Some will argue that it is incorrect to delete the infinite loop, while
others regard an infinite loop as erroneous and anything goes.


Regards


Vinod Grover
Sun Microsystems


[1] S. Horwitz, J. Prins, T. Reps "On the adequacy of program dependence
graphs representing programs" Proceedings of the 15th POPL, 1988, pp.
146-157.
--

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