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