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