normalize.c

Go to the documentation of this file.

/*
 
  $Id: normalize.c 23065 2016-03-02 09:05:50Z coelho $
 
  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
 */