public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
[parent not found: <bug-18927-5884@http.gcc.gnu.org/bugzilla/>]
* [Bug target/18927] New: O(n^2) compile time with -O0 (n= number of basic blocks) in global alloc
@ 2004-12-10 15:43 heinrich dot brand at fujitsu-siemens dot com
  2004-12-11 13:14 ` [Bug middle-end/18927] O(n^2) compile time with -O0 (n= number of basic blocks) in local alloc steven at gcc dot gnu dot org
                   ` (2 more replies)
  0 siblings, 3 replies; 5+ messages in thread
From: heinrich dot brand at fujitsu-siemens dot com @ 2004-12-10 15:43 UTC (permalink / raw)
  To: gcc-bugs

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


^ permalink raw reply	[flat|nested] 5+ messages in thread
end of thread, other threads:[~2012-05-20 22:06 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
     [not found] <bug-18927-4@http.gcc.gnu.org/bugzilla/>
2012-05-20 22:23 ` [Bug middle-end/18927] O(n^2) compile time with -O0 (n= number of basic blocks) in local alloc steven at gcc dot gnu.org
     [not found] <bug-18927-5884@http.gcc.gnu.org/bugzilla/>
2009-06-10  1:54 ` pinskia at gcc dot gnu dot org
2004-12-10 15:43 [Bug target/18927] New: O(n^2) compile time with -O0 (n= number of basic blocks) in global alloc heinrich dot brand at fujitsu-siemens dot com
2004-12-11 13:14 ` [Bug middle-end/18927] O(n^2) compile time with -O0 (n= number of basic blocks) in local alloc steven at gcc dot gnu dot org
2004-12-13 11:37 ` heinrich dot brand at fujitsu-siemens dot com
2004-12-23 11:21 ` steven at gcc dot gnu dot org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).