Method of generating optimised stack code

• US 20060200811A1
• Filed: 03/07/2006
• Published: 09/07/2006
• Est. Priority Date: 03/07/2005
• Status: Abandoned Application

• Current Assignee: Innaworks Development Limited
• Original Assignee: Innaworks Development Limited
• Inventors: Cheng, Stephen M.K.
• Application Number:
  US11/368,692
• Publication Number:
  US 20060200811A1
• Time in Patent Office: Days
• US Class Current: 717/144
• CPC Class Codes: G06F 8/41 Compilation

Abstract

The present invention relates to a method for generating optimised stack code for a stack-based machine from a register-based representation of the original code. The method includes the steps of: creating a dependence graph from the representation; removing true dependencies from the dependence graph by matching portions of the dependence graph with a set of patterns; and defining stack code corresponding to the dependence graph using code generation rules associated with each pattern.

Claims

1. A method for generating optimised stack code from a register-based representation, including the steps of:

i) creating a dependence graph from the representation;

ii) removing true dependencies from the dependence graph by matching portions of the dependence graph with a set of patterns; and

iii) defining stack code corresponding to the dependence graph using code generation rules associated with each patter.

2. A method as claimed in claim 1, wherein the representation is a representation of a basic code block or an extended basic code block.

3. A method as claimed in claim 2, wherein the dependence graph is a directed acyclic graph and is not a tree.

4. A method as claimed in claim 3, wherein one or more of the patterns is not a tree.

5. A method as claimed in claim 1, wherein the code generation rules include one or more rules from the set of inserting stack manipulation instructions, inserting stack store instructions, and inserting store load instructions.

6. A method as claimed in claim 5, wherein the set of patterns includes a set of pass patterns and a set of collapse patterns.

7. A method as claimed in claim 6, wherein step (ii) includes the sub-step of:

traversing the dependence graph and during the traversal of the graph applying the following rules;

a) if one or more nodes forming a portion of the graph match a pass pattern continue to traverse the graph;

b) if two or more nodes forming a portion of the graph match a collapse pattern collapse the nodes to a single collapsed node; and

c) if one or more nodes forming a portion of the graph do not match either a pass pattern or a collapse pattern then define the result of a node to be stored.

8. A method as claimed in claim 7, wherein the graph is traversed in reverse topological order.

9. A method as claimed in claim 8, wherein each collapse pattern has a set of constraints.

10. A method as claimed in claim 9, wherein the set of constraints include the dependency between nodes.

11. A method as claimed in claim 10, wherein the set of constraints include the non-true dependency between nodes.

12. A method as claimed in claim 7, wherein if rule (c) applies then the traversal of the graph is rolled-back to a position where the result of a node can be stored according to a predetermined rule.

13. A method as claimed in claim 12, wherein the rolling-back includes un-collapsing one or more collapsed nodes.

14. A method as claimed in claim 1, wherein the set of patterns includes a set of collapse patterns and wherein a collapse pattern which creates a single collapsed node is associated with a code generation rule which leaves the result of the single collapsed node on the stack when one or more nodes in the graph have a true dependence on the single collapsed node.

15. A method as claimed in claim 1, wherein the set of patterns includes a set of collapse patterns and wherein a collapse pattern which creates a single collapsed node with a true dependence on one or more result-generating nodes in the graph is associated with a code generation rule which removes the results of the one or more result-generating nodes from the stack.

16. A method as claimed in claim 1 wherein the set of patterns includes a set of collapse patterns and wherein stack code is defined in step (iii) by traversing the graph and during traversal applying the following rule:

if the node is a collapsed node then schedule the constituent nodes according to the code generation rules associated with the pattern that matched the collapsed node.

17. A method as claimed in claim 1, wherein the stack code is JAVA bytecode or ECMA-335 instructions.

19. Software arranged for performing the method of claim 1.

21. Storage media arranged for storing software as claimed in claim 19.

18. A system for generating optimised stack code from a register-based representation, including:

a processor arranged for creating a dependence graph from the representation;

removing true dependencies from the dependence graph by matching portions of the dependence graph with a set of patterns; and

defining stack code corresponding to the dependence graph using code generation rules associated with each pattern.

20. Software arranged for performing the system of claim 18.

22. Storage media arranged for storing software as claimed in claim 20.