Optimization method for compiler, optimizer for a compiler and storage medium storing optimizing code
View Patent ↗The invention pertains to an optimization method for a compiler, comprising providing a model of inter-operand constraints of physical registers of a target-platform of a compilation; and a) providing an intermediate representation of a source code using virtual registers; b) grouping the virtual registers of the intermediate representation based on the model of inter-operand constraints into two or more groups, each group comprising at least one virtual register; c) if for at least one group at least one interference of virtual registers within the group occurs, amending the intermediate representation to resolve at least one interference and jumping to step b); otherwise d) providing a representation of a group interference graph of interferences between the groups; and e) allocating virtual registers to physical registers using a coloring scheme on the representation of the group interference graph. The invention also refers to a corresponding optimizer for a compiler and a computer-readable storage medium storing optimizing code.
1. An optimization method for a compiler, comprising: providing a model of inter-operand constraints of physical registers of a target-platform of a compilation; and
a) providing an intermediate representation of a source code using virtual registers;
b) grouping the virtual registers of the intermediate representation based on the model of inter-operand constraints into two or more groups, each group comprising at least one virtual register;
c) if for at least one group at least one interference of virtual registers within the group occurs, amending the intermediate representation to resolve the at least one interference and jumping to step b); otherwise
d) providing a representation of a group interference graph of interferences between the groups; and
e) allocating virtual registers to physical registers using a coloring scheme on the representation of the group interference graph.
2. The optimization method of claim 1 , wherein b) further comprises detecting live ranges of the virtual registers of the intermediate representation before the grouping is performed.
3. The optimization method of claim 1 , wherein d) further comprises spilling to memory a part of one group or one group if at least one interference between two or more groups occurs after providing the representation of the group interference graph.
4. The optimization method according to claim 1 , comprising providing target-platform strategy information.
5. The optimization method according to one of claim 4 , wherein the target-platform strategy information includes information regarding register manipulation instructions of the target-platform.
6. The optimization method according to claim 4 , wherein amending the intermediate representation is performed based on the target-platform strategy information.
7. The optimization method according to claim 3 , wherein spilling to memory is performed based on target-platform strategy information.
8. The optimization method according to claim 1 , wherein the model of inter-operand constraints of physical registers comprises an enumeration of combinations of physical registers allowed by the inter-operand constraints of the target-platform.
9. A tangible computer storage medium comprising an optimizer for a compiler, the optimizer comprising:
a model component adapted to provide a model of a inter-operand constraints of physical registers of a target-platform of a compilation;
an intermediate representation component adapted to provide and/or receive an intermediate representation of source code using virtual registers;
a grouping component adapted to group the virtual registers of the intermediate representation into two or more groups based on the model of inter-operand constraints, wherein each group comprises at least one virtual register;
a representation amending component adapted to amend the intermediate representation if for at least one group at least one interference of virtual registers within the group occurs to resolve the at least one interference;
a group interference graph component adapted to provide a representation of a group interference graph of interferences between the groups; and
an allocating component adapted to allocate virtual registers to physical registers using a coloring scheme on the representation of the group interference graph.
10. The optimizer according to claim 9 , further comprising a live range detection component adapted to detect live ranges of the virtual registers of the intermediate representation.
11. The optimizer according to claim 9 , further comprising a spilling component adapted to spill a group or part of a group to memory.
12. The optimizer according to claim 9 , further comprising a target-platform information component adapted to provide target-platform strategy information.
13. The optimizer according to claim 9 , wherein the representation amending component is adapted to amend the intermediate representation based on the target-platform strategy information and/or the spilling component is adapted to spill a group or part of a group to memory based on the target-platform strategy information.
14. The optimization method of claim 2 , wherein d) further comprises spilling to memory a part of one group or one group if at least one interference between two or more groups occurs after providing the representation of the group interference graph.
15. The optimization method according to claim 2 , comprising providing target-platform strategy information.
16. The optimization method according to claim 3 , comprising providing target-platform strategy information.
17. The optimization method according to claim 2 , wherein the model of inter-operand constraints of physical registers comprises an enumeration of combinations of physical registers allowed by the inter-operand constraints of the target-platform.
18. The optimization method according to claim 3 , wherein the model of inter-operand constraints of physical registers comprises an enumeration of combinations of physical registers allowed by the inter-operand constraints of the target-platform.
19. The optimizer according to claim 10 , further comprising a spilling component adapted to spill a group or part of a group to memory.
20. The optimizer according to claim 10 , further comprising a target-platform information component adapted to provide target-platform strategy information.