#include <cassert>
#include "utils.h"
#include "AST.h"
#include "CodeContext.h"
#include "CfSource.h"
#include "clone.h"
#include "code.h"
#include "code-util.h"
#include "code-grid.h"
#include "garbageList.h"
#include "nullify-local.h"
#include "optimize.h"
#include "dominator.h"
#include "lower.h"
#include "code-MIVE.h"
#include "Worklist.h"
#include "ullist.h"
#include "cfg.h"

#define FP(t)								  \
do {									  \
  TreeNode *fixee = (t);						  \
  int count, total = 0, passes = 0;					  \
  do {									  \
    total += (count = fixee->fixParent()); passes++;			  \
  } while (count > 0 && passes < 5);					  \
  /*            							  \
  if (total > 0) {							  \
    string s = "/home/pike/bin/msg fixed " + int2string(total) + " in " + \
      int2string(passes) + " passes at " +				  \
      __FILE__ + ':' + int2string(__LINE__);				  \
    system(s.c_str());							  \
  }									  \
  */            							  \
} while (0)

extern void SRsetup();

static void staticAnal(TreeNode *method, bool dominators,
		       bool ignoreNSE = false, bool computeDeps = false);
static TreeNode *optimize(TreeNode *t);

void DummyNode::emitStatement( CodeContext &context ) {}

PrimitiveLitNode *newBoolLit(bool b, SourcePosn p)
{
  return new PrimitiveLitNode(Literal(b), p);
}

/* X should be one of PAR's children.  Make Y be PAR's child in X's place. */
void replaceChild(TreeNode *par, TreeNode *x, TreeNode *y)
{
  for (int i = par->arity(); i-- > 0; )
    if (par->child(i) == x) {
      par->child(i, y);
      return;
    }
  fatal_error("");
}

TreeNode *CloneTree(const TreeNode *t, bool cleanUseDef)
{
  TreeNode *newNode = t->clone();
  if (cleanUseDef) {
    newNode->setUses(NULL);
    newNode->setDefs(NULL);
  }
  const int childCount = newNode->arity();
  for (int sweep = 0; sweep < childCount; ++sweep)
    newNode->child(sweep, CloneTree(newNode->child(sweep), cleanUseDef));

  return newNode;
}

static bool assignablenode(const TreeNode *t) {
  return t->hasLval();
}

static bool objectnode(const TreeNode *t)
{
  return isObjectNode(t);
}

static bool exprnode(const TreeNode *t)
{
  return isExprNode(t);
}

/////////////////////////////////////////////////////////////////////////////
// Utils that return all statements or all exprs that are parts or subparts
//  of a list or set of TreeNodes
/////////////////////////////////////////////////////////////////////////////

static treeSet *vardecls(llist<const TreeNode *> *l, treeSet *result = NULL);
static treeSet *vardecls(const TreeNode *t, treeSet *result = NULL);

// helper for vardecls(), below
static treeSet *vardecls(const TreeNode *t, treeSet *result)
{
  llist<const TreeNode *> *l = cons(t);
  result = vardecls(l, result);
  l->free();
  return result;
}

/* Return result += the set of vardecls that are elements of s or subparts of
   elements of s. */
static treeSet *vardecls(llist<const TreeNode *> *l, treeSet *result)
{
  if (result == NULL)
    result = new treeSet();
  if (l != NULL) {
    if (isVarDeclNode(l->front()))
      result->insert(l->front());
    for (int i = l->front()->arity(); --i >= 0; )
      result = vardecls(l->front()->child(i), result);
    return vardecls(l->tail(), result);
  }
  return result;
}

#if 0
/* Return the set of vardecls that are elements of s or subparts of
   elements of s. */
static treeSet *vardecls(const treeSet *s)
{
  treeSet *result = new treeSet();
  for (treeSet::const_iterator i = s->begin(); i != s->end(); ++i)
    result = vardecls(*i, result);
  return result;
}
#endif

static treeSet *statements(llist<const TreeNode *> *l, treeSet *result = NULL);
static treeSet *statements(const TreeNode *t, treeSet *result = NULL);

// helper for statements(), below
static treeSet *statements(const TreeNode *t, treeSet *result)
{
  llist<const TreeNode *> *l = cons(t);
  result = statements(l, result);
  l->free();
  return result;
}

/* Return result += the set of statements that are elements of s or subparts of
   elements of s. */
static treeSet *statements(llist<const TreeNode *> *l, treeSet *result)
{
  if (result == NULL)
    result = new treeSet();
  if (l != NULL) {
    if (l->front()->isStatementNode())
      result->insert(l->front());
    for (int i = l->front()->arity(); --i >= 0; )
      result = statements(l->front()->child(i), result);
    return statements(l->tail(), result);
  }
  return result;
}

#if 0
/* Return the set of statements that are elements of s or subparts of
   elements of s. */
static treeSet *statements(const treeSet *s)
{
  treeSet *result = new treeSet();
  for (treeSet::const_iterator i = s->begin(); i != s->end(); ++i)
    result = statements(*i, result);
  return result;
}
#endif

static treeSet *exprs(llist<const TreeNode *> *l, treeSet *result = NULL);
static treeSet *exprs(const TreeNode *t, treeSet *result = NULL);

// helper for exprs(), below
static treeSet *exprs(const TreeNode *t, treeSet *result)
{
  llist<const TreeNode *> *l = cons(t);
  result = exprs(l, result);
  l->free();
  return result;
}

/* Return result += the set of exprs that are elements of s or subparts of
   elements of s. */
static treeSet *exprs(llist<const TreeNode *> *l, treeSet *result)
{
  if (result == NULL)
    result = new treeSet();
  if (l != NULL) {
    if (l->front()->isExprNode())
      result->insert(l->front());
    for (int i = l->front()->arity(); --i >= 0; )
      result = exprs(l->front()->child(i), result);
    return exprs(l->tail(), result);
  }
  return result;
}

/* Return the set of exprs that are elements of s or subparts of
   elements of s. */
static treeSet *exprs(const treeSet *s)
{
  treeSet *result = new treeSet();
  for (treeSet::const_iterator i = s->begin(); i != s->end(); ++i)
    result = exprs(*i, result);
  return result;
}

/////////////////////////////////////////////////////////////////////////////
// Foreach Opts 
/////////////////////////////////////////////////////////////////////////////

/* The enclosing loop of a foreach loop, if any */
static map_tree_to_tree enclLoop;

#define REPORT_AND_ADD(x, o)			\
((DEBUG_OPT ?					\
  ((o << " Add "),				\
   (o << PLCODE(x)),				\
   (o << " to worklist"),			\
   (o << endl), 0) :				\
  0),						\
(w)->add((x)))

#define ADD(x, w) do if (isExprNode((x))) REPORT_AND_ADD((x), cout); while (0)

void propagateChanges(Worklist *w, TreeNode *t)
{
  if (DEBUG_OPT)
    cout << "propagateChanges(" << pseudocode1(t) << ")\n";
  ADD(t->parent(), w);
  foreach (u, llist<TreeNode *>, *(t->getUses()))
    ADD(*u, w);
}

#undef ADD
#undef REPORT_AND_ADD

Worklist *current_worklist;

static void invAndPropToCurrentWorklist(TreeNode *t, TreeNode *WRTloop)
{
  if (!isInvar(t, WRTloop)) {
    foundInvariant(t, WRTloop);
    propagateChanges(current_worklist, t);
  }
}

/* INVARIANT_AND_PROPAGATE(w) is used as (lambda (t) (invAndPropTo w t)),
   but since we don't have lambda we use current_worklist as
   a hackish way to store w. */
#define INVARIANT_AND_PROPAGATE(w) \
    ((current_worklist = (w)), invAndPropToCurrentWorklist)

extern void gotMIVE(TreeNode *t, TreeNode *WRTloop, MIVE *m);

#define GOT_MIVE(w) \
    ((current_worklist = (w)), gotMIVE)

/////////////////////////////////////////////////////////////////////////////
// Figure out if t is invariant and/or if we can put a polynomial on it.
/////////////////////////////////////////////////////////////////////////////

static void computeMIVE(TreeNode *t, TreeNode *WRTloop, treeSet *loopContents,
			Worklist *w) 
{
  /* If t is the child of an assignment, work on t's parent instead. */
  if (isAssignNode(t->parent())) {
    w->add(t->parent());
    return;
  }

  /* If t is already known to be invariant there's no need to
     recompute anything, unless t is an assignment, in which case we
     may have improved MIVE info to deal with. */
  bool recompute_all = !isInvar(t, WRTloop), assign = isAssignNode(t);

  /* Determine and record whether it is an invariant. */
  if (recompute_all) 
    t->loopInvariant(WRTloop, loopContents, INVARIANT_AND_PROPAGATE(w));

  /* Try to compute a polynomial describing it. */
  if (recompute_all || assign)
    t->computeMIVE(WRTloop, GOT_MIVE(w));
}

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

/* Build a treeSet that contains the given list of nodes. */
treeSet * list_to_set(llist<TreeNode *> *l)
{
  return new treeSet(l->begin(), l->end());
}

CFGset * list_to_CFGset(llist<CfgNode *> *l)
{
  return new CFGset(l->begin(), l->end());
}

/* The loopAnal pass tags each foreach loop with a list of loop invariants
  and computes polynomials (over invariants and induction variables) that
  represent what certain exprs are computing.  The workhorse is foreachAnal().
*/

void TreeNode::loopAnal(TreeNode *enclosingLoop)
{
  for (int i = arity(); i-- > 0; )
    child(i)->loopAnal(enclosingLoop);
}

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

/* This will terminate because at each step either the worklist gets
   smaller or the information we have gets better.  (And the info
   can only get better a finite number of times.)
*/
static void foreachAnal(ForEachStmtNode *l)
{
  if (DEBUG_LOOP_ANAL)
    cout << endl << "foreachAnal: " << l->position().asString()
	 << endl << endl;
  Worklist w(l);
  treeSet *loopContents = list_to_set(cons(l->vars()->child(0), w.asList()));
  w.filter(exprnode);
  MIVEcontext *e = MIVEcontextOfLoop(l);
  if (e == NULL) {
    e = MIVEcontextOfLoop(l) = new MIVEcontext();
    TreeNode *pairnode = l->vars()->child(0);
    gotMIVE(pairnode->simpName(), l,
	    e->adjoin(pairnode->simpName()->ident(), l->tiArity(), l));
  }

  while (!w.empty()) {
    TreeNode *t = w.pop();
    if (contains(loopContents, t)) {
      if (isExprNode(t)) {
	if (DEBUG_LOOP_ANAL)
	  cout << endl << "Working on: " << pseudocode(t) <<
	    " at " << t->position().asString() << endl << endl;
	computeMIVE(t, l, loopContents, &w);
      } else {
	// should not happen
	cout << "Not an ExprNode: ";
	t->pseudoprint(cout, 2);
	cout << endl;
      }
    }
  }
  delete loopContents;
  
  setDerivs(l);
}

#define isIntType(type) \
    ((type)->isIntegralType() && (type)->kind() == Common::IntKind)

/* If t is a PlusNode (MinusNode) then return true after setting isSum
to true (false).  If t is neither a PlusNode nor a MinusNode then
return false.  */
static bool isSumOrDifference(const TreeNode *t, bool &isSum)
{
  if (isPlusNode(t)) {
    isSum = true;
    return true;
  } else if (isMinusNode(t)) {
    isSum = false;
    return true;
  } else return false;
}

static bool matchingField(const TreeNode *a, const TreeNode *b)
{
  return isNameNode(a) && isNameNode(b) &&
    a->qualifier()->absent() && b->qualifier()->absent() &&
    a->ident() == b->ident();
}

static bool matchingObjOrOFAN(const TreeNode *a, const TreeNode *b)
{
  return isThisNode(a) ? isThisNode(b) :
    ((isObjectNode(a) && isObjectNode(b) &&
      a->name()->decl() == b->name()->decl()) ||
     (isOFAN(a) && isOFAN(b) && matchingObjOrOFAN(a->object(), b->object()) &&
      matchingField(a->simpName(), b->simpName())));
}

static bool ObviouslySameValue(const TreeNode *a, const TreeNode *b)
{
  const TreeNode *ap = a->parent(), *bp = b->parent(),
    *underlyinga = (isObjectNode(a) ? a : (isOFAN(a) ? a->object() : ap)),
    *underlyingb = (isObjectNode(b) ? b : (isOFAN(b) ? b->object() : bp));
  if (DEBUG_LOOP_ANAL)
    cout << "ObviouslySameValue(" << pseudocode(a) << ", " <<
      pseudocode(b) << ")\n";
  if ((!isObjectNode(underlyinga) && !isThisNode(underlyinga)) ||
      (!isObjectNode(underlyingb) && !isThisNode(underlyingb)))
    return false;
  llist<TreeNode *> *da = underlyinga->getDefs(), *db = underlyingb->getDefs();
  if (DEBUG_LOOP_ANAL) {
    cout << "  Defs of " << pseudocode(underlyinga) << ":\n";
    print(da, cout, 1);
    cout << "\n  Defs of " << pseudocode(underlyingb) << ":\n";
    print(db, cout, 1);
    cout << '\n';
  }
  if (db == NULL) {
    swap(da, db);
    swap(a, b);
  }
  bool result = da == NULL && db != NULL && db->tail() == NULL &&
    isAssignNode(b = db->front()) && matchingObjOrOFAN(a, b->opnd1());
  if (DEBUG_LOOP_ANAL) {
    cout << "ObviouslySameValue(" << pseudocode(a) << ", " <<
      pseudocode(b) << "): " << result << "\n";
  }
  return result;
}

static bool matchingNode(const TreeNode *a, const TreeNode *b)
{
  return
      (isObjectNode(a) && isObjectNode(b) &&
       a->name()->decl() == b->name()->decl()) ||
      ObviouslySameValue(a, b);
}

static bool isConstantIncrAssignNode(const TreeNode *e,
				     const ForEachStmtNode *l,
				     int *incrChild)
{
  TreeNode *lhs, *rhs;
  bool isSum;
  return 
    isAssignNode(e) && isSumOrDifference(rhs = e->opnd1(), isSum) &&
    ((matchingNode(lhs = e->opnd0(), rhs->child(0)) &&
      isInvar(rhs->child(*incrChild = 1), l)) ||
     (isSum && matchingNode(lhs, rhs->child(1)) &&
      isInvar(rhs->child(*incrChild = 0), l)));
}
    

static size_t find_or_insert(const TreeNode *t,
			     vector<const TreeNode *> &IVvector)
{
  size_t i, s = IVvector.size();
  for (i = 0; i < s; i++)
    if (matchingNode(t, IVvector[i]))
      return i;
  IVvector.push_back(t);
  return i;
}


// T is a block or a labelled block.  Return first statement inside the block.
static TreeNode *first_stmt(TreeNode *t)
{
  while (isLabeledStmtNode(t))
    t = t->stmt();
  if (t->absent() || isEmptyStmtNode(t))
    return NULL;
  if (isBlockNode(t)) {
    t = t->stmts();
    for (int i = 0; i < t->arity(); ++i)
      if (t->child(i)->isStatementNode())
	return t->child(i);
    return NULL;
  }
  abort();
  return NULL;
}

/* Helper for performIVtransformation(). */
static void createIVpreloop(ForEachStmtNode *l,
			    set<Decl *> &IV,
			    const TreeNode *assn,
			    llist<TreeNode *> *& stmts,
			    llist<TreeNode *> *& decls,
			    map<size_t, const TreeNode *> &map_index_to_incr,
			    map<size_t, const TreeNode *> &map_index_to_base,
			    vector<const TreeNode *> &IVvector)
{
  const TreeNode *lhs = assn->child(0), *rhs, *contributor, *v,
    *nn = isOFAN(lhs) ? lhs->simpName() : lhs->name();
  
  if (IV.find(nn->decl()) == IV.end()) {
    if (DEBUG_OPT)
      cout << "ignore " << pseudocode(assn) << endl;
    return;
  }
  if (DEBUG_OPT)
    cout << "considering poss. IV update " << pseudocode(assn) << endl;
  SourcePosn p = nn->position();
  size_t index = find_or_insert(lhs, IVvector);
  bool isSum, isSumOrDiff;
  isSumOrDiff = isSumOrDifference(rhs = assn->opnd1(), isSum);
  assert(isSumOrDiff);
  if (matchingNode(lhs, rhs->child(0)))
    contributor = rhs->child(1);
  else {
    assert(isSum && matchingNode(lhs, rhs->child(1)));
    contributor = rhs->child(0);
  }
  if ((v = map_index_to_incr[index]) == NULL) {
    TreeNode *vardecl, *stmt;
    map_index_to_base[index] =
      MakeTemporary(CloneTree(lhs, true), vardecl, stmt, NULL);
    if (DEBUG_OPT)
      cout << "  set base: " << pseudocode1(stmt) << endl;
    decls = cons(vardecl, decls);
    stmts = cons(stmt, stmts);
    v = map_index_to_incr[index] =
      MakeTemporary(CloneTree(contributor, true), vardecl, stmt, NULL);
    decls = cons(vardecl, decls);
    stmts = cons(stmt, stmts);
    if (!isSum)
      stmts = cons((TreeNode *)(new ExpressionStmtNode
		   (new AssignNode(CloneTree(v, true),
				   new UnaryMinusNode(CloneTree(v, true), p),
				   p), p)),
		   stmts);
  } else {
    TreeNode *update;
    if (isSum)
      update = new PlusNode(CloneTree(v, true),
			    CloneTree(contributor, true),
			    p);
    else
      update = new MinusNode(CloneTree(v, true),
			     CloneTree(contributor, true),
			     p);
    stmts = cons((TreeNode *)(new ExpressionStmtNode
		 (new AssignNode(CloneTree(v, true), update, p), p)), stmts);
  }
  if (DEBUG_OPT)
    cout << "  contributor: " << (isSum ? '+' : '-') <<
      pseudocode1(contributor) << endl;
}

/* Transform the variables in loop l whose decls appear in IV.  In
   particular, those variables will be incremented by some constant at
   the start of each iteration.  The amount of the increment is
   determined by running through possibleIVupdate.  */
static void performIVtransformation(ForEachStmtNode *l,
				    set<Decl *> &IV,
				    treeSet &possibleIVupdate)
{
  if (DEBUG_OPT) {
    cout << "performIVtransformation(" << l->position().asString() << ", {";
    set<Decl *>::const_iterator i = IV.begin();
    if (i != IV.end()) {
      (*i)->print(cout);
      while (++i != IV.end()) {
	cout << ", ";
	(*i)->print(cout);
      }
    }
    cout << "})\n";
  }
  TreeNode *insertion_point = first_stmt(l->stmt());
  if (IV.empty() || insertion_point == NULL)
    return;
  TreeNode *lp = l->parent();
  l->tentative() = false;
  l->lo() = new PrimitiveLitNode((int32) 0);
  vector<const TreeNode *> IVvector;
  // index here means index in IVvector
  map<size_t, const TreeNode *> map_index_to_incr;
  map<size_t, const TreeNode *> map_index_to_base;
  llist<TreeNode *> *decls = NULL, *stmts = NULL;
  /* Create statements that will precede the loop. */
  for (treeSet::const_iterator i = possibleIVupdate.begin();
       i != possibleIVupdate.end(); ++i) 
    createIVpreloop(l, IV, *i, stmts, decls, map_index_to_incr,
		    map_index_to_base, IVvector);
  stmts = extend(decls, dreverse(stmts));
  if (DEBUG_OPT) {
    cout << "prepend:\n";
    print(stmts, cout, 1);
  }
  SourcePosn lpos = l->position();
  replaceChild(lp, l,
	       new BlockNode(extend(stmts, static_cast<TreeNode *>(l)), NULL, lpos));
  /* Insert statements at top of l's body to set the IV(s) from the
     foreach iteration point. */
  size_t i, s = IVvector.size();
  for (i = 0; i < s; i++) {
    const TreeNode *IV = IVvector[i];
    extern BlockNode *stmt_to_lowered_block(TreeNode *t);
    TreeNode
      *p = new ObjectNode(CloneTree(l->vars()->child(0)->child(0), true)),
      *one = new PrimitiveLitNode((int32) 1),
      *v = new PlusNode(const_cast<TreeNode *>(map_index_to_base[i]),
			new MultNode(CloneTree(map_index_to_incr[i], true),
				     new PointArrayAccessNode(p, one, lpos),
				     lpos),
			lpos),
      *assn = new AssignNode(CloneTree(IV, true), v, lpos),
      *b = stmt_to_lowered_block(new ExpressionStmtNode(assn, lpos));
    if (DEBUG_OPT) {
      Worklist w(b);
      w.filter(exprnode);
      cout << "In IV update:\n";
      while (!w.empty()) {
	TreeNode *t = w.pop(), *tp = t->parent();
	string ty;
	if (t->type() == NULL)
	  ty = "(no type)";
	else 
	  ty = t->type()->typeName();
	cout << "  expr " << pseudocode(t) << ' ' << ty << " | " <<
	  (tp->isStatementNode() ?
	   string("...") :
	   pseudocode(tp)) << " | " <<
	  (tp->parent()->isStatementNode() || tp->isStatementNode() ?
	   string("...") :
	   pseudocode(tp->parent())) << endl;
      }
    }
    AddStmts(insertion_point, cons(b));
  }
}

bool executesOnceOnEveryIter(const TreeNode *e, const TreeNode *l)
{
  bool result = false;
  if (appearsOnEveryIter(e, l)) {
    if (DEBUG_OPT) {
      static set<string> shown;
      string s = pseudocode(l);
      if (shown.find(s) == shown.end()) {
	cout << "Considering loop at " << l->position().asString() <<
	  s << endl;
	shown.insert(s);
      }
    }
    Worklist w;
    w.add_child_trees(l->stmt());
    treeSet *loopStmts = list_to_set(w.asList());
    result = !hasSelfPath(enclosingStmt(e)->getCfgExtent().exit,
			  loopStmts);
    delete loopStmts;
  }
  if (DEBUG_OPT)
    cout << "at " << e->position().asString() <<
      ", executesOnceOnEveryIter(" << pseudocode(e) << "): " << result << endl;
  return result;
}

static void seekInductionVars(ForEachStmtNode *l,
			      set<Decl *> &possibleIV,
			      treeSet &possibleIVupdate)
{
  /* Process vars of type int used as LHS of an assignment in l
     that are declared outside l. */
  set<Decl *> vardeclnodes;
  treeSet todo;
  Worklist w;
  w.add(l->stmt());
  const treeSet *loopExprs = exprs(list_to_set(w.asList()));
  while (!w.empty()) {
    int incrChild;
    TreeNode *t = w.pop(), *parent = t->parent();
    if (isVarDeclNode(t))
      vardeclnodes.insert(t->decl());
    else if (isNameNode(t)) {
      if ((isObjectNode(parent) || isOFAN(parent)) &&
	  isIntType(parent->type()) &&
	  isLHSofAssignNode(parent) &&
	  isConstantIncrAssignNode(parent->parent(), l, &incrChild) &&
	  noDefsFromSet(parent->parent()->child(1)->child(incrChild),
			loopExprs) &&
	  executesOnceOnEveryIter(parent->parent(), l))
	todo.insert(t);
    } else for (int i = t->arity(); --i >= 0; )
         w.add(t->child(i));
  }
  for (treeSet::iterator i = todo.begin(); i != todo.end(); ++i) {
    const TreeNode *t = *i;
    if (vardeclnodes.find(t->decl()) == vardeclnodes.end()) {
      TreeNode *tpp = t->parent()->parent();
      if (DEBUG_OPT)
	cout << "Poss. IV update: " << pseudocode(tpp) << '\n';
      possibleIV.insert(t->decl());
      possibleIVupdate.insert(tpp);
    }
  }
  delete loopExprs;
}

static void rewrite_tentative_foreach(ForEachStmtNode *l)
{
  set<Decl *> possibleIV, IV;
  treeSet possibleIVupdate;
  seekInductionVars(l, possibleIV, possibleIVupdate);
  if (possibleIV.empty())
    return;

  // Process the loop body to see which candidates are only updated by
  // i = i + <loop invariant expression> or equivalent.
  Worklist w(l);
  treeSet *loopContents = list_to_set(w.asList());
  for (treeSet::const_iterator i = loopContents->begin();
       i != loopContents->end(); ++i) {
    const TreeNode *t = *i;
    if (isNameNode(t) &&
	possibleIV.find(t->decl()) != possibleIV.end() &&
	IV.find(t->decl()) == IV.end()) {
      const TreeNode *tp = t->parent();
      llist<TreeNode *> *defs = tp->getDefs();
      if (DEBUG_OPT) {
	cout << "defs of " << pseudocode(tp) <<
	  " (in " << pseudocode1(tp->parent()) << "):\n";
	print(defs, cout, 1);
	cout << '\n';
      }
      // Any var with a def in the loop that isn't of the proper form
      // leads us to give up on that var.  A def that can occur other
      // than exactly once has the same effect.
      while (defs != NULL) {
	TreeNode *d = defs->front();
	if (loopContents->find(d) != loopContents->end() &&
	    possibleIVupdate.find(d) == possibleIVupdate.end()) {
	  if (DEBUG_OPT)
	    cout << "def " << pseudocode(d) << " is not an IVupdate\n";
	  possibleIV.erase(t->decl());
	  goto next;
	}
	if (loopContents->find(d) != loopContents->end() &&
	    !executesOnceOnEveryIter(d, l)) {
	  if (DEBUG_OPT)
	    cout << "def " << pseudocode(d) << " may not execute exactly once per iter\n";
	  possibleIV.erase(t->decl());
	  goto next;
	}
	defs = defs->tail();
      }
      IV.insert(t->decl());
    next: ;
    }
  }
  performIVtransformation(l, IV, possibleIVupdate);
  delete loopContents;
}

static vector<ForEachStmtNode *> tentative_foreaches;

void ForEachStmtNode::loopAnal(TreeNode *enclosingLoop)
{
  compile_status(3, string("loop analysis of foreach at ") + position().asString());
  enclLoop[this] = enclosingLoop;
  initInvar(this);

  for (int i = arity(); i-- > 0; )
    child(i)->loopAnal(this);

  foreachAnal(this);
  if (tentative())
    tentative_foreaches.push_back(this);
}

/////////////////////////////////////////////////////////////////////////////
// utils
/////////////////////////////////////////////////////////////////////////////

llist<TreeNode *> *& ForEachStmtNode::junk_post() { return _junk_post; }
llist<TreeNode *> *& ForEachStmtNode::junk_pre() { return _junk_pre; }

/* Remove all statements in s from t. */
TreeNode *deleteStmts(TreeNode *t, set<StatementNode *> *s)
{
  treeSet ss;
  for (set<StatementNode *>::iterator i = s->begin(); i != s->end(); i++)
    ss.insert(*i);
  return t->deleteStmts(&ss);
}


// deleteStmts() behavior is documented in AST.h

TreeNode *TreeNode::deleteStmts(treeSet *s)
{
  const int childCount = arity();
  for (int sweep = 0; sweep < childCount; ++sweep)
    child(sweep, child(sweep)->deleteStmts(s));

  return this;
}

TreeNode *BlockNode::deleteStmts(treeSet *s)
{
  TreeNode *l = child(0);
  TreeNode *result = this;
  int c = l->arity();
  bool del = false; // whether any top-level stmts in the block must be deleted

#if 0
  cout << endl << "Deleting stmts from block:" << endl;
  pseudoprint(cout, 0);
  cout << endl;
#endif

  for (int i = 0; i < c; ++i)
    if (contains(s, l->child(i)) ||
	isExpressionStmtNode(l->child(i)) &&
	contains(s, l->child(i)->expr()))
      del = true;
    else
      l->child(i, l->child(i)->deleteStmts(s));
  
  // If top-level stmts must be deleted then rebuild the block from scratch.
  if (del) {
    llist<TreeNode *> *q = NULL;
    while (c-- > 0)
      if (!(contains(s, l->child(c)) ||
	    isExpressionStmtNode(l->child(c)) &&
	    contains(s, l->child(c)->expr())))
	q = cons(l->child(c), q);
      else {
        //l->child(c)->free();
      }
    //result = q ? (TreeNode *)new BlockNode(q, NULL, position()) : (TreeNode *)new EmptyStmtNode();
    stmts(new TreeListNode(q, position())); // DOB: prevent regenerating the BlockNode 
    //delete l;
  }

#if 0
  cout << endl << "Result of deleting stmts from block:" << endl;
  result->pseudoprint(cout, 0);
  cout << endl;
#endif

  return result;
}

TreeNode *StatementNode::deleteStmts(treeSet *s)
{
  if (contains(s, this)) {
    //this->free();
    return new EmptyStmtNode();
  }
  else
    return TreeNode::deleteStmts(s);
}

TreeNode *ExpressionStmtNode::deleteStmts(treeSet *s)
{
  if (contains(s, expr())) {
    //this->free();
    return new EmptyStmtNode();
  }
  else
    return StatementNode::deleteStmts(s);
}

/* Delete decls in s from t and return t or a rewritten version of t. */
TreeNode *deleteDeclsFromBlocks(TreeNode *t, treeSet *s)
{
  // This is safe, but it does rely on undocumented behavior of
  // deleteStmts(), above.
  return t->deleteStmts(s);
}

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

static llist<CfgNode *> * current_list;
static void addToList(CfgNode *x, void*)
{
  current_list = cons(x, current_list);
}
#define ADD_TO_LIST() ((current_list ?					\
			(free_all(current_list), current_list = NULL) :	\
			NULL),						\
		       addToList)

bool isFullDomainLoop(TreeNode *t)
{
  assert(isForEachStmtNode(t));
  llist<CfgNode *> *l;
  TraverseCfgScope(t, ADD_TO_LIST(), NULL);
  l = dreverse(current_list);
  const CFGset *ls = list_to_CFGset(l);
  bool ignored = false;
  foreach (n, llist<CfgNode *>, *l) {
    (*n)->predIter(true, ls, &ignored);
    if (ignored) {
      cout << "isFullDomainLoop(): false at " << t->position().asString() <<
	endl;
      return false;
    }
  }
  return true;
}

#undef ADD_TO_LIST

/* Destructively replace all occurences of x in t with y. */
TreeNode *replaceNode(TreeNode *t, TreeNode *x, TreeNode *y)
{
  if (t == x)
    return y;
  else {
    int a = t->arity();
    for (int i = 0; i < a; i++)
      t->child(i, replaceNode(t->child(i), x, y));
    return t;
  }
}

/* Destructively replace any one occurence of x in t with y.  Returns t.
   Does fatal_error("") if x does not occur. */
TreeNode *replaceOneNode(TreeNode *t, TreeNode *x, TreeNode *y)
{
  if (t == x)
    return y;
  else {
    llist<TreeNode *> *todo = cons(t);
    while (todo != NULL) {
      TreeNode *c = todo->front();
      todo = todo->free();
      int a = c->arity();
      for (int i = 0; i < a; i++)
	if (c->child(i) == x) {
	  c->child(i, y);
	  free_all(todo);
	  return t;
	} else
	  push(todo, c->child(i));
    }
    fatal_error("");
    return t;
  }
}

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

treeSet *allDefs(treeSet *vars)
{
  treeSet *result = new treeSet();
  for (treeSet::iterator i = vars->begin(); i != vars->end(); ++i) {
    treeSet *s = list_to_set(((TreeNode *) (*i))->getDefs());
    destructively_union(result, s);
    delete s;
  }
  return result;
}

treeSet *allUses(const TreeNode *t)
{
  return list_to_set(t->getUses());
}

static inline bool opnd0_of_assignnode(TreeNode *t)
{
  TreeNode *p = t->parent();
  return (isAssignNode(p) && p->opnd0() == t);
}

static bool lval_context(TreeNode *t)
{
  while (isIIFAN(t->parent()))
    t = t->parent();
  return opnd0_of_assignnode(t);
}

// Return a set of uses that contains all Lvalue uses.
// Callee should delete the result.
treeSet *LvalueUses(const TreeNode *t)
{
  llist< TreeNode * > * const uses = t->getUses();
  treeSet *result = new treeSet;

  remove_copy_if( uses->begin(), uses->end(),
		  inserter( *result, result->begin() ),
		  not1( ptr_fun( lval_context ) ) );
  return result;
}

// Return a set of uses that contains all Rvalue uses.
// Callee should delete the result.
treeSet *RvalueUses(const TreeNode *t)
{
  llist< TreeNode * > * const uses = t->getUses();
  treeSet *result = new treeSet;

  remove_copy_if( uses->begin(), uses->end(),
		  inserter( *result, result->begin() ),
		  lval_context );
  return result;
}

treeSet *ObjectNodes(TreeNode *e)
{
  Worklist w(e);
  return list_to_set(w.filter(objectnode)->asList());
}

treeSet *AssignableNodes(TreeNode *e)
{
  Worklist w(e);
  return list_to_set(w.filter(assignablenode)->asList());
}


/////////////////////////////////////////////////////////////////////////////
// treeSet / CFGset utils
/////////////////////////////////////////////////////////////////////////////

/* True iff s is a set containing just e. */
bool isSingletonContaining(TreeNode *e, treeSet *s)
{
  return s->size() == 1 && *(s->begin()) == e;
}

treeSet *exprset_to_stmtset(treeSet *t)
{
  treeSet * result = new treeSet;
  for (treeSet::iterator i = t->begin(); i != t->end(); ++i)
    result = adjoin(result, enclosingStmt(*i));
  return result;
}

treeSet *convert_cfguset_to_treeset(const CFGuset *s)
{
  treeSet *result = new treeSet;
  for (CFGuset::const_iterator i = s->begin(); i != s->end(); ++i)
    adjoin(result, (*i)->astNode());
  return result;
}

map_tree_to_treeSet *
destructive_convert_cfgmap_to_astmap(map_CFGnode_to_CFGuset *r)
{
  map_tree_to_treeSet *result = new map_tree_to_treeSet;
  for (map_CFGnode_to_CFGuset::iterator i = r->begin(); i != r->end(); ++i)
    (*result)[(*i).first->astNode()] =
      convert_cfguset_to_treeset((*i).second);
  delete r;
  return result;
}

treeSet *destructive_convert_cfgset_to_treeset(CFGset *s)
{
  treeSet *result = new treeSet;
  for (CFGset::iterator i = s->begin(); i != s->end(); ++i)
    adjoin(result, (*i)->astNode());
  delete s;
  return result;
}

map_tree_to_treeSet *
destructive_convert_cfgmap_to_astmap(map_CFGnode_to_CFGset *r)
{
  map_tree_to_treeSet *result = new map_tree_to_treeSet;
  for (map_CFGnode_to_CFGset::iterator i = r->begin(); i != r->end(); ++i)
    (*result)[(*i).first->astNode()] =
      destructive_convert_cfgset_to_treeset((*i).second);
  delete r;
  return result;
}

// Add t to s if it isn't already there.
treeSet *treeSetAdjoin(treeSet *s, const TreeNode *t)
{
  return adjoin(s, t);
}

// Add t to s if it isn't already there.
treeSet *adjoin(treeSet *s, const TreeNode *t)
{
  s->insert(t);
  return s;
}

// Add t to s if it isn't already there.
CFGset *adjoin(CFGset *s, const CfgNode *t)
{
  s->insert((CfgNode *) t);
  return s;
}

bool contains(const CFGset *s, const CfgNode *t)
{
  return s->find((CfgNode *) t) != s->end();
}


bool contains_any_child(const treeSet *s, const TreeNode *t)
{
  for (int i = t->arity(); --i >= 0; )
    if (contains(s, t->child(i)))
      return true;
  return false;
}

bool contains_any_grandchild(const treeSet *s, const TreeNode *t)
{
  for (int i = t->arity(); --i >= 0; )
    if (contains_any_child(s, t->child(i)))
      return true;
  return false;
}

bool contains_any_greatgrandchild(const treeSet *s, const TreeNode *t)
{
  for (int i = t->arity(); --i >= 0; )
    if (contains_any_grandchild(s, t->child(i)))
      return true;
  return false;
}

bool contains(const treeSet *s, const TreeNode *t)
{
  return treeSetContains(s, t);
}

bool contains(const treeSet &s, const TreeNode *t)
{
  return treeSetContains(s, t);
}

bool treeSetContains(const treeSet *s, const TreeNode *t)
{
  return s != NULL && treeSetContains(*s, t);
}

bool treeSetContains(const treeSet &s, const TreeNode *t)
{
  return s.find(t) != s.end();
}

treeSet *copy(treeSet *s)
{
  return new treeSet(*s);
}

// Change s to s intersect t.
treeSet *destructively_intersect(treeSet *s, treeSet *t)
{
  treeSet::iterator i = s->begin();
  treeSet::iterator j = t->begin();
  while (true) {
    while (i != s->end() && (j == t->end() || *i < *j))
      s->erase(i++);
    if (i == s->end()) break;
    if (*i == *j)
      ++i;
    ++j;
  }
  return s;
}

// Change s to s intersect t.
CFGset *destructively_intersect(CFGset *s, CFGset *t)
{
  CFGset::iterator i = s->begin();
  CFGset::iterator j = t->begin();
  while (true) {
    while (i != s->end() && (j == t->end() || *i < *j))
      s->erase(i++);
    if (i == s->end()) break;
    if (*i == *j)
      ++i;
    ++j;
  }
  return s;
}

// Change s to s union t.
treeSet *destructively_union(treeSet *s, treeSet *t)
{
  s->insert( t->begin(), t->end() );
  return s;
}

treeSet *filter(bool f(const TreeNode *t), const treeSet *s)
{
  treeSet *result = new treeSet;
  remove_copy_if( s->begin(), s->end(),
		  inserter( *result, result->begin() ),
		  not1( ptr_fun( f ) ) );
  return result;
}

treeSet *destructively_filter(bool f(const TreeNode *t), treeSet *s)
{
  for (treeSet::iterator i = s->begin(); i != s->end(); ) {
    if (f(*i)) ++i;
    else s->erase(i++);
  }
  return s;
}

void print(llist<TreeNode *> *s, ostream &os, int m)
{
  if (s == NULL) {
    os << "empty" << endl;
  } else for ( ; s != NULL; s = s->tail()) {
    indent(os, m);
    os << PLCODE2(os, s->front()) << endl;
  }
}

void printTreeSet(const treeSet *s, ostream &os, int m)
{
  if (s == NULL) {
    os << "NULL" << endl;
  } else if (s->empty()) {
    os << "empty" << endl;
  } else
    for (treeSet::const_iterator i = s->begin(); i != s->end(); ++i) {
      indent(os, m);
      os << PLCODE2(os, *i) << endl;
    }
}

void printTreeSetWithParents(const treeSet *s, ostream &os, int m)
{
  if (s == NULL) {
    os << "NULL" << endl;
  } else if (s->empty()) {
    os << "empty" << endl;
  } else
    for (treeSet::const_iterator i = s->begin(); i != s->end(); ++i) {
      indent(os, m);
      os << PLCODE2(os, *i);
      os << endl;
      indent(os, m + 1);
      os << "Par: ";
      os << PLCODE2(os, (*i)->parent());
      os << endl;
    }
}

/* Whether t appears at the top level of b. */
bool block_contains(TreeNode *t, BlockNode *b)
{
  foriter (p, b->stmts()->allChildren(), TreeNode::ChildIter)
    if (t == *p)
      return true;
  return false;
}

/* If t appears at the top level of b then return a new block that contains
   everything but t.  Otherwise return t. */
BlockNode *remove_node_from_block(TreeNode *t, BlockNode *b)
{
  bool hit = false;
  llist<TreeNode *> *l = NULL;
  foriter (p, b->stmts()->allChildren(), TreeNode::ChildIter)
    if (t == *p)
      hit = true;
    else
      push(l, *p);

  if (hit)
    return new BlockNode(dreverse(l), NULL, b->position());
  else {
    free_all(l);
    return b;
  }
}

// Is s a subset of t?
bool isSubset(const treeSet &s, const treeSet &t)
{
  return includes( t.begin(), t.end(), s.begin(), s.end() );
}

// Is s a subset of t?
bool isSubset(const treeSet *s, const treeSet *t)
{
  return isSubset(*s, *t);
}

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

/* Move all VarDeclNodes in the block to the front, and make their
   initializers absent by creating separate assignment statements as needed. */
BlockNode *SortVarDeclsInBlock(BlockNode *b)
{
  TreeListNode *s = b->stmts();
  llist<TreeNode *> *decls = NULL, *newStmts = NULL;
  int c = s->arity();
  for (int i = c; i-- > 0; ) {
    TreeNode *t = s->child(i);
    if (isVarDeclNode(t)) {
      VarDeclNode *d = (VarDeclNode *) t;

      if (!d->initExpr()->absent()) {

	TreeNode *init = d->initExpr();
	d->initExpr(TreeNode::omitted);

	TreeNode *varNode = new ObjectNode (d->simpName()->clone());
	TreeNode *assn = new ExpressionStmtNode(new AssignNode(varNode, init));
	newStmts = cons(assn, newStmts);
      }
      decls = cons(t, decls);
    } else {
      newStmts = cons(t, newStmts);
    }
  }
  newStmts = extend(decls, newStmts);
  b->stmts(new TreeListNode(newStmts));
  return b;
}

SwitchBranchNode *SortVarDeclsInSwitch(SwitchBranchNode *b)
{
  TreeListNode *s = b->stmts();
  llist<TreeNode *> *decls = NULL, *newStmts = NULL;
  int c = s->arity();
  for (int i = c; i-- > 0; ) {
    TreeNode *t = s->child(i);
    if (isVarDeclNode(t)) {
      VarDeclNode *d = (VarDeclNode *) t;

      if (!d->initExpr()->absent()) {

	TreeNode *init = d->initExpr();
	d->initExpr(TreeNode::omitted);

	TreeNode *varNode = new ObjectNode (d->simpName()->clone());
	TreeNode *assn = new ExpressionStmtNode(new AssignNode(varNode, init));
	newStmts = cons(assn, newStmts);
      }
      decls = cons(t, decls);
    } else {
      newStmts = cons(t, newStmts);
    }
  }
  newStmts = extend(decls, newStmts);
  b->stmts(new TreeListNode(newStmts));
  return b;
}

/* def appears on the list returned by use->getDefs().  Return a node
   that has the same run-time value as use, if possible.  Otherwise
   return NULL. */
TreeNode *valueTransferred(TreeNode *def, TreeNode *use)
{
  TreeNode *r = NULL;

  if (isAssignNode(def))
    r = def->opnd0();
  else if (isForEachPairNode(def))
    r = def->simpName();

  if (DEBUG_OPT) {
    cout << "Value transferred from ";
    def->pseudoprint(cout, 0);
    cout << " to ";
    use->pseudoprint(cout, 0);
    cout << ": ";
    if (r == NULL)
      cout << "?";
    else
      r->pseudoprint(cout, 0);
    cout << endl;
  }

  return r;
}

llist<TreeNode *> *add_descendants_to_list(llist<TreeNode *> *l,
					   const TreeNode *t)
{
  l = cons(const_cast<TreeNode *>(t), l);
  for (int i = t->arity(); i-- > 0; )
    l = add_descendants_to_list(l, t->child(i));
  return l;
}

/* Does s contain any elt of l? */
bool set_contains_any(const treeSet *s, const llist<TreeNode *> *l)
{
  return find_first_of( s->begin(), s->end(),
			l->begin(), l->end() ) != s->end();
}

/* True iff no DEF of t appears in the set s. */
bool noDefsFromSet(const TreeNode *t, const treeSet *s)
{
  bool result = !set_contains_any(s, t->getDefs());
  if (DEBUG_OPT) {
    cout << "noDefsFromSet(" << pseudocode(t) << "): " << result <<
      " with defs:\n";
    for (llist<TreeNode *> *l = t->getDefs(); l != NULL; l = l->tail())
      cout << "  " << pseudocode1(l->front()) << '\n';
    cout << " and set:\n";
    for (llist<TreeNode *> *l = set_to_list(s); l != NULL; l = l->tail())
      cout << "  " << pseudocode1(l->front()) << '\n';
  }
  return result;
}


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

static treeSet * validCFG = NULL;

// If method does not have a valid CFG then do some analysis now.
// Analyses invoked: basic blocks, use/def, foreach dominators (if dominators
// is true), and deps (if computeDeps is true).
static void staticAnal(TreeNode *method, bool dominators, bool ignoreNSE,
		       bool computeDeps)
{
  garbageListClear();
  if (validCFG == NULL)
    validCFG = new treeSet;
  else if (treeSetContains(validCFG, method))
    return;
  validCFG->insert(method);

  if (DEBUG_OPT)
    cout << "Setting up bblocks" << endl;
  setupBblocksMethod(method);
  if (DEBUG_OPT)
    cout << "Setting up usedef" << endl;
  setupUdMethod(method, computeDeps);
  if (dominators) {
    computeMethodDominators (method->body (), ignoreNSE);
    method->body()->computeForeachDominators(ignoreNSE, 0);
  }
  /*
  if (computeDeps)
    computeArrayAccessSummary(method);
  */
}

void invalidateCFG()
{
  delete validCFG;
  validCFG = NULL;
  CfgNode::reset ();
}

void redoDefUse(TreeNode *t)
{
  staticAnal(enclosingMethod(t), false);
}

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

static void removeLazyOptNode(TreeNode *par, TreeNode *t)
{
  replaceChild(par, t, t->body());
}

static inline void renameLoops(TreeNode *t)
{
  extern bool opt_stoptifu;
  if (opt_stoptifu) {
    /* If doing loop fusion, we need to make iteration variable names unique
       to avoid name collisions. */
    extern void loop_var_rename(TreeNode *t);
    loop_var_rename(t);
  }
}

void LazyOptimizeNode::codeGen(CodeContext &context)
{
  TreeNode *t;
  removeLazyOptNode(parent(), this);
  renameLoops(body());
  staticAnal(enclosingMethod(this), true);
  parent()->body(t = optimize(body()));
  if (DEBUG_OPT) {
    cout << "codeGen():\n\n";
    t->pseudoprint(cout, 0);
    cout << "\n\n";
  }
  t->checkIF(true);
  t->codeGen(context);
}

/* Currently unused, though it could be made to work fairly easily. */
const string LazyOptimizeNode::emitExpression(CodeContext &context)
{
  fatal_error("");

  TreeNode *t;
  removeLazyOptNode(parent(), this);
  renameLoops(body());
  staticAnal(enclosingMethod(this), true);
  parent()->body(t = optimize(body()));
  if (DEBUG_OPT) {
    cout << "emitExpression():\n\n";
    t->pseudoprint(cout, 0);
    cout << "\n\n";
  }
  t->checkIF(true);
  return t->emitExpression(context);
}

/////////////////////////////////////////////////////////////////////////////
// Mark parts of the tree to be optimized later.  Optimizations that require
// interprocedural information are done separately.  The LazyOptimizeNodes
// trigger opts during the codegen pass; they are also removed at that time.
/////////////////////////////////////////////////////////////////////////////

void lazyOptimize()
{
  foreach (f, llist<CompileUnitNode *>, *allFiles)
    (*f)->lazyOptimize();
}

static TreeNode *lazyOptNode(TreeNode *s)
{
  if (s == NULL || s->absent())
    return s;
  else
    return new LazyOptimizeNode(s, s->position());
}

TreeNode *TreeNode::lazyOptimize()
{
  for (int i = arity(); i-- > 0; )
    child(i, child(i)->lazyOptimize());
  return this;
}

TreeNode *MethodDeclNode::lazyOptimize()
{
  body(lazyOptNode(body()));
  return this;
}

TreeNode *ConstructorDeclNode::lazyOptimize()
{
  body(lazyOptNode(body()));
  // DOB: optimization has been disabled for constructorCall, because performing UAE there
  // currently causes live expressions to get thrown away
  // I think it's because the method def-use analysis does not include 
  // analysis of uses in constructorCall, therefore it misses those uses and axes the defs
  // there generally isn't much optimization opportunity here anyhow, so it's probably not worth fixing
  //constructorCall(lazyOptNode(constructorCall()));
  return this;
}

TreeNode *VarDeclNode::lazyOptimize()
{
  initExpr(lazyOptNode(initExpr()));
  return this;
}

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

// helper for summarize_statements_and_expressions(), below
static treeSet *summ_exprs(const TreeNode *t)
{
  return exprs(isIfStmtNode(t) ?
	       t->condition() :
	       (isForEachStmtNode(t) ? t->vars() : t));
}

// helper for summarize_statements_and_expressions(), below
static void summ_pseudoprint(const TreeNode *t, ostream &os, unsigned depth)
{
  if (isIfStmtNode(t)) {
    os << endl;
    indent(os, depth);
    os << "if (";
    t->condition()->pseudoprint(os, depth);
    os << ") ...";
  } else if (isForEachStmtNode(t)) {
    extern void ForEachStmtNode_pseudoprint_no_body(const ForEachStmtNode *f,
						    ostream& os,
						    unsigned depth);
    ForEachStmtNode_pseudoprint_no_body(static_cast<const ForEachStmtNode *>(t),
					os, depth);
    os << " ...";
  } else
    t->pseudoprint(os, depth);
}

/* Show info about statements, expressions, decls, etc. in t.
   Intended for debugging purposes. */
void summarize_statements_and_expressions(const TreeNode *t)
{
  treeSet *decls = vardecls(t);
  cout << "Summary of local variable decls:\n";
  for (treeSet::const_iterator i = decls->begin(); i != decls->end(); ++i) {
    const TreeNode *x = *i;
    cout << ' ' << pseudocode1(x) << "\n   decl " <<
      long2hexstring((long) x->decl()) << endl;
  }

  treeSet *s = statements(t);
  cout << "\nSummary of statements and expressions:\n";
  for (treeSet::const_iterator i = s->begin(); i != s->end(); ++i) {
    const TreeNode *x = *i;
    if (!isIfStmtNode(x) && !isForEachStmtNode(x) &&
	(contains_any_child(s, x) || contains_any_grandchild(s, x)))
      continue;
    treeSet *expressions = summ_exprs(x);
    cout << "\n At line " + x->position().asString() << ":";
    summ_pseudoprint(x, cout, 1);
    if (!expressions->empty()) {
      cout << "\n expressions:\n";
      for (treeSet::const_iterator j = expressions->begin();
	   j != expressions->end(); ++j) {
	const TreeNode *e = *j;
	if (isObjectNode(e) && isNameNode(e->child(0))) {
	  const Decl *decl = e->child(0)->decl();
	  const TreeNode *declsource =
	    decl->hasSource() ? decl->source() : NULL;
	  cout << "  " <<
	    (contains(decls, declsource) ? "local " : "") <<
	    pseudocode(e) << " with decl " <<
	    (decl == NULL ? "null" :
	     (long2hexstring((long) decl) + " " +
	      decl->type()->typeName() +
	      (declsource != NULL ?
	       " at " + declsource->position().asString() :
	       "")));
	} else
	  cout << "  " << pseudocode(e);
	cout << endl;
      }
    }
    delete expressions;
    cout << endl;
  }
  delete s;
  delete decls;
}

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

/* Useless assignment elimination. */
static inline TreeNode *UAE(TreeNode *t)
{
  if (DEBUG_UAE) {
    cout << endl << "Before UAE:" << endl;
    t->pseudoprint(cout, 0);
    cout << endl << endl;
    summarize_statements_and_expressions(t);
  }
  redoDefUse(t);
  treeSet *useless = t->uselessAssignments();
  TreeNode *result = t->deleteStmts(useless);
  if (DEBUG_UAE) {
    cout << endl << "After UAE:" << endl;
    result->pseudoprint(cout, 0);
    cout << endl;
  }
  delete useless;
  return result;
}

/* Copy propagation / constant folding / common subexpression elim */
static TreeNode *CPCFCSE(TreeNode *t, const char *s = NULL)
{
  int numcopychanges, numcsechanges, totalchanges = 0;
  int iters=0;
  static int firsttime = 1;
  if (firsttime && opt_foldextra) {
   /* initial global constant folding to get the more aggressive foldings
      that are not required by Java and hence not performed during 
      static analysis - also enables this aggressive mode for the folding below */
    foldConstants(true); 
    firsttime = 0;
  }
  do {
    iters++;
    if (opt_subexpr) {
      if (DEBUG_SUBEXPR)                 
        cout << "Common subexpression elimination, pass #" << iters << endl;
      invalidateCFG();
      t->fixParent();
      redoDefUse(t);
      numcsechanges = doCommonSubexprElim(t);
      if (DEBUG_SUBEXPR)                 
        cout << "Made " << numcsechanges << " replacements." << endl;
    } else numcsechanges = 0;

    if (opt_copy) {
      if (DEBUG_COPY)                 
        cout << "Copy propagation, pass #" << iters << endl;
      invalidateCFG();
      t->fixParent();
      redoDefUse(t);
      numcopychanges = doCopyPropagation(t);
      if (DEBUG_COPY)
        cout << "Made " << numcopychanges << " replacements." << endl;
    } else numcopychanges = 0;

    totalchanges += numcsechanges + numcopychanges;
    t->foldConstants();
  } while(numcsechanges || numcopychanges);

  if (DEBUG_COPY || DEBUG_SUBEXPR) {
    if (s != NULL)
      cout << "\nCPCFCSE pass " << s << " did " <<
	(totalchanges > 0 ? "" : "not ") << "make changes\n";
    if (totalchanges > 0) {
      cout << "\nAfter copy propagation / constant folding / common subexpr elim:\n\n";
      t->pseudoprint(cout, 0);
      cout << "\n\n";
    }
  }

  t->checkIF(true);
  return t;
}

static TreeNode * foreachOpt_and_CPCF(TreeNode *t)
{
  if (DEBUG_OPT) {
    cout << endl;
    cout << "foreachOpt:";
    PLCODE(t);
    cout << endl;
  }

  FP(t);
  if (opt_lift || opt_sr || opt_osr) {
    t->loopAnal((TreeNode *) 0);

    /* this next line still converts foreach to foreach+ even if !opt_lift */
    t = t->liftInvariantExprs();
    FP(t);
    checkAndFixAliasing(t, "after lifting");

    if (opt_copy || opt_subexpr || opt_foldextra)
      t = CPCFCSE(t, "after lifting");

    FP(t);
    checkAndFixAliasing(t, "after CPCFCSE");

    if (!tentative_foreaches.empty()) {
      invalidateCFG();
      staticAnal(enclosingMethod(t), true, true);
      for (vector<ForEachStmtNode *>::const_iterator i =
	     tentative_foreaches.begin(); i != tentative_foreaches.end(); ++i){
	compile_status(3,string("rewrite tentative foreach at ") +
	    (*i)->position().asString());
	rewrite_tentative_foreach(*i);
      }
      FP(t);
      checkAndFixAliasing(t, "after rewrite_tentative_foreach");
      if (DEBUG_OPT) {
	cout << "\nSummary of CFG after rewrite_tentative_foreach\n\n";
	summarizeCFG(enclosingMethod(t), cout);
	cout << "\nEnd summary of CFG after rewrite_tentative_foreach\n\n";
      }
      if (!opt_sr) {
	invalidateCFG();
	staticAnal(enclosingMethod(t), true, true);
      }
    }
    
    if (opt_sr) {
      invalidateCFG();
      staticAnal(enclosingMethod(t), true, true);
      /* Loops once but no longer marked as tentative have been
	 modified and must be reanalyzed. */
      for (vector<ForEachStmtNode *>::const_iterator i =
	     tentative_foreaches.begin(); i != tentative_foreaches.end(); ++i) 
	if (!(*i)->tentative())
	  foreachAnal(*i);
      SRsetup();
      t = t->strengthReduce();
      FP(t);
      checkAndFixAliasing(t, "after SR");
    }
  } else if (opt_copy || opt_subexpr || opt_foldextra)
    t = CPCFCSE(t);
  FP(t);

  tentative_foreaches.clear();

  if (DEBUG_OPT) {
    cout << endl;
    cout << "After loop opts and CPCFCSE:";
    PLCODE(t);
    cout << endl;
  }
  checkAndFixAliasing(t, "before stoptifu");
  if (opt_stoptifu) {
    extern TreeNode * stoptifu(TreeNode *t);
    invalidateCFG();
    staticAnal(enclosingMethod(t), true, false, true);
    t = stoptifu(t);
    FP(t);
  }
  checkAndFixAliasing(t, "after stoptifu");
  return t;
}

TreeNode *TreeNode::applyReordering()
{
  const int childCount = arity();
  for (int sweep = 0; sweep < childCount; ++sweep)
    child(sweep, child( sweep )->applyReordering());
  
  return this;
}

TreeNode *UpdatePointBeforeStmtNode::applyReordering()
{
  if (stmt()->absent())
    stmt(deepCloneWithCrossTreeFixup(WRTloop()->stmt(), false));
  return TreeNode::applyReordering();
}

TreeNode *ReorderNode::applyReordering()
{
  TreeNode *t = stmt();
  t = ::deleteStmts(t, stmtsToDelete());
  t = deleteDeclsFromBlocks(t, declsToDelete());
  {
    map_tree_to_tree &m = *(remap());
    for (map_tree_to_tree::iterator i = m.begin(); i != m.end(); i++)
      t = replaceOneNode(t, i->first, i->second);
  }
  // t = t->collapseTrivialBlocks();
  t->fixParent();
  delete this;
  return t->applyReordering();
}

/*
   Given a piece of code to be optimized, optimize() returns an
   optimized version of that code.  The input may be destructively
   modified in the process.  (Which optimizations to perform is controlled
   by command line flags.)
*/
static TreeNode *optimize(TreeNode *t)
{
  debug_lift = DEBUG_LIFT;
  debug_sr = DEBUG_SR;

  if (DEBUG_OPT) {
    cout << "Optimizing:\n\n";
    t->pseudoprint(cout, 0);
    cout << "\n\n";
  }

  t = foreachOpt_and_CPCF(t);

  /* currently unnecessary
  if (opt_copy || opt_subexpr)
    t = CPCFCSE(t, "before UAE");
  */

  if (opt_uae) {
    invalidateCFG();
    t->fixParent();
    t = UAE(t);
  }

  if (opt_unreachable) {
    t->fixParent();
    setupBblocksMethod(enclosingMethod(t));    
    removeUnreachableStmts(t);
  }

  if (opt_deadvar) {
    t->fixParent();
    t = doDeadVariableRemoval(t);
  }

  invalidateCFG();
  t->fixParent();
  t = t->applyReordering();
  t = t->collapseTrivialBlocks();

  if (DEBUG_OPT) {
    cout << "Result of optimization:\n\n";
    t->pseudoprint(cout, 0);
    cout << "\n\n";
  }

  checkAndFixAliasing(t, "after optimization");
  return t;
}