#ifndef _AC_H_
#define _AC_H_

#include <utility>
#include <iostream>
#include <string>
#include <cassert>

#include <map>
#include <vector>
#include <set>

#include "indirect-omega.h"
#include "osstream.h"
#include "printing.h"
#include "int2string.h"
#include "ACvar.h"
#include "InPoly.h"
#include "TilingPlane.h"
#include "parameter.h"
#include "omint.h"
#include "smap.h"
#include "BoundingBox.h"
#include "errors.h"

/* how to represent MAXINT in the generated code */
#define MAXINT_STRING "STOPTIFU_MAXINT"

class ACStat;
class Block;
class Foreach;
class Megatile;
class OrderingConstraint;
class st_source;
class UpdateAndExecute;
class UpdateOnly;

typedef pair<int, int> intpair;

typedef struct {
  int rl, rindex, wl, windex;
  const intvector *d;
} subset_requirement;

typedef struct {
  smap_element const *read, *src;
  Relation readr, srcr;
  int delta_k;
  string varname;
} opt_read;

#ifndef DEBUG_AC 
#define DEBUG_AC AC::debug_level
#endif

#ifndef DEBUG_OR_VERBOSE_AC 
#define DEBUG_OR_VERBOSE_AC (DEBUG_AC || AC::verbose_level)
#endif

#define DPRINT(x) do { if (DEBUG_AC) cout << (x); } while (0) 
#define DPRINTLN(x) DPRINT(string(x) + '\n')
#define DBG(x) do { if (DEBUG_AC) { x; } } while (0)
#define DPRINT2(x) do { if (DEBUG_AC >= 2) cout << (x); } while (0) 
#define DPRINTLN2(x) DPRINT2(string(x) + '\n')
#define DBG2(x) do { if (DEBUG_AC >= 2) { x; } } while (0)
#define DPRINTV(x) do { if (DEBUG_OR_VERBOSE_AC) cout << (x); } while (0) 
#define DPRINTLNV(x) DPRINTV(string(x) + '\n')
#define DBGV(x) do { if (DEBUG_OR_VERBOSE_AC) { x; } } while (0)

static inline void fatal(string s, int e = 1) {
  fatal_error(s);
}

class AC {
 public:
  static int debug_level, verbose_level;
  static bool skip_megatile_verification, greenlight, force_big;
  static int allow_any_shape, coarse_interleaving, min_domain_size,
    rr_aggressiveness, stats_level;
  static ostringstream *stats_stream;
  static set<int> dead_arrays;

  virtual ~AC() {}

  virtual void print(ostream &o, int depth = 0) const = 0;
  virtual void subprint(ostream &o, int depth = 0) const;
  static void clear_dead_array_on_exit() { dead_arrays.clear(); }
  static void dead_array_on_exit(int a) { dead_arrays.insert(a); }
  virtual AC *cons(AC *) { fatal("cons unimplemented"); return 0; }
  virtual AC *analyze();
  virtual void seqanalyze(int &s, int &i, llist<AC *> *encl);
  virtual void fix_parent(AC *p);
  virtual AC *concretize();

  static void * (*translator)(const AC *);
  virtual void *translate() const {
    return (translator == NULL) ? NULL : (*translator)(this);
  }
  static void *translate(const AC *x) {
    return (translator == NULL) ? NULL : (*translator)(x);
  }

  /* Reordering optimizations */
  virtual bool tile_a_loop(llist<OrderingConstraint *> *oc);
  virtual bool megatile(llist<OrderingConstraint *> *oc);
  bool do_not_touch() const;

  /* helpers, utils */
  bool find_simply_nested_Foreach(Foreach *& f);
  virtual void find_Foreaches(llist<Foreach *> *&l, bool tiled_only = false);
  virtual AC *find_tiled(llist<Megatile *> *&l);
  virtual void find_ACStats(llist<const ACStat *> *&l) const;
  static void find_ACStats(const AC *a, llist<const ACStat *> *&l) {
    if (a != NULL)
      a->find_ACStats(l);
  }
  Foreach *enclosing_Foreach();
  virtual bool is_Block() { return false; }
  virtual bool is_Foreach() { return false; }
  virtual bool is_tiled_Foreach() { return false; }
  virtual int highest_arity_iteration_space() const { return 0; }
  virtual Block *find_block_which_stmt_is_in(AC *s);

  /* Do a DFS and return the number of loops in the first megatile found. */
  virtual int num_loops_in_megatile() const { return 0; }

  /* memory management */
  virtual void free_all() { delete this; }

  AC *parent;

  int seq() const { return s; }
  int seqindex() const { return si; }
  
  bool enclosed_by(AC *f) const { return contains(enclosing, f); }

 public:
  string source_code_location;
 protected:
  llist<AC *> *enclosing;
  int s;  /* sequence number */
  int si; /* position in that sequence */
};

class ACDecl : public AC {
 public:
  ACDecl(ACvar *v_) : v(v_) {}

  static void * (*translator)(const ACDecl *);
  virtual void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    v->type()->print(o);
    o << ' ';
    v->print(o);
    o << ';' << endl;
  }

  ACvar *v;
};

class ACexpr : public AC {
 private:
  const Ty *t;

 public:
  ACexpr() : t(NULL) {}
  ACexpr(const Ty *t) : t(t) {}

  const Ty *type() const { return t; }

  virtual int asInt() const { fatal("Not an integer"); return 0; }
  virtual bool isConstant() const { return false; } 
  virtual bool zerop() const { return false; } 
  virtual bool onep() const { return false; } 

  static void * (*translator)(const ACexpr *);
  virtual void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

class ACexprStmt : public AC {
 public:
  ACexpr *e;
  
  ACexprStmt(ACexpr *e) : e(e) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    e->print(o, depth);
    o << ';' << endl;
  }

  static void * (*translator)(const ACexpr *);
  virtual void *translate() const {
    return (translator == NULL) ? e->translate() : (*translator)(e);
  }
};

class ACmyproc : public ACexpr {
 public:
  ACmyproc() : ACexpr(Ty::intTy) {}
  void print(ostream &o, int depth = 0) const { o << "MYPROC"; }

  static void * (*translator)();
  void *translate() const {
    return (translator == NULL) ? ACexpr::translate() : (*translator)();
  }
};

class ACnumprocs : public ACexpr {
 public:
  ACnumprocs() : ACexpr(Ty::intTy) {}
  void print(ostream &o, int depth = 0) const { o << "PROCS"; }

  static void * (*translator)();
  void *translate() const {
    return (translator == NULL) ? ACexpr::translate() : (*translator)();
  }
};

class ACconstant : public ACexpr {
 public:
  int k;

  ACconstant(int k_) : ACexpr(Ty::intTy), k(k_) {}
  void print(ostream &o, int depth = 0) const { o << k; }
  int asInt() const { return k; }
  bool isConstant() const { return true; } 
  bool zerop() const { return (k == 0); } 
  bool onep() const { return (k == 1); } 

  static void * (*translator)(int);
  void *translate() const {
    return (translator == NULL) ? ACexpr::translate() : (*translator)(k);
  }
};

class ACvariable : public ACexpr {
 public:
  const ACvar *v;

  ACvariable(const ACvar *v_, const Ty *t = NULL) :
    ACexpr(t == NULL ? v_->type() : t), v(v_) {}
  void print(ostream &o, int depth = 0) const { v->print(o); }

  static void * (*translator)(const ACvariable *v);
  void *translate() const {
    return (translator == NULL) ? ACexpr::translate() : (*translator)(this);
  }
};

class BinaryExpr : public ACexpr {
 public:
  ACexpr *x, *y;
  /* If op is += or -= or similar then x must have no side-effects. */
  const string op;

  BinaryExpr(ACexpr *x_, const string op_, ACexpr *y_, Ty *t = NULL) :
    ACexpr(t), x(x_), y(y_), op(op_) {}

  void print(ostream &o, int depth = 0) const {
    o << '(';
    x->print(o);
    o << ' ' << op << ' ';
    y->print(o);
    o << ')';
  }
  static void * (*translator)(const BinaryExpr *v);
  void *translate() const {
    return (translator == NULL) ? ACexpr::translate() : (*translator)(this);
  }
};

class UnaryExpr : public ACexpr {
 public:
  ACexpr *y;
  const string op;

  UnaryExpr(const string op_, ACexpr *y_, Ty *t = NULL) :
    ACexpr(t), y(y_), op(op_) {}

  void print(ostream &o, int depth = 0) const {
    o << '(' << op;
    y->print(o);
    o << ')';
  }

  static void * (*translator)(const UnaryExpr *v);
  void *translate() const {
    return (translator == NULL) ? ACexpr::translate() : (*translator)(this);
  }
};

class FuncallExpr : public ACexpr {
 public:
  const string fn;
  llist<ACexpr *> *args;

  FuncallExpr(const string fn, llist<ACexpr *> *args, Ty *t = NULL) :
    ACexpr(t), fn(fn), args(args) {}

  void print(ostream &o, int depth = 0) const {
    o << fn << "(";
    bool first = true;
    foreach (e, llist<ACexpr *>, *args) {
      if (first)
	first = false;
      else
	o << ", ";
      (*e)->print(o);
    }    
    o << ")";
  }

  static void * (*translator)(const FuncallExpr *);
  void *translate() const {
    return (translator == NULL) ? ACexpr::translate() : (*translator)(this);
  }
};

static inline ACexpr *boolfuncall(string fn, llist<ACexpr *> *args)
{
  return new FuncallExpr(fn, args, Ty::boolTy);
}

static inline ACexpr *boolexpr(ACexpr *x, string op, ACexpr *y)
{
  return new BinaryExpr(x, op, y, Ty::boolTy);
}
static inline ACexpr *boolexpr(string op, ACexpr *y)
{
  return new UnaryExpr(op, y, Ty::boolTy);
}
static inline ACexpr *boolexpr(const ACvar *x, string op, const ACvar *y)
{
  return boolexpr(new ACvariable(x), op, new ACvariable(y));
}
static inline ACexpr *boolexpr(const ACvar *x, string op, ACexpr *y)
{
  return boolexpr(new ACvariable(x), op, y);
}
static inline ACexpr *boolexpr(ACexpr *x, string op, int y)
{
  return boolexpr(x, op, new ACconstant(y));
}
static inline ACexpr *boolexpr(const ACvar *x, string op, int y)
{
  return boolexpr(new ACvariable(x), op, y);
}

static inline ACexpr *intexpr(ACexpr *x, string op, ACexpr *y)
{
  return new BinaryExpr(x, op, y, Ty::intTy);
}
static inline ACexpr *intexpr(const ACvar *x, string op, const ACvar *y)
{
  return intexpr(new ACvariable(x), op, new ACvariable(y));
}
static inline ACexpr *intexpr(const ACvar *x, string op, ACexpr *y)
{
  return intexpr(new ACvariable(x), op, y);
}
static inline ACexpr *intexpr(const ACvar *x, string op, int y)
{
  return intexpr(new ACvariable(x), op, new ACconstant(y));
}
static inline ACexpr *intexpr(ACexpr *x, string op, int y)
{
  return intexpr(x, op, new ACconstant(y));
}
static inline ACexpr *makesum(ACexpr *x, int y)
{
  return (y == 0) ? x : intexpr(x, "+", y);
}
static inline ACexpr *makesum(ACexpr *x, ACexpr *y)
{
  return x->zerop() ?
    y :
    (y->zerop() ? x : intexpr(x, "+", y));
}
static inline ACexpr *makeproduct(ACexpr *x, ACexpr *y)
{
  if (y->zerop())
    return y;
  else if (x->zerop() || y->onep())
    return x;
  else
    return (x->onep() ? y : intexpr(x, "*", y));
}
static inline ACexpr *makeproduct(ACexpr *x, int y)
{
  return (y == 0) ?
    new ACconstant(0) :
    ((y == 1) ? x : intexpr(x, "*", y));
}
static inline ACexpr *makeproduct(ACvar *x, int y)
{
  return makeproduct(new ACvariable(x), y);
}

// An opaque expression.
class Opaque : public ACexpr {
 public:
  Opaque(llist<ACvar *> *used, const char *desc, Ty *t = NULL) :
    ACexpr(t), u(used), d(desc), shouldfree(false) {}
  Opaque(const char *desc, Ty *t = NULL) :
    ACexpr(t), u(NULL), d(desc), shouldfree(false) {}
  Opaque(string s, Ty *t = NULL) : ACexpr(t), u(NULL) {
    const char *desc = s.c_str();
    d = new char [strlen(desc) + 1];
    strcpy((char *) d, desc);
    shouldfree = true;
  }
  ~Opaque() { if (shouldfree) delete[] d; }

  void print(ostream &o, int depth = 0) const {
    o << d;
  }
  const char *c_str() const { return d; }

 private:
  llist<ACvar *> *u;
  const char *d;
  bool shouldfree;
};

// An opaque statement.
class OpaqueStmt : public AC {
 public:
  OpaqueStmt(const char *s) : d(s), shouldfree(false) {}
  OpaqueStmt(string s) {
    const char *desc = s.c_str();
    d = new char [strlen(desc) + 1];
    strcpy((char *) d, desc);
    shouldfree = true;
  }
  ~OpaqueStmt() { if (shouldfree) delete[] d; }

  static void * (*translator)(const OpaqueStmt *v);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    o << d << ';' << endl;
  }

 private:
  const char *d;
  bool shouldfree;
};

class FieldOfHeadInterval : public ACexpr {
 public:
  ACexpr *s;
  const char *f;

  FieldOfHeadInterval(ACexpr *src, const char *field, Ty *t_ = Ty::intTy) :
    ACexpr(t_), s(src), f(field) {}
  FieldOfHeadInterval(ACvar *src, const char *field, Ty *t_ = Ty::intTy) :
    ACexpr(t_), s(new ACvariable(src)), f(field) {}

  void print(ostream &o, int depth = 0) const {
    o << "head_interval(";
    s->print(o);
    o << ")->" << f;
  }
};

class SizedArray : public AC {
 public:
  Ty *subtype;
  string flags;
  llist<ACexpr *> *exprs;
  bool constants;
  int size;
  ACvar *v;

  SizedArray(string name, Ty *pt, Ty *t, string fl, int size) :
    subtype(t), flags(fl), exprs(NULL), size(size)
    { v = new ACvar(name, pt); }
  SizedArray(string name, Ty *pt, Ty *t, string fl, llist<ACexpr *> *l,
	     bool c = true) :
    subtype(t), flags(fl), exprs(l), constants(c), size(l->size())
    { v = new ACvar(name, pt); }
  SizedArray(string name, Ty *pt, Ty *t, string fl, llist<int> *l,
	     bool c = true) :
    subtype(t), flags(fl), constants(c), size(l->size()) {
    v = new ACvar(name, pt);
    for (exprs = NULL; l != NULL; l = l->tail())
      push(exprs, (ACexpr *) new ACconstant(l->front()));
    exprs = dreverse(exprs);
  }

  ACexpr *index(int i) { return (*exprs)[i]; }

  void print(ostream &o, int depth = 0) const {
    const string &vs = v->to_string();
    indent2(o, depth);
    o << flags;
    if (flags != "")
      o << ' ';
    o << subtype->to_string() << ' ' << vs << "[" << size << "]";
    if (exprs == NULL)
      /* No initialization */
      o << ';' << endl;
    else if (constants) {
      /* initialize elements in the decl */
      o << " = {";
      for (llist<ACexpr *> *e = exprs; e != NULL; e = e->tail()) {
	e->front()->print(o);
	if (e->tail() != NULL)
	  o << ", ";
      }
      o << "};" << endl;
    } else {
      /* initialize elements separately */
      o << ';' << endl;
      int i = 0;
      for (llist<ACexpr *> *e = exprs; e != NULL; e = e->tail()) {
	o << vs << "[" << i++ << "] = ";
	e->front()->print(o);
	o << "; ";
      }
      o << endl;
    }
  }
};

class IndexExpr : public ACexpr {
 public:
  ACexpr *a, *i; /* a[i] */

  IndexExpr(ACexpr *a, ACexpr *i) :
    ACexpr(a->type()->indexed_type()), a(a), i(i) {}
  IndexExpr(ACexpr *a, ACvar *v) :
    ACexpr(a->type()->indexed_type()), a(a), i(new ACvariable(v)) {}
  IndexExpr(ACexpr *a, int x) :
    ACexpr(a->type()->indexed_type()), a(a), i(new ACconstant(x)) {}
  IndexExpr(ACvar *a, ACexpr *i) :
    ACexpr(a->type()->indexed_type()), a(new ACvariable(a)), i(i) {}
  IndexExpr(ACvar *a, ACvar *v) :
    ACexpr(a->type()->indexed_type()), a(new ACvariable(a)),
    i(new ACvariable(v)) {}
  IndexExpr(ACvar *a, int x) :
    ACexpr(a->type()->indexed_type()), a(new ACvariable(a)),
    i(new ACconstant(x)) {}

  static void * (*translator)(const IndexExpr *);
  void *translate() const {
    return
      (translator == NULL) ? ACexpr::translate() : (*translator)(this);
  }

  void print(ostream &o, int depth = 0) const {
    a->print(o);
    o << '[';
    i->print(o);
    o << ']';
  }
};

/*
class  : public ACexpr {
 public:
  ACvar *

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    o << "head_interval(" << s->to_string() << ")." << f;
  }
};
*/

class GatherStats : public AC {
 public:
  GatherStats(AC *a, string label) : a(a), label(label) {}

  static void * (*translator)(const GatherStats *);
  void *translate() const {
    return
      (translator == NULL) ? AC::translate() : (*translator)(this);
  }

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    subprint(o, depth);
  }    
  void subprint(ostream &o, int depth = 0) const {
    o << '{' << endl;
    ++depth;
    indent2(o, depth);
    o << "/* begin gather stats */" << endl;
    if (label != "") {
      indent2(o, depth);
      o << label << endl;
    }
    indent2(o, depth);
    a->print(o, depth);
    indent2(o, depth);
    o << "/* end gather stats */" << endl;
    --depth;
    indent2(o, depth);
    o << '}' << endl;
  }

  AC *a;
  string label;
};


class Block : public AC {
 public:
  Block() : stmts(NULL), decls(NULL) {}
  Block(string s) : stmts(NULL), decls(NULL) { source_code_location = s; }

  AC *cons(AC *x) { stmts = ::cons(x, stmts); return this; }
  AC *append(AC *x) { stmts = extend(stmts, ::cons(x)); return this; }
  AC *append(llist<AC *> *l) { stmts = extend(stmts, l); return this; }
  ACvar *temp(const char *s, const Ty *t) {
    ACvar *v = new ACvar(s, t);
    decls = ::cons((AC *) new ACDecl(v), decls);
    return v;
  } 
  ACvar *temp(const string *s, const Ty *t) { 
    ACvar *v = new ACvar(s, t);
    decls = ::cons((AC *) new ACDecl(v), decls);
    return v;
  }
  inline ACvar *temp(const string &s, const Ty *t) { return temp(new string(s), t); }

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    subprint(o, depth);
  }    
  void subprint(ostream &o, int depth = 0) const {
    o << '{' << endl;
    for (llist<AC *> const *i = decls; i != NULL; i = i->tail())
      i->front()->print(o, depth + 1);
    for (llist<AC *> const *i = stmts; i != NULL; i = i->tail())
      i->front()->print(o, depth + 1);
    indent2(o, depth);
    o << '}' << endl;
  }

  static void * (*translator)(const llist<AC *> *, const llist<AC *> *);
  void *translate() const {
    return
      (translator == NULL) ? AC::translate() : (*translator)(decls, stmts);
  }

  void free_all() {
    while (stmts != NULL) {
      stmts->front()->free_all();
      stmts = stmts->free();
    }
    while (decls != NULL) {
      decls->front()->free_all();
      decls = decls->free();
    }
    delete this;
  }

  void fix_parent(AC *p);
  void seqanalyze(int &s, int &i, llist<AC *> *encl);
  llist<AC *> *statements() { return stmts; }
  virtual bool is_Block() { return true; }

  bool tile_a_loop(llist<OrderingConstraint *> *oc);
  bool megatile(llist<OrderingConstraint *> *oc);
  void find_Foreaches(llist<Foreach *> * &l, bool tiled_only = false);
  AC *find_tiled(llist<Megatile *> *&l);
  void find_ACStats(llist<const ACStat *> *&l) const;
  int highest_arity_iteration_space() const;
  Block *find_block_which_stmt_is_in(AC *s);
  int num_loops_in_megatile() const { 
    int n = 0;
    for (llist<AC *> const *i = stmts; i != NULL; i = i->tail())
      if ((n = i->front()->num_loops_in_megatile()) > 0)
	break;
    return n;
  }

  int find_stmt(AC *s) const;
  void replace_stmt(int i, AC *s) { (*stmts)[i] = s; }
  void remove_stmt(AC *s) { remove(s, stmts); }

  AC *concretize();

 private:
  llist<AC *> *stmts;
  llist<AC *> *decls;
};

class ConstructTempArray : public ACexpr {
 public:
  Ty *t;
  int dim;

  ConstructTempArray(Ty *t, int dim) : ACexpr(t), t(t), dim(dim) {}

  static void * (*translator)(const ConstructTempArray *);
  void *translate() const {
    return (translator == NULL) ? ACexpr::translate() : (*translator)(this);
  }
  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    o << "construct " << dim << "D temp" << endl;
  }
};


class DestructTempArray : public AC {
 public:
  Ty *t;
  int dim;
  ACvar *x;

  DestructTempArray(ACvar *x, Ty *t, int dim) : t(t), dim(dim), x(x) {}

  void print(ostream &o, int depth = 0) const {
    const string &xs = x->to_string();
    indent2(o, depth);
    o << "free " << xs << " (" << dim << "D temp)" << endl;
  }

  static void * (*translator)(const DestructTempArray *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }

};

// static inline AC * nop() { return new Block(); }

class ReadWrite : public AC {
  /* there are several forms:
     v = a;    // Copy
     v = a[p]; // Read
     v = a[s]; // Read
     a[p] = v; // Write
     a[s] = v; // Write
     v = RHS;  // Write, where RHS is opaque
  */
 public:
  ReadWrite() {}
  ReadWrite(ACvar *v_, ACvar *a_, llist<InPoly *> *p_) :
    v(v_), a(a_), p(p_), RHS(NULL) {}
  ReadWrite(ACvar *v_, ACvar *a_, string &s_) :
    v(v_), a(a_), p(NULL), RHS(NULL), s(s_) {}
  ReadWrite(ACvar *v_, AC *RHS_) :
    v(v_), a(NULL), p(NULL), RHS(RHS_) {}
 protected:
  ACvar *v, *a;
  llist<InPoly *> *p;
  AC *RHS;
  string s;
};

class Copy : public ReadWrite {
 public:
  Copy() {}
  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    v->print(o);
    o << " = ";
    a->print(o);
    o << ';' << endl;
  }
};

class Read : public ReadWrite {
 public:
  Read(ACvar *v, ACvar *a, InPoly *p) : ReadWrite(v, a, ::cons(p)) {}
  Read(ACvar *v, ACvar *a, string s) : ReadWrite(v, a, s) {}
  Read(ACvar *v, ACvar *a, llist<InPoly *> *ps) : ReadWrite(v, a, ps) {}
  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    v->print(o);
    o << " = ";
    a->print(o);
    o << '[';
    if (p == NULL)
      o << s;
    else
      ::print(p, o);
    o << ']';
    o << ';' << endl;
  }
};

class Write : public ReadWrite {
 public:
  Write(ACvar *v, llist<ACvar *> *used, const char *description) :
    ReadWrite(v, new Opaque(used, description)) {}
  Write(ACvar *a, llist<InPoly *> *ps, ACvar *v) : ReadWrite(v, a, ps) {}
  Write(ACvar *a, string s, ACvar *v) : ReadWrite(v, a, s) {}
  Write(ACvar *a, InPoly *p, ACvar *v) : ReadWrite(v, a, ::cons(p)) {}
  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    if (RHS == NULL) {
      a->print(o);
      o << '[';
      if (p == NULL)
	o << s;
      else
	::print(p, o);
      o << ']';
      o << " = ";
      v->print(o);
    } else {
      v->print(o);
      o << " = ";
      RHS->print(o);
    }
    o << ';' << endl;
  }
};

class Foreach : public AC {
 public:
  Foreach(ACvar *p_, ACvar *D_, AC *b, bool o, bool r, bool par, string s) :
    p(p_), D(D_), body(b), ordered(o), rectangular(r), parallel(par),
    arity_including_nested_loops(-1), before_tile0(NULL), before_GT(NULL),
    tiled(false), do_not_tile(false)
    { source_code_location = s; }
  Foreach(ACvar *p_, ACvar *D_, AC *b, bool o, string s) :
    p(p_), D(D_), body(b), ordered(o), rectangular(true), parallel(false),
    arity_including_nested_loops(-1), before_tile0(NULL), before_GT(NULL),
    tiled(false), do_not_tile(false) 
    { source_code_location = s; }

  void print(ostream &o, int depth = 0) const;
  void fix_parent(AC *p);
  void seqanalyze(int &s, int &i, llist<AC *> *encl);

  bool select_tile(llist<OrderingConstraint *> *oc);
  void find_Foreaches(llist<Foreach *> * &l, bool tiled_only = false);
  AC *find_tiled(llist<Megatile *> *&l);
  void find_ACStats(llist<const ACStat *> *&l) const;
  bool is_Foreach() { return true; }
  bool is_tiled_Foreach() { return tiled; }
  bool nesting_allows_tiling();
  bool tile_a_loop(llist<OrderingConstraint *> *oc);

  inline void adjoin_to_junk_pre(int n) {
    if (n != 0)
      junk_pre.insert(n);
  }
  inline void adjoin_to_junk_post(int n) {
    if (n != 0)
      junk_post.insert(n);
  }
  inline bool was_junk_before_this(int arr) {
    return (junk_pre.find(arr) != junk_pre.end());
  }
  inline bool will_be_junk_after_this(int arr) {
    return (junk_post.find(arr) != junk_post.end());
  }

  int arity() const { return p->arity(); }
  bool is_rectangular() const { return rectangular; }
  bool is_ordered() const { return ordered; }
  int highest_arity_iteration_space() const {
    if (arity_including_nested_loops > 0)
      return arity_including_nested_loops;
    else
      return arity_including_nested_loops =
	arity() + body->highest_arity_iteration_space();
  }

  AC *concretize();
  void compute_concrete_tiles(Block *b, Block *cleanup, ACvar *ai,
			      ACvar *bestcase, ACvar *z, bool first);

  static void * (*translator)(const Foreach *f, const ACvar *p,
			      const ACvar *D, const AC *body);
  void *translate() const {
    return (translator == NULL) ?
      AC::translate() :
      (*translator)(this, p, D, body);
  }

  friend class Megatile;
  friend class UpdateAndExecute;

 private:
  void permute_planes(llist<int> *&p);
  intvector *mapping(intvector const *);
  void show_mapping();
  void show_bundles();
  void select_steps();
  void select_lines();
  bool select_register_tile(llist<OrderingConstraint *> *oc);
  bool order_register_tile(llist<OrderingConstraint *> *oc,
			   Relation been_done);

  Relation tiles_prior_to_tile0() const;
  Relation tiles_prior_to_GT(Free_Var_Decl **a) const;
  /* The next group of methods are not to be used on induced tilings. */
  bool is_within_bundle0(intvector const *v);
  Relation bundles_prior_to_bundle0() const;
  Relation tiles_prior_to_tile(int x) const; // unused
  Relation *halfline_in_bundle0(intvector const *z, int q = 0);
  Relation *antihalfline_in_bundle0(intvector const *z, int q = 0);
  bool must_be_subset(Relation s, Relation t);

  intvector const *along() const { return (*steps)[IS_arity - 1]; }
  bool steps_are_axis_aligned() const;
  BoundingBox bb() const {
    BoundingBox b;
    for (int i = 0; i < k; i++)
      b.insert(s[i]);
    return b;
  }
  bool tile_is_rectangular() const { return bb().volume() == k; }

  void compute_concrete_tiles(Block *b, const string &ai,
			      ACvar *bestcase, ACvar *z);
  UpdateAndExecute *update_pt_and_execute(const intvector *new_v,
					  const intvector *v);
  UpdateOnly *update_pt_only(const intvector *new_v, const intvector *v);

 public:
  Relation generic_translate(Relation r, Free_Var_Decl **a) const;

 private:
  // foreach (p in D) body
  ACvar *p;
  ACvar *D;
  AC *body;

  bool ordered, rectangular, parallel;
  mutable int arity_including_nested_loops;
  mutable Relation *before_tile0; /* cached result of tiles_prior_to_tile0() */
  mutable Relation *before_GT; /* cached result of tiles_prior_to_GT() */

 public:
  bool tiled, do_not_tile, induced;
  int IS_arity; /* arity of iteration space tiled */

  /* The tile space has the same arity as the IS being tiled.  We go
     through tile space in "C" order, i.e., last index varies fastest.
     To do node (x_0, ..., x_{n-1}) of the tile space, we do the nodes
     of the original loop specified by s, in order, offset by the
     sum over i of x_i times steps_i.  See also show_mappings().
  */

  llist<TilingPlane *> *planes;
  llist<int> *widths; /* requested widths --- for actual widths, see steps */
  llist<intvector *> *steps; /* How to move from one tile/bundle to the next */
  llist<intvector *> *lines; /* points in the register tile */
  int unroll; /* 0 means none, 1 means the inner loop is doubled, etc. */
  int k; /* size of register tile (= length of lines and of s) */
  /* The nodes in the canonical tile (also known as tile 0) */
  intvector **s;

  set<int> junk_pre; /* arrays that can be treated as junk upon entry */
  set<int> junk_post; /* arrays that can be assumed to be unread after exit */
};

class Megatile : public AC {
 private:
  llist<Foreach *> *loops;
  llist<int> *m; /* alternating: loop #, index into that loop's s[] */
  int n; /* number of loops */

 public:
  Megatile(Foreach *f);
  ~Megatile();

  int arity() const { return (loops == NULL) ? 0 : loops->front()->IS_arity; }
  void find_Foreaches(llist<Foreach *> * &l, bool tiled_only = false);
  AC *find_tiled(llist<Megatile *> *&l);
  void find_ACStats(llist<const ACStat *> *&l) const;

  bool try_reorder(llist<AC *> *&c, llist<OrderingConstraint *> *oc);
  bool merge(AC *x, llist<OrderingConstraint *> *oc);
 private:
  bool reshape_induced_tile(Foreach *f, llist<OrderingConstraint *> *oc,
			    llist<int> *&new_m,
			    llist<Foreach *> *&new_loops,
			    vector<Relation> *induced_ready);
  bool calculate_steps(Foreach *f, llist<OrderingConstraint *> *oc,
		       llist<int> *&new_m,
		       llist<Foreach *> *&new_loops);
  bool calculate_step(Foreach *f, int j,
		      llist<OrderingConstraint *> *oc,
		      llist<int> *&new_m, llist<Foreach *> *&new_loops);
  bool find_first_induced_in_offset_tile(Foreach *f, int j,
					 llist<OrderingConstraint *> *oc,
					 intvector *&v,
					 llist<int> *&new_m,
					 llist<Foreach *> *&new_loops);
  bool induce_tile0(Foreach *f, llist<OrderingConstraint *> *oc,
		    llist<int> *&new_m, llist<Foreach *> *&new_loops,
		    vector<Relation> *induced_ready = NULL);
  bool get_first_candidate(Relation candidates,
			   Relation &been_done,
			   llist<OrderingConstraint *> *oc,
			   intvector **first);
  bool add_candidates(Foreach *f, Relation candidates,
		      Relation &been_done, llist<OrderingConstraint *> *oc,
		      llist<int> *&new_order);

  bool induce_tile(Foreach *f, llist<OrderingConstraint *> *oc,
		   intvector *offset, intvector **first,
		   llist<int> *&new_m, llist<Foreach *> *&new_loops,
		   vector<Relation> *induced_ready = NULL,
		   llist<intvector *> *select_from = NULL);
  bool legal_everywhere(Foreach *f, llist<OrderingConstraint *> *oc,
			llist<int> *new_m, llist<Foreach *> *new_loops);
  bool verify(Foreach *f, llist<OrderingConstraint *> *oc,
	      llist<int> *new_m, llist<Foreach *> *new_loops);
  Relation tiles_required(int l, intvector *p,
			  map< int, map<int, llist<OrderingConstraint *> * > > &ocf);

  bool parallelize(Foreach *f, llist<OrderingConstraint *> *oc,
		   llist<int> *new_m, llist<Foreach *> *new_loops);
  AC *pipeline_parallel_start_bundle(const ACvar *z, bool zrect,
				     ACvar **ti, Block *b);
  AC *pipeline_parallel_end_bundle();
  AC *create_and_broadcast_parstruct_array(Block *, ACvar *);
  ACvar *parstruct_array;
  int parstruct_eltsize;
  map<int, ACvar *> parstruct_array_stride;
  ACvar *progress_indicator;
  map<const intvector *, const ACvar *> *other_bundles_progress;
  Opaque *index_parstruct_array(ACvar **ti, const intvector *v,
				int offset) const;
  Opaque *index_parstruct_array1(ACvar **ti, int x, int offset) const;
  Opaque *deref_parstruct_array1(ACvar **ti, int x, int offset) const;
  Opaque *index_parstruct_array2(ACvar **ti, int x, int y, int offset) const;
  Opaque *deref_parstruct_array2(ACvar **ti, int x, int y, int offset) const;
  AC *set_progress_indicator(ACexpr *e, bool fence = true) const;
  AC *set_progress_indicator(ACvar *v, bool fence = true) const {
    return set_progress_indicator(new ACvariable(v), fence);
  }
  AC *set_progress_indicator(const int n, bool fence = true) const {
    return set_progress_indicator(new ACconstant(n), fence);
  }

  bool add(Foreach *f, llist<int> *new_m, llist<Foreach *> *new_loops);
  void ts_next_tile_within_bundle(Block *b); /* in storage.cc */
  size_t number_of_ts_arrays() const;
  void rotate_temp_arrays(const int depth, Block *b, ACvar *tile_index);

 public:

  class iterator {
  public:
    iterator () : p(NULL), l(NULL) {}
    iterator (llist<Foreach *> *loops, llist<int> *m) : p(m), l(loops) {}
    bool operator== (const iterator& x) const { return x.p == p && x.l == l; }
    void next() { p = p->tail()->tail(); }
    bool isDone() { return (p == NULL); }
    inline int loop_number() const { return p->front(); }
    inline Foreach *loop() const { return (*l)[p->front()]; }
    inline int v_number() const { return p->tail()->front(); }
    inline intvector *v() const { return loop()->s[p->tail()->front()]; }
    /* The point translated by the vector of free vars in a. */
    inline Relation generic(Free_Var_Decl **a) {
      return loop()->generic_translate(*intvector_to_singleton_set(v()), a);
    }
  private:
    llist<int> *p;
    llist<Foreach *> *l;
  };

  inline iterator begin() const { return iterator(loops, m); }
  inline iterator step(int k) const {
    iterator i = begin();
    while (k-- > 0)
      i.next();
    return i;
  }
  inline iterator end() const { return iterator(); }

  llist<Foreach *> *loop_list() { return loops; }
  inline Foreach *nth_loop(int n) { return (*loops)[n]; } // count from 0
  int which_loop(AC *f) {
    for (int i = 0; i < n; i++)
      if ((*loops)[i] == f)
	return i;
    fatal_error("");
    return -1;
  }

  llist<set<touch> *> *usib;
  void use_scalar_in_bundle(set<touch> *s) { push(usib, s); }
  void summarize_usib(ostream &);
  void summarize_ts(ostream &, int verbose_level = 2);
  void summarize_rr(ostream &, int verbose_level = 2);

  /* Variables that indicate how to shrink temp arrays */
  map< intpair, st_source * > reader_to_writer;
  map< smap_at_k, string > writer_to_name;
  map< smap_at_k, intvector * > writer_to_maxdist;

#if 0  
  /* Unused. */
  bool usib_contains(const touch &t) const {
    foreach (u, llist<set<touch> *>, *usib)
      if ((*u)->find(t) != (*u)->end())
	return true;
    return false;
  }
  /* Unused. */
  bool usib_contains(int k, int access) const {
    foreach (u, llist<set<touch> *>, *usib)
      for (set<touch>::iterator i = (*u)->begin(); i != (*u)->end(); i++)
	if ((*i).first == k && (*i).second->access == access)
	  return true;
    return false;
  }
#endif

  void optimize_read_from_reg(const smap_element *read, Relation readr,
                              const smap_element *src, Relation srcr,
                              int k, int delta_k) {
    /* DOB: this code was rewritten very painstakingly to avoid a compiler bug
       on the Cray X-1 C++ compiler v5.1.0.2. Test there when making changes
     */
    opt_read _x = {read, src, readr, srcr, delta_k, ""};
    opt_read *x = (opt_read *)malloc(sizeof(opt_read));
    //*x = _x;
    memcpy(x, &_x, sizeof(opt_read));
    array_read_elisions[k] = ::cons(x, array_read_elisions[k]);
  }
  void filter_read_from_reg();

 private:
  // rwmap &rw;
  map< int, llist<opt_read*> * > array_read_elisions;
  vector<subset_requirement> subset_requirements;
  
 public:
  void remove_stmts(Block *b) const;
  void mark_loops_as_tiled() const;
  int size() const; // number of steps in tile
  int count(int l) const; // number of steps in tile that are loop l
  int which_node_from_loop(int l, int k); // l is loop number; k is step
  BoundingBox bb(int l) const;
  void print(ostream &o, int depth = 0) const;
  void print(ostream &o, int depth, bool show_steps) const;
  string short_summary() const;
  void summarize(const Foreach **& f, const intvector **& v, int &size);
  void *translate() const { return AC::translate(); }
  void subset_or_fail(int rl, int rindex, int wl, int windex,
		      const intvector *d) {
    subset_requirement s = {rl, rindex, wl, windex, d};
    subset_requirements.push_back(s);
  }

  AC *concretize();

  int num_loops_in_megatile() const { return n; }
  
  bool zrect;
  bool general_case_is_rect() const;
  bool approximate_general_case_with_rect() const;

  bool *aligned_parallelepiped_only;

 private:
  Relation map_iter_to_tile(int l, intvector *q) const; // unused
  void setup_map_iter_to_tile(); // called by parallelize()
  Relation *mitt; /* mitt[l] maps from iter space of loop l to tile space */
  llist<intvector *> *tile_space_deps;
  bool parallel;
  const char *pd; /* description of kind of parallelism */

  AC *best_code(ACvar **ti, int a, ACvar *stop);
  AC *general_code(ACvar **ti, ACvar **ai, ACvar **o,
		  ACvar *s, int a, ACvar *stop);
  AC *handle_general_node(ACvar *ii, int lo, int hi,
			  ACvar **ti, SizedArray **p0, ACvar *kk);
  AC *handle_general_node(int loop_number, int k,
			  ACvar **ti, SizedArray **p0);
  llist<ACexpr *> *setup_pt(Foreach *f, SizedArray **p0,
			    ACvar *kk, ACvar **ti);
  llist<ACexpr *> *setup_pt(Foreach *f, SizedArray **p0,
			    int k, ACvar **ti);
  UpdateAndExecute *setup_pt_and_execute(Foreach *f, SizedArray **p0,
					 ACvar *kk, ACvar **ti);
  UpdateAndExecute *setup_pt_and_execute(Foreach *f, const intvector *v,
					 ACvar **ti);
  UpdateAndExecute *setup_pt_and_execute(Foreach *f, SizedArray **p0,
					 int k, ACvar **ti);
  UpdateOnly *setup_pt_only(Foreach *f, const intvector *v, ACvar **ti);
  AC *set_Sij(ACvar **ti, ACvar **ai, ACvar *s, int i, int j, int a);
  AC *set_S(ACvar **ti, ACvar **ai, ACvar *s, int a);
  bool steps_are_axis_aligned(int l) const {
    return (*loops)[l]->steps_are_axis_aligned();
  }

};

///////////////////////////////////////////////////////////////////////////
// Classes used in concretization
///////////////////////////////////////////////////////////////////////////

class ACBarrier : public AC {
  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    o << "barrier();" << endl;
  }
  static void * (*translator)();
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)();
  }
};

class ACBroadcast : public AC {
 public:
  ACexpr *result, *v, *from;
  ACBroadcast(ACexpr *r, ACexpr *v, ACexpr *from) :
    result(r), v(v), from(from) {}
  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    result->print(o);
    o << " = broadcast ";
    v->print(o);
    o << " from ";
    from->print(o);
    o << ";" << endl;
  }
  static void * (*translator)(const ACexpr *, const ACexpr *, const ACexpr *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(result,
								      v, from);
  }
};

class FencePreRead : public AC {
  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    o << "FENCE_PRE_READ();" << endl;
  }
  static void * (*translator)(const FencePreRead *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

class FencePostWrite : public AC {
  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    o << "FENCE_POST_WRITE();" << endl;
  }
  static void * (*translator)(const FencePostWrite *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};


class StackAlloc : public AC {
 public:
  ACvar *result;
  const Ty *T;
  ACexpr *count;
  bool cast;

  StackAlloc(ACvar *r, const Ty *t, int k = 1, bool cast = false) :
    result(r), T(t), count(new ACconstant(k)), cast(cast) {}
  StackAlloc(ACvar *r, const Ty *t, ACvar *count, bool cast = false) :
    result(r), T(t), count(new ACvariable(count)), cast(cast) {}
  StackAlloc(ACvar *r, const Ty *t, ACexpr *count, bool cast = false) :
    result(r), T(t), count(count), cast(cast) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    result->print(o);
    o << " = STACK_ALLOC(" << T->to_string() << ", ";
    count->print(o);
    o << ");" << endl; 
  }
  static void * (*translator)(const StackAlloc *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

class StackDealloc : public AC {
 public:
  ACvar *v;

  StackDealloc(ACvar *v) : v(v) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    o << "STACK_DEALLOC(";
    v->print(o);
    o << ");" << endl; 
  }
  static void * (*translator)(const StackDealloc *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

class ComputeAlpha : public AC {
 public:
  Foreach *f;
  ACvar *result, *p, *j, *v, *vi, *r;
  int k;

  ComputeAlpha(ACvar *result, Foreach *f, ACvar *p, ACvar *j,
	       ACvar *v, ACvar *vi, int k, ACvar *r) :
    f(f), result(result), p(p), j(j), v(v), vi(vi), r(r), k(k) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    result->print(o);
    o << " = compute alpha (";
    j->print(o);
    o << ", ";
    v->print(o);
    o << ", ";
    vi->print(o);
    o << ", " << k << ", ";
    r->print(o);
    o << ");" << endl;
  }
  static void * (*translator)(const ComputeAlpha *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

typedef pair< ACvar *, string > rpair;


class UpdateAndExecute : public AC {
 public:
  UpdateAndExecute(Foreach *f, llist<ACexpr *> *l, AC *stmt, bool isU) :
    f(f), l(l), stmt(stmt), isU(isU), _elisions(NULL), _save_in_reg(NULL),
    _use_reg(NULL), shrink_mods_are_set(false) {}
  UpdateAndExecute(Foreach *f, llist<ACexpr *> *l, bool isU) :
    f(f), l(l), stmt(NULL), isU(isU), _elisions(NULL), _save_in_reg(NULL),
    _use_reg(NULL), shrink_mods_are_set(false) {}

  //typedef Megatile::opt_read opt_read;

  void print(ostream &o, int depth = 0) const;
  void find_ACStats(llist<const ACStat *> *&l) const;

  static void * (*translator)(const UpdateAndExecute *);
  void *translate() const {
    assert(shrink_mods_are_set);
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }

  Foreach *f;
  llist<ACexpr *> *l;
  AC *stmt;
  bool isU; /* true if deltas to prior values; false if values */

  UpdateAndExecute *
    set_shrink_mods(int k, map< intpair, st_source * > *reader_to_writer,
		    map< smap_at_k, string > *writer_to_name,
		    map< smap_at_k, intvector * > *writer_to_maxdist,
		    ACvar **ti, bool parallel);
  
  llist<opt_read*> *& elisions() { return _elisions; }
  llist<opt_read*> *elisions() const { return _elisions; }
  llist<opt_read *> *& save_in_reg() { return _save_in_reg; }
  llist<opt_read *> *save_in_reg() const { return _save_in_reg; }
  map<int, string> *& use_reg() { return _use_reg; }
  map<int, string> *use_reg() const { return _use_reg; }
  map<int, rpair> *replace_read() { return &_replace_read; }
  const map<int, rpair> *replace_read() const { return &_replace_read; }
  map<int, rpair> *replace_write() { return &_replace_write; }
  const map<int, rpair> *replace_write() const { return &_replace_write; }

 private:
  llist<opt_read*> *_elisions;
  llist<opt_read *> *_save_in_reg;
  map<int, string> *_use_reg;     // access -> variable name
  bool shrink_mods_are_set;

  // maps from access to how to replace that access
  map<int, rpair> _replace_read, _replace_write;

  void shrink_opt_read(const int access,
		       const st_source *src,
		       map< smap_at_k, string > *writer_to_name_all_k,
		       map< smap_at_k, intvector * > *writer_to_maxdist_all_k,
		       ACvar **ti, bool parallel);
  void shrink_opt_write(const smap_element *write,
			const string &name,
			const intvector *maxdist,
			ACvar **ti, bool parallel);
};

class UpdateOnly : public AC {
 public:
  UpdateOnly(Foreach *f, llist<ACexpr *> *l, AC *stmt, bool isU) :
    f(f), l(l), stmt(stmt), isU(isU) {}
  UpdateOnly(Foreach *f, llist<ACexpr *> *l, bool isU) :
    f(f), l(l), stmt(NULL), isU(isU) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    o << (isU ? "update" : "set") << " iter point: {";
    foreach (e, llist<ACexpr *>, *l)
      if (*e == NULL)
	o << " NULL";
      else {
	o << ' ';
	(*e)->print(o, depth);
      }
    o << " }" << endl;
  }

  static void * (*translator)(const UpdateOnly *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }

  Foreach *f;
  llist<ACexpr *> *l;
  AC *stmt;
  bool isU; /* true if deltas to prior values; false if values */
};

class IsSubset : public ACexpr {
 public:
  ACexpr *s1, *s2;
  const intvector *offset;
  
  IsSubset(ACexpr *s1, ACexpr *s2, const intvector *offset) :
    ACexpr(Ty::boolTy), s1(s1), s2(s2), offset(offset) {}

  void print(ostream &o, int depth = 0) const {
    o << "is_subset(";
    s1->print(o, depth + 1);
    o << ", ";
    s2->print(o, depth + 1);
    o << ", " << offset->to_string() << ")";
  }
  static void * (*translator)(const IsSubset *);
  void *translate() const {
    return (translator == NULL) ? ACexpr::translate() : (*translator)(this);
  }
};

class SetToConstant : public AC {
 public:
  ACvar *v;
  int c;

  SetToConstant(ACvar *v_, int c_) : v(v_), c(c_) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    v->print(o);
    o << " = " << c << ";" << endl;
  }
  static void * (*translator)(const SetToConstant *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

class SetToEmpty : public SetToConstant {
 public:
  SetToEmpty(ACvar *v_) : SetToConstant(v_, 0) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    v->print(o);
    o << " = emptyset;" << endl;
  }
  static void * (*translator)(const SetToEmpty *);
  void *translate() const {
    return (translator == NULL) ? SetToConstant::translate() : (*translator)(this);
  }
};

class SetToInfinity : public SetToConstant {
 public:
  SetToInfinity(ACvar *v_) : SetToConstant(v_, MAXINT) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    v->print(o);
    o << " = infinity;" << endl;
  }
  static void * (*translator)(const SetToInfinity *);
  void *translate() const {
    return (translator == NULL) ? SetToConstant::translate() : (*translator)(this);
  }
};

class IsEmpty : public ACexpr {
 public:
  ACexpr *s;

  IsEmpty(ACexpr *s_) : ACexpr(Ty::boolTy), s(s_) {}

  void print(ostream &o, int depth = 0) const {
    o << "is_empty(";
    s->print(o);
    o << ")";
  }
  static void * (*translator)(const IsEmpty *);
  void *translate() const {
    return (translator == NULL) ? ACexpr::translate() : (*translator)(this);
  }
};

/* At step k, load some array element (specified by access) into a
   temporary (varname). */
class LoadArrayEltTemp : public AC {
 public:
  string &varname;
  int access, k;

  LoadArrayEltTemp(opt_read *o, int k) :
    varname(o->varname), access(o->src->access), k(k) {} 
  LoadArrayEltTemp(const string &v, int k, int access) :
    varname(*(new string(v))), access(access), k(k) {}

  void print(ostream &os, int depth = 0) const {
    indent2(os, depth);
    os << "LoadArrayEltTemp " << varname << " (k=" << k <<
      ", access=" << access << ")" << endl;
  }

  static void * (*translator)(const LoadArrayEltTemp *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

/* The reverse of a LoadArrayEltTemp.
   If the load does tmp=a[x] then this does a[x]=tmp. */
class WriteArrayEltTemp : public AC {
 public:
  string &varname;
  int access, k;

  WriteArrayEltTemp(opt_read *o, int k) :
    varname(o->varname), access(o->src->access), k(k) {} 
  WriteArrayEltTemp(const string &v, int k, int access) :
    varname(*(new string(v))), access(access), k(k) {}

  void print(ostream &os, int depth = 0) const {
    indent2(os, depth);
    os << "WriteArrayEltTemp " << varname << " (k=" << k <<
      ", access=" << access << ")" << endl;
  }

  static void * (*translator)(const WriteArrayEltTemp *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

/* Declare the temporary to hold some array element specified by l. */
class DeclareArrayEltTemp : public AC {
 public:
  string &varname;
  int access;

  DeclareArrayEltTemp(opt_read *o) : 
    varname(o->varname), access(o->src->access) {} 
  DeclareArrayEltTemp(const string &v, int access) : 
    varname(*(new string(v))), access(access) {}

  void print(ostream &os, int depth = 0) const {
    indent2(os, depth);
    os << "declare " << varname << ";" << endl;
  }

  static void * (*translator)(const DeclareArrayEltTemp *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

//////////////////////////////////////////////////////////////////////

class SetCopy : public AC {
 public:
  ACvar *x, *y;

  SetCopy(ACvar *x_, ACvar *y_) : x(x_), y(y_) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    x->print(o);
    o << " = copy(";
    y->print(o);
    o << ");" << endl;
  }
  static void * (*translator)(const SetCopy *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

class SetUnion : public AC {
 public:
  ACvar *x, *y;
  bool destroy2nd;

  SetUnion(ACvar *x_, ACvar *y_, bool d = false) :
    x(x_), y(y_), destroy2nd(d) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    x->print(o);
    o << " = ";
    x->print(o);
    o << " union ";
    y->print(o);
    o << "; /* " << (destroy2nd ? "may modify/share parts of" : "won't share any part of") << " arg 2 */" <<
      endl;
  }
  static void * (*translator)(const SetUnion *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

class SetIntersection : public AC {
 public:
  ACvar *x, *y;
  bool destroy2nd;

  SetIntersection(ACvar *x_, ACvar *y_, bool d = false) :
    x(x_), y(y_), destroy2nd(d) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    x->print(o);
    o << " = ";
    x->print(o);
    o << " intersection ";
    y->print(o);
    o << "; /* " << (destroy2nd ? "may modify/share parts of" : "won't share any part of") << " arg 2 */" <<
      endl;
  }
  static void * (*translator)(const SetIntersection *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

//////////////////////////////////////////////////////////////////////

class ForLoop : public AC {
 public:
  ACvar *i; /* iteration variable */
  ACexpr *lo, *hi;
  AC *body;

  ForLoop(ACvar *i, int l, int h, AC *b) :
    i(i), lo(new ACconstant(l)), hi(new ACconstant(h)), body(b) {}
  ForLoop(ACvar *i, int h, AC *b) :
    i(i), lo(NULL), hi(new ACconstant(h)), body(b) {}
  ForLoop(ACvar *i, ACvar *l, ACvar *h, AC *b) :
    i(i), lo(new ACvariable(l)), hi(new ACvariable(h)), body(b) {}
  ForLoop(ACvar *i, ACvar *h, AC *b) :
    i(i), lo(NULL), hi(new ACvariable(h)), body(b) {}

  void find_ACStats(llist<const ACStat *> *&l) const;

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    o << "for (";
    if (lo != NULL) {
      i->print(o);
      o << " = ";
      lo->print(o);
    }
    o << "; ";
    i->print(o);
    o << " <= ";
    hi->print(o);
    o << "; ";
    i->print(o);
    o << "++) ";
    body->subprint(o, depth);
  }
  static void * (*translator)(const ForLoop *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

class WhileLoop : public AC {
 public:
  ACexpr *test;
  AC *body;

  WhileLoop(ACexpr *t, AC *b) : test(t), body(b) {}

  void find_ACStats(llist<const ACStat *> *&l) const;

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    o << "while (";
    test->print(o);
    o << ") ";
    body->subprint(o, depth);
  }
  static void * (*translator)(const WhileLoop *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

class IfStmt : public AC {
 public:
  ACexpr *test;
  AC *thenpart, *elsepart;

  IfStmt(ACexpr *t, AC *x, AC *y) : test(t), thenpart(x), elsepart(y) {}

  void find_ACStats(llist<const ACStat *> *&l) const;

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    o << "if (";
    test->print(o);
    o << ") ";
    thenpart->subprint(o, depth);
    if (elsepart != NULL) {
      indent2(o, depth);
      o << "else ";
      elsepart->subprint(o, depth);
    }
  }
  static void * (*translator)(const IfStmt *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

class ForEveryRect : public AC {
 public:
  ACvar *i; /* iteration variable */
  ACvar *d; /* list of rectangles */
  AC *body;

  ForEveryRect(ACvar *i, ACvar *d_, AC *b) :
    i(i), d(d_), body(b) {}

  void find_ACStats(llist<const ACStat *> *&l) const;

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    o << "for (every rectangle ";
    i->print(o);
    o << " in ";
    d->print(o);
    o << ") ";
    body->subprint(o, depth);
  }
  static void * (*translator)(const ForEveryRect *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

/* ivseti iteration, etc. */

class GetSetiFromIvseti : public AC {
 public:
  ACvar *d, *s;

  GetSetiFromIvseti(ACvar *dest, ACvar *src) : d(dest), s(src) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    d->print(o);
    o << " = ivseti_intervals(";
    s->print(o);
    o << ");" << endl;
  }
};

/* Spin until e becomes non-zero.  Then assign result to v. */
class SpinLock : public AC {
 public:
  const ACvar *v;
  const ACexpr *e;

  SpinLock(const ACvar *v, const ACexpr *e) : v(v), e(e) {}
  void print(ostream &o, int depth = 0) const {
    string T("int");
    indent2(o, depth);
    o << "SPIN_LOCK(" << v->to_string() << ", ";
    e->print(o, depth);
    o << ", " << T << " *);";
  }
  static void * (*translator)(const SpinLock *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

class Contains : public ACexpr {
 public:
  const ACvar *s;
  const bool is_rect; /* whether the set s is a rect */
  const ACvar **ti;
  const intvector *value;
  string str;
  /* s is a set represented as either an ivseti or a rectN. */
  /* The vector (ti[0] + (*value)[0], ti[1] + (*value)[1], ...)
     represents a point that may or may not be in s. */
  Contains(const ACvar *s, const bool is_rect,
	   const ACvar **ti, const intvector *value) :
    ACexpr(Ty::boolTy), s(s), is_rect(is_rect), ti(ti), value(value) {
    const int n = value->size();
    if (is_rect) {
      str = "rect" + i2s(n + 1) + "_contains" + i2s(n) + "(" + s->to_string();
      for (int i = 0; i < n; i++)
	str += ", " + ti[i]->to_string() + " + " + i2s((*value)[i]);
      str += ")";
    } else {
      str = "ivseti_contains" + i2s(n) + "(" + s->to_string();
      for (int i = 0; i < n; i++)
	str += ", " + ti[i]->to_string() + " + " + i2s((*value)[i]);
      str += ")";
    }
  }

  void print(ostream &o, int depth = 0) const {
    o << str;
  }
  static void * (*translator)(const Contains *);
  void *translate() const {
    return (translator == NULL) ? ACexpr::translate() : (*translator)(this);
  }
  
};

class GetBounds : public AC {
 public:
  ACvar *src, *lo, *hi;
  int dim;
  /* src may be an ivseti or a rectN */

  GetBounds(ACvar *src, int dim, ACvar *lo, ACvar *hi) :
    src(src), lo(lo), hi(hi), dim(dim) {}

  void print(ostream &o, int depth = 0) const {
    const string &ls = lo->to_string(), &hs = hi->to_string(),
      &ss = src->to_string();
    indent2(o, depth);
    if (src->type() == Ty::ivsetiTy) {
      o << "ivseti_range(" << ss << ", " <<
	dim << ", &" << ls << ", &" << hs << ");" << endl;
    } else {
      o << "{ " << ls << " = " << ss << ".l" << dim << "; " <<
	hs << " = " << ss << ".h" << dim << "; }" << endl;
    }
  }
};

class IndexIvseti : public AC { // d = s[i]
 public:
  ACvar *d, *s, *i; 

  IndexIvseti(ACvar *dest, ACvar *src, ACvar *ind) : d(dest), s(src), i(ind) {}

  void print(ostream &o, int depth = 0) const {
    const string &is = i->to_string(), &ds = d->to_string(),
      &ss = s->to_string();
    indent2(o, depth);
    o << ds << " = (" << ss << " is empty) ? emptyset : "
      "ivget(" << is << ", " << ss << "->h);" << endl;
  }

  static void * (*translator)(const IndexIvseti *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

class SetiIter : public AC {
 public:
  ACvar *i;
  AC *body;

  SetiIter(ACvar *i_, AC *body_) : i(i_), body(body_) {}

  void find_ACStats(llist<const ACStat *> *&l) const;

  void print(ostream &o, int depth = 0) const {
    const string &is = i->to_string();
    indent2(o, depth);
    o << "for ( ; " << is << " != NULL; " <<
      is << " = tail_interval(" << is << ")) ";
    body->subprint(o, depth);
  }
  static void * (*translator)(const SetiIter *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

class GetTailInterval : public AC {
 public:
  ACexpr *v, *x; // v = tail(x);

  GetTailInterval(ACexpr *v_, ACexpr *x_) : v(v_), x(x_) {}
  GetTailInterval(ACvar *v_, ACvar *x_) :
    v(new ACvariable(v_)), x(new ACvariable(x_)) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    v->print(o);
    o  << " = tail_interval(";
    x->print(o);
    o << ");" << endl;
  }
};

class Assign : public AC {
 public:
  ACexpr *lhs;
  ACexpr *rhs;

  Assign(ACvar *l, ACvar *r) :
    lhs(new ACvariable(l)), rhs(new ACvariable(r)) {}
  Assign(ACvar *l, ACexpr *r) : lhs(new ACvariable(l)), rhs(r) {}
  Assign(ACexpr *l, ACvar *r) : lhs(l), rhs(new ACvariable(r)) {}
  Assign(ACexpr *l, ACexpr *r) : lhs(l), rhs(r) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    lhs->print(o);
    o << " = ";
    rhs->print(o);
    o << ';' << endl;
  }
  static void * (*translator)(const Assign *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

/*
class Assign : public AC {
 public:
  ACvar *lhs;
  ACexpr *rhs;

  Assign(ACvar *l, ACexpr *r) : lhs(l), rhs(r) {}
  Assign(ACvar *l, ACvar *r) : lhs(l), rhs(new ACvariable(r)) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    lhs->print(o);
    o << " = ";
    rhs->print(o);
    o << ';' << endl;
  }
  static void * (*translator)(const Assign *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};
*/

class Label : public AC {
 public:
  const string s;

  Label(const string s_) : s(s_) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth - 1);
    o << ' ' << s << ':' << endl;
  }
  static void * (*translator)(const Label *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

class Goto : public AC {
 public:
  Label *l;

  Goto(Label *l_) : l(l_) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    o << "goto " << l->s << ';' << endl;
  }
  static void * (*translator)(const Label *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(l);
  }
};

class Fail : public AC {
 public:
  const string s;

  Fail() : s("") {}
  Fail(const string s_) : s(s_) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth - 1);
    o << "fail " << s << ';' << endl;
  }
  static void * (*translator)(const Fail *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};


class GetSetiMax : public AC {
 public:
  ACvar *v;
  ACexpr *e;
  
  GetSetiMax(ACvar *v_, ACexpr *e_) : v(v_), e(e_) {}
  GetSetiMax(ACvar *v_, ACvar *e_) : v(v_), e(new ACvariable(e_)) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    o << v->to_string() << " = seti_max(";
    e->print(o);
    o << ");" << endl;
  }
  
};

class GetSetiMin : public AC {
 public:
  ACvar *v;
  ACexpr *e;
  
  GetSetiMin(ACvar *v_, ACexpr *e_) : v(v_), e(e_) {}
  GetSetiMin(ACvar *v_, ACvar *e_) : v(v_), e(new ACvariable(e_)) {}

  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
    o << v->to_string() << " = seti_min(";
    e->print(o);
    o << ");" << endl;
  }
  
};

class GetHeadIntervalHiLo : public AC {
 public:
  ACvar *s, *lo, *hi; 
  
  GetHeadIntervalHiLo(ACvar *s_, ACvar *lo_, ACvar *hi_) :
    s(s_), lo(lo_), hi(hi_) {}

  void print(ostream &o, int depth = 0) const {
    const string &l = lo->to_string(), &h = hi->to_string(),
      &ss = s->to_string();
    indent2(o, depth);
    o << "if (" << ss << " is empty) " << l << " = " << h << " = infinity;" <<
      endl; 
    indent2(o, depth);
    o << "else { " << l << " = head_interval(" << ss << ")->lo; " <<
      h << " = head_interval(" << ss << ")->hi; }" << endl;
  }

  static void * (*translator)(const GetHeadIntervalHiLo *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

class GetRectHiLo : public AC {
 public:
  ACvar *s, **ti;
  int arity;
  ACvar *lo, *hi; 
  
  GetRectHiLo(ACvar *s, ACvar **ti_, int arity, ACvar *lo, ACvar *hi) :
    s(s), arity(arity), lo(lo), hi(hi) {
    ti = new ACvar * [arity];
    for (int i = 0; i < arity; i++)
      ti[i] = ti_[i];
  }
  ~GetRectHiLo() { delete[] ti; }

  void print(ostream &o, int depth = 0) const {
    const string &l = lo->to_string(), &h = hi->to_string(),
      &ss = s->to_string();
    indent2(o, depth);
    string condition("1");
    for (int i = 0; i < arity - 1; i++) {
      const string &v = ti[i]->to_string();
      condition += " && " + v + " >= " + ss + ".l" + i2s(i) + " && " +
	v + " <= " + ss + ".h" + i2s(i);
    }
    o << "if (" << condition << ") { " <<
      l << " = " << ss << ".l" << arity - 1 << "; " <<
      h << " = " << ss << ".h" << arity - 1 << "; }"
      " else { " << l << " = " << h << " = " << MAXINT_STRING << "; }" << endl;
  }

  static void * (*translator)(const GetRectHiLo *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }
};

static inline llist<ACexpr *> *vars_to_exprs(llist<ACvar *> *l)
{
  llist<ACexpr *> *r = NULL;
  foreach (v, llist<ACvar *>, *l)
    push(r, new ACvariable(*v));
  return dreverse(r);
}

class ACDebug : public AC {
 public:
  ACDebug(string flag, string format, llist<ACvar *> *l) :
    flag(flag), format(format), l(vars_to_exprs(l)) {}
  ACDebug(string flag, string format, llist<ACexpr *> *l) :
    flag(flag), format(format), l(copylist(l)) {}
  ACDebug(string flag, string format) :
    flag(flag), format(format), l(NULL) {}

  ~ACDebug() { ::free_all(l); }

  void print(ostream &o, int depth = 0) const {
    o << "#if DEBUG_" << flag << endl;
    indent2(o, depth);
    o << "printf(\"" << format << '\"';
    foreach (e, llist<ACexpr *>, *l) {
      o << ", ";
      (*e)->print(o);
    }
    o << ");" << endl;
    o << "#endif" << endl;
  }

  static void * (*translator)(const ACDebug *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }

  string flag, format;
  llist<ACexpr *> *l;
};


class ACStat : public AC {
 public:
  ACStat(string varname, string description,
	 string format, llist<ACvar *> *l) :
    varname(varname), description(description), format(format),
    type("int"), initial_value("0"), l(vars_to_exprs(l)) {}
  ACStat(string varname, string description,
	 string format, llist<ACexpr *> *l = NULL,
	 string type = "int", string initial_value = "0") :
    varname(varname), description(description), format(format),
    type(type), initial_value(initial_value), l(l) {}

  void find_ACStats(llist<const ACStat *> *&l) const;

  void print(ostream &o, int depth = 0) const {
    o << "#if STOPTIFU_STATS" << endl;
    indent2(o, depth);
    o << "{" << endl;
    depth++;
    indent2(o, depth);
    o << "/* " << description << " */" << endl;
    indent2(o, depth);
    o << "varname=" << varname << endl;
    indent2(o, depth);
    o << "format=" << format << endl;
    indent2(o, depth);
    o << "l=(";
    bool needcomma = false;
    foreach (e, llist<ACexpr *>, *l) {
      if (needcomma)
	o << ", ";
      else
	needcomma = true;
      (*e)->print(o);
    }
    o << ")" << endl;
    depth--;
    indent2(o, depth);
    o << "}" << endl << "#endif" << endl;
  }

  static void * (*translator)(const ACStat *);
  void *translate() const {
    return (translator == NULL) ? AC::translate() : (*translator)(this);
  }

  string varname, description, format, type, initial_value;
  llist<ACexpr *> *l;
};


static inline AC * getFieldOfHeadInterval(ACvar *dest, ACvar *src,
					  const char *field)
{
  return new Assign(dest, new FieldOfHeadInterval(src, field));
}

AC *skipIntervals(ACexpr *s, ACvar *v, bool checkempty = true);
static inline AC *skipIntervals(ACvar *s, ACvar *v, bool checkempty = true) {
  return skipIntervals(new ACvariable(s), v, checkempty);
}

Ty *&type_of_access(int access);

Free_Var_Decl *freevar(unsigned int n);
void freevar_map_clear();

static inline string pseudocode(const AC *t)
{
  if (t == NULL)
    return "NULL";
  ostringstream o;
  t->print(o, 0);
  string s = o.str();
  return s;
}

#if 0
class  : public AC {
  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
  }
};

class  : public AC {
  void print(ostream &o, int depth = 0) const {
    indent2(o, depth);
  }
};
#endif // 0

#endif /* _AC_H_ */