Back to results
US 8,806,460 B2Granted
Method and apparatus for avoiding register interference
AssigneeQUALCOMM Incorporated
InventorChristopher A. Vick
Life of this patent
Estimating the term…
Abstract
The aspects enable a computing device to allocate memory space to variables during runtime compilation of a software application. A first variable associated with a code segment within code being compiled may be identified and assigned a priority tag. A second variable associated with another code segment within the code being compiled may also be assigned a priority tag. A determination may be made regarding whether the first and second variables are contemporaneously live during execution, and whether legal storage location sets for the first and second variables overlap. The assigned priority tags may be used for assigning storage locations to the first and second variables based on the determination.
Claims32
A method for allocating storage locations to variables while compiling code for a computing system, comprising:
- identifying a first variable associated with a code segment within code being compiled;
- assigning a first priority tag to the first variable;
- identifying a second variable associated with another code segment within the code being compiled;
- assigning a second priority tag to the second variable;
- using the assigned priority tags in assigning storage locations to the first and second variables;
- wherein using the assigned priority tags in assigning storage locations to the first and second variables comprises:
- determining whether the first and second variable are contemporaneously live during execution of the compiled code;
- determining whether legal storage location sets for the first and second variables overlap when it is determined that the first and second variable are contemporaneously live during execution of the compiled code;
- comparing the priority tags assigned to each of the first and second variables when it is determined that the first and second variables are contemporaneously live during execution of the compiled code and have overlapping legal storage location sets;
- and
- subtracting, when the first and second variables have different priority tags, the legal storage location set of the higher priority variable from the legal storage location set of the lower priority variable to obtain a remainder set of storage locations;
- determining whether the remainder set of storage locations is empty;
- assigning the remainder set of storage locations to the variable with the lower priority tag as a new legal parameter set and proceeding with compiler operations when the remainder storage location set is not empty;
- and
- inserting an interference edge in an interference graph and proceeding with the compiler operations when the remainder set of storage locations is empty.
12 more elements
A computing device configured to allocate storage locations to variables while compiling code, comprising:
- a memory;
- a processor;
- means for identifying a first variable associated with a code segment within code being compiled;
- means for assigning a first priority tag to the first variable;
- means for identifying a second variable associated with another code segment within the code being compiled;
- means for assigning a second priority tag to the second variable;
- means for using the assigned priority tags in assigning storage locations to the first and second variables;
- wherein means for using the assigned priority tags in assigning storage locations to the first and second variables comprises:
- means for determining whether the first and second variable are contemporaneously live during execution of the compiled code;
- means for determining whether legal storage location sets for the first and second variables overlap when it is determined that the first and second variable are contemporaneously live during execution of the compiled code;
- means for comparing the priority tags assigned to each of the first and second variables when it is determined that the first and second variables are contemporaneously live during execution of the compiled code and have overlapping legal storage location sets;
- and
- means for subtracting, when the first and second variables have different priority tags, the legal storage location set of the higher priority variable from the legal storage location set of the lower priority variable to obtain a remainder set of storage locations;
- means for determining whether the remainder set of storage locations is empty;
- means for assigning the remainder set of storage locations to the variable with the lower priority tag as a new legal parameter set and proceeding with compiler operations when the remainder set of storage locations is not empty;
- and
- means for inserting an interference edge in an interference graph and proceeding with the compiler operations when the remainder set of storage locations is empty.
14 more elements
A non-transitory computer readable storage medium having stored thereon processor-executable software instructions configured to cause a processor to perform operations for allocating storage locations to variables while compiling code, the operations comprising:
- identifying a first variable associated with a code segment within code being compiled;
- assigning a first priority tag to the first variable;
- identifying a second variable associated with another code segment within the code being compiled;
- assigning a second priority tag to the second variable;
- and
- using the assigned priority tags in assigning storage locations to the first and second variables;
- wherein using the assigned priority tags in assigning storage locations to the first and second variables comprises:
- determining whether the first and second variable are contemporaneously live during execution of the compiled code;
- determining whether legal storage location sets for the first and second variables overlap when it is determined that the first and second variable are contemporaneously live during execution of the compiled code;
- comparing the priority tags assigned to each of the first and second variables when it is determined that the first and second variables are contemporaneously live during execution of the compiled code and have overlapping legal storage location sets;
- and
- subtracting, when the first and second variables have different priority tags, the legal storage location set of the higher priority variable from the legal storage location set of the lower priority variable to obtain a remainder set of storage locations;
- determining whether the remainder set of storage locations is empty;
- assigning the remainder set of storage locations to the variable with the lower priority tag as a new legal parameter set and proceeding with compiler operations when the remainder set of storage locations is not empty;
- and
- inserting an interference edge in an interference graph and proceeding with the compiler operations when the remainder set of storage locations is empty.
13 more elements
A computing device, comprising:
- a memory;
- and a processor coupled to the computing device and the memory, wherein the processor is configured with processor-executable instructions to perform operations comprising:
- identifying a first variable associated with a code segment within code being compiled;
- assigning a first priority tag to the first variable;
- identifying a second variable associated with another code segment within the code being compiled;
- assigning a second priority tag to the second variable;
- using the assigned priority tags in assigning storage locations to the first and second variables;
- wherein using the assigned priority tags in assigning storage locations to the first and second variables comprises:
- determining whether the first and second variable are contemporaneously live during execution of the compiled code;
- determining whether legal storage location sets for the first and second variables overlap when it is determined that the first and second variable are contemporaneously live during execution of the compiled code;
- comparing the priority tags assigned to each of the first and second variables when it is determined that the first and second variables are contemporaneously live during execution of the compiled code and have overlapping legal storage location sets;
- and
- subtracting, when the first and second variables have different priority tags, the legal storage location set of the higher priority variable from the legal storage location set of the lower priority variable to obtain a remainder set of storage locations;
- determining whether the remainder set of storage locations is empty;
- assigning the remainder set of storage locations to the variable with the lower priority tag as a new legal parameter set and proceeding with compiler operations when the remainder set of storage locations is not empty;
- and
- inserting an interference edge in an interference graph and proceeding with the compiler operations when the remainder set of storage locations is empty.
14 more elements
Dependencies are inferred from the claim text.