X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;ds=sidebyside;f=gcc%2Fweb.c;h=ff917333f59bf486c997285e495ccd5bd292d642;hb=4d93673dd1c64f9dedcd35809946371cce2dd104;hp=2683511617242dde0db3ed1fa1c3599c48f2f64f;hpb=b04fab2aba38bf469795b687884b9656a498474d;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/web.c b/gcc/web.c index 26835116172..ff917333f59 100644 --- a/gcc/web.c +++ b/gcc/web.c @@ -1,12 +1,13 @@ /* Web construction code for GNU compiler. Contributed by Jan Hubicka. - Copyright (C) 2001, 2002, 2004 Free Software Foundation, Inc. + Copyright (C) 2001, 2002, 2004, 2006, 2007, 2008, 2010 + Free Software Foundation, Inc. This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free -Software Foundation; either version 2, or (at your option) any later +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -15,9 +16,8 @@ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 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. */ +along with GCC; see the file COPYING3. If not see +. */ /* Simple optimization pass that splits independent uses of each pseudo, increasing effectiveness of other optimizations. The optimization can @@ -28,14 +28,6 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA is almost unusable. TODO - - Add code to keep debugging up-to-date after splitting user variable - pseudos. This can be done by keeping track of all the pseudos used - for the variable and using life analysis information before reload - to determine which one is live and, in case more than one are live, - choose the one with the latest definition. - - Other optimization passes can benefit from the infrastructure too. - - We may use profile information and ignore infrequent use for the purpose of web unifying, inserting the compensation code later to implement full induction variable expansion for loops (currently @@ -51,31 +43,20 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "rtl.h" #include "hard-reg-set.h" #include "flags.h" +#include "obstack.h" #include "basic-block.h" #include "output.h" #include "df.h" #include "function.h" +#include "insn-config.h" +#include "recog.h" +#include "timevar.h" +#include "tree-pass.h" -/* This entry is allocated for each reference in the insn stream. */ -struct web_entry -{ - /* Pointer to the parent in the union/find tree. */ - struct web_entry *pred; - /* Newly assigned register to the entry. Set only for roots. */ - rtx reg; -}; - -static struct web_entry *unionfind_root (struct web_entry *); -static void unionfind_union (struct web_entry *, struct web_entry *); -static void union_defs (struct df *, struct ref *, struct web_entry *, - struct web_entry *); -static rtx entry_register (struct web_entry *, struct ref *, char *); -static void replace_ref (struct ref *, rtx); - /* Find the root of unionfind tree (the representative of set). */ -static struct web_entry * +struct web_entry * unionfind_root (struct web_entry *element) { struct web_entry *element1 = element, *element2; @@ -91,88 +72,175 @@ unionfind_root (struct web_entry *element) return element; } -/* Union sets. */ +/* Union sets. + Return true if FIRST and SECOND points to the same web entry structure and + nothing is done. Otherwise, return false. */ -static void +bool unionfind_union (struct web_entry *first, struct web_entry *second) { first = unionfind_root (first); second = unionfind_root (second); if (first == second) - return; + return true; second->pred = first; + return false; } -/* For each use, all possible defs reaching it must come in the same - register, union them. */ +/* For INSN, union all defs and uses that are linked by match_dup. + FUN is the function that does the union. */ static void -union_defs (struct df *df, struct ref *use, struct web_entry *def_entry, - struct web_entry *use_entry) +union_match_dups (rtx insn, struct web_entry *def_entry, + struct web_entry *use_entry, + bool (*fun) (struct web_entry *, struct web_entry *)) { - rtx insn = DF_REF_INSN (use); - struct df_link *link = DF_REF_CHAIN (use); - struct df_link *use_link = DF_INSN_USES (df, insn); - struct df_link *def_link = DF_INSN_DEFS (df, insn); - rtx set = single_set (insn); + struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn); + df_ref *use_link = DF_INSN_INFO_USES (insn_info); + df_ref *def_link = DF_INSN_INFO_DEFS (insn_info); + int i; - /* Some instructions may use match_dup for their operands. In case the - operands are dead, we will assign them different pseudos, creating - invalid instructions, so union all uses of the same operand for each - insn. */ + extract_insn (insn); - while (use_link) + for (i = 0; i < recog_data.n_dups; i++) { - if (use != use_link->ref - && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (use_link->ref)) - unionfind_union (use_entry + DF_REF_ID (use), - use_entry + DF_REF_ID (use_link->ref)); - use_link = use_link->next; + int op = recog_data.dup_num[i]; + enum op_type type = recog_data.operand_type[op]; + df_ref *ref, *dupref; + struct web_entry *entry; + + for (dupref = use_link; *dupref; dupref++) + if (DF_REF_LOC (*dupref) == recog_data.dup_loc[i]) + break; + + if (*dupref == NULL + || DF_REF_REGNO (*dupref) < FIRST_PSEUDO_REGISTER) + continue; + + ref = type == OP_IN ? use_link : def_link; + entry = type == OP_IN ? use_entry : def_entry; + for (; *ref; ref++) + if (DF_REF_LOC (*ref) == recog_data.operand_loc[op]) + break; + + (*fun) (use_entry + DF_REF_ID (*dupref), entry + DF_REF_ID (*ref)); } +} + +/* For each use, all possible defs reaching it must come in the same + register, union them. + FUN is the function that does the union. - /* Recognize trivial noop moves and attempt to keep them as noop. - While most of noop moves should be removed, we still keep some - of them at libcall boundaries and such. */ + In USED, we keep the DF_REF_ID of the first uninitialized uses of a + register, so that all uninitialized uses of the register can be + combined into a single web. We actually offset it by 2, because + the values 0 and 1 are reserved for use by entry_register. */ + +void +union_defs (df_ref use, struct web_entry *def_entry, + unsigned int *used, struct web_entry *use_entry, + bool (*fun) (struct web_entry *, struct web_entry *)) +{ + struct df_insn_info *insn_info = DF_REF_INSN_INFO (use); + struct df_link *link = DF_REF_CHAIN (use); + df_ref *eq_use_link; + df_ref *def_link; + rtx set; + + if (insn_info) + { + rtx insn = insn_info->insn; + eq_use_link = DF_INSN_INFO_EQ_USES (insn_info); + def_link = DF_INSN_INFO_DEFS (insn_info); + set = single_set (insn); + } + else + { + /* An artificial use. It links up with nothing. */ + eq_use_link = NULL; + def_link = NULL; + set = NULL; + } + + /* Union all occurrences of the same register in reg notes. */ + + if (eq_use_link) + while (*eq_use_link) + { + if (use != *eq_use_link + && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link)) + (*fun) (use_entry + DF_REF_ID (use), + use_entry + DF_REF_ID (*eq_use_link)); + eq_use_link++; + } + + /* Recognize trivial noop moves and attempt to keep them as noop. */ if (set && SET_SRC (set) == DF_REF_REG (use) && SET_SRC (set) == SET_DEST (set)) { - while (def_link) - { - if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def_link->ref)) - unionfind_union (use_entry + DF_REF_ID (use), - def_entry + DF_REF_ID (def_link->ref)); - def_link = def_link->next; - } + if (def_link) + while (*def_link) + { + if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link)) + (*fun) (use_entry + DF_REF_ID (use), + def_entry + DF_REF_ID (*def_link)); + def_link++; + } + } + + /* UD chains of uninitialized REGs are empty. Keeping all uses of + the same uninitialized REG in a single web is not necessary for + correctness, since the uses are undefined, but it's wasteful to + allocate one register or slot for each reference. Furthermore, + creating new pseudos for uninitialized references in debug insns + (see PR 42631) causes -fcompare-debug failures. We record the + number of the first uninitialized reference we found, and merge + with it any other uninitialized references to the same + register. */ + if (!link) + { + int regno = REGNO (DF_REF_REAL_REG (use)); + if (used[regno]) + (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2); + else + used[regno] = DF_REF_ID (use) + 2; } + while (link) { - unionfind_union (use_entry + DF_REF_ID (use), - def_entry + DF_REF_ID (link->ref)); + (*fun) (use_entry + DF_REF_ID (use), + def_entry + DF_REF_ID (link->ref)); link = link->next; } /* A READ_WRITE use requires the corresponding def to be in the same register. Find it and union. */ - if (use->flags & DF_REF_READ_WRITE) + if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE) { - struct df_link *link = DF_INSN_DEFS (df, DF_REF_INSN (use)); - - while (link) - { - if (DF_REF_REAL_REG (link->ref) == DF_REF_REAL_REG (use)) - unionfind_union (use_entry + DF_REF_ID (use), - def_entry + DF_REF_ID (link->ref)); - link = link->next; - } + df_ref *link; + + if (insn_info) + link = DF_INSN_INFO_DEFS (insn_info); + else + link = NULL; + + if (link) + while (*link) + { + if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use)) + (*fun) (use_entry + DF_REF_ID (use), + def_entry + DF_REF_ID (*link)); + link++; + } } } /* Find the corresponding register for the given entry. */ static rtx -entry_register (struct web_entry *entry, struct ref *ref, char *used) +entry_register (struct web_entry *entry, df_ref ref, unsigned int *used) { struct web_entry *root; rtx reg, newreg; @@ -185,23 +253,19 @@ entry_register (struct web_entry *entry, struct ref *ref, char *used) /* We are seeing this web for the first time, do the assignment. */ reg = DF_REF_REAL_REG (ref); - /* In case the original register is already assigned, generate new one. */ - if (!used[REGNO (reg)]) + /* In case the original register is already assigned, generate new + one. Since we use USED to merge uninitialized refs into a single + web, we might found an element to be nonzero without our having + used it. Test for 1, because union_defs saves it for our use, + and there won't be any use for the other values when we get to + this point. */ + if (used[REGNO (reg)] != 1) newreg = reg, used[REGNO (reg)] = 1; - else if (REG_USERVAR_P (reg) && 0/*&& !flag_messy_debugging*/) - { - newreg = reg; - if (dump_file) - fprintf (dump_file, - "New web forced to keep reg=%i (user variable)\n", - REGNO (reg)); - } else { newreg = gen_reg_rtx (GET_MODE (reg)); REG_USERVAR_P (newreg) = REG_USERVAR_P (reg); REG_POINTER (newreg) = REG_POINTER (reg); - REG_LOOP_TEST_P (newreg) = REG_LOOP_TEST_P (reg); REG_ATTRS (newreg) = REG_ATTRS (reg); if (dump_file) fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg), @@ -215,59 +279,152 @@ entry_register (struct web_entry *entry, struct ref *ref, char *used) /* Replace the reference by REG. */ static void -replace_ref (struct ref *ref, rtx reg) +replace_ref (df_ref ref, rtx reg) { rtx oldreg = DF_REF_REAL_REG (ref); rtx *loc = DF_REF_REAL_LOC (ref); + unsigned int uid = DF_REF_INSN_UID (ref); if (oldreg == reg) return; if (dump_file) fprintf (dump_file, "Updating insn %i (%i->%i)\n", - INSN_UID (DF_REF_INSN (ref)), REGNO (oldreg), REGNO (reg)); + uid, REGNO (oldreg), REGNO (reg)); *loc = reg; + df_insn_rescan (DF_REF_INSN (ref)); +} + + +static bool +gate_handle_web (void) +{ + return (optimize > 0 && flag_web); } /* Main entry point. */ -void +static unsigned int web_main (void) { - struct df *df; struct web_entry *def_entry; struct web_entry *use_entry; - unsigned int i; - int max = max_reg_num (); - char *used; - - df = df_init (); - df_analyze (df, 0, DF_UD_CHAIN | DF_EQUIV_NOTES); - - def_entry = xcalloc (df->n_defs, sizeof (struct web_entry)); - use_entry = xcalloc (df->n_uses, sizeof (struct web_entry)); - used = xcalloc (max, sizeof (char)); + unsigned int max = max_reg_num (); + unsigned int *used; + basic_block bb; + unsigned int uses_num = 0; + rtx insn; + + df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES); + df_chain_add_problem (DF_UD_CHAIN); + df_analyze (); + df_set_flags (DF_DEFER_INSN_RESCAN); + + /* Assign ids to the uses. */ + FOR_ALL_BB (bb) + FOR_BB_INSNS (bb, insn) + { + unsigned int uid = INSN_UID (insn); + if (NONDEBUG_INSN_P (insn)) + { + df_ref *use_rec; + for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) + { + df_ref use = *use_rec; + if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) + DF_REF_ID (use) = uses_num++; + } + for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++) + { + df_ref use = *use_rec; + if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) + DF_REF_ID (use) = uses_num++; + } + } + } - if (dump_file) - df_dump (df, DF_UD_CHAIN | DF_DU_CHAIN, dump_file); + /* Record the number of uses and defs at the beginning of the optimization. */ + def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE()); + used = XCNEWVEC (unsigned, max); + use_entry = XCNEWVEC (struct web_entry, uses_num); /* Produce the web. */ - for (i = 0; i < df->n_uses; i++) - union_defs (df, df->uses[i], def_entry, use_entry); + FOR_ALL_BB (bb) + FOR_BB_INSNS (bb, insn) + { + unsigned int uid = INSN_UID (insn); + if (NONDEBUG_INSN_P (insn)) + { + df_ref *use_rec; + union_match_dups (insn, def_entry, use_entry, unionfind_union); + for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) + { + df_ref use = *use_rec; + if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) + union_defs (use, def_entry, used, use_entry, unionfind_union); + } + for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++) + { + df_ref use = *use_rec; + if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) + union_defs (use, def_entry, used, use_entry, unionfind_union); + } + } + } /* Update the instruction stream, allocating new registers for split pseudos in progress. */ - for (i = 0; i < df->n_uses; i++) - replace_ref (df->uses[i], entry_register (use_entry + i, df->uses[i], - used)); - for (i = 0; i < df->n_defs; i++) - replace_ref (df->defs[i], entry_register (def_entry + i, df->defs[i], - used)); - - /* Dataflow information is corrupt here, but it can be easily updated - by creating new entries for new registers and updates or calling - df_insns_modify. */ + FOR_ALL_BB (bb) + FOR_BB_INSNS (bb, insn) + { + unsigned int uid = INSN_UID (insn); + if (NONDEBUG_INSN_P (insn)) + { + df_ref *use_rec; + df_ref *def_rec; + for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++) + { + df_ref use = *use_rec; + if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) + replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used)); + } + for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++) + { + df_ref use = *use_rec; + if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER) + replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used)); + } + for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) + { + df_ref def = *def_rec; + if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER) + replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used)); + } + } + } + free (def_entry); free (use_entry); free (used); - df_finish (df); + return 0; } + +struct rtl_opt_pass pass_web = +{ + { + RTL_PASS, + "web", /* name */ + gate_handle_web, /* gate */ + web_main, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_WEB, /* tv_id */ + 0, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_df_finish | TODO_verify_rtl_sharing | + TODO_dump_func /* todo_flags_finish */ + } +}; +