Rearrangement of algebraic expressions based on operand ranking schemes

摘要

A system and method for rearranging algebraic expressions occurring in program code based on a scheme of ranking operands. The system scans program code to identify an algebraic expression specified by the program code. The expression includes binary operations, scalar operands and at least one array operand. The system operates on the algebraic expression to obtain a final expression by: computing a rank for each of the operands; and performing algebraic transformations on selected subexpressions of the algebraic expression so that in the final expression operands are combined in the order of their rank. The ranking scheme may be designed to force scalars to be combined before arrays, and/or, to force constants to be combined first, loop invariants second, and variants last. In some embodiments, the ranking scheme is a vector ranking scheme including two or more components (such as invariance rank, dimensional rank and data-size rank).

主权项

1. A method for operating a compiler, the method comprising:
utilizing a computer to perform:
scanning program code to identify a first algebraic expression specified by the program code, wherein the first algebraic expression includes two or more mutually-compatible binary operations and three or more input operands, wherein the three or more input operands include two or more scalar operands and one or more array operands; andoperating on the first algebraic expression to obtain a final algebraic expression by:
(a) computing a rank vector for each of the three or more input operands, wherein the rank vector for any given one of the three or more input operands includes a first component that is based on an invariance rank of the input operand and a second component that is based on a dimension of the input operand, and(b) performing transformations on selected subexpressions of the first algebraic expression, wherein the transformations include one or more commute transformations and one or more associate transformations, wherein each of the commute transformations exchanges input operands of a corresponding one of the two or more binary operations to order the input operands according to an ordering of possible states of the rank vector, wherein the ordering of possible states gives precedence to the first component over the second component;wherein the final algebraic expression specifies an order of execution for the two or more binary operations such that the three or more input operands are combined in an order that agrees with the ordering of possible states of the rank vector.