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

grover@brahmand.Eng.Sun.COM (Vinod Grover)
16 Jan 1992 04:04:45 GMT

          From comp.compilers

Related articles
Static Single Assignment (TOPLAS Oct '91 paper questions) chuck_lins1@gateway.qm.apple.com (Chuck Lins) (1992-01-15)
Re: Static Single Assignment (TOPLAS Oct '91 paper questions) grover@brahmand.Eng.Sun.COM (1992-01-16)
Re: Static Single Assignment (TOPLAS Oct '91 paper questions) preston@dawn.cs.rice.edu (1992-01-19)
| List of all articles for this month |

Newsgroups: comp.compilers
From: grover@brahmand.Eng.Sun.COM (Vinod Grover)
Keywords: optimize, design
Organization: Sun Microsystems, Mt. View, Ca.
References: 92-01-061
Date: 16 Jan 1992 04:04:45 GMT

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.
--


Post a followup to this message

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