/* code-MIVE.cc */

/*

  MIVE stands for "Map Induction Variables to Expressions."  The goal
  is to construct a function for every expression such that the
  function maps the induction variable(s) of enclosing loops to the
  value of the expression.

*/

#include <iostream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include "osstream.h"
#include "utils.h"
#include "AST.h"
#include "CodeContext.h"
#include "decls.h"
#include "errors.h"
#include "interface.h"
#include "code.h"
#include "code-MIVE.h"
#include "code-util.h"
#include "code-foreach.h"
#include "Worklist.h"
#include "optimize.h"
#include "pseudocode.h"
#include "MIVEset.h"

#define DEBUG_MIVE (DEBUG_PHASE_ENABLED("MIVE", currentFilename)	\
		    || DEBUG_PHASE_ENABLED("mive", currentFilename))

extern Worklist *current_worklist;

/* Note that we don't care about modifiers (such as single) here. */
#define isIntType(type) \
    ((type)->isIntegralType() && (type)->kind() == Common::IntKind)

#define PMIVE(m) ((m) ? (((m)->print(cout)), "") : "NULL")

/////////////////////////////////////////////////////////////////////////////
// some methods for class MIVEcontext
/////////////////////////////////////////////////////////////////////////////

Poly * MIVEcontext::introduceVar(string name, TreeNode *t, int index)
{
  static int n = 0;

  if (DEBUG_MIVE) {
    cout << "Introducing " << name;
    if (index == SCALAR) cout << " for int:\n";
    else cout << " for index " << index << " of";
    if (isForEachStmtNode(t))
      cout << " foreach at " << t->position().asString();
    else {
      cout << '\n';
      t->pseudoprint(cout, 3);
    }
    cout << '\n';
  }

  PolyFactor f(n++, name);
  PolyFactorToTreeNode(f) = t;
  PolyFactorToIndexWithinTreeNode(f) = index;
  return newPoly(f);
}

string PolyFactor_to_string(MIVEcontext *e, PolyFactor f, CodeContext &context)
{
  TreeNode *t = e->PolyFactorToTreeNode(f);
  int i = e->PolyFactorToIndexWithinTreeNode(f);
  assert(t != NULL);
  if (i != SCALAR) {
    if (isForEachStmtNode(t))
      return *iterationPoint(t, i);
    t = new PointArrayAccessNode(t, new PrimitiveLitNode(Literal((int32) i)));
    string r = t->emitExpression(context);
    delete t;
    return r;
  } else
    return t->emitExpression(context);
} 

// If t is an object node with a namenode as its child and we have
// source for the var decl then change t to the var decl.
static void setToVarDeclSource(TreeNode *& t)
{
  Decl *d;
  if (isObjectNode(t) &&
      isNameNode(t->child(0)) &&
      ((d = t->child(0)->decl()) != NULL) &&
      d->hasSource() && 
      d->source() != NULL)
    t = d->source();
}

/* If the type of t is point<n> or int then return variables for it,
   creating them if necessary.  t is loop invariant with respect to
   foreach loop l. */
MIVE * MIVEcontext::introduceInv(TreeNode *t, TreeNode *l)
{
  static int n = 0;

  // Literals shouldn't be dealt with here because the only kind of
  // literal we care about are int literals, and we don't need
  // variables to handle them!
  if (isPrimitiveLitNode(t)) return NULL;

  TreeNode *expr = t; // To be used later if we need to codeGen this var.

  setToVarDeclSource(t);

  TypeNode *T;

  if (isExprNode(t))
    T = t->type();
  else if (isVarDeclNode(t))
    T = t->dtype();
  else {
    if (DEBUG_LOOP_INVAR) {
      cout << "Unable to get symbolic variable(s) for ";
      cout << PCODE(t);
      cout << endl;
    }
    return NULL;
  }

  // shouldn't happen
  if (T == NULL)
    return NULL;

  if (DEBUG_LOOP_INVAR) {
    cout << "Getting symbolic variable(s) for ";
    cout << PCODE(t);
    cout << " ";
    T->print(cout, 0);
    cout << endl;
  }

  if (T->isPointType()) {
    int arity = T->tiArity();
    Poly **p = newPolyArray(arity);
    for (int i = 1; i <= arity; i++) {
      if (exprToPoly(t, i) == NULL) // Job not already done
	exprToPoly(t, i) =
	  introduceVar(string("<i") + int2string(n) + ">[" + int2string(i) + "]",
		       expr, i);
      p[i - 1] = exprToPoly(t, i);
    }
    n++;
    return new MIVE(T, this, p);
  } else if (isIntType(T)) {
    if (exprToPoly(t, SCALAR) == NULL) 
      exprToPoly(t, SCALAR) =
	introduceVar(string("<i") + int2string(n) + ">", expr, SCALAR);
    n++;
    return new MIVE(this, exprToPoly(t, SCALAR));
  } else
    return NULL;
}

// Called when we enter a foreach loop.  Variables are created for the
// iteration var and for invariants.  Returns a MIVE * for the
// iteration variable.
MIVE * MIVEcontext::adjoin(const string *var, int arity, TreeNode *t)
{
  Poly **p = newPolyArray(arity);

  for (int i = 1; i <= arity; i++)
    p[i - 1] = introduceVar(*var + '[' + int2string(i) + ']', t, i);

  return new MIVE(makePointType(arity), this, p);
}

///////////////////////////////////////////////////////////////////////////
// setMIVE(), getMIVE()
///////////////////////////////////////////////////////////////////////////

static map_tree_tree_to_MIVE *the_m = NULL;

void TreeNode::setMIVE(TreeNode *l, MIVE *p)
{
  if (the_m == NULL)
    the_m = new map_tree_tree_to_MIVE;
  (*the_m)[this][l] = p;
}

MIVE * TreeNode::getMIVE(TreeNode *l)
{
  if (the_m == NULL)
    the_m = new map_tree_tree_to_MIVE;
  return (*the_m)[this][l];
}

///////////////////////////////////////////////////////////////////////////
// computeMIVE()
///////////////////////////////////////////////////////////////////////////

static map_tree_to_MIVEcontext *the_mc;

MIVEcontext *& MIVEcontextOfLoop(TreeNode *l)
{
  if (the_mc == NULL)
    the_mc = new map_tree_to_MIVEcontext;
  return (*the_mc)[l];
}

void TreeNode::computeMIVE(TreeNode *WRTloop, void action(TreeNode *, TreeNode *, MIVE *))
{
  foriter (c, allChildren(), ChildIter)
    (*c)->computeMIVE(WRTloop, action);
}

void ExprNode::computeMIVE(TreeNode *WRTloop,
			   void action(TreeNode *, TreeNode *, MIVE *))
{
  MIVEcontext *e = MIVEcontextOfLoop(WRTloop);
  foriter (c, allChildren(), ChildIter)
    (*c)->computeMIVE(WRTloop, action);

  action(this, WRTloop, defaultMIVE(e));
}

void AssignNode::computeMIVE(TreeNode *WRTloop,
			     void action(TreeNode *, TreeNode *, MIVE *))
{
  opnd1()->computeMIVE(WRTloop, action);
  opnd0()->computeMIVE(WRTloop, action);
  MIVE *m = opnd1()->getMIVE(WRTloop);
  defaultOrSetMIVE(m, WRTloop, action);
  opnd0()->defaultOrSetMIVE(m, WRTloop, action);
}

void CastNode::computeMIVE(TreeNode *WRTloop,
			   void action(TreeNode *, TreeNode *, MIVE *))
{
  opnd0()->computeMIVE(WRTloop, action);
  assert(!type()->isPointType() ||
	 type()->tiArity() == opnd0()->type()->tiArity());
  MIVE *m = ((isIntType(type()) || type()->isPointType()) ?
	     opnd0()->getMIVE(WRTloop) :
	     (MIVE *) 0);
  defaultOrSetMIVE(m, WRTloop, action);
}

#define SHOW_IF_DEBUGGING_ON(use, def) 		\
(DEBUG_MIVE ?					\
 ((cout << "Reaching MIVE "),			\
  (cout << SHOWMIVE(p)),			\
  (cout << " (from "),				\
  (cout << PCODE(use)),				\
  (cout << " to "),				\
  (cout << PCODE(def)),				\
  (cout << " in "),				\
  (cout << PCODE(def->parent()->parent())),	\
  (cout << ")"),				\
  (cout << endl), 0) :				\
 0)

#define SHOW(x, use, def) ((x), SHOW_IF_DEBUGGING_ON((use), (def)), p)

/* Attempt to use dataflow to figure out a polynomial for this
   namenode.  This is done by looking at the reaching defs (often
   there is only one) and using the poly from there, if all such
   defs have the same poly. */
void NameNode::computeMIVE(TreeNode *WRTloop,
			   void action(TreeNode *, TreeNode *, MIVE *))
{
  TreeNode *t = parent();
  if (isObjectNode(t)) {
    if (isLHSofAssignNode(t)) {
      defaultOrSetMIVE(t->parent()->opnd1()->getMIVE(WRTloop),
		       WRTloop, action);
      return;
    }
    llist<TreeNode *> *defs = t->getDefs();
    MIVE *p = NULL;
    foreach (u, llist<TreeNode *>, *defs) {
      TreeNode *source = valueTransferred((*u), t);
      if (source == NULL ||
	  (p != NULL) && !p->equals(source->getMIVE(WRTloop)) ||
	  (SHOW(p = source->getMIVE(WRTloop), *u, this) == NULL))
	goto useDefault;
    }
    defaultOrSetMIVE(p, WRTloop, action);
    return;
  }
 useDefault:
  MIVEcontext *e = MIVEcontextOfLoop(WRTloop);
  action(this, WRTloop, defaultMIVE(e));
}

#undef SHOW

void ObjectNode::computeMIVE(TreeNode *WRTloop, void action(TreeNode *, TreeNode *, MIVE *))
{
  name()->computeMIVE(WRTloop, action);
  defaultOrSetMIVE(name()->getMIVE(WRTloop), WRTloop, action);
}

void PointNode::computeMIVE(TreeNode *WRTloop, void action(TreeNode *, TreeNode *, MIVE *))
{
  llist < Poly * > *q = NULL;
  foriter (c, child(0)->allChildren(), ChildIter) {
    (*c)->computeMIVE(WRTloop, action);
    MIVE *m = (*c)->getMIVE(WRTloop);
    push(q, (m == NULL || m->unknown()) ? (Poly *)NULL : m->p[0]);
  }
  elementwiseMIVE(dreverse(q), WRTloop, action);
}

/*
void xNode::computeMIVE(TreeNode *WRTloop, void action(TreeNode *, TreeNode *, MIVE *))
{
  MIVEcontext *e = MIVEcontextOfLoop(WRTloop);
} */

//////////////////////////////////////////////////////////////////////////////
// defaultMIVE(), defaultOrSetMIVE(), elementwiseMIVE()
//////////////////////////////////////////////////////////////////////////////

MIVE * TreeNode::defaultMIVE(MIVEcontext *) const
{
  return NULL;
}

MIVE * ExprNode::defaultMIVE(MIVEcontext *e) const
{
  TypeNode *type = ((TreeNode *)this)->type();
  if (type->isPointType()) {
    int n = type->tiArity();
    Poly **p = newPolyArray(n);
    for (int i = 0; i < n; i++)
      p[i] = e->exprToPoly(this, i + 1);

    return new MIVE(type, e, p);
  } else if (isIntType(type))
    return new MIVE(type, e, &e->exprToPoly(this, SCALAR));
  else
    return NULL;
}

MIVE * PrimitiveLitNode::defaultMIVE(MIVEcontext *e) const
{
  TypeNode *type = ((TreeNode *)this)->type();

  if (isIntType(type))
    return new MIVE(e, newPoly(literal().intValue()));
  else
    return NULL;
}

void TreeNode::defaultOrSetMIVE(MIVE *m, TreeNode *WRTloop,
				void action(TreeNode *, TreeNode *, MIVE *))
{
  MIVEcontext *e = MIVEcontextOfLoop(WRTloop);
  if (m == NULL || m->unknown())
    m = defaultMIVE(e);

  action(this, WRTloop, m);
}

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

#define NO							\
do {								\
  if (DEBUG_LOOP_INVAR)						\
    cout << "literalFromDef(" << pseudocode1(t) << "): NULL\n";	\
  return NULL;							\
} while (0)

/* If a single def reaches t and t's value is thus a known integer or
   point then return a MIVE representing that integer or point.
   Otherwise return NULL. */
static MIVE * literalFromDef(MIVEcontext *e, TreeNode *t)
{
  if (isNameNode(t) && isObjectNode(t->parent()))
    t = t->parent();
  MIVE *ret = NULL;
  llist<TreeNode *> *defs = t->getDefs();
  if (defs == NULL || defs->size() != 1)
    NO;
  TreeNode *def = defs->front();
  if (isAssignNode(def))
    if (isPrimitiveLitNode(def->opnd1())) {
      TypeNode *ty = def->opnd1()->type();
      if (!isIntType(ty))
	NO;
      ret = new MIVE(e, newPoly(def->opnd1()->literal().intValue()));
    } else if (isPointNode(def->opnd1())) {
      TypeNode *type = def->opnd1()->type();
      int n = type->tiArity();
      Poly **p = newPolyArray(n);
      for (int i = 0; i < n; i++) {
	TreeNode *w = def->opnd1()->child(0)->child(i);
	if (isPrimitiveLitNode(w) && isIntType(w->type()))
	  p[i] = newPoly(w->literal().intValue());
	else
	  NO;
      }
      ret = new MIVE(type, e, p);
    }

  if (DEBUG_LOOP_INVAR && ret != NULL) {
    cout << "MIVE "; cout << PMIVE(ret);
    cout << " for loop invariant "; cout << PCODE(t); cout << endl;
  }
  return ret;
}
#undef NO

void TreeNode::elementwiseMIVE(llist < Poly * > *q, TreeNode *WRTloop,
			       void action(TreeNode *, TreeNode *, MIVE *))
{
  MIVEcontext *e = MIVEcontextOfLoop(WRTloop);
  assert(type()->isPointType());
  int n = type()->tiArity();
  Poly **p = newPolyArray(n);
  for (int i = 0; i < n; i++) {
    p[i] = (q->front() == NULL) ?
      e->exprToPoly(this, i) :
      q->front();
    q = q->tail();
  }
  
  action(this, WRTloop, new MIVE(type(), e, p));
}

/////////////////////////////////////////////////////////////////////////////
// handling +, -, *, selection and point construction
/////////////////////////////////////////////////////////////////////////////

static MIVE *safeAdd(MIVE *a, MIVE *b)
{
  return (a == NULL || b == NULL) ? (MIVE *) NULL : a->add(b);
}

static MIVE *safeMult(MIVE *a, MIVE *b)
{
  return (a == NULL || b == NULL) ? (MIVE *) NULL : a->mult(b);
}

static MIVE *safeNegate(MIVE *a)
{
  return (a == NULL) ? (MIVE *) NULL : a->negate();
}

static MIVE *safeBest(MIVE *x, MIVE *y)
{
  return (x == NULL) ? y : x->best(y);
}


#define GET0() opnd0()->getMIVE(WRTloop)
#define GET1() opnd1()->getMIVE(WRTloop)

void UnaryPlusNode::computeMIVE(TreeNode *WRTloop,
				void action(TreeNode *, TreeNode *, MIVE *))
{
  opnd0()->computeMIVE(WRTloop, action);
  defaultOrSetMIVE(GET0(), WRTloop, action);
}
     
void UnaryMinusNode::computeMIVE(TreeNode *WRTloop,
				 void action(TreeNode *, TreeNode *, MIVE *))
{
  opnd0()->computeMIVE(WRTloop, action);
  defaultOrSetMIVE(safeNegate(GET0()), WRTloop, action);
}
     
void PlusNode::computeMIVE(TreeNode *WRTloop,
			   void action(TreeNode *, TreeNode *, MIVE *))
{
  opnd0()->computeMIVE(WRTloop, action);
  opnd1()->computeMIVE(WRTloop, action);
  defaultOrSetMIVE(safeAdd(GET0(), GET1()), WRTloop, action);
}

void MinusNode::computeMIVE(TreeNode *WRTloop,
			    void action(TreeNode *, TreeNode *, MIVE *))
{
  opnd0()->computeMIVE(WRTloop, action);
  opnd1()->computeMIVE(WRTloop, action);
  defaultOrSetMIVE(safeAdd(GET0(), safeNegate(GET1())), WRTloop, action);
}

void MultNode::computeMIVE(TreeNode *WRTloop,
			   void action(TreeNode *, TreeNode *, MIVE *))
{
  opnd0()->computeMIVE(WRTloop, action);
  opnd1()->computeMIVE(WRTloop, action);
  defaultOrSetMIVE(safeMult(GET0(), GET1()), WRTloop, action);
}

void ArrayAccessNode::computeMIVE(TreeNode *WRTloop,
				  void action(TreeNode *, TreeNode *, MIVE *))
{
  MIVEcontext *e = MIVEcontextOfLoop(WRTloop);
  MIVE *result = NULL;

  array()->computeMIVE(WRTloop, action);
  index()->computeMIVE(WRTloop, action);
  if (array()->type()->isPointType()) {
    MIVE *im = index()->getMIVE(WRTloop);
    MIVE *am = array()->getMIVE(WRTloop);
    if (!(im == NULL || im->unknown() || !im->p[0]->constantp()
	  || am == NULL || am->unknown())) {
      assert(im->arity() == SCALAR);
      int i = im->p[0]->constantTerm();
      int n = array()->type()->tiArity();
      if (i < 1 || i > n)
	warning("point-bounds") << "Point access is out of bounds" << endl;
      else
	result = new MIVE(e, am->p[i - 1]);
    }
  }
  defaultOrSetMIVE(result, WRTloop, action);
}


#define left() \
   (child(0)->child(0)->computeMIVE(WRTloop, action), \
    child(0)->child(0)->getMIVE(WRTloop))
#define right() \
   (child(1)->child(0)->computeMIVE(WRTloop, action), \
    child(1)->child(0)->getMIVE(WRTloop))

void MethodCallNode::computeMIVE(TreeNode *WRTloop,
				 void action(TreeNode *, TreeNode *, MIVE *))
{
  MIVEcontext *e = MIVEcontextOfLoop(WRTloop);
  switch (arithCall(this)) {
  case '+':
    action(this, WRTloop, safeBest(safeAdd(left(), right()), defaultMIVE(e)));
    return;
  case '-':
    action(this, WRTloop, safeBest(safeAdd(left(), safeNegate(right())), defaultMIVE(e)));
    return;
  case '*':
    action(this, WRTloop, safeBest(safeMult(left(), right()), defaultMIVE(e)));
    return;
  default:
    ExprNode::computeMIVE(WRTloop, action);
  }
}
#undef left
#undef right

#define MIVEops(op)						\
MIVE * MIVE::op(const MIVE *x) const				\
{								\
  assert(!(this == NULL || x == NULL));				\
  if (x->unknown() || unknown()) return NULL;			\
  int n = arity();						\
								\
  if (n == SCALAR)						\
    return x->op(p[0]);						\
  else if (x->arity() == SCALAR)				\
    return op(x->p[0]);						\
								\
  /* operation on two points */					\
								\
  assert(x->arity() == n);					\
								\
  /* If either is unknown, return unknown */			\
  if (unknown()) return (MIVE *)this;				\
  if (x->unknown()) return (MIVE *)x;				\
								\
  Poly **newp = newPolyArray(n);				\
  for (int i = 0; i < n; i++)					\
    newp[i] = (p[i] == NULL || x->p[i] == NULL) ? (Poly *)NULL	\
      : (Poly *)p[i]->op(x->p[i]);				\
  return new MIVE(exprType, e, newp);				\
}								\
								\
MIVE * MIVE::op(const Poly *q) const				\
{								\
  assert(!(this == NULL || q == NULL));				\
  if (unknown()) return NULL;					\
  if (noPolysPresent()) return (MIVE *)this;			\
  int n = arity();						\
  if (n == SCALAR) n = 1;					\
  Poly **newp = newPolyArray(n);				\
  while (n-- > 0)						\
    newp[n] = (q == NULL || p[n] == NULL) ? (Poly *)NULL	\
	: (Poly *)p[n]->op(q);					\
  return new MIVE(exprType, e, newp);				\
}

MIVEops(mult)
MIVEops(add)

MIVE * MIVE::negate() const
{
  if (this == NULL) return NULL;
  if (noPolysPresent()) return (MIVE *)this;
  int n = arity();
  if (n == SCALAR) n = 1;
  Poly **newp = newPolyArray(n);
  while (n-- > 0)
    newp[n] = (p[n] == NULL) ? (Poly *)NULL : (Poly *)p[n]->negate();

  return new MIVE(exprType, e, newp);
}

/////////////////////////////////////////////////////////////////////////////
// miscellaneous
/////////////////////////////////////////////////////////////////////////////

/* Returns something that looks like this except that NULL
polynomials, if any, are replaced by the corresponding poly in x. */
MIVE * MIVE::best(MIVE *x) const
{
  if (x == NULL)
    return (MIVE *) this;

  int n = arity();
  assert(n == x->arity());
  if (unknown())
    return x;
  else if (x->unknown() || n == SCALAR || allPolysPresent())
    return (MIVE *)this;
  else {
    Poly **newp = newPolyArray(n);
    for (int i = 0; i < n; i++)
      newp[i] = (p[i] == NULL) ? x->p[i] : p[i];
    return new MIVE(exprType, e, newp);
  }    
}

/* Returns true iff none of the polynomial pointers in the array
   this->p are NULL. */
bool MIVE::allPolysPresent() const
{
  if (p == NULL) return false;

  int n = arity();
  if (n == SCALAR) n = 1;
  while (n-- > 0)
    if (p[n] == NULL) return false;

  return true;
}

/* Returns true iff all of the polynomial pointers in the array
   this->p are NULL. */
bool MIVE::noPolysPresent() const
{
  if (p == NULL) return true;

  int n = arity();
  if (n == SCALAR) n = 1;
  while (n-- > 0)
    if (p[n] != NULL) return false;

  return true;
}

void MIVE::print(ostream &os) const
{
  if (this == NULL || unknown())
    os << "unknown";
  else {
    if (exprType->isPointType()) os << '[';
    int n = exprType->isPointType() ? exprType->tiArity() : 1;
    for (int i = 0; i < n; i++) {
      if (i > 0) os << ", ";
      p[i]->print(os);
    }
    if (exprType->isPointType()) os << ']';
  }
}

string stringify(const MIVE *m)
{
  if (m == NULL)
    return "unknown";
  ostringstream s;
  m->print(s);
  return s.str();
}


bool equalMIVE(const MIVE *x, const MIVE *y)
{
  if (DEBUG_MIVE) {
    cout << "Checking if "; cout << PMIVE(x); cout << " and ";
    cout << PMIVE(y); cout << " are provably equal: ";
  }

#define R(v, s)						\
  do if (DEBUG_MIVE) {					\
    if (v) { cout << "yes" << endl; return true; }	\
    else { cout << (s) << endl; return false; }		\
  } else return (v); while (0)

  if (x == NULL || y == NULL)
    R(false, "one or both are unknown");
  if (x->e != y->e)
    R(false, "different MIVEcontexts");
  if (x->arity() != y->arity())
    R(false, "different arities");
  if (!x->allPolysPresent() || !y->allPolysPresent())
    R(false, "not all polys present");
  int a = x->arity();
  if (a == SCALAR)
    R(x->p[0]->equalp(y->p[0]), "no");
  else
    while (a-- > 0)
      if (!x->p[a]->equalp(y->p[a]))
	R(false, "no");

  R(true, "");
#undef R
}

bool sameInfo(const MIVE *x, const MIVE *y)
{
  if (DEBUG_MIVE) {
    cout << "Checking if "; cout << PMIVE(x); cout << " and ";
    cout << PMIVE(y); cout << " convey the same info: ";
  }

#define R(v, s)						\
  do if (DEBUG_MIVE) {					\
    if (v) { cout << "yes" << endl; return true; }	\
    else { cout << (s) << endl; return false; }		\
  } else return (v); while (0)

  if (x == NULL && y == NULL)
    R(true, "yes");
  if (x == NULL || y == NULL)
    R(false, "one is unknown");
  if (x->e != y->e)
    R(false, "different MIVEcontexts");
  if (x->arity() != y->arity())
    R(false, "different arities");
  if (x->allPolysPresent() != y->allPolysPresent())
    R(false, "not all polys present");
  int a = x->arity();
  if (a == SCALAR)
    R(((x->p[0] == y->p[0]) ||
       (x->p[0] != NULL) && x->p[0]->equalp(y->p[0])),
      "no");
  else
    while (a-- > 0)
      if (!((x->p[a] == y->p[a]) ||
	    (x->p[a] != NULL) && x->p[a]->equalp(y->p[a])))
	R(false, "no");
  
  R(true, "");
#undef R
}

/* Return the MIVE in l equal to this, if any.  If no MIVE in l is equal to
   this, then add this to l and return this. */
MIVE * MIVE::find(llist<MIVE *> * & l) const
{
  if (l == NULL) {
    l = cons((MIVE *) this);
    return (MIVE *) this;
  } else if (equals(l->front()))
    return l->front();
  else
    return find(l->tail());
}

/* Return the MIVE in l equal to this, if any.  If no MIVE in l is equal to
   this, then add this to l and return this. */
const MIVE * MIVE::find(llist<const MIVE *> * & l) const
{
  if (l == NULL) {
    l = cons(this);
    return this;
  } else if (equals(l->front()))
    return l->front();
  else
    return find(l->tail());
}

const Poly *& MIVEcontext::derivtab(PolyFactor f, PolyFactor g)
{
  return d[f.varNum][g.varNum];
}

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

/* The MIVE of t (with respect to given loop) is m. */
/* Record this fact and add appropriate items to the worklist. */
void gotMIVE(TreeNode *t, TreeNode *WRTloop, MIVE *m)
{
  MIVE *old = t->getMIVE(WRTloop);

  /* If m is not NULL but contains no useful information, set it to NULL. */
  if (m != NULL && (m->p == NULL || m->noPolysPresent()))
    m = NULL;

  /* If we have a MIVE of NULL and t is loop invariant, we may be able
     to introduce new variables to represent the value and build a MIVE
     from these new variables. Or we may use an integer constant, if there
     is only one def that reaches t and that def looks like, say, "x = 7". */
  if (m == NULL && old == NULL && isInvar(t, WRTloop) &&
      !isLHSofAssignNode(t)) {
    MIVEcontext *e = MIVEcontextOfLoop(WRTloop);
    m = literalFromDef(e, t);
    if (m == NULL)
      m = e->introduceInv(t, WRTloop);
  }

  // This prevents us from replacing the MIVE for t with a less informative
  // MIVE.  I don't know why it is necessary, but it is.
  m = safeBest(m, old);

  /* If old and m convey the same info then return. */
  if (old == m ||
      m != NULL && m->sameInfo(old)) return;

  t->setMIVE(WRTloop, m);

  if (DEBUG_MIVE) {
    cout << "Set MIVE of {" << t->oper_name() << "} ";
    t->pseudoprint(cout, 0);
    cout << " to ";
    if (m == NULL) cout << "NULL";
    else m->print(cout);
    cout << "\n";
  }

  propagateChanges(current_worklist, t);
}

/* Build a list that contains the given set of nodes. */
llist<const MIVE *> * MIVEset_to_list(const MIVEset *s)
{
  llist<const MIVE *> * result = NULL;
  if (s != NULL)
    for (MIVEset::const_iterator i = s->begin(); i != s->end(); ++i)
      result = cons((const MIVE *) *i, result);
  return result;
}

/////////////////////////////////////////////////////////////////////////////
// Derivatives
/////////////////////////////////////////////////////////////////////////////

MIVE * MIVE::deriv(PolyFactor v)
{
  if (this == NULL) return NULL;
  int n = arity();
  int numPolys = (n == SCALAR) ? 1 : n;

  Poly **newp = newPolyArray(numPolys);
  for (int i = 0; i < numPolys; i++)
    newp[i] = e->deriv(p[i], v);

  return new MIVE(exprType, e, newp);
}


/* Return the derivative of p with respect to v. */
/* A Poly is a sum of terms.  Derivative is sum of derivatives of terms. */
Poly * MIVEcontext::deriv(const Poly *p, PolyFactor v)
{
  if (p == NULL) return NULL;
  const Poly *result = Poly::zero;
  for (list< const PolyTerm *> :: const_iterator k = p->terms->begin();
       result != NULL && k != p->terms->end();
       k++)
    result = safeAdd(result, deriv((*k), v));
  if (debug_sr)
    cout << "d/d" << v.asString() << " (" << p->asString() << ") = " <<
      stringify(result) << endl;

  return (Poly *) result;
}

/* The product of t and p divided by the i'th factor of t. */
/* That is, p times the coefficent of t times all but the i'th factor of t. */
static const Poly *multiplyByOtherFactors(const Poly *p,
					  const PolyTerm *t, int i)
{
  if (p == NULL || t == NULL)
    return NULL;
  const Poly *result = p->mult(t->coefficient);
  int j = 0;
  for (list< PolyFactor > :: iterator k = t->factors->begin();
       result != NULL && k != t->factors->end();
       k++, j++)
    if (j != i)
      result = result->mult(*k);
  return result;
}

/* Return the derivative of t with respect to v. */
/* A PolyTerm is a coefficient times a product of factors.  Use chain rule. */
Poly * MIVEcontext::deriv(const PolyTerm *t, PolyFactor v)
{
  const Poly *result = Poly::zero;
  if (t->constantp())
    return (Poly *) result;
  if (t->factors == NULL)
    return NULL;

  int i = 0;
  for (list< PolyFactor > :: iterator k = t->factors->begin();
       result != NULL && k != t->factors->end();
       k++, i++)
    result = safeAdd(result, multiplyByOtherFactors(derivtab(*k, v), t, i));

  return (Poly *) result;
}

/* t is a loop invariant with respect to l.  Note that the derivative
of t with respect to each loop variable of the foreach loop l is 0. */
static void set0Derivs(TreeNode *t, TreeNode *l)
{
  TypeNode *T;
  MIVE *loopMIVE = l->vars()->child(0)->simpName()->getMIVE(l);
  int arity = loopMIVE->arity();
  setToVarDeclSource(t);
  if (isExprNode(t))
    T = t->type();
  else if (isVarDeclNode(t))
    T = t->dtype();
  else
    return;

  if (T->isPointType())
    arity = T->tiArity();
  else
    arity = SCALAR;
  if (DEBUG_MIVE) {
    cout << "set0Derivs("; cout << PLCODE(t); cout << ") ";
    cout << " arity = " <<
      (arity == SCALAR ? string("scalar") : int2string(arity)) << endl;
  }
  if (arity == SCALAR) {
    if (loopMIVE->e->exprToPoly(t, SCALAR) != NULL)
      loopMIVE->e->set0Derivs(loopMIVE->e->exprToPoly(t, SCALAR)
			      ->asPolyFactor(), l); 
  } else
    for (int i = 1; i <= arity; i++)
      if (loopMIVE->e->exprToPoly(t, i) != NULL)
	loopMIVE->e->set0Derivs(loopMIVE->e->exprToPoly(t, i)
				->asPolyFactor(), l); 
}

/* Note that the derivative of f with respect to each loop variable of
the foreach loop l is 0. */
void MIVEcontext::set0Derivs(PolyFactor f, TreeNode *l)
{
  MIVE *loopMIVE = l->vars()->child(0)->simpName()->getMIVE(l);
  int arity = loopMIVE->arity();
  for (int i = 0; i < arity; i++) {
    derivtab(f, loopMIVE->p[i]->asPolyFactor()) = Poly::zero;
    if (DEBUG_MIVE) {
      cout << "noted that derivative of ";
      f.print(cout);
      cout << " wrt ";
      loopMIVE->p[i]->asPolyFactor().print(cout);
      cout << " is 0\n";
    }
  }
}

#define pf(m, i) (m)->p[(i)]->asPolyFactor()

void setDerivs(TreeNode *l)
{
  MIVEcontext *e = MIVEcontextOfLoop(l);
  TreeNode *pairnode = l->vars()->child(0);
  MIVE *m = pairnode->simpName()->getMIVE(l);
  int n = m->arity();

  /* Set derivtab(p[i], p[j]) to 1 for i = j and 0 otherwise */

  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      e->derivtab(pf(m, i), pf(m, j)) = (i == j) ? Poly::one : Poly::zero;

  /* Set derivtab(x, p[i]) to 0 for all i for each invariant x */

  treeSet *s = l->invariants();
  if (s != NULL) {
    for (treeSet::iterator x = s->begin(); x != s->end(); x++)
      set0Derivs((TreeNode *) *x, l);
  }
}

typedef map< int, bool > map_int_to_bool;
typedef map< const MIVE *, map_int_to_bool > map_cMIVE_int_to_bool;
typedef map< const MIVE *, map_cMIVE_int_to_bool > map_cMIVE_cMIVE_int_to_bool;
typedef map< const MIVE *, map_int_to_int > map_cMIVE_int_to_int;
typedef map< const MIVE *, map_cMIVE_int_to_int > map_cMIVE_cMIVE_int_to_int;

static map_cMIVE_cMIVE_int_to_bool *the_mr = NULL;
static map_cMIVE_cMIVE_int_to_bool &constantDiff_result_memo()
{
  if (the_mr == NULL)
    the_mr = new map_cMIVE_cMIVE_int_to_bool;
  return *the_mr;
}

static map_cMIVE_cMIVE_int_to_int *the_md = NULL;
static map_cMIVE_cMIVE_int_to_int &constantDiff_diff_memo()
{
  if (the_md == NULL)
    the_md = new map_cMIVE_cMIVE_int_to_int;
  return *the_md;
}

/* If the difference between x and y in the given dimension is a known integer
   then set diff to that value and return true.  Otherwise return false.
   Memoized. */
static bool constantDiff(const MIVE *x, const MIVE *y, int dim, int &diff)
{
  if (x == NULL || y == NULL || x->p[dim] == NULL || y->p[dim] == NULL)
    return false;
  map_cMIVE_cMIVE_int_to_bool &memo_result = constantDiff_result_memo();
  map_cMIVE_cMIVE_int_to_int &memo_diff = constantDiff_diff_memo();
  map_int_to_bool &mr = memo_result[x][y];
  map_int_to_int &md = memo_diff[x][y];
  if (mr.find(dim) != mr.end())
    return mr[dim] && ((diff = md[dim]), true);
  
  const Poly *z = x->p[dim]->add(y->p[dim]->negate());
  if (z->constantp()) {
    mr[dim] = true;
    diff = md[dim] = z->asInt();
    return true;
  } else
    return (mr[dim] = false);
}

static bool mustBeLess(const MIVE *x, const MIVE *y, int dim)
{
  int diff;
  if (constantDiff(x, y, dim, diff))
    return (diff < 0);
  else
    return false;
}

static bool mustBeLessOrEqual(const MIVE *x, const MIVE *y, int dim)
{
  int diff;
  if (constantDiff(x, y, dim, diff))
    return (diff <= 0);
  else
    return false;
}

llist<const MIVE *> * mightBeMinimum(llist<const MIVE *> *l, int dim)
{
  llist<const MIVE *> *result = NULL;  
  while (l != NULL) {
    const MIVE *m = l->front();
    bool needed = true;
    for (ListIterator<const MIVE *> i(result); needed && !i.isDone(); i.next())
      if (mustBeLess(m, *i, dim)) {
	*i = m;
	needed = false;
      } else if (mustBeLessOrEqual(*i, m, dim))
	needed = false;
    if (needed)
      result = cons(m, result);
    l = l->tail();
  }
  return result;
}

llist<const MIVE *> * mightBeMaximum(llist<const MIVE *> *l, int dim)
{
  llist<const MIVE *> *result = NULL;  
  while (l != NULL) {
    const MIVE *m = l->front();
    bool needed = true;
    for (ListIterator<const MIVE *> i(result); needed && !i.isDone(); i.next())
      if (mustBeLess(*i, m, dim)) {
	*i = m;
	needed = false;
      } else if (mustBeLessOrEqual(m, *i, dim))
	needed = false;
    if (needed)
      result = cons(m, result);
    l = l->tail();
  }
  return result;
}

/* Should be called after codeGen'ing each method to release dead data
   structures and prevent the possibility of a false memo hit. */
void reset_MIVE()
{
  delete the_m;
  the_m = NULL;
  delete the_mc;
  the_mc = NULL;
  delete the_mr;
  the_mr = NULL;
  delete the_md;
  the_md = NULL;
}