# US 2018/0024820 A1 · Linear-time algorithm to determine the maximum number of iterations of the iterative algorithm for data-flow analysis for reducible loops

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

- Number: US 2018/0024820 A1
- Document ID: US20180024820A1
- Status: Published application
- Kind: A1
- Application number: 15/213,425
- Filed: 2016-07-19
- Published: 2018-01-25
- Earliest claimed: 2016-07-19
- Assignees: Texas Instruments Incorporated
- Applicants: Texas Instruments Incorporated
- Inventors: Alan L. Davis; Paul Fuqua; Timothy John Harvey
- Web page: https://patentgrep.com/patent/US20180024820A1

## CPC

- G06F 8/433: {Dependency analysis; Data or control flow analysis}
- G06F 8/443: {Optimisation}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A compiler converts a human readable high level program into a corresponding machine language program. This invention improves data-flow analysis. A compiler implementing data-flow analysis typically relies on an iterative algorithm for data-flow analysis. According to the prior art determination of the exact number of loop iterations required for convergence was believed impractical. The prior art selected a maximum number of data-flow analysis iterations relatively arbitrarily. This invention calculates the number of iterations for convergence using backedges in a control flow graph of the source program. This permits the data-flow analysis to be run for exactly the number of iterations needed for convergence. In the event of convergence, an extra, useless iteration is avoided. In the event of non-convergence, valid data can be separated from invalid data, whereas all data was previously discarded.

## Claims

### Claim 1

A computer implemented method of compiling a human readable high level language program into a machine readable language program of a target computer type comprising the steps of:
forming an initial control-flow graph of the program in the human readable language program having nodes, including a starting node, and edges;
iteratively
detecting each node having a backedge into a current starting node,
for each node having a backedge into the current starting node, collapsing the control-flow graph including all nodes between the node having the backedge into the current starting node and the current starting node into a new starting node,
counting each collapse,
until only a single node remains in the control-flow graph;
performing data-flow analysis over the initial control flow graph iterating one more than a number of times equal to the number of counted collapses; and
generating a machine readable language program corresponding to said human readable high level language program based upon the data-flow analysis.

### Claim 2 (depends on 1)

The method of claim 1, further comprising the steps of:
identifying variables within the high level language program; and
wherein said step of performing data-flow analysis over the initial control flow graph
operates separately for each identified variable,
retains data corresponding to a variable for with the data-flow analysis converges, and
discards data corresponding to a variable for which the data-flow analysis does not converge.

### Claim 3 (depends on 2)

The method of claim 2, further comprising the step of:
wherein said step of performing data-flow analysis over the initial control flow graph
determines a variable converges if data corresponding to the variable does not change between iterations of said data-flow analysis; and
determines a variable does not converge if data corresponding to the variable changes between a next to last iteration of said data-flow analysis and a last iteration of said data-flow analysis.

### Claim 4 (depends on 1)

The method of claim 1, further comprising the step of:
recalling human readable high level language program from non-transitory and non-volatile memory.

### Claim 5 (depends on 4)

The method of claim 4, further comprising the step of:
transmitting the machine readable language program to a computer of the target computer type; and
running the machine readable language program on the computer.

### Claim 6 (depends on 6)

The method of claim 6, wherein:
said step of transmitting the machine readable language program to a computer of the target computer type includes
storing the machine readable language program on a non-transitory and non-volatile media carrier,
conveying the media carrier to the computer of the target computer type, and
recalling the machine readable language program from the media carrier.

### Claim 7 (depends on 1)

The method of claim 1, further comprising the step of:
storing the machine readable language program into non-transitory and non-volatile memory.

### Claim 8

A tangible, non-transitory and non-volatile data storage media storing instructions controlling a general purpose computer to compile a human readable high level language program into a machine readable language program of a target computer type, said controlling including:
forming an initial control-flow graph of the program in the human readable language program having nodes, including a starting node, and edges;
iteratively
for each node having a backedge into a current starting node, collapsing the control-flow graph including all nodes between the node having the backedge into the current starting node and the current starting node into a new starting node,
counting each collapse,
until only a single node remains in the control-flow graph;
performing data-flow analysis over the initial control flow graph iterating one more than a number of times equal to the number of counted collapses; and
generating a machine readable language program corresponding to said human readable high level language program based upon the data-flow analysis.

### Claim 9 (depends on 8)

The tangible, non-transitory and non-volatile data storage media of claim 8, further including instructions for controlling a general purpose computer, said controlling further including:
identifying variables within the high level language program; and
wherein said step of performing data-flow analysis over the initial control flow graph
operates separately for each identified variable,
retains data corresponding to a variable for with the data-flow analysis converges, and
discards data corresponding to a variable for which the data-flow analysis does not converge.

### Claim 10 (depends on 9)

The tangible, non-transitory and non-volatile data storage media of claim 9, further including instructions for controlling a general purpose computer, said controlling further including:
wherein said step of performing data-flow analysis over the initial control flow graph
determines a variable converges if data corresponding to the variable does not change between iterations of said data-flow analysis; and
determines a variable does not converge if data corresponding to the variable changes between a next to last iteration of said data-flow analysis and a last iteration of said data-flow analysis.

### Claim 11 (depends on 8)

The tangible, non-transitory and non-volatile data storage media of claim 8, further including instructions for controlling a general purpose computer, said controlling further including:
recalling human readable high level language program from non-transitory and non-volatile memory.

### Claim 12 (depends on 8)

The tangible, non-transitory and non-volatile data storage media of claim 8, further including instructions for controlling a general purpose computer, said controlling further including:
transmitting the machine readable language program to a computer of the target computer type; and
running the machine readable language program on the computer.

### Claim 13 (depends on 12)

The tangible, non-transitory and non-volatile data storage media of claim 12, further including instructions for controlling a general purpose computer, wherein said step of controlling transmitting the machine readable language program to a computer of the target computer type including:
storing the machine readable language program on a non-transitory and non-volatile media carrier,
conveying the media carrier to the computer of the target computer type, and
recalling the machine readable language program from the media carrier.

### Claim 14 (depends on 8)

The tangible, non-transitory and non-volatile data storage media of claim 8, further including instructions for controlling a general purpose computer, said controlling further including:
storing the machine readable language program into non-transitory and non-volatile memory.
