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