Method and system for generating compact code for the loop unrolling transformation

Abstract

A loop unrolling trasformation specified by loop unrolling factors UF[1], . . . , UF[k] is performed on a perfect nest of k multiple loops to produce an unrolled loop representation as follows. Moving from the outermost loop to the innermost loop of the nest, the unroll factor UF[j] of the current loop is examined. First, the separate unrolled loop body is expanded by the specified unroll factor UF[j]. Second, the loop header for the current loop is adjusted so that if the loop's iteration count, COUNT[j], is known to be less than or equal to the unroll factor, UP[j], then the loop header is simply an assignment of the index variable to the lower-bound expression; otherwise, the loop header is adjusted so that the unrolled loop's iteration count equals .left brkt-bot.COUNT[J]/UF[J].right brkt-bot. a rounded down truncation of the division. Third, a remainder loop nest is generated, if needed. The size of the generated code when unrolling multiple nested loops is substantially reduced. The proportion of the object code comprising lower execution frequency remainder loops is also substantially reduced. The compile-time of unrolled multiple nested loops is also substantially reduced.

Claims

We claim:

1. A method of performing a loop unrolling transformation specified by loop unrolling factors UF[1], . . . , UF[k] on a perfect nest of k multiple loops 1, . . . , k, wherein UK[j] is an unrolling factor corresponding to loop j, to produce an unrolled loop representation, said method comprising the steps of:

moving from an outermost loop 1 to an innermost loop k of the nest, examining an unroll factor UF[j] of a current loop j;

expanding a separate unrolled loop body by the specified unroll factor UF[j];

adjusting a loop header for the current loop j, further comprising:

adjusting the loop header to be an assignment of an index variable to a lower-bound expression if an iteration count of the current loop, COUNT[j], is less than or equal to the unroll factor of the current loop, UF[j]; and

adjusting the loop header so that the iteration count of the current loop j equals a rounded down truncation of a result of dividing the iteration count of the current loop by the unroll factor of the current loop, .left brkt-bot.COUNT[j]/UF[j].right brkt-bot., if the iteration count of the current loop, COUNT[j], is not less than or equal to the unroll factor of the current loop, UF[j]; and

generating a remainder loop nest if the remainder loop nest is needed to complete the unrolled loop representation.

2. The method of claim 1 wherein the step of generating the remainder loop nest if the remainder loop nest is needed to complete the unrolled loop representation further comprises:

not generating the remainder loop nest if the an iteration count of the current loop, COUNT[j], is a multiple of the unroll factor of the current loop, UF[j].

3. The method of claim 2 wherein a body of the remainder loop nest is a single copy of an input loop body.

4. The method of claim 2 wherein a body of the remainder loop is a cross product of unrolled copies from loops 1, . . . , j-1 and single copies from loops j, . . . , k.

5. The method of claim 1 wherein the step of expanding the separate unrolled loop body by the specified unroll factor UF[j] further comprises:

replacing all occurrences of a loop index variable, i.sub.j, for a j.sup.th loop, LOOP[j], in the separate unrolled loop body by a summation of the loop index variable, i.sub.j, and a product of an increment, inc.sub.j, of the j.sup.th loop, LOOP[j], and an unroll variable, u, wherein the unroll variable, u, is incremented from one to the specified unroll factor UF[j] corresponding to each copy of the j.sup.th loop, LOOP[j], in the separate unrolled loop body.

6. The method of claim 1 wherein the step of expanding the separate unrolled loop body by the specified unroll factor UF[j] further comprises:

generating an assignment statement of the form "i.sub.j =i.sub.j +inc.sub.j " at a start of each instance of the separate unrolled loop body.

7. An article of manufacture for use in a computer system for performing a loop unrolling transformation specified by loop unrolling factors UF[1], . . . UF[k] on a perfect nest of k multiple loops 1, . . . , k, wherein UF[j] is an unrolling factor corresponding to loop j, to produce an unrolled loop representation, said article of manufacture comprising a computer-readable storage medium having a computer program embodied in said medium which may cause the computer system to:

move from an outermost loop 1 to an innermost loop k of the nest, examining an unroll factor UF[j] of a current loop j;

expand a separate unrolled loop body by the specified unroll factor UF[j];

adjust a loop header for the current loop j, which may further cause the computer system to:

adjust the loop header to be an assignment of an index variable to a lower-bound expression if an iteration count of the current loop, COUNT[j], is less than or equal to the unroll factor of the current loop, UF[j]; and

adjust the loop header so that the iteration count of the current loop j equals a rounded down truncation of a result of dividing the iteration count of the current loop by the unroll factor of the current loop, .left brkt-bot.COUNT[j]/UF[j].right brkt-bot., if the iteration count of the current loop, COUNT[j], is not less than or equal to the unroll factor of the current loop, UF[j]; and

generate a remainder loop nest if the remainder loop nest is needed to complete the unrolled loop representation.

8. The article of manufacture of claim 7 wherein the computer program in causing the computer system to generate the remainder loop nest if the remainder loop nest is needed to complete the unrolled loop representation may further cause the computer system to:

not generate the remainder loop nest if the an iteration count of the current loop, COUNT[j], is a multiple of the unroll factor of the current loop, UF[j].

9. The article of manufacture of claim 8 wherein a body of the remainder loop nest is a single copy of an input loop body.

10. The article of manufacture of claim 8 wherein a body of the remainder loop is a cross product of unrolled copies from loops 1, . . . , j-1 and single copies from loops j, . . . , k.

11. The article of manufacture of claim 7 wherein the computer program in causing the computer system to expand the separate unrolled loop body by the specified unroll factor UF[j] may further cause the computer system to:

replace all occurrences of a loop index variable, i.sub.j, for a j.sup.th loop, LOOP[j], in the separate unrolled loop body by a summation of the loop index variable, i.sub.j, and a product of an increment, inc.sub.j, of the j.sup.th loop, LOOP[j], and an unroll variable, u, wherein the unroll variable, u, is incremented from one to the specified unroll factor UF[j] corresponding to each copy of the j.sup.th loop, LOOP[j], in the separate unrolled loop body.

12. The article of manufacture of claim 7 wherein the computer program in causing the computer system to expand the separate unrolled loop body by the specified unroll factor UF[j] may further cause the computer system to:

generate an assignment statement of the form "i.sub.j =i.sub.j +inc.sub.j " at a start of each instance of the separate unrolled loop body.

13. A computer system for performing a loop unrolling transformation specified by loop unrolling factors UF[1], . . . , UF[k] on a perfect nest of k multiple loops 1, . . . , k, wherein UF[j] is an unrolling factor corresponding to loop j, to produce an unrolled loop representation, said computer system comprising:

a movement from an outermost loop 1 to an innermost loop k of the nest, examining an unroll factor UF[j] of a current loop j;

an expansion of a separate unrolled loop body by the specified unroll factor UF[j];

an adjustment of a loop header for the current loop j, which further comprises:

an adjustment of the loop header to be an assignment of an index variable to a lower-bound expression if an iteration count of the current loop, COUNT[j], is less than or equal to the unroll factor of the current loop, UF[j]; and

an adjustment of the loop header so that the iteration count of the current loop j equals a rounded down truncation of a result of dividing the iteration count of the current loop by the unroll factor of the current loop, .left brkt-bot.COUNT[j]/UF[j].right brkt-bot., if the iteration count of the current loop, COUNT[j], is not less than or equal to the unroll factor of the current loop, UF[j]; and

a generation of a remainder loop nest if the remainder loop nest is needed to complete the unrolled loop representation.

14. The computer system of claim 13 wherein the generation of the remainder loop nest if the remainder loop nest is needed to complete the unrolled loop representation further comprises:

a non-generation of the remainder loop nest if the an iteration count of the current loop, COUNT[j], is a multiple of the unroll factor of the current loop, UF[j].

15. The computer system of claim 14 wherein a body of the remainder loop nest is a single copy of an input loop body.

16. The computer system of claim 14 wherein a body of the remainder loop is a cross product of unrolled copies from loops 1, . . . , j-1 and single copies from loops j, . . . , k.

17. The computer system of claim 13 wherein the expansion of the separate unrolled loop body by the specified unroll factor UF[j] further comprises:

a replacement of all occurrences of a loop index variable, i.sub.j, for a j.sup.th loop, LOOP[j], in the separate unrolled loop body by a summation of the loop index variable, i.sub.j, and a product of an increment, inc.sub.j, of the j.sup.th loop, LOOP[j], and an unroll variable, u, wherein the unroll variable, u, is incremented from one to the specified unroll factor UF[j] corresponding to each copy of the j.sup.th loop, LOOP[j], in the separate unrolled loop body.

18. The computer system of claim 13 wherein the expansion of the separate unrolled loop body by the specified unroll factor UF[j] further comprises:

a generation of an assignment statement of the form "i.sub.j =i.sub.j +inc.sub.j " at a start of each instance of the separate unrolled loop body.

Description

A portion of the Disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates in general to software optimization that may be used by a programmer or an automatic program optimizer, and more particularly to a technique for generating compact code for the unrolling transformation applied to a perfect nest of loops.

2. Description of the Related Art

Loop unrolling is a well known program transformation used by programmers and program optimizers to improve the instruction-level parallelism and register locality and to decrease the branching overhead of program loops. These benefits arise because creating multiple copies of the loop body provides more opportunities for program optimization. Most optimizing compilers employ the loop unrolling transformation to some degree. In addition, many software packages, especially those for matrix computations, contain library routines in which loops have been hand-unrolled for improved performance.

Historically, the unrolling transformation has been defined for a single loop. More recently, it has been observed that further benefits may be obtained by unrolling multiple nested loops and fusing or jamming together unrolled copies of inner loops. This "unroll-and jam" transformation has a multiplicative effect on the unroll factors of the individual loops, such that the number of copies in the unrolled loop body equals the product of the unroll factors of the individual loops.

A general concern with the aggressive use of unrolling is with the size of the code generated after the loop unrolling transformation is performed, especially when unrolling multiple perfectly nested loops. Apart from creating a larger unrolled loop body, additional loops have to be introduced to correctly handle cases where the unroll factor does not evenly divide the number of iterations. These "remainder" loops substantially increase the compile-time for the transformed code and the size of the final object code, even though only a small fraction of the program's execution time is spent in these remainder loops.

To quantitatively understand the substantial code size increase that may result from applying the unroll-and-jam transformation to multiple loops, let UF[1], . . . , UF[k] be the unroll factors for a perfect nest of k loops numbered from outermost to innermost. After the conventional unroll-and-jam transformation is applied, the unrolled loop will contain .vertline.UF[1]+mod(1,UF[1]).vertline..times..vertline.UF[2]+mod(1,UF[2]). vertline..times. . . . .times..vertline.UF[k]+mod(1,UF[k]).vertline.copies of the loop body for the general and common case of loop bounds that are unknown at compile-time, where "mod(1, UF[i])" is a function that equals zero when UF[i]=1 and where the function equals one when UF[i]>1. For example, if all k loops have the same unroll factor m where UF[1]=UF[2]= . . . =UF[k]=m>1, then the conventional unroll-and-jam transformation will generate C'=(m+1).sup.k copies of the loop body in the unrolled code. More specifically, if the conventional unroll-and-jam transformation is applied to the example code of Table A with m=4 and k=3, then 125 copies will be generated, C'=125=(4+1).sup.3. This generated code is shown in Table C. Note that only 64 copies are in the main unrolled loop body, and that the remaining 65 copies are lower execution frequency remainder loops. Thus, this example clearly illustrates the high proportion of code comprising lower execution frequency remainder loops, as in this example, the prior art generates a greater amount of code in lower execution frequency remainder loops than it does in the higher execution frequency main unrolled loop body.

Thus, conventional techniques of loop unrolling in generating remainder loops substantially increase the compile-time, the size of the object code, and the proportion of the object code comprising lower execution frequency remainder loops. As such, there is a need for a method of, and apparatus for, and article of manufacture for generating smaller more compact code for the unrolling transformation of multiple nested loops.

SUMMARY OF THE INVENTION

The invention disclosed herein comprises a method of, a system for, and an article of manufacture for generating compact code for the unrolling transformation. The present invention substantially reduces the size of the generated code when unrolling multiple nested loops. The present invention substantially reduces the proportion of the object code comprising lower frequency execution remainder loops. The present invention substantially reduces the compile-time of unrolled multiple nested loops.

Given a perfect nest of k multiple loops, the present invention performs a loop unrolling transformation specified by loop unrolling factors UF[1], . . . , UF[k] and produces an unrolled loop representation as follows. Moving from the outermost loop to the innermost loop of the nest, the invention examines the unroll factor UF[j] of the current loop. The first major step is to expand the separate unrolled loop body by the specified unroll factor UF[j]. The second major step is to adjust the loop header for the current loop. If the loop's iteration count, COUNT[j], is known to be less than or equal to the unroll factor, UF[j], then the loop header is simply an assignment of the index variable to the lower-bound expression; otherwise, the loop header is adjusted so that the unrolled loop's iteration count equals .left brkt-bot.COUNT[j]/UF[j].right brkt-bot., a rounded down truncation of the division. The third major step is to generate a remainder loop nest, if needed. The body of the remainder loop nest is a single copy of the input loop body. The body of the remainder loop is a cross product of unrolled copies from loops 1 . . . j-1 and single copies from loops j . . . k. The remainder loop is not created if it is determined at compile time that the loop length COUNT[j] is a multiple of the unroll factor UF[j].

As opposed to the conventional unroll-and-jam transformation discussed above which produces .vertline.UF[1]+mod(1,UF[1]).vertline..times..vertline.UF[2]+mod(1,UF[2]). vertline. . . . .times..vertline.UF[k]+mod(1,UF[k]).vertline. loop copies in the transformed code, the present invention only produces UF[1].times. . . . .times.UF[k]copies of the code from the original loop body in addition to at most (UF[1].times. . . . .times.UF[k-1])+(UF[1].times. . . . .times.UF[k-2])+ . . . +(UF[1].times.UF[2])+(UF[1])+1 remainder loops in the transformed code, each containing a single copy of the code from the original loop body. More precisely, the number of remainder loops generated by the present invention is at most: SUM FROM i=1 to k(PRODUCT FROM j=1 to k-i (UF[j])). For the k=1 single loop case, the present invention produces the same number of copies as the conventional unroll-and-jam transformation, at most UF[1]+1 copies: UF[1] copies of the unrolled loop and at most one remainder loop. However, for the k.gtoreq.2 multiple-loop case, the present invention generates substantially fewer lower execution frequency remainder loops than the conventional unroll-and-jam transformation.

Referring back to the example code of Table A where application of the conventional unroll-and-jam transformation produced 125 copies of the loop body, if the unroll transformation of the present invention is applied to the example code of Table A with m=4 and k=3, then only 85 copies will be generated, C=1+m+m.sup.2 + . . . +m.sup.k =.vertline.m.sup.(k+ 1-1.vertline./.vertline.m-1.vertline.=.vertline.4.sup.(3+1) -1.vertline./.vertline.4-1.vertline.=85. The transformed code generated by the present invention for the example code is shown in Table B. Note that only 21 copies (85 total-64 main unrolled loop body copies) of the lower execution frequency remainder loops are generated by the present invention as opposed to the 61 copies of lower execution frequency remainder loops generated by the prior art.

The present invention has the advantage of generating fewer remainder loop statements after unrolling, and hence reducing the compilation time to process the output generated by the unrolling transformation.

The present invention has the further advantage of reducing the code size that results after the unrolling transformation is performed.

BRIEF DESCRIPTION OF THE DRAWINGS

For a more complete understanding of the present invention and the advantages thereof, reference is now made to the Detailed Description in conjunction with the attached Drawings, in which:

FIG. 1 illustrates a symbolic pictorial representation of a partitioning of loop iterations for the simple case of k=1 (a perfect nest of a single loop) in accordance with the present invention;

FIG. 2 illustrates a symbolic pictorial representation of a partitioning of loop iterations for the simple case of k=2 (a perfect nest of two loops) in accordance with the present invention;

FIG. 3 illustrates psuedo-code comprising the operations preferred in carrying out the present invention;

FIG. 4 is a flowchart illustrating the operations preferred in carrying out the present invention;

FIG. 5 illustrates a tree structure for an original intermediate representation of loops to be unrolled in accordance with the present invention;

FIG. 6 and FIG. 7 illustrate unrolled loop bodies produced in accordance with the present invention;

FIG. 8, FIG. 9, and FIG. 10 are additional flowcharts illustrating the operations preferred in carrying out the present invention; and

FIG. 11 is a block diagram of a computer system used in performing the method of the present invention, forming part of the apparatus of the present invention, and which may use the article of manufacture comprising a computer-readable storage medium having a computer program embodied in said medium which may cause the computer system to practice the present invention.

DESCRIPTION OF THE PREFERRED EMBODIMENT

Referring now to FIG. 1 and FIG. 2, pictorial representations of partitioning of loop iterations according to the present invention are shown for the simple cases of k=1 (a perfect nest of a single loop) and k=2 (a perfect nest of two loops). FIG. 1 illustrates that application of the present invention to a perfect nest of a single loop (k=1) produces UF[1]+1 copies of the unrolled loop body, UF[1] copies in the unrolled loop and one copy in the remainder loop. FIG. 2 illustrates that application of the present invention to a perfect nest of two loops (k=2) produces UF[1].times.UF[2]+UF[1]+1 copies of the unrolled loop body, UF[1].times.UF[2] copies in the unrolled loop and UF[1]+1 copies in the remainder loop.

Referring now to Table A, there is shown an example comprising a perfect nest of four loops, the outer three of which are each to be unrolled with an unroll factor of four (UF[1]=UF[2]=UF[3]=4). Thus, the innermost loop is considered a part of the unrolled loop body as the innermost loop is not unrolled in this example.

                  TABLE A
    ______________________________________
    do l = 1, n
    do k = 1, n
    do j = 1, n
    do i = 1, n
    sum = sum + a(i,j,k) + b(i,j,l) + c(i,k,l)
    end do
    end do
    end do
    end do
    ______________________________________

                  TABLE B
    ______________________________________
    do l=1,n - 3,4
     do k=1,n - 3,4
     do j=1,n - 3,4
      do i=1,n,1
      sum = sum + a(i,j,k) + b(i,j,l) + c(i,k,l)
      sum = sum + a(i,j,k) + b(i,j,l + 1) + c(i,k,l + 1)
      sum = sum + a(i,j,k) + b(i,j,l + 2) + c(i,k,l + 2)
      sum = sum + a(i,j,k) + b(i,j,l + 3) + c(i,k,l + 3)
      sum = sum + a(i,j,k + 1) + b(i,j,l) + c(i,k + 1,l)
      sum = sum + a(i,j,k + 1) + b(i,j,l + 1) + c(i,k + 1,l + 1)
      sum = sum + a(i,j,k + 1) + b(i,j,l + 2) + c(i,k + 1,l + 2)
      sum = sum + a(i,j,k + 1) + b(i,j,l + 3) + c(i,k + 1,l + 3)
      sum = sum + a(i,j,k + 2) + b(i,j,l) + c(i,k + 2,l)
      sum = sum + a(i,j,k + 2) + b(i,j,l + 1) + c(i,k + 2,l + 1)
      sum = sum + a(i,j,k + 2) + b(i,j,l + 2) + c(i,k + 2,l + 2)
      sum = sum + a(i,j,k + 2) + b(i,j,l + 3) + c(i,k + 2,l + 3)
      sum = sum + a(i,j,k + 3) + b(i,j,l) + c(i,k + 3,l)
      sum = sum + a(i,j,k + 3) + b(i,j,l + 1) + c(i,k + 3,l + 1)
      sum = sum + a(i,j,k + 3) + b(i,j,l + 2) + c(i,k + 3,l + 2)
      sum = sum + a(i,j,k + 3) + b(i,j,l + 3) + c(i,k + 3,l + 3)
      sum = sum + a(i,j + 1,k) + b(i,j + 1,l) + c(i,k,l)
      sum = sum + a(i,j + 1,k) + b(i,j + 1,l + 1) + c(i,k,l + 1)
      sum = sum + a(i,j + 1,k) + b(i,j + 1,l + 2) + c(i,k,l + 2)
      sum = sum + a(i,j + 1,k) + b(i,j + 1,l + 3) + c(i,k,l + 3)
      sum = sum + a(i,j + 1,k + 1) + b(i,j + 1,l) + c(i,k + 1,l)
      sum = sum + a(i,j + 1,k + 1) + b(i,j + 1,l + 1) + c(i,k + i,l + 1)
      sum = sum + a(i,j + 1,k + 1) + b(i,j + 1,l + 2) + c(i,k + i,l + 2)
      sum = sum + a(i,j + 1,k + 1) + b(i,j + 1,l + 3) + c(i,k + i,l + 3)
      sum = sum + a(i,j + 1,k + 2) + b(i,j + 1,l) + c(i,k + 2,l)
      sum = sum + a(i,j + 1,k + 2) + b(i,j + 1,l + 1) + c(i,k + 2,l + 1)
      sum = sum + a(i,j + 1,k + 2) + b(1,j + 1,l + 2) + c(i,k.+ 2,l + 2)
      sum = sum + a(i,j + 1,k + 2) + b(i,j + 1,l + 3) + c(i,k + 2,l + 3)
      sum = sum + a(i,j + 1,k + 3) + b(i,j + 1,l) + c(i,k + 3,l)
      sum = sum + a(i,j + 1,k + 3) + b(i,j + 1,l + 1) + c(i,k + 3,l + 1)
      sum = sum + a(i,j + 1,k + 3) + b(i,j + 1,l + 2) + c(i,k + 3,l + 2)
      sum = sum + a(i,j + 1,k + 3) + b(i,j + 1,l + 3) + c(i,k + 3,l + 3)
      sum = sum + a(i,j + 2,k) + b(i,j + 2,l) + c(i,k,l)
      sum = sum + a(i,j + 2,k) + b(i,j + 2,l + 1) + c(i,k,l + 1)
      sum = sum + a(i,j + 2,k) + b(i,j + 2,l + 2) + c(i,k,l + 2)
      sum = sum + a(i,j + 2,k) + b(i,j + 2,l + 3) + c(i,k,l + 3)
      sum = sum + a(i,j + 2,k + 1) + b(i,j + 2,l) + c(i,k + 1,l)
      sum = sum + a(i,j + 2,k + 1) + b(i,j + 2,l + 1) + c(i,k + 1,l + 1)
      sum = sum + a(i,j + 2,k + 1) + b(i,j + 2,l + 2) + c(i,k + 1,l + 2)
      sum = sum + a(i,j + 2,k + 1) + b(i,j + 2,l + 3) + c(i,k + 1,l + 3)
      sum = sum + a(i,j + 2,k + 2) + b(i,j + 2,l) + c(1,k + 2,l)
      sum = sum + a(i,j + 2,k + 2) + b(i,j + 2,l + 1) + c(i,k + 2,l + 1)
      sum = sum + a(i,j + 2,k + 2) + b(i,j + 2,l + 2) + c(i,k + 2,l + 2)
      sum = sum + a(i,j + 2,k + 2) + b(i,j + 2,l + 3) + c(i,k + 2,l + 3)
      sum = sum + a(i,j + 2,k + 3) + b(i,j + 2,l) + c(i,k + 3,l)
      sum = sum + a(i,j + 2,k + 3) + b(i,j + 2,l + 1) + c(i,k + 3,l + 1)
      sum = sum + a(i,j + 2,k + 3) + b(i,j + 2,l + 2) + c(i,k + 3,l + 2)
      sum = sum + a(i,j + 2,k + 3) + b(i,j + 2,l + 3) + c(i,k + 3,l + 3)
      sum = sum + a(i,j + 3,k) + b(i,j + 3,l) + c(i,k,l)
      sum = sum + a(i,j + 3,k) + b(i,j + 3,l + 1) + c(i,k,l + 1)
      sum = sum + a(i,j + 3,k) + b(i,j + 3,l + 2) + c(i,k,l + 2)
      sum = sum + a(i,j + 3,k) + b(i,j + 3,l + 3) + c(i,k,l + 3)
      sum = sum + a(i,j + 3,k + 1) + b(i,j + 3,l) + c(i,k + 1,l)
      sum = sum + a(i,j + 3,k + 1) + b(i,j + 3,l + 1) + c(i,k + i,l + 1)
      sum = sum + a(i,j + 3,k + 1) + b(i,j + 3,l + 2) + c(i,k + i,l + 2)
      sum = sum + a(i,j + 3,k + 1) + b(i,j + 3,l + 3) + c(i,k + i,l + 3)
      sum = sum + a(i,j + 3,k + 2) + b(i,j + 3,l) + c(i,k + 2,l)
      sum = sum + a(i,j + 3,k + 2) + b(i,j + 3,l + 1) + c(i,k + 2,l + 1)
      sum = sum + a(i,j + 3,k + 2) + b(i,j + 3,l + 2) + c(i,k + 2,l + 2)
      sum = sum + a(i,j + 3,k + 2) + b(i,j + 3,l + 3) + c(i,k + 2,l + 3)
      sum = sum + a(i,j + 3,k + 3) + b(i,j + 3,l) + c(i,k + 3,l)
      sum = sum + a(i,j + 3,k + 3) + b(i,j + 3,l + 1) + c(i,k + 3,l + 1)
      sum = sum + a(i,j + 3,k + 3) + b(i,j + 3,l + 2) + c(i,k + 3,l + 2)
      sum = sum + a(i,j + 3,k + 3) + b(i,j + 3,l + 3) + c(i,k + 3,l + 3)
      end do
     end do
     do j=j,n,1
      do i=1,n,1
      sum = sum + a(i,j,k) + b(i,j,l) + c(i,k,l)
      sum = sum + a(i,j,k) + b(i,j,l + 1) + c(i,k,l + 1)
      sum = sum + a(i,j,k) + b(i,j,l + 2) + c(i,k,l + 2)
      sum = sum + a(i,j,k) + b(i,j,l + 3) + c(i,k,l + 3)
      sum = sum + a(i,j,k + 1) + b(i,j,l) + c(i,k + 1,l)
      sum = sum + a(i,j,k + 1) + b(i,j,l + 1) + c(i,k + 1,l + 1)
      sum = sum + a(i,j,k + 1) + b(i,j,l + 2) + c(i,k + 1,l + 2)
      sum = sum + a(i,j,k + 1) + b(i,j,l + 3) + c(i,k + 1,l + 3)
      sum = sum + a(i,j,k + 2) + b(i,j,l) + c(i,k + 2,l)
      sum = sum + a(i,j,k + 2) + b(i,j,l + 1) + c(i,k + 2,l + 1)
      sum = sum + a(i,j,k + 2) + b(i,j,l + 2) + c(i,k + 2,l + 2)
      sum = sum + a(i,j,k + 2) + b(i,j,l + 3) + c(i,k + 2,l + 3)
      sum = sum + a(i,j,k + 3) + b(i,j,l) + c(i,k + 3,l)
      sum = sum + a(i,j,k + 3) + b(i,j,l + 1) + c(i,k + 3,l + 1)
      sum = sum + a(i,j,k + 3) + b(i,j,l + 2) + c(i,k + 3,l + 2)
      sum = sum + a(i,j,k + 3) + b(i,j,l + 3) + c(i,k + 3,l + 3)
      end do
     end do
     end do
     do k=k,n,1
     do j=1,n,1
      do i=1,n,1
      sum = sum + a(i,j,k) + b(i,j,l) + c(i,k,l)
      sum = sum + a(i,j,k) + b(i,j,l + 1) + c(i,k,l + 1)
      sum = sum + a(i,j,k) + b(i,j,l + 2) + c(i,k,l + 2)
      sum = sum + a(i,j,k) + b(i,j,l + 3) + c(i,k,l + 3)
      end do
     end do
     end do
    end do
    do i=l,n,1
     do k=1,n,1
     do j=1,n,1
      do i=1,n,1
      sum = sum + a(i,j,k) + b(i,j,l) + c(i,k,l)
      end do
     end do
     end do
    end do
    ______________________________________

                  TABLE C
    ______________________________________
    do l = 1, n-3, 4
     do k = 1, n-3, 4
     do j = 1, n-3, 4
      do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l) + c(i,k,l)
      sum = sum + a(i,j+1,k) + b(i,j+1,l) + c(i,k,l)
      sum = sum + a(i,j+2,k) + b(i,j+2,l) + c(i,k,l)
      sum = sum + a(i,j+3,k) + b(i,j+3,l) + c(i,k,l)
      sum = sum + a(i,j,k+1) + b(i,j,l) + c(i,k+1,l)
      sum = sum + a(i,j+1,k+1) + b(i,j+1,l) + c(i,k+1,l)
      sum = sum + a(i,j+2,k+1) + b(i,j+2,l) + c(i,k+1,l)
      sum = sum + a(i,j+3,k+1) + b(i,j+3,l) + c(i,k+1,l)
      sum = sum + a(i,j,k+2) + b(i,j,l) + c(i,k+2,l)
      sum = sum + a(i,j+1,k+2) + b(i,j+1,l) + c(i,k+2,l)
      sum = sum + a(i,j+2,k+2) + b(i,j+2,l) + c(i,k+2,l)
      sum = sum + a(i,j+3,k+2) + b(i,j+3,l) + c(i,k+2,l)
      sum = sum + a(i,j,k+3) + b(i,j,l) + c(i,k+3,l)
      sum = sum + a(i,j+1,k+3) + b(i,j+1,l) + c(i,k+3,l)
      sum = sum + a(i,j+2,k+3) + b(i,j+2,l) + c(i,k+3,l)
      sum = sum + a(i,j+3,k+3) + b(i,j+3,l) + c(i,k+3,l)
      sum = sum + a(i,j,k) + b(i,j,l+1) + c(i,k,l+l)
      sum = sum + a(i,j+1,k) + b(i,j+1,l+1) + c(i,k,l+l)
      sum = sum + a(i,j+2,k) + b(i,j+2,l+1) + c(i,k,l+l)
      sum = sum + a(i,j+3,k) + b(i,j+3,l+1) + c(i,k,l+l)
      sum = sum + a(i,j,k+1) + b(i,j,l+l) + c(i,k+1,l+1)
      sum = sum + a(i,j+1,k+1) + b(i,j+1,l+1) + c(i,k+1,l+1)
      sum = sum + a(i,j+2,k+1) + b(i,j+2,l+1) + c(i,k+1,l+1)
      sum = sum + a(i,j+3,k+1) + b(i,j+3,l+1) + c(i,k+1,l+1)
      sum = sum + a(i,j,k+2) + b(i,j,l+1) + c(i,k+2,l+1)
      sum = sum + a(i,j+1,k+2) + b(i,j+1,l+1) + c(i,k+2,l+1)
      sum = sum + a(i,j+2,k+2) + b(i,j+2,l+1) + c(i,k+2,l+1)
      sum = sum + a(i,j+3,k+2) + b(i,j+3,l+1) + c(i,k+2,l+1)
      sum = sum + a(i,j,k+3) + b(i,j,l+1) + c(i,k+3,l+1)
      sum = sum + a(i,j+1,k+3) + b(i,j+1,l+1) + c(i,k+3,l+1)
      sum = sum + a(i,j+2,k+3) + b(i,j+2,l+1) + c(i,k+3,l+1)
      sum = sum + a(i,j+3,k+3) + b(i,j+3,l+1) + c(i,k+3,l+1)
      sum = sum + a(i,j,k) + b(i,j,l+2) + c(i,k,l+2)
      sum = sum + a(i,j+1,k) + b(i,j+1,l+2) + c(i,k,l+2)
      sum = sum + a(i,j+2,k) 4 b(1,j+2,l+2) + c(i,k,l+2)
      sum = sum + a(i,j+3,k) + b(i,j+3,l+2) + c(i,k,l+2)
      sum = sum + a(i,j,k+1) + b(i,j,l+2) + c(i,k+1,l+2)
      sum = sum + a(i,j+1,k+1) + b(i,j+1,l+2) + c(i,k+1,l+2)
      sum = sum + a(i,j+2,k+1) + b(i,j+2,l+2) + c(i,k+1,l+2)
      sum = sum + a(i,j+3,k+1) + b(i,j+3,l+2) + c(i,k+1,l+2)
      sum = sum + a(i,j,k+2) + b(i,j,l+2) + c(i,k+2,l+2)
      sum = sum + a(i,j+1,k+2) + b(i,j+1,l+2) + c(i,k+2,l+2)
      sum = sum + a(i,j+2,k+2) + b(i,j+2,l+2) + c(i,k+2,l+2)
      sum = sum + a(i,j+3,k+2) + b(i,j+3,l+2) + c(i,k+2,l+2)
      sum = sum + a(i,j,k+3) + b(i,j,l+2) + c(i,k+3,l+2)
      sum = sum + a(i,j+1,k+3) + b(i,j+1,l+2) + c(i,k+3,l+2)
      sum = sum + a(i,j+2,k+3) + b(i,j+2,l+2) + c(i,k+3,l+2)
      sum = sum + a(i,j+3,k+3) + b(i,j+3,l+2) + c(i,k+3,l+2)
      sum = sum + a(i,j,k) + b(i,j,l+3) + c(i,k,l+3)
      sum = sum + a(i,j+1,k) + b(i,j+1,l+3) + c(i,k,l+3)
      sum = sum + a(i,j+2,k) + b(i,j+2,l+3) + c(i,k,l+3)
      sum = sum + a(i,j+3,k) + b(i,j+3,l+3) + c(i,k,l+3)
      sum = sum + a(i,j,k+1) + b(i,j,l+3) + c(i,k+1,l+3)
      sum = sum + a(i,j+1,k+1) + b(i,j+1,l+3) + c(i,k+1,l+3)
      sum = sum + a(i,j+2,k+1) + b(i,j+2,l+3) + c(i,k+1,l+3)
      sum = sum + a(i,j+3,k+1) + b(i,j+3,l+3) + c(i,k+1,l+3)
      sum = sum + a(i,j,k+2) + b(i,j,l+3) + c(i,k+2,l+3)
      sum = sum + a(i,j+1,k+2) + b(i,j+1,l+3) + c(i,k+2,l+3)
      sum = sum + a(i,j+2,k+2) + b(i,j+2,l+3) + c(i,k+2,l+3)
      sum = sum + a(i,j+3,k+2) + b(i,j+3,l+3) + c(i,k+2,l+3)
      sum = sum + a(i,j,k+3) + b(i,j,l+3) + c(i,k+3,l+3)
      sum = sum + a(i,j+1,k+3) + b(i,j+1,l+3) + c(i,k+3,l+3)
      sum = sum + a(i,j+2,k+3) + b(i,j+2,l+3) + c(i,k+3,l+3)
      sum = sum + a(i,j+3,k+3) + b(i,j+3,l+3) + c(i,k+3,l+3)
      end do
     end do
     do j = j, n
      do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l) + c(i,k,l)
      sum = sum + a(i,j,k+1) + b(i,j,l) + c(i,k+1,l)
      sum = sum + a(i,j,k+2) + b(i,j,l) + c(i,k+2,l)
      sum = sum + a(i,j,k+3) + b(i,j,l) + c(i,k+3,l)
      end do
     end do
     end do
     do k = k, n
     do j = 1, n-3, 4
      do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l) + c(i,k,l)
      sum = sum + a(i,j+1,k) + b(i,j+1,l) + c(i,k,l)
      sum = sum + a(i,j+2,k) + b(i,j+2,l) + c(i,k,l)
      sum = sum + a(i,j+3,k) + b(i,j+3,l) + c(i,k,l)
     end do
     end do
     do j = j, n
     do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l) + c(i,k,l)
     end do
     end do
    end do
    do k = 1, n-3, 4
     do j = j, n
     do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l+1) + c(i,k,l+1)
      sum = sum + a(i,j,k+1) + b(i,j,l+1) + c(i,k+1,l+1)
      sum = sum + a(i,j,k+2) + b(i,j,l+1) + c(i,k+2,l+1)
      sum = sum + a(i,j,k+3) + b(i,j,l+1) + c(i,k+3,l+1)
      end do
     end do
     end do
     do k = k,n
     do j = 1, n-3, 4
      do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l+1) + c(i,k,l+1)
      sum = sum + a(i,j+1,k) + b(i,j+1,l+1) + c(i,k,l+1)
      sum = sum + a(i,j+2,k) + b(i,j+2,l+1) + c(i,k,l+1)
      sum = sum + a(i,j+3,k) + b(i,j+3,l+1) + c(i,k,l+1)
      end do
     end do
     do j = j, n
      do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l+1) + c(i,k,l+1)
      end do
     end do
     end do
     do k = 1, n-3, 4
     do j = j, n
      do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l+2) + c(i,k,l+2)
      sum = sum + a(i,j,k+1) + b(i,j,l+2) + c(i,k+1,l+2)
      sum = sum + a(i,j,k+2) + b(i,j,l+2) + c(i,k+2,l+2)
      sum = sum + a(i,j,k+3) + b(i,j,l+2) + c(i,k+3,l+2)
      end do
     end do
     end do
    do k = k, n
     do j = 1, n-3, 4
     do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l+2) + c(i,k,l+2)
      sum = sum + a(i,j+1,k) + b(i,j+1,l+2) + c(i,k,l+2)
      sum = sum + a(i,j+2,k) + b(i,j+2,l+2) + c(i,k,l+2)
      sum = sum + a(i,j+3,k) + b(i,j+3,l+2) + c(i,k,l+2)
      end do
     end do
     do j = j, n
      do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l+2) + c(i,k,l+2)
      end do
     end do
     end do
     do k = 1, n-3, 4
     do j = j, n
      do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l+3) + c(i,k,l+3)
      sum = sum + a(i,j,k+1) + b(i,j,l+3) + c(i,k+1,l+3)
      sum = sum + a(i,j,k+2) + b(i,j,l+3) + c(i,k+2,l+3)
      sum = sum + a(i,j,k+3) + b(i,j,l+3) + c(i,k+3,l+3)
      end do
     end do
     end do
     do k = k, n
     do j = 1, n-3, 4
      do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l+3) + c(i,k,l+3)
      sum = sum + a(i,j+1,k) + b(i,j+1,l+3) + c(i,k,l+3)
      sum = sum + a(i,j+2,k) + b(i,j+2,l+3) + c(i,k,l+3)
      sum = sum + a(i,j+3,k) + b(i,j+3,l+3) + c(i,k,l+3)
      end do
     end do
     do j = j, n
      do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l+3) + c(i,k,l+3)
      end do
     end do
     end do
    end do
    do l = l, n
     do k = 1, n-3, 4
     do j = 1, n-3, 4
      do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l) + c(i,k,l)
      sum = sum + a(i,j+1,k) + b(i,j+1,l) + c(i,k,l)
      sum = sum + a(i,j+2,k) + b(i,j+2,l) + c(i,k,l)
      sum = sum + a(i,j+3,k) + b(i,j+3,l) + c(i,k,l)
      sum = sum + a(i,j,k+1) + b(i,j,l) + c(i,k+1,l)
      sum = sum + a(i,j+1,k+1) + b(i,j+1,l) + c(i,k+1,l)
      sum = sum + a(i,j+2,k+1) + b(i,j+2,l) + c(i,k+1,l)
      sum = sum + a(i,j+3,k+1) + b(i,j+3,l) + c(i,k+1,l)
      sum = sum + a(i,j,k+2) + b(i,j,l) + c(i,k+2,l)
      sum = sum + a(i,j+1,k+2) + b(i,j+1,l) + c(i,k+2,l)
      sum = sum + a(i,j+2,k+2) + b(i,j+2,l) + c(i,k+2,l)
      sum = sum + a(i,j+3,k+2) + b(i,j+3,l) + c(i,k+2,l)
      sum = sum + a(i,j,k+3) + b(i,j,l) + c(i,k+3,l)
      sum = sum + a(i,j+1,k+3) + b(i,j+1,l) + c(i,k+3,l)
      sum = sum + a(i,j+2,k+3) + b(i,j+2,l) + c(i,k+3,l)
      sum = sum + a(i,j+3,k+3) + b(i,j+3,l) + c(i,k+3,l)
      end do
     end do
     do j = j, n
      do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l) + c(i,k,l)
      sum = sum + a(i,j,k+1) + b(i,j,l) + c(i,k+1,l)
      sum = sum + a(i,j,k+2) + b(i,j,l) + c(i,k+2,l)
      sum = sum + a(i,j,k+3) + b(i,j,l) + c(i,k+3,l)
      end do
     end do
     end do
     do k = k, n
     do j = 1, n-3, 4
      do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l) + c(i,k,l)
      sum = sum + a(i,j+1,k) + b(i,j+1,l) + c(i,k,l)
      sum = sum + a(i,j+2,k) + b(i,j+2,l) + c(i,k,l)
      sum = sum + a(i,j+3,k) + b(i,j+3,l) + c(i,k,l)
      end do
     end do
     do j = j, n
      do i = 1, n
      sum = sum + a(i,j,k) + b(i,j,l) + c(i,k,l)
      end do
     end do
     end do
    end do
    ______________________________________

                  TABLE D
    ______________________________________
    INPUTS:
    1.  LOOP[l]. . . LOOP[k], a perfect nest of k loops, numbered from
        outermost to innermost, in an optimizer intermediate representation.
        The notation, "do i.sub.j = lb.sub.j, ub.sub.j, inc.sub.j ", denotes
        the contents
        of statement LOOP[j] with index variable i.sub.j, lower bound
        lb.sub.j, upper bound ub.sub.j, and increment inc.sub.j.
    2.  UF[j] >= 1, unroll factor for each LOOP[j].
    3.  COUNT[j], constant value or symbolic expression for number of
        iterations executed by LOOP[j], where UF[j] is assumed to be less
        than or equal to COUNT[j] if COUNT[j] is a constant. It is well
        known by those skilled in the art to derive COUNT[j] from ib.sub.j
        (lower bound of j), ub.sub.j (upper bound of j), and inc.sub.j
        (increment of j).
    OUTPUT:
    1.  Updated intermediate representation of the unrolled loops to reflect
        the loop unrolling transformation specified by UF[l], . . ., UF[k].
    METHOD:
    Set next.sub.-- parent = parent of LOOP[j] in intermediate
    representation, the
      original loop nest;
    Detach subtree rooted at LOOP[l] from next.sub.-- parent/* this subtree
      is used as the source for generating copies of the original loop body
      in the unrolled and remainder loops */;
    Set unrolled.sub.-- body = copy of body of innermost loop, LOOP[k];
    for(j = l; j <= k; j++) {
     Set current.sub.--parent = next.sub.-- parent;
     /* STEP 1: Expand unrolled.sub.-- body by factor UF[j] for index i.sub.j
    */
     Set new.sub.-- unrolled.sub.-- loop.sub.-- body = copy of
    unrolled.sub.-- body;
     for (u = l; u <= UF[j] - 1; u++) {
      Set one.sub.-- copy = copy of unrolled.sub.-- body;
      replace all references of loop index variable "i.sub.j " in one.sub.--
    copy by
      "i.sub.j + inc.sub.j *u";
      append one.sub.-- copy to end of new.sub.-- unrolled.sub.-- loop.sub.--
    body;
     }
     Delete unrolled.sub.-- body and set unrolled.sub.-- body =
     new.sub.-- unrolled.sub.-- loop.sub.-- body;
     /* STEP 2: Adjust header for unrolled loop j */
     Construct the remainder expression er.sub.j, = mod(COUNT[j], UF[j]);
     if( COUNT[j] is constant and COUNT[j] = UF[j]) {
      /* loop j is to be completely unrolled */
      Construct the statement, "i" = lb.sub.j ", call it next.sub.-- parent,
      and make it the first
      (leftmost) child of current.sub.-- parent;
     }
     else {
      Make a copy of the LOOP[j] statement, call it next.sub.-- parent,
    change
      it to "do i.sub.j = lb.sub.j, ub.sub.j - er.sub.j *inc.sub.j,
      UF[j]*inc.sub.j ", and make it a child of
      current.sub.-- parent;
     }
     /* STEP 3: Generate remainder loop sub-nest, if necessary */
     if (er.sub.j is not a constant 0) {
      Set tree.sub.-- copy = copy of subtree rooted at LOOP[j];
      change the outermost statement in tree.sub.-- copy to
      "do i.sub.j = ub.sub.j - (er.sub.j -l)*inc.sub.j, ub.sub.j, inc.sub.j
    ";
      Make tree.sub.-- copy a child of current.sub.-- parent;
     }
     } /* for (j = . . . ) */
    Make unrolled.sub.-- body a child of next.sub.-- parent;
    Delete subtree rooted at LOOP[l] (original loop nest);
    ______________________________________

• Inventors
  Nguyen, Khoa; Sarkar, Vivek;
• Assignee
  International Business Machines Corporation (Armonk, NY)
• Published
  Mar-7-2000
• Current US Classes:
  717/160
• Application #
  900809
• International Classes
  G06F 009/445
• Field of Search
  395/709 395/704 395/706 395/708
• Examiner
  Hafiz; Tariq R.
• Agent
  Gates & Cooper
• US Patent References:
  5121498
  5430850
  5560029
  5704053
  5770894
  5790859
  5797013
  5842022
  5930510
  5950003