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 independent uses of each pseudo,
  23    increasing effectivity of other optimizations.  The optimization can
  24    serve as an example of use for the dataflow module.
  25
  26    We don't split registers with REG_USERVAR set unless -fmessy-debugging
  27    is specified, because debugging information about such split variables
  28    is almost unusable.
  29
  30    TODO
  31     - Add code to keep debugging up-to-date after splitting user variable
  32       pseudos.  This can be done by keeping track of all the pseudos used
  33       for the variable and using life analysis information before reload
  34       to determine which one is live and, in case more than one are live,
  35       choose the one with the latest definition.
  36
  37       Other optimization passes can benefit from the infrastructure too.
  38
  39     - We may use profile information and ignore infrequent use for the
  40       purpose of web unifying, inserting the compensation code later to
  41       implement full induction variable expansion for loops (currently
  42       we expand only if the induction variable is dead afterward, which
  43       is often the case).  */
  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 representative 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 the same
 113    register, 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 their operands.  In case the
 129      operands are dead, we will assign them different pseudos, creating
 130      invalid instructions, so union all uses of the same operand 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 as noop.
 143      While most of noop moves should be removed, we still keep some
 144      of them at 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   /* A READ_WRITE use requires 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 the corresponding register for the 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 the corresponding web and see if it has been visited.  */
 192   root = unionfind_root (entry);
 193   if (root->reg)
 194     return root->reg;
 195
 196   /* We are seeing this web for the first time, do the assignment.  */
 197   reg = DF_REF_REAL_REG (ref);
 198
 199   /* In case the original register is already assigned, generate new one.  */
 200   if (!used[REGNO (reg)])
 201     newreg = reg, used[REGNO (reg)] = 1;
 202   else if (REG_USERVAR_P (reg) && 0/*&& !flag_messy_debugging*/)
 203     {
 204       newreg = reg;
 205       if (rtl_dump_file)
 206         fprintf (rtl_dump_file,
 207                  "New web forced to keep reg=%i (user variable)\n",
 208                  REGNO (reg));
 209     }
 210   else if (use_addressof [REGNO (reg)])
 211     {
 212       newreg = reg;
 213       if (rtl_dump_file)
 214         fprintf (rtl_dump_file,
 215                  "New web forced to keep reg=%i (address taken)\n",
 216                  REGNO (reg));
 217     }
 218   else
 219     {
 220       newreg = gen_reg_rtx (GET_MODE (reg));
 221       REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
 222       REG_POINTER (newreg) = REG_POINTER (reg);
 223       REG_LOOP_TEST_P (newreg) = REG_LOOP_TEST_P (reg);
 224       RTX_UNCHANGING_P (newreg) = RTX_UNCHANGING_P (reg);
 225       REG_ATTRS (newreg) = REG_ATTRS (reg);
 226       if (rtl_dump_file)
 227         fprintf (rtl_dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
 228                  REGNO (newreg));
 229     }
 230
 231   root->reg = newreg;
 232   return newreg;
 233 }
 234
 235 /* Replace the reference by REG.  */
 236
 237 static void
 238 replace_ref (ref, reg)
 239    struct ref *ref;
 240    rtx reg;
 241 {
 242   rtx oldreg = DF_REF_REAL_REG (ref);
 243   rtx *loc = DF_REF_REAL_LOC (ref);
 244
 245   if (oldreg == reg)
 246     return;
 247   if (rtl_dump_file)
 248     fprintf (rtl_dump_file, "Updating insn %i (%i->%i)\n",
 249              INSN_UID (DF_REF_INSN (ref)), REGNO (oldreg), REGNO (reg));
 250   *loc = reg;
 251 }
 252
 253 /* Mark each pseudo whose address is taken.  */
 254
 255 static int
 256 mark_addressof (rtl, data)
 257      rtx *rtl;
 258      void *data;
 259 {
 260   if (!*rtl)
 261     return 0;
 262   if (GET_CODE (*rtl) == ADDRESSOF
 263       && REG_P (XEXP (*rtl, 0)))
 264     ((char *)data)[REGNO (XEXP (*rtl, 0))] = 1;
 265   return 0;
 266 }
 267
 268 /* Main entry point.  */
 269
 270 void
 271 web_main ()
 272 {
 273   struct df *df;
 274   struct web_entry *def_entry;
 275   struct web_entry *use_entry;
 276   unsigned int i;
 277   int max = max_reg_num ();
 278   char *used;
 279   char *use_addressof;
 280   rtx insn;
 281
 282   df = df_init ();
 283   df_analyse (df, 0, DF_UD_CHAIN | DF_EQUIV_NOTES);
 284
 285   def_entry =
 286     (struct web_entry *) xcalloc (df->n_defs, sizeof (struct web_entry));
 287   use_entry =
 288     (struct web_entry *) xcalloc (df->n_uses, sizeof (struct web_entry));
 289   used = (char *) xcalloc (max, sizeof (char));
 290   use_addressof = (char *) xcalloc (max, sizeof (char));
 291
 292   if (rtl_dump_file)
 293     df_dump (df, DF_UD_CHAIN | DF_DU_CHAIN, rtl_dump_file);
 294
 295   /* Produce the web.  */
 296   for (i = 0; i < df->n_uses; i++)
 297     union_defs (df, df->uses[i], def_entry, use_entry);
 298
 299   /* We can not safely rename registers whose address is taken.  */
 300   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 301     if (INSN_P (insn))
 302       for_each_rtx (&PATTERN (insn), mark_addressof, use_addressof);
 303
 304   /* Update the instruction stream, allocating new registers for split pseudos
 305      in progress.  */
 306   for (i = 0; i < df->n_uses; i++)
 307     replace_ref (df->uses[i], entry_register (use_entry + i, df->uses[i],
 308                                               used, use_addressof));
 309   for (i = 0; i < df->n_defs; i++)
 310     replace_ref (df->defs[i], entry_register (def_entry + i, df->defs[i],
 311                                               used, use_addressof));
 312
 313   /* Dataflow information is corrupt here, but it can be easily updated
 314      by creating new entries for new registers and updates or calling
 315      df_insns_modify.  */
 316   free (def_entry);
 317   free (use_entry);
 318   free (used);
 319   free (use_addressof);
 320   df_finish (df);
 321 }