#include "AST.h"
#include "optimize.h"
#include "string-utils.h"
#include "stoptifu/stoptifu.h"
#include "StorageAnnotations.h"
#include "clone.h"
#include "pseudocode.h"
#include "lower.h"

extern TreeNode *& ACtoIF(AC *r);
extern TreeNode *mapACLabelToIF(const Label *z);
extern const string rectField(const string r, const string field, int arity);
extern StorageAnnotations *current_StorageAnnotations;

typedef pair<TreeNode *, TreeNode *> treepair;

extern bool debug_stoptifu;

/* Macros for debugging output */
#undef DPRINT
#undef DPRINTLN
#undef DBG
#define DPRINT(x) do { if (debug_stoptifu) cout << (x); } while (0) 
#define DPRINTLN(x) DPRINT(string(x) + '\n')
#define DBG(x) do { if (debug_stoptifu) { x; } } while (0)

/* Macros copied from lower.cc */
#define GOTO(n) (new GotoNode(n))
#define LABELED(n, pos) (new LabeledStmtNode(TreeNode::omitted, (n), (pos)))
#define NAKEDLABEL() LABELED(TreeNode::omitted, NoSourcePosition)

static const string empty = "";

/* from code-foreach.cc */
extern string rectMin(const string &r, int dim, int arity);
extern string rectUpb(const string &r, int dim, int arity);

/* from lower.cc */
BlockNode *stmt_to_lowered_block(TreeNode *t);

/* SR or OSR access -> string. */
string SRAstr(TreeNode *t)
{
  if (isSRArrayAccessNode(t))
    return t->codeString();
  else if (isOSRArrayAccessNode(t))
    return t->codeString() + '+' + t->offsetString();
  else
    fatal_error("");
  return "";
}

/////////////////////////////////////////////////////////////////////////////
// Translation of stoptifu result back to our IF (AC * to TreeNode *):
//   Relies heavily on CodeLiteralNodes
//
// Be careful to distinguish "int" from "jint."
/////////////////////////////////////////////////////////////////////////////

static inline TreeNode *add_to(TreeNode *t, int delta)
{
  return new PlusNode(t, new PrimitiveLitNode((int32) delta));
}

/* unused */
static inline TreeNode *lower(TreeNode *t)
{
  llist<TreeNode *> *decls = NULL, *stmts = NULL;
  t->fixParent();
  /*
  DBG({
    cout << "lower():" << endl;
    t->print(cout);
    cout << endl;
  });
  */
  t = t->lower(decls, stmts);
  assert(decls == NULL);
  assert(stmts == NULL);
  return t;
} 

#define K(v) ((TreeNode *) (v))
#define V(t) ((void *) (t))
#define X(e) (new ExpressionStmtNode((e)))

// This function is (the only function in the file?) called from outside.
TreeNode *translate(const AC *x)
{
  return (x == NULL) ? TreeNode::omitted : K(x->translate());
}

TreeNode *translate(const ACvar *v)
{
  return (v == NULL) ? NULL : K((new ACvariable(v))->translate());
}

string translate_to_string(const ACvar *v)
{
  assert(v != NULL);
  ostringstream o;
  v->print(o);
  string s = o.str();
  return s;
}

string translate_to_string(const ACexpr *e)
{
  assert(e != NULL);
  ostringstream o;
  e->print(o);
  string s = o.str();
  return s;
}

/* Convert t to a C type that can be used in generated code. */
static string Ctype(const Ty *t)
{
  static bool inited = false;
  static map<string, string> m;
  if (!inited) {
    for (int i = 1; i <= MAX_TIARITY; i++) {
      string s = int2string(i);
      m["Point<" + s + ">"] = makePointType(i)->cType();
      m["Domain<" + s + ">"] = makeDomainType(i)->cType();
      m["RectDomain<" + s + ">"] = makeRectDomainType(i)->cType();
    }
    inited = true;
  }

  string s = t->to_string();
  const string &r = m[s];
  return (r == "") ? s : r;
}

map<string, TypeNode *> override_typemap;

/* Return a TypeNode corresponding to t. */
static TypeNode *translate_type(const Ty *t)
{
  static bool inited = false;
  static map<string, TypeNode *> m;
  if (!inited) {
    /* Make an entry in m for every type that we intend to translate. */
    for (int i = 1; i <= MAX_TIARITY; i++) {
      string s = int2string(i);
      m[makePointType(i)->cType()] = makePointType(i);
      m[makeDomainType(i)->cType()] = makeDomainType(i);
      m[makeRectDomainType(i)->cType()] = makeRectDomainType(i);
    }
    m["int"] = theIntType;
    m["bool"] = theBoolType;
    m["float"] = theFloatType;
    m["double"] = theDoubleType;
    inited = true;
  }
  
  TypeNode *r = override_typemap[Ctype(t)];
  if (r == NULL) {
    r = m[Ctype(t)];
    if (r == NULL) {
      fatal_error("Internal error: Ty `" + t->to_string() + "' is untranslatable!");
    }
  }
  return r;
}

static void *translate_ACexpr(const ACexpr *z)
{
  ostringstream o;
  z->print(o);
  CodeLiteralExprNode *t = new CodeLiteralExprNode(o.str());
  if (z->type() == NULL) {
    fatal_error("Internal Error: type of " + o.str() + " is NULL");
  } else
    t->type(translate_type(z->type()));
  return V(t);
}

static void *translate_ACvariable(const ACvariable *v)
{
  void *t = v->v->alternate_translation();
  if (t != NULL)
    return (void *) CloneTree((TreeNode *) t);

  /* Output a CodeLiteralExprNode, a bit of a hack since name
     collisions might occur.  However, they're extremely unlikely because
     of the naming scheme used by tc for source code variables and
     compiler generated variables. */
  return translate_ACexpr(v);
}

static void *translate_ACvariable(const ACvar *v)
{
  ACvariable n(v);
  return translate_ACvariable(&n);
}

static void *translate_ACconstant(int k)
{
  return V(new PrimitiveLitNode((int32) k));
}

static void *translate_ACexprStmt(const ACexpr *e)
{
  llist<TreeNode *> *l = NULL;
  push(l, new CodeLiteralNode(";"));
  push(l, K(e->translate()));
  return V(new BlockNode(l, NULL));
}

static void *translate_BinaryExpr(const BinaryExpr *z)
{
  ExprNode *t;
  if (z->op == "==")
    t = new EQNode(K(z->x->translate()), K(z->y->translate()));
  if (z->op == ">=")
    t = new GENode(K(z->x->translate()), K(z->y->translate()));
  if (z->op == "<=")
    t = new LENode(K(z->x->translate()), K(z->y->translate()));
  if (z->op == ">")
    t = new GTNode(K(z->x->translate()), K(z->y->translate()));
  if (z->op == "<")
    t = new LTNode(K(z->x->translate()), K(z->y->translate()));
  else if (z->op == "&&")
    t = new CandNode(K(z->x->translate()), K(z->y->translate()));
  else if (z->op == "||")
    t = new CorNode(K(z->x->translate()), K(z->y->translate()));
  else if (z->op == "+")
    t = new PlusNode(K(z->x->translate()), K(z->y->translate()));
  else if (z->op == "-")
    t = new MinusNode(K(z->x->translate()), K(z->y->translate()));
  else if (z->op == "*")
    t = new MultNode(K(z->x->translate()), K(z->y->translate()));
  else if (z->op == "/")
    t = new DivNode(K(z->x->translate()), K(z->y->translate()));
  else if (z->op == "-=" || z->op == "+=")
    /* Translate to a typeless node to avoid problems if type of z->x
       is unrepresentable (e.g., if type is "jint *") */
    return V(new CodeLiteralNode(translate_to_string(z->x) + " " + z->op +
				 " " + translate_to_string(z->y)));
  else
    return translate_ACexpr(z);

  t->type(translate_type(z->type()));
  return V(t);
}

static string ACexpr_formatted_for_printf(const ACexpr *e)
{
  static bool inited = false;
  static map<string, int> m;
  if (!inited) {
    /* Make an entry in m for every type that we intend to translate. */
    for (int i = 1; i <= MAX_TIARITY; i++) {
      string s = int2string(i);
      m[makePointType(i)->cType()] = i * 10 + 1;
      m[makeDomainType(i)->cType()] = i * 10 + 2;
      m[makeRectDomainType(i)->cType()] = i * 10 + 3;
    }
    for (int i = 1; i <= MAX_TIARITY; i++) {
      string s = int2string(i);
      m["rect" + s] = 100 + i;
    }
    m["int"] = m["bool"] = m["float"] = m["double"] = 1;
    m["ivseti *"] = 2;
    m["iseti *"] = 3;
    m["seti *"] = 4;
    // format some types by casting to int
    m["int *"] = m["void *"] = m["double *"] = m["float *"] =
      m["jint *"] = m["jdouble *"] = m["jfloat *"] = 9;

    inited = true;
  }
  string s = translate_to_string(e);
  switch (m[Ctype(e->type())]) {
  case 0:
    fatal_error("Can't format type " + e->type()->to_string() + " for printf\n");
  case 11: // P1
  case 12: // D1
  case 13: // R1
  case 21: // P2
  case 22: // D2
  case 23: // R2
  case 31: // P3
  case 32: // D3
  case 33: // R3
  default:
    assert(0 && "unimplemented");
  case 1: // No translation needed
    return s;
  case 2: // ivseti *
    return "ivseti_to_string(" + s + ")";
  case 3: // iseti *
    return "iseti_to_string(" + s + ")";
  case 4: // seti *
    return "iinterval_list_to_string(" + s + ")";
  case 9: // format as integer
    return "((int) " + s + ")";
  case 101: // rect1
    return "rect1_to_string(" + s + ")";
  case 102: // rect2
    return "rect2_to_string(" + s + ")";
  case 103: // rect3
    return "rect3_to_string(" + s + ")";
  }
}

static void *translate_ACDebug(const ACDebug *z)
{
  string s("\n#if DEBUG_" + z->flag + "\nprintf(\"{%d} " + z->format + '\"');
  s += ", MYPROC";
  foreach (e, llist<ACexpr *>, *z->l)
    s += ", " + ACexpr_formatted_for_printf(*e);
  s += ");\n#endif\n";
  return V(new CodeLiteralNode(s));
}

/* Convert a string, left, of the form "AAAAXXXXBBBBB" to AAAA and put
   BBBBB in right.  XXXX is the splitter.  Return left.  E.g., 
   if left="xyz%dqrs%dz" and splitter="%d" then after returning, left="xyz"
   and right="qrs%dz". */
string &split_string(string &left, const string &splitter, string &right)
{
  string::size_type f = left.find(splitter);
  left.erase(f, splitter.size());
  right = left.substr(f);
  left.erase(f);
  return left;
}

static void *translate_GatherStats(const GatherStats *z)
{
  const AC *a = z->a;
  llist<const ACStat *> *l = NULL;
  a->find_ACStats(l);
  string header, footer;
  set<string> done;
  foreach_const (s, llist<const ACStat *>, *l) {
    const string &v = (*s)->varname;
    if (done.find(v) == done.end()) {
      const string &desc = (*s)->description;
      header += (*s)->type + ' ' + v + " = " + (*s)->initial_value + ";\n";
      footer += "printf(\"{%d} %s: %d\\n\", MYPROC, \"" + desc + "\", " +
	v + ");\n";
      done.insert(v);
    }
  }
  if (z->label != "")
    header += "puts(\"" + z->label + "\");\n";
  header = "\n#if STOPTIFU_STATS\n{\n" + header + "#endif\n";
  footer = "\n#if STOPTIFU_STATS\n" + footer + "}\n#endif\n";
  free_all(l);
  llist<TreeNode *> *result = NULL;
  push(result, new CodeLiteralNode(footer));
  push(result, translate(a)); 
  push(result, new CodeLiteralNode(header));
  return V(new BlockNode(result, NULL));
}

static void *translate_ACStat(const ACStat *z)
{
  string s("\n#if STOPTIFU_STATS\n");
  string r(z->format);
  const string expected_format("%d");
  foreach (e, llist<ACexpr *>, *z->l) {
    string tmp;
    split_string(r, expected_format, tmp);
    s += r + translate_to_string(*e);
    r = tmp;
  }
  s += r + ";\n#endif\n";
  return V(new CodeLiteralNode(s));
}

static void *translate_UnaryExpr(const UnaryExpr *z)
{
  ExprNode *t;

  if (z->op == "!")
    t = new NotNode(K(z->y->translate()));
  else if (z->op == "-")
    t = new UnaryMinusNode(K(z->y->translate()));
  else
    return translate_ACexpr(z);

  t->type(translate_type(z->type()));
  return V(t);
}

static void *translate_ACBroadcast(const ACexpr *result,
				   const ACexpr *v, const ACexpr *from)
{
  if (has_indexed_type(v->type())) {
    const string rs = translate_to_string(result), vs = translate_to_string(v),
      fs = translate_to_string(from), ts = Ctype(v->type());
    return V(new CodeLiteralNode("STOPTIFU_BCAST_LP(" + rs + ", " + vs + ", " +
				 fs + ", " + ts + ");"));
  } else {
    TreeNode *t = new AssignNode(translate(result),
				 new BroadcastNode(translate(v),
						   translate(from)));
    return V(stmt_to_lowered_block(new ExpressionStmtNode(t)));
  }
}

static void *translate_Decl(const ACDecl *d)
{
  return V(new CodeLiteralNode(Ctype(d->v->type()) + ' ' +
			       translate_to_string(d->v) + ';'));
}

static void *translate_Block(const llist<AC *> *decls,
			     const llist<AC *> *stmts)
{
  llist<TreeNode *> *l = NULL;
  while (decls != NULL) {
    push(l, K(decls->front()->translate()));
    decls = decls->tail();
  }
  while (stmts != NULL) {
    push(l, K(stmts->front()->translate()));
    stmts = stmts->tail();
  }
  return V(new BlockNode(dreverse(l), NULL));
}

static TreeNode *construct_While(TreeNode *test, TreeNode *body)
{
  const SourcePosn pos = body->position();
  TreeNode *s = LABELED(body, pos);
  TreeNode *b = new IfStmtNode(test, GOTO(s), TreeNode::omitted,
			       test->position());
  if (!b->checkIF(false))
    b = stmt_to_lowered_block(b);
  TreeNode *bot = LABELED(b, pos);
  TreeNode *initial_goto = GOTO(bot);
  return new BlockNode(cons(initial_goto, cons(s, cons(bot))), NULL); 
}

static TreeNode *construct_For(TreeNode *init, TreeNode *test,
			    TreeNode *bump, TreeNode *body)
{
  TreeNode *y = (init == NULL) ? NULL : new BlockNode(cons(init), NULL);
  TreeNode *z = construct_While(test, new BlockNode(cons(body, cons(bump)), NULL));
  return (y == NULL) ? z : new BlockNode(cons(y, cons(z)), NULL);
}

static void *translate_WhileLoop(const WhileLoop *z)
{
  return V(construct_While(translate(z->test), translate(z->body)));
}

static void *translate_SetiIter(const SetiIter *z)
{
  const string &is = z->i->to_string();
  TreeNode *a, *b;
  a = new CodeLiteralNode("for ( ; " + is + " != NULL; " +
			  is + " = tail_interval(" + is + ")) ");
  b = translate(z->body);
  return V(new BlockNode(cons(a, cons(b)), NULL));
}

static void *translate_ForLoop(const ForLoop *z)
{
  TreeNode *i = translate(new ACvariable(z->i));
  TreeNode *init =
    (z->lo == NULL) ? NULL : X(new AssignNode(i, translate(z->lo)));
  TreeNode *test = translate(boolexpr(z->i, "<=", z->hi));
  TreeNode *bump =
  X(new AssignNode(CloneTree(i), add_to(CloneTree(i), 1)));
  TreeNode *bod = translate(z->body);
  return V(construct_For(init, test, bump, bod));
}

static void *translate_IfStmt(const IfStmt *z)
{
  ExprNode *cond = static_cast<ExprNode *>(z->test->translate());
  IfStmtNode *i =
    new IfStmtNode(cond, translate(z->thenpart), translate(z->elsepart));
  return i->checkIF(false) ? V(i) : V(stmt_to_lowered_block(i));
}

/* Uses the iterators for general domains to iterate through the
   rectangles that comprise a general domain.  This code is based on
   foreachGeneralStart() and foreachGeneralEnd() in code-foreach.cc.
*/
static void *translate_ForEveryRect(const ForEveryRect *z)
{
  int i, arity = translate_type(z->d->type())->tiArity();
  string name = translate_to_string(z->i);
#if 0
  char *header1 = strdup("\n"
			 "PT17tiRectDomainListX7domains2ti Hmdl;\n"
			 "PT25tiRectDomainListIteratorX7domains2ti Hd_iter;\n"
			 "PT9tiDomainX7domains2ti Hd;\n"
			 "jboolean Hiter_cont;\n"
			 "ti5cdescmT9tiDomainX7domains2ti *Hd_desc;\n"
			 "ti5cdescmT17tiRectDomainListX7domains2ti *Hmdl_desc;\n"
			 "ti5cdescmT25tiRectDomainListIteratorX7domains2ti *Hd_iter_desc;");

  char *header2 = strdup("\n"
			 "CLASS_INFO_GLOBAL(Hd_desc, ti5cdescmT9tiDomainX7domains2ti, Hd);\n"
			 "Hmdl = Hd_desc->m13getRectangles(Hd);\n"
			 "CLASS_INFO_GLOBAL(Hmdl_desc, ti5cdescmT17tiRectDomainListX7domains2ti, Hmdl);\n"
			 "Hd_iter = Hmdl_desc->m11newIterator(Hmdl);\n"
			 "CLASS_INFO_GLOBAL(Hd_iter_desc, ti5cdescmT25tiRectDomainListIteratorX7domains2ti, Hd_iter);\n"
			 "do {\n"
			 "  Hiter_cont = !(Hd_iter_desc->m5isEnd(Hd_iter));\n"
			 "  if (Hiter_cont) {\n"
			 "     RDX ");
  
  char *header3 = " = Hd_iter_desc->m11dereference(Hd_iter);\n";

  char *footer = "\n"
    "     Hd_iter_desc->m7advance(Hd_iter);\n"
    "  }\n"
    "} while (Hiter_cont);\n";
#else
  char *header1 = strdup("\n"
			 "PT9tiDomainX7domains2ti Hd;\n"
                         "LTAT13tiRectDomainX7domains2ti Hd_rdarr;\n"
                        );
  char *header2 = strdup("\n"
      "LTAT13tiRectDomain17domains2ti Hd_rdarr;\n"
      "Hd_rdarr = m14getRectsJArraymT19tiMultiRectADomainX7domains2ti(*(PT19tiMultiRectADomainX7domains2ti*)&Hd);\n"
      "if (Hd_rdarr != NULL) {\n"
      "  int Hd_rdcnt;\n"
      "  T13tiRectDomainX7domains2ti *Hd_rdptr;\n"
      "  JAVA_ARRAY_LENGTH_LOCAL(Hd_rdcnt, Hd_rdarr);\n"
      "  JAVA_ARRAY_ADDR_LOCAL(Hd_rdptr, Hd_rdarr, 0, \"foreach over general domain\");\n"
      "  while (Hd_rdcnt--) {\n"
      "    T13tiRectDomainX7domains2ti "
                        );
  char *header3 = " = *(Hd_rdptr++);\n";
  char *footer = "\n } } \n";
#endif

  for (i = 0; header1[i] != '\0'; i++)
    if (header1[i] == 'X')
      header1[i] = '0' + arity;
  for (i = 0; header2[i] != '\0'; i++)
    if (header2[i] == 'X')
      header2[i] = '0' + arity;

  llist<TreeNode *> *l = NULL;
#define P(x) push(l, static_cast<TreeNode *>((x)))
  P(new CodeLiteralNode((string) header1));
  AssignNode *assign_Hd = new AssignNode(new CodeLiteralExprNode("Hd"),
					 K(translate_ACvariable(z->d)));
  P(new ExpressionStmtNode(assign_Hd));
  P(new CodeLiteralNode(header2 + name + header3));
  P(z->body->translate());
  P(new CodeLiteralNode(footer));
#undef P
  free(header1);
  free(header2);
  return new BlockNode(dreverse(l), NULL);
}

static void *translate_Goto(const Label *z)
{
  return V(new GotoNode(mapACLabelToIF(z)));
}

static void *translate_Label(const Label *z)
{
  return V(mapACLabelToIF(z));
}

static void *translate_Fail(const Fail *z)
{
  extern TreeNode *fail_label;
  llist<TreeNode *> *l = NULL;
  // push(l, new CodeLiteralNode("/* " + z->s + " */"));
  push(l, new CodeLiteralNode("/* printf(\"cannot use megatile: !(" + z->s + ")\\n\"); */"));
  push(l, new GotoNode(fail_label));
  return V(new BlockNode(dreverse(l), NULL));
}

static void *translate_StackAlloc(const StackAlloc *z)
{
  string v = translate_to_string(z->result), t = Ctype(z->T),
    count = translate_to_string(z->count),
    args = z->cast ?
    (Ctype(z->result->type()) + ", " + t + ", " + v + ", " + count) :
    (t + ", " + v + ", " + count),
    fn = z->cast ? "STOPTIFU_VARARRAY_CREATE_" : "STOPTIFU_VARARRAY_CREATE";
  return V(new CodeLiteralNode(fn + "(" + args + ");"));
}

static void *translate_StackDealloc(const StackDealloc *z)
{
  return V(new CodeLiteralNode("STOPTIFU_VARARRAY_DESTROY(" +
			       translate_to_string(z->v) + ");"));
}

static string type_prefix(const Ty *t)
{
  if (has_indexed_type(t))
    return type_prefix(t->indexed_type());
  const char *x = t->to_string().c_str();
  char *y = new char [1 + strlen(x)];
  int i = 0;
  while ((y[i] = x[i]))
    if (y[i] == ' ') {
      y[i] = '\0';
      break;
    } else
      ++i;
  string r(y);
  delete[] y;
  return r;
}

static void *translate_SetUnion(const SetUnion *z)
{
  string x = translate_to_string(z->x), y = translate_to_string(z->y),
    tx = type_prefix(z->x->type()), ty = type_prefix(z->y->type()),
    op = ty + "_union";
  if (hasPrefix(tx, "rect"))
    op = tx + "_" + ty + "_approximate_union";
  else {
    if (tx != ty)
      op = tx + "_" + op;
    if (!z->destroy2nd)
      y = ty + "_copy(" + y + ")";
  }
  return V(new CodeLiteralNode(x + " = " + op + "(" + x + ", " + y + ");"));
}  

static void *translate_SetIntersection(const SetIntersection *z)
{
  string x = translate_to_string(z->x), y = translate_to_string(z->y),
    tx = type_prefix(z->x->type()), ty = type_prefix(z->y->type()),
    op = ty + "_intersection";
  if (tx != ty)
    op = tx + "_" + op;
  if (!z->destroy2nd)
    y = ty + "_copy(" + y + ")";
  return V(new CodeLiteralNode(x + " = " + op + "(" + x + ", " + y + ");"));
}

static void *translate_SetCopy(const SetCopy *z)
{
  string x = translate_to_string(z->x), y = translate_to_string(z->y),
    tx = type_prefix(z->x->type()), ty = type_prefix(z->y->type());
  if (tx == ty)
    return V(new CodeLiteralNode(x + " = " + ty + "_copy(" + y + ");"));
  else
    return V(new CodeLiteralNode(x + " = " + ty + "_to_" + tx + "(" + y + ");"));
}

static void *translate_SetToInfinity(const SetToInfinity *z)
{
  string s = translate_to_string(z->v);
  return V(new CodeLiteralNode(s + " = " + string(MAXINT_STRING) + ";"));
}

static void *translate_GetHeadIntervalHiLo(const GetHeadIntervalHiLo *z)
{
  string ss = translate_to_string(z->s), l = translate_to_string(z->lo),
    h = translate_to_string(z->hi), i = "head_interval(" + ss +")";
  string s = "if (" + ss + " == NULL) " +
    l + " = " + h + " = " + string(MAXINT_STRING) + ";"
    " else { " + l + " = " + i + "->lo; " + h + " = " + i + "->hi; }";
  return V(new CodeLiteralNode(s));
}

static void *translate_IndexIvseti(const IndexIvseti *z)
{
  string d = translate_to_string(z->d), s = translate_to_string(z->s),
    i = translate_to_string(z->i);
  string r = d + " = ivseti_is_empty(" + s + ") ? " + s +
    " : ivget(" + i + ", " + s + "->h);";
  return V(new CodeLiteralNode(r));
}

static void *translate_IsEmpty(const IsEmpty *z)
{
  string s = translate_to_string(z->s), p = type_prefix(z->s->type()),
    op = p + "_is_empty";
  ExprNode *t = new CodeLiteralExprNode(op + "(" + s + ")");
  t->type(theBoolType);
  return V(t);
}

/* Depending of types of z->s1 and z->s2, generates a call to one of:
   ivseti_is_shifted_subsetN()
   rectN_is_shifted_subset()
   rectN_ivseti_is_shifted_subset()
   ivseti_rectN_is_shifted_subset()
*/
static void *translate_IsSubset(const IsSubset *z)
{
  const int n = z->offset->size();
  string s1 = translate_to_string(z->s1), s2 = translate_to_string(z->s2),
    p1 = type_prefix(z->s1->type()), p2 = type_prefix(z->s2->type()),
    op = p2 + "_is_shifted_subset", args = s1 + ", " + s2;
  const bool p1rect = hasPrefix(p1, "rect"), p2rect = hasPrefix(p2, "rect");
  if (!p1rect && !p2rect)
    op += i2s(n);
  else if (p1 != p2)
    op = p1 + '_' + op;
  for (int i = 0; i < n; ++i)
    args += ", " + i2s((*(z->offset))[i]);
  ExprNode *t = new CodeLiteralExprNode(op + "(" + args + ")");
  t->type(theBoolType);
  return V(t);
}

static void *translate_SetToEmpty(const SetToEmpty *z)
{
  string s = translate_to_string(z->v), p = type_prefix(z->v->type());
  return V(new CodeLiteralNode(s + " = " + p + "_emptyset();"));
}

static void *translate_OpaqueStmt(const OpaqueStmt *z)
{
  TreeNode *q = ACtoIF(const_cast<OpaqueStmt *>(z));
  return (q == NULL) ?
    AC::translate(z) :
    V(deepCloneWithCrossTreeFixup(q, false));
}

static void *translate_IndexExpr(const IndexExpr *z)
{
  const Ty *arrtype = z->a->type();
  const TypeNode *a = translate_type(arrtype);
  /*
  DBG({
    cout << "Type of indexed array: ";
    a->print(cout, 0);
    cout << endl;
  });
  */
  if (a->isPointType()) {
    ExprNode *t =
      new PointArrayAccessNode(K(z->a->translate()), K(z->i->translate()));
    t->type(theIntType);
    return V(t);
  } else
    return translate_ACexpr(z);
}

/* The rect v has the given arity.  Find its min in the given dimension. */
static TreeNode *rectMin(const ACvar *v, int dim, int arity)
{
  string s = rectMin(empty, dim, arity).substr(1);
  return
    new CodeLiteralFieldAccessNode((TreeNode *) translate_ACvariable(v), s);
}

static TreeNode *rectMax(const ACvar *v, int dim, int arity)
{
  string s = rectUpb(empty, dim, arity).substr(1);
  return add_to(new CodeLiteralFieldAccessNode((TreeNode *)
					       translate_ACvariable(v), s),
		-1);
}

/* AETsm[x] is an initialization of the temp named x.  If x does not
   need to be preloaded then it is not included in the code that is
   generated. */
static map<string, TreeNode *> AETsm;

void ACtrans_reset() { AETsm.clear(); }

static void *translate_DeclareArrayEltTemp(const DeclareArrayEltTemp *z)
{
  TreeNode *decl;
  const string &s = z->varname;
  MakeTemporary(CloneTree(current_StorageAnnotations->i2a(z->access).t),
		decl, AETsm[s], &s);
  return decl;
}

static void *translate_LoadArrayEltTemp(const LoadArrayEltTemp *z)
{
  const string &s = z->varname;
  assert(AETsm[s] != NULL);
  return AETsm[s];
}

/* If the load does tmp=a[x] then this does a[x]=tmp. */
static void *translate_WriteArrayEltTemp(const WriteArrayEltTemp *z)
{
  const string &s = z->varname;
  TreeNode *a = AETsm[s];
  assert(isExpressionStmtNode(a) && isAssignNode(a->child(0)));
  a = a->child(0);
  return new ExpressionStmtNode(new AssignNode(CloneTree(a->opnd1()),
					       CloneTree(a->opnd0())));
}

static void *translate_FuncallExpr(const FuncallExpr *z)
{
  string s;
  bool first = true;
  foreach (e, llist<ACexpr *>, *(z->args)) {
    if (first)
      first = false;
    else
      s += ", ";
    s += translate_to_string(*e);
  }
  ExprNode *t = new CodeLiteralExprNode(z->fn + "(" + s + ")");
  t->type(theBoolType);
  return V(t);
}

static void *translate_UpdateOnly(const UpdateOnly *z)
{
  /* the ForEachStmtNode whose iteration point we are modifying */
  TreeNode *f = ACtoIF(z->f);

  /* Convert ACexprs to strings */
  llist<string *> *l = NULL;
  foreach (e, llist<ACexpr *>, *z->l)
    push(l, (*e == NULL) ? NULL : new string(translate_to_string(*e)));

  TreeNode *do_nothing = new CodeLiteralNode(";");
  UpdatePointBeforeStmtNode *result =
    new UpdatePointBeforeStmtNode(do_nothing, dreverse(l)->to_array(),
				  NULL, NULL, NULL, f);
  result->valuesAreDeltas() = z->isU;
  free_all(l);
  return result;
}

/* AETsm[s] must contain an assignment whose LHS is an ObjectNode for
   the temporary named by s.  Return a clone of that ObjectNode. */
static inline TreeNode *varname_to_ObjectNode(const string &s)
{
  TreeNode *t = AETsm[s];
  if (isExpressionStmtNode(t))
    t = t->child(0);
  return CloneTree(t->opnd0());
}

static inline treepair ts_replacement_as_treepair(const pair<int, rpair> &p,
						  bool is_read)
{
  const int acc = p.first;
  TreeNode *t; // The replacement for access acc
  ACvar *v = p.second.first;
  string index = p.second.second;
  if (index != "") {
    const string vs = translate_to_string(v),
      s = "ACCESS_TEMP_ARRAY(\"" + vs + "\", " + b2s(is_read) +
      ", " + vs + ", " + index + ")";
    ExprNode *tmp = new CodeLiteralExprNode(s);
    tmp->type(translate_type(v->type()->indexed_type(true)));
    t = tmp;
  } else
    t = K(translate_ACvariable(v));
  return treepair(t, current_StorageAnnotations->i2a(acc).t);
}

static void *translate_UpdateAndExecute(const UpdateAndExecute *z)
{
  /* the ForEachStmtNode whose iteration point we are modifying */
  TreeNode *f = ACtoIF(z->f);

  /* Convert ACexprs to strings */
  llist<string *> *l = NULL;
  foreach (e, llist<ACexpr *>, *z->l)
    push(l, (*e == NULL) ? NULL : new string(translate_to_string(*e)));

  /* Construct storage opt info */
  llist<treepair> *els = NULL;  // elided array reads
  llist<treepair> *sirs = NULL; // save in regs
  llist<treepair> *urs = NULL;  // use regs
  {
    /* compute urs */
    map<int, string> *m = z->use_reg();
    if (m != NULL)
      for (map<int, string>::const_iterator i = m->begin(); i != m->end(); i++)
	push(urs, treepair(varname_to_ObjectNode((*i).second),
			   current_StorageAnnotations->i2a((*i).first).t));
    /* compute urs for TS */
    {
      const map<int, rpair> *m = z->replace_read();
      for (map<int, rpair>::const_iterator i = m->begin(); i != m->end(); i++)
	push(urs, ts_replacement_as_treepair(*i, true));
      m = z->replace_write();
      for (map<int, rpair>::const_iterator i = m->begin(); i != m->end(); i++)
	push(urs, ts_replacement_as_treepair(*i, false));
    }
    /* compute els */
    set< pair<string, string> > u; // varname/unused SRAstrs
    foreach (el, llist<opt_read*>, *z->elisions()) {
      const string &varname = (**el).varname;
      treepair p =
	treepair(varname_to_ObjectNode(varname),
		 current_StorageAnnotations->i2a((**el).read->access).t);
      push(els, p);
      /* Keep track of what SRAstrs we're not using */
      u.insert(pair<string, string>(varname, SRAstr(p.second)));
    }
    /* compute sirs */
    foreach (sir, llist<opt_read *>, *z->save_in_reg()) {
      const string &varname = (*sir)->varname;
      treepair p =
	treepair(varname_to_ObjectNode(varname),
		 current_StorageAnnotations->i2a((*sir)->src->access).t);
      /* If the var named by p.first already holds SRAstr(p.second)
	 then don't bother---the var is invariant code wrt the tile stack. */
      if (u.find(pair<string, string>(varname, SRAstr(p.second))) ==
	  u.end())
	push(sirs, p);
    }
  }

  UpdatePointBeforeStmtNode *result =
    new UpdatePointBeforeStmtNode((z->stmt == NULL ?
				   TreeNode::omitted /* means use f's body */ :
				   K(z->stmt->translate())),
				  dreverse(l)->to_array(),
				  els, sirs, urs, f);
  result->valuesAreDeltas() = z->isU;
  free_all(l);
  return result;
}

static void *translate_ComputeAlpha_rect(const ComputeAlpha *z)
{
  const int arity = z->f->arity();
  const string offset =
    translate_to_string(z->p) + "[" + translate_to_string(z->j) + "]",
    result = translate_to_string(z->result);
  llist<TreeNode *> *l = NULL;
#define PUSH(x) push(l, static_cast<TreeNode *>(new CodeLiteralNode(x)))
  for (int i = 0; i < arity; i++)
    PUSH("int r_0_" + i2s(i) + ", r_1_" + i2s(i) + ";");
  for (int i = 0; i < arity; i++) {
    // Note that in the assignments below the LHS has type int and the RHS
    // has type jint.  Shouldn't be a problem.
    TreeNode *lhs, *rhs;
    lhs = new CodeLiteralExprNode("r_0_" + i2s(i));
    rhs = rectMin(z->r, i, arity);
    push(l, new ExpressionStmtNode(new AssignNode(lhs, rhs)));
    lhs = new CodeLiteralExprNode("r_1_" + i2s(i));
    rhs = rectMax(z->r, i, arity);
    push(l, new ExpressionStmtNode(new AssignNode(lhs, rhs)));
  }
  for (int i = 0; i < arity; i++) {
    // handle ith element of f->steps
    const intvector *vec = (*z->f->steps)[i];
    const int d = vec->find_non_zero();
    const string is = i2s(i), ds = i2s(d), offset_1D = offset + "[" + ds + "]";
    PUSH("compute_alpha_1D(" +
	 i2s((*vec)[d]) + ", " +
	 "r_0_" + ds + " - " + offset_1D + ", " +
	 "r_1_" + ds + " - " + offset_1D + ", " +
	 "&" + result + ".l" + is + ", " +
	 "&" + result + ".h" + is + ");");
  } 
  return V(new BlockNode(dreverse(l), NULL));
#undef PUSH
}

static void *translate_ComputeAlpha_ivseti(const ComputeAlpha *z)
{
  const int arity = z->f->arity();
  const string offset =
    translate_to_string(z->p) + "[" + translate_to_string(z->j) + "]";
  llist<TreeNode *> *l = NULL;
#define PUSH(x) push(l, static_cast<TreeNode *>(new CodeLiteralNode(x)))
  PUSH("int *rr[2], rr0[" + i2s(arity) + "], rr1[" + i2s(arity) + "];");
  PUSH("rr[0] = rr0; rr[1] = rr1;");
  for (int i = 0; i < arity; i++) {
    // Note that in the assignments below the LHS has type int and the RHS
    // has type jint.  Shouldn't be a problem.
    TreeNode *lhs, *rhs;
    lhs = new CodeLiteralExprNode("rr[0][" + i2s(i) + "]");
    rhs = rectMin(z->r, i, arity);
    push(l, new ExpressionStmtNode(new AssignNode(lhs, rhs)));
    lhs = new CodeLiteralExprNode("rr[1][" + i2s(i) + "]");
    rhs = rectMax(z->r, i, arity);
    push(l, new ExpressionStmtNode(new AssignNode(lhs, rhs)));
  }
  PUSH(translate_to_string(z->result) + " = ivseti_compute_alpha(" +
       i2s(arity) + ", " +
       offset + ", " +
       translate_to_string(z->v) + ", " +
       translate_to_string(z->vi) + ", " +
       i2s(z->k) + ", rr, COMPUTE_ALPHA_DEBUG_LEVEL);");
  return V(new BlockNode(dreverse(l), NULL));
#undef PUSH
}

static void *translate_ComputeAlpha(const ComputeAlpha *z)
{
  if (type_prefix(z->result->type()) == "ivseti")
    return translate_ComputeAlpha_ivseti(z);
  else
    return translate_ComputeAlpha_rect(z);
}

static void *translate_Foreach(const Foreach *f, const ACvar *p,
			       const ACvar *D, const AC *body)
{
  llist<TreeNode *> *l = NULL;
  push(l, new CodeLiteralNode("/* foreach that was not tiled */"));
  push(l, ACtoIF((AC *) f));
  return V(new BlockNode(dreverse(l), NULL));
}

static void *default_translate_AC_to_IF(const AC *z)
{
  TreeNode *x = ACtoIF(const_cast<AC *>(z));
  if (x == NULL) {
    ostringstream o;
    z->print(o);
    x = new CodeLiteralNode(o.str());
  } else
    x = deepCloneWithCrossTreeFixup(x, false);
  return V(x);
}

#undef K
#undef V

void ACtranslations()
{
  AC::translator = &default_translate_AC_to_IF;
  Block::translator = &translate_Block;
  ACBroadcast::translator = &translate_ACBroadcast;
  ACDecl::translator = &translate_Decl;
  ACexpr::translator = &translate_ACexpr;
  ACexprStmt::translator = &translate_ACexprStmt;
  ACvariable::translator = &translate_ACvariable;
  ACconstant::translator = &translate_ACconstant;
  WhileLoop::translator = &translate_WhileLoop;
  ForLoop::translator = &translate_ForLoop;
  SetiIter::translator = &translate_SetiIter;
  IfStmt::translator = &translate_IfStmt;
  ComputeAlpha::translator = &translate_ComputeAlpha;
  ForEveryRect::translator = &translate_ForEveryRect;
  Label::translator = &translate_Label;
  Fail::translator = &translate_Fail;
  Goto::translator = &translate_Goto;
  StackAlloc::translator = &translate_StackAlloc;
  StackDealloc::translator = &translate_StackDealloc;
  FuncallExpr::translator = &translate_FuncallExpr;
  IsSubset::translator = &translate_IsSubset;
  IsEmpty::translator = &translate_IsEmpty;
  SetToEmpty::translator = &translate_SetToEmpty;
  SetToInfinity::translator = &translate_SetToInfinity;
  SetCopy::translator = &translate_SetCopy;
  SetUnion::translator = &translate_SetUnion;
  SetIntersection::translator = &translate_SetIntersection;
  GetHeadIntervalHiLo::translator = &translate_GetHeadIntervalHiLo;
  IndexIvseti::translator = &translate_IndexIvseti;
  IndexExpr::translator = &translate_IndexExpr;
  OpaqueStmt::translator = &translate_OpaqueStmt;
  UpdateAndExecute::translator = &translate_UpdateAndExecute;
  UpdateOnly::translator = &translate_UpdateOnly;
  BinaryExpr::translator = &translate_BinaryExpr;
  UnaryExpr::translator = &translate_UnaryExpr;
  ACDebug::translator = &translate_ACDebug;
  Foreach::translator = &translate_Foreach;
  ACStat::translator = &translate_ACStat;
  GatherStats::translator = &translate_GatherStats;
  DeclareArrayEltTemp::translator = &translate_DeclareArrayEltTemp;
  LoadArrayEltTemp::translator = &translate_LoadArrayEltTemp;
  WriteArrayEltTemp::translator = &translate_WriteArrayEltTemp;
  /*
  X::translator = &translate_X;
  X::translator = &translate_X;
  */
}