diff options
author | Jing Yu <jingyu@google.com> | 2010-07-22 14:03:48 -0700 |
---|---|---|
committer | Jing Yu <jingyu@google.com> | 2010-07-22 14:03:48 -0700 |
commit | b094d6c4bf572654a031ecc4afe675154c886dc5 (patch) | |
tree | 89394c56b05e13a5413ee60237d65b0214fd98e2 /gcc-4.4.3/gcc/web.c | |
parent | dc34721ac3bf7e3c406fba8cfe9d139393345ec5 (diff) | |
download | toolchain_gcc-b094d6c4bf572654a031ecc4afe675154c886dc5.tar.gz toolchain_gcc-b094d6c4bf572654a031ecc4afe675154c886dc5.tar.bz2 toolchain_gcc-b094d6c4bf572654a031ecc4afe675154c886dc5.zip |
commit gcc-4.4.3 which is used to build gcc-4.4.3 Android toolchain in master.
The source is based on fsf gcc-4.4.3 and contains local patches which
are recorded in gcc-4.4.3/README.google.
Change-Id: Id8c6d6927df274ae9749196a1cc24dbd9abc9887
Diffstat (limited to 'gcc-4.4.3/gcc/web.c')
-rw-r--r-- | gcc-4.4.3/gcc/web.c | 393 |
1 files changed, 393 insertions, 0 deletions
diff --git a/gcc-4.4.3/gcc/web.c b/gcc-4.4.3/gcc/web.c new file mode 100644 index 000000000..2c5f93e3f --- /dev/null +++ b/gcc-4.4.3/gcc/web.c @@ -0,0 +1,393 @@ +/* Web construction code for GNU compiler. + Contributed by Jan Hubicka. + Copyright (C) 2001, 2002, 2004, 2006, 2007, 2008 + 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 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +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 COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +/* Simple optimization pass that splits independent uses of each pseudo, + increasing effectiveness of other optimizations. The optimization can + serve as an example of use for the dataflow module. + + We don't split registers with REG_USERVAR set unless -fmessy-debugging + is specified, because debugging information about such split variables + 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 + we expand only if the induction variable is dead afterward, which + is often the case). */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "toplev.h" + +#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 "timevar.h" +#include "tree-pass.h" + + +static rtx entry_register (struct web_entry *, df_ref, char *); +static void replace_ref (df_ref, rtx); + +/* Find the root of unionfind tree (the representative of set). */ + +struct web_entry * +unionfind_root (struct web_entry *element) +{ + struct web_entry *element1 = element, *element2; + + while (element->pred) + element = element->pred; + while (element1->pred) + { + element2 = element1->pred; + element1->pred = element; + element1 = element2; + } + return element; +} + +/* Union sets. + Return true if FIRST and SECOND points to the same web entry structure and + nothing is done. Otherwise, return false. */ + +bool +unionfind_union (struct web_entry *first, struct web_entry *second) +{ + first = unionfind_root (first); + second = unionfind_root (second); + if (first == second) + return true; + second->pred = first; + return false; +} + +/* For each use, all possible defs reaching it must come in the same + register, union them. + FUN is the function that does the union. */ + +void +union_defs (df_ref use, struct web_entry *def_entry, + 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 *use_link; + df_ref *eq_use_link; + df_ref *def_link; + rtx set; + + if (insn_info) + { + rtx insn = insn_info->insn; + use_link = DF_INSN_INFO_USES (insn_info); + 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. */ + use_link = NULL; + eq_use_link = NULL; + def_link = NULL; + set = NULL; + } + + /* 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. */ + + if (use_link) + while (*use_link) + { + if (use != *use_link + && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*use_link)) + (*fun) (use_entry + DF_REF_ID (use), + use_entry + DF_REF_ID (*use_link)); + use_link++; + } + + 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)) + { + 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++; + } + } + while (link) + { + (*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 (DF_REF_FLAGS (use) & DF_REF_READ_WRITE) + { + 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, df_ref ref, char *used) +{ + struct web_entry *root; + rtx reg, newreg; + + /* Find the corresponding web and see if it has been visited. */ + root = unionfind_root (entry); + if (root->reg) + return root->reg; + + /* 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)]) + 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_ATTRS (newreg) = REG_ATTRS (reg); + if (dump_file) + fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg), + REGNO (newreg)); + } + + root->reg = newreg; + return newreg; +} + +/* Replace the reference by REG. */ + +static void +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", + 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. */ + +static unsigned int +web_main (void) +{ + struct web_entry *def_entry; + struct web_entry *use_entry; + unsigned int max = max_reg_num (); + char *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 (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++; + } + } + } + + /* 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 (char, max); + use_entry = XCNEWVEC (struct web_entry, uses_num); + + /* Produce the web. */ + FOR_ALL_BB (bb) + FOR_BB_INSNS (bb, insn) + { + unsigned int uid = INSN_UID (insn); + if (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) + union_defs (use, def_entry, 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, use_entry, unionfind_union); + } + } + } + + /* Update the instruction stream, allocating new registers for split pseudos + in progress. */ + FOR_ALL_BB (bb) + FOR_BB_INSNS (bb, insn) + { + unsigned int uid = INSN_UID (insn); + if (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); + 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 */ + } +}; + |