This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Loop unrolling
- To: gcc at gcc dot gnu dot org
- Subject: Loop unrolling
- From: Frank Klemm <pfk at fuchs dot offl dot uni-jena dot de>
- Date: Mon, 3 Sep 2001 01:54:24 +0200
- >Received: (from pfk@localhost)by fuchs.offl.uni-jena.de (8.9.3/8.9.3/SuSE Linux 8.9.3-0.1) id BAA07352for gcc@gcc.gnu.org; Mon, 3 Sep 2001 01:54:24 +0200
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發ps 10發ps 100 發ps
Such a table can look like:
: 2 4 8 16 32 64 128 256 512
loops : 發p 發p 發p 發p 發p 發p 發p 發p 發p 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