EP0405845A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Performing compilation optimisation procedures in an optimisation compiler
Assignee: International Business Machines Corp
•
Filing: 1990-06-21
•
Granted: —
•
Expires: 2010-06-21
Abstract
Abstract The present invention relates to a method, in an optimising compiler using specified optimisation procedures for identifying ways of improving the quality of compiled code, for performing preliminary optimising procedures on a program to be compiled, prior to carrying out any specified optimisation procedure. According to the invention the preliminary optimising procedures comprise: (a) developing a control flowgraph representing all possible execution paths for the program; (b) identifying subgraphs in the program; (c) performing the steps of: (1) selecting a subgraph to be examined for the optimisation procedure, the first subgraph on a first iteration being the entire program; (2) by examining the code sequences in the subgraph, determining the number of entities in the subgraph which are relevant to each dimension of arrays used in the specified procedure to represent data flow equations; (3) determining the amount of memory required to contain the arrays; (4) if the amount of memory exceeds a predetermined memory usage limit for the compilation thereby denoting an unsuccessful attempt at the optimisation procedure, applying step (5) to the subgraph, otherwise applying the optimisation procedure to the subgraph, and (5) applying steps (2) to (4) for every subgraph contained in the subgraph for which insufficient memory was found in step (4).
Inventors
- 👤 Joyce Marie Janczyn
- 👤 Peter Willy Markstein
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-02 07:29
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
210 words
In an optimising compiler using specified optimisation procedures for identifying ways of improving the quality of compiled code, a method of performing preliminary optimising procedures on a program to be compiled prior to carrying out any specified optimisation procedures, said preliminary optimising procedures comprising: a. developing a control flowgraph representing all possible execution paths for said program; b. identifying subgraphs (SCR 16, 17, 18, 19, 20) contained within said program; c. performing the steps of: 1) defining a subgraph to be examined for said optimisation procedure, said first subgraph on a first iteration being the entire program (SCR 20); 2) by examining the code sequences in said subgraph, determining the number of entities in said subgraph which are relevant to each dimension of arrays used in said optimisation procedure to represent data flow equations; 3) determining the amount of memory required to contain said arrays; 4) if said amount of memory exceeds a predetermined memory usage limit for said optimisation procedure thereby denoting an unsuccessful attempt at applying said optimisation procedure, applying step 5) to said subgraph, otherwise applying said optimisation procedure to said subgraph, and 5) for every subgraph contained in said subgraph for which insufficient memory was available as determined in step 4), applying steps 2) to 4).
Claim 2
Dependent Claim
210 words
In an optimising compiler using specified optimisation procedures for identifying ways of improving the quality of compiled code, a method of performing preliminary optimising procedures on a program to be compiled prior to carrying out any specified optimisation procedures, said preliminary optimising procedures comprising: a. developing a control flowgraph representing all possible execution paths for said program; b. identifying subgraphs (SCR 16, 17, 18, 19, 20) contained within said program; c. performing the steps of: 1) defining a subgraph to be examined for said optimisation procedure, said first subgraph on a first iteration being the entire program (SCR 20); 2) by examining the code sequences in said subgraph, determining the number of entities in said subgraph which are relevant to each dimension of arrays used in said optimisation procedure to represent data flow equations; 3) determining the amount of memory required to contain said arrays; 4) if said amount of memory exceeds a predetermined memory usage limit for said optimisation procedure thereby denoting an unsuccessful attempt at applying said optimisation procedure, applying step 5) to said subgraph, otherwise applying said optimisation procedure to said subgraph, and 5) for every subgraph contained in said subgraph for which insufficient memory was available as determined in step 4), applying steps 2) to 4).
Claim 3
Dependent Claim
17 words
A method as claimed in Claim 1, in which a plurality of specified optimisation procedures are performed.
Claim 4
Dependent Claim
18 words
A method as claimed in Claim 1, in which said subgraphs are strongly connected regions within said program.
Claim 5
Dependent Claim
35 words
A method as claimed in Claim 1, in which said specified optimisation procedures are selected from the group consisting of code motion, store motion, removing redundant code sequences, removing useless code sequences, and simplifying expressions.
Claim 6
Dependent Claim
39 words
A method as claimed in Claim 1, in which said entities are selected from the group consisting of instructions, results, expressions, dictionary entries, regions in a source code program, basic blocks in a source code program and combinations thereof.
Claim 7
Dependent Claim
95 words
A method as claimed in Claim 1, wherein the amount of memory required to contain all entities generated by said compiler is calculated by: a) for each array, multiplying the unit size of each dimension to obtain the total number of elements in the array; b) multiplying the number of array elements by the size of one array element to obtain the number of memory units which would be occupied by the array; and c) summing the memory requirements of the arrays to derive the total amount of memory needed by the particular optimisation procedure.
Claim 8
Dependent Claim
47 words
A method as claimed in Claim 1, further comprising the step of, after a successful optimisation procedure has been defined and performed, examining a subgraph containing the subgraph for which said successful optimisation procedure was performed to determine whether it can be optimised by said specified procedure.
Claim 9
Dependent Claim
39 words
A method as claimed in Claim 1, further comprising the step of, after a successful optimisation procedure has been defined and performed, examining the containing strongly connection region to determine whether it can be optimised by said specified procedure.
Claim 10
Dependent Claim
71 words
A method as claimed in Claim 1, further comprising the steps of: a. after a successful optimisation procedure has been defined and performed on at least one inner subgraph, examining its containing subgraph to determine whether it can be optimised by said specified procedure; b. if said containing subgraph can be optimised, examining its containing strongly connected region in the same manner and, if it can be optimised, performing said optimisation.
Claim 11
Dependent Claim
224 words
An optimising compiler using specified optimisation procedures for identifying ways of improving the quality of compiled code, and comprising means for performing preliminary optimising procedures on a program to be compiled prior to carrying out any specified optimisation procedure characterised in that said means for performing preliminary optimisation procedures comprises: a. means (21) for developing a control flowgraph representing all possible execution paths for said program; b. means (22) for identifying subgraphs contained within said program; c. means (23) for defining a subgraph to be examined for said optimisation procedure, said first subgraph on a first iteration being the entire program, and by examining the code sequences in said subgraph, determining she number of entities in said subgraph which are relevant to each dimension of arrays used in said optimisation procedure to represent data flow equations; d. means (24) for determining the amount of memory required to contain said arrays; e. means (25) for, if said amount of memory exceeds a predetermined memory usage limit for said optimi sation procedure thereby denoting an unsuccessful attempt at applying said optimisation procedure, applying step 5) to said subgraph, and otherwise for applying said optimisation procedure to said subgraph; and f. means for applying steps b) d) and e) for every subgraph contained in said subgraph for which insufficient memory was available as determined in step e).
Claim 12
Dependent Claim
224 words
An optimising compiler using specified optimisation procedures for identifying ways of improving the quality of compiled code, and comprising means for performing preliminary optimising procedures on a program to be compiled prior to carrying out any specified optimisation procedure characterised in that said means for performing preliminary optimisation procedures comprises: a. means (21) for developing a control flowgraph representing all possible execution paths for said program; b. means (22) for identifying subgraphs contained within said program; c. means (23) for defining a subgraph to be examined for said optimisation procedure, said first subgraph on a first iteration being the entire program, and by examining the code sequences in said subgraph, determining she number of entities in said subgraph which are relevant to each dimension of arrays used in said optimisation procedure to represent data flow equations; d. means (24) for determining the amount of memory required to contain said arrays; e. means (25) for, if said amount of memory exceeds a predetermined memory usage limit for said optimi sation procedure thereby denoting an unsuccessful attempt at applying said optimisation procedure, applying step 5) to said subgraph, and otherwise for applying said optimisation procedure to said subgraph; and f. means for applying steps b) d) and e) for every subgraph contained in said subgraph for which insufficient memory was available as determined in step e).
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.