Re: Loop unrolling

Re: Loop unrolling

[Mike Stump]

> Date: Wed, 10 Jun 1998 20:16:08 +0200 (MET DST)
> From: Gerald Pfeifer <pfeifer@dbai.tuwien.ac.at>

> I'm the one who started this monster thread, and actually I believe that
> John Carr <jfc@mit.edu>,

His example was mistaken.  He had no ``empty'' ``loops''.

 struct x
        {
          x() {}
        };
        
        f()
        {
          x x1[10];
        }

I see no for, nor no while.  This should optimize down.

> Branko Cibej <branko.cibej@hermes.si>,

His example was mistaken.  He had no ``empty'' loops.

                for (size_t i = 0; i < size; ++i)
                    new (&objs[i]) T(init);

In this case, ``new (&objs[i]) T(init)'' != ``'', hence the loop is
not empty.

    for (size_t i = 0; i < size; ++i)
                    objs[i].~T();

In this case, ``objs[i].~T()'' != ``'', hence the loop is not empty.

This case should optimize down.

> Martin von Loewis <martin@mira.isdn.cs.tu-berlin.de> have provided
> examples that empty loops _should_ get removed.

His example was also mistaken:

class A {
  int i;
public:
  A(){};
};

int main() 
{
  A a[1000];
}

I see no loops.  This should be optimized down.

The definition of loop means the use of the keyword ``for'' or
``while''. The definition of empty (in C and C++) means that textually
in the users source program, the character ';' follows the ')' from
the loop syntax.

I know, somewhat arbitrary, but prefectly clear.  This was the result
of the conversation from eons ago that we had.  It is not currently
implemented this way, but as I said, that is a bug in the
implementation, that can be fixed, if someone cares.

> Jeff, what happened to my patch? You neither commented on it nor has
> it been installed. :-(

I don't think it should be.

Re: Loop unrolling

[Joern Rennecke]

> > Branko Cibej <branko.cibej@hermes.si>,
> 
> His example was mistaken.  He had no ``empty'' loops.
> 
>                 for (size_t i = 0; i < size; ++i)
>                     new (&objs[i]) T(init);
> 
> In this case, ``new (&objs[i]) T(init)'' != ``'', hence the loop is
> not empty.
> 
>     for (size_t i = 0; i < size; ++i)
>                     objs[i].~T();
> 
> In this case, ``objs[i].~T()'' != ``'', hence the loop is not empty.

Well, how about some plain C macroid code:

#define NOP(X, N) /* This space intentionally left blank */

#define FROB(X, OP) \
do { \
  foo (x); \
  for (i = n; --i >=0; ) \
    OP (X, i); \
  bar(x); \
} while (0);

FROB (x, NOP);

Re: Loop unrolling

[Branko Cibej]

Mike Stump wrote:

> > Branko Cibej <branko.cibej@hermes.si>,
>
> His example was mistaken.  He had no ``empty'' loops.

Aha. All right then, I'll remember my early Pascal days and write

     int n = 1;
     do { n = n + 1; } while (n != 100);

then I'll compile that with -fread-programmers-mind to tell the compiler I
don't want the loop optimised out.

(Or should it be -fdivine-from-fish-entrails? :-)

--
Branko Cibej   <branko.cibej@hermes.si>
HERMES SoftLab, Litijska 51, 1000 Ljubljana, Slovenia
phone: (++386 61) 186 53 49  fax: (++386 61) 186 52 70

Re: Loop unrolling

[Joern Rennecke]

> Aha. All right then, I'll remember my early Pascal days and write
> 
>      int n = 1;
>      do { n = n + 1; } while (n != 100);
> 
> then I'll compile that with -fread-programmers-mind to tell the compiler I
> don't want the loop optimised out.
> 
> (Or should it be -fdivine-from-fish-entrails? :-)

Apropos... is the following an empty loop?

for (i = 0; i <= 9; i = foo (i));

Or this one?

for (i = 0; i <= bar (); i++);

Or that one?

for (i = 0; baz (i, 9); i++);

Re: Loop unrolling

[Jeffrey A Law]

  In message < 199806121642.RAA00482@phal.cygnus.co.uk >you write:
  > Apropos... is the following an empty loop?
  > 
  > for (i = 0; i <= 9; i = foo (i));
Not if foo is a function call.  Similarly for your other
examples.

An empty loop would be a loop with a body that consists of a
counter increment and branch to the top of the loop (at the
RTL level).  Nothing more, nothing less.

I don't think trying to describe what an empty loop is with C
source is all that interesting since in the end it's going to be
detected by the loop optimizer.

jeff

Re: Loop unrolling

[Gerald Pfeifer]

On Fri, 12 Jun 1998, Jeffrey A Law wrote:
> I don't think trying to describe what an empty loop is with C
> source is all that interesting since in the end it's going to be
> detected by the loop optimizer.

As far as I understood the discussion, however, this (i.e., not
solely relying on the optimizer, but passing down parser information)
is definitely required for full support of the ``old'' behavior.


In any case, I agree with Mike:

  So, I guess this is the close of this thread...  I think everything
  important has been said, and all side presented, now just up to Law
  and/or whoever else he chooses.  :-)
     
  http://www.cygnus.com/ml/egcs/1998-Jun/0597.html


Jeff, please let us know what your decision is and I will work out a new
patch, either along my original lines or following Mike's (previous)
suggestions.

(The current documentation is not fully sufficient, so we should
definitely fix it, one way or the other.) 

Gerald
-- 
Gerald Pfeifer (Jerry)      Vienna University of Technology
pfeifer@dbai.tuwien.ac.at   http://www.dbai.tuwien.ac.at/~pfeifer/

Loop unrolling

[Frank Klemm]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 20556 bytes --]

Take the following piece of code:

--- code 1 ---------------------------------------------------

unsigned int   x;

int  main ( void )
{
    int  i;

    for ( i = 0; i < NUMBER; i++ )
        x /= 15;

    return 0;
}

--------------------------------------------------------------

Compile it with:

    gcc -O2 -DNUMBER=... -fomit-frame-pointer -march=... -S -o code1.s code1.c

gcc3 does also do an unrolling with -O2. Not a bad idea, especially if the
number of loops is known during the compile time. But:

NUMBER		unrolling
-------------------------
1...500*10^6	 1
 600*10^6	15
 700*10^6	14
 800*10^6	20
 900*10^6	15
1000*10^6	20
1100*10^6	10
1200*10^6	15
1300*10^6	10
1400*10^6	14
1500*10^6	 1
1600*10^6	 1
1700*10^6	20
1800*10^6	15
1900*10^6	20
2000*10^6	20
1504997777	 1

This does not look very sophisticated.

---------------------------------------------------

I propose the following:

  -Os  never unrolls (except loops=0 and loops=1)
  -O1  \
  -O2  | do unrolls, but with different affinity 
  -O3  /

									-0	-O2	-O3
1st affinity param: 
	maximum unroll count						 2	10	40
2nd affinity param:
	maximum code enlargement for every percent speed increase	1µops   10µops	100 µops


Such a table can look like:

          :    2   4   8  16  32  64 128 256 512
    loops :  µop µop µop µop µop µop µop µop µop per loop
----------:-------------------------------------
         1:    1   1   1   1   1   1   1   1   1
         2:    2   2   2   2   2   1   1   1   1
         3:    3   3   3   3   1   1   1   1   1
         4:    4   4   4   4   1   1   1   1   1
         5:    5   5   5   5   1   1   1   1   1
         6:    6   6   6   2   1   1   1   1   1
         7:    7   7   7   2   1   1   1   1   1
         8:    8   8   8   2   1   1   1   1   1
         9:    9   9   9   3   1   1   1   1   1
        10:   10  10  10   2   1   1   1   1   1
        11:   11  11   5   2   1   1   1   1   1
        12:   12  12   4   2   1   1   1   1   1
        13:   13  13   4   2   1   1   1   1   1
        14:   14  14   7   2   1   1   1   1   1
        15:   15  15   5   3   1   1   1   1   1
        16:   16  16   4   2   1   1   1   1   1
        17:   17  17   4   2   1   1   1   1   1
        18:   18  18   3   2   1   1   1   1   1
        19:   19  19   3   2   1   1   1   1   1
        20:   20  20   4   2   1   1   1   1   1
        22:   22   7   3   2   1   1   1   1   1
        24:   24   8   4   2   1   1   1   1   1
        26:   26   8   5   2   1   1   1   1   1
        28:   28   7   4   2   1   1   1   1   1
        30:   30  10   5   2   1   1   1   1   1
        32:   32   8   4   2   1   1   1   1   1
        34:   34   8   3   2   1   1   1   1   1
        36:   36   9   4   2   1   1   1   1   1
        38:   38   9   4   2   1   1   1   1   1
        40:   40   8   4   2   1   1   1   1   1
        43:   14   7   3   2   1   1   1   1   1
        46:   15   9   5   2   1   1   1   1   1
        49:   16   7   4   2   1   1   1   1   1
        52:   13  13   4   2   1   1   1   1   1
        55:   18  11   5   2   1   1   1   1   1
        58:   19   8   3   2   1   1   1   1   1
        61:   15  10   4   2   1   1   1   1   1
        65:   13   8   5   2   1   1   1   1   1
        69:   17   6   3   3   1   1   1   1   1
        73:   18   8   4   2   1   1   1   1   1
        77:   19   7   4   2   1   1   1   1   1
        81:   16   9   3   3   1   1   1   1   1
        86:   17   7   5   2   1   1   1   1   1
        91:   13   7   5   2   1   1   1   1   1
        96:   16   8   4   2   1   1   1   1   1
       101:   20  10   4   2   1   1   1   1   1
       107:   15   7   5   2   1   1   1   1   1
       113:   16   8   4   2   1   1   1   1   1
       119:   17   7   7   2   1   1   1   1   1
       125:   25   5   5   2   1   1   1   1   1
       132:   12   6   4   2   1   1   1   1   1
       139:   17   6   3   2   1   1   1   1   1
       146:   16   8   5   2   1   1   1   1   1
       154:   14   7   3   2   1   1   1   1   1
       162:   18   9   3   2   1   1   1   1   1
       171:   19   9   3   3   1   1   1   1   1
       180:   15   9   4   2   1   1   1   1   1
       190:   19  10   5   2   1   1   1   1   1
       200:   20   8   4   2   1   1   1   1   1
       211:   15   7   5   2   1   1   1   1   1
       222:   17   6   3   2   1   1   1   1   1
       234:   18   9   3   2   1   1   1   1   1
       246:   22   6   3   2   1   1   1   1   1
       259:   16   7   7   2   1   1   1   1   1
       272:   16   8   4   2   1   1   1   1   1
       286:   13  11   5   2   1   1   1   1   1
       301:   15   7   4   2   1   1   1   1   1
       317:   15   7   4   2   1   1   1   1   1
       333:   15   9   3   3   1   1   1   1   1
       350:   14   7   5   2   1   1   1   1   1
       368:   16   8   4   2   1   1   1   1   1
       387:   16   9   3   3   1   1   1   1   1
       407:   14  11   5   2   1   1   1   1   1
       428:   17   7   4   2   1   1   1   1   1
       450:   15   9   5   2   1   1   1   1   1
       473:   11  11   4   2   1   1   1   1   1
       497:   16   7   4   2   1   1   1   1   1
       522:   18   9   3   2   1   1   1   1   1
       549:   14   9   3   3   1   1   1   1   1
       577:   16   8   4   2   1   1   1   1   1
       606:   11   6   3   2   1   1   1   1   1
       637:   13   7   4   2   1   1   1   1   1
       669:   18   9   3   3   1   1   1   1   1
       703:   19   9   3   2   1   1   1   1   1
       739:   18   9   3   2   1   1   1   1   1
       776:   18   8   4   2   1   1   1   1   1
       815:   22   5   5   2   1   1   1   1   1
       856:   15   8   4   2   1   1   1   1   1
       899:   13   8   3   2   1   1   1   1   1
       944:   16   8   4   2   1   1   1   1   1
       992:   16   8   4   2   1   1   1   1   1
      1042:   16   8   3   2   1   1   1   1   1
      1095:   15   5   5   3   1   1   1   1   1
      1150:   14  10   5   2   1   1   1   1   1
      1208:   17   8   4   2   1   1   1   1   1
      1269:   27   9   3   3   1   1   1   1   1
      1333:   18   9   4   2   1   1   1   1   1
      1400:   14   8   4   2   1   1   1   1   1
      1471:   15   7   5   2   1   1   1   1   1
      1545:   15   8   5   3   1   1   1   1   1
      1623:   15   9   3   3   1   1   1   1   1
      1705:   11  11   5   2   1   1   1   1   1
      1791:   12   9   3   3   1   1   1   1   1
      1881:   19   9   3   3   1   1   1   1   1
      1976:   19   8   4   2   1   1   1   1   1
      2075:   17   5   5   2   1   1   1   1   1
      2179:   18   9   3   2   1   1   1   1   1
      2288:   16   8   4   2   1   1   1   1   1
      2403:   16   9   3   3   1   1   1   1   1
      2524:   13   4   4   2   1   1   1   1   1
      2651:   11  11   5   2   1   1   1   1   1
      2784:   16   8   4   2   1   1   1   1   1
      2924:   17   6   4   2   1   1   1   1   1
      3071:   13  10   5   2   1   1   1   1   1
      3225:   15   8   5   3   1   1   1   1   1
      3387:   18   8   3   3   1   1   1   1   1
      3557:   14   7   4   2   1   1   1   1   1
      3735:   15   9   5   3   1   1   1   1   1
      3922:   16   8   3   2   1   1   1   1   1
      4119:   14   7   3   3   1   1   1   1   1
      4325:   23   5   5   2   1   1   1   1   1
      4542:   19   6   3   2   1   1   1   1   1
      4770:   15   9   5   2   1   1   1   1   1
      5009:   16   8   4   2   1   1   1   1   1
      5260:   20  10   4   2   1   1   1   1   1
      5524:   21   7   4   2   1   1   1   1   1
      5801:   20   8   4   2   1   1   1   1   1
      6092:   15   7   4   2   1   1   1   1   1
      6397:   13   6   4   2   1   1   1   1   1
      6717:   17   9   3   3   1   1   1   1   1
      7053:   15  11   3   3   1   1   1   1   1
      7406:   14   7   5   2   1   1   1   1   1
      7777:   16   7   4   2   1   1   1   1   1
      8166:   13   6   3   2   1   1   1   1   1
      8575:   25   7   5   2   1   1   1   1   1
      9004:   14   7   4   2   2   1   1   1   1
      9455:   17   5   5   2   1   1   1   1   1
      9928:   17   8   4   2   2   1   1   1   1
     10425:   15   8   5   3   1   1   1   1   1
     10947:   13  11   3   3   1   1   1   1   1
     11495:   19  11   5   2   1   1   1   1   1
     12070:   17  10   5   2   2   1   1   1   1
     12674:   19   8   4   2   2   1   1   1   1
     13308:   12   6   4   2   2   1   1   1   1
     13974:   17   6   3   2   2   1   1   1   1
     14673:   16   8   3   3   1   1   1   1   1
     15407:   15   7   7   2   1   1   1   1   1
     16178:   16   7   4   2   2   1   1   1   1
     16987:   19   6   3   2   1   1   1   1   1
     17837:   14   7   4   2   1   1   1   1   1
     18729:    9   9   3   3   1   1   1   1   1
     19666:   15   9   5   2   2   1   1   1   1
     20650:   14   7   5   2   2   1   1   1   1
     21683:   16   9   3   2   1   1   1   1   1
     22768:   16   8   4   2   2   1   1   1   1
     23907:   13  13   3   3   1   1   1   1   1
     25103:   13   7   7   2   1   1   1   1   1
     26359:   23   6   3   2   1   1   1   1   1
     27677:   13  11   4   2   1   1   1   1   1
     29061:   20   9   3   3   1   1   1   1   1
     30515:   17  11   5   2   1   1   1   1   1
     32041:   15   8   4   2   1   1   1   1   1
     33644:   13  13   4   2   2   1   1   1   1
     35327:   17   9   5   2   1   1   1   1   1
     37094:   17   7   4   2   2   1   1   1   1
     38949:   14   7   3   3   1   1   1   1   1
     40897:   16   8   4   2   1   1   1   1   1
     42942:   17   6   3   2   2   1   1   1   1
     45090:   15   9   5   2   2   1   1   1   1
     47345:   17   8   5   2   1   1   1   1   1
     49713:   16   8   3   3   1   1   1   1   1
     52199:   13   7   7   2   1   1   1   1   1
     54809:   17   8   4   2   1   1   1   1   1
     57550:   25  10   5   2   2   1   1   1   1
     60428:   18   9   4   2   2   1   1   1   1
     63450:   15   9   5   2   2   1   1   1   1
     66623:   17  10   3   2   1   1   1   1   1
     69955:   17   6   5   2   1   1   1   1   1
     73453:   12   6   4   2   1   1   1   1   1
     77126:   14   7   5   2   2   1   1   1   1
     80983:   18   7   7   2   1   1   1   1   1
     85033:   13   8   4   2   1   1   1   1   1
     89285:   17   7   5   2   1   1   1   1   1
     93750:   15  10   5   2   2   1   1   1   1
     98438:   13   6   4   2   2   1   1   1   1
    103360:   16   8   4   2   2   1   1   1   1
    108529:   16   8   4   2   1   1   1   1   1
    113956:   15   5   4   2   2   1   1   1   1
    119654:   13   6   4   2   2   1   1   1   1
    125637:   14   7   3   3   1   1   1   1   1
    131919:   19   6   3   3   1   1   1   1   1
    138515:   13  13   5   2   1   1   1   1   1
    145441:   16   8   4   2   1   1   1   1   1
    152714:   18  11   4   2   2   1   1   1   1
    160350:   15  10   5   2   2   1   1   1   1
    168368:   16   8   4   2   2   1   1   1   1
    176787:   13   9   3   3   1   1   1   1   1
    185627:   13   7   5   2   1   1   1   1   1
    194909:   13  11   4   2   1   1   1   1   1
    204655:   11  11   5   2   1   1   1   1   1
    214888:   14   8   4   2   2   1   1   1   1
    225633:   16   8   3   3   1   1   1   1   1
    236915:   16   7   5   2   1   1   1   1   1
    248761:   17   8   4   2   1   1   1   1   1
    261200:   16   8   4   2   2   1   1   1   1
    274261:   17   7   4   2   1   1   1   1   1
    287975:   21   5   5   2   1   1   1   1   1
    302374:   14   9   3   2   2   1   1   1   1
    317493:   17   9   3   3   1   1   1   1   1
    333368:   14   8   4   2   2   1   1   1   1
    350037:   19   9   3   3   3   1   1   1   1
    367539:   16   8   3   3   3   1   1   1   1
    385916:   11   6   4   2   2   1   1   1   1
    405212:   17  10   4   2   2   1   1   1   1
    425473:   16   8   4   2   1   1   1   1   1
    446747:   19   7   7   2   1   1   1   1   1
    469085:   14   7   5   2   1   1   1   1   1
    492540:   15  10   4   2   2   1   1   1   1
    517168:   16   8   4   2   2   1   1   1   1
    543027:   22  11   3   3   3   1   1   1   1
    570179:   14   7   7   2   1   1   1   1   1
    598688:   16   8   4   2   2   1   1   1   1
    628623:   15   9   3   3   3   1   1   1   1
    660055:   11  11   5   2   1   1   1   1   1
    693058:   16   8   3   2   2   1   1   1   1
    727711:   15  10   5   2   2   1   1   1   1
    764097:   16   8   3   3   3   1   1   1   1
    802302:   20   6   3   2   2   1   1   1   1
    842418:   17   9   3   2   2   1   1   1   1
    884539:   18   9   6   2   2   1   1   1   1
    928766:   18   9   5   2   2   1   1   1   1
    975205:   17   7   5   2   2   1   1   1   1
   1023966:   18   9   6   2   2   1   1   1   1
   1075165:   17   7   5   2   2   1   1   1   1
   1128924:   18   9   4   2   2   1   1   1   1
   1185371:   11  11   5   2   2   1   1   1   1
   1244640:   16   8   4   2   2   1   1   1   1
   1306873:   18   8   4   2   2   1   1   1   1
   1372217:   15   7   4   2   2   1   1   1   1
   1440828:   18   9   4   2   2   2   1   1   1
   1512870:   15  10   5   2   2   2   1   1   1
   1588514:   17   8   4   2   2   2   1   1   1
   1667940:   15  10   4   2   2   2   1   1   1
   1751338:   21   9   3   2   2   2   1   1   1
   1838905:   12   8   5   2   2   1   1   1   1
   1930851:   13   9   3   3   3   1   1   1   1
   2027394:   18   9   6   2   2   2   1   1   1
   2128764:   12  11   4   2   2   2   1   1   1
   2235203:   16   8   3   2   2   1   1   1   1
   2346964:   16   8   4   2   2   2   1   1   1
   2464313:   23   8   4   2   2   1   1   1   1
   2587529:   12   7   4   2   2   1   1   1   1
   2716906:   17   8   5   2   2   2   1   1   1
   2852752:   16   8   4   2   2   2   1   1   1
   2995390:   19  10   5   2   2   2   1   1   1
   3145160:   20   8   4   2   2   2   1   1   1
   3302419:   14   7   6   2   2   1   1   1   1
   3467540:   20  10   4   2   2   2   1   1   1
   3640918:   21   7   3   2   2   2   1   1   1
   3822964:   13  11   4   2   2   2   1   1   1
   4014113:   16   8   4   2   2   1   1   1   1
   4214819:   23   7   7   2   2   1   1   1   1
   4425560:   20   8   4   2   2   2   1   1   1
   4646839:   14   7   6   3   2   1   1   1   1
   4879181:   19  10   4   2   2   1   1   1   1
   5123141:   19  10   4   2   2   1   1   1   1
   5379299:   19   7   3   2   2   1   1   1   1
   5648264:   19   8   4   2   2   2   1   1   1
   5930678:   13  13   4   2   2   2   1   1   1
   6227212:   19  10   4   2   2   2   1   1   1
   6538573:   18   9   4   3   2   1   1   1   1
   6865502:   14   7   7   2   2   2   1   1   1
   7208778:   15   6   6   3   2   2   1   1   1
   7569217:   16   8   4   3   2   1   1   1   1
   7947678:   15   6   6   3   2   2   1   1   1
   8345062:   17  11   3   2   2   2   1   1   1
   8762316:   12   6   4   3   2   2   1   1   1
   9200432:   16   8   4   2   2   2   1   1   1
   9660454:   17  11   3   2   2   2   1   1   1
  10143477:   14   9   3   3   3   1   1   1   1
  10650651:   11  11   3   3   3   1   1   1   1
  11183184:   16   8   4   3   2   2   1   1   1
  11742344:   17   8   4   2   2   2   1   1   1
  12329462:   19   9   5   2   2   2   1   1   1
  12945936:   16   8   4   3   2   2   1   1   1
  13593233:   16   8   4   2   2   1   1   1   1
  14272895:   19   7   5   2   2   1   1   1   1
  14986540:   20  10   5   2   2   2   1   1   1
  15735868:   21   7   4   2   2   2   1   1   1
  16522662:   13   6   6   3   2   2   1   1   1
  17348796:   18   9   4   3   2   2   1   1   1
  18216236:   18   9   4   2   2   2   1   1   1
  19127048:   13   8   4   2   2   2   1   1   1
  20083401:   13   9   3   3   3   3   1   1   1
  21087572:   22  11   4   2   2   2   1   1   1
  22141951:   13  10   5   3   2   1   1   1   1
  23249049:   17   8   3   3   3   3   1   1   1
  24411502:   20   9   3   2   2   2   1   1   1
  25632078:   15   6   6   3   2   2   1   1   1
  26913682:   16   9   3   2   2   2   1   1   1
  28259367:   19   7   3   3   3   3   1   1   1
  29672336:   16   8   4   2   2   2   2   1   1
  31155953:   19   8   4   2   2   2   1   1   1
  32713751:   23   7   7   2   2   2   1   1   1
  34349439:   18   9   3   3   3   3   1   1   1
  36066911:   17  10   5   2   2   2   1   1   1
  37870257:   16   8   3   3   3   3   1   1   1
  39763770:   15  10   5   3   2   2   2   1   1
  41751959:   13  13   3   2   2   2   1   1   1
  43839557:   15  11   4   2   2   2   1   1   1
  46031535:   15   9   5   3   3   3   1   1   1
  48333112:   19   8   4   2   2   2   2   1   1
  50749768:   13   8   4   2   2   2   2   1   1
  53287257:   22   8   3   3   3   3   1   1   1
  55951620:   15  10   5   3   2   2   2   1   1
  58749202:   21   9   7   2   2   2   2   1   1
  61686663:   15  10   3   3   3   3   1   1   1
  64770997:   12  12   4   3   2   2   1   1   1
  68009547:   22  11   3   3   3   3   1   1   1
  71410025:   14   8   5   5   2   2   1   1   1
  74980527:   17  12   3   3   3   3   1   1   1
  78729554:   16   7   7   2   2   2   2   1   1
  82666032:   16   8   4   3   2   2   2   1   1
  86799334:   19   9   3   2   2   2   2   1   1
  91139301:   14   9   5   3   3   3   1   1   1
  95696267:   15   7   5   2   2   2   1   1   1
 100481081:   14   8   5   4   2   2   1   1   1
 105505136:   16   8   4   4   2   2   2   1   1
 110780393:   19   8   4   4   2   2   1   1   1
 116319413:   22   7   7   4   2   2   1   1   1
 122135384:   14   8   4   4   2   2   2   1   1
 128242154:   19   9   4   2   2   2   2   1   1
 134654262:   20   6   6   3   2   2   2   1   1
 141386976:   16   9   4   3   2   2   2   1   1
 148456325:   17   9   5   5   2   2   1   1   1
 155879142:   23   6   6   3   2   2   2   1   1
 163673100:   18   9   5   3   2   2   2   1   1
 171856756:   15   9   4   4   2   2   2   1   1
 180449594:   17  13   6   2   2   2   2   1   1
 189472074:   22  11   6   3   2   2   2   1   1
 198945678:   15   6   6   3   2   2   2   1   1
 208892962:   16   9   5   2   2   2   2   1   1
 219337611:   14  10   5   3   3   3   1   1   1
 230304492:   18   9   6   3   2   2   2   1   1
 241819717:   12  12   6   3   2   2   1   1   1
 253910703:   18  11   3   3   3   3   1   1   1
 266606239:   13   6   6   3   2   2   1   1   1
 279936551:   25  10   5   2   2   2   1   1   1
 293933379:   16   9   3   3   3   3   1   1   1
 308630048:   16   8   4   4   2   2   2   1   1
 324061551:   19   9   5   3   3   3   1   1   1
 340264629:   22   9   4   3   3   3   1   1   1
 357277861:   18   9   5   3   2   2   1   1   1
 375141755:   17   9   5   5   2   2   1   1   1
 393898843:   18   9   6   3   2   2   1   1   1
 413593786:   19   9   5   2   2   2   2   1   1
 434273476:   14   7   4   4   2   2   2   1   1
 455987150:   25  10   5   5   2   2   2   1   1
 478786508:   22  11   4   4   2   2   2   1   1
 502725834:   18   9   6   3   2   2   2   1   1
 527862126:   22  11   6   3   2   2   2   2   1
 554255233:   17   7   7   3   2   2   2   1   1
 581967995:   18   7   5   5   2   2   2   1   1
 611066395:   17   9   5   5   2   2   2   1   1
 641619715:   17  11   5   5   2   2   2   1   1
 673700701:   17  10   5   3   2   2   2   1   1
 707385737:   15   8   4   4   2   2   2   1   1
 742755024:   17   9   6   3   2   2   2   2   1
 779892776:   13   8   4   4   2   2   2   2   1
 818887415:   14   5   5   5   2   2   2   1   1
 859831786:   22  11   5   2   2   2   2   2   1
 902823376:   16   8   7   4   2   2   2   2   1
 947964545:   16  11   5   5   2   2   2   1   1
 995362773:   15  10   4   3   3   3   3   1   1
1045130912:   16   8   7   4   2   2   2   2   1
1097387458:   16   8   4   3   2   2   2   2   1
1152256831:   15  11   5   3   2   2   2   1   1
1209869673:   22   8   4   3   3   3   3   1   1
1270363157:   15   7   7   4   2   2   2   1   1
1333881315:   15   9   5   3   3   3   3   1   1
1400575381:   20  10   5   3   2   2   2   1   1
1470604151:   21  10   5   5   2   2   2   1   1
1544134359:   13  13   3   3   3   3   3   1   1
1621341077:   15  15   4   4   2   2   2   1   1
1702408131:   16   9   5   3   3   3   3   1   1
1787528538:   18   9   6   3   2   2   2   2   1
1876904965:   18  13   5   5   2   2   2   1   1
1970750214:   18   9   6   3   2   2   2   2   1



------------------

BTW: The printf ("string without format charcters") optimization is *-COOL-*.

-- 
Frank Klemm

Re: Loop unrolling

[Martin von Loewis]

> Not sure if this would be considered empty either.  

I believe this case that got this started is

struct Foo{
  Foo(){}
};

main()
{
  Foo foo[30];
}

g++ would generate a loop to call all the empty constructors, and
nobody would optimize-away this empty implicit loop.

Regards,
Martin

Re: Loop unrolling

[Jeffrey A Law]

  In message < 3602E6AF.ECC8E445@nospam.cantrip.org >you write:
  > Generally the kinds of "empty" loops that show up in template 
  > expansions look something like:
  > 
  >   for (i = 0; i < 0; ++i) *p++ = *q++;
That's not empty though :-)

The compiler is certainly free to unroll it fully though.

  > or probably more frequently
  >    
  >   for (i = 0; i < 10; ++i, ++p) { if (p); }
Not sure if this would be considered empty either.  

jeff

Re: Loop unrolling

[Nathan Myers]

Jeffrey A Law wrote:

>   > 2) Determining whether a loop is empty or not needs some kind of
>   >    register lifetime information.  Last I looked, this was not
>   >    reliable at the time of loop unrolling.  If this is no longer true,
>   >    then I can resurrect some code to do this.
> Maybe I misunderstood the kinds of loops people wanted to eliminate.
> I thought if they were empty there was nothing but an increment of
> the counter, and a condjump back to the counter increment.

Generally the kinds of "empty" loops that show up in template 
expansions look something like:

  for (i = 0; i < 0; ++i) *p++ = *q++;

or probably more frequently
   
  for (i = 0; i < 10; ++i, ++p) { if (p); }

Nathan Myers
ncm@cantrip.org

Re: Loop unrolling

[Scott A Crosby]

On Fri, 18 Sep 1998, Joern Rennecke wrote:

> > 2) Determining whether a loop is empty or not needs some kind of
> >    register lifetime information.  Last I looked, this was not
> >    reliable at the time of loop unrolling.  If this is no longer true,
> >    then I can resurrect some code to do this.
> 
> As long as the end value o the loop counter can be calculated, this is
> no problem.
> 

There are cases where a loop may be not empty or the iteration count
isn't known at compile time. 

You can have multiply-nested loops where the innermost one is empty, and
the others just wrap around around another loop who's final effect is
do-nothing. For example, case 'x2' below. (Does this happen with >1d
arrays of objects with do-nothing constructors, or constructors that are
proven to do nothing?)

I am not good at reading assembly code on x86, so I can't tell if/when
this happens, but there are several different cases of empty loops that
can/should be eliminated. What code is generated for the 7 constructions
below?

I have a feeling that the multidimensional case causes nested empty loops,
given that the compiler produces empty loops for the 1d case. Actually,
removing the latter 4 loops may be a much bigger win than the first 3 in
many templated instances. For loops that you can prove will terminate, you
don't necessarily have to know the end-value of the loop at compile time,
you just need to know that it is constant throughout the lifetime of the
loop.

class A { 
   int i ; 
public:
   A() {};
}


foo ( int a, int b, int c) {
   // These should only reserve a static amount of 
   //   space on the stack frame, and do nothing else. (no looping)
   A x1 [10];
   A x2 [10][10];
   A x3 [10][10][10];

   // These should only calculate and reserve a static amount of space 
   //   on the stack frame, and do nothing else. (no looping)
   A y1 [a];
   A y2 [a][10];
   A y3 [a][b];
   A y4 [a][10][b][10][c];

}

Scott



--
This sig is the answer to the ultimate question of life, the universe, and
everything else.

Re: Loop unrolling

[Joern Rennecke]

> 2) Determining whether a loop is empty or not needs some kind of
>    register lifetime information.  Last I looked, this was not
>    reliable at the time of loop unrolling.  If this is no longer true,
>    then I can resurrect some code to do this.

As long as the end value o the loop counter can be calculated, this is
no problem.

Re: Loop unrolling

[Lee Iverson]

In message < 12183.906015270@hurl.cygnus.com > you write:
> 
>   In message <Pine.GSO.4.03.9809161956460.15088-100000@markab.dbai.tuwien.ac.
> at>you write:
>   > The current state of this is that basically the discussion has stopped
>   > without any clear decision for or against removal of empty loops and
>   > that currently the documentation does not (always) match actual behaviour
> .
> I thought I had said something about this.
> 
> Basically I have no objection to the optimizers removing empty loops.
> The old arguments against removing them were lame to start with and
> they're even more lame now.
> 
> If someone wants to submit code to allow loop.c to remove such loops,
> it will not be rejected because "gcc isn't supposed to remove empty
> loops".

The technical problems are:

1) Semi-reliably determine that a loop terminates (the constraint is
   all one-sided in that we can never delete a loop unless we can
   prove that it terminates).

2) Determining whether a loop is empty or not needs some kind of
   register lifetime information.  Last I looked, this was not
   reliable at the time of loop unrolling.  If this is no longer true,
   then I can resurrect some code to do this.

-------------------------------------------------------------------------------
Lee Iverson     		SRI International
leei@ai.sri.com			333 Ravenswood Ave., Menlo Park CA 94025
http://www.ai.sri.com/~leei/	(650) 859-3307

Re: Loop unrolling

[Jeffrey A Law]

  In message < 199809171822.LAA23671@Canada.AI.SRI.COM >you write:
  > The technical problems are:
  > 
  > 1) Semi-reliably determine that a loop terminates (the constraint is
  >    all one-sided in that we can never delete a loop unless we can
  >    prove that it terminates).
Absolutely correct.

  > 2) Determining whether a loop is empty or not needs some kind of
  >    register lifetime information.  Last I looked, this was not
  >    reliable at the time of loop unrolling.  If this is no longer true,
  >    then I can resurrect some code to do this.
Maybe I misunderstood the kinds of loops people wanted to eliminate.
I thought if they were empty there was nothing but an increment of
the counter, and a condjump back to the counter increment.

Obviously we can not eliminate a loop if we can not prove doing so
is safe.

jeff

Re: Loop unrolling

[Jeffrey A Law]

  In message < Pine.GSO.4.03.9809161956460.15088-100000@markab.dbai.tuwien.ac.at >you write:
  > The current state of this is that basically the discussion has stopped
  > without any clear decision for or against removal of empty loops and
  > that currently the documentation does not (always) match actual behaviour.
I thought I had said something about this.

Basically I have no objection to the optimizers removing empty loops.
The old arguments against removing them were lame to start with and
they're even more lame now.

If someone wants to submit code to allow loop.c to remove such loops,
it will not be rejected because "gcc isn't supposed to remove empty
loops".


jeff

Re: Loop unrolling

[Scott A Crosby]

On Wed, 16 Sep 1998, Joern Rennecke wrote:

> It is a special case of loop unrolling.  It is fairly easy to modify
> unroll.c to completely unroll all empty loops.  The tricky part is that
> some loops might not terminate before unrolling, yet unrolling them
> completely removes them.

Also, you would want to rerun this pass multiple times, because you might
have multiple-nested empty loops. (I think this could happen when you 
initializing a multidimensional array of objects.)

It would at least help a 'little' at speeding up template code and it
would definitely remove unnecessary do-nothing code, decreasing
code-bloat a small amount.

Scott

--
This message is copyright 1998 by Scott A Crosby. Unauthorized
reproduction or duplication if forbidden without the express permission of
the author.

Re: Loop unrolling

[Gerald Pfeifer]

On Wed, 16 Sep 1998, Scott A Crosby wrote:
> I hate to bring up a 3 month-old horse, but has anyone added in such
> functionality to remove empty loops, unconditionally? (Or, could a
> complete newbie GCC/EGCS hacker add it in himself and submit a patch?)

The current state of this is that basically the discussion has stopped
without any clear decision for or against removal of empty loops and
that currently the documentation does not (always) match actual behaviour.

The issue is now upon Jeff Law (egcs maintainer) to resolve, who probably
has been to busy to review the entire mail thread lately and is now in
EOQ meetings at Cygnus. 

Once a decision has been taken, I'll immediately correct the documentation
to reflect the desired behavior.

Gerald, who actually started this whole discussion, by the way.
-- 
Gerald Pfeifer (Jerry)      Vienna University of Technology
pfeifer@dbai.tuwien.ac.at   http://www.dbai.tuwien.ac.at/~pfeifer/

Re: Loop unrolling

[Joern Rennecke]

> I hate to bring up a 3 month-old horse, but has anyone added in such
> functionality to remove empty loops, unconditionally? (Or, could a
> complete newbie GCC/EGCS hacker add it in himself and submit a patch?)

It is a special case of loop unrolling.  It is fairly easy to modify
unroll.c to completely unroll all empty loops.  The tricky part is that
some loops might not terminate before unrolling, yet unrolling them
completely removes them.

Re: Loop unrolling

[Jeffrey A Law]

  In message < Pine.LNX.3.95.980916022553.4023B-100000@qwe3.math.cmu.edu >you write:
  > I hate to bring up a 3 month-old horse, but has anyone added in such
  > functionality to remove empty loops, unconditionally? (Or, could a
  > complete newbie GCC/EGCS hacker add it in himself and submit a patch?)
Nobody has contributed such functionality --  or if they did, it got
buried in the mountain of mail on this topic.


jeff

Re: Loop unrolling

[Scott A Crosby]

On Wed, 3 Jun 1998, Nathan Myers wrote:

> This is absolutely correct.  The performance of programs that use STL
> facilities, and similar libraries like Blitz++, is utterly dependent on 
> the compiler crushing out "abstraction overhead", which often means 
> empty loops.  
> 
> It is impossible in general for the programmer to ensure that empty loops 
> are not generated, because with templates there is no one place in the source
> where all such knowledge is available.
> 
> Perhaps in C code such loops cannot be eliminated without some political
> wrangling, but there can be no such excuse for g++. 

I hate to bring up a 3 month-old horse, but has anyone added in such
functionality to remove empty loops, unconditionally? (Or, could a
complete newbie GCC/EGCS hacker add it in himself and submit a patch?)

Scott


--
This message is copyright 1998 by Scott A Crosby. Unauthorized
reproduction or duplication if forbidden without the express permission of
the author.

Re: Loop unrolling

[Mike Stump]

Ok, that's two people that don't mind just ripping all special
handling of empty loops out.  If that is the direction the maintainers
choose, then the right patch to install is one that just removes the
hair of it all, or maybe one that says gcc used to try and preserve
empty loops in the past, but now doesn't as code can use other
mechanisms (like volatile) if they want.

So, I haven't heard from Jim or Jeff....  I won't object to it's
removal, as it seams kinda old to me.  I agree, from a C++
perspective, it'd be nice to remove it, also it enhances the
predictability of the compiler.

So, I guess this is the close of this thread...  I think everything
important has been said, and all side presented, now just up to Law
and/or whoever else he chooses.  :-)

Re: Loop unrolling

[Joern Rennecke]

> What you mean to say is that people that expect gcc to correctly
> compile old style timing loops are wrong for expecting it to work, and
> that you think we should break their existing code, renig on our
> documented promise to not break their code, and remove this documented
> GNU extension from gcc, and break their code.

When I first read that part of the documentation - I was still a mere
gcc user then - I understood it to be an explanation, not to say an
apology, why empty loops are not optimized out.
The reasoning why removing empty loops is not worth the bother no
longer holds.  Hence we should remove them.
We should probably avoid loops with volatile loop variables for the
time being, but we should not condone this as a valid way to write
a timing loop.  If you must write a timing loop, make it non-empty
in such a way that the contents cannot be optimized out
(e.g. an asm volatile that uses the loop counter in a register).

Re: Loop unrolling

[Horst von Brand]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2939 bytes --]

mrs@wrs.com (Mike Stump) said:
> > From: Horst von Brand <vonbrand@sleipnir.valparaiso.cl>
> > mrs@wrs.com (Mike Stump) said:

> > [...]

[...]

> > That is a horribly broken idea.

> What you mean to say is that people that expect gcc to correctly
> compile old style timing loops are wrong for expecting it to work, and
> that you think we should break their existing code, renig on our
> documented promise to not break their code, and remove this documented
> GNU extension from gcc, and break their code.

How many people are really using empty timing loops? How many of them use
different gccs for timing loops and expect them to time the same? If I was
to write a timing loop, I certainly wouldn't rely on gcc to give me the
same timing everytime: The loop that computes BogoMIPS inside Linux is
written in assembly, and for good reason. That's what I think is a horribly
broken idea. That, and the misguided "niceness" to programmers that don't
know better and write empty loops for timing in C. 

As you state, this adds hair to the compiler (which is widely considered
way too hairy as it is). Several rather ad hoc (and very un-C-like, IMHO)
lexical conventions for expressing "purposely empty loops" have been
proposed.

There was a flamewar not long ago (in comp.lang.c, IIRC) where somebody
complained bitterly that the compiler would not execute his statements
exactly as written. It was very forcefully stated that the compiler had to
give results "as if" it did was was written down; if it knew a better way
to do what it was asked to do, by all means use it! The C compiler today
(with weird CPUs, caches, ...) is a rather different animal than the
simplistic C compiler of early Unix systems and PCs.

[...]

> That is a fine thing to say, but it is better to express it that way
> so that people understand the totality of your statement, otherwise
> people that don't know better are led to the mistaken conclusion that
> I am just misguided and that you are obviously correct.

OK, maybe I didn't state both sides evenly. But please show cases of people
that really depend on this rather bizarre behaviour of gcc.

> > That way you have to get non-standard lexical information down to
> > the loop-optimizer.

> And?

Unecesary hair.

> > The data paths for that surely aren't in place,

> They mostly are, but some icky code would have to be added to get the
> last ounce of performance out of the optimizer, if one wanted it.

Better leave the icky code out. As the old maxim says: "The code that costs
the least to program, costs least runtime and least memory space, and which
moreover costs least to document and maintain is the code that isn't
there." Icky code is fine, so long as you can show a clear need for it. In
this case, I just can't see any.
-- 
Horst von Brand                             vonbrand@sleipnir.valparaiso.cl
Casilla 9G, Viña del Mar, Chile                               +56 32 672616

Re: Loop unrolling

[Mike Stump]

> Date: Sat, 13 Jun 1998 08:32:30 -0500
> From: Horst von Brand <vonbrand@sleipnir.valparaiso.cl>

> mrs@wrs.com (Mike Stump) said:

> [...]

> > Well, this wasn't the result of the consersation when last we agreed
> > on what to do and what the doc meant and what the compiler should do.
> > The decision whether or not a loop could be removed was to be decided
> > by the source input tokens to the lexer.  Not by the existing rtl
> > codes.

> That is a horribly broken idea.

What you mean to say is that people that expect gcc to correctly
compile old style timing loops are wrong for expecting it to work, and
that you think we should break their existing code, renig on our
documented promise to not break their code, and remove this documented
GNU extension from gcc, and break their code.

Do I have that right?

If so, that is a much better way to phrase it.  I won't argue against
it heavily.

That is a fine thing to say, but it is better to express it that way
so that people understand the totality of your statement, otherwise
people that don't know better are led to the mistaken conclusion that
I am just misguided and that you are obviously correct.

> That way you have to get non-standard lexical information down to
> the loop-optimizer.

And?

> The data paths for that surely aren't in place,

They mostly are, but some icky code would have to be added to get the
last ounce of performance out of the optimizer, if one wanted it.

Re: Loop unrolling

[Horst von Brand]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 917 bytes --]

mrs@wrs.com (Mike Stump) said:

[...]

> Well, this wasn't the result of the consersation when last we agreed
> on what to do and what the doc meant and what the compiler should do.
> The decision whether or not a loop could be removed was to be decided
> by the source input tokens to the lexer.  Not by the existing rtl
> codes.

That is a horribly broken idea. That way you have to get non-standard
lexical information down to the loop-optimizer. The data paths for that
surely aren't in place, and would just add gratuitous complexity. All just
for supporting a broken feature.

There are non-intrusive solutions, like the asm volatile ("" : : : "r(i)")
idea. If somebody wants to do something like this, they deserve to have to
write it this way, IMHO.
-- 
Horst von Brand                             vonbrand@sleipnir.valparaiso.cl
Casilla 9G, Viña del Mar, Chile                               +56 32 672616

Re: Loop unrolling

[Daniel Egger]

On Fri, 12 Jun 1998, Alexandre Oliva wrote:

>So why don't we decide to remove empty loops regardless of them being
>explicit or not, and suggest people to use this syntax or
>-fno-remove-empty-loops in order to prevent empty loops from being
>optimized away?

 Could anyone please sum up what this thread is all about?
 Especially the part: Why do I need empty loops...
 They aren't even usefull for benchmarking jumps.....

--

Servus,
       Daniel

Re: Loop unrolling

[Tim Hollebeek]

Alexandre Oliva writes ...
> 
> The {{;;}} sequence would be recognized by gcc as a special token,
> that expanded to a special RTL node that marked the enclosing loop as
> non-removable.
> 
> Alternatively, we could use this ``nonsense'' definition you have
> presented to denote non-removable empty loops.

And someone has to explain why these completely arbitrary constructs are
superior to a normal loop over a volatile variable, which seems like a 
far more natural way to express this concept.

---------------------------------------------------------------------------
Tim Hollebeek                           | "Everything above is a true
email: tim@wfn-shop.princeton.edu       |  statement, for sufficiently
URL: http://wfn-shop.princeton.edu/~tim |  false values of true."

Re: Loop unrolling

[Mike Stump]

> From: Alexandre Oliva <oliva@dcc.unicamp.br>
> Date: 12 Jun 1998 17:53:53 -0300

> So why don't we decide to remove empty loops regardless of them
> being explicit or not, and suggest people to use this syntax or
> -fno-remove-empty-loops in order to prevent empty loops from being
> optimized away?

I haven't seen a good reason yet to add a flag.  Flags cost money.
Don't add a flag, unless you have a good reason.

Re: Loop unrolling

[Mike Stump]

> Date: Fri, 12 Jun 1998 16:09:22 -0600
> From: Jeffrey A Law <law@hurl.cygnus.com>

> An empty loop would be a loop with a body that consists of a counter
> increment and branch to the top of the loop (at the RTL level).
> Nothing more, nothing less.

> I don't think trying to describe what an empty loop is with C
> source is all that interesting since in the end it's going to be
> detected by the loop optimizer.

Well, this wasn't the result of the consersation when last we agreed
on what to do and what the doc meant and what the compiler should do.
The decision whether or not a loop could be removed was to be decided
by the source input tokens to the lexer.  Not by the existing rtl
codes.

Oh course, the optimizer still has to examine the loop to figure out
if it can remove it but this is separate if you will...

Re: Loop unrolling

[Mike Stump]

> From: Joern Rennecke <amylaar@cygnus.co.uk>
> To: branko.cibej@hermes.si (Branko Cibej)
> Date: Fri, 12 Jun 1998 17:42:58 +0100 (BST)
> Cc: mrs@wrs.com, egcs@cygnus.com, pfeifer@dbai.tuwien.ac.at

> Apropos... is the following an empty loop?

I feel these cases were already covered in my prior definition...

> for (i = 0; i <= 9; i = foo (i));

Yes.

> Or this one?

> for (i = 0; i <= bar (); i++);

Yes.

> Or that one?

> for (i = 0; baz (i, 9); i++);

Yes.

The token sequence `);' is the definition of empty (only for while and
for statements).  For a do while statement, as some cleaver person
pointed out, the sequemce would be do {} while or do ; while.

Re: Loop unrolling

[Joern Rennecke]

> for (i = 0; i < 10; ++i) __asm __volatile ("" : );
> 
> cannot be removed.  no need for special syntax.

It cannot be removed, but it can be unrolled.  And since the loop
count isn't used, no instructions are needed.

If you write instead:
for (i = 0; i < 10; ++i) __asm __volatile ("" : : "r" (i));
gcc still has to do one register load per iteration.

Re: Loop unrolling

[Mike Stump]

> To: Richard Henderson <rth@cygnus.com>
> Cc: Mike Stump <mrs@wrs.com>, amylaar@cygnus.co.uk, egcs-patches@cygnus.com,
>         egcs@cygnus.com, pfeifer@dbai.tuwien.ac.at
> From: Alexandre Oliva <oliva@dcc.unicamp.br>
> Date: 12 Jun 1998 17:16:24 -0300
> X-Emacs: 20.4 "Emerald" XEmacs  Lucid without mule

> Richard Henderson <rth@cygnus.com> writes:

> Someone once has suggested a special syntax to denote an empty loop:

> for (i=0; i<10; ++i) {{;;}}

> The {{;;}} sequence would be recognized by gcc as a special token,
> that expanded to a special RTL node that marked the enclosing loop as
> non-removable.

This is wrong.  It was that we wanted the simple form to be
non-removable.  If we decide to change this, then we will just to to
remove any and all special handling, and just require the use
volatile...  not do anything like the above.

Now, if you want it to be removable, then we can make the above be
removable, and make only the ``;'' and ``{}'' forms non-removable, or
maybe just the ``;'' form.

Re: Loop unrolling

[Alexandre Oliva]

Richard Henderson <rth@dot.cygnus.com> writes:

> On Fri, Jun 12, 1998 at 05:16:24PM -0300, Alexandre Oliva wrote:
>> for (i=0; i<10; ++i) {{;;}}

> for (i = 0; i < 10; ++i) __asm __volatile ("" : );

> cannot be removed.  no need for special syntax.

So why don't we decide to remove empty loops regardless of them being
explicit or not, and suggest people to use this syntax or
-fno-remove-empty-loops in order to prevent empty loops from being
optimized away?

-- 
Alexandre Oliva
mailto:oliva@dcc.unicamp.br mailto:aoliva@acm.org
http://www.dcc.unicamp.br/~oliva
Universidade Estadual de Campinas, SP, Brasil

Re: Loop unrolling

[Richard Henderson]

On Fri, Jun 12, 1998 at 05:16:24PM -0300, Alexandre Oliva wrote:
> for (i=0; i<10; ++i) {{;;}}

for (i = 0; i < 10; ++i) __asm __volatile ("" : );

cannot be removed.  no need for special syntax.


r~

Re: Loop unrolling

[Alexandre Oliva]

Richard Henderson <rth@cygnus.com> writes:

> Also a nonsense definition:

> 	for (i = 0; i < 10; ++i) continue;

Someone once has suggested a special syntax to denote an empty loop:

for (i=0; i<10; ++i) {{;;}}

The {{;;}} sequence would be recognized by gcc as a special token,
that expanded to a special RTL node that marked the enclosing loop as
non-removable.

Alternatively, we could use this ``nonsense'' definition you have
presented to denote non-removable empty loops.

-- 
Alexandre Oliva
mailto:oliva@dcc.unicamp.br mailto:aoliva@acm.org
http://www.dcc.unicamp.br/~oliva
Universidade Estadual de Campinas, SP, Brasil

Re: Loop unrolling

[Richard Henderson]

On Thu, Jun 11, 1998 at 11:04:17AM -0700, Mike Stump wrote:
> > Well, how about some plain C macroid code:
> 
> macros are not your friend, don't use them.

Ok, now that's just stupid.  Macros in C are as to inlines in C++,
that is, indespensible.

> Having said that...
> After preprocessing, the ')' and ';' appear adjacent, hence it is a
> empty loop, hence it should not be removed.

Also a nonsense definition:

	for (i = 0; i < 10; ++i) continue;

is by that definition not an empty loop.  But if you distinguish
between that and just `;' you are being gratuitously obtuse.

In summary, there are lots of empty loops that occur naturally
in C, very few programs rely on such things, and for them we
provide a switch.


r~

Re: Loop unrolling

[Mike Stump]

> From: Joern Rennecke <amylaar@cygnus.co.uk>
> To: mrs@wrs.com (Mike Stump)
> Date: Thu, 11 Jun 1998 13:18:50 +0100 (BST)
> Cc: pfeifer@dbai.tuwien.ac.at, egcs-patches@cygnus.com, egcs@cygnus.com

> Well, how about some plain C macroid code:

macros are not your friend, don't use them.  Having said that...
After preprocessing, the ')' and ';' appear adjacent, hence it is a
empty loop, hence it should not be removed.

> #define NOP(X, N) /* This space intentionally left blank */

> #define FROB(X, OP) \
> do { \
>   foo (x); \
>   for (i = n; --i >=0; ) \
>     OP (X, i); \
>   bar(x); \
> } while (0);

> FROB (x, NOP);

Re: Loop unrolling

[Sol Foster]

mrs@wrs.com (Mike Stump) wrote:
> The definition of loop means the use of the keyword ``for'' or
> ``while''. 

So what's the word for "a piece of code that exhibits looping behaviour
but is generated automatically by the compiler"?  I take it that the cases
are handled distinctly by EGCS.

> The definition of empty (in C and C++) means that textually
> in the users source program, the character ';' follows the ')' from
> the loop syntax.

Before or after the preprocessor runs on it?  Is "while (1) {}" not an
empty loop?

> I know, somewhat arbitrary, but prefectly clear.  This was the result
> of the conversation from eons ago that we had.  

I was not aware that special, non-obvious meanings had been given to these
terms.  Forgive me my earlier post on this subject.

So I take it that your opinion is that 

    for (i = 0; i < 10; i++);

should not be optimized away, but 

    inline void DoNothing () {}

    for (i = 0; i < 10; i++) DoNothing ();

can be?  I know that's fine with me.

-- 
Sol Foster: colomon@ralf.org

Sometimes I think the world has gone completely mad.  And then I 
think, "Aw, who cares?"  And then I think, "Hey, what's for supper?" 
                                        -Jack Handey

Re: Loop unrolling

[Jeffrey A Law]

  In message < Pine.GSO.3.96.980603144750.28549B-100000@nashira.dbai.tuwien.ac.at >you write:
  > Jeff, what happened to my patch? You neither commented on it nor has
  > it been installed. :-(
I'm still waiting for the discussion to die down.  There seems to
be a significant desire to remove empty loops, which seems reasonable
to me.  If we go that route, then the doc changes are going to need
to be revamped again.

jeff

Re: Loop unrolling

[Gerald Pfeifer]

On Mon, 1 Jun 1998, Mike Stump wrote:
> I don't think this should go in the docs.  I think it is a bug in the
> unroller that gcc optimizes away an empty loop.  I think this should
> be fixed.  I think the docs can admit the current bug, but should not
> call it anything but a bug.

I'm the one who started this monster thread, and actually I believe that
John Carr <jfc@mit.edu>, Branko Cibej <branko.cibej@hermes.si>, Martin
von Loewis <martin@mira.isdn.cs.tu-berlin.de> have provided examples that 
empty loops _should_ get removed.

Jeff, what happened to my patch? You neither commented on it nor has
it been installed. :-(

Please find below a typo-fixed version of my patch. (Thanks go to
Craig Burley <burley@gnu.org>!)

Gerald


Mon Jun  1 22:28:31 1998  Gerald Pfeifer <pfeifer@dbai.tuwien.ac.at>

	* ``Empty'' loops sometimes do get deleted and can indeed be
	generated by optimization.
	  

Index: gcc.texi
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/gcc.texi,v
retrieving revision 1.11
diff -r1.11 gcc.texi
2004,2006c2004,2007
< GNU CC does not delete ``empty'' loops because the most likely reason
< you would put one in a program is to have a delay.  Deleting them will
< not make real programs run any faster, so it would be pointless.
---
> GNU CC does not delete ``empty'' loops because (historically) the most
> likely reason you would put one in a program was to have a delay.
> Deleting these will not make real programs run any faster, so it would 
> be pointless.
2008,2009c2009,2015
< It would be different if optimization of a nonempty loop could produce
< an empty one.  But this generally can't happen.
---
> However, the rationale here was that optimization of a nonempty loop
> cannot produce an empty one, which holds for C but is not the case for
> C++ in general.
> 
> Moreover, with @samp{-funroll-loops} small ``empty'' loops indeed are
> removed, so the current behavior is both sub-optimal and inconsistent
> and may well change in the future. 

Re: Loop unrolling

[Kaz Kylheku]

On Sun, 7 Jun 1998, Jeffrey A Law wrote:

> 
>   In message < 199806042119.OAA03778@atrus.synopsys.com >you write:
>   > > Why can't GCC go a step farther and honor the volatile attribute for
>   > > any auto object?  
>   > 
>   > Yes, if someone writes an automatic volatile variable, they've presumably d one
>   > so for a reason, so we should give them what they expect (don't optimize
>   > redundant reads and writes).
> Right.  Principle of least suprise.
> 
> IMHO, if I've stuck "volatile" on something, the optimizers should
> treat it as potentially changing at any time, regardless of the
> storage class of the object.

You are right.

By the way there is something we have been overlooking in these debates:
the possibility that a program might do something to clobber the cached
values of some objects, which necessitates reloading them from
the underlying storage.

This can even happen to auto objects whose address is never taken---the
obvious example is that of a longjmp which does not necessarily
restore the full machine context.

Thus volatile has to be honored on auto variables as well, however not
across code that cannot be interrupted by a setjmp/longjmp activity. :) 

Re: Loop unrolling

[Jeffrey A Law]

  In message < 199806042119.OAA03778@atrus.synopsys.com >you write:
  > > Why can't GCC go a step farther and honor the volatile attribute for
  > > any auto object?  
  > 
  > Yes, if someone writes an automatic volatile variable, they've presumably d one
  > so for a reason, so we should give them what they expect (don't optimize
  > redundant reads and writes).
Right.  Principle of least suprise.

IMHO, if I've stuck "volatile" on something, the optimizers should
treat it as potentially changing at any time, regardless of the
storage class of the object.


jeff

Re: Loop unrolling

[Joern Rennecke]

> Yes, if someone writes an automatic volatile variable, they've presumably done
> so for a reason, so we should give them what they expect (don't optimize
> redundant reads and writes).

Well, maybe they passed the address of that variable to a function that
might do something funny with it - but in this loop, the function call
was unreachable and optimized away.  Since we have ADDRESSOF now, the
address-taking doesn't force variables into the stack if the address
use is optimized away.

I'm not saying that we should do this kind of optimization right now, but
just pointing out that there are valid reasons to want it, and a programmer
should not rely on volatile for timing effects.

Re: Loop unrolling

[Joe Buck]

> Kaz Kylheku writes:
>  > Of course, the compiler in question is GCC, which must meet additional
>  > requirements because it is intended to support access to hardware
>  > and threading. For that reason it must honor the volatile attribute
>  > for static objects, objects referred to through pointers and auto
>  > objects whose address is taken, to be safe.
> 
> Why can't GCC go a step farther and honor the volatile attribute for
> any auto object?  

Yes, if someone writes an automatic volatile variable, they've presumably done
so for a reason, so we should give them what they expect (don't optimize
redundant reads and writes).

Re: Loop unrolling

[Martin von Loewis]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1043 bytes --]

> Is that from the C++ DWP? 

Yes. The concepts (sequence point, side effect) are borrowed from C++,
though.

> How does it define observable behavior?

>> The observable behavior of the abstract machine is its sequence of
>> reads and writes to volatile data and calls to library I/O
>> functions.6)

with footnote 6: 

>> An implementation can offer additional library I/O functions as an
>> extension. Implementations that do so should treat calls to those
>> functions as ''observable behavior'' as well.

The relation to sequence points is explained as

>> A conforming implementation executing a well­formed program shall
>> produce the same observable behavior as one of the possible
>> execution sequences of the corresponding instance of the abstract
>> machine with the same program and the same input.

> Who is the observer?

This standard does not deal with human-machine interaction. However,
the intent is clear: Observable behaviour really happens, and can be
observed by anyone using the conforming implementation.

Martin

Re: Loop unrolling

[Kaz Kylheku]

On Wed, 3 Jun 1998, Martin von Loewis wrote:

> > i has automatic storage, and its address is never taken, so the compiler
> > might decide to allocate this object to some 'write-only-memory'.
> 
> No, it may not. Modification of i is 'observable behaviour' as per
> [intro.execution]/6. So I want to observe this on the machine in front
> of me. If the compiler optimizes the loop away, I cannot observe it.
> If it would leave the loop, I could observe it, eg. by means of a
> debugger.

What document is this from? I don't recognize it as being part of the
current C standard. Clause 6 of ISO C describes the elements of
the language.

Is that from the C++ DWP? How does it define observable behavior?
Who is the observer?

Re: Loop unrolling

[Gavin Romig-Koch]

Kaz Kylheku writes:
 > Of course, the compiler in question is GCC, which must meet additional
 > requirements because it is intended to support access to hardware
 > and threading. For that reason it must honor the volatile attribute
 > for static objects, objects referred to through pointers and auto
 > objects whose address is taken, to be safe.

Why can't GCC go a step farther and honor the volatile attribute for
any auto object?  

                                             -gavin...

Re: Loop unrolling

[Gavin Romig-Koch]

Kaz Kylheku writes:
 > Of course, the compiler in question is GCC, which must meet additional
 > requirements because it is intended to support access to hardware
 > and threading. For that reason it must honor the volatile attribute
 > for static objects, objects referred to through pointers and auto
 > objects whose address is taken, to be safe.

Why can't GCC go a step farther and honor the volatile attribute for
any auto object?  

                                             -gavin...

Re: Loop unrolling

[Kaz Kylheku]

On Wed, 3 Jun 1998, Joe Buck wrote:

> 
> > No.  The "volatile" requires the compiler to keep the implied
> > loads and stores, dispite the as-if rule, and thus the loop is
> > not empty, and thus not deleted.
> 
> I don't believe the standard ever makes an exception to the as-if rule.
> 'volatile' for a static or global variable matters because you can
> write a program where the effect is visible (make it multithreaded,

Volatile matters for auto variables too, if their address is taken.
However poor the practice may be, the address of such a variable may
be communicated to another thread.

> use a signal handler, map the variable to a hardware register).
> Thus 'volatile' is *not* an exception to as-if.

Actually, the standard doesn't define support for threading or hardware
register mapping, and the only thing that a maximally portable signal
handler may do is access a static object of type volatile sig_atomic_t. 

Thus to adhere with the as-if rule, a compiler can ignore the
the recommendations with respect to volatile. If a strictly conforming
program can't tell the difference, it's conforming. A strictly conforming
program can't be multi-threaded, nor can it access hardware registers.
There is no way for it to detect the changes in the state of the
execution environment brought about by accesses to volatile objects.

Of course, the compiler in question is GCC, which must meet additional
requirements because it is intended to support access to hardware
and threading. For that reason it must honor the volatile attribute
for static objects, objects referred to through pointers and auto
objects whose address is taken, to be safe.

A strict interpretation of the standard motivated by the desire to
determine what an implementation can get away with and still be
conforming is not appropriate to GCC.

Re: Loop unrolling

[Stephen Williams]

I think I'm the embedded programmer that started this thread. (Sorry:-)


branko.cibej@hermes.si said:
> If they want _accurate_ timing loops, they should, as Tim Hollebeek
> pointed out, use asm statements. Otherwise they can always use
> volatile loop variables. 

If I want inaccurate timing loops (that is, at *least* some number of
iterations and excess is OK) I put a thread_yield() in the body.

If I want more accurate loops that really waits for a certain number of
bus cycle clocks, I will read a volatile variable in the body. For example,
if a device needs N PCI clocks to complete something, I can usually resort
to a PCI read N/2 times.

If wall-clock time is important, I use an interval timer or an assembly
coded nap function.

As one of the embedded programmers who read gcc.info and believed it, I would
be delighted to see egcs eliminate empty loops, always unroll short loops,
etc. It would even be OK to me if:

	for (int idx = 0 ; idx < 4 ;  idx += 1)
		asm("");

were to go away, as long as I can change the body to "asm volatile ("")"
to prevent the loop vanishing, although I can even see that being changed
into:

	asm volatile("");
	asm volatile("");
	asm volatile("");
	asm volatile("");

(Yikes!)

This leaves:

	for (volatile idx = 0 ;  idx < 4 ;  idx += 1)
		;

as something that should continue to work as it does now. Heck, turning
that into:

	idx = 0;
	idx = 1;
	idx = 2;
	idx = 3;

would get the desired delay.
-- 
Steve Williams                "The woods are lovely, dark and deep.
steve@icarus.com              But I have promises to keep,
steve@picturel.com            and lines to code before I sleep,
http://www.picturel.com       And lines to code before I sleep."

Re: Loop unrolling

[Martin von Loewis]

> i has automatic storage, and its address is never taken, so the compiler
> might decide to allocate this object to some 'write-only-memory'.

No, it may not. Modification of i is 'observable behaviour' as per
[intro.execution]/6. So I want to observe this on the machine in front
of me. If the compiler optimizes the loop away, I cannot observe it.
If it would leave the loop, I could observe it, eg. by means of a
debugger.

Regards,
Martin

Re: Loop unrolling

[Nathan Myers]

Branko Cibej wrote:
> My previous post with the template class
> example contains only loops written by the user -- but some STL containers
> (e.g., vector) have almost identical initialisation code.
> 
> Yes, the compiler could treat code in the standard library as "written by the
> compiler", but what if the user wrote her own STL-like container?
> 
> (I'm sure nobody wants a new #pragma :)
> 
> > This might also keep embedded programmers who believed the gcc manual
> > and wrote timing loops happy.
> 
> If they want _accurate_ timing loops, they should, as Tim Hollebeek pointed
> out, use asm statements. Otherwise they can always use volatile loop variables.

This is absolutely correct.  The performance of programs that use STL
facilities, and similar libraries like Blitz++, is utterly dependent on 
the compiler crushing out "abstraction overhead", which often means 
empty loops.  

It is impossible in general for the programmer to ensure that empty loops 
are not generated, because with templates there is no one place in the source
where all such knowledge is available.

Perhaps in C code such loops cannot be eliminated without some political
wrangling, but there can be no such excuse for g++. 

Nathan Myers
ncm@cygnus.com

Re: Loop unrolling

[Joe Buck]

> No.  The "volatile" requires the compiler to keep the implied
> loads and stores, dispite the as-if rule, and thus the loop is
> not empty, and thus not deleted.

I don't believe the standard ever makes an exception to the as-if rule.
'volatile' for a static or global variable matters because you can
write a program where the effect is visible (make it multithreaded,
use a signal handler, map the variable to a hardware register).
Thus 'volatile' is *not* an exception to as-if.

Re: Loop unrolling

[Joe Buck]

re: removing emptly loops:

> If someone actually bitches, I suppose we could provide a switch
> to disable the optimization, but I would prefer that it be on by
> default.

Fine with me.  I suggest that there be a flag 

-fremove-empty-loops

which is on by default (or, at least, turned on by -O or -Ospace),
and that we tell users that they can say

-fno-remove-empty-loops

if they really need them for some reason.  The only reason for this
is that it has been in the manual for so long that empty loops are
not removed.  We may both think that no one cares, but I'm afraid
that someone will, and possibly he will be one of your customers.

Re: Loop unrolling

[Branko Cibej]

Joe Buck wrote:

> > > If you can provide source examples which show C++ & Java creating empty
> > > loops behind the programmer's back it would go a long way to convincing
> > > everyone that eliminating empty loops is a good idea.
> >
> > I sent this to RMS years ago during the original empty loop debate
> > (1991?) but he had already made up his mind.  I don't remember if I
> > sent it to the gcc2 list.
> >
> >       struct x
> >       {
> >         x() {}
> >       };
> >
> >       f()
> >       {
> >         x x1[10];
> >       }
>
> Yup.  I suppose if anyone really cares about keeping RMS happy, loops
> could be flagged as "the user wrote this loop" vs. "the compiler wrote
> this loop".

I don't think that's sufficient. My previous post with the template class
example contains only loops written by the user -- but some STL containers
(e.g., vector) have almost identical initialisation code.

Yes, the compiler could treat code in the standard library as "written by the
compiler", but what if the user wrote her own STL-like container?

(I'm sure nobody wants a new #pragma :)

> This might also keep embedded programmers who believed the gcc manual
> and wrote timing loops happy.

If they want _accurate_ timing loops, they should, as Tim Hollebeek pointed
out, use asm statements. Otherwise they can always use volatile loop variables.

--
Branko Cibej   <branko.cibej@hermes.si>
HERMES SoftLab, Litijska 51, 1000 Ljubljana, Slovenia
phone: (++386 61) 186 53 49  fax: (++386 61) 186 52 70

Re: Loop unrolling

[Richard Henderson]

On Tue, Jun 02, 1998 at 02:48:08PM -0700, Joe Buck wrote:
> Yup.  I suppose if anyone really cares about keeping RMS happy, loops
> could be flagged as "the user wrote this loop" vs. "the compiler wrote
> this loop".

No, as I'd like to see things of the form

#define destroy_pte(PTR)

	for (i = 0; i < PAGE_SIZE/sizeof(pte); ++i)
		destroy_pte(base+i);

where destroy_pte is defined in some target-specific header, be
eliminated as well.

> This might also keep embedded programmers who believed the gcc manual
> and wrote timing loops happy.

How often does this occur do you think?  Given that there are
any number of ways to write an empty loop that cannot be
removed, I would think this would not be much of an issue.

If someone actually bitches, I suppose we could provide a switch
to disable the optimization, but I would prefer that it be on by
default.


r~

Re: Loop unrolling

[Jason Merrill]

>>>>> Joe Buck <jbuck@synopsys.com> writes:

> Yup.  I suppose if anyone really cares about keeping RMS happy, loops
> could be flagged as "the user wrote this loop" vs. "the compiler wrote
> this loop".

Or we could go ahead and eliminate any loops with function begin/end notes
inside them.

Jason

Re: Loop unrolling

[Stephen Williams]

	struct x
	{
	  x() {}
	};
	
	f()
	{
	  x x1[10];
	}

jfc@mit.edu said:
> If you want to complain about the code style, assume that the empty
> constructor appears in a read-only header file (possibly in a base
> class definition -- that's where I first saw this bug).

Or a template. Actually, that code will work great if compiled with
-O2 -funroll-loops. However, I found that if I put an empty destructor
on, all hell breaks loose:

	struct x
	{
	  x() {}
	  ~x() { }
	};
	
	f()
	{
	  x x1[10];
	}

This is for the alpha. I think an important optimization is missed here.

icarus.icarus.com % g++ -v -O9 -funroll-loops -S foo.cc
Reading specs from /usr/local/lib/gcc-lib/alphaev5-unknown-linux-gnu/egcs-2.90.27/specs
gcc version egcs-2.90.27 980315 (egcs-1.0.2 release)
 /usr/local/lib/gcc-lib/alphaev5-unknown-linux-gnu/egcs-2.90.27/cpp -lang-c++ -v -undef -D__GNUC__=2 -D__GNUG__=2 -D__cplusplus -D__GNUC_MINOR__=90 -D__alpha -D__alpha__ -D__linux__ -D__linux -D_LONGLONG -Dlinux -Dunix -D__ELF__ -D__alpha -D__alpha__ -D__linux__ -D__linux -D_LONGLONG -D__linux__ -D__unix__ -D__ELF__ -D__linux -D__unix -Asystem(linux) -Acpu(alpha) -Amachine(alpha) -D__EXCEPTIONS -D__OPTIMIZE__ -D__LANGUAGE_C__ -D__LANGUAGE_C -DLANGUAGE_C -D__LANGUAGE_C_PLUS_PLUS__ -D__LANGUAGE_C_PLUS_PLUS -D__cplusplus foo.cc /tmp/cca02854.ii
GNU CPP version egcs-2.90.27 980315 (egcs-1.0.2 release) (Alpha Linux/ELF)
#include "..." search starts here:
#include <...> search starts here:
 /usr/local/include/g++
 /usr/local/include
 /usr/local/alphaev5-unknown-linux-gnu/include
 /usr/local/lib/gcc-lib/alphaev5-unknown-linux-gnu/egcs-2.90.27/include
 /usr/include
End of search list.
 /usr/local/lib/gcc-lib/alphaev5-unknown-linux-gnu/egcs-2.90.27/cc1plus /tmp/cca02854.ii -quiet -dumpbase foo.cc -O9 -version -funroll-loops -o foo.s
GNU C++ version egcs-2.90.27 980315 (egcs-1.0.2 release) (alphaev5-unknown-linux-gnu) compiled by GNU C version egcs-2.90.27 980315 (egcs-1.0.2 release).


-- 
Steve Williams                "The woods are lovely, dark and deep.
steve@icarus.com              But I have promises to keep,
steve@picturel.com            and lines to code before I sleep,
http://www.picturel.com       And lines to code before I sleep."

Re: Loop unrolling

[Martin von Loewis]

> If you can provide source examples which show C++ & Java creating empty
> loops behind the programmer's back it would go a long way to convincing
> everyone that eliminating empty loops is a good idea.

This is what actually started this whole thread. For

class A {
  int i;
public:
  A(){};
};

int main() 
{
  A a[1000];
}

i486-pc-linux-gnu/egcs-2.91.34/cc1plus -O2 produces

        movl $999,%eax
        .align 4
.L5:
        subl $1,%eax
        jnc .L5

It recognizes that the constructor is inline, but fails to recognize
that this makes the loop trivial.

Martin

Re: Loop unrolling

[Kaz Kylheku]

On Tue, 2 Jun 1998, Gavin Romig-Koch wrote:

> Martin Knoblauch writes:
>  > > 	{
>  > > 	  volatile int i;
>  > > 	  for (i = 0; i < 10000; ++i);
>  > > 	}
>  > >
>  > 
>  >  Hmm. Does this prevent the loop from being deleted,
>  > or would it allow the compiler to just assign
>  > 9999 to "i"?
> 
> It should prevent the loop from being deleted.  My memory
> of the standard is vague, but basically, "volatile" tells
> the compiler that it actually must read and write the 
> memory location.  The compiler must assume that writing
> to the memory location has some unseen effect (say the
> memory location actually some device register),  and
> also that the memory locations value might change in
> an unseen way from the write to the following read.
> 
> This isn't the actuall wording, but it's something like:
> If the expressions between two sequence points contain
> one or more stores to a volatile memory location, then the
> running program must make at least one store to that
> memory location (storing the proper value).  Similarly
> for reads from a volatile memory location.

An access to an object through a volatile l-value constitutes a side effect. At
a sequence point, side effects must stabilize, so that the actual data objects
receive their correct values. Moreover, all evaluations that have side effects
must be performed.  However, the standard unfortunately leaves it up to the
implementation to define what constitutes access to an object declared
volatile. (See sections 5.1.2.3 and 6.5.3 of the ISO 9899:1990 standard).

An implementation could still optimize away a useless loop that iterates
over an auto variable that is not subsequently accessed, because auto
variables usually cannot have any properties that are useful in
connection with the volatile keyword.

In none of the GCC implementations does a hardware register appear in automatic
storage. Furthermore, the address of i was never taken, so there isn't any
reasonable way another process can have access to it. If its address
were taken, we might suspect that a pointer to i was communicated to
another thread---though a potentially difficult analysis could prove
otherwise.

I think that it's quite reasonable for a C implementation for a typical
platform to only apply special access semantics to volatile objects that are
accessed through pointers, are static, or are auto objects whose address was
taken (and hence which could not have been declared register).

In other words, a C compiler can do anything as long as a correct program
cannot detect a deviation from the requirements. A useless loop over an
auto variable whose location hasn't been disclosed to any other part of
the program in any legal way, may be replaced by a simple assignment
of the final value---and even that may be thrown away if there is no
subsequent use of that value.

Re: Loop unrolling

[Joe Buck]

> > If you can provide source examples which show C++ & Java creating empty
> > loops behind the programmer's back it would go a long way to convincing
> > everyone that eliminating empty loops is a good idea.
> 
> I sent this to RMS years ago during the original empty loop debate
> (1991?) but he had already made up his mind.  I don't remember if I
> sent it to the gcc2 list.
> 
> 	struct x
> 	{
> 	  x() {}
> 	};
> 	
> 	f()
> 	{
> 	  x x1[10];
> 	}

Yup.  I suppose if anyone really cares about keeping RMS happy, loops
could be flagged as "the user wrote this loop" vs. "the compiler wrote
this loop".

This might also keep embedded programmers who believed the gcc manual
and wrote timing loops happy.

Re: Loop unrolling

[Joern Rennecke]

>  > AFAIK it prevents current versions of gcc to delete the loop (unless the loop
>  > is unreachable), but the standard's 'as if' rule still allows to optimize
>  > the loop away.
> 
> No.  The "volatile" requires the compiler to keep the implied
> loads and stores, dispite the as-if rule, and thus the loop is
> not empty, and thus not deleted.

i has automatic storage, and its address is never taken, so the compiler
might decide to allocate this object to some 'write-only-memory'.
This object has the property that you can have an implied store of any value
or a read at any desired point of time in the program execution,
without requiring any actual instructions.
Let's say our target needs a minimum time of '1' to executa an actual
instruction.  So you could have:
time t0:   nop
time t0+0.00001 i := 0
time t0+0.00002 read i
time t0+0.00003 i := 1
time t0+0.00004 read i
...
time t0+0.19999 i := 9999
time t0+0.20000 read i
time t0+0.20001 i := 10000
time t0+0.20002 read i
time t0+1: nop

Re: Loop unrolling

[Gavin Romig-Koch]

Joern Rennecke writes:
 > > > But the correct way to write an empty loop that
 > > shouldn't be deleted
 > > > (a timing loop) already exists:
 > > > 
 > > > 	{
 > > > 	  volatile int i;
 > > > 	  for (i = 0; i < 10000; ++i);
 > > > 	}
 > > >
 > > 
 > >  Hmm. Does this prevent the loop from being deleted,
 > > or would it allow the compiler to just assign
 > > 9999 to "i"?
 > 
 > AFAIK it prevents current versions of gcc to delete the loop (unless the loop
 > is unreachable), but the standard's 'as if' rule still allows to optimize
 > the loop away.

No.  The "volatile" requires the compiler to keep the implied
loads and stores, dispite the as-if rule, and thus the loop is
not empty, and thus not deleted.

                                           -gavin...
                      

Re: Loop unrolling

[Branko Cibej]

Jeffrey A Law wrote:

> If you can provide source examples which show C++ & Java creating empty
> loops behind the programmer's back it would go a long way to convincing
> everyone that eliminating empty loops is a good idea.

I don't know about Java, but it's terribly easy to do in C++:

     $ c++ -v
     Reading specs from /opt/freeware/gnu/lib/gcc-lib/sparc-sun-solaris2.6/2.8.1/specs
     gcc version 2.8.1
     $ c++ -O2 -save-temps dead_loop.cc

If I read the gibberish in dead_loop.s correctly. there are two empty loops in
main, at .LL211 and .LL212.

--
Branko Cibej   <branko.cibej@hermes.si>
HERMES SoftLab, Litijska 51, 1000 Ljubljana, Slovenia
phone: (++386 61) 186 53 49  fax: (++386 61) 186 52 70

Re: Loop unrolling

[Lee Iverson]

In message < 19980602093834.24519.rocketmail@web2.rocketmail.com > you write:
> 
> > But the correct way to write an empty loop that
> shouldn't be deleted
> > (a timing loop) already exists:
> > 
> > 	{
> > 	  volatile int i;
> > 	  for (i = 0; i < 10000; ++i);
> > 	}
> >
> 
>  Hmm. Does this prevent the loop from being deleted,
> or would it allow the compiler to just assign
> 9999 to "i"?

I don't believe so, since the compiler cannot assume that "i" isn't
modified within the loop.  Thus, the compiler can't assume that the
loop even terminates.  The only legal option is to increment the index
"i" throughout the loop.

-------------------------------------------------------------------------------
Lee Iverson     		SRI International
leei@ai.sri.com			333 Ravenswood Ave., Menlo Park CA 94025
http://www.ai.sri.com/~leei/	(650) 859-3307

Re: Loop unrolling

[Horst von Brand]

Tim Hollebeek <tim@wagner.princeton.edu> said:
> Stephen Williams writes ...
> > pfeifer@dbai.tuwien.ac.at said:
> > > As a matter of fact, is there still any strong reason not to delete
> > > empty loops in general? 

> > As a matter of fact, there is. Us embedded programmers are sometimes
> > compelled to write timing loops. I guess we should (and I usually do)
> > make those loops non-empty, but still ....

[...]

> It seems to me that such a timing loop relies on the loop generating the
> same code, and as such is better as an explicit asm statement.  Linux,
> for example, gets this right.

I wholeheartedly agree.
-- 
Dr. Horst H. von Brand                       mailto:vonbrand@inf.utfsm.cl
Departamento de Informatica                     Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria              +56 32 654239
Casilla 110-V, Valparaiso, Chile                Fax:  +56 32 797513

Re: Loop unrolling

[Sol Foster]

Jeffrey A Law <law@cygnus.com> wrote:
> If you can provide source examples which show C++ & Java creating empty
> loops behind the programmer's back it would go a long way to convincing
> everyone that eliminating empty loops is a good idea.

The obvious example would be something like 

    class A
    {
        public: A () {}
    };

    ....

    new A [100];

In theory, the compiler should generate a loop to call the default
constructor for each element.  The default constructor doesn't do
anything, though, so this loop would ideally go away.  (Perhaps EGCS
already does this as a special case... I don't have the compiler handy to
test it.)

I'd argue that even more important would be case where the programmer
intentionally created an empty loop, something like this (quickly hacked
together, not actual tested code):

    template <class iter> void
    DisplayData (iter begin, iter end)
    {
        for (iter i = begin; i != end; i++)
            i->Prepare ();
        for (iter i = begin; i != end; i++)
            i->Display ();
    }

In many cases (perhaps even the normal case) the Prepare code might just
be an inlined empty function, in which case you'd like the first loop to
go away.
    

-- 
Sol Foster: colomon@ralf.org

Socks aren't vegatables -- they deserve to be wiped out. 
                                        -Neil

Re: Loop unrolling

[Joern Rennecke]

> > But the correct way to write an empty loop that
> shouldn't be deleted
> > (a timing loop) already exists:
> > 
> > 	{
> > 	  volatile int i;
> > 	  for (i = 0; i < 10000; ++i);
> > 	}
> >
> 
>  Hmm. Does this prevent the loop from being deleted,
> or would it allow the compiler to just assign
> 9999 to "i"?

AFAIK it prevents current versions of gcc to delete the loop (unless the loop
is unreachable), but the standard's 'as if' rule still allows to optimize
the loop away.

Re: Loop unrolling

[Gavin Romig-Koch]

Martin Knoblauch writes:
 > > 	{
 > > 	  volatile int i;
 > > 	  for (i = 0; i < 10000; ++i);
 > > 	}
 > >
 > 
 >  Hmm. Does this prevent the loop from being deleted,
 > or would it allow the compiler to just assign
 > 9999 to "i"?

It should prevent the loop from being deleted.  My memory
of the standard is vague, but basically, "volatile" tells
the compiler that it actually must read and write the 
memory location.  The compiler must assume that writing
to the memory location has some unseen effect (say the
memory location actually some device register),  and
also that the memory locations value might change in
an unseen way from the write to the following read.

This isn't the actuall wording, but it's something like:
If the expressions between two sequence points contain
one or more stores to a volatile memory location, then the
running program must make at least one store to that
memory location (storing the proper value).  Similarly
for reads from a volatile memory location.


                              -gavin...

Re: Loop unrolling

[John Carr]

> If you can provide source examples which show C++ & Java creating empty
> loops behind the programmer's back it would go a long way to convincing
> everyone that eliminating empty loops is a good idea.

I sent this to RMS years ago during the original empty loop debate
(1991?) but he had already made up his mind.  I don't remember if I
sent it to the gcc2 list.

	struct x
	{
	  x() {}
	};
	
	f()
	{
	  x x1[10];
	}

gcc's output contains an empty loop.  If you want to complain about
the code style, assume that the empty constructor appears in a
read-only header file (possibly in a base class definition -- that's
where I first saw this bug).

(This also shows a deficiency in the SPARC machine description: there
is an unnecessary compare.)

Re: Loop unrolling

[Joern Rennecke]

> I really don't see what's wrong with something like:
> 
> 	for (i = 0; i < n; i++)
> 		__asm__ ("");
> 
> for doing empty loops.

Since the loop index is not used in the asm, this loop may be unrolled.

Re: Loop unrolling

[Martin Knoblauch]

---Lee Iverson <leei@ai.sri.com> wrote:
>
> In message
< 199806011514.IAA02191@icarus.icarus.com > you write:
> > 
> > pfeifer@dbai.tuwien.ac.at said:
> > > As a matter of fact, is there still any strong
reason not to delete
> > > empty loops in general? 
> > 
> > As a matter of fact, there is. Us embedded
programmers are sometimes
> > compelled to write timing loops. I guess we
should (and I usually do)
> > make those loops non-empty, but still ....
> 
> But the correct way to write an empty loop that
shouldn't be deleted
> (a timing loop) already exists:
> 
> 	{
> 	  volatile int i;
> 	  for (i = 0; i < 10000; ++i);
> 	}
>

 Hmm. Does this prevent the loop from being deleted,
or would it allow the compiler to just assign
9999 to "i"?

Martin 
===
------------------------------------------------------
Martin Knoblauch
email: knobi@knobisoft.de or knobi@rocketmail.com
www:   http://www.knobisoft.de

_________________________________________________________
DO YOU YAHOO!?
Get your free @yahoo.com address at http://mail.yahoo.com

Re: Loop unrolling

[Jeffrey A Law]

  > As is stands now, deleting empty loops is a very desirable *feature*,
  > especially for higher-level languages like C++ and Java which may just
  > generate loops that the programmer doesn't see.  If anything, we need
  > to expand the detection and deletion of empty loops.  A couple of us
  > embarked on this exercise for a couple of weeks last summer, but the
  > lack of register lifetime information in the loop optimization pass
  > bit us badly.  Maybe its time to resurrect this old code and make it
  > work?
If you can provide source examples which show C++ & Java creating empty
loops behind the programmer's back it would go a long way to convincing
everyone that eliminating empty loops is a good idea.

It's also been suggested that having register lifetime information would
allow us to fix the infamous x86 strength reduction bug and re-enable
strength reduction.

jeff

Re: Loop unrolling

[Lee Iverson]

In message < 199806011514.IAA02191@icarus.icarus.com > you write:
> 
> pfeifer@dbai.tuwien.ac.at said:
> > As a matter of fact, is there still any strong reason not to delete
> > empty loops in general? 
> 
> As a matter of fact, there is. Us embedded programmers are sometimes
> compelled to write timing loops. I guess we should (and I usually do)
> make those loops non-empty, but still ....

But the correct way to write an empty loop that shouldn't be deleted
(a timing loop) already exists:

	{
	  volatile int i;
	  for (i = 0; i < 10000; ++i);
	}

As is stands now, deleting empty loops is a very desirable *feature*,
especially for higher-level languages like C++ and Java which may just
generate loops that the programmer doesn't see.  If anything, we need
to expand the detection and deletion of empty loops.  A couple of us
embarked on this exercise for a couple of weeks last summer, but the
lack of register lifetime information in the loop optimization pass
bit us badly.  Maybe its time to resurrect this old code and make it
work?

-------------------------------------------------------------------------------
Lee Iverson     		SRI International
leei@ai.sri.com			333 Ravenswood Ave., Menlo Park CA 94025
http://www.ai.sri.com/~leei/	(650) 859-3307

Re: Loop unrolling

[Tim Hollebeek]

Stephen Williams writes ...
> 
> 
> pfeifer@dbai.tuwien.ac.at said:
> > As a matter of fact, is there still any strong reason not to delete
> > empty loops in general? 
> 
> As a matter of fact, there is. Us embedded programmers are sometimes
> compelled to write timing loops. I guess we should (and I usually do)
> make those loops non-empty, but still ....

Is there any compelling reason why this shouldn't be an asm() block,
since otherwise optimizer changes could change the length of the loop?
For example, an "intelligent" loop optimizer could add nop's to a loop
to improve alignment, cache, or scheduling constraints.

It seems to me that such a timing loop relies on the loop generating the
same code, and as such is better as an explicit asm statement.  Linux,
for example, gets this right.

So there really is no need for an empty loop in such a case.

---------------------------------------------------------------------------
Tim Hollebeek                           | "Everything above is a true
email: tim@wfn-shop.princeton.edu       |  statement, for sufficiently
URL: http://wfn-shop.princeton.edu/~tim |  false values of true."

Re: Loop unrolling

[Nick Burrett]

Stephen Williams wrote:
>   pfeifer@dbai.tuwien.ac.at said:
>   > As a matter of fact, is there still any strong reason not to delete
>   > empty loops in general? 

>   As a matter of fact, there is. Us embedded programmers are sometimes
>   compelled to write timing loops. I guess we should (and I usually do)
>   make those loops non-empty, but still ....

You could always add a command line switch: -fremove-empty-loops

Nick.

Re: Loop unrolling

[Mike Stump]

> Date: Mon, 1 Jun 1998 12:57:21 +0200 (MET DST)
> From: Gerald Pfeifer <pfeifer@dbai.tuwien.ac.at>
> To: egcs-patches@cygnus.com, egcs@cygnus.com
> cc: Tim Hollebeek <tim@wagner.princeton.edu>

> As a matter of fact, is there still any strong reason not to delete
> empty loops in general?

I don't think we should.

> > Morover, with @samp{-funroll-loops} small ``empty'' loops indeed are
> > removed, so the current behavior is both sub-optimal and inconsistent
> > and may well change in the future. 

I don't think this should go in the docs.  I think it is a bug in the
unroller that gcc optimizes away an empty loop.  I think this should
be fixed.  I think the docs can admit the current bug, but should not
call it anything but a bug.

Re: Loop unrolling

[Branko Cibej]

Stephen Williams wrote:

> pfeifer@dbai.tuwien.ac.at said:
> > As a matter of fact, is there still any strong reason not to delete
> > empty loops in general?
>
> As a matter of fact, there is. Us embedded programmers are sometimes
> compelled to write timing loops. I guess we should (and I usually do)
> make those loops non-empty, but still ....

Somebody on this list mentioned making the loop variable volatile, as in:

     {
         int volatile i:
         for (i = 0; i < 10000; ++i);
     }

The compiler mustn't delete the accesses to i, therefore it can't make
the loop empty and therefore it can't delete it.

I do believe this is the way delay loops should be written.

--
Branko Cibej   <branko.cibej@hermes.si>
HERMES SoftLab, Litijska 51, 1000 Ljubljana, Slovenia
phone: (++386 61) 186 53 49  fax: (++386 61) 186 52 70

Re: Loop unrolling

[Gerald Pfeifer]

This is a slighty modified (i.e., corrected) version of my previous
patch: ``rationale'' instead of ``rational''.

Thanks a lot to a friendly and helpful lurker!


Mon Jun  1 22:28:31 1998  Gerald Pfeifer <pfeifer@dbai.tuwien.ac.at>

	* ``Emtpy'' loops sometimes do get deleted and can indeed be
	generated by optimization.
	  

Index: gcc.texi
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/gcc.texi,v
retrieving revision 1.11
diff -r1.11 gcc.texi
2004,2006c2004,2007
< GNU CC does not delete ``empty'' loops because the most likely reason
< you would put one in a program is to have a delay.  Deleting them will
< not make real programs run any faster, so it would be pointless.
---
> GNU CC does not delete ``empty'' loops because (historically) the most
> likely reason you would put one in a program was to have a delay.
> Deleting these will not make real programs run any faster, so it would 
> be pointless.
2008,2009c2009,2015
< It would be different if optimization of a nonempty loop could produce
< an empty one.  But this generally can't happen.
---
> However, the rationale here was that optimization of a nonempty loop
> cannot produce an empty one, which holds for C but is not the case for
> C++ in general.
> 
> Morover, with @samp{-funroll-loops} small ``empty'' loops indeed are
> removed, so the current behavior is both sub-optimal and inconsistent
> and may well change in the future. 

Re: Loop unrolling

[Stephen Williams]

	{
	  volatile int i;
	  for (i = 0; i < 10000; ++i);
	}

Nifty! Or in C++ "for (volatile int i = 0; i < 10000; i+=1) ;"


leei@ai.sri.com said:
> As is stands now, deleting empty loops is a very desirable *feature*,
> especially for higher-level languages like C++ and Java which may just
> generate loops that the programmer doesn't see.


Yes yes yes, I agree. I'm all for the compiler being aggressive, especially
in memory-tight and kinda slow embedded processors. I believe, in fact, that
a C++ compiler has the extra information needed to surpass the compiled code
performance of C. And with things like inline functions and templates,
loops can be drained of active contents pretty quickly.
-- 
Steve Williams                "The woods are lovely, dark and deep.
steve@icarus.com              But I have promises to keep,
steve@picturel.com            and lines to code before I sleep,
http://www.picturel.com       And lines to code before I sleep."

Re: Loop unrolling

[Joern Rennecke]

> As a matter of fact, there is. Us embedded programmers are sometimes
> compelled to write timing loops. I guess we should (and I usually do)
> make those loops non-empty, but still ....

If you must use a timing loop, you should use an asm statement.

Re: Loop unrolling

[Michael Meissner]

Stephen Williams writes:
| 
| pfeifer@dbai.tuwien.ac.at said:
| > As a matter of fact, is there still any strong reason not to delete
| > empty loops in general? 
| 
| As a matter of fact, there is. Us embedded programmers are sometimes
| compelled to write timing loops. I guess we should (and I usually do)
| make those loops non-empty, but still ....

I really don't see what's wrong with something like:

	for (i = 0; i < n; i++)
		__asm__ ("");

for doing empty loops.

-- 
Michael Meissner, Cygnus Solutions (Massachusetts office)
4th floor, 955 Massachusetts Avenue, Cambridge, MA 02139, USA
meissner@cygnus.com,	617-354-5416 (office),	617-354-7161 (fax)

Re: Loop unrolling

[Stephen Williams]

pfeifer@dbai.tuwien.ac.at said:
> As a matter of fact, is there still any strong reason not to delete
> empty loops in general? 

As a matter of fact, there is. Us embedded programmers are sometimes
compelled to write timing loops. I guess we should (and I usually do)
make those loops non-empty, but still ....
-- 
Steve Williams                "The woods are lovely, dark and deep.
steve@icarus.com              But I have promises to keep,
steve@picturel.com            and lines to code before I sleep,
http://www.picturel.com       And lines to code before I sleep."

Loop unrolling

[Gerald Pfeifer]

This should make the documentation better match what egcs actually
does (-funroll-loops) resp. should do (C++).

Cf. http://www.cygnus.com/ml/egcs/1998-May/0651.html and following.

As a matter of fact, is there still any strong reason not to delete
empty loops in general?


Mon Jun  1 12:47:07 1998  Gerald Pfeifer <pfeifer@dbai.tuwien.ac.at>

	* ``Emtpy'' loops sometimes do get deleted and can indeed be
	generated by optimization.
	  

Index: gcc.texi
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/gcc.texi,v
retrieving revision 1.11
diff -r1.11 gcc.texi
2004,2006c2004,2007
< GNU CC does not delete ``empty'' loops because the most likely reason
< you would put one in a program is to have a delay.  Deleting them will
< not make real programs run any faster, so it would be pointless.
---
> GNU CC does not delete ``empty'' loops because (historically) the most
> likely reason you would put one in a program was to have a delay.
> Deleting these will not make real programs run any faster, so it would 
> be pointless.
2008,2009c2009,2015
< It would be different if optimization of a nonempty loop could produce
< an empty one.  But this generally can't happen.
---
> However, the rational here was that optimization of a nonempty loop
> cannot produce an empty one, which holds for C but is not the case for
> C++ in general.
> 
> Morover, with @samp{-funroll-loops} small ``empty'' loops indeed are
> removed, so the current behavior is both sub-optimal and inconsistent
> and may well change in the future.