/*

  $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/>.

*/
#ifdef HAVE_CONFIG_H
    #include "pips_config.h"
#endif
#include <stdio.h>
#include "genC.h"
#include "database.h"
#include "resources.h"
#include "misc.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "pipsdbm.h"
#include "transformations.h"
#include "locality.h"

#define DEFAULT_INT_PREFIX 	"I_"
#define DEFAULT_FLOAT_PREFIX 	"F_"
#define DEFAULT_LOGICAL_PREFIX 	"L_"
#define DEFAULT_COMPLEX_PREFIX	"C_"
#define DEFAULT_STRING_PREFIX	"S_" 
#define  depth_max  40    /* La profondeur des differents  nids */
#define  st_max 40       /* Le nombre maximum de stencils q'un nid peut contenir */
#define nid_nbr 6    /* nombre de nid de la sequence */


/* La structure d'une boucle : son index et ces deux bornes */

typedef struct INFO_LOOP {    
  Variable index;
  Value upper, lower;  
} info_loop;


/* La structure d'un nid */

typedef struct NID { 
  entity tableau;       /*  le tableau en ecriture */
  Pmatrix  *st;        /* les stencils */
  info_loop *nd;       /* les boucles */ 
  int nbr_stencil;    /* nombre de stencils */
  Pmatrix delai;      /* le delai qu'on doit ajouter a ce nid */ 
  statement s;        /* le corps de ce nid */
  Value surface;      /* le volume memoire du tableau en ecriture de ce nid */
  Pmatrix coef;       /* le coefficient des fonctions d'acces  */
  Pvecteur pv_acces;     /*  */ 
  entity ref;           /*   */
  Pmatrix n;
} nid;

static Pvecteur *tiling_indice;
static int k1=0, k2=0;  /* k1 represente le nombre de nid et k2 leur profondeur */

static nid  sequen[nid_nbr]; /* la sequence de nids */

static int depth;     /* la pronfondeur des nids */

static info_loop   *merged_nest, *tiled_nest;  /* le nid fusionne */

loop loop1;       /* une copie de l'un des nids de la sequence */

entity first_array;  /* le tableau en entree */

/* J'ai ameliore la fonction make_new_scalar_variable */
/* afin de l'etendre  a des tableau   */
static entity internal_make_new_array_variable(int i, int j, entity module,
                         basic b,list lis)
{
  char *buffer;
  if(j==-1)
  asprintf(&buffer,"%s%d", "B",i);
  else 
    asprintf(&buffer,"%s%d_%d", "B",i,j);
  entity e = make_new_array_variable_with_prefix(buffer, module, b,lis);
  free(buffer);
  return e;
}

/* Compteurs des suffixes de nouvelles references */
/*
static int unique_integer_number = 0,
  unique_float_number = 0,
  unique_logical_number = 0,
  unique_complex_number = 0,
  unique_string_number = 0;
*/
/* first_turn permet de detecter le premier retour de la fonction loop_rwt()  */
/* overflow permet de detecter un debordemebnt dans l'un des nids */

static bool first_turn=false, overflow=false;


/* pour marquer si la sequence repond a nos hypotheses */

typedef enum {is_a_stencil, is_a_continue, is_a_no_stencil } contenu_t;


static bool loop_flt(loop l )
{  
  range range1;
  expression lower, upper;
  normalized norm1, norm2;
  Variable  index;
  Pvecteur pv1,pv2;
  if( ! first_turn )        /* la premiere boucle d'un nid donne */
    {
      loop1=copy_loop(l);
      first_turn = true; 
      /* allouer de la memoire pour les differentes boucles de ce nid */
      sequen[k1].nd= (struct INFO_LOOP  *)malloc(depth_max *sizeof(struct INFO_LOOP));
      /* allouer de la memoire pour les differents stencils  de ce nid */
      sequen[k1].st= ( Pmatrix *)malloc(st_max *sizeof(Pmatrix));
    }; 
  index =(Variable) loop_index(l);
  range1=loop_range(l);    
  lower=range_lower(range1);  /* la borne inferieure */  
  upper=range_upper(range1);  /* la borne superiere */
  normalize_all_expressions_of(lower);
  normalize_all_expressions_of(upper);
  norm1=expression_normalized(lower);
  norm2=expression_normalized(upper);
  pips_assert("normalized are linear", normalized_linear_p(norm1)&& normalized_linear_p(norm2));
  pv1= normalized_linear(norm1);
  pv2= normalized_linear(norm2); 
  sequen[k1].nd[k2].index=index;    /* stocker l'index de la boucle l */
  sequen[k1].nd[k2].lower=vect_coeff(TCST,pv1);  /* stocker sa borne inferieure */
  sequen[k1].nd[k2].upper=vect_coeff(TCST,pv2);   /* stocker sa borne superieure  */
  k2++;    /* incrementer le compteur des profondeur des nids */
  return true;
} 

static void loop_rwt(loop l, context_p context  ) 
{  
  contenu_t contenu;
  intptr_t depth;
  statement s = loop_body(l);    /* recuperer le coprs de le boucle l */
  contenu = (contenu_t) hash_get(context->contenu, s);
  depth= (intptr_t) hash_get(context->depth, s);   
  depth++;
  hash_put(context->depth,stack_head(context->statement_stack), ( void *) depth); 
  hash_put(context->contenu,stack_head(context->statement_stack), (void *) contenu  );
  if (first_turn)
    {
      first_turn=false;
      k2=0;
      k1++;
    }
}

static bool stmt_flt(statement s,context_p context )
{  
  stack_push(s, context->statement_stack); 
  return true;
}


static void stmt_rwt( statement s, context_p context)
{  
  pips_assert("true", s==s && context==context);
  stack_pop(context->statement_stack);   
}

static bool seq_flt(   )
{
  return true;
}

static void seq_rwt(sequence sq, context_p context)
{
  contenu_t contenu;
  intptr_t depth1=0, depth2=0;
  intptr_t max=0;
  int i=0;
  list l= sequence_statements(sq);
  contenu=is_a_stencil;
  hash_put(context->contenu, stack_head(context->statement_stack), (void *) contenu);
  MAP(STATEMENT, s,
  {
    contenu = (contenu_t) hash_get(context->contenu, s);
    if (i==0) depth1 = (intptr_t ) hash_get(context->depth, s);
    if (contenu ==is_a_stencil)  
      {  
	depth2= (intptr_t ) hash_get(context->depth, s);
	if (depth1!=depth2)
	  {  
	    contenu=is_a_no_stencil;
	    hash_put(context->contenu, stack_head(context->statement_stack),(void *) contenu);
	  };
	depth1 =  depth2;
      }
    else 
      {
	if ( contenu !=is_a_continue)
	  { 
	    contenu=is_a_no_stencil;
	    hash_put(context->contenu, stack_head(context->statement_stack),(void *) contenu);
	  };
      };
    if (depth2 > max) max=depth2;
    i++;
  };, l); 
  hash_put(context->depth,stack_head(context->statement_stack), (void *) max   );
} 

static bool uns_flt(   )
{
  return true;
}

static void uns_rwt( context_p context)
{  contenu_t contenu;
 
 contenu=is_a_no_stencil; 
 hash_put(context->contenu,stack_head(context->statement_stack),(void *)contenu );
 hash_put(context->depth,stack_head(context->statement_stack), ( void *) 0);  
}

static bool test_flt( )
{
  return true;
}

static void test_rwt( context_p context)
{
  contenu_t contenu;
  contenu=is_a_no_stencil; 
  hash_put(context->contenu, stack_head(context->statement_stack), (void *)contenu );
  hash_put(context->depth,stack_head(context->statement_stack), ( void *) 0);   
} 
static bool call_flt( )
{
  return true ;
}

static void call_rwt(call  ca, context_p context)
{ 
  contenu_t contenu=is_a_stencil;
  if ((strcmp(entity_name(call_function(ca)),"TOP-LEVEL:CONTINUE" )==0)||
      (strcmp(entity_name(call_function(ca)),"TOP-LEVEL:RETURN" )  ==0))
    {
      contenu=is_a_continue; 
    }
  else
    {
      if (strcmp(entity_name(call_function(ca)),"TOP-LEVEL:=")==0)
	{
	  list lis;
	  expression gauche=NULL, droite=NULL;
	  syntax stg,std;
          normalized norm;
	  Pvecteur pv;       
	  int i=0,j=0;
	  lis =call_arguments(ca);
	  MAP(EXPRESSION,exp,{  
	    if (i==0)  gauche=exp;
	    if (i==1)  droite=exp;
	    i++;
	  },lis) ; 
	  stg= expression_syntax(gauche);
	  std= expression_syntax(droite);
	  if ((syntax_reference_p(stg))&&(syntax_call_p(std))&&(i==2))
	    { 
	      reference ref;
              list lis,lis2;
	      Variable vt=NULL;
	      Pvecteur pvt;
	      Value v1;
	      ref =syntax_reference(stg);
	      lis  =reference_indices(ref);
	      i=1;
	      sequen[k1].tableau=reference_variable(ref);
	      MAP(EXPRESSION,exp,{ 
                if (k2-i >=0) {
		  vt=sequen[k1].nd[k2-i].index;
		}
                else{
		  contenu=is_a_no_stencil;
		}
		normalize_all_expressions_of(exp);
		norm=expression_normalized(exp);
		pv= normalized_linear(norm);
                pvt = vect_make(VECTEUR_NUL, vt, VALUE_ONE,
				TCST,VALUE_ZERO);
		if (!vect_equal(pvt, pv))
		  {
		    contenu=is_a_no_stencil;
		  } ;
		i++;
	      },lis) ;      
	      if (i-1!=k2)
		{
		  contenu=is_a_no_stencil;
		};
	      lis  =call_arguments( syntax_call(std));
	      j=0;
	      MAP(EXPRESSION,exp,{ 
		ref =expression_reference(exp);
		if(k1==0)
		  first_array=reference_variable(ref);
		if(k1>0)
		  {
		    if (reference_variable(ref) !=sequen[k1-1].tableau)
		      contenu=is_a_no_stencil;
		  };
		lis2  =reference_indices(ref);
		i=1;
		sequen[k1].st[j]=matrix_new(k2,1);
		MAP(EXPRESSION,exp2,{
		  if (k2-i >=0) 
		    vt=sequen[k1].nd[k2-i].index;
		  else
		    contenu=is_a_no_stencil;
		  normalize_all_expressions_of(exp2);
		  norm=expression_normalized(exp2);
		  pv= normalized_linear(norm);
		  v1=vect_coeff(TCST,pv);
		  MATRIX_ELEM(sequen[k1].st[j],k2-i+1,1)=v1;
		  pvt = vect_make(VECTEUR_NUL, vt, VALUE_ONE,
				  TCST,v1);
		  if (!vect_equal(pvt, pv)){
		    contenu=is_a_no_stencil;
		  };
		  i++; 
		},lis2) ;  
		if (i-1!=k2){
		  contenu=is_a_no_stencil; };
		j++;
	      },lis) ; 
	      sequen[k1].nbr_stencil=j;
	    }
	  else
	    {    
              contenu=is_a_no_stencil; 
	    }; 
	}
      else
	{
	  contenu=is_a_no_stencil; 
	}
    }
  hash_put(context->contenu,stack_head(context->statement_stack), (void *)contenu );
  hash_put(context->depth,stack_head(context->statement_stack), ( void *) 0);  
  sequen[k1].s= copy_statement( stack_head(context->statement_stack));
}


static void wl_rwt( context_p context)
{  
  contenu_t contenu;
  contenu=is_a_no_stencil; 
  hash_put(context->contenu,stack_head(context->statement_stack),(void *)contenu );
  hash_put(context->depth,stack_head(context->statement_stack), ( void *) 0); 
} 

/* Cette fonction retourne true si  le vecteur 'a' est lexicographiquement superieur au vecteur 'b' */
static bool lexi_sup(Pmatrix a, Pmatrix b)
{
  int i;
  for (i=1;i<=depth;i++)
    {
      if (MATRIX_ELEM(a,i,1) >MATRIX_ELEM(b,i,1))
	return true;
      if (MATRIX_ELEM(a,i,1) < MATRIX_ELEM(b,i,1))
	return false;
    }
  return false;
} 

/* Cette fonction trie un tableau de stencil d'un  nid donne. st est le tableau 
   de stencils et length sa taille */

static void  trier(Pmatrix *st,int length)
{
  Value    temp;
  int   i, j,k;
  for (i=0;i<=length-2;i++)
    for(j=i+1;j<=length-1;j++)
      {
	if (lexi_sup(st[i],st[j]))
	  {
	    for (k=1;k<=depth;k++)
	      {   
		temp= MATRIX_ELEM(st[j],k,1);
		MATRIX_ELEM(st[j],k,1)=  MATRIX_ELEM(st[i],k,1);
		MATRIX_ELEM(st[i],k,1)=temp;
	      };
	  };
      };
}

/* Cette fonction calcule les delais qu'on doit ajouter aux differents nids */
 
static void compute_delay_merged_nest ()
{
  int i;
  for (i=k1-1;i>=0;i--)
    {
      sequen [i].delai=matrix_new(depth,1);
      if (i==k1-1)  matrix_nulle(sequen [i].delai);   /* le delaie  du dernier est le vecteur nul */
      else
	matrix_substract(sequen [i].delai, sequen [i+1].delai,   
			 sequen[i+1].st[sequen[i+1].nbr_stencil-1]);
      /*d_k=d_{k+1} - plus grand vecteur stencil du nid  k+1*/
    }
}
 
static void compute_delay_tiled_nest ()
{
  int i,j,k;
  Pmatrix max_st=matrix_new(depth,1);
  
  for (i=k1-1;i>=0;i--)
    {
      sequen [i].delai=matrix_new(depth,1);
      if (i==k1-1)  matrix_nulle(sequen [i].delai);   /* le delaie  du dernier est le vecteur nul */
      else
	{  
	  for(k=0;k<=depth-1;k++)
	    {
	      Value val;
	      val=MATRIX_ELEM(sequen[i+1].st[0],k+1,1);
	      for (j=1;j<=sequen[i+1].nbr_stencil-1;j++)
	      {
		if ( MATRIX_ELEM(sequen[i+1].st[j],k+1,1)>val)
		  val=MATRIX_ELEM(sequen[i+1].st[j],k+1,1);
		
	      };
	      MATRIX_ELEM(max_st,k+1,1)=val;
            };
	  matrix_substract(sequen [i].delai, sequen [i+1].delai, max_st);
	}
   
      /*d_k=d_{k+1} - plus grand vecteur stencil du nid  k+1*/
    }
  
}


/* Cette fonction calcule les bornes du nid fusionne */
static void compute_bound_merged_nest ()
{
  int i,j;
  merged_nest= (struct INFO_LOOP  *)malloc(depth *sizeof(struct INFO_LOOP));
  for(j=0;j<=depth-1;j++)
    {
      merged_nest[j].lower =sequen[0].nd[j].lower+MATRIX_ELEM( sequen[0].delai,j+1,1);
      merged_nest[j].upper=sequen[0].nd[j].upper+MATRIX_ELEM( sequen[0].delai,j+1,1);
      for (i=1;i<=k1-1;i++)
       {
	 if( merged_nest[j].lower > sequen[i].nd[j].lower+MATRIX_ELEM( sequen[i].delai,j+1,1)) 
	   merged_nest[j].lower =sequen[i].nd[j].lower+MATRIX_ELEM( sequen[i].delai,j+1,1 );
	 if( merged_nest[j].upper <sequen[i].nd[j].upper+MATRIX_ELEM( sequen[i].delai,j+1,1))
	   merged_nest[j].upper=sequen[i].nd[j].upper+MATRIX_ELEM( sequen[i].delai,j+1,1);
       };
    } 
}
static void compute_bound_tiled_nest ()
{
  int i,j;
  
  tiled_nest= (struct INFO_LOOP  *)malloc(depth *sizeof(struct INFO_LOOP));
  for(j=0;j<=depth-1;j++)
    {
      Value val;
      tiled_nest[j].lower =sequen[0].nd[j].lower+MATRIX_ELEM( sequen[0].delai,j+1,1);
      tiled_nest[j].upper=sequen[0].nd[j].upper+MATRIX_ELEM( sequen[0].delai,j+1,1);
      for (i=1;i<=k1-1;i++)
       {
	 if( tiled_nest[j].lower > sequen[i].nd[j].lower+MATRIX_ELEM( sequen[i].delai,j+1,1)) 
	   tiled_nest[j].lower =sequen[i].nd[j].lower+MATRIX_ELEM( sequen[i].delai,j+1,1 );
	 if( tiled_nest[j].upper <sequen[i].nd[j].upper+MATRIX_ELEM( sequen[i].delai,j+1,1))
	   tiled_nest[j].upper=sequen[i].nd[j].upper+MATRIX_ELEM( sequen[i].delai,j+1,1);
       };
      val =value_uminus(tiled_nest[j].lower);
      tiled_nest[j].lower =value_plus(tiled_nest[j].lower,val);
      tiled_nest[j].upper =value_plus(tiled_nest[j].upper,val);
      for (i=0;i<=k1-1;i++)
	MATRIX_ELEM(sequen[i].delai,j+1,1)=value_plus( MATRIX_ELEM(sequen[i].delai,j+1,1),val);
       

    } 
 
}



/* cette fonction donne le code fusionne */
static statement  fusion()
{ 
  int i,j;
  list lis=NULL;
  instruction ins;  
  sequence seq=NULL;
  statement s;
  loop ls=NULL;
  /* calculer les delais des differents nis */
  compute_delay_merged_nest();
  /* calculer les bornes du nid fusionne */
  compute_bound_merged_nest ();
  /* on construit la liste des instructions qui vont former le corps du nid fusionne */
  for (i=k1-1;i>=0;i--)
    {
      expression e1,e2,e,gauche=NULL,droite=NULL,delai_plus;
      test t;
      call c;
      int m;
      Pvecteur pv;
      e1=ge_expression(entity_to_expression ((entity)sequen[i].nd[0].index),
		       Value_to_expression( value_plus(sequen[i].nd[0].lower,
						       MATRIX_ELEM( sequen[i].delai,1,1))));
      e2=le_expression(entity_to_expression ((entity)sequen[i].nd[0].index),
		       Value_to_expression( value_plus(sequen[i].nd[0].upper,
						       MATRIX_ELEM( sequen[i].delai,1,1))));
      if (value_eq( value_plus(sequen[i].nd[0].lower,
			       MATRIX_ELEM( sequen[i].delai,1,1)),merged_nest[0].lower))
	{
	  if (value_eq( value_plus(sequen[i].nd[0].upper,
				   MATRIX_ELEM( sequen[i].delai,1,1)),merged_nest[0].upper)) 
	    e=NULL;
	  else
	    e=e2;
	}
      else
	{
	  if (value_eq( value_plus(sequen[i].nd[0].upper,
				   MATRIX_ELEM( sequen[i].delai,1,1)),merged_nest[0].upper)) 
	    e=e1;
	  else
	    e=and_expression(e1,e2);
	};
      for(j=0;j<=depth-1;j++)
	{
	  if (j>=1) 
	    {
	      e1=ge_expression(entity_to_expression((entity)sequen[i].nd[j].index),
			       Value_to_expression(value_plus(sequen[i].nd[j].lower,
							      MATRIX_ELEM( sequen[i].delai,j+1,1))));
	      e2=le_expression(entity_to_expression ((entity)sequen[i].nd[j].index),
			       Value_to_expression( value_plus(sequen[i].nd[j].upper,
							       MATRIX_ELEM( sequen[i].delai,j+1,1))));
	      if (value_eq( value_plus(sequen[i].nd[j].lower,
				       MATRIX_ELEM( sequen[i].delai,j+1,1)),merged_nest[j].lower))
		{
		  if (!value_eq( value_plus(sequen[i].nd[j].upper,
					    MATRIX_ELEM( sequen[i].delai,j+1,1)),merged_nest[j].upper)) 
		    {
		      if (e==NULL)
			e=e2;
		      else
			e=and_expression(e,e2);
		    };
		}
	      else
		{
		  if (value_eq( value_plus(sequen[i].nd[j].upper,
					   MATRIX_ELEM( sequen[i].delai,j+1,1)),merged_nest[j].upper)) 
		    {
		      if (e==NULL)
			e=e1;
		      else
			e=and_expression(e,e1);
		    }
		  else
		    {
		      e1=and_expression(e1,e2);
		      if(e==NULL)
			e=e1;
		      else
			e=and_expression(e,e1);
		    }
		};
	    };
	  c= instruction_call(statement_instruction((sequen[i].s )));
	  m=0;
	  MAP(EXPRESSION,exp,{  
	    if (m==0)  gauche=exp;
	    if (m==1)  droite=exp;
	    m++;
	  },call_arguments(c)) ;
	  pv = vect_make(VECTEUR_NUL, sequen[i].nd[j].index, VALUE_ONE,
			 TCST,value_uminus(MATRIX_ELEM(sequen[i].delai,j+1,1)));
	  delai_plus=Pvecteur_to_expression(pv);
      replace_entity_by_expression(gauche,(entity) sequen[i].nd[j].index,delai_plus);
      FOREACH(EXPRESSION,exp,call_arguments( syntax_call(expression_syntax(droite))))
          replace_entity_by_expression(exp,(entity) sequen[i].nd[j].index,delai_plus);
	};
      if (e==NULL)
	s=sequen[i].s;
      else
	{
	  t= make_test(e,sequen[i].s,make_block_statement(NIL));
	  s=test_to_statement(t);
	};
      if(i==k1-1)   lis=CONS(STATEMENT,s,NIL);
      else      lis=CONS(STATEMENT,s,lis);
    };
  seq= make_sequence(lis);
  ins= make_instruction_sequence(seq);
  s= instruction_to_statement(ins);
  ls=loop1;
  for(j=0;j<=depth-1;j++)
    {
      range range1;
      range1=loop_range(ls); 
      range_lower(range1)=int_to_expression(merged_nest[j].lower);
      range_upper(range1)= int_to_expression(merged_nest[j].upper);
      if  (j!=depth-1) ls=instruction_loop(statement_instruction(loop_body(ls)));
      else loop_body(ls)=s;
    };
  s=loop_to_statement(loop1);
  return s;
} 

/*ON construit la coifficients des fonctions d'acces */
/*                   ->             ->                      */
/* si par exemple f( i )= (N, 1)^t( i- (1,1)^t) alors p= (N, 1)^t */
static void cons_coef(Pmatrix p, int nid)
{
  int i;
  Value temp;
  for(i=depth;i>=1 ;i--)
    {
      if (i==depth) MATRIX_ELEM(p,1,i)=1;
      else  
	{
	  temp= value_minus(sequen[nid].nd[i].upper,sequen[nid].nd[i].lower);
	  temp=value_plus(temp,VALUE_ONE);
	  MATRIX_ELEM(p,1,i)=  value_direct_multiply( MATRIX_ELEM(p,1,i+1),temp );
	} 
    }
}
/* On  construit  la foction d'acces  */
 /*                  ->             ->                        ->      */
/* si par exemple f( i )= (N, 1)^t( i- (1,1)^t) alors  pv= f( i ) */

static Pvecteur buffer_acces(int nid )
{
  Pvecteur pv=NULL,tmp;
  int j;
  for(j=0;j<=depth-1;j++)
    {
      if(j==0) 
	pv=vect_make(VECTEUR_NUL,sequen[nid].nd[j].index,MATRIX_ELEM(sequen[nid].coef,1,j+1), 
		     TCST,value_uminus(value_direct_multiply(MATRIX_ELEM(sequen[nid].coef,1,j+1),
		     value_plus( sequen[nid].nd[j].lower,
				 MATRIX_ELEM( sequen[nid].delai,j+1,1 ) ))));
      else 
	{
          tmp =pv;
	  pv = vect_make(tmp,sequen[nid].nd[j].index,MATRIX_ELEM(sequen[nid].coef,1,j+1),
	       TCST,value_uminus(value_direct_multiply(MATRIX_ELEM(sequen[nid].coef,1,j+1), 
	       value_plus(sequen[nid].nd[j].lower,
			  MATRIX_ELEM( sequen[nid].delai,j+1,1 ) ))));
	}
    };
  
  return pv;
} 



/* Cette fonction donne le code fusionne avec allocation des tampons */
static statement fusion_buffer()
{
  call c;
  int m;
  int i;
  int j;
  list lis,lis3,lisi=NULL;
                                 
  entity name;
 
  reference ref=NULL;
   Pmatrix temp1,temp2,temp3;
   sequence seq;
   instruction ins;
   statement s;
   loop ls;
  compute_delay_merged_nest();
  compute_bound_merged_nest ();
   

  temp1=matrix_new(1,1);
  temp2=matrix_new(depth,1);
  temp3=matrix_new(depth,1);
  for(i=0;i<=k1-1;i++)
    {
      expression e1,e2,e,exp,gauche=NULL,droite=NULL;
      test t;
      statement s;
      if (i < k1-1)
	{
	  sequen[i].coef=matrix_new(1,depth);
	  cons_coef(sequen[i].coef,i);
	  matrix_substract(temp2,sequen[i+1].delai, sequen[i].delai);
	  matrix_substract(temp3, temp2,sequen[i+1].st[0]);
	  matrix_multiply(sequen[i].coef,temp3,temp1);
	  sequen[i].surface=value_plus(MATRIX_ELEM(temp1,1,1),VALUE_ONE);
	  sequen[i].pv_acces= buffer_acces(i);
	  exp= binary_intrinsic_expression ("MOD",Pvecteur_to_expression(  sequen[i].pv_acces),
					    Value_to_expression( sequen[i].surface) );
	  lis=CONS(DIMENSION,
		   make_dimension(int_to_expression(0),
				  Value_to_expression(value_minus 
						      (sequen[i].surface,VALUE_ONE)),
				  NIL),
		   NIL);
	  name= internal_make_new_array_variable(i+1,-1,get_current_module_entity() , make_basic(is_basic_int, (void *) 4), lis);
	  
	  lis =CONS(EXPRESSION, exp, NIL);
	  ref=make_reference(name,lis);
	  sequen[i].ref=name; 
	}
      e1=ge_expression(entity_to_expression ((entity)sequen[i].nd[0].index),
		       Value_to_expression( value_plus(sequen[i].nd[0].lower,MATRIX_ELEM( sequen[i].delai,1,1))));
      e2=le_expression(entity_to_expression ((entity)sequen[i].nd[0].index),
		       Value_to_expression( value_plus(sequen[i].nd[0].upper,MATRIX_ELEM( sequen[i].delai,1,1))));

      if (value_eq( value_plus(sequen[i].nd[0].lower,MATRIX_ELEM( sequen[i].delai,1,1)),merged_nest[0].lower))
	{
	  if (value_eq( value_plus(sequen[i].nd[0].upper,MATRIX_ELEM( sequen[i].delai,1,1)),merged_nest[0].upper)) 
	     {
	       e=NULL;
	     }
	  else
	     {
	       e=e2;
	     }
	}
      else
	{
	  if (value_eq( value_plus(sequen[i].nd[0].upper,MATRIX_ELEM( sequen[i].delai,1,1)),merged_nest[0].upper)) 
	    {
	      e=e1;
	    }
	  else
	     {
	       e=and_expression(e1,e2);
	     }
	};
    
      for(j=1;j<=depth-1;j++)
       {
	 e1=ge_expression(entity_to_expression ((entity)sequen[i].nd[j].index),
	 		  Value_to_expression( sequen[i].nd[j].lower+MATRIX_ELEM( sequen[i].delai,j+1,1)));
	  
	 e2=le_expression(entity_to_expression ((entity)sequen[i].nd[j].index),
			  Value_to_expression( sequen[i].nd[j].upper+MATRIX_ELEM( sequen[i].delai,j+1,1)));
	 if (value_eq( value_plus(sequen[i].nd[j].lower,MATRIX_ELEM( sequen[i].delai,j+1,1)),merged_nest[j].lower))
	   {
	     if (!value_eq( value_plus(sequen[i].nd[j].upper,MATRIX_ELEM( sequen[i].delai,j+1,1)),merged_nest[j].upper)) 
	       {
		 if (e==NULL)
                   e=e2;
		 else
		   e=and_expression(e,e2);
	       };
	   }
	 else
	   {
	     if (value_eq( value_plus(sequen[i].nd[j].upper,MATRIX_ELEM( sequen[i].delai,j+1,1)),merged_nest[j].upper)) 
	       {
		 if (e==NULL)
		   e=e1;
		 else
		    e=and_expression(e,e1);
	       }
	     else
	       {
		 e1=and_expression(e1,e2);
		 if(e==NULL)
		   e=e1;
		 else
		   e=and_expression(e,e1);
	       }
	   };
	 

 
       };
      if(e==NULL)     
	s=sequen[i].s;
      else
	{
	  t= make_test(e,sequen[i].s,make_block_statement(NIL));
	  s=test_to_statement(t);
	};
      
     if(i==0)   lisi=CONS(STATEMENT,s,NIL);
     else      lisi= gen_nconc(lisi, CONS(STATEMENT,s,NIL));
     c= instruction_call(statement_instruction((sequen[i].s )));
      m=0;
      MAP(EXPRESSION,exp,{  
	if (m==0)  gauche=exp;
	if (m==1)  droite=exp;
	m++;
      },call_arguments(c)) ;
      if(i!=k1-1)   syntax_reference(expression_syntax(gauche))=ref;
      lis3=call_arguments( syntax_call(expression_syntax(droite)));
      if(i==0)
	{
	  for(j=0;j<=depth-1;j++)
	    {
	      Pvecteur pv;
              expression delai_plus;
	      pv = vect_make(VECTEUR_NUL, sequen[i].nd[j].index, VALUE_ONE,
			     TCST,value_uminus(MATRIX_ELEM(sequen[i].delai,j+1,1)));
	      delai_plus=Pvecteur_to_expression(pv);
	      
	      
          FOREACH(EXPRESSION,exp,call_arguments( syntax_call(expression_syntax(droite))))
              replace_entity_by_expression(exp,(entity) sequen[i].nd[j].index,delai_plus);
	      
	    };

	  
	}    
      else
	 {
	   for(j=0;j<=sequen[i].nbr_stencil-1;j++)
	     {
	       Pvecteur pvt; 
               expression expt;
	       pvt=vect_dup(sequen[i-1].pv_acces) ;
               matrix_multiply(sequen[i-1].coef,sequen[i].delai,temp1);
	       pvt=vect_make(pvt,TCST, value_uminus (MATRIX_ELEM(temp1,1,1)));
	       matrix_multiply(sequen[i-1].coef,sequen[i-1].delai,temp1);
	       pvt=vect_make(pvt,TCST, MATRIX_ELEM(temp1,1,1) );
	       matrix_multiply(sequen[i-1].coef,sequen[i].st[j],temp1);
	       pvt=vect_make(pvt,TCST,MATRIX_ELEM(temp1,1,1)  );
	       exp= binary_intrinsic_expression ("MOD",Pvecteur_to_expression(pvt), 
						 Value_to_expression( sequen[i-1].surface) );
	       lis =CONS(EXPRESSION, exp, NIL);
	       ref=make_reference(sequen[i-1].ref,lis);
	       expt=EXPRESSION( CAR(lis3));
	       lis3=CDR(lis3);
	       syntax_reference(expression_syntax(expt))=ref;
	     };
	 };
    
    };
  seq= make_sequence(lisi);
  ins= make_instruction_sequence(seq);
  s= instruction_to_statement(ins);
  ls=loop1;
  for(j=0;j<=depth-1;j++)
    {
      range range1;
    
      range1=loop_range(ls); 
      range_lower(range1)=
	int_to_expression(merged_nest[j].lower);
      range_upper(range1)=
       int_to_expression(merged_nest[j].upper);
      
      if  (j!=depth-1) ls=instruction_loop(statement_instruction(loop_body(ls)));
      else loop_body(ls)=s;
      
    };
  
 s=loop_to_statement(loop1);
  
 return s;

}



static entity 
make_tile_index_entity_n(entity old_index,char *su)
{
    entity new_index;
    string old_name;
    char *new_name = (char*) malloc(33);
    
    old_name = entity_name(old_index);
    for (sprintf(new_name, "%s%s", old_name, su);
         gen_find_tabulated(new_name, entity_domain)!=entity_undefined; 

         old_name = new_name) {
        sprintf(new_name, "%s%s", old_name, su);
	pips_assert("Variable name cannot be longer than 32 characters",
		    strlen(new_name)<33);
    }
 
   new_index = make_entity(new_name,
			   copy_type(entity_type(old_index)),
			   /* Should be AddVariableToCommon(DynamicArea) or
			      something similar! */
			   copy_storage(entity_storage(old_index)),
			   copy_value(entity_initial(old_index)));

    return(new_index);
}
static void derive_new_basis_deux(Pbase base_oldindex, Pbase * base_newindex, entity (*new_entity)(entity, char*))
{
    Pbase pb;
    entity new_name;
    char *a;
    for (pb=base_oldindex; pb!=NULL; pb=pb->succ)
      { 
	a="1";
	new_name = new_entity((entity) pb->var,a);
        base_add_dimension(base_newindex, (Variable) new_name);
	a="2";
	new_name = new_entity((entity) pb->var,a);
	base_add_dimension(base_newindex, (Variable) new_name);
	a="3";
	new_name = new_entity((entity) pb->var,a);
        printf("%s \n",entity_name(new_name));
	base_add_dimension(base_newindex, (Variable) new_name);

    }
    /* *base_newindex = base_reversal(*base_newindex); */
}
static void derive_new_basis_une(Pbase base_oldindex, Pbase * base_newindex, entity (*new_entity)(entity, char*))
{
    Pbase pb;
    entity new_name;
    char *a;
    for (pb=base_oldindex; pb!=NULL; pb=pb->succ)
      { 
	a="1";
	new_name = new_entity((entity) pb->var,a);
        base_add_dimension(base_newindex, (Variable) new_name);
	a="2";
	new_name = new_entity((entity) pb->var,a);
	base_add_dimension(base_newindex, (Variable) new_name);
	

    }
    /* *base_newindex = base_reversal(*base_newindex); */
}


statement permutation( s, P)
     statement s;
     Pmatrix P;
{
  statement scopy;
  int i,j;
  loop ls1,ls2;
  bool found=false;
  scopy=copy_statement(s);
  ls1=instruction_loop(statement_instruction(scopy));
  for(i=1;i<=3*depth;i++)
    {
      j=1;
      found=false;
      ls2=instruction_loop(statement_instruction(s));
      while ((j<=3*depth)&& !found)
	{
	  if (value_eq(MATRIX_ELEM(P,i,j),VALUE_ONE))
	    {
	      found =true;
	      loop_index(ls1)=loop_index(ls2);
	      loop_range(ls1)=loop_range(ls2);
	    };
	  ls2=instruction_loop(statement_instruction(loop_body(ls2)));
	  j++;
	};
      ls1=instruction_loop(statement_instruction(loop_body(ls1)));
    }
  
  return scopy;
}

statement permutation2( s, P)
     statement s;
     Pmatrix P;
{
  statement scopy;
  int i,j;
  loop ls1,ls2;
  bool found=false;
  scopy=copy_statement(s);
  ls1=instruction_loop(statement_instruction(scopy));
  for(i=1;i<=2*depth;i++)
    {
      j=1;
      found=false;
      ls2=instruction_loop(statement_instruction(s));
      while ((j<=2*depth)&& !found)
	{
	  if (value_eq(MATRIX_ELEM(P,i,j),VALUE_ONE))
	    {
	      found =true;
	      loop_index(ls1)=loop_index(ls2);
	      loop_range(ls1)=loop_range(ls2);
	    };
	  ls2=instruction_loop(statement_instruction(loop_body(ls2)));
	  j++;
	};
      ls1=instruction_loop(statement_instruction(loop_body(ls1)));
    }
  
  return scopy;
}

statement Hierarchical_tiling ()
{
  FILE *infp;
  char *name_file;
  Pmatrix A,P;
  int rw,cl,i,j;
  list lis=NULL;
  instruction ins;
  sequence seq=NULL;
  statement s,s1;
  loop ls=NULL;
  cons *lls=NULL;
  Pbase base_oldindex = NULL;
  Pbase base_newindex = NULL;
  Pbase pb;
  expression upper=NULL,lower=NULL;
  int plus;
  Value elem_mat1,elem_mat2;
  Psysteme  loop_iteration_domaine_to_sc();
  name_file = user_request("nom du fichier pour la matrice A ");
  infp = safe_fopen(name_file,"r");
  matrix_fscan(infp,&A,&rw,&cl);
  name_file = user_request("nom du fichier pour la matrice P ");
  infp = safe_fopen(name_file,"r");
  matrix_fscan(infp,&P,&cl,&cl);
  matrix_print(A);
  matrix_print(P); 
  compute_delay_tiled_nest ();
  compute_bound_tiled_nest();
  ls=loop1;
  for(j=0;j<=depth-1;j++)
    {
      range range1;  
      range1=loop_range(ls); 
      range_lower(range1)=int_to_expression(tiled_nest[j].lower);
      range_upper(range1)= int_to_expression(tiled_nest[j].upper);
      if  (j!=depth-1) ls=instruction_loop(statement_instruction(loop_body(ls)));
    };
  s1=loop_to_statement(loop1);
  while(instruction_loop_p(statement_instruction (s1))) {
    lls = CONS(STATEMENT,s1,lls);
    s1 = loop_body(instruction_loop(statement_instruction(s1)));
  }
  (void)loop_iteration_domaine_to_sc(lls, &base_oldindex);

  derive_new_basis_deux(base_oldindex, &base_newindex , make_tile_index_entity_n);
  tiling_indice= ( Pvecteur  *)malloc(depth *sizeof( Pvecteur*));
  plus=depth*3-1;
  for (pb =base_newindex; pb!=NULL; pb=pb->succ) {
    loop tl;
    switch(plus%3)
      {
      case 2: 
	{
	  elem_mat1=MATRIX_ELEM(A,plus/3+1,plus);
	  elem_mat2=MATRIX_ELEM(A,plus/3+1,plus+1);
	  upper= int_to_expression(value_minus(elem_mat1,VALUE_ONE));
	  lower= int_to_expression(0);
	  tiling_indice[plus/3]=vect_make(VECTEUR_NUL,vecteur_var(pb),elem_mat2,TCST,VALUE_ZERO);
	};
	break;
      case 1: 
	{ 
	  elem_mat1=MATRIX_ELEM(A,plus/3+1,plus) ;
	  elem_mat2=MATRIX_ELEM(A,plus/3+1,plus+1  ) ;
	  upper= int_to_expression(value_minus(value_div(elem_mat1,elem_mat2),VALUE_ONE));
	  lower= int_to_expression(0);
	  tiling_indice[plus/3]=vect_make( tiling_indice[plus/3],pb->var , elem_mat2,TCST,VALUE_ZERO);
	};
	break;   
      case 0:
	{ 
	  elem_mat1=MATRIX_ELEM(A,plus/3+1,plus+1);
	  upper= int_to_expression(value_div(tiled_nest[plus/3].upper,elem_mat1));
	  lower= int_to_expression(0);
	  tiling_indice[plus/3]=vect_make( tiling_indice[plus/3],pb->var ,elem_mat1,TCST,VALUE_ZERO);
	};
      default: break;
      }  
    tl = make_loop((entity) vecteur_var(pb),
		   make_range(copy_expression(lower), copy_expression(upper),
			      int_to_expression(1)),
		   s1,
		   entity_empty_label(),
		   make_execution(is_execution_sequential, UU),
		   NIL);
    s1 = instruction_to_statement(make_instruction(is_instruction_loop, tl));
    plus--;
  };
  
  printf(" azuuuul lalallalalal \n"); getchar();

  /******/
  for (i=k1-1;i>=0;i--)
    {
      expression e1,e2,e,gauche=NULL,droite=NULL,delai_plus;
      test t;
      call c;
      int m;
      Pvecteur pv;
      e1=ge_expression(Pvecteur_to_expression (tiling_indice[0]),
		       Value_to_expression( value_plus(sequen[i].nd[0].lower,
						       MATRIX_ELEM( sequen[i].delai,1,1))));
      e2=le_expression(Pvecteur_to_expression (tiling_indice[0]), 
		       Value_to_expression( value_plus(sequen[i].nd[0].upper,
						       MATRIX_ELEM( sequen[i].delai,1,1))));
      if (value_eq( value_plus(sequen[i].nd[0].lower,MATRIX_ELEM( sequen[i].delai,1,1)),tiled_nest[0].lower))
	{
	  if (value_eq( value_plus(sequen[i].nd[0].upper,MATRIX_ELEM( sequen[i].delai,1,1)),tiled_nest[0].upper)&&
	      value_eq(value_mod( value_plus(sequen[i].nd[0].upper,MATRIX_ELEM( sequen[i].delai,1,1)), 
				  MATRIX_ELEM(A,1,1)),VALUE_ZERO))
	    e=NULL;
	  else
	    e=e2;
	}
      else
	{
	  if (value_eq( value_plus(sequen[i].nd[0].upper,MATRIX_ELEM( sequen[i].delai,1,1)),tiled_nest[0].upper)&&
	      value_eq(value_mod( value_plus(sequen[i].nd[0].upper,MATRIX_ELEM( sequen[i].delai,1,1)), 
				  MATRIX_ELEM(A,1,1)),VALUE_ZERO))
	    e=e1;
	   
	  else
	    e=and_expression(e1,e2);
	    
	};
    
      for(j=0;j<=depth-1;j++)
	{
         
	  if (j>=1) 
	    { 
	       
             
              print_expression(Pvecteur_to_expression (tiling_indice[j])  );
               
              
	      e1=ge_expression( Pvecteur_to_expression (tiling_indice[j]),
				Value_to_expression(value_plus(sequen[i].nd[j].lower,
							       MATRIX_ELEM( sequen[i].delai,j+1,1))));
             
	      e2=le_expression(Pvecteur_to_expression (tiling_indice[j]), 
			       Value_to_expression( value_plus(sequen[i].nd[j].upper,
							       MATRIX_ELEM( sequen[i].delai,j+1,1))));
	      
	      if (value_eq( value_plus(sequen[i].nd[j].lower,MATRIX_ELEM( sequen[i].delai,j+1,1)),tiled_nest[j].lower))
		{
		  if (! (value_eq(value_plus(sequen[i].nd[j].upper,MATRIX_ELEM( sequen[i].delai,j+1,1)),tiled_nest[j].upper)&&
			 value_eq(value_mod( value_plus(sequen[i].nd[j].upper,MATRIX_ELEM( sequen[i].delai,j+1,1)), 
					     MATRIX_ELEM(A,j+1,3*j+1)),VALUE_ZERO)))
		    {
		      if (e==NULL)
			e=e2;
		      else
			e=and_expression(e,e2);
		    };
		}
	      else
		{
		  if (value_eq(value_plus(sequen[i].nd[j].upper,MATRIX_ELEM( sequen[i].delai,j+1,1)),tiled_nest[j].upper)&&
		      value_eq(value_mod( value_plus(sequen[i].nd[j].upper,MATRIX_ELEM( sequen[i].delai,j+1,1)), 
					  MATRIX_ELEM(A,j+1,3*j+1)),VALUE_ZERO))
		    {
		      if (e==NULL)
			e=e1;
		      else
			e=and_expression(e,e1);
		    }
		  else
		    {
		      e1=and_expression(e1,e2);
		      if(e==NULL)
			e=e1;
		      else
			e=and_expression(e,e1);
		    }
		};

                
	    }; 
	  c= instruction_call(statement_instruction((sequen[i].s )));
	  m=0;
	  MAP(EXPRESSION,exp,{  
	    if (m==0)  gauche=exp;
	    if (m==1)  droite=exp;
	    m++;
	  },call_arguments(c)) ;
	  pv = vect_make(tiling_indice[j],TCST,value_uminus(MATRIX_ELEM(sequen[i].delai,j+1,1)));
	  delai_plus=Pvecteur_to_expression(pv);
      replace_entity_by_expression(gauche,(entity) sequen[i].nd[j].index,delai_plus);
      FOREACH(EXPRESSION,exp,call_arguments( syntax_call(expression_syntax(droite))))
          replace_entity_by_expression(exp,(entity) sequen[i].nd[j].index,delai_plus);
	};
      t= make_test(e,sequen[i].s,make_block_statement(NIL));
      s=test_to_statement(t);
      if(i==k1-1)   lis=CONS(STATEMENT,s,NIL);
      else      lis=CONS(STATEMENT,s,lis);
    };
  seq= make_sequence(lis);
  ins= make_instruction_sequence(seq);
  s= instruction_to_statement(ins);
  ls=instruction_loop(statement_instruction(s1));
  for(j=0;j<=3*depth-1;j++)
    if  (j!=3*depth-1) ls=instruction_loop(statement_instruction(loop_body(ls)));
    else loop_body(ls)=s;
  s1=permutation(s1,P);
  return s1;
}



int position_one_element(Pmatrix P, int i)
{
  int j;
  for (j=1;j<=depth;j++)
    if(MATRIX_ELEM(P,i,j)==VALUE_ONE) return j;
  pips_internal_error("asking for a non existing element");
  return -1;
}

 
statement Tiling_buffer_allocation ()
{
  FILE *infp;
  char *name_file;
  Pmatrix A,P,ATE,ATEP,ATEPP,P1,P2,N[nid_nbr],NP[nid_nbr],G_PRO[nid_nbr], G_PROP[nid_nbr],G_PROPP[nid_nbr];
  int rw,cl,i,j,k,pos;
  list lis=NULL,lis1=NULL,lis2=NULL;
  instruction ins;
  sequence seq=NULL;
  statement s, s1, sequenp[nid_nbr],
    ps1 = statement_undefined, ps2 = statement_undefined /*,*pst1*/;
  loop ls=NULL;
  cons *lls=NULL;
  Pbase base_oldindex = NULL;
  Pbase base_newindex = NULL;
  Pbase pb;
  expression upper=NULL,lower=NULL,exp=NULL;
  int plus;
  Value elem_mat1,elem_mat2;
  entity *ref[nid_nbr],name;
  reference *buf_ref[nid_nbr];
  statement *scopy[nid_nbr];
  Psysteme  loop_iteration_domaine_to_sc();
  Variable *iter, *itert;
  name_file = user_request("nom du fichier pour la matrice A ");
  infp = safe_fopen(name_file,"r");
  matrix_fscan(infp,&A,&rw,&cl);
  name_file = user_request("nom du fichier pour la matrice P ");
  infp = safe_fopen(name_file,"r");
  matrix_fscan(infp,&P,&cl,&cl);
  compute_delay_tiled_nest ();
  compute_bound_tiled_nest();
  P1=matrix_new(depth,depth);
  
  for(i=1;i<=depth;i++)
    for(j=1;j<=2*depth;j=j+2)
      {
	if ( value_eq(MATRIX_ELEM(P,i,j),VALUE_ONE))
          MATRIX_ELEM(P1,i,j/2+1)=VALUE_ONE;
	else 
          MATRIX_ELEM(P1,i,j/2+1)=VALUE_ZERO;
      };
  
  
  P2=matrix_new(depth,depth);
  for(i=depth+1;i<=2*depth;i++)
    for(j=2;j<=2*depth;j=j+2)
      {
	if (value_eq(MATRIX_ELEM(P,i,j),VALUE_ONE))
          MATRIX_ELEM(P2,(i-1)%depth+1,j/2)=VALUE_ONE;
	else 
          MATRIX_ELEM(P2,(i-1)%depth+1,j/2)=VALUE_ZERO;
      };
  
  ATE=matrix_new(depth,1);
  for(i=0;i<=depth-1;i++)
    MATRIX_ELEM(ATE,i+1,1)=MATRIX_ELEM(A,i+1,2*i+1);
 
  ATEP=matrix_new(depth,1);
  matrix_multiply(P1,ATE,ATEP);
  ATEPP=matrix_new(depth,1);
  matrix_multiply(P2,ATE,ATEPP);
 



  s1=loop_to_statement(loop1);
  while(instruction_loop_p(statement_instruction (s1))) {
    lls = CONS(STATEMENT,s1,lls);
    s1 = loop_body(instruction_loop(statement_instruction(s1)));
  }
 
  (void)loop_iteration_domaine_to_sc(lls, &base_oldindex);
  derive_new_basis_une(base_oldindex, &base_newindex , make_tile_index_entity_n);
 
  iter= ( Variable  *)malloc(depth *sizeof( Variable));
  itert=( Variable  *)malloc(depth *sizeof( Variable));
  i=2*depth-1;
  for (pb =base_newindex; pb!=NULL; pb=pb->succ) {
    if (i%2==1) iter[i/2]=(pb->var);
    else itert[i/2]=(pb->var);
    i--;
  };
  
    
  for(i=0;i<=k1-1;i++)
    {
      //statement s1;
      sequence seq;
      instruction ins;

      Pvecteur pv;
      Value con;
      expression e,gauche=expression_undefined,cavite=expression_undefined;
      test t;
      statement s;
      call c;
      int m;
      
      N[i]=matrix_new(depth,1);
      for (j=1;j<=depth;j++)
	MATRIX_ELEM(N[i],j,1)= value_plus(value_minus(sequen[i].nd[j-1].upper,sequen[i].nd[j-1].lower),VALUE_ONE);
      NP[i]=matrix_new(depth,1);
      matrix_multiply(P1,N[i],NP[i]);
   
      if (i<=k1-2)
	{ 
	  
	  
	  lis2=NULL;
	  G_PRO[i]=matrix_new(depth,1);
	  for(j=1;j<=depth;j++)
	    {
	      
	      Value temp;
	 
	      temp=value_minus(MATRIX_ELEM(sequen[i+1].delai,j,1),MATRIX_ELEM(sequen[i].delai,j,1));
	      MATRIX_ELEM( G_PRO[i],j,1)=value_minus(temp, MATRIX_ELEM(sequen[i+1].st[0],j,1));
	      for(k=1;k<=sequen[i].nbr_stencil-1;k++)
		{   
		  if (MATRIX_ELEM( G_PRO[i],j,1)< value_minus(temp, MATRIX_ELEM(sequen[i].st[k],j,1)))
		    MATRIX_ELEM( G_PRO[i],j,1)=value_minus(temp, MATRIX_ELEM(sequen[i].st[k],j,1));
		};
	    };
             
	  G_PROP[i]=matrix_new(depth,1);
	  matrix_multiply(P1,G_PRO[i],G_PROP[i]);
	  G_PROPP[i]=matrix_new(depth,1);
	  matrix_multiply(P2,G_PRO[i],G_PROPP[i]);
	  ref[i]= ( entity  *)malloc((depth+1) *sizeof( entity));
	  buf_ref[i]=( reference  *)malloc((depth+1) *sizeof( reference));
          scopy[i]=( statement   *)malloc((depth+1) *sizeof( statement));
	 
	  for(j=1;j<=depth;j++)
	    {	      

	      lis= NULL;
              lis1=NULL;
	     
	      lis=CONS(DIMENSION, make_dimension(int_to_expression(0),
						 int_to_expression(1),
						 NIL),
		       lis);
	      pos=position_one_element(P1,j);
	      pv= vect_make(VECTEUR_NUL ,itert[pos-1], VALUE_ONE,TCST,VALUE_ZERO);
	      exp= binary_intrinsic_expression ("MOD",Pvecteur_to_expression(pv ),Value_to_expression(2));
	      lis1 =CONS(EXPRESSION, exp,lis1);
	 
	      for (k=1;k<=j-1;k++)
		{
		 
		  lis=CONS(DIMENSION,
			   make_dimension(int_to_expression(0),
					  Value_to_expression(value_minus 
							      (MATRIX_ELEM(ATEP,k,1),VALUE_ONE)),
					  NIL),
			   lis);
		  pos=position_one_element(P1,k);
		  pv= vect_make(VECTEUR_NUL ,iter[pos-1], VALUE_ONE,TCST,VALUE_ZERO);
		  exp=Pvecteur_to_expression(pv);
		 
		  lis1 =CONS(EXPRESSION, exp,lis1);
		}

              if (value_minus (MATRIX_ELEM(G_PROP[i],j,1),VALUE_ONE)==VALUE_MONE)
		{
 
		  cavite=int_to_expression(0);
		}
	      
              else 
		{ 

		  cavite =Value_to_expression(value_minus (MATRIX_ELEM(G_PROP[i],j,1),VALUE_ONE));
		};
	      lis=CONS(DIMENSION,
		       make_dimension(int_to_expression(0),
				      cavite,
				      NIL), 
		       lis);
	      pos=position_one_element(P1,k);
              con=value_minus(MATRIX_ELEM(G_PRO[i],pos,1), MATRIX_ELEM(ATE,pos,1));    
	      pv= vect_make(VECTEUR_NUL ,iter[pos-1], VALUE_ONE,TCST,con);
	      
	      exp=Pvecteur_to_expression(pv);
	     
	      lis1 =CONS(EXPRESSION, exp,lis1);
	      for (k=j+1;k<=depth;k++)
		{
		  Value v1;
		  lis=CONS(DIMENSION,
			   make_dimension(int_to_expression(0),
					  Value_to_expression(value_minus 
							      (MATRIX_ELEM(NP[i],k,1), VALUE_ONE)),
					  NIL),
			   lis);
		  pos=position_one_element(P1,k);
		 v1=sequen[i].nd[pos-1].lower+MATRIX_ELEM( sequen[i].delai,pos,1 );
		 
		 
		 pv= vect_make(VECTEUR_NUL ,iter[pos-1], VALUE_ONE,itert[pos-1], MATRIX_ELEM(ATE,pos,1) ,TCST,
				value_uminus(v1)  );
		 
		  vect_dump(pv);
		  exp=Pvecteur_to_expression(pv);
		  print_expression(exp);
		 
		  lis1 =CONS(EXPRESSION, exp,lis1);
		}
	      
	   
	      name= internal_make_new_array_variable(i+1,j,get_current_module_entity() , make_basic(is_basic_int, (void *) 4), lis);
	      buf_ref[i][j-1]=make_reference(name,lis1);
	      ref[i][j-1]=name;
              scopy[i][j-1]=copy_statement(sequen[i].s);

	      pos=position_one_element(P1,j);
	      con=value_minus(MATRIX_ELEM(G_PRO[i],pos,1), MATRIX_ELEM(ATE,pos,1));  
	      pv= vect_make(VECTEUR_NUL ,iter[pos-1], VALUE_ONE,TCST,con);
	      e=ge_expression( Pvecteur_to_expression (pv), Value_to_expression( VALUE_ZERO));
              t= make_test(e,scopy[i][j-1],make_block_statement(NIL));
	      s=test_to_statement(t);
	      lis2=CONS(STATEMENT,s,lis2);
	      c= instruction_call(statement_instruction((   scopy[i][j-1] )));
	      m=0;
	      FOREACH(EXPRESSION, exp, call_arguments(c)) {  
		if (m==0)
		  gauche = exp;
		m++;
	      }
	      syntax_reference(expression_syntax(gauche))= buf_ref[i][j-1];
	      

	    }
	 
	  lis=CONS(DIMENSION,
		   make_dimension(int_to_expression(0),
				  Value_to_expression(MATRIX_ELEM(G_PROPP[i],1,1)),
				  NIL),
		   NIL);
	  pos=position_one_element(P2,1);
	  pv= vect_make(VECTEUR_NUL ,iter[pos-1], VALUE_ONE,TCST,VALUE_ZERO);
	 

	  exp= binary_intrinsic_expression ("MOD",Pvecteur_to_expression(pv ),
					    Value_to_expression(value_plus(MATRIX_ELEM(G_PROPP[i],1,1),VALUE_ONE)));

	  
	  lis1 =CONS(EXPRESSION, exp,NIL);
	  for (k=2;k<=depth;k++)
	    {
	      lis=CONS(DIMENSION,
		       make_dimension(int_to_expression(0),
				      Value_to_expression(value_minus 
							  (MATRIX_ELEM(ATEPP,k,1),VALUE_ONE)),
				      NIL),
		       lis);
	      pos=position_one_element(P2,k);
	      pv= vect_make(VECTEUR_NUL ,iter[pos-1], VALUE_ONE,TCST,VALUE_ZERO);
	      exp=Pvecteur_to_expression(pv);
	      
	      lis1 =CONS(EXPRESSION, exp,lis1);
	    }
	  name= internal_make_new_array_variable(i+1,depth+1,get_current_module_entity() , make_basic(is_basic_int, (void *) 4), lis);
	  buf_ref[i][depth]=make_reference(name,lis1);
	  ref[i][depth]=name;
	  scopy[i][depth]=copy_statement(sequen[i].s);
	  c= instruction_call(statement_instruction((   scopy[i][depth] )));
	  m=0;
	  MAP(EXPRESSION,exp,{  
	    if (m==0)  gauche=exp;
	    m++;
	  },call_arguments(c)) ;
	  syntax_reference(expression_syntax(gauche))= buf_ref[i][depth];
	  lis2=CONS(STATEMENT, scopy[i][depth],lis2);
	  seq= make_sequence(lis2);
	  ins= make_instruction_sequence(seq);
	  sequenp[i]= instruction_to_statement(ins);
	 
	};
    };
   
  for(i=1;i<=k1-2;i++)
    { 
      expression e=NULL;
      Pvecteur pv;
      Pmatrix *temp;
      reference *regi[nid_nbr];
      int m1;
     
      for(j=1;j<=depth;j++)
	{
	  Value v2;
	  v2=value_uminus(MATRIX_ELEM(G_PRO[i-1],j,1));
	  pv= vect_make(VECTEUR_NUL,iter[j-1], VALUE_ONE,TCST ,v2);
	  if (j==1)  e=ge_expression(Pvecteur_to_expression(pv),Value_to_expression(VALUE_ZERO));  
	  else
	    e=and_expression(e,ge_expression(Pvecteur_to_expression(pv),Value_to_expression(VALUE_ZERO)));
	}
      temp=( Pmatrix *)malloc( sequen[i].nbr_stencil *sizeof(Pmatrix));
      regi[i]=( reference *)malloc( sequen[i].nbr_stencil *sizeof(reference));;
      for(k=0;k<=sequen[i].nbr_stencil-1;k++)
	{
	  entity name;
	  char buffer[20];  
 	  //expression exp;
	  //reference ref;
	  temp[k]=matrix_new(depth,1);
	  matrix_substract(temp[k],sequen[i].delai, sequen[i-1].delai);
	  matrix_substract(temp[k], temp[k],sequen[i].st[k]);
	  sprintf(buffer,"%s%d_%d", "R",i+1,k);
	  name= make_scalar_entity(buffer,  module_local_name(get_current_module_entity()),
				   make_basic(is_basic_int, (void *) 4) );
	  regi[i][k]=make_reference(name,NIL);
	}
      for(j=0;j<=depth;j++) 
	{
	  expression droite = expression_undefined, expt;
	  statement s1,s2,s3;
          sequence seq;
	  instruction ins;
	  call c;
	  test t;
	  int m,l;
	  list lis,lisp;
	  reference ref;
	  s1=copy_statement(scopy[i][j]);
	  c= instruction_call(statement_instruction(( s1)));
	  m=0;
	  MAP(EXPRESSION,exp,{  
	    if (m==1)  droite=exp;
	    m++;
	  },call_arguments(c)) ;
	  lis=call_arguments( syntax_call(expression_syntax(droite)));
	  for(k=0;k<=sequen[i].nbr_stencil-1;k++)
	    {
	      expression exp;
	      ref=copy_reference (buf_ref[i-1][depth]);  /**** ?????? ****/
	      exp=reference_to_expression(ref);
              for(l=0;l<=depth-1;l++)
		{
		  Pvecteur pv;
		  expression delai_plus;
		  pv = vect_make(VECTEUR_NUL,iter[l], VALUE_ONE, TCST,-MATRIX_ELEM(temp[k],l+1,1));
		  delai_plus=Pvecteur_to_expression(pv);
          replace_entity_by_expression(exp,(entity)iter[l],delai_plus);
		}
	      expt=EXPRESSION( CAR(lis));
	      lis=CDR(lis);
	      syntax_reference(expression_syntax(expt))=ref;
	    }
	  lis=NIL;
	  for(k=0;k<=sequen[i].nbr_stencil-1;k++)
	    {
	      statement s,*stemp;
	      stemp=( statement  *)malloc( (depth+1) *sizeof(statement));
	      for(l=0;l<=depth;l++)
		{ 
		  int r;
		  expression exp;
		  reference ref;
		   
		  ref=copy_reference (buf_ref[i-1][l]);
		  exp=reference_to_expression(ref);
                  for (r=0;r<=depth-1;r++)
		    {
		      Pvecteur pv;
		      expression delai_plus;
		      
		      if(r==l)
			{
			  Value t;
			  int pos;
			  pos=position_one_element(P1,r+1);
			  t=value_minus(MATRIX_ELEM(ATEP,r+1,1),MATRIX_ELEM(temp[k],pos,1));
			  pv = vect_make(VECTEUR_NUL,iter[pos-1], VALUE_ONE, TCST,t);
			  delai_plus=Pvecteur_to_expression(pv);
              replace_entity_by_expression(exp,(entity)iter[pos-1],delai_plus);
			}		   
		      
		      else	     
			{
			  int pos;
			  pos=position_one_element(P1,r+1);
			  pv = vect_make(VECTEUR_NUL,iter[pos-1], VALUE_ONE, TCST,-MATRIX_ELEM(temp[k],pos,1));
			  delai_plus=Pvecteur_to_expression(pv);
              replace_entity_by_expression(exp,(entity)iter[pos-1],delai_plus);
			}
		    }

		  
		  r=0;
		  MAP(EXPRESSION,exp,{  
		   
		    if (r==depth)
		      {
			 
			int pos;
			expression delai_plus;
			pos=position_one_element(P1,l+1);
			pv= vect_make(VECTEUR_NUL ,itert[pos-1], VALUE_ONE,TCST,-VALUE_ONE);
			delai_plus=Pvecteur_to_expression(pv);
            replace_entity_by_expression(exp,(entity)itert[pos-1],delai_plus);

		      };
		    r++;
		  },reference_indices(ref)) 

		  stemp[l]=make_assign_statement(reference_to_expression(regi[i][k]),reference_to_expression(ref));
		};
	      s=  stemp[depth];
	      for(l=depth-1;l>=0;l--)
		{
		  int pos;
		  Pvecteur pv2;
		  //statement s1/*,s2*/;
		  test t;
		  expression exp;
		  pos=position_one_element(P1,l+1);
		  pv2= vect_make(VECTEUR_NUL,iter[pos-1], VALUE_ONE,TCST , -MATRIX_ELEM(temp[k],pos,1));
		  exp=lt_expression(Pvecteur_to_expression(pv2 ),Value_to_expression(VALUE_ZERO));
		  t= make_test(exp,stemp[l],s);
		  s=test_to_statement(t);
		}
	      lis=CONS(STATEMENT,s,lis);

	    }
	  s3=copy_statement(s1);
	 
	  c= instruction_call(statement_instruction(( s3)));
	  m=0;
	  MAP(EXPRESSION,exp,{  
	    if (m==1)  droite=exp;
	    m++;
	  },call_arguments(c)) ;
	  lisp=call_arguments( syntax_call(expression_syntax(droite)));
	  for(k=0;k<=sequen[i].nbr_stencil-1;k++)
	    {
	     
	      expression expt;
	     
	   
               
	      expt=EXPRESSION( CAR(lisp));
	       
	      lisp=CDR(lisp);
	   
	      syntax_reference(expression_syntax(expt))=regi[i][k];
	     
	    }
 


	  lis=CONS(STATEMENT,s3,lis);
	  lis=gen_nreverse(lis);
	  
	  seq= make_sequence(lis);
	  ins= make_instruction_sequence(seq);
	  s2= instruction_to_statement(ins);
	  t= make_test(e,s1,s2);
	  scopy[i][j]=test_to_statement(t);
	  
	  
	};

      m1=0; 

        CHUNK(CAR( sequence_statements(instruction_sequence(statement_instruction(sequenp[i])))))=   (gen_chunk *) scopy[i][depth];  
      MAP(STATEMENT,s,{  
	if (m1!=0)   
	  {
	    test_true(instruction_test(statement_instruction(s)) )=  scopy[i][depth-m1];
    
	  }
	m1++;
	}, sequence_statements(instruction_sequence(statement_instruction(sequenp[i]))) ) ; 




      
    };
  /*   **********************************   */

  for(i= k1-1 ;i<=k1-1;i++)
    { 
      expression e=NULL;
      Pvecteur pv;
      Pmatrix *temp;
      reference *regi[nid_nbr];
      //int m1;
      /* */

      expression droite = expression_undefined, expt;
      statement s1,s2,s3;
      sequence seq;
      instruction ins;
      call c;
      test t;
      int m,l;
      list lis,lisp;
      reference ref;
      
     
      for(j=1;j<=depth;j++)
	{
	  
          Value v2;
	  
	  
	  
	  v2=value_uminus(MATRIX_ELEM(G_PRO[i-1],j,1));
	  
	  pv= vect_make(VECTEUR_NUL,iter[j-1], VALUE_ONE,TCST ,v2);
	  
	  if (j==1)  e=ge_expression(Pvecteur_to_expression(pv),Value_to_expression(VALUE_ZERO));  
	  else
	    e=and_expression(e,ge_expression(Pvecteur_to_expression(pv),Value_to_expression(VALUE_ZERO)));
	  
	}
      
      temp=( Pmatrix *)malloc( sequen[i].nbr_stencil *sizeof(Pmatrix));
      regi[i]=( reference *)malloc( sequen[i].nbr_stencil *sizeof(reference));;
      for(k=0;k<=sequen[i].nbr_stencil-1;k++)
	{
	  entity name;
	  char buffer[24];
 	  //expression exp;
	  //reference ref;
	  temp[k]=matrix_new(depth,1);
	  
	  matrix_substract(temp[k],sequen[i].delai, sequen[i-1].delai);
	  matrix_substract(temp[k], temp[k],sequen[i].st[k]);
	  
	  
	  
	  sprintf(buffer,"%s%d_%d", "R",i+1,k);
	  name= make_scalar_entity(buffer,  module_local_name(get_current_module_entity()),
				   make_basic(is_basic_int, (void *) 4) );
	  
	  regi[i][k]=make_reference(name,NIL);
	  
	  
	      
	}
      
      s1=copy_statement( sequen[i].s);
      ps1=s1;
      c= instruction_call(statement_instruction(( s1)));
      m=0;
      MAP(EXPRESSION,exp,{  
	if (m==1)  droite=exp;
	m++;
      },call_arguments(c)) ;
      lis=call_arguments( syntax_call(expression_syntax(droite)));
      for(k=0;k<=sequen[i].nbr_stencil-1;k++)
	{
	  expression exp;
	  ref=copy_reference (buf_ref[i-1][depth]);
	  exp=reference_to_expression(ref);
	  for(l=0;l<=depth-1;l++)
	    {
	      Pvecteur pv;
	      expression delai_plus;
	      pv = vect_make(VECTEUR_NUL,iter[l], VALUE_ONE, TCST,-MATRIX_ELEM(temp[k],l+1,1));
	      delai_plus=Pvecteur_to_expression(pv);
          replace_entity_by_expression(exp,(entity)iter[l],delai_plus);
	    }
	  expt=EXPRESSION( CAR(lis));
	  lis=CDR(lis);
	  syntax_reference(expression_syntax(expt))=ref;
	} 
      lis=NIL;
      for(k=0;k<=sequen[i].nbr_stencil-1;k++)
	{
	  statement s,*stemp;
	  stemp=( statement  *)malloc( (depth+1) *sizeof(statement));
	  for(l=0;l<=depth;l++)
	    { 
	      int r;
	      expression exp;
	      reference ref;
	      
	      ref=copy_reference (buf_ref[i-1][l]);
	      
	      
	      exp=reference_to_expression(ref);
	      for (r=0;r<=depth-1;r++)
		{
		  Pvecteur pv;
		  expression delai_plus;
		  
		     if(r==l)
			{
			  Value t;
			  int pos;
			  pos=position_one_element(P1,r+1);
			  t=value_minus(MATRIX_ELEM(ATEP,r+1,1),MATRIX_ELEM(temp[k],pos,1));
			  pv = vect_make(VECTEUR_NUL,iter[pos-1], VALUE_ONE, TCST,t);
			  delai_plus=Pvecteur_to_expression(pv);
              replace_entity_by_expression(exp,(entity) iter[pos-1], delai_plus);
			}		   
		      
		      else	     
			{
			  int pos;
			  pos=position_one_element(P1,r+1);
			  pv = vect_make(VECTEUR_NUL,iter[pos-1], VALUE_ONE, TCST,-MATRIX_ELEM(temp[k],pos,1));
			  delai_plus=Pvecteur_to_expression(pv);
              replace_entity_by_expression(exp,(entity) iter[pos-1], delai_plus);
			}
		    
		}
	      r=0;
	      MAP(EXPRESSION,exp,{  
		
		if (r==depth)
		  {
		    int pos;
		    expression delai_plus;
		    pos=position_one_element(P1,l+1);
                    
		 
		    pv= vect_make(VECTEUR_NUL ,itert[pos-1], VALUE_ONE,TCST,-VALUE_ONE);
		 
		    delai_plus=Pvecteur_to_expression(pv);
            replace_entity_by_expression(exp,(entity) itert[pos-1], delai_plus);
		    

		  
		  };
		r++;
	      },reference_indices(ref));
	      
	      stemp[l]=make_assign_statement(reference_to_expression(regi[i][k]),reference_to_expression(ref));
	    };
	  s=  stemp[depth];
	  for(l=depth-1;l>=0;l--)
	    {
	      int pos;
	      Pvecteur pv2;
	      //statement s1,s2;
	      test t;
	      expression exp;
	      pos=position_one_element(P1,l+1);
	      pv2= vect_make(VECTEUR_NUL,iter[pos-1], VALUE_ONE,TCST , -MATRIX_ELEM(temp[k],pos,1));
	      exp=lt_expression( Pvecteur_to_expression(pv2 ) ,Value_to_expression(VALUE_ZERO) );
	      t= make_test(exp,stemp[l],s);
	      s=test_to_statement(t);
	    }
	  lis=CONS(STATEMENT,s,lis);
	  
	}
      s3=copy_statement(s1);
      ps2=s3;
      c= instruction_call(statement_instruction(( s3)));
      m=0;
      MAP(EXPRESSION,exp,{  
	if (m==1)  droite=exp;
	m++;
      },call_arguments(c)) ;
      lisp=call_arguments( syntax_call(expression_syntax(droite)));
      for(k=0;k<=sequen[i].nbr_stencil-1;k++)
	{
	  expression expt;
	  expt=EXPRESSION( CAR(lisp));
	  lisp=CDR(lisp);
	  syntax_reference(expression_syntax(expt))=regi[i][k];
	}
      lis=CONS(STATEMENT,s3,lis);
      lis=gen_nreverse(lis);
      seq= make_sequence(lis);
      ins= make_instruction_sequence(seq);
      s2= instruction_to_statement(ins);
      t= make_test(e,s1,s2);
      sequen[i].s=test_to_statement(t);


      
    }; 




      

/* ************************** */







  ls=loop1;
  for(j=0;j<=depth-1;j++)
    {
      range range1;  
      range1=loop_range(ls); 
      range_lower(range1)=int_to_expression(tiled_nest[j].lower);
      range_upper(range1)= int_to_expression(tiled_nest[j].upper);
      if  (j!=depth-1) ls=instruction_loop(statement_instruction(loop_body(ls)));
    };
  tiling_indice= ( Pvecteur  *)malloc(depth *sizeof( Pvecteur*));
  plus=depth*2-1;
  
  for (pb =base_newindex; pb!=NULL; pb=pb->succ) {
    loop tl;
    switch(plus%2)
      {
      case 1: 
	{ 
	  
	  elem_mat2=MATRIX_ELEM(A,plus/2+1,plus  ) ;
	  
	  upper= int_to_expression(value_minus(elem_mat2,VALUE_ONE));
	  
	  lower= int_to_expression(0);
	  
	  tiling_indice[plus/2]=vect_make(VECTEUR_NUL ,pb->var , VALUE_ONE,TCST,VALUE_ZERO);
	        
	  vect_dump( tiling_indice[plus/2]);
	  
	 
	  break;
	}
	
      case 0:
	{ 
	  elem_mat1=MATRIX_ELEM(A,plus/2+1,plus+1);
	  upper= int_to_expression(value_div(tiled_nest[plus/2].upper,elem_mat1));
	  lower= int_to_expression(0);
	 
	  tiling_indice[plus/2]=vect_make( tiling_indice[plus/2],pb->var ,elem_mat1,TCST,VALUE_ZERO);
	  vect_dup( tiling_indice[plus/2]);
	 
	  break;
	};
	
      default: break;
      }  
    
    tl = make_loop((entity) vecteur_var(pb),
		   make_range(copy_expression(lower), copy_expression(upper),
			      int_to_expression(1)),
		   s1,
		   entity_empty_label(),
		   make_execution(is_execution_sequential, UU),
		   NIL);
    s1 = instruction_to_statement(make_instruction(is_instruction_loop, tl));
    
    
    plus--;
  };
  
  

  /******/
  for (i=k1-1;i>=0;i--)
    {
      expression e1,e2,e/*,gauche=NULL,droite=NULL*/,delai_plus;
      test t;
      //call c;
      //int m;
      //Pvecteur pv;
      e1=ge_expression(Pvecteur_to_expression (tiling_indice[0]),
		       Value_to_expression( value_plus(sequen[i].nd[0].lower,
						       MATRIX_ELEM( sequen[i].delai,1,1))));
      e2=le_expression(Pvecteur_to_expression (tiling_indice[0]), 
		       Value_to_expression( value_plus(sequen[i].nd[0].upper,
						       MATRIX_ELEM( sequen[i].delai,1,1))));
      if (value_eq( value_plus(sequen[i].nd[0].lower,MATRIX_ELEM( sequen[i].delai,1,1)),tiled_nest[0].lower))
	{
	  if (value_eq( value_plus(sequen[i].nd[0].upper,MATRIX_ELEM( sequen[i].delai,1,1)),tiled_nest[0].upper)&&
	      value_eq(value_mod( value_plus(sequen[i].nd[0].upper,MATRIX_ELEM( sequen[i].delai,1,1)), 
				  MATRIX_ELEM(A,1,1)),VALUE_ZERO))
	    e=NULL;
	  else
	    e=e2;
	}
      else
	{
	  if (value_eq( value_plus(sequen[i].nd[0].upper,MATRIX_ELEM( sequen[i].delai,1,1)),tiled_nest[0].upper)&&
	      value_eq(value_mod( value_plus(sequen[i].nd[0].upper,MATRIX_ELEM( sequen[i].delai,1,1)), 
				  MATRIX_ELEM(A,1,1)),VALUE_ZERO))
	    e=e1;
	  
	  else
	    e=and_expression(e1,e2);
	  
	};
     
      for(j=0;j<=depth-1;j++)
	{
	  if (j>=1) 
	    {
	      e1=ge_expression( Pvecteur_to_expression (tiling_indice[j]),
				Value_to_expression(value_plus(sequen[i].nd[j].lower,
							       MATRIX_ELEM( sequen[i].delai,j+1,1))));
	      e2=le_expression(Pvecteur_to_expression (tiling_indice[j]), 
			       Value_to_expression( value_plus(sequen[i].nd[j].upper,
							       MATRIX_ELEM( sequen[i].delai,j+1,1))));
	      if (value_eq( value_plus(sequen[i].nd[j].lower,MATRIX_ELEM( sequen[i].delai,j+1,1)),tiled_nest[j].lower))
		{
		  if (! (value_eq(value_plus(sequen[i].nd[j].upper,MATRIX_ELEM( sequen[i].delai,j+1,1)),tiled_nest[j].upper)&&
			 value_eq(value_mod( value_plus(sequen[i].nd[j].upper,MATRIX_ELEM( sequen[i].delai,j+1,1)), 
					     MATRIX_ELEM(A,j+1,2*j+1)),VALUE_ZERO)))
		    {
		      if (e==NULL)
			e=e2;
		      else
			e=and_expression(e,e2);
		    };
		}
	      else
		{
		  if (value_eq(value_plus(sequen[i].nd[j].upper,MATRIX_ELEM( sequen[i].delai,j+1,1)),tiled_nest[j].upper)&&
		      value_eq(value_mod( value_plus(sequen[i].nd[j].upper,MATRIX_ELEM( sequen[i].delai,j+1,1)), 
					  MATRIX_ELEM(A,j+1,2*j+1)),VALUE_ZERO))
		    {
		      if (e==NULL)
			e=e1;
		      else
			e=and_expression(e,e1);
		    }
		  else
		    {
		      e1=and_expression(e1,e2);
		      if(e==NULL)
			e=e1;
		      else
			e=and_expression(e,e1);
		    }
		};
	    };
	};
      if(i<= k1-2) 
	{
	  if(i==0)
	    {
	      call c;
	      int m ,j,l;
	      expression droite = expression_undefined;
	      Pvecteur pv;

	      for(j=0;j<depth+1;j++)
		{
		  c= instruction_call(statement_instruction(( scopy[i][j])));
		  m=0;
		  MAP(EXPRESSION,exp,{  
		    if (m==1)  droite=exp;
		    m++;
		  },call_arguments(c)) ;
		  for(l=0;l<=depth-1;l++)
		    {
		      pv = vect_make(tiling_indice[l],TCST,value_uminus(MATRIX_ELEM(sequen[i].delai,l+1,1)));
		      delai_plus=Pvecteur_to_expression(pv);
		   
		      FOREACH(EXPRESSION,exp,call_arguments( syntax_call(expression_syntax(droite))))
                  replace_entity_by_expression(exp,(entity)  sequen[i].nd[l].index, delai_plus);
		    }
		}
	    }	      
	  
	  t= make_test(e,sequenp[i],make_block_statement(NIL));
	}
      else 
	{
	  call c;
	  int m ,j;
	  expression gauche = expression_undefined;
	  Pvecteur pv;
	  c= instruction_call(statement_instruction(( ps1 )));
	  m=0;
	  MAP(EXPRESSION,exp,{  
	    if (m==0)  gauche=exp;
	    m++;
	  },call_arguments(c)) ;
	  for(j=0;j<=depth-1;j++)
	    {  
	      pv = vect_make(tiling_indice[j],TCST,value_uminus(MATRIX_ELEM(sequen[i].delai,j+1,1)));
	      delai_plus=Pvecteur_to_expression(pv);
          replace_entity_by_expression(gauche,(entity)  sequen[i].nd[j].index, delai_plus);
	    }
	  c= instruction_call(statement_instruction(( ps2 )));
	  m=0;
	  MAP(EXPRESSION,exp,{  
	    if (m==0)  gauche=exp;
	    m++;
	  },call_arguments(c)) ;
	  for(j=0;j<=depth-1;j++)
	    {  
	      pv = vect_make(tiling_indice[j],TCST,value_uminus(MATRIX_ELEM(sequen[i].delai,j+1,1)));
	      delai_plus=Pvecteur_to_expression(pv);
          replace_entity_by_expression(gauche,(entity)  sequen[i].nd[j].index, delai_plus);
	    }


	  
	  t= make_test(e,sequen[i].s,make_block_statement(NIL));
	};
      s=test_to_statement(t);
 
      if(i==k1-1)   lis=CONS(STATEMENT,s,NIL);
      else      lis=CONS(STATEMENT,s,lis);
      
    };
 
  seq= make_sequence(lis);
  ins= make_instruction_sequence(seq);
  s= instruction_to_statement(ins);
  ls=instruction_loop(statement_instruction(s1));
  for(j=0;j<=2*depth-1;j++)
    if  (j!=2*depth-1) ls=instruction_loop(statement_instruction(loop_body(ls)));
    else loop_body(ls)=s;
 
   
  s1=permutation2(s1,P);
  
  return s1;
}










static bool array_overflow()
{ int i,j,k;

 for(i=0;i<=k1-1;i++)
   {
     trier (sequen[i].st,sequen[i].nbr_stencil);
     if(i==0)
       {
	 int m=0;
	 list lis;
	 expression lower, upper;
	 normalized norm1,norm2;
	 Pvecteur pv1,pv2;
	    Value v1,v2;
	    lis= variable_dimensions(type_variable(entity_type(first_array)));
          
	    MAP(DIMENSION,dim,{
	      lower= dimension_lower(dim);
	      upper=dimension_upper(dim);
	      normalize_all_expressions_of(lower);
	      norm1=expression_normalized(lower);
	      pv1= normalized_linear(norm1);
	      v1=vect_coeff(TCST,pv1);
	    

	     
	      normalize_all_expressions_of(upper);
	      norm2=expression_normalized(upper);
	      pv2= normalized_linear(norm2);
	      v2=vect_coeff(TCST,pv2);
	        
	      for(j=0;j<=sequen[i].nbr_stencil-1;j++)
		{    
		  if (value_plus(MATRIX_ELEM(sequen[i].st[j],depth-m,1), sequen[i].nd[depth-m-1].lower)
		      < v1 )
		    { 
		      overflow=true ;
		      printf(" Debordement dans le   tableau: %s\n",entity_name(first_array));


		    };
		  if (value_plus(MATRIX_ELEM(sequen[i].st[j],depth-m,1), sequen[i].nd[depth-m-1].upper)> 
		      v2 )
		    {   

		      overflow=true ;
		      printf(" Debordement dans le  tableau: %s\n",entity_name(first_array));
		    };
		}
	      m++;
	    },lis) ;
       }
     else
       { 
	 for(j=0;j<=sequen[i].nbr_stencil-1;j++)
	   for(k=0;k<=depth-1;k++)
		{
		  if (value_plus(MATRIX_ELEM(sequen[i].st[j],k+1,1), sequen[i].nd[k].lower)
		      <sequen[i-1].nd[k].lower )
		    {
		      overflow=true ;
		      printf(" Debordement dans le domaine du tableau: %s\n",entity_name(sequen[i-1].tableau));
		    };
		  if (value_plus(MATRIX_ELEM(sequen[i].st[j],k+1,1), sequen[i].nd[k].upper)> 
		      sequen[i-1].nd[k].upper )
		    {
		      overflow=true ;
		      printf(" Debordement dans le domaine du tableau: %s\n",entity_name(sequen[i-1].tableau));
		    };
		  
		};
       };
   };

 return overflow;
}

 

static void unroll_recursive(statement s,int n)
    
{
  if (n==1) 
    full_loop_unroll(s);
  else 
    {
 
      unroll_recursive(loop_body(instruction_loop(statement_instruction(s))), n-1);
      full_loop_unroll(s);
    };
}

statement  Tiling2_buffer()
{
  FILE *infp;
  char *name_file;
  Pmatrix A,A1,A2,P, P1,P2,P3;
  int rw,cl,i,j;
  list lis=NULL;
  instruction ins;
  sequence seq=NULL;
  statement s,s1,s2;
  loop ls=NULL;
  cons *lls=NULL;
  Pbase base_oldindex = NULL;
  Pbase base_newindex = NULL;
  Pbase pb;
  expression upper=NULL,lower=NULL;
  int plus;
  Value elem_mat1,elem_mat2;
  Psysteme  loop_iteration_domaine_to_sc();
  //  void  full_loop_unroll();
  name_file = user_request("nom du fichier pour la matrice A ");
  infp = safe_fopen(name_file,"r");
  matrix_fscan(infp,&A,&rw,&cl);
  name_file = user_request("nom du fichier pour la matrice P ");
  infp = safe_fopen(name_file,"r");
  matrix_fscan(infp,&P,&cl,&cl);
  matrix_print(A);
  matrix_print(P); 
  P1=matrix_new(depth,depth);
  for(i=1;i<=depth;i++)
    for(j=1;j<=3*depth;j=j+3)
      {
	if ( value_eq(MATRIX_ELEM(P,i,j),VALUE_ONE))
          MATRIX_ELEM(P1,i,j/3+1)=VALUE_ONE;
	else 
          MATRIX_ELEM(P1,i,j/3+1)=VALUE_ZERO;
      };

  P2=matrix_new(depth,depth);
  for(i=depth+1;i<=2*depth;i++)
    for(j=2;j<=3*depth;j=j+3)
      {
	if (value_eq(MATRIX_ELEM(P,i,j),VALUE_ONE))
          MATRIX_ELEM(P2,(i-1)%depth+1,j/3+1)=VALUE_ONE;
	else 
          MATRIX_ELEM(P2,(i-1)%depth+1,j/3+1)=VALUE_ZERO;
      };
  
  P3=matrix_new(depth,depth);
  for(i=2*depth+1;i<=3*depth;i++)
    for(j=3;j<=3*depth;j=j+3)
      {
	if (value_eq(MATRIX_ELEM(P,i,j),VALUE_ONE))
          MATRIX_ELEM(P3,(i-1)%depth+1,j/3)=VALUE_ONE;
	else 
          MATRIX_ELEM(P3,(i-1)%depth+1,j/3)=VALUE_ZERO;
      };


  A1=matrix_new(depth,1);
  for(i=0;i<=depth-1;i++)
    MATRIX_ELEM(A1,i+1,1)=MATRIX_ELEM(A,i+1,3*i+1);

  A2=matrix_new(depth,1);
  for(i=0;i<=depth-1;i++)
    MATRIX_ELEM(A2,i+1,1)=MATRIX_ELEM(A,i+1,3*i+2);



 matrix_print(P1);
 matrix_print(P2);
 matrix_print(P3);
 matrix_print(A1);
 matrix_print(A2);

 getchar();
 getchar(); 

  compute_delay_tiled_nest ();
  compute_bound_tiled_nest();
  ls=loop1;
  for(j=0;j<=depth-1;j++)
    {
      range range1;  
      range1=loop_range(ls); 
      range_lower(range1)=int_to_expression(tiled_nest[j].lower);
      range_upper(range1)= int_to_expression(tiled_nest[j].upper);
      if  (j!=depth-1) ls=instruction_loop(statement_instruction(loop_body(ls)));
    };
  s1=loop_to_statement(loop1);
  while(instruction_loop_p(statement_instruction (s1))) {
    lls = CONS(STATEMENT,s1,lls);
    s1 = loop_body(instruction_loop(statement_instruction(s1)));
  }
  (void)loop_iteration_domaine_to_sc(lls, &base_oldindex);

  derive_new_basis_deux(base_oldindex, &base_newindex , make_tile_index_entity_n);
  tiling_indice= ( Pvecteur  *)malloc(depth *sizeof( Pvecteur*));
  plus=depth*3-1;
  for (pb =base_newindex; pb!=NULL; pb=pb->succ) {
    loop tl;
    switch(plus%3)
      {
      case 2: 
	{
	  elem_mat1=MATRIX_ELEM(A,plus/3+1,plus);
	  elem_mat2=MATRIX_ELEM(A,plus/3+1,plus+1);
	  upper= int_to_expression(value_minus(elem_mat1,VALUE_ONE));
	  lower= int_to_expression(0);
	  tiling_indice[plus/3]=vect_make(VECTEUR_NUL,vecteur_var(pb),elem_mat2,TCST,VALUE_ZERO);
	};
	break;
      case 1: 
	{ 
	  elem_mat1=MATRIX_ELEM(A,plus/3+1,plus) ;
	  elem_mat2=MATRIX_ELEM(A,plus/3+1,plus+1  ) ;
	  upper= int_to_expression(value_minus(value_div(elem_mat1,elem_mat2),VALUE_ONE));
	  lower= int_to_expression(0);
	  tiling_indice[plus/3]=vect_make( tiling_indice[plus/3],pb->var , elem_mat2,TCST,VALUE_ZERO);
	};
	break;   
      case 0:
	{ 
	  elem_mat1=MATRIX_ELEM(A,plus/3+1,plus+1);
	  upper= int_to_expression(value_div(tiled_nest[plus/3].upper,elem_mat1));
	  lower= int_to_expression(0);
	  tiling_indice[plus/3]=vect_make( tiling_indice[plus/3],pb->var ,elem_mat1,TCST,VALUE_ZERO);
	};
      default: break;
      }  
    tl = make_loop((entity) vecteur_var(pb),
		   make_range(copy_expression(lower), copy_expression(upper),
			      int_to_expression(1)),
		   s1,
		   entity_empty_label(),
		   make_execution(is_execution_sequential, UU),
		   NIL);
    s1 = instruction_to_statement(make_instruction(is_instruction_loop, tl));
    plus--;
  };
  
 

  /******/
  for (i=k1-1;i>=0;i--)
    {
      expression e1,e2,e,gauche=NULL,droite=NULL,delai_plus;
      test t;
      call c;
      int m;
      Pvecteur pv;
      e1=ge_expression(Pvecteur_to_expression (tiling_indice[0]),
		       Value_to_expression( value_plus(sequen[i].nd[0].lower,
						       MATRIX_ELEM( sequen[i].delai,1,1))));
      e2=le_expression(Pvecteur_to_expression (tiling_indice[0]), 
		       Value_to_expression( value_plus(sequen[i].nd[0].upper,
						       MATRIX_ELEM( sequen[i].delai,1,1))));
      if (value_eq( value_plus(sequen[i].nd[0].lower,MATRIX_ELEM( sequen[i].delai,1,1)),tiled_nest[0].lower))
	{
	  if (value_eq( value_plus(sequen[i].nd[0].upper,MATRIX_ELEM( sequen[i].delai,1,1)),tiled_nest[0].upper)&&
	      value_eq(value_mod( value_plus(sequen[i].nd[0].upper,MATRIX_ELEM( sequen[i].delai,1,1)), 
				  MATRIX_ELEM(A,1,1)),VALUE_ZERO))
	    e=NULL;
	  else
	    e=e2;
	}
      else
	{
	  if (value_eq( value_plus(sequen[i].nd[0].upper,MATRIX_ELEM( sequen[i].delai,1,1)),tiled_nest[0].upper)&&
	      value_eq(value_mod( value_plus(sequen[i].nd[0].upper,MATRIX_ELEM( sequen[i].delai,1,1)), 
				  MATRIX_ELEM(A,1,1)),VALUE_ZERO))
	    e=e1;
	   
	  else
	    e=and_expression(e1,e2);
	    
	};
      for(j=0;j<=depth-1;j++)
	{
	  if (j>=1) 
	    {
	      e1=ge_expression( Pvecteur_to_expression (tiling_indice[j]),
				Value_to_expression(value_plus(sequen[i].nd[j].lower,
							       MATRIX_ELEM( sequen[i].delai,j+1,1))));
	      e2=le_expression(Pvecteur_to_expression (tiling_indice[j]), 
			       Value_to_expression( value_plus(sequen[i].nd[j].upper,
							       MATRIX_ELEM( sequen[i].delai,j+1,1))));
	      if (value_eq( value_plus(sequen[i].nd[j].lower,MATRIX_ELEM( sequen[i].delai,j+1,1)),tiled_nest[j].lower))
		{
		  if (! (value_eq(value_plus(sequen[i].nd[j].upper,MATRIX_ELEM( sequen[i].delai,j+1,1)),tiled_nest[j].upper)&&
			 value_eq(value_mod( value_plus(sequen[i].nd[j].upper,MATRIX_ELEM( sequen[i].delai,j+1,1)), 
					     MATRIX_ELEM(A,j+1,3*j+1)),VALUE_ZERO)))
		    {
		      if (e==NULL)
			e=e2;
		      else
			e=and_expression(e,e2);
		    };
		}
	      else
		{
		  if (value_eq(value_plus(sequen[i].nd[j].upper,MATRIX_ELEM( sequen[i].delai,j+1,1)),tiled_nest[j].upper)&&
		      value_eq(value_mod( value_plus(sequen[i].nd[j].upper,MATRIX_ELEM( sequen[i].delai,j+1,1)), 
					  MATRIX_ELEM(A,j+1,3*j+1)),VALUE_ZERO))
		    {
		      if (e==NULL)
			e=e1;
		      else
			e=and_expression(e,e1);
		    }
		  else
		    {
		      e1=and_expression(e1,e2);
		      if(e==NULL)
			e=e1;
		      else
			e=and_expression(e,e1);
		    }
		};
	    }; 
	  c= instruction_call(statement_instruction((sequen[i].s )));
	  m=0;
	  MAP(EXPRESSION,exp,{  
	    if (m==0)  gauche=exp;
	    if (m==1)  droite=exp;
	    m++;
	  },call_arguments(c)) ;
	  pv = vect_make(tiling_indice[j],TCST,value_uminus(MATRIX_ELEM(sequen[i].delai,j+1,1)));
	  delai_plus=Pvecteur_to_expression(pv);
      replace_entity_by_expression(gauche,(entity) sequen[i].nd[j].index,delai_plus);
      FOREACH(EXPRESSION,exp,call_arguments( syntax_call(expression_syntax(droite))))
        replace_entity_by_expression(exp,(entity) sequen[i].nd[j].index,delai_plus);
	};
      t= make_test(e,sequen[i].s,make_block_statement(NIL));
      s=test_to_statement(t);
      if(i==k1-1)   lis=CONS(STATEMENT,s,NIL);
      else      lis=CONS(STATEMENT,s,lis);
    };
  seq= make_sequence(lis);
  ins= make_instruction_sequence(seq);
  s= instruction_to_statement(ins);
  ls=instruction_loop(statement_instruction(s1));
  for(j=0;j<=3*depth-1;j++)
    if  (j!=3*depth-1) ls=instruction_loop(statement_instruction(loop_body(ls)));
    else loop_body(ls)=s;
  s1=permutation(s1,P);
  
  i=1;
  s2=s1;
  while (i <=2*depth)
    {
      printf(" %d \n", i);
      s2= loop_body(instruction_loop(statement_instruction(s2)));
      i++;
    }
  print_statement(s2);
  printf(" tptpto \n");
  unroll_recursive(s2,depth);

  
  return s1;
}







bool tiling_sequence(string module)
{
  statement stat,s1=NULL;
  context_t context;
  contenu_t contenu;

  debug_on("STATISTICS_DEBUG_LEVEL");
  pips_debug(1, "considering module %s\n", module);
  set_current_module_entity(local_name_to_top_level_entity(module));

  stat = (statement) db_get_memory_resource(DBR_CODE, module, true);

  context.contenu = hash_table_make(hash_pointer, 0);
  context.depth   = hash_table_make(hash_pointer, 0);
  context.statement_stack = stack_make(statement_domain, 0, 0);

  gen_context_multi_recurse
    (stat, & context,
     statement_domain, stmt_flt, stmt_rwt,
     sequence_domain, seq_flt, seq_rwt,
     test_domain, test_flt, test_rwt,
     loop_domain, loop_flt, loop_rwt,
     call_domain, call_flt, call_rwt,
     whileloop_domain, gen_true, wl_rwt,
     unstructured_domain, uns_flt, uns_rwt,
     expression_domain, gen_false, gen_null,
     NULL);
  contenu = (contenu_t) hash_get(context.contenu, stat);
  depth = (intptr_t ) hash_get(context.depth, stat);

  if (contenu!=is_a_stencil)
    {
      printf(" Le programme ne repond pas aux hypotheses  \n");
      array_overflow();
    }
  else
    {
      if(!array_overflow())
	{
	  int choix ;
	  printf("--------------Choix de la transformation-------\n");
	  printf(" 1: Fusion  \n");
	  printf(" 2: Fusion avec allocation des tampons  \n");
	  printf(" 3: Tiling \n");
	  printf(" 4: Tiling a seul niveau avec  allocation des tampons \n");
	  printf(" 5: Tiling a deux niveaux avec  allocation des tampons \n");
	  printf(" Choix: ");
	  if(scanf("%d", &choix)!=1)
	    pips_user_error("Undefined variable \"choix\".\n");
	  switch(choix)
	    {
	    case 1: s1=fusion();
	      break;
	    case 2:  s1= fusion_buffer();
	      break;
	    case 3: s1=Hierarchical_tiling();
	      break;
	    case 4: s1=Tiling_buffer_allocation();
	      break;
            case 5: s1=Tiling2_buffer();
	      break;
	    default: break;
            }
	  module_reorder(s1);
	  DB_PUT_MEMORY_RESOURCE(DBR_CODE, module, s1);
	}
    }
  reset_current_module_entity();
  //  reset_current_module_statement();

  pips_debug(1, "done.\n");
  debug_off();
  return true;
}