gcc/postreload-gcse.c

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