#include "AST.h"
#include "ArrayAccessSet.h"
#include "CodeContext.h"
#include "code-call.h"
#include "code-foreach.h"
#include "code-grid.h"
#include "code-bounds.h"
#include "code-util.h"
#include "code.h"
#include "compiler.h"
#include "decls.h"
#include "utils.h"
#include "optimize.h"
#include "code-MIVE.h"
#include "buildexpr.h"
#include "PolyToCode.h"
#include "stats.h"

/****************************************************************************
 Optimization of Bounds Checking

 Optimized array index expressions are bounds checked in the loop preheader.
 For each dimension of each index expression, we generally test the following:
   1. lowest value is at or above array's minimum
   2. highest value is at or below array's maximum
   3. starting value is on stride
   4. difference between iterations is on stride

 If all 4 tests pass then the index expression will be in bounds and
 on stride for the entire loop.

 We omit one or both of the first two if other index expressions are
 known to be more extreme.  E.g., if the lowest value of e - 1 is at
 or above the array's minimum then lowest value of e must be too.
  
 We omit the last test if the iteration is trivial (0 or 1 iters).

 We omit both of the last two tests if the stride of the array must be 1
 in the dimension of interest.  E.g., if a[p] and a[p + [0, 1]]
 appear on every iteration then we simply check that the stride of a
 is 1 in the 2nd dimension and omit all other stride related tests for
 that dimension.

 The first three tests are generated by a call to
 void generateBoundsChecks(CodeContext &context,
			   ForEachStmtNode *WRTloop,
			   const StringRect *curr_rect,
			   ArrayAccessSet *arrayAccesses,
			   map_int_to_treeSet &provablyUnitStride)
 from foreachRectIterate().  The last test is generated later, in
 convertDiffToOffset().
 ****************************************************************************/

/* The list of MIVEs, c, is a list of the array index expressions
   whose minimums in dimension dim we need to consider.  Generate code
   to find the minimum of those and return the string that represents
   the result.  curr_rect is the rectangle over which we're iterating;
   arr is the array in question.
*/
static string
findMin(CodeContext &context, ForEachStmtNode *WRTloop,
	const StringRect *curr_rect, const string &arr,
	int dim, llist<const MIVE *> *c)
{
  // cout << "findMin(): # candidates = " << c->size() << endl;
  llist<string> *possibleMin = NULL;
  /* n is the number of dimensions in the iteration */
  int n = WRTloop->vars()->child(0)->initExpr()->type()->tiArity();
  /* the variables that represent the iteration point */
  Poly **p = WRTloop->vars()->child(0)->simpName()->getMIVE(WRTloop)->p;

  for (ListIterator<const MIVE *> i(c); !i.isDone(); i.next()) {
    string s("0");
    const Poly *goal = (*i)->p[dim];
    // cout << "initial goal: " << goal->asString() << endl;
    /* We want s to be the minimum value that goal can have over the
       course of the loop. */
    for (int j = 0; j < n; j++) {
      string sj;
      /* The change in the array index expr in the dimension of interest
	 is known to be constant with respect to the change in the iteration
	 variables.  However, it isn't necessarily a known integer at
	 compile time. */
      const Poly *d = deriv(*i, dim, WRTloop, j);
      if (d->zerop())
	continue;
      else if (d->constantp()) {
	int x = d->asInt();
	if (x > 0)
	  sj = product(int2string(x), curr_rect->lo(j), context);
	else
	  sj = product(int2string(x), curr_rect->hi(j), context);
      } else {
	string t = PolyToCode(d, WRTloop, context);
	sj = "((" + t + " > 0) ? " +
	  "(" + t + " * " + curr_rect->lo(j) + ") : " + 
	  "(" + t + " * " + curr_rect->hi(j) + "))";
      }
      s = sum(s, sj, context);
      goal = goal->add(p[j]->mult(d)->negate());
      // cout << "goal after " << j << ": " << goal->asString() << endl;
    }
    s = sum(s, PolyToCode(goal, WRTloop, context));
    possibleMin = cons(s, possibleMin);
  }
  return min(possibleMin, context);
}

/* Check the condition, and abort with an useful error message if it fails. */
void generateBoundsAssert(CodeContext &context, const string &condition,
			  const string &arr, TypeNode *arrayType,
			  int dim, ForEachStmtNode *WRTloop,
			  const string &n1, const string &between,
			  string n2)
{
  string args, method;
  if (n2 == "") {
    args = n1 + ", \"" + between + "\"";
    method = "_ARRAY_BOUNDS_VIOLATIONds";
  } else {
    args = n1 + ", \"" + between + "\", " + n2;
    method = "_ARRAY_BOUNDS_VIOLATIONdsd";
  }
  args = "(\"" + WRTloop->position().asString() + "\", &(" + arr + "), " +
    int2string(dim + 1) + ", " + args + ")";
  context << "if (!(" << condition << "))" << endCline << "  " <<
    callGridMethod(*arrayType, method, args) << ';' << endCline;
}
    
/* Check that every elt of l is on stride in dimension dim.  This is
   sometimes overkill, but the savings from doing it intelligently
   would be small. */
static void
generateStrideTest(CodeContext &context, ForEachStmtNode *WRTloop,
		   const string &arr, int arity,
		   TypeNode *arrayType, int dim, llist<const MIVE *> *l)
{
  const string stride = build(rectStride(arr + ".domain", dim, arity),
			      theIntType->cType(), context);
  context << "if (" << stride << " != 1) {" << endCline;
  const string base = build(rectMin(arr + ".domain", dim, arity),
			    theIntType->cType(), context);
  for (ListIterator<const MIVE *> i(l); !i.isDone(); i.next()) {
    const string v0 = PolyToCode((*i)->p[dim], WRTloop, context);
    const string v = v0 + " - " + base;
    generateBoundsAssert(context, "((" + v + ") % " + stride + ") == 0",
			 arr, arrayType, dim, WRTloop,
			 v0, " must be on stride");
  }
  context << "}" << endCline;
}

static void
generateMinBoundsTest(CodeContext &context, ForEachStmtNode *WRTloop,
		      const StringRect *curr_rect, const string &arr,
		      int arity,
		      TypeNode *arrayType,
		      int dim, llist<const MIVE *> *c)
{
  const string minUsed = findMin(context, WRTloop, curr_rect, arr, dim, c);
  const string minOfArray = rectMin(arr + ".domain", dim, arity);
  generateBoundsAssert(context, minUsed + " >= " + minOfArray,
		       arr, arrayType, dim, WRTloop,
		       minUsed, " >= ", minOfArray);
  if (DEBUG_BC) 
    cout << "assert(" << minUsed << " >= " << minOfArray << ");" << endl;
}

static void
generateMaxBoundsTest(CodeContext &context, ForEachStmtNode *WRTloop,
		      const StringRect *curr_rect, const string &arr,
		      int arity,
		      TypeNode *arrayType,
		      int dim, llist<const MIVE *> *c)
{
  for (ListIterator<const MIVE *> i(c); !i.isDone(); i.next())
    *i = (*i)->negate();
  const string maxUsed =
    "-(" + findMin(context, WRTloop, curr_rect, arr, dim, c) + ")";
  /* Warning: assumes that end - 1 is the last point in a rectdomain,
     regardless of its stride.  This echoes the implementation of 
     max() in tiRectDomainN.java. */
  const string maxOfArray = rectMax(arr + ".domain", dim, arity);
  generateBoundsAssert(context, maxUsed + " <= " + maxOfArray,
		       arr, arrayType, dim, WRTloop,
		       maxUsed, " <= ", maxOfArray);
  if (DEBUG_BC) 
    cout << "assert(" << maxUsed << " <= " << maxOfArray << ");" << endl;
}

/* Generate bounds checks for a dimension of a particular array that
   is used in a particular foreach loop.  The uses of array that we
   need to check are given by the MIVEset s.  The idea is to notice
   when certain accesses must be greater than or equal to others, in which
   case we can reduce the number of checks we need at run time.  E.g.,
   p + 1 is always bigger than p, so p + 1 need only be considered as a
   possible maximum, while p need only be considered as a possible min.
   In addition to max and min testing, we do stride testing if needed.
*/
static void
generateBoundsChecks(CodeContext &context, ForEachStmtNode *WRTloop,
		     const StringRect *curr_rect, const string &arr, int arity,
		     TypeNode *arrayType,
		     const MIVEset *s, int dim, bool needStrideTest)
{
  llist<const MIVE *> *c, *l = MIVEset_to_list(s);
  c = mightBeMinimum(l, dim);
  generateMinBoundsTest(context, WRTloop, curr_rect,
			arr, arity, arrayType, dim, c);
  c = mightBeMaximum(l, dim);
  generateMaxBoundsTest(context, WRTloop, curr_rect,
			arr, arity, arrayType, dim, c);
  if (needStrideTest)
    generateStrideTest(context, WRTloop, 
		       arr, arity, arrayType, dim, l);
}

/* Generate bounds checks for a particular array that is used in a
   particular foreach loop.  ad is the var decl for the array. */
static void generateBoundsChecks(CodeContext &context, 
				 ForEachStmtNode *WRTloop,
				 const StringRect *curr_rect,
				 ArrayAccessSet *arrayAccesses,
				 map_int_to_treeSet &provablyUnitStride,
				 const TreeNode *ad)
{
  assert(ad != NULL);
  TreeNode *array = arrayAccesses->use(ad)->array();
  TypeNode *arrayType = array->type();
  int arity = arrayType->tiArity();
  const string arr = array->emitExpression(context);
  const MIVEset *s = arrayAccesses->allMIVEs(array);
  if (DEBUG_BC) {
    cout << "generateBoundsChecks(" << arr << "); s:" << endl;
    for (MIVEset::const_iterator i = s->begin(); i != s->end(); ++i) {
      cout << "    ";
      SHOWMIVE(*i);
      cout << endl;
    }
  }
  for (int i = 0; i < arity; i++)
    generateBoundsChecks(context, WRTloop, curr_rect, arr, arity, arrayType,
			 s, i, !contains(provablyUnitStride[i], ad));
}

void generateBoundsChecks(CodeContext &context, 
			  ForEachStmtNode *WRTloop,
			  const StringRect *curr_rect,
			  ArrayAccessSet *arrayAccesses,
			  map_int_to_treeSet &provablyUnitStride)
{
  const treeSet *s = arrayAccesses->SRarrays();
  if (s != NULL && !s->empty()) {
    context.pushNoLineDirectives();
    context << "#if BOUNDS_CHECKING" << endCline;
    {
      CodeContext subcontext(context);
      for (treeSet::const_iterator i = s->begin(); i != s->end(); ++i)
	generateBoundsChecks(subcontext, WRTloop, curr_rect, arrayAccesses,
			     provablyUnitStride, *i);
    }
    context << "#endif" << endCline;
    context.popNoLineDirectives();
    reset_buildexpr();
    delete s;
  }
}

static void generateUnitStrideCheck(CodeContext &context,
				    ForEachStmtNode *WRTloop,
				    TreeNode *array, int i)
{
  const string arr = array->emitExpression(context);
  TypeNode *type = array->type();
  int arity = type->tiArity();
  const string stride = rectStride(arr + ".domain", i, arity);
  generateBoundsAssert(context, stride + " == 1", arr, type,
		       i, WRTloop, stride, ", the array stride, "
		       "should be 1 for this loop to make sense");
}

void generateUnitStrideCheck(CodeContext &context, 
			     ForEachStmtNode *WRTloop,
			     ArrayAccessSet *arrayAccesses,
			     map_int_to_treeSet &provablyUnitStride)
{
  bool none = true;

  context.pushNoLineDirectives();
  for (map_int_to_treeSet::iterator i = provablyUnitStride.begin();
       i != provablyUnitStride.end();
       i++) {
    int dim = (*i).first;
    treeSet *s = (*i).second;
    for (treeSet::const_iterator j = s->begin(); j != s->end(); j++) {
      TreeNode *ad = (TreeNode *) *j;
      if (none) {	 
	context << "  /*** begin verification of unit strides ***/" <<
	  endCline << "#if BOUNDS_CHECKING" << endCline;
	none = false;
      }
      generateUnitStrideCheck(context, WRTloop,
			      arrayAccesses->use(ad)->array(), dim);
    }
  }
  if (!none)
    context << "#endif" << endCline <<
      "  /*** end verification of unit strides ***/" << endCline;
  context.popNoLineDirectives();
}