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 "diagnostic-core.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 "df.h"
  49 #include "function.h"
  50 #include "insn-config.h"
  51 #include "recog.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 INSN, union all defs and uses that are linked by match_dup.
  89    FUN is the function that does the union.  */
  90
  91 static void
  92 union_match_dups (rtx insn, struct web_entry *def_entry,
  93                   struct web_entry *use_entry,
  94                   bool (*fun) (struct web_entry *, struct web_entry *))
  95 {
  96   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
  97   df_ref *use_link = DF_INSN_INFO_USES (insn_info);
  98   df_ref *def_link = DF_INSN_INFO_DEFS (insn_info);
  99   int i;
 100
 101   extract_insn (insn);
 102
 103   for (i = 0; i < recog_data.n_dups; i++)
 104     {
 105       int op = recog_data.dup_num[i];
 106       enum op_type type = recog_data.operand_type[op];
 107       df_ref *ref, *dupref;
 108       struct web_entry *entry;
 109
 110       for (dupref = use_link; *dupref; dupref++)
 111         if (DF_REF_LOC (*dupref) == recog_data.dup_loc[i])
 112           break;
 113
 114       if (*dupref == NULL
 115           || DF_REF_REGNO (*dupref) < FIRST_PSEUDO_REGISTER)
 116         continue;
 117
 118       ref = type == OP_IN ? use_link : def_link;
 119       entry = type == OP_IN ? use_entry : def_entry;
 120       for (; *ref; ref++)
 121         if (DF_REF_LOC (*ref) == recog_data.operand_loc[op])
 122           break;
 123
 124       (*fun) (use_entry + DF_REF_ID (*dupref), entry + DF_REF_ID (*ref));
 125     }
 126 }
 127
 128 /* For each use, all possible defs reaching it must come in the same
 129    register, union them.
 130    FUN is the function that does the union.
 131
 132    In USED, we keep the DF_REF_ID of the first uninitialized uses of a
 133    register, so that all uninitialized uses of the register can be
 134    combined into a single web.  We actually offset it by 2, because
 135    the values 0 and 1 are reserved for use by entry_register.  */
 136
 137 void
 138 union_defs (df_ref use, struct web_entry *def_entry,
 139             unsigned int *used, struct web_entry *use_entry,
 140             bool (*fun) (struct web_entry *, struct web_entry *))
 141 {
 142   struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
 143   struct df_link *link = DF_REF_CHAIN (use);
 144   df_ref *eq_use_link;
 145   df_ref *def_link;
 146   rtx set;
 147
 148   if (insn_info)
 149     {
 150       rtx insn = insn_info->insn;
 151       eq_use_link = DF_INSN_INFO_EQ_USES (insn_info);
 152       def_link = DF_INSN_INFO_DEFS (insn_info);
 153       set = single_set (insn);
 154     }
 155   else
 156     {
 157       /* An artificial use.  It links up with nothing.  */
 158       eq_use_link = NULL;
 159       def_link = NULL;
 160       set = NULL;
 161     }
 162
 163   /* Union all occurrences of the same register in reg notes.  */
 164
 165   if (eq_use_link)
 166     while (*eq_use_link)
 167       {
 168         if (use != *eq_use_link
 169             && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link))
 170           (*fun) (use_entry + DF_REF_ID (use),
 171                   use_entry + DF_REF_ID (*eq_use_link));
 172         eq_use_link++;
 173     }
 174
 175   /* Recognize trivial noop moves and attempt to keep them as noop.  */
 176
 177   if (set
 178       && SET_SRC (set) == DF_REF_REG (use)
 179       && SET_SRC (set) == SET_DEST (set))
 180     {
 181       if (def_link)
 182         while (*def_link)
 183           {
 184             if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link))
 185               (*fun) (use_entry + DF_REF_ID (use),
 186                       def_entry + DF_REF_ID (*def_link));
 187             def_link++;
 188           }
 189     }
 190
 191   /* UD chains of uninitialized REGs are empty.  Keeping all uses of
 192      the same uninitialized REG in a single web is not necessary for
 193      correctness, since the uses are undefined, but it's wasteful to
 194      allocate one register or slot for each reference.  Furthermore,
 195      creating new pseudos for uninitialized references in debug insns
 196      (see PR 42631) causes -fcompare-debug failures.  We record the
 197      number of the first uninitialized reference we found, and merge
 198      with it any other uninitialized references to the same
 199      register.  */
 200   if (!link)
 201     {
 202       int regno = REGNO (DF_REF_REAL_REG (use));
 203       if (used[regno])
 204         (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
 205       else
 206         used[regno] = DF_REF_ID (use) + 2;
 207     }
 208
 209   while (link)
 210     {
 211       (*fun) (use_entry + DF_REF_ID (use),
 212               def_entry + DF_REF_ID (link->ref));
 213       link = link->next;
 214     }
 215
 216   /* A READ_WRITE use requires the corresponding def to be in the same
 217      register.  Find it and union.  */
 218   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
 219     {
 220       df_ref *link;
 221
 222       if (insn_info)
 223         link = DF_INSN_INFO_DEFS (insn_info);
 224       else
 225         link = NULL;
 226
 227       if (link)
 228         while (*link)
 229           {
 230             if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use))
 231               (*fun) (use_entry + DF_REF_ID (use),
 232                       def_entry + DF_REF_ID (*link));
 233             link++;
 234           }
 235     }
 236 }
 237
 238 /* Find the corresponding register for the given entry.  */
 239
 240 static rtx
 241 entry_register (struct web_entry *entry, df_ref ref, unsigned int *used)
 242 {
 243   struct web_entry *root;
 244   rtx reg, newreg;
 245
 246   /* Find the corresponding web and see if it has been visited.  */
 247   root = unionfind_root (entry);
 248   if (root->reg)
 249     return root->reg;
 250
 251   /* We are seeing this web for the first time, do the assignment.  */
 252   reg = DF_REF_REAL_REG (ref);
 253
 254   /* In case the original register is already assigned, generate new
 255      one.  Since we use USED to merge uninitialized refs into a single
 256      web, we might found an element to be nonzero without our having
 257      used it.  Test for 1, because union_defs saves it for our use,
 258      and there won't be any use for the other values when we get to
 259      this point.  */
 260   if (used[REGNO (reg)] != 1)
 261     newreg = reg, used[REGNO (reg)] = 1;
 262   else
 263     {
 264       newreg = gen_reg_rtx (GET_MODE (reg));
 265       REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
 266       REG_POINTER (newreg) = REG_POINTER (reg);
 267       REG_ATTRS (newreg) = REG_ATTRS (reg);
 268       if (dump_file)
 269         fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
 270                  REGNO (newreg));
 271     }
 272
 273   root->reg = newreg;
 274   return newreg;
 275 }
 276
 277 /* Replace the reference by REG.  */
 278
 279 static void
 280 replace_ref (df_ref ref, rtx reg)
 281 {
 282   rtx oldreg = DF_REF_REAL_REG (ref);
 283   rtx *loc = DF_REF_REAL_LOC (ref);
 284   unsigned int uid = DF_REF_INSN_UID (ref);
 285
 286   if (oldreg == reg)
 287     return;
 288   if (dump_file)
 289     fprintf (dump_file, "Updating insn %i (%i->%i)\n",
 290              uid, REGNO (oldreg), REGNO (reg));
 291   *loc = reg;
 292   df_insn_rescan (DF_REF_INSN (ref));
 293 }
 294
 295 \f
 296 static bool
 297 gate_handle_web (void)
 298 {
 299   return (optimize > 0 && flag_web);
 300 }
 301
 302 /* Main entry point.  */
 303
 304 static unsigned int
 305 web_main (void)
 306 {
 307   struct web_entry *def_entry;
 308   struct web_entry *use_entry;
 309   unsigned int max = max_reg_num ();
 310   unsigned int *used;
 311   basic_block bb;
 312   unsigned int uses_num = 0;
 313   rtx insn;
 314
 315   df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
 316   df_chain_add_problem (DF_UD_CHAIN);
 317   df_analyze ();
 318   df_set_flags (DF_DEFER_INSN_RESCAN);
 319
 320   /* Assign ids to the uses.  */
 321   FOR_ALL_BB (bb)
 322     FOR_BB_INSNS (bb, insn)
 323     {
 324       unsigned int uid = INSN_UID (insn);
 325       if (NONDEBUG_INSN_P (insn))
 326         {
 327           df_ref *use_rec;
 328           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 329             {
 330               df_ref use = *use_rec;
 331               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 332                 DF_REF_ID (use) = uses_num++;
 333             }
 334           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 335             {
 336               df_ref use = *use_rec;
 337               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 338                 DF_REF_ID (use) = uses_num++;
 339             }
 340         }
 341     }
 342
 343   /* Record the number of uses and defs at the beginning of the optimization.  */
 344   def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE());
 345   used = XCNEWVEC (unsigned, max);
 346   use_entry = XCNEWVEC (struct web_entry, uses_num);
 347
 348   /* Produce the web.  */
 349   FOR_ALL_BB (bb)
 350     FOR_BB_INSNS (bb, insn)
 351     {
 352       unsigned int uid = INSN_UID (insn);
 353       if (NONDEBUG_INSN_P (insn))
 354         {
 355           df_ref *use_rec;
 356           union_match_dups (insn, def_entry, use_entry, unionfind_union);
 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                 union_defs (use, def_entry, used, use_entry, unionfind_union);
 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                 union_defs (use, def_entry, used, use_entry, unionfind_union);
 368             }
 369         }
 370     }
 371
 372   /* Update the instruction stream, allocating new registers for split pseudos
 373      in progress.  */
 374   FOR_ALL_BB (bb)
 375     FOR_BB_INSNS (bb, insn)
 376     {
 377       unsigned int uid = INSN_UID (insn);
 378
 379       if (NONDEBUG_INSN_P (insn)
 380           /* Ignore naked clobber.  For example, reg 134 in the second insn
 381              of the following sequence will not be replaced.
 382
 383                (insn (clobber (reg:SI 134)))
 384
 385                (insn (set (reg:SI 0 r0) (reg:SI 134)))
 386
 387              Thus the later passes can optimize them away.  */
 388           && GET_CODE (PATTERN (insn)) != CLOBBER)
 389         {
 390           df_ref *use_rec;
 391           df_ref *def_rec;
 392           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 393             {
 394               df_ref use = *use_rec;
 395               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 396                 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
 397             }
 398           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 399             {
 400               df_ref use = *use_rec;
 401               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 402                 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
 403             }
 404           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 405             {
 406               df_ref def = *def_rec;
 407               if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
 408                 replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used));
 409             }
 410         }
 411     }
 412
 413   free (def_entry);
 414   free (use_entry);
 415   free (used);
 416   return 0;
 417 }
 418 \f
 419 struct rtl_opt_pass pass_web =
 420 {
 421  {
 422   RTL_PASS,
 423   "web",                                /* name */
 424   gate_handle_web,                      /* gate */
 425   web_main,                             /* execute */
 426   NULL,                                 /* sub */
 427   NULL,                                 /* next */
 428   0,                                    /* static_pass_number */
 429   TV_WEB,                               /* tv_id */
 430   0,                                    /* properties_required */
 431   0,                                    /* properties_provided */
 432   0,                                    /* properties_destroyed */
 433   0,                                    /* todo_flags_start */
 434   TODO_df_finish | TODO_verify_rtl_sharing  /* todo_flags_finish */
 435  }
 436 };