diff options
Diffstat (limited to 'gcc/web.c')
| -rw-r--r-- | gcc/web.c | 323 |
1 files changed, 323 insertions, 0 deletions
diff --git a/gcc/web.c b/gcc/web.c new file mode 100644 index 00000000000..e200453971a --- /dev/null +++ b/gcc/web.c @@ -0,0 +1,323 @@ +/* Web construction code for GNU compiler. + Contributed by Jan Hubicka + Copyright (C) 2001, 2002 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 +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 COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +/* Simple optimization pass that splits indepdendent uses of each pseudo + increasing effectivity of other optimizations. The optimization can + serve as an example of the use of dataflow module. + + We don't split registers with REG_USERVAR set unless -fmessy-debugging is + used, because debug information about such split variables is almost + useless. + + TODO + - Add code to keep debugging up-to-date after splitting of user variable + pseudos. This can be done by remembering all the pseudos used for the + variable and use life analysis information before reload to determing + wich one of the possible choices is alive and in case more are live, + choose one with latest definition. + + Some other optimization passes will benefit from the infrastructure + too. + + - We may use profile information and ignore infrequent use for purposes + of web unifying inserting the compensation code later to implement full + induction variable expansion for loops (currently we expand only if + induction is dead afterwards, that is often the case anyway). */ + +#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 "basic-block.h" +#include "output.h" +#include "df.h" +#include "function.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 PARAMS ((struct web_entry *)); +static void unionfind_union PARAMS ((struct web_entry *, + struct web_entry *)); +static void union_defs PARAMS ((struct df *, struct ref *, + struct web_entry *, + struct web_entry *)); +static rtx entry_register PARAMS ((struct web_entry *, + struct ref *, char *, char *)); +static void replace_ref PARAMS ((struct ref *, rtx)); +static int mark_addressof PARAMS ((rtx *, void *)); + +/* Find the root of unionfind tree (the representatnt of set). */ + +static struct web_entry * +unionfind_root (element) + 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. */ + +static void +unionfind_union (first, second) + struct web_entry *first, *second; +{ + first = unionfind_root (first); + second = unionfind_root (second); + if (first == second) + return; + second->pred = first; +} + +/* For each use, all possible defs reaching it must come in same register, + union them. */ + +static void +union_defs (df, use, def_entry, use_entry) + struct df *df; + struct ref *use; + struct web_entry *def_entry; + struct web_entry *use_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); + + /* Some instructions may use match_dup for it's operands. In case the + operands are dead, we will assign them different pseudos creating + invalid instruction, so union all uses of the same operands for each + insn. */ + + while (use_link) + { + 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; + } + + /* Recognize trivial noop moves and attempt to keep them noop. + While most of noop moves should be removed we still keep some at + libcall boundaries and such. */ + + 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; + } + } + while (link) + { + unionfind_union (use_entry + DF_REF_ID (use), + def_entry + DF_REF_ID (link->ref)); + link = link->next; + } + + /* An READ_WRITE use require the corresponding def to be in the same + register. Find it and union. */ + if (use->flags & DF_REF_READ_WRITE) + { + struct df_link *link = DF_INSN_DEFS (df, DF_REF_INSN (use)); + + while (DF_REF_REAL_REG (link->ref) != DF_REF_REAL_REG (use)) + link = link->next; + + unionfind_union (use_entry + DF_REF_ID (use), + def_entry + DF_REF_ID (link->ref)); + } +} + +/* Find corresponding register for given entry. */ + +static rtx +entry_register (entry, ref, used, use_addressof) + struct web_entry *entry; + struct ref *ref; + char *used; + char *use_addressof; +{ + struct web_entry *root; + rtx reg, newreg; + + /* Find corresponding web and see if it has been visited. */ + + root = unionfind_root (entry); + if (root->reg) + return root->reg; + + /* We are seeing this web 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 (rtl_dump_file) + fprintf (rtl_dump_file, + "New web forced to keep reg=%i (user variable)\n", + REGNO (reg)); + } + else if (use_addressof [REGNO (reg)]) + { + newreg = reg; + if (rtl_dump_file) + fprintf (rtl_dump_file, + "New web forced to keep reg=%i (address taken)\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); + RTX_UNCHANGING_P (newreg) = RTX_UNCHANGING_P (reg); + REG_ATTRS (newreg) = REG_ATTRS (reg); + if (rtl_dump_file) + fprintf (rtl_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 (ref, reg) + struct ref *ref; + rtx reg; +{ + rtx oldreg = DF_REF_REAL_REG (ref); + rtx *loc = DF_REF_REAL_LOC (ref); + + if (oldreg == reg) + return; + if (rtl_dump_file) + fprintf (rtl_dump_file, "Updating insn %i (%i->%i)\n", + INSN_UID (DF_REF_INSN (ref)), REGNO (oldreg), REGNO (reg)); + *loc = reg; +} + +/* Mark each pseudo, whose address is taken. */ + +static int +mark_addressof (rtl, data) + rtx *rtl; + void *data; +{ + if (!*rtl) + return 0; + if (GET_CODE (*rtl) == ADDRESSOF + && REG_P (XEXP (*rtl, 0))) + ((char *)data)[REGNO (XEXP (*rtl, 0))] = 1; + return 0; +} + +/* Main entry point. */ + +void +web_main () +{ + struct df *df; + struct web_entry *def_entry; + struct web_entry *use_entry; + unsigned int i; + int max = max_reg_num (); + char *used; + char *use_addressof; + rtx insn; + + df = df_init (); + df_analyse (df, 0, DF_UD_CHAIN | DF_EQUIV_NOTES); + + def_entry = + (struct web_entry *) xcalloc (df->n_defs, sizeof (struct web_entry)); + use_entry = + (struct web_entry *) xcalloc (df->n_uses, sizeof (struct web_entry)); + used = (char *) xcalloc (max, sizeof (char)); + use_addressof = (char *) xcalloc (max, sizeof (char)); + + if (rtl_dump_file) + df_dump (df, DF_UD_CHAIN | DF_DU_CHAIN, rtl_dump_file); + + /* Produce the web. */ + for (i = 0; i < df->n_uses; i++) + union_defs (df, df->uses[i], def_entry, use_entry); + + /* We can not safely rename registers whose address is taken. */ + for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) + if (INSN_P (insn)) + for_each_rtx (&PATTERN (insn), mark_addressof, use_addressof); + + /* 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, use_addressof)); + for (i = 0; i < df->n_defs; i++) + replace_ref (df->defs[i], entry_register (def_entry + i, df->defs[i], + used, use_addressof)); + + /* Dataflow information is corrupt here, but it can be easy to update it + by creating new entries for new registers and update or calilng + df_insns_modify. */ + free (def_entry); + free (use_entry); + free (used); + free (use_addressof); + df_finish (df); +} |