gcc/web.c

   1 /* Web construction code for GNU compiler.
   2    Contributed by Jan Hubicka
   3    Copyright (C) 2001, 2002 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* Simple optimization pass that splits indepdendent uses of each pseudo
  23    increasing effectivity of other optimizations.  The optimization can
  24    serve as an example of the use of dataflow module.
  25
  26    We don't split registers with REG_USERVAR set unless -fmessy-debugging is
  27    used, because debug information about such split variables is almost
  28    useless.
  29
  30    TODO
  31     - Add code to keep debugging up-to-date after splitting of user variable
  32       pseudos.  This can be done by remembering all the pseudos used for the
  33       variable and use life analysis information before reload to determing
  34       wich one of the possible choices is alive and in case more are live,
  35       choose one with latest definition.
  36
  37       Some other optimization passes will benefit from the infrastructure
  38       too.
  39
  40     - We may use profile information and ignore infrequent use for purposes
  41       of web unifying inserting the compensation code later to implement full
  42       induction variable expansion for loops (currently we expand only if
  43       induction is dead afterwards, that is often the case anyway).  */
  44
  45 #include "config.h"
  46 #include "system.h"
  47 #include "coretypes.h"
  48 #include "tm.h"
  49 #include "toplev.h"
  50
  51 #include "rtl.h"
  52 #include "hard-reg-set.h"
  53 #include "flags.h"
  54 #include "basic-block.h"
  55 #include "output.h"
  56 #include "df.h"
  57 #include "function.h"
  58
  59
  60 /* This entry is allocated for each reference in the insn stream.  */
  61 struct web_entry
  62 {
  63     /* pointer to the parent in the union/find tree.  */
  64   struct web_entry *pred;
  65     /* Newly assigned register to the entry.  Set only for roots.  */
  66   rtx reg;
  67 };
  68
  69 static struct web_entry *unionfind_root PARAMS ((struct web_entry *));
  70 static void unionfind_union             PARAMS ((struct web_entry *,
  71                                                  struct web_entry *));
  72 static void union_defs                  PARAMS ((struct df *, struct ref *,
  73                                                  struct web_entry *,
  74                                                  struct web_entry *));
  75 static rtx entry_register               PARAMS ((struct web_entry *,
  76                                                  struct ref *, char *, char *));
  77 static void replace_ref                 PARAMS ((struct ref *, rtx));
  78 static int mark_addressof               PARAMS ((rtx *, void *));
  79
  80 /* Find the root of unionfind tree (the representatnt of set).  */
  81
  82 static struct web_entry *
  83 unionfind_root (element)
  84      struct web_entry *element;
  85 {
  86   struct web_entry *element1 = element, *element2;
  87
  88   while (element->pred)
  89     element = element->pred;
  90   while (element1->pred)
  91     {
  92       element2 = element1->pred;
  93       element1->pred = element;
  94       element1 = element2;
  95     }
  96   return element;
  97 }
  98
  99 /* Union sets.  */
 100
 101 static void
 102 unionfind_union (first, second)
 103      struct web_entry *first, *second;
 104 {
 105   first = unionfind_root (first);
 106   second = unionfind_root (second);
 107   if (first == second)
 108     return;
 109   second->pred = first;
 110 }
 111
 112 /* For each use, all possible defs reaching it must come in same register,
 113    union them.  */
 114
 115 static void
 116 union_defs (df, use, def_entry, use_entry)
 117      struct df *df;
 118      struct ref *use;
 119      struct web_entry *def_entry;
 120      struct web_entry *use_entry;
 121 {
 122   rtx insn = DF_REF_INSN (use);
 123   struct df_link *link = DF_REF_CHAIN (use);
 124   struct df_link *use_link = DF_INSN_USES (df, insn);
 125   struct df_link *def_link = DF_INSN_DEFS (df, insn);
 126   rtx set = single_set (insn);
 127
 128   /* Some instructions may use match_dup for it's operands.  In case the
 129      operands are dead, we will assign them different pseudos creating
 130      invalid instruction, so union all uses of the same operands for each
 131      insn.  */
 132
 133   while (use_link)
 134     {
 135       if (use != use_link->ref
 136           && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (use_link->ref))
 137         unionfind_union (use_entry + DF_REF_ID (use),
 138                          use_entry + DF_REF_ID (use_link->ref));
 139       use_link = use_link->next;
 140     }
 141
 142   /* Recognize trivial noop moves and attempt to keep them noop.
 143      While most of noop moves should be removed we still keep some at
 144      libcall boundaries and such.  */
 145
 146   if (set
 147       && SET_SRC (set) == DF_REF_REG (use)
 148       && SET_SRC (set) == SET_DEST (set))
 149     {
 150       while (def_link)
 151         {
 152           if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def_link->ref))
 153             unionfind_union (use_entry + DF_REF_ID (use),
 154                              def_entry + DF_REF_ID (def_link->ref));
 155           def_link = def_link->next;
 156         }
 157     }
 158   while (link)
 159     {
 160       unionfind_union (use_entry + DF_REF_ID (use),
 161                        def_entry + DF_REF_ID (link->ref));
 162       link = link->next;
 163     }
 164
 165   /* An READ_WRITE use require the corresponding def to be in the same
 166      register.  Find it and union.  */
 167   if (use->flags & DF_REF_READ_WRITE)
 168     {
 169       struct df_link *link = DF_INSN_DEFS (df, DF_REF_INSN (use));
 170
 171       while (DF_REF_REAL_REG (link->ref) != DF_REF_REAL_REG (use))
 172         link = link->next;
 173
 174       unionfind_union (use_entry + DF_REF_ID (use),
 175                        def_entry + DF_REF_ID (link->ref));
 176     }
 177 }
 178
 179 /* Find corresponding register for given entry.  */
 180
 181 static rtx
 182 entry_register (entry, ref, used, use_addressof)
 183      struct web_entry *entry;
 184      struct ref *ref;
 185      char *used;
 186      char *use_addressof;
 187 {
 188   struct web_entry *root;
 189   rtx reg, newreg;
 190
 191   /* Find corresponding web and see if it has been visited.  */
 192
 193   root = unionfind_root (entry);
 194   if (root->reg)
 195     return root->reg;
 196
 197   /* We are seeing this web first time, do the assignment.  */
 198
 199   reg = DF_REF_REAL_REG (ref);
 200
 201   /* In case the original register is already assigned, generate new one.  */
 202   if (!used[REGNO (reg)])
 203     newreg = reg, used[REGNO (reg)] = 1;
 204   else if (REG_USERVAR_P (reg) && 0/*&& !flag_messy_debugging*/)
 205     {
 206       newreg = reg;
 207       if (rtl_dump_file)
 208         fprintf (rtl_dump_file,
 209                  "New web forced to keep reg=%i (user variable)\n",
 210                  REGNO (reg));
 211     }
 212   else if (use_addressof [REGNO (reg)])
 213     {
 214       newreg = reg;
 215       if (rtl_dump_file)
 216         fprintf (rtl_dump_file,
 217                  "New web forced to keep reg=%i (address taken)\n",
 218                  REGNO (reg));
 219     }
 220   else
 221     {
 222       newreg = gen_reg_rtx (GET_MODE (reg));
 223       REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
 224       REG_POINTER (newreg) = REG_POINTER (reg);
 225       REG_LOOP_TEST_P (newreg) = REG_LOOP_TEST_P (reg);
 226       RTX_UNCHANGING_P (newreg) = RTX_UNCHANGING_P (reg);
 227       REG_ATTRS (newreg) = REG_ATTRS (reg);
 228       if (rtl_dump_file)
 229         fprintf (rtl_dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
 230                  REGNO (newreg));
 231     }
 232
 233   root->reg = newreg;
 234   return newreg;
 235 }
 236
 237 /* Replace the reference by REG.  */
 238
 239 static void
 240 replace_ref (ref, reg)
 241    struct ref *ref;
 242    rtx reg;
 243 {
 244   rtx oldreg = DF_REF_REAL_REG (ref);
 245   rtx *loc = DF_REF_REAL_LOC (ref);
 246
 247   if (oldreg == reg)
 248     return;
 249   if (rtl_dump_file)
 250     fprintf (rtl_dump_file, "Updating insn %i (%i->%i)\n",
 251              INSN_UID (DF_REF_INSN (ref)), REGNO (oldreg), REGNO (reg));
 252   *loc = reg;
 253 }
 254
 255 /* Mark each pseudo, whose address is taken.  */
 256
 257 static int
 258 mark_addressof (rtl, data)
 259      rtx *rtl;
 260      void *data;
 261 {
 262   if (!*rtl)
 263     return 0;
 264   if (GET_CODE (*rtl) == ADDRESSOF
 265       && REG_P (XEXP (*rtl, 0)))
 266     ((char *)data)[REGNO (XEXP (*rtl, 0))] = 1;
 267   return 0;
 268 }
 269
 270 /* Main entry point.  */
 271
 272 void
 273 web_main ()
 274 {
 275   struct df *df;
 276   struct web_entry *def_entry;
 277   struct web_entry *use_entry;
 278   unsigned int i;
 279   int max = max_reg_num ();
 280   char *used;
 281   char *use_addressof;
 282   rtx insn;
 283
 284   df = df_init ();
 285   df_analyse (df, 0, DF_UD_CHAIN | DF_EQUIV_NOTES);
 286
 287   def_entry =
 288     (struct web_entry *) xcalloc (df->n_defs, sizeof (struct web_entry));
 289   use_entry =
 290     (struct web_entry *) xcalloc (df->n_uses, sizeof (struct web_entry));
 291   used = (char *) xcalloc (max, sizeof (char));
 292   use_addressof = (char *) xcalloc (max, sizeof (char));
 293
 294   if (rtl_dump_file)
 295     df_dump (df, DF_UD_CHAIN | DF_DU_CHAIN, rtl_dump_file);
 296
 297   /* Produce the web.  */
 298   for (i = 0; i < df->n_uses; i++)
 299     union_defs (df, df->uses[i], def_entry, use_entry);
 300
 301   /* We can not safely rename registers whose address is taken.  */
 302   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 303     if (INSN_P (insn))
 304       for_each_rtx (&PATTERN (insn), mark_addressof, use_addressof);
 305
 306   /* Update the instruction stream, allocating new registers for split pseudos
 307      in progress.  */
 308   for (i = 0; i < df->n_uses; i++)
 309     replace_ref (df->uses[i], entry_register (use_entry + i, df->uses[i],
 310                                               used, use_addressof));
 311   for (i = 0; i < df->n_defs; i++)
 312     replace_ref (df->defs[i], entry_register (def_entry + i, df->defs[i],
 313                                               used, use_addressof));
 314
 315   /* Dataflow information is corrupt here, but it can be easy to update it
 316      by creating new entries for new registers and update or calilng
 317      df_insns_modify.  */
 318   free (def_entry);
 319   free (use_entry);
 320   free (used);
 321   free (use_addressof);
 322   df_finish (df);
 323 }