Scalar code reduction using shortest path routing
AssigneeCray Inc.
InventorJames C. Beyer
Life of this patent
Estimating the term…
Abstract
This document discusses, among other things, a system and method computing the shortest path expression in a loop having a plurality of expressions. Candidate expressions in the loop are identified and partitioned into sets. A cost matrix is computed as a function of the sets. Paths are found through the cost matrix and, if there are cycles in the paths, the cycles are broken. One or more shortest path expressions are generated as a function of the paths and one or more of the expressions in the loop are replaced with the shortest path expressions.
Claims10
In a compiler, a method of computing the shortest path expression in a loop having a plurality of expressions, comprising:
- identifying candidate expressions from the plurality of loop expressions;
- partitioning candidate expressions into sets, including a first set;
- computing a cost matrix as a function of the sets;
- finding one or more paths through the cost matrix;
- detecting cycles in the paths;
- if there are cycles in the paths, breaking the cycles;
- generating one or more shortest path expressions as a function of the paths;
- and
- replacing one or more of the expressions in the loop with the shortest path expressions.
A computer, comprising:
- a processor;
- a data source;
- and
- a compiler executing within the computer, wherein the compiler reads source code from the data source, wherein the source code includes a loop having a plurality of expressions, wherein the compiler identifies candidate expressions from the plurality of loop expressions, partitions candidate expressions into sets, computes a cost matrix as a function of the sets, finds paths through the cost matrix, detects cycles in the paths, breaks any cycles, generates one or more shortest path expressions as a function of the paths, and replaces one or more of the expressions in the loop with the shortest path expressions.
Dependencies are inferred from the claim text.