new web construction pass

[Jan Hubicka <jh at suse dot cz>]

Hi,
this patch adds new "web" pass that construct webs using df.c module and
split single pseudo to multiple if possible.

While I've implemented the pass as a excercise to famialize myself with df.c
design, it appears to help mesurably in common benchmarks (bzip,
stephanov,...).  It is because it makes several optimizations stronger (not
only register allocation). For instance delete_trivially_dead_insns is now
as string as dead code removal in life analyzis, copy and CSE works better now
too.

For instance sequence:
*a++=0;
*a++=0;
*a++=0;
*a++=0;

now avoids multiple increments.

It takes about 1% of CPU time on compiling combine and saves about 1% of
instructions there.

Also it will hopefully serve as testcase for df.c to fix it before nontrivial
code depdedent on it will get in.

It has problems with debug information updating. At the moment I prohibit
splitting of user variables unless -fmessy-debugging is set that makes the
pass somewhat humorous, but interestingly enought still effective.

Bootstrapped/regtested i686.

Depends on the two df.c fixes I've sent at the beggining of week.

Fri Sep 28 19:08:55 CEST 2001  Jan Hubicka  <jh@suse.cz>
	* Makefile.in (web.o): Add.
	* rtl.h (web_main): Add prototype.
	* timervar.def (TV_WEB): New.
	* toplev.c (dump_file_index): Add DFI_web.
	(dump_file_info): Add "web".
	(flag_web): New static variable.
	(f_options): Add "web".
	(rest_of_compilation): Call web_main.
	(toplev_main): Add flag_web.
	* web.c: New file.
diff -Nrc3p /p2/cfg9/egcs/gcc/Makefile.in gcc/Makefile.in
*** /p2/cfg9/egcs/gcc/Makefile.in	Thu Sep 20 18:45:12 2001
--- gcc/Makefile.in	Thu Sep 27 13:21:43 2001
*************** OBJS =									\
*** 747,753 ****
   sdbout.o sibcall.o simplify-rtx.o splay-tree.o ssa.o ssa-ccp.o         \
   ssa-dce.o stmt.o stor-layout.o stringpool.o timevar.o toplev.o tree.o  \
   unroll.o varasm.o varray.o version.o xcoffout.o cfg.o cfganal.o	\
!  cfgbuild.o cfgcleanup.o cfgloop.o cfgrtl.o        \
   $(GGC) $(out_object_file) $(EXTRA_OBJS)
  
  BACKEND = main.o libbackend.a
--- 747,753 ----
   sdbout.o sibcall.o simplify-rtx.o splay-tree.o ssa.o ssa-ccp.o         \
   ssa-dce.o stmt.o stor-layout.o stringpool.o timevar.o toplev.o tree.o  \
   unroll.o varasm.o varray.o version.o xcoffout.o cfg.o cfganal.o	\
!  cfgbuild.o cfgcleanup.o cfgloop.o cfgrtl.o web.o        \
   $(GGC) $(out_object_file) $(EXTRA_OBJS)
  
  BACKEND = main.o libbackend.a
*************** cse.o : cse.c $(CONFIG_H) $(SYSTEM_H) $(
*** 1451,1456 ****
--- 1451,1459 ----
     real.h insn-config.h $(RECOG_H) $(EXPR_H) toplev.h output.h function.h \
     $(BASIC_BLOCK_H) $(GGC_H) $(TM_P_H)
  gcse.o : gcse.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(REGS_H) hard-reg-set.h \
+    flags.h real.h insn-config.h ggc.h $(RECOG_H) $(EXPR_H) $(BASIC_BLOCK_H) \
+    function.h output.h toplev.h $(TM_P_H) $(PARAMS_H)
+ web.o : gcse.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(REGS_H) hard-reg-set.h \
     flags.h real.h insn-config.h ggc.h $(RECOG_H) $(EXPR_H) $(BASIC_BLOCK_H) \
     function.h output.h toplev.h $(TM_P_H) $(PARAMS_H)
  sibcall.o : sibcall.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(REGS_H) function.h \
diff -Nrc3p /p2/cfg9/egcs/gcc/rtl.h gcc/rtl.h
*** /p2/cfg9/egcs/gcc/rtl.h	Thu Sep 20 18:33:14 2001
--- gcc/rtl.h	Thu Sep 27 13:39:11 2001
*************** extern rtx expand_mult_highpart		PARAMS 
*** 1857,1862 ****
--- 1859,1867 ----
  extern int gcse_main			PARAMS ((rtx, FILE *));
  #endif
  
+ /* In web.c */
+ extern void web_main			PARAMS ((void));
+ 
  /* In global.c */
  extern void mark_elimination		PARAMS ((int, int));
  #ifdef BUFSIZ
diff -Nrc3p /p2/cfg9/egcs/gcc/timevar.def gcc/timevar.def
*** /p2/cfg9/egcs/gcc/timevar.def	Thu Sep 20 18:33:14 2001
--- gcc/timevar.def	Thu Sep 27 13:38:55 2001
*************** DEFTIMEVAR (TV_VARCONST              , "
*** 52,57 ****
--- 52,58 ----
  DEFTIMEVAR (TV_INTEGRATION           , "integration")
  DEFTIMEVAR (TV_JUMP                  , "jump")
  DEFTIMEVAR (TV_CSE                   , "CSE")
+ DEFTIMEVAR (TV_WEB                   , "web construction")
  DEFTIMEVAR (TV_GCSE                  , "global CSE")
  DEFTIMEVAR (TV_LOOP                  , "loop analysis")
  DEFTIMEVAR (TV_CSE2                  , "CSE 2")
diff -Nrc3p /p2/cfg9/egcs/gcc/toplev.c gcc/toplev.c
*** /p2/cfg9/egcs/gcc/toplev.c	Thu Sep 20 18:33:13 2001
--- gcc/toplev.c	Thu Sep 27 15:36:53 2001
*************** enum dump_file_index
*** 263,268 ****
--- 263,269 ----
    DFI_ussa,
    DFI_cse,
    DFI_addressof,
+   DFI_web,
    DFI_gcse,
    DFI_loop,
    DFI_cse2,
*************** struct dump_file_info dump_file[DFI_MAX]
*** 309,314 ****
--- 310,316 ----
    { "ussa",	'e', 1, 0, 0 },	/* Yes, duplicate enable switch.  */
    { "cse",	's', 0, 0, 0 },
    { "addressof", 'F', 0, 0, 0 },
+   { "web",      'Z', 0, 0, 0 },
    { "gcse",	'G', 1, 0, 0 },
    { "loop",	'L', 1, 0, 0 },
    { "cse2",	't', 1, 0, 0 },
*************** int flag_syntax_only = 0;
*** 659,664 ****
--- 661,669 ----
  
  static int flag_gcse;
  
+ /* Nonzero means performs web construction pass.  */
+ static int flag_web;
+ 
  /* Nonzero means to use global dataflow analysis to eliminate
     useless null pointer tests.  */
  
*************** lang_independent_options f_options[] =
*** 1061,1066 ****
--- 1069,1076 ----
     N_("Return 'short' aggregates in registers") },
    {"delayed-branch", &flag_delayed_branch, 1,
     N_("Attempt to fill delay slots of branch instructions") },
+   {"web", &flag_web, 1,
+    N_("Construct webs and split unrelated uses of single variable") },
    {"gcse", &flag_gcse, 1,
     N_("Perform the global common subexpression elimination") },
    {"gcse-lm", &flag_gcse_lm, 1,
*************** rest_of_compilation (decl)
*** 2957,2962 ****
--- 2969,2987 ----
        find_basic_blocks (insns, max_reg_num (), rtl_dump_file);
        cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_PRE_LOOP);
  
+       if (flag_web)
+ 	{
+ 	  timevar_push (TV_WEB);
+ 	  open_dump_file (DFI_web, decl);
+ 
+ 	  web_main ();
+ 	  delete_trivially_dead_insns (insns, max_reg_num (), 0);
+ 	  cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_PRE_LOOP);
+ 
+ 	  close_dump_file (DFI_web, print_rtl_with_bb, insns);
+ 	  timevar_pop (TV_WEB);
+ 	}
+ 
        /* ??? Run if-conversion before delete_null_pointer_checks,
           since the later does not preserve the CFG.  This should
  	 be changed -- no since converting if's that are going to
*************** toplev_main (argc, argv)
*** 4741,4746 ****
--- 4771,4777 ----
    if (optimize >= 2)
      {
        flag_optimize_sibling_calls = 1;
+       flag_web = 1;
        flag_cse_follow_jumps = 1;
        flag_cse_skip_blocks = 1;
        flag_gcse = 1;
diff -Nrc3p /p2/cfg9/egcs/gcc/web.c gcc/web.c
*** /p2/cfg9/egcs/gcc/web.c	Thu Jan  1 01:00:00 1970
--- gcc/web.c	Thu Sep 27 15:20:40 2001
***************
*** 0 ****
--- 1,281 ----
+ /* Web construction code for GNU compiler.
+    Contributed by Jan Hubicka
+    Copyright (C) 2001 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 "toplev.h"
+ 
+ #include "rtl.h"
+ #include "hard-reg-set.h"
+ #include "flags.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "df.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;
+ {
+   struct df_link *link = DF_REF_CHAIN (use);
+ 
+   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;
+   if (REG_USERVAR_P (reg) && !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));
+       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);
+ }