Expression Simplifier

Expression simplifier supports normalization and simplification of expressions. It internally transforms a given expression to a normalized form so that each operand of a commutative and associative operation is located at the same height in the tree representation; in other words, it converts a binary tree to a n-ary tree. This internal representation makes the simplification algorithm easier and the result of the simplification is converted back to the original internal representation of Cetus.

Like its predecessor Polaris, a key feature of Cetus is the ability to reason about the represented program in symbolic terms. For example, compiler analyses and optimizations at the source level often require the expressions in the program to be in a simplified form. A specific example is data dependence analysis that collects the coefficients of affine subscript expressions, which are passed to the underlying data dependence test package. Cetus has functionalities that ease the manipulation of expressions for pass writers. The following example shows how to invoke the simplifier. The simplifier returns a new copy of the original expression that was converted to a normalized form.

 import cetus.hir.*;
 Expression e = ...
 e = Symbolic.simplify(e);

It is also possible for users to invoke individual simplification technique for their own purposes. The following examples show the functionality of the individual simplification technique. See the javadoc page or the source code to learn how to invoke each technique individually.

 1+2*a+4-a --> 5+a (folding)
 a*(b+c) --> a*b+a*c (distribution)
 (a*2)/(8*c) --> a/(4*c) (division)