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.
Claims15
In a compiler, a method of computing a 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 of the candidate expressions, the cost matrix indicating cost of generating each candidate expression from other candidate expressions and having a row for each candidate expression and a column for each candidate expression;
- 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 of the candidate expressions, the cost matrix indicating cost of generating each candidate expression from other candidate expressions, 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.
A data storage storing computer-executable instructions for controlling a computer to generate reduced expressions for a loop having a plurality of expressions, by a method comprising:
- identifying candidate expressions from the plurality of loop expressions;
- generating a cost matrix indicating a cost of generating each candidate expression from each other candidate expression;
- identifying paths through the cost matrix that do not have cycles, each path having a cost;
- selecting an identified path based on the cost of the identified paths;
- generating shortest path expressions based on the selected path;
- and
- replacing expressions in the loop with the shortest path expressions.
Dependencies are inferred from the claim text.