#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"

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.
*/


// 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) || 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;
}

static NameNode *DeclTemporary(TypeNode *t, TreeNode *&declStmt,
			       SourcePosn p, const string *tempname = NULL);
static NameNode *DeclTemporary(TypeNode *t, TreeNode *&declStmt,
			       SourcePosn p, const string *tempname)
{
  const string *str =
    intern((tempname == NULL) ? tempGenerator.next() : *tempname);
  TreeNode *name = new NameNode (TreeNode::omitted, str, (Decl *)NULL);
  TreeNode *varDecl =
    new VarDeclNode (false, t->addModifiers(Common::CompilerGenerated),
		     name, TreeNode::omitted, p);
  Decl *d = new LocalVarDecl(varDecl->simpName()->ident(),
			     varDecl->dtype(), varDecl, true);
  varDecl->simpName()->decl(d);
  declStmt = varDecl;
  
  return new NameNode(TreeNode::omitted, str, d, p);
}

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 assert(0);
}

// 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), 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 - we need to grab that field
	    TypeNode *cl = immutableDeclNode->decl()->container()->asType();
	    result = new ObjectFieldAccessNode(new ThisNode(cl, currentThisFlags, pos), name, pos);
      }
    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()) {
    assert(0); // now obsolete - 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
    assert(0);
  result->type(t);
  return result;
}

/* 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) || isStaticInitNode(t))
    t = new BlockNode(cons(t));
  else if (t->absent())
    return new BlockNode(NULL);
  else {
    if (!t->isExprNode()) {
      cerr << "****\nInternal error lowering " << pseudocode(t) << endl;
      t->print(cerr, 3);
      cerr << "\n****\n";
      // assert(0);
    }
    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, oldJump->position() );
    llist< TreeNode * > *sequence = 0;
    push( sequence, newJump );
    push( sequence, cleanupBlock );
    return new BlockNode( sequence, 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;
}


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


TreeNode *TreeNode::lower(llist<TreeNode *> *&decls,
			  llist<TreeNode *> *&stmts)
{
  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)
{
  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));
  if (stmts == NULL)
    return this;
  else {
    TreeNode *result = new BlockNode(extend(reverse(stmts),
					    cons((TreeNode *) this)));
    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(), 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));
  AddStmts(this, stmts);
  stmts = NULL;
  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;
}


static TreeListNode *empty_treelist(SourcePosn p = NoSourcePosition);

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

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));
  body = body->lower(decls, stmts);
  if (!isBlockNode(body))
    body = new BlockNode(cons(body));
  body = AddBlockStmtsAtBegin((BlockNode *)body, stmts);
  body = AddBlockStmtsAtBegin((BlockNode *)body, decls);
  decls = NULL; stmts = NULL;
  return body;
}

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 );
  
  if (constructorCall() == TreeNode::omitted) {
    // this is the bottom-level immutable constructor (or java.lang.Object)
    // perform instance field initialization here
    ClassDeclNode *cdn = dynamic_cast<ClassDeclNode *>(decl()->container()->source());
    //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;
  }
  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 - 1; i >= 0; i--) {
      if (isVarDeclNode(s->child(i))) {
	// cout << "Child " << i << " is a var decl" << endl;
	if (s->child(i)->initExpr()->absent() && 
	    !(s->child(i)->dtype()->modifiers() &
	      Common::CompilerGenerated)) {
	  // don't bother to initialize temps
	  if (s->child(i)->dtype()->isImmutable()) 
	    setImmutableDefaultInitExpr(s->child(i));
	  else 
	    s->child(i)->
	      initExpr(defaultInitializer(s->child(i)->dtype(),
					  s->child(i)->position()));
	  // 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 - 1; i >= 0; i--) {
      if (isVarDeclNode(s->child(i))) {
	// cout << "Child " << i << " is a var decl" << endl;
      } 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())));

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

  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)
{
  // This function is essentially the same as the following function.
  SourcePosn p = n->position();
  TreeNode *conLabel = NAKEDLABEL(), *afterLabel = NAKEDLABEL(), *test;
  test = new IfStmtNode(new NotNode(n->test(), n->test()->position()),
			GOTO(afterLabel), TreeNode::omitted, p);
  // loop body is test followed by n->stmt() followed by conLabel
  llist<TreeNode *> *t = cons(test, cons(n->stmt(), cons(conLabel)));
  TreeNode *loopBody = new BlockNode(t);
  replaceBreakContinue(loopBody, n, afterLabel, conLabel);
  TreeNode *f = new ForNode(NULL, TreeNode::omitted, NULL, loopBody, p);
  return new BlockNode(cons(f, cons(afterLabel)));
}

// 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)
{
  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);
  replaceBreakContinue(loopBody, n, afterLabel, conLabel);
  TreeNode *f = new ForNode(NULL, TreeNode::omitted, NULL, loopBody, p);
  return new BlockNode(cons(f, cons(afterLabel)));
}

/* 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()), 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)));
  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)), 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))));
#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)));

  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)));

  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() - 1; c >= 0; c--)
      t = cons(updStmts->child(c), t);
    //   1st in loop body: stmt()
    t = cons(stmt(), cons(updateLabel, t));
    TreeNode *loopBody = new BlockNode(t);
    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)));
    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)),
				     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() - 1; c >= 0; c--)
      t = cons(initStmts->child(c), t);
    result = new BlockNode(t);

#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() - 1; c >= 0; c--)
    updList = cons(updStmts->child(c), updList);
  updList = cons(stmt(), cons(updateLabel, updList));
  TreeNode *loopBody = new BlockNode(updList);
  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() - 1; c >= 0; c--)
    t = cons(initStmts->child(c), t);
    
  BlockNode *b = new BlockNode(t);
#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))));
}

/////////////////////////////////////////////////////////////////////////////
// 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)
{
  if (opnd0()->type()->typeIdent(dtype()))
    return newBoolLit(true, position());
  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;
  else {
    ExprNode *t = static_cast<ExprNode *>(CloneTree(opnd1()));
    push(stmts, new ExpressionStmtNode(this));
    return t;
  }
}

/* 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);
  TreeNode *lhs =
    (MC ? x->method()->object() : x->child(0))->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) {
    t = new MethodCallNode(x->method(), NULL, pos);
    t->method()->object(lhs);
    t->child(1, rhs);
  }
  else assert(0);

  t->type(x->type());

  ExprNode *result;
  if (isExpressionStmtNode(x->parent())) {
    AssignNode *r = new AssignNode(assignment_target, t, pos);
    r->type(assignment_target->type());
#if DEBUG_OPASSIGN
    cout << "r: ";
    r->pseudoprint(cout, 0);
    cout << endl;
#endif
    result = r->lower(decls, stmts);
  } 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);
    r->type(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)) {
    const TypeNode *t = m->object()->type();
    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) ||
      method()->simpName()->decl()->type()->returnType()->kind() !=
      Common::VoidKind) {
    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(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(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(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, 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), 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)
{
  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;

    while (b < e) {
	t = cons(transform_init(*b++), t);
    }
    t = dreverse(t);
    return new BlockNode(t);
}

TreeNode *transform_init(TreeNode *t)
{ // lower field initializers
  if (isStaticInitNode(t))
	  return stmt_to_lowered_block(t);

  if (isFieldDeclNode(t)) {
    if (t->initExpr()->absent()) {
      if (t->dtype()->isImmutable()) 
        setImmutableDefaultInitExpr(t);
      else 
        t->initExpr(defaultInitializer(t->dtype(), t->position()));
      }
    // need our own copy because we may call this several times for the same field
    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(cl, l, t->position()), sname,
						    t->position());
	  ExprNode *a = new AssignNode(fld, initExpr,
				       t->position());
	  a->type(initExpr->type());
	  return stmt_to_lowered_block(new ExpressionStmtNode(a));
  } else {
    // nothing else should get passwd to this function
    assert(0);
    return 0;
  }
}

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

  // start by building a list non-static fields in this class
  vector< TreeNode * > fieldinits;
  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
      	fieldinits.push_back( node );
      }
    }
  return EncapsulateInits(fieldinits); 
  }


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

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()
{
  if (!block()->absent()) {
    /* Body should be a block, and keep it that way. */
    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()))
    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, l->front()->position());
  }
}