gcc/web.c

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