gcc/postreload-gcse.c

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