#ifdef HAVE_CONFIG_H
    #include "pips_config.h"
#endif


#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include "boolean.h"
#include <stdbool.h>

#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "database.h"
#include "misc.h"
#include "text.h"
#include "text-util.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "accel-util.h"

#include "effects-generic.h"
#include "effects-simple.h"

#include "pipsdbm.h"
#include "resources.h"
#include "control.h"
#include "conversion.h"
#include "properties.h"
#include "semantics.h"
#include "transformations.h"

#include "effects-convex.h"
#include "genC.h"

#include "complexity_ri.h"


#include "dg.h"

/* Instantiation of the dependence graph: */
typedef dg_arc_label arc_label;
typedef dg_vertex_label vertex_label;
#include "graph.h"
#include "ricedg.h"
#include "chains.h"
#include "semantics.h"
#include "task_parallelization.h"

static transformer p_transformer;
static graph sdg;

/* parameters of BDSC, to be recovered using pips properties */
int  NBCLUSTERS;
int  MEMORY_SIZE;
string INSTRUMENTED_FILE;

/* Global variables */
gen_array_t annotations;
gen_array_t clusters;


static
void get_private_entities_walker(loop l, set s)
{
  set_append_list(s,loop_locals(l));
}

static
set get_private_entities(void *s)
{
    set tmp = set_make(set_pointer);
    gen_context_recurse(s, tmp, loop_domain, gen_true2, get_private_entities_walker);
    return tmp;
}


struct cpv {
    entity e;
    bool rm;
};


static
void check_private_variables_call_walker(call c,struct cpv * p)
{
    set s = get_referenced_entities(c);
    if(set_belong_p(s,p->e)){
        p->rm=true;
        gen_recurse_stop(0);
    }
    set_free(s);
}
static
bool check_private_variables_loop_walker(loop l, struct cpv * p)
{
    return !has_entity_with_same_name(p->e,loop_locals(l));
}


static list private_variables(statement stat)
{
    set s = get_private_entities(stat);
    list l =NIL;
    SET_FOREACH(entity,e,s) {
        struct cpv p = { .e=e, .rm=false };
        gen_context_multi_recurse(stat,&p,
                call_domain,gen_true,check_private_variables_call_walker,
                loop_domain,check_private_variables_loop_walker,gen_null,
                0);
        if(!p.rm)
            l=CONS(ENTITY,e,l);
    }
    set_free(s);

    return l;
}


bool statement_equal_p(statement s1, statement s2)
{
    return (statement_number(s1) == statement_number(s2) && statement_ordering(s1) == statement_ordering(s2) );
}

 
/* *************SDG: Sequence Dependence Graph ***************************/ 

vertex statement_to_vertex(statement s, graph g)
{
    MAP(VERTEX, v, {
        statement sv = vertex_to_statement(v);
	if (statement_equal_p(s, sv))
	  return v;
    }, graph_vertices(g));
    return vertex_undefined;
}

static list enclosed_statements_ast(statement stmt, list children_s)
{
  instruction inst = statement_instruction(stmt);
  switch(instruction_tag(inst))
    {
    case is_instruction_block :
      {
	MAPL( stmt_ptr,
	      {
		statement local_stmt = STATEMENT(CAR( stmt_ptr ));
		children_s = CONS( STATEMENT, local_stmt, children_s);
		children_s = enclosed_statements_ast(local_stmt,children_s);
	      },
	      instruction_block( inst ) );
	break;
      }
    case is_instruction_test :
      {
	test t = instruction_test(inst);
	children_s = CONS( STATEMENT, test_true(t), children_s);
	children_s = CONS( STATEMENT, test_false(t), children_s);
	children_s = enclosed_statements_ast(test_true(t),children_s);
	children_s = enclosed_statements_ast(test_false(t),children_s);
	break;
      }
    case is_instruction_loop :
      {
	loop l = statement_loop(stmt);
	statement body = loop_body(l);
	children_s = CONS( STATEMENT, body, children_s);
	children_s = enclosed_statements_ast(body,children_s);
	break;
      }
    case is_instruction_forloop :
      {
	forloop l = statement_forloop(stmt);
	statement body = forloop_body(l);
	children_s = CONS( STATEMENT, body, children_s);
	children_s = enclosed_statements_ast(body,children_s);
	break;
      }
    case is_instruction_whileloop :
      {
	whileloop l = statement_whileloop(stmt);
	statement body = whileloop_body(l);
	children_s = CONS( STATEMENT, body, children_s);
	children_s = enclosed_statements_ast(body,children_s);
	break;
      }
    case is_instruction_call:
      //children_s = CONS( STATEMENT, stmt, children_s);
      break;
    default:
      break;
    }
  return children_s;
}

static bool same_level_p(statement s1, statement s2, bool found_p)
{
    
  if(statement_equal_p(s1, s2))
    return true;
  else {
    instruction inst = statement_instruction(s2);
    switch(instruction_tag(inst)){
    case is_instruction_block :{
      MAPL( stmt_ptr,
	    {
	      statement local_stmt = STATEMENT(CAR( stmt_ptr ));
	      found_p = found_p || same_level_p(s1, local_stmt, found_p);
	    },
	    instruction_block(inst));
      break;
    }
    case is_instruction_test :{
      test t = instruction_test(inst);
      found_p = found_p || same_level_p(s1, test_true(t), found_p);
      return found_p || same_level_p(s1, test_false(t), found_p);
      break;
    }
    case is_instruction_loop :{
      loop l = statement_loop(s2);
      statement body = loop_body(l);
      return found_p || same_level_p(s1, body, found_p);
      break;
    }
    case is_instruction_forloop :{
      forloop l = statement_forloop(s2);
      statement body = forloop_body(l);
      return found_p || same_level_p(s1, body, found_p);
      break;
    }
    case is_instruction_whileloop :{
      whileloop l = statement_whileloop(s2);
      statement body = whileloop_body(l);
      return found_p || same_level_p(s1, body, found_p);
      break;
    }
    default:
      break;
    }
  }
  return found_p;
}
static statement in_same_sequence(statement child, sequence seq)
{
  statement enclosing_st = statement_undefined;
  bool found_p;
  list stmts = sequence_statements(seq);
  FOREACH(STATEMENT, st, stmts){
    found_p = same_level_p(child, st, false);
    if(found_p){
      enclosing_st = st;
      return st;
    }
  }
  return enclosing_st;
}

/* for precision in dependences in arrays, we use array regions in this function*/

static bool test_dependence_using_regions(statement s1, statement s2)
{
  bool dependence_b = false;
  list l_write_1 = regions_dup(regions_write_regions(load_statement_local_regions(s1)));
  list private_ents1 = NIL, private_ents2 = NIL;
  if(statement_loop_p(s1))
    private_ents1 =  loop_locals(statement_loop(s1));
  private_ents1= gen_nconc(private_ents1,private_variables(s1));
  if(statement_loop_p(s2))
     private_ents2 = loop_locals(statement_loop(s2));
  private_ents2= gen_nconc(private_ents2, private_variables(s2));
  FOREACH(ENTITY,e,private_ents1){
    FOREACH(REGION,reg,l_write_1){
      if (same_entity_p(region_entity(reg),e))
	gen_remove(&l_write_1, reg);
    }
  }
  list l_write_2 = regions_dup(regions_write_regions(load_statement_local_regions(s2)));
  FOREACH(ENTITY,e,private_ents2){
    FOREACH(REGION,reg,l_write_2){
      if (same_entity_p(region_entity(reg),e))
	gen_remove(&l_write_2, reg);
    }
  }
  l_write_2 = convex_regions_transformer_compose(l_write_2, p_transformer);
  list l_read_2 = regions_dup(regions_read_regions(load_statement_local_regions(s2)));  
  FOREACH(ENTITY,e,private_ents2){
    FOREACH(REGION,reg,l_read_2) {
      if (same_entity_p(region_entity(reg),e))
	gen_remove(&l_read_2, reg);
    }
  }
  l_read_2 = convex_regions_transformer_compose(l_read_2, p_transformer);
  list l_read_1 = regions_dup(regions_read_regions(load_statement_local_regions(s1)));  
  FOREACH(ENTITY,e,private_ents1){
    FOREACH(REGION,reg,l_read_1){
      if (same_entity_p(region_entity(reg),e))
	gen_remove(&l_read_1, reg);
    }
  }
  list dependence_rw = RegionsIntersection(regions_dup(l_read_1), regions_dup(l_write_2), r_w_combinable_p);
  list dependence_wr = RegionsIntersection(regions_dup(l_write_1), regions_dup(l_read_2), w_r_combinable_p);
  list dependence_ww = RegionsIntersection(regions_dup(l_write_1), regions_dup(l_write_2), w_w_combinable_p);
  if(gen_length(dependence_rw)==0)
    {
      if(gen_length(dependence_wr)==0)
	{
	  if(gen_length(dependence_ww)>0)
	    dependence_b=true;
	}
      else
	dependence_b=true;
    }
  else
    dependence_b = true;
  return dependence_b;
}

static bool sequence_dg(statement stmt)
{
  if(statement_sequence_p(stmt)){
    sequence seq = statement_sequence(stmt);
    list stmts = sequence_statements(seq);
    path pbegin;
    path pend;
    FOREACH(STATEMENT, st_g, stmts) {
      {
	list children_s = CONS(STATEMENT, st_g, NIL);
	list ls = NIL;
	children_s = enclosed_statements_ast(st_g,children_s);
	vertex pre_g = statement_to_vertex(st_g, sdg);
	FOREACH(STATEMENT, st, children_s){
	  vertex pre = statement_to_vertex(st, sdg);
	  FOREACH(SUCCESSOR, su, (vertex_successors(pre))) {
	    vertex s = successor_vertex(su);
	    statement child = vertex_to_statement(s);
	    statement enclosing_stmt = statement_undefined;
	    enclosing_stmt = in_same_sequence(child, seq);
	    if(statement_undefined_p(enclosing_stmt))
	      enclosing_stmt = in_same_sequence(st, seq);

	    p_transformer =  transformer_identity();
	    path_initialize(stmt, st,child, &pbegin, &pend);
	    //p_transformer = compute_path_transformer(stmt, pbegin, pend);
	    /*update the sdg for st(parent) using enclosing_stmt instead of
	     *the enclosed one child*/
	    if(!statement_equal_p(st_g, enclosing_stmt) && test_dependence_using_regions(st_g,enclosing_stmt)){
	      if(statement_ordering(st_g)<statement_ordering(enclosing_stmt)){
		vertex new_v = statement_to_vertex(enclosing_stmt, sdg);
		successor_vertex(su) = new_v;
		if(gen_occurences(su, ls) == 0)
		  ls = CONS(SUCCESSOR, su, ls);
	      }
	    }
	  }
	}
	vertex_successors(pre_g) = ls; 
      }
    }
  }
  return true;
}

static bool statement_in_sequence_p(statement s, statement stmt, bool found_p)
{
  instruction inst = statement_instruction(stmt);
  switch(instruction_tag(inst))
    {
    case is_instruction_block :
      {
	MAPL( stmt_ptr,
	      {
		statement local_stmt = STATEMENT(CAR( stmt_ptr ));
		if(statement_equal_p(s, local_stmt))
		  return true;
		else
		  found_p = found_p ||  statement_in_sequence_p(s, local_stmt, found_p);
	      },
	      instruction_block( inst ) );
	break;
      }
    case is_instruction_test :
      {
	test t = instruction_test(inst);
	found_p = found_p ||  statement_in_sequence_p(s, test_true(t), found_p);
	return found_p ||  statement_in_sequence_p(s, test_false(t), found_p);
	break;
      }
    case is_instruction_loop :
      {
	loop l = statement_loop(stmt);
	statement body = loop_body(l);
	return found_p ||  statement_in_sequence_p(s, body, found_p);
	break;
      }
    case is_instruction_forloop :
      {
	forloop l = statement_forloop(stmt);
	statement body = forloop_body(l);
	return found_p ||  statement_in_sequence_p(s, body, found_p);
	break;
      }
    case is_instruction_whileloop :
      {
	whileloop l = statement_whileloop(stmt);
	statement body = whileloop_body(l);
	return found_p ||  statement_in_sequence_p(s, body, found_p);
	break;
      }
    default:
      break;
    }
  return found_p;
}


/* Second step to form a clustered DG (SDG), delete dependences between  statement s1 and another statement S2
   if s1 is not in a sequence  and redondont dependences*/  
static graph clean_sdg(statement module_stmt, graph tg)
{
  list vertices = graph_vertices(tg);
  statement s;
  FOREACH(VERTEX, pre, vertices)
    {
      s = vertex_to_statement(pre);
      bool found_p =  statement_in_sequence_p(s, module_stmt, false);
      if(!found_p)
	{
	  gen_free_list(vertex_successors(pre));
	  vertex_successors(pre) = NIL;
	}
      else{
	int count;
	list ls = NIL, lv = NIL;
	FOREACH(SUCCESSOR, su, (vertex_successors(pre))) {
	  vertex ssu = successor_vertex(su);
	  statement child = vertex_to_statement(ssu);
	  count = gen_occurences(child, ls);
	  if(count == 0 && statement_ordering(s)<statement_ordering(child))
	    {
	      ls = CONS(STATEMENT, child,ls);
	      if(gen_occurences(su, lv) == 0)
		lv = CONS(SUCCESSOR,su,lv);
	    }
	}
	vertex_successors(pre) = lv; 
      }
    }
  return tg;
}


graph partitioning_sdg(statement module_stmt)
{
  gen_recurse(module_stmt, statement_domain, sequence_dg, gen_null);
  return clean_sdg(module_stmt, sdg);
}






/** \def dot_print_label_string( fd, str )
  print the string str in file descriptor fd, removing all \n
 */
#define dot_print_label_string( ftg, str )				\
  fprintf(ftg," [fontsize=24,fontcolor=black, label=\"");	   \
  while ( *str ) {			   \
    char c = *str++;				    \
    if ( c == '"' ) { /* some char must be escaped */	\
      (void) putc( '\\', ftg);				\
    }							\
    (void) putc( c, ftg);				\
  }\
  fprintf(ftg," \"]; \n"); 


static string prettyprint_dot_label(statement s, string label1 ) {
  string label2="";
  // saving comments
  string i_comments = statement_comments(s);
  // remove them
  statement_comments(s) = string_undefined;
  // Get the text without comments
  text txt = Text_Statement(entity_undefined, 0, s);
  // Restoring comments
  statement_comments(s) = i_comments;
  label2 = strdup (concatenate (label1, text_to_string(txt),"\\n", NULL));
  free_text(txt);
  return label2;
 }

/* 
 *return a dot graph for SDG, print only nodes that have at least one
 *successor
 */
static void print_sdg_task(FILE *ftg, gen_array_t annotations, statement stmt) {
  string ver = "";
  ver = prettyprint_dot_label(stmt,ver);
  fprintf( ftg,"%d",(int)statement_ordering(stmt) );
  if(strlen(ver)>1000)
    ver = "too large statement label with ordering \\n";
  if(gen_array_nitems(annotations)>0){
    annotation *an=gen_array_item(annotations, (int)statement_ordering(stmt));
    if(an->cluster != -1)
      {
	ver = strdup (concatenate (ver, "cluster = ", NULL));ver = strdup (concatenate (ver, i2a(an->cluster),"\\n", NULL));
	ver = strdup (concatenate (ver, "order = ", NULL)); ver = strdup (concatenate (ver, i2a(an->order_sched),"\\n", NULL));
	ver = strdup (concatenate (ver, "time = ", NULL)); ver = strdup (concatenate (ver, i2a(an->task_time),"\\n", NULL));
      }
  }
  dot_print_label_string( ftg, ver);	
  return;
}

static int count = 0;
void print_SDGs(statement stmt, graph tg, FILE *ftg, gen_array_t annotations) {
  instruction inst = statement_instruction(stmt);
  switch(instruction_tag(inst))
    {
    case is_instruction_block :
      {
      sequence seq = statement_sequence(stmt);
      list stmts = sequence_statements(seq);
      fprintf( ftg, "subgraph cluster%d { color = blue; \n ",count );
      FOREACH(STATEMENT, s, stmts) {
	list vertices = graph_vertices(tg);
	annotation *anp = NULL;
	FOREACH(VERTEX, pre, vertices) {
	  statement parent = vertex_to_statement(pre);
	  if(statement_equal_p(parent, s)){
	    if(gen_array_nitems(annotations)>0)
	      anp = gen_array_item(annotations, (int)statement_ordering(parent));
	    print_sdg_task(ftg, annotations, parent);
	    FOREACH(SUCCESSOR, su, (vertex_successors(pre))) {
	      vertex s = successor_vertex(su);
	      statement child = vertex_to_statement(s);
	      print_sdg_task(ftg, annotations, child);
	      if(gen_array_nitems(annotations)>0){
		annotation *an=gen_array_item(annotations, (int)statement_ordering(child));
		if(an->cluster!=-1)
		  {//FFT
		    double edge_c = (intptr_t)(gen_array_item(anp->edge_cost,statement_ordering(child)));
		    fprintf( ftg,"%d -> %d [style=filled,color=blue,fontsize=16,label=\"%ld\",color=black];\n", (int)statement_ordering(parent),(int)statement_ordering(child),(long)(edge_c));
		  }
	      }
	      else
		fprintf( ftg,"%d -> %d [style=filled,color=blue,fontsize=16,color=black];\n", (int)statement_ordering(parent),(int)statement_ordering(child));
	    }
	  }
	}
      }
      fprintf( ftg, "} \n " );
      count ++;
      stmts = sequence_statements(seq);
      FOREACH(STATEMENT, s, stmts) 
	print_SDGs(s,tg, ftg, annotations);
      break;
      }
    case is_instruction_test:
      {
	test t = instruction_test(inst);
	print_SDGs(test_true(t),tg, ftg, annotations); 
	print_SDGs(test_false(t),tg, ftg, annotations); 
	break;
      }
    case is_instruction_loop :
      {
	loop l = statement_loop(stmt);
	print_SDGs(loop_body(l),tg, ftg, annotations);
	break;
      }
    case is_instruction_forloop :
      {
	forloop l = statement_forloop(stmt);
	print_SDGs(forloop_body(l),tg, ftg, annotations);
	break;
      }
    case is_instruction_whileloop :
      {
	whileloop l = statement_whileloop(stmt);
	print_SDGs(whileloop_body(l),tg, ftg, annotations);
	break;
      }
    default:
      break;
    }
  return; 
}
bool sequence_dependence_graph(char * module_name)
{ 
  //entity	module;
  statement	module_stat;
  string tg_name = NULL;
  FILE *ftg;
  //module = local_name_to_top_level_entity(module_name);
  module_stat = (statement)db_get_memory_resource(DBR_CODE, module_name, true);
  set_ordering_to_statement(module_stat);
  set_current_module_entity(module_name_to_entity(module_name));
  set_current_module_statement(module_stat);
  set_precondition_map((statement_mapping)db_get_memory_resource(DBR_PRECONDITIONS, module_name, true));
  set_transformer_map((statement_mapping)
		      db_get_memory_resource(DBR_TRANSFORMERS, module_name, true));
  /* The proper effect to detect the I/O operations: */
  set_proper_rw_effects((statement_effects)db_get_memory_resource(DBR_PROPER_EFFECTS, module_name, true));
  set_cumulated_rw_effects((statement_effects)db_get_memory_resource(DBR_CUMULATED_EFFECTS, module_name, true));
  module_to_value_mappings(get_current_module_entity());
  set_rw_effects((statement_effects) 
		 db_get_memory_resource(DBR_REGIONS, module_name, true));
  set_in_effects((statement_effects) db_get_memory_resource(DBR_IN_REGIONS, module_name, true));
  set_out_effects((statement_effects) db_get_memory_resource(DBR_OUT_REGIONS, module_name, true));
  set_methods_for_convex_effects();
  init_convex_rw_prettyprint(module_name);
 
  ddg = (graph) db_get_memory_resource (DBR_DG, module_name, true );
  /*ddg contains the original dependences before clustering and  scheduling, it
    is saved to not make a side effect on the original dg when
    constructing the SDG*/
  sdg = copy_graph(ddg);
  sdg = partitioning_sdg(module_stat);
  tg_name = strdup(concatenate(db_get_current_workspace_directory(),
			       "/",module_name,"/",module_name, "_sdg.dot", NULL));
  ftg = safe_fopen(tg_name, "w");
  fprintf( ftg, "digraph {\n compound=true;ratio=fill; node[fontsize=24,fontname=\"Courier\",labelloc=\"t\"];nodesep=.05;\n" );
  print_SDGs(module_stat, sdg, ftg, gen_array_make(0));
  fprintf( ftg, "\n}\n" );
  safe_fclose(ftg, tg_name);
  free(tg_name);
  
  reset_ordering_to_statement();
  DB_PUT_MEMORY_RESOURCE(DBR_SDG, module_name, (char*) sdg);
  
  reset_proper_rw_effects();
  reset_cumulated_rw_effects();
  reset_rw_effects();
  reset_in_effects();
  reset_out_effects();
  reset_precondition_map();
  reset_transformer_map();
  reset_current_module_statement();
  reset_current_module_entity();
  generic_effects_reset_all_methods();
  free_value_mappings();
  return true;
}