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