/*
   Copyright Universite de Versailles Saint-Quentin en Yvelines 2009
   AUTHORS: Sebastien Briais, Sid Touati

   This file is part of RS.
   
   RS is free software: you can redistribute it and/or modify it
   under the terms of the GNU Lesser General Public License as
   published by the Free Software Foundation, either version 3 of the
   License, or (at your option) any later version.
   
   RS 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
   Lesser General Public License for more details.
   
   You should have received a copy of the GNU Lesser General Public
   License along with RS.  If not, see
   <http://www.gnu.org/licenses/>.
*/
#include <stdio.h>

#include <SCEDA/graph.h>
#include <SCEDA/pqueue.h>
#include <SCEDA/graph_dag.h>

#include <GDD/ddg.h>
#include <GDD/opcode.h>

#include "util.h"
#include "pkill.h"

// v1 < v2 iff v1 comes after v2 in topological order
// (thus there can't be a path from v1 to v2)
static int compare_vertex(SCEDA_Vertex *v1, SCEDA_Vertex *v2) {
  int i = SCEDA_vertex_get_index(v1);
  int j = SCEDA_vertex_get_index(v2);
  if(i < j) {
    return 1;
  } else if(i == j) {
    return 0;
  } else {
    return -1;
  }
}

/** Compute the potential killers graph for given type.

    @param[in] ddg = GDD_DAG
    @param[in] type = considered type

    @return the potential killers graph

    Vertices are labelled with vertex of the underlying DAG.
    Edges are not labelled. */
SCEDA_Graph *RS_ddag_pkill(GDD_DAG *ddg, const char *type) {
  SCEDA_Graph *pk_g = SCEDA_graph_create(NULL, NULL);
  SCEDA_Graph *g = GDD_dag_get_ddg(ddg);

  safe_call(SCEDA_graph_compute_topological_order(g));

  int n = SCEDA_graph_vcount(g);

  SCEDA_Vertex *vpk[n];

  SCEDA_VerticesIterator g_vertice;
  SCEDA_vertices_iterator_init(g, &g_vertice);
  while(SCEDA_vertices_iterator_has_next(&g_vertice)) {
    SCEDA_Vertex *v = SCEDA_vertices_iterator_next(&g_vertice);
    int i = SCEDA_vertex_get_index(v);
    vpk[i] = SCEDA_graph_add_vertex(pk_g, v);
  }
  SCEDA_vertices_iterator_cleanup(&g_vertice);

  int i;
  SCEDA_PQueue *heap = SCEDA_pqueue_create(NULL, (SCEDA_compare_fun)compare_vertex);

  for(i = 0; i < n; i++) {
    SCEDA_Vertex *pk_v = vpk[i];
    SCEDA_Vertex *v = SCEDA_vertex_get_data(SCEDA_Vertex *, pk_v);

    if(GDD_vertex_is_value_of_type(v, type)) {
      SCEDA_HashSet *cons_v = GDD_consumers_of_type(v, type);

      SCEDA_HashSetIterator consumers;
      SCEDA_hashset_iterator_init(cons_v, &consumers);
      while(SCEDA_hashset_iterator_has_next(&consumers)) {
	SCEDA_Vertex *w = SCEDA_hashset_iterator_next(&consumers);
	safe_call(SCEDA_pqueue_insert(heap, w));
      }
      SCEDA_hashset_iterator_cleanup(&consumers);

      SCEDA_hashset_delete(cons_v);

      while(SCEDA_pqueue_size(heap) > 0) {
	SCEDA_Vertex *w;
	safe_call(SCEDA_pqueue_extract(heap, (void **)&w));
	int j = SCEDA_vertex_get_index(w);

	int is_pkiller = TRUE;

	SCEDA_VertexSuccIterator succ;
	SCEDA_vertex_succ_iterator_init(pk_v, &succ);
	while(SCEDA_vertex_succ_iterator_has_next(&succ)) {
	  SCEDA_Vertex *pk_z = SCEDA_vertex_succ_iterator_next(&succ);
	  SCEDA_Vertex *z = SCEDA_vertex_get_data(SCEDA_Vertex *, pk_z);
	  // by construction, there is no path from z to w
	  // so we check only whether there is a path from w to z
	  if(GDD_dag_lt(ddg, w, z)) {
	    is_pkiller = FALSE;
	    break;
	  }
	}
	SCEDA_vertex_succ_iterator_cleanup(&succ);

	if(is_pkiller) {
	  SCEDA_Vertex *pk_w = vpk[j];
	  SCEDA_graph_add_edge(pk_g, pk_v, pk_w, NULL);
	}
      }
    }
  }

  SCEDA_pqueue_delete(heap);

  return pk_g;
}