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