/* DDG - Data Dependence Graph implementation.
- Copyright (C) 2004, 2005, 2006, 2007
+ Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
Free Software Foundation, Inc.
Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
#include "system.h"
#include "coretypes.h"
#include "tm.h"
+#include "diagnostic-core.h"
#include "toplev.h"
#include "rtl.h"
#include "tm_p.h"
#include "bitmap.h"
#include "ddg.h"
+#ifdef INSN_SCHEDULING
+
/* A flag indicating that a ddg edge belongs to an SCC or not. */
enum edge_flag {NOT_IN_SCC = 0, IN_SCC};
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, dep_t);
+static void create_ddg_dep_from_intra_loop_link (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,
/* Computes the dependence parameters (latency, distance etc.), creates
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, dep_t link)
+create_ddg_dep_from_intra_loop_link (ddg_ptr g, ddg_node_ptr src_node,
+ ddg_node_ptr dest_node, dep_t link)
{
ddg_edge_ptr e;
int latency, distance = 0;
- int interloop = (src_node->cuid >= dest_node->cuid);
dep_type t = TRUE_DEP;
dep_data_type dt = (mem_access_insn_p (src_node->insn)
&& mem_access_insn_p (dest_node->insn) ? MEM_DEP
: REG_DEP);
-
- /* For now we don't have an exact calculation of the distance,
- so assume 1 conservatively. */
- if (interloop)
- distance = 1;
-
+ gcc_assert (src_node->cuid < dest_node->cuid);
gcc_assert (link);
/* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
- if (DEP_KIND (link) == REG_DEP_ANTI)
+ if (DEP_TYPE (link) == REG_DEP_ANTI)
t = ANTI_DEP;
- else if (DEP_KIND (link) == REG_DEP_OUTPUT)
+ else if (DEP_TYPE (link) == REG_DEP_OUTPUT)
t = OUTPUT_DEP;
- latency = dep_cost (link);
- e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
-
- if (interloop)
+ gcc_assert (!DEBUG_INSN_P (dest_node->insn) || t == ANTI_DEP);
+ gcc_assert (!DEBUG_INSN_P (src_node->insn) || t == ANTI_DEP);
+
+ /* We currently choose not to create certain anti-deps edges and
+ compensate for that by generating reg-moves based on the life-range
+ analysis. The anti-deps that will be deleted are the ones which
+ have true-deps edges in the opposite direction (in other words
+ the kernel has only one def of the relevant register). TODO:
+ support the removal of all anti-deps edges, i.e. including those
+ whose register has multiple defs in the loop. */
+ if (flag_modulo_sched_allow_regmoves && (t == ANTI_DEP && dt == REG_DEP))
{
- /* Some interloop dependencies are relaxed:
- 1. Every insn is output dependent on itself; ignore such deps.
- 2. Every true/flow dependence is an anti dependence in the
- opposite direction with distance 1; such register deps
- will be removed by renaming if broken --- ignore them. */
- if (!(t == OUTPUT_DEP && src_node == dest_node)
- && !(t == ANTI_DEP && dt == REG_DEP))
- add_backarc_to_ddg (g, e);
- else
- free (e);
+ rtx set;
+
+ set = single_set (dest_node->insn);
+ /* TODO: Handle registers that REG_P is not true for them, i.e.
+ subregs and special registers. */
+ if (set && REG_P (SET_DEST (set)))
+ {
+ int regno = REGNO (SET_DEST (set));
+ df_ref first_def;
+ struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
+
+ first_def = df_bb_regno_first_def_find (g->bb, regno);
+ gcc_assert (first_def);
+
+ if (bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def)))
+ return;
+ }
}
- 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);
+
+ latency = dep_cost (link);
+ e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
+ add_edge_to_ddg (g, e);
}
/* The same as the above function, but it doesn't require a link parameter. */
enum reg_note dep_kind;
struct _dep _dep, *dep = &_dep;
+ gcc_assert (!DEBUG_INSN_P (to->insn) || d_t == ANTI_DEP);
+ gcc_assert (!DEBUG_INSN_P (from->insn) || d_t == ANTI_DEP);
+
if (d_t == ANTI_DEP)
dep_kind = REG_DEP_ANTI;
else if (d_t == OUTPUT_DEP)
add_edge_to_ddg (g, e);
}
-\f
-/* Given a downwards exposed register def RD, add inter-loop true dependences
- for all its uses in the next iteration, and an output dependence to the
- first def of the next iteration. */
+
+/* Given a downwards exposed register def LAST_DEF (which is the last
+ definition of that register in the bb), add inter-loop true dependences
+ to all its uses in the next iteration, an output dependence to the
+ first def of the same register (possibly itself) in the next iteration
+ and anti-dependences from its uses in the current iteration to the
+ first definition in the next iteration. */
static void
-add_deps_for_def (ddg_ptr g, struct df_ref *rd)
+add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def)
{
- int regno = DF_REF_REGNO (rd);
- struct df_ru_bb_info *bb_info = DF_RU_BB_INFO (g->bb);
+ int regno = DF_REF_REGNO (last_def);
struct df_link *r_use;
- int use_before_def = false;
- rtx def_insn = DF_REF_INSN (rd);
- ddg_node_ptr src_node = get_node_of_insn (g, def_insn);
+ int has_use_in_bb_p = false;
+ rtx def_insn = DF_REF_INSN (last_def);
+ ddg_node_ptr last_def_node = get_node_of_insn (g, def_insn);
+ ddg_node_ptr use_node;
+#ifdef ENABLE_CHECKING
+ struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
+#endif
+ df_ref first_def = df_bb_regno_first_def_find (g->bb, regno);
+
+ gcc_assert (last_def_node);
+ gcc_assert (first_def);
- /* Create and inter-loop true dependence between RD and each of its uses
- that is upwards exposed in RD's block. */
- for (r_use = DF_REF_CHAIN (rd); r_use != NULL; r_use = r_use->next)
+#ifdef ENABLE_CHECKING
+ if (DF_REF_ID (last_def) != DF_REF_ID (first_def))
+ gcc_assert (!bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def)));
+#endif
+
+ /* Create inter-loop true dependences and anti dependences. */
+ for (r_use = DF_REF_CHAIN (last_def); r_use != NULL; r_use = r_use->next)
{
- 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);
+ rtx use_insn = DF_REF_INSN (r_use->ref);
- gcc_assert (src_node && dest_node);
+ if (BLOCK_FOR_INSN (use_insn) != g->bb)
+ continue;
- /* Any such upwards exposed use appears before the rd def. */
- use_before_def = true;
- create_ddg_dep_no_link (g, src_node, dest_node, TRUE_DEP,
+ /* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
+ use_node = get_node_of_insn (g, use_insn);
+ gcc_assert (use_node);
+ has_use_in_bb_p = true;
+ if (use_node->cuid <= last_def_node->cuid)
+ {
+ /* Add true deps from last_def to it's uses in the next
+ iteration. Any such upwards exposed use appears before
+ the last_def def. */
+ create_ddg_dep_no_link (g, last_def_node, use_node,
+ DEBUG_INSN_P (use_insn) ? ANTI_DEP : TRUE_DEP,
REG_DEP, 1);
}
- }
+ else if (!DEBUG_INSN_P (use_insn))
+ {
+ /* Add anti deps from last_def's uses in the current iteration
+ to the first def in the next iteration. We do not add ANTI
+ dep when there is an intra-loop TRUE dep in the opposite
+ direction, but use regmoves to fix such disregarded ANTI
+ deps when broken. If the first_def reaches the USE then
+ there is such a dep. */
+ ddg_node_ptr first_def_node = get_node_of_insn (g,
+ DF_REF_INSN (first_def));
+
+ gcc_assert (first_def_node);
+
+ if (DF_REF_ID (last_def) != DF_REF_ID (first_def)
+ || !flag_modulo_sched_allow_regmoves)
+ create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP,
+ REG_DEP, 1);
- /* Create an inter-loop output dependence between RD (which is the
- last def in its block, being downwards exposed) and the first def
- in its block. Avoid creating a self output dependence. Avoid creating
- an output dependence if there is a dependence path between the two defs
- starting with a true dependence followed by an anti dependence (i.e. if
- there is a use between the two defs. */
- if (! use_before_def)
+ }
+ }
+ /* Create an inter-loop output dependence between LAST_DEF (which is the
+ last def in its block, being downwards exposed) and the first def in
+ its block. Avoid creating a self output dependence. Avoid creating
+ an output dependence if there is a dependence path between the two
+ defs starting with a true dependence to a use which can be in the
+ next iteration; followed by an anti dependence of that use to the
+ first def (i.e. if there is a use between the two defs.) */
+ if (!has_use_in_bb_p)
{
- struct df_ref *def = df_bb_regno_first_def_find (g->bb, regno);
- int i;
ddg_node_ptr dest_node;
- if (!def || rd->id == def->id)
+ if (DF_REF_ID (last_def) == DF_REF_ID (first_def))
return;
- /* Check if there are uses after RD. */
- for (i = src_node->cuid + 1; i < g->num_nodes; i++)
- if (df_find_use (g->nodes[i].insn, DF_REF_REG (rd)))
- return;
-
- dest_node = get_node_of_insn (g, def->insn);
- create_ddg_dep_no_link (g, src_node, dest_node, OUTPUT_DEP, REG_DEP, 1);
+ dest_node = get_node_of_insn (g, DF_REF_INSN (first_def));
+ gcc_assert (dest_node);
+ create_ddg_dep_no_link (g, last_def_node, dest_node,
+ OUTPUT_DEP, REG_DEP, 1);
}
}
-
-/* Given a register USE, add an inter-loop anti dependence to the first
- (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_ref *use)
-{
- int i;
- int regno = DF_REF_REGNO (use);
- struct df_ref *first_def = df_bb_regno_first_def_find (g->bb, regno);
- ddg_node_ptr use_node;
- ddg_node_ptr def_node;
- struct df_rd_bb_info *bb_info;
-
- bb_info = DF_RD_BB_INFO (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);
-
- 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 (g->nodes[i].insn, DF_REF_REG (use)))
- 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->gen, first_def->id))
- create_ddg_dep_no_link (g, use_node, def_node, ANTI_DEP, REG_DEP, 1);
-}
-
/* Build inter-loop dependencies, by looking at DF analysis backwards. */
static void
build_inter_loop_deps (ddg_ptr g)
{
- unsigned rd_num, u_num;
+ unsigned rd_num;
struct df_rd_bb_info *rd_bb_info;
- struct df_ru_bb_info *ru_bb_info;
bitmap_iterator bi;
rd_bb_info = DF_RD_BB_INFO (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 (rd_bb_info->gen, 0, rd_num, bi)
+ /* Find inter-loop register output, true and anti deps. */
+ EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info->gen, 0, rd_num, bi)
+ {
+ df_ref rd = DF_DEFS_GET (rd_num);
+
+ add_cross_iteration_register_deps (g, rd);
+ }
+}
+
+
+static int
+walk_mems_2 (rtx *x, rtx mem)
+{
+ if (MEM_P (*x))
{
- struct df_ref *rd = DF_DEFS_GET (rd_num);
+ if (may_alias_p (*x, mem))
+ return 1;
- add_deps_for_def (g, rd);
+ return -1;
}
+ return 0;
+}
- ru_bb_info = DF_RU_BB_INFO (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 (ru_bb_info->kill, 0, u_num, bi)
+static int
+walk_mems_1 (rtx *x, rtx *pat)
+{
+ if (MEM_P (*x))
{
- struct df_ref *use = DF_USES_GET (u_num);
- if (!(DF_REF_FLAGS (use) & DF_REF_IN_NOTE))
- /* We are interested in uses of this BB. */
- if (BLOCK_FOR_INSN (use->insn) == g->bb)
- add_deps_for_use (g, use);
+ /* Visit all MEMs in *PAT and check indepedence. */
+ if (for_each_rtx (pat, (rtx_function) walk_mems_2, *x))
+ /* Indicate that dependence was determined and stop traversal. */
+ return 1;
+
+ return -1;
}
+ return 0;
+}
+
+/* Return 1 if two specified instructions have mem expr with conflict alias sets*/
+static int
+insns_may_alias_p (rtx insn1, rtx insn2)
+{
+ /* For each pair of MEMs in INSN1 and INSN2 check their independence. */
+ return for_each_rtx (&PATTERN (insn1), (rtx_function) walk_mems_1,
+ &PATTERN (insn2));
}
/* Given two nodes, analyze their RTL insns and add inter-loop mem deps
static void
add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
{
+ if (!insns_may_alias_p (from->insn, to->insn))
+ /* Do not create edge if memory references have disjoint alias sets. */
+ return;
+
if (mem_write_insn_p (from->insn))
{
if (mem_read_insn_p (to->insn))
- create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 1);
+ create_ddg_dep_no_link (g, from, to,
+ DEBUG_INSN_P (to->insn)
+ ? ANTI_DEP : TRUE_DEP, MEM_DEP, 1);
else if (from->cuid != to->cuid)
- create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 1);
+ create_ddg_dep_no_link (g, from, to,
+ DEBUG_INSN_P (to->insn)
+ ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 1);
}
else
{
return;
else if (from->cuid != to->cuid)
{
- create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
- create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
+ create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
+ if (DEBUG_INSN_P (from->insn) || DEBUG_INSN_P (to->insn))
+ create_ddg_dep_no_link (g, to, from, ANTI_DEP, MEM_DEP, 1);
+ else
+ create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
}
}
{
int i;
/* Hold the dependency analysis state during dependency calculations. */
- struct deps tmp_deps;
+ struct deps_desc tmp_deps;
rtx head, tail;
- dep_link_t link;
/* Build the dependence information, using the sched_analyze function. */
init_deps_global ();
- init_deps (&tmp_deps);
+ init_deps (&tmp_deps, false);
/* Do the intra-block data dependence analysis for the given block. */
get_ebb_head_tail (g->bb, g->bb, &head, &tail);
for (i = 0; i < g->num_nodes; i++)
{
ddg_node_ptr dest_node = &g->nodes[i];
+ sd_iterator_def sd_it;
+ dep_t dep;
if (! INSN_P (dest_node->insn))
continue;
- FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (dest_node->insn))
+ FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep)
{
- 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_forw_dep (link);
- create_ddg_dependence (g, src_node, dest_node, dep);
+ create_ddg_dep_from_intra_loop_link (g, src_node, dest_node, dep);
}
/* If this insn modifies memory, add an edge to all insns that access
for (j = 0; j <= i; j++)
{
ddg_node_ptr j_node = &g->nodes[j];
+ if (DEBUG_INSN_P (j_node->insn))
+ continue;
if (mem_access_insn_p (j_node->insn))
/* Don't bother calculating inter-loop dep if an intra-loop dep
already exists. */
/* Free the INSN_LISTs. */
finish_deps_global ();
free_deps (&tmp_deps);
+
+ /* Free dependencies. */
+ sched_free_deps (head, tail, false);
}
if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
continue;
- if (mem_read_insn_p (insn))
- g->num_loads++;
- if (mem_write_insn_p (insn))
- g->num_stores++;
+ if (DEBUG_INSN_P (insn))
+ g->num_debug++;
+ else
+ {
+ if (mem_read_insn_p (insn))
+ g->num_loads++;
+ if (mem_write_insn_p (insn))
+ g->num_stores++;
+ }
num_nodes++;
}
/* There is nothing to do for this BB. */
- if (num_nodes <= 1)
+ if ((num_nodes - g->num_debug) <= 1)
{
free (g);
return NULL;
g->nodes[i++].insn = insn;
first_note = NULL_RTX;
}
-
+
/* We must have found a branch in DDG. */
gcc_assert (g->closing_branch);
-
+
/* Build the data dependency graph. */
build_intra_loop_deps (g);
{
ddg_edge_ptr e;
+ fprintf (file, "Node num: %d\n", g->nodes[i].cuid);
print_rtl_single (file, g->nodes[i].insn);
fprintf (file, "OUT ARCS: ");
for (e = g->nodes[i].out; e; e = e->next_out)
compare_sccs (const void *s1, const void *s2)
{
const int rec_l1 = (*(const ddg_scc_ptr *)s1)->recurrence_length;
- const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length;
+ const int rec_l2 = (*(const ddg_scc_ptr *)s2)->recurrence_length;
return ((rec_l2 > rec_l1) - (rec_l2 < rec_l1));
-
+
}
/* Order the backarcs in descending recMII order using compare_sccs. */
sbitmap_free (tmp);
return result;
}
+
+#endif /* INSN_SCHEDULING */