gcc/web.c

   1 /* Web construction code for GNU compiler.
   2    Contributed by Jan Hubicka.
   3    Copyright (C) 2001-2013 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       for (dup_entry = use_entry, dupref = use_link; *dupref; dupref++)
 111         if (DF_REF_LOC (*dupref) == recog_data.dup_loc[i])
 112           break;
 113
 114       if (*dupref == NULL && type == OP_INOUT)
 115         {
 116
 117           for (dup_entry = def_entry, dupref = def_link; *dupref; 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++)
 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           for (ref = use_link, entry = use_entry; *ref; ref++)
 146             {
 147               rtx *l = DF_REF_LOC (*ref);
 148               if (l == recog_data.operand_loc[op])
 149                 break;
 150               if (l && DF_REF_REAL_LOC (*ref) == recog_data.operand_loc[op])
 151                 break;
 152             }
 153         }
 154
 155       gcc_assert (*ref);
 156       (*fun) (dup_entry + DF_REF_ID (*dupref), entry + DF_REF_ID (*ref));
 157     }
 158 }
 159
 160 /* For each use, all possible defs reaching it must come in the same
 161    register, union them.
 162    FUN is the function that does the union.
 163
 164    In USED, we keep the DF_REF_ID of the first uninitialized uses of a
 165    register, so that all uninitialized uses of the register can be
 166    combined into a single web.  We actually offset it by 2, because
 167    the values 0 and 1 are reserved for use by entry_register.  */
 168
 169 void
 170 union_defs (df_ref use, struct web_entry *def_entry,
 171             unsigned int *used, struct web_entry *use_entry,
 172             bool (*fun) (struct web_entry *, struct web_entry *))
 173 {
 174   struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
 175   struct df_link *link = DF_REF_CHAIN (use);
 176   df_ref *eq_use_link;
 177   df_ref *def_link;
 178   rtx set;
 179
 180   if (insn_info)
 181     {
 182       rtx insn = insn_info->insn;
 183       eq_use_link = DF_INSN_INFO_EQ_USES (insn_info);
 184       def_link = DF_INSN_INFO_DEFS (insn_info);
 185       set = single_set (insn);
 186     }
 187   else
 188     {
 189       /* An artificial use.  It links up with nothing.  */
 190       eq_use_link = NULL;
 191       def_link = NULL;
 192       set = NULL;
 193     }
 194
 195   /* Union all occurrences of the same register in reg notes.  */
 196
 197   if (eq_use_link)
 198     while (*eq_use_link)
 199       {
 200         if (use != *eq_use_link
 201             && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link))
 202           (*fun) (use_entry + DF_REF_ID (use),
 203                   use_entry + DF_REF_ID (*eq_use_link));
 204         eq_use_link++;
 205     }
 206
 207   /* Recognize trivial noop moves and attempt to keep them as noop.  */
 208
 209   if (set
 210       && SET_SRC (set) == DF_REF_REG (use)
 211       && SET_SRC (set) == SET_DEST (set))
 212     {
 213       if (def_link)
 214         while (*def_link)
 215           {
 216             if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link))
 217               (*fun) (use_entry + DF_REF_ID (use),
 218                       def_entry + DF_REF_ID (*def_link));
 219             def_link++;
 220           }
 221     }
 222
 223   /* UD chains of uninitialized REGs are empty.  Keeping all uses of
 224      the same uninitialized REG in a single web is not necessary for
 225      correctness, since the uses are undefined, but it's wasteful to
 226      allocate one register or slot for each reference.  Furthermore,
 227      creating new pseudos for uninitialized references in debug insns
 228      (see PR 42631) causes -fcompare-debug failures.  We record the
 229      number of the first uninitialized reference we found, and merge
 230      with it any other uninitialized references to the same
 231      register.  */
 232   if (!link)
 233     {
 234       int regno = REGNO (DF_REF_REAL_REG (use));
 235       if (used[regno])
 236         (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
 237       else
 238         used[regno] = DF_REF_ID (use) + 2;
 239     }
 240
 241   while (link)
 242     {
 243       (*fun) (use_entry + DF_REF_ID (use),
 244               def_entry + DF_REF_ID (link->ref));
 245       link = link->next;
 246     }
 247
 248   /* A READ_WRITE use requires the corresponding def to be in the same
 249      register.  Find it and union.  */
 250   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
 251     {
 252       df_ref *link;
 253
 254       if (insn_info)
 255         link = DF_INSN_INFO_DEFS (insn_info);
 256       else
 257         link = NULL;
 258
 259       if (link)
 260         while (*link)
 261           {
 262             if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use))
 263               (*fun) (use_entry + DF_REF_ID (use),
 264                       def_entry + DF_REF_ID (*link));
 265             link++;
 266           }
 267     }
 268 }
 269
 270 /* Find the corresponding register for the given entry.  */
 271
 272 static rtx
 273 entry_register (struct web_entry *entry, df_ref ref, unsigned int *used)
 274 {
 275   struct web_entry *root;
 276   rtx reg, newreg;
 277
 278   /* Find the corresponding web and see if it has been visited.  */
 279   root = unionfind_root (entry);
 280   if (root->reg)
 281     return root->reg;
 282
 283   /* We are seeing this web for the first time, do the assignment.  */
 284   reg = DF_REF_REAL_REG (ref);
 285
 286   /* In case the original register is already assigned, generate new
 287      one.  Since we use USED to merge uninitialized refs into a single
 288      web, we might found an element to be nonzero without our having
 289      used it.  Test for 1, because union_defs saves it for our use,
 290      and there won't be any use for the other values when we get to
 291      this point.  */
 292   if (used[REGNO (reg)] != 1)
 293     newreg = reg, used[REGNO (reg)] = 1;
 294   else
 295     {
 296       newreg = gen_reg_rtx (GET_MODE (reg));
 297       REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
 298       REG_POINTER (newreg) = REG_POINTER (reg);
 299       REG_ATTRS (newreg) = REG_ATTRS (reg);
 300       if (dump_file)
 301         fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
 302                  REGNO (newreg));
 303     }
 304
 305   root->reg = newreg;
 306   return newreg;
 307 }
 308
 309 /* Replace the reference by REG.  */
 310
 311 static void
 312 replace_ref (df_ref ref, rtx reg)
 313 {
 314   rtx oldreg = DF_REF_REAL_REG (ref);
 315   rtx *loc = DF_REF_REAL_LOC (ref);
 316   unsigned int uid = DF_REF_INSN_UID (ref);
 317
 318   if (oldreg == reg)
 319     return;
 320   if (dump_file)
 321     fprintf (dump_file, "Updating insn %i (%i->%i)\n",
 322              uid, REGNO (oldreg), REGNO (reg));
 323   *loc = reg;
 324   df_insn_rescan (DF_REF_INSN (ref));
 325 }
 326
 327 \f
 328 static bool
 329 gate_handle_web (void)
 330 {
 331   return (optimize > 0 && flag_web);
 332 }
 333
 334 /* Main entry point.  */
 335
 336 static unsigned int
 337 web_main (void)
 338 {
 339   struct web_entry *def_entry;
 340   struct web_entry *use_entry;
 341   unsigned int max = max_reg_num ();
 342   unsigned int *used;
 343   basic_block bb;
 344   unsigned int uses_num = 0;
 345   rtx insn;
 346
 347   df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
 348   df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
 349   df_chain_add_problem (DF_UD_CHAIN);
 350   df_analyze ();
 351   df_set_flags (DF_DEFER_INSN_RESCAN);
 352
 353   /* Assign ids to the uses.  */
 354   FOR_ALL_BB (bb)
 355     FOR_BB_INSNS (bb, insn)
 356     {
 357       unsigned int uid = INSN_UID (insn);
 358       if (NONDEBUG_INSN_P (insn))
 359         {
 360           df_ref *use_rec;
 361           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 362             {
 363               df_ref use = *use_rec;
 364               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 365                 DF_REF_ID (use) = uses_num++;
 366             }
 367           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 368             {
 369               df_ref use = *use_rec;
 370               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 371                 DF_REF_ID (use) = uses_num++;
 372             }
 373         }
 374     }
 375
 376   /* Record the number of uses and defs at the beginning of the optimization.  */
 377   def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE());
 378   used = XCNEWVEC (unsigned, max);
 379   use_entry = XCNEWVEC (struct web_entry, uses_num);
 380
 381   /* Produce the web.  */
 382   FOR_ALL_BB (bb)
 383     FOR_BB_INSNS (bb, insn)
 384     {
 385       unsigned int uid = INSN_UID (insn);
 386       if (NONDEBUG_INSN_P (insn))
 387         {
 388           df_ref *use_rec;
 389           union_match_dups (insn, def_entry, use_entry, unionfind_union);
 390           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 391             {
 392               df_ref use = *use_rec;
 393               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 394                 union_defs (use, def_entry, used, use_entry, unionfind_union);
 395             }
 396           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 397             {
 398               df_ref use = *use_rec;
 399               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 400                 union_defs (use, def_entry, used, use_entry, unionfind_union);
 401             }
 402         }
 403     }
 404
 405   /* Update the instruction stream, allocating new registers for split pseudos
 406      in progress.  */
 407   FOR_ALL_BB (bb)
 408     FOR_BB_INSNS (bb, insn)
 409     {
 410       unsigned int uid = INSN_UID (insn);
 411
 412       if (NONDEBUG_INSN_P (insn)
 413           /* Ignore naked clobber.  For example, reg 134 in the second insn
 414              of the following sequence will not be replaced.
 415
 416                (insn (clobber (reg:SI 134)))
 417
 418                (insn (set (reg:SI 0 r0) (reg:SI 134)))
 419
 420              Thus the later passes can optimize them away.  */
 421           && GET_CODE (PATTERN (insn)) != CLOBBER)
 422         {
 423           df_ref *use_rec;
 424           df_ref *def_rec;
 425           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 426             {
 427               df_ref use = *use_rec;
 428               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 429                 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
 430             }
 431           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 432             {
 433               df_ref use = *use_rec;
 434               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 435                 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
 436             }
 437           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 438             {
 439               df_ref def = *def_rec;
 440               if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
 441                 replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used));
 442             }
 443         }
 444     }
 445
 446   free (def_entry);
 447   free (use_entry);
 448   free (used);
 449   return 0;
 450 }
 451 \f
 452 namespace {
 453
 454 const pass_data pass_data_web =
 455 {
 456   RTL_PASS, /* type */
 457   "web", /* name */
 458   OPTGROUP_NONE, /* optinfo_flags */
 459   true, /* has_gate */
 460   true, /* has_execute */
 461   TV_WEB, /* tv_id */
 462   0, /* properties_required */
 463   0, /* properties_provided */
 464   0, /* properties_destroyed */
 465   0, /* todo_flags_start */
 466   ( TODO_df_finish | TODO_verify_rtl_sharing ), /* todo_flags_finish */
 467 };
 468
 469 class pass_web : public rtl_opt_pass
 470 {
 471 public:
 472   pass_web(gcc::context *ctxt)
 473     : rtl_opt_pass(pass_data_web, ctxt)
 474   {}
 475
 476   /* opt_pass methods: */
 477   bool gate () { return gate_handle_web (); }
 478   unsigned int execute () { return web_main (); }
 479
 480 }; // class pass_web
 481
 482 } // anon namespace
 483
 484 rtl_opt_pass *
 485 make_pass_web (gcc::context *ctxt)
 486 {
 487   return new pass_web (ctxt);
 488 }