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