Method and system for performing global processor resource assignment in an assembler

• US 20040139427A1
• Filed: 01/10/2003
• Published: 07/15/2004
• Est. Priority Date: 01/10/2003
• Status: Active Grant

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Jeffries, Clark D., Garvey, Joseph F.
• Granted Patent: US 7,111,287 B2
• Time in Patent Office: Days
• US Class Current: 717/141
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

A method and system for assembling code using an assembler is disclosed. The assembly language code includes a plurality of code blocks associated with resource-needs, such as variables, and resources, such as registers, I/O locations, memory locations, and coprocessors. The method and system include providing a technology that allows the global assignment of resource-needs to resources such that run time resource conflicts are avoided. The method and system further includes providing a grammar for allowing resources to be defined and managed, a grammar for allowing the resource-needs to be defined and managed, a grammar providing definition of code blocks, and a grammar for associating resources with code blocks.

Claims

1. A method for assembling assembly language code using an assembler, the code including a plurality of code blocks, the plurality of code blocks having a plurality of resource-needs and the plurality of code blocks having a plurality of resources, the method comprising the steps of:

(a) recognizing a context, the plurality of resource-needs, and the plurality of resources;

(b) automatically assigning at least a portion of the plurality of resources based upon a context, the plurality of resources being defined and managed using a grammar, at least a portion of the plurality of resources being assigned by pairing members of the plurality of resources with the plurality of resource-needs such that no two contexts exist simultaneously at a run time using the same resource; and

(c) creating an executable image based on the assembly language code if all of the plurality of resources-needs have been assigned from the plurality of resources.

2. The method of claim 1 wherein the automatically assigning step (b) further includes the step of:

(b1) if any of the plurality of resources cannot be automatically assigned to the plurality of resource-needs, indicating which of the plurality of resource-needs does not have at least one of the plurality of resources assigned.

3. A method for assembling assembly language code using an assembler, the code including a plurality of code blocks, the plurality of code blocks having a plurality of resource-needs and the plurality of code blocks having a plurality of resources, the method comprising the steps of:

(a) providing a first grammar for specifying a context;

(b) providing a second grammar for specifying a plurality of resource-needs associated with the context;

(c) providing a third grammar for specifying a plurality of resources associated with the context;

(d) providing a fourth grammar for resolving ambiguities in usage of indirect resources or indirect use of resource-needs within the context;

(e) providing a fifth grammar for resolving ambiguities in indirect control flow changes within the context;

(f) automatically assigning at least portion of the plurality of resources by pairing members of the plurality of resources with the plurality of resource-needs so a portion of the plurality of contexts that exist simultaneously at a run time do not use the same resource.

4. The method of claim 3 further comprising the step of:

(g) recognizing resource usage in the plurality of code blocks.

5. The method of claim 3 further comprising the step of:

(g) if any of the plurality of resources cannot be automatically assigned to the plurality of resource-needs, indicating which of the plurality of resource-needs does not have at least one of the plurality of resources assigned.

6. The method of claim 3 wherein the resource assignment step (f) further includes the steps of:

(f1) making assignments using a resource assignment graph including a plurality of vertices and a plurality of edges connecting the plurality of vertices, each of the plurality of vertices corresponding to a use of a resource-need by a code block of the plurality of code blocks, each of the plurality of edges connecting a pair of the plurality of vertices representing concurrent resource-needs.

7. The method of claim 6 wherein the resource assignment step (f) further includes the steps of:

(f2) assigning a portion of the plurality of resources to the plurality of vertices in the resource assignment graph such that members of the plurality of vertices sharing a common edge use different resources.

8. The method of claim 7 wherein the assignment step (f2) further includes the steps of:

(f2i) providing a weight for each of the plurality of vertices based upon a number of contexts the resource-need represented by the vertex is active in; and

(f2ii) assigning resources to the plurality of vertices in an order based upon the weight of each of the plurality of vertices.

9. The method of claim 8 further comprising the step of:

(g) if the any of the plurality of vertices in the resource assignment graph cannot be assigned resources, indicating which of the plurality of vertices cannot be assigned such that members of the plurality of vertices sharing a common edge use different resources.

10. An assembler for processing assembly language code, the assembly language code including a plurality of code blocks, the plurality of code blocks using a plurality of resources having a plurality of resource-needs, the assembler comprising:

a parser and lexer for reading the assembly language code, recognizing a context, recognizing declarations and usages of the plurality of resource-needs and recognizing declarations and usages of the plurality of resources;

a code generator for generating an executable image based on the code; and

a resource manager for automatically assigning at least a portion of the plurality of resources based upon a context, the plurality of resources being defined and managed using a grammar, at least a portion of the plurality of resources being assigned by pairing members of the plurality of resources with the plurality of resource-needs such that no two contexts exist simultaneously at a run time using the same resource.

11. The assembler of claim 10 wherein the resource manager indicates which of the plurality of resource-needs cannot be assigned members from the plurality of resources if the plurality of resources cannot be automatically assigned to the plurality of resource-needs.

12. The assembler of claim 10 wherein the resource manager assigns a portion of the plurality of resources by using a resource graph including a plurality of vertices and a plurality of edges connecting the plurality of vertices, each of the plurality of vertices corresponding to a use of a resource-need, each of the plurality of edges corresponding to a pair of concurrent resource-needs.

13. The assembler of claim 12 wherein the resource manager further assigns a portion of the plurality of resources to the plurality of vertices such that any of the plurality of vertices sharing a common edge are assigned different resources from the plurality of resources.

14. The assembler of claim 13 wherein the resource manager assigns resources from the plurality of resources to the plurality of vertices in the resource graph(s) guided by a weight for each of the plurality of vertices based upon the number of contexts in which the resource-need represented by the vertex is present in.

15. The assembler of claim 14 wherein the resource manager further indicates which of the plurality of vertices cannot be assigned resources from the plurality of resources such that vertices sharing a common edge are assigned different resources from the plurality of resources.