Approach for Expression optimization

RESOLVED: I HAVE DECIDED TO USE YAP BASED EXPRESSION OPTIMIZER

The string-based optimization I presented in the proposal is not very YAP friendly, If we can use YAP to transform expressions we can surely transform the expression into an optimized version easily. This not only makes the complete thing very uniform but also helps and reviews from YAP creators could help us better optimize the expressions using mathematical laws.

---

Archived

In my Proposal, I presented two approaches for expression optimizations. For In-depth analysis of the approach please read the proposal here. The approaches that I presented were based on

• String-based Optimization
• Using YAP for optimization

In String based optimization, We take an AST and traverse it assigning each node a string representation of what it computes and then. We optimize the root node representation using String optimization techniques and recreate the new expression with the newly optimized string.

For YAP based optimization I sent an email to Zach the maintainer of boost.YAP and he replied with the following code that could be used to optimize the expression of type A*X + B*X = X*(A+B). A thing to note here is that YAP is not primarily focused on optimizing expression rather it only provides a helpful limited set of functions to operate with the expression templates.

Approach provided by Zach is as follow:

auto expr = A * B + A * C;

It Capture your expression. You'll need your own expression template that defines operator==; see below.

Next,

template <boost::yap::expr_kind outer_op, boost::yap::expr_kind inner_op,
          typename Expr1, typename Expr2, typename Expr3, typename Expr4>
auto eval_considering_common_subexpressions(Expr1 && expr1, Expr2 && expr2, Expr3 && expr3, Expr4 && expr4);

Returns a 4-tuple of the evaluated given expressions. You want to generalise this to N expressions instead of 4.

struct xform_and_eval
{
    template <typename LExpr, typename RExpr>
    auto operator() (boost::yap::plus_tag, LExpr && lexpr, RExpr && rexpr) {
        if constexpr (LExpr::expr_kind == RExpr::expr_kind && boost::hana::size(lexpr.elements) == 2) {
            return eval_considering_common_subexpressions<boost::yap::expr_kind::plus, LExpr::expr_kind> (
                boost::yap::left(lexpr), boost::yap::right(lexpr), boost::yap::left(rexpr), boost::yap::right(rexpr));
        } else {
            return boost::yap::evaluate(lexpr) + boost::yap::evaluate(rexpr); // exprs should be forwarded
        }
    }
};

First we Match a top-level operator+, and look within it for binary ops (e.g. operator* containing common subexpressions.

If we find a common subexpression within plus_tag, we evaluate the expression using sub expressions. otherwise we forward the operands performaing + in between.

template <boost::yap::expr_kind_outer_op, boost::yap::expr_kind inner_op,
                 typename Expr1, typename Expr2, typename Expr3, typename Expr4>
auto eval_considering_common_subexpressions(Expr1 && expr1, Expr2 && expr2, Expr3 && expr3, Expr4 && expr4)
{
    auto const evaluated_expr1 = boost::yap::evaluate(expr1);

    bool const _1_eq_3 = expr1 == expr3;
    if (_1_eq_3) {
        return boost::yap::evaluate(
            boost::yap::make_expression(inner_op,
                evaluated_expr1,
                boost::yap::make_expression(outer_op, expr2, expr4)));
    } else {
        bool const _1_eq_4 = expr1 == expr4;
        if (_1_eq_4) {
            return boost::yap::evaluate(
                boost::yap::make_expression(inner_op,
                    evaluated_expr1,
                    boost::yap::make_expression(outer_op, expr2, expr3)));
        } else {
        }
    }
    
    return retval;
}

To make the code easier to write, you need to supply an operator== for your expression template. Without this, we would have to write a whole bunch of code to establish whether ExprN and ExprM were the same kind of expression, and then whether they had the same value. The operator should be defined for any two instantiations of your expression template, but should only return true if the two instantiations are the same type and have equal args.

There's an opportunity here to remove common subexpression evaluation from the evaluate() call below. You just need to use evaluated_expr1 instead of expr2 and/or expr4 if they're the same. Similarly, you could only evaluate expr2 when expr2 == expr4.

auto final_result = boost::yap::transform(expr, xform_and_eval);