gcc/web.c

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