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   true, /* has_execute */
 312   TV_WEB, /* tv_id */
 313   0, /* properties_required */
 314   0, /* properties_provided */
 315   0, /* properties_destroyed */
 316   0, /* todo_flags_start */
 317   TODO_df_finish, /* todo_flags_finish */
 318 };
 319
 320 class pass_web : public rtl_opt_pass
 321 {
 322 public:
 323   pass_web (gcc::context *ctxt)
 324     : rtl_opt_pass (pass_data_web, ctxt)
 325   {}
 326
 327   /* opt_pass methods: */
 328   virtual bool gate (function *) { return (optimize > 0 && flag_web); }
 329   virtual unsigned int execute (function *);
 330
 331 }; // class pass_web
 332
 333 unsigned int
 334 pass_web::execute (function *fun)
 335 {
 336   struct web_entry *def_entry;
 337   struct web_entry *use_entry;
 338   unsigned int max = max_reg_num ();
 339   unsigned int *used;
 340   basic_block bb;
 341   unsigned int uses_num = 0;
 342   rtx insn;
 343
 344   df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
 345   df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
 346   df_chain_add_problem (DF_UD_CHAIN);
 347   df_analyze ();
 348   df_set_flags (DF_DEFER_INSN_RESCAN);
 349
 350   /* Assign ids to the uses.  */
 351   FOR_ALL_BB_FN (bb, fun)
 352     FOR_BB_INSNS (bb, insn)
 353     {
 354       if (NONDEBUG_INSN_P (insn))
 355         {
 356           struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
 357           df_ref use;
 358           FOR_EACH_INSN_INFO_USE (use, insn_info)
 359             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 360               DF_REF_ID (use) = uses_num++;
 361           FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
 362             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 363               DF_REF_ID (use) = uses_num++;
 364         }
 365     }
 366
 367   /* Record the number of uses and defs at the beginning of the optimization.  */
 368   def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE ());
 369   used = XCNEWVEC (unsigned, max);
 370   use_entry = XCNEWVEC (struct web_entry, uses_num);
 371
 372   /* Produce the web.  */
 373   FOR_ALL_BB_FN (bb, fun)
 374     FOR_BB_INSNS (bb, insn)
 375       if (NONDEBUG_INSN_P (insn))
 376         {
 377           struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
 378           df_ref use;
 379           union_match_dups (insn, def_entry, use_entry, unionfind_union);
 380           FOR_EACH_INSN_INFO_USE (use, insn_info)
 381             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 382               union_defs (use, def_entry, used, use_entry, unionfind_union);
 383           FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
 384             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 385               union_defs (use, def_entry, used, use_entry, unionfind_union);
 386         }
 387
 388   /* Update the instruction stream, allocating new registers for split pseudos
 389      in progress.  */
 390   FOR_ALL_BB_FN (bb, fun)
 391     FOR_BB_INSNS (bb, insn)
 392       if (NONDEBUG_INSN_P (insn)
 393           /* Ignore naked clobber.  For example, reg 134 in the second insn
 394              of the following sequence will not be replaced.
 395
 396                (insn (clobber (reg:SI 134)))
 397
 398                (insn (set (reg:SI 0 r0) (reg:SI 134)))
 399
 400              Thus the later passes can optimize them away.  */
 401           && GET_CODE (PATTERN (insn)) != CLOBBER)
 402         {
 403           struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
 404           df_ref def, use;
 405           FOR_EACH_INSN_INFO_USE (use, insn_info)
 406             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 407               replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
 408                                                 use, used));
 409           FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
 410             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 411               replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
 412                                                 use, used));
 413           FOR_EACH_INSN_INFO_DEF (def, insn_info)
 414             if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
 415               replace_ref (def, entry_register (def_entry + DF_REF_ID (def),
 416                                                 def, used));
 417         }
 418
 419   free (def_entry);
 420   free (use_entry);
 421   free (used);
 422   return 0;
 423 }
 424 \f
 425 } // anon namespace
 426
 427 rtl_opt_pass *
 428 make_pass_web (gcc::context *ctxt)
 429 {
 430   return new pass_web (ctxt);
 431 }