US5146594A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of producing object program based on interprocedural dataflow analysis of a source program
Assignee: Hitachi Ltd
•
Filing: 1988-11-02
•
Granted: 1992-09-08
•
Expires: 2008-11-02
Abstract
Abstract A method of producing an object program from an inputted source program with a compiler using a computer, includes the steps of: performing an interprocedural dataflow analysis of a variable associated with a procedure such as a subroutine, function, and initialization subprogram; analyzing and summarizing a procedure call effect into a variable region having a possibility of modifying the value of a variable upon a procedure call, a variable region having a possibility of using the value of a variable, and a variable region having a necessity of defining the value of a variable, in accordance with the interprocedural dataflow analysis; and representing data reference at the procedure call by using the summary information, in the dataflow analysis of a procedure part including the procedure call, performing an interprocedural dataflow analysis while discriminating between a case where there is a possibility of data reference and a case where there is a necessity of data reference, and performing an optimization process in accordance with the result of the last-mentioned interprocedural dataflow analysis.
Inventors
- 👤 Takayoshi Iitsuka
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 11:48
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/43; G06F8/433
Claims Analysis
Total Claims: 4
Claim 1
Independent Claim
607 words
A method of generating an object program from a source program which includes a plurality of procedures, at least one procedure of the procedures including at least one loop containing a procedure call for calling another procedure within the source program as a called procedure, and the object program being for executing the loop in parallel for different iterations of the loop, the method comprising the steps executed by a computer, the steps including: detecting one or plural regions of a first kind, one or plural regions of a second kind and one or plural regions of a third kind, for each of iterations of the loop with respect to each of one or more arrays each appearing in a statement of the loop except the procedure call or each appearing as an actual argument in the procedure call, each of the one or plural regions of the first kind and each of the one or plural regions of the second kind for said each appearing array for said each iteration of the loop being regions respectively defined and used on one or more program execution paths executable for said each iteration which includes one or plural program execution paths in the called procedure executable for said each iteration, and each of the one or plural regions of the third kind for the each appearing array for the each iteration being a region within the one or plural regions of the second kind which is used on one of the program execution paths for said each iteration without being defined on said one program execution path before being used; wherein said detecting step includes the step of detecting the regions of the first to third kinds for said each iteration for one of the one or more appearing arrays which appears as an actual argument in the procedure call, by regarding definition and use of a dummy argument associated with the actual argument within the called procedure, as definition and use of the one appearing array respectively; determining whether or not each of the one or more appearing arrays satisfies a first or second condition, the first condition being that any one of the one or plural regions of the first kind for the each appearing array for any iteration of the loop does not intersect with any one of the one or plural regions of the second kind for said each appearing array for any iteration of the loop, and the second condition being that nay one of the one or plural regions of the first kind for the appearing array for any iteration of the loop does not intersect with any of the one or plural regions of the third kind for said each appearing array for another iteration of the loop following an iteration of the loop for which one of the one or plural regions of the first kind has been detected; replacing, when any of the one or more appearing arrays is one of an array of a first kind which satisfies the first condition and an array group of a second kind which does not satisfy the first condition but satisfies the second condition, each of the one or more arrays which is an array of the second kind by a new array having more dimensions than the each replaced array by one added dimension, a subscript of the new array for the added dimension being a loop control variable of the loop; and, compiling the source program after replacing the replaced each of the one or more arrays into an object program including codes for executing the loop in parallel.
Claim 2
Independent Claim
607 words
A method of generating an object program from a source program which includes a plurality of procedures, at least one procedure of the procedures including at least one loop containing a procedure call for calling another procedure within the source program as a called procedure, and the object program being for executing the loop in parallel for different iterations of the loop, the method comprising the steps executed by a computer, the steps including: detecting one or plural regions of a first kind, one or plural regions of a second kind and one or plural regions of a third kind, for each of iterations of the loop with respect to each of one or more arrays each appearing in a statement of the loop except the procedure call or each appearing as an actual argument in the procedure call, each of the one or plural regions of the first kind and each of the one or plural regions of the second kind for said each appearing array for said each iteration of the loop being regions respectively defined and used on one or more program execution paths executable for said each iteration which includes one or plural program execution paths in the called procedure executable for said each iteration, and each of the one or plural regions of the third kind for the each appearing array for the each iteration being a region within the one or plural regions of the second kind which is used on one of the program execution paths for said each iteration without being defined on said one program execution path before being used; wherein said detecting step includes the step of detecting the regions of the first to third kinds for said each iteration for one of the one or more appearing arrays which appears as an actual argument in the procedure call, by regarding definition and use of a dummy argument associated with the actual argument within the called procedure, as definition and use of the one appearing array respectively; determining whether or not each of the one or more appearing arrays satisfies a first or second condition, the first condition being that any one of the one or plural regions of the first kind for the each appearing array for any iteration of the loop does not intersect with any one of the one or plural regions of the second kind for said each appearing array for any iteration of the loop, and the second condition being that nay one of the one or plural regions of the first kind for the appearing array for any iteration of the loop does not intersect with any of the one or plural regions of the third kind for said each appearing array for another iteration of the loop following an iteration of the loop for which one of the one or plural regions of the first kind has been detected; replacing, when any of the one or more appearing arrays is one of an array of a first kind which satisfies the first condition and an array group of a second kind which does not satisfy the first condition but satisfies the second condition, each of the one or more arrays which is an array of the second kind by a new array having more dimensions than the each replaced array by one added dimension, a subscript of the new array for the added dimension being a loop control variable of the loop; and, compiling the source program after replacing the replaced each of the one or more arrays into an object program including codes for executing the loop in parallel.
Claim 3
Dependent Claim
80 words
A method according to claim 1, upper and lower limits of the added dimension of the new array are defined by upper and lower limits of a loop control variable representing each iteration of the loop, upper and lower limits of dimensions of the new array except for the added dimension are same as the replaced array, and a subscript of each dimension of the new array except for the added dimension is identical to that of the replaced array.
Claim 4
Dependent Claim
97 words
A method according to claim 1, wherein further comprising the step of adding before the compiling step, when one of the one or more appearing arrays which is an array of the second kind is defined in the loop and used outside of the loop, a statement for setting data of a portion of the new array defined during execution of the loop for the last one of the iterations in a region of the first kind detected for the last iteration of the loop, for the one array which is an array of the second kind.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-09-08 | 1996-03-09 | 1996-09-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-09-08 | 2000-03-09 | 2000-09-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-09-08 | 2004-03-09 | 2004-09-08 | $7700.00 | Window Closed / Lapsed |