Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!ux1.cso.uiuc.edu!aries!mcdonald
From: mcdonald@aries.scs.uiuc.edu (Doug McDonald)
Newsgroups: comp.arch
Subject: Re: Compile Times on BIG Basic Blocks
Message-ID: <1990May7.222839.22954@ux1.cso.uiuc.edu>
Date: 7 May 90 22:28:39 GMT
References: <7942@granola.ai.mit.edu> <9124@pt.cs.cmu.edu> <560@argosy.UUCP>
Sender: usenet@ux1.cso.uiuc.edu (News)
Reply-To: mcdonald@aries.scs.uiuc.edu (Doug McDonald)
Organization: School of Chemical Sciences, Univ. of Illinois at Urbana-Champaign
Lines: 51

In article <560@argosy.UUCP> ian@bear.UUCP (Ian L. Kaplan) writes:
>In article <9124@pt.cs.cmu.edu> ram@wb1.cs.cmu.edu (Rob MacLachlan) writes:
>>
>>It's pretty silly to get worked up about compiler algorithms that perform
>>badly on large basic blocks; all large blocks means is that the program is
>>very simple, giving the optimizers an embarassment of riches.
>>
>>If these algorithms really were optimal, and if it really were important to
>>extend optimality across as large an extent of the program as possible, then
>>there might be some reason for concern.  However neither is true.  All you
>>need to do is limit the extent of the intra-block optimization, either with
>>a window or by gratuitously splitting blocks.
>>
>>The really nasty problems in flow analysis are those which blow up with
>>program *complexity*, not simplicitly.
>>
>>  Rob
>
>  Like most gross generalizations, this one is wrong. 
I'm not so sure of that.

> Very large
>basic blocks can and do arise in non-trivial programs.
Very true.

  For example,
>Fortran 8x programs that contain array expressions can generate very
>large basic blocks. 

True. 

But also true is that even ordinary Fortran 77 or C programs for
science and engineering can contain large blocks: hundreds or thousands of
lines of arithmetic statements. The largest I personally have seen 
was perhaps 900 of code. Very complex statements, full of scores
of variables, many of them  indexed :

      DO 1 I=1,N
      DO 2 J=1,N
      A(I,17) = B(I,17) * C(J,22) + D(I,6)*E(I,4)*F(J)
      A(I,18) = B(I,17) * C(J,22) + D(I,6)*E(I,5)*F(51-J)
      A(I,19) = B(I,17) * C(J,25) + D(I,3)*E(I,5)*F(51-J)
           **898 more in the block **
2     CONTINUE
1     CONTINUE

This sort of mess can (and did!) result from machine generated code that
would be excruciatingly slow if all those fixed indices had to be
recalculated during every loop . Notice those common subexpressions. 

Doug McDonald