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