gcc/web.c

   1 /* Web construction code for GNU compiler.
   2    Contributed by Jan Hubicka.
   3    Copyright (C) 2001, 2002, 2004, 2006, 2007, 2008, 2010
   4    Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* Simple optimization pass that splits independent uses of each pseudo,
  23    increasing effectiveness of other optimizations.  The optimization can
  24    serve as an example of use for the dataflow module.
  25
  26    We don't split registers with REG_USERVAR set unless -fmessy-debugging
  27    is specified, because debugging information about such split variables
  28    is almost unusable.
  29
  30    TODO
  31     - We may use profile information and ignore infrequent use for the
  32       purpose of web unifying, inserting the compensation code later to
  33       implement full induction variable expansion for loops (currently
  34       we expand only if the induction variable is dead afterward, which
  35       is often the case).  */
  36
  37 #include "config.h"
  38 #include "system.h"
  39 #include "coretypes.h"
  40 #include "tm.h"
  41 #include "diagnostic-core.h"
  42
  43 #include "rtl.h"
  44 #include "hard-reg-set.h"
  45 #include "flags.h"
  46 #include "obstack.h"
  47 #include "basic-block.h"
  48 #include "df.h"
  49 #include "function.h"
  50 #include "insn-config.h"
  51 #include "recog.h"
  52 #include "timevar.h"
  53 #include "tree-pass.h"
  54
  55
  56 /* Find the root of unionfind tree (the representative of set).  */
  57
  58 struct web_entry *
  59 unionfind_root (struct web_entry *element)
  60 {
  61   struct web_entry *element1 = element, *element2;
  62
  63   while (element->pred)
  64     element = element->pred;
  65   while (element1->pred)
  66     {
  67       element2 = element1->pred;
  68       element1->pred = element;
  69       element1 = element2;
  70     }
  71   return element;
  72 }
  73
  74 /* Union sets.
  75    Return true if FIRST and SECOND points to the same web entry structure and
  76    nothing is done.  Otherwise, return false.  */
  77
  78 bool
  79 unionfind_union (struct web_entry *first, struct web_entry *second)
  80 {
  81   first = unionfind_root (first);
  82   second = unionfind_root (second);
  83   if (first == second)
  84     return true;
  85   second->pred = first;
  86   return false;
  87 }
  88
  89 /* For INSN, union all defs and uses that are linked by match_dup.
  90    FUN is the function that does the union.  */
  91
  92 static void
  93 union_match_dups (rtx insn, struct web_entry *def_entry,
  94                   struct web_entry *use_entry,
  95                   bool (*fun) (struct web_entry *, struct web_entry *))
  96 {
  97   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
  98   df_ref *use_link = DF_INSN_INFO_USES (insn_info);
  99   df_ref *def_link = DF_INSN_INFO_DEFS (insn_info);
 100   int i;
 101
 102   extract_insn (insn);
 103
 104   for (i = 0; i < recog_data.n_dups; i++)
 105     {
 106       int op = recog_data.dup_num[i];
 107       enum op_type type = recog_data.operand_type[op];
 108       df_ref *ref, *dupref;
 109       struct web_entry *entry;
 110
 111       for (dupref = use_link; *dupref; dupref++)
 112         if (DF_REF_LOC (*dupref) == recog_data.dup_loc[i])
 113           break;
 114
 115       if (*dupref == NULL
 116           || DF_REF_REGNO (*dupref) < FIRST_PSEUDO_REGISTER)
 117         continue;
 118
 119       ref = type == OP_IN ? use_link : def_link;
 120       entry = type == OP_IN ? use_entry : def_entry;
 121       for (; *ref; ref++)
 122         if (DF_REF_LOC (*ref) == recog_data.operand_loc[op])
 123           break;
 124
 125       (*fun) (use_entry + DF_REF_ID (*dupref), entry + DF_REF_ID (*ref));
 126     }
 127 }
 128
 129 /* For each use, all possible defs reaching it must come in the same
 130    register, union them.
 131    FUN is the function that does the union.
 132
 133    In USED, we keep the DF_REF_ID of the first uninitialized uses of a
 134    register, so that all uninitialized uses of the register can be
 135    combined into a single web.  We actually offset it by 2, because
 136    the values 0 and 1 are reserved for use by entry_register.  */
 137
 138 void
 139 union_defs (df_ref use, struct web_entry *def_entry,
 140             unsigned int *used, struct web_entry *use_entry,
 141             bool (*fun) (struct web_entry *, struct web_entry *))
 142 {
 143   struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
 144   struct df_link *link = DF_REF_CHAIN (use);
 145   df_ref *eq_use_link;
 146   df_ref *def_link;
 147   rtx set;
 148
 149   if (insn_info)
 150     {
 151       rtx insn = insn_info->insn;
 152       eq_use_link = DF_INSN_INFO_EQ_USES (insn_info);
 153       def_link = DF_INSN_INFO_DEFS (insn_info);
 154       set = single_set (insn);
 155     }
 156   else
 157     {
 158       /* An artificial use.  It links up with nothing.  */
 159       eq_use_link = NULL;
 160       def_link = NULL;
 161       set = NULL;
 162     }
 163
 164   /* Union all occurrences of the same register in reg notes.  */
 165
 166   if (eq_use_link)
 167     while (*eq_use_link)
 168       {
 169         if (use != *eq_use_link
 170             && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*eq_use_link))
 171           (*fun) (use_entry + DF_REF_ID (use),
 172                   use_entry + DF_REF_ID (*eq_use_link));
 173         eq_use_link++;
 174     }
 175
 176   /* Recognize trivial noop moves and attempt to keep them as noop.  */
 177
 178   if (set
 179       && SET_SRC (set) == DF_REF_REG (use)
 180       && SET_SRC (set) == SET_DEST (set))
 181     {
 182       if (def_link)
 183         while (*def_link)
 184           {
 185             if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (*def_link))
 186               (*fun) (use_entry + DF_REF_ID (use),
 187                       def_entry + DF_REF_ID (*def_link));
 188             def_link++;
 189           }
 190     }
 191
 192   /* UD chains of uninitialized REGs are empty.  Keeping all uses of
 193      the same uninitialized REG in a single web is not necessary for
 194      correctness, since the uses are undefined, but it's wasteful to
 195      allocate one register or slot for each reference.  Furthermore,
 196      creating new pseudos for uninitialized references in debug insns
 197      (see PR 42631) causes -fcompare-debug failures.  We record the
 198      number of the first uninitialized reference we found, and merge
 199      with it any other uninitialized references to the same
 200      register.  */
 201   if (!link)
 202     {
 203       int regno = REGNO (DF_REF_REAL_REG (use));
 204       if (used[regno])
 205         (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
 206       else
 207         used[regno] = DF_REF_ID (use) + 2;
 208     }
 209
 210   while (link)
 211     {
 212       (*fun) (use_entry + DF_REF_ID (use),
 213               def_entry + DF_REF_ID (link->ref));
 214       link = link->next;
 215     }
 216
 217   /* A READ_WRITE use requires the corresponding def to be in the same
 218      register.  Find it and union.  */
 219   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
 220     {
 221       df_ref *link;
 222
 223       if (insn_info)
 224         link = DF_INSN_INFO_DEFS (insn_info);
 225       else
 226         link = NULL;
 227
 228       if (link)
 229         while (*link)
 230           {
 231             if (DF_REF_REAL_REG (*link) == DF_REF_REAL_REG (use))
 232               (*fun) (use_entry + DF_REF_ID (use),
 233                       def_entry + DF_REF_ID (*link));
 234             link++;
 235           }
 236     }
 237 }
 238
 239 /* Find the corresponding register for the given entry.  */
 240
 241 static rtx
 242 entry_register (struct web_entry *entry, df_ref ref, unsigned int *used)
 243 {
 244   struct web_entry *root;
 245   rtx reg, newreg;
 246
 247   /* Find the corresponding web and see if it has been visited.  */
 248   root = unionfind_root (entry);
 249   if (root->reg)
 250     return root->reg;
 251
 252   /* We are seeing this web for the first time, do the assignment.  */
 253   reg = DF_REF_REAL_REG (ref);
 254
 255   /* In case the original register is already assigned, generate new
 256      one.  Since we use USED to merge uninitialized refs into a single
 257      web, we might found an element to be nonzero without our having
 258      used it.  Test for 1, because union_defs saves it for our use,
 259      and there won't be any use for the other values when we get to
 260      this point.  */
 261   if (used[REGNO (reg)] != 1)
 262     newreg = reg, used[REGNO (reg)] = 1;
 263   else
 264     {
 265       newreg = gen_reg_rtx (GET_MODE (reg));
 266       REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
 267       REG_POINTER (newreg) = REG_POINTER (reg);
 268       REG_ATTRS (newreg) = REG_ATTRS (reg);
 269       if (dump_file)
 270         fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
 271                  REGNO (newreg));
 272     }
 273
 274   root->reg = newreg;
 275   return newreg;
 276 }
 277
 278 /* Replace the reference by REG.  */
 279
 280 static void
 281 replace_ref (df_ref ref, rtx reg)
 282 {
 283   rtx oldreg = DF_REF_REAL_REG (ref);
 284   rtx *loc = DF_REF_REAL_LOC (ref);
 285   unsigned int uid = DF_REF_INSN_UID (ref);
 286
 287   if (oldreg == reg)
 288     return;
 289   if (dump_file)
 290     fprintf (dump_file, "Updating insn %i (%i->%i)\n",
 291              uid, REGNO (oldreg), REGNO (reg));
 292   *loc = reg;
 293   df_insn_rescan (DF_REF_INSN (ref));
 294 }
 295
 296 \f
 297 static bool
 298 gate_handle_web (void)
 299 {
 300   return (optimize > 0 && flag_web);
 301 }
 302
 303 /* Main entry point.  */
 304
 305 static unsigned int
 306 web_main (void)
 307 {
 308   struct web_entry *def_entry;
 309   struct web_entry *use_entry;
 310   unsigned int max = max_reg_num ();
 311   unsigned int *used;
 312   basic_block bb;
 313   unsigned int uses_num = 0;
 314   rtx insn;
 315
 316   df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
 317   df_chain_add_problem (DF_UD_CHAIN);
 318   df_analyze ();
 319   df_set_flags (DF_DEFER_INSN_RESCAN);
 320
 321   /* Assign ids to the uses.  */
 322   FOR_ALL_BB (bb)
 323     FOR_BB_INSNS (bb, insn)
 324     {
 325       unsigned int uid = INSN_UID (insn);
 326       if (NONDEBUG_INSN_P (insn))
 327         {
 328           df_ref *use_rec;
 329           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 330             {
 331               df_ref use = *use_rec;
 332               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 333                 DF_REF_ID (use) = uses_num++;
 334             }
 335           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 336             {
 337               df_ref use = *use_rec;
 338               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 339                 DF_REF_ID (use) = uses_num++;
 340             }
 341         }
 342     }
 343
 344   /* Record the number of uses and defs at the beginning of the optimization.  */
 345   def_entry = XCNEWVEC (struct web_entry, DF_DEFS_TABLE_SIZE());
 346   used = XCNEWVEC (unsigned, max);
 347   use_entry = XCNEWVEC (struct web_entry, uses_num);
 348
 349   /* Produce the web.  */
 350   FOR_ALL_BB (bb)
 351     FOR_BB_INSNS (bb, insn)
 352     {
 353       unsigned int uid = INSN_UID (insn);
 354       if (NONDEBUG_INSN_P (insn))
 355         {
 356           df_ref *use_rec;
 357           union_match_dups (insn, def_entry, use_entry, unionfind_union);
 358           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 359             {
 360               df_ref use = *use_rec;
 361               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 362                 union_defs (use, def_entry, used, use_entry, unionfind_union);
 363             }
 364           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 365             {
 366               df_ref use = *use_rec;
 367               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 368                 union_defs (use, def_entry, used, use_entry, unionfind_union);
 369             }
 370         }
 371     }
 372
 373   /* Update the instruction stream, allocating new registers for split pseudos
 374      in progress.  */
 375   FOR_ALL_BB (bb)
 376     FOR_BB_INSNS (bb, insn)
 377     {
 378       unsigned int uid = INSN_UID (insn);
 379
 380       if (NONDEBUG_INSN_P (insn)
 381           /* Ignore naked clobber.  For example, reg 134 in the second insn
 382              of the following sequence will not be replaced.
 383
 384                (insn (clobber (reg:SI 134)))
 385
 386                (insn (set (reg:SI 0 r0) (reg:SI 134)))
 387
 388              Thus the later passes can optimize them away.  */
 389           && GET_CODE (PATTERN (insn)) != CLOBBER)
 390         {
 391           df_ref *use_rec;
 392           df_ref *def_rec;
 393           for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
 394             {
 395               df_ref use = *use_rec;
 396               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 397                 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
 398             }
 399           for (use_rec = DF_INSN_UID_EQ_USES (uid); *use_rec; use_rec++)
 400             {
 401               df_ref use = *use_rec;
 402               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
 403                 replace_ref (use, entry_register (use_entry + DF_REF_ID (use), use, used));
 404             }
 405           for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 406             {
 407               df_ref def = *def_rec;
 408               if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
 409                 replace_ref (def, entry_register (def_entry + DF_REF_ID (def), def, used));
 410             }
 411         }
 412     }
 413
 414   free (def_entry);
 415   free (use_entry);
 416   free (used);
 417   return 0;
 418 }
 419 \f
 420 struct rtl_opt_pass pass_web =
 421 {
 422  {
 423   RTL_PASS,
 424   "web",                                /* name */
 425   gate_handle_web,                      /* gate */
 426   web_main,                             /* execute */
 427   NULL,                                 /* sub */
 428   NULL,                                 /* next */
 429   0,                                    /* static_pass_number */
 430   TV_WEB,                               /* tv_id */
 431   0,                                    /* properties_required */
 432   0,                                    /* properties_provided */
 433   0,                                    /* properties_destroyed */
 434   0,                                    /* todo_flags_start */
 435   TODO_df_finish | TODO_verify_rtl_sharing  /* todo_flags_finish */
 436  }
 437 };