gcc/web.c

   1 /* Web construction code for GNU compiler.
   2    Contributed by Jan Hubicka.
   3    Copyright (C) 2001-2013 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* Simple optimization pass that splits independent uses of each pseudo,
  22    increasing effectiveness of other optimizations.  The optimization can
  23    serve as an example of use for the dataflow module.
  24
  25    We don't split registers with REG_USERVAR set unless -fmessy-debugging
  26    is specified, because debugging information about such split variables
  27    is almost unusable.
  28
  29    TODO
  30     - We may use profile information and ignore infrequent use for the
  31       purpose of web unifying, inserting the compensation code later to
  32       implement full induction variable expansion for loops (currently
  33       we expand only if the induction variable is dead afterward, which
  34       is often the case).  */
  35
  36 #include "config.h"
  37 #include "system.h"
  38 #include "coretypes.h"
  39 #include "tm.h"
  40 #include "diagnostic-core.h"
  41
  42 #include "rtl.h"
  43 #include "hard-reg-set.h"
  44 #include "flags.h"
  45 #include "obstack.h"
  46 #include "basic-block.h"
  47 #include "df.h"
  48 #include "function.h"
  49 #include "insn-config.h"
  50 #include "recog.h"
  51 #include "tree-pass.h"
  52
  53
  54 /* Find the root of unionfind tree (the representative of set).  */
  55
  56 struct web_entry *
  57 unionfind_root (struct web_entry *element)
  58 {
  59   struct web_entry *element1 = element, *element2;
  60
  61   while (element->pred)
  62     element = element->pred;
  63   while (element1->pred)
  64     {
  65       element2 = element1->pred;
  66       element1->pred = element;
  67       element1 = element2;
  68     }
  69   return element;
  70 }
  71
  72 /* Union sets.
  73    Return true if FIRST and SECOND points to the same web entry structure and
  74    nothing is done.  Otherwise, return false.  */
  75
  76 bool
  77 unionfind_union (struct web_entry *first, struct web_entry *second)
  78 {
  79   first = unionfind_root (first);
  80   second = unionfind_root (second);
  81   if (first == second)
  82     return true;
  83   second->pred = first;
  84   return false;
  85 }
  86
  87 /* For INSN, union all defs and uses that are linked by match_dup.
  88    FUN is the function that does the union.  */
  89
  90 static void
  91 union_match_dups (rtx insn, struct web_entry *def_entry,
  92                   struct web_entry *use_entry,
  93                   bool (*fun) (struct web_entry *, struct web_entry *))
  94 {
  95   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
  96   df_ref *use_link = DF_INSN_INFO_USES (insn_info);
  97   df_ref *def_link = DF_INSN_INFO_DEFS (insn_info);
  98   struct web_entry *dup_entry;
  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 (dup_entry = use_entry, dupref = use_link; *dupref; dupref++)
 111         if (DF_REF_LOC (*dupref) == recog_data.dup_loc[i])
 112           break;
 113
 114       if (*dupref == NULL && type == OP_INOUT)
 115         {
 116
 117           for (dup_entry = def_entry, dupref = def_link; *dupref; dupref++)
 118             if (DF_REF_LOC (*dupref) == recog_data.dup_loc[i])
 119               break;
 120         }
 121       /* ??? *DUPREF can still be zero, because when an operand matches
 122          a memory, DF_REF_LOC (use_link[n]) points to the register part
 123          of the address, whereas recog_data.dup_loc[m] points to the
 124          entire memory ref, thus we fail to find the duplicate entry,
 125          even though it is there.
 126          Example: i686-pc-linux-gnu gcc.c-torture/compile/950607-1.c
 127                   -O3 -fomit-frame-pointer -funroll-loops  */
 128       if (*dupref == NULL
 129           || DF_REF_REGNO (*dupref) < FIRST_PSEUDO_REGISTER)
 130         continue;
 131
 132       ref = type == OP_IN ? use_link : def_link;
 133       entry = type == OP_IN ? use_entry : def_entry;
 134       for (; *ref; ref++)
 135         if (DF_REF_LOC (*ref) == recog_data.operand_loc[op])
 136           break;
 137
 138       if (!*ref && type == OP_INOUT)
 139         {
 140           for (ref = use_link, entry = use_entry; *ref; ref++)
 141             if (DF_REF_LOC (*ref) == recog_data.operand_loc[op])
 142               break;
 143         }
 144
 145       gcc_assert (*ref);
 146       (*fun) (dup_entry + DF_REF_ID (*dupref), entry + DF_REF_ID (*ref));
 147     }
 148 }
 149
 150 /* For each use, all possible defs reaching it must come in the same
 151    register, union them.
 152    FUN is the function that does the union.
 153
 154    In USED, we keep the DF_REF_ID of the first uninitialized uses of a
 155    register, so that all uninitialized uses of the register can be
 156    combined into a single web.  We actually offset it by 2, because
 157    the values 0 and 1 are reserved for use by entry_register.  */
 158
 159 void
 160 union_defs (df_ref use, struct web_entry *def_entry,
 161             unsigned int *used, struct web_entry *use_entry,
 162             bool (*fun) (struct web_entry *, struct web_entry *))
 163 {
 164   struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
 165   struct df_link *link = DF_REF_CHAIN (use);
 166   df_ref *eq_use_link;
 167   df_ref *def_link;
 168   rtx set;
 169
 170   if (insn_info)
 171     {
 172       rtx insn = insn_info->insn;
 173       eq_use_link = DF_INSN_INFO_EQ_USES (insn_info);
 174       def_link = DF_INSN_INFO_DEFS (insn_info);
 175       set = single_set (insn);
 176     }
 177   else
 178     {
 179       /* An artificial use.  It links up with nothing.  */
 180       eq_use_link = NULL;
 181       def_link = NULL;
 182       set = NULL;
 183     }
 184
 185   /* Union all occurrences of the same register in reg notes.  */
 186
 187   if (eq_use_link)
 188     while (*eq_use_link)
 189       {
 190         if (use != *eq_use_link
 191             && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link))
 192           (*fun) (use_entry + DF_REF_ID (use),
 193                   use_entry + DF_REF_ID (*eq_use_link));
 194         eq_use_link++;
 195     }
 196
 197   /* Recognize trivial noop moves and attempt to keep them as noop.  */
 198
 199   if (set
 200       && SET_SRC (set) == DF_REF_REG (use)
 201       && SET_SRC (set) == SET_DEST (set))
 202     {
 203       if (def_link)
 204         while (*def_link)
 205           {
 206             if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link))
 207               (*fun) (use_entry + DF_REF_ID (use),
 208                       def_entry + DF_REF_ID (*def_link));
 209             def_link++;
 210           }
 211     }
 212
 213   /* UD chains of uninitialized REGs are empty.  Keeping all uses of
 214      the same uninitialized REG in a single web is not necessary for
 215      correctness, since the uses are undefined, but it's wasteful to
 216      allocate one register or slot for each reference.  Furthermore,
 217      creating new pseudos for uninitialized references in debug insns
 218      (see PR 42631) causes -fcompare-debug failures.  We record the
 219      number of the first uninitialized reference we found, and merge
 220      with it any other uninitialized references to the same
 221      register.  */
 222   if (!link)
 223     {
 224       int regno = REGNO (DF_REF_REAL_REG (use));
 225       if (used[regno])
 226         (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
 227       else
 228         used[regno] = DF_REF_ID (use) + 2;
 229     }
 230
 231   while (link)
 232     {
 233       (*fun) (use_entry + DF_REF_ID (use),
 234               def_entry + DF_REF_ID (link->ref));
 235       link = link->next;
 236     }
 237
 238   /* A READ_WRITE use requires the corresponding def to be in the same
 239      register.  Find it and union.  */
 240   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
 241     {
 242       df_ref *link;
 243
 244       if (insn_info)
 245         link = DF_INSN_INFO_DEFS (insn_info);
 246       else
 247         link = NULL;
 248
 249       if (link)
 250         while (*link)
 251           {
 252             if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use))
 253               (*fun) (use_entry + DF_REF_ID (use),
 254                       def_entry + DF_REF_ID (*link));
 255             link++;
 256           }
 257     }
 258 }
 259
 260 /* Find the corresponding register for the given entry.  */
 261
 262 static rtx
 263 entry_register (struct web_entry *entry, df_ref ref, unsigned int *used)
 264 {
 265   struct web_entry *root;
 266   rtx reg, newreg;
 267
 268   /* Find the corresponding web and see if it has been visited.  */
 269   root = unionfind_root (entry);
 270   if (root->reg)
 271     return root->reg;
 272
 273   /* We are seeing this web for the first time, do the assignment.  */
 274   reg = DF_REF_REAL_REG (ref);
 275
 276   /* In case the original register is already assigned, generate new
 277      one.  Since we use USED to merge uninitialized refs into a single
 278      web, we might found an element to be nonzero without our having
 279      used it.  Test for 1, because union_defs saves it for our use,
 280      and there won't be any use for the other values when we get to
 281      this point.  */
 282   if (used[REGNO (reg)] != 1)
 283     newreg = reg, used[REGNO (reg)] = 1;
 284   else
 285     {
 286       newreg = gen_reg_rtx (GET_MODE (reg));
 287       REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
 288       REG_POINTER (newreg) = REG_POINTER (reg);
 289       REG_ATTRS (newreg) = REG_ATTRS (reg);
 290       if (dump_file)
 291         fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
 292                  REGNO (newreg));
 293     }
 294
 295   root->reg = newreg;
 296   return newreg;
 297 }
 298
 299 /* Replace the reference by REG.  */
 300
 301 static void
 302 replace_ref (df_ref ref, rtx reg)
 303 {
 304   rtx oldreg = DF_REF_REAL_REG (ref);
 305   rtx *loc = DF_REF_REAL_LOC (ref);
 306   unsigned int uid = DF_REF_INSN_UID (ref);
 307
 308   if (oldreg == reg)
 309     return;
 310   if (dump_file)
 311     fprintf (dump_file, "Updating insn %i (%i->%i)\n",
 312              uid, REGNO (oldreg), REGNO (reg));
 313   *loc = reg;
 314   df_insn_rescan (DF_REF_INSN (ref));
 315 }
 316
 317 \f
 318 static bool
 319 gate_handle_web (void)
 320 {
 321   return (optimize > 0 && flag_web);
 322 }
 323
 324 /* Main entry point.  */
 325
 326 static unsigned int
 327 web_main (void)
 328 {
 329   struct web_entry *def_entry;
 330   struct web_entry *use_entry;
 331   unsigned int max = max_reg_num ();
 332   unsigned int *used;
 333   basic_block bb;
 334   unsigned int uses_num = 0;
 335   rtx insn;
 336
 337   df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
 338   df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
 339   df_chain_add_problem (DF_UD_CHAIN);
 340   df_analyze ();
 341   df_set_flags (DF_DEFER_INSN_RESCAN);
 342
 343   /* Assign ids to the uses.  */
 344   FOR_ALL_BB (bb)
 345     FOR_BB_INSNS (bb, insn)
 346     {
 347       unsigned int uid = INSN_UID (insn);
 348       if (NONDEBUG_INSN_P (insn))
 349         {
 350           df_ref *use_rec;
 351           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 352             {
 353               df_ref use = *use_rec;
 354               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 355                 DF_REF_ID (use) = uses_num++;
 356             }
 357           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 358             {
 359               df_ref use = *use_rec;
 360               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 361                 DF_REF_ID (use) = uses_num++;
 362             }
 363         }
 364     }
 365
 366   /* Record the number of uses and defs at the beginning of the optimization.  */
 367   def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE());
 368   used = XCNEWVEC (unsigned, max);
 369   use_entry = XCNEWVEC (struct web_entry, uses_num);
 370
 371   /* Produce the web.  */
 372   FOR_ALL_BB (bb)
 373     FOR_BB_INSNS (bb, insn)
 374     {
 375       unsigned int uid = INSN_UID (insn);
 376       if (NONDEBUG_INSN_P (insn))
 377         {
 378           df_ref *use_rec;
 379           union_match_dups (insn, def_entry, use_entry, unionfind_union);
 380           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 381             {
 382               df_ref use = *use_rec;
 383               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 384                 union_defs (use, def_entry, used, use_entry, unionfind_union);
 385             }
 386           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 387             {
 388               df_ref use = *use_rec;
 389               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 390                 union_defs (use, def_entry, used, use_entry, unionfind_union);
 391             }
 392         }
 393     }
 394
 395   /* Update the instruction stream, allocating new registers for split pseudos
 396      in progress.  */
 397   FOR_ALL_BB (bb)
 398     FOR_BB_INSNS (bb, insn)
 399     {
 400       unsigned int uid = INSN_UID (insn);
 401
 402       if (NONDEBUG_INSN_P (insn)
 403           /* Ignore naked clobber.  For example, reg 134 in the second insn
 404              of the following sequence will not be replaced.
 405
 406                (insn (clobber (reg:SI 134)))
 407
 408                (insn (set (reg:SI 0 r0) (reg:SI 134)))
 409
 410              Thus the later passes can optimize them away.  */
 411           && GET_CODE (PATTERN (insn)) != CLOBBER)
 412         {
 413           df_ref *use_rec;
 414           df_ref *def_rec;
 415           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 416             {
 417               df_ref use = *use_rec;
 418               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 419                 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
 420             }
 421           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 422             {
 423               df_ref use = *use_rec;
 424               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 425                 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
 426             }
 427           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 428             {
 429               df_ref def = *def_rec;
 430               if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
 431                 replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used));
 432             }
 433         }
 434     }
 435
 436   free (def_entry);
 437   free (use_entry);
 438   free (used);
 439   return 0;
 440 }
 441 \f
 442 struct rtl_opt_pass pass_web =
 443 {
 444  {
 445   RTL_PASS,
 446   "web",                                /* name */
 447   OPTGROUP_NONE,                        /* optinfo_flags */
 448   gate_handle_web,                      /* gate */
 449   web_main,                             /* execute */
 450   NULL,                                 /* sub */
 451   NULL,                                 /* next */
 452   0,                                    /* static_pass_number */
 453   TV_WEB,                               /* tv_id */
 454   0,                                    /* properties_required */
 455   0,                                    /* properties_provided */
 456   0,                                    /* properties_destroyed */
 457   0,                                    /* todo_flags_start */
 458   TODO_df_finish | TODO_verify_rtl_sharing  /* todo_flags_finish */
 459  }
 460 };