/*
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;
}