gcc/web.c

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