#include <functional>

#include "UniqueId.h"
#include "hash_maps.h"
#include "AST.h"
#include "optimize.h"
#include "code-util.h"
#include "cfg.h"
#include "lower.h" // for AddStmts

// Common sub-expression elimination
// Author: Johnathon Jamison <jjamison@cs.berkeley.edu>, 5-2003

static int numLocalReplacements = 0;

// keep statistics
static int stats_num_times_called = 0;
static int stats_numCSE = 0;
static int stats_numReplacements = 0;

static void print_stats() {
  cout << "Common Sub-expression Elimination Statistics:" << endl;
  cout << " Total times called:                    "
       << stats_num_times_called << endl;
  cout << " Number of CSE:                         "
       << stats_numCSE << endl;
  cout << " Number of replacements made:           "
       << stats_numReplacements << endl;
  cout << endl;
}

struct OperandKey {
  union {
    Decl *variable_operand;
    const string *literal_operand;
  } data;
  OperandKey() { data.variable_operand = NULL; }
  OperandKey(Decl *op) { data.variable_operand = op; }
  OperandKey(const string *op) { data.literal_operand = op; }
  operator void*() const { return (void*)data.variable_operand; }
};
struct ExprKey {
  OperandKey opd1;
  const string *op;
  OperandKey opd2;
  ExprKey(OperandKey o1, const string *o, OperandKey o2) :
    opd1(o1), op(o), opd2(o2) {}
  bool operator<(const ExprKey &other) const {
    if ((void*)opd1 < (void*)other.opd1) {
      return true;
    } else if ((void*)opd1 > (void*)other.opd1) {
      return false;
    } else if (op < other.op) {
      return true;
    } else if (op > other.op) {
      return false;
    } else if ((void*)opd2 < (void*)other.opd2) {
      return true;
    } else if ((void*)opd2 > (void*)other.opd2) {
      return false;
    } else {
      return false;
    }
  }
};
struct ExprValue {
  TreeNode *loc;
  TreeNode *declaring_block;
  TreeNode *declaration;
  ObjectNode *temp;
  ExprValue(TreeNode *l) :
    loc(l), declaring_block(NULL), declaration(NULL), temp(NULL) {}
};
typedef HASH_MAP(ExprKey, ExprValue) ExprHashTable;

static OperandKey getName(TreeNode *t) {
  assert(t != NULL);
  assert((isObjectNode(t) && (t->name() != NULL) && isNameNode(t->name())) ||
	 isThisNode(t) ||
	 isPrimitiveLitNode(t) ||
	 isNullPntrNode(t));
  if (isObjectNode(t) && isNameNode(t->name())) {
    assert(t->name() != NULL);
    assert(t->name()->ident() != NULL);
    return OperandKey(t->name()->decl());
  } else if (isThisNode(t)) {
    return OperandKey(t->theClass()->decl());
  } if (isPrimitiveLitNode(t)) {
    return OperandKey(intern(t->literal().asString()));
  } else {
    assert(isNullPntrNode(t));
    return OperandKey(intern("null"));
  }
}

static ExprKey getExprKey(TreeNode *baby_expr) {
  assert(baby_expr != NULL);
  assert(baby_expr->isExprNode());
  if (/*is_field(baby_expr)*/false) {
    // 2a. var.field
    fatal_error("");
  } else if (/*is_imm_field(baby_expr)*/false) {
    // 2b. var.i0.i1....ik.field	 (where i0, ..., ik are immutable)
    fatal_error("");
  } else if (isUnaryArithNode(baby_expr) || isNotNode(baby_expr) ||
	     isComplementNode(baby_expr)) {
    // 3a. op var			 (UnaryArithNode, NotNode, ComplementNode)
    OperandKey opnd0 = getName(baby_expr->opnd0());
    const string *opr = intern(baby_expr->oper_name());
    return ExprKey(opnd0, opr, OperandKey());
  } else if (isBinaryArithNode(baby_expr) || isShiftNode(baby_expr) ||
	     isEqualityNode(baby_expr) || isRelationNode(baby_expr) ||
	     isBitwiseNode(baby_expr)) {
    // 3b. var op var			 (BinaryArithNode, ShiftNode,
    // 				  EqualityNode, RelationNode,
    // 				  BitwiseNode, but not LogCondNode)
    OperandKey opnd0 = getName(baby_expr->opnd0());
    const string *opr = intern(baby_expr->oper_name());
    OperandKey opnd1 = getName(baby_expr->opnd1());
    // Now we want to canonicalize
    // to catch textually different but equivalent statements
    if (isMultNode(baby_expr) || isPlusNode(baby_expr) ||
	isEQNode(baby_expr) || isNENode(baby_expr) ||
	isBitAndNode(baby_expr) || isBitOrNode(baby_expr) ||
	isBitXorNode(baby_expr)) {
      if (opnd0 > opnd1) {
	OperandKey tmp = opnd1;
	opnd1 = opnd0;
	opnd0 = tmp;
      }
    } else if (isLTNode(baby_expr)) {
      OperandKey tmp = opnd1;
      opnd1 = opnd0;
      opnd0 = tmp;
      opr = intern("GTNode");
    } else if (isLENode(baby_expr)) {
      OperandKey tmp = opnd1;
      opnd1 = opnd0;
      opnd0 = tmp;
      opr = intern("GENode");
    }
    return ExprKey(opnd0, opr, opnd1);
  } else if (/*is(array access)(baby_expr)*/false) {
    // 4.  var[var]			 (array access)
    fatal_error("");
  } else if (isCastNode(baby_expr)) {
    // 5.  (type) var			 (CastNode)
    fatal_error("");
  } else if (isInstanceOfNode(baby_expr)) {
    // 6.  var instanceof type		 (InstanceOfNode)
    fatal_error("");
  } else if (isPointNode(baby_expr)) {
    // 8.  [var, ..., var]              (PointNode)
    fatal_error("");
  } else if (isDomainNode(baby_expr)) {
    // 9.  [var : var, var : var, ...], and variants  (DomainNode)
    fatal_error("");
  } else {
    fatal_error("");
  } // if baby_expr
  return ExprKey(OperandKey(), NULL, OperandKey());
}

static UniqueId tempGenerator("cse");

static ObjectNode *MakeCSETemporary(TreeNode *expr, TreeNode *&declStmt,
				    TreeNode *&assnStmt) {
  SourcePosn pos = expr->position();
  const string *str = intern(tempGenerator.next());
  TreeNode *name = new NameNode (TreeNode::omitted, str, (Decl *)NULL, pos);
  TreeNode *varDecl =
    new VarDeclNode(false,
		    expr->type()->addModifiers(Common::CompilerGenerated),
		    name, TreeNode::omitted, pos);
  Decl *d = new LocalVarDecl(str, varDecl->dtype(), varDecl, true);
  name->decl(d);
  declStmt = varDecl;
  
  ObjectNode *varNode =
    new ObjectNode (new NameNode(TreeNode::omitted, str, d, pos), pos);
  varNode->type(expr->type());
  assnStmt = new ExpressionStmtNode(new AssignNode(varNode, expr, pos), pos);

  return varNode;
}

#if 0
typedef HASH_MAP(TreeNode*, TreeNode*) NodeSet;
static TreeNode *smallest_containing_block_of(TreeNode *block1,
					      TreeNode *block2) {
  assert(isBlockNode(block1));
  assert(isBlockNode(block2));
  NodeSet blocks;
  for (TreeNode *node = block1;
       !isMethodDeclNode(node) && !isConstructorDeclNode(node);
       node = node->parent()) {
    if (isBlockNode(node)) {
      blocks.insert(make_pair(node, node));
    }
  }
  for (TreeNode *node = block2;
       !isMethodDeclNode(node) && !isConstructorDeclNode(node);
       node = node->parent()) {
    if (blocks.find(node) != blocks.end()) {
      return node;
    }
  }
  fatal_error("");
  return NULL;
}
#endif

typedef HASH_MAP(const string*, const string*) VariableSet;
static void recursively_add_uses(VariableSet &variables_used,
				 TreeNode *current_node) {
  for(llist<TreeNode *>* uses = current_node->getUses();
      uses != NULL;
      uses = uses->tail()) {
    TreeNode *use_object = uses->front();
    assert(use_object != NULL);
    assert(isObjectNode(use_object));
    TreeNode *use_var = use_object->name();
    assert(use_var != NULL);
    assert(isNameNode(use_var));
    const string *var_name = use_var->ident();
    assert(var_name != NULL);
    variables_used.insert(make_pair(var_name, var_name));
  }

  for (int i=0; i < current_node->arity(); i++) {
    recursively_add_uses(variables_used, current_node->child(i));
  }
}

#if 0
static void insert_declaration(ExprHashTable::iterator item) {
  if (item->second.temp != NULL) {
    assert(item->second.declaration != NULL);
    if (DEBUG_SUBEXPR) {
      cout << "Inserting declaration: ";
      item->second.declaration->pseudoprint(cout);
      cout << endl;
    }
    TreeNode *decl_block = item->second.declaring_block;
    assert(decl_block != NULL);
    TreeNode *statments = decl_block->stmts();
    llist<TreeNode*>* new_stmts = NULL;
    llist<TreeNode*> **curr_stmt_pos = &new_stmts;
    for (TreeNode::ChildIter statement_iter = statments->allChildren();
	 !statement_iter.isDone();
	 statement_iter.next()) {
      *curr_stmt_pos = cons(*statement_iter);
      curr_stmt_pos = &(*curr_stmt_pos)->tail();
    }
    new_stmts = cons(item->second.declaration, new_stmts);
    item->second.declaring_block->stmts(new TreeListNode(new_stmts));
    if (DEBUG_SUBEXPR) {
      cout << "Block after insertion is now: ";
      item->second.declaring_block->pseudoprint(cout);
      cout << endl;
    }
    stats_numCSE++;
  }
}

// private helper for doCommonSubexprElim
// performs elimination of common subexpressions on stmts in this bblock 
static void eliminateSubexprsBblock(Bblock *b) {
  assert(b != NULL);
  if (DEBUG_SUBEXPR) {
    cout << "Doing local elimination on basic block #" << b->number << endl;
  }

  // Traverse the CFG list for this block
  ExprHashTable available_subexprs;
  for (ListIterator<CfgNode *> cfgIt = b->cfgIter();
       !cfgIt.isDone();
       cfgIt.next()) {
    CfgNode *cfg = *cfgIt;
    assert(cfg != NULL);
    TreeNode *current_node = cfg->astNode();
    assert(current_node != NULL);
    // if is a potential eliminator
    if (isAssignNode(current_node) && !inDummyNode(current_node)) {
      TreeNode *&current_assignment = current_node;
      TreeNode *lhs = current_assignment->opnd0();
      assert(lhs != NULL);
      TreeNode *rhs = current_assignment->opnd1();
      assert(rhs != NULL);
      TreeNode *current_assign_stmt = current_assignment->parent();
      assert(isExpressionStmtNode(current_assign_stmt));
      if (/*is_field(rhs)*/false) {
	// 2a. var.field
      } else if (/*is_imm_field(rhs)*/false) {
	// 2b. var.i0.i1....ik.field	 (where i0, ..., ik are immutable)
      } else if (isUnaryArithNode(rhs) || isNotNode(rhs) ||
		 isComplementNode(rhs) ||
	// 3a. op var			 (UnaryArithNode, NotNode, ComplementNode)
		 isBinaryArithNode(rhs) || isShiftNode(rhs) ||
		 isEqualityNode(rhs) || isRelationNode(rhs) ||
		 isBitwiseNode(rhs)) {
	// 3b. var op var			 (BinaryArithNode, ShiftNode,
	// 				  EqualityNode, RelationNode,
	// 				  BitwiseNode, but not LogCondNode)
	if (DEBUG_SUBEXPR) {
	  cout << "A rhs eligable for eliminating others:";
	  rhs->pseudoprint(cout);
	  cout << endl;
	}
	ExprKey key = getExprKey(rhs);
	ExprHashTable::iterator item = available_subexprs.find(key);
	if (item == available_subexprs.end()) {
	  ExprValue value(current_assignment);
	  available_subexprs.insert(make_pair(key, value));
	  if (DEBUG_SUBEXPR) cout << "Saved " << key.opd1 << ' '
				  << *key.op << ' ' << key.opd2
				  << " for possible future use" << endl;
	} else {
	  if (DEBUG_SUBEXPR) cout << "Previously saved for reuse" << endl;
	  TreeNode *original_assignment = item->second.loc;
	  assert(isAssignNode(original_assignment));
	  if (item->second.temp == NULL) {
	    TreeNode *original_statement = original_assignment->parent();
	    assert(isExpressionStmtNode(original_statement));
	    TreeNode *orig_stmt_parent = original_statement->parent();
	    assert(isTreeListNode(orig_stmt_parent));
	    TreeNode *block_node = orig_stmt_parent->parent();
	    assert(isBlockNode(block_node));
	    TreeNode *original_rhs = original_assignment->opnd1();
	    assert(isExprNode(original_rhs));
	    TreeNode *assnStmt = NULL;
	    TreeNode *declStmt = NULL;
	    item->second.temp =
	      MakeCSETemporary(original_rhs, declStmt, assnStmt);
	    item->second.declaration = declStmt;
	    item->second.declaring_block = block_node;
	    assert(assnStmt != NULL);
	    llist<TreeNode*> *new_stmts = NULL;
	    llist<TreeNode*> **curr_stmt_pos = &new_stmts;
	    for (TreeNode::ChildIter old_stmt_pos =
		   orig_stmt_parent->allChildren();
		 !old_stmt_pos.isDone();
		 old_stmt_pos.next()) {
	      if (*old_stmt_pos == original_statement) {
		if (DEBUG_SUBEXPR) {
		  cout << "Inserting assignment statement: ";
		  assnStmt->pseudoprint(cout);
		  cout << endl;
		}
		*curr_stmt_pos = cons(assnStmt);
		curr_stmt_pos = &(*curr_stmt_pos)->tail();
	      }
	      *curr_stmt_pos = cons(*old_stmt_pos);
	      curr_stmt_pos = &(*curr_stmt_pos)->tail();
	    } // for
	    block_node->stmts(new TreeListNode(new_stmts));
	    if (DEBUG_SUBEXPR) cout << "Resetting RHS of original" << endl;
	    original_assignment->opnd1(CloneTree(item->second.temp));
	    stats_numReplacements++;
	  }
	  if (DEBUG_SUBEXPR) cout << "Resetting RHS of common use" << endl;
	  current_assignment->opnd1(CloneTree(item->second.temp));
	  stats_numReplacements++;
	  TreeNode *current_node_list = current_assign_stmt->parent();
	  assert(isTreeListNode(current_node_list));
	  TreeNode *current_block = current_node_list->parent();
	  assert(isBlockNode(current_block));
	  item->second.declaring_block =
	    smallest_containing_block_of(item->second.declaring_block,
					 current_block);
	}
      } else if (/*is(array access)(rhs)*/false) {
	// 4.  var[var]			 (array access)
      } else if (isCastNode(rhs)) {
	// 5.  (type) var			 (CastNode)
      } else if (isInstanceOfNode(rhs)) {
	// 6.  var instanceof type		 (InstanceOfNode)
      } else if (isPointNode(rhs)) {
	// 8.  [var, ..., var]              (PointNode)
      } else if (isDomainNode(rhs)) {
	// 9.  [var : var, var : var, ...], and variants  (DomainNode)
      } else {
      } // if rhs
    } // if is a potential eliminator
    // check for invalidation
    // (1) assignment
    // (2) non-void method call on right of assignment
    // (3) void method calls
//     VariableSet variables_used;
//     recursively_add_uses(variables_used, current_node);
//     for (ExprHashTable::iterator item = available_subexprs.begin();
// 	 item != available_subexprs.end();
// 	 item++) {
//       if ((variables_used.find(item->first.opd1) != variables_used.end()) ||
// 	  (variables_used.find(item->first.opd2) != variables_used.end())) {
// 	insert_declaration(item);
// 	available_subexprs.erase(item);
//       }
//     }
  } // for
  for (ExprHashTable::iterator item = available_subexprs.begin();
       item != available_subexprs.end();
       item++) {
    insert_declaration(item);
  } // for
}
#endif

static bool is_assignment(const TreeNode *t)
{
  return isExpressionStmtNode(t) && isAssignNode(t->child(0));
}

treeSet *collect_assignments(const TreeNode *t) {
  assert(t != NULL);
  treeSet *result = new treeSet();
  assert(result != NULL);
  int a = t->arity();
  for (int i = 0; i < a; i++) {
    const TreeNode *child = t->child(i);
    assert(child != NULL);
    treeSet *childs_assignments = collect_assignments(child);
    result = destructively_union(result, childs_assignments);
    delete childs_assignments;
    Worklist w(const_cast<TreeNode *>(child));
    w.filter(is_assignment);
    result = destructively_union(result, list_to_set(w.asList()));
  }
  return result;
}

// take the given statment, and put it inside a block of its own
static void encloseStmtInBlock (TreeNode * stmt) {
  TreeNode * oldParent = stmt->parent();
  
  llist<TreeNode *> * nodeList = cons(stmt);

  TreeNode * block = new BlockNode(nodeList, NULL);
  
  int children = oldParent->arity();

  for (int c = 0; c < children; c++) {
    if (oldParent->child(c) == stmt) {
      oldParent->child(c, block);
    }
  }
}

// Allows us to track the locations of fake DefUses
// the key is the decl for the given variable paired with
// the statement we need to insert the fake DefUse before
//
// the value is the statement containing the fake defuse
typedef map<TreeNode*, llist<TreeNode*>*> DefUseStmtMap;
static DefUseStmtMap *fakeDefUseStmts;
typedef map<TreeNode*, TreeNode*> DefUseOriginMap;
static DefUseOriginMap *fakeDefUseOrigins;

// add a fake defuse (x = x) before the given statement, 
// and keep a record of it
// so we can find it later

// object should be any ObjectNode representing the 
// variable we want to use in the FakeDefUse (we will clone it)
//
static void addFakeDefUseBeforeStmt(TreeNode * stmt, TreeNode * object)
{
  assert(fakeDefUseStmts != NULL);
  assert(fakeDefUseOrigins != NULL);
  assert(isObjectNode(object));

  // check if we already have a fake defuse before that stmt
  // and bail out if we do
  llist<TreeNode*> *fake_stmts = (*fakeDefUseStmts)[stmt];
  for (llist<TreeNode*>::iterator i = fake_stmts->begin();
       i != fake_stmts->end();
       i++) {
    assert(isNameNode((*i)->child(0)->opnd1()->name()));
    if ((*i)->child(0)->opnd1()->name()->ident() == object->name()->ident()) {
      return;
    }
  }

  // make a fake defuse
  // 
  // make sure not to include old def/use information in the newly
  // created nodel use CloneTree() from optimize.cc to strip old
  // def/use info
  TreeNode * fakeDefUse = new AssignNode(CloneTree(object, true), CloneTree(object, true));

  // add the fake defuse before the given statement
  // note that we have to wrap the AssignNode in an ExpressionStmtNode
  TreeNode * fakeDefUseStmt = new ExpressionStmtNode(fakeDefUse);

  // if the statement isn't directly contained in a block
  // (for example, it's the only statment in a branch of an if)
  // put it in a block of its own, so AddStmts() will work
  TreeNode *container = stmt->parent()->parent();
  if (!isBlockNode(container) && !isSwitchBranchNode(container)) {
    encloseStmtInBlock(stmt);
  }

  llist<TreeNode *> * newStmts = cons(fakeDefUseStmt);
  AddStmts(stmt, newStmts);

  // add the new statement to our data structure
  (*fakeDefUseStmts)[stmt] = cons(fakeDefUseStmt, (*fakeDefUseStmts)[stmt]);
  (*fakeDefUseOrigins)[fakeDefUseStmt] = stmt;
}

struct ExprInfo {
  bool only_one_use;
  set<TreeNode *> uses;
  ExprInfo(TreeNode *assn_stmt) : only_one_use(true), uses() {
    uses.insert(assn_stmt);
  }
};
typedef HASH_MAP(ExprKey, ExprInfo) ExprTable;

static void insert_fake_defs(ExprTable &subexpr_table,
			     const treeSet::iterator &assignment_iter) {
  TreeNode *assignment_stmt = const_cast<TreeNode *>(*assignment_iter);
  assert(isExpressionStmtNode(assignment_stmt));
  TreeNode *assignment_expression = assignment_stmt->child(0);
  assert(isAssignNode(assignment_expression));
  TreeNode *rhs = assignment_expression->opnd1();
  assert(isExprNode(rhs));
  if (DEBUG_SUBEXPR) {
    cout << "Possibly inserting fake defs on expr ";
    rhs->pseudoprint(cout);
    cout << endl;
    rhs->print(cout);
    cout << endl;
  }
  if (/*is_field(rhs)*/false) {
    // 2a. var.field
  } else if (/*is_imm_field(rhs)*/false) {
    // 2b. var.i0.i1....ik.field	 (where i0, ..., ik are immutable)
  } else if (isUnaryArithNode(rhs) || isNotNode(rhs) ||
	     isComplementNode(rhs)) {
    // 3a. op var			 (UnaryArithNode, NotNode, ComplementNode)
    TreeNode *operand = rhs->opnd0();
    assert((isObjectNode(operand) && isNameNode(operand->name())) ||
	   isThisNode(operand) ||
	   isPrimitiveLitNode(operand) ||
	   isNullPntrNode(operand));
    if (isObjectNode(operand)) {
      addFakeDefUseBeforeStmt(assignment_stmt, operand);
    }
    ExprKey key = getExprKey(rhs);
    ExprTable::iterator item = subexpr_table.find(key);
    if (item == subexpr_table.end()) {
      ExprInfo value(assignment_stmt);
      subexpr_table.insert(make_pair(key, value));
      if (DEBUG_SUBEXPR) cout << "Saved " << *key.op << ' ' << key.opd1
			      << " for possible future use" << endl;
    } else {
      if (DEBUG_SUBEXPR) cout << "Previously saved " 
			      << *key.op << ' ' << key.opd1
			      << " for reuse" << endl;
      item->second.only_one_use = false;
      assert(item->second.uses.find(assignment_stmt) ==
	     item->second.uses.end());
      item->second.uses.insert(assignment_stmt);
    }
  } else if (isBinaryArithNode(rhs) || isShiftNode(rhs) ||
	     isEqualityNode(rhs) || isRelationNode(rhs) ||
	     isBitwiseNode(rhs)) {
    // 3b. var op var			 (BinaryArithNode, ShiftNode,
    // 				  EqualityNode, RelationNode,
    // 				  BitwiseNode, but not LogCondNode)
    TreeNode *operand1 = rhs->opnd0();
    assert((isObjectNode(operand1) && isNameNode(operand1->name())) ||
	   isThisNode(operand1) ||
	   isPrimitiveLitNode(operand1) ||
	   isNullPntrNode(operand1));
    if (isObjectNode(operand1)) {
      addFakeDefUseBeforeStmt(assignment_stmt, operand1);
    }
    TreeNode *operand2 = rhs->opnd1();
    assert((isObjectNode(operand2) && isNameNode(operand2->name())) ||
	   isThisNode(operand2) ||
	   isPrimitiveLitNode(operand2) ||
	   isNullPntrNode(operand2));
    if (isObjectNode(operand2)) {
      addFakeDefUseBeforeStmt(assignment_stmt, operand2);
    }
    ExprKey key = getExprKey(rhs);
    ExprTable::iterator item = subexpr_table.find(key);
    if (item == subexpr_table.end()) {
      ExprInfo value(assignment_stmt);
      subexpr_table.insert(make_pair(key, value));
      if (DEBUG_SUBEXPR) cout << "Saved " << key.opd1
			      << ' ' << *key.op << ' ' << key.opd2
			      << " for possible future use" << endl;
    } else {
      if (DEBUG_SUBEXPR) cout << "Previously saved " << key.opd1
			      << ' ' << *key.op << ' ' << key.opd2
			      << " for reuse" << endl;
      item->second.only_one_use = false;
      item->second.uses.insert(assignment_stmt);
    }
  } else if (/*is(array access)(rhs)*/false) {
    // 4.  var[var]			 (array access)
  } else if (isCastNode(rhs)) {
    // 5.  (type) var			 (CastNode)
  } else if (isInstanceOfNode(rhs)) {
    // 6.  var instanceof type		 (InstanceOfNode)
  } else if (isPointNode(rhs)) {
    // 8.  [var, ..., var]              (PointNode)
  } else if (isDomainNode(rhs)) {
    // 9.  [var : var, var : var, ...], and variants  (DomainNode)
  } else {
  } // if rhs
}

// check if the given node is a fake defuse
static bool isFakeDefUse(TreeNode * assign)
{
  if (!isAssignNode(assign->child(0))) return false;

  if (fakeDefUseOrigins->find(assign) != fakeDefUseOrigins->end()) {
    return true;
  } else {
    return false;
  }
//   TreeNode * lhs = assign->opnd0();
//   TreeNode * rhs = assign->opnd1();

//   if (!isObjectNode(lhs) || !isObjectNode(rhs)) return false;

//   return isSameObject(lhs, rhs);
}

// Check if from is the only definition that reaches to, ignoring
// intervening fake defuses
static bool defReachesHelper(TreeNode *from_stmt,
			     const set<TreeNode*> &to_stmts,
			     set<TreeNode*> &fakeDefUses,
			     set<TreeNode*> &fakeDefUsesToIgnore) {
  if (DEBUG_SUBEXPR) {
    cout << "calling defReachesHelper(";
    from_stmt->pseudoprint(cout, 0);
    cout << ")" << endl;
  }

  assert(isExpressionStmtNode(from_stmt));
  assert(isAssignNode(from_stmt->child(0)));
  TreeNode *from = from_stmt->child(0)->opnd1();
  assert(isObjectNode(from));

  if (DEBUG_SUBEXPR) {
    cout << "getting defs on: ";
    from->name()->pseudoprint(cout, 0);
    cout << endl;
  }
  llist <TreeNode *> * defsList = from->getDefs();

  assert(defsList != NULL);

  for(; defsList != NULL; defsList = defsList->tail()) {
    TreeNode * def = defsList->front();
    if (DEBUG_SUBEXPR) {
      cout << "defReachesHelper(): inspecting def:";
      def->pseudoprint(cout, 0);
      cout << endl;
    }
    if (isFakeDefUse(def->parent())) {
      if (fakeDefUsesToIgnore.find(def->parent()) !=
	  fakeDefUsesToIgnore.end()) {
	if (DEBUG_SUBEXPR) cout << "defReachesHelper(): ignoring" << endl;
      } else {
	fakeDefUsesToIgnore.insert(def->parent());
	if (to_stmts.find((*fakeDefUseOrigins)[def->parent()]) !=
	    to_stmts.end()) {
	  if (DEBUG_SUBEXPR) cout << "found a CSE def" << endl;
	  fakeDefUses.insert(def->parent());
	} else {
	  if (DEBUG_SUBEXPR) cout << "passing through this def" << endl;
	  if (!defReachesHelper(def->parent(), to_stmts,
				fakeDefUses, fakeDefUsesToIgnore)) {
	    return false;
	  }
	}
      }
    } else {
      if (DEBUG_SUBEXPR) {
	cout << "encountered a real def:" << endl;
	def->pseudoprint(cout, 0);
	cout << endl;
      }
      return false;
    }
  }

  return true;
}

// Check if from is the only definition that reaches to, ignoring
// intervening fake defuses
static bool defReaches (TreeNode *from_stmt,
			const set<TreeNode*> &to_stmts,
			set<TreeNode*> &fakeDefUses) {
  // make an empty set of fake defuses to ignore
  set < TreeNode * > fakeDefUsesToIgnore;
  fakeDefUsesToIgnore.insert(from_stmt);
  return defReachesHelper(from_stmt, to_stmts,
			  fakeDefUses, fakeDefUsesToIgnore);
}

static int elim_CSE_for_assign(TreeNode *assignment_stmt,
			       const set<TreeNode*> &other_assignments,
			       llist<TreeNode*> *&decls) {
  assert(isExpressionStmtNode(assignment_stmt));
  TreeNode *assignment_expr = assignment_stmt->child(0);
  assert(isAssignNode(assignment_expr));

  if (DEBUG_SUBEXPR) {
    cout << "Eliminating CSE on assign ";
    assignment_expr->pseudoprint(cout);
    cout << endl;
  }

  assert(fakeDefUseStmts != NULL);
  llist<TreeNode*> *fake_stmts = (*fakeDefUseStmts)[assignment_stmt];
  if (fake_stmts == NULL) return 0;

  bool okay = true;
  set<TreeNode*> fakeDefs;
  for (llist<TreeNode*>::iterator i = fake_stmts->begin();
       i != fake_stmts->end();
       i++) {
    fakeDefs.clear();
    okay = okay && defReaches(*i, other_assignments, fakeDefs);
  }
  if (!okay) return 0;

  if (DEBUG_SUBEXPR) cout << "we can eliminate" << endl;

  TreeNode *assnStmt = NULL;
  TreeNode *declStmt = NULL;
  TreeNode *temp_object = NULL;
  for (set<TreeNode*>::iterator i = fakeDefs.begin();
       i != fakeDefs.end();
       i++) {
    TreeNode *original_assignment_stmt = (*fakeDefUseOrigins)[*i];
    assert(original_assignment_stmt != NULL);
    assert(isExpressionStmtNode(original_assignment_stmt));
    if (DEBUG_SUBEXPR) {
      cout << "Origin of CSE: ";
      original_assignment_stmt->pseudoprint(cout);
      cout << endl;
    }
    TreeNode *original_assignment = original_assignment_stmt->child(0);
    assert(isAssignNode(original_assignment));
    TreeNode *lhs = original_assignment->opnd0();
    assert(isObjectNode(lhs));
    if (temp_object == NULL) {
      if (DEBUG_SUBEXPR) cout << "Creating temporary" << endl;
      temp_object = MakeCSETemporary(CloneTree(lhs, true), declStmt, assnStmt);
      decls = cons(declStmt, decls);
      stats_numCSE++;
      if (DEBUG_SUBEXPR) cout << "created" << endl;
    }
    if (DEBUG_SUBEXPR) cout << "cloning tree" << endl;
    TreeNode *assnStmt_copy = CloneTree(assnStmt);
    if (DEBUG_SUBEXPR) cout << "resetting rhs" << endl;
    assnStmt_copy->child(0)->opnd1(CloneTree(lhs, true));
    if (DEBUG_SUBEXPR) cout << "inserting assignment" << endl;
    llist<TreeNode*> *new_stmts = NULL;
    llist<TreeNode*> **curr_stmt_pos = &new_stmts;
    for (TreeNode::ChildIter old_stmt_pos =
	   original_assignment_stmt->parent()->allChildren();
	 !old_stmt_pos.isDone();
	 old_stmt_pos.next()) {
      *curr_stmt_pos = cons(*old_stmt_pos);
      curr_stmt_pos = &(*curr_stmt_pos)->tail();
      if (*old_stmt_pos == original_assignment_stmt) {
	if (DEBUG_SUBEXPR) {
	  cout << "Inserting assignment statement: ";
	  assnStmt_copy->pseudoprint(cout);
	  cout << endl;
	}
	*curr_stmt_pos = cons(assnStmt_copy);
	curr_stmt_pos = &(*curr_stmt_pos)->tail();
	stats_numReplacements++;
      }
    } // for
    TreeNode *orig_stmt_parent = original_assignment_stmt->parent();
    assert(isTreeListNode(orig_stmt_parent));
    TreeNode *block_node = orig_stmt_parent->parent();
    assert(isBlockNode(block_node));
    block_node->stmts(new TreeListNode(new_stmts));
    if (DEBUG_SUBEXPR) cout << "complete" << endl;
  }
  if (DEBUG_SUBEXPR) {
    cout << "Changing assignment statement:";
    assignment_stmt->pseudoprint(cout);
    cout << endl;
  }
  assignment_stmt->child(0)->opnd1(CloneTree(temp_object));
  if (DEBUG_SUBEXPR) {
    cout << "To:";
    assignment_stmt->pseudoprint(cout);
    cout << endl;
  }
  stats_numReplacements++;

  return 1;
}

static int eliminate_CSE(ExprTable::iterator &item, llist<TreeNode*> *&decls) {
  if (DEBUG_SUBEXPR) cout << "eliminating_CSE called" << endl;

  int numCSEsEliminated = 0;
  ExprInfo info = item->second;

  if (DEBUG_SUBEXPR) {
    cout << "eliminating CSEs for " << item->first.opd1 << ' '
	 << *item->first.op << ' ' << item->first.opd2 << endl;
  }

  if (info.only_one_use) return 0;

  if (DEBUG_SUBEXPR) {
    int count = 0;
    cout << "CSEs" << endl;
    for (set<TreeNode*>::iterator i = info.uses.begin();
	 i != info.uses.end();
	 i++) {
      count++;
      assert(isExpressionStmtNode(*i));
      TreeNode *assignment_expr = (*i)->child(0);
      assert(isAssignNode(assignment_expr));
      assignment_expr->pseudoprint(cout);
      cout << endl;
    }
    cout << "There are " << count << " CSEs." << endl;
  }

  for (set<TreeNode*>::iterator i = info.uses.begin();
       i != info.uses.end();
       i++) {
    numCSEsEliminated += elim_CSE_for_assign(*i, info.uses, decls);
  }

  return numCSEsEliminated;
}

// remove the given statment from its enclosing block
static void removeStmt(TreeNode * stmt)
{
  TreeNode * container = stmt->parent()->parent();
  
  assert(isBlockNode(container) || isSwitchBranchNode(container));

  TreeListNode *s = container->stmts();

  int c = s->arity();
  llist<TreeNode *> *t = NULL;
  
  for (int i=c-1; i>=0; i--) {
    TreeNode * currentStmt = s->child(i);
    if (currentStmt != stmt) {
      t = cons(currentStmt, t);
    }
  }

  container->stmts(new TreeListNode(t));
}

static void remove_fake_defs(ExprTable subexpr_table) {
  for (DefUseOriginMap::iterator fakeDefUse_iter = fakeDefUseOrigins->begin();
       fakeDefUse_iter != fakeDefUseOrigins->end();
       fakeDefUse_iter++) {
    TreeNode * fakeDefUse = fakeDefUse_iter->first;
    removeStmt(fakeDefUse);
  }
}

// performs global common sub-expression elimination on the enclosing method
// returns the number of replacements made
int doGlobalCSE(TreeNode *method_decl_node) {
  if (DEBUG_SUBEXPR) cout << "called doGlobalCSE" << endl;
  assert(method_decl_node != NULL);
  assert(isMethodDeclNode(method_decl_node) ||
	 isConstructorDeclNode(method_decl_node));
  // Methods without stmts don't have CFGs.
  assert(method_decl_node->getBblockRoot() != NULL);

  assert(fakeDefUseStmts == NULL);
  fakeDefUseStmts = new DefUseStmtMap();
  assert(fakeDefUseOrigins == NULL);
  fakeDefUseOrigins = new DefUseOriginMap();

  treeSet *assign_set = collect_assignments(method_decl_node);
  assert(assign_set != NULL);
  if (DEBUG_SUBEXPR) {
    cout << "Assignments for common subexpression elimination";
    for (treeSet::iterator i = assign_set->begin();
	 i != assign_set->end();
	 i++) {
      assert(*i != NULL);
      (*i)->pseudoprint(cout, 0);
    }
    cout << "\nEnd list" << endl;
  }

  int numGlobalReplacements = 0;

  ExprTable subexpr_table;
  // Get all possible expressions
  for (treeSet::iterator i = assign_set->begin();
       i != assign_set->end();
       i++) {
    insert_fake_defs(subexpr_table, i);
  }
  delete assign_set;

  if (DEBUG_SUBEXPR) cout << "Fake defs inserted" << endl;
  if (DEBUG_SUBEXPR) {
    method_decl_node->pseudoprint(cout);
    cout << endl;
  }
  invalidateCFG();
  redoDefUse(method_decl_node);
  if (DEBUG_SUBEXPR) cout << "Def/Use redid" << endl;

  llist<TreeNode *> *decls = NULL;
  if (DEBUG_SUBEXPR) cout << "now to eliminate CSEs" << endl;
  for (ExprTable::iterator i = subexpr_table.begin();
       i != subexpr_table.end();
       i++) {
    numGlobalReplacements += eliminate_CSE(i, decls);
  }
  if (DEBUG_SUBEXPR) cout << "now CSEs are eliminated" << endl;

  if (decls != NULL) {
    if (DEBUG_SUBEXPR) {
      cout << "inserting CSE temporary decls into method" << endl;
    }
    assert(isBlockNode(method_decl_node->body()));
    AddStmts(method_decl_node->body()->stmts()->child(0), decls);
  }

  if (DEBUG_SUBEXPR) cout << "removing added statements" << endl;
  remove_fake_defs(subexpr_table);

  method_decl_node->checkIF(true);

  delete fakeDefUseStmts;
  fakeDefUseStmts = NULL;    
  delete fakeDefUseOrigins;
  fakeDefUseOrigins = NULL;    

  if (DEBUG_SUBEXPR) {
    cout << "\nGlobal Common Subexpression Elimination Occured" << endl;
  }
  return numGlobalReplacements;
}

extern TreeNode *fixSubtreeSharing(TreeNode *t);

// main entry point for copy propagation - 
// performs common sub-expression elimination on the enclosing method
// returns the number of replacements made
int doCommonSubexprElim(TreeNode *t) {
  //  return 0;
  if (DEBUG_SUBEXPR) cout << "Called doCommonSubexprElim" << endl;
  assert(t != NULL);

  static bool first_time = true;
  if (first_time) {
    if (DEBUG_SUBEXPR) atexit(print_stats);
    first_time = false;
  }

  stats_num_times_called++;

  TreeNode *method_decl_node = enclosingMethod(t);
  assert(method_decl_node != NULL);
  assert(isMethodDeclNode(method_decl_node) ||
	 isConstructorDeclNode(method_decl_node));

  int chk_als = checkAliasing(method_decl_node);
  assert(chk_als == 0);

  fixSubtreeSharing(method_decl_node);

  // Methods without stmts don't have CFGs.
  if (!method_decl_node->getBblockRoot()) {
    return 0;
  }

//   return 0;

  numLocalReplacements = 0;

//   TraverseBblocks(method_decl_node->getBblockRoot(), eliminateSubexprsBblock);

  method_decl_node->fixParent();
  method_decl_node->checkIF(true);

  int numGlobalReplacements = doGlobalCSE(method_decl_node);

  if (DEBUG_SUBEXPR) {
    cout << "\nCommon Subexpression Elimination Occured" << endl;
    cout << numGlobalReplacements << " CSEs eliminated" << endl;
    cout << "After modifications:";
    method_decl_node->pseudoprint(cout);
    cout << endl;
  }

  chk_als = checkAliasing(method_decl_node);
  assert(0 == chk_als);

  return numLocalReplacements + numGlobalReplacements;
}