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