Some C-Code is (with Option -O0) processed by an algorithm with O(n^2) time.
This simple code scheme shows that the compile time grows fast with
the number of basic blocks in a function. If the number of
basic blocks is doubled the compile time is almost quadrupled.
The output of -ftime-report shows that global alloc uses most of the time.
But C-Code with a small difference has roughly O(n) compile time.
expensive code:
if(*i0){int a; a=(*i1);*i2=(a/3+a/7);} : roughly O(n*n) compile time
if(*i0){int a; a=(*i1);*i2=(a/3+(*i2)/7);} : roughly O(n*n) compile time
cheap code:
if(*i0){int a; a=(*i1);*i2=(a*3+a*7);} : roughly O(n) compile time
if(*i0){int a; a=(*i1);*i2=(a*3+(*i2)*7);} : roughly O(n) compile time
Used Code Scheme:
void test(int *i0,int *i1,int *i2){
if(*i0){int a; a=(*i1);*i2=(a/3+a/7);}
... copies of the last statement
return;}
The body of the test function consists of a number of copies of
the following Statement:
if(*i0){int a; a=(*i1);*i2=(a/3+a/7);}
Each statement produces 2 basic blocks.
Content of the following table:
BBs : number of basic blocks in if-statements
user : user time from /usr/bin/time gcc
global_alloc : from output of -ftime-report
lines of assembler code : lines of gcc output
(Intel Pentium 700Mhz or an old SPARC-Computer)
Table relating number of basic block to compile time for gcc 3.4.3 intel
========================================================================
BBs user global_alloc lines of assembler code
---------------------------------------------------------------
100 0.22 0.12 (55%) 1468
200 0.54 0.30 (56%) 2918
400 1.36 0.91 (67%) 5818
800 4.09 3.15 (77%) 11618
1600 15.52 13.67 (88%) 23218
3200 76.63 72.87 (95%) 46418
6400 277.25 269.49 (97%) 92818
12800 1072.58 1057.20 (99%) 185618
Table relating number of basic block to compile time for gcc 3.2 intel
======================================================================
BBs user global_alloc lines of assembler code
---------------------------------------------------------------
100 0.17 0.07 (41%) 1369
200 0.37 0.15 (42%) 2719
400 0.76 0.36 (48%) 5419
800 1.53 0.76 (50%) 10819
1600 3.50 1.80 (52%) 21619
3200 8.13 4.59 (56%) 43219
6400 21.59 14.33 (66%) 86419
12800 62.03 45.75 (74%) 172819
Table relating number of basic block to compile time for gcc 3.4.3 sparc
=========================================================================
BBs user global_alloc lines of assembler code
---------------------------------------------------------------
100 0.32 0.05 (16%) 1218
200 0.49 0.07 (15%) 2418
400 0.87 0.16 (19%) 4818
800 1.49 0.30 (20%) 9618
1600 3.10 0.67 (22%) 19218
3200 6.72 1.51 (23%) 38418
6400 14.95 4.45 (30%) 76818
12800 54.73 32.43 (59%) 153618
Table relating number of basic block to compile time for gcc 2.95.2 sparc
=========================================================================
BBs user global_alloc lines of assembler code
---------------------------------------------------------------
100 0.11 1173
200 0.17 2323
400 0.30 4623
800 0.62 9223
1600 1.35 18423
3200 2.90 36823
6400 6.19 73623
12800 14.97 147223
Table relating number of basic block to compile time for gcc 3.4.3 intel
for this Code: if(*i0){int a; a=(*i1);*i2=(a*3+a*7);}
=========================================================================
BBs user global_alloc lines of assembler code
---------------------------------------------------------------
100 0.11 0.01 (10%) 713
200 0.16 0.03 (20%) 1413
400 0.35 0.07 (21%) 2813
800 0.65 0.14 (22%) 5613
1600 1.33 0.28 (21%) 11213
3200 2.93 0.58 (20%) 22413
6400 5.80 1.15 (20%) 44813
12800 12.09 2.68 (22%) 89613
Shellscripts:
-----------------------------------------------------------------------
for x in 50 100 200 400 800 1600 3200 6400
do
echo "############ $x"
run $x
done
---------------------------------------------------------------------------
[[ -z $1 ]] && exit 1
N=$1
echo 'void test(int *i0,int *i1,int *i2){' >z.c
IF="if(*i0){int a; a=(*i1);*i2=(a/3+(*i2)/7);}"
((i=$N))
while((i>0))
do
echo " $IF" >>z.c
((i=i-1))
done
echo 'return;}' >>z.c
wc z.c
echo "$IF"
/usr/bin/time -p gcc -S -O0 -ftime-report z.c
((BB=N+N))
echo "### BB $BB"
wc z.s
-----------------------------------------------------------------------------
gawk '
$1=="global" && $2 == "alloc" {gsub(":"," ");ga=$3; proz=$4 }
$1=="user" { u=$2; }
$1=="###" && $2=="BB" {bb=$3;}
$4=="z.s" {printf("%s\t %s\t %s\t %s\t %s\n",bb,u,ga,proz ,$1)};
' nohup.out
--
Summary: O(n^2) compile time with -O0 (n= number of basic blocks)
in global alloc
Product: gcc
Version: 3.4.3
Status: UNCONFIRMED
Severity: minor
Priority: P3
Component: target
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: heinrich dot brand at fujitsu-siemens dot com
CC: gcc-bugs at gcc dot gnu dot org
GCC build triplet: Intel SUSE 8.1
GCC host triplet: Intel SUSE 8.1
GCC target triplet: Intel SUSE 8.1
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18927
