X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;ds=sidebyside;f=gcc%2Fddg.c;h=a5158827638942dc32cccf876360e90b4a8d3644;hb=6b1b2cb74b2779a3aaf5d134289bfaa80ea0cb76;hp=c67b6c2486989f545a89436a0907ece8007d77a4;hpb=2e49e3bce41a772e383c119a06432fbaa8295f62;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/ddg.c b/gcc/ddg.c index c67b6c24869..a5158827638 100644 --- a/gcc/ddg.c +++ b/gcc/ddg.c @@ -1,5 +1,5 @@ /* 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 @@ -24,7 +24,7 @@ along with GCC; see the file COPYING3. If not see #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" @@ -145,6 +145,45 @@ mem_access_insn_p (rtx insn) 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 @@ -166,14 +205,23 @@ create_ddg_dep_from_intra_loop_link (ddg_ptr g, ddg_node_ptr src_node, 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; @@ -183,14 +231,13 @@ create_ddg_dep_from_intra_loop_link (ddg_ptr g, ddg_node_ptr src_node, 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; } } @@ -210,6 +257,9 @@ create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to, 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) @@ -240,7 +290,7 @@ create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to, 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; @@ -251,14 +301,15 @@ add_cross_iteration_register_deps (ddg_ptr g, struct df_ref *last_def) #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. */ @@ -278,10 +329,11 @@ add_cross_iteration_register_deps (ddg_ptr g, struct df_ref *last_def) /* 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 @@ -290,12 +342,20 @@ add_cross_iteration_register_deps (ddg_ptr g, struct df_ref *last_def) 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); @@ -312,10 +372,10 @@ add_cross_iteration_register_deps (ddg_ptr g, struct df_ref *last_def) { 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); @@ -332,26 +392,98 @@ build_inter_loop_deps (ddg_ptr g) 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 { @@ -359,8 +491,11 @@ add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to) 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); } } @@ -373,12 +508,12 @@ build_intra_loop_deps (ddg_ptr g) { 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); @@ -414,11 +549,25 @@ build_intra_loop_deps (ddg_ptr g) 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); + } } } } @@ -455,15 +604,20 @@ create_ddg (basic_block bb, int closing_branch_deps) 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; @@ -506,10 +660,10 @@ create_ddg (basic_block bb, int closing_branch_deps) 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); @@ -852,9 +1006,9 @@ static int 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. */ @@ -949,6 +1103,7 @@ free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs) for (i = 0; i < all_sccs->num_sccs; i++) free_scc (all_sccs->sccs[i]); + free (all_sccs->sccs); free (all_sccs); }