Re: reducible loops

If you want an example of an irreducible loop, here's the simplest example
I can think of. As you can see, it's nothing more than a 4 state machine,
with several possible cycles.


To reduce this, you'd have to introduce a variable to hold the state
information, and introduce something with properties similar to a case
statement based on that variable. Then the branches become something
"simpler" (like table lookup).


I'm fairly sure that this is irreducible, but I forget my graph theory,
and am not sure that the proof applies to the sort of reduction we're
talking about here. If anyone can show how to reduce this, I'd be
pleasantly surprised.


          $ start here
  10 continue
            if test1 goto 11
            statement a
            goto 20
  11 statement b
            goto 30


  20 if test2a goto 21
            if test2b goto 22
            statement c
            goto 10
  21 statement d
            goto 30
  22 statement e
            goto 40


  30 if test3a goto 31
            if test2b goto 32
            statement f
            goto 10
  31 statement g
            goto 20
  32 statement h
            goto 40


  40 if test4a goto 41
            if test4b goto 42
            statement j
            goto 20
  41 statement k
            goto 30
  42 continue
          $ exit here


--
Raul Deluth Miller-Rockwell <rockwell@socrates.umd.edu>
--

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