Runtime Optimization using variants

Working Optimizer could be found on vatiant-optimizer branch.

Due to limitations of constexpr in C++17 the compile-time expression optimizer we were building didn't worked, moreover the expression template library we are using Boost.YAP does not fully supported constexpr expressions. After trying many approaches we failed to create an optimizer that could do the optimization at compile time. Optimization at runtime was possible but I doubt if its really efficient to optimize and evaluate at runtime. Hence I am presenting a std::variant based optimization.

---

Introduction

Currently, I have made a small optimizer that optimizes only one type of expression as follow:

• a + a == 2*a

We assume that * overload is available with int and tensor::value_type. I have not added any check for its availability since most fundamental tensor::value_type (like int, float, complex) have such overload. In future we may add this check and if no such operator can be resolved we skip the optimization.

Working

The Idea behind std::variant based optimizer is our optimization transform returns a terminal<variant<Optimized_expr_t, Unoptimized_expr_t>> where terminal<T> represents that it is a terminal type in AST having T in terminal.

Following is the simple snippet from runtime_scalar_optimizer transform, Which builds and returns a new expression (possibly optimized) result.

struct runtime_scalar_optimizer{
    using namespace boost::yap;
    template <class Lexpr, class Rexpr>
        auto operator()(tag<expr_kind::plus>, Lexpr&& lexpr, Rexpr && rexpr){
        
        if constexpr(is_scalar_optimizable<Lexpr, Rexpr>::value){
            using optimized_t = decltype(make_expression<expr_kind::multiplies>(2,lexpr));
            using unoptimized_t = decltype(make_expression<expr_kind::plus>(rexpr,lexpr));
            if(std::addressof(lexpr) == std::addressof(rexpr)) {
                std::variant<optimized_t, unoptimized_t> result(optimized_t{lexpr});
                return std::move(result);
            }
            else{
                // Cannot optimize
                std::variant<optimized_t, unoptimized_t> 
                    result(unoptimized_t{lexpr, rexpr});
                return std::move(result);
            }

        }
        else{
            // Recurse to lexpr and rexpr
        }
    }
};

Modified Helper Transforms

The Expression that ever wants to optimize, it will have variant inside it regardless of whether optimization was a success or not. Calling out the helper transforms such as transform::get_extents{} are a bit difficult. We need to handle the terminal that is variant and propagate the transform inside the variant. This can be achieved via std::visit.

Consider this modified implementation of the transform::get_extents{}

struct get_extents{
    using namespace boost::yap;
    // Handled all other terminals.
    
    template <class Yes, class Not>
        auto operator()(expr_tag<expr_kind::terminal>, variant<Yes, No> && v){
        return std::visit(
            [this](auto &&subexpr){
                return transform(subexpr, *this); // Assume perfect forward
            }
            ,v); // Assume perfect forward
    }
};

The Idea behind the transform is that whenever we find a variant terminal we know that it will have at-least one valid subexpression inside of it. Since no optimization can change extents of tensors. We can be assured that return type of visit is same type and equal. In case of some transforms such at transform::at_index we return a variant from the visitor itself. For more information on how that works please check its source here(add).

Modified Evaluate

The optimization transform returns a expression within variant which cannot be evaluated by boost::yap::evaluate(). Hence I had to come up with my own evaluate transform that could work with such expressions.

Following is a simple snippet that shows the transform that evaluates such expressions.

struct evalute_with_variants{
  using namespace boost::yap;
  template <Term>
    decltype(auto) operator()(expr_tag<expr_kind::terminal>, Term&& t){
      return std::forward<Term>(t);
  }
  
    // Here is the specialization of terminal node which has variant inside it,
    // In this case also we write a visitor which dispatches out our transform
    // to its content.
    
  template <Op, Unop>
    decltype(auto) operator(expr_tag<expr_kind::terminal>, variant<Op, Unop>&& v){
      return std::visit([this](auto &&subexpr){
          return transform(subexpr, *this); // Assume perfect forward
      }, 
      v);
  }
    
    // Other overload goes here
};

Limitations

• It does the optimization at Runtime-time.
• Adds Compile-time overhead as variants are template heavy.
• User cannot define or invoke their own YAP transforms on tensor-expressions. They must be told to handle variants in their transforms.
• Does not optimizes in case of data_type mismatch.
• Does not optimizes with r-values as operands. We compare quality by address not by value.