gcc/web.c

   1 /* Web construction code for GNU compiler.
   2    Contributed by Jan Hubicka.
   3    Copyright (C) 2001, 2002, 2004, 2006, 2007, 2008, 2010
   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 3, 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 COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* Simple optimization pass that splits independent uses of each pseudo,
  23    increasing effectiveness 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     - We may use profile information and ignore infrequent use for the
  32       purpose of web unifying, inserting the compensation code later to
  33       implement full induction variable expansion for loops (currently
  34       we expand only if the induction variable is dead afterward, which
  35       is often the case).  */
  36
  37 #include "config.h"
  38 #include "system.h"
  39 #include "coretypes.h"
  40 #include "tm.h"
  41 #include "toplev.h"
  42
  43 #include "rtl.h"
  44 #include "hard-reg-set.h"
  45 #include "flags.h"
  46 #include "obstack.h"
  47 #include "basic-block.h"
  48 #include "output.h"
  49 #include "df.h"
  50 #include "function.h"
  51 #include "timevar.h"
  52 #include "tree-pass.h"
  53
  54
  55 /* Find the root of unionfind tree (the representative of set).  */
  56
  57 struct web_entry *
  58 unionfind_root (struct web_entry *element)
  59 {
  60   struct web_entry *element1 = element, *element2;
  61
  62   while (element->pred)
  63     element = element->pred;
  64   while (element1->pred)
  65     {
  66       element2 = element1->pred;
  67       element1->pred = element;
  68       element1 = element2;
  69     }
  70   return element;
  71 }
  72
  73 /* Union sets.
  74    Return true if FIRST and SECOND points to the same web entry structure and
  75    nothing is done.  Otherwise, return false.  */
  76
  77 bool
  78 unionfind_union (struct web_entry *first, struct web_entry *second)
  79 {
  80   first = unionfind_root (first);
  81   second = unionfind_root (second);
  82   if (first == second)
  83     return true;
  84   second->pred = first;
  85   return false;
  86 }
  87
  88 /* For each use, all possible defs reaching it must come in the same
  89    register, union them.
  90    FUN is the function that does the union.
  91
  92    In USED, we keep the DF_REF_ID of the first uninitialized uses of a
  93    register, so that all uninitialized uses of the register can be
  94    combined into a single web.  We actually offset it by 2, because
  95    the values 0 and 1 are reserved for use by entry_register.  */
  96
  97 void
  98 union_defs (df_ref use, struct web_entry *def_entry,
  99             unsigned int *used, struct web_entry *use_entry,
 100             bool (*fun) (struct web_entry *, struct web_entry *))
 101 {
 102   struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
 103   struct df_link *link = DF_REF_CHAIN (use);
 104   df_ref *use_link;
 105   df_ref *eq_use_link;
 106   df_ref *def_link;
 107   rtx set;
 108
 109   if (insn_info)
 110     {
 111       rtx insn = insn_info->insn;
 112       use_link = DF_INSN_INFO_USES (insn_info);
 113       eq_use_link = DF_INSN_INFO_EQ_USES (insn_info);
 114       def_link = DF_INSN_INFO_DEFS (insn_info);
 115       set = single_set (insn);
 116     }
 117   else
 118     {
 119       /* An artificial use.  It links up with nothing.  */
 120       use_link = NULL;
 121       eq_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   if (use_link)
 132     while (*use_link)
 133       {
 134         if (use != *use_link
 135             && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*use_link))
 136           (*fun) (use_entry + DF_REF_ID (use),
 137                   use_entry + DF_REF_ID (*use_link));
 138         use_link++;
 139       }
 140
 141   if (eq_use_link)
 142     while (*eq_use_link)
 143       {
 144         if (use != *eq_use_link
 145             && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link))
 146           (*fun) (use_entry + DF_REF_ID (use),
 147                   use_entry + DF_REF_ID (*eq_use_link));
 148         eq_use_link++;
 149     }
 150
 151   /* Recognize trivial noop moves and attempt to keep them as noop.  */
 152
 153   if (set
 154       && SET_SRC (set) == DF_REF_REG (use)
 155       && SET_SRC (set) == SET_DEST (set))
 156     {
 157       if (def_link)
 158         while (*def_link)
 159           {
 160             if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link))
 161               (*fun) (use_entry + DF_REF_ID (use),
 162                       def_entry + DF_REF_ID (*def_link));
 163             def_link++;
 164           }
 165     }
 166
 167   /* UD chains of uninitialized REGs are empty.  Keeping all uses of
 168      the same uninitialized REG in a single web is not necessary for
 169      correctness, since the uses are undefined, but it's wasteful to
 170      allocate one register or slot for each reference.  Furthermore,
 171      creating new pseudos for uninitialized references in debug insns
 172      (see PR 42631) causes -fcompare-debug failures.  We record the
 173      number of the first uninitialized reference we found, and merge
 174      with it any other uninitialized references to the same
 175      register.  */
 176   if (!link)
 177     {
 178       int regno = REGNO (DF_REF_REAL_REG (use));
 179       if (used[regno])
 180         (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
 181       else
 182         used[regno] = DF_REF_ID (use) + 2;
 183     }
 184
 185   while (link)
 186     {
 187       (*fun) (use_entry + DF_REF_ID (use),
 188               def_entry + DF_REF_ID (link->ref));
 189       link = link->next;
 190     }
 191
 192   /* A READ_WRITE use requires the corresponding def to be in the same
 193      register.  Find it and union.  */
 194   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
 195     {
 196       df_ref *link;
 197
 198       if (insn_info)
 199         link = DF_INSN_INFO_DEFS (insn_info);
 200       else
 201         link = NULL;
 202
 203       if (link)
 204         while (*link)
 205           {
 206             if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use))
 207               (*fun) (use_entry + DF_REF_ID (use),
 208                       def_entry + DF_REF_ID (*link));
 209             link++;
 210           }
 211     }
 212 }
 213
 214 /* Find the corresponding register for the given entry.  */
 215
 216 static rtx
 217 entry_register (struct web_entry *entry, df_ref ref, unsigned int *used)
 218 {
 219   struct web_entry *root;
 220   rtx reg, newreg;
 221
 222   /* Find the corresponding web and see if it has been visited.  */
 223   root = unionfind_root (entry);
 224   if (root->reg)
 225     return root->reg;
 226
 227   /* We are seeing this web for the first time, do the assignment.  */
 228   reg = DF_REF_REAL_REG (ref);
 229
 230   /* In case the original register is already assigned, generate new
 231      one.  Since we use USED to merge uninitialized refs into a single
 232      web, we might found an element to be nonzero without our having
 233      used it.  Test for 1, because union_defs saves it for our use,
 234      and there won't be any use for the other values when we get to
 235      this point.  */
 236   if (used[REGNO (reg)] != 1)
 237     newreg = reg, used[REGNO (reg)] = 1;
 238   else
 239     {
 240       newreg = gen_reg_rtx (GET_MODE (reg));
 241       REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
 242       REG_POINTER (newreg) = REG_POINTER (reg);
 243       REG_ATTRS (newreg) = REG_ATTRS (reg);
 244       if (dump_file)
 245         fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
 246                  REGNO (newreg));
 247     }
 248
 249   root->reg = newreg;
 250   return newreg;
 251 }
 252
 253 /* Replace the reference by REG.  */
 254
 255 static void
 256 replace_ref (df_ref ref, rtx reg)
 257 {
 258   rtx oldreg = DF_REF_REAL_REG (ref);
 259   rtx *loc = DF_REF_REAL_LOC (ref);
 260   unsigned int uid = DF_REF_INSN_UID (ref);
 261
 262   if (oldreg == reg)
 263     return;
 264   if (dump_file)
 265     fprintf (dump_file, "Updating insn %i (%i->%i)\n",
 266              uid, REGNO (oldreg), REGNO (reg));
 267   *loc = reg;
 268   df_insn_rescan (DF_REF_INSN (ref));
 269 }
 270
 271 \f
 272 static bool
 273 gate_handle_web (void)
 274 {
 275   return (optimize > 0 && flag_web);
 276 }
 277
 278 /* Main entry point.  */
 279
 280 static unsigned int
 281 web_main (void)
 282 {
 283   struct web_entry *def_entry;
 284   struct web_entry *use_entry;
 285   unsigned int max = max_reg_num ();
 286   unsigned int *used;
 287   basic_block bb;
 288   unsigned int uses_num = 0;
 289   rtx insn;
 290
 291   df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
 292   df_chain_add_problem (DF_UD_CHAIN);
 293   df_analyze ();
 294   df_set_flags (DF_DEFER_INSN_RESCAN);
 295
 296   /* Assign ids to the uses.  */
 297   FOR_ALL_BB (bb)
 298     FOR_BB_INSNS (bb, insn)
 299     {
 300       unsigned int uid = INSN_UID (insn);
 301       if (INSN_P (insn))
 302         {
 303           df_ref *use_rec;
 304           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 305             {
 306               df_ref use = *use_rec;
 307               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 308                 DF_REF_ID (use) = uses_num++;
 309             }
 310           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 311             {
 312               df_ref use = *use_rec;
 313               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 314                 DF_REF_ID (use) = uses_num++;
 315             }
 316         }
 317     }
 318
 319   /* Record the number of uses and defs at the beginning of the optimization.  */
 320   def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE());
 321   used = XCNEWVEC (unsigned, max);
 322   use_entry = XCNEWVEC (struct web_entry, uses_num);
 323
 324   /* Produce the web.  */
 325   FOR_ALL_BB (bb)
 326     FOR_BB_INSNS (bb, insn)
 327     {
 328       unsigned int uid = INSN_UID (insn);
 329       if (INSN_P (insn))
 330         {
 331           df_ref *use_rec;
 332           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 333             {
 334               df_ref use = *use_rec;
 335               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 336                 union_defs (use, def_entry, used, use_entry, unionfind_union);
 337             }
 338           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 339             {
 340               df_ref use = *use_rec;
 341               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 342                 union_defs (use, def_entry, used, use_entry, unionfind_union);
 343             }
 344         }
 345     }
 346
 347   /* Update the instruction stream, allocating new registers for split pseudos
 348      in progress.  */
 349   FOR_ALL_BB (bb)
 350     FOR_BB_INSNS (bb, insn)
 351     {
 352       unsigned int uid = INSN_UID (insn);
 353       if (INSN_P (insn))
 354         {
 355           df_ref *use_rec;
 356           df_ref *def_rec;
 357           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 358             {
 359               df_ref use = *use_rec;
 360               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 361                 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
 362             }
 363           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 364             {
 365               df_ref use = *use_rec;
 366               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 367                 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
 368             }
 369           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 370             {
 371               df_ref def = *def_rec;
 372               if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
 373                 replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used));
 374             }
 375         }
 376     }
 377
 378   free (def_entry);
 379   free (use_entry);
 380   free (used);
 381   return 0;
 382 }
 383 \f
 384 struct rtl_opt_pass pass_web =
 385 {
 386  {
 387   RTL_PASS,
 388   "web",                                /* name */
 389   gate_handle_web,                      /* gate */
 390   web_main,                             /* execute */
 391   NULL,                                 /* sub */
 392   NULL,                                 /* next */
 393   0,                                    /* static_pass_number */
 394   TV_WEB,                               /* tv_id */
 395   0,                                    /* properties_required */
 396   0,                                    /* properties_provided */
 397   0,                                    /* properties_destroyed */
 398   0,                                    /* todo_flags_start */
 399   TODO_df_finish | TODO_verify_rtl_sharing |
 400   TODO_dump_func                        /* todo_flags_finish */
 401  }
 402 };
 403