# US 2006/0080645 A1 · System and method for optimizing source code

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

- Number: US 2006/0080645 A1
- Document ID: US20060080645A1
- Status: Published application
- Kind: A1
- Application number: 11/284,338
- Filed: 2005-11-21
- Published: 2006-04-13
- Earliest claimed: 2001-01-12
- Assignees: Imec
- Inventors: Miguel Miranda; Francky Catthoor; Martin Janssen; Hugo De Man
- Web page: https://patentgrep.com/patent/US20060080645A1

## CPC

- G06F 8/443: {Optimisation}
- G06F 8/51: Source to source
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

One aspect of the invention includes a method of address expression optimization of source-level code. The source-level code describes the functionality of an application to be executed on a digital device. The method comprises first inputting first source-level code that describes the functionality of the application into optimization system. The optimization system then transforms the first source-level into a second source level that has fewer nonlinear operations than the first source-level code.

## Claims

### Claim 1

A method of optimizing address expressions within source-level code, wherein the source-level code describes the functionality of an application to be executed on a digital device, the method comprising:
inputting a first source-level code that describes the functionality of the application, the first source-level code comprising address computation code and a plurality of arrays with address expressions in at least one programming loop construct, wherein the address computation code or one of the address expressions has nonlinear operations; and
transforming the first source-level code into a second source-level code that describes substantially the same functionality as the first source-level code, wherein the second source-level code has fewer nonlinear operations than the first source-level code, and wherein the second source level code has the same number of loop constructs as the first source-level code; and
wherein the digital device comprises at least one programmable instruction set processor.

### Claim 2 (depends on 1)

The method of in claim 1, wherein the nonlinear operations are selected from the group comprising: modulo operations, integer division operations, power operations and multiplication operations.

### Claim 3 (depends on 1)

The method of claim 1, wherein the transforming comprises: a first code transforming, a second code transforming and a third code transforming, the first code transforming comprising algebraic code transformations and common subexpression elimination code transformations, the second code transforming including code hoisting and the third code transforming including induction analysis.

### Claim 4 (depends on 3)

The method of claim 3, wherein first the first code transforming is executed, thereafter the second code transforming and thereafter the third code transforming.

### Claim 5 (depends on 1)

The method of claim 1, wherein the arrays are multi-dimensional arrays.

### Claim 6 (depends on 1)

The method of claim 1, wherein the first, second source-level code and intermediate source-level codes generated are represented as shared data-flow graphs.

### Claim 7 (depends on 6)

The method of claim 6, wherein the shared data-flow graphs are directed acyclic graphs with homogeneous synchronous data-flow behavior.

### Claim 8 (depends on 7)

The method of claim 7, wherein the shared data-flow graph enables modeling in a single subgraph address expressions and address calculation code with substantially different iterators.

### Claim 9 (depends on 8)

The method of claim 8, wherein the method uses a select operation for enabling single subgraph modeling.

### Claim 10 (depends on 6)

The method of claim 6, wherein the method time-multiplexes calculations that are related to address expressions.

### Claim 11 (depends on 1)

The method of claim 1, wherein the method is independent of the digital device architecture.

### Claim 12 (depends on 11)

The method of claim 11, wherein the method does not use detailed knowledge of the target device of the source code.

### Claim 13 (depends on 1)

The method of claim 1, wherein the method transforms the source-level codes by applying composite transformations with look-ahead local minima avoiding capabilities.

### Claim 14 (depends on 13)

The method of claim 13, wherein the composite transformations comprise a finite predetermined sequence of elementary, non-decomposable transformations, wherein each of the elementary transformations are executable if a single set of conditions related to the elementary transformation are satisfied, wherein each of the composite transformations are composed such that the composite transformation can be executed if one of a plurality of sets of conditions is satisfied.

### Claim 15 (depends on 14)

The method of claim 14, wherein the composite transformation transforms a first source-level code with a first cost into a second source-level code with a second cost, the second cost being lower than the first cost, and while executing the elementary transformation of which the composite transformation is composed of, intermediate source-level codes are generated, at least one of the intermediate source-level codes having a cost being larger than the first cost.

### Claim 16 (depends on 1)

The method of claim 1, wherein transforming comprises applying an algebraic transformation on at least one of the address expressions or part of the address calculation code, wherein the algebraic transformation replaces at least a part of the address expressions or part of an expression within the address computation code by another equivalent expression.

### Claim 17 (depends on 15)

The method of claim 15, wherein the execution of the composite transformations is performed on shared data-flow graph representations of the source-level codes.

### Claim 18 (depends on 17)

The method of claim 17, wherein applying the algebraic transformation increases the number of common subexpressions that are affected by nonlinear operations.

### Claim 19 (depends on 1)

The method of claim 1, wherein the transformation comprises common subexpression elimination on at least one of the address expressions or part of the address computation code, and wherein the common subexpression elimination detects a subexpression that is found within at least two expressions within either the address expressions or the address computation code and replaces the subexpression with a single variable, wherein the variable is computed via the subexpression higher in the code, the variable computation becoming part of the address computation code.

### Claim 20 (depends on 19)

The method of claim 19, wherein the common subexpression elimination decreases the amount of nonlinear operations within the source-level code.

### Claim 21 (depends on 1)

The method of claim 1, wherein at least one piece of address calculation code is located within a selected scope and transforming comprises code hoisting wherein a part of the piece of address calculation code is moved outside the scope.

### Claim 22 (depends on 1)

The method of claim 1, wherein the moving of the part of the piece of address calculation code reduces the amount of executions of nonlinear operations within the part of the piece of address calculation code.

### Claim 23 (depends on 21)

The method of claim 21, wherein code hoisting is applied across the scope of a loop construct.

### Claim 24 (depends on 21)

The method of claim 21, wherein code hoisting is applied across the scope of a conditional.

### Claim 25 (depends on 24)

The method of claim 24, wherein code hoisting is based on a range analysis.

### Claim 26 (depends on 25)

The method of claim 25, wherein code hoisting is considered for applying only for expressions with overlapping ranges.

### Claim 27 (depends on 25)

The method of claim 25, wherein the code hoisting is applied only to expressions with at least one common factor.

### Claim 28 (depends on 25)

The method of claim 25, wherein code hoisting is applied for equal expressions only when the sum of their ranges is larger than the overall range.

### Claim 29 (depends on 25)

The method of claim 25, wherein code hoisting is applied for non-equal expressions after a cost-benefit analysis that evaluates: the degree of similarity of the non-equal expressions, the degree of similarity being expressed as the amount of common subexpressions within the non-equal expressions, their costs and the cost after a potential code hoisting step.

### Claim 30 (depends on 1)

The method of claim 1 wherein modulo related algebraic transformation combined with a common subexpression elimination and code hoisting are executed iteratively.

### Claim 31 (depends on 1)

The method of claim 1, wherein a linear induction analysis based step is applied on at least one address expression, which is piece wise linear, the induction analysis step replaces the address expression with single pointer arithmetic and a single conditional.

### Claim 32 (depends on 31)

The method of claim 31, wherein the piece wise linear address expression comprise at least of one of the group comprising: a modulo operation or a division operation.

### Claim 33 (depends on 32)

The method of claim 32, wherein the piece wise linear address expression comprises nested operations.

### Claim 34 (depends on 1)

The method of claim 1, wherein nonlinear induction analysis is applied on at least one address expression, which is nonlinear, wherein the induction replaces the address expression with add, accumulate, constant division and constant multiplication operations or combinations thereof.

### Claim 35

A system for address expression optimization of source-level code, wherein the source-level code describes the functionality of an application to be executed on a digital device, wherein the digital device comprises at least one programmable instruction set processor, the system comprising:
means for inputting a first source-level code that describes the functionality of the application, the first source-level code comprising address computation code and a plurality of arrays with address expressions in at least one programming loop construct, wherein at least the address computation code or one of the address expressions has nonlinear operations; and
means for transforming the first source-level code into a second source-level code that describes substantially the same functionality as the first source-level code, wherein the second source-level code has fewer nonlinear operations than the first source-level code,
wherein the means for transforming comprises means for performing a linear induction analysis step on at least one piece wise linear address expression and wherein performing the induction analysis step comprises replacing the address expression with single pointer arithmetic and a single conditional, and
wherein the second source level code has the same number of loop constructs as the first source-level code.

### Claim 36

A system for address expression optimization of source-level code, wherein the source-level code describes the functionality of an application to be executed on a digital device, the system comprising:
an optimizing system for receiving a first source-level code that describes the functionality of the application, wherein the first source-level code has nonlinear operations in at least one programming loop construct, and wherein the optimizing system transforms the first source-level code into a second source-level code that has fewer nonlinear operations than the first source-level code, and wherein the second source level code has the same number of loop constructs as the first source-level code, and wherein the digital device comprises at least one programmable instruction set processor,
and wherein the optimizing system transforms the first source-level code by performing a linear induction analysis step on at least one piece wise linear address expression and wherein performing the induction analysis step comprises replacing the address expression with single pointer arithmetic and a single conditional.

### Claim 37

Executable code that has been optimized by the method comprising:
transforming first source-level code having at least one programming loop construct and an at least one non-linear address expression within the programming loop construct, the first source level code into a second source-level code that describes substantially the same functionality as the first source-level code, wherein the second source-level code has fewer nonlinear operations than the first source-level code, and wherein the second source-level code has the same number of loop constructs as the first source-level code and wherein the second source-level code has been compiled for subsequent execution on a programmable instruction set processor, and
wherein transforming the first source-level code comprises performing a linear induction analysis step on at least one piece wise linear address expression and wherein performing the induction analysis step comprises replacing the address expression with single pointer arithmetic and a single conditional.

### Claim 38 (depends on 1)

The method of claim 1, wherein the loop construct of the first source-level code is structured to loop the same number of times as the loop construct of the second source-level code.

### Claim 39 (depends on 1)

The method of claim 1, wherein transforming comprises generating conditional expressions.

### Claim 40 (depends on 35)

The system of claim 35, wherein the loop construct of the first source-level code is structured to loop the same number of times as the loop construct of the second source-level code.

### Claim 41 (depends on 36)

The system of claim 36, wherein the loop construct of the first source-level code is structured to loop the same number of times as the loop construct of the second source-level code.

### Claim 42 (depends on 37)

The executable code of claim 37, wherein the loop construct of the first source-level code is structured to loop the same number of times as the loop construct of the second source-level code.
