Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uflorida!gatech!hubcap!billwolf
From: billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,)
Newsgroups: comp.software-eng
Subject: Re: Software Restructuring
Message-ID: <4564@hubcap.UUCP>
Date: 26 Feb 89 17:40:58 GMT
References: <172@qusunb.queensu.CA>
Sender: news@hubcap.UUCP
Reply-To: wtwolfe@hubcap.clemson.edu
Lines: 42

From article <172@qusunb.queensu.CA>, by tsitinis@qucis.queensu.CA (Vaggelis Tsitinis):
> 
>    Many algorithms have been proposed for restructuring a program into a 
> simplest one, eliminating the nested loops and avoiding the use of gotos.
> However, these techniques do not necessarily produce clear flow of control.

   The January 1988 issue of CACM abstracts (page 140) an October 1988
   JACM article which addresses this topic:

      Eliminating GOTOs While Preserving Program Structure
      Lyle Ramshaw

      Suppose we want to eliminate the local GOTO statements of a Pascal
      program by replacing them with multilevel loop exit statements.  The
      standard ground rules for eliminating GOTOs require that we preserve
      the flow graph of the program, but they allow us to completely rewrite
      the control structures that glue together the program's atomic tests
      and actions.  The GOTOs can be eliminated from a program under those
      ground rules if and only if the flow graph of that program has the
      graph-theoretic property named reducibility.

      This paper considers a stricter set of ground rules, introduced by
      Peterson, Kasami, and Tokura, which demand that we preserve the
      program's original control structures, as well as its flow graph,
      while we eliminate its GOTOs.  In particular, we are allowed to
      delete the GOTO statements and the labels that they jump to, and
      to insert various exit statements and labeled repeat-endloop pairs
      for them to jump out of.  But we are forbidden to change the rest
      of the program text in any way.  The critical issue that determines
      whether GOTOs can be eliminated under these stricter rules turns out
      to be the static order of the atomic tests and actions in the program
      text.  This static order can be encoded in the program's flow graph
      by augmenting it with extra edges.  It can then be shown that the
      reducibility of a program's augmented flow graph, augmenting edges
      and all, is a necessary and sufficient condition for the eliminability
      of GOTOs from that program under the stricter rules.

      For Correspondence: Digital Equipment Corporation Systems Research
                          Center, 130 Lytton Ave., Palo Alto, Ca  94301  USA


   Bill Wolfe, wtwolfe@hubcap.clemson.edu