Patent US1153244A successfully refreshed from Google Patents.
Patent US4702743A successfully refreshed from Google Patents.
Patent US5581762A successfully refreshed from Google Patents.
US5581762A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Compiling apparatus having a function to analyze overlaps of memory addresses of two or more data expressions and a compiling method
Assignee: Fujitsu Ltd
•
Filing: 1994-02-28
•
Granted: 1996-12-03
•
Expires: 2014-02-28
Abstract
Abstract An object of the present invention is to realize a compiling apparatus producing an object program which can be executed at a high speed. In a compiling apparatus according to the present invention, an aliasing address comparison instruction generating unit inserts a instruction to compare the two memory addresses of each pair of data expressions whose overlap is judged to be obscure, generates a plurality of paths defined by combinations of conditions whether or not memory addresses of data expressions of each pair overlap, and generates a instruction to branch to one of the paths according to a comparison result obtained by the instruction in an execution of a compiled program, and an optimization unit for respectively optimizing the paths. When the object program is executed, one path corresponding to a practical condition is selected from the plurality of paths, and only the selected path is executed.
Inventors
- 👤 Masakazu Hayashi
- 👤 Tadashi Nakahira
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 15:53
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/43; G06F8/433; G06F8/434
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
234 words
A compiling apparatus comprising: a structure analysis unit for analyzing a structure of an intermediate language program of a source program output from a front-end unit, and for recognizing program units constituting loops; a data flow analysis unit for analyzing a scope of declarations of respective data expressions in the loop units recognized at the structure analysis unit; a static aliasing analysis unit for statically analyzing an overlap of two memory addresses of data expressions of each pair and for outputting an overlap analysis result of each pair which is whether the two memory addresses overlap each other, the two memory addresses do not overlap each other, or the overlap of the two memory addresses is obscure; an aliasing address comparison instruction generating unit for inserting an instruction to compare the two memory addresses of data expressions of each pair whose overlap is judged to be obscure by the static memory data analysis unit, for generating a plurality of paths defined by combinations of conditions whether or not the two memory addresses of data expressions of each pair overlap, and for generating an instruction to branch to one of the plurality of paths according to a comparison result obtained by the instruction in an execution of a compiled program compiled from the source program; and an optimization unit for respectively optimizing the plurality of paths generated by the aliasing address comparison instruction generating unit.
Claim 2
Dependent Claim
234 words
A compiling apparatus comprising: a structure analysis unit for analyzing a structure of an intermediate language program of a source program output from a front-end unit, and for recognizing program units constituting loops; a data flow analysis unit for analyzing a scope of declarations of respective data expressions in the loop units recognized at the structure analysis unit; a static aliasing analysis unit for statically analyzing an overlap of two memory addresses of data expressions of each pair and for outputting an overlap analysis result of each pair which is whether the two memory addresses overlap each other, the two memory addresses do not overlap each other, or the overlap of the two memory addresses is obscure; an aliasing address comparison instruction generating unit for inserting an instruction to compare the two memory addresses of data expressions of each pair whose overlap is judged to be obscure by the static memory data analysis unit, for generating a plurality of paths defined by combinations of conditions whether or not the two memory addresses of data expressions of each pair overlap, and for generating an instruction to branch to one of the plurality of paths according to a comparison result obtained by the instruction in an execution of a compiled program compiled from the source program; and an optimization unit for respectively optimizing the plurality of paths generated by the aliasing address comparison instruction generating unit.
Claim 3
Dependent Claim
36 words
A compiling apparatus as set forth in claim 1, wherein the operations of the aliasing address comparison instruction generating unit are partly carried out on pairs of data expressions whose overlaps are judged to be obscure.
Claim 4
Dependent Claim
32 words
A compiling apparatus as set forth in claim 2, wherein the operations of the aliasing address comparison instruction generating unit are carried out only on pairs of data expressions in the loops.
Claim 5
Dependent Claim
33 words
A compiling apparatus as set forth in claim 3, wherein the operations of the aliasing address comparison instruction generating unit are carried out only on pairs of data expressions in the innermost loops.
Claim 6
Dependent Claim
161 words
A compiling apparatus as set forth in claim 3, wherein the structure analysis unit and the data flow analysis unit generate information on loops, and the static aliasing analysis unit generates an aliasing obscure list of pairs of data expressions whose overlaps are statically judged to be obscure, the aliasing address comparison instruction generating unit comprises: a loop seek process/branch condition preparation process which receives the aliasing obscure list, seeks loops to be processed by the aliasing address comparison instruction generating unit, and generates a processing loop list showing pairs of data expressions to be expanded into two paths in each loop; and a control flow construction process/loop copy process which determines a number of paths to be generated in each loop according to a number of pairs of data expressions to be expanded, generates an expansion loop list by copying the processing loop list by the number of paths, and rewrites judgement conditions made by the static aliasing analysis unit.
Claim 7
Dependent Claim
161 words
A compiling apparatus as set forth in claim 4, wherein the structure analysis unit and the data flow analysis unit generate information on loops, and the static aliasing analysis unit generates an aliasing obscure list of pairs of data expressions whose overlaps are statically judged to be obscure, the aliasing address comparison instruction generating unit comprises: a loop seek process/branch condition preparation process which receives the aliasing obscure list, seeks loops to be processed by the aliasing address comparison instruction generating unit, and generates a processing loop list showing pairs of data expressions to be expanded into two paths in each loop; and a control flow construction process/loop copy process which determines the number of paths to be generated in each loop according to a number of pairs of data expressions to be expanded, generates an expansion loop list by copying the processing loop list by the number of paths, and rewrites judgement conditions made by the static aliasing analysis unit.
Claim 8
Dependent Claim
58 words
A compiling apparatus as set forth in claim 2, wherein the aliasing address comparison instruction generating unit comprises an effect judgement unit for judging whether the aliasing address comparison instruction generating unit should generate two paths to each pair of data expressions in consideration of a size of object program, compiling time, effect of optimization and so forth.
Claim 9
Dependent Claim
29 words
A compiling apparatus as set forth in claim 7, wherein the operations of the effect judgement unit are carried out only on pairs of data expressions in the loops.
Claim 10
Dependent Claim
29 words
A compiling apparatus as set forth in claim 8, wherein the operations of effect judgement unit are carried out only to pairs of data expressions in the innermost loops.
Claim 11
Dependent Claim
161 words
A compiling apparatus as set forth in claim 8, wherein the structure analysis unit and the data flow analysis unit generate information about loops, and the static aliasing analysis unit generates an aliasing obscure list of pairs of data expressions whose overlaps are statically judged to be obscure, the aliasing address comparison instruction generating unit comprises: a loop seek process/branch condition preparation process which receives the aliasing obscure list, seeks loops to be processed by the aliasing address comparison instruction generating unit, and generates a processing loop list showing pairs of data expressions to be expanded into two paths in each loop; and a control flow construction process/loop copy process which determines the number of paths to be generated in each loop according to a number of pairs of data expressions to be expanded, generates an expansion loop list by copying the processing loop list by the number of paths, and rewrites judgement conditions made by the static aliasing analysis unit.
Claim 12
Dependent Claim
162 words
A compiling apparatus as set forth in claim 9, wherein the structure analysis unit and the data flow analysis unit generate information on loops, and the static aliasing analysis unit generates an aliasing obscure list of pairs of data expressions whose overlaps are statically judged to be obscure, the aliasing address comparison instruction generating unit comprises: a loop seek process/branch condition preparation process which receives the aliasing obscure list, seeks loops to be processed by the aliasing address comparison instruction generating unit, and generates a processing loop list showing pairs of data expressions to be expanded into two paths in each loop; and a control flow construction process/loop copy process which determines the number of paths to be generated in each loop according to the number of pairs of data expressions to be expanded, generates an expansion loop list by copying the processing loop list by the number of paths, and rewrites the judgement conditions made by the static aliasing analysis unit.
Claim 13
Dependent Claim
34 words
A compiling apparatus as set forth in claim 2, wherein pairs of data expressions to which the operations of the aliasing address comparison instruction generating unit are carried out can be indicated by user.
Claim 14
Dependent Claim
36 words
A compiling apparatus as set forth in claim 12, wherein the aliasing address comparison instruction generating unit further insert instructions to output warning messages into paths which are different from the paths indicated by the user.
Claim 15
Dependent Claim
40 words
A compiling apparatus as set forth in claim 1, wherein the aliasing address comparison instruction generating unit generates a instruction to compare the two memory addresses according to changing conditions of data expressions made by the data flow analysis unit.
Claim 16
Dependent Claim
234 words
A compiling method comprising: a structure analysis step for analyzing a structure of an intermediate language program of a source program output from a front-end step, and for recognizing program units constituting loops; a data flow analysis step for analyzing a scope of declarations of respective data expressions in the loop units recognized at the structure analysis step; a static aliasing analysis step for statically analyzing an overlap of two memory addresses of data expressions of each pair and for outputting an overlap analysis result of each pair which is whether the two memory addresses overlap each other, the two memory addresses do not overlap each other, or the overlap of the two memory addresses is obscure; an aliasing address comparison instruction generating step for inserting an instruction to compare the two memory addresses of data expressions of each pair whose overlap is judged to be obscure by the static memory data analysis step, for generating a plurality of paths defined by combinations of two conditions whether or not the two memory addresses of data expressions of each pair overlap, and for generating an instruction to branch to one of the plurality of paths according to a comparison result obtained by the instruction in an execution of a program compiled from the source program; and an optimization step for respectively optimizing the plurality of paths generated by the aliasing address comparison instruction generating step.
Claim 17
Dependent Claim
234 words
A compiling method comprising: a structure analysis step for analyzing a structure of an intermediate language program of a source program output from a front-end step, and for recognizing program units constituting loops; a data flow analysis step for analyzing a scope of declarations of respective data expressions in the loop units recognized at the structure analysis step; a static aliasing analysis step for statically analyzing an overlap of two memory addresses of data expressions of each pair and for outputting an overlap analysis result of each pair which is whether the two memory addresses overlap each other, the two memory addresses do not overlap each other, or the overlap of the two memory addresses is obscure; an aliasing address comparison instruction generating step for inserting an instruction to compare the two memory addresses of data expressions of each pair whose overlap is judged to be obscure by the static memory data analysis step, for generating a plurality of paths defined by combinations of two conditions whether or not the two memory addresses of data expressions of each pair overlap, and for generating an instruction to branch to one of the plurality of paths according to a comparison result obtained by the instruction in an execution of a program compiled from the source program; and an optimization step for respectively optimizing the plurality of paths generated by the aliasing address comparison instruction generating step.
References Cited (Backward Citations)
JPH0425942A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-12-03 | 2000-06-03 | 2000-12-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-12-03 | 2004-06-03 | 2004-12-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-12-03 | 2008-06-03 | 2008-12-03 | $7700.00 | Window Closed / Lapsed |