gcc/web.c

   1 /* Web construction code for GNU compiler.
   2    Contributed by Jan Hubicka.
   3    Copyright (C) 2001, 2002, 2004, 2006, 2007 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 3, 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 COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* Simple optimization pass that splits independent uses of each pseudo,
  22    increasing effectiveness of other optimizations.  The optimization can
  23    serve as an example of use for the dataflow module.
  24
  25    We don't split registers with REG_USERVAR set unless -fmessy-debugging
  26    is specified, because debugging information about such split variables
  27    is almost unusable.
  28
  29    TODO
  30     - Add code to keep debugging up-to-date after splitting user variable
  31       pseudos.  This can be done by keeping track of all the pseudos used
  32       for the variable and using life analysis information before reload
  33       to determine which one is live and, in case more than one are live,
  34       choose the one with the latest definition.
  35
  36       Other optimization passes can benefit from the infrastructure too.
  37
  38     - We may use profile information and ignore infrequent use for the
  39       purpose of web unifying, inserting the compensation code later to
  40       implement full induction variable expansion for loops (currently
  41       we expand only if the induction variable is dead afterward, which
  42       is often the case).  */
  43
  44 #include "config.h"
  45 #include "system.h"
  46 #include "coretypes.h"
  47 #include "tm.h"
  48 #include "toplev.h"
  49
  50 #include "rtl.h"
  51 #include "hard-reg-set.h"
  52 #include "flags.h"
  53 #include "obstack.h"
  54 #include "basic-block.h"
  55 #include "output.h"
  56 #include "df.h"
  57 #include "function.h"
  58 #include "timevar.h"
  59 #include "tree-pass.h"
  60
  61
  62 static rtx entry_register (struct web_entry *, struct df_ref *, char *);
  63 static void replace_ref (struct df_ref *, rtx);
  64
  65 /* Find the root of unionfind tree (the representative of set).  */
  66
  67 struct web_entry *
  68 unionfind_root (struct web_entry *element)
  69 {
  70   struct web_entry *element1 = element, *element2;
  71
  72   while (element->pred)
  73     element = element->pred;
  74   while (element1->pred)
  75     {
  76       element2 = element1->pred;
  77       element1->pred = element;
  78       element1 = element2;
  79     }
  80   return element;
  81 }
  82
  83 /* Union sets.
  84    Return true if FIRST and SECOND points to the same web entry structure and
  85    nothing is done.  Otherwise, return false.  */
  86
  87 bool
  88 unionfind_union (struct web_entry *first, struct web_entry *second)
  89 {
  90   first = unionfind_root (first);
  91   second = unionfind_root (second);
  92   if (first == second)
  93     return true;
  94   second->pred = first;
  95   return false;
  96 }
  97
  98 /* For each use, all possible defs reaching it must come in the same
  99    register, union them.
 100    FUN is the function that does the union.  */
 101
 102 void
 103 union_defs (struct df *df, struct df_ref *use, struct web_entry *def_entry,
 104             struct web_entry *use_entry,
 105             bool (*fun) (struct web_entry *, struct web_entry *))
 106 {
 107   rtx insn = DF_REF_INSN (use);
 108   struct df_link *link = DF_REF_CHAIN (use);
 109   struct df_ref *use_link;
 110   struct df_ref *def_link;
 111   rtx set;
 112
 113   if (insn)
 114     {
 115       use_link = DF_INSN_USES (df, insn);
 116       def_link = DF_INSN_DEFS (df, insn);
 117       set = single_set (insn);
 118     }
 119   else
 120     {
 121       use_link = NULL;
 122       def_link = NULL;
 123       set = NULL;
 124     }
 125
 126   /* Some instructions may use match_dup for their operands.  In case the
 127      operands are dead, we will assign them different pseudos, creating
 128      invalid instructions, so union all uses of the same operand for each
 129      insn.  */
 130
 131   while (use_link)
 132     {
 133       if (use != use_link
 134           && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (use_link))
 135         (*fun) (use_entry + DF_REF_ID (use),
 136                 use_entry + DF_REF_ID (use_link));
 137       use_link = use_link->next_ref;
 138     }
 139
 140   /* Recognize trivial noop moves and attempt to keep them as noop.
 141      While most of noop moves should be removed, we still keep some
 142      of them at libcall boundaries and such.  */
 143
 144   if (set
 145       && SET_SRC (set) == DF_REF_REG (use)
 146       && SET_SRC (set) == SET_DEST (set))
 147     {
 148       while (def_link)
 149         {
 150           if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def_link))
 151             (*fun) (use_entry + DF_REF_ID (use),
 152                     def_entry + DF_REF_ID (def_link));
 153           def_link = def_link->next_ref;
 154         }
 155     }
 156   while (link)
 157     {
 158       (*fun) (use_entry + DF_REF_ID (use),
 159               def_entry + DF_REF_ID (link->ref));
 160       link = link->next;
 161     }
 162
 163   /* A READ_WRITE use requires the corresponding def to be in the same
 164      register.  Find it and union.  */
 165   if (use->flags & DF_REF_READ_WRITE)
 166     {
 167       struct df_ref *link;
 168
 169       if (DF_REF_INSN (use))
 170         link = DF_INSN_DEFS (df, DF_REF_INSN (use));
 171       else
 172         link = NULL;
 173
 174       while (link)
 175         {
 176           if (DF_REF_REAL_REG (link) == DF_REF_REAL_REG (use))
 177             (*fun) (use_entry + DF_REF_ID (use),
 178                     def_entry + DF_REF_ID (link));
 179           link = link->next_ref;
 180         }
 181     }
 182 }
 183
 184 /* Find the corresponding register for the given entry.  */
 185
 186 static rtx
 187 entry_register (struct web_entry *entry, struct df_ref *ref, char *used)
 188 {
 189   struct web_entry *root;
 190   rtx reg, newreg;
 191
 192   /* Find the corresponding web and see if it has been visited.  */
 193   root = unionfind_root (entry);
 194   if (root->reg)
 195     return root->reg;
 196
 197   /* We are seeing this web for the first time, do the assignment.  */
 198   reg = DF_REF_REAL_REG (ref);
 199
 200   /* In case the original register is already assigned, generate new one.  */
 201   if (!used[REGNO (reg)])
 202     newreg = reg, used[REGNO (reg)] = 1;
 203   else if (REG_USERVAR_P (reg) && 0/*&& !flag_messy_debugging*/)
 204     {
 205       newreg = reg;
 206       if (dump_file)
 207         fprintf (dump_file,
 208                  "New web forced to keep reg=%i (user variable)\n",
 209                  REGNO (reg));
 210     }
 211   else
 212     {
 213       newreg = gen_reg_rtx (GET_MODE (reg));
 214       REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
 215       REG_POINTER (newreg) = REG_POINTER (reg);
 216       REG_ATTRS (newreg) = REG_ATTRS (reg);
 217       if (dump_file)
 218         fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
 219                  REGNO (newreg));
 220     }
 221
 222   root->reg = newreg;
 223   return newreg;
 224 }
 225
 226 /* Replace the reference by REG.  */
 227
 228 static void
 229 replace_ref (struct df_ref *ref, rtx reg)
 230 {
 231   rtx oldreg = DF_REF_REAL_REG (ref);
 232   rtx *loc = DF_REF_REAL_LOC (ref);
 233
 234   if (oldreg == reg)
 235     return;
 236   if (dump_file)
 237     fprintf (dump_file, "Updating insn %i (%i->%i)\n",
 238              INSN_UID (DF_REF_INSN (ref)), REGNO (oldreg), REGNO (reg));
 239   *loc = reg;
 240 }
 241
 242 /* Main entry point.  */
 243
 244 static void
 245 web_main (void)
 246 {
 247   struct df *df;
 248   struct web_entry *def_entry;
 249   struct web_entry *use_entry;
 250   unsigned int i;
 251   int max = max_reg_num ();
 252   char *used;
 253
 254   df = df_init (DF_EQUIV_NOTES);
 255   df_chain_add_problem (df, DF_UD_CHAIN);
 256   df_analyze (df);
 257   df_reorganize_refs (&df->def_info);
 258   df_reorganize_refs (&df->use_info);
 259
 260   def_entry = XCNEWVEC (struct web_entry, DF_DEFS_SIZE (df));
 261   use_entry = XCNEWVEC (struct web_entry, DF_USES_SIZE (df));
 262   used = XCNEWVEC (char, max);
 263
 264   if (dump_file)
 265     df_dump (df, dump_file);
 266
 267   /* Produce the web.  */
 268   for (i = 0; i < DF_USES_SIZE (df); i++)
 269     union_defs (df, DF_USES_GET (df, i), def_entry, use_entry, unionfind_union);
 270
 271   /* Update the instruction stream, allocating new registers for split pseudos
 272      in progress.  */
 273   for (i = 0; i < DF_USES_SIZE (df); i++)
 274     replace_ref (DF_USES_GET (df, i),
 275                  entry_register (use_entry + i, DF_USES_GET (df, i), used));
 276   for (i = 0; i < DF_DEFS_SIZE (df); i++)
 277     replace_ref (DF_DEFS_GET (df, i),
 278                  entry_register (def_entry + i, DF_DEFS_GET (df, i), used));
 279
 280   /* Dataflow information is corrupt here, but it can be easily updated
 281      by creating new entries for new registers and updates or calling
 282      df_insns_modify.  */
 283   free (def_entry);
 284   free (use_entry);
 285   free (used);
 286   df_finish (df);
 287   df = NULL;
 288 }
 289 \f
 290 static bool
 291 gate_handle_web (void)
 292 {
 293   return (optimize > 0 && flag_web);
 294 }
 295
 296 static unsigned int
 297 rest_of_handle_web (void)
 298 {
 299   web_main ();
 300   delete_trivially_dead_insns (get_insns (), max_reg_num ());
 301   cleanup_cfg (CLEANUP_EXPENSIVE);
 302   reg_scan (get_insns (), max_reg_num ());
 303   return 0;
 304 }
 305
 306 struct tree_opt_pass pass_web =
 307 {
 308   "web",                                /* name */
 309   gate_handle_web,                      /* gate */
 310   rest_of_handle_web,                   /* execute */
 311   NULL,                                 /* sub */
 312   NULL,                                 /* next */
 313   0,                                    /* static_pass_number */
 314   TV_WEB,                               /* tv_id */
 315   0,                                    /* properties_required */
 316   0,                                    /* properties_provided */
 317   0,                                    /* properties_destroyed */
 318   0,                                    /* todo_flags_start */
 319   TODO_dump_func,                       /* todo_flags_finish */
 320   'Z'                                   /* letter */
 321 };
 322