3. The method of claim 1 , wherein computing a cost matrix includes subtracting each of the expressions within the first set from all of the other expressions in the first set.
1. 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.