/* Web construction code for GNU compiler.
- Contributed by Jan Hubicka
- Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+ Contributed by Jan Hubicka.
+ Copyright (C) 2001, 2002, 2004 Free Software Foundation, Inc.
This file is part of GCC.
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.
+/* 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
- used, because debug information about such split variables is almost
- useless.
+ 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 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.
+ - 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.
- Some other optimization passes will benefit from the infrastructure
- too.
+ Other optimization passes can 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). */
+ - 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"
/* This entry is allocated for each reference in the insn stream. */
struct web_entry
{
- /* pointer to the parent in the union/find tree. */
+ /* Pointer to the parent in the union/find tree. */
struct web_entry *pred;
- /* Newly assigned register to the entry. Set only for roots. */
+ /* 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 *));
+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 representatnt of set). */
+/* Find the root of unionfind tree (the representative of set). */
static struct web_entry *
-unionfind_root (element)
- struct web_entry *element;
+unionfind_root (struct web_entry *element)
{
struct web_entry *element1 = element, *element2;
/* Union sets. */
static void
-unionfind_union (first, second)
- struct web_entry *first, *second;
+unionfind_union (struct web_entry *first, struct web_entry *second)
{
first = unionfind_root (first);
second = unionfind_root (second);
second->pred = first;
}
-/* For each use, all possible defs reaching it must come in same register,
- union them. */
+/* For each use, all possible defs reaching it must come in the 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;
+union_defs (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 *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
+ /* 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. */
while (use_link)
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. */
+ /* 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. */
if (set
&& SET_SRC (set) == DF_REF_REG (use)
link = link->next;
}
- /* An READ_WRITE use require the corresponding def to be in the same
+ /* 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)
{
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));
+ 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;
+ }
}
}
-/* Find corresponding register for given entry. */
+/* Find the corresponding register for the given entry. */
static rtx
-entry_register (entry, ref, used, use_addressof)
- struct web_entry *entry;
- struct ref *ref;
- char *used;
- char *use_addressof;
+entry_register (struct web_entry *entry, struct ref *ref, char *used)
{
struct web_entry *root;
rtx reg, newreg;
- /* Find corresponding web and see if it has been visited. */
-
+ /* 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 first time, do the assignment. */
-
+ /* 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. */
else if (REG_USERVAR_P (reg) && 0/*&& !flag_messy_debugging*/)
{
newreg = reg;
- if (rtl_dump_file)
- fprintf (rtl_dump_file,
+ if (dump_file)
+ fprintf (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_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),
+ if (dump_file)
+ fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
REGNO (newreg));
}
/* Replace the reference by REG. */
static void
-replace_ref (ref, reg)
- struct ref *ref;
- rtx reg;
+replace_ref (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",
+ if (dump_file)
+ fprintf (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 ()
+web_main (void)
{
struct df *df;
struct web_entry *def_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);
+ df_analyze (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));
+ 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));
- if (rtl_dump_file)
- df_dump (df, DF_UD_CHAIN | DF_DU_CHAIN, rtl_dump_file);
+ if (dump_file)
+ df_dump (df, DF_UD_CHAIN | DF_DU_CHAIN, 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));
+ used));
for (i = 0; i < df->n_defs; i++)
replace_ref (df->defs[i], entry_register (def_entry + i, df->defs[i],
- used, use_addressof));
+ used));
- /* Dataflow information is corrupt here, but it can be easy to update it
- by creating new entries for new registers and update or calilng
+ /* 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. */
free (def_entry);
free (use_entry);
free (used);
- free (use_addressof);
df_finish (df);
}