gcc/postreload-gcse.c

   1 /* Post reload partially redundant load elimination
   2    Copyright (C) 2004-2016 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "backend.h"
  24 #include "target.h"
  25 #include "rtl.h"
  26 #include "tree.h"
  27 #include "predict.h"
  28 #include "df.h"
  29 #include "tm_p.h"
  30 #include "insn-config.h"
  31 #include "emit-rtl.h"
  32 #include "recog.h"
  33
  34 #include "cfgrtl.h"
  35 #include "profile.h"
  36 #include "expr.h"
  37 #include "params.h"
  38 #include "tree-pass.h"
  39 #include "dbgcnt.h"
  40 #include "gcse-common.h"
  41
  42 /* The following code implements gcse after reload, the purpose of this
  43    pass is to cleanup redundant loads generated by reload and other
  44    optimizations that come after gcse. It searches for simple inter-block
  45    redundancies and tries to eliminate them by adding moves and loads
  46    in cold places.
  47
  48    Perform partially redundant load elimination, try to eliminate redundant
  49    loads created by the reload pass.  We try to look for full or partial
  50    redundant loads fed by one or more loads/stores in predecessor BBs,
  51    and try adding loads to make them fully redundant.  We also check if
  52    it's worth adding loads to be able to delete the redundant load.
  53
  54    Algorithm:
  55    1. Build available expressions hash table:
  56        For each load/store instruction, if the loaded/stored memory didn't
  57        change until the end of the basic block add this memory expression to
  58        the hash table.
  59    2. Perform Redundancy elimination:
  60       For each load instruction do the following:
  61          perform partial redundancy elimination, check if it's worth adding
  62          loads to make the load fully redundant.  If so add loads and
  63          register copies and delete the load.
  64    3. Delete instructions made redundant in step 2.
  65
  66    Future enhancement:
  67      If the loaded register is used/defined between load and some store,
  68      look for some other free register between load and all its stores,
  69      and replace the load with a copy from this register to the loaded
  70      register.
  71 */
  72 \f
  73
  74 /* Keep statistics of this pass.  */
  75 static struct
  76 {
  77   int moves_inserted;
  78   int copies_inserted;
  79   int insns_deleted;
  80 } stats;
  81
  82 /* We need to keep a hash table of expressions.  The table entries are of
  83    type 'struct expr', and for each expression there is a single linked
  84    list of occurrences.  */
  85
  86 /* Expression elements in the hash table.  */
  87 struct expr
  88 {
  89   /* The expression (SET_SRC for expressions, PATTERN for assignments).  */
  90   rtx expr;
  91
  92   /* The same hash for this entry.  */
  93   hashval_t hash;
  94
  95   /* Index in the transparent bitmaps.  */
  96   unsigned int bitmap_index;
  97
  98   /* List of available occurrence in basic blocks in the function.  */
  99   struct occr *avail_occr;
 100 };
 101
 102 /* Hashtable helpers.  */
 103
 104 struct expr_hasher : nofree_ptr_hash <expr>
 105 {
 106   static inline hashval_t hash (const expr *);
 107   static inline bool equal (const expr *, const expr *);
 108 };
 109
 110
 111 /* Hash expression X.
 112    DO_NOT_RECORD_P is a boolean indicating if a volatile operand is found
 113    or if the expression contains something we don't want to insert in the
 114    table.  */
 115
 116 static hashval_t
 117 hash_expr (rtx x, int *do_not_record_p)
 118 {
 119   *do_not_record_p = 0;
 120   return hash_rtx (x, GET_MODE (x), do_not_record_p,
 121                    NULL,  /*have_reg_qty=*/false);
 122 }
 123
 124 /* Callback for hashtab.
 125    Return the hash value for expression EXP.  We don't actually hash
 126    here, we just return the cached hash value.  */
 127
 128 inline hashval_t
 129 expr_hasher::hash (const expr *exp)
 130 {
 131   return exp->hash;
 132 }
 133
 134 /* Callback for hashtab.
 135    Return nonzero if exp1 is equivalent to exp2.  */
 136
 137 inline bool
 138 expr_hasher::equal (const expr *exp1, const expr *exp2)
 139 {
 140   int equiv_p = exp_equiv_p (exp1->expr, exp2->expr, 0, true);
 141
 142   gcc_assert (!equiv_p || exp1->hash == exp2->hash);
 143   return equiv_p;
 144 }
 145
 146 /* The table itself.  */
 147 static hash_table<expr_hasher> *expr_table;
 148 \f
 149
 150 static struct obstack expr_obstack;
 151
 152 /* Occurrence of an expression.
 153    There is at most one occurrence per basic block.  If a pattern appears
 154    more than once, the last appearance is used.  */
 155
 156 struct occr
 157 {
 158   /* Next occurrence of this expression.  */
 159   struct occr *next;
 160   /* The insn that computes the expression.  */
 161   rtx_insn *insn;
 162   /* Nonzero if this [anticipatable] occurrence has been deleted.  */
 163   char deleted_p;
 164 };
 165
 166 static struct obstack occr_obstack;
 167
 168 /* The following structure holds the information about the occurrences of
 169    the redundant instructions.  */
 170 struct unoccr
 171 {
 172   struct unoccr *next;
 173   edge pred;
 174   rtx_insn *insn;
 175 };
 176
 177 static struct obstack unoccr_obstack;
 178
 179 /* Array where each element is the CUID if the insn that last set the hard
 180    register with the number of the element, since the start of the current
 181    basic block.
 182
 183    This array is used during the building of the hash table (step 1) to
 184    determine if a reg is killed before the end of a basic block.
 185
 186    It is also used when eliminating partial redundancies (step 2) to see
 187    if a reg was modified since the start of a basic block.  */
 188 static int *reg_avail_info;
 189
 190 /* A list of insns that may modify memory within the current basic block.  */
 191 struct modifies_mem
 192 {
 193   rtx_insn *insn;
 194   struct modifies_mem *next;
 195 };
 196 static struct modifies_mem *modifies_mem_list;
 197
 198 /* The modifies_mem structs also go on an obstack, only this obstack is
 199    freed each time after completing the analysis or transformations on
 200    a basic block.  So we allocate a dummy modifies_mem_obstack_bottom
 201    object on the obstack to keep track of the bottom of the obstack.  */
 202 static struct obstack modifies_mem_obstack;
 203 static struct modifies_mem  *modifies_mem_obstack_bottom;
 204
 205 /* Mapping of insn UIDs to CUIDs.
 206    CUIDs are like UIDs except they increase monotonically in each basic
 207    block, have no gaps, and only apply to real insns.  */
 208 static int *uid_cuid;
 209 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
 210
 211 /* Bitmap of blocks which have memory stores.  */
 212 static bitmap modify_mem_list_set;
 213
 214 /* Bitmap of blocks which have calls.  */
 215 static bitmap blocks_with_calls;
 216
 217 /* Vector indexed by block # with a list of all the insns that
 218    modify memory within the block.  */
 219 static vec<rtx_insn *> *modify_mem_list;
 220
 221 /* Vector indexed by block # with a canonicalized list of insns
 222    that modify memory in the block.  */
 223 static vec<modify_pair> *canon_modify_mem_list;
 224
 225 /* Vector of simple bitmaps indexed by block number.  Each component sbitmap
 226    indicates which expressions are transparent through the block.  */
 227 static sbitmap *transp;
 228 \f
 229
 230 /* Helpers for memory allocation/freeing.  */
 231 static void alloc_mem (void);
 232 static void free_mem (void);
 233
 234 /* Support for hash table construction and transformations.  */
 235 static bool oprs_unchanged_p (rtx, rtx_insn *, bool);
 236 static void record_last_reg_set_info (rtx_insn *, rtx);
 237 static void record_last_reg_set_info_regno (rtx_insn *, int);
 238 static void record_last_mem_set_info (rtx_insn *);
 239 static void record_last_set_info (rtx, const_rtx, void *);
 240 static void record_opr_changes (rtx_insn *);
 241
 242 static void find_mem_conflicts (rtx, const_rtx, void *);
 243 static int load_killed_in_block_p (int, rtx, bool);
 244 static void reset_opr_set_tables (void);
 245
 246 /* Hash table support.  */
 247 static hashval_t hash_expr (rtx, int *);
 248 static void insert_expr_in_table (rtx, rtx_insn *);
 249 static struct expr *lookup_expr_in_table (rtx);
 250 static void dump_hash_table (FILE *);
 251
 252 /* Helpers for eliminate_partially_redundant_load.  */
 253 static bool reg_killed_on_edge (rtx, edge);
 254 static bool reg_used_on_edge (rtx, edge);
 255
 256 static rtx get_avail_load_store_reg (rtx_insn *);
 257
 258 static bool bb_has_well_behaved_predecessors (basic_block);
 259 static struct occr* get_bb_avail_insn (basic_block, struct occr *, int);
 260 static void hash_scan_set (rtx_insn *);
 261 static void compute_hash_table (void);
 262
 263 /* The work horses of this pass.  */
 264 static void eliminate_partially_redundant_load (basic_block,
 265                                                 rtx_insn *,
 266                                                 struct expr *);
 267 static void eliminate_partially_redundant_loads (void);
 268 \f
 269
 270 /* Allocate memory for the CUID mapping array and register/memory
 271    tracking tables.  */
 272
 273 static void
 274 alloc_mem (void)
 275 {
 276   int i;
 277   basic_block bb;
 278   rtx_insn *insn;
 279
 280   /* Find the largest UID and create a mapping from UIDs to CUIDs.  */
 281   uid_cuid = XCNEWVEC (int, get_max_uid () + 1);
 282   i = 1;
 283   FOR_EACH_BB_FN (bb, cfun)
 284     FOR_BB_INSNS (bb, insn)
 285       {
 286         if (INSN_P (insn))
 287           uid_cuid[INSN_UID (insn)] = i++;
 288         else
 289           uid_cuid[INSN_UID (insn)] = i;
 290       }
 291
 292   /* Allocate the available expressions hash table.  We don't want to
 293      make the hash table too small, but unnecessarily making it too large
 294      also doesn't help.  The i/4 is a gcse.c relic, and seems like a
 295      reasonable choice.  */
 296   expr_table = new hash_table<expr_hasher> (MAX (i / 4, 13));
 297
 298   /* We allocate everything on obstacks because we often can roll back
 299      the whole obstack to some point.  Freeing obstacks is very fast.  */
 300   gcc_obstack_init (&expr_obstack);
 301   gcc_obstack_init (&occr_obstack);
 302   gcc_obstack_init (&unoccr_obstack);
 303   gcc_obstack_init (&modifies_mem_obstack);
 304
 305   /* Working array used to track the last set for each register
 306      in the current block.  */
 307   reg_avail_info = (int *) xmalloc (FIRST_PSEUDO_REGISTER * sizeof (int));
 308
 309   /* Put a dummy modifies_mem object on the modifies_mem_obstack, so we
 310      can roll it back in reset_opr_set_tables.  */
 311   modifies_mem_obstack_bottom =
 312     (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack,
 313                                            sizeof (struct modifies_mem));
 314
 315   blocks_with_calls = BITMAP_ALLOC (NULL);
 316   modify_mem_list_set = BITMAP_ALLOC (NULL);
 317
 318   modify_mem_list = (vec_rtx_heap *) xcalloc (last_basic_block_for_fn (cfun),
 319                                               sizeof (vec_rtx_heap));
 320   canon_modify_mem_list
 321     = (vec_modify_pair_heap *) xcalloc (last_basic_block_for_fn (cfun),
 322                                         sizeof (vec_modify_pair_heap));
 323 }
 324
 325 /* Free memory allocated by alloc_mem.  */
 326
 327 static void
 328 free_mem (void)
 329 {
 330   free (uid_cuid);
 331
 332   delete expr_table;
 333   expr_table = NULL;
 334
 335   obstack_free (&expr_obstack, NULL);
 336   obstack_free (&occr_obstack, NULL);
 337   obstack_free (&unoccr_obstack, NULL);
 338   obstack_free (&modifies_mem_obstack, NULL);
 339
 340   unsigned i;
 341   bitmap_iterator bi;
 342   EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set, 0, i, bi)
 343     {
 344       modify_mem_list[i].release ();
 345       canon_modify_mem_list[i].release ();
 346     }
 347
 348   BITMAP_FREE (blocks_with_calls);
 349   BITMAP_FREE (modify_mem_list_set);
 350   free (reg_avail_info);
 351   free (modify_mem_list);
 352   free (canon_modify_mem_list);
 353 }
 354 \f
 355
 356 /* Insert expression X in INSN in the hash TABLE.
 357    If it is already present, record it as the last occurrence in INSN's
 358    basic block.  */
 359
 360 static void
 361 insert_expr_in_table (rtx x, rtx_insn *insn)
 362 {
 363   int do_not_record_p;
 364   hashval_t hash;
 365   struct expr *cur_expr, **slot;
 366   struct occr *avail_occr, *last_occr = NULL;
 367
 368   hash = hash_expr (x, &do_not_record_p);
 369
 370   /* Do not insert expression in the table if it contains volatile operands,
 371      or if hash_expr determines the expression is something we don't want
 372      to or can't handle.  */
 373   if (do_not_record_p)
 374     return;
 375
 376   /* We anticipate that redundant expressions are rare, so for convenience
 377      allocate a new hash table element here already and set its fields.
 378      If we don't do this, we need a hack with a static struct expr.  Anyway,
 379      obstack_free is really fast and one more obstack_alloc doesn't hurt if
 380      we're going to see more expressions later on.  */
 381   cur_expr = (struct expr *) obstack_alloc (&expr_obstack,
 382                                             sizeof (struct expr));
 383   cur_expr->expr = x;
 384   cur_expr->hash = hash;
 385   cur_expr->avail_occr = NULL;
 386
 387   slot = expr_table->find_slot_with_hash (cur_expr, hash, INSERT);
 388
 389   if (! (*slot))
 390     {
 391       /* The expression isn't found, so insert it.  */
 392       *slot = cur_expr;
 393
 394       /* Anytime we add an entry to the table, record the index
 395          of the new entry.  The bitmap index starts counting
 396          at zero.  */
 397       cur_expr->bitmap_index = expr_table->elements () - 1;
 398     }
 399   else
 400     {
 401       /* The expression is already in the table, so roll back the
 402          obstack and use the existing table entry.  */
 403       obstack_free (&expr_obstack, cur_expr);
 404       cur_expr = *slot;
 405     }
 406
 407   /* Search for another occurrence in the same basic block.  */
 408   avail_occr = cur_expr->avail_occr;
 409   while (avail_occr
 410          && BLOCK_FOR_INSN (avail_occr->insn) != BLOCK_FOR_INSN (insn))
 411     {
 412       /* If an occurrence isn't found, save a pointer to the end of
 413          the list.  */
 414       last_occr = avail_occr;
 415       avail_occr = avail_occr->next;
 416     }
 417
 418   if (avail_occr)
 419     /* Found another instance of the expression in the same basic block.
 420        Prefer this occurrence to the currently recorded one.  We want
 421        the last one in the block and the block is scanned from start
 422        to end.  */
 423     avail_occr->insn = insn;
 424   else
 425     {
 426       /* First occurrence of this expression in this basic block.  */
 427       avail_occr = (struct occr *) obstack_alloc (&occr_obstack,
 428                                                   sizeof (struct occr));
 429
 430       /* First occurrence of this expression in any block?  */
 431       if (cur_expr->avail_occr == NULL)
 432         cur_expr->avail_occr = avail_occr;
 433       else
 434         last_occr->next = avail_occr;
 435
 436       avail_occr->insn = insn;
 437       avail_occr->next = NULL;
 438       avail_occr->deleted_p = 0;
 439     }
 440 }
 441 \f
 442
 443 /* Lookup pattern PAT in the expression hash table.
 444    The result is a pointer to the table entry, or NULL if not found.  */
 445
 446 static struct expr *
 447 lookup_expr_in_table (rtx pat)
 448 {
 449   int do_not_record_p;
 450   struct expr **slot, *tmp_expr;
 451   hashval_t hash = hash_expr (pat, &do_not_record_p);
 452
 453   if (do_not_record_p)
 454     return NULL;
 455
 456   tmp_expr = (struct expr *) obstack_alloc (&expr_obstack,
 457                                             sizeof (struct expr));
 458   tmp_expr->expr = pat;
 459   tmp_expr->hash = hash;
 460   tmp_expr->avail_occr = NULL;
 461
 462   slot = expr_table->find_slot_with_hash (tmp_expr, hash, INSERT);
 463   obstack_free (&expr_obstack, tmp_expr);
 464
 465   if (!slot)
 466     return NULL;
 467   else
 468     return (*slot);
 469 }
 470 \f
 471
 472 /* Dump all expressions and occurrences that are currently in the
 473    expression hash table to FILE.  */
 474
 475 /* This helper is called via htab_traverse.  */
 476 int
 477 dump_expr_hash_table_entry (expr **slot, FILE *file)
 478 {
 479   struct expr *exprs = *slot;
 480   struct occr *occr;
 481
 482   fprintf (file, "expr: ");
 483   print_rtl (file, exprs->expr);
 484   fprintf (file,"\nhashcode: %u\n", exprs->hash);
 485   fprintf (file,"list of occurrences:\n");
 486   occr = exprs->avail_occr;
 487   while (occr)
 488     {
 489       rtx_insn *insn = occr->insn;
 490       print_rtl_single (file, insn);
 491       fprintf (file, "\n");
 492       occr = occr->next;
 493     }
 494   fprintf (file, "\n");
 495   return 1;
 496 }
 497
 498 static void
 499 dump_hash_table (FILE *file)
 500 {
 501   fprintf (file, "\n\nexpression hash table\n");
 502   fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
 503            (long) expr_table->size (),
 504            (long) expr_table->elements (),
 505            expr_table->collisions ());
 506   if (expr_table->elements () > 0)
 507     {
 508       fprintf (file, "\n\ntable entries:\n");
 509       expr_table->traverse <FILE *, dump_expr_hash_table_entry> (file);
 510     }
 511   fprintf (file, "\n");
 512 }
 513 \f
 514 /* Return true if register X is recorded as being set by an instruction
 515    whose CUID is greater than the one given.  */
 516
 517 static bool
 518 reg_changed_after_insn_p (rtx x, int cuid)
 519 {
 520   unsigned int regno, end_regno;
 521
 522   regno = REGNO (x);
 523   end_regno = END_REGNO (x);
 524   do
 525     if (reg_avail_info[regno] > cuid)
 526       return true;
 527   while (++regno < end_regno);
 528   return false;
 529 }
 530
 531 /* Return nonzero if the operands of expression X are unchanged
 532    1) from the start of INSN's basic block up to but not including INSN
 533       if AFTER_INSN is false, or
 534    2) from INSN to the end of INSN's basic block if AFTER_INSN is true.  */
 535
 536 static bool
 537 oprs_unchanged_p (rtx x, rtx_insn *insn, bool after_insn)
 538 {
 539   int i, j;
 540   enum rtx_code code;
 541   const char *fmt;
 542
 543   if (x == 0)
 544     return 1;
 545
 546   code = GET_CODE (x);
 547   switch (code)
 548     {
 549     case REG:
 550       /* We are called after register allocation.  */
 551       gcc_assert (REGNO (x) < FIRST_PSEUDO_REGISTER);
 552       if (after_insn)
 553         return !reg_changed_after_insn_p (x, INSN_CUID (insn) - 1);
 554       else
 555         return !reg_changed_after_insn_p (x, 0);
 556
 557     case MEM:
 558       if (load_killed_in_block_p (INSN_CUID (insn), x, after_insn))
 559         return 0;
 560       else
 561         return oprs_unchanged_p (XEXP (x, 0), insn, after_insn);
 562
 563     case PC:
 564     case CC0: /*FIXME*/
 565     case CONST:
 566     CASE_CONST_ANY:
 567     case SYMBOL_REF:
 568     case LABEL_REF:
 569     case ADDR_VEC:
 570     case ADDR_DIFF_VEC:
 571       return 1;
 572
 573     case PRE_DEC:
 574     case PRE_INC:
 575     case POST_DEC:
 576     case POST_INC:
 577     case PRE_MODIFY:
 578     case POST_MODIFY:
 579       if (after_insn)
 580         return 0;
 581       break;
 582
 583     default:
 584       break;
 585     }
 586
 587   for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
 588     {
 589       if (fmt[i] == 'e')
 590         {
 591           if (! oprs_unchanged_p (XEXP (x, i), insn, after_insn))
 592             return 0;
 593         }
 594       else if (fmt[i] == 'E')
 595         for (j = 0; j < XVECLEN (x, i); j++)
 596           if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, after_insn))
 597             return 0;
 598     }
 599
 600   return 1;
 601 }
 602 \f
 603
 604 /* Used for communication between find_mem_conflicts and
 605    load_killed_in_block_p.  Nonzero if find_mem_conflicts finds a
 606    conflict between two memory references.
 607    This is a bit of a hack to work around the limitations of note_stores.  */
 608 static int mems_conflict_p;
 609
 610 /* DEST is the output of an instruction.  If it is a memory reference, and
 611    possibly conflicts with the load found in DATA, then set mems_conflict_p
 612    to a nonzero value.  */
 613
 614 static void
 615 find_mem_conflicts (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
 616                     void *data)
 617 {
 618   rtx mem_op = (rtx) data;
 619
 620   while (GET_CODE (dest) == SUBREG
 621          || GET_CODE (dest) == ZERO_EXTRACT
 622          || GET_CODE (dest) == STRICT_LOW_PART)
 623     dest = XEXP (dest, 0);
 624
 625   /* If DEST is not a MEM, then it will not conflict with the load.  Note
 626      that function calls are assumed to clobber memory, but are handled
 627      elsewhere.  */
 628   if (! MEM_P (dest))
 629     return;
 630
 631   if (true_dependence (dest, GET_MODE (dest), mem_op))
 632     mems_conflict_p = 1;
 633 }
 634 \f
 635
 636 /* Return nonzero if the expression in X (a memory reference) is killed
 637    in the current basic block before (if AFTER_INSN is false) or after
 638    (if AFTER_INSN is true) the insn with the CUID in UID_LIMIT.
 639
 640    This function assumes that the modifies_mem table is flushed when
 641    the hash table construction or redundancy elimination phases start
 642    processing a new basic block.  */
 643
 644 static int
 645 load_killed_in_block_p (int uid_limit, rtx x, bool after_insn)
 646 {
 647   struct modifies_mem *list_entry = modifies_mem_list;
 648
 649   while (list_entry)
 650     {
 651       rtx_insn *setter = list_entry->insn;
 652
 653       /* Ignore entries in the list that do not apply.  */
 654       if ((after_insn
 655            && INSN_CUID (setter) < uid_limit)
 656           || (! after_insn
 657               && INSN_CUID (setter) > uid_limit))
 658         {
 659           list_entry = list_entry->next;
 660           continue;
 661         }
 662
 663       /* If SETTER is a call everything is clobbered.  Note that calls
 664          to pure functions are never put on the list, so we need not
 665          worry about them.  */
 666       if (CALL_P (setter))
 667         return 1;
 668
 669       /* SETTER must be an insn of some kind that sets memory.  Call
 670          note_stores to examine each hunk of memory that is modified.
 671          It will set mems_conflict_p to nonzero if there may be a
 672          conflict between X and SETTER.  */
 673       mems_conflict_p = 0;
 674       note_stores (PATTERN (setter), find_mem_conflicts, x);
 675       if (mems_conflict_p)
 676         return 1;
 677
 678       list_entry = list_entry->next;
 679     }
 680   return 0;
 681 }
 682 \f
 683
 684 /* Record register first/last/block set information for REGNO in INSN.  */
 685
 686 static inline void
 687 record_last_reg_set_info (rtx_insn *insn, rtx reg)
 688 {
 689   unsigned int regno, end_regno;
 690
 691   regno = REGNO (reg);
 692   end_regno = END_REGNO (reg);
 693   do
 694     reg_avail_info[regno] = INSN_CUID (insn);
 695   while (++regno < end_regno);
 696 }
 697
 698 static inline void
 699 record_last_reg_set_info_regno (rtx_insn *insn, int regno)
 700 {
 701   reg_avail_info[regno] = INSN_CUID (insn);
 702 }
 703
 704
 705 /* Record memory modification information for INSN.  We do not actually care
 706    about the memory location(s) that are set, or even how they are set (consider
 707    a CALL_INSN).  We merely need to record which insns modify memory.  */
 708
 709 static void
 710 record_last_mem_set_info (rtx_insn *insn)
 711 {
 712   struct modifies_mem *list_entry;
 713
 714   list_entry = (struct modifies_mem *) obstack_alloc (&modifies_mem_obstack,
 715                                                       sizeof (struct modifies_mem));
 716   list_entry->insn = insn;
 717   list_entry->next = modifies_mem_list;
 718   modifies_mem_list = list_entry;
 719
 720   record_last_mem_set_info_common (insn, modify_mem_list,
 721                                    canon_modify_mem_list,
 722                                    modify_mem_list_set,
 723                                    blocks_with_calls);
 724 }
 725
 726 /* Called from compute_hash_table via note_stores to handle one
 727    SET or CLOBBER in an insn.  DATA is really the instruction in which
 728    the SET is taking place.  */
 729
 730 static void
 731 record_last_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data)
 732 {
 733   rtx_insn *last_set_insn = (rtx_insn *) data;
 734
 735   if (GET_CODE (dest) == SUBREG)
 736     dest = SUBREG_REG (dest);
 737
 738   if (REG_P (dest))
 739     record_last_reg_set_info (last_set_insn, dest);
 740   else if (MEM_P (dest))
 741     {
 742       /* Ignore pushes, they don't clobber memory.  They may still
 743          clobber the stack pointer though.  Some targets do argument
 744          pushes without adding REG_INC notes.  See e.g. PR25196,
 745          where a pushsi2 on i386 doesn't have REG_INC notes.  Note
 746          such changes here too.  */
 747       if (! push_operand (dest, GET_MODE (dest)))
 748         record_last_mem_set_info (last_set_insn);
 749       else
 750         record_last_reg_set_info_regno (last_set_insn, STACK_POINTER_REGNUM);
 751     }
 752 }
 753
 754
 755 /* Reset tables used to keep track of what's still available since the
 756    start of the block.  */
 757
 758 static void
 759 reset_opr_set_tables (void)
 760 {
 761   memset (reg_avail_info, 0, FIRST_PSEUDO_REGISTER * sizeof (int));
 762   obstack_free (&modifies_mem_obstack, modifies_mem_obstack_bottom);
 763   modifies_mem_list = NULL;
 764 }
 765 \f
 766
 767 /* Record things set by INSN.
 768    This data is used by oprs_unchanged_p.  */
 769
 770 static void
 771 record_opr_changes (rtx_insn *insn)
 772 {
 773   rtx note;
 774
 775   /* Find all stores and record them.  */
 776   note_stores (PATTERN (insn), record_last_set_info, insn);
 777
 778   /* Also record autoincremented REGs for this insn as changed.  */
 779   for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 780     if (REG_NOTE_KIND (note) == REG_INC)
 781       record_last_reg_set_info (insn, XEXP (note, 0));
 782
 783   /* Finally, if this is a call, record all call clobbers.  */
 784   if (CALL_P (insn))
 785     {
 786       unsigned int regno;
 787       rtx link, x;
 788       hard_reg_set_iterator hrsi;
 789       EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call, 0, regno, hrsi)
 790         record_last_reg_set_info_regno (insn, regno);
 791
 792       for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
 793         if (GET_CODE (XEXP (link, 0)) == CLOBBER)
 794           {
 795             x = XEXP (XEXP (link, 0), 0);
 796             if (REG_P (x))
 797               {
 798                 gcc_assert (HARD_REGISTER_P (x));
 799                 record_last_reg_set_info (insn, x);
 800               }
 801           }
 802
 803       if (! RTL_CONST_OR_PURE_CALL_P (insn))
 804         record_last_mem_set_info (insn);
 805     }
 806 }
 807 \f
 808
 809 /* Scan the pattern of INSN and add an entry to the hash TABLE.
 810    After reload we are interested in loads/stores only.  */
 811
 812 static void
 813 hash_scan_set (rtx_insn *insn)
 814 {
 815   rtx pat = PATTERN (insn);
 816   rtx src = SET_SRC (pat);
 817   rtx dest = SET_DEST (pat);
 818
 819   /* We are only interested in loads and stores.  */
 820   if (! MEM_P (src) && ! MEM_P (dest))
 821     return;
 822
 823   /* Don't mess with jumps and nops.  */
 824   if (JUMP_P (insn) || set_noop_p (pat))
 825     return;
 826
 827   if (REG_P (dest))
 828     {
 829       if (/* Don't CSE something if we can't do a reg/reg copy.  */
 830           can_copy_p (GET_MODE (dest))
 831           /* Is SET_SRC something we want to gcse?  */
 832           && general_operand (src, GET_MODE (src))
 833 #ifdef STACK_REGS
 834           /* Never consider insns touching the register stack.  It may
 835              create situations that reg-stack cannot handle (e.g. a stack
 836              register live across an abnormal edge).  */
 837           && (REGNO (dest) < FIRST_STACK_REG || REGNO (dest) > LAST_STACK_REG)
 838 #endif
 839           /* An expression is not available if its operands are
 840              subsequently modified, including this insn.  */
 841           && oprs_unchanged_p (src, insn, true))
 842         {
 843           insert_expr_in_table (src, insn);
 844         }
 845     }
 846   else if (REG_P (src))
 847     {
 848       /* Only record sets of pseudo-regs in the hash table.  */
 849       if (/* Don't CSE something if we can't do a reg/reg copy.  */
 850           can_copy_p (GET_MODE (src))
 851           /* Is SET_DEST something we want to gcse?  */
 852           && general_operand (dest, GET_MODE (dest))
 853 #ifdef STACK_REGS
 854           /* As above for STACK_REGS.  */
 855           && (REGNO (src) < FIRST_STACK_REG || REGNO (src) > LAST_STACK_REG)
 856 #endif
 857           && ! (flag_float_store && FLOAT_MODE_P (GET_MODE (dest)))
 858           /* Check if the memory expression is killed after insn.  */
 859           && ! load_killed_in_block_p (INSN_CUID (insn) + 1, dest, true)
 860           && oprs_unchanged_p (XEXP (dest, 0), insn, true))
 861         {
 862           insert_expr_in_table (dest, insn);
 863         }
 864     }
 865 }
 866 \f
 867
 868 /* Create hash table of memory expressions available at end of basic
 869    blocks.  Basically you should think of this hash table as the
 870    representation of AVAIL_OUT.  This is the set of expressions that
 871    is generated in a basic block and not killed before the end of the
 872    same basic block.  Notice that this is really a local computation.  */
 873
 874 static void
 875 compute_hash_table (void)
 876 {
 877   basic_block bb;
 878
 879   FOR_EACH_BB_FN (bb, cfun)
 880     {
 881       rtx_insn *insn;
 882
 883       /* First pass over the instructions records information used to
 884          determine when registers and memory are last set.
 885          Since we compute a "local" AVAIL_OUT, reset the tables that
 886          help us keep track of what has been modified since the start
 887          of the block.  */
 888       reset_opr_set_tables ();
 889       FOR_BB_INSNS (bb, insn)
 890         {
 891           if (INSN_P (insn))
 892             record_opr_changes (insn);
 893         }
 894
 895       /* The next pass actually builds the hash table.  */
 896       FOR_BB_INSNS (bb, insn)
 897         if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == SET)
 898           hash_scan_set (insn);
 899     }
 900 }
 901 \f
 902
 903 /* Check if register REG is killed in any insn waiting to be inserted on
 904    edge E.  This function is required to check that our data flow analysis
 905    is still valid prior to commit_edge_insertions.  */
 906
 907 static bool
 908 reg_killed_on_edge (rtx reg, edge e)
 909 {
 910   rtx_insn *insn;
 911
 912   for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
 913     if (INSN_P (insn) && reg_set_p (reg, insn))
 914       return true;
 915
 916   return false;
 917 }
 918
 919 /* Similar to above - check if register REG is used in any insn waiting
 920    to be inserted on edge E.
 921    Assumes no such insn can be a CALL_INSN; if so call reg_used_between_p
 922    with PREV(insn),NEXT(insn) instead of calling reg_overlap_mentioned_p.  */
 923
 924 static bool
 925 reg_used_on_edge (rtx reg, edge e)
 926 {
 927   rtx_insn *insn;
 928
 929   for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
 930     if (INSN_P (insn) && reg_overlap_mentioned_p (reg, PATTERN (insn)))
 931       return true;
 932
 933   return false;
 934 }
 935 \f
 936 /* Return the loaded/stored register of a load/store instruction.  */
 937
 938 static rtx
 939 get_avail_load_store_reg (rtx_insn *insn)
 940 {
 941   if (REG_P (SET_DEST (PATTERN (insn))))
 942     /* A load.  */
 943     return SET_DEST (PATTERN (insn));
 944   else
 945     {
 946       /* A store.  */
 947       gcc_assert (REG_P (SET_SRC (PATTERN (insn))));
 948       return SET_SRC (PATTERN (insn));
 949     }
 950 }
 951
 952 /* Return nonzero if the predecessors of BB are "well behaved".  */
 953
 954 static bool
 955 bb_has_well_behaved_predecessors (basic_block bb)
 956 {
 957   edge pred;
 958   edge_iterator ei;
 959
 960   if (EDGE_COUNT (bb->preds) == 0)
 961     return false;
 962
 963   FOR_EACH_EDGE (pred, ei, bb->preds)
 964     {
 965       if ((pred->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (pred))
 966         return false;
 967
 968       if ((pred->flags & EDGE_ABNORMAL_CALL) && cfun->has_nonlocal_label)
 969         return false;
 970
 971       if (tablejump_p (BB_END (pred->src), NULL, NULL))
 972         return false;
 973     }
 974   return true;
 975 }
 976
 977
 978 /* Search for the occurrences of expression in BB.  */
 979
 980 static struct occr*
 981 get_bb_avail_insn (basic_block bb, struct occr *orig_occr, int bitmap_index)
 982 {
 983   struct occr *occr = orig_occr;
 984
 985   for (; occr != NULL; occr = occr->next)
 986     if (BLOCK_FOR_INSN (occr->insn) == bb)
 987       return occr;
 988
 989   /* If we could not find an occurrence in BB, see if BB
 990      has a single predecessor with an occurrence that is
 991      transparent through BB.  */
 992   if (single_pred_p (bb)
 993       && bitmap_bit_p (transp[bb->index], bitmap_index)
 994       && (occr = get_bb_avail_insn (single_pred (bb), orig_occr, bitmap_index)))
 995     {
 996       rtx avail_reg = get_avail_load_store_reg (occr->insn);
 997       if (!reg_set_between_p (avail_reg,
 998                               PREV_INSN (BB_HEAD (bb)),
 999                               NEXT_INSN (BB_END (bb)))
1000           && !reg_killed_on_edge (avail_reg, single_pred_edge (bb)))
1001         return occr;
1002     }
1003
1004   return NULL;
1005 }
1006
1007
1008 /* This helper is called via htab_traverse.  */
1009 int
1010 compute_expr_transp (expr **slot, FILE *dump_file ATTRIBUTE_UNUSED)
1011 {
1012   struct expr *expr = *slot;
1013
1014   compute_transp (expr->expr, expr->bitmap_index, transp,
1015                   blocks_with_calls, modify_mem_list_set,
1016                   canon_modify_mem_list);
1017   return 1;
1018 }
1019
1020 /* This handles the case where several stores feed a partially redundant
1021    load. It checks if the redundancy elimination is possible and if it's
1022    worth it.
1023
1024    Redundancy elimination is possible if,
1025    1) None of the operands of an insn have been modified since the start
1026       of the current basic block.
1027    2) In any predecessor of the current basic block, the same expression
1028       is generated.
1029
1030    See the function body for the heuristics that determine if eliminating
1031    a redundancy is also worth doing, assuming it is possible.  */
1032
1033 static void
1034 eliminate_partially_redundant_load (basic_block bb, rtx_insn *insn,
1035                                     struct expr *expr)
1036 {
1037   edge pred;
1038   rtx_insn *avail_insn = NULL;
1039   rtx avail_reg;
1040   rtx dest, pat;
1041   struct occr *a_occr;
1042   struct unoccr *occr, *avail_occrs = NULL;
1043   struct unoccr *unoccr, *unavail_occrs = NULL, *rollback_unoccr = NULL;
1044   int npred_ok = 0;
1045   gcov_type ok_count = 0; /* Redundant load execution count.  */
1046   gcov_type critical_count = 0; /* Execution count of critical edges.  */
1047   edge_iterator ei;
1048   bool critical_edge_split = false;
1049
1050   /* The execution count of the loads to be added to make the
1051      load fully redundant.  */
1052   gcov_type not_ok_count = 0;
1053   basic_block pred_bb;
1054
1055   pat = PATTERN (insn);
1056   dest = SET_DEST (pat);
1057
1058   /* Check that the loaded register is not used, set, or killed from the
1059      beginning of the block.  */
1060   if (reg_changed_after_insn_p (dest, 0)
1061       || reg_used_between_p (dest, PREV_INSN (BB_HEAD (bb)), insn))
1062     return;
1063
1064   /* Check potential for replacing load with copy for predecessors.  */
1065   FOR_EACH_EDGE (pred, ei, bb->preds)
1066     {
1067       rtx_insn *next_pred_bb_end;
1068
1069       avail_insn = NULL;
1070       avail_reg = NULL_RTX;
1071       pred_bb = pred->src;
1072       for (a_occr = get_bb_avail_insn (pred_bb,
1073                                        expr->avail_occr,
1074                                        expr->bitmap_index);
1075            a_occr;
1076            a_occr = get_bb_avail_insn (pred_bb,
1077                                        a_occr->next,
1078                                        expr->bitmap_index))
1079         {
1080           /* Check if the loaded register is not used.  */
1081           avail_insn = a_occr->insn;
1082           avail_reg = get_avail_load_store_reg (avail_insn);
1083           gcc_assert (avail_reg);
1084
1085           /* Make sure we can generate a move from register avail_reg to
1086              dest.  */
1087           rtx_insn *move = gen_move_insn (copy_rtx (dest),
1088                                           copy_rtx (avail_reg));
1089           extract_insn (move);
1090           if (! constrain_operands (1, get_preferred_alternatives (insn,
1091                                                                    pred_bb))
1092               || reg_killed_on_edge (avail_reg, pred)
1093               || reg_used_on_edge (dest, pred))
1094             {
1095               avail_insn = NULL;
1096               continue;
1097             }
1098           next_pred_bb_end = NEXT_INSN (BB_END (BLOCK_FOR_INSN (avail_insn)));
1099           if (!reg_set_between_p (avail_reg, avail_insn, next_pred_bb_end))
1100             /* AVAIL_INSN remains non-null.  */
1101             break;
1102           else
1103             avail_insn = NULL;
1104         }
1105
1106       if (EDGE_CRITICAL_P (pred))
1107         critical_count += pred->count;
1108
1109       if (avail_insn != NULL_RTX)
1110         {
1111           npred_ok++;
1112           ok_count += pred->count;
1113           if (! set_noop_p (PATTERN (gen_move_insn (copy_rtx (dest),
1114                                                     copy_rtx (avail_reg)))))
1115             {
1116               /* Check if there is going to be a split.  */
1117               if (EDGE_CRITICAL_P (pred))
1118                 critical_edge_split = true;
1119             }
1120           else /* Its a dead move no need to generate.  */
1121             continue;
1122           occr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
1123                                                   sizeof (struct unoccr));
1124           occr->insn = avail_insn;
1125           occr->pred = pred;
1126           occr->next = avail_occrs;
1127           avail_occrs = occr;
1128           if (! rollback_unoccr)
1129             rollback_unoccr = occr;
1130         }
1131       else
1132         {
1133           /* Adding a load on a critical edge will cause a split.  */
1134           if (EDGE_CRITICAL_P (pred))
1135             critical_edge_split = true;
1136           not_ok_count += pred->count;
1137           unoccr = (struct unoccr *) obstack_alloc (&unoccr_obstack,
1138                                                     sizeof (struct unoccr));
1139           unoccr->insn = NULL;
1140           unoccr->pred = pred;
1141           unoccr->next = unavail_occrs;
1142           unavail_occrs = unoccr;
1143           if (! rollback_unoccr)
1144             rollback_unoccr = unoccr;
1145         }
1146     }
1147
1148   if (/* No load can be replaced by copy.  */
1149       npred_ok == 0
1150       /* Prevent exploding the code.  */
1151       || (optimize_bb_for_size_p (bb) && npred_ok > 1)
1152       /* If we don't have profile information we cannot tell if splitting
1153          a critical edge is profitable or not so don't do it.  */
1154       || ((! profile_info || ! flag_branch_probabilities
1155            || targetm.cannot_modify_jumps_p ())
1156           && critical_edge_split))
1157     goto cleanup;
1158
1159   /* Check if it's worth applying the partial redundancy elimination.  */
1160   if (ok_count < GCSE_AFTER_RELOAD_PARTIAL_FRACTION * not_ok_count)
1161     goto cleanup;
1162   if (ok_count < GCSE_AFTER_RELOAD_CRITICAL_FRACTION * critical_count)
1163     goto cleanup;
1164
1165   /* Generate moves to the loaded register from where
1166      the memory is available.  */
1167   for (occr = avail_occrs; occr; occr = occr->next)
1168     {
1169       avail_insn = occr->insn;
1170       pred = occr->pred;
1171       /* Set avail_reg to be the register having the value of the
1172          memory.  */
1173       avail_reg = get_avail_load_store_reg (avail_insn);
1174       gcc_assert (avail_reg);
1175
1176       insert_insn_on_edge (gen_move_insn (copy_rtx (dest),
1177                                           copy_rtx (avail_reg)),
1178                            pred);
1179       stats.moves_inserted++;
1180
1181       if (dump_file)
1182         fprintf (dump_file,
1183                  "generating move from %d to %d on edge from %d to %d\n",
1184                  REGNO (avail_reg),
1185                  REGNO (dest),
1186                  pred->src->index,
1187                  pred->dest->index);
1188     }
1189
1190   /* Regenerate loads where the memory is unavailable.  */
1191   for (unoccr = unavail_occrs; unoccr; unoccr = unoccr->next)
1192     {
1193       pred = unoccr->pred;
1194       insert_insn_on_edge (copy_insn (PATTERN (insn)), pred);
1195       stats.copies_inserted++;
1196
1197       if (dump_file)
1198         {
1199           fprintf (dump_file,
1200                    "generating on edge from %d to %d a copy of load: ",
1201                    pred->src->index,
1202                    pred->dest->index);
1203           print_rtl (dump_file, PATTERN (insn));
1204           fprintf (dump_file, "\n");
1205         }
1206     }
1207
1208   /* Delete the insn if it is not available in this block and mark it
1209      for deletion if it is available. If insn is available it may help
1210      discover additional redundancies, so mark it for later deletion.  */
1211   for (a_occr = get_bb_avail_insn (bb, expr->avail_occr, expr->bitmap_index);
1212        a_occr && (a_occr->insn != insn);
1213        a_occr = get_bb_avail_insn (bb, a_occr->next, expr->bitmap_index))
1214     ;
1215
1216   if (!a_occr)
1217     {
1218       stats.insns_deleted++;
1219
1220       if (dump_file)
1221         {
1222           fprintf (dump_file, "deleting insn:\n");
1223           print_rtl_single (dump_file, insn);
1224           fprintf (dump_file, "\n");
1225         }
1226       delete_insn (insn);
1227     }
1228   else
1229     a_occr->deleted_p = 1;
1230
1231 cleanup:
1232   if (rollback_unoccr)
1233     obstack_free (&unoccr_obstack, rollback_unoccr);
1234 }
1235
1236 /* Performing the redundancy elimination as described before.  */
1237
1238 static void
1239 eliminate_partially_redundant_loads (void)
1240 {
1241   rtx_insn *insn;
1242   basic_block bb;
1243
1244   /* Note we start at block 1.  */
1245
1246   if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1247     return;
1248
1249   FOR_BB_BETWEEN (bb,
1250                   ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
1251                   EXIT_BLOCK_PTR_FOR_FN (cfun),
1252                   next_bb)
1253     {
1254       /* Don't try anything on basic blocks with strange predecessors.  */
1255       if (! bb_has_well_behaved_predecessors (bb))
1256         continue;
1257
1258       /* Do not try anything on cold basic blocks.  */
1259       if (optimize_bb_for_size_p (bb))
1260         continue;
1261
1262       /* Reset the table of things changed since the start of the current
1263          basic block.  */
1264       reset_opr_set_tables ();
1265
1266       /* Look at all insns in the current basic block and see if there are
1267          any loads in it that we can record.  */
1268       FOR_BB_INSNS (bb, insn)
1269         {
1270           /* Is it a load - of the form (set (reg) (mem))?  */
1271           if (NONJUMP_INSN_P (insn)
1272               && GET_CODE (PATTERN (insn)) == SET
1273               && REG_P (SET_DEST (PATTERN (insn)))
1274               && MEM_P (SET_SRC (PATTERN (insn))))
1275             {
1276               rtx pat = PATTERN (insn);
1277               rtx src = SET_SRC (pat);
1278               struct expr *expr;
1279
1280               if (!MEM_VOLATILE_P (src)
1281                   && GET_MODE (src) != BLKmode
1282                   && general_operand (src, GET_MODE (src))
1283                   /* Are the operands unchanged since the start of the
1284                      block?  */
1285                   && oprs_unchanged_p (src, insn, false)
1286                   && !(cfun->can_throw_non_call_exceptions && may_trap_p (src))
1287                   && !side_effects_p (src)
1288                   /* Is the expression recorded?  */
1289                   && (expr = lookup_expr_in_table (src)) != NULL)
1290                 {
1291                   /* We now have a load (insn) and an available memory at
1292                      its BB start (expr). Try to remove the loads if it is
1293                      redundant.  */
1294                   eliminate_partially_redundant_load (bb, insn, expr);
1295                 }
1296             }
1297
1298           /* Keep track of everything modified by this insn, so that we
1299              know what has been modified since the start of the current
1300              basic block.  */
1301           if (INSN_P (insn))
1302             record_opr_changes (insn);
1303         }
1304     }
1305
1306   commit_edge_insertions ();
1307 }
1308
1309 /* Go over the expression hash table and delete insns that were
1310    marked for later deletion.  */
1311
1312 /* This helper is called via htab_traverse.  */
1313 int
1314 delete_redundant_insns_1 (expr **slot, void *data ATTRIBUTE_UNUSED)
1315 {
1316   struct expr *exprs = *slot;
1317   struct occr *occr;
1318
1319   for (occr = exprs->avail_occr; occr != NULL; occr = occr->next)
1320     {
1321       if (occr->deleted_p && dbg_cnt (gcse2_delete))
1322         {
1323           delete_insn (occr->insn);
1324           stats.insns_deleted++;
1325
1326           if (dump_file)
1327             {
1328               fprintf (dump_file, "deleting insn:\n");
1329               print_rtl_single (dump_file, occr->insn);
1330               fprintf (dump_file, "\n");
1331             }
1332         }
1333     }
1334
1335   return 1;
1336 }
1337
1338 static void
1339 delete_redundant_insns (void)
1340 {
1341   expr_table->traverse <void *, delete_redundant_insns_1> (NULL);
1342   if (dump_file)
1343     fprintf (dump_file, "\n");
1344 }
1345
1346 /* Main entry point of the GCSE after reload - clean some redundant loads
1347    due to spilling.  */
1348
1349 static void
1350 gcse_after_reload_main (rtx f ATTRIBUTE_UNUSED)
1351 {
1352
1353   memset (&stats, 0, sizeof (stats));
1354
1355   /* Allocate memory for this pass.
1356      Also computes and initializes the insns' CUIDs.  */
1357   alloc_mem ();
1358
1359   /* We need alias analysis.  */
1360   init_alias_analysis ();
1361
1362   compute_hash_table ();
1363
1364   if (dump_file)
1365     dump_hash_table (dump_file);
1366
1367   if (expr_table->elements () > 0)
1368     {
1369       /* Knowing which MEMs are transparent through a block can signifiantly
1370          increase the number of redundant loads found.  So compute transparency
1371          information for each memory expression in the hash table.  */
1372       df_analyze ();
1373       /* This can not be part of the normal allocation routine because
1374          we have to know the number of elements in the hash table.  */
1375       transp = sbitmap_vector_alloc (last_basic_block_for_fn (cfun),
1376                                      expr_table->elements ());
1377       bitmap_vector_ones (transp, last_basic_block_for_fn (cfun));
1378       expr_table->traverse <FILE *, compute_expr_transp> (dump_file);
1379       eliminate_partially_redundant_loads ();
1380       delete_redundant_insns ();
1381       sbitmap_vector_free (transp);
1382
1383       if (dump_file)
1384         {
1385           fprintf (dump_file, "GCSE AFTER RELOAD stats:\n");
1386           fprintf (dump_file, "copies inserted: %d\n", stats.copies_inserted);
1387           fprintf (dump_file, "moves inserted:  %d\n", stats.moves_inserted);
1388           fprintf (dump_file, "insns deleted:   %d\n", stats.insns_deleted);
1389           fprintf (dump_file, "\n\n");
1390         }
1391
1392       statistics_counter_event (cfun, "copies inserted",
1393                                 stats.copies_inserted);
1394       statistics_counter_event (cfun, "moves inserted",
1395                                 stats.moves_inserted);
1396       statistics_counter_event (cfun, "insns deleted",
1397                                 stats.insns_deleted);
1398     }
1399
1400   /* We are finished with alias.  */
1401   end_alias_analysis ();
1402
1403   free_mem ();
1404 }
1405
1406 \f
1407
1408 static unsigned int
1409 rest_of_handle_gcse2 (void)
1410 {
1411   gcse_after_reload_main (get_insns ());
1412   rebuild_jump_labels (get_insns ());
1413   return 0;
1414 }
1415
1416 namespace {
1417
1418 const pass_data pass_data_gcse2 =
1419 {
1420   RTL_PASS, /* type */
1421   "gcse2", /* name */
1422   OPTGROUP_NONE, /* optinfo_flags */
1423   TV_GCSE_AFTER_RELOAD, /* tv_id */
1424   0, /* properties_required */
1425   0, /* properties_provided */
1426   0, /* properties_destroyed */
1427   0, /* todo_flags_start */
1428   0, /* todo_flags_finish */
1429 };
1430
1431 class pass_gcse2 : public rtl_opt_pass
1432 {
1433 public:
1434   pass_gcse2 (gcc::context *ctxt)
1435     : rtl_opt_pass (pass_data_gcse2, ctxt)
1436   {}
1437
1438   /* opt_pass methods: */
1439   virtual bool gate (function *fun)
1440     {
1441       return (optimize > 0 && flag_gcse_after_reload
1442               && optimize_function_for_speed_p (fun));
1443     }
1444
1445   virtual unsigned int execute (function *) { return rest_of_handle_gcse2 (); }
1446
1447 }; // class pass_gcse2
1448
1449 } // anon namespace
1450
1451 rtl_opt_pass *
1452 make_pass_gcse2 (gcc::context *ctxt)
1453 {
1454   return new pass_gcse2 (ctxt);
1455 }