* Makefile.in (web.o): New.

	* web.c: New file.
	* rtl.h (web_main): Declare.
	* timervar.def (TV_WEB): New.
	* toplev.c (dump_file_index, dump_file_info): Add DFI_web.
	(rest_of_hanle_web): New.
	(flag_web): New static variable.
	(lang_independent_options): Add "web".
	(rest_of_compilation): Call rest_of_handle_web.
	* invoke.texi (-fweb): Document.
	* common.opt (fweb): New.
	* flags.h (flag_web): New.
	* opts.c (decode_options): Set flag_web at -O3.

	* passes.texi (web construction):  Document.
	* invoke.texi (-O3): Document that -fweb is enabled.

	* regrename.c (regrename_optimize): Deal better with situation when
	replacement failed.

	* sched-ebb.c: Include params.h and profile.h
	(schedule_ebbs):  Use tracer parameters to discover superblocks
	* Makefile.in (sched-ebb.o):  Add dependencies.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@72383 138bc75d-0d04-0410-961f-82ee72b054a4

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);
+}