# US 2012/0254847 A1 · Register liveness analysis for simd architectures

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254847 A1
- Document ID: US20120254847A1
- Status: Published application
- Kind: A1
- Application number: 13/075,590
- Filed: 2011-03-30
- Published: 2012-10-04
- Earliest claimed: 2011-03-30
- Assignees: Intel Corporation
- Inventors: Biju George; Guei-Yuan Lueh
- Web page: https://patentgrep.com/patent/US20120254847A1

## CPC

- G06F 8/441: {Register allocation; Assignment of physical memory space to logical memory space}
- G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

Systems and methods of allocating physical registers to variables may involve identifying a partial definition of a variable in an inter-procedural control flow graph. A determination can be made as to whether to terminate a live range of the variable based at least in part on the partial definition. Additionally, a physical register may be allocated to the variable based at least in part on the live range.

## Claims

### Claim 1

A method comprising:
conducting a context-sensitive traversal of an inter-procedural control flow graph corresponding to vector-based executable code;
identifying a partial definition of a variable in the inter-procedural control flow graph, wherein the partial definition is associated with a single instruction multiple data execution context;
identifying a strongly connected component status of an inter-procedural control flow graph block containing the partial definition;
determining whether to terminate a live range of the variable based at least in part on the strongly connected component status, and whether the strongly connected component contains multiple entry loops, and whether the partial definition is a direct definition; and
allocating a physical register to the variable based at least in part on the live range.

### Claim 2 (depends on 1)

The method of claim 1, further including terminating the live range of the variable if the partial definition is a direct definition and the partial definition is not within a strongly connected component containing multiple entry loops, wherein terminating the live range includes marking the partial definition as a first definition of the variable.

### Claim 3 (depends on 1)

The method of claim 1, further including filtering out the live range of the variable for a block of the inter-procedural control flow graph if no first definition is associated with the variable, and no definition for the variable reaches the block.

### Claim 4 (depends on 1)

The method of claim 1, wherein conducting the context-sensitive traversal includes:
traversing the inter-procedural control flow graph to identify first definitions;
identifying a call block in the inter-procedural control flow graph, wherein the call block calls a subprogram;
terminating traversal of the subprogram at an exit node of the subprogram; and
using return link information stored in the call block to resume traversal at a return node of the call block.

### Claim 5

A method comprising:
identifying a partial definition of a variable in an inter-procedural control flow graph;
determining whether to terminate a live range of the variable based at least in part on the partial definition; and
allocating a physical register to the variable based at least in part on the live range.

### Claim 6 (depends on 5)

The method of claim 5, further including:
identifying a strongly connected component status of an inter-procedural control flow graph block containing the partial definition; and
determining whether to terminate the live range of the variable based at least in part on the strongly connected component status and whether the strongly connected component contains multiple entry loops.

### Claim 7 (depends on 6)

The method of claim 6, further including terminating the live range of the variable if the partial definition is a direct definition and the partial definition is not within a strongly connected component having multiple entry loops.

### Claim 8 (depends on 7)

The method of claim 7, wherein terminating the live range includes marking the partial definition as a first definition of the variable.

### Claim 9 (depends on 6)

The method of claim 6, further including filtering out the live range of the variable for a block of the inter-procedural control flow graph if no first definition is associated with the variable, and no definition for the variable reaches the block.

### Claim 10 (depends on 5)

The method of claim 5, further including conducting a context-sensitive traversal of the inter-procedural control flow graph to identify a first definition.

### Claim 11 (depends on 10)

The method of claim 10, wherein conducting the context-sensitive traversal includes:
traversing the inter-procedural control flow graph to identify first definitions;
identifying a call block in the inter-procedural control flow graph, wherein the call block calls a subprogram;
terminating traversal of the subprogram at an exit node of the subprogram; and
using return link information stored in the call block to resume traversal at a return node of the call block.

### Claim 12 (depends on 5)

The method of claim 5, further including computing at least one of a set of variables that may be defined by a function and a set of variables that may be used indirectly in a block.

### Claim 13 (depends on 5)

The method of claim 5, wherein the partial definition is associated with a single instruction multiple data execution context in vector-based executable code.

### Claim 14

A computer readable storage medium comprising a set of instructions which, if executed by a processor, cause a computer to:
identify a partial definition of a variable in an inter-procedural control flow graph;
determine whether to terminate a live range of the variable based at least in part on the partial definition; and
allocate a physical register to the variable based at least in part on the live range.

### Claim 15 (depends on 14)

The medium of claim 14, wherein the instructions, if executed, cause a computer to:
identify a strongly connected component status of an inter-procedural control flow graph block containing the partial definition; and
determine whether to terminate the live range of the variable based at least in part on the strongly connected component status and whether the strongly connected component contains multiple entry loops.

### Claim 16 (depends on 15)

The medium of claim 15, wherein the instructions, if executed, cause a computer to terminate the live range of the variable if the partial definition is a direct definition and the partial definition is not within a strongly connected component having multiple entry loops.

### Claim 17 (depends on 16)

The medium of claim 16, wherein the instructions, if executed, cause a computer to mark the partial definition as a first definition of the variable.

### Claim 18 (depends on 15)

The medium of claim 15, wherein the instructions, if executed, cause a computer to filter out the live range of the variable for a block of the inter-procedural control flow graph if no first definition is associated with the variable, and no definition for the variable reaches the block.

### Claim 19 (depends on 14)

The medium of claim 14, wherein the instructions, if executed, cause a computer to conduct a context-sensitive traversal of the inter-procedural control flow graph to identify a first definition.

### Claim 20 (depends on 19)

The medium of claim 19, wherein the instructions, if executed, cause a computer to:
traversing the inter-procedural control flow graph to identify first definitions;
identify a call block in the inter-procedural control flow graph, wherein the call block is to call a subprogram;
terminate traversal of the subprogram at an exit node of the subprogram; and
use return link information stored in the call block to resume traversal at a return node of the call block.

### Claim 21 (depends on 14)

The medium of claim 14, wherein the instructions, if executed, cause a computer to compute at least one of a set of variables that may be defined by a function and a set of variables that may be used indirectly in a block.

### Claim 22 (depends on 14)

The medium of claim 14, wherein the partial definition is to be associated with a single instruction multiple data execution context in vector-based executable code.

### Claim 23

A system comprising:
a main processor;
a graphics processor coupled to the main processor; and
a computer readable storage medium including a set of instructions which, if executed by the graphics processor, cause the system to,
identify a partial definition of a variable in an inter-procedural control flow graph, wherein the partial definition is to be associated with a single instruction multiple data execution context in vector-based executable code,
determine whether to terminate a live range of the variable based at least in part on the partial definition, and
allocate a physical register to the variable based at least in part on the live range.

### Claim 24 (depends on 23)

The system of claim 23, wherein the instructions, if executed, cause the system to,
identify a strongly connected component status of an inter-procedural control flow graph block containing the partial definition, and
determine whether to terminate the live of the variable based at least in part on the strongly connected component status and whether the strongly connected component contains multiple entry loops.

### Claim 25 (depends on 24)

The system of claim 24, wherein the instructions, if executed, cause the system to terminate the live range of the variable if the partial definition is a direct definition and the partial definition is not within a strongly connected component having multiple entry loops.

### Claim 26 (depends on 25)

The system of claim 25, wherein the instructions, if executed, cause the system to mark the partial definition as a first definition of the variable.

### Claim 27 (depends on 24)

The system of claim 24, wherein the instructions, if executed, cause the system to filter out the live range of the variable for a block of the inter-procedural control flow graph if no first definition is associated with the variable, and no definition for the variable reaches the block.

### Claim 28 (depends on 23)

The system of claim 23, wherein the instructions, if executed, cause the system to conduct a context-sensitive traversal of the inter-procedural control flow graph to identify the partial definition.

### Claim 29 (depends on 28)

The system of claim 28, wherein the instructions, if executed, cause the system to:
traversing the inter-procedural control flow graph to identify first definitions;
identify a call block in the inter-procedural control flow graph, wherein the call block is to call a subprogram,
terminate traversal of the subprogram at an exit node of the subprogram, and
use return link information stored in the call block to resume traversal at a return node of the call block.

### Claim 30 (depends on 23)

The system of claim 23, wherein the instructions, if executed, cause the system to compute at least one of a set of variables that may be defined by a function and a set of variables that may be used indirectly in a block.
