Global processor resource assignment in an assembler

• US 7,111,287 B2
• Filed: 01/10/2003
• Issued: 09/19/2006
• Est. Priority Date: 01/10/2003
• Status: Expired due to Fees

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Jeffries, Clark D., Garvey, Joseph F.
• Primary Examiner(s): Ingberg, Todd
• Application Number:
  US10/340,499
• Publication Number:
  US 20040139427A1
• Time in Patent Office: 1,348 Days
• Field of Search: 717/144, 717/149, 718/104
• US Class Current: 717/144
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space

Abstract

An assembler for assembling code 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. A technology is provided that allows the global assignment of resource-needs to resources such that run time resource conflicts are avoided. 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 are also provided.

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:

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

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;

writing an executable image to a computer-readable medium based on the assembly language code if all of the plurality of resources-needs have been assigned from the plurality of resources;

if any of the plurality of resources cannot be automatically assigned to the plurality of resource-needs, automatically providing an indication, of which of the plurality of resource-needs does not have at least one of the plurality of resources assigned; and

allowing a user to manually free at least a portion of the plurality of resources if all of the plurality of resource-needs have not been assigned, the portion of the plurality of resources being selectable by the user based upon the indication of which of the plurality of resource-needs does not have at least one of the plurality of resources assigned.

2. The method of claim 1 wherein the executable image creating further includes;

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

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:

providing a first grammar for specifying a context;

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

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

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

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

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;

if any of the plurality of resources cannot be automatically assigned to the plurality of resource-needs, automatically providing an indication of which of the plurality of resource-needs does not have at least one of the plurality of the resources assigned;

allowing a user to free at least a portion of the plurality of resources if all of the plurality of resource-needs have not been assigned the portion of the plurality of resources being selectable by the user based upon the indication of which of the plurality of resource-needs does not have at least one of the plurality of resources assigned and

writing an executable image to a computer-readable medium based on the assembly language code if all of the plurality of resource needs have been assigned from the plurality of resources.

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

recognizing resource usage in the plurality of code blocks.

5. The method of claim 3 wherein the resource assignment step further includes the steps of:

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.

6. The method of claim 5 wherein the resource assignment step 4 further includes the steps of:

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.

7. The method of claim 6 wherein the assignment step further includes the steps of:

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

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

8. The method of claim 7 further comprising the step of;

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.

9. The method of claim 3 further comprising;

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

10. A computer-readable medium containing a program 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 program further comprising instructions for:

utilizing 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;

using 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;

if any of the plurality of resources cannot be automatically assigned to the plurality of resource-needs. automatically providing an indication of which of the plurality of resource-needs does not have at least one of the plurality of resources assigned;

allowing a user to manually free at least a portion of the plurality of resources if all of the plurality of resource-needs have not been assigned, the portion of the plurality of resources being selectable by the user based upon the indication of which the plurality of resource-needs does not have at least one of the plurality of sources assigned; and

using a code generator to write an executable image to another computer-readable medium based on the code if the plurality of the resource-needs have been assigned.

11. The computer readable medium of claim 10 wherein the resource manager further includes assigning 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.

12. The computer-readable medium of claim 11 wherein the resource manager further using further includes assigning 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.

13. The computer-readable medium of claim 12 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.

14. The computer-readable medium of claim 13 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.

15. The computer-readable medium of claim 10 wherein the code generator using further includes:

using the code generator for generating the executable image based on the code only if all of the plurality of resources-needs have been assigned from the plurality of resources.