/* Deps 

The findMayMustReadWrite pass determines what each expression may/must
read/write.  It doesn't worry about control flow (since IF expressions
have only trivial control flow).

A separate pass, computeArrayAccessSummary(), uses info from the
findMayMustReadWrite pass to compute what array elements must/may be
read/written by each Foreach loop.  (currently disabled)
*/

#include "AST.h"
#include "optimize.h"
#include "cfg.h"
#include "code-deps.h"
#include "code-defs.h"
#include "TouchSet.h"

/* Macros for debugging output */
#define DPRINT(x) do { if (DEBUG_DEPS) cout << (x); } while (0) 
#define DPRINTLN(x) DPRINT(string(x) + '\n')
#define DBG(x) do { if (DEBUG_DEPS) { x; } } while (0)

void TreeNode::findMayMustReadWrite(bool r, bool w)
{
  DBG(if (isStatementNode()) {
    cout << "Analyzing";
    pseudoprint(cout, 2);
    cout << endl;
  });
  foriter (p, allChildren(), ChildIter)
    (*p)->findMayMustReadWrite(r, false);
}

/* Merge u's info and t's info and store the result in t's info. */
static void mergeMayMustReadWrite(ExprNode *t, ExprNode *u)
{
  t->mayRead() = TouchSet_union(t->mayRead(), u->mayRead());
  t->mustRead() = TouchSet_union(t->mustRead(), u->mustRead());
  t->mayWrite() = TouchSet_union(t->mayWrite(), u->mayWrite());
  t->mustWrite() = TouchSet_union(t->mustWrite(), u->mustWrite());
}

/* Set mayRead, mustRead, mayWrite, and mustWrite for t.  Do it by
   aggregating information from u's children. */
static void aggregateMayMustReadWrite(ExprNode *t, TreeNode *u = NULL)
{
  if (u == NULL)
    u = t;
  t->mayRead() = t->mustRead() = t->mayWrite() = t->mustWrite() = NULL;
  int a = u->arity();
  if (a > 0)
    while (--a >= 0)
      if (isExprNode(u->child(a)))
	mergeMayMustReadWrite(t, static_cast<ExprNode *>(u->child(a)));
}

void ExprNode::findMayMustReadWrite(bool r, bool w)
{
  TreeNode::findMayMustReadWrite(r, w);
  aggregateMayMustReadWrite(this);
}

void AssignNode::findMayMustReadWrite(bool r, bool w)
{
  opnd1()->findMayMustReadWrite(true, false);
  opnd0()->findMayMustReadWrite(false, true);
  aggregateMayMustReadWrite(this);
}

void ObjectNode::findMayMustReadWrite(bool r, bool w)
{
  mayRead() = mustRead() = mayWrite() = mustWrite() = NULL;
  TouchSet *ts = new TouchSet(name()->decl());
  if (r) {
    DPRINT("Reading from object node: ");
    DBG((pseudoprint(cout, 2), cout << endl));
    mustRead() = ts;
  }
  if (w) {
    DPRINT("Writing to object node: ");
    DBG((pseudoprint(cout, 2), cout << endl));
    mustWrite() = ts;
  }
}

void ThisNode::findMayMustReadWrite(bool r, bool w)
{
  mayRead() = mustRead() = mayWrite() = mustWrite() = NULL;
  TouchSet *ts = makeTouchSetThis();
  if (r) {
    DPRINTLN("Reading from this");
    // DBG((pseudoprint(cout, 2), cout << endl));
    mustRead() = ts;
  }
  if (w) {
    DPRINTLN("Writing to this");
    // DBG((pseudoprint(cout, 2), cout << endl));
    mustWrite() = ts;
  }
}

void ArrayAccessNode::findMayMustReadWrite(bool r, bool w)
{
  mayRead() = mustRead() = mayWrite() = mustWrite() = NULL;
  TreeNode *a = array();
  a->findMayMustReadWrite(true, false);
  index()->findMayMustReadWrite(true, false);
  TouchSet *ts = new TouchSet(cons(a->type(),
				   Defs::aliasableArrayTypes(a->type())));
  if (r) {
    DPRINT("indexing array for read: ");
    DBG((pseudoprint(cout, 2), cout << endl));
    DPRINT("TouchSet = \n" + ts->to_string());
    mustRead() = ts;
  }
  if (w) {
    DPRINT("indexing array for write: ");
    DBG((pseudoprint(cout, 2), cout << endl));
    DPRINT("TouchSet = \n" + ts->to_string());
    mustWrite() = ts;
  }
}

/* T is a FieldAccessNode.  TY is the type of the field being accessed.
   NAME is the name of the field being accessed. */
static void fieldMayMustReadWrite(ExprNode *t, TypeNode *ty, TreeNode *name,
				  bool r, bool w)
{
  xtype x = type2xtype(ty);
  const string &f = *name->ident();
  TouchSet *ts = new TouchSet(x, f);
  if (r) {
    DBG(cout << "Read from <" << xtype2str(x) << ", " << f << ">" << endl);
    t->mustRead() = ts;
  }
  if (w) {
    DBG(cout << "Write to <" << xtype2str(x) << ", " << f << ">" << endl);
    t->mustWrite() = ts;
  }
}

void ObjectFieldAccessNode::findMayMustReadWrite(bool r, bool w)
{
  mayRead() = mustRead() = mayWrite() = mustWrite() = NULL;
  ExprNode *o = (ExprNode *) object();
  o->findMayMustReadWrite(true, false);
  if (isIIFAN(this) && isObjectNode(o) && isLocalOrParam(o->decl())) {
    TouchSet *ts = new TouchSet(o->decl(), *simpName()->ident());
    if (r) {
      DPRINTLN("read field of immutable local/param");
      mustRead() = ts;
    }
    if (w) {
      DPRINTLN("write field of immutable local/param");
      mustWrite() = ts;
    }
  } else
    fieldMayMustReadWrite(this, simpName()->decl()->container()->asType(),
			  simpName(), r, w);
  mergeMayMustReadWrite(this, o);
}

void TypeFieldAccessNode::findMayMustReadWrite(bool r, bool w)
{
  mayRead() = mustRead() = mayWrite() = mustWrite() = NULL;
  fieldMayMustReadWrite(this, ftype(), simpName(), r, w);
}

void MethodCallNode::findMayMustReadWrite(bool r, bool w)
{
  args()->findMayMustReadWrite(true, false);
  r = !doesNotReadOrWriteNonArgs(this);
  w = r && !isSideEffectFree();
  DBG(cout << "Method call " << pseudocode(this) << " " <<
      (w ? "may read and write" : (r ? "may read" : "won't touch")) <<
      " vars" << endl);
  aggregateMayMustReadWrite(this, args());
  mayRead() = TouchSet_union(mayRead(), new TouchSet(r));
  mayWrite() = TouchSet_union(mayWrite(), new TouchSet(w));
}

/* Ignore DummyNodes. */
void DummyNode::findMayMustReadWrite(bool r, bool w) { }

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

/*
static bool setupDeps(Bblock *b)
{
  return false;
}
*/

void setupDepsMethod(TreeNode *t)
{
  Bblock *root = t->getBblockRoot();

  if (!root) 
    return;

  DPRINTLN("Setting up deps for method at " + t->position().asString());
  
  t->findMayMustReadWrite(true, true);
  // TraverseBblocksIter(root, setupDeps);
}

#if 0
///////////////////////////////////////////////////////////////////////////
/* current_list, ADD_TO_LIST(), and addToList() are used by
   loopArrayAccessSummary(). */

static llist<CfgNode *> * current_list = NULL;
#define ADD_TO_LIST() ((current_list ?					\
			(free_all(current_list), current_list = NULL) :	\
			NULL),						\
		       addToList)

static void addToList(CfgNode *x, void*)
{
  current_list = cons(x, current_list);
}

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

/* loopArrayAccessSummary() uses info from the findMayMustReadWrite
pass (and the CFG) to compute what array elements must/may be
read/written by a full-domain Foreach loop. */
void loopArrayAccessSummary(ForEachStmtNode *l)
{
  if (l->partialDomain())
    return;
  CfgExtent extent = l->getCfgExtent();
  CfgNode *from = extent.entry;
  CfgNode *to = extent.exit;
  TraverseCfgScope(l, ADD_TO_LIST(), NULL);
  current_list = dreverse(current_list);
  bool progress = false;
  map<CfgNode *, ArrayAccessSummary *> m;
  do {
    llist<CfgNode *> *q = current_list;
    while (q != NULL) {
      CfgNode *f = q->front();
      q = q->tail();
      TreeNode *t = f->astNode();
      cout << "Processing f=" << f << " t=" << pseudocode(t) << endl;
      ArrayAccessSummary *aas = NULL;
      // First, set a to the merge of the predecessors' values.
      ListIterator<CfgNode *> preds = f->predIter();
      for (; !preds.isDone(); preds.next())
	mergeArrayAccessSummary(aas, *preds, m);
      // Second, if we are processing an ExprNode, merge in its accesses.
      if (t->isExprNode())
	mergeArrayAccessSummary(aas, static_cast<ExprNode *>(t), progress);
      // Did we make progress?
      ArrayAccessSummary *&o = m[f];
      if (o == NULL || o->different(aas)) {
	o = aas;
	progress = true;
      }
    }
  } while (progress);
}

void computeArrayAccessSummary(TreeNode *t)
{
  if (isForEachStmtNode(t))
    loopArrayAccessSummary(static_cast<ForEachStmtNode *>(t));
  foriter (p, t->allChildren(), TreeNode::ChildIter)
    computeArrayAccessSummary(*p);
}

#endif /* 0 */