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