/* DDG - Data Dependence Graph implementation.
- Copyright (C) 2004, 2005
+ Copyright (C) 2004, 2005, 2006
Free Software Foundation, Inc.
Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
#include "config.h"
for all its uses in the next iteration, and an output dependence to the
first def of the next iteration. */
static void
-add_deps_for_def (ddg_ptr g, struct df *df, struct ref *rd)
+add_deps_for_def (ddg_ptr g, struct df *df, struct df_ref *rd)
{
int regno = DF_REF_REGNO (rd);
- struct bb_info *bb_info = DF_BB_INFO (df, g->bb);
+ struct df_ru_bb_info *bb_info = DF_RU_BB_INFO (df, g->bb);
struct df_link *r_use;
int use_before_def = false;
rtx def_insn = DF_REF_INSN (rd);
that is upwards exposed in RD's block. */
for (r_use = DF_REF_CHAIN (rd); r_use != NULL; r_use = r_use->next)
{
- if (bitmap_bit_p (bb_info->ru_gen, r_use->ref->id))
+ if (bitmap_bit_p (bb_info->gen, r_use->ref->id))
{
rtx use_insn = DF_REF_INSN (r_use->ref);
ddg_node_ptr dest_node = get_node_of_insn (g, use_insn);
there is a use between the two defs. */
if (! use_before_def)
{
- struct ref *def = df_bb_regno_first_def_find (df, g->bb, regno);
+ struct df_ref *def = df_bb_regno_first_def_find (df, g->bb, regno);
int i;
ddg_node_ptr dest_node;
/* Check if there are uses after RD. */
for (i = src_node->cuid + 1; i < g->num_nodes; i++)
- if (df_reg_used (df, g->nodes[i].insn, rd->reg))
+ if (df_find_use (df, g->nodes[i].insn, rd->reg))
return;
dest_node = get_node_of_insn (g, def->insn);
(nearest BLOCK_BEGIN) def of the next iteration, unless USE is followed
by a def in the block. */
static void
-add_deps_for_use (ddg_ptr g, struct df *df, struct ref *use)
+add_deps_for_use (ddg_ptr g, struct df *df, struct df_ref *use)
{
int i;
int regno = DF_REF_REGNO (use);
- struct ref *first_def = df_bb_regno_first_def_find (df, g->bb, regno);
+ struct df_ref *first_def = df_bb_regno_first_def_find (df, g->bb, regno);
ddg_node_ptr use_node;
ddg_node_ptr def_node;
- struct bb_info *bb_info;
+ struct df_rd_bb_info *bb_info;
- bb_info = DF_BB_INFO (df, g->bb);
+ bb_info = DF_RD_BB_INFO (df, g->bb);
if (!first_def)
return;
/* We must not add ANTI dep when there is an intra-loop TRUE dep in
the opposite direction. If the first_def reaches the USE then there is
such a dep. */
- if (! bitmap_bit_p (bb_info->rd_gen, first_def->id))
+ if (! bitmap_bit_p (bb_info->gen, first_def->id))
create_ddg_dep_no_link (g, use_node, def_node, ANTI_DEP, REG_DEP, 1);
}
build_inter_loop_deps (ddg_ptr g, struct df *df)
{
unsigned rd_num, u_num;
- struct bb_info *bb_info;
+ struct df_rd_bb_info *rd_bb_info;
+ struct df_ru_bb_info *ru_bb_info;
bitmap_iterator bi;
- bb_info = DF_BB_INFO (df, g->bb);
+ rd_bb_info = DF_RD_BB_INFO (df, g->bb);
/* Find inter-loop output and true deps by connecting downward exposed defs
to the first def of the BB and to upwards exposed uses. */
- EXECUTE_IF_SET_IN_BITMAP (bb_info->rd_gen, 0, rd_num, bi)
+ EXECUTE_IF_SET_IN_BITMAP (rd_bb_info->gen, 0, rd_num, bi)
{
- struct ref *rd = df->defs[rd_num];
+ struct df_ref *rd = DF_DEFS_GET (df, rd_num);
add_deps_for_def (g, df, rd);
}
+ ru_bb_info = DF_RU_BB_INFO (df, g->bb);
+
/* Find inter-loop anti deps. We are interested in uses of the block that
appear below all defs; this implies that these uses are killed. */
- EXECUTE_IF_SET_IN_BITMAP (bb_info->ru_kill, 0, u_num, bi)
+ EXECUTE_IF_SET_IN_BITMAP (ru_bb_info->kill, 0, u_num, bi)
{
- struct ref *use = df->uses[u_num];
+ struct df_ref *use = DF_USES_GET (df, u_num);
/* We are interested in uses of this BB. */
if (BLOCK_FOR_INSN (use->insn) == g->bb)
- add_deps_for_use (g, df,use);
+ add_deps_for_use (g, df, use);
}
}
init_deps (&tmp_deps);
/* Do the intra-block data dependence analysis for the given block. */
- get_block_head_tail (g->bb->index, &head, &tail);
+ get_ebb_head_tail (g->bb, g->bb, &head, &tail);
sched_analyze (&tmp_deps, head, tail);
/* Build intra-loop data dependencies using the scheduler dependency
if (!src_node)
continue;
- add_forward_dependence (XEXP (link, 0), dest_node->insn,
- REG_NOTE_KIND (link));
+ add_forw_dep (dest_node->insn, link);
create_ddg_dependence (g, src_node, dest_node,
INSN_DEPEND (src_node->insn));
}
}
void
-print_ddg_edge (FILE *dump_file, ddg_edge_ptr e)
+print_ddg_edge (FILE *file, ddg_edge_ptr e)
{
char dep_c;
dep_c = 'T';
}
- fprintf (dump_file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
+ fprintf (file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
dep_c, e->latency, e->distance, INSN_UID (e->dest->insn));
}
/* Print the DDG nodes with there in/out edges to the dump file. */
void
-print_ddg (FILE *dump_file, ddg_ptr g)
+print_ddg (FILE *file, ddg_ptr g)
{
int i;
{
ddg_edge_ptr e;
- print_rtl_single (dump_file, g->nodes[i].insn);
- fprintf (dump_file, "OUT ARCS: ");
+ print_rtl_single (file, g->nodes[i].insn);
+ fprintf (file, "OUT ARCS: ");
for (e = g->nodes[i].out; e; e = e->next_out)
- print_ddg_edge (dump_file, e);
+ print_ddg_edge (file, e);
- fprintf (dump_file, "\nIN ARCS: ");
+ fprintf (file, "\nIN ARCS: ");
for (e = g->nodes[i].in; e; e = e->next_in)
- print_ddg_edge (dump_file, e);
+ print_ddg_edge (file, e);
- fprintf (dump_file, "\n");
+ fprintf (file, "\n");
}
}
/* Print the given DDG in VCG format. */
void
-vcg_print_ddg (FILE *dump_file, ddg_ptr g)
+vcg_print_ddg (FILE *file, ddg_ptr g)
{
int src_cuid;
- fprintf (dump_file, "graph: {\n");
+ fprintf (file, "graph: {\n");
for (src_cuid = 0; src_cuid < g->num_nodes; src_cuid++)
{
ddg_edge_ptr e;
int src_uid = INSN_UID (g->nodes[src_cuid].insn);
- fprintf (dump_file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
- print_rtl_single (dump_file, g->nodes[src_cuid].insn);
- fprintf (dump_file, "\"}\n");
+ fprintf (file, "node: {title: \"%d_%d\" info1: \"", src_cuid, src_uid);
+ print_rtl_single (file, g->nodes[src_cuid].insn);
+ fprintf (file, "\"}\n");
for (e = g->nodes[src_cuid].out; e; e = e->next_out)
{
int dst_uid = INSN_UID (e->dest->insn);
/* Give the backarcs a different color. */
if (e->distance > 0)
- fprintf (dump_file, "backedge: {color: red ");
+ fprintf (file, "backedge: {color: red ");
else
- fprintf (dump_file, "edge: { ");
+ fprintf (file, "edge: { ");
- fprintf (dump_file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
- fprintf (dump_file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
- fprintf (dump_file, "label: \"%d_%d\"}\n", e->latency, e->distance);
+ fprintf (file, "sourcename: \"%d_%d\" ", src_cuid, src_uid);
+ fprintf (file, "targetname: \"%d_%d\" ", dst_cuid, dst_uid);
+ fprintf (file, "label: \"%d_%d\"}\n", e->latency, e->distance);
}
}
- fprintf (dump_file, "}\n");
+ fprintf (file, "}\n");
}
/* Create an edge and initialize it with given values. */
create_scc (ddg_ptr g, sbitmap nodes)
{
ddg_scc_ptr scc;
- int u;
+ unsigned int u = 0;
+ sbitmap_iterator sbi;
scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
scc->backarcs = NULL;
sbitmap_copy (scc->nodes, nodes);
/* Mark the backarcs that belong to this SCC. */
- EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
+ EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
{
ddg_edge_ptr e;
ddg_node_ptr n = &g->nodes[u];
if (e->distance > 0)
add_backarc_to_scc (scc, e);
}
- });
+ }
set_recurrence_length (scc, g);
return scc;
void
find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
{
- int i;
+ unsigned int i = 0;
+ sbitmap_iterator sbi;
- EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i,
+ EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
{
const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
sbitmap_a_or_b (succ, succ, node_succ);
- });
+ };
/* We want those that are not in ops. */
sbitmap_difference (succ, succ, ops);
void
find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
{
- int i;
+ unsigned int i = 0;
+ sbitmap_iterator sbi;
- EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i,
+ EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
{
const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
sbitmap_a_or_b (preds, preds, node_preds);
- });
+ };
/* We want those that are not in ops. */
sbitmap_difference (preds, preds, ops);
find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
{
int answer;
- int change, u;
+ int change;
+ unsigned int u = 0;
int num_nodes = g->num_nodes;
+ sbitmap_iterator sbi;
+
sbitmap workset = sbitmap_alloc (num_nodes);
sbitmap reachable_from = sbitmap_alloc (num_nodes);
sbitmap reach_to = sbitmap_alloc (num_nodes);
change = 0;
sbitmap_copy (workset, tmp);
sbitmap_zero (tmp);
- EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
+ EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
{
ddg_edge_ptr e;
ddg_node_ptr u_node = &g->nodes[u];
change = 1;
}
}
- });
+ }
}
sbitmap_copy (reach_to, to);
change = 0;
sbitmap_copy (workset, tmp);
sbitmap_zero (tmp);
- EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
+ EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
{
ddg_edge_ptr e;
ddg_node_ptr u_node = &g->nodes[u];
change = 1;
}
}
- });
+ }
}
answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to);
int
longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
{
- int i, u;
+ int i;
+ unsigned int u = 0;
int change = 1;
int result;
int num_nodes = g->num_nodes;
while (change)
{
+ sbitmap_iterator sbi;
+
change = 0;
sbitmap_copy (workset, tmp);
sbitmap_zero (tmp);
- EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
+ EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
{
ddg_node_ptr u_node = &g->nodes[u];
change |= update_dist_to_successors (u_node, nodes, tmp);
- });
+ }
}
result = g->nodes[dest].aux.count;
sbitmap_free (workset);