#include "AST.h"
#include "UniqueId.h"
#include "clone.h"
#include "code.h"
#include "code-util.h"
#include "compiler.h"
#include "decls.h"
#include "delimit.h"
#include "optimize.h"
#include "lower.h"
#include "st-field.h"
#include "streq.h"
#include "utils.h"
#include "ctBox.h"
#include "CtType.h"
#include "CtReference.h"

extern TreeNode *fixSubtreeSharing(TreeNode *t);
extern bool fixAliasing;
extern bool isIFPointOrDomainConstructor(const TreeNode *t);

/*

The intermediate form (IF) we are constructing has a simplified form
compared to what the frontend creates and manipulates.

INPUT: a correct AST.  A correct AST has parent pointers set correctly
	and has types on all expressions, among other things.

OUTPUT: IF, a correct AST that conforms to the rules below, and passes
        checkIF() (see checkIF.cc).

AST nodes may appear only once in a tree, except for TypeNodes.  (See
checkAliasing(), below.)  Sharing makes it impossible to set the
_parent pointer correctly and may confuse analyses that annotate
the nodes.

All expressions must be "baby expressions" of the following forms:
(this should be expressed in terms of AST nodes rather than
pseudo code)

1.  var
2a. var.field
2b. var.i0.i1....ik.field	 (where i0, ..., ik are immutable)
3a. op var			 (UnaryArithNode, NotNode, ComplementNode)
3b. var op var			 (BinaryArithNode, ShiftNode,
				  EqualityNode, RelationNode,
				  BitwiseNode, but not LogCondNode)
3c. var.method(var, var, ...)	 (method call)
3d. foo.method(var, var, ...)	 (static method call (foo = var or ObjectNode))
3e. new type	                 (AllocateSpaceNode)
3f. new type(var, ...)[var]...   (AllocateArrayNode)
4.  var[var]			 (array access)
5.  (type) var			 (CastNode)
6.  var instanceof type		 (InstanceOfNode)
7.  ibroadcast var from var	 (see note below)
8.  [var, ..., var]              (PointNode)
9.  [var : var, var : var, ...], and variants  (DomainNode)
10. var doesn't overlap with var (HasNoOverlapNode)

In the above, var means a local variable, compiler generated temporary,
or constant (PrimitiveLitNode, NullPntrNode, or CodeLiteralExprNode).
In practice, it will often be a temporary variable that is written once
and read once, but not always.  In "baby expressions" that contain
multiple "vars," the "vars" may be evaluated in any order.  Rewriting
to enforce ordering constraints specified by the source language must
take place before/during the conversion to IF.

In Titanium, "broadcast foo from bar" has special evaluations rules.
In the IF, evaluation (on all procs) of the sending proc and
evaluation (on the sending proc) of the value to be sent must precede
the ibroadcast node.  We could have used the same AST node type
(broadcast), but by having two different node types there should be
less confusion.  The type of ibroadcast is (T, int) -> T, where T is
any type, so we can't rewrite it as a normal method call.

An assignment must be an AssignNode of the following form:

e1 = e2		(where e1 is assignable from e2 and both are baby expressions)

All control flow must be expressed using method calls or the following
node types:

BlockNode
IfStmtNode
ForEachStmtNode (with ForEachPairNode)
SwitchNode (with CaseNode and SwitchBranchNode)
LabeledStmtNode
GotoNode
ReturnNode
MonitorFetchNode, MonitorUseNode, and subclasses of those
TryStmtNode, TryNode, CatchNode, FinallyNode, ThrowNode
StaticInitNode
EmptyStmtNode
ExpressionStmtNode
CheckNullNode

Any ExprNodes which are direct children of these statement nodes must be vars 
This includes: 
 ReturnNode arg (if any)
 IfStmtNode conditional
 ThrowNode arg
 SwitchNode arg

Further rules:

VarDeclNodes must have no initExpr.
ReturnNodes must have no cleanups.
Method calls to non-void methods must assign the return value into a var (for inlining purposes).
The top-level contents of BlockNodes must consist of VarDeclNodes and StatementNodes.
All instance initializations are moved into the constructors, and all
static initializations into a single static initializer (which, though
technically illegal for interfaces, shouldn't be a problem for the
backend). NOTE: Field initializers still remain for use by later
optimizations and may violate the IF rules above. However, analyses
that rely on the IF may safely ignore them, since they aren't
codegened.
*/


// DEBUG_LOWERING is mainly used for things "of current interest"---not much.
#define DEBUG_LOWERING 0
#define DEBUG_ADD_STMTS 0
#define DEBUG_GOTO 0
#define DEBUG_LOWER_FOR_TO_WHILE 0
#define DEBUG_CONVERT_FOR_TO_FOREACH 0
#define DEBUG_IFEXPRNODE 0
#define DEBUG_LABELEDSTMT 0
#define DEBUG_LOWER_STMT_TO_BLOCK 0
#define DEBUG_LOWERING_OPTS 0
#define DEBUG_OPASSIGN 0
#define DEBUG_CONSTRUCTOR_CALLS 0

#define SHOWTREE(s, t) \
    do { cout << s << '\n'; (t)->print(cout, 0); cout << '\n'; } while (0)

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

#define GOTO(n) (new GotoNode(n))
#define LABELED(n, pos) (new LabeledStmtNode(TreeNode::omitted, (n), (pos)))
#define NAKEDLABEL() LABELED(TreeNode::omitted, NoSourcePosition)

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

Common::Modifiers currentThisFlags = Common::None;

Common::Modifiers relevantThisFlags( const TreeNode &function )
{
  const Decl &decl = *function.decl();
  return (Common::Modifiers) ((decl.type()->isImmutable() ? Common::None : Common::Local)
			      | (decl.modifiers() & (Common::NonsharedQ | Common::PolysharedQ)));
}

/* Return true if t is a local variable, parameter, constant, or a ThisNode. */
/* Print an error message if return value is false and p is true. */
bool verifyIsVar(const TreeNode *t, bool p)
{
  if (isLocalVar(t) || isFormalParam(t) || isConstant(t) || isNullPntrNode(t) || isThisNode(t) ||
      isCodeLiteralExprNode(t) || isCodeLiteralFAN(t))
    return true;

  if (p) {
    t->error() << "Internal error: expecting local variable or method parameter" << endl;
    t->print(cout, 2);
    cout << endl;
  }
  return false;
}

/* Return true iff t is a local variable, parameter, constant, or a ThisNode. */
bool isVar(const TreeNode *t)
{
  return verifyIsVar(t, false);
}

// Walks over the tree to make sure there aren't any aliased nodes except
// for type nodes and TreeNode::omitted. The use/def edges are attached
// directly to ObjectNodes and thus aliasing is Uncool.
// Returns true if there is aliasing.
bool checkAliasing(TreeNode *n) {
  bool aliasFound = false;
  int childCount = n->arity();
  for (int sweep = 0; sweep < childCount; sweep++) {
    TreeNode *child = n->child(sweep);
    if (child != TreeNode::omitted && 
	!::strstr(child->oper_name(), "Type")) {
      if (n->child(sweep)->parent() != n) {
	cout << "Aliasing error! Child is:\n";
	n->child(sweep)->print(cout,0);
	cout << "\nParent in downward direction is: " << endl;
	n->print(cout,0);
	cout << "\nParent in upward direction is:\n";
	n->child(sweep)->parent()->print(cout,0);
	cout << endl;
	aliasFound = true;
      }
      aliasFound |= checkAliasing(n->child(sweep));
    }
  }
  return aliasFound;
}

void checkAndFixAliasing(TreeNode *n, const char *s)
{
  if (checkAliasing(n)) {
    if (s == NULL)
      cout << "Internal error: Aliasing problem" << endl;
    else
      cout << "Internal error: Aliasing problem (" << s << ")" << endl;
    cout << "Please file a bug report!";
    if (fixAliasing)
      fixSubtreeSharing(n);
    else {
      cout << "  Also, try the -fixsharing flag to tc." << endl;
      exit(11);
    }
    cout << endl;
  }
}

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

static UniqueId tempGenerator( "x" );

void resetIFtemp()
{
  tempGenerator.reset();
}

ObjectNode *MakeTemporary(TreeNode *expr, TreeNode *&declStmt,
			  TreeNode *&assnStmt, const string *tempname)
{
  SourcePosn p = expr->position();
  const string *str =
    intern((tempname == NULL) ? tempGenerator.next() : *tempname);
  TreeNode *name = new NameNode (TreeNode::omitted, str, (Decl *)NULL);
  TreeNode *varDecl =
    new VarDeclNode (false, expr->type()->addModifiers(Common::CompilerGenerated),
		     name, TreeNode::omitted, p);
  Decl *d = new LocalVarDecl(varDecl->simpName()->ident(),
			     varDecl->dtype(), varDecl, true);
  varDecl->simpName()->decl(d);
  declStmt = varDecl;
  
  ObjectNode *varNode = new ObjectNode (new NameNode(TreeNode::omitted,
						     str, d, p), p);
  varNode->type(expr->type());
  assnStmt = new ExpressionStmtNode(new AssignNode(varNode, expr, p), p);
  
  return CloneTree(varNode);
}


static ObjectNode *MakeTemporary(TreeNode *expr,
				 llist<TreeNode *> *&decls,
				 llist<TreeNode *> *&stmts)
{
  TreeNode *decl;
  TreeNode *stmt;
  ObjectNode * const result = MakeTemporary(expr, decl, stmt);  
  push(decls, decl);
  push(stmts, stmt);  
  return result;
}

BlockNode *AddBlockStmts(BlockNode *b, TreeNode *insertPt,
			 llist<TreeNode *> *newStmts)
{
  if (!newStmts)
    return b;

#if DEBUG_ADD_STMTS  
  cout << "Adding to block:\n";
  b->print(cout, 0);
  cout << "\ninsertPt:\n";
  if (insertPt == NULL) cout << "NULL";
  else insertPt->print(cout, 0);
  for (llist<TreeNode *> *s = newStmts; s; s = s->tail()) {
    cout << "\nTo be added:\n";
    s->front()->print(cout, 0);
  }
  cout << "\n";
#endif
    TreeListNode *s = b->stmts();
    int c = s->arity();
    llist<TreeNode *> *t = NULL;
    if (c != 0) {
	for (int i=c-1; i>=0; i--) {
	    t = cons(s->child(i), t);
	    if (s->child(i) == insertPt) {
		for ( ; newStmts; newStmts = newStmts->tail() ) {
		    t = cons(newStmts->front(), t);
		}
	    }
	}
    } else {
	for ( ; newStmts; newStmts = newStmts->tail() )
	    t = cons(newStmts->front(), t);
    }
    b->stmts(new TreeListNode(t));
#if DEBUG_ADD_STMTS  
  cout << "Result of adding to block:\n";
  b->print(cout, 0);
  cout << "\n";
#endif
    return b;
}

SwitchBranchNode *AddSwitchBranchStmts(SwitchBranchNode *b, TreeNode *insertPt,
				       llist<TreeNode *> *newStmts)
{
    TreeListNode *s = b->stmts();
    int c = s->arity();
    llist<TreeNode *> *t = NULL;
    if (c != 0) {
	for (int i=c-1; i>=0; i--) {
	    t = cons(s->child(i), t);
	    if (s->child(i) == insertPt) {
		for ( ; newStmts; newStmts = newStmts->tail() ) {
		    t = cons(newStmts->front(), t);
		}
	    }
	}
    } else {
	for ( ; newStmts; newStmts = newStmts->tail() )
	    t = cons(newStmts->front(), t);
    }
    b->stmts(new TreeListNode(t));
    return b;
}

void AddStmts(TreeNode *insertPt, llist<TreeNode *> *newStmts)
{
  TreeNode *container = insertPt->parent()->parent();
  if (newStmts)
    if (isBlockNode(container))
      AddBlockStmts((BlockNode *) container,
		    insertPt, newStmts);
    else if (isSwitchBranchNode(container))
      AddSwitchBranchStmts((SwitchBranchNode *) container,
			   insertPt, newStmts);
    else fatal_error("");
}

// newStmts is in reverse order...
BlockNode *AddBlockStmtsAtBegin(BlockNode *b, llist<TreeNode *> *newStmts)
{
#if DEBUG_ADD_STMTS  
  cout << "Adding to block with arity " << b->stmts()->arity();
  cout << "\n";
#endif
  TreeNode *insert = (b->stmts()->arity() ? b->stmts()->child(0) : (TreeNode *)NULL);
  return AddBlockStmts(b, insert, newStmts);
}

/* Non-destructive.  Create a new Block that includes everything in b
   followed by everything in l. */
static BlockNode *appendToBlock(BlockNode *b, llist<TreeNode *> *l)
{
  return new BlockNode(appendTreeList(b->stmts(), l), NULL, b->position());
}

void setImmutableDefaultInitExpr(TreeNode *immutableDeclNode) {
  // sets the initExpr() for an immutable declnode to be a call
  // to the immutable's default initializer
  assert(isVarDeclNode(immutableDeclNode) || isFieldDeclNode(immutableDeclNode));
  assert(immutableDeclNode->dtype()->isImmutable());
  assert(immutableDeclNode->initExpr()->absent());
  
  ExprNode *result;
  SourcePosn pos = immutableDeclNode->position();
  TypeNode *t = immutableDeclNode->dtype();

  if (t->isTitaniumArrayType() || t->isTitaniumBuiltinType()) {
    // code gen these immediately, because we have no hope of inlining them at the AST level anyhow
    result = new CodeLiteralExprNode(callNoArgConstructor(t), pos);
    }
  else { // is a standard immutable
    // convert into a simple method call to constructor (which returns an immutable by value)
    // we do this so the call will be visible to subsequent optimization phases (esp. method inlining)

    // first, grab the no-arg constructor decl node
    ClassDeclNode *cdn = static_cast<ClassDeclNode *>(t->decl()->source());
    assert(isClassDeclNode(cdn));
    TreeListNode *members = cdn->members();
    TreeNode *mdn = NULL;
    for (int i = 0 ; i < members->arity(); i++) {
      if (isConstructorDeclNode(members->child(i)) &&
          (members->child(i)->params()->absent() || 
           members->child(i)->params()->arity() == 0)) {
        assert(!mdn);
        mdn = members->child(i); // found it
        }
      }
    assert(mdn != NULL);

    // constructor transformed into a non-static method call on the object being constructed
    // this is actually kind of silly because the object parameter is never actually used in generated code
    TreeNode * const name = immutableDeclNode->simpName()->deepClone();
    if (isVarDeclNode(immutableDeclNode)) {
      result = new ObjectNode(name, pos);
    } else { // it's a field 
      // if we actually grab that field it will lower into redundant work
      TypeNode *cl = immutableDeclNode->decl()->container()->asType();
      result = new ObjectFieldAccessNode(new ThisNode(TreeNode::omitted, cl, currentThisFlags, pos), name, pos);
      // instead generate a bogus temp var as a placeholder (it won't be used)
      TreeNode *discard1, *discard2;
      result = MakeTemporary(result, discard1, discard2, intern("immutable_constructor_dummy"));
    }
    result = new ObjectFieldAccessNode(result, mdn->simpName()->deepClone(), pos);
    result = new MethodCallNode(result, NULL, pos); // no args
    }

  // constructors don't have a correct return type right now, so fake it
  result->type(t);
  
  immutableDeclNode->initExpr(result);
  }

/* Return an expression for the default initializer for a given type. */
ExprNode *defaultInitializer(TypeNode *t,
			     const SourcePosn &pos)
{
  ExprNode *result;
  if (t->isTitaniumArrayType() || t->isReference())
    result = new CastNode(new NullPntrNode(), t, pos);
  else if (t->isImmutable()) {
    fatal_error("use setImmutableDefaultInitExpr() for immutable *DeclNodes");
    //result = new CodeLiteralExprNode(callNoArgConstructor(t), pos);
  } else if (t->isPrimitive())
    result = new PrimitiveLitNode(Literal((int32) 0).cast(t->kind()));
  else fatal_error("unknown type in defaultInitializer");
  result->type(t);
  return result;
}

bool FieldDeclNode::compilerGeneratedInitExpr() const {
  return _compilerGeneratedInitExpr;
}
                                 
void FieldDeclNode::compilerGeneratedInitExpr(bool val) {
  _compilerGeneratedInitExpr = val;
} 

/* Convert any stmt or expr into a self-contained block that is lowered. */
/* Has no side effects except on t and its children. */
BlockNode *stmt_to_lowered_block(TreeNode *t)
{
  if (t->isStatementNode() || isSuperConstructorCallNode(t) ||
      isThisConstructorCallNode(t))
    t = new BlockNode(cons(t), NULL);
  else if (isStaticInitNode(t) || isInstanceInitNode(t)) 
    t = new BlockNode(cons(t->block()), NULL); 
  else if (t->absent())
    return new BlockNode(NULL, NULL);
  else {
    if (!t->isExprNode()) {
      cerr << "****\nInternal error lowering " << pseudocode(t) << endl;
      t->print(cerr, 3);
      cerr << "\n****\n";
      // fatal_error("");
    }
    return stmt_to_lowered_block(new ExpressionStmtNode(t));
  }

#if DEBUG_LOWER_STMT_TO_BLOCK
  static int count = 0;
  int n = count++;
  cout << "Lowering stmt " << n << " to block:\n";
  t->print(cout, 2);
  cout << "\n";
#endif

  /* At this point t is a block with one stmt in it. */

  llist<TreeNode *> *substmts = NULL;
  llist<TreeNode *> *subdecls = NULL;
  TreeNode *c = t->stmts()->child(0)->lower(subdecls, substmts);

#if DEBUG_LOWER_STMT_TO_BLOCK
  cout << "Lowered stmt " << n << " to block.  intermediate results:\n";
  cout << "c is:\n";
  c->print(cout, 2);
  cout << "\n";
  cout.flush();
#endif

  /* At this point t is a block with one or more stmts in it.
     Put the lowered stmt last in the block. */

  t->stmts()->child(t->stmts()->arity() - 1, c);

#if DEBUG_LOWER_STMT_TO_BLOCK
  cout << "Lowered stmt " << n << " to block.  intermediate results:\n";
  cout << "t is:\n";
  t->print(cout, 2);
  cout << "\n";
  cout.flush();
#endif

  t = AddBlockStmtsAtBegin((BlockNode *) t, substmts);
  t = AddBlockStmtsAtBegin((BlockNode *) t, subdecls);

#if DEBUG_LOWER_STMT_TO_BLOCK
  cout << "Lowered stmt " << n << " to block.  Result:\n";
  t->print(cout, 2);
  cout << "\n";
  cout.flush();
#endif

  SortVarDeclsInBlock((BlockNode *) t);
  return (BlockNode *) t;
}

// Pull out any cleanup operations associated with "oldJump", and
// arrange for them to be performed before "newJump".
//
// If there are indeed cleanup operations, then the result will be a
// BlockNode ending with "newJump".  If there are no cleanup
// operations, the result will just be "newJump" by itself.

static StatementNode *prependCleanups(GotoNode *newJump, TreeNode *oldJump)
{
  llist< TreeNode * > * const cleanups = oldJump->cleanups();
  if (cleanups) {
    TreeNode * const cleanupBlock = new BlockNode( cleanups, NULL, oldJump->position() );
    llist< TreeNode * > *sequence = 0;
    push( sequence, newJump );
    push( sequence, cleanupBlock );
    return new BlockNode( sequence, NULL, oldJump->position() );
  } else
    return newJump;
}

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

static ObjectNode *ProcessExpr(TreeNode *expr,
			       llist<TreeNode *> *&decls,
			       llist<TreeNode *> *&stmts)
{
    const int childCount = expr->arity();
    for (int sweep = 0; sweep < childCount; ++sweep)
	expr->child(sweep, expr->child(sweep)->lower(decls, stmts));

    return MakeTemporary(expr, decls, stmts);
}

#define ProcessAllSubExpr(e, decls, stmts) \
    ProcessSubExpr((e), 0, 0, (decls), (stmts))

/* If a==b then process all children of expr; Otherwise process
   child a and child b (if they exist).  Return expr. */
static TreeNode *ProcessSubExpr(TreeNode *expr,
				int a,
				int b,
				llist<TreeNode *> *&decls,
				llist<TreeNode *> *&stmts)
{
  const int childCount = expr->arity();
  for (int sweep = 0; sweep < childCount; ++sweep) {
    expr->child(sweep, expr->child(sweep)->lower(decls, stmts));
    if ((a == b || a == sweep || b == sweep) && !isVar(expr->child(sweep)))
      expr->child(sweep, MakeTemporary(expr->child(sweep), decls, stmts));
  }
  return expr;
}


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

static void checkNodeIsLegalToLower(TreeNode *t) {
  if (isThisFieldAccessNode(t) || 
      isSuperFieldAccessNode(t) ||
      isStringConcatNode(t) ||
      isStringConcatAssignNode(t) || 
      isAssertNode(t) || 
      isSynchronizedNode(t)) {
    cerr << "Internal compiler error: illegal TreeNode made it to lowering:" << endl;
    t->print(cerr);
    abort();
  }
}

TreeNode *TreeNode::lower(llist<TreeNode *> *&decls,
			  llist<TreeNode *> *&stmts)
{
  checkNodeIsLegalToLower(this);
  const int a = arity();
  for (int i = 0; i < a; i++) {
    if (!child(i)->absent() && !isVar(child(i)))
      child(i, child(i)->lower(decls, stmts));
  }
  return this;
}


ExprNode *ExprNode::lower(llist<TreeNode *> *&decls,
			  llist<TreeNode *> *&stmts)
{
  checkNodeIsLegalToLower(this);
  TreeNode::lower(decls, stmts);
  return this;
}


TreeNode *TemplateDeclNode::lower( llist< TreeNode * > *&, llist< TreeNode * > *& )
{
  return this;
}

TreeNode *ExpressionStmtNode::lower(llist<TreeNode *> *&decls,
				    llist<TreeNode *> *&stmts)
{
  assert(stmts == NULL);
  if (checkIF(false))
    return this;
  expr(expr()->lower(decls, stmts));
  TreeNode *me = this;
  TreeNode *myexpr = expr();
  while (isCastNode(myexpr)) myexpr = myexpr->opnd0();
  if (isVar(myexpr) || isOFAN(myexpr)) 
    me = new EmptyStmtNode(position()); /* expr has no side-effects, so drop it */
  if (stmts == NULL)
    return me;
  else {
    TreeNode *result = new BlockNode(extend(reverse(stmts),
					    cons((TreeNode *) me)), NULL);
    stmts = NULL;
    return result;
  }
}

TreeNode *ReturnNode::lower(llist<TreeNode *> *&decls,
			    llist<TreeNode *> *&stmts)
{
  assert(stmts == NULL);

  // completely evaluate return value
  if (!expr()->absent() && !isVar(expr()))
    expr(MakeTemporary(expr()->lower(decls, stmts), decls, stmts));

  // perform any last-minute cleanups
  if (cleanups()) {
    TreeNode *cleanBlock = new BlockNode(cleanups(), NULL, position());
    cleanBlock = cleanBlock->lower(decls, stmts);
    push(stmts, cleanBlock);
    cleanups(0);
  }
  
  AddStmts(this, stmts);  
  stmts = NULL;
  return this;
}

TreeNode *ThrowNode::lower(llist<TreeNode *> *&decls,
			   llist<TreeNode *> *&stmts)
{
  assert(stmts == NULL);
  expr(expr()->lower(decls, stmts));
  AddStmts(this, stmts);
  stmts = NULL;
  return this;
}

TreeNode *MonitorFetchInstanceNode::lower(llist<TreeNode *> *&decls,
					  llist<TreeNode *> *&stmts)
{
  assert(stmts == NULL);
  expr(expr()->lower(decls, stmts));
  return this;
}


static treeSet should_convert;

/* True iff t or any descendant is a Titanium array access. */
static bool contains_grid_access(const TreeNode *t)
{
  if (isTitaniumArrayAccessNode(t))
    return true;
  foriter (c, t->allChildren(), TreeNode::ConstChildIter)
    if (contains_grid_access(*c))
      return true;
  return false;
}

/* Consider t and all its subtrees.  Return true if any loops are marked for
   conversion to foreach.  Ignore loops that contain no titanium array
   accesses unless aggressive is true. */
static bool consider_loop_to_foreach_transform(TreeNode *t,
					       TreeNode *enclosingLoop,
					       bool aggressive)
{
  bool b = false;
  if (!(t == NULL || t->absent())) {
    if (isForNode(t)) {
      foriter (c, t->allChildren(), TreeNode::ChildIter)
	if (consider_loop_to_foreach_transform(*c, t, aggressive))
	  b = aggressive || contains_grid_access(t);
      if (!b)
	should_convert.insert(t);
#if DEBUG_CONVERT_FOR_TO_FOREACH
      cout <<
	(contains(should_convert, t) ? "should conv\n" : "shouldn't conv\n") <<
	pseudocode(t) << '\n';
#endif
      return true;
    }
    foriter (c, t->allChildren(), TreeNode::ChildIter)
      if (consider_loop_to_foreach_transform(*c, t, aggressive))
	b = true;
  }
  return b;
}


#if 0
static TreeListNode *empty_treelist(SourcePosn p = NoSourcePosition);

static TreeListNode *empty_treelist(SourcePosn p)
{
  static llist<TreeNode *> *l = NULL;
  return new TreeListNode(l, p);
}
#endif

static TreeNode *rewrite_while_and_do_loops(TreeNode *t);

static TreeNode *lower_method_body(TreeNode *body,
				   llist<TreeNode *> *&decls,
				   llist<TreeNode *> *&stmts)
{
  extern int opt_for_to_foreach_level;
  
  if (opt_for_to_foreach_level) {
    should_convert.clear();
    body = rewrite_while_and_do_loops(body);
    consider_loop_to_foreach_transform(body, NULL,
				       opt_for_to_foreach_level > 1);
  }
  if (!isBlockNode(body))
    body = new BlockNode(cons(body), NULL);
  body = body->lower(decls, stmts);
  if (!isBlockNode(body))
    body = new BlockNode(cons(body), NULL);
  body = AddBlockStmtsAtBegin((BlockNode *)body, stmts);
  body = AddBlockStmtsAtBegin((BlockNode *)body, decls);
  decls = NULL; stmts = NULL;
  return body;
}

BlockNode *EncapsulateInits(vector<TreeNode *> inits);

static TreeNode *staticInitializer(TypeDeclNode *tdn) {
  vector< TreeNode * > classInits;
  foriter (member, tdn->members()->allChildren(), TreeNode::ChildIter) {
    TreeNode * const node = *member;
    if (isStaticInitNode(node) || 
	(isFieldDeclNode(node) && (node->decl()->modifiers() & Common::Static)))
	classInits.push_back(node);
  }
  return new StaticInitNode(EncapsulateInits(classInits), tdn->position());
}

TreeNode *ClassDeclNode::lower(llist<TreeNode *> *&decls,
				llist<TreeNode *> *&stmts)
{
  assert(decls == NULL);
  assert(stmts == NULL);
  TreeNode::lower(decls,stmts);

  // lower all static initializers into member 0, reserved by the parser
  // for this purpose
  TreeNode *sinit = staticInitializer(this);
  members()->child(0, sinit);
  
  // remove InstanceInitNodes since these get lowered into constructors,
  // and all but first StaticInitNode
  llist<TreeNode*> *contents = cons(sinit);
  bool changed = false;
  int i, num = members()->arity();
  for (i = 1; i < num; i++) {
    TreeNode * const node = members()->child(i);
    if (isInstanceInitNode(node) || isStaticInitNode(node)) { changed = true; }
    else contents = cons(node, contents);
  }
  if (changed) {
    contents = dreverse(contents); // maintain order
    members(new TreeListNode(contents, position()));
  } else free_all(contents);

  return this; 
}

TreeNode *InterfaceDeclNode::lower(llist<TreeNode *> *&decls,
				   llist<TreeNode *> *&stmts)
{
  TreeNode::lower(decls, stmts);

  // lower all static initializations into member 0, reserved by the parser
  // for this purpose
  TreeNode *sinit = staticInitializer(this);
  members()->child(0, sinit);
  // static initializers are illegal in interfaces, so nothing to remove

  return this;
}

TreeNode *MethodDeclNode::lower(llist<TreeNode *> *&decls,
				llist<TreeNode *> *&stmts)
{
  assert(decls == NULL);
  assert(stmts == NULL);
  if (!body()->absent()) {
    currentThisFlags = relevantThisFlags( *this );
    body(lower_method_body(body(), decls, stmts));
  }    
  return this;
}

TreeNode *instanceInitializerBlock(ClassDeclNode *cdn); // defined below

ClassDeclNode *currentClassDeclNode = NULL;
// This is kind of a hack - used to pass info from 
// ConstructorDeclNode::lower to SuperConstructorCallNode::lower
// noone else should touch this or rely on it

TreeNode *ConstructorDeclNode::lower(llist<TreeNode *> *&decls,
				     llist<TreeNode *> *&stmts)
{
#if 0
  cout << "Lowering constructor:\n";
  print(cout, 2);
  cout << "\n";
#endif
  assert(decls == NULL);
  assert(stmts == NULL);
  currentThisFlags = relevantThisFlags( *this );
  
  ClassDeclNode *cdn = dynamic_cast<ClassDeclNode *>(decl()->container()->source());

  if (constructorCall() == TreeNode::omitted) {
    // this is the bottom-level immutable constructor (or java.lang.Object)
    // perform instance field initialization here
    //assert(decl()->type()->isImmutable() || cdn->decl() == ObjectDecl); // also have some ti.domains garbage here
    constructorCall(instanceInitializerBlock(cdn));
  }
  else { 
    currentClassDeclNode = dynamic_cast<ClassDeclNode *>(decl()->container()->source());
    constructorCall(stmt_to_lowered_block(constructorCall()));
    currentClassDeclNode = NULL;
  }

  // Inner and local classes.
  if (initEncloser() != NULL && !initEncloser()->absent()) {
    llist<TreeNode*>* l = NULL;
    push(l, constructorCall());
    push(l, stmt_to_lowered_block(initEncloser()));
    // Add null check for enclosing instance.
    if (cdn->hasEnclosingInstance() &&
	!(cdn->enclosingType()->flags() & Immutable)) {
      extern llist<TreeNode *> *addToFront(TreeNode *, TreeListNode *);
      NameNode *id = new NameNode(TreeNode::omitted, 
				  params()->child(0)->simpName()->ident(),
				  params()->child(0)->simpName()->decl(),
				  NoSourcePosition);
      TreeNode *chk = new CheckNullNode(new ObjectNode(id, position()),
					position());
      push(l, stmt_to_lowered_block(chk));
    }
    constructorCall(new BlockNode(l, NULL));
    initEncloser(TreeNode::omitted);
  }
  if (!body()->absent())
    body(lower_method_body(body(), decls, stmts));
#if 0
  cout << "Constructor lowered to:\n";
  print(cout, 2);
  cout << "\n";
#endif
  return this;
}

TreeNode *BlockNode::lower(llist<TreeNode *> *&,
			   llist<TreeNode *> *&)
{
  if (!checkIF(false)) {
    TreeListNode *s = stmts();
    int childCount = s->arity();
    //static int k = 0;
    //int n = k++;

    /* First, make sure all vardecls have initializers. */
    for (int i = childCount; --i >= 0; ) {
      if (isVarDeclNode(s->child(i))) {
        VarDeclNode *vdn = static_cast<VarDeclNode*>(s->child(i));
	// cout << "Child " << i << " is a var decl" << endl;
	if (vdn->initExpr()->absent() && vdn->needsDefaultInitialization()) {
	  // don't bother to initialize temps
	  assert(!(vdn->dtype()->modifiers() & Common::CompilerGenerated));
	  if (vdn->dtype()->isImmutable()) 
	    setImmutableDefaultInitExpr(vdn);
	  else 
	    vdn->initExpr(defaultInitializer(vdn->dtype(), vdn->position()));
          // ensure we initialize exactly once, even if we repeatedly lower this BlockNode
          vdn->needsDefaultInitialization(false); 
	  // cout << "Set initializer to ";
	  // cout << PCODE(s->child(i)->initExpr());
	  // cout << endl;
	}
      }
    }

    SortVarDeclsInBlock(this);
    s = stmts();
    childCount = s->arity();

    // cout << n << ": Doing a block with " << childCount << " children\n";
    for (int i = childCount; --i >= 0; ) {
      if (isVarDeclNode(s->child(i))) {
	// cout << "Child " << i << " is a var decl" << endl;
      } else if (isMonitorFetchNode(s->child(i))) {
	/* Since a MonitorFetchNode has an implict variable declaration, it can't
	 * be placed in its own block. */
	llist<TreeNode *> *substmts = NULL, *subdecls = NULL;
	TreeNode *mon = s->child(i);
	mon->lower(subdecls, substmts);
	i += subdecls->size();
	i += substmts->size();
	*this = *AddBlockStmts((BlockNode *) this, mon, substmts);
	*this = *AddBlockStmtsAtBegin((BlockNode *) this, subdecls);
	s = stmts();
	childCount = s->arity();
      } else {
	// cout << "Lowering child " << i << " of a block\n";
	// cout << "BEFORE " << n << '.' << i << "\n\n";
	// s->child(i)->print(cout, 0);
	// cout << "\n\n";

	s->child(i, stmt_to_lowered_block(s->child(i)));

	// cout << "AFTER " << n << '.' << i << "\n\n";
	// s->child(i)->print(cout, 0);
	// cout << "\n\n";
	// s->child(i)->checkIF(true);
      }
    }

    stmts(s);

    // cout << "Lowered block: " << endl;
    // cout << PCODE(this);
    // cout << endl;
    // checkIF(true);
    // cout << n << ": Done\n";
  }
  return this;
}

TreeNode *IfStmtNode::lower(llist<TreeNode *> *&decls,
			    llist<TreeNode *> *&stmts)
{
  if (!isBlockNode(thenPart()))
    thenPart(new BlockNode(cons(thenPart()), NULL));

  if (!isBlockNode(elsePart()))
    elsePart(new BlockNode(cons(elsePart()), NULL));

  assert(stmts == NULL);
  assert(decls == NULL);
  condition( condition()->lower(decls, stmts) );
  AddStmts(this, stmts);
  AddStmts(this, decls);
  stmts = NULL;
  decls = NULL;
  thenPart( thenPart()->lower(decls, stmts) );
  elsePart( elsePart()->lower(decls, stmts) );
  assert(stmts == NULL);
  assert(decls == NULL);

#if 0 /* DEBUG_LOWERING */
  cout << "Lowered if statement to:\n";
  print(cout, 0);
  cout << "\n";
#endif

  return this;
}

/* 
Lowering of while, do, and for, break, continue: use GOTO.
*/

static TreeNode *replaceBreakContinue(TreeNode *t, TreeNode *l,
				      TreeNode *breakTo, TreeNode *continueTo,
				      int *count = NULL);
static TreeNode *replaceBreak(TreeNode *t, TreeNode *l,
			      TreeNode *breakTo, int *count = NULL);

// In the subtree t, replace a break of statement l with a GOTO to breakTo;
// if count is not NULL, increment *count once per replaced break.
// Also replace a continue of statement l with a GOTO to continueTo.
static TreeNode *replaceBreakContinue(TreeNode *t, TreeNode *l,
				      TreeNode *breakTo, TreeNode *continueTo,
				      int *count)
{
  if (isBreakNode(t))
    if (t->destination() == l) {
      if (count != NULL)
	++*count;
      return prependCleanups(GOTO(breakTo), t);
    } else
      return t;
  else if (continueTo != NULL && isContinueNode(t))
    if (t->destination() == l) {
      return prependCleanups(GOTO(continueTo), t);
    } else
      return t;
  else {
    const int childCount = t->arity();
    for (int sweep = 0; sweep < childCount; ++sweep)
      t->child(sweep, replaceBreakContinue(t->child(sweep), l,
					   breakTo, continueTo, count));
    return t;
  }
}

static TreeNode *replaceBreak(TreeNode *t, TreeNode *l,
			      TreeNode *breakTo, int *count)
{
  return replaceBreakContinue(t, l, breakTo, NULL, count);
}

// The only reason this is complicated is that breaks and continues
// for the original loop need to be dealt with.  We convert them to gotos.
static TreeNode *convert_while_to_for(WhileNode *n)
{
/*  while (condition) { body; } =>
  if (!condition) goto after;
  for(;;) {
   body; // with "break" replaced with "goto after" and "continue" replaced with "goto con"
   con:
   if (!condition) goto after;
  }
  after:
*/
  // This translation ensures the body is executed on every iteration, for best loop opts
  SourcePosn p = n->position();
  TreeNode *conLabel = NAKEDLABEL(), *afterLabel = NAKEDLABEL();
  TreeNode *test = new IfStmtNode(new NotNode(n->test(), n->test()->position()),
			GOTO(afterLabel), TreeNode::omitted, p);
  TreeNode *test2 = test->deepClone();
  // EmptyStmtNode below preserves loop position reported by loopStats
  llist<TreeNode *> *t = cons((TreeNode *)new EmptyStmtNode(p), cons(n->stmt(), cons(conLabel, cons(test2))));
  TreeNode *loopBody = new BlockNode(t, NULL);
  replaceBreakContinue(loopBody, n, afterLabel, conLabel);
  TreeNode *f = new ForNode(NULL, TreeNode::omitted, NULL, loopBody, p);
  return new BlockNode(cons(test, cons(f, cons(afterLabel))), NULL);
}

// The only reason this is complicated is that breaks and continues
// for the original loop need to be dealt with.  We convert them to gotos.
static TreeNode *convert_do_to_for(DoNode *n)
{
/*  do { body; } while (condition); =>
  for(;;) {
   body; // with "break" replaced with "goto after" and "continue" replaced with "goto con"
   con:
   if (!condition) goto after;
  }
  after:
*/
  /* special case: don't modify "do { } while (false)" idiom
     because we want that to expand into straight-line code with no cruft */
  if (n->test()->constantType() == Common::BoolKind && 
     !n->test()->literal().boolValue()) return n;

  SourcePosn p = n->position();
  TreeNode *conLabel = NAKEDLABEL(), *afterLabel = NAKEDLABEL();
  llist<TreeNode *> *t;
  // Create the for loop body
  //   last in loop body: check exit condition
  t = cons(static_cast<TreeNode *>
	   (new IfStmtNode(new NotNode(n->test(), n->test()->position()),
			   GOTO(afterLabel), TreeNode::omitted, p)));
  //   1st in loop body: n->stmt()
  t = cons(n->stmt(), cons(conLabel, t));
  TreeNode *loopBody = new BlockNode(t, NULL);
  replaceBreakContinue(loopBody, n, afterLabel, conLabel);
  TreeNode *f = new ForNode(NULL, TreeNode::omitted, NULL, loopBody, p);
  return new BlockNode(cons(f, cons(afterLabel)), NULL);
}

/* Rewrite while and do loops as for loops.  This is to allow the
   for->foreach transformation to have a crack at them.  It shouldn't
   affect performance otherwise. */
static TreeNode *rewrite_while_and_do_loops(TreeNode *t)
{
  foriter (c, t->allChildren(), TreeNode::ChildIter)
    *c = rewrite_while_and_do_loops(*c);
  if (isWhileNode(t))
    return convert_while_to_for(static_cast<WhileNode *>(t));
  if (isDoNode(t))
    return convert_do_to_for(static_cast<DoNode *>(t));
  else
    return t;
}

TreeNode *ForEachPairNode::lower(llist<TreeNode *> *&decls,
				 llist<TreeNode *> *&stmts)
{
  return ProcessSubExpr(this, -1, 1, decls, stmts);
}

/* After lowering, the stmt() should be a block containing a single statement,
   a LabeledStmtNode that contains a block.  That inner block is where the
   work actually gets done.  The outer label is never used.  This is dumb,
   but apparently something in the optimizer may croak otherwise. */
TreeNode *ForEachStmtNode::lower(llist<TreeNode *> *&decls,
				 llist<TreeNode *> *&stmts)
{
  assert(stmts == NULL);
  assert(decls == NULL);

  if (!isBlockNode(stmt()))
    stmt(new BlockNode(cons(stmt()), NULL, stmt()->position()));

  TreeNode *after = NAKEDLABEL(), *continueTo = NAKEDLABEL();
  stmt(appendToBlock((BlockNode *) stmt(), cons(continueTo)));
  TreeNode *top = LABELED(stmt(), stmt()->position());
  int count = 0;

  assert(arity() == 2);

  stmt(new BlockNode(cons(top), NULL));
  replaceBreakContinue(this, this, after, continueTo, &count);
  if (stride() == NULL)
    vars((TreeListNode *) vars()->lower(decls, stmts));
  AddStmts(this, decls);
  AddStmts(this, stmts);
  stmts = NULL;
  decls = NULL;
  stmt(stmt_to_lowered_block(stmt()));
  return ((count == 0) ?
	  (TreeNode *)this :
	  new BlockNode(cons((TreeNode *) this, cons(after)), NULL, position()));
}

TreeNode *LabeledStmtNode::lower(llist<TreeNode *> *&decls,
				 llist<TreeNode *> *&stmts)
{
  if (isOmittedNode(stmt()))
    return (TreeNode *) this;
  else {
    TreeNode *after = NAKEDLABEL(), *s = stmt(), *r;
    int count = 0;
    stmt(stmt_to_lowered_block(replaceBreak(s, s, after, &count)));
    r = ((count == 0) ?
	 (TreeNode *) this :
	 new BlockNode(cons((TreeNode *) this, cons(after)), NULL));
#if DEBUG_LABELEDSTMT
    cout << "Lowered labeled stmt to:" << endl;
    pseudoprint(cout, 0);
    cout << endl;
#endif
    return r;
  }
}

TreeNode *WhileNode::lower(llist<TreeNode *> *&decls,
			   llist<TreeNode *> *&stmts)
{
  // while (test) do S;   =>    { goto bot; top: S; bot: if (test) goto top; }

#if DEBUG_GOTO
  cout << "Lowering while loop:\n";
  print(cout, 0);
  cout << "\n";
#endif

  const SourcePosn pos = position();

  TreeNode *body = stmt_to_lowered_block(stmt());
  TreeNode *s = LABELED(body, pos);
  BlockNode *b =
    stmt_to_lowered_block(new IfStmtNode(test(), GOTO(s), TreeNode::omitted,
					 test()->position()));
#if DEBUG_GOTO
  cout << "Test is:\n";
  b->print(cout, 0);
  cout << "\n";
  cout << "Body is:\n";
  body->print(cout, 0);
  cout << "\n";
#endif
		   
  TreeNode *bot = LABELED(b, pos);
  TreeNode *after = NAKEDLABEL();
  int count = 0;
  replaceBreakContinue(body, this, after, bot, &count);
  b = new BlockNode(count == 0 ? cons(bot) : cons(bot, cons(after)), NULL);

  b = AddBlockStmtsAtBegin(b, cons(s, cons((TreeNode *) GOTO(bot))));

#if DEBUG_GOTO
  cout << "\nwhile loop lowered to:\n";
  b->print(cout, 0);
  cout << "\n";
#endif

  return b;
}

TreeNode *DoNode::lower(llist<TreeNode *> *&decls,
			llist<TreeNode *> *&stmts)
{
  // do S while (test)    =>    { label: S; if (test) goto label; }

#if DEBUG_GOTO
  cout << "Lowering do loop:\n";
  print(cout, 0);
  cout << "\n";
#endif

  const SourcePosn pos = position();

  TreeNode *body = stmt_to_lowered_block(stmt());
  TreeNode *s = LABELED(body, pos);
  BlockNode *b =
    stmt_to_lowered_block(new IfStmtNode(test(), GOTO(s), TreeNode::omitted,
					 test()->position()));
		   
  TreeNode *bot = LABELED(b, pos);
  TreeNode *after = NAKEDLABEL();
  int count = 0;
  replaceBreakContinue(body, this, after, bot, &count);
  b = new BlockNode((count == 0) ? cons(bot) : cons(bot, cons(after)), NULL);

  b = AddBlockStmtsAtBegin(b, cons(s));

#if DEBUG_GOTO
  cout << "\ndo loop lowered to:\n";
  b-> print(cout, 0);
  cout << "\n";
#endif

  return b;
}

static bool for_should_become_foreach(ForNode *f)
{
  return contains(should_convert, f);
}

/* There are two cases: either the ForNode is converted to a foreach,
   or to a while loop.  In either case, additional lowering is done
   after the conversion. */
TreeNode *ForNode::lower(llist<TreeNode *> *&decls,
			 llist<TreeNode *> *&stmts)
{
  bool test_absent = test()->absent();
  if (for_should_become_foreach(this)) {
    TreeNode *updateLabel = NAKEDLABEL(), *afterLabel = NAKEDLABEL();
    llist<TreeNode *> *t;
    // Create the foreach loop body
    TreeListNode *updStmts = update();
    //   last in loop body: check exit condition
    t = test_absent ?
      NULL :
      cons(static_cast<TreeNode *>
	   (new IfStmtNode(new NotNode(test()),
			   new GotoNode(afterLabel), TreeNode::omitted,
			   position())));
    //   2nd to last in loop body: the update
    for (int c = updStmts->arity(); --c >= 0; )
      t = cons(updStmts->child(c), t);
    //   1st in loop body: stmt()
    t = cons(stmt(), cons(updateLabel, t));
    TreeNode *loopBody = new BlockNode(t, NULL);
    replaceBreakContinue(loopBody, this, afterLabel, updateLabel);

    // Create the foreach loop and follow it with the afterLabel
    static TypeNode *pt1 = makePointType(1);
    pt1->modifiers(Local);
    const string *name = intern(tempGenerator.next());
    TreeNode *p = new NameNode(TreeNode::omitted, name, NULL, position());
    t = cons(static_cast<TreeNode *>
	     (new ForEachPairNode(p, TreeNode::omitted, TreeNode::omitted)));
    ForEachStmtNode *f = new ForEachStmtNode(t, loopBody, false, position());
    Decl *d = new LocalVarDecl(f->vars()->child(0)->simpName()->ident(), pt1,
			       f->vars()->child(0), false);
    f->vars()->child(0)->simpName()->decl(d);
    f->ordered() = f->tentative() = true;
    f->stride() = new PrimitiveLitNode(Literal((int32) 1));
    TreeNode *result = new BlockNode(cons(static_cast<TreeNode *>(f),
					  cons(afterLabel)),
				     NULL, position());
    if (!test_absent)
      result = new IfStmtNode(CloneTree(test()), result,
			      TreeNode::omitted, position());
    f->cannotBeEmpty() = result;

    // Include the initialization part of the for loop
    TreeListNode *initStmts = init();
    t = cons(result);
    // Attach the initStmts to a newly created enclosing block.
    for (int c = initStmts->arity(); --c >= 0; )
      t = cons(initStmts->child(c), t);
    result = new BlockNode(t, NULL);

#if DEBUG_CONVERT_FOR_TO_FOREACH
    cout << "for loop converted to foreach:\n" <<
      pseudocode(result) << endl;
#endif
    result = stmt_to_lowered_block(result);
#if DEBUG_CONVERT_FOR_TO_FOREACH
    cout << "for loop that was converted to foreach was lowered to:\n" <<
      pseudocode(result) << endl;
#endif
    return result;
  }
  
  // Normal case: lower for to while

  TreeNode *updateLabel = NAKEDLABEL(), *afterLabel = NAKEDLABEL();

#if DEBUG_LOWER_FOR_TO_WHILE
  cout << "Lowering for loop:\n";
  print(cout, 0);
  cout << "\n";
#endif

  // Create the loop body: the body of the "for" plus the update stmts.
  TreeListNode *updStmts = update();
  llist<TreeNode *> *updList = NULL;
  for (int c = updStmts->arity(); --c >= 0; )
    updList = cons(updStmts->child(c), updList);
  updList = cons(stmt(), cons(updateLabel, updList));
  TreeNode *loopBody = new BlockNode(updList, NULL);
  int count = 0;
  replaceBreakContinue(loopBody, this, afterLabel, updateLabel, &count);

  // Construct a while loop with appropriate test, and body from above.
  TreeNode *whileLoop;
  if (test()->absent())
    whileLoop = new WhileNode(newBoolLit(true), loopBody);
  else
    whileLoop = new WhileNode(test(), loopBody);

  // Handle the init stmts.
  TreeListNode *initStmts = init();
  llist<TreeNode *> *t =
    (count == 0 ? cons(whileLoop) : cons(whileLoop, cons(afterLabel)));
  // Attach the initStmts to a newly created enclosing block
  // with the new while loop as the last statement of the block.
  for (int c = initStmts->arity(); --c >= 0; )
    t = cons(initStmts->child(c), t);
    
  BlockNode *b = new BlockNode(t, NULL);
#if DEBUG_LOWER_FOR_TO_WHILE
  cout << "for loop lowered to while:\n";
  b-> print(cout, 0);
  cout << "\n";
#endif
  return b->lower(decls, stmts);
}


TreeNode *SwitchNode::lower(llist<TreeNode *> *&decls,
			    llist<TreeNode *> *&newStmts)
{
  assert(newStmts == NULL);
  expr( expr()->lower(decls, newStmts) );
  AddStmts(this, newStmts);
  newStmts = NULL;

  TreeListNode *swB = switchBlocks();
  const int childCount = swB->arity();
  for (int sweep = 0; sweep < childCount; ++sweep) {
    SwitchBranchNode *b = (SwitchBranchNode *)swB->child(sweep);

    SortVarDeclsInSwitch(b);
    TreeListNode *s = b->stmts();
    const int num = s->arity();

    for (int i = 0; i < num; i++)
      if (!isVarDeclNode(s->child(i)))
	s->child(i, stmt_to_lowered_block(s->child(i)));
  }

  int count = 0;
  TreeNode *after = NAKEDLABEL();
  replaceBreak(this, this, after, &count);

  return ((count == 0) ?
	  (TreeNode *) this :
	  new BlockNode(cons((TreeNode *) this, cons(after)), NULL));
}

/////////////////////////////////////////////////////////////////////////////
// Basic unary exprs
/////////////////////////////////////////////////////////////////////////////

#define UNARY(this, decls, stmts) \
	ProcessSubExpr((this), 0, -1, (decls), (stmts)), (this)

ExprNode *UnaryArithNode::lower(llist<TreeNode *> *&decls,
				llist<TreeNode *> *&stmts)
{
  return UNARY(this, decls, stmts);
}

ExprNode *ComplementNode::lower(llist<TreeNode *> *&decls,
				llist<TreeNode *> *&stmts)
{
  return UNARY(this, decls, stmts);
}

ExprNode *NotNode::lower(llist<TreeNode *> *&decls,
			 llist<TreeNode *> *&stmts)
{
  return UNARY(this, decls, stmts);
}

ExprNode *InstanceOfNode::lower(llist<TreeNode *> *&decls,
				llist<TreeNode *> *&stmts)
{
/* Java spec 15.19.2 states that result of instanceof is true
 * iff the passed expression is _not_ null and it could be
 * cast to the given type without raising ClassCastException.
 */
  if (opnd0()->type()->typeIdent(dtype())) {
    ExprNode *t = new NENode(opnd0(), 
                             new CastNode(new NullPntrNode(position()), 
                               opnd0()->type(), position()), position());
    return t->lower(decls, stmts);
  } else
    return UNARY(this, decls, stmts);
}

ExprNode *CastNode::lower(llist<TreeNode *> *&decls,
			  llist<TreeNode *> *&stmts)
{
  if (opnd0()->type()->typeIdent(dtype()))
    return ((ExprNode *) opnd0())->lower(decls, stmts);
  else
    return UNARY(this, decls, stmts);
}

ExprNode *ObjectFieldAccessNode::lower(llist<TreeNode *> *&decls,
				       llist<TreeNode *> *&stmts)
{
  if ((decl()->modifiers() & Static) &&
      (isThisNode(object()) || isObjectNode(object())))
    return this;
  else
    return UNARY(this, decls, stmts);
}

TreeNode *AllocateArrayDimensionNode::lower(llist<TreeNode *> *&decls,
					    llist<TreeNode *> *&stmts)
{
  return UNARY(this, decls, stmts);
}

ExprNode *DomainNode::lower(llist<TreeNode *> *&decls,
			    llist<TreeNode *> *&stmts)
{
  if (isIFPointOrDomainConstructor(this))
    return this;
  // cout << PCODE(this); cout << " lowered to ";
  args()->child(0, ProcessAllSubExpr(args()->child(0), decls, stmts));
  // cout << PCODE(this); cout << endl;
  return this;
}

ExprNode *PointNode::lower(llist<TreeNode *> *&decls,
			   llist<TreeNode *> *&stmts)
{
  // cout << PCODE(this) << " lowered to ";
  if (!isIFPointOrDomainConstructor(this))
    args((TreeListNode *) ProcessAllSubExpr(args(), decls, stmts));
  // cout << PCODE(this) << endl;
  return this;
}

/////////////////////////////////////////////////////////////////////////////
// Basic binary exprs
/////////////////////////////////////////////////////////////////////////////

#define BINARY(this, decls, stmts) \
	ProcessSubExpr((this), 0, 1, (decls), (stmts)), (this)

ExprNode *BinaryArithNode::lower(llist<TreeNode *> *&decls,
				 llist<TreeNode *> *&stmts)
{
  return BINARY(this, decls, stmts);
}

ExprNode *ShiftNode::lower(llist<TreeNode *> *&decls,
			   llist<TreeNode *> *&stmts)
{
  return BINARY(this, decls, stmts);
}

ExprNode *EqualityNode::lower(llist<TreeNode *> *&decls,
			      llist<TreeNode *> *&stmts)
{
  return BINARY(this, decls, stmts);
}

ExprNode *RelationNode::lower(llist<TreeNode *> *&decls,
			      llist<TreeNode *> *&stmts)
{
  return BINARY(this, decls, stmts);
}

ExprNode *BitwiseNode::lower(llist<TreeNode *> *&decls,
			     llist<TreeNode *> *&stmts)
{
  return BINARY(this, decls, stmts);
}

ExprNode *CandNode::lower(llist<TreeNode *> *&decls,
			  llist<TreeNode *> *&stmts)
{
  IfExprNode *n = new IfExprNode(opnd0(), opnd1(),
				 newBoolLit(false, position()), position());
  n->type(opnd1()->type());
  return n->lower(decls, stmts);
}

ExprNode *CorNode::lower(llist<TreeNode *> *&decls,
			 llist<TreeNode *> *&stmts)
{
  IfExprNode *n = new IfExprNode(opnd0(), newBoolLit(true, position()),
				 opnd1(), position());
  n->type(opnd1()->type());
  return n->lower(decls, stmts);
}

ExprNode *ArrayAccessNode::lower(llist<TreeNode *> *&decls,
				 llist<TreeNode *> *&stmts)
{
  return BINARY(this, decls, stmts);
}

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


ExprNode *AssignNode::lower(llist<TreeNode *> *&decls,
			    llist<TreeNode *> *&stmts)
{
  opnd0(opnd0()->lower(decls, stmts));
  opnd1(opnd1()->lower(decls, stmts));

  if (parent() != NULL && isExpressionStmtNode(parent()))
    return this; /* parent will execute the side effect */
  else {
    push(stmts, new ExpressionStmtNode(this)); /* execute the side effect */
    /* parent may need the value resulting from this AssignNode 
     * both opnd0 and opnd1 compute the necessary value, but it's
     * not safe in general to return a copy of either one - because the lhs
     * (opnd0) may be a user variable changed by a subsequent assign 
     * before the value is used by our parent, and we cannot return a 
     * copy of opnd1 because in the case of x = x + 1 the rhs 
     * no longer computes the correct value, and otherwise it may
     * read other user variables that change subsequent to our parent's use
     */
    TreeNode *op0 = opnd0();
    TreeNode *op1 = opnd1();
    while (isCastNode(op0)) op0 = op0->opnd0();
    while (isCastNode(op1)) op1 = op1->opnd0();
    if (isConstant(op0) || isNullPntrNode(op0) ||
        (isLocalVar(op0) && (op0->decl()->type()->modifiers() & CompilerGenerated))) {
      /* lhs is a constant or single-assignment compiler temporary, so case 1 above cannot happen */
      return static_cast<ExprNode *>(CloneTree(opnd0()));
    } else if (isConstant(op1) || isNullPntrNode(op1) ||
        (isLocalVar(op1) && (op1->decl()->type()->modifiers() & CompilerGenerated))) {
      /* rhs is a constant or single-assignment compiler temporary, so case 2 above cannot happen */
      return static_cast<ExprNode *>(CloneTree(opnd1()));
    } else { /* general case - create a new compiler temp to store the result */
      return MakeTemporary(CloneTree(opnd0()), decls, stmts);
    }
  }
}

/* This will have an opnd0() (call it a) that is an assignment.
   Example:
    a->opnd0(): Test.a.foo().x
    a->opnd1(): (String local)(StringBuffer)new StringBuffer local ((String)Test.a.foo().x) .append((String)"dog").append((String)"cat").toString()
    y: new StringBuffer local ((String)Test.a.foo().x) 
    lhs: x_8.x

    The problem is that a clone of a->opnd0() also appears in a->opnd1(),
    which would lead to side-effects occurring twice when they should only
    occur once.  We fix this by replacing both clones with a lowered version.
*/
ExprNode *StringConcatAssignPreLoweringNode::lower(llist<TreeNode *> *&decls,
						   llist<TreeNode *> *&stmts)
{
  AssignNode *a = static_cast<AssignNode *>(opnd0());
  AllocateNode *y = a->opnd1()->findAllocateNode();
  TreeNode *parent_of_right_clone = 
    isCastNode(y->args()->child(0)) ?
    y->args()->child(0) :
    y->args();
  /* The call to lower() in the next line puts the necessary side-effects
     in stmts. */ 
  TreeNode *lhs = parent_of_right_clone->child(0)->lower(decls, stmts);
  parent_of_right_clone->child(0, lhs);
  a->opnd0(lhs->deepClone());
  return a->lower(decls, stmts);
}

static ExprNode *opAssignNode_lower(TreeNode *x,
				    llist<TreeNode *> *&decls,
				    llist<TreeNode *> *&stmts)
{
  ExprNode *t;
  bool MC = isMethodCallAssignNode(x);
  bool MC_RHSOv = MC && ((MethodCallAssignNode*)x)->isRewrittenRHSOpOverload();

  TreeNode *lhs;
  if (MC_RHSOv) lhs = x->args()->child(0);
  else if (MC) lhs = x->method()->object();
  else lhs = x->child(0);
  lhs = lhs->lower(decls, stmts);

  TreeNode *assignment_target = CloneTree(lhs);
  TreeNode *rhs = x->child(1);
  const SourcePosn pos = x->position();

#if DEBUG_OPASSIGN
  cout << "lowering ";
  x->pseudoprint(cout, 0);
  cout << endl;
  cout << "lhs: ";
  lhs->pseudoprint(cout, 0);
  cout << endl;
  cout << "rhs: ";
  rhs->pseudoprint(cout, 0);
  cout << endl;
#endif

  if (isMultAssignNode(x)) {
    t = new MultNode(lhs, rhs, pos);
  } else if (isDivAssignNode(x)) {
    t = new DivNode(lhs, rhs, pos);
  } else if (isRemAssignNode(x)) {
    t = new RemNode(lhs, rhs, pos);
  } else if (isPlusAssignNode(x)) {
    t = new PlusNode(lhs, rhs, pos);
  } else if (isMinusAssignNode(x)) {
    t = new MinusNode(lhs, rhs, pos);	
  } else if (isLeftShiftLogAssignNode(x)) {
    t = new LeftShiftLogNode(lhs, rhs, pos);
  } else if (isRightShiftLogAssignNode(x)) {
    t = new RightShiftLogNode(lhs, rhs, pos);
  } else if (isRightShiftArithAssignNode(x)) {
    t = new RightShiftArithNode(lhs, rhs, pos);
  } else if (isBitAndAssignNode(x)) {
    t = new BitAndNode(lhs, rhs, pos);
  } else if (isBitXorAssignNode(x)) {
    t = new BitXorNode(lhs, rhs, pos);
  } else if (isBitOrAssignNode(x)) {
    t = new BitOrNode(lhs, rhs, pos);
  } else if (MC_RHSOv) {
    assert(x->args()->arity() == 2 && isNullOrCastOfNull(x->args()->child(1)));
    x->args()->child(0, lhs);
    x->method(x->method()->lower(decls, stmts));
    TreeNode *arg1 = x->method()->object()->deepClone();
    if (!arg1->type()->typeIdent(x->args()->child(1)->type()))
      arg1 = new CastNode(arg1, x->args()->child(1)->type());
    x->args()->child(1, arg1);
    MethodCallNode *m = new MethodCallNode(x->method(), NULL, pos);
    m->args(x->args());
    t = m;
  } else if (MC) {
    MethodCallNode *m = new MethodCallNode(x->method(), NULL, pos);
    m->method()->object(lhs);
    m->args(x->args());
    t = m;
  } else fatal_error("unrecognized op-assign operator in lowering");

  if (x->castResult() != NULL) t = new CastNode(t, x->castResult(), pos);
  assert(t->type()->typeIdent(x->type()));
  while (isCastNode(assignment_target)) assignment_target = assignment_target->opnd0();

  ExprNode *result;
  if (isExpressionStmtNode(x->parent())) {
    AssignNode *r = new AssignNode(assignment_target, t, pos);
    assert(r->type()->typeIdent(assignment_target->type()));
#if DEBUG_OPASSIGN
    cout << "r: ";
    r->pseudoprint(cout, 0);
    cout << endl;
#endif
    /* The call to AssignNode::lower() may operate better if t->_parent is set
       to an ExpressionStmtNode.  So create a placeholder ExpressionStmtNode just in case. 
       The placeholder will be discarded later. */
    ExpressionStmtNode *wrapper = new ExpressionStmtNode(r);
    llist<TreeNode *> *tstmts = NULL;
    TreeNode *tmp = wrapper->lower(decls, tstmts);
    assert(tstmts == NULL);
    if (isExpressionStmtNode(tmp)) {
      result = (ExprNode*)tmp->expr();
    } else if (isEmptyStmtNode(tmp)) { /* lowered away to nothing */
      result = new NullPntrNode(); /* dummy expression that will be discarded */
    } else {
      assert(isBlockNode(tmp));
      push(stmts, tmp);
      result = new NullPntrNode(); /* dummy expression that will be discarded */
    }
    /* NOT safe to delete wrapper - may end up as part of the BlockNode above */
  } else {
    /* The call to t->lower() may operate better if t->_parent is set
       to an AssignNode.  So create a placeholder AssignNode just in case. 
       The placeholder will be discarded later. */
    AssignNode *placeholder = new AssignNode(assignment_target, t, pos);
    t = t->lower(decls, stmts);
    if (!isVar(t))
      t = MakeTemporary(t, decls, stmts);
    result = CloneTree(t);
    delete placeholder;
    AssignNode *r = new AssignNode(assignment_target, t, pos);
    assert(r->type()->typeIdent(assignment_target->type()));
    TreeNode *assign = r->lower(decls, stmts);
    push(stmts, new ExpressionStmtNode(assign, pos));
  }

#if DEBUG_OPASSIGN
  cout << "to ";
  result->pseudoprint(cout, 0);
  cout << endl;
#endif

  return result;
}

ExprNode *BinaryArithAssignNode::lower(llist<TreeNode *> *&decls,
				       llist<TreeNode *> *&stmts)
{
  return opAssignNode_lower(this, decls, stmts);
}

ExprNode *MethodCallAssignNode::lower(llist<TreeNode *> *&decls,
				      llist<TreeNode *> *&stmts)
{
  return opAssignNode_lower(this, decls, stmts);
}

ExprNode *ShiftAssignNode::lower(llist<TreeNode *> *&decls,
				 llist<TreeNode *> *&stmts)
{
  return opAssignNode_lower(this, decls, stmts);
}

ExprNode *BitwiseAssignNode::lower(llist<TreeNode *> *&decls,
				   llist<TreeNode *> *&stmts)
{
  return opAssignNode_lower(this, decls, stmts);
}

// See transform_init().
TreeNode *FieldDeclNode::lower(llist<TreeNode *> *&decls,
			       llist<TreeNode *> *&stmts)
{
  return this;
}

ExprNode *IfExprNode::lower(llist<TreeNode *> *&decls,
			    llist<TreeNode *> *&stmts)
{
  const SourcePosn pos = position();
  TreeNode *etrue = thenOpnd(), *efalse = elseOpnd();
  TypeNode *T = etrue->type();
  ObjectNode *varNode;
  ExprNode *a;  

#if DEBUG_IFEXPRNODE
  cout << "Lowering a ? b : c\netrue = \n";
  etrue->print(cout, 0);
  cout << "\nefalse = \n";
  efalse->print(cout, 0);
  cout << "\n";
#endif

  // Create a variable that will contain the result;
  const string *str = intern(tempGenerator.next());
  TreeNode *name = new NameNode (TreeNode::omitted, str, (Decl *)NULL);
  TreeNode *varDecl =
    new VarDeclNode (false, T->addModifiers(Common::CompilerGenerated),
		     name, TreeNode::omitted);
  Decl *d = new LocalVarDecl(varDecl->simpName()->ident(), varDecl->dtype(),
			     varDecl, true);
  varDecl->simpName()->decl(d);

  TreeNode *atrue, *afalse; // Blocks that compute the result and store it

  varNode = new ObjectNode(new NameNode(TreeNode::omitted, str, d));
  varNode->type(T);
  a = new AssignNode(varNode, etrue, pos);
  a->type(T);
  atrue = stmt_to_lowered_block(new ExpressionStmtNode(a));

  varNode = new ObjectNode(new NameNode(TreeNode::omitted, str, d));
  varNode->type(T);
  a = new AssignNode(varNode, efalse, pos);
  a->type(T);
  afalse = stmt_to_lowered_block(new ExpressionStmtNode(a));
  
#if DEBUG_IFEXPRNODE
  cout << "\natrue = \n";
  atrue->print(cout, 0);
  cout << "\nafalse = \n";
  afalse->print(cout, 0);
  cout << "\n";
#endif

  TreeNode *cond = condition()->lower(decls, stmts);
  push(decls, varDecl);
  TreeNode *c = MakeTemporary(cond, decls, stmts);
  TreeNode *i = new IfStmtNode(c, atrue, afalse, pos);
  push(stmts, i);

#if DEBUG_IFEXPRNODE
  cout << "i = \n";
  i->print(cout, 0);
  cout << "\n";
#endif

  ObjectNode *result = new ObjectNode (new NameNode(TreeNode::omitted, str, d));
  result->type(T);
  return result;
}


/* If x is of the form A.arity() for a titanium type A then rewrite it to the
   appropriate int literal (don't bother checking whether A is null).
   This is valid because x has already been lowered, so we need not
   worry about side effects of A.  If this function returns x (i.e.,
   does not rewrite) then the call is done and the result is put in a
   temporary.  (See MethodCallNode::lower(), below.).  If
   this function does not return x then the method has been rewritten
   and the returned value is assumed to be a lowered AST representing
   the appropriate result.  
   if testonly, just return NULL if method needs a rewrite
*/
static ExprNode *arity_rewrite(MethodCallNode *x, bool testonly) {
  const TreeNode *m = x->method();
  Decl *d = m->simpName()->decl();
  if ((d->modifiers() & Common::Static) && (isOFAN(m)||isTypeFAN(m))) {
    const TypeNode *t = (isOFAN(m)?m->object()->type():m->ftype());
    if ((t->isTitaniumArrayType() || t->isTitaniumBuiltinType())
      && isNameNode(m->simpName())) {
      MethodDecl *d = static_cast< MethodDecl * >( m->simpName()->decl() );
      if (streq(d->name()->c_str(), "arity")) {
        #if DEBUG_LOWERING_OPTS
	  cout << "\nRewriting call to ti method arity()\n\n";
	  x->print(cout, 2);
	  cout << "\n\n";
        #endif
        if (testonly) return NULL;
	else return new PrimitiveLitNode(Literal((int32) t->tiArity()));
      }
    }
  }
  return x;
}

ExprNode *MethodCallNode::lower(llist<TreeNode *> *&decls,
				llist<TreeNode *> *&stmts)
{
  if (arity_rewrite(this,true)==NULL || !checkIF(false) ||
      isRewrittenRHSOpOverload() ||
      method()->simpName()->decl()->type()->returnType()->kind() !=
      Common::VoidKind) {
    if (isRewrittenRHSOpOverload()) {
      assert(args()->arity() == 2 && isNullOrCastOfNull(args()->child(1)));
      args()->child(0, args()->child(0)->lower(decls, stmts));
      method(method()->lower(decls, stmts));
      args()->child(1, new CastNode(method()->object()->deepClone(), args()->child(1)->type()));
      args((TreeListNode *) ProcessAllSubExpr(args(), decls, stmts));
      isRewrittenRHSOpOverload(false);
    } else {
      method(method()->lower(decls, stmts));
      args((TreeListNode *) ProcessAllSubExpr(args(), decls, stmts));
    }

    Decl *dcl = method()->simpName()->decl();
    if (dcl->type()->returnType()->kind() != Common::VoidKind) {
      ExprNode *newExpr;
      if ((newExpr = arity_rewrite(this, false)) != this)
	return newExpr;
      else
	return MakeTemporary(this, decls, stmts);
    }
  }
  return this;    
}

TreeNode *ThisConstructorCallNode::lower(llist<TreeNode *> *&decls, 
                                         llist<TreeNode *> *&stmts) {
  #if DEBUG_CONSTRUCTOR_CALLS
	  cout << "\nlowering ThisConstructorCallNode:\n";
    cout << "before:\n";
	  this->print(cout, 2);
  #endif

  // convert into a simple method call
  SourcePosn pos = position();
  MethodDecl *md = dynamic_cast<MethodDecl *>(decl()); 
  assert(md->category() & Decl::Constructor);
  ConstructorDeclNode *mdn = dynamic_cast<ConstructorDeclNode *>(md->source());

  ClassDecl *clsd = dynamic_cast<ClassDecl *>(md->container());
  assert(clsd->category() & Decl::Class);
  //ClassDeclNode *clsdn = dynamic_cast<ClassDeclNode *>(clsd->source());

  TypeNode *classTypeNameNode = clsd->asType();

  ExprNode *expression = NULL;
  bool isImmutable = clsd->asType()->isImmutable();

  // treat objects & immutables the same for now - 
  // handle parameter convention differences in codegen
  // transformed into a non-static method call on 'this'
  expression = new ObjectFieldAccessNode(new ThisNode(TreeNode::omitted, classTypeNameNode, currentThisFlags, pos), 
                                     mdn->simpName()->deepClone(), pos);
  expression = new MethodCallNode(expression, NULL, pos);
  expression->args(args());

  expression = expression->lower(decls, stmts);

  // immutable constructors don't take a this pointer
  // instead, they return the newly created object by value
  if (isImmutable) {
    expression->type(classTypeNameNode);
    expression = new AssignNode(new ThisNode(TreeNode::omitted, classTypeNameNode, None, pos), expression, pos);
    expression->type(classTypeNameNode);
    }

  TreeNode *result = new ExpressionStmtNode(expression, pos);


  #if DEBUG_CONSTRUCTOR_CALLS
	  cout << "\nafter:\n";
	  result->print(cout, 2);
	  cout << "\n\n";
  #endif

  return result;
  }

TreeNode *SuperConstructorCallNode::lower(llist<TreeNode *> *&decls, 
					  llist<TreeNode *> *&stmts) {

  #if DEBUG_CONSTRUCTOR_CALLS
	  cout << "\nlowering SuperConstructorCallNode:\n";
    cout << "before:\n";
	  this->print(cout, 2);
  #endif

  // convert into a simple method call
  // note we also do object field initialization at super constructor call time
  SourcePosn pos = position();

  // first, find the ClassDeclNode for the class making this call
#if 0
  // this doesn't work during lowering
  ClassDeclNode *clsdn = NULL;
  {
    TreeNode *temp = this;
    while (!isClassDeclNode(temp)) temp = temp->parent();
    clsdn = dynamic_cast<ClassDeclNode *>(temp);
    }
#else
  // this only works because we never inline before lowering
  assert(currentClassDeclNode != NULL);
  ClassDeclNode *clsdn = currentClassDeclNode;
#endif

  assert(!(clsdn->flags() & Common::Immutable)); // immutables can't call super()
  TypeNode *classTypeNameNode = clsdn->decl()->asType();
  TreeNode *thisNode = new ThisNode(TreeNode::omitted, classTypeNameNode, currentThisFlags, pos);

  if (clsdn->decl() == ObjectDecl) { // java.lang.Object only needs field init
    return instanceInitializerBlock(clsdn);
    }

  MethodDecl *md = dynamic_cast<MethodDecl *>(decl()); 
  assert(md->category() & Decl::Constructor);
  ConstructorDeclNode *mdn = dynamic_cast<ConstructorDeclNode *>(md->source());
  ClassDecl *superclsd = dynamic_cast<ClassDecl *>(md->container());
  assert(superclsd->category() & Decl::Class);

  TreeNode *result = NULL;
  // transformed into a non-static method call on 'this' (gets casted by code gen)
  result = new ObjectFieldAccessNode(thisNode, mdn->simpName()->deepClone(), pos);
  result = new MethodCallNode(result, NULL, pos);
  result->args(args());
  result = new ExpressionStmtNode(result, pos);

  result = stmt_to_lowered_block(result);
  
  llist<TreeNode*>* l = NULL;
    // The rules for chaining one constructor onto another
    // constructor for the same class ultimately mean that
    // only a subset of "terminal" constructors will call
    // the superclass constructor.  The same subset can also
    // bear responsibility for intializing instance fields
    // that were declared with initializer expressions 
  push(l, instanceInitializerBlock(clsdn)); // do field init after super call (note push reverses order)
  push(l, result);
  result = new BlockNode(l, NULL, pos);

  #if DEBUG_CONSTRUCTOR_CALLS
	  cout << "\nafter:\n";
	  result->print(cout, 2);
	  cout << "\n\n";
  #endif

  return result;
  }

ExprNode *AllocateNode::lower(llist<TreeNode *> *&decls,
			      llist<TreeNode *> *&stmts)
{
  #if DEBUG_CONSTRUCTOR_CALLS
	  cout << "\nlowering AllocateNode:\n";
    cout << "before:\n";
	  this->print(cout, 2);
  #endif

  SourcePosn pos = position();
  TypeNode *t = dtype();
  assert(!t->isTitaniumArrayType());
  ClassDecl *clsd = dynamic_cast< ClassDecl * >( t->decl() );
  assert( clsd->category() & (Decl::Class | Decl::Interface) );

  bool allocOnly = t->isPointType() || t->isRectDomainType(); // handle these two specially

  ExprNode *result;
  ObjectNode *space = NULL;
  
  // do space allocation
  if (t->isImmutable()) {
    TreeNode *d, *s;
    space = MakeTemporary(this, d, s);
    push(decls, d); // we just need the decl, not the assign - this object will never actually be used
    }
  else {
    TreeNode * const heap = region()->lower(decls, stmts);
    ExprNode * const alloc = new AllocateSpaceNode(heap, dtype());
    space = MakeTemporary(alloc, decls, stmts);
  }

  if (allocOnly)
    result = space;
  else {
    // convert into a simple method call to constructor
    MethodDecl * const md = dynamic_cast<MethodDecl *>(decl()); 
    assert(md->category() & Decl::Constructor);
    ConstructorDeclNode *mdn = dynamic_cast<ConstructorDeclNode *>(md->source());

    // constructor transformed into a non-static method call on the newly allocated object
    ExprNode * const access = new ObjectFieldAccessNode(space, mdn->simpName()->deepClone(), pos);
    ExprNode *call = new MethodCallNode(access, NULL, pos);
    call->args(args());
    call = call->lower(decls, stmts);

    if (t->isImmutable()) { 
      // constructors don't have a correct return type right now, so fake it
      call->type(t);
      result = call;
      }
    else {
      // use the properly typed space we already allocated
      TreeNode *init = new ExpressionStmtNode(call, pos);
      push(stmts, init);
      result = space->deepClone();
    }
  }
  
  #if DEBUG_CONSTRUCTOR_CALLS
	  cout << "\nafter:\n";
	  result->print(cout, 2);
	  cout << "\n\n";
  #endif

  return result;
  }

ExprNode *AllocateSpaceNode::lower(llist<TreeNode *> *&decls,
				   llist<TreeNode *> *&stmts)
{
    return ProcessExpr(this, decls, stmts);
}


ExprNode *IncrDecrNode::lower(llist<TreeNode *> *&decls,
			      llist<TreeNode *> *&stmts)
{
    ExprNode *t = ((ExprNode *) opnd0())->lower(decls, stmts);
    ExprNode *old = MakeTemporary(t, decls, stmts);

    TreeNode *oneNode = new PrimitiveLitNode ((int32) 1);
    ExprNode *assign;
    // Do the increment/decrement operation
    if (isPostIncrNode(this) || isPreIncrNode(this))
	assign = new AssignNode(CloneTree(t), new PlusNode(old, oneNode));
    else
	assign = new AssignNode(CloneTree(t), new MinusNode(old, oneNode));
    assign->type(t->type());

    // If the order does not matter...
    if (isExpressionStmtNode(parent()))
	return assign;

    // The order matters.  So store the assignment operation.
    push(stmts, new ExpressionStmtNode(assign));

    // Return the old or the new value
    if (isPostIncrNode(this) || isPostDecrNode(this))
	return CloneTree(old);
    else
	return CloneTree(t);
}

static CodeLiteralExprNode *nodeMYPROC()
{
  CodeLiteralExprNode *m = new CodeLiteralExprNode("MYPROC");
  m->type(theIntType);
  return m;
}

/* Return an ExprNode that compares p to MYPROC. */
static EQNode *isMYPROC(TreeNode *p)
{
  EQNode *r = new EQNode(p, nodeMYPROC());
  r->type(theBoolType);
  return r;
}

ExprNode *BroadcastNode::lower(llist<TreeNode *> *&decls,
			       llist<TreeNode *> *&stmts)
{
  const SourcePosn pos = position();
  TreeNode *d1, *s1, *d2, *s2;
  TreeNode *p = MakeTemporary(proc()->lower(decls, stmts),
			      d1, s1);
  llist<TreeNode *> *substmts = NULL;
  llist<TreeNode *> *subdecls = NULL;
  TreeNode *e =
    MakeTemporary(expr()->lower(subdecls, substmts),
		  d2, s2);

  s2 = new BlockNode(cons(s2), NULL, pos);
  s2 = AddBlockStmtsAtBegin((BlockNode *) s2, substmts);
  s2 = AddBlockStmtsAtBegin((BlockNode *) s2, subdecls);

  TreeNode *ifMyBcastComputeExpr =
    new IfStmtNode(isMYPROC(CloneTree(p)), s2, TreeNode::omitted, pos);

  decls = cons(d1, cons(d2, decls));
  stmts = cons(ifMyBcastComputeExpr, cons(s1, stmts));

  ExprNode *result = new IBroadcastNode(e, p, pos);
  result->type(type());
  return result;
}

ExprNode *AllocateArrayNode::lower(llist<TreeNode *> *&decls,
				   llist<TreeNode *> *&stmts)
{
  if (!initExpr()->absent())
    return ProcessExpr(initExpr(), decls, stmts);
  return ProcessExpr(this, decls, stmts);
}

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

extern TreeNode *transform_init(TreeNode *t);

BlockNode *EncapsulateInits(vector<TreeNode *> inits)
{
    vector<TreeNode *>::iterator b = inits.begin();
    vector<TreeNode *>::iterator e = inits.end();
    llist<TreeNode *> *t = NULL;

    // AK - run any default initializers first, so that they don't undo the effects
    // of static/instance initializers
    while (b < e) {
      if (isFieldDeclNode(*b) && 
	  ((*b)->initExpr()->absent() || 
	   ((FieldDeclNode *) *b)->compilerGeneratedInitExpr()))
	t = cons(transform_init(*b++), t);
      else
	b++;
    }
    b = inits.begin();
    while (b < e) {
      if (!isFieldDeclNode(*b) || 
	  !((*b)->initExpr()->absent() ||
	    ((FieldDeclNode *) *b)->compilerGeneratedInitExpr()))
	t = cons(transform_init(*b++), t);
      else
	b++;
    }
    t = dreverse(t);
    return new BlockNode(t, NULL);
}

TreeNode *transform_init(TreeNode *t)
{ // lower field initializers
  if (isStaticInitNode(t)) return stmt_to_lowered_block(t);
  if (isInstanceInitNode(t)) 
    return stmt_to_lowered_block(deepCloneWithCrossTreeFixup(t->block()));

  if (isFieldDeclNode(t)) {
    if (t->initExpr()->absent()) {
      if (t->dtype()->isImmutable()) 
        setImmutableDefaultInitExpr(t);
      else {
        assert(t->decl()->modifiers() & Common::Static || t->decl()->container()->asType()->isImmutable());
        // DOB: we never need or use a default initializer for non-immutable instance fields of non-immutable types
        // ti_malloc already gives us cleared memory, so Objects already contain zeroed defaults for primitive and reference types
	// AK: this also means we don't need a special case for nested class fields that need to be initialized
	// before the super constructor call
        t->initExpr(defaultInitializer(t->dtype(), t->position()));
      }
      // Extrafold constant folding uses the user-provided initializers for final instance fields
      // as a signal that the initializer is safe to constant-fold, so we need to flag the
      // default initializer as compiler-generated to prevent the bogus zero value 
      // (which is not the final value) from getting propagated to field uses
      ((FieldDeclNode*)t)->compilerGeneratedInitExpr(true);
    }
    TreeNode* initExpr = t->initExpr()->deepClone(); 
    
	  TypeNode *cl = t->decl()->container()->asType();
	  TreeNode *sname = new NameNode(TreeNode::omitted,
				         t->decl()->name(),
				         t->decl());
	  Common::Modifiers l = cl->isReference() ? Common::Local : Common::None;
	  TreeNode *fld = new ObjectFieldAccessNode(new ThisNode(TreeNode::omitted, cl, l, t->position()), sname,
						    t->position());
	  ExprNode *a = new AssignNode(fld, initExpr,
				       t->position());
	  a->type(initExpr->type());
    TreeNode *result = stmt_to_lowered_block(new ExpressionStmtNode(a));
    // do NOT clear field initializer - Extrafold constant folding still uses it post-lowering for final fields
    return result;
  } else {
    // nothing else should get passed to this function
    abort();
    return 0;
  }
}

TreeNode *instanceInitializerBlock(ClassDeclNode *cdn) {
  // scan the given class decl for instance initializers 
  // (i.e. non-static fields with initializers and instance initializer nodes)
  // and return a lowered block that performs the required initialization 

 static map<ClassDeclNode *, TreeNode *> classInstanceInitializer;
 TreeNode *&result = classInstanceInitializer[cdn];

 if (result == NULL) {
  // start by building a list non-static fields in this class
  vector< TreeNode * > instanceinits;
  foriter (member, cdn->members()->allChildren(), TreeNode::ChildIter) {
	  TreeNode * const node = *member;
	  if (isFieldDeclNode(node)) {
	    const FieldDeclNode * const fieldDecl = static_cast< const FieldDeclNode * >( node );
	    if (!(fieldDecl->decl()->modifiers() & Common::Static) && // it's a non-static field
               (!fieldDecl->initExpr()->absent() || // user-provided initializer to encapsulate
                (node->dtype()->isImmutable() && 
                !node->dtype()->isTitaniumArrayType()) || // or non-array immutable field type (need to run no-arg constructor)
                node->decl()->container()->asType()->isImmutable())) { // or immutable enclosing class (unboxed, so not zeroed by allocator)
      	      instanceinits.push_back( node );
            }
            // force instantiation of the headers required to support field types
            // (otherwise get missing headers for uninitialized fields with types not mentioned elsewhere)
            const CtType & rawType = node->dtype()->cType();
            if (!node->dtype()->isImmutable())
              ctBox( rawType, true );             
          } else if (isInstanceInitNode(node)) instanceinits.push_back( node );
    }
  result = EncapsulateInits(instanceinits); 
  }
 return deepCloneWithCrossTreeFixup(result);
}


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

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

TreeListNode * TreeListNode::collapseTrivialBlocks()
{
  TreeNode::collapseTrivialBlocks();  
  return this;
}

TreeNode *TemplateDeclNode::collapseTrivialBlocks()
{
  return this;
}

TreeNode * MethodDeclNode::collapseTrivialBlocks()
{
  if (!body()->absent()) {
    /* Body should be a block, and keep it that way. */
    assert(isBlockNode(body()));
    body()->stmts(body()->stmts()->collapseTrivialBlocks());
  }
  return this;
}

TreeNode * ConstructorDeclNode::collapseTrivialBlocks()
{
  if (!body()->absent()) {
    /* Body should be a block, and keep it that way. */
    assert(isBlockNode(body()));
    body()->stmts(body()->stmts()->collapseTrivialBlocks());
  }
  // do the same for the constructor call block
  if (!constructorCall()->absent() && isBlockNode(constructorCall())) {
    constructorCall()->stmts( static_cast<TreeListNode*>(constructorCall()->stmts()->collapseTrivialBlocks()));
    }
  return this;
}

TreeNode * StaticInitNode::collapseTrivialBlocks()
{
  /* Body should be a block, and keep it that way. */
  assert(!block()->absent());
  assert(isBlockNode(block()));
  block()->stmts(block()->stmts()->collapseTrivialBlocks());
  return this;
}

TreeNode * InstanceInitNode::collapseTrivialBlocks()
{
  /* Body should be a block, and keep it that way. */
  assert(!block()->absent());
  assert(isBlockNode(block()));
  block()->stmts(block()->stmts()->collapseTrivialBlocks());
  return this;
}

TreeNode * SynchronizedNode::collapseTrivialBlocks()
{
  if (!stmt()->absent()) {
    /* Body should be a block, and keep it that way. */
    assert(isBlockNode(stmt()));
    stmt()->stmts(stmt()->stmts()->collapseTrivialBlocks());
  }
  return this;
}

TreeNode * IfStmtNode::collapseTrivialBlocks()
{
  if (isTrue(condition()))
    return thenPart()->collapseTrivialBlocks();
  if (isFalse(condition())) {
    if (elsePart()->absent()) return new EmptyStmtNode(position());
    else return elsePart()->collapseTrivialBlocks();
  }
  TreeNode *e, *t;
  thenPart(t = thenPart()->collapseTrivialBlocks());
  elsePart(e = elsePart()->collapseTrivialBlocks());
  if (!e->absent() && isNOP(e))
    elsePart(e = TreeNode::omitted);
  if (e->absent() && isNOP(t))
    // If neither branch of the statement does anything then remove it---
    // the condition can't have side-effects.
    return new EmptyStmtNode(position());
  return this;
}

TreeNode * BlockNode::collapseTrivialBlocks()
{
  int a = stmts()->arity();
  for (int i = 0; i < a; i++)
    stmts()->child(i, stmts()->child(i)->collapseTrivialBlocks());
  vector<int> useful;
  for (int i = 0; i < a; i++)
    if (!stmts()->child(i)->absent() && !isEmptyStmtNode(stmts()->child(i)))
      useful.push_back(i);
  int new_size = (int) useful.size();
  switch (new_size) {
  case 0: return new EmptyStmtNode(position());
  case 1: return stmts()->child(useful.front());
  default:
    if (a == new_size)
      return this;
    llist<TreeNode *> *l = NULL;
    for (int i = new_size; --i >= 0; )
      push(l, stmts()->child(useful[i]));
    delete this;
    return new BlockNode(l, NULL, l->front()->position());
  }
}