X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fddg.c;h=6fbf477b61df4e49ccea0f460126f1dd61bf18cd;hb=bca4d139fd7eb1b554c6701071c27048a0e458a6;hp=377ad99d502d88ba53e66776cee3e40e56af83a9;hpb=365db11eea46f39f4e46a11a6509d212e41c2307;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/ddg.c b/gcc/ddg.c index 377ad99d502..6fbf477b61d 100644 --- a/gcc/ddg.c +++ b/gcc/ddg.c @@ -1,5 +1,5 @@ /* DDG - Data Dependence Graph implementation. - Copyright (C) 2004 + Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc. Contributed by Ayal Zaks and Mustafa Hagog @@ -17,8 +17,8 @@ for more details. 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" @@ -29,7 +29,6 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #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" @@ -54,7 +53,7 @@ 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, 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, @@ -68,7 +67,7 @@ static bool mem_ref_p; 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; } @@ -92,7 +91,7 @@ mem_read_insn_p (rtx insn) 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; } @@ -116,7 +115,7 @@ rtx_mem_access_p (rtx x) if (x == 0) return false; - if (GET_CODE (x) == MEM) + if (MEM_P (x)) return true; code = GET_CODE (x); @@ -149,7 +148,7 @@ mem_access_insn_p (rtx insn) 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; @@ -164,15 +163,14 @@ create_ddg_dependence (ddg_ptr g, ddg_node_ptr src_node, 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); @@ -189,6 +187,8 @@ create_ddg_dependence (ddg_ptr g, ddg_node_ptr src_node, 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); } @@ -200,15 +200,23 @@ create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to, { 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) @@ -222,10 +230,10 @@ create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to, 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); @@ -235,13 +243,12 @@ add_deps_for_def (ddg_ptr g, struct df *df, struct ref *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; @@ -258,7 +265,7 @@ add_deps_for_def (ddg_ptr g, struct df *df, struct ref *rd) 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; @@ -267,7 +274,7 @@ add_deps_for_def (ddg_ptr g, struct df *df, struct ref *rd) /* 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); @@ -279,16 +286,16 @@ add_deps_for_def (ddg_ptr g, struct df *df, struct ref *rd) (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; @@ -296,17 +303,16 @@ add_deps_for_use (ddg_ptr g, struct df *df, struct ref *use) 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 - such a dep. */ - if (! bitmap_bit_p (bb_info->rd_gen, first_def->id)) + 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); } @@ -314,30 +320,34 @@ add_deps_for_use (ddg_ptr g, struct df *df, struct ref *use) 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 @@ -366,24 +376,25 @@ add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to) } /* Perform intra-block Data Dependency analysis and connect the nodes in - the DDG. We assume the loop has a single basic block. */ + the DDG. We assume the loop has a single basic block. */ static void build_intra_loop_deps (ddg_ptr g) { 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 dependecies using the scheduler dependecy + /* Build intra-loop data dependencies using the scheduler dependency analysis. */ for (i = 0; i < g->num_nodes; i++) { @@ -392,17 +403,16 @@ build_intra_loop_deps (ddg_ptr g) 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 @@ -477,17 +487,15 @@ create_ddg (basic_block bb, struct df *df, int closing_branch_deps) { 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) { @@ -505,11 +513,12 @@ create_ddg (basic_block bb, struct df *df, 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); + - if (!g->closing_branch) - abort (); /* Found no branch in DDG. */ - - /* Build the data dependecy graph. */ + /* Build the data dependency graph. */ build_intra_loop_deps (g); build_inter_loop_deps (g, df); return g; @@ -545,11 +554,12 @@ free_ddg (ddg_ptr 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; @@ -558,15 +568,15 @@ print_ddg_edge (FILE *dump_file, ddg_edge_ptr e) 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; @@ -574,34 +584,34 @@ print_ddg (FILE *dump_file, ddg_ptr g) { 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); @@ -609,16 +619,16 @@ vcg_print_ddg (FILE *dump_file, ddg_ptr g) /* 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. */ @@ -646,8 +656,8 @@ add_edge_to_ddg (ddg_ptr g ATTRIBUTE_UNUSED, ddg_edge_ptr e) 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); @@ -694,7 +704,8 @@ static ddg_scc_ptr 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; @@ -703,7 +714,7 @@ create_scc (ddg_ptr g, sbitmap nodes) 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]; @@ -715,7 +726,7 @@ create_scc (ddg_ptr g, sbitmap nodes) if (e->distance > 0) add_backarc_to_scc (scc, e); } - }); + } set_recurrence_length (scc, g); return scc; @@ -784,13 +795,14 @@ get_node_of_insn (ddg_ptr g, rtx insn) 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); @@ -802,13 +814,14 @@ find_successors (sbitmap succ, ddg_ptr g, sbitmap 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); @@ -898,13 +911,16 @@ free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs) /* 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); @@ -919,7 +935,7 @@ find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap 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]; @@ -936,7 +952,7 @@ find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to) change = 1; } } - }); + } } sbitmap_copy (reach_to, to); @@ -948,7 +964,7 @@ find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap 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]; @@ -965,7 +981,7 @@ find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to) change = 1; } } - }); + } } answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to); @@ -1010,7 +1026,8 @@ update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp) 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; @@ -1029,15 +1046,17 @@ longest_simple_path (struct ddg * g, int src, int dest, sbitmap 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);