// Code related to the "junk" method on grids

#include "AST.h"
#include "EquivalenceRelation.h"
#include "optimize.h"
#include "stoptifu/stoptifu.h"
#include "clone.h"
#include "snippet.h"
#include "string-utils.h"
#include "TouchSet.h"
#include "Bridge.h"
#include "free_map.h"
#include "pseudocode.h"
#include "lower.h"
#include "StorageAnnotations.h"
#include "junk.h"

extern bool debug_stoptifu;
#define debug_junk debug_stoptifu

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

typedef map<TreeNode *, ForEachStmtNode *> map_ifstmt_to_loop;

/////////////////////////////////////////////////////////////////////////////
// Utils for ISFs 
//  (an ISF is an "if surrounding a foreach," in particular the one
//   automatically introduced to check that the domain is non-empty)
/////////////////////////////////////////////////////////////////////////////

static void find_loops(TreeNode *x, set<TreeNode *> &ISFs,
		       map_ifstmt_to_loop &ifstmtToLoop)
{
  if (isForEachStmtNode(x)) {
    ForEachStmtNode *t = static_cast<ForEachStmtNode *>(x);
    TreeNode *ifstmt = t->cannotBeEmpty();
    assert(ifstmt != NULL);
    ISFs.insert(ifstmt);
    ifstmtToLoop[ifstmt] = t;
  }
  foriter (p, x->allChildren(), TreeNode::ChildIter)
    find_loops(*p, ISFs, ifstmtToLoop);
}

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

/* Return true if all paths from *i (and *(i.next()) etc.) lead to second.
   Accumulate nodes seen along the way in path, pathAsSet, and b.
   Exception: Do not put calls to grid method "junk" in b.
   If second is NULL, set second to a foreach loop, if one is found.
   The only foreaches considered for second are ones whose ISF appears in
   ISFs.  (Based on find_pair_DFS() in stoptifu.cc.)
*/
static bool find_following_loop(set<TreeNode *> &ISFs,
				map_ifstmt_to_loop &ifstmtToLoop,
				Bridge *b,
				ForEachStmtNode *& second,
				ListIterator<CfgNode *> i,
				llist<CfgNode *> *path,
				CFGset *pathAsSet = NULL)
{
#define FAIL(s) do { failstr = (s); result = false; goto done; } while (0)
#define QUIETFAIL() do { result = false; goto dealloc; } while (0)

  bool mustfree;
  if (pathAsSet == NULL) {
    assert(path == NULL);
    pathAsSet = new CFGset();
    mustfree = true;
  } else
    mustfree = false;

  string failstr = "can reach end of method";
  bool result = false;
  while (!i.isDone()) {
    CfgNode *n = *i;
    if (!contains(pathAsSet, n)) {
      TreeNode *t = n->astNode();
      if (t->isExprNode())
	t = enclosingStmt(t);
      DBG({
	size_t size = path->size();
	cout << "find_following_loop: path is ";
	if (size <= 10) {
	  path = dreverse(path);
	  shortCFGlist(cout, ListIterator<CfgNode *>(path));
	  path = dreverse(path);
	} else {
	  shortCFGnode(cout, path->last());
	  cout << " ... (" << (size - 2) << " nodes) ...";
	  shortCFGnode(cout, path->front());
	}
	cout << ' ';
	shortCFGnode(cout, n);
	cout << endl;
	cout << "t is:" << endl;
	if (t == TreeNode::omitted)
	  cout << " (omitted)";
	else
	  t->pseudoprint(cout, 0);
	cout << endl;
      });
      if (ISFs.find(t) != ISFs.end()) {
	ForEachStmtNode *c = ifstmtToLoop[t];
	DBG(cout << "reached loop " << nameOfLoop(c) << endl);
	if (second == NULL) {
	  second = c;
	  DBG(cout << "second = " << nameOfLoop(second) << endl);
	  goto sofarsogood;
	} else if (second == c)
	  goto sofarsogood;
	else
	  FAIL("can reach " + nameOfLoop(second) + " or " + nameOfLoop(c));
      }
      /*  recurse: */
      DBG({
	cout << "find_following_loop: recurse on ";
	shortCFGlist(cout, n->succIter());
	cout << endl;
      });
      {
	path = cons(n, path);
	pathAsSet->insert(n);
	bool r = find_following_loop(ISFs, ifstmtToLoop, b,
				     second, n->succIter(), path, pathAsSet);
	pathAsSet->erase(n);
	path = path->free();
	if (!r)
	  QUIETFAIL();
      }
      if (t != TreeNode::omitted && !is_junk_call(enclosingStmt(t))) {
	DBG({
	  cout << "Adding to bridge:" << endl;
	  t->pseudoprint(cout, 0);
	  cout << endl;
	});
	b->adjoin(t);
      }
    }
  sofarsogood:
    result = true;
    i.next();
  }

 done:
  result = result && (second != NULL);
  if (debug_stoptifu && !result)
    cout << "find_following_loop() failed: " <<
      failstr << endl;
  
 dealloc:
  if (mustfree)
    delete pathAsSet;

  return result;

#undef FAIL
#undef QUIETFAIL
}

/* Return true if all paths from *i (and *(i.next()) etc.) lead to second.
   Accumulate nodes seen along the way in path, pathAsSet, and b.
   Exception: Do not put calls to grid method "junk" in b.
  (Based on find_pair_DFS() in stoptifu.cc.)
*/
static bool find_loop_then_junk(set<TreeNode *> &ISFs,
				map_ifstmt_to_loop &ifstmtToLoop,
				ForEachStmtNode *first,
				Bridge *b,
				MethodCallNode *second,
				ListIterator<CfgNode *> i,
				llist<CfgNode *> *path,
				CFGset *pathAsSet = NULL)
{
#define FAIL(s) do { failstr = (s); result = false; goto done; } while (0)
#define QUIETFAIL() do { result = false; goto dealloc; } while (0)

  bool mustfree;
  if (pathAsSet == NULL) {
    assert(path == NULL);
    pathAsSet = new CFGset();
    mustfree = true;
  } else
    mustfree = false;

  string failstr = "can reach end of method";
  bool result = false;
  while (!i.isDone()) {
    CfgNode *n = *i;
    if (!contains(pathAsSet, n)) {
      TreeNode *t = n->astNode();
      if (t->isExprNode())
	t = enclosingStmt(t);
      DBG({
	size_t size = path->size();
	cout << "find_loop_then_junk: path is ";
	if (size <= 10) {
	  path = dreverse(path);
	  shortCFGlist(cout, ListIterator<CfgNode *>(path));
	  path = dreverse(path);
	} else {
	  shortCFGnode(cout, path->last());
	  cout << " ... (" << (size - 2) << " nodes) ...";
	  shortCFGnode(cout, path->front());
	}
	cout << ' ';
	shortCFGnode(cout, n);
	cout << endl;
	cout << "t is:" << endl;
	if (t == TreeNode::omitted)
	  cout << " (omitted)";
	else
	  t->pseudoprint(cout, 0);
	cout << endl;
      });
      if (isExpressionStmtNode(t) && t->expr() == second)
	goto sofarsogood;
      DBG({
	if (ISFs.find(t) != ISFs.end())
	  cout << "reached loop " << nameOfLoop(ifstmtToLoop[t]) << endl;
      });
      /* recurse: */
      DBG({
	cout << "find_loop_then_junk: recurse on ";
	shortCFGlist(cout, n->succIter());
	cout << endl;
      });
      {
	path = cons(n, path);
	pathAsSet->insert(n);
	bool r = find_loop_then_junk(ISFs, ifstmtToLoop, first, b, second,
				     n->succIter(), path, pathAsSet);
	pathAsSet->erase(n);
	path = path->free();
	if (!r)
	  QUIETFAIL();
      }
      if (t != TreeNode::omitted && !is_junk_call(enclosingStmt(t))) {
	DBG({
	  cout << "Adding to bridge:" << endl;
	  t->pseudoprint(cout, 0);
	  cout << endl;
	});
	b->adjoin(t);
      }
    }
  sofarsogood:
    result = true;
    i.next();
  }

  /* done: */
  result = result && (second != NULL);
  if (debug_stoptifu && !result)
    cout << "find_loop_then_junk() failed: " <<
      failstr << endl;
  
 dealloc:
  if (mustfree)
    delete pathAsSet;

  return result;

#undef FAIL
#undef QUIETFAIL
}

static void assert_array_result_junked(ForEachStmtNode *f, MethodCallNode *t)
{
  TreeNode *array = t->method()->child(0);
  DPRINTLN("assert_array_result_junked(foreach at " + 
	   f->position().asString() + ", " + pseudocode(array) + " at " +
	   t->position().asString() + ")");
  push(f->junk_post(), array);
}

static void assert_junk_reaches(MethodCallNode *t, ForEachStmtNode *f)
{
  TreeNode *array = t->method()->child(0);
  DPRINTLN("assert_junk_reaches(" + pseudocode(array) + " at " +
	   t->position().asString() + ", foreach at " + 
	   f->position().asString() + ")");
  push(f->junk_pre(), array);
}

/* ISFs is a set of "ifs surrounding foreaches," as defined above.
   ifstmtToLoop maps each elt of ISFs to the corresponding ForEachStmtNode.
   t is a call to the junk method on some grid.

   For every loop in ISFs, check if <loop, t> is a pair of statements
   that satisfy the following:
   1. t must must, inexorably, be followed by the execution of loop.
   2. No value junked in t is written in the code between t and loop
      (except perhaps by another call to the junk method on a grid).
*/
static void find_loop_after_junk_call(set<TreeNode *> &ISFs,
				      map_ifstmt_to_loop &ifstmtToLoop,
				      MethodCallNode *t)
{
  DPRINTLN("find_loop_after_junk_call(" + pseudocode(t) + ")");
  ForEachStmtNode *f = NULL;
  StatementNode *encl = enclosingStmt(t);
  ListIterator<CfgNode *> after =
    encl->getCfgExtent().exit->succIter();
  Bridge *b = new Bridge();
  if (find_following_loop(ISFs, ifstmtToLoop, b, f, after, NULL)) {
    DPRINTLN("loop after junk call is: " + pseudocode(f));
    b->finalize(NULL);
    t->findMayMustReadWrite(true, true);
    if (TouchSet_does_intersect(writes(t, false), b->writes(true), true)) {
      DPRINTLN("  ... ignored due to conflicting write in bridge");
    } else if (!b->must_come_from(encl)) {
      DPRINTLN("  ... ignored because bridge has other entry points");
    } else {
      assert_junk_reaches(t, f);
      /* Recursively check if junk reaches subsequent loop (if any) */
      TreeNode *ifstmt = f->cannotBeEmpty();
      assert(ifstmt != NULL);
      ISFs.erase(ifstmt);
      DPRINTLN("recurse");
      find_loop_after_junk_call(ISFs, ifstmtToLoop, t);
      DPRINTLN("recurse done");
      ISFs.insert(ifstmt);
    }
  }
  delete b;
}

/* ISFs is a set of "ifs surrounding foreaches," as defined above.
   ifstmtToLoop maps each elt of ISFs to the corresponding ForEachStmtNode.
   t is a call to the junk method on some grid.

   For every loop in ISFs, check if <loop, t> is a pair of statements
   that satisfy the following:
   1. The end of loop must, inexorably, be followed by the execution of t.
   2. No value written in loop and also junked in t is read in
      between loop and t.
*/

static void find_loop_prior_to_junk_call(set<TreeNode *> &ISFs,
					 map_ifstmt_to_loop &ifstmtToLoop,
					 MethodCallNode *t)
{
  for (set<TreeNode *>::const_iterator i = ISFs.begin();
       i != ISFs.end(); ++i) {
    ForEachStmtNode *f = ifstmtToLoop[const_cast<TreeNode *>(*i)];
    DPRINTLN("find_loop_prior_to_junk_call(" + pseudocode(t) + 
	     " at " + t->position().asString() + ", foreach at " + 
	     f->position().asString() + ")");
    ListIterator<CfgNode *> after_f =
      f->cannotBeEmpty()->getCfgExtent().exit->succIter();
    Bridge *b = new Bridge();
    if (find_loop_then_junk(ISFs, ifstmtToLoop, f, b, t, after_f, NULL)) {
      llist<ForEachStmtNode *> *exclude = cons(f);
      DPRINTLN("loop prior to junk call is: " + pseudocode(f));
      b->finalize(exclude);
      if (TouchSet_does_intersect(writes(t, false), b->reads(true), true)) {
	DPRINTLN("  ... ignored due to conflicting read in bridge");
      } else if (!b->must_come_from(f)) {
	DPRINTLN("  ... ignored because bridge has other entry points");
      } else
	assert_array_result_junked(f, t);
      free_all(exclude);
    }
    delete b;
  }
}


/* Find junked arrays.  Also, note junkings relationship to loops:
   1. If an array is junked and a foreach loop must follow the junking,
      with no intervening non-junk writes to the array, then label the loop.
   2. If a junking must follow a loop, with no intervening reads of the
      array junked, then mark the loop.  */
void find_junked_arrays(TreeNode *method)
{
  DPRINTLN("find_junked_arrays(" + nameOfEnclosingMethod(method) + ")");
  set<TreeNode *> ISFs;
  map_ifstmt_to_loop ifstmtToLoop;
  find_loops(method, ISFs, ifstmtToLoop);
  llist<TreeNode *> *todo = cons(method);
  do {
    TreeNode *t = todo->front();
    todo = todo->free();
    if (isGridMethod(t, "junk")) {
      find_loop_prior_to_junk_call(ISFs, ifstmtToLoop,
				   static_cast<MethodCallNode *>(t));
      find_loop_after_junk_call(ISFs, ifstmtToLoop,
				static_cast<MethodCallNode *>(t));
    } else
      foriter (p, t->allChildren(), TreeNode::ChildIter)
	push(todo, *p);
  } while (todo != NULL);
}