/* Find useless assignment statements (the heart of "UAE"). */

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

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

/* t is an AssignNode.  s is a set of assignments believed to be useless.
   If the result of t is used by a statement not in s then t is useful.
   I.e., if the result of t is used by a non-useless stmt then return false.
   Also return false if t has or may have side-effects. */
static bool useless(TreeNode *t, const treeSet *s)
{
  TreeNode *lhs = t->opnd0();
  if (DEBUG_UAE) {
    cout << "Checking utility of ";
    cout << PCODE(t);
    cout << endl;
  }

  if (!isIIFAN(lhs)) {
    if (!isObjectNode(lhs))
      return false;
    if (!isLocalOrParam(lhs->decl()))
      return false;
  }
  TreeNode *rhs = t->opnd1();
  
  // Do we have to execute rhs because of possible side effects?
  // If so, return false immediately.
  if (!(isObjectNode(rhs) && isLocalOrParam(rhs->decl())) &&
      !isSideEffectFreeAndCannotFail(rhs) &&
      !isConstantOrCastOfConstant(rhs) &&
      !isNullOrCastOfNull(rhs) &&
      !isIIFAN(rhs) &&
      !isTrivialPointOrDomain(rhs))
    return false;

  if (isObjectNode(lhs) && isObjectNode(rhs) && 
      lhs->decl() == rhs->decl() && 
      isLocalOrParam(rhs->decl())) 
    return true; /* quickly detect "x = x", a very common case */

  treeSet *rvu = RvalueUses(lhs);
  treeSet *u = exprset_to_stmtset(rvu);
  bool r = isSubset(u, s);
  if (DEBUG_UAE) {
    cout << "Stmts with rvalue uses stemming from ";
    cout << PLCODE(lhs);
    cout << ":" << endl;
    printTreeSet(u, cout, 1);
    cout << "(all uses:" << endl;
    printTreeSet(allUses(lhs), cout, 1);
    cout << ")" << endl << "Therefore, ";
    cout << PCODE(t);
    cout << (r ? " is" : " is not") << " useless" << endl << endl;
  }
  delete rvu;
  delete u;
  return r;
}

static void showAssignmentsAndUses(const treeSet *r, ostream &os)
{
  for (treeSet::const_iterator i = r->begin();
       i != r->end();
       ++i) {
    (*i)->pseudoprint(os, 0);
    os << endl << "  Uses of ";
    (*i)->child(0)->child(0)->pseudoprint(os, 0);
    os << endl;
    printTreeSetWithParents(list_to_set((*i)->child(0)->child(0)->getUses()), os, 2);
    os << endl << "  Defs:" << endl;
    printTreeSetWithParents(list_to_set((*i)->child(0)->child(0)->getDefs()), os, 2);
    os << endl;
  }
}

/* Find all assignments under t that are not under a "noUAE" pragma. */
static treeSet *find_UAE_candidates(TreeNode *t)
{
  treeSet *result = new treeSet;
  if (underPragma(Pragma::noUAE, t))
    return result;
  treeSet *subtrees = find_subtrees_not_with_pragma(Pragma::noUAE, t);
  for (treeSet::iterator i = subtrees->begin(); i != subtrees->end(); i++) {
    Worklist w(const_cast<TreeNode *>(*i));
    w.filter(assignment);
    result = destructively_union(result, list_to_set(w.asList()));
  }
  delete subtrees;
  return result;
}

/* Find useless assignments.  Caller should free the set that is returned. */
treeSet * TreeNode::uselessAssignments()
{
  treeSet *r = find_UAE_candidates(this);

  if (DEBUG_UAE) {
    cout << "Preparing to eliminate useless assignments." << endl << endl;
    showAssignmentsAndUses(r, cout);
    cout << endl;
  }

  bool progress;
  do {
    progress = false;
    for (treeSet::iterator i = r->begin();
	 i != r->end(); )
      if (!useless((*i)->child(0), r)) {
	r->erase(i++);
	progress = true;
      } 
      else ++i;
  } while (progress);

  if (DEBUG_UAE) {
    cout << "Useless Assignments:" << endl;
    printTreeSet(r, cout, 1);
  }
  return r;
}