Re: reducible loops

Raul Deluth Miller-Rockwell <rockwell@socrates.umd.edu>
Tue, 25 Feb 92 00:48:10 -0500

          From comp.compilers

Related articles
reducible loops preston@cs.rice.edu (1992-02-24)
Re: reducible loops rockwell@socrates.umd.edu (Raul Deluth Miller-Rockwell) (1992-02-25)
Re: reducible loops preston@dawn.cs.rice.edu (1992-02-26)
Re: reducible loops lee@dumas.rutgers.edu (1992-02-26)
Re: reducible loops glew@pdx007.intel.com (1992-02-26)
Re: reducible loops preston@dawn.cs.rice.edu (1992-02-27)
Re: reducible loops joel@decwrl.dec.com (1992-02-28)
Re: reducible loops idacrd!desj@uunet.UU.NET (1992-03-09)
[1 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: Raul Deluth Miller-Rockwell <rockwell@socrates.umd.edu>
In-Reply-To: preston@cs.rice.edu's message of Mon, 24 Feb 92 17:05:14 CST
Keywords: optimize
Organization: Compilers Central
References: <9202220021.AA28153@ucbvax.Berkeley.EDU> 92-02-110
Date: Tue, 25 Feb 92 00:48:10 -0500

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


Post a followup to this message

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