ram@wb1.cs.cmu.edu (Rob MacLachlan) (05/02/90)
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
ian@argosy.UUCP (Ian L. Kaplan) (05/08/90)
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. Very large basic blocks can and do arise in non-trivial programs. For example, Fortran 8x programs that contain array expressions can generate very large basic blocks. In "scalar" Fortran code these array expressions would have been expressed as loops and conditional statements. As Mr. MacLachlan suggests, we would see many small basic blocks. However, Fortran is starting to move away from scalar expressions toward vector expressions. Calculations in scalar Fortran that were done in loops and if statements can now be written as array expressions or WHERE statements in Fortran 8x. This can reduce a routine that used to contain a number of basic blocks to a single basic block. Before this is discarded as an artifact of Fortran 8x, I would also like to point out that vectorizing compilers do much the same sort of thing: by converting loops into vector expressions they remove basic blocks. Sometimes people seem to forget that the world is not made up entirely of "C" users. Ian Kaplan ian@maspar.com
mcdonald@aries.scs.uiuc.edu (Doug McDonald) (05/08/90)
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
meissner@osf.org (Michael Meissner) (05/10/90)
In article <560@argosy.UUCP> ian@argosy.UUCP (Ian L. Kaplan) writes: | In article <9124@pt.cs.cmu.edu> ram@wb1.cs.cmu.edu (Rob MacLachlan) writes: | Like most gross generalizations, this one is wrong. Very large | basic blocks can and do arise in non-trivial programs. For example, | Fortran 8x programs that contain array expressions can generate very | large basic blocks. In "scalar" Fortran code these array expressions | would have been expressed as loops and conditional statements. As Mr. | MacLachlan suggests, we would see many small basic blocks. However, | Fortran is starting to move away from scalar expressions toward vector | expressions. Calculations in scalar Fortran that were done in loops | and if statements can now be written as array expressions or WHERE | statements in Fortran 8x. This can reduce a routine that used to | contain a number of basic blocks to a single basic block. Before this | is discarded as an artifact of Fortran 8x, I would also like to point | out that vectorizing compilers do much the same sort of thing: by | converting loops into vector expressions they remove basic blocks. | | Sometimes people seem to forget that the world is not made up | entirely of "C" users. Umm, aren't we forgetting what a basic block is? It is a section of straight-line code that has no entrances except for the top, and except for the last statement contains no conditionals or branches. Array expressions would typically generate a loop around a small inner basic block, unless you completely unroll the loop. Unrolling extermely large array loops completely is not typically a reasonable thing to do. Unless it is fully unrolled, a new small basic block is formed, so that the assertion that fortran 8x array ops makes a large basic block is false. -- Michael Meissner email: meissner@osf.org phone: 617-621-8861 Open Software Foundation, 11 Cambridge Center, Cambridge, MA Catproof is an oxymoron, Childproof is nearly so