Boost logo

Boost :

From: Maurizio Vitale (mav_at_[hidden])
Date: 2007-04-29 20:15:13


Ok, I painfully crawled my way to something that has the functionality I needed. The code attached does indeed compute the sum of all widths for expressions
involving a user defined integer and binary operations.

The good news are that the generated assembly is good (actually, as it is often the case with template metaprogramming is better than what I expected: remember
I wanted one addition when only one term has a run-time width, well I've got no additions, for this case where the compiler had all the information local).
This is to say that the following fragment:

  MARK ("B rt_width");
  int j = get_rt_width (b+i+c+b+b); b is 4 bit, compile-time; c is 8 bit, compile-time; i is 8 bit, run-time. Total width=28
  MARK ("E rt_width");

  std::cout << j << "\n";

Get's translated into:

#APP
        #### B rt_width
#NO_APP
        leaq 64(%rsp), %r13
        leaq 96(%rsp), %r12
        leaq 80(%rsp), %rbx
        leaq 16(%rsp), %rax
        movq %r13, 24(%rsp)
        movq %r12, 16(%rsp)
        movq %rbx, 8(%rsp)
        movq %rax, (%rsp)
#APP
        #### E rt_width
#NO_APP
        movl $28, %esi <-- Look me, no sums!
        movl $_ZSt4cout, %edi
        call _ZNSolsEi

On the not so bright side, there's more copying that I would have liked (the part between #### mark), but I haven't tracked down where they come from.

Now, enough with the good stuff. The code below, imo, sucks. It takes me two transforms and many backflips to compute what should be a very simple thing.
I'm not sure it is the right way to go about it. At some point I've also toyed with the idea of using a special evaluation context for this, rather than the two
transform.
Eric, which would be the way you'd have gone?
Is there a way to have a single transform?
[I've tried many variations, but it seemed like I could never have the type "blanket" in the transform covering both apply and call: when one was
type-happy the other was type-cold and vice-versa]

-----------------------------------------------------------------------------
#include <iostream>
#include <boost/xpressive/proto/proto.hpp>
#include <boost/xpressive/proto/context.hpp>
#include <boost/xpressive/proto/extends.hpp>
#include <boost/xpressive/proto/debug.hpp>
#include <boost/typeof/typeof.hpp>
#include <boost/typeof/std/ostream.hpp>
#include <boost/mpl/plus.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/contains.hpp>

using namespace boost;

struct run_time {};

struct my_domain : proto::domain<> {};

template <typename Expr>
struct my_expr : proto::extends<Expr, my_expr<Expr>, my_domain> {
  typedef proto::extends<Expr, my_expr<Expr>, my_domain> base_type;

  my_expr (Expr const& expr = Expr()) : base_type (expr) {};

  using base_type::operator =;

  typedef int result_type;

  operator result_type () const {
    return 10;
  }
};

namespace boost { namespace proto {
  template<typename Expr>
  struct generate<my_domain, Expr> {
    typedef my_expr<Expr> type;
      
    static type make (Expr const& expr) {
      return type (expr);
    }
  };
} } // end namespace boost::proto

template<typename T=run_time> struct number;

template<typename T>
std::ostream& operator << (std::ostream& os, const number<T> o);

template<typename T>
struct number {
  typedef T width;
  number () : m_data (0) {}
  number (int i) : m_data (i) {}
  friend std::ostream& operator << <> (std::ostream& os, const number<T> o);
  unsigned int m_data;
};

template<>
struct number<run_time> {
  typedef run_time width;
  number () : m_data (0) {}
  number (int w, int i) : m_data (i), m_width (w) {}
  friend std::ostream& operator << <> (std::ostream& os, const number<run_time> o);
  unsigned int m_data;
  unsigned int m_width;
};

template<typename T>
std::ostream& operator << (std::ostream& os, const number<T> o) { os << "~" << o.m_data << "~"; return os; }

template<template<typename,typename> class Op, typename A1, typename A2>
struct unless_run_time : mpl::if_<mpl::contains<mpl::vector<A1,A2>, run_time>, run_time, Op<A1,A2> > {};

template<typename Grammar>
struct binary_width
  : Grammar
{
  binary_width();

  template<typename Expr, typename State, typename Visitor>
  struct apply
  {
    typedef typename mpl::apply_wrap3<Grammar,Expr,State,Visitor>::type expr_type;
    typedef typename proto::result_of::left<expr_type>::type _1;
    typedef typename proto::result_of::right<expr_type>::type _2;

    typedef typename unless_run_time<mpl::plus, _1, _2>::type type;
  };
};

template<typename Grammar>
struct terminal_width
  : Grammar
{
  terminal_width();

  template<typename Expr, typename State, typename Visitor>
  struct apply
  {
    typedef typename proto::result_of::arg_c<Expr,0>::type number;
    typedef typename number::width type;
  };
};

using proto::_;

struct width_transform : proto::or_ <
  terminal_width<proto::terminal< number<_> > >,
  binary_width<proto::binary_expr<_, width_transform, width_transform> >
> {};

template<typename Grammar>
struct rt_binary_width
  : Grammar
{
  rt_binary_width();

  template<typename Expr, typename State, typename Visitor>
  struct apply
  {
    typedef int type;
  };

  template<typename Expr, typename State, typename Visitor>
  static typename apply<Expr,State,Visitor>::type
  call(Expr const &expr, State const &, Visitor &) {
    typedef typename proto::result_of::left<Expr>::type left;
    typedef typename proto::result_of::left<Expr>::type right;

    return get_rt_width(proto::left (expr)) + get_rt_width(proto::right (expr));
  }
};

template<typename Grammar>
struct rt_terminal_width
  : Grammar
{
  rt_terminal_width();

  template<typename Expr, typename State, typename Visitor>
  struct apply
  {
    typedef int type;
  };

  template<typename Expr, typename State, typename Visitor>
  static typename apply<Expr,State,Visitor>::type
  call(Expr const &expr, State const &, Visitor &) {
    return proto::arg (expr).m_width;
  }
};

struct rt_width_transform : proto::or_ <
  rt_terminal_width<proto::terminal< number<_> > >,
  rt_binary_width<proto::binary_expr<_, rt_width_transform, rt_width_transform> >
> {};

template<typename Expr>
struct width : width_transform::template apply<Expr, mpl::true_, mpl::void_>
{};

template<typename T>
struct aux {
  template<typename U>
  static int
  call (U) { return T::value; }
};

template<>
struct aux<run_time> {
  template<typename T>
  static int
  call (T e) {
    mpl::void_ null;
    return rt_width_transform::call (e, null, null); }
};

template<typename Expr>
int get_rt_width (Expr e) {
  return aux<typename width<Expr>::type >::call (e);
}

template<typename Expr>
int get_width (Expr e) {
  mpl::void_ null;
  return width<Expr>::type::value;
}

template<typename Expr>
struct my_context : proto::callable_context<const my_context<Expr> > {
  typedef int result_type; // later we'll compute this from Expr
};

int foo (int,int) { return 0; }

template<int N>
struct my_int : my_expr<typename proto::terminal<number<mpl::int_<N> > >::type >
{
  typedef number<mpl::int_<N> > number_type;
  typedef my_expr<typename proto::terminal<number_type>::type> expr_type;

  my_int () {}
  my_int (int i) : expr_type (expr_type::type::make (number_type (i))) {}

  template<typename Expr>
  my_int& operator = (const Expr& e) {
    proto::arg (*this).m_data = proto::eval(e, my_context<Expr> ());
    return *this;
  }
};

struct my_int_base : my_expr<proto::terminal<number<run_time> >::type >
{
  typedef number<run_time> number_type;
  typedef my_expr<proto::terminal<number_type>::type > expr_type;

  my_int_base () {}
  my_int_base (int w, int i) : expr_type (expr_type::type::make (number_type(w,i))) {}

  template<typename Expr>
  my_int_base& operator = (const Expr& e) {
    proto::arg (*this).m_data = proto::eval(e, my_context<Expr> ());
    return *this;
  }
};

#define MARK(s) __asm__ __volatile__ ("#### " s)

int main (int, char**) {
  my_int<4> b(3);
  my_int<8> c;

  my_int_base i(8,42);

  MARK ("B rt_width");
  int j = get_rt_width (b+i+c+b+b);
  MARK ("E rt_width");

  std::cout << j << "\n";

  std::cout << "bounds(b)=" << get_rt_width (b) << "\n";
  std::cout << "bounds(b+c)=" << get_rt_width (b+c) << "\n";
  std::cout << "bounds(i+i)=" << get_rt_width (i+i) << "\n";
  std::cout << "bounds(b+i+c+b+b)=" << get_rt_width (b+i+c+b+b) << "\n";
}


/// Local Variables:
/// mode:c++
/// comment-column:80
/// fill-column:160
/// compilation-read-command:nil
/// compile-command:"g++ -I. -oex4 ex4.cpp"
/// End:


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk