Compiler with improved live range interference investigation

• US 5,642,512 A
• Filed: 07/27/1995
• Issued: 06/24/1997
• Est. Priority Date: 09/13/1994
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Tanaka, Akira, Sayama, Junko, Yukawa, Hiroshi
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): Chaki, Kakali
• Application Number:
  US08/508,136
• Time in Patent Office: 698 Days
• Field of Search: 395/700, 395/709
• US Class Current: 717/153
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory

Abstract

The present invention is constructed so as to form simple blocks within each basic block, with the simple block internal live range storage unit 12 storing variables whose live ranges are entirely located within one simple block. basic block internal live range storage unit 13 stores variables whose live ranges are located within a number of simple blocks but, at the same time, entirely within one basic block, and the inter-basic block live range group storage unit 14 stores variables whose live ranges extend between basic blocks. The live range generation unit 15 detects the live ranges of the variables and stores the result in the live range storage unit 11, whilst also storing the variables during the detection of live ranges in one of the simple block internal live range storage unit 12, the basic block internal live range storage unit 13 and the inter-basic block live range group storage unit 14. Then, the live range interference investigation unit 16 investigates the interference of live ranges between only the live ranges of the variables to be assigned by means of comparing the live ranges. By doing so, the investigation process for the live ranges of variables can be speeded up, and hence the speed of the compiling operation can be improved.

Claims

1. A compiler for compiling a program composed of a plurality of instructions into a machine language program, comprising:

jump instruction detection means for detecting jump instructions in the program and a jump destination instruction for each of the jump instructions;

division means for dividing the program into basic blocks based on the jump instructions and the jump destination instructions detected by the jump instruction detection means;

live range detection means for detecting, for every variable in the program, a live range which is a range for which a variable in the program is valid, and for expressing a detection result for each variable as a set of instruction position information showing positions of instructions included in the live range;

basic block internal live variable detection means for detecting every variable for which the live range detected by the live range detection means is positioned entirely within one of the basic blocks and for expressing a detection result for each of the basic blocks as a basic block internal live variable group corresponded to an appropriate basic block;

inter-basic block live variable detection means for detecting every variable for which the live range detected by the live range detection means extends between basic blocks and for expressing a detection result as an inter-basic block live variable group;

first live range interference judgement means for taking two variables at a time from the inter-basic block live variable group and, by finding an intersection set of sets of instruction position information corresponding to the live ranges of two variables, for judging whether there is interference between the live ranges;

second live range interference judgement means for taking two variables at a time from a basic block internal live variable group corresponded to a same basic block and, by calculating an intersection set of sets of instruction position information corresponding to the live ranges of the two variables, for judging whether there is interference between the live ranges; and

third live range interference judgement means for taking one variable at a time from a basic block internal live variable group corresponded to a basic block and one variable at a time from the inter-basic block live variable group and, by calculating an intersection set of sets of instruction position information corresponding to the live ranges of the two variables, for judging whether there is interference between the live ranges,

wherein the compiler executes resource assignment using judgement results of the first, the second and the third live range interference judgement means.

2. The compiler of claim 1, further comprising:

simple block formation means for forming simple blocks inside each basic block, each of which is a series of instructions including at least one pair of a definition instruction which is an instruction setting a value of a variable and a reference instruction which is an instruction using the variable set by the definition instruction;

simple block internal live variable detection means for detecting every variable in the basic block internal live variable groups whose live range is included in only one of the simple blocks, and for expressing a detection result for each of the simple blocks as a simple block internal live variable group corresponded to an appropriate simple block; and

inter-simple block live variable detection means for detecting every variable in the basic block internal live variable groups whose live range extends between simple blocks, and for expressing a detection result as an inter-simple block live variable group for an appropriate basic block,

wherein the second live range interference judgement means includes;

a first live range interference judgement unit for taking two variables at a time from one of the inter-simple block live variable groups and, by calculating an intersection set of sets of instruction position information corresponding to the live ranges of the two variables, for judging whether there is interference between the live ranges;

a second live range interference judgement unit for taking two variables at a time from a simple block internal live variable group corresponded to a same simple block and, by calculating an intersection set of sets of instruction position information corresponding to the live ranges of the two variables, for judging whether there is interference between the live ranges; and

a third live range interference judgement unit for taking one variable at a time from a simple block internal live variable group corresponded to a simple block and one variable at a time from the inter-simple block live variable group and, by calculating an intersection set of sets of instruction position information corresponding to the live ranges of the two variables, for judging whether there is interference between the live ranges.

3. The compiler of claim 2, wherein

the simple block generation means includes:

definition instruction extraction means for extracting one definition instruction at a time from one of the basic blocks formed by the division means;

corresponding reference instruction detection means for detecting a reference instruction corresponding to the definition instruction from the basic block including the definition instruction extracted by the definition instruction extraction means;

definition instruction movement possibility judgement means for judging whether it is possible to move the definition instruction to a position of the reference instruction detected by the corresponding reference instruction detection means;

definition instruction movement means for moving, when the definition instruction movement possibility judgement means judges that movement is possible, the definition instruction for which movement is judged by the definition instruction movement possibility judgement means to be possible to a point just before the reference instruction corresponding to the definition instruction and for synthesizing the definition instruction and the reference instruction into one simple block; and

simple block remaining instruction movement means for moving, when the definition instruction moved by the definition instruction movement means before movement is a final instruction in a simple block, every remaining instruction in a same simple block as the definition instruction moved by the definition instruction movement means before movement to a point just before a movement destination of the definition instruction and for synthesizing every remaining instruction into a destination simple block.

4. The compiler of claim 3, wherein

the definition instruction movement possibility judgement means includes:

variable singular/plural judgement unit for judging whether a variable whose value is set by the definition instruction extracted by the definition instruction extraction means is singular;

reference singular/plural judgement unit for judging, when the variable singular/plural judgement unit judges that the variable is singular, whether there is only one reference instruction detected by the corresponding reference instruction detection means;

a first resetting validity judgement unit for judging, when the reference singular/plural judgement unit judges that there is only one reference instruction, whether the variable whose value is set in the definition instruction corresponding to the reference instruction is reset during a part of the program from the definition instruction to the reference instruction;

definition instruction used variable detection unit for detecting, when the first resetting validity judgement unit judges that there is no resetting, any variables used in the definition instruction;

a second resetting validity judgement unit for judging whether any variables detected by the definition instruction used variable detection unit are reset during a part of the program from the definition instruction to the reference instruction;

a movement possibility judgement unit for judging, when the second resetting validity judgement unit judges that there is no resetting, that the definition instruction can be moved to a position of the reference instruction.

5. The compiler of claim 4, wherein

the third live range interference judgement means includes:

a fourth live range interference judgement unit for taking one variable at a time from the inter-basic block live variable group and one variable at a time from a simple block internal live variable group corresponded to a simple block and, by finding an intersection set of the sets of instruction position information corresponding to the live ranges of the two variables, for judging whether there is interference between the live ranges; and

a fifth live range interference judgement unit for taking one variable at a time from the inter-basic block live variable group and one variable at a time from the inter-simple block live variable group and, by finding an intersection set of the sets of instruction position information corresponding to the live ranges of the two variables, for judging whether there is interference between the live ranges.

6. The compiler of claim 5, further comprising valid variable information storage means for storing variables valid at an entry point of a basic block and variables valid at an exit point of a basic block, corresponded with each basic block in the program,

wherein the live range detection means includes:

a definition instruction extraction unit for extracting one definition instruction in the program at a time;

an exit point invalidity judgement unit for detecting a basic block including a definition instruction extracted by the definition extraction unit and the variable defined by definition instruction and for judging whether a set value of the detected variable is invalid at an exit point of the basic block, based on a stored content of the valid variable information storage means;

an exit point closest reference instruction detection unit for detecting, when the exit point invalidity judgement unit detects that the set value is invalid, a reference instruction corresponding to the definition instruction which is closest to the exit point of the basic block;

a basic block internal instruction position detection unit for detecting all of the instruction position information from an instruction following after the definition instruction to the reference instruction detected by the exit point closest reference instruction detection unit; and

a basic block internal live range expression unit for expressing a live range of the variable whose instruction position information was detected as all of the instruction position information detected by the basic block internal instruction position detection unit,

wherein the basic block internal live variable detection means sets the variable whose live range is expressed by the basic block internal live range expression unit as a member of the basic block internal live variable group corresponding to a basic block which includes the variable.

7. The compiler of claim 6, further comprising a basic block internal definition information storage means for storing each basic block corresponded with any variables defined in each basic block, wherein

the live range detection means includes:

a resetting validity judgement unit for judging, when the exit point invalidity judgement unit judges that the variable is valid, whether the variable defined in a definition instruction judged to be valid by the exit point invalidity judgement means is reset during the period from the definition instruction to an exit point of a basic block including the definition instruction, based on a stored content of the basic block internal definition information storage means;

an exit point validity position information detection unit for detecting, when the resetting validity judgement unit judges that there is no resetting, instruction position information from an instruction following the definition instruction to the exit point of the basic block;

a live basic block detection unit for detecting, when the resetting validity judgement unit judges that there is no resetting, every basic block, out of basic blocks following in order after the basic block including the definition instruction, in which the variable is valid at an entry point and at an exit point with no resetting of the variable in between, based on stored contents of the valid variable information storage means and of the basic block internal definition information storage means;

an inter-basic block position information detection unit for detecting all instruction position information included in the basic block retrieved by the live basic block detection unit, based on a stored content of the basic block internal definition information storage means;

a final basic block detection unit for detecting, when the resetting validity judgement unit judges that there is no resetting, a basic block for which the value of the variable is valid at an entry point but is invalid at an exit point, out of all the basic blocks following in order after the basic block which includes the definition instruction;

a final reference instruction detection unit for detecting a final reference instruction corresponding to the definition instruction in the basic block detected by the final basic block detection unit;

an entry point validity position information detection unit for detecting all instruction position information from an entry point of the basic block detected by the final basic block detection unit to the reference instruction detected by the final reference instruction detection unit; and

an inter-basic block live range expression unit for expressing a total live range of the variable judged by the resetting validity judgement unit as not being reset as a total of a detection result of the exit point validity position information detection means, a detection result of the entry point validity position information detection means, and a detection result of the inter-basic block position information detection means,

wherein the inter-basic block live variable detection means sets the variable, judged by the resetting validity judgement means as not being reset, as a member of the inter-basic block live variable group.

8. The compiler of claim 7, further comprising reference-definition information storage means for storing information for each instruction position in the program corresponded with any variables used at each instruction position and instruction position information of instructions defining the variables,

wherein the live range detection means includes:

a marking unit for adding identification information to a position of a definition instruction extracted by the definition instruction extraction unit;

a reference variable detection unit for detecting a variable used in a reference instruction corresponding to a definition instruction extracted by the definition instruction extraction unit;

a definition instruction detection unit for detecting all definition instructions which set a set value to the variable detected by the reference variable detection unit, based on a stored content of the reference-definition information storage means;

a non-marked definition instruction extraction unit for detecting a definition instruction which has not been marked with identification information by the marking unit, out of all the definition instructions detected by the definition instruction detection unit;

a first branch block internal position information detection unit for detecting all instruction position information from an instruction following the definition instruction detected by non-marked definition instruction extraction unit to an exit point of the basic block including the definition instruction; and

a first instruction position information addition unit for adding the instruction position information detected by the first branch block internal position information detection unit to the instruction position information expressed by the inter-basic block live range expression unit.

9. The compiler of claim 8, further comprising definition-reference information storage unit for storing information for each instruction position in the program corresponded with any variables defined at each instruction position and instruction position information of instructions using the variables,

wherein the live range detection means includes:

a branch block internal reference instruction detection unit for detecting a reference instruction corresponding to the definition instruction detected by the non-marked definition instruction extraction unit, based on a stored content of the definition-reference information storage unit;

a branch block detection unit for detecting a basic block including the reference instruction detected by the branch block internal reference instruction detection unit;

a second branch block internal position information detection unit for detecting all instruction position information from an entry point of the basic block detected by branch block detection unit to the reference instruction detected by the branch block internal reference instruction detection unit; and

a second instruction position information addition unit for adding the instruction position information detected by the second branch block internal position information detection unit to the group of instruction position information expressed by the inter-basic block expression unit.

10. A compiler for compiling a program, composed of a plurality of instructions, in which a number of simple blocks each of which is a series wherein at least one pair of a definition instruction for setting a value of a variable and a reference instruction which uses the value of the variable set by the definition variable are arranged in order, into a machine language program for which every variable in the program is assigned to one of registers and memory, comprising:

jump instruction detection means for detecting jump instructions in the program and a jump destination instruction for each of the jump instruction;

division means for dividing the program into basic blocks based on the jump instructions and the jump destination instructions detected by the jump instruction detection means;

definition instruction extraction means for extracting, once the program has been divided into basic blocks, one definition instruction at a time from a basic block;

corresponding reference instruction detection means for detecting, once a definition instruction has been extracted, a reference instruction using a variable whose value is set by the definition instruction from the basic block including the definition instruction extracted by the definition instruction extraction means;

definition instruction movement possibility judgement means for judging, once the reference instruction has been detected, whether it is possible to move the definition instruction to a position of the reference instruction detected by the corresponding reference instruction detection means;

definition instruction movement means for moving, the definition instruction for which movement is judged by the definition instruction movement possibility judgement means to be possible to a point just before the reference instruction corresponding to the definition instruction and for synthesizing the definition instruction and the reference instruction into one simple block; and

simple block remaining instruction movement means for moving, when the definition instruction moved by the definition instruction movement means before movement is a final instruction in a simple block, every remaining instruction in a same simple block as the definition instruction moved by the definition instruction movement means before movement to a point just before a movement destination of the definition instruction and for synthesizing every remaining instruction into a destination simple block; and

resource assignment means for assigning, once the definition instruction extraction means has extracted every definition instruction, all variables whose live ranges interfere with one another to different registers.

11. The compiler of claim 10, wherein

the definition instruction movement possibility judgement means includes:

variable singular/plural judgement unit for judging whether a variable whose value is set by the definition instruction extracted by the definition instruction extraction means is singular;

reference singular/plural judgement unit for judging, when the variable singular/plural judgement unit judges that the variable is singular, whether there is only one reference instruction detected by the corresponding reference instruction detection means;

a first resetting validity judgement unit for judging, when the reference singular/plural judgement unit judges that there is only one reference instruction, whether the variable whose value is set in the definition instruction corresponding to the reference instruction is reset during a part of the program from the definition instruction to the reference instruction;

definition instruction used variable detection unit for detecting, when the first resetting validity judgement unit judges that there is no resetting, any variables used in the definition instruction;

a second resetting validity judgement unit for judging whether any variables detected by the definition instruction used variable detection unit are reset during the part of the program from the definition instruction to the reference instruction; and

a movement possibility judgement unit for judging, when the second resetting validity judgement unit judges that there is no resetting, that the definition instruction can be moved to a position of the reference instruction.

12. The compiler of claim 11, wherein

the resource assignment means includes:

live range detection means for detecting, for every variable in the program, a live range which is a range for which a variable in the program is valid, and for expressing a detection result as a set of instruction position information showing positions of instructions included in the live range;

basic block internal live variable detection means for detecting every variable for which the live range detected by the live range detection means is positioned entirely within one of the basic blocks and for expressing a detection result as a basic block internal live variable group corresponded to an appropriate basic block;

inter-basic block live variable detection means for detecting every variable for which the live range detected by the live range detection means extends between basic blocks and for expressing a detection result as an inter-basic block live variable group;

first live range interference judgement means for taking two variables at a time from the inter-basic block live variable group and, by calculating an intersection set of sets of instruction position information corresponding to the live ranges of the two variables, for judging whether there is interference between the live ranges;

second live range interference judgement means for taking two variables at a time from a basic block internal live variable group corresponded to a same basic block and, by calculating an intersection set of sets of instruction position information corresponding to the live ranges of the two variables, for judging whether there is interference between the live ranges; and

third live range interference judgement means for taking one at a time variable from a basic block internal live variable group corresponded to a basic block and one variable at a time from the inter-basic block live variable group and, by calculating an intersection set of the sets of instruction position information corresponding to the live ranges of the two variables, for judging whether there is interference between the live ranges; and

assignment means for assigning variables whose live ranges interfere with one another to different registers by using judgement results of the first, the second and the third live range interference judgement means.

13. The compiler of claim 12, wherein

the resource assigning means further includes:

simple block internal live variable detection means for detecting every variable in the basic block internal live variable group whose live range is included in only one of the simple blocks, and for expressing a detection result as a simple block internal live variable group corresponded to an appropriate simple block; and

inter-simple block live variable detection means for detecting every variable in the basic block internal live variable group whose live range extends between simple blocks, and for expressing a detection result as an inter-simple block live variable group,

wherein the second live range interference judgement means includes;

a first live range interference judgement unit for taking two variables at a time from the inter-simple block live variable group and, by calculating an intersection set of the sets of instruction position information corresponding to the live ranges of the two variables, for judging whether there is interference between the live ranges;

a second live range interference judgement unit for taking two variables at a time from a simple block internal live variable group corresponded to a same simple block and, by calculating an intersection set of the sets of instruction position information corresponding to the live ranges of the two variables, for judging whether there is interference between the live ranges; and

a third live range interference judgement unit for taking one variable from a simple block internal live variable group corresponded to a simple block and one variable from the inter-simple block live variable group and, by calculating an intersection set of the sets of instruction position information corresponding to the live ranges of the two variables, for judging whether there is interference between the live ranges.

14. The compiler of claim 13, wherein

the third live range interference judgement means includes:

a fourth live range interference judgement unit for taking one variable at a time from the inter-basic block live variable group and one variable at a time from a simple block internal live variable group corresponded to a simple block and, by finding an intersection set of the sets of instruction position information corresponding to the live ranges of the two variables, for judging whether there is interference between the live ranges; and

a fifth live range interference judgement unit for taking one variable at a time from the inter-basic block live variable group and one variable at a time from the inter-simple block live variable group and, by finding an intersection set of the sets of instruction position information corresponding to the live ranges of the two variables, for judging whether there is interference between the live ranges.

15. The compiler of claim 14, further comprising valid variable information storage means for storing variables valid at an entry point of a basic block and variables valid at an exit point of a basic block, corresponded with each basic block in the program,

wherein the live range detection means includes:

a definition instruction extraction unit for extracting one definition instruction in the program at a time;

an exit point invalidity judgement unit for detecting a basic block including a definition instruction extracted by the definition extraction unit and the variable defined by definition instruction and for judging whether a set value of the detected variable is invalid at an exit point of the basic block, based on a stored content of the valid variable information storage means;

an exit point closest reference instruction detection unit for detecting, when the exit point invalidity judgement unit detects that the set value is invalid, a reference instruction corresponding to the definition instruction which is closest to the exit point of the basic block;

a basic block internal instruction position detection unit for detecting all of the instruction position information from an instruction following after the definition instruction to the reference instruction detected by the exit point closest reference instruction detection unit; and

a basic block internal live range expression unit for expressing a live range of the variable whose instruction position information was detected as all of the instruction position information detected by the basic block internal instruction position detection unit,

wherein the basic block internal live variable detection means sets the variable whose live range is expressed by the basic block internal live range expression unit as a member of the basic block internal live variable group corresponding to a basic block which includes the variable.

16. The compiler of claim 15, further comprising a basic block internal definition information storage means for storing each basic block corresponded with any variables defined in each basic block, wherein

the live range detection means includes:

a resetting validity judgement unit for judging, when the exit point invalidity judgement unit judges that the variable is valid, whether the variable defined in a definition instruction judged to be valid by the exit point invalidity judgement means is reset during the period from the definition instruction to an exit point of a basic block including the definition instruction, based on a stored content of the basic block internal definition information storage means;

an exit point validity position information detection unit for detecting, when the resetting validity judgement unit judges that there is no resetting, instruction position information from an instruction following the definition instruction to the exit point of the basic block;

a live basic block detection unit for detecting, when the resetting validity judgement unit judges that there is no resetting, every basic block, out of basic blocks following in order after the basic block including the definition instruction, in which the variable is valid at an entry point and at an exit point with no resetting of the variable in between, based on stored contents of the valid variable information storage means and of the basic block internal definition information storage means;

an inter-basic block position information detection unit for detecting all instruction position information included in the basic block retrieved by the live basic block detection unit, based on a stored content of the basic block internal definition information storage means;

a final basic block detection unit for detecting, when the resetting validity judgement unit judges that there is no resetting, a basic block for which the value of the variable is valid at an entry point but is invalid at an exit point, out of all the basic blocks following in order after the basic block which includes the definition instruction;

a final reference instruction detection unit for detecting a final reference instruction corresponding to the definition instruction in the basic block detected by the final basic block detection unit;

an entry point validity position information detection unit for detecting all instruction position information from an entry point of the basic block detected by the final basic block detection unit to the reference instruction detected by the final reference instruction detection unit; and

an inter-basic block live range expression unit for expressing a total live range of the variable judged by the resetting validity judgement unit as not being reset as a total of a detection result of the exit point validity position information detection means, a detection result of the entry point validity position information detection means, and a detection result of the inter-basic block position information detection means,

wherein the inter-basic block live variable detection means sets the variable, judged by the resetting validity judgement means as not being reset, as a member of the inter-basic block live variable group.

17. The compiler of claim 16, further comprising reference-definition information storage means for storing information for each instruction position in the program corresponded with any variables used at each instruction position and instruction position information of instructions defining the variables,

wherein the live range detection means includes:

a marking unit for adding identification information to a position of a definition instruction extracted by the definition instruction extraction unit;

a reference variable detection unit for detecting a variable used in a reference instruction corresponding to a definition instruction extracted by the definition instruction extraction unit;

a definition instruction detection unit for detecting all definition instructions which set a set value to the variable detected by the reference variable detection unit, based on a stored content of the reference-definition information storage means;

a non-marked definition instruction extraction unit for detecting a definition instruction which has not been marked with identification information by the marking unit, out of all the definition instructions detected by the definition instruction detection unit;

a first branch block internal position information detection unit for detecting all instruction position information from an instruction following the definition instruction detected by non-marked definition instruction extraction unit to an exit point of the basic block including the definition instruction; and

a first instruction position information addition unit for adding the instruction position information detected by the first branch block internal position information detection unit to the instruction position information expressed by the inter-basic block live range expression unit.

18. The compiler of claim 17, further comprising definition-reference information storage unit for storing information for each instruction position in the program corresponded with any variables defined at each instruction position and instruction position information of instructions using the variables,

wherein the live range detection means includes:

a branch block internal reference instruction detection unit for detecting a reference instruction corresponding to the definition instruction detected by the non-marked definition instruction extraction unit, based on a stored content of the definition-reference information storage unit;

a branch block detection unit for detecting a basic block including the reference instruction detected by the branch block internal reference instruction detection unit;

a second branch block internal position information detection unit for detecting all instruction position information from an entry point of the basic block detected by branch block detection unit to the reference instruction detected by the branch block internal reference instruction detection unit; and

a second instruction position information addition unit for adding the instruction position information detected by the second branch block internal position information detection unit to the group of instruction position information expressed by the inter-basic block expression unit.