Method of, system for, and computer program product for providing inlined nested array constructors using normalized counters

Abstract

Method of, system for, and computer program product for generating efficient code for a set of nested Fortran 90 array constructors without introducing temporary vectors by the use of normalized counters and by maintaining array constructor extent structure trees. Non-perfectly nested array constructors and array constructors with dynamic extents may be inlined. The results provided include a reduction in run-time memory storage usage and an improvement in execution time performance.

Claims

We claim:

1. A method for translating an expression containing one or more array constructors nested in one or more array constructor levels in a source program, said method comprising the steps of:

searching a plurality of nodes of an expression tree of the expression for each of the array constructors;

associating a normalized counter with each of the array constructor levels;

scalarizing the array constructors nested in an array constructor level by use of the normalized counter associated with the array constructor level;

building an extent structure tree of a portion of the expression tree rooted at a current expression tree node if the current expression tree node is an array constructor; and

splitting the current expression tree node if the current expression tree node is a non-elemental operator.

2. The method of claim 1 wherein the building step further comprises the steps of:

determining if the current expression tree node has a non-elemental operator ancestor and no other array constructor in between, or if the extent structure tree rooted at the current expression tree node is not identical to a prior extent structure tree built at the array constructor level of the current expression tree node; and

splitting the current expression tree node, associating the normalized counter with the array constructor, and scalarizing the portion of the expression tree rooted at the current expression tree node using the associated normalized counter, if the determination is true.

3. The method of claim 2 wherein the scalarizing step further comprises the steps of:

scalarizing a surrounding expression of the current expression node using the associated normalized counter as an index variable;

incrementing the associated normalized counter;

scalarizing the portion of the expression tree rooted at a current expression tree node using an ac-value of an array constructor located at a top level of the expression tree; and

attaching the scalarized portion to the scalarized surrounding expression.

4. The method of claim 3 wherein the scalarizing portion step further comprises the steps of:

if the ac-value is an implied-do, creating a loop with bounds from the implied-do and scalarizing the ac-value;

if the ac-value contains an array constructor, creating another normalized counter and scalarizing the ac-value;

scalarizing the ac-value if the ac-value is a scalar expression; and

creating a loop nest with depth equal to a rank of the ac-value and with bounds from extents of the ac-value, and scalarizing the ac-value using loop index variables based on the depth and the bounds, if the ac-value is an array expression.

5. A computer system for translating an expression containing one or more array constructors nested in one or more array constructor levels in a source program, said computer system comprising:

a searcher for searching a plurality of nodes of an expression tree of the expression for each of the array constructors;

an associator for associating a normalized counter with each of the array constructor levels;

a scalarizer for scalarizing the array constructors nested in an array constructor level by use of the normalized counter associated with the array constructor level;

an extent structure tree builder for building an extent structure tree of a portion of the expression tree rooted at a current expression tree node if the current expression tree node is an array constructor; and

a splitter for splitting the current expression tree node if the current expression tree node is a non-elemental operator.

6. The computer system of claim 5 wherein the building means further comprises:

a comparator for determining if the current expression tree node has a non-elemental operator ancestor and no other array constructor in between, or if the extent structure tree rooted at the current expression tree node is not identical to a prior extent structure tree built at the array constructor level of the current expression tree node; and

an expression splitter for splitting the current expression tree node, an associator for associating the normalized counter with the array constructor, and a scalarizer for scalarizing the portion of the expression tree rooted at the current expression tree node using the associated normalized counter, if the determination is true.

7. The computer system of claim 6 wherein the scalarizer further comprises:

a scalarizer for scalarizing a surrounding expression of the current expression node using the associated normalized counter as an index variable;

an incrementer for incrementing the associated normalized counter;

a scalarizer for scalarizing the portion of the expression tree rooted at a current expression tree node using an ac-value of an array constructor located at a top level of the expression tree; and

an associator for attaching the scalarized portion to the scalarized surrounding expression.

8. The computer system of claim 7 wherein the scalarizer for scalarizing the portion further comprises:

a loop scalarizer for creating a loop with bounds from the implied-do and scalarizing the ac-value if the ac-value is an implied-do;

a counter creator for creating another normalized counter and a scalarizer for scalarizing the ac-value if the ac-value contains an array constructor;

a scalarizer for scalarizing the ac-value if the ac-value is a scalar expression; and

a loop scalarizer for creating a loop nest with depth equal to a rank of the ac-value and with bounds from extents of the ac-value, and scalarizing the ac-value using loop index variables based on the depth and the bounds, if the ac-value is an array expression.

9. An article of manufacture for use in a computer system for translating an expression containing one or more array constructors nested in one or more array constructor levels in a source program, 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:

search a plurality of nodes of an expression tree of the expression for each of the array constructors;

associate a normalized counter with each of the array constructor levels;

scalarize the array constructors nested in an array constructor level by use of the normalized counter associated with the array constructor level;

build an extent structure tree of a portion of the expression tree rooted at a current expression tree node if the current expression tree node is an array constructor; and

split the current expression tree node if the current expression tree node is a non-elemental operator.

10. The article of manufacture of claim 9, wherein said computer program, in causing the computer system to build the extent structure tree of the portion of the expression tree, may further cause the computer system to:

determine if the current expression tree node has a non-elemental operator ancestor and no other array constructor in between, or if the extent structure tree rooted at the current expression tree node is not identical to a prior extent structure tree built at the array constructor level of the current expression tree node; and

split the current expression tree node, associating the normalized counter with the array constructor, and scalarize the portion of the expression tree rooted at the current expression tree node using the associated normalized counter, if the determination is true.

11. The article of manufacture of claim 10, wherein said computer program in causing the computer system to scalarize the portion of the expression tree rooted at the current expression tree node, may further cause the computer system to:

scalarize a surrounding expression of the current expression node using the associated normalized counter as an index variable;

increment the associated normalized counter;

scalarize the portion of the expression tree rooted at a current expression tree node using an ac-value of an array constructor located at a top level of the expression tree; and

attach the scalarized portion to the scalarized surrounding expression.

12. The article of manufacture of claim 11, wherein said computer program in causing the computer system to scalarize the portion of the expression tree rooted at the current expression tree node, may further cause the computer system to:

if the ac-value is an implied-do, create a loop with bounds from the implied-do and scalarize the ac-value;

if the ac-value contains an array constructor, create another normalized counter and scalarize the ac-value;

scalarize the ac-value if the ac-value is a scalar expression; and

create a loop nest with depth equal to a rank of the ac-value and with bounds from extents of the ac-value, and scalarize the ac-value using loop index variables based on the depth and the bounds, if the ac-value is an array expression.

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

This invention relates generally to optimizing compilers for development of computer programs for use on a computer, and more particularly to generating efficient code for array constructors.

2. Description of the Related Art

Recently, the X3J3 subcommittee of the American and National Standards Institute (ANSI), in collaboration with a corresponding International Standards Organization (ISO) group ISO/IEC JTC1/SC22/WG5, approved a new standard for the Fortran programming language. This new Fortran programming language standard is generally denominated the "Fortran 90" language standard and is also in the art denominated the "Fortran 90 Array" language standard. While maintaining compatibility with and providing support for the previous "FORTRAN 77" language standard, this new Fortran 90 Array language standard defines many new programming constructs and functions.

Among these new features are the "array language" protocols. Fortran programs in the Fortran 90 language may specify operations to be performed on entire arrays or on specific sections of arrays. To facilitate the construction of these arrays and these new array operations, the Fortran 90 standard defines a new class of array functions denominated "array constructors". The Fortran 90 standard is promulgated by the ISO as the International Fortran Standard specification number ISO/IEC 1539:1991 and is promulgated by the ANSI as specification number ANSI X3.198-199x.

The new features promulgated in the Fortran 90 language standard create new challenges for existing Fortran compiler and preprocessor technology. The existing FORTRAN 77 compilers do not address the array constructor functions and must be completely rewritten and restructured to accommodate the Fortran 90 standard. The new problems created by Fortran 90 array constructors can be appreciated with reference to the FORTRAN compiler art.

FIG. 1 illustrates a procedure for translating a FORTRAN program 10 to create an executable binary object program 12. A lexical/syntax analysis 14 is conducted to transform source program 10 to a first intermediate language program 16. First intermediate language program 16 is then processed by an optimization routine 18 to create a second intermediate language program 20, which is then directly interpreted by the code generation routine 22 to create object program 12.

Lexical/syntax analysis routine 14 and code generation routine 22 are easily defined in terms of the Fortran 90 specification and the machine binary code set, respectively. Thus, it is optimization routine 18 that is primarily affected by the new Fortran 90 standard. Optimization routine 18 is illustrated in FIG. 2 as it is understood in the art. Optimization processing is achieved by first performing a control flow analysis in routine 24 of first intermediate language 16. Control flow analysis routine 24 provides the control flow data 26, which are then passed to a data-flow analysis routine 28 wherein first intermediate language program 16 is analyzed for data flow. Data-flow analysis routine 28 produces the data-flow data 30. Finally, a program transformation procedure 32 accepts control flow data 26, data-flow data 30, and first intermediate language program 16 to produce second intermediate language program 20.

Many methods for constructing arrays are known in the art. For instance, in U.S. Pat. No. 5,200,915, Ken Hayami et al. disclose a device for solving a symmetric linear system that is capable of carrying out vector processing at a high speed. Hayami et al. teach the use of an array construction section 11 which uses a temporary workspace array IL to construct a pointer array JL in a set of nested DO-loops. The objects of this device are high speed and a smaller memory area. Hayami et al. suggest the use of such temporary arrays provides high speed and a smaller memory area.

Similarly, Albert et al. (Eugene Albert, Joan D. Lukas, and Guy L. Steele, Jr., "Data Parallel Computers and the FORALL Statement", Journal of Parallel and Distributed Computing, vol. 13, no. 2, October 1991, p. 185-192) disclose compiling methods for Fortran 90 array constructors and FORALL statements. The FORALL statement is an element array assignment statement used to specify an array assignment in terms of individual elements or sections. Albert et al. teach that a FORALL statement is semantically equivalent to a pair of nested DO loops wherein the first DO loop evaluates the right hand side of the FORALL into a temporary array, and wherein the second DO loop assigns the temporary array to the left hand side of the FORALL. Although Albert et al. teach that the temporary array is not needed when there are no order dependencies, Albert et al. suggests that the temporary array is needed when there are order dependencies.

Choudhary et al. (Alok Choudhary, Geoffrey Fox, and Seema Hiranandani, "Unified Compilation of Fortran 77D and 90D", ACM Letters on Programmning Languages and Systems, vol. 2, no. 1-4, March-December, 1993, p. 95-114) also disclose compiling methods for Fortran 90 array constructors, FORALL statements, and WHERE statements. Choudhary et al. also teach assigning the results of right hand side evaluations to temporary arrays before storing the results to left hand sides. Choudhary et al. recognize that the use of such temporary arrays is a problem, and suggest loop reversal and data prefetching as partial solutions for some, but not all, situations.

Similarly, Gao et al. (Guang R. Gao, Robert Kim Yates, Jack B. Dennis, and Lenore M. R. Mullin, "A Strict Monolithic Array Constructor", Proceeding of the Second IEEE Symposium on Parallel and Distributed Processing, p. 596-603, 1990.) recognize that the use of such temporary arrays is a problem. Gao et al. suggest extending the semantics of an array constructor statement to allow a programmer to specify an evaluation order of the array constructor. If the programmer knows an evaluation order which does not need temporary arrays, then the programmer may avoid the use of temporary arrays. However, if the programmer does not know such an evaluation order, then temporary arrays may be used. This suggested partial solution effectively moves the program optimization from the compiler to the mind of the programmer.

Thus, practitioners in the art generally employ temporary arrays during the construction of arrays. Despite extensive effort in the compiler art related to array construction and optimization, the array constructor functions introduced by the new Fortran 90 standard bring with them new inefficiencies in storage and processing and there is an accordingly clearly-felt need in the art for more efficient compiling procedures suitable for application to these new Fortran 90 array constructor functions.

This problem can be better understood by considering an example. The Fortran 90 standard specification defines an array constructor (ac) as a sequence of specified scalar values and is interpreted as a rank-one array whose element values are those specified in the sequence. An array constructor has the following syntax:

    ______________________________________
    array-constructor:
                 (/ac-value-list/)
    ac-value-list:
                 ac-value-list, ac-value
    ac-value:     expr or ac-implied-do
    ac-implied-do:
                 (ac-value-list, ac-implied-do-control)
    ac-implied-do-control:
                 ac-do-variable = scalar-int-expr, scalar-int-expr
                  {, scalar-int-expr}
    ac-do-variable:
                 scalar-int-variable
    ______________________________________

                  TABLE A
    ______________________________________
    a(2:12:2) = d(1:16:3)+(/20.0,c(2:8:3)+(/0.0,b(3:4)/),(10.0*i,i=2,3)/)
    ______________________________________

                  TABLE B
    ______________________________________
    a = ›20.0+d(1) c(2)+d(4) b(3)+c(5)+d(7) b(4)+c(8)+d(10) 20.0+d(13)
    30.0+d(16)!
    ______________________________________

                  TABLE C
    ______________________________________
    j1 = 1
    r1(j1) = 0.0
    do i1 = 1,2
     j1 = j1 + 1
     r1(j1) = b(il+2)
    enddo
    j2 = 0
    do i = 2,3
     j2 = j2 + 1
     r2(j2) = 10.0 * i
    enddo
    j3 = 1
    r3(j3) = 20.0
    do i3 = 1,3
     j3 = j3 + 1
     r3(j3) = c(3*i3-1) + r1(i3)
    enddo
    do i3 = 1,3
     j3 = j3 + 1
     r3(j3) = r2(i3)
    enddo
    do i4 = 1,6
     a(2*i4) = d(3*i4-2) + r3(i4)
    enddo
    ______________________________________

                  TABLE D
    ______________________________________
    j2 = 0
    j2 = j2 + 1
    r1(j2) = 0.0
    do i2 = 1,2
     j2 = j2 + 1
     r1(j2) = b(i2+2)
    enddo
    j3 = 0
    j3 = j3 + 1
    r2(j3) = 20.0
    do i3 = 1,2
     j3 = j3 + 1
     r2(j3) = c(2) + r1(1)
    enddo
    do i = 2,3
     j3 = j3 + 1
     r2(j3) = 10.0*i;
    enddo
    do j1 = 1, 6
     a(j1*2) = d(j1*3-2) + r2(j1)
    end do
    ______________________________________

                  TABLE E
    ______________________________________
    nc1 = 1
    a(2*ncl) = d(3*ncl-2) + 20.0
    ncl = nc1+1
    nc2 = 1
    a(2*nc1) = d(3*nc1-2) + c(3*nc2-1) + 0.0
    do j = 1,2
     nc1 = nc1+1
     nc2 = nc2 + 1
     a(2*nc1=d(3*nc1-2)+c(3*nc2-1)+b(j+2)
    enddo
    do I = 2,3
     nc1 = nc1+1
     a(2*nc1) = d(3*nc1-2) + 10.0*I
    enddo
    ______________________________________

                  TABLE F
    ______________________________________
    / .backslash.
    1 2
    ______________________________________

                  TABLE G
    ______________________________________
    / .backslash.
    2 1
    ______________________________________

                  TABLE H
    ______________________________________
    Pseudo Code to Prune a Parse Tree
    ______________________________________
    TreePruning(expr ExprTree)
     Get a node T from ExprTree based on a post order until all nodes are
     visited {
     if(T = AC) {
      T.sub.-- EST = BuildEST(expr rooted at T);
      if(T has an ancestor of non-elemental operator and-no other AC in
      between, or T.sub.-- EST not identical to the current EST (if any) at
    this AC
      level) {
      Split T and create a temporary vector, TempV;
      Create a normalized counter NC1 and generate code for an
      initialization;
      ScalarizedExpr = ScalarizeAC(TempV = expr rooted at T, NC1);
      Generate code for ScalarizedExpr;
      } endif
     }
     else {
     if(T = non-elemental operator)
      Split T;
     } endif
     } enddo
     if(ExprTree contains AC)
     Create a normalized counter NC1 and generate code for an
    initialization;
     ScalarizeExpr = ScalarizeAC(ExprTree, NC1);
     Generate code for ScalarizedExpr;
    }
    ______________________________________


              TABLE I
    ______________________________________
    Pseudo code to Construct an Extent Structure Tree
    ______________________________________
    ExtentStructureTree BuildEST(expr ExprTree)
     ExtentStructureTree EST=NULL;
     if(ExprTree = implied-do) {
     return EST = *
          / .backslash.
      extent of implied-do  BuildEST(ac-value-list of implied-do)
     }
     else
     if(ExprTree contains no AC) {
     if(Rank(ExprTree) = 0)
      return(EST = 1);
     else /* Rank(ExprTree) = n>0 */
      return EST = *
          / .backslash.
      extent of dim(1) *
          / .backslash.
           :
           *
            / .backslash.
      extent of dim(n-1)  *extent ofdim(n)
     } endif
     } endif
     For every immediate AC in ExprTree do {
     For every AC.sub.-- VALUE in AC do {
      sub.sub.-- EST = BuildEST(expr rooted at AC.sub.-- VALUE);
      if(EST |= NULL)
       EST = +
          / .backslash.
        EST  sub.sub.-- EST
      else
       EST = sub.sub.-- EST
      } endif
     } enddo
     } enddo
    }
    ______________________________________


              TABLE J
    ______________________________________
    Pseudo Code to Scalarize Array Constructors
    expr ScalarizeAC(expr ExprTree, NormCounter NCx)
     S.sub.-- Expr = surrounding expr of ExprTree;
     Scalarize S.sub.-- Expr using NCx as the index variable;
     Generate NCx = NCx + 1 to update the normalized counter;
     Find AC.sub.-- VALUE.sub.-- SET in all of ACs at top level of ExprTree
    to obtain
     current elements;
     if(AC.sub.-- VALUE.sub.-- SET = implied-do) {
     Create a loop with the bounds from the implied-do;
     ScalarizedExpr.sub.-- SET = ScalarizeAC(ac-value-list's of
     AC.sub.-- VALUE.sub.-- SET, NCx);
     }
     else
     if(AC.sub.-- VALUE.sub..sub.-- SET contains AC) {
     Create a normalized counter NCy and generate code for an
    initialization;
     ScalarizedExpr.sub.-- SET = ScalarizeAC(AC.sub.-- VALUE.sub.-- SET,
    NCy);
     }
     else
     if(AC.sub.-- VALUE.sub.-- SET = scalar expr) {
     ScalarizedExpr.sub.-- SET = AC.sub.-- VALUE.sub.-- SET;
     }
     else /* AC.sub.-- VALUE.sub.-- SET = array expr */ {
     Create a loop nest with depth equal to rank(AC.sub.-- VALUE.sub.-- SET)
    &
     bounds from extents of AC.sub.-- VALUE.sub.-- SET;
     ScalarizeExpr.sub.-- SET = AC.sub.-- VALUE.sub.-- SET scalarized using
    the
     loop index variables;
     } endif
     Attach ScalarizedExpr.sub.-- SET to S.sub.-- Expr;
     return S.sub.-- Expr;
    }
    ______________________________________

                  TABLE K
    ______________________________________
    a(2) = d(1) + 20.0
    a(4) = d(4) + c(2) + 0.0
    nc2 = 1
    nc1 = 2
    do j = 1,2
     nc1 = nc1+1
     nc2 = nc2+1
     a(2*nc1)=d(3*nc1-2)+c(3*nc2-1)+b(j+2)
    enddo
    do i = 2,3
     nc1 = nc1+1
     a(2*nc1) = d(3*nc1-2) + 10.0*i
    enddo
    ______________________________________

                  TABLE L
    ______________________________________
    real a(80002),b(50000),c(50005),d(80002)
    do k = 1,20
     a(1:80002) =
      d(1:80002)+(/20.0,c(1:50001)+(/0.0,b(1:50000)/),(10.0*i,i=1,30000)/)
    enddo
    end
    ______________________________________

                  TABLE M
    ______________________________________
                       Execution
    Compiler used      time (in user CPU seconds)
    ______________________________________
    IBM XLF compiler with VAST-2
                       0.32
    preprocessor
    Compiler using present invention
                       0.20
    ______________________________________

• Inventors
  Ju, Dz Ching; Ng, John Shek-Luen;
• Assignee
  International Business Machines Corporation (Armonk, NY)
• Published
  Dec-1-1998
• Current US Classes:
  717/114
  717/144
  717/149
  717/160
• Application #
  570173
• International Classes
  G06F 009/45
• Field of Search
  395/705 395/706 395/707 395/708
• Examiner
  Trammell; James P.
• Agent
  Johnson; Prentiss W.
• US Patent References:
  5175856
  5200915
  5274818
  5276881
  5280613
  5339419
  5375242
  5485619
  5640568