#line 8493 "smat.w"

#line 5507 "smat.w"
#include "smat.h"
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <map>
#include <sstream>
#include <utility>
#include <vector>
#ifdef linux
#include <getopt.h>
#endif
#line 8493 "smat.w"

using namespace std;


#line 9165 "smat.w"
template <int n>
struct smat_numeric {
  enum {
    log2 = 1 + smat_numeric<n / 2>::log2,
    on_bit = (n & 1) + smat_numeric<n / 2>::on_bit,
    is_power_of_two = (on_bit == 1)
  };
};
template <> struct smat_numeric<2>
{ enum { log2 = 1, on_bit = 1, is_power_of_two = true }; };
template <> struct smat_numeric<1>
{ enum { log2 = 0, on_bit = 1, is_power_of_two = true }; };
template <> struct smat_numeric<0>
{ enum { on_bit = 0, is_power_of_two = false }; };
#line 8496 "smat.w"


#line 8441 "smat.w"
template <size_t wsize>
class swin {

  BOOST_STATIC_ASSERT(smat_numeric<wsize>::is_power_of_two);
  BOOST_STATIC_ASSERT(wsize >= 2);

  static const unsigned mask = wsize - 1;

  smat_inst v_[wsize];
  size_t start_;                // index of the window-top in v_.
  size_t end_;                  // index of the window-bottom in v_.
                                // window is empty if start_ == end_.
  size_t last_;                 // index of the last element if any

  size_t seqno_;                // sequence number at v_[start_].

  // slide the window forward by one element.
  void slide() { ++seqno_; ++start_; start_ &= mask; }

public:
  swin() : start_(0), end_(0), seqno_(0) {}

  size_t seqno() { return seqno_; }
  smat_inst& back() { return v_[last_]; }

  bool is_full() { return (start_ & mask) == ((end_ + 1) & mask); }
  bool is_empty() { return start_ == end_; }

  template <typename T>
  smat_inst& operator[](const T& s)
  { return v_[(s - seqno_ + start_) & mask]; }

  int read() {
    if (! v_[end_].read())
      return -1;
    last_ = end_;
    ++end_;
    end_ &= mask;
    return 0;
  }

  void write() {
    v_[start_].write();
    slide();
  }
};
#line 8497 "smat.w"


#line 8779 "smat.w"
static bool copy_propagation(swin<1024>& w,
                             const size_t& seq_from, const size_t& seq_to,
                             size_t nread, const unsigned& addr_src,
                             const unsigned& addr_dst)
{
  // make sure that addr_dst does not appear on dst.
  for (size_t s = seq_from + 1; s <= seq_to; ++s)
    {
      switch (w[s].code)
        {
        case SMAT_MOV: case SMAT_CMPL: case SMAT_MINUS: case SMAT_IAND:
        case SMAT_IOR: case SMAT_IXOR: case SMAT_IADD: case SMAT_ISUB:
        case SMAT_IMUL: case SMAT_IDIV: case SMAT_IMOD: case SMAT_ILSHIFT:
        case SMAT_IRSHIFT: case SMAT_CCTOR: case SMAT_BCTOR:
        case SMAT_INC: case SMAT_DEC: case SMAT_WRITE:
        case SMAT_AND: case SMAT_OR: case SMAT_XOR:
        case SMAT_ADD: case SMAT_SUB: case SMAT_MUL:
        case SMAT_DIV: case SMAT_MOD: case SMAT_LSHIFT: case SMAT_RSHIFT:
          if (w[s].dst == addr_dst)
            return false;
          break;
        }
    }

  for (size_t s = seq_from; s <= seq_to; ++s)
    {
      switch (w[s].code)
        {
        case SMAT_AND: case SMAT_OR: case SMAT_XOR: case SMAT_ADD:
        case SMAT_SUB: case SMAT_MUL: case SMAT_DIV: case SMAT_MOD:
        case SMAT_LSHIFT: case SMAT_RSHIFT:
        case SMAT_EQ: case SMAT_NEQ: case SMAT_GT: case SMAT_GEQ:
        case SMAT_LT: case SMAT_LEQ:
          if (w[s].src2 == addr_src)
            {
              w[s].src2 = addr_dst;
              if (--nread == 0)
                return true;
            }
          // fall through

        case SMAT_MOV: case SMAT_IADD: case SMAT_ISUB: case SMAT_IMUL:
        case SMAT_IDIV: case SMAT_IMOD: case SMAT_ILSHIFT:
        case SMAT_IRSHIFT: case SMAT_IAND: case SMAT_IOR: case SMAT_IXOR:
        case SMAT_MINUS: case SMAT_CMPL: case SMAT_INC: case SMAT_DEC:
        case SMAT_READ: case SMAT_IEQ: case SMAT_INEQ: case SMAT_IGT:
        case SMAT_IGEQ: case SMAT_ILT: case SMAT_ILEQ:
        case SMAT_CCTOR: case SMAT_BCTOR:
          if (w[s].src1 == addr_src)
            {
              w[s].src1 = addr_dst;
              if (--nread == 0)
                return true;
            }
          break;

        default:
          break;
        }
    }

  return true;
}
#line 8498 "smat.w"


#line 8677 "smat.w"
struct addr_history {
  size_t seqno_born, seqno_last, nwrite, nread;
  addr_history() : seqno_born(0), seqno_last(0), nwrite(0), nread(0) {}
};

#if __GNUC__ == 3 && 2 <= __GNUC_MINOR__
#include <ext/hash_map>

struct addr_hash {
  size_t operator()(unsigned a) const { return a / 4; }
};

typedef unsigned _Key;
typedef __gnu_cxx::hash_map<_Key, addr_history, addr_hash> Map;
typedef Map::iterator Iter;
#else
typedef unsigned _Key;
typedef map<_Key, addr_history> Map;
typedef Map::iterator Iter;
#endif

Map m;

static inline void addr_read(const _Key& addr, const addr_history& ah)
{
  pair<Iter, bool> p;
  p = m.insert(pair<_Key, addr_history>(addr, ah));
  p.first->second.seqno_last = ah.seqno_born;
  ++(p.first->second.nread);
}

static inline void addr_write(const _Key& addr, const addr_history& ah)
{
  pair<Iter, bool> p;
  p = m.insert(pair<_Key, addr_history>(addr, ah));
  p.first->second.seqno_last = ah.seqno_born;
  ++(p.first->second.nwrite);
}

static void addr_update(smat_inst& s, const addr_history& ah)
{
  switch (s.code)
    {
    case SMAT_MOV: case SMAT_IADD: case SMAT_ISUB: case SMAT_IMUL:
    case SMAT_IDIV: case SMAT_IMOD: case SMAT_ILSHIFT:
    case SMAT_IRSHIFT: case SMAT_IAND: case SMAT_IOR: case SMAT_IXOR:
    case SMAT_MINUS: case SMAT_CMPL: case SMAT_CCTOR: case SMAT_BCTOR:
      addr_read(s.src1, ah);
      addr_write(s.dst, ah);
      break;

    case SMAT_INC: case SMAT_DEC:
      addr_read(s.src1, ah);
      addr_write(s.src1, ah);
      break;

    case SMAT_READ: case SMAT_IEQ: case SMAT_INEQ: case SMAT_IGT:
    case SMAT_IGEQ: case SMAT_ILT: case SMAT_ILEQ:
      addr_read(s.src1, ah);
      break;

    case SMAT_WRITE:
      addr_write(s.src1, ah);
      break;

    case SMAT_AND: case SMAT_OR: case SMAT_XOR: case SMAT_ADD:
    case SMAT_SUB: case SMAT_MUL: case SMAT_DIV: case SMAT_MOD:
    case SMAT_LSHIFT: case SMAT_RSHIFT:
      addr_read(s.src1, ah);
      addr_read(s.src2, ah);
      addr_write(s.dst, ah);
      break;

    case SMAT_EQ: case SMAT_NEQ: case SMAT_GT: case SMAT_GEQ:
    case SMAT_LT: case SMAT_LEQ:
      addr_read(s.src1, ah);
      addr_read(s.src2, ah);
      break;

    case SMAT_DTOR: case SMAT_CTOR: case SMAT_NOP: case SMAT_FMARK:
      break;

    default:
      exit(EXIT_FAILURE);
      break;
    }
}
#line 8499 "smat.w"


#line 8634 "smat.w"
static void usage(char *progname, int status)
{
  if (status != 0)
    std::cerr << "Try `" << progname << " -h' for more information.\n";
  else
    {
      std::cout << "Usage: " << progname << " [OPTION]... < TRACEFILE\n\
Optimize a trace file.\n\
\n\
  -h        display this help and exit\n";
    }

  exit(status);
}
#line 8500 "smat.w"


struct addr_len {
  unsigned addr, len;
  int type;
  addr_len(unsigned addr_, unsigned len_, int type_)
    : addr(addr_), len(len_), type(type_) {}
};

int main(int argc, char *argv[])
{
  int c;
  addr_history ah;              // just a counter
  //smat_inst dtor_writer(SMAT_DTOR);
  swin<1024> w;
  multimap<unsigned, addr_len> dtor;

  ios::sync_with_stdio(false);
  cin.tie(0);

  
#line 8650 "smat.w"
  while ((c = getopt(argc, argv, "h")) != -1)
    {
      switch (c)
        {
        case 'h': usage(argv[0], EXIT_SUCCESS); break;
        default: usage(argv[0], EXIT_FAILURE); break;
        }
    }
  
  if (optind != argc)
    usage(argv[0], EXIT_FAILURE);
#line 8520 "smat.w"


  // sentinel
  dtor.insert(pair<unsigned, addr_len>(0xffffffffU, addr_len(0, 0, 0)));

  for (;; ++ah.seqno_born)
    {
      if (w.is_full())
        
#line 8606 "smat.w"
        {
          w.write();
          while (dtor.begin()->first <= w.seqno() - 1)
            {
              smat_inst::write_binary(SMAT_DTOR, dtor.begin()->second.type,
                dtor.begin()->second.len, dtor.begin()->second.addr, 0, 0);
              dtor.erase(dtor.begin());
            }
        }
#line 8528 "smat.w"


      if (w.read() < 0)
        break;

      if (w.back().code != SMAT_DTOR)
        {
          addr_update(w.back(), ah);
          continue;
        }

      // Destructing unregistered address?
      Iter i = m.find(w.back().src1);
      if (i == m.end())
        continue;

      addr_history& s = i->second;

      
#line 8569 "smat.w"
      if (w.seqno() <= s.seqno_born && s.nwrite == 1)
        {
          if (s.nread > 0 && (w[s.seqno_born].code == SMAT_CCTOR
                              || w[s.seqno_born].code == SMAT_MOV
                              || w[s.seqno_born].code == SMAT_BCTOR))
            {
              // copy propagation
              if (copy_propagation(w, s.seqno_born + 1, ah.seqno_born - 1,
                    s.nread, w[s.seqno_born].dst, w[s.seqno_born].src1))
                w[s.seqno_born].code = w.back().code = SMAT_NOP;
            }
          else if (s.nread == 1 && (w[s.seqno_last].code == SMAT_CCTOR
                                    || w[s.seqno_last].code == SMAT_MOV
                                    || w[s.seqno_last].code == SMAT_BCTOR))
            {
              // temporary object elimination
      
              // w[s.seqno_last].dst must be born at s.seqno_last.
              Iter j = m.find(w[s.seqno_last].dst);
              if (j != m.end() && j->second.seqno_born == s.seqno_last)
                {
                  w[s.seqno_born].dst = w[s.seqno_last].dst;
                  w[s.seqno_last].code = w.back().code = SMAT_NOP;
                  j->second.seqno_born = s.seqno_born;
                }
            }
          else
            
#line 8620 "smat.w"
            {
              if (s.seqno_last < ah.seqno_born - 1)
                {
                  dtor.insert(pair<unsigned, addr_len>
                              (max(s.seqno_last, w.seqno()),
                               addr_len(w.back().src1, w.back().len, w.back().type)));
                  w.back().code = SMAT_NOP;
                }
            }
#line 8596 "smat.w"
      
        }
      else
        
#line 8620 "smat.w"
        {
          if (s.seqno_last < ah.seqno_born - 1)
            {
              dtor.insert(pair<unsigned, addr_len>
                          (max(s.seqno_last, w.seqno()),
                           addr_len(w.back().src1, w.back().len, w.back().type)));
              w.back().code = SMAT_NOP;
            }
        }
#line 8599 "smat.w"
      
#line 8546 "smat.w"


      m.erase(i);
    }

  while (! w.is_empty())
    
#line 8606 "smat.w"
    {
      w.write();
      while (dtor.begin()->first <= w.seqno() - 1)
        {
          smat_inst::write_binary(SMAT_DTOR, dtor.begin()->second.type,
            dtor.begin()->second.len, dtor.begin()->second.addr, 0, 0);
          dtor.erase(dtor.begin());
        }
    }
#line 8552 "smat.w"


  return EXIT_SUCCESS;
}