gcc/web.c

   1 /* Web construction code for GNU compiler.
   2    Contributed by Jan Hubicka.
   3    Copyright (C) 2001, 2002, 2004, 2006, 2007
   4    Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  21 02110-1301, USA.  */
  22
  23 /* Simple optimization pass that splits independent uses of each pseudo,
  24    increasing effectiveness of other optimizations.  The optimization can
  25    serve as an example of use for the dataflow module.
  26
  27    We don't split registers with REG_USERVAR set unless -fmessy-debugging
  28    is specified, because debugging information about such split variables
  29    is almost unusable.
  30
  31    TODO
  32     - Add code to keep debugging up-to-date after splitting user variable
  33       pseudos.  This can be done by keeping track of all the pseudos used
  34       for the variable and using life analysis information before reload
  35       to determine which one is live and, in case more than one are live,
  36       choose the one with the latest definition.
  37
  38       Other optimization passes can benefit from the infrastructure too.
  39
  40     - We may use profile information and ignore infrequent use for the
  41       purpose of web unifying, inserting the compensation code later to
  42       implement full induction variable expansion for loops (currently
  43       we expand only if the induction variable is dead afterward, which
  44       is often the case).  */
  45
  46 #include "config.h"
  47 #include "system.h"
  48 #include "coretypes.h"
  49 #include "tm.h"
  50 #include "toplev.h"
  51
  52 #include "rtl.h"
  53 #include "hard-reg-set.h"
  54 #include "flags.h"
  55 #include "obstack.h"
  56 #include "basic-block.h"
  57 #include "output.h"
  58 #include "df.h"
  59 #include "function.h"
  60 #include "timevar.h"
  61 #include "tree-pass.h"
  62
  63
  64 static rtx entry_register (struct web_entry *, struct df_ref *, char *);
  65 static void replace_ref (struct df_ref *, rtx);
  66
  67 /* Find the root of unionfind tree (the representative of set).  */
  68
  69 struct web_entry *
  70 unionfind_root (struct web_entry *element)
  71 {
  72   struct web_entry *element1 = element, *element2;
  73
  74   while (element->pred)
  75     element = element->pred;
  76   while (element1->pred)
  77     {
  78       element2 = element1->pred;
  79       element1->pred = element;
  80       element1 = element2;
  81     }
  82   return element;
  83 }
  84
  85 /* Union sets.
  86    Return true if FIRST and SECOND points to the same web entry structure and
  87    nothing is done.  Otherwise, return false.  */
  88
  89 bool
  90 unionfind_union (struct web_entry *first, struct web_entry *second)
  91 {
  92   first = unionfind_root (first);
  93   second = unionfind_root (second);
  94   if (first == second)
  95     return true;
  96   second->pred = first;
  97   return false;
  98 }
  99
 100 /* For each use, all possible defs reaching it must come in the same
 101    register, union them.
 102    FUN is the function that does the union.  */
 103
 104 void
 105 union_defs (struct df_ref *use, struct web_entry *def_entry,
 106             struct web_entry *use_entry,
 107             bool (*fun) (struct web_entry *, struct web_entry *))
 108 {
 109   rtx insn = DF_REF_INSN (use);
 110   struct df_link *link = DF_REF_CHAIN (use);
 111   struct df_ref **use_link;
 112   struct df_ref **eq_use_link;
 113   struct df_ref **def_link;
 114   rtx set;
 115
 116   if (insn)
 117     {
 118       use_link = DF_INSN_USES (insn);
 119       eq_use_link = DF_INSN_EQ_USES (insn);
 120       def_link = DF_INSN_DEFS (insn);
 121       set = single_set (insn);
 122     }
 123   else
 124     {
 125       use_link = NULL;
 126       eq_use_link = NULL;
 127       def_link = NULL;
 128       set = NULL;
 129     }
 130
 131   /* Some instructions may use match_dup for their operands.  In case the
 132      operands are dead, we will assign them different pseudos, creating
 133      invalid instructions, so union all uses of the same operand for each
 134      insn.  */
 135
 136   if (use_link)
 137     while (*use_link)
 138       {
 139         if (use != *use_link
 140             && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*use_link))
 141           (*fun) (use_entry + DF_REF_ID (use),
 142                   use_entry + DF_REF_ID (*use_link));
 143         use_link++;
 144       }
 145
 146   if (eq_use_link)
 147     while (*eq_use_link)
 148       {
 149         if (use != *eq_use_link
 150             && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link))
 151           (*fun) (use_entry + DF_REF_ID (use),
 152                   use_entry + DF_REF_ID (*eq_use_link));
 153         eq_use_link++;
 154     }
 155
 156   /* Recognize trivial noop moves and attempt to keep them as noop.
 157      While most of noop moves should be removed, we still keep some
 158      of them at libcall boundaries and such.  */
 159
 160   if (set
 161       && SET_SRC (set) == DF_REF_REG (use)
 162       && SET_SRC (set) == SET_DEST (set))
 163     {
 164       if (def_link)
 165         while (*def_link)
 166           {
 167             if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link))
 168               (*fun) (use_entry + DF_REF_ID (use),
 169                       def_entry + DF_REF_ID (*def_link));
 170             def_link++;
 171           }
 172     }
 173   while (link)
 174     {
 175       (*fun) (use_entry + DF_REF_ID (use),
 176               def_entry + DF_REF_ID (link->ref));
 177       link = link->next;
 178     }
 179
 180   /* A READ_WRITE use requires the corresponding def to be in the same
 181      register.  Find it and union.  */
 182   if (use->flags & DF_REF_READ_WRITE)
 183     {
 184       struct df_ref **link;
 185
 186       if (DF_REF_INSN (use))
 187         link = DF_INSN_DEFS (DF_REF_INSN (use));
 188       else
 189         link = NULL;
 190
 191       if (link)
 192         while (*link)
 193           {
 194             if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use))
 195               (*fun) (use_entry + DF_REF_ID (use),
 196                       def_entry + DF_REF_ID (*link));
 197             link++;
 198           }
 199     }
 200 }
 201
 202 /* Find the corresponding register for the given entry.  */
 203
 204 static rtx
 205 entry_register (struct web_entry *entry, struct df_ref *ref, char *used)
 206 {
 207   struct web_entry *root;
 208   rtx reg, newreg;
 209
 210   /* Find the corresponding web and see if it has been visited.  */
 211   root = unionfind_root (entry);
 212   if (root->reg)
 213     return root->reg;
 214
 215   /* We are seeing this web for the first time, do the assignment.  */
 216   reg = DF_REF_REAL_REG (ref);
 217
 218   /* In case the original register is already assigned, generate new one.  */
 219   if (!used[REGNO (reg)])
 220     newreg = reg, used[REGNO (reg)] = 1;
 221   else if (REG_USERVAR_P (reg) && 0/*&& !flag_messy_debugging*/)
 222     {
 223       newreg = reg;
 224       if (dump_file)
 225         fprintf (dump_file,
 226                  "New web forced to keep reg=%i (user variable)\n",
 227                  REGNO (reg));
 228     }
 229   else
 230     {
 231       newreg = gen_reg_rtx (GET_MODE (reg));
 232       REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
 233       REG_POINTER (newreg) = REG_POINTER (reg);
 234       REG_ATTRS (newreg) = REG_ATTRS (reg);
 235       if (dump_file)
 236         fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
 237                  REGNO (newreg));
 238     }
 239
 240   root->reg = newreg;
 241   return newreg;
 242 }
 243
 244 /* Replace the reference by REG.  */
 245
 246 static void
 247 replace_ref (struct df_ref *ref, rtx reg)
 248 {
 249   rtx oldreg = DF_REF_REAL_REG (ref);
 250   rtx *loc = DF_REF_REAL_LOC (ref);
 251   unsigned int uid = INSN_UID (DF_REF_INSN (ref));
 252
 253   if (oldreg == reg)
 254     return;
 255   if (dump_file)
 256     fprintf (dump_file, "Updating insn %i (%i->%i)\n",
 257              uid, REGNO (oldreg), REGNO (reg));
 258   *loc = reg;
 259   df_insn_rescan (DF_REF_INSN (ref));
 260 }
 261
 262 \f
 263 static bool
 264 gate_handle_web (void)
 265 {
 266   return (optimize > 0 && flag_web);
 267 }
 268
 269 /* Main entry point.  */
 270
 271 static unsigned int
 272 web_main (void)
 273 {
 274   struct web_entry *def_entry;
 275   struct web_entry *use_entry;
 276   unsigned int max = max_reg_num ();
 277   char *used;
 278   basic_block bb;
 279   unsigned int uses_num = 0;
 280   rtx insn;
 281
 282   df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
 283   df_chain_add_problem (DF_UD_CHAIN);
 284   df_analyze ();
 285   df_set_flags (DF_DEFER_INSN_RESCAN);
 286
 287   /* Assign ids to the uses.  */
 288   FOR_ALL_BB (bb)
 289     FOR_BB_INSNS (bb, insn)
 290     {
 291       unsigned int uid = INSN_UID (insn);
 292       if (INSN_P (insn))
 293         {
 294           struct df_ref **use_rec;
 295           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 296             {
 297               struct df_ref *use = *use_rec;
 298               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 299                 DF_REF_ID (use) = uses_num++;
 300             }
 301           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 302             {
 303               struct df_ref *use = *use_rec;
 304               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 305                 DF_REF_ID (use) = uses_num++;
 306             }
 307         }
 308     }
 309
 310   /* Record the number of uses and defs at the beginning of the optimization.  */
 311   def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE());
 312   used = XCNEWVEC (char, max);
 313   use_entry = XCNEWVEC (struct web_entry, uses_num);
 314
 315   /* Produce the web.  */
 316   FOR_ALL_BB (bb)
 317     FOR_BB_INSNS (bb, insn)
 318     {
 319       unsigned int uid = INSN_UID (insn);
 320       if (INSN_P (insn))
 321         {
 322           struct df_ref **use_rec;
 323           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 324             {
 325               struct df_ref *use = *use_rec;
 326               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 327                 union_defs (use, def_entry, use_entry, unionfind_union);
 328             }
 329           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 330             {
 331               struct df_ref *use = *use_rec;
 332               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 333                 union_defs (use, def_entry, use_entry, unionfind_union);
 334             }
 335         }
 336     }
 337
 338   /* Update the instruction stream, allocating new registers for split pseudos
 339      in progress.  */
 340   FOR_ALL_BB (bb)
 341     FOR_BB_INSNS (bb, insn)
 342     {
 343       unsigned int uid = INSN_UID (insn);
 344       if (INSN_P (insn))
 345         {
 346           struct df_ref **use_rec;
 347           struct df_ref **def_rec;
 348           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 349             {
 350               struct df_ref *use = *use_rec;
 351               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 352                 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
 353             }
 354           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 355             {
 356               struct df_ref *use = *use_rec;
 357               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 358                 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
 359             }
 360           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 361             {
 362               struct df_ref *def = *def_rec;
 363               if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
 364                 replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used));
 365             }
 366         }
 367     }
 368
 369   free (def_entry);
 370   free (use_entry);
 371   free (used);
 372   return 0;
 373 }
 374 \f
 375 struct tree_opt_pass pass_web =
 376 {
 377   "web",                                /* name */
 378   gate_handle_web,                      /* gate */
 379   web_main,                             /* execute */
 380   NULL,                                 /* sub */
 381   NULL,                                 /* next */
 382   0,                                    /* static_pass_number */
 383   TV_WEB,                               /* tv_id */
 384   0,                                    /* properties_required */
 385   0,                                    /* properties_provided */
 386   0,                                    /* properties_destroyed */
 387   0,                                    /* todo_flags_start */
 388   TODO_df_finish |
 389   TODO_dump_func,                       /* todo_flags_finish */
 390   'Z'                                   /* letter */
 391 };
 392