Method and apparatus for compiling source code by flattening hierarchies

Abstract

A method and apparatus for optimizing the compilation of computer program by exposing parallelism are disclosed. The computer program contains steps which involve index expressions. The program also involves function calls. An index path in the program is identified by noting the steps involving index expressions. A non-hierarchical representation of the index path, including operations in the function calls is created and interrogated with questions relating to memory accesses. The results of the interrogation are stored in or back annotated to a question data structure. The method and apparatus preferably involve the use of a signal flow graph which is completed using the information in the question data structure.

Claims

We claim:

1. A method of optimizing compilation of a computer program, the program comprising operations involving one or more index expressions, the method comprising the steps of:

identifying an index path by noting the operations involving one or more index expressions;

creating a non-hierarchical representation of the index path;

examining memory accesses in the non-hierarchical representation of the index path to identify program steps that could be executed in parallel.

2. The method of claim 1 wherein the program comprises one or more function calls and wherein the step of identifying an index path comprises the step of noting operations in the function calls and wherein the non-hierarchical representation of the index path comprises information relating to operations in the function calls.

3. The method of claim 2 further comprising the step of merging the information relating to operations in the function calls back into a hierarchical representation of the index path.

4. The method of claim 1 wherein the step of examining memory accesses comprises the step of creating a data structure of the non-hierarchical representation, interrogating the data structure with questions relating to memory accesses and storing results of the step of interrogating in a question data structure.

5. The method of claim 2 further comprising the steps of storing the questions relating to memory accesses in a question data structure and wherein the step of storing the results comprises back-annotating the question data structure.

6. An apparatus for compiling computer code, the computer code comprising function calls having a hierarchy, the apparatus comprising:

first signal flow analysis means for creating a signal flow data structure for index expression s used by the computer code, wherein the first signal flow analysis means comprises:

means for identifying steps in an index path in the computer code, the index path identifying parts of memory accessed by index expressions;

means for removing the hierarchy from the computer code, thereby creating a non-hierarchical representation of the computer code.

7. A method of optimizing compilation of a computer program, the program comprising one or more function calls, operations involving one or more scalars and operations involving one or more index expressions, the method comprising the steps of:

determining an index path by flagging the operations involving index expressions;

creating a non-hierarchical representation of the index path;

generating questions relating to memory accesses by the computer program;

creating a symbolic execution data structure comprising information relating to memory accesses by operations involving index expressions;

executing the symbolic execution data structure, thereby identifying steps in the program which could be executed in parallel.

8. The method of claim 7 further comprising obtaining answers to the questions relating to memory accesses and using the answers to identify parts of the computer program that can be executed in parallel.

Description

BACKGROUND

The present invention relates to the field of computer software engineering. More specifically, it relates to a method and apparatus for compiling source code by exposing parallelism, thereby enabling the generation of more efficient compiled code, allowing more parallel instructions to be created and leading to better utilization of processor resources.

Compiling a computer program involves converting a high level language code (source code) into instructions which are intelligible to the processor of a computer (object code). One of the goals of a compiler is to generate an efficient implementation of the source code. In the case of processors which can execute more than one instruction in parallel, it is an objective of the compiler to compile the code such that as many instructions as possible can be executed in parallel.

It is an object of the invention to provide a method and apparatus for efficiently compiling code by exposing parallelism in that code. The present invention is applicable to any computer architecture having multiple functional units, for example, Very Long Instruction Word ("VLIW") architectures for implementing real-time implementations of Digital Signal Processing ("DSP") applications.

It is a further and more specific object of the invention to determine and represent dependencies for each of the memory accesses in a source program. This exposes the execution paths in the program so that the compiler can exploit the parallelism to the maximum extent. In the case of VLIW architectures, the failure to detect parallelism accurately can lead to fewer instructions being packed into a VLIW instruction word and hence the processor performing below its capabilities.

Index expressions present special problems for compilers. Consider the following piece of pseudo-code:

1 void f(

2 double A[4]

3 )

4 {

5 double a=A[0];

6 double b=A[1];

7 double c=a+b;

8 A[0]=c;

9

10 double d=A[2];

11 double e=A[3]

12 double f=d-e;

13 A[2]=f;

14 }

The block code starting with "double a=A[0]" can be executed in parallel with the code starting with "double d=A[2]" since they do not access the same memory locations in array A.

Now consider the following example of more complex parallelism:

1 double f(

2 double in

3 )

4 {

5 double A[16];

6 A[0]=in;

7 for (int i=0; i<16; i++) {

8 A[i+1]=A[i]*2.0

9 }

10 return A[15];

}

The indices for array A are now linear index expressions of the loop iterators (the linear expressions are i, i+1 and loop iterator i). The term "linear" as applied to an index expression means that the index expression is the result of a combination of a constant times the iterator plus a constant. This information can be used to determine if multiple iterations of a loop can be run in parallel--referred to as "array privatization." In this example, the compiler can tell that the array value is produced in the previous iteration. It therefore cannot postpone the write operation until after the read of the next iteration.

Now consider the following example involving an induction variable (which is behaviorally equivalent to the previous example):

1 double f(

2 double in

3 )

4 {

5 double A[16];

6 A[0]=in;

7 int idx1=1;

8 int idx2=0;

9 for (int i=0; i<16; i++) {

10 A[idx1]=A[idx2]*2.0;

11 idx1=idx1+1;

12 idx2=idx2+1;

13 }

14 return A[15];

15

In this expression, a variable is initialized before a loop. The value used and updated inside the loop is called an induction variable. In some cases the induction variable can be converted into a linear index expression and the parallelism in the code thus exposed. This is the case here because the code is completely equivalent to that of the previous example.

Known methods of compiler optimization only consider linear index expressions--assuming a worst case of non-parallelism for non-linear expressions. Induction variables are handled by transformation into linear index expressions. Most systems of the prior art use heuristic approaches to obtain memory access information from such expressions. Prior art algorithms formulate the linear index expressions and a specific data flow analysis question as the proof of the existence of a solution of an Integer Linear Programming problem. Another known method for simplifying the Integer Linear Programming problem is Fourier-Motzkin variable elimination, which reduces the number of dimensions of the problem.

One benefit of the present invention is the ability to perform inter-procedural data flow analysis over multiple function calls. In the prior art, this was done by combining the results of intra- and inter-procedural data flow analysis in a post-processing step. In contrast, the present invention performs operations which flatten the hierarchy of function calls in order to determine data dependencies for memory accesses. Here, the flattening operation is performed prior to the analysis stage.

These and other advantages of the invention will be apparent from the following description and claims.

SUMMARY OF THE INVENTION

The present invention relates to a method of optimizing the compilation of a computer program. The method includes the steps of identifying an index path by noting the operations of the program which involve one or more index expressions. A non-hierarchical representation of the index path is created. The memory accesses in the non-hierarchical representation of the index path are examined to identify program steps that could be executed in parallel.

Where the program includes function calls, the step of identifying an index path involves noting operations in the function calls, and the non-hierarchical representation of the index path includes information relating to operations in the function calls.

In a further embodiment of the invention, the method includes the steps of merging the information relating to operations in the function calls back into a hierarchical representation of the index path.

In yet a further embodiment, a data structure of the non-hierarchical representation is created and interrogated with questions relating to memory accesses. The results are stored in or back annotated to a question data structure.

The invention also encompasses an apparatus for compiling computer code including a module which creates a signal flow data structure for index expressions used by the computer code. That module includes a means for identifying steps in the index path of the computer code, identifying parts of memory accessed by index expressions. A module removes the hierarchy from the computer code, creating a non-hierarchical representation of the computer code.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a flowchart showing the basic method of the invention;

FIG. 2 is a block diagram showing the basic components of the invention and the interactions between them;

FIG. 3 is a signal flow graph ("SFG") of nodes representing the operations in the pseudo code example in the Detailed Description;

FIG. 4 is a function call graph for an example in the Detailed Description;

FIG. 5 is a signal flow graph showing the routing of data and sequence edges for scalar variables in the example in the Detailed Description;

FIG. 6 is a signal flow graph for the example in the Detailed Description, showing the marking of the index path of the program;

FIG. 7 is an example of a DFA Problem Graph as used in the present invention;

FIG. 8 is the DFA Problem Graph for the example in the Detailed Description;

FIG. 9 is a snapshot of DFA questions for one function call in the example in the Detailed Description;

FIGS. 10-15 are graphical representations showing a set of DFA questions in the context of the DFA Problem Graph shown in FIG. 8, the DFA Question database and the symbolic execution data structure in the example in the Detailed Description;

FIG. 16 is the resulting signal flow graph for the example in the Detailed Description, routed with data and sequence edges, and as used to expose parallelism.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

The following is a detailed description of the preferred embodiment, which will enable a person of ordinary skill in the art to make and use the invention. The description is intended to be illustrative rather than limiting of the invention, the full scope of which is to be determined by reference to the appended claims and their equivalents. Persons of ordinary skill in the art will recognize that a wide range of alternative embodiments of the invention is encompassed by the invention.

The invention provides a method and apparatus for efficient compilation of a source code program for use in a computer architecture which produces an efficient compiled code, allowing operations to be executed in parallel, for example in a Very Long Instruction Word ("VLIW") architecture. The aim of the invention is to produce a signal flow graph ("SFG") which exposes as much parallelism in the input source code as possible. An SFG is a data structure representing an algorithm and used to assist in the compilation of code. The SFG is a commonly used and convenient way of representing dependencies in a program by means of data edges (which route data between operations) and sequence edges (which impose order relations between operations) through a program. An example of the use of an SFG data structure is described in DSP Station SFG Concepts and Procedural Interface (Software Version 8.6.1) produced by Frontier Design, b.v.b.a. of Leuven, Belgium. It will be recognized by those of ordinary skill in the art that, the same results can be achieved by othermeans such as alternative representations of data and sequence information. It is intended that the term SFG imply any such representation.

The following description assumes source code comprising operations involving scalar and array variables as well as an index path made up of operations that are involved in the computation of indices of memory operation. The basic steps in the data flow analysis are shown in FIG. 1 and are summarized as follows:

1. Extract the program operations and the information about the sequence of those operations from the source code (S1).

2. Route the control and data edges between operations for scalar variables (S2). Accessing a scalar variable (i.e. reading or writing) consumes (read) or produces (write) the entire variable. Classic data flow analysis can handle this situation. However, classic data flow analysis does not assist in optimization where arrays are concerned, particularly in cases involving non-linear indices.

3. Flag all operations in the index path (S3).

4. Generate "expansion contexts" (S4). If a function has a function call which has been flagged in step 2, then a data structure is generated which enables subsequent stages of the algorithm to "see" that function's operations as if the operations in the function were "inlined" in the calling function's context.

5. Construct the DFA Problem Graph (S5). This removes and flattens the hierarchies in the index path, for example, due to function calls involving index variables. The DFA Problem Graph has nodes which relate to memory accesses and operations in the index path.

6. Create a set of questions relating to memory access ("DFA questions") which can be posed by the data and sequence flow router in a subsequent phase (S6). The questions are generated for relevant triplets of loop, memory access 1 and memory access 2. These questions are stored in a DFA question database.

7. Create a symbolic execution data structure (S7). This contains data structures necessary to accumulate or hold information about all memory accesses.

8. Perform a symbolic execution of the source code (S8).

9. Back annotate the data produced by the symbolic execution to the DFA question data base (S9). In the case of expanded function calls, this stage merges the symbolic execution data generated by all the function invocations.

10. Route the control and data edges between operations for array variables using the answers to the DFA questions (S10).

These steps will now be described in detail with particular reference to FIG. 2 and to the following pseudo code which serves as an example to aid in the description of the invention.

1 #define N 10

2

3 void fibonacci(

4 int fibo[N]

5 )

6 {

7 #pragma OUT(fibo)

8 int i;

9 fibo[0]=1;

10 fibo[1]=1;

11 for (i=2; i<N; i++) {

12 // the feedbackset with looping degree GT one for fibo[i] to fibo[i-1]

13 // with respect to loop i is empty, for fibo[i-2] it's not empty and

14 // this causes a feedthrough edge

15 is fibo[i]=fibo[i-1]+fibo[i-2];

16 }

17 }

18

The following description will make reference to this code and to the representations of data structures which relate to the code. FIGS. 5, 6 and 8-16 provide graphical representations of the analysis of the above code using the invention in a manner which will be well understood by persons of ordinary skill in the art.

Front end 2 receives the source code 10 as an input, performs lexical analysis by means of parser 12 and produces an intermediate level language representation of the source code in the form of annotated syntax tree 14.

Annotated syntax tree 14 is input to Signal Flow Graph Generator 4. Signal Flow Graph Generator 4 first checks the source code to determine if it is capable of synthesis. If so, it traverses the syntax tree (S1 and S2 in FIG. 1) to produce the SFG data structure.

SFG generator 4 produces the following outputs: Bare SFG 16, Sequence Information 18 and Call Graph 20. Bare SFG 16 is an SFG which represents all the operations in source code 10, but does not include any data or sequence edges linking the operations. The bare SFG thus contains an unscheduled set of operations. An example of a bare SFG can be found in FIG. 3.

Sequence information 18 is a list which contains information about the lexical order and exclusivity of the different operations in the bare SFG. The exclusivity is derived from conditional statements in the source code. In a language such as C, these are the if-then-else statements, case statements and ? operators. The following is the sequence information for the above mentioned pseudo code example and of bare SFG shown in FIG. 3:

                                             Re-
    VAR   TYPE        Operation:Port         mark  Source
    t1    OutputPort  Sfg_constantOp(1):out0       1
          InputPort   Sfg_storeOp(5):in0     data  fibo[0] = 1
    t2    OutputPort  Sfg_constantOp(2):out0       0
          InputPort   Sfg_storeOp(5):in1     index [0]
    t3    OutputPort  Sfg_constantOp(3):out0       1
          InputPort   Sfg_storeOp(6):in0     data  fibo[1] = 1
    t4    OutputPort  Sfg_constantOp(4):out0       1
          InputPort   Sfg_storeOp(6):in1     index [1]
    t5    OutputPort  Sfg_constantOp(7):out0       2
          InputPort   Sfg_loopOp(6):in0      low   i = 2
    t6    OutputPort  Sfg_constantOp(8):out0       10
          InputPort   Sfg_loopOp(9):in1      high  i < 10
    i     OutputPort  Sfg_sourceOp(10):out0        For iterator
          InputPort   Sfg_subtractOp(12):in0       argument of i-1
          InputPort   Sfg_subtractOp(14):in0       argument of i-2
          InputPort   Sfg_storeOp(18):in0    index [i]
    t7    OutputPort  Sfg_constantOp(11):out0       1
          InputPort   Sfg_subtractOp(12):in1       argument of i-1
    t8    OutputPort  Sfg_subtractOp(12):out0       i-1
          InputPort   Sfg_fetchOp(15):in1    index [i-1]
    t9    OutputPort  Sfg_fetchOp(15):out0         fibo[i-1]
          InputPort   Sfg_addOp(15):in0            fibo[i-1] + . . .
    t10   OutputPort  Sfg_constantOp(13):out0       2
          InputPort   Sfg_subtractOp(14):in1       argument of i-2
    t11   OutputPort  Sfg_subtractOp(14):out0       i-2
          InputPort   Sfg_fetchOp(16):in1    index [i-2]
    t12   OutputPort  Sfg_fetchOp(16):out0         fibo[i-2]
          InputPort   Sfg_addOp(16):in1            .. + fibo[i-2]
    t13   OutputPort  Sfg_addOp(17):out0           fibo[i-1] +
                                                   fibo[i-2]
          InputPort   Sfg_storeOp(18):in0    data  fibo[i] = . . .
    fibo  Store       Sfg_storeOp(5):out0          fibo[0]
          Store       Sfg_storeOp(6):out0          fibo[1]
          Fetch       Sfg_fetchOp(15):out0         fibo[i-1]
          Fetch       Sfg_fetchOp(16):out0         fibo[i-2]
          Store       Sfg_storeOp(18):out0         fibo[i]
          InputPort   Sfg_sinkOp(18):in0           output of
                                                   fibonacci

• Inventors
  Guffens, Jan; Du Pont, Kurt;
• Assignee
  Adelante Technologies, NV (Leuven, BE)
• Published
  Mar-25-2003
• Current US Classes:
  717/151
  717/159
  717/160
  717/161
• Application #
  450329
• International Classes
  G06F 009/45
• Field of Search
  717/151-161 717/140-144 717/150
• Examiner
  Morse; Gregory
• Agent
  Michael Schwarz & Associates P.C.
• US Patent References:
  5437034
  5491823
  5537620
  5842022
  6101488
  6148439
  6351845
  6374403
  6393423
  6438747