/*

  $Id$

  Copyright 1989-2016 MINES ParisTech

  This file is part of PIPS.

  PIPS is free software: you can redistribute it and/or modify it
  under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  any later version.

  PIPS is distributed in the hope that it will be useful, but WITHOUT ANY
  WARRANTY; without even the implied warranty of MERCHANTABILITY or
  FITNESS FOR A PARTICULAR PURPOSE.

  See the GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with PIPS.  If not, see <http://www.gnu.org/licenses/>.

*/
/*
 * Expression normalization
 *
 * Expressions are stored in two different ways: a standard expression
 * tree (syntax) and, when possible, an affine expression
 * (normalized_linear). The purpose of normalize.c is to derive the affine
 * expression from the expression tree, when an affine form exists.
 *
 * Expressions are declared as Newgen objects by these two lines:
 *
 * expression = syntax x normalized ;
 * normalized = linear:Pvecteur + complex:unit ;
 *
 * The expression tree, often generated by the parsers, is stored in
 * "syntax". The affine equivalent expression is stored in the linear
 * field of "normalized". If no equivalent affine expression exists,
 * "normalized" is of kind "complex".
 *
 * The data structure "Pvecteur" is imported from the Linear
 * library. See the Section "Expressions" in ri.tex.
 *
 * Motivation: many analysis and parallelization algorithms are based
 * on affine expressions. Rather than recomputing the affine forms
 * each time they are needed, they are store once and for all.
 *
 * Consistency: when an expression is modified, its normalized field
 * must be invalidated.
 *
 * Most of the functions here must be changed to static
 */
#ifdef HAVE_CONFIG_H
    #include "pips_config.h"
#endif
#include <stdio.h>
#include <string.h>
#include <limits.h>

#include "linear.h"

#include "genC.h"
#include "ri.h"
#include "misc.h"

#include "ri-util.h"
#include "properties.h"

#include "operator.h"

/* this function shouldn't be called.
 * Use macro NORMALIZE_EXPRESSION(e) instead.
 */

static normalized _NormalizeExpression(expression e)
{
	return NormalizeSyntax(expression_syntax(e));
}

normalized NormalizeExpression(expression e)
{
    normalized n;

    if (expression_normalized(e) != normalized_undefined)
	user_warning("NormalizeExpression",
		     "expression is already normalized\n");

    n = _NormalizeExpression(e);
    // expression_normalized(e) = n;
    return(n);
}

normalized NormalizeSyntax(syntax s)
{
    normalized n=normalized_undefined;

    switch (syntax_tag(s)) {
      case is_syntax_reference:
	n = NormalizeReference(syntax_reference(s));
	break;
      case is_syntax_range:
	n = make_normalized_complex();
	break;
      case is_syntax_call:
	n = NormalizeCall((syntax_call(s)));
	break;
    case is_syntax_cast:
      n = NormalizeCast(syntax_cast(s));
      break;
    case is_syntax_sizeofexpression:
	n = make_normalized_complex();
      break;
    case is_syntax_subscript:
	n = make_normalized_complex();
      break;
    case is_syntax_application:
	n = make_normalized_complex();
      break;
    case is_syntax_va_arg:
	n = make_normalized_complex();
      break;
      default:
	pips_internal_error("cas default");
    }

    return(n);
}

normalized NormalizeCast(cast c)
{
  normalized n=normalized_undefined;
   type ct = cast_type(c);
   expression cexp = cast_expression(c);
   type cexpt = expression_to_type(cexp);

   if (type_equal_p(ct, cexpt))
     n = NormalizeExpression(cexp);
   else
     n = make_normalized_complex();
   free_type(cexpt);
   return(n);
}

normalized NormalizeCall(call c)
{
    normalized n=normalized_undefined;
    entity f = call_function(c);
    value v = entity_initial(f);

    switch (value_tag(v)) {
      case is_value_intrinsic:
	n = NormalizeIntrinsic(f, call_arguments(c));
	break;
      case is_value_constant:
	n = NormalizeConstant((value_constant(v)));
	break;
      case is_value_symbolic:
        if(get_bool_property("EVAL_SYMBOLIC_CONSTANT"))
          n = NormalizeConstant((symbolic_constant(value_symbolic(v))));
        else
          n= make_normalized_linear( vect_new(f, VALUE_ONE) );
        break;
      case is_value_unknown:
      case is_value_code:
	n = make_normalized(is_normalized_complex, UU);
	break;
      default:
	pips_internal_error("case default");
    }

    return(n);
}

normalized NormalizeConstant(constant c)
{
    return((constant_int_p(c)) ?
	   make_normalized_linear(vect_new(TCST, constant_int(c))) :
	   make_normalized_complex());
}

normalized NormalizeReference(reference r)
{
  normalized n = normalized_undefined;
  entity e = reference_variable(r);
  type t = entity_type(e);

  pips_assert("constant term ore is an entity",
	      entity_domain_number(e)==entity_domain);

  if (!type_variable_p(t)) {
    if(type_functional_p(t)) {
      // FI: we might not want to keep the warning for C code...
      pips_user_warning("Reference to function \"%s\" cannot be normalized.\n"
			"Is it an undeclared variable?\n",
			entity_user_name(e));
      n = make_normalized(is_normalized_complex, UU);
    }
    else {
      pips_user_warning("Reference to entity \"%s\" cannot be normalized because of its type tag %d\n",
			entity_name(e), type_tag(t));
      pips_user_error("Referenced entity should be a variable!\n");
    }
  }
  else {
    Variable v = (Variable) e;
    Value val = VALUE_ONE;

    /* SG is there any good reason to exclude pointer arithmetic ?*/
    n = (entity_integer_scalar_p(e) || 
            entity_enum_variable_p(e) ||
            ( entity_pointer_p(e) && ENDP(reference_indices(r))) ) ?
      make_normalized(is_normalized_linear,
		      vect_new(v, val)) :
      make_normalized(is_normalized_complex, UU);
  }

  return n;
}

normalized NormalizeIntrinsic(entity e, list la)
{
  normalized n;

  if (! top_level_entity_p(e))
    return(make_normalized(is_normalized_complex, UU));

  if (ENTITY_UNARY_MINUS_P(e)) {
    n = _NormalizeExpression(EXPRESSION(CAR(la)));

    if (normalized_complex_p(n))
      return(n);

    vect_chg_sgn(normalized_linear(n));
  }
  else if (ENTITY_MINUS_P(e) || ENTITY_MINUS_C_P(e) || ENTITY_PLUS_P(e) || ENTITY_PLUS_C_P(e)) {
    normalized ng, nd;

    ng = _NormalizeExpression(EXPRESSION(CAR(la)));
    if (normalized_complex_p(ng))
      return(ng);

    nd = _NormalizeExpression(EXPRESSION(CAR(CDR(la))));
    if (normalized_complex_p(nd)) {
      FreeNormalized(ng);
      return(nd);
    }

    n = (ENTITY_PLUS_P(e) || ENTITY_PLUS_C_P(e)) ?
      make_normalized(is_normalized_linear,
		      vect_add(normalized_linear(ng),
			       normalized_linear(nd))) :
      make_normalized(is_normalized_linear,
		      vect_substract(normalized_linear(ng),
				     normalized_linear(nd)));

    FreeNormalized(ng);
    FreeNormalized(nd);
  }
  else if (ENTITY_MINUS_UPDATE_P(e) || ENTITY_PLUS_UPDATE_P(e)) {
    /* There is no point in normalizing ng since this cannot be
       expressed by a normalized expression */
    //normalized nd;

    (void) _NormalizeExpression(EXPRESSION(CAR(CDR(la))));
    return make_normalized_complex();
  }
  else if (ENTITY_MULTIPLY_P(e)) {
    normalized ng, nd;
    int val;

    ng = _NormalizeExpression(EXPRESSION(CAR(la)));
    if (normalized_complex_p(ng))
      return(ng);

    nd = _NormalizeExpression(EXPRESSION(CAR(CDR(la))));
    if (normalized_complex_p(nd)) {
      FreeNormalized(ng);
      return(nd);
    }

    if (EvalNormalized(nd, &val)) {
      FreeNormalized(nd);
      normalized_linear(n = ng) =
	vect_multiply(normalized_linear(ng), val);
    }
    else if (EvalNormalized(ng, &val)) {
      FreeNormalized(ng);
      normalized_linear(n = nd) =
	vect_multiply(normalized_linear(nd), val);
    }
    else {
      FreeNormalized(ng);
      FreeNormalized(nd);
      return(make_normalized(is_normalized_complex, UU));
    }
  }
  else if((ENTITY_MIN_P(e) || ENTITY_MIN0_P(e)) && gen_length(la) == 2) {
    n = binary_to_normalized(la, MINIMUM);
  }
  else if((ENTITY_MAX_P(e) || ENTITY_MAX0_P(e)) && gen_length(la) == 2) {
    n = binary_to_normalized(la, MAXIMUM);
  }
  else if(ENTITY_MODULO_P(e)) {
    n = binary_to_normalized(la, MOD);
  }
  else if(ENTITY_DIVIDE_P(e)) {
    n = binary_to_normalized(la, SLASH);
  }
  else if(ENTITY_POWER_P(e)) {
    n = binary_to_normalized(la, POWER);
  }
  else {
    return(make_normalized(is_normalized_complex, UU));
  }

  return(n);
}

normalized binary_to_normalized(list la, int op)
{
    normalized ng;
    normalized nd;
    normalized n;
    int val1;
    int val2;
    int val = 0; /* initialized to please gcc */

    pips_assert("binary_to_normalize", gen_length(la) == 2);

    ng = _NormalizeExpression(EXPRESSION(CAR(la)));
    if (normalized_complex_p(ng))
	return(ng);

    nd = _NormalizeExpression(EXPRESSION(CAR(CDR(la))));
    if (normalized_complex_p(nd)) {
	FreeNormalized(ng);
	return(nd);
    }

    if (EvalNormalized(nd, &val2) && EvalNormalized(ng, &val1)) {
	bool succeed = true;

	FreeNormalized(nd);
	FreeNormalized(ng);
	switch(op) {
	case MINIMUM:
	    val = MIN(val1, val2);
	    break;
	case MAXIMUM:
	    val = MAX(val1, val2);
	    break;
	case MOD:
	    /* FI: the C operator is different from the Fortran operator
	     * for non-positive arguments.
	     */
	    if(val2==0) {
		user_error("binary_to_normalize",
			   "0 divide in modulo evaluation\n");
	    }
	    else {
		val = val1%val2;
	    }
	    break;
	case SLASH:
	    /* FI: the C operator is different from the Fortran operator
	     * for non-positive arguments.
	     */
	    if(val2==0) {
		user_error("binary_to_normalize",
			   "0 divide\n");
	    }
	    else {
		val = val1/val2;
	    }
	    break;
	case POWER:
	    if(val2<0) {
		succeed = false;
	    }
	    else {
		val = ipow(val1,val2);
	    }
	    break;
	default:
	    pips_internal_error("Unknown binary operator %d", op);
	}
	if(succeed) {
	    n = make_normalized(is_normalized_linear,
				vect_new(TCST, val));
	}
	else {
	    n = make_normalized(is_normalized_complex, UU);
	}
    }
    else {
	FreeNormalized(ng);
	FreeNormalized(nd);
	n = make_normalized(is_normalized_complex, UU);
    }
    return n;
}

bool EvalNormalized(n, pv)
normalized n;
int *pv;
{
    if (normalized_linear_p(n)) {
	Pvecteur v = (Pvecteur) normalized_linear(n);
	if (vect_size(v) == 1 && var_of(v) == TCST) {
	    *pv = VALUE_TO_INT(val_of(v));
	    return(true);
	}
    }

    return(false);		
}

void FreeNormalized(n)
normalized n;
{
    /* FI: theoretically, free_normalized() performs the next three lines... */
    if (normalized_linear_p(n)) {
	vect_rm(normalized_linear(n));
	normalized_linear_(n) = NULL;
    }

    free_normalized(n);
    /* gen_free(n); */
}

void free_expression_normalized(e)
expression e;
{
    normalized n = normalized_undefined;

    if((n = expression_normalized(e)) != normalized_undefined) {
	FreeNormalized(n);
	expression_normalized(e) = normalized_undefined;
    }
}

/* void unnormalize_expression(expression exp): puts all the normalized
 * field of expressions in "st" to undefined and does the unnormalization recursively
 *
 * This is very useful when you combine expressions. It prohibits
 * unnormalized expressions with normalized sub-expressions.
 *
 * FI: any chunk* can be passed;
 * this function could be applied to an expression
 */
void unnormalize_expression(void * st)
{
    gen_multi_recurse(st,
		      expression_domain,
		      gen_true,
		      free_expression_normalized,
		      NULL);
}

Pvecteur expression_to_affine(expression e)
{
    normalized n;
    Pvecteur v;

    /* As long as VECTEUR_UNDEFINED is not different from VECTEUR_NUL
       this routine cannot be used safely; either 0 will be considered
       not linear or every non linear expression will be equal to 0 */

    /* should it also perform the conversion from variable entities
       to new value entities? */

    if(expression_normalized(e)==normalized_undefined)
	n = _NormalizeExpression(e);
    else
	n = expression_normalized(e);

    if(normalized_linear_p(n))
	v = vect_dup((Pvecteur) normalized_linear(n));
    else
	v = VECTEUR_UNDEFINED;

    return v;
}


/* -----------------------------------------------------------
 *
 *    New Stuff to normalize all expressions - bottom-up
 *
 *    FC 09/06/94
 */

static bool normalized_constant_p(normalized n, int *pv)
{
    if (normalized_linear_p(n))
    {
	Pvecteur v = normalized_linear(n);
	int length = vect_size(v);
	
	if (length==0)
	{
	    *pv=0;
	    return true;
	}
	else if (length==1 && var_of(v)==TCST)
	{
	  *pv=VALUE_TO_INT(val_of(v));
	  return true;
	}
    }

    return false;
}

static normalized
normalize_intrinsic(
    entity f,
    list la)
{
    bool minus;
	
    if (! top_level_entity_p(f))
	return(make_normalized(is_normalized_complex, UU));

    if (ENTITY_UNARY_MINUS_P(f))
    {
	Pvecteur tmp = VECTEUR_NUL;
	normalized n = expression_normalized(EXPRESSION(CAR(la)));

	return(normalized_complex_p(n) ?
	       make_normalized(is_normalized_complex, UU) :
	       make_normalized(is_normalized_linear,
		   (vect_chg_sgn(tmp=vect_dup(normalized_linear(n))), tmp)));
    }
    /* else */
    if ((minus=ENTITY_MINUS_P(f)) || (ENTITY_PLUS_P(f)))
    {
	normalized
	    n1 = expression_normalized(EXPRESSION(CAR(la))),
	    n2 = expression_normalized(EXPRESSION(CAR(CDR(la))));
	Pvecteur (*operation)() = minus ? vect_substract : vect_add;

	assert(!normalized_undefined_p(n1) && !normalized_undefined_p(n2));

	if (normalized_complex_p(n1) || normalized_complex_p(n2))
	    return(make_normalized(is_normalized_complex, UU));
	/* else */
	return(make_normalized(is_normalized_linear,
			       operation(normalized_linear(n1),
					 normalized_linear(n2))));
    }
    /* else */
    if (ENTITY_MULTIPLY_P(f))
    {
	normalized
	    n1 = expression_normalized(EXPRESSION(CAR(la))),
	    n2 = expression_normalized(EXPRESSION(CAR(CDR(la))));
	bool b1, b2;
	int i1, i2;
	Pvecteur v;

	if (normalized_complex_p(n1) || normalized_complex_p(n2))
	    return(make_normalized(is_normalized_complex, UU));
	/* else */
	b1 = normalized_constant_p(n1, &i1),
	b2 = normalized_constant_p(n2, &i2);

	if (! (b1 || b2)) return(make_normalized(is_normalized_complex, UU));

	/* else multiply (caution: vect_multiply does not allocate...)
	 */
	v = vect_dup(b1 ? normalized_linear(n2) : normalized_linear(n1));

	return(make_normalized(is_normalized_linear,
			       vect_multiply(v, b1 ? i1 : i2)));
    }
    /* else */
    return(make_normalized(is_normalized_complex, UU));
}

static normalized
normalize_constant(constant c)
{
    return((constant_int_p(c)) ?
	   make_normalized(is_normalized_linear,
			   vect_new(TCST, constant_int(c))) :
	   make_normalized(is_normalized_complex, UU));
}

normalized
normalize_reference(reference r)
{
    entity var = reference_variable(r);

    pips_assert("The entity var is a variable", entity_variable_p(var));

    return(entity_integer_scalar_p(var) ?
	   make_normalized(is_normalized_linear, vect_new((Variable) var, 1)) :
	   make_normalized(is_normalized_complex, UU));
}

static normalized
normalize_call(call c)
{
    normalized n = normalized_undefined;
    entity f = call_function(c);
    value v = entity_initial(f);
    tag	t = value_tag(v);

    switch (t)
    {
    case is_value_intrinsic:
	n = normalize_intrinsic(f, call_arguments(c));
	break;
      case is_value_constant:
	n = normalize_constant(value_constant(v));
	break;
      case is_value_symbolic:
	n = normalize_constant(symbolic_constant(value_symbolic(v)));
	break;
      case is_value_unknown:
      case is_value_code:
	n = make_normalized(is_normalized_complex, UU);
	break;
      default:
	pips_internal_error("unexpected value tag (%d)", t);
    }

    return(n);
}

/* Look for affine expressions and encode them as vectors when
   possible */
static void norm_all_rewrite(expression e)
{
  syntax s = expression_syntax(e);
  tag t = syntax_tag(s);

  if (normalized_undefined_p(expression_normalized(e))) {
    normalized n = normalized_undefined;

    switch(t) {
    case is_syntax_range:
      n = make_normalized(is_normalized_complex, UU);
      break;
    case is_syntax_reference:
      n = normalize_reference(syntax_reference(s));
      break;
    case is_syntax_call:
      n = normalize_call(syntax_call(s));
      break;
    case is_syntax_cast:
    case is_syntax_sizeofexpression:
    case is_syntax_subscript:
    case is_syntax_application:
    case is_syntax_va_arg:
      n = make_normalized(is_normalized_complex, UU);
      break;
    default:
      n = normalized_undefined;
      pips_internal_error("undefined syntax tag (%d)", t);
    }
    expression_normalized(e) = n;
  }
}

void normalize_all_expressions_of(void * obj)
{
    gen_multi_recurse(obj, expression_domain, gen_true, norm_all_rewrite,
		      NULL);
}

/* ---------------------------------------------------------------------
 *
 *   the first expressions encountered are normalized
 */

static bool normalize_first_expressions_filter(expression e)
{
    if (normalized_undefined_p(expression_normalized(e)))
    {
	// FI: to avoid cycles betwen librairies ri-util and prettyprint
	/* normalized */
	/*     n = NORMALIZE_EXPRESSION(e); */
	/* ifdebug(8) */
	/*     fprintf(stderr, "[NormExpr] result (%p)\n", n), */
	/*     print_expression(e); */
    }

    return false;
}

void normalize_first_expressions_of(void * obj)
{
    gen_multi_recurse(obj,
		      expression_domain,
		      normalize_first_expressions_filter,
		      gen_null,
		      NULL);
}

/*   that is all
 */