/* DDG - Data Dependence Graph implementation.
- Copyright (C) 2004
+ 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"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
-#include "basic-block.h"
#include "regs.h"
#include "function.h"
#include "flags.h"
static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr);
static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr);
static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr);
-static void create_ddg_dependence (ddg_ptr, ddg_node_ptr, ddg_node_ptr, rtx);
+static void create_ddg_dependence (ddg_ptr, ddg_node_ptr, ddg_node_ptr, dep_t);
static void create_ddg_dep_no_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr,
dep_type, dep_data_type, int);
static ddg_edge_ptr create_ddg_edge (ddg_node_ptr, ddg_node_ptr, dep_type,
static int
mark_mem_use (rtx *x, void *data ATTRIBUTE_UNUSED)
{
- if (GET_CODE (*x) == MEM)
+ if (MEM_P (*x))
mem_ref_p = true;
return 0;
}
static void
mark_mem_store (rtx loc, rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
{
- if (GET_CODE (loc) == MEM)
+ if (MEM_P (loc))
mem_ref_p = true;
}
if (x == 0)
return false;
- if (GET_CODE (x) == MEM)
+ if (MEM_P (x))
return true;
code = GET_CODE (x);
a ddg_edge and adds it to the given DDG. */
static void
create_ddg_dependence (ddg_ptr g, ddg_node_ptr src_node,
- ddg_node_ptr dest_node, rtx link)
+ ddg_node_ptr dest_node, dep_t link)
{
ddg_edge_ptr e;
int latency, distance = 0;
if (interloop)
distance = 1;
- if (!link)
- abort ();
+ gcc_assert (link);
/* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
- if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
+ if (DEP_KIND (link) == REG_DEP_ANTI)
t = ANTI_DEP;
- else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
+ else if (DEP_KIND (link) == REG_DEP_OUTPUT)
t = OUTPUT_DEP;
- latency = insn_cost (src_node->insn, link, dest_node->insn);
+ latency = dep_cost (link);
e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
else
free (e);
}
+ else if (t == ANTI_DEP && dt == REG_DEP)
+ free (e); /* We can fix broken anti register deps using reg-moves. */
else
add_edge_to_ddg (g, e);
}
{
ddg_edge_ptr e;
int l;
- rtx link = alloc_INSN_LIST (to->insn, NULL_RTX);
+ enum reg_note dep_kind;
+ struct _dep _dep, *dep = &_dep;
if (d_t == ANTI_DEP)
- PUT_REG_NOTE_KIND (link, REG_DEP_ANTI);
+ dep_kind = REG_DEP_ANTI;
else if (d_t == OUTPUT_DEP)
- PUT_REG_NOTE_KIND (link, REG_DEP_OUTPUT);
+ dep_kind = REG_DEP_OUTPUT;
+ else
+ {
+ gcc_assert (d_t == TRUE_DEP);
+
+ dep_kind = REG_DEP_TRUE;
+ }
+
+ init_dep (dep, from->insn, to->insn, dep_kind);
- l = insn_cost (from->insn, link, to->insn);
- free_INSN_LIST_node (link);
+ l = dep_cost (dep);
e = create_ddg_edge (from, to, d_t, d_dt, l, distance);
if (distance > 0)
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);
- if (!src_node || !dest_node)
- abort ();
+ gcc_assert (src_node && dest_node);
/* Any such upwards exposed use appears before the rd def. */
use_before_def = true;
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;
use_node = get_node_of_insn (g, use->insn);
def_node = get_node_of_insn (g, first_def->insn);
- if (!use_node || !def_node)
- abort ();
+ gcc_assert (use_node && def_node);
/* Make sure there are no defs after USE. */
for (i = use_node->cuid + 1; i < g->num_nodes; i++)
if (df_find_def (df, g->nodes[i].insn, use->reg))
return;
/* We must not add ANTI dep when there is an intra-loop TRUE dep in
- the opozite direction. If the first_def reaches the USE then there is
+ 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);
}
static void
build_inter_loop_deps (ddg_ptr g, struct df *df)
{
- int rd_num, u_num;
- struct bb_info *bb_info;
+ unsigned rd_num, u_num;
+ 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,
+ 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,
+ 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);
+ }
}
/* Given two nodes, analyze their RTL insns and add inter-loop mem deps
int i;
/* Hold the dependency analysis state during dependency calculations. */
struct deps tmp_deps;
- rtx head, tail, link;
+ rtx head, tail;
+ dep_link_t link;
/* Build the dependence information, using the sched_analyze function. */
init_deps_global ();
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 (! INSN_P (dest_node->insn))
continue;
- for (link = LOG_LINKS (dest_node->insn); link; link = XEXP (link, 1))
+ FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (dest_node->insn))
{
- ddg_node_ptr src_node = get_node_of_insn (g, XEXP (link, 0));
+ dep_t dep = DEP_LINK_DEP (link);
+ ddg_node_ptr src_node = get_node_of_insn (g, DEP_PRO (dep));
if (!src_node)
continue;
- add_forward_dependence (XEXP (link, 0), dest_node->insn,
- REG_NOTE_KIND (link));
- create_ddg_dependence (g, src_node, dest_node,
- INSN_DEPEND (src_node->insn));
+ add_forw_dep (link);
+ create_ddg_dependence (g, src_node, dest_node, dep);
}
/* If this insn modifies memory, add an edge to all insns that access
{
if (! INSN_P (insn))
{
- if (! first_note && GET_CODE (insn) == NOTE
+ if (! first_note && NOTE_P (insn)
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
first_note = insn;
continue;
}
- if (GET_CODE (insn) == JUMP_INSN)
+ if (JUMP_P (insn))
{
- if (g->closing_branch)
- abort (); /* Found two branches in DDG. */
- else
- g->closing_branch = &g->nodes[i];
+ gcc_assert (!g->closing_branch);
+ g->closing_branch = &g->nodes[i];
}
else if (GET_CODE (PATTERN (insn)) == USE)
{
g->nodes[i++].insn = insn;
first_note = NULL_RTX;
}
-
- if (!g->closing_branch)
- abort (); /* Found no branch in DDG. */
+
+ /* We must have found a branch in DDG. */
+ gcc_assert (g->closing_branch);
+
/* Build the data dependency graph. */
build_intra_loop_deps (g);
}
void
-print_ddg_edge (FILE *dump_file, ddg_edge_ptr e)
+print_ddg_edge (FILE *file, ddg_edge_ptr e)
{
char dep_c;
- switch (e->type) {
+ switch (e->type)
+ {
case OUTPUT_DEP :
dep_c = 'O';
break;
break;
default:
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. */
ddg_node_ptr src = e->src;
ddg_node_ptr dest = e->dest;
- if (!src->successors || !dest->predecessors)
- abort (); /* Should have allocated the sbitmaps. */
+ /* Should have allocated the sbitmaps. */
+ gcc_assert (src->successors && dest->predecessors);
SET_BIT (src->successors, dest->cuid);
SET_BIT (dest->predecessors, src->cuid);
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);
\f
/* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
nodes - find all nodes that lie on paths from FROM to TO (not excluding
- nodes from FROM and TO). Return non zero if nodes exist. */
+ nodes from FROM and TO). Return nonzero if nodes exist. */
int
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);
OSDN Git Service
