Method of compiling a loop

Details Method of compiling a loop Method of compiling a loop

1994-04-08

2001-01-09

Lim, Krisna (Department: 2758)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000

Reexamination Certificate

active

06173443

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to a computer implemented method of compiling computer program loops containing calculations dealing with data arrays.
Prior art methods of compiling computer programs will be explained using program examples. A variety of compiling methods are well known in the prior art. For example A. Aho and J. Ullman, Principles of Compiler Design, Addison-Wesley Pub. Co., pp. 557-60, discloses a FORTRAN H compiler and a C compiler. Both illustrate the basic structural features of a compiler including lexical and syntactic analysis, code generation and optimization.
FIG. 17
is the FORTRAN coding for program example 1,
FIG. 18
is the FORTRAN coding for program example 2,
FIG. 19
is the dummy object coding for program example 1, and,
FIG. 20
is the dummy object coding for program example 2. Such dummy object coding is well known in the prior art. For example, W. Barrett and J. Couch, Compiler Construction Theory and Practice, Science Research Assocs., Inc. pp 563-69, illustrates the use of dummy object code to describe to others in the art their algorithms. See also U.S. Pat. No. 4,719,867, Watanabe.
The programming sequences shown in
FIGS. 19 and 20
each being with an Initial Loop Setting instruction, namely:
LOOP ENTRY x=y, z, w
In this instruction, the index is x, the initial value is y, the final value is z and the increment is w.
A Loading Register instruction is also included, namely:
LOAD #x, reg y
In this instruction, the memory content of location x is loaded into register y.
A first Addition instruction:
ADD reg x, reg y, reg z
performs the following operation:
reg z=reg x+reg y.
while a second Addition instruction:
Add reg x, #y, reg z
performs the following operation:
reg z=reg x+#y.
A Storing Register instruction:
STORE reg x, #y
results in the contents of register x being stored in memory y.
An Inter-Register Move instruction:
MOVE reg x, reg y
results in the contents of register x being copied into register y.
In a Post Processing instruction:
LOOP_RETURN x=x+y, z
the value of X is added to the value of Y and program execution skips to z. An appropriate value of X results in an exiting of the loop.
If the exemplary computer program which is shown in
FIG. 17
(Program example 1) is compiled by well known prior art methods, the result is as in FIG.
19
. As shown, loop execution is initialized. Next, at the start of the loop body, B(I−1) and B(I) are loaded and added, then B(I+1) is also added. Finally, the result is stored in A(I) and loop return is executed. If the exemplary computer program which is shown in
FIG. 18
(Program example 2) is compiled by well known prior art methods, the result is as in FIG.
20
. As shown, loop execution is initialized. Then, at the start of the loop body, A(I−1) is loaded and added to instant value 1. The result is stored in A(I). Then A(I+1) is also loaded and added to instant value 2. Finally, the result is stored in A(I−1) and loop return is executed.
As related above, in accordance with prior art methods, the same data is loaded and stored a plurality of times when the index values are different. For example, in the dummy coding for program example 1, the value for B(3) is loaded as B(I=1) when I=2, as B(I) when I=3, and, as B(I−1) when I=4. Furthermore, in the dummy coding for program example 2, the value for A(3) is stored as A(I) when I=3, and as A(I−1) when I=4; and loaded as A(I−1) when I=4 and as A(I+1) when I=2. Thus, in well known prior art methods of compiling, there is more accessing of memory than is necessary.
SUMMARY OF THE INVENTION
The subject invention relates to a computer implemented method of compiling a computer program. When compiling loop statements containing calculations dealing with data arrays, steps are included for finding data arrays within the program and finding locations of loops. Loops are composed of three parts consisting of loop entry (which is the pre-processing before the results of compiling the said loop statements enters the loop) the loop body (which is the repetitive calculation portion), and the loop return (which is the post-processing portion to repeat the loop). Steps are included where, of the data arrays, those with different array names and different indexes are respectively allocated to separate registers. Steps are included where, for the data arrays corresponding to arrays other than that having the highest index, the loading from memory to the registers are undertaken prior to loop entry. Steps are included where, for the data array having the highest index, the loading from memory of the corresponding said register is undertaken in the loop body. Steps within the loop body wherein the contents of the registers corresponding to the data arrays are moved to the registers corresponding to the data arrays having a different index from the data arrays. Steps are included so that when it is necessary to store the data array in memory, the data array having the smallest index within the loop body is stored in memory. Steps are also to store all other data arrays after the loop return.
Thus, the present invention relates to a method of compiling characterized by not undertaking moves to the registers but unrolling the loop by an integer multiple of the maximum difference between the indexes of the data arrays within the loop.
By utilizing the above configurated method of register allocation to change the method of register allocation, execution of loop statements including calculations of data arrays can be expedited by the number of unnecessary memory accesses which have been eliminated. Also, through the unrolling technique, register moves can be omitted.


REFERENCES:
patent: 4463423 (1984-07-01), Potash et al.
patent: 4567574 (1986-01-01), Saade et al.
patent: 4642765 (1987-02-01), Cocke et al.
patent: 4656582 (1987-04-01), Chaitin et al.
patent: 4656583 (1987-04-01), Auslander et al.
patent: 4710867 (1987-12-01), Watanabe
patent: 4763255 (1988-08-01), Hopkins et al.
patent: 4773007 (1988-09-01), Kanada et al.
patent: 4802091 (1989-01-01), Cocke et al.
patent: 4807126 (1989-02-01), Gotou et al.
patent: 4821181 (1989-04-01), Iwasawa et al.
patent: 4833606 (1989-05-01), Iwasawa et al.
patent: 4953084 (1990-08-01), Meloy et al.
patent: 4991088 (1991-02-01), Kam
patent: 5067068 (1991-11-01), Iwasawa et al.
patent: 5121498 (1992-06-01), Gilbert et al.
patent: 5146594 (1992-09-01), Iitsuka
patent: 5151991 (1992-09-01), Iwasawa et al.
patent: 5202995 (1993-04-01), O'Brien
Sowell; “Programming in Asssembly Language Macro-11” pp 70-71.
Struble; Assembler Language Programming: the IBM System/360 and 370; pp 156-184.
W. Henhapl et al., “Parallel Loop Structures”,IBM Technical Disclosure Bulletin, vol. 16, No. 4, at 1047-1049 (Sep. 1973).
R.E. Kizis, “Loopable Code Enhancement For An Ate Compiler”,IBM Technical Disclosure Bulletin, vol. 25, No. 11B, at 6085-6089 (Apr. 1983).
A.K. Chandra, “Identifying Inner Loops of Programs”,IBM Technical Disclosure Bulletin, vol. 18, No. 10 at 3514-3515 (Mar. 1976).
P.F. Carpenter et al., “Program Optimization Technique”,IBM Technical Disclosure Bulletin, vol. 12, No. 6, at 891-893 (Nov. 1969).
F.E. Allen et al., “A Catalogue of Optimizing Transformations”, IBM Thomas J. Watson Research Center, Yorktown Heights, New York.
R. Tarjan, “Depth-First Search and Linear Graph Algorithms”, vol. 1, No. 2, at 146-160 (Jun. 1972).
J. Ferrante et al., “The Program Dependence Graph And Its Use In Optimization”,IBM Technical Report RC-10543, at 1-33 (Jun. 1984).
M.S. Johnson et al., “Effectiveness of a Machine-level, Global Optimizer”,Proceedings of the SIGPLAN '86 Symposium On Compiler Construction, at 99-108 (Jun. 1986).
D.S. Coutant et al., “Compilers for the New Generation of Hewlett-Packard Computers”,Hewlett-Packard Journal, vol. 37, No. 1, at 4-18 (Jan. 1986).
A.V. Aho et al.,Principles of Compiler Design, Addison-Wesley Publishin

Affiliated with

Also associated with

Rating

Method of compiling a loop does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of compiling a loop, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of compiling a loop will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2514232