thr3ads.net - llvm dev - [LLVMdev] really long time to compile [Dec 2002]

If this information is useful, please help other people find it:
Share via:

Brian R. Gaeke

2002-Dec-14 07:48 UTC

[LLVMdev] really long time to compile

Hi,

Can anyone suggest any reasons why this seemingly-innocuous (though
stupid-looking) excerpt from gnu fileutils 4.1 would make llvm-gcc
go so incredibly slowly? It doesn't seem to be a question of the
size of the output.

Here's what I do:

% time llvm-gcc -c sha24.c
56.840u 0.050s 1:07.05 84.8%    0+0k 0+0io 1050pf+0w
% ls -l sha24.o
-rw-r--r--    1 brg      brg          5784 2002-12-14 07:43 sha24.o

The problem goes away if I use -S:

% time llvm-gcc -S sha24.c
0.060u 0.010s 0:00.09 77.7%     0+0k 0+0io 548pf+0w

-- 
gaeke at uiuc.edu
-------------- next part --------------
struct sha_ctx
{
  unsigned int A;
  unsigned int B;
  unsigned int C;
  unsigned int D;
  unsigned int E;
  unsigned int total[2];
  unsigned int buflen;
  char buffer[128];
};
void
sha_process_block (const void *buffer, unsigned long len, struct sha_ctx *ctx)
{
  const unsigned int *words = buffer;
  unsigned long nwords = len / sizeof (unsigned int);
  const unsigned int *endp = words + nwords;
  unsigned int x[16];
  unsigned int a = ctx->A;
  unsigned int b = ctx->B;
  unsigned int c = ctx->C;
  unsigned int d = ctx->D;
  unsigned int e = ctx->E;
  ctx->total[0] += len;
  if (ctx->total[0] < len)
    ++ctx->total[1];
  while (words < endp)
    {
      unsigned int tm;
      int t;
      for (t = 0; t < 16; t++)
	{
	  x[t] 	    (((*words) << 24) | (((*words) & 0xff00) << 8) |
	     (((*words) >> 8) & 0xff00) | ((*words) >> 24));
	  words++;
	}
      do
	{
	  e +	    (((a) << (5)) | ((a) >> (32 - (5)))) + (d ^ (b & (c ^
d))) +
	    0x5a827999L + x[0];
	  b = (((b) << (30)) | ((b) >> (32 - (30))));
	}
      while (0);
      do
	{
	  d +	    (((e) << (5)) | ((e) >> (32 - (5)))) + (c ^ (a & (b ^
c))) +
	    0x5a827999L + (tm 			   x[16 & 0x0f] ^ x[(16 - 14) & 0x0f] ^ x[(16
- 8) &
								  0x0f] ^
			   x[(16 - 3) & 0x0f], (x[16 & 0x0f] 						(((tm) << (1)) |
						 ((tm) >> (32 - (1))))));
	  a = (((a) << (30)) | ((a) >> (32 - (30))));
	}
      while (0);
      do
	{
	  e +	    (((a) << (5)) | ((a) >> (32 - (5)))) + (b ^ c ^ d) +
0x6ed9eba1L +
	    (tm 	     x[20 & 0x0f] ^ x[(20 - 14) & 0x0f] ^ x[(20 - 8) &
0x0f] ^
	     x[(20 - 3) & 0x0f], (x[20 & 0x0f] 				  (((tm) << (1)) |
((tm) >> (32 - (1))))));
	  b = (((b) << (30)) | ((b) >> (32 - (30))));
	}
      while (0);
      do
	{
	  e +	    (((a) << (5)) | ((a) >> (32 - (5)))) + ((b & c) | (d
& (b | c))) +
	    0x8f1bbcdcL + (tm 			   x[40 & 0x0f] ^ x[(40 - 14) & 0x0f] ^ x[(40
- 8) &
								  0x0f] ^
			   x[(40 - 3) & 0x0f], (x[40 & 0x0f] 						(((tm) << (1)) |
						 ((tm) >> (32 - (1))))));
	  b = (((b) << (30)) | ((b) >> (32 - (30))));
	}
      while (0);
      do
	{
	  e +	    (((a) << (5)) | ((a) >> (32 - (5)))) + (b ^ c ^ d) +
0xca62c1d6L +
	    (tm 	     x[60 & 0x0f] ^ x[(60 - 14) & 0x0f] ^ x[(60 - 8) &
0x0f] ^
	     x[(60 - 3) & 0x0f], (x[60 & 0x0f] 				  (((tm) << (1)) |
((tm) >> (32 - (1))))));
	  b = (((b) << (30)) | ((b) >> (32 - (30))));
	}
      while (0);
      do
	{
	  d +	    (((e) << (5)) | ((e) >> (32 - (5)))) + (a ^ b ^ c) +
0xca62c1d6L +
	    (tm 	     x[71 & 0x0f] ^ x[(71 - 14) & 0x0f] ^ x[(71 - 8) &
0x0f] ^
	     x[(71 - 3) & 0x0f], (x[71 & 0x0f] 				  (((tm) << (1)) |
((tm) >> (32 - (1))))));
	  a = (((a) << (30)) | ((a) >> (32 - (30))));
	}
      while (0);
      do
	{
	  c +	    (((d) << (5)) | ((d) >> (32 - (5)))) + (e ^ a ^ b) +
0xca62c1d6L +
	    (tm 	     x[72 & 0x0f] ^ x[(72 - 14) & 0x0f] ^ x[(72 - 8) &
0x0f] ^
	     x[(72 - 3) & 0x0f], (x[72 & 0x0f] 				  (((tm) << (1)) |
((tm) >> (32 - (1))))));
	  e = (((e) << (30)) | ((e) >> (32 - (30))));
	}
      while (0);
      do
	{
	  b +	    (((c) << (5)) | ((c) >> (32 - (5)))) + (d ^ e ^ a) +
0xca62c1d6L +
	    (tm 	     x[73 & 0x0f] ^ x[(73 - 14) & 0x0f] ^ x[(73 - 8) &
0x0f] ^
	     x[(73 - 3) & 0x0f], (x[73 & 0x0f] 				  (((tm) << (1)) |
((tm) >> (32 - (1))))));
	  d = (((d) << (30)) | ((d) >> (32 - (30))));
	}
      while (0);
      do
	{
	  a +	    (((b) << (5)) | ((b) >> (32 - (5)))) + (c ^ d ^ e) +
0xca62c1d6L +
	    (tm 	     x[74 & 0x0f] ^ x[(74 - 14) & 0x0f] ^ x[(74 - 8) &
0x0f] ^
	     x[(74 - 3) & 0x0f], (x[74 & 0x0f] 				  (((tm) << (1)) |
((tm) >> (32 - (1))))));
	  c = (((c) << (30)) | ((c) >> (32 - (30))));
	}
      while (0);
      do
	{
	  e +	    (((a) << (5)) | ((a) >> (32 - (5)))) + (b ^ c ^ d) +
0xca62c1d6L +
	    (tm 	     x[75 & 0x0f] ^ x[(75 - 14) & 0x0f] ^ x[(75 - 8) &
0x0f] ^
	     x[(75 - 3) & 0x0f], (x[75 & 0x0f] 				  (((tm) << (1)) |
((tm) >> (32 - (1))))));
	  b = (((b) << (30)) | ((b) >> (32 - (30))));
	}
      while (0);
      do
	{
	  d +	    (((e) << (5)) | ((e) >> (32 - (5)))) + (a ^ b ^ c) +
0xca62c1d6L +
	    (tm 	     x[76 & 0x0f] ^ x[(76 - 14) & 0x0f] ^ x[(76 - 8) &
0x0f] ^
	     x[(76 - 3) & 0x0f], (x[76 & 0x0f] 				  (((tm) << (1)) |
((tm) >> (32 - (1))))));
	  a = (((a) << (30)) | ((a) >> (32 - (30))));
	}
      while (0);
      do
	{
	  c +	    (((d) << (5)) | ((d) >> (32 - (5)))) + (e ^ a ^ b) +
0xca62c1d6L +
	    (tm 	     x[77 & 0x0f] ^ x[(77 - 14) & 0x0f] ^ x[(77 - 8) &
0x0f] ^
	     x[(77 - 3) & 0x0f], (x[77 & 0x0f] 				  (((tm) << (1)) |
((tm) >> (32 - (1))))));
	  e = (((e) << (30)) | ((e) >> (32 - (30))));
	}
      while (0);
      do
	{
	  b +	    (((c) << (5)) | ((c) >> (32 - (5)))) + (d ^ e ^ a) +
0xca62c1d6L +
	    (tm 	     x[78 & 0x0f] ^ x[(78 - 14) & 0x0f] ^ x[(78 - 8) &
0x0f] ^
	     x[(78 - 3) & 0x0f], (x[78 & 0x0f] 				  (((tm) << (1)) |
((tm) >> (32 - (1))))));
	  d = (((d) << (30)) | ((d) >> (32 - (30))));
	}
      while (0);
      do
	{
	  a +	    (((b) << (5)) | ((b) >> (32 - (5)))) + (c ^ d ^ e) +
0xca62c1d6L +
	    (tm 	     x[79 & 0x0f] ^ x[(79 - 14) & 0x0f] ^ x[(79 - 8) &
0x0f] ^
	     x[(79 - 3) & 0x0f], (x[79 & 0x0f] 				  (((tm) << (1)) |
((tm) >> (32 - (1))))));
	  c = (((c) << (30)) | ((c) >> (32 - (30))));
	}
      while (0);
      a = ctx->A += a;
      b = ctx->B += b;
      c = ctx->C += c;
      d = ctx->D += d;
      e = ctx->E += e;
    }
}

Chris Lattner

2002-Dec-14 15:25 UTC

head link

[LLVMdev] really long time to compile

> Can anyone suggest any reasons why this seemingly-innocuous (though
> stupid-looking) excerpt from gnu fileutils 4.1 would make llvm-gcc
> go so incredibly slowly? It doesn't seem to be a question of the
> size of the output.
I'll look into it.  That is a very, uh, interesting code snippet :)

-Chris
> Here's what I do:
>
> % time llvm-gcc -c sha24.c
> 56.840u 0.050s 1:07.05 84.8%    0+0k 0+0io 1050pf+0w
> % ls -l sha24.o
> -rw-r--r--    1 brg      brg          5784 2002-12-14 07:43 sha24.o
>
> The problem goes away if I use -S:
>
> % time llvm-gcc -S sha24.c
> 0.060u 0.010s 0:00.09 77.7%     0+0k 0+0io 548pf+0w
>
>
-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

Chris Lattner

2002-Dec-14 21:58 UTC

head link

[LLVMdev] really long time to compile

> Can anyone suggest any reasons why this seemingly-innocuous (though
> stupid-looking) excerpt from gnu fileutils 4.1 would make llvm-gcc
> go so incredibly slowly? It doesn't seem to be a question of the
> size of the output.
As it turns out, it was (suprisingly) the reassociate pass that was taking
the huge amounts of time.  This is fixed by applying these two patches:

http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20021209/001946.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20021209/001947.html

The first patch is just a cleanup patch which simplifies moving an
instruction, the second fixes the problem by introducing a cache to avoid
some pretty incredible recomputation for this testcase.

Thanks for finding this, in my debug build, reassociate went from
taking> 27 seconds on this testcase to .35  :)
-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

Possibly Parallel Threads

Search for more apparently analagous threads

llvm dev - Dec 2002 - [LLVMdev] really long time to compile

[LLVMdev] really long time to compile

[LLVMdev] really long time to compile

[LLVMdev] really long time to compile

Possibly Parallel Threads