/* DDG - Data Dependence Graph implementation.
- Copyright (C) 2004, 2005, 2006, 2007
+ Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
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 "toplev.h"
+#include "diagnostic-core.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
return rtx_mem_access_p (PATTERN (insn));
}
+/* Return true if DEF_INSN contains address being auto-inc or auto-dec
+ which is used in USE_INSN. Otherwise return false. The result is
+ being used to decide whether to remove the edge between def_insn and
+ use_insn when -fmodulo-sched-allow-regmoves is set. This function
+ doesn't need to consider the specific address register; no reg_moves
+ will be allowed for any life range defined by def_insn and used
+ by use_insn, if use_insn uses an address register auto-inc'ed by
+ def_insn. */
+bool
+autoinc_var_is_used_p (rtx def_insn, rtx use_insn)
+{
+ rtx note;
+
+ for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1))
+ if (REG_NOTE_KIND (note) == REG_INC
+ && reg_referenced_p (XEXP (note, 0), PATTERN (use_insn)))
+ return true;
+
+ return false;
+}
+
+/* Return true if one of the definitions in INSN has MODE_CC. Otherwise
+ return false. */
+static bool
+def_has_ccmode_p (rtx insn)
+{
+ df_ref *def;
+
+ for (def = DF_INSN_DEFS (insn); *def; def++)
+ {
+ enum machine_mode mode = GET_MODE (DF_REF_REG (*def));
+
+ if (GET_MODE_CLASS (mode) == MODE_CC)
+ return true;
+ }
+
+ return false;
+}
+
/* Computes the dependence parameters (latency, distance etc.), creates
a ddg_edge and adds it to the given DDG. */
static void
else if (DEP_TYPE (link) == REG_DEP_OUTPUT)
t = OUTPUT_DEP;
+ 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
+ the kernel has only one def of the relevant register).
+ If the address that is being auto-inc or auto-dec in DEST_NODE
+ is used in SRC_NODE then do not remove the edge to make sure
+ reg-moves will not be created for this address.
+ 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))
+ if (flag_modulo_sched_allow_regmoves
+ && (t == ANTI_DEP && dt == REG_DEP)
+ && !def_has_ccmode_p (dest_node->insn)
+ && !autoinc_var_is_used_p (dest_node->insn, src_node->insn))
{
rtx set;
if (set && REG_P (SET_DEST (set)))
{
int regno = REGNO (SET_DEST (set));
- struct df_ref *first_def;
- struct df_ref *last_def;
+ 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);
- last_def = df_bb_regno_last_def_find (g->bb, regno);
- if (first_def == last_def)
+ if (bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def)))
return;
}
}
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)
and anti-dependences from its uses in the current iteration to the
first definition in the next iteration. */
static void
-add_cross_iteration_register_deps (ddg_ptr g, struct df_ref *last_def)
+add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def)
{
int regno = DF_REF_REGNO (last_def);
struct df_link *r_use;
#ifdef ENABLE_CHECKING
struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
#endif
- struct df_ref *first_def = df_bb_regno_first_def_find (g->bb, regno);
+ df_ref first_def = df_bb_regno_first_def_find (g->bb, regno);
gcc_assert (last_def_node);
gcc_assert (first_def);
#ifdef ENABLE_CHECKING
- if (last_def->id != first_def->id)
- gcc_assert (!bitmap_bit_p (bb_info->gen, first_def->id));
+ 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. */
/* 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, TRUE_DEP,
+ create_ddg_dep_no_link (g, last_def_node, use_node,
+ DEBUG_INSN_P (use_insn) ? ANTI_DEP : TRUE_DEP,
REG_DEP, 1);
}
- else
+ 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
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,
- first_def->insn);
+ DF_REF_INSN (first_def));
gcc_assert (first_def_node);
- if (last_def->id != first_def->id
- || !flag_modulo_sched_allow_regmoves)
+ /* Always create the edge if the use node is a branch in
+ order to prevent the creation of reg-moves.
+ If the address that is being auto-inc or auto-dec in LAST_DEF
+ is used in USE_INSN then do not remove the edge to make sure
+ reg-moves will not be created for that address. */
+ if (DF_REF_ID (last_def) != DF_REF_ID (first_def)
+ || !flag_modulo_sched_allow_regmoves
+ || JUMP_P (use_node->insn)
+ || autoinc_var_is_used_p (DF_REF_INSN (last_def), use_insn)
+ || def_has_ccmode_p (DF_REF_INSN (last_def)))
create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP,
REG_DEP, 1);
{
ddg_node_ptr dest_node;
- if (last_def->id == first_def->id)
+ if (DF_REF_ID (last_def) == DF_REF_ID (first_def))
return;
- dest_node = get_node_of_insn (g, first_def->insn);
+ 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);
rd_bb_info = DF_RD_BB_INFO (g->bb);
/* Find inter-loop register output, true and anti deps. */
- EXECUTE_IF_SET_IN_BITMAP (rd_bb_info->gen, 0, rd_num, bi)
+ EXECUTE_IF_SET_IN_BITMAP (&rd_bb_info->gen, 0, rd_num, bi)
{
- struct df_ref *rd = DF_DEFS_GET (rd_num);
+ 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))
+ {
+ if (may_alias_p (*x, mem))
+ return 1;
+
+ return -1;
+ }
+ return 0;
+}
+
+static int
+walk_mems_1 (rtx *x, rtx *pat)
+{
+ if (MEM_P (*x))
+ {
+ /* 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 intra-loop mem deps
+ to ddg G. */
+static void
+add_intra_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
+{
+
+ if ((from->cuid == to->cuid)
+ || !insns_may_alias_p (from->insn, to->insn))
+ /* Do not create edge if memory references have disjoint alias sets
+ or 'to' and 'from' are the same instruction. */
+ return;
+
+ if (mem_write_insn_p (from->insn))
+ {
+ if (mem_read_insn_p (to->insn))
+ create_ddg_dep_no_link (g, from, to,
+ DEBUG_INSN_P (to->insn)
+ ? ANTI_DEP : TRUE_DEP, MEM_DEP, 0);
+ else
+ create_ddg_dep_no_link (g, from, to,
+ DEBUG_INSN_P (to->insn)
+ ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 0);
+ }
+ else if (!mem_read_insn_p (to->insn))
+ create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 0);
+}
+
/* Given two nodes, analyze their RTL insns and add inter-loop mem deps
to ddg G. */
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;
/* 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 (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. */
+ {
+ /* Don't bother calculating inter-loop dep if an intra-loop dep
+ already exists. */
if (! TEST_BIT (dest_node->successors, j))
add_inter_loop_mem_dep (g, dest_node, j_node);
+ /* If -fmodulo-sched-allow-regmoves
+ is set certain anti-dep edges are not created.
+ It might be that these anti-dep edges are on the
+ path from one memory instruction to another such that
+ removing these edges could cause a violation of the
+ memory dependencies. Thus we add intra edges between
+ every two memory instructions in this case. */
+ if (flag_modulo_sched_allow_regmoves
+ && !TEST_BIT (dest_node->predecessors, j))
+ add_intra_loop_mem_dep (g, j_node, dest_node);
+ }
}
}
}
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);
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. */
for (i = 0; i < all_sccs->num_sccs; i++)
free_scc (all_sccs->sccs[i]);
+ free (all_sccs->sccs);
free (all_sccs);
}
OSDN Git Service
