#include "AST.h"
#include "optimize.h"
#include "code-util.h"
#include "cfg.h"
#include "pragma.h"

// Unreachable code removal optimization
// Author: Dan Bonachea <bonachea@cs.berkeley.edu>, 8/2001

static treeSet unreachableStmts;
static void findUnreachableStatements(TreeNode *t);

// main entry point for unreachable code removal
// remove any unreachable StatementNodes in the given AST subtree
// to remove dead code often created by inlining and/or CPCF
// for best results, run this before dead variable elimination
// assumes Cfg and basicblocks are valid
// returns modified tree

TreeNode *removeUnreachableStmts(TreeNode *t) {
  if (!underPragma(Pragma::noOpt, t)) {
    assert(enclosingMethod(t)->getBblockRoot() != NULL); // require a valid CFG/basicblock analysis

    unreachableStmts.clear();
    findUnreachableStatements(t);

    if (DEBUG_UNREACHABLE) {
      cout << "Unreachable stmt removal found " 
	   << unreachableStmts.size() << " unreachable statements:" << endl;
      for (treeSet::iterator it=unreachableStmts.begin();
	   it != unreachableStmts.end();
	   it++) {
	(*it)->pseudoprint(cout, 0);
	cout << endl;
      }
    }

    t = t->deleteStmts(&unreachableStmts);
    unreachableStmts.clear();
  }
  return t;
}

// return the CfgNode corresponding to this StatementNode
static CfgNode *getCfgEntry(TreeNode *t) {
  assert(t->isStatementNode());
  CfgNode *c = t->getCfgExtent().entry;
  if (!c) {
    cerr << "*** ERROR: CfgNode missing for this StatementNode:" << endl;
    t->print(cerr, 0);
    fatal_error("");
  }
  return c;
}

// sanity check - make sure entire subtree is unreachable
static void assertUnreachable(TreeNode *t) {
  if (t->isStatementNode()) {
    CfgNode *c = getCfgEntry(t);
    if (c->bblock != NULL) {
      cout << "Error in assertUnreachable; t is " << pseudocode(t) <<
	endl << "parent of t is " << pseudocode(t->parent()) <<
	endl << "parent of parent of t is " <<
	pseudocode(t->parent()->parent()) << endl;
      fatal_error("");
    }
  }
  for (int i=0; i < t->arity(); i++) 
    assertUnreachable(t->child(i));
}

static void findUnreachableStatements(TreeNode *t) {
  if (t->isPragma(Pragma::noOpt))
    return;

  if (t->isStatementNode()) {
    CfgNode *c = getCfgEntry(t);
    if (c->bblock == NULL) { // statement is unreachable
      unreachableStmts.insert(t);
      // make sure and child stmts are also unreachable
      // (should always be the case because the language does not
      // allow branching into substructures)
      for (int i=0; i < t->arity(); i++) 
        assertUnreachable(t->child(i));
      return;
    }
  }

  for (int i=0; i < t->arity(); i++) 
    findUnreachableStatements(t->child(i));
}