From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 14323 invoked by alias); 10 Dec 2004 15:43:05 -0000 Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org Received: (qmail 14312 invoked by uid 48); 10 Dec 2004 15:43:01 -0000 Date: Fri, 10 Dec 2004 15:43:00 -0000 From: "heinrich dot brand at fujitsu-siemens dot com" To: gcc-bugs@gcc.gnu.org Message-ID: <20041210154259.18927.heinrich.brand@fujitsu-siemens.com> Reply-To: gcc-bugzilla@gcc.gnu.org Subject: [Bug target/18927] New: O(n^2) compile time with -O0 (n= number of basic blocks) in global alloc X-Bugzilla-Reason: CC X-SW-Source: 2004-12/txt/msg01499.txt.bz2 List-Id: 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