Re: loops

In article 92-02-118 mwolfe@ogicse.ogi.edu writes:
> ....
>In structured code, even if there is only one header node, the inner/outer
>relationship can be disambiguated, as mentioned. In unstructured graphs,
>however, truly ambiguous relationships can be derived. For instance, how
>to define inner/outer relationships of:
>
> stuff1
> if( more ) then
> stuff 2
> if( other ) goto stuff1
> else
> stuff3
> if( stillother) goto stuff1
> endif
>
>so the CFG has the shape:
>
> |
> ____ | _________
> / \ | / \
>| stuff1 |
>| | |
>| | |
>| more |
>| / \ |
>| / \ |
>| stuff2 stuff3 |
>| | | |
>| other stillother |
> \/ \ / \/
> \ /
> |
> |
>
>The loop header is 'stuff1', and there are two back edges, but there is no
>rhyme nor reason to choose one back edge as the inner over the other.


At first reading, I thought this kind of code was unique to unstructured
languages like FORTRAN IV. But the above code is easily translated by a
human being to structured code; how hard is it for a compiler? Has anyone
tried it? For example:




repeat
      stuff1;
      if (more) then
            stuff2;
            done := (NOT other);
      else
            stuff3;
            done := (NOT stillother);
      endif;
until (done);




This has the much nicer control flow graph (CFG) :


      ____ |
  / \ |
| stuff1
| |
| |
| more
| / \
| / \
| stuff2 stuff3
| | |
| \ /
  \ \ /
      \ \ /
          \ |
              \-done


(I'm not showing the dependence of "done" on "other" and "stillother" here.)


The resulting code shows clearly what seemed apparent to me from the original
code: There was no inner loop within an outer loop, but rather a conditional
statement in a loop. Can this transformation be done by an intermediate code
optimizer today?


>Another interesting case is:
>
> stuff1
> stuff2
> if( s2 ) goto stuff1
> stuff3
> if( s3 ) goto stuff2
>
>so the CFG looks like:
>
> |
> | /\
> stuff1 |
> | |
> /\ | |
> | stuff2 |
> | | \/
> | stuff3
> \/ |
> |


Again, this is equivalent to:


do_stuff1 := FALSE;
done := FALSE;
repeat
      if (do_stuff1) then
            stuff1;
      endif;
      do_stuff1 := TRUE;
      stuff2;
      if (NOT s2) then
            stuff3;
            do_stuff1 := (NOT s3);
            done := (NOT s3);
      endif;
until (done);


The CFG, which I will not draw here, will have conditionals but only one
loop. Notice that neither example required duplication of code in order
to structure the CFG.


Is the general case just too difficult for a compiler? Is there enough
gain to offset the testing of "done", which is a compiler artifact?


How about the reverse transformation after the intermediate code
optimization is finished? Take unnecessary boolean flags and convert the
code back to the appropriate jumps.


>Is this of any interest to anyone? probably not.


Sure it is. Especially FORTRAN compiler designers. But also everyone else
compiling languages that allow gotos, even if they are discouraged, and
especially if the reverse transformation can be done on structured
languages.
--
||| clc5q@virginia.edu (Clark L. Coleman)
--

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