Re: reducible loops

glew@pdx007.intel.com (Andy Glew)
Wed, 26 Feb 1992 23:33:33 GMT

          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)
Duff's device glew@pdx007.intel.com (1992-02-27)
Re: reducible loops joel@decwrl.dec.com (1992-02-28)
Re: reducible loops idacrd!desj@uunet.UU.NET (1992-03-09)
Re: reducible loops preston@dawn.cs.rice.edu (1992-03-10)
| List of all articles for this month |

Newsgroups: comp.compilers
From: glew@pdx007.intel.com (Andy Glew)
Keywords: optimize
Organization: Intel Corp, Hillsboro, Oregon
References: <9202220021.AA28153@ucbvax.Berkeley.EDU> 92-02-122
Date: Wed, 26 Feb 1992 23:33:33 GMT

Let me add Duff's device to the discussion about irreducible loops.


Duff's device is a technique for unrolling loops with minimal overhead.
Let's see if I can get an example right:


        j = i / 8;
        switch( i % 8 ) {
         do {
         case 7:
         destptr++ = srcptr++;
         case 6:
         destptr++ = srcptr++;
         case 5:
         destptr++ = srcptr++;
         case 4:
         destptr++ = srcptr++;
         case 3:
         destptr++ = srcptr++;
         case 2:
         destptr++ = srcptr++;
         case 1:
         destptr++ = srcptr++;
         case 0:
         destptr++ = srcptr++;
         } while( --j >= 0 );
        }


If you're smart you can replace all of the pointer increments by a
single increment.


(1) Most compilers cannot generate code that uses Duff's device - because
they just don't consider irreducible loops.


(2) Most compilers cannot perform optimizations around Duff's device, because
of the irreducible loop.


--
Andy Glew, glew@ichips.intel.com
Intel Corp., M/S JF1-19, 5200 NE Elam Young Pkwy,
Hillsboro, Oregon 97124-6497
--


Post a followup to this message

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