gcc/web.c

   1 /* Web construction code for GNU compiler.
   2    Contributed by Jan Hubicka.
   3    Copyright (C) 2001-2015 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 "predict.h"
  47 #include "function.h"
  48 #include "dominance.h"
  49 #include "cfg.h"
  50 #include "basic-block.h"
  51 #include "df.h"
  52 #include "insn-config.h"
  53 #include "recog.h"
  54 #include "tree-pass.h"
  55
  56
  57 /* Find the root of unionfind tree (the representative of set).  */
  58
  59 web_entry_base *
  60 web_entry_base::unionfind_root ()
  61 {
  62   web_entry_base *element = this, *element1 = this, *element2;
  63
  64   while (element->pred ())
  65     element = element->pred ();
  66   while (element1->pred ())
  67     {
  68       element2 = element1->pred ();
  69       element1->set_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 (web_entry_base *first, web_entry_base *second)
  81 {
  82   first = first->unionfind_root ();
  83   second = second->unionfind_root ();
  84   if (first == second)
  85     return true;
  86   second->set_pred (first);
  87   return false;
  88 }
  89
  90 class web_entry : public web_entry_base
  91 {
  92  private:
  93   rtx reg_pvt;
  94
  95  public:
  96   rtx reg () { return reg_pvt; }
  97   void set_reg (rtx r) { reg_pvt = r; }
  98 };
  99
 100 /* For INSN, union all defs and uses that are linked by match_dup.
 101    FUN is the function that does the union.  */
 102
 103 static void
 104 union_match_dups (rtx_insn *insn, web_entry *def_entry, web_entry *use_entry,
 105                   bool (*fun) (web_entry_base *, web_entry_base *))
 106 {
 107   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
 108   df_ref use_link = DF_INSN_INFO_USES (insn_info);
 109   df_ref def_link = DF_INSN_INFO_DEFS (insn_info);
 110   struct web_entry *dup_entry;
 111   int i;
 112
 113   extract_insn (insn);
 114
 115   for (i = 0; i < recog_data.n_dups; i++)
 116     {
 117       int op = recog_data.dup_num[i];
 118       enum op_type type = recog_data.operand_type[op];
 119       df_ref ref, dupref;
 120       struct web_entry *entry;
 121
 122       dup_entry = use_entry;
 123       for (dupref = use_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
 124         if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
 125           break;
 126
 127       if (dupref == NULL && type == OP_INOUT)
 128         {
 129           dup_entry = def_entry;
 130           for (dupref = def_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
 131             if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
 132               break;
 133         }
 134       /* ??? *DUPREF can still be zero, because when an operand matches
 135          a memory, DF_REF_LOC (use_link[n]) points to the register part
 136          of the address, whereas recog_data.dup_loc[m] points to the
 137          entire memory ref, thus we fail to find the duplicate entry,
 138          even though it is there.
 139          Example: i686-pc-linux-gnu gcc.c-torture/compile/950607-1.c
 140                   -O3 -fomit-frame-pointer -funroll-loops  */
 141       if (dupref == NULL
 142           || DF_REF_REGNO (dupref) < FIRST_PSEUDO_REGISTER)
 143         continue;
 144
 145       ref = type == OP_IN ? use_link : def_link;
 146       entry = type == OP_IN ? use_entry : def_entry;
 147       for (; ref; ref = DF_REF_NEXT_LOC (ref))
 148         {
 149           rtx *l = DF_REF_LOC (ref);
 150           if (l == recog_data.operand_loc[op])
 151             break;
 152           if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
 153             break;
 154         }
 155
 156       if (!ref && type == OP_INOUT)
 157         {
 158           entry = use_entry;
 159           for (ref = use_link; ref; ref = DF_REF_NEXT_LOC (ref))
 160             {
 161               rtx *l = DF_REF_LOC (ref);
 162               if (l == recog_data.operand_loc[op])
 163                 break;
 164               if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
 165                 break;
 166             }
 167         }
 168
 169       gcc_assert (ref);
 170       (*fun) (dup_entry + DF_REF_ID (dupref), entry + DF_REF_ID (ref));
 171     }
 172 }
 173
 174 /* For each use, all possible defs reaching it must come in the same
 175    register, union them.
 176    FUN is the function that does the union.
 177
 178    In USED, we keep the DF_REF_ID of the first uninitialized uses of a
 179    register, so that all uninitialized uses of the register can be
 180    combined into a single web.  We actually offset it by 2, because
 181    the values 0 and 1 are reserved for use by entry_register.  */
 182
 183 void
 184 union_defs (df_ref use, web_entry *def_entry,
 185             unsigned int *used, web_entry *use_entry,
 186             bool (*fun) (web_entry_base *, web_entry_base *))
 187 {
 188   struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
 189   struct df_link *link = DF_REF_CHAIN (use);
 190   rtx set;
 191
 192   if (insn_info)
 193     {
 194       df_ref eq_use;
 195
 196       set = single_set (insn_info->insn);
 197       FOR_EACH_INSN_INFO_EQ_USE (eq_use, insn_info)
 198         if (use != eq_use
 199             && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (eq_use))
 200           (*fun) (use_entry + DF_REF_ID (use), use_entry + DF_REF_ID (eq_use));
 201     }
 202   else
 203     set = NULL;
 204
 205   /* Union all occurrences of the same register in reg notes.  */
 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       df_ref def;
 214
 215       FOR_EACH_INSN_INFO_DEF (def, insn_info)
 216         if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
 217           (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
 218     }
 219
 220   /* UD chains of uninitialized REGs are empty.  Keeping all uses of
 221      the same uninitialized REG in a single web is not necessary for
 222      correctness, since the uses are undefined, but it's wasteful to
 223      allocate one register or slot for each reference.  Furthermore,
 224      creating new pseudos for uninitialized references in debug insns
 225      (see PR 42631) causes -fcompare-debug failures.  We record the
 226      number of the first uninitialized reference we found, and merge
 227      with it any other uninitialized references to the same
 228      register.  */
 229   if (!link)
 230     {
 231       int regno = REGNO (DF_REF_REAL_REG (use));
 232       if (used[regno])
 233         (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
 234       else
 235         used[regno] = DF_REF_ID (use) + 2;
 236     }
 237
 238   while (link)
 239     {
 240       (*fun) (use_entry + DF_REF_ID (use),
 241               def_entry + DF_REF_ID (link->ref));
 242       link = link->next;
 243     }
 244
 245   /* A READ_WRITE use requires the corresponding def to be in the same
 246      register.  Find it and union.  */
 247   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
 248     if (insn_info)
 249       {
 250         df_ref def;
 251
 252         FOR_EACH_INSN_INFO_DEF (def, insn_info)
 253           if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
 254             (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
 255       }
 256 }
 257
 258 /* Find the corresponding register for the given entry.  */
 259
 260 static rtx
 261 entry_register (web_entry *entry, df_ref ref, unsigned int *used)
 262 {
 263   web_entry *root;
 264   rtx reg, newreg;
 265
 266   /* Find the corresponding web and see if it has been visited.  */
 267   root = (web_entry *)entry->unionfind_root ();
 268   if (root->reg ())
 269     return root->reg ();
 270
 271   /* We are seeing this web for the first time, do the assignment.  */
 272   reg = DF_REF_REAL_REG (ref);
 273
 274   /* In case the original register is already assigned, generate new
 275      one.  Since we use USED to merge uninitialized refs into a single
 276      web, we might found an element to be nonzero without our having
 277      used it.  Test for 1, because union_defs saves it for our use,
 278      and there won't be any use for the other values when we get to
 279      this point.  */
 280   if (used[REGNO (reg)] != 1)
 281     newreg = reg, used[REGNO (reg)] = 1;
 282   else
 283     {
 284       newreg = gen_reg_rtx (GET_MODE (reg));
 285       REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
 286       REG_POINTER (newreg) = REG_POINTER (reg);
 287       REG_ATTRS (newreg) = REG_ATTRS (reg);
 288       if (dump_file)
 289         fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
 290                  REGNO (newreg));
 291     }
 292
 293   root->set_reg (newreg);
 294   return newreg;
 295 }
 296
 297 /* Replace the reference by REG.  */
 298
 299 static void
 300 replace_ref (df_ref ref, rtx reg)
 301 {
 302   rtx oldreg = DF_REF_REAL_REG (ref);
 303   rtx *loc = DF_REF_REAL_LOC (ref);
 304   unsigned int uid = DF_REF_INSN_UID (ref);
 305
 306   if (oldreg == reg)
 307     return;
 308   if (dump_file)
 309     fprintf (dump_file, "Updating insn %i (%i->%i)\n",
 310              uid, REGNO (oldreg), REGNO (reg));
 311   *loc = reg;
 312   df_insn_rescan (DF_REF_INSN (ref));
 313 }
 314
 315 \f
 316 namespace {
 317
 318 const pass_data pass_data_web =
 319 {
 320   RTL_PASS, /* type */
 321   "web", /* name */
 322   OPTGROUP_NONE, /* optinfo_flags */
 323   TV_WEB, /* tv_id */
 324   0, /* properties_required */
 325   0, /* properties_provided */
 326   0, /* properties_destroyed */
 327   0, /* todo_flags_start */
 328   TODO_df_finish, /* todo_flags_finish */
 329 };
 330
 331 class pass_web : public rtl_opt_pass
 332 {
 333 public:
 334   pass_web (gcc::context *ctxt)
 335     : rtl_opt_pass (pass_data_web, ctxt)
 336   {}
 337
 338   /* opt_pass methods: */
 339   virtual bool gate (function *) { return (optimize > 0 && flag_web); }
 340   virtual unsigned int execute (function *);
 341
 342 }; // class pass_web
 343
 344 unsigned int
 345 pass_web::execute (function *fun)
 346 {
 347   web_entry *def_entry;
 348   web_entry *use_entry;
 349   unsigned int max = max_reg_num ();
 350   unsigned int *used;
 351   basic_block bb;
 352   unsigned int uses_num = 0;
 353   rtx_insn *insn;
 354
 355   df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
 356   df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
 357   df_chain_add_problem (DF_UD_CHAIN);
 358   df_analyze ();
 359   df_set_flags (DF_DEFER_INSN_RESCAN);
 360
 361   /* Assign ids to the uses.  */
 362   FOR_ALL_BB_FN (bb, fun)
 363     FOR_BB_INSNS (bb, insn)
 364     {
 365       if (NONDEBUG_INSN_P (insn))
 366         {
 367           struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
 368           df_ref use;
 369           FOR_EACH_INSN_INFO_USE (use, insn_info)
 370             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 371               DF_REF_ID (use) = uses_num++;
 372           FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
 373             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 374               DF_REF_ID (use) = uses_num++;
 375         }
 376     }
 377
 378   /* Record the number of uses and defs at the beginning of the optimization.  */
 379   def_entry = XCNEWVEC (web_entry, DF_DEFS_TABLE_SIZE ());
 380   used = XCNEWVEC (unsigned, max);
 381   use_entry = XCNEWVEC (web_entry, uses_num);
 382
 383   /* Produce the web.  */
 384   FOR_ALL_BB_FN (bb, fun)
 385     FOR_BB_INSNS (bb, insn)
 386       if (NONDEBUG_INSN_P (insn))
 387         {
 388           struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
 389           df_ref use;
 390           union_match_dups (insn, def_entry, use_entry, unionfind_union);
 391           FOR_EACH_INSN_INFO_USE (use, insn_info)
 392             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 393               union_defs (use, def_entry, used, use_entry, unionfind_union);
 394           FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
 395             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 396               union_defs (use, def_entry, used, use_entry, unionfind_union);
 397         }
 398
 399   /* Update the instruction stream, allocating new registers for split pseudos
 400      in progress.  */
 401   FOR_ALL_BB_FN (bb, fun)
 402     FOR_BB_INSNS (bb, insn)
 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           struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
 415           df_ref def, use;
 416           FOR_EACH_INSN_INFO_USE (use, insn_info)
 417             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 418               replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
 419                                                 use, used));
 420           FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
 421             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 422               replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
 423                                                 use, used));
 424           FOR_EACH_INSN_INFO_DEF (def, insn_info)
 425             if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
 426               replace_ref (def, entry_register (def_entry + DF_REF_ID (def),
 427                                                 def, used));
 428         }
 429
 430   free (def_entry);
 431   free (use_entry);
 432   free (used);
 433   return 0;
 434 }
 435 \f
 436 } // anon namespace
 437
 438 rtl_opt_pass *
 439 make_pass_web (gcc::context *ctxt)
 440 {
 441   return new pass_web (ctxt);
 442 }