From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=0.6 required=5.0 tests=BAYES_05,INVALID_DATE,
	MSGID_SHORT autolearn=no autolearn_force=no version=3.4.4
Path: utzoo!attcan!uunet!husc6!mailrus!uflorida!gatech!hubcap!wtwolfe
From: wtwolfe@hubcap.UUCP (Bill Wolfe)
Newsgroups: comp.lang.ada
Subject: Automatic removal of GOTOs
Message-ID: <4164@hubcap.UUCP>
Date: 22 Jan 89 18:27:05 GMT
Organization: Clemson University, Clemson, SC
List-Id: <comp.lang.ada>


   There has been a series of articles from those interested in automatic
   translation who wish to target Ada and still retain GOTOs for convenience.

   The following abstract, which appears in the current issue of 
   Communications of the ACM (V32,#1,P140), shows that it is possible 
   for automatic translators to have their GOTOs and eat them too,
   even while retaining the same general control structures.

      ELIMINATING GO TO'S WHILE PRESERVING PROGRAM STRUCTURE
      Lyle Ramshaw 

      Suppose we want to eliminate the local GO TO statements of a Pascal
      program by replacing them with multilevel loop exit statements.  The
      standard ground rules for eliminating GO TO's 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 GO TO's 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 GO TO's.  In particular, we are allowed to 
      delete the GO TO 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 pr
      program text in any way.  The critical issue that determines whether
      GO TO's 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 GO TO's from that program under the stricter rules.

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

   Thus, automatic translators can ensure that the gotos they generate
   do not violate the reducibility property with respect to the flow graph,
   and then remove the gotos in the final phase of translation.  If it is
   desirable to leave the control structures of the final code intact,
   this paper shows that it is even possible to do that.  Therefore, it
   seems that automatic translators could survive quite nicely even if
   the GOTOs are eliminated in the 9X version of Ada.  

   Bill Wolfe, wtwolfe@hubcap.clemson.edu